Products > Programming
FatFS sorted directory listing, but without needing a large RAM buffer
peter-h:
The standard code (this is mine so not as smart as people here would expect) gets filenames in the order in the directory+FAT.
--- Code: ---/*
* Scans directory, fill array flist with the names, sizes and attribs, up to maxcount (each entry takes 17 bytes)
* Returns # of files actually found in fcount.
* The array is not initialised so you have to use fcount to determine how many filenames were loaded.
* Any filename shorter than 12 bytes (the 12 includes the dot) has a 0x00 appended.
* Directories are found also.
* Each entry is 17 bytes:
* 0..11 filename
* 12..15 filesize (uint32_t, LSB in byte 12)
* 16 attrib byte:
*
* #define AM_RDO 0x01 Read only
* #define AM_HID 0x02 Hidden
* #define AM_SYS 0x04 System
* #define AM_DIR 0x10 Directory
* #define AM_ARC 0x20 Archive
*
*/
uint32_t get_file_list( char *flist, uint32_t maxcount )
{
FRESULT fr; /* Return value */
DIR dj; /* Directory object */
FILINFO fno; /* File information */
uint32_t fcount=0; // # of files found so far
uint32_t idx=0; // index into flist
fr = f_findfirst(&dj, &fno, "", "*"); // Start to search for any file
while (fr == FR_OK && fno.fname[0] && maxcount) // Repeat while an item is found
{
// debug_thread_printf("%.12s", fno.fname);
memcpy(&flist[idx],&fno.fname,12);
flist[idx+12] = 0x000000ff & fno.fsize;
flist[idx+13] = (0x0000ff00 & fno.fsize) >> 8;
flist[idx+14] = (0x00ff0000 & fno.fsize) >> 16;
flist[idx+15] = (0xff000000 & fno.fsize) >> 24;
flist[idx+16] = fno.fattrib;
idx+=17;
fcount++;
maxcount--;
fr = f_findnext(&dj, &fno); // Search for next item
}
f_closedir(&dj);
return fcount;
}
--- End code ---
It is 2MB which is FAT12 and I think the max # of files in root (no subdirs are supported in this case) is 512. Sorting these conventionally will need a lot of RAM. The names are limited to 8.3 (the LFN build option bloats the code quite a lot).
I was thinking of a rather crude method, like this:
Initialise a uint64_t smallest_name = 0xffffffffffffffff
Do one directory scan. Load each filename, left-justified and padded with trailing spaces, into a uint64_t, but in big-endian order, so you have a number which is a) unique for the filename and b) comparing two of these numbers will yield an alphabetical-equivalent comparison. Determine the "smallest" name file in the list. Set smallest_name to that. Display that filename / send it to the client / whatever.
Now scan the directory again, looking for the smallest name, but not smaller than the last one. When found, display that one.
Repeat until no more files.
So if you have 500 files you scan the dir 500 times, but with FatFS running on a FLASH (or RAM) disk this is very fast - around 500kbytes/sec on a 168MHz arm32.
Surprisingly, a search did not dig up anything like this (apart from the usual of people asking and getting no replies) so I wonder if there are slicker ways. This is a simple file listing function running in an HTTP server, to deliver a file listing to a client browser.
ledtester:
--- Quote from: peter-h on June 21, 2022, 09:08:46 am ---This is a simple file listing function running in an HTTP server, to deliver a file listing to a client browser.
--- End quote ---
How about having the client's browser sort the results using javascript?
ejeffrey:
This is a reasonably standard way to find the M smallest entries in a list. Normally you wouldn't do it for every element in a large list because you are trading N^2 time and IO for N memory but if you don't have the memory that's just what you have to do.
Another thing you can do is a indirect sort. Instead of sorting the data in memory, sort an array of index values. Instead of 512*11 bytes you would only need 512*2. With a bit of cleverness using a combination of merge sort and quick sort you should be able to do that in 512 bytes. The downside of this is that you have a lot more random IO. Also 512 bytes is a lot better than kB but that might still be too much.
peter-h:
--- Quote ---How about having the client's browser sort the results using javascript?
--- End quote ---
I did wonder about that but how futureproof / browser-compatible is that? So much JS breaks as browsers are updated...
--- Quote ---you should be able to do that in 512 bytes
--- End quote ---
I wondered about a CRC16 hash, so 512 x 2 bytes storage, and you check for a collision and if you get one then you just serve it unsorted :)
mariush:
It would make more sense to have the file list sorted in browser. You can add more cleverness like "group files by extension, then sort each group by filename" or stuff like that.
If you want it sorted by in the microcontroller, I'd just build an array with the first or two characters and the sector where the file info is stored so basically 4-6 bytes per entry .. sort this list and then print each full file name by re-reading that sector to get the full file name.
If it's really FAT12 there's other limitations you could take advantage of like the file names and extensions always being uppercase... you could use each top bit of those 12 possible characters for something (like position in listing for example... as you only need 9 bits if the maximum number of entries in a folder is 512
also you wouldn't need to store the file size in 4 bytes because the maximum fat12 can do is 32 MB
Navigation
[0] Message Index
[#] Next page
Go to full version