Microsoft introduced a new "exFAT" file system a few years ago, and I
wouldn't care about it in the least, except that it is now the official
filesystem for SD-XC cards. I only care about that in that digital
cameras and such will likely only support exFAT on SD-XC cards, and I'd
like my computer, not running Windows, to be able to efficiently access
files on such cards. The problem is that Microsoft filed several patent
applications covering exFAT. One of them is application US 2009/0164440
A1, for which the US patent office has recently mailed a "Notice of
Allowance", which means that they have decided to issue the patent.
This application is titled "Quick filename lookup using name hash".
Based on the title, it sounded like they are doing what TRS-DOS 2.0 did
back in 1978, which is putting on the disk a hash table of filenames
which then refer to directory entries. TRS-DOS did that so that it
usually only needed to read two sectors to look up a file, the HIT (Hash
Index Table) sector, and the actual directory sector containing the
file's directory entry. Otherwise they might have had to read multiple
directory sectors to find the file if it existed, and all of the
directory sectors if it did not.
The claims of the patent are a little difficult to interpret. They
refer to "a first one or more computer readable storage media having
computer executable instructions...". This is basically referring to
the disk/flash/etc. the operating system is booted from. They refer to
"a second one or more..." which is the disk/flash/etc. which holds the
file system in question.
Here's are two of the independent claims:
1. A first one or more computer readable storage media having computer
executable instructions that, when executed on at least one processor,
configure the at least one processor to perform a method of detecting if
a target file name exists on a second one or more computer readable
storage media, the method comprising:
(A) determining a name hash from the target name;
(B) determining if the name hash corresponds to a directory entry
set name hash value, the directory entry set name hash value
corresponding to one of a plurality of directory entry sets, each of
the plurality of directory entry sets stored on the second one or
more computer readable storage media;
(C) determining if the target name matches a directory entry set
name corresponding to the one of the plurality of directory entry
sets after step (B) determines the name hash corresponds to the
directory entry set name hash value; and
(D) indicating that the target name exists after step (C) determines
the target name matches the directory entry set name.
19. A method of detecting if a target file name exists, the method
executing on one or more processors, the method comprising:
(A) determining a file name hash from the target file name;
(B) determining if the file name hash corresponds to a directory
entry hash value, the directory entry hash value corresponding to
one of a plurality of directory entries;
(C) determining if the target file name matches a file name, the
file name corresponding to the one of the plurality of directory
entries after step (B) determines the file name hash corresponds to
the directory entry hash value; and
(D) indicating that the target file name exists after step (C)
determines the target file name matches the file name corresponding
to the one of the plurality of directory entries.
These seem to be to be to be *exactly* what TRS-DOS 2.0 did as early as
1978, so it seems possible that TRS-DOS could be used as prior art to
invalidate at least these independent claims, and quite possibly some of
the dependent claims as well.
So my question is, are there any published works documenting the TRS-DOS
file system on-disk format, especially the use of the HIT table, other
than "TRS-80 Disk and Other Mysteries" by H. C. Pennington?