JP4038725B2 - File position search method and apparatus - Google Patents

Description

  The present invention relates to a file position search method and apparatus for searching file position information in a FAT file system.

  In order to perform file position information search in the FAT file system, it is necessary to acquire the logical cluster at the target position using the first cluster of each existing file and the forward cluster link table.

  In the search method using the first cluster of the file and the file allocation table when searching for the file, the number of times the file allocation table is referred to is BC for the number of bytes per cluster and BPd for the byte position (0− base), NC is the file allocation table reference count, and ip (x) is the integer part of x, the file allocation table reference count NC can be obtained as ip (BPd / BC).

  According to this, when the logical size of the data at the end of the file is searched when the file size is very large, the BPd of the equation for obtaining the reference number NC of the file allocation table described above becomes very large, and the file allocation is performed. The reference count NC of the table becomes a very large value.

The time required to access the position BPd where the file is located is the time required for Td to search, and the reference time required for Tf to refer to the file allocation table once.
Then, the time Td required for the search is Tf × NC.

In such a large-sized data file to be played back, the address of the previous cluster corresponding to the address of the current cluster in the file is stored as the desired part can be accessed faster and more freely. There is a method for accessing a disc-shaped recording medium as described above (for example, see Patent Document 1).
JP-A-7-220457

This conventional access method has the following disadvantages. That is, in a system in which the reference time for one time of the file allocation table is large, there is a problem that the search speed Td becomes slower as going backward depending on the file reading position.
The present invention has been made in view of such circumstances, and an object of the present invention is to provide a file position search method and apparatus that can shorten the time required to access a position of a file.

In order to achieve the above-described object, the file position search method according to the present invention uses a size relationship between the byte position of the target data and the byte position stored as history information used when the position search of the data of the file is performed. A determination step for determining a difference between the first byte position of the file and the byte position of the target data, and a difference between the byte position of the target data and the byte position of the history information. And in the determination step, the byte position of the target data is smaller than the byte position of the history information, and the difference between the byte position of the history information and the byte position of the target data is the byte of the target data. If it is determined that the difference between the position and the first byte position of the file is smaller, the byte position of the target data and the history information File that you want to access and reference number of times, which was determined on the basis of the byte position, the cluster for the purpose of data of the file follow the link of the reverse file allocation table on the basis of the search start cluster is a cluster number of the history information And a position search step.

The recording / reproducing apparatus according to the present invention determines a magnitude relationship between the byte position of the target file data and the byte position stored as history information used when searching the position of the file data. And determining the magnitude relationship between the difference between the first byte position of the file and the byte position of the target file data, and the difference between the byte position of the target file data and the byte position of the history information. The byte position is smaller than the byte position of the history information, and the difference between the byte position of the history information and the byte position of the target file data is the byte position of the target file data and the first byte position of the file. And the byte position of the target file data, the byte position of the history information, and It includes a reference count obtained on the basis of the file position search means for accessing the cluster of interest of the file data follows the link opposite file allocation table on the basis of the search start cluster is a cluster number of the history information It is characterized by that.

  The file position search method and apparatus according to the present invention uses the reference number of the reverse file allocation table based on the target byte position and the byte position of the history information used and stored when the file position search is performed. The file allocation table is referred to by accessing the target cluster of the file by following the link of the reverse file allocation table based on the number of times of reference and the search start cluster which is the cluster number of the history information. Reduce the number of times required to access a file location.

  In order to provide a file location search method and apparatus that can reduce the time required to access a location of a file, the number of references in the reverse file allocation table, the target byte position, and the location of the file are searched. Based on the byte position of the history information used and stored in the file, and following the link of the reverse file allocation table based on the reference count and the search start cluster which is the cluster number of the history information. Realized by accessing the target cluster.

  FIG. 1 is a block diagram showing a disk drive device 100 of a disk-shaped recording medium to which the file position search method of the first embodiment is applied, and a personal computer connected to the disk drive device 100. The disk drive device 100 includes an audio processing unit 10, a media drive unit 12, a memory transfer controller 13, a cluster buffer memory 14, an auxiliary memory 15, USB interfaces 16 and 18, a USB hub 17, and a system controller (file position search means) 19. I have.

The audio processing unit 10 includes an analog audio signal input unit, an A / D, and a digital audio data input unit as an input system. In addition, an analog audio signal output unit is provided as an output system. In addition, an ATRAC compression encoder / decoder and a buffer memory for compressed data are provided.
The media drive unit 12 performs recording / reproduction with respect to the loaded disk 53. The memory transfer controller 3 controls delivery of playback data from the media drive unit 12 and recording data supplied to the media drive unit 12.
The cluster buffer memory 14 performs buffering of data read from the data track of the disc 53 by the media drive unit 12 in units of recording blocks based on the control of the memory transfer controller 13.
The auxiliary memory 15 records various management information and special information read from the disk 53 by the media drive unit 12 based on the control of the memory transfer controller 13.
The system controller 19 controls the entire disk drive device 100 and controls communication with the connected personal computer 52. The system controller 19 instructs the media drive unit 12 to read management information from the disk 53 when the disk 53 is loaded into the media drive unit 12, for example, and the management information read by the memory transfer controller 13. Is stored in the auxiliary memory 15.

  When there is a request to read a FAT sector from the personal computer 52, the system controller 19 causes the media drive unit 12 to read a recording block including the FAT sector. The read recording block data is written into the cluster buffer memory 14 by the memory transfer controller 13. The system controller 19 performs control to read out the requested FAT sector data from the recording block data written in the cluster buffer memory 14 and transmit it to the personal computer 52 via the USB interface 16 and the USB hub 17. .

  When there is a write request for a FAT sector from the personal computer 52, the system controller 19 first causes the media drive unit 12 to read a recording block including the FAT sector. The read recording block is written to the cluster buffer memory 14 by the memory transfer controller 13. Then, the system controller 19 supplies the FAT sector data from the personal computer 52 to the memory transfer controller 13 via the USB interface 16 and rewrites the corresponding FAT sector data on the cluster buffer memory 14. Further, the system controller 19 instructs the memory transfer controller 13 to transfer the recording block data stored in the cluster buffer memory 14 with the necessary FAT sector being rewritten to the media drive unit 12 as recording data. In the media drive unit 12, the recording data of the recording block is modulated and written to the disk 53.

  Further, the system controller 19 has a file position search function for searching for file position information on a recording medium managed in cluster units by the FAT file system. This file position search function obtains the reference count of the reverse file allocation table based on the target byte position and the byte position of the history information used and stored when the file position search is performed, and the reference The target cluster of the file can be accessed by following the link of the reverse file allocation table based on the number of times and the search start cluster which is the cluster number of the history information.

Further, the size relationship between the target byte position and the byte position of the history information is determined, and the difference between the first byte position of the file and the target byte position, the target byte position, and the history information are determined. A determination function for determining the magnitude relationship of the difference from the byte position is provided.
In the file position search function, the target byte position is smaller than the byte position of the history information in the determination function, and the difference between the byte position of the history information and the target byte position is the target byte position. When the file is determined to be smaller than the difference between the first byte position of the file and the first byte position of the file, the link of the reverse file allocation table is traced based on the reference count and the search start cluster. Can be accessed.
In addition, a holding function for storing the byte position and cluster number used when the file position search is performed as history information is provided.

  The file position search function includes a search start cluster setting function for setting a search start cluster of the file to a cluster number of history information stored by the holding function, a reference number of a reverse file allocation table, and a target byte position. , The reference count acquisition function obtained based on the byte position of the history information and the number of bytes per cluster, the reference count obtained by the reference count acquisition function, and the search start cluster set by the search start cluster setting function And a search function for accessing the cluster of the file by following the link of the reverse file allocation table based on the above.

  The display 51 can display text data and icons, and displays status information, messages, and the like based on a display control signal supplied from the system controller 19.

Here, the terminology used in the following description including Example 1, Example 2, Example 3 and Example 4 to be described later will be explained. The FAT is a file allocation table (order of file recording clusters). This is a table that manages information), and is a table that indicates the link status of a certain cluster, whether it is the end of the cluster, the next cluster, or which cluster is continued.
FFS is a FAT file system (file management system using a file allocation table).
RFAT is a reverse file allocation table that manages information on the order of recording clusters of files in the reverse direction. Whether a given cluster is the first cluster or continues to the previous cluster. This is a table showing the reverse link status of which cluster is continued. This FAT file system includes a reverse file allocation table in addition to a normal forward file allocation table.
BC is the number of bytes per cluster, and is calculated from the BIOS Parameter Block in FFS. CFS is the search start cluster number of the file. CFs is the first cluster of the file and is obtained from the directory entry. CFh is a cluster number obtained as a result of the search.
BP is a byte position (0-base). BPd is the target byte position (0-base). BPs is the first byte position (0-base) of the file. BPh is the byte position (0-base) used for the search.
NC is the number of FAT references. NCs is the number of FAT references from the beginning of the file. NCh is the number of FAT references from BPh.
FAT [n] means acquisition of the item number of the nth cluster in FAT, and rFAT [n] means acquisition of the item number of the nth cluster in RFAT.
Further, JIS X 0605 notation is used if necessary, and ip (x) means an integer part of x.
The mini disk uses a FAT file system as a file management system. The FAT file system reads from a disk to a memory such as an SDRAM and performs file management on the memory.

  FIG. 2 is a conceptual diagram showing the FAT file system FFS read from the disk 53 to a memory such as an SDRAM. As shown in FIG. 2, the FAT file system FFS is a BIOS Parameter Block (which is one of the system areas in the FAT file system, hereinafter referred to as BPB) and FAT (file allocation table, that is, the order of file recording clusters). This is a table for managing information, and for a certain cluster, a table indicating the link status of whether the cluster ends, continues to the next cluster, or which cluster if it continues, and FAT2 And a FAT file system FFS system area in which disk management information such as a root directory (hereinafter referred to as Root Dir), which is one of the system areas in the FAT file system FFS, is recorded. Consisting of data from the file data area to 16K bytes.

First, a logical cluster search method for an arbitrary byte position (BPd) of a standard file using FFS will be described.
FIG. 3 is a flowchart showing a method for searching a logical cluster at an arbitrary byte position in this standard file. In this standard search method, first, the first cluster (CFs) of a file is acquired from the directory entry of the file (step S1). The file search start cluster (CF) is set to the file head (CFs), and the FAT reference count and access count (NCs) are obtained from NCs = ip (BPd / BC) (step S2). Then, the link is traced by the number of times of FAT reference (NCs) (step S3, step S4, step S5), and the obtained cluster is accessed.

  In this standard logical cluster search method, as in the case of mini-disc audio, when a certain file size is about 1 GB at the maximum, and the number of bytes per cluster is 16 KB, the logical cluster of the last byte is determined. The number of FAT reference times NCs for searching is ip (1 GB / 16 KB) from NCs = ip (BPd / BC), which exceeds 60000 times.

  In the first embodiment, when searching for file position information on a disk medium such as a mini disk and using a FAT file system as a file management system, it is used once for position search as “Countermeasure 1”. It is considered that the number of FAT references is reduced by holding and using the byte position and the cluster number at that time.

  In mini-disc audio, random access repeatedly occurs for files of up to 1 GB. The number of FAT references is reduced by storing the previous byte position and the obtained cluster number. This compares NCh and NCs against the FAT reference count (NCs) from the head (BPs) to the target position (BPd) and the FAT reference count (NCh) from the stored position (BPh) to the target position (BPd). This is because the smaller one can be selected.

  However, in this case, since FAT can only perform backward search, it can be used only when the condition of BPs <BPh <BPd is satisfied. If this condition is not satisfied, it is obtained using the FAT reference count (NCs) from the top.

  FIG. 4 is a flowchart showing the file position search method according to the first embodiment. In this file position search method, a logical cluster at an arbitrary byte position (BPd) of a file is searched using the previous byte position (BPh) and the logical cluster number (CFh) at that time. Hereinafter, a logical cluster search method will be described with reference to this flowchart. First, the first cluster (CFs) of the file is acquired from the directory entry of the file (step S11). Next, it is determined whether the previous byte position (BPh) <the arbitrary byte position (BPd) of the file, that is, whether the byte position in the history is smaller (step S12), and if the byte position (BPh) in the history is smaller The process proceeds to step S13, and if the byte position (BPh) in the history is larger than an arbitrary byte position (BPd) of the file, the process proceeds to step S15.

  In step S13, the file search start cluster (CF) is set to the stored logical cluster (CFh). That is, CF = CFh. Subsequently, the FAT reference count (NCh) using the previous byte position (BPh) is obtained by NCh = ip (BPd / BC) −ip (BPh / BC) (step S14), and the process proceeds to step S17.

  On the other hand, in step S15, the search start cluster (CF) of the file is set to the first cluster (CFs) of the stored file. That is, CF = CFs. Subsequently, the FAT reference count (NCs) when searching from the beginning of the file is obtained from NCh = ip (BPd / BC) (step S16), and the process proceeds to step S17. Then, in steps S17, S18, and S19, a loop process that follows the link for the FAT reference count (NCh) is executed, and the obtained cluster is accessed.

  Here, the FAT reference count NCh = ip (BPd / BC) -ip (BPh / BC) using the previous byte position (BPh), and the FAT reference count NCh = ip (when searching from the beginning of the file) BPd / BC), (the FAT reference count NCh using the previous byte position BPh) = (FAT reference count NCh when searching from the beginning of the file) −ip (BPh / BC) Thus, as NCh is larger, the number of times of reference is increased, so that the search is speeded up.

  As described above, according to the first embodiment, when the condition of BPs <BPh <BPd is satisfied, the previous byte position (BPh) obtained by NCh = ip (BPd / BC) −ip (BPh / BC) The FAT reference count (NCh) using the is less than the FAT reference count NCh = ip (BPd / BC) when searching from the beginning of the file, and the search for accessing the cluster at the target position (BPd) There is an effect that it is possible to provide a file position search method and apparatus capable of speeding up the process.

In the second embodiment, when searching for file location information in a device using a FAT file system as its file management system on a disk medium such as a mini-disk, a link is made in the reverse direction as “Countermeasure 2”. Create and use reverse file allocation table. In other words, in addition to the original forward-direction cluster link table, a reverse-direction cluster link table, that is, a reverse cluster link table, is prepared to realize a high-speed determination of the logical cluster position of the target position. .
Hereinafter, a logical cluster search method for increasing the speed by creating and using the reverse direction cluster link table RFAT will be described.
By applying “Countermeasure 1” of the first embodiment, the number of FAT reference times NC could be reduced. However, it was only possible to meet the condition of BPs <BPh <BPd. Therefore, in the second embodiment, the number of FAT reference times NC is further reduced by creating and using RFAT.

  Compare the number of FAT references (NCs) from the beginning (BPs) to the target position (BPd) and the number of FAT (or RFAT) references (NCh) from the stored position (BPh) to the target position (BPd), and select the smaller one To do. Here, whether to use FAT or RFAT is determined based on whether or not the condition of BPs <BPd <BPh is satisfied. If this condition is satisfied, RFAT is used. In order to satisfy the condition of BPs <BPd <BPh and further satisfy the condition of (BPh−BPd) <(BPd−BPs), it is considered that RFAT can be used.

  When the condition of (BPh−BPd) <(BPd−BPs) is satisfied, when there is an RFAT that can follow the link in the reverse direction, NCh is determined as NCh = ip (BPh / BC) −ip (BPd / BC ).

  When the condition of (BPh−BPd) <(BPd−BPs) is satisfied, NCh that can be obtained by NCh = ip (BPh / BC) −ip (BPd / BC) is the target position (BPs). It is always smaller than the FAT reference count (NCs) of BPd).

  As described above, according to the second embodiment, in addition to satisfying the condition of BPs <BPh <BPd and further satisfying the condition of (BPh−BPd) <(BPd−BPs), the object can be obtained by using RFAT. The number of FAT references (NCs) of the position (BPd) can be reduced, and there is an effect that it is possible to provide a file position search method and apparatus capable of speeding up the search for accessing the cluster at the target position (BPd).

  In the third embodiment, the byte position used for the position search of “Countermeasure 1” and the cluster number at that time are retained and used, and the reverse file allocation table of “Countermeasure 2” is created and used, resulting in a file allocation table. Reduce the number of times to reference and speed up the determination of file location information.

  Hereinafter, the logical cluster search method using the previous byte position (BPh) and the logical cluster number (CFh) at that time described in the first embodiment, and the reverse cluster link table RFAT described in the second embodiment. A logical cluster search method that uses a logical cluster search method that creates and uses the above will be described.

  FIG. 5 is a flowchart including a method of searching for a logical cluster at an arbitrary byte position in a file using the RFAT already created in the third embodiment and the previous byte position and the logical cluster number at that time. The operation of this logical cluster search method will be described below according to this flowchart. In FIG. 5, the same or corresponding processing steps as those in FIG. 4 are denoted by the same reference numerals.

  First, the first cluster (CFs) of the file is acquired from the directory entry of the file (step S11). Next, it is determined whether or not “Countermeasure 1” of the first embodiment is applicable (step S12). In this determination, it is determined whether or not the condition BPh <BPd is satisfied. As a result of this determination, if the condition BPh <BPd is satisfied, the process proceeds to step S13 and “Countermeasure 1” described in the first embodiment is executed. If the condition BPh <BPd is not satisfied, the process proceeds to step S30. In step S30, it is determined whether or not “Countermeasure 2” of the second embodiment is applicable. In this determination, it is determined whether or not the condition (BPh−BPd) <(BPd−BPs) described in the second embodiment is satisfied. If the condition is satisfied as a result of the determination, the process proceeds to step S41, and “Countermeasure 2” including “Countermeasure 1” is executed. If the condition is not satisfied, the process proceeds to step S15.

  In step S13, "Countermeasure 1" is executed, and the file search start cluster (CF) is set to the stored logical cluster (CFh), that is, CF = CFh. In the subsequent step S14, the FAT reference count (NCh) using BPh is obtained by NCh = ip (BPd / BC) -ip (BPh / BC). In step S17, step S18, and step S19, the link is traced by the number of FAT reference times (NCh), and the obtained cluster is accessed.

  In step S15, the file search start cluster (CF) is set as the first cluster (CFs) of the stored file, that is, CF = CFs. In the subsequent step S16, the FAT reference count (NCs) when searching from the beginning of the file is obtained from NCs = ip (BPd / BC). In step S17, step S18, and step S19, the link is traced by the number of FAT reference times (NCh), and the obtained cluster is accessed.

  In step S41, the file search start cluster (CF) is set to the logical cluster (CFh) stored in the “Countermeasure 1”, that is, CF = CFh. In the subsequent step S42, using the reverse file allocation table of “Countermeasure 2”, the RFAT reference count (NCh) using BPh and RFAT is obtained from NCh = ip (BPh / BC) −ip (BPd / BC). . In subsequent steps S43, S44, and S45, a link is traced from the set file search start cluster (CFh) for the determined RFAT reference count (NCh), and the obtained cluster is accessed.

  As described above, according to the third embodiment, the number of FAT references (NCs) of the target position (BPd) can be obtained by holding and using the byte position used for the position search and the cluster number at that time, and using the RFAT. And a file position search method and apparatus capable of speeding up the search for accessing the cluster at the target position (BPd).

Next, an RFAT creation method will be described.
FIG. 6 is a flowchart showing this RFAT creation method. The RFAT creation method will be described below according to this flowchart.
First, the total number of clusters (total) is acquired (step S51). Next, a table area having the same size as the FAT is prepared, and all the areas are set to the “free” state (0 clear) (step S52). ). Then, it is determined whether or not total> 0 (step S53). If total = 0, the process ends. If total> 0 in step S53, N = FAT [total] is acquired, and it is determined whether N is valid (step S54). If it is determined in step S54 that N is a valid value (when linking to the next cluster), “total” is registered in N of the reverse FAT. That is, RFAT [N] = total is set (step S56). If it is determined in step S54 that N is not a valid value, total = total-1 is performed, and the process returns to step S53.

  By creating and using this RFAT, as the size of one file increases, the expected value of the number of FAT references required when accessing an arbitrary position in the file can be reduced. As a result, an improvement in access speed for a large file can be expected.

1 is a block diagram illustrating a disk drive device of a disk-shaped recording medium to which a file position search method according to a first embodiment of the present invention is applied, and a personal computer connected to the disk drive device. It is a conceptual diagram which shows FAT file system FFS read to memory, such as SDRAM, from the disk of the disk drive apparatus of Example 1 of this invention. It is a flowchart which shows the search method of the logical cluster of the arbitrary byte positions of a standard file. It is a flowchart which shows the file location search method of Example 1 of this invention. It is a flowchart including the search method of the logical cluster of the arbitrary byte positions of the file in Example 3 of this invention. It is a flowchart which shows the RFAT production method of Example 4 of this invention.

Explanation of symbols

19... System controller (file position search means) 53... Disc (recording medium)

Claims (3)

In a file location search method for searching location information of file data on a recording medium managed in units of clusters by the FAT file system,
The size relationship between the byte position of the target data and the byte position stored as history information used when searching the position of the data of the file is determined, and the leading byte position of the file and the target data A determination step of determining a magnitude relationship between a difference between a byte position and a difference between a byte position of the target data and a byte position of the history information;
In the determination step, the byte position of the target data is smaller than the byte position of the history information, and the difference between the byte position of the history information and the byte position of the target data is the byte position of the target data. If it is determined that the difference is smaller than the first byte position of the file, the number of references obtained based on the byte position of the target data and the byte position of the history information, and the history information cluster A file location search step of accessing the target cluster of the data of the file by following the link of the reverse file allocation table based on the search start cluster which is a number ;
A file position search method characterized by comprising: A holding step of storing, as history information, a byte position and a cluster number of the history information used when the file location search is performed, and the file location search step stores the search start cluster of the file. The search start cluster setting step that is set to the cluster number of the history information stored in the step, the reference number of the reverse file allocation table, the byte position of the target data, the byte position of the history information, and the number of bytes per cluster Based on the reference number acquisition step obtained based on, the reference number obtained in the reference number acquisition step, and the search start cluster set in the search start cluster setting step, the link of the reverse file allocation table is followed. Search steps to access the data of the file cluster File position search method according to claim 1, characterized in that it has and. In a recording / reproducing apparatus for retrieving position information of file data on a recording medium managed in units of clusters by the FAT file system, and recording / reproducing the file data,
Determine the size relationship between the byte position of the target file data and the byte position stored as history information used when the position search of the file data is performed, and further, the first byte position of the file and the target file data And the difference between the byte position of the target file data and the byte position of the history information is determined, and the byte position of the target file data is larger than the byte position of the history information. When it is determined that the difference between the byte position of the history information and the byte position of the target file data is smaller than the difference between the byte position of the target file data and the first byte position of the file. , The number of references obtained based on the byte position of the target file data and the byte position of the history information, and the history information. Recording reproducing apparatus characterized by comprising a file location retrieval means for accessing a cluster of interest of the file data follows the link opposite file allocation table on the basis of the search start cluster is a cluster number.

Images