2 Design and implementation

A FAT file system is composed of four different sections.

1. The Boot Sector (aka Partition Boot Record, BIOS Parameter Block or Reserved Sector). This is always the first sector of the partition and includes some basic file system information (in particular, its type), pointers to the location of the other sections and the operating system's boot loader code.
2. The FAT Region. This contains two copies of the File Allocation Table for the sake of redundancy. These are maps of the partition, indicating how the clusters are allocated.
3. The Root Directory Region. This is a Directory Table that stores information about the files and directories in the root directory. With FAT32 it can be stored anywhere in the partition, however with earlier versions it is always located immediately after the FAT Region.
4. The Data Region. This is where the actual file and directory data is stored and takes up most of the partition. The size of files and subdirectories can be increased arbitrarily (as long as there are free clusters) by simply adding more links to the file's chain in the FAT. Note however, that each cluster can be taken only by one file, and so if a 1KB file resides in a 32KB cluster, 31KB are wasted.

The Boot Sector is of the following format:

Byte Offset	Length	Description
0	3	Jump instruction (to skip over header on boot)
3	8	OEM Name (padded with spaces)
11	2	Bytes per sector
13	1	Sectors per cluster
14	2	Reserved sector count (including boot sector)
16	1	Number of file allocation tables
17	2	Number of root directory entries
19	2	Total sectors (bits 0-15)
21	1	Media descriptor
22	2	Sectors per file allocation table
24	2	Sectors per track
26	2	Number of heads
28	4	Hidden sectors
32	4	Total sectors (bits 16-47)
36	1	Physical drive number
37	1	Current head
38	1	Signature
39	4	ID
43	11	Volume Label
54	8	FAT file system type (e.g. FAT, FAT12, FAT16, FAT32)

2.1 File Allocation Table

A partition is divided up into identically sized clusters, small blocks of contiguous space. Cluster sizes vary depending on the type of FAT file system being used and the size of the partition, typically cluster sizes lie somewhere between 2KB and 32KB. Each file may occupy one or more of these clusters depending on its size, a file is represented by a chain of these clusters (referred to as a singly linked list). However these chains are not necessarily stored adjacently on the disk's surface but are often instead fragmented throughout the Data Region.

The File Allocation Table (FAT) is a list of entries that map to each cluster on the partition. Each entry records one of five things:

• the address of the next cluster in a chain
• a special end of file (EOF) character that indicates the end of a chain
• a special character to mark a bad cluster
• a special character to mark a reserved cluster
• a zero to note that that cluster is unused

Each version of the FAT file system uses a different size for FAT entries. The size is indicated by the name, for example the FAT16 file system uses 16 bits for each entry while the FAT32 file system uses 32 bits. This difference means that the File Allocation Table of a FAT32 system can map a greater number of clusters than FAT16, allowing for larger partition sizes with FAT32. This also allows for more efficient use of space than FAT16, because on the same hard drive a FAT32 table can address smaller clusters which means less wasted space.

FAT entry values:

FAT12	FAT16	FAT32	Description
0x000	0x0000	0x00000000	Free Cluster
0x001	0x0001	0x00000001	Reserved Cluster
0x002 - 0xFEF	0x0002 - 0xFFEF	0x00000002 - 0xFFFFFFEF	Used cluster; value points to next cluster
0xFF0 - 0xFF6	0xFFF0 - 0xFFF6	0xFFFFFFF0 - 0xFFFFFFF6	Reserved values
0xFF7	0xFFF7	0xFFFFFFF7	Bad cluster
0xFF8 - 0xFFF	0xFFF8 - 0xFFFF	0xFFFFFFF8 - 0xFFFFFFFF	Last cluster in file

2.2 Directory Table

A Directory Table is a special type of file that represents a directory. Each file or directory stored within it is represented by a 32 byte entry in the table. Each entry records the name, extension, attributes (archive, directory, hidden, read-only, system and volume), the date and time of creation, the address of the first cluster of the file/directory's data and finally the size of the file/directory.

Aside from the Root Directory Table in FAT12 and FAT16 file systems which occupies the special Root Directory Region location, all Directory Tables are stored in the Data Region.

Legal characters for DOS file names include the following:

• Upper case letters A-Z
• Numbers 0-9
• Space (though trailing spaces are considered to be padding and not a part of the file name)
• ! # $ % & ( ) - @ ^ _ ` { } ~
• Values 128-255

Directory entries, both in the Root Directory Region and in subdirectories, are of the following format:

Byte Offset	Length	Description
0	8	DOS file name (padded with spaces) The first byte can have the following special values: 0x00 Entry is available and no subsequent entry is in use 0x05 Initial character is actually 0xE5 0x2E 'Dot' entry; either '.' or '..' 0xE5 Entry has been previously erased and is now available
8	3	DOS file extension (padded with spaces)
11	1	File Attributes The first byte can have the following special values: Bit Mask Description 0 0x01 Read Only 1 0x02 Hidden 2 0x04 System 3 0x08 Volume Label 4 0x10 Subdirectory 5 0x20 Archive 6 0x40 Unused 7 0x80 Unused An attribute value of 0x0F is used to designate a long file name entry.
12	1	Reserved
14	4	Time of Creation
18	2	Last Access Time
20	2	EA-Index (used by OS/2)
22	4	Last Modified Time
26	2	First cluster
28	4	File size

Long File Names (LFN) are stored on a FAT32 file system using a trick - adding phoney entries into the Directory Tables. The entries are marked with a Volume Label attribute which is impossible for a regular file and because of that they're ignored by most old MS-DOS programs. Each phoney entry can contain up to 13 UCS-2 characters (26 bytes), gaining about 15 bytes in addition to the old 8 + 3 by using fields in the record which contained file size or time stamps (but for security versus disk checking tools the starting cluster field is left unused with a 0 value). See 8.3 for additional explanations.

LFN entries use the following format:

Byte Offset	Length	Description
0	1	Sequence Number
1	10	Name characters (five UTF-16 characters)
11	1	Attributes (always 0x0F)
12	1	Reserved (always 0x00)
13	1	Checksum of DOS file name
14	12	Name characters (six UTF-16 characters)
26	2	First cluster (always 0x0000)
28	4	Name characters (two UTF-16 characters)

3 FAT licensing

On December 3 2003, Microsoft announced it would be offering licenses for use of its FAT specification and "associated intellectual property". [2] at the cost of a US $0.25 royalty per unit sold, with a $250,000 maximum royalty per license agreement. In particular, Microsoft targetted the producers of consumer devices (such as digital cameras and PDAs) which make use of removable solid state media that can also be inserted into home computers (such as Compact Flash cards and USB pen drives).

To this end, Microsoft cited four patents on the FAT filesystem as the basis of its intellectual property claims.

Several technical commentators hold[3] that the FAT filesystem specification itself could not be patented. As Microsoft first derived it from CP/M in 1976, no patent could still apply to the original implementation. Analysis of the four patents show that all pertain to the "long filenames" backwards compatibility feature found in Windows 95.

• US Patent #5,745,902 - Method and system for accessing a file using file names having different file name formats. Filed July 6, 1992. This covers the ability to access the same file with both a long and short filename, e.g. "Microsoft.txt" and "MICROS~1.TXT". This covers the basic fact of pointing several file entries with different filenames at the same actual file data, the method of translating from a long name to an MS-DOS compliant 8.3 filename, and the method of resolving filename clashes (e.g. creating short names MICROS~2.TXT, MICROS~3.TXT and so on), and cross-referencing the long and short filenames for a file. It is unclear that this patent would be infringed in the implementation of a FAT filesystem without explicit long filename capabilities. The first claim has prior art in the form of hard links in older file systems.

• US Patent #5,579,517 - Common name space for long and short filenames. Filed for on April 24, 1995. This covers the method of using the file meta-data table normally used only for short filenames to store a number of "fake" entries which hold the long filename data. This patent was challenged by the Public Patent Foundation and its claims were rejected on September 14 2004, due to prior disclosure of the claimed techniques in patents 5,307,494 and 5,367,671. [4]

• US Patent #5,758,352 - Common name space for long and short filenames. Filed on September 5, 1996. This is very similar to 5,579,517, however it has not yet been challenged.

• US Patent #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 claims on the methods used when Windows 95, Windows 98 and Windows Me expose long filenames to their MS-DOS compatibility layer. It does not appear to affect any third party implementations outwith the Windows and MS-DOS operating systems.

Many technical commentators have concluded that these patents only cover FAT implementations that include support for long filenames, and that removable solid state media and consumer devices only using short names would be unaffected.

Additionally, in the document "Microsoft Extensible Firmware Initiative FAT 32 File System Specification, FAT: General Overview of On-Disk Format" published by Microsoft (version 1.03, December 6, 2000), Microsoft specifically grants a number of rights, which many readers have interpreted as permitting operating system vendors to implement FAT.

3.1 Re-opened investigation

As there has been widespread call for these patents to be re-examined, the Public Patent Foundation submitted evidence to the US Patent and Trade Office (USPTO) disputing the validity of these patents, including prior art references from Xerox and IBM. The USPTO acknowledged that the evidence raised "substantial new question[s] of patentability", and opened an investigation into the validity of Microsoft's FAT patents.

On September 30 2004, the USPTO rejected all claims of patent 5,579,517, based primarily on evidence provided by the Public Patent Foundation. Dan Ravicher, the foundation's executive director, said "The Patent Office has simply confirmed what we already knew for some time now, Microsoft's FAT patent is bogus."

Microsoft still has the opportunity to respond to the Patent Office's rejection. Typically, third party requests for reexamination, like the one filed by PUBPAT, are successful in having the subject patent either narrowed or completely revoked roughly 70% of the time.

4 See also

• Comparison of file systems
• Drive letter assignment
• Software patent
• NTFS
• ext2
• ext3
• ReiserFS.

5 External links

• Microsoft' statement on "FAT File System Technology and Patent License"
• Rock Ridge Interchange Protocol (PDF)
• Slashdot discussion on Microsoft's claims of FAT-related patents
• Microsoft Extensible Firmware Initiative FAT 32 File System Specification, FAT: General Overview of On-Disk Format
• Microsoft's war on GPL dealt patent setback
• A Short History of MS-DOS, by Tim Paterson
• Detailed Explanation of FAT Boot Sector - Microsoft Knowledge Base Article 140418
• At PUBPAT's Request, Patent Office Rejects Microsoft's FAT Patent: All Claims of Reynolds '517 Patent Ruled Invalid

Computer file systems

<Hide>