Method and apparatus for audio editing incorporating visual comparison5675778Abstract A method and apparatus for storing and retrieving visual representations of audio in real-time. The system generates a plurality of sets of waveform display data from a digital audio signal and stores the display data in addition to the audio signal. In the preferred embodiment, each set of waveform display data describes a different time scale representation of the audio signal. The system can edit and playback the audio signal from the visual presentations described by the waveform display data sets. The system implements a file management system to relate each set of data describing the visual representations and the audio signal. Claims What is claimed is: Description FIELD OF THE INVENTION
______________________________________
ConvertLoop:; // return here for next sample
while (|ConverterReady0)
// wait for converter to be ready;
int SAMPLE = ReadConverter0;
// read one sample
______________________________________
The digital processor 20 then compares the value of SAMPLE with the values of MIN and MAX. If SAMPLE is smaller than MIN, then the processor 20 copies the value of SAMPLE into MIN. Likewise, if SAMPLE is greater than MAX, the processor 20 copies the value of SAMPLE into MAX. The digital audio sample is then stored on a digital storage device 9 of some kind (for example: a hard disk drive).
______________________________________
if (SAMPLE<MIN) // compute minimum
MIN = SAMPLE;
if (SAMPLE>MAX) // compute maximum
MAX = SAMPLE;
FileWriteInt(SampleFile, SAMPLE):
// store raw sample to disk
______________________________________
The variable COUNT is then incremented by 1. If COUNT is less than 256, the computer branches back to analyze another converter sample.
______________________________________
COUNT+=1; //increment loop counter
if (COUNT<256) //process more data until done
goto ConvertLoop ;
______________________________________
At the end of processing 256 samples in the way described, the variable MIN will hold the value of the smallest of the 256 samples converted and MAX will hold the value of the largest of the 256 samples converted. The values of MIN and MAX could be used to display to the user a vertical line on the computer screen 10 that is proportional to the loudness of the audio signal represented by the 256 samples that were analyzed. These values of and M and MAX are also written to disk 9, along with the audio samples, so that a visual representation of the audio can easily and quickly be constructed.
______________________________________
FileWriteInt(ImageFile, MIN);
//write image data to disk
FileWriteInt(ImageFile, MAX);
______________________________________
II. Recalling a Visual Representation to the Screen There are two basic computational methods that can be used to present a visual representation of digital audio on a computer screen. The first method, called simply plotting, involves connected points on the screen with line segments. This method is particularly suitable for drawing a visual representation from the actual raw digital audio data itself. FIG. 14 presents a flowchart of this process. 1. PLOTTING DIGITAL AUDIO The flowchart shown in FIG. 14 describes how a digital processor constructs a visual representation of the raw audio samples that were stored to disk by the Waveform Generator 3 described above. Plotting may be thought of as being performed on a simple piece of graph paper. The horizontal, or X, axis runs from left to right. Each vertical line on the graph paper is associated with a number beginning with zero (for the left-most line on the graph paper) and incrementing by 1 for each line to the right; these lines are perpendicular to the X axis. The Y axis runs vertically from the bottom of the graph paper to the top of the graph paper. Normally, the number 0 is associated with the horizontal line located in the middle of the graph paper (e.g., located half way between the top of the graph paper and the bottom of the graph paper). Thus, negative numbers (beginning with -1) are associated with lines below this middle line, and positive numbers (beginning with +1) are associated with lines above the middle line. Of course, plotting is more usefully done on a computer video screen positioned in front of the user instead of on graph paper. Numerous electronic plotting methods are available and described by companies that manufacture computer screens. The flowchart of FIG. 14 describes how the digital processor would read through the digital samples that were stored to disk 9 by the Waveform Generator 3 and construct a visual representation of these samples by plotting a series of line segments on the computer screen 10. The processor 5 would read each sample from disk 9 and plot one line segment on the screen 10 for each sample. Plotting the raw audio samples as proposed in the Flowchart of FIG. 14 is useful for presenting very short segments of audio (one the order of one hundredth of a second or so) to the user. Presenting several seconds of recorded audio by simply plotting them is very time consuming for the computer and tedious for the user. Plotting is simple to implement and is sufficient for short segments of digital audio. Plotting is much less useful for presenting longer segments of audio (greater than 1/2 second) due to the large amount of digital audio data that must be processed. 2. CONSTRUCTING A VISUAL DISPLAY FROM MINIMUM AND MAXIMUM DATA VALUES The second method for presenting a visual representation of digital audio on a computer screen involves reading through compressed visual display data that had been generated and stored according to the Waveform Generator flowchart shown in FIG. 13. To present the Waveform, the compressed data is expanded using a preferred method for Data Expansion shown in the flowchart of FIG. 15. The Data Expansion flowchart presented in FIG. 15 describes a processing technique that can be used by digital processor 5 to easily and quickly construct a visual representation of a large volume of digital audio samples to the user. As the flowchart describes, the computer initializes the current plotting position (normally to X=0, which represents the left edge of the computer screen). The computer then reads a minimum and a maximum value that had previously been computed by the Waveform Generator 3 described above. Each pair which is read consists of one minimum and one maximum value encodes the signal level of the audio over the 256 raw audio samples that were analyzed to compute the minimum and maximum values. The computer constructs the visual representation by plotting a vertical line for each (minimum, maximum) pair. As the flowchart explains, the computer reads a (minimum, maximum) pair from the disk 9 (this pair was written to the disk 9 by the Waveform Generator 3 at an earlier time). The processor 5 then plots a single vertical line for this pair; the vertical location and length of this line are determined by the values in the pair. The processor 5 iterates until the entire display is constructed for the user. III. Relating the Visual Presentation Back to the Original Digital Audio Data The practical application of visual waveform presentation is to use the visual display to identify a particular region of audio and then use the computer to edit the actual digital audio data. Any point in the visual presentation can be related back to the digital audio data by using the scale factor that was used to create the visual presentation. FIG. 13 waveform generator flowchart shows a scale factor of 256 being used. The preferred embodiment uses scale factors of 1:64, 1:256, 1:1024, 1:4096 and 1:16,384. Basically, the location in the visual presentation is multiplied by the scale factor to compute a pointer to the location of the actual digital audio data. For example, assume the user used a mouse cursor to select the region of the visual display from location 125 to location 198. If the scale factor for the visual presentation was 1:256, the selection region would correspond to samples 32,000 to 50,688 of the actual digital audio data. If, for example, the user desired to delete the selected segment of audio, the computer could delete the digital audio data from sample 32,000 to sample 50,688 using a memory-copy or disk-copy method. The desired edit would thereby be effected. IV. File System and Operating System Requirements The file system used to implement the preferred embodiment of the invention must be capable of storing digital audio data in large quantities at rates that exceed 100,000 bytes per second. Individual files must be byte-addressable to access the desired location. The operating system must provide sufficient plotting capability to implement the plotting flowchart and data expansion flowchart shown above. The ability to draw line segments in a rectangular region of the screen is required. Graphical scale factors to control the size of the visual presentation would also be required. I. The Hardware Platform FIG. 3 illustrates a computer system 30 which allows the file management system of the preferred embodiment of the present invention to be used. The elements of computer system 30 show a further view of the processor and memory elements of FIG. 1 as they are dedicated to file management and storage. For example, digital processor 31 (FIG. 3) corresponds to digital processor 5 (FIG. 1). Data Memory 33 (FIG. 3) corresponds to data memory 6 (FIG. 1), program memory 32 (FIG. 3) corresponds to program memory 7 (FIG. 1), storage device 37 (FIG. 3) corresponds to storage device 9 (FIG. 1), and computer interface bus 35 (FIG. 3) corresponds to computer interface bus 4 (FIG. 1). Computer system 30 includes a digital processor 31, a program memory 32 and a data memory 33. Program memory 32 contains a file management module 34 which controls the operation of digital processor 31 and instructs digital processor 31 to perform the necessary computational tasks to implement the file management and storage system of the preferred embodiment of the present invention. FIG. 3 also shows a large capacity peripheral random access memory storage device 37 such as a commonly known magnetic or magneto-optical disk on which may be stored a large memory cache or memory volume 38. As shown in FIG. 3, a computer interface bus 35 includes a plurality of computer interface bus connectors 36 that can be used to connect various input and output devices to digital processor 31. For example, in the field of digital audio, in addition to the Waveform generator 3 (FIG. 1) sampling apparatuses (not shown) and playback apparatuses 20 (FIG. 2) could be connected to digital processor 31 using computer interface bus 35 and computer interface bus connectors 36 to provide an easy mechanism for getting an information stream of digital audio data in and out of digital processor 31. II. The Organization of Stored Data The structure illustrated in FIG. 3 allows multiple input devices to each provide a stream of information. In the preferred embodiment, these multiple input devices include the plurality of Waveform generators 3 shown in FIG. 1. The file management system of the preferred embodiment of the present invention generally uses two classes of information that are stored on a storage device 37 to organize those streams of information. "System" data is information that is used by the file management system to organize, catalog, locate, and otherwise manage the storage and retrieval of all data. "User" data is the actual data or stream of information that the File Management System stores and retrieves directly. The preferred file management system of the present invention uses files and directory keys to manage the storage and retrieval of data. A file is a particular collection of stored user data that should be easily and quickly accessible. The user data is said to be "stored in" or "contained in" the file. Associated with each file is a directory key that is used to access that particular file. The preferred embodiment of the file management system of the present invention uses a user-supplied file name as the directory key for each file. The preferred file management system is particularly well suited for applications where the user data stored in a particular file consists of a plurality of related data sets as discussed below. In this context, a data set is merely a subset of the total user data that is stored in a particular file. Each data set is distinguishable in some way from other data subsets of the same file. In the preferred embodiment of the present invention each stream of information from each Waveform generator 3 connected to the interface bus connectors 36 provides one of several related data sets. In the preferred embodiment, each of the several related sets contains similarly formatted elements of information which can be retrieved in whole or in part to provide particular details describing the stream of information in a certain style. In the preferred embodiment the style of each date set describes the visual representation of the sample digital audio data at a particular scale factor. The preferred embodiment creates several related data sets describing a single information stream to store different characteristics of the information stream. In this manner, each set of data describing a characteristic can be very quickly retrieved, and since all of the related data sets describing the different characteristics of any information stream are coincidental, the system can easily reference one characteristic from another. The preferred embodiment of the present invention recognizes that each digital audio signal may be described in a number of different ways which all relate to each other. Those several descriptions may each be stored as a single data set to provide an entire group of related data sets. For example, in addition to the audio or sound representation of any single audio event, that same audio event may have a graphical or display representation which is recorded as a related data set in its own format. The preferred embodiment records and accesses these related representations by storing the representations as groups of related sets of data. The description hereinafter describes two (2) groups of information and two (2) sets of related data within each group for illustrative purposes only. The preferred embodiment can be expanded to record an access an infinite number of groups of information and an infinite number of related data sets per group by applying the principles discussed herein. The groups of related sets of data correspond to each other based upon a coincidental relationship. In the preferred embodiment, the coincidental relationship is the time of the audio event within the length of the digital audio recording or audio soundtrack. In the preferred embodiment, even though the digitally stored visual representations are each maintained as a data set of a different style, the file management system requires that the number of data sets stored in any particular file be the same as the number of data sets stored in every other file in the system, and that the relative sizes of the data sets stored in a particular file be the same relative sizes as the data sets stored in each of the other files in the system. The preferred embodiment recognizes that the length of the recording is not known, but will be determined while the recording is taking place. III. The File Management Structure Referring to FIG. 4, memory volume 38 is segmented into a number of logical blocks 41. Typically, each logical block 41 is comprised of a predetermined fixed number of bytes, such as 512 bytes for the preferred embodiment. A fixed number of logical blocks starting at block 0 and ending at block X-1 are reserved for the storage of system data. Memory volume 38 is divided into four data structure areas, including a volume descriptor area 42, a free data block list area 43, a file descriptor list area 44, and a file content area 45 in order quickly to organize, index and store data in related groups or sets which can be stored or retrieved from memory in related groups. Referring to FIG. 5, file content area 45 is shown divided into a plurality of file data areas 51. Each file data area represents one entire set of similarly formatted data, or one of a plurality of related data sets where each data set provides a group of information which is singularly formatted. Each file data area 51 is further divided into a plurality of file data blocks 52. Each file data block 52 is a memory grouping which holds the smallest fractional size of information which can be stored in the file data area 51. For instance, if the related data sets include different visual waveform representations of information then a particular file data area 51 will store all of the information for any one visual representation and file data block 52 will hold information corresponding to the minimum image resolution which can be stored or displayed for that particular visual representation. The number of file data areas 51 is chosen to be equal to the number of related data sets that will be stored and then may be accessed by a single directory key. To allow for coincidental access from one related data set to another each file data area 51 includes the same number NUM.sub.-- FDBS of file data blocks 52. Each sequential file data block 52 in any related data set is coincidentally related to all other file data blocks having an identical location in the sequence in any other related data set. The size FDB.sub.-- SIZE and number NUM.sub.-- FDBS of total file data blocks 52 is chosen by a formula discussed below. FIG. 8 shows the structure of file descriptor list area 44 of the memory volume 38 of the preferred embodiment of the file management system of the present invention. The file descriptor list area 44 contains descriptive information about the related data sets including the number NUM.sub.-- FILES 81 of sets of a group of related data sets which are stored and a plurality of file descriptor blocks 82 which each contain descriptive information about each particular set of the related data sets which are stored in segregated file data areas 51 of the file content area 45. Within each file descriptor block 82, information is contained describing each particular set of the related data sets and allowing access thereto. F.sub.-- NAME 83 contains the code name that is used to retrieve data from each particular set of the related data sets. NUM.sub.-- BLOCKS 84 contains the number of file data blocks 52 that contain data for each particular set of the related data sets. A plurality of DBLOCK.sub.-- NUMs 85 identify which file data blocks 52 contain the data for each particular set of the related data sets. FIG. 7 shows the structure of free data block list area 43 of the storage device in the preferred embodiment of the present invention. Free data block list area 43 manages the storage of new information. Within the free data block list area 43, NUM.sub.-- FREE 71 contains the number of file data blocks 52 that are not in use and thus are available for the storage of new information. A plurality of FREE.sub.-- BLOCKs 72 each contain a number that uniquely identifies a particular file data block 52 that is not in use and is thus available for the storage of new information. The number 0 is associated with the first file data block 52 in each file data area 51, the number 1 is associated with the second file data block 52 in each file data area 51, and so forth. FIG. 6 shows the structure of volume descriptor area 42 of the memory volume 38 of the preferred embodiment of the file management system of the present invention. The volume descriptor area 42 identifies which regions of memory volume 38 are used to store system information and which regions of memory volume 38 are used to store user information. In volume descriptor area 42, FREE.sub.-- LIST.sub.-- PTR 61 contains the logical block number of the beginning of free data block list area 43 on memory volume 38. This allows the system to quickly access the available free data blocks in order to store new information. FILE.sub.-- LIST.sub.-- PTR 62 contains the logical block number of the beginning of file descriptor list area 44 on memory volume 38. This allows the system to quickly access the descriptive information about the related data sets. NUM.sub.-- FDAS 63 contains the number of file data areas 51 that are included in file content area 45. NUM.sub.-- FDAS 63 defines the number of sets of data in a group of related data sets. NUM.sub.-- FDBS 64 contains the number of file data blocks 52 that are included in each file data area 51. NUM.sub.-- FDBS 64 defines the number of file data blocks 52 that are available for the storage of new information when memory volume 38 contains no user data. Volume descriptor area 42 also includes a plurality of file data area descriptors 65. Each file data area descriptor 65 provides information about each file data area 51 so that the particular set of the related data sets which is stored at the file data area 51 may be accessed. In the preferred embodiment, each file data area descriptor 65 contains a file data area pointer FDA.sub.-- PTR 66 and a description of the file data block size FDB.sub.-- SIZE 67. FDA.sub.-- PTR 66 contains the logical block number of the beginning of the associated file data area 51. FDB.sub.-- SIZE 67 contains the number of logical blocks in each file data block 52 of its associated file data area 51. IV. General Usage of the File Management System The file management system of the preferred embodiment of the present invention stores and retrieves information on a high capacity information storage device 37. To accomplish that end, there are several specific operations that the file management system might perform. These operations include, but are not limited to: 1. Initializing a new storage device 37 for use with the file management system; 2. Creating a file and allocating data storage space for that file; 3. Writing data to a file or reading data from a file. Other operations that the file management system may perform, such as allocating additional storage for a file or deleting a file, will become apparent to one skilled in the art once the three basic operations listed above are described. A. INITIALIZING A NEW STORAGE DEVICE A storage device 37 that is to be used with the file management system of the preferred embodiment of the present invention must be "initialized" before it can be used for the storage and retrieval of data. During the initialization process, certain values are computed and stored on the device itself. These values define the sizes and locations of different regions of the storage device that will be used to store the "system" and "user" data discussed above. These values also record certain attributes of the user data that will be stored on the device, in particular the number of related data sets for which room is to be reserved, and their relative sizes. Several steps must be performed to initialize storage device 37: 1. DETERMINE STORAGE DEVICE PARAMETERS The file management system must ascertain several parameters about the storage device itself before the storage device can be initialized. In particular, the file management system must determine the total capacity of the storage device as well as the size of the logical blocks that can be addressed thereon. As discussed above, the size of each logical block is normally expressed in bytes, where a byte consists of 8 binary digits (for example: the number 10011011.sub.2). Each logical block on the storage device must contain the same number of bytes. The total capacity of the storage device is normally expressed as the number of logical blocks that can be uniquely addressed. Storage devices 37 that conform to the well-known Small Computer System Interface standard (called the "SCSI" standard, pronounced "skuzee") can be interrogated by the file management system itself to determine these device parameters. The preferred file management system will interrogate the storage device 37 to determine the total capacity C.sub.t of the storage device 37 expressed as the number of logical blocks of length L stored thereon: L length in bytes of each logical block available on the storage device (supplied by the manufacturer of the storage device) C.sub.t total capacity of memory volume 38 expressed as the number of logical blocks that may be uniquely addressed thereon (supplied by the manufacturer of the storage device) A typical large capacity storage device of recent design might have a capacity of 1,000,000 logical blocks where each logical block can store 512 bytes, yielding values of: C.sub.t =1,000,000 and L=512 2. DETERMINE USER DATA ATTRIBUTES The file management system must calculate and ascertain several attributes about the user data that will be stored on the storage device before the storage device can be initialized. Specifically, the file management system must determine the number N of related data sets that are to be stored in each file, the relative size of each data set R.sub.1 -R.sub.n, and the approximate size (in logical blocks) of the largest such data set in a "typical" or "average" file S.sub.ave. These attributes of the user data are specified to the file management system by the user.
______________________________________
N number of related data sets that are stored in
each file. Each of the related data sets in the
file are accessed by a single directory key.
R.sub.l -R.sub.n
relative size of each related data set l-n.
Each R.sub.x must be an integer and common multiples
must be removed.
S.sub.ave
approximate size (in logical blocks) of the
largest such data set in a "typical" or "average"
file.
______________________________________
A sample application for the file management system of the present invention might be to store 30 second digital audio recordings and associated waveshape display information on a large capacity storage device. Assuming the digital audio was recorded for thirty (30) seconds with 16-bit resolution at 44,100 samples per second requiring 2,646,000 bytes of storage which is equal to approximately 5168 logical blocks where each block stores 512 bytes, and the waveform information was compressed to a single 8-bit byte for every 256 samples of digital audio, we get: N=2 R.sub.1 =512 R.sub.2 =1 and S.sub.ave =5168 3. COMPUTE SPECIFIC FILE MANAGEMENT SYSTEM FACTORS USING FORMULAS Based upon the storage device parameters and user data attributes determined in steps 1 and 2, the file management system next computes several factors that determine where on the storage device different the classes of information will be stored. These factors are chosen by the following formulas to provide for optimal and efficient data storage and retrieval. ps COMPUTE:
______________________________________
X sum of all relative sizes R.sub.l through R.sub.n
= R.sub.l + . . . + R.sub.n
C.sub.a capacity available for data storage. A good
value for C.sub.a is 98% of C.sub.t. Smaller values of C.sub.a
(such as 90% of the C.sub.t) may be used to provide
more room on the storage device for the storage
of system data. This would be desirable if a
great number of very small files were to be
stored. Larger values of C.sub.a (such as 99.9% of C.sub.t)
may be used to provide more room for the storage
of user data.
= .98 * C.sub.t (approximately; other values may be
used)
N.sub.a approximate number of file data blocks 52 (also
called extents) to use (round down to nearest
whole integer value). Any number greater than or
equal to 1 will allow the preferred embodiment to
function, however optimal performance will be
achieved by setting N.sub.a anywhere between
approximately 10 * C.sub.a .div. S.sub.ave and 100 * C.sub.a
S.sub.ave. If
the result is zero, the storage device is too
small for the intended application.
= 50 * C.sub.a .div. S.sub.ave (approximately; other values may
be
used)
S = C.sub.a .div. X .div. N.sub.a (round down to nearest whole
integer
value; substitute 1 if result is zero)
S.sub.n size of file data blocks in logical blocks for
each file data area
= S * R.sub.n
N.sub.fdb
actual number of file data blocks 52 (also called
extents) to use (round down to nearest whole
integer value).
= C.sub.a .div. X .div. S
______________________________________
These calculations will yield values to be used by the system as the number of file data blocks 52 (NUM.sub.-- FDBS) and the size of file data blocks 52 (FDB.sub.-- SIZE), 64 and 67 respectively, used for each file data area 51. Here N.sub.fdb =NUM.sub.-- FDBS and S.sub.n =FDB.sub.-- SIZE. For example, in the preferred embodiment of storing digital audio and waveforms on the storage device described in step 1: X=R.sub.1 + . . . +R.sub.n =513 C.sub.a =0.98*C.sub.t =980,000 N.sub.a =50*C.sub.a +S.sub.ave =9,481 S=C.sub.a .div.X.div.N.sub.a (round down to nearest whole integer value; substitute 1 if result is zero) =1 S.sub.n =S*R.sub.n S.sub.1 =512 S.sub.2 =1 N.sub.fdb =C.sub.a .div.X.div.S =1,910 4. DETERMINE LOCATION AND SIZE OF VOLUME DESCRIPTOR AREA, FREE DATA BLOCK LIST AREA, FILE DESCRIPTOR LIST AREA, AND FILE CONTENT AREA Referring to FIG. 4, Memory Volume 38 is divided into four areas: Volume Descriptor Area 42, Free Data Block List Area 43, File Descriptor List 44, and File Content Area 45. The next step in the initialization process is to compute the size of each of these 4 areas, and determine where each area will be stored on the storage device 37. Volume Descriptor Area 42 is used to store the Volume Descriptor as depicted in FIG. 6. In the preferred embodiment, the Volume Descriptor Area 42 begins at the very first logical block on the storage device, called Block 0. The number of logical blocks required to hold the Volume Descriptor can be readily determined by one skilled in the art and will depend on the programming language that is used, the amount of memory taken up by a single numeric quantity in that particular programming language, and the size of the logical blocks available on the storage device. The well-known programming language "C" offers a convenient "sizeof" function that can be used to perform this computation. Free Data Block List Area 43 is used to store the Free Data Block List as depicted in FIG. 7. In the preferred embodiment, the Free Data Block List Area 43 begins at the very next logical block after the end of the Volume Descriptor Area 42. Assuming that Volume Descriptor Area 42 is stored in Block 0 and further assuming that the Volume Descriptor Area 42 will fit in a single logical block, Free Data Block List Area 43 would normally begin at Block 1. The variable FREE.sub.-- LIST.sub.-- PTR is set to equal this logical block number. The number of logical blocks required to hold the Free Block List can also be readily determined by one skilled in the art as described in the preceding paragraph. File Descriptor List Area 44 is used to store the File Descriptor List as depicted in FIG. 8. In the preferred embodiment, the File Descriptor List Area 44 begins at the very next logical block after the end of Free Data Block List Area 43. Thus the logical block where File Descriptor List Area 44 is stored is easily computed by adding the number of logical blocks in Volume Descriptor Area 42 to the number of logical blocks in Free Data Block List Area 43. The result of this addition will be the logical block number where File Descriptor List Area 44 begins and is stored in the variable FILE.sub.-- LIST.sub.-- PTR. When the storage device is initialized, the File Descriptor List Area 44 will be empty. It will consist of a single number (0) indicating that there are no files listed in the File Descriptor List. The content of the File Descriptor List 44 will grow as the user creates new files. To provide as much room as possible for the growth of the File Descriptor List 44, File Content Area 45 is normally chosen to begin at the logical block computed by the expression (C.sub.t minus C.sub.a). 5. CONSTRUCT AND STORE THE VOLUME DESCRIPTOR Once the locations and sizes of the 4 disk areas have been determined (step 4), a memory image of the Volume Descriptor 42 is constructed in data memory 33. This memory image is filled with the results of the computations completed in steps 2 through 4. Referring to FIG. 6, FREE.sub.-- LIST.sub.-- PTR and FILE.sub.-- LIST.sub.-- PTR were computed directly in step 4. NUM.sub.-- FDAS is equal to N as determined in step 2, NUM.sub.-- FDBS is equal to S.sub.n as determined in step 3. Each file data area pointer FDA PTR is computed by totaling the prior FDB.sub.-- SIZE's and adding that to the result of C.sub.t minus C.sub.a. Once the Volume Descriptor 42 is constructed in data memory 33, it is written to the storage device 37 at the logical block address determined in step 4 (normally Block 0). 6. CONSTRUCT AND STORE THE FREE DATA BLOCK LIST Next, a memory image of the Free Data Block List 43 (FIG. 7) is constructed in data memory 33. This list may be easily constructed by one skilled in the art. NUM.sub.-- FREE is equal to N.sub.fdb computed in step 3 above. The list of free blocks consists of the numbers 0 through N.sub.fdb -1. Once the Free Data Block List 43 is constructed in data memory 33, it is written to the storage device 37 at the logical block address determined in step 4 (normally Block 1). 7. CONSTRUCT AND STORE THE FILE DESCRIPTOR LIST A memory image of the File Descriptor List 44 (FIG. 8) is then constructed in data memory 33. Since the list 44 is empty at this time (no files have been created yet), this list 44 consists of the single number 0. Once the File Descriptor List 44 is constructed in data memory 33, it is written to the storage device 37 at the logical block address determined in step 4. B. CREATING A NEW FILE AND ALLOCATING STORAGE FOR THAT FILE Once the storage device 37 has been initialized, the user may then create a new file and allocate storage for that file. The File Management System performs the following steps to create a file: 1. DETERMINE THE DIRECTORY KEY AND INITIAL FILE LENGTH The user must specify to the file management system the Directory Key that will be used to access the file after it is created. In the preferred embodiment of the present invention, the user specifies a 16 character file name as the Directory Key. The user must also specify to the file system how much storage is to be allocated to this file when it is created. Since storage can be allocated for the file at a later time, this value can be specified as zero when the file is first created. 2. READ THE VOLUME DESCRIPTOR, FREE DATA BLOCK LIST, AND THE FILE DESCRIPTOR LIST INTO MEMORY These data structures must be read into data memory 33 from the storage device 37 so they can be accessed quickly and modified. First, the Volume Descriptor 42 is read into data memory 33 from its designated location on the storage device 37 (normally Block 0). The information in the Volume Descriptor 42 is then used to read in the Free Data Block List 43 and the File Descriptor List 44. For example, the FREE.sub.-- LIST.sub.-- PTR entry of the Volume Descriptor 42 tells the File Management System where the Free Data Block List 43 is stored on the storage device 37. Likewise, the FILE.sub.-- LIST.sub.-- PTR entry of the Volume Descriptor 42 tells the File Management System where the File Descriptor List 44 is stored on the storage device 37 (see FIG. 6). 3. PERFORM ERROR DETECTION Once the data structures have been read into data memory 33, the File Management System of the preferred embodiment checks for several possible error conditions. The File Descriptor List 44 is searched to see if a file already exists that uses the same directory key as the directory key that was entered by the user in step 1. An error is reported to the user if a duplicate entry is found. Additionally, the Free Data Block List 43 is examined to make sure there is sufficient free storage available on the storage device 37 to meet the users request. The NUM.sub.-- FREE entry of the Free Data Block List 43 (FIG. 7) tells the file management system how much free storage is available on the storage device 37. 4. CREATE A FILE DESCRIPTOR FOR THE NEW FILE Provided the error checks in step 3 are completed correctly, the file management system then creates a File Descriptor (FIG. 8, item 82) for the new file. An image of the new File Descriptor 82 is created in data memory 33. The directory key specified by the user in step 1 is stored in the F.sub.-- NAME field 83. The amount of storage requested to be allocated for this new file is stored in NUM.sub.-- BLOCKS 84. The DBLOCK.sub.-- NUM entries of the File Descriptor List 44 are determined by removing entries from the Free Data Block List 43 and appending these entries to the new File Descriptor List 44. As each entry is removed from the end of the Free Data Block List 43 (FIG. 7), NUM.sub.-- FREE is reduced by 1. The Free Data Block List 43 is managed by the commonly known first-in, last-out push-down system. 5. INCREMENT NUM FILES Once the new File Descriptor has been created in step 4, the NUM.sub.-- FILES entry 81 of the File Descriptor 83 List 44 is incremented by one to signify that one new file has been created. 6. WRITE THE MODIFIED FILE DESCRIPTOR LIST AND FREE DATA BLOCK LIST BACK OUT TO THE STORAGE DEVICE The File Descriptor List 44 and the Free Data Block List 43 were read into data memory 33 in step 2 and were modified in steps 4 and 5. The modified File Descriptor List 44 and Free Data Block List 43 are now written back out to their respective areas of the storage device 37. C. WRITE DATA TO A FILE OR READ DATA FROM A FILE Once the file management system has created a file, user data may then be written to or read from any location of any data set provided for that file. The File Management System performs the following steps to access a particular file: 1. DETERMINE THE DIRECTORY KEY, DATA SET AND STARTING LOCATION The user must specify to the File Management System the Directory Key or file name F.sub.-- NAME 83 for the file which is to be accessed. Additionally, the user must specify which related data set is to be accessed (0 specifies the first data set, 1 specifies the second data set, etc.). Lastly, the user must specify where in the related data set the data is to be read from or written to. The related data set consists of file data blocks 52 which relate to each other in the preferred embodiment based upon time along an audio signal input. This time will correspond to logical block numbers where the file data blocks are stored. 2. READ THE VOLUME DESCRIPTOR AND THE FILE DESCRIPTOR LIST INTO MEMORY The volume descriptor 42 and the file descriptor list 44 data structures are read into data memory 33 from the storage device 37 so they can be accessed quickly (see step 2 of section 4 above). 3. SEARCH THE FILE DESCRIPTOR LIST The File Descriptor List 44 is searched for a File Descriptor whose F.sub.-- NAME entry 83 matches the Directory Key specified by the user in step 1. Once the File Descriptor for the specified file is located, that File Descriptor is copied into data memory 33 and preserved so that later access to this same file can occur without again searching the File Descriptor List 44. This process is well known to someone skilled in the art and is called "caching". 4. PERFORM ERROR DETECTION Once the correct File Descriptor is located, the file management system checks for several possible errors. Most importantly, the file management system must make sure that sufficient storage has been allocated for this file so that the data is written to or read from a section of the storage device 37 that is reserved for use by this particular file. This error detection is performed by comparing the NUM BLOCKS entry of the File Descriptor List 44 with the starting location plus the length specified by the user in step 1. 5. DETERMINE WHICH EXTENT IS TO BE WRITTEN The file management system next determines which file data block 52 of the file must be accessed by indexing down the File Descriptor List 44 to the appropriate DBLOCK.sub.-- NUM. The starting location specified by the user in step 1 is used as an index to the list of file data blocks 52 allocated for this file. The value stored in the indexed DBLOCK.sub.-- NUM identifies the logical file data block 52 which is to be accessed. 6. DETERMINE LOGICAL BLOCK ADDRESS The file management system next determines which logical block of storage device 37 is to be accessed. This is done by multiplying the logical file data block 52 number (determined in step 5) by the FDB.sub.-- SIZE entry for the related data set that is being accessed (specified by the user in step 1) (see FIG. 6). The product of this multiplication is added to the corresponding FDA.sub.-- PTR. The sum identifies the logical block address of the storage device 37 that is to be accessed. 7. READ OR WRITE THE USER DATA The user data, which in the preferred embodiment is digital audio data, specified in step 1 is written to or read from the storage device 37 at the logical block address determined in step 6. Those skilled in the art will appreciate that various adaptations and modifications of the just described preferred embodiments can be used and configured without departing from the scope and spirit of the invention. Therefore, it is to be understood that, within the scope of the appended claims, the invention may be practiced other than as specifically described herein.
|
Same subclass Same class Consider this |
||||||||||