Slashdot Mirror
Microsoft to Charge for FAT File System
pario writes "According to Microsoft, the Redmond company is going to charge a license fee for any product that is formatted in FAT by the manufacturer. Any manufacturer of compact flash memory cards or digital cameras may end up paying Microsoft as much as $250,000 for the use of the file format. The FAT File System is covered by several US patents."
I see nothing wrong with it. They own the patents, so they have the right to sell it to whoever pays. BTW, slashdot post is a bit misleading.
"Pricing for this license is US$0.25 per unit with a cap on total royalties of $250,000 per licensee."
The $250K is the cap; that means, that is the maximum amount they will charger per license holder for the use of the FAT. Just thought it came across incorrectly.
A blog like any other.
Is there a win32 ext2/3 filesystem driver out there anywhere?
Searching for "win32 ext2" yields this as the first link.
WWTTD?
Where do you get your information? That number is inaccurate:
NTFS, FAT, FAT32
A blog like any other.
If you RTFA (Wait, what was I thinking! This is /.) you would find that this only applies to consumer electronics (DVD players, TV's, etc.) and portable memory devices, like Compact Flash and those little USB memory sticks. At least for right now. And it only counts if it comes preformatted from the mfr.
I suspect this will drive most manufacturers to not format their media, or it will drive them to an open format, like jffs.
In the USA, we like stuff watered down, like beer, television, and freedom.
RTFA. (Go ahead, give me the old "You must be new here" - joke. :)
:)
The linked article does not mention home computers. Microsoft wants license fees from:
1) Manufacturers of solid state removeable memory devices
and
2) Manufacturers of certain types of consumer electronics that use the FAT file system:
portable digital still cameras
portable digital video cameras
portable digital still/video cameras
portable digital audio players
portable digital video players
portable digital audio/video players
multifunction printers
electronic photo frames
electronic musical instruments
standard televisions
Do you think you'll ever buy one of those? Then it'll affect you.
"I'd rather have a full bottle in front of me than a full frontal lobotomy"
http://www.vcnet.com/bms/departments/innovation.ht ml
Rich.
libguestfs - tools for accessing and modifying virtual machine disk images
As I read the license options, this applies only to devices that come pre-formatted as FAT. No mention of software. Limiting the ability of others to write FAT-compatible software would be a bad strategic move on MS's part - anyone who currently has another OS interoperating with Windows via FAT may be just as likely to ditch Windows as they are the "other" OS.
Do these devices really need compatibility with "dead" operating systems?
The second patent seems to another concerning filename formats. I haven't bothered to look at the other 2.
That doesn't mean they won't go there, just that they haven't yet. Still, the typical knee-jerk reactions here are as yet unwarrented.
It's very good move by MS.
/. -- when you're done writing around 200k files to flash media it was already past erasure limit for those sectors at the beginning i.e. media was destroyed.
FAT is a terrible format for Flash media, because it constantly updates some variables in first several sectors of the disk. The effect was mentioned some time ago on
So it might actually give some incentive for vendors to move to JFFS or similar FS _designed_ with this flash-specific limitation in mind.
rrw
Bastard Operator From 193.219.28.162
It's not like they provide very much information, but here are the patent abstracts, plus links to the full patents. They sure don't seem interesting, and they all seem to deal with the coexistence of long and short filenames. All of this wouldn't be patentable in Europe.
United States Patent 5,579,517
Reynolds , et al. November 26, 1996
Common name space for long and short filenames
Abstract
An operating system provides a common name space for both long filenames and short filenames. In this common namespace, a long filename and a short filename are provided for each file. Each file has a short filename directory entry and may have at least one long filename directory entry associated with it. The number of long filename directory entries that are associated with a file depends on the number of characters in the long filename of the file. The long filename directory entries are configured to minimize compatibility problems with existing installed program bases.
United States Patent 5,745,902
Miller , et al. April 28, 1998
Method and system for accessing a file using file names having different file name formats
Abstract
A multiple file name referencing system stores multiple file names in a file. These multiple file names include an operating system formatted file name and an application formatted file name. When an operating system formatted file name is created or renamed, the multiple file name referencing system automatically generates an application formatted file name having a potentially different format from, but preserving the extension of, the operating system formatted name. The multiple file name referencing system similarly generates an operating system formatted name upon creation or renaming of an application formatted name. A B-tree is provided which contains an operating system entry for the operating system formatted name and an application entry for the application formatted name, each entry containing the address of the same file to which both names refer. The multiple file name referencing system converts the operating system formatted file name to the application formatted file name by accessing the B-tree with reference to the operating system entry, and vice versa. As a result, either file name can be used to directly reference the file without requiring additional file name translation.
United States Patent 5,758,352
Reynolds , et al. May 26, 1998
Common name space for long and short filenames
Abstract
An operating system provides a common name space for both long filenames and short filenames. In this common namespace, a long filename and a short filename are provided for each file. Each file has a short filename directory entry and may have at least one long filename directory entry associated with it. The number of long filename directory entries that are associated with a file depends on the number of characters in the long filename of the file. The long filename directory entries are configured to minimize compatibility problems with existing installed program bases.
United States Patent 6,286,013
Otoh, patents do not make this discrimination. The only exception is that if you used a patented technique before it was patented (but you never published it, so your work cannot be considered as prior art), then you can continue to use this technique *for personal use* even after the patent has been granted (which excludes any commercial use afaik, though I'm not certain of this). If you independently came up with it after the patent was granted, you're completely out of luck.
The reasoning is that patents exist to protect big investments in R&D, which generally wouldn't have occurred if there was no way to safeguard the results from imitation with patents. So patents are considered as some kind of necessary evil (temporary monopolies), required to promote innovation and disclosure. Of course, in case of software patents this reasoning is almost never true and you are pretty much stuck with only the negative sides.
Donate free food here
If you looked it up, you'd see that the patents listed on microsoft's page are not for FAT itself, but for long filename extensions to it.
The patents listed were filed in '92, 95, 96, and 97. I haven't looked into the details of the patents, but I assume the date those features were published would be during the mareting of windows 95, so the first 2 at the very least are within the 1 year publish-file grace period.
Your credit card information wants to be free.
The validity of one claim typically does not invalidate the others. My patent lawyers call this a layered approach, where the first claims are purposely broad in an attempt to grab as much IP ground as possible. Subsequent numbered claims in the patent are become more specific. They take this land grabbing approach essentially because they can.
"Microsoft needs to defend this patent lest they lose it."
You're confusing Trademark law with Patent law; Trademarks must be defended lest they be abandoned, patents can be enforced against some, all, or none of those infringing on the patent at the patent-holder's whim. The entire practice of "defensive patents" rests on this.
U.S. Patent #5,579,517 Common name space for long and short filenames
An operating system provides a common name space for both long filenames and short filenames. In this common namespace, a long filename and a short filename are provided for each file. Each file has a short filename directory entry and may have at least one long filename directory entry associated with it. The number of long filename directory entries that are associated with a file depends on the number of characters in the long filename of the file. The long filename directory entries are configured to minimize compatibility problems with existing installed program bases.
U.S. Patent #5,745,902 Method and system for accessing a file using file names having different file name formats
A multiple file name referencing system stores multiple file names in a file. These multiple file names include an operating system formatted file name and an application formatted file name. When an operating system formatted file name is created or renamed, the multiple file name referencing system automatically generates an application formatted file name having a potentially different format from, but preserving the extension of, the operating system formatted name. The multiple file name referencing system similarly generates an operating system formatted name upon creation or renaming of an application formatted name. A B-tree is provided which contains an operating system entry for the operating system formatted name and an application entry for the application formatted name, each entry containing the address of the same file to which both names refer. The multiple file name referencing system converts the operating system formatted file name to the application formatted file name by accessing the B-tree with reference to the operating system entry, and vice versa. As a result, either file name can be used to directly reference the file without requiring additional file name translation.
U.S. Patent #5,758,352 Common name space for long and short filenames
An operating system provides a common name space for both long filenames and short filenames. In this common namespace, a long filename and a short filename are provided for each file. Each file has a short filename directory entry and may have at least one long filename directory entry associated with it. The number of long filename directory entries that are associated with a file depends on the number of characters in the long filename of the file. The long filename directory entries are configured to minimize compatibility problems with existing installed program bases.
U.S. Patent #6,286,013 Method and system for providing a common name space for long and short file names in an operating system
An operating system provides a common name space for both long filenames and short
Nothing for 6-digit uids?
The GIF file format isn't patented. You can't have a patent on file formats, the order of fields in a sector, etc. There is nothing innovative in that.
... instead of following the compression algorithm.
The hardware process of the LZW compression algorithm was what as patented. You can write GIF files without using compression (literal, clear dictionary, literal, clear dictionary
Here, Microsoft's patents relate to algorithms for fitting long filenames onto a file system that only supports short filenames. They do NOT have a patent on the (V)FAT filing system. However, in working with those filing systems you may need to use algorithms which Microsoft managed to patent.
Does my bum look big in this?
yes NTFS is indeed covered under many patents and trademarks.
...as witnessed by the article yesterday on using windoze DLLs in *NIX to get write access to NTFS media...
the format has not fully been determined, nor has it been fully released by MS.
The problem with it is, their implementation of long filenames for FAT was in the hands of people outside of Microsoft well before the one-year prior drop-dead date for the application. Before it was Windows 95, it was codenamed Chicago and it was available to ISV's beginning of 1994 (as in it was available to developers outside of the company BEFORE April 24 1994...) - I know, I was part of that beta program. It does not matter WHAT you have with those people in the way of non-disclosure, they're customers and the moment you put an improvement in the hands of anyone outside of your company, the clock on the filing date starts ticking because you've revealed it to the world as far as the law is concerned.
The first patent, at least, is invalid by their OWN prior art.
I am not merely a "consumer" or a "taxpayer". I am a Citizen of the State of Texas
A Patent, in and of itself, doesn't care about those things. So, in actuality, Microsoft could ask for royalties on each and every Patent on this list and legitmately so unless each are invalidated or your implementation is somehow found to not infringe.
Let's go over the Patents one by one, shall we?
5,579,517 - Common name space for long and short filenames. Filed for on April 24, 1995. This one only impacts you if you're using a Common Name Space for long and short filenames. Basically, the scheme they deployed for Chicago- references a preferred embodiment for MS-Dos 5.0 that was apparently handed to the USPTO as part of the application. Very much likely to be invalidated, though, by their OWN prior art release of Chicago to the world in December of 1993. This describes a scheme for handling long and short filenames correctly. If it's not invalidated, you might run afoul of it trying to do a VFAT type implementation.
5,745,902 - Method and system for accessing a file using file names having different file name formats. Filed for on July 6, 1992. Reading the abstract of this one, you'd have to allow renaming of just the name and preserving the extention for the purposes of keeping track of the filetype. Abstract explicitly mentions the use of a B-tree (Limits the scope of what they're claiming- you can possibly sidestep things by using red-black, AVL, etc...). They don't appear to have troubled this application with a possible prior art release, but unless you're doing the exact same thing for handling renames, etc. I don't think you're impacted by this one.
5,758,352 - Common name space for long and short filenames. Filed on September 5, 1996. A cursory reading of the Patent filing made by Microsoft leads one to believe that this is a re-application of the 5,579,517 Patent. While I'm not an IP lawyer, they appear to be claiming the same basic things in both documents. If this, in fact, the case, the 5,579,517 Patent's invalidation would likely invalidate this one. You would probably run afoul of this Patent if you attempted to implement a VFAT style filesystem.
6,286,013 - Method and system for providing a common name space for long and short file names in an operating system. Filed on January 28, 1997. This one is an EXPLICIT Patent-style description of how Windows 95/98/Me handles long filenames on an x86-32 platform. Cute. The applicablity of this Patent to anything other than an exact clone of Windows 95/98/Me is doubtful at best. They explicitly mention things like BIOS interrupts and x86 register names in their claims. Better yet, the preferred implementation was deployed to the World at large in Windows 95- TWO YEARS PRIOR to the filing date.
You should consult a Patent attorney before making any decisions regarding this request for royalties from Microsoft. However, having said this, I'd feel fairly comfortable about the situation overall based on the observations made above.
I am not merely a "consumer" or a "taxpayer". I am a Citizen of the State of Texas
While flash is random access and doesn't have a physical seek latency, it is indeed a block device. On reads this isn't evident, but on writes it is. You can only overwrite whole blocks at a time. This is why it actually does make some sense to use traditional file systems on flash devices.
The enemies of Democracy are
Maybe in theory, but it's not like the patent guys have time to verify complete documentation by sitting down and re-implementing each and every application using only the applicant's docs. Considering the way the patent system has been bent, folded, spindled, and mutilated in recent years (e.g., Amazon's one-click, Netflix's business model), less-than-complete disclosure starts to look like the least of the patent office's worries.
Ok, I'll bite. IMHO, NTFS is about as different from FAT as any Real file system.
FAT is very simplistic, there's essentially two structures. One is the File Allocation Table, which keeps track of which blocks are used in what way (e.g. part of a file, last block in a file, bad block, free block). Then there are the directories, which are just arrays of inodes, which also contain the file names. The inode points to the first block, the FAT tells which blocks follow. There are no permissions, hard links, symlinks, file types (other than regular vs. directory). The FAT and root directory are stored at the beginning of the volume.
Now to NTFS. (Disclaimer: NTFS is complex and I don't claim to fully understand it.) NTFS Has a Master File Table, which has inodes for every file on the volume (which are seperate from filenames, like on Unix file systems). NTFS supports hard links, symlins, attributes, permissions (based on Access Control Lists), and sparse files. File names are looked up in b-trees rather than sequential lists. Instead of listing every single block occupied by a file, it uses start, length pairs (AKA extents). NTFS uses journaling and supports transparent compression and encryption. Several structures are stored in the middle of the volume to minimize seek times.
Compare this to traditional Unix file systems (UFS, FFS, ext2). There's an inode table at the beginning of the volume. Inodes encode ownership, permissions (based on owner and group), a few attributes (e.g. setid bits), often part of the block list or the content of the file. Directories are sequential lists of (inode number, file name) pairs. Hard links and symlinks are supported, as are special files like devices and FIFOs. No extended attributes, no B-trees, no ACLs, no compression, no encryption, no journaling. (although many/all of these have been added at one point or another to ext2 and FFS, sometimes preserving compatibility). Important structures are replicated in various parts of the volume to enhance speed and reliability.
As you can see, NTFS is a very advanced filesystem, supporting many features that Linux filesystems are now beginning to have. FAT is hardly any more advanced than the very minimum required to store and retrieve data. Unix filesystems are somewhere in between, supporting features important to Unix systems such as permissions and device nodes, while at the same time keeping it simple. Personally, I think a the traditional Unix filesystems are much closer to FAT than NTFS is.
Please correct me if I got my facts wrong.
The FAT file system format was never patentable to begin with, since there was nothing particularly novel about it when it was created. What's more, it has been in use for more than 20 years (the lifetime of a patent) and nothing about it was patented within a year of its implementation and release to the public. So, Microsoft has no rights here. Its claims to the contrary are absurd.
As you can see, NTFS is a very advanced filesystem, supporting many features that Linux filesystems are now beginning to have.
You are confusing feature bloat with being advanced. NTFS is a feature-bloated file system, but none of the features they crammed into that file system are anything new, and many of them will never make it into mainstream UNIX file systems because they are just not a good engineering tradeoff.
Compare this to traditional Unix file systems (UFS, FFS, ext2).
Your comments imply an incorrect timeline. By the time NTFS came out, there were already several UNIX file systems with a comparable feature set. Furthermore, a number of key NTFS features existed in name only for several years, until Microsoft finally got around to implementing them.
Uhhh, neither is FAT.
FAT has fixed size directory indexes. If you have half a dozen files in a directory, you are discarding most of the directory index. If you make the directory index small then you can't store lots of files in a single directory. It's a no-win tradeoff. A space efficient filesystem would use dynamically resizable directory indexes.
The FAT itself is a bitmap (one FAT entry for every single block) with each entry referencing the next entry (like a linked list). You find the first block of the file from the directory index. Imagine how inefficient this is when the file has contiguous blocks. Why not use extents? That would greatly reduce the space requirements for the FAT.
The original FAT16 limited you to only 65536 possible block numbers. If you have a 512MB USB key then that means every block is 8kB. So on average you waste 4kB per file; 1000s of files means many megabytes of wasted space. Another glaring example of FAT inefficiency. A space efficient filesystem would offer variable sized blocks.
For FAT to perform efficiently you must load the entire FAT into memory (otherwise traversing the list of blocks is a nightmare of head seeks). This makes it vulnerable to files being corrupted or lost if there is sudden power failure or the disk is removed. The "saving grace" is that the FAT is protected because it never had the chance to be flushed out of RAM, so the filesystem is at least consistent. Whether this behaviour is good or bad seems to be a matter of debate; my opinion is that the data is more important than the damn filesystem and FAT fails in that regard.
The only thing FAT has going for it is incredible simplicity which made sense on the woefully underpowered and underfeatured IBM PC of 1980. But in terms of efficiency it is exactly the same as many other bitmap-based filesystems. FAT was also heavily optimised for 320kB (that's not a typo) floppy disks because the FAT would fit into a single 512 byte sector. It makes no sense in a modern world with gigabyte removable media.
These USB keys should be using something clever like CRAMFS but with journalling and "balanced writes" (each block gets roughly equal write time) to preserve the life of the key.