Hardware-Accelerated FAT filesystem searching

[gardners]

Is your feature request related to a problem? Please describe. Considerable discussion is occurring as to how we can make HYPPO and the MEGA65 better live with subdirectories. A key challenge is that the HYPPO ROM is very space-limited, and thus remembering paths is currently a bit problematic. And even if we did, HYPPO is not particularly fast at traversing through a FAT file system to set the CWD to a particular directory. The findfile logic in HYPPO is also already quite large, as well, occupying space that could be better used for other functions, if we could simplify it.

Describe the solution you'd like

1. Enhance the SD card controller to have a new request type "find file in file system" that works by populating the SD card sector buffer with the request details (path and file name, file system location on SD card etc), that when triggered, does all the file system searching, including using LFNs, and returns the first or next match against the search specification.
2. Behind the scenes, allow the SD card controller to cache a modest number of sectors on targets that have enough BRAM free, to further accelerate the searching of previously accessed directories (and probably FAT sectors), so as to make this search function even faster.
3. Modify HYPPO to use this hardware function instead of its software implementation of findfile(), resulting in a much faster solution, as well as freeing up quite a bit of space in HYPPO, at least enough to have a copy of the search specification block, that would be required to be maintained by HYPPO to support its findnext() functionality.

Describe alternatives you've considered Persisting with the software implementation, which continues with the existing challenges.

Additional context This functionality would allow for the better handling paths in HYPPO, including remembering the full path to each mounted disk image, in parallel to the current working directory of the running application.

[gardners]

Positive side effect, is that it will greatly improve the speed of the most common SD card file operations.

[gardners]

Also, as it only reads the SD card, not modifies it, this functionality can be exposed to applications that want to access the SD card directly.

[gardners]

An optional extension would be to report if a file is fragmented or not, so that the disk mount logic can be simplified in HYPPO, also.

[gardners]

First, some house-keeping to track the request:

1. Version of status information (to allow for future improvements / changed layouts) (1 byte)
2. Status: $00 = not started, $01 = in progress, $02 = found match, $E0 = Error: not found, $EE = Error: endless loop detected, $FF = interrupted by freezing, search must be restarted (1 byte)
3. Start offset in the sector buffer of the requested path (which must be null-terminated) (2 bytes)
4. File flag bits that must be set (eg system, hidden) (1 byte)
5. File flag bits that must be clear (eg system, hidden) (1 byte)

The request would also need to know:

0. Which SD card bus (1 byte)
1. Sector number of first FAT sector (4 bytes)
2. Cluster number of first true cluster (typically =2) (1 byte)
3. Sector number of first true cluster (4 bytes)

With those 16 bytes, it has all the information it needs to know to traverse a FAT file system.

Then we can add information about where in the traversal we are up to:

1. Current cluster in search (set to zero for findfirst() functionality) (4 bytes)
2. Current sector in current cluster (1 byte)
3. Resolved absolute sector number of the above (4 bytes)
4. Current directory entry in current cluster (x32 to yield offset in sector) (1 byte)
5. Copy of FAT directory entry for the most recent match (32 bytes)

That is, with another 42 bytes, we have a complete record of where in the search we are up to.

Thus the total request needs to use only 16+42 = 58 of the 512 bytes of the sector buffer, and thus could allow absolute paths of up to 512 - 58 = 554 bytes (null termination can be implied, if the path extends to the end of the sector buffer).

For longer paths, multiple calls would be required, and could be handled by munging the starting point of the search. But this should not be required.

[gardners]

The probable algorithm would be:

1. Load the file system info and initial search point into internal buffers in the SD card controller.
2. Set initial offset of path to be searched for.
3. Determine if path element is terminal (ends in null, or end of sector buffer, or if a / character occurs first), so that it knows if searching for a directory, or searching for a file with the indicated flags set and cleared.
4. Load initial directory sector
5. For each directory entry slot in the sector, update current LFN OR test accumulated LFN and 8.3 name for match.
6. If a match, return the match, or proceed to the next path element in step (3).
7. If not a match, advance to next directory entry in the sector, or to the next sector in the directory cluster, or to the next directory cluster, or terminate with FILE NOT FOUND. Go to step (3).