一種讀取fat磁碟文件的方法和裝置的製作方法

2023-09-23 21:24:30

專利名稱：一種讀取fat磁碟文件的方法和裝置的製作方法
技術領域：
本發明涉及計算機存儲技術領域，特別涉及一種讀取文件分配表 (FileAllocation Table, FAT)磁碟文件的索引方法和裝置。
背景技術：
可攜式的數碼產品常採用嵌入式系統架構，在主電路板上包括嵌入式存儲模塊， 存儲模塊通常包括一個或多個磁碟分區，磁碟分區用於存儲圖片、視頻或音頻文件；主電路 板上還包括業務模塊，業務模塊具有內存，用於將存儲模塊上的文件讀取到內存中並進行 相應的業務，例如顯示圖片或者播放音視頻文件等。所述內存可以是快閃記憶體或非易失存儲器。
在一些採用嵌入式系統的數碼產品讀取存儲模塊上的文件並進行相應的業務的 過程中，通常會搜索磁碟分區下的所有圖片、音樂或者視頻文件，讀取文件內容後進行解 碼，然後顯示或者播放。所述嵌入式數碼產品可以是數碼相框、數碼伴侶、數位相機、多媒體 播放器等。所述搜索並打開文件的過程，一般是根據所有文件的全路徑名，執行文件的打開 操作。具體地說，通過逐級解析目錄名，查找其目錄項，再由當前目錄的目錄項找到子目錄 的目錄項，最終在目標文件所在的目錄項位置獲取目標文件的所有信息。如果文件分布在 許多不同的多級目錄中、或者同一目錄下包含很多文件時，這種打開文件的方法變得非常 緩慢，在嵌入式系統中，會直接導致性能的降低。現有技術還有另一種打開文件的方案在搜索到所有文件後，分別將其全路徑保 存在內存中，以便在打開前不必搜索。但這種方式同樣需要解析輸入的路徑名，才能逐級查 找到最終的子目錄，獲取目錄項內的信息。根據數碼產品常用的FAT規範，保存一個文件的 全路徑名最多需要80位元組，當文件數量龐大時，所保存的文件全路徑名就會佔用內存相當 一部分存儲空間，這在嵌入式系統應用中，會導致硬體成本的上升。

發明內容
有鑑於此，本發明的目的在於，提出一種讀取FAT磁碟文件的方法和裝置，可以佔 用較小內存實現快速讀取FAT磁碟文件。本發明實施例提出一種讀取FAT磁碟文件的方法，包括如下步驟預先對FAT格式的磁碟分區中特定類型的文件進行全分區搜索，為每一個搜索到 的文件分配唯一的索引號；在內存中保存N個索引號連續的文件目錄項位置信息的序列；N 為自然數；判斷所要讀取的文件索引號i是否在所述序列內，若是，則直接從序列內獲取索 引號i對應的文件目錄項位置信息；否則，確定搜索方向並將索引號i及其附近的共N個文 件目錄項位置信息保存到序列內，並從序列中獲取目錄項位置信息；根據所述目錄項位置信息讀取文件。較佳地，在內存中保存如下內容全分區最小索引號及該索引號對應文件的全位置信息；全分區最大索引號及該索引號對應文件的文件全位置信息；序列元素對應的最大索引號及該索引號對應文件的文件 全位置信息；以及序列元素對應的最小索引號及該索引號對應文件的文件全位置信息；所 述文件全位置信息包括文件目錄項位置信息、文件目錄項在其所在目錄的目錄項中的位置 偏移以及文件所在目錄的簇號；所述判斷所要讀取的文件索引號i是否在所述序列內，若是，則直接從序列內找 到文件目錄項位置信息；否則，確定搜索方向並將索引號i及其附近的共N個文件目錄項位 置信息保存到序列內，並從序列中獲取目錄項位置信息；根據所述目錄項位置信息讀取文 件包括判斷所要讀取的文件索引號i是否在序列元素對應的最小索引號到序列元素對 應的最大索引號的範圍內，若是，則從序列元素中找到索引號i對應的文件目錄項位置信 息，並根據所找到的文件目錄項位置信息讀取所述磁碟分區上的文件；否則，在全分區最小索引號、全分區最大索引號、序列元素對應的最大索引號和序 列元素對應的最小索引號這四個索引號之間取與i的差值最小的索引號，計為k，並以索引 號k對應的文件的全位置信息為起點確定搜索方向；以索引號k對應的文件的全位置信息為起點，以所確定的搜索方向進行所述類型 文件的部分搜索，搜索到包含索引號i的連續的N個索引號，將所搜索到的N個索引號對應 的目錄項位置信息保存為序列元素；並根據所保存的序列元素中、索引號i對應的文件目 錄項位置信息讀取所述磁碟分區上的文件。所述為每一個搜索到的文件分配唯一的索引號為按照搜索結果的順序號作為該 文件的索引號。所述序列的維數為2的正整數冪次。所述以索引號k對應的文件的全位置信息為起點確定搜索方向包括比較索引號i與索引號k的大小，當i < k時向全分區搜索的相反方向執行部分 搜索，否則向全分區搜索的相同方向執行部分搜索。所述包含索引號的連續的N個索引號為索引號從i到i+Ν-Ι的N個索引號；或者，將索引號從i_(N/2)到i+(N/2)_l的N個索引號。所述以索引號k對應的文件的全位置信息為起點，以所確定的搜索方向進行所述 類型文件的部分搜索的步驟包括判斷所搜索到的N個索引號中的最小索引號Ml是否小於內存中已保存的序列元 素對應的最小索引號，若是，則將Ml保存為新的序列元素對應的最小索引號，以內存中已 保存的全分區最小索引號對應文件的全位置信息為起點，向全分區搜索的相同方向搜索所 述類型文件；或者，判斷所搜索到的N個索引號中的最大索引號M2是否大於內存中已保存的序 列元素對應的最大索引號，若是，則將M2保存為新的序列元素對應的最大索引號，以內存 中已保存的全分區最大索引號對應文件的全位置信息為起點，向全分區搜索的相反方向搜 索所述類型文件。其特徵在於，所述以索引號k對應的文件的全位置信息為起點，以所確定的搜索 方向進行所述類型文件的部分搜索，搜索到包含索引號i的連續的N個索引號包括
在已保存的文件目錄項位置信息中查找是否有需要保留的內容，若是，則跳過所 述需要保留的內容，並更新其餘的文件目錄項位置信息。本發明實施例還提出一種讀取FAT磁碟文件的裝置，包括全分區搜索模塊、存儲 模塊、讀取模塊和部分搜索模塊；全分區搜索模塊，用於對FAT格式的磁碟分區中特定類型的文件進行全分區搜 索，為每一個搜索到的文件分配唯一的索引號；存儲模塊，包括N維的序列存儲單元，所述序列存儲單元用於保存所 述全分區搜 索模塊搜索到的N個索引號連續的文件目錄項位置信息；根據來自部分搜索模塊的索引號 i及其附近共N個文件的目錄項位置信息，對所保存的文件目錄項信息進行更新；讀取模塊，用於判斷所要讀取的文件索引號是否在所述存儲模塊的序列存儲單元 內，若是，則直接從序列存儲單元獲取文件目錄項位置信息；否則，確定搜索起點以及搜索 方向並向部分搜索模塊發送搜索指令；待存儲模塊存儲的內容更新後，從序列存儲單元中 找到索引號i對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述 磁碟分區上的文件；部分搜索模塊用於以來自讀取模塊的搜索起點為起點，以讀取模塊所確定的搜索 方向進行部分搜索，將搜索到的索引號i及其附近共N個文件的目錄項位置信息發送至存 儲模塊。較佳地，所述存儲模塊保存全分區最小索引號及該索引號對應文件的全位置信 息；全分區最大索引號及該索引號對應文件的文件全位置信息；序列元素對應的最大索引 號及該索引號對應文件的文件全位置信息；以及序列元素對應的最小索引號及該索引號對 應文件的文件全位置信息；所述文件全位置信息包括文件目錄項位置信息、文件目錄項在 其所在目錄的目錄項中的位置偏移以及文件所在目錄的簇號；所述讀取模塊，用於判斷所要讀取的文件的索引號i是否在存儲模塊保存序列元 素對應的最小索引號到序列元素對應的最大索引號的範圍內，若是，則從序列元素中找到 索引號i對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟 分區上的文件；否則，在全分區最小索引號、全分區最大索引號、序列元素對應的最大索引 號和序列元素對應的最小索引號這四個索引號之間取與i的差值最小的索引號，計為k，並 以索引號k對應的文件的全位置信息為起點確定搜索方向，將索引號k與所確定的索引方 向發送至部分搜索模塊；待存儲模塊存儲的內容更新後，從序列存儲單元中找到索引號i 對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟分區上的 文件。所述讀取模塊進一步包括搜索方向確定單元，用於比較所述索引號k和i的大小，當i < k時，確定搜索方 向為全分區搜索的相反方向，否則確定搜索方向為全分區搜索的相同方向。較佳地，所述裝置進一步包括邊界調整模塊，用於判斷部分搜索模塊所搜索到的N個索引號中的最小索引號Ml 是否小於存儲模塊中已保存的序列元素對應的最小索引號，若是，則通知所述部分搜索模 塊以存儲模塊中已保存的全分區最小索引號對應文件的全位置信息為起點；或者，用於判斷部分搜索模塊所搜索到的N個索引號中的最大索引號M2是否大於存儲模塊中已保存的序列元素對應的最大索引號，若是，則通知所述部分搜索模塊以存儲 模塊中已保存的全分區最大索引號對應文件的全位置信息為起點從以上技術方案可以看 出，由於全分區搜索產生的文件目錄項信息的數目太大，本發明方案通過設定一定大小的 內存空間來存儲一小段連續的索引號及文件目錄項位置信息，在此基礎上通過部分搜索的 方式找到目標文件的文件目錄項位置信息。內存空間大小可以根據實際內存需求以及系統 的運行速度調整，從而可以在佔用較小內存空間的情況下快速讀取FAT磁碟文件。


圖1為本發明提出讀取FAT磁碟文件的方法的基本流程圖；
圖2為本發明實施例的執行全盤分區搜索後，數組kFIndex所保存的索引文件的 目錄項位置信息對應的索引號範圍示意圖；圖3為本發明實施例的某次部分搜索之前，kFIndex所保存的索引文件的目錄項 位置信息對應的索引號範圍示意圖；圖4為本發明實施例進行部分搜索過程中，kFIndex所保存的索引文件的目錄項 位置信息對應的索引號超出左邊界時進行調整的示意圖；圖5為本發明實施例進行部分搜索過程中，kFIndex所保存的索引文件的目錄項 位置信息對應的索引號超出右邊界時進行調整的示意圖；圖6為本發明實施例進行部分搜索之後，kFIndex所保存的目錄項位置信息對應 的索引號範圍示意圖；圖7為本發明實施例進行部分搜索之後，kFIndex所保存的目錄項位置信息對應 的索引號範圍示意圖，所述索引號範圍與部分搜索之前kFIndex所保存的目錄項位置信息 對應的索引號範圍部分重合；圖8為本發明實施例提出一種讀取FAT磁碟文件的方法流程圖；圖9為在圖3所示情況下，執行本發明實施例方案的部分搜索的流程圖。
具體實施例方式為使本發明的目的、技術方案和優點更加清楚，下面結合附圖對本發明作進一步 的詳細闡述。一個FAT磁碟文件的大小、創建時間、文件數據所在的起始位置即首簇號信息都 是記錄在文件目錄項中，文件目錄項的長度為32位元組。讀取FAT磁碟文件，必須首先找到 這個目錄項，獲得文件大小、創建時間、文件首簇號即文件實際數據的起始位置等信息，當 需要讀取數據時，再根據文件的首簇號，查找FAT表中的簇鏈一一讀取。以下所述文件如未 加說明，均為FAT磁碟文件。根據FAT規範，一個文件的目錄項位置信息最少需要如下信息1)該文件目錄項所在磁碟分區的扇區信息因FAT32格式最大支持32GB (GB為2的19次方字節數量)大小的磁碟分區，一個 扇區佔512位元組(Byte)，因此表示一個扇區號最多使用26比特(bit)表示。2)該文件目錄項在當前扇區中的偏移量。由於一個扇區大小為512位元組，一個目錄項大小為32位元組，因此一個扇區最多16個目錄項，偏移量只需4b i t表示。3)該文件所在目錄的目錄項首簇號，佔32bit。如果不要求在顯示時獲取文件全路徑名，則該信息不是必須的。因此，記錄一個文件的目錄項位置信息，最少需要26bit+4bit+32bit = 8Byte，可 用C語言表示成如下數據結構typedef struct_DIRITEM_ADDRINFO{Unsigned long secoff :26 ； //目錄項所在磁碟分區的扇區信息；Unsigned long diroff 4 ； //目錄項在當前扇區中的偏移；Unsigned long reserved :2 ;//保留，未使用；Signed long pclust ； //當前文件所在目錄的目錄項的首簇號；}Diritem_AddrInfo ；搜索完一個磁碟分區上的所有文件後，將文件出現的順序號作為索引號，通常以 非負整數從0開始表示，每個文件的索引號唯一。具有索引號的文件稱為索引文件。打開 索引文件的參數為索引號和磁碟分區號，而不是文件路徑，並僅以只讀方式打開。所謂一個 索引文件的全位置信息，是指除了索引文件的目錄項位置信息外，還包含下列信息a)文件目錄項在其所在目錄的目錄項中的位置偏移，以字節表示，是32的整數 倍；b)索引文件所在目錄的簇號；c)索引文件所在目錄的深度。在很多應用中，對FAT系統上打開的目錄深度有限制，根目錄深度為0，進入一級 子目錄，則深度加1，二級子目錄則深度為2，並依此類推。最大搜索目錄深度需在搜索前固定。d)關於索引文件所在目錄的其他信息。索引文件的全位置信息，表示了該索引文件在磁碟分區上某個目錄下的相對位 置。若已知索引文件A的全位置信息，才能根據索引文件A的索引號，知道另一索引號的索 引文件B是在索引文件A之前還是之後，以便可以找到其他同類型文件的目錄項位置信息。 文件屬於相同類型是指文件具有相同的格式，可以通過文件的後綴名識別出文件的類型， 文件的後綴名如「· jpg，，、「· mp3」、「. avi 」等。本實施例中，索引文件的全位置信息可以表示成一個包含了文件的目錄項位置信 息結構Diritem_AddrInfo變量的一個數據結構。全分區搜索和部分搜索所謂全分區搜索，是指從格式化為FAT格式的磁碟某個分區的根目錄開始，根據 目錄結構，按照事先設定的最大目錄深度，一次性搜索完該磁碟分區上的一種、幾種或者所 有文件類型的搜索方式。如果磁碟分區上的文件沒有改變，則不必重新搜索。所謂部分搜索，是指在當前全盤分區搜索的文件中，以與全盤分區搜索同樣規定 的文件類型，以某個索引文件的全位置信息為起點，在同一磁碟分區上搜索其他索引文件 的方式。本發明方案讀取文件的原理為如果一個磁碟分區上文件數量很大，為所有的文件保存它們的目錄項位置信息會佔用過多的內存空間，則根據事先設定的內存空間，保存 一部分文件的目錄項位置信息；如果需要讀取其他的文件，則根據所保存的目錄項位置信 息通過執行部分搜索的方式來實現。假設磁碟D上有10000個同類型文件，需要在瀏覽時快速打開，分配適當大小的內 存空間來保存文件目錄項位置信息，比如，設置能保存64個文件目錄項位置信息的內存空 間，共64X8 = 512位元組，數組kFIndeX[N]用於保存文件目錄項位置信息，N表示所保存的 目錄項位置信息的數目。實際應用中，N的大小可以根據實際內存需求、以及系統的運行速 度進行調整。本發明提出讀取FAT磁碟文件的方法的基本流程如圖1所示，包括如下步驟步驟101 預先對FAT格式的磁碟分區中特定類型的文件進行全分區搜索，為每一 個搜索到的文件分配唯一的索引號；在內存中設置用於保存N個索引號連續的文件目錄項 位置信息的N維數組；步驟102 判斷所要讀取的文件索引號是否在所述數組內，若是，則直接從數組內 獲取文件目錄項位置信息；否則，確定搜索方向並將索引號i及其附近的共N個文件目錄項 位置信息保存到數組內，並從數組中獲取目錄項位置信息；步驟103 根據所述目錄項位置信息讀取文件。在首次執行全盤分區搜索的過程中，相當於為所有文件建立了一個一一對應的索 引號，對10000個文件來說，其索引號分別從0到9999，而數組kFIndex[N]則只記錄了索引 號為0 63這64個索引文件的目錄項位置信息。在整個搜索過程中，還記下了四個全位 置信息，它們是在執行全盤分區搜索或部分搜索時得到的，分別是(1)、磁碟分區搜索到的第1個文件的全位置信息，記為Dstart在本實施例中，Dstart是索引號為0的文件的全位置信息，一次全盤分區搜索完 成後，其值不改變。其對應索引號記為Dstartjndex，本實施例中，Dstartjndex的值恆為 O0(2)、磁碟分區搜索到的最後1個文件的全位置信息，記為Dend。在本實施例中，Dend是索引號為9999的文件的全位置信息，一次全盤分區搜索完 成後，其值不改變。其對應索引號加上1後的值記為DencLindex，本實施例中，DencLindex 的值恆為10000。(3), kFIndex數組中所記錄的索引號最小的索引文件全位置信息，記為Mstart。在本實施例中，Mstart為當前時刻kFIndeX
所表示的索引文件的全位置信息， 在執行部分搜索後會更新。其對應索引號記為Mstartjndex，初始取為與Dstartjndex相 同。(4)、klndex數組所記錄的索引號最大的索引文件的全位置信息。記為Mend。在本實施例中，Mend為當前時刻kFIndex[63]所表示的索引文件的全位置信息， 在執行部分搜索後會更新。其對應索引號加上1後的值記為MencLindex。圖2示出了執行全盤分區搜索後，kFIndex所保存的索引文件的目錄項位置信息。 如圖2所示，在為建立索引而執行全盤分區磁碟的過程中，將保存第一個文件的全位置信 息Dstart和索引號Dstartjndex，以及最後一個文件的全位置信息Dend和索引號Dend_ index-1 ；同時，還根據設定的N值，在數組kFIndex中記錄下了索引號為Mstartjndex到Mend_index-1這N個文件的目錄項位置信息，以及索引號為Mstartjndex和Mend_ index-1這兩個索引文件的全位置信息。其中，Mstart_index+N = Mend_index。特殊情況 下，如果N > = DencLindex，則以後不必進行部分搜索。本發明實施例提出一種讀取FAT磁碟文件的方法流程如圖8所示，包括如下步 驟步驟801 預先對FAT格式的磁碟分區中特定類型的文件進行全分區搜索，為每一 個搜索到的文件分配唯一的索引號；步驟802 在內存中設置N維的數組kFIndeX[N]，用於保存N個索引號連續的文 件目錄項位置信息；在內存中保存最小索引號的文件全位置信息Dstart及對應的索引號 Dstartjndex、最大索引號的文件全位置信息Dend及對應 的索引號DencLindex-l，數組 kFIndex[N]中最大索引號的文件全位置信息Mend及對應的索引號MencLindex-l，以及數 組kFIndeX[N]中最小索引號的文件全位置信息Mstart及對應的索引號Mstartjndex ；所 述文件全位置信息包括文件目錄項位置信息、文件目錄項在其所在目錄的目錄項中的位置 偏移以及文件所在目錄的簇號；步驟803 判斷所要讀取的文件的索引號i是否在索引號Mstartjndex到索引號 Mend_index-1的範圍內，若是，執行步驟804，否則轉至步驟805 ；步驟804 從數組kFIndeX[N]中找到索引號i對應的文件目錄項位置信息，並根 據所找到的文件目錄項位置信息讀取所述磁碟分區上的文件，流程結束。步驟 805 在 Dstart_index、Dend_index、Mstart_index 禾口 Mend_index 這四個索 弓丨號之間取與i的差值最小的索引號，計為k，並以索引號k對應的文件的全位置信息為起 點確定搜索方向；步驟806 以索引號k為起點，以所確定的搜索方向進行部分搜索，將索引號i及 其附近共N個文件的目錄項位置信息保存到數組kFIndeX[N]中，並根據數組kFIndeX[N] 中索引號i的文件的目錄項位置信息讀取所述磁碟分區上的文件。下面再以一種具體的實施情況為例，給出詳細的處理流程。假定在運行一段時間 後，各個記錄點的位置如圖3所示，當前kFIndex保存了索引號為Mstartjndexl到Mend_ indexl-1這N個索引文件的目錄項位置信息，而且執行全盤分區搜索後，又執行過部分搜 索，導致Mstartjndexl不再與Dstarti_ndex相等。讀取文件的流程如圖9所示，包括如 下步驟步驟100 判斷所要讀取的文件的索引號i是否在索引號Mstartjndex到索引號 Mend_index-1的範圍內，若是，則從數組kFIndex[N]中找到索引號i對應的文件目錄項位 置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟分區上的文件；否則執行步驟 200 ；步驟 200 在 Dstart_index、Dend_index、Mstart_indexl 禾口 Mend_indexl 這四個 索引號之間，取與i的差值最小的索引號，計為k，並以k對應的索引文件的全位置信息為起 點確定搜索方向。確定索引方向的步驟可以為比較i與k的大小，當i < k時向全分區搜索的相反 方向執行部分搜索(記為backward)，否則向全分區搜索的相同方向執行部分搜索(記為 forward)。全分區搜索的方向指按照文件在存儲介質上原有的從前到後的存放順序。
步驟300 以索引號k為起點，以所確定的搜索方向進行部分搜索，將索引號i及 其附近共N個文件的目錄項位置信息保存到kFIndex中，並根據數組kFIndex[N]中索引號 i的文件的目錄項位置信息讀取所述磁碟分區上的文件。具體地，可以取kFIndexN]來讀取索引號i的文件的目錄項位置信息。其中， N表示i除以N所得的餘數。較佳地，保存的目錄項位置信息對應的索引號範圍可以是
從i到i+Ν-Ι ；也可以是索引號從i-(N/2)到i+(N/2)-l。步驟400 判斷kFIndeX[N]保存的目錄項位置信息對應的索引號是否超出允許範 圍，若是，則將其調整為允許範圍以內。允許範圍就是[Dstartjndex，Dend_index-1]區 間。假設保存到kFIndeX[N]的最小索引號為MJlJi M Dend_index時，表示理論計算的、欲保存到kFIndex的最大索引值超出了右邊 緣，N值調整為DencLindex，以Dend全位置信息backward搜索，如圖5所示。但無論如何 調整，所要保存的目錄項位置信息個數始終為N。步驟500 部分搜索完成後，Mstart_indexl和MencLindexl需要分別更新為 Mstart_index2 禾口 Mend_index2，Mstart_index2 的值為 Μ, Mend_index2 的值為 N, Mstart 更新為索引號M對應的索引文件的全位置信息，將Mend更新為索引號N對應的索引文件的 全位置信息。圖6所示為重新執行部分搜索後，kFIndex所保存的目錄項位置信息對應的 索引號範圍。其中部分搜索之前的kFIndex對應的索引號範圍如虛線部分所示，部分搜索 之後更新的kFIndex對應的索引號範圍如粗實線部分所示。在某些情況下，部分搜索前後的kFIndex對應的索引號範圍有可能出現一部分重 疊，如圖7所示。部分搜索之前的kFIndex對應的索引號範圍與欲更新的索引號範圍在陰影 區域重合，則陰影區域對應的目錄項位置信息是不必更新的，此時以全位置信息Mend為起 點，搜索(也是跳過)共(Mend_index2-Mstart_indexl)後，更新全位置信息Mend和Mend_ index,搜索完N個文件後，將後面搜索的文件的目錄項位置信息保存在kFIndex中，保存個 數小於N。此處所謂的搜索是指在已有的保存數據中查找是否有需要保留的內容，因為原 kFIndex已經保存有陰影區域部分索引文件的目錄項位置信息，這部分不必重新保存。在搜 索完最後一個index文件後，更新全位置信息Mstart和Mstartjndex的值。相比而言，如果以backward方向搜索，則其起點索引號值(只可能是Mstart或 者Mend)需事先減1，仍以全分區搜索有10000個索引文件為例，當前kFIndex保存了從 500到564(不包含564這個索引號本身)共64個索引文件的目錄項位置信息。此時，若 欲打開的索引文件號i為480，則起點索引號首先減1變為563，這是當前kFIndex中對應 的實際最大索引號，並取該點的全位置信息開始backword搜索。其中索引號500 512的 目錄項位置信息為需要保留的內容，索引號512 563的目錄項位置信息為此次丟棄的內 容。由於新的目標索引範圍左邊是480-64/2 = 448，右邊480+64/2 = 512，最大索引號值 為511，因此在忽略了 563-511 = 52個索引文件後，將搜索到的第53個文件所在的全位置 信息，更新到Mend ；在搜索到第64個文件後，從第65個文件開始將其目錄項位置信息記錄 到kFIndex 64]中，共更新64+500-512 = 52個文件的目錄項位置信息，其餘12個文件(索引號從500到511)的目錄項位置信息仍留在kFIndex中。較佳地，N的取值為2的正整數冪次。設N = 2n此時在通過索引號i存取kFIndex 變量元素時，可以通過kFIndex [i&((1 < < η) -1)]，獲得比kFIndex [i % N]更高的效率。其 中i表示索引號，η表示N的取值是2的幾次冪，整個表達式等效於對i求N的餘數。本發明實施例還提出一種讀取FAT磁碟文件的裝置，包括全分區搜索模塊、存儲 模塊、讀取模塊和部分搜索模塊；全分區搜索模塊，用於對FAT格式的磁碟分區中特定類型的文件進行全分區搜 索，為每一個搜索到的文件分配唯一的索引號；存儲模塊，包括N維的序列存儲單元，所述序列存儲單元用於保存所述全分區搜 索模塊搜索到的N個索引號連續的文件目錄項位置信息；根據來自部分搜索模塊的索引號 i及其附近共N個文件的目錄項位置信息，對所保存的文件目錄項信息進行更新；讀取模塊，用於判斷所要讀取的文件索引號是否在所述存儲模塊的序列存儲單元 內，若是，則直接從序列存儲單元獲取文件目錄項位置信息；否則，確定搜索起點以及搜索 方向並向部分搜索模塊發送搜索指令；待存儲模塊存儲的內容更新後，從序列存儲單元中 找到索引號i對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述 磁碟分區上的文件；
部分搜索模塊用於以來自讀取模塊的搜索起點為起點，以讀取模塊所確定的搜索 方向進行部分搜索，將搜索到的索引號i及其附近共N個文件的目錄項位置信息發送至存 儲模塊。較佳地，所述存儲模塊還保存全分區最小索引號及該索引號對應文件的全位置信 息；全分區最大索引號及該索引號對應文件的文件全位置信息；序列元素對應的最大索引 號及該索引號對應文件的文件全位置信息；以及序列元素對應的最小索引號及該索引號對 應文件的文件全位置信息；所述文件全位置信息包括文件目錄項位置信息、文件目錄項在 其所在目錄的目錄項中的位置偏移以及文件所在目錄的簇號；所述讀取模塊，用於判斷所要讀取的文件的索引號i是否在存儲模塊保存序列元 素對應的最小索引號到序列元素對應的最大索引號的範圍內，若是，則從序列元素中找到 索引號i對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟 分區上的文件；否則，在全分區最小索引號、全分區最大索引號、序列元素對應的最大索引 號和序列元素對應的最小索引號這四個索引號之間取與i的差值最小的索引號，計為k，並 以索引號k對應的文件的全位置信息為起點確定搜索方向，將索引號k與所確定的索引方 向發送至部分搜索模塊；待存儲模塊存儲的內容更新後，從序列存儲單元中找到索引號i 對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟分區上的 文件。所述讀取模塊進一步包括搜索方向確定單元，用於比較所述索引號k和i的大小，當i < 1^時，確定搜索方 向為全分區搜索的相反方向，否則確定搜索方向為全分區搜索的相同方向。所述裝置進一步包括邊界調整模塊，用於判斷部分搜索模塊所搜索到的N個索引號中的最小索引號Ml 是否小於存儲模塊中已保存的序列元素對應的最小索引號，若是，則通知所述部分搜索模塊以存儲模塊中已保存的全分區最小索引號對應文件的全位置信息為起點；或者，用於判斷部分搜索模塊所搜索到的N個索引號中的最大索引號M2是否大於 存儲模塊中已保存的序列元素對應的最大索引號，若是，則通知所述部分搜索模塊以存儲 模塊中已保存的全分區最大索引號對應文件的全位置信息為起點。由於全分區搜索產生的文件目錄項信息的數目太大，本發明方案通 過設定一定大 小的內存空間來存儲一小段連續的索引號及文件目錄項位置信息，在此基礎上通過部分搜 索的方式找到目標文件的文件目錄項位置信息。內存空間大小可以根據實際內存需求以及 系統的運行速度調整。該方案特別適用於內存受限的嵌入式系統中，可以為非目錄的方式 快速打開大量文件時，提供一種靈活的搜索方法。在一個實現了常規FAT文件系統接口的 系統中，增加本發明方案提供的文件打開方式，能保持與舊有其他文件系統接口的兼容，也 就是說，以這種方式打開的文件，能夠像以文件名打開文件後一樣，使用原來的read，write 等接口。本發明方案尤其適用於數碼相框、數碼伴侶或數位相機中，在LCD屏中顯示多幅 JPEG縮略圖中，能夠快速前後瀏覽圖片，也可以瀏覽指定索引號的文件即圖片，對於存儲在 目錄層次多的文件打開操作中，能獲得優良的效果。以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精 神和原則之內所作的任何修改、等同替換和改進等，均應包含在本發明的保護範圍之內。
權利要求
一種讀取FAT磁碟文件的方法，其特徵在於，包括如下步驟預先對FAT格式的磁碟分區中特定類型的文件進行全分區搜索，為每一個搜索到的文件分配唯一的索引號；在內存中保存N個索引號連續的文件目錄項位置信息的序列；N為自然數；判斷所要讀取的文件索引號i是否在所述序列內，若是，則直接從序列內獲取索引號i對應的文件目錄項位置信息；否則，確定搜索方向並將索引號i及其附近的共N個文件目錄項位置信息保存到序列內，並從序列中獲取目錄項位置信息；根據所述目錄項位置信息讀取文件。
2.根據權利要求1所述的方法，其特徵在於，在內存中保存如下內容全分區最小索引號及該索引號對應文件的全位置信息；全分區最大索引號及該索引號 對應文件的文件全位置信息；序列元素對應的最大索引號及該索引號對應文件的文件全位 置信息；以及序列元素對應的最小索引號及該索引號對應文件的文件全位置信息；所述文 件全位置信息包括文件目錄項位置信息、文件目錄項在其所在目錄的目錄項中的位置偏移 以及文件所在目錄的簇號；所述判斷所要讀取的文件索引號i是否在所述序列內，若是，則直接從序列內找到文 件目錄項位置信息；否則，確定搜索方向並將索引號i及其附近的共N個文件目錄項位置信 息保存到序列內，並從序列中獲取目錄項位置信息；根據所述目錄項位置信息讀取文件包 括判斷所要讀取的文件索引號i是否在序列元素對應的最小索引號到序列元素對應的 最大索引號的範圍內，若是，則從序列元素中找到索引號i對應的文件目錄項位置信息，並 根據所找到的文件目錄項位置信息讀取所述磁碟分區上的文件；否則，在全分區最小索引號、全分區最大索引號、序列元素對應的最大索引號和序列元 素對應的最小索引號這四個索引號之間取與i的差值最小的索引號，計為k，並以索引號k 對應的文件的全位置信息為起點確定搜索方向；以索引號k對應的文件的全位置信息為起點，以所確定的搜索方向進行所述類型文件 的部分搜索，搜索到包含索引號i的連續的N個索引號，將所搜索到的N個索引號對應的目 錄項位置信息保存為序列元素；並根據所保存的序列元素中、索引號i對應的文件目錄項 位置信息讀取所述磁碟分區上的文件。
3.根據權利要求2所述的方法，其特徵在於，所述為每一個搜索到的文件分配唯一的 索引號為按照搜索結果的順序號作為該文件的索引號。
4.根據權利要求2所述的方法，其特徵在於，所述序列的維數為2的正整數冪次。
5.根據權利要求2所述的方法，其特徵在於，所述以索引號k對應的文件的全位置信息 為起點確定搜索方向包括比較索引號i與索引號k的大小，當i < k時向全分區搜索的相反方向執行部分搜索， 否則向全分區搜索的相同方向執行部分搜索。
6.根據權利要求2所述的方法，其特徵在於，所述包含索引號的連續的N個索引號為索引號從i到i+N-1的N個索引號；或者，將索引號從i_ (N/2)到i+ (N/2) -1的N個索引號。
7.根據權利要求2所述的方法，其特徵在於，所述以索引號k對應的文件的全位置信息為起點，以所確定的搜索方向進行所述類型文件的部分搜索的步驟包括判斷所搜索到的N個索引號中的最小索引號Ml是否小於內存中已保存的序列元素對 應的最小索引號，若是，則將Ml保存為新的序列元素對應的最小索引號，以內存中已保存 的全分區最小索引號對應文件的全位置信息為起點，向全分區搜索的相同方向搜索所述類 型文件；或者，判斷所搜索到的N個索引號中的最大索引號M2是否大於內存中已保存的序列元 素對應的最大索引號，若是，則將M2保存為新的序列元素對應的最大索引號，以內存中已 保存的全分區最大索引號對應文件的全位置信息為起點，向全分區搜索的相反方向搜索所 述類型文件。
8.根據權利要求2至7任一項所述的方法，其特徵在於，所述以索引號k對應的文件的 全位置信息為起點，以所確定的搜索方向進行所述類型文件的部分搜索，搜索到包含索引 號i的連續的N個索引號包括在已保存的文件目錄項位置信息中查找是否有需要保留的內容，若是，則跳過所述需 要保留的內容，並更新其餘的文件目錄項位置信息。
9.一種讀取FAT磁碟文件的裝置，其特徵在於，包括全分區搜索模塊、存儲模塊、讀取 模塊和部分搜索模塊；全分區搜索模塊，用於對FAT格式的磁碟分區中特定類型的文件進行全分區搜索，為 每一個搜索到的文件分配唯一的索引號；存儲模塊，包括N維的序列存儲單元，所述序列存儲單元用於保存所述全分區搜索模 塊搜索到的N個索引號連續的文件目錄項位置信息；根據來自部分搜索模塊的索引號i及 其附近共N個文件的目錄項位置信息，對所保存的文件目錄項信息進行更新；讀取模塊，用於判斷所要讀取的文件索引號是否在所述存儲模塊的序列存儲單元內， 若是，則直接從序列存儲單元獲取文件目錄項位置信息；否則，確定搜索起點以及搜索方向 並向部分搜索模塊發送搜索指令；待存儲模塊存儲的內容更新後，從序列存儲單元中找到 索引號i對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟 分區上的文件；部分搜索模塊用於以來自讀取模塊的搜索起點為起點，以讀取模塊所確定的搜索方向 進行部分搜索，將搜索到的索引號i及其附近共N個文件的目錄項位置信息發送至存儲模 塊。
10.根據權利要求9所述的裝置，其特徵在於，所述存儲模塊保存全分區最小索引號及該索引號對應文件的全位置信息；全分區最大 索引號及該索引號對應文件的文件全位置信息；序列元素對應的最大索引號及該索引號對 應文件的文件全位置信息；以及序列元素對應的最小索引號及該索引號對應文件的文件全 位置信息；所述文件全位置信息包括文件目錄項位置信息、文件目錄項在其所在目錄的目 錄項中的位置偏移以及文件所在目錄的簇號；所述讀取模塊，用於判斷所要讀取的文件的索引號i是否在存儲模塊保存序列元素對 應的最小索引號到序列元素對應的最大索引號的範圍內，若是，則從序列元素中找到索引 號i對應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟分區 上的文件；否則，在全分區最小索引號、全分區最大索引號、序列元素對應的最大索引號和序列元素對應的最小索引號這四個索引號之間取與i的差值最小的索引號，計為k，並以 索引號k對應的文件的全位置信息為起點確定搜索方向，將索引號k與所確定的索引方向 發送至部分搜索模塊；待存儲模塊存儲的內容更新後，從序列存儲單元中找到索引號i對 應的文件目錄項位置信息，並根據所找到的文件目錄項位置信息讀取所述磁碟分區上的文 件。
11.根據權利要求10所述的裝置，其特徵在於，所述讀取模塊進一步包括搜索方向確定單元，用於比較所述索引號k和i的大小，當i <k時，確定搜索方向為 全分區搜索的相反方向，否則確定搜索方向為全分區搜索的相同方向。
12.根據權利要求10或11所述的裝置，其特徵在於，所述裝置進一步包括邊界調整模塊，用於判斷部分搜索模塊所搜索到的N個索引號中的最小索引號Ml是否 小於存儲模塊中已保存的序列元素對應的最小索引號，若是，則通知所述部分搜索模塊以 存儲模塊中已保存的全分區最小索引號對應文件的全位置信息為起點；或者，用於判斷部分搜索模塊所搜索到的N個索引號中的最大索引號M2是否大於存儲 模塊中已保存的序列元素對應的最大索引號，若是，則通知所述部分搜索模塊以存儲模塊 中已保存的全分區最大索引號對應文件的全位置信息為起點。
全文摘要
本發明公開了一種讀取FAT磁碟文件的方法，預先對FAT格式的磁碟分區中特定類型的文件進行全分區搜索，為每一個搜索到的文件分配唯一的索引號；在內存中保存N個索引號連續的文件目錄項位置信息的序列；N為自然數；判斷所要讀取的文件索引號i是否在所述序列內，若是，則直接從序列內獲取索引號i對應的文件目錄項位置信息；否則，確定搜索方向並將索引號i及其附近的共N個文件目錄項位置信息保存到序列內，並從序列中獲取目錄項位置信息；根據所述目錄項位置信息讀取文件。本發明還公開了一種讀取FAT磁碟文件的裝置。本發明方案可以在佔用較小內存空間的情況下快速讀取FAT磁碟文件。
文檔編號G06F17/30GK101833559SQ20091023721
公開日2010年9月15日 申請日期2009年11月5日 優先權日2009年11月5日
發明者何亞康, 葉凱 申請人:北京炬力北方微電子有限公司