TRS-DOS as possible prior art for MS patent on exFAT, and reference request

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?

This entry was posted in Patents, Retrocomputing, Software. Bookmark the permalink.

3 Responses to TRS-DOS as possible prior art for MS patent on exFAT, and reference request

  1. Teuxe says:

    I am also upset by such patent acceptance. I am pretty sure some other filesystems may also already make use of such hash tables to boost accesses to files in a hierarchy; hash tables sounds so close to “fast accesses”… if someone has any information?

    The subsidiary question is also: if you get such documentation, do you have enough political weight to break this Microsoft patent? Who should we address the claim to? (The US patent office is less competent in judging of the legality of deposited patents, when a lot of money is on -or even under- the table.)

  2. Eric says:

    I have no idea what you’re referring to by “fast accesses”. There may well be other file systems that used file name hashes prior to TRS-DOS, but I don’t have any concrete information about them.

    I don’t have any “political weight” whatsoever. The most I can do is try to share information about prior art so that it is available to anyone who is able to request a reexamination of the patent, or to litigate it.

    Note that the particular patent I reference has other claims for which TRS-DOS may not serve as prior art, and also that this was not the only patent application relating to exFAT. I wouldn’t count on the patents being invalidated any time soon.

  3. Eric says:

    I found another instance of a file system using a hash table for fast file lookup, the HP 64000 development system, introduced in 1979. The directory format is described on page 10 and 12 of the October 1980 issue of the Hewlett-Packard Journal.

Leave a Reply