DOS File Allocation Tables

Also:

• The DOS File System

By: Inbar Raz
--------------------------------------------------------------------

 The FAT is a linked-list table that DOS uses to keep track of the physical
 position of data on a disk and for locating free space for storing new files.

 The word at offset 1aH in a directory entry is a cluster number of the first
 cluster in an allocation chain.  If you locate that cell in the FAT, it will
 either indicate the end of the chain or the next cell, etc.  Observe:

                                    starting cluster number --|
Directory +-------------------+-+-------------------+---+---+-+-+-------+
Entry -- |M Y F I L E   T X T|a|                   |tim|dat|08 | size  |
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|-+-+-+-+-+
                                    +-------------------------+
    00  01  02  03  04  05  06  07  |8  09  0a  0b  0c  0d  0e  0f
   +--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
00 |ID||ff||03--04--05--ff||00||00||09--0a--0b--15||00||00||00||00|
   +--++--++--++--++--++--++--++--++--++--++--++|-++--++--++--++--+
                        +-----------------------+
   +--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
10 |00||00||00||00||00||16--17--19||f7||1a--1b--ff||00||00||00||00|
   +--++--++--++--++--++--++--++|-++--++--++--++--++--++--++--++--+
                                +-------+
This diagram illustrates the main concepts of reading the FAT.  In it:
þ The file MYFILE.TXT is 10 clusters long.  The first byte is in cluster 08
  and the last is in cluster 1bH.  The chain is 8,9,0a,0b,15,16,17,19,1a,1b.
  Each entry indicates the next entry in the chain, with a special code in
  the last entry.
þ Cluster 18H is marked bad and is not part of any allocation chain.
þ Clusters 6,7, 0cH-14H, and 1cH-1fH are empty and available for allocation.
þ Another chain starts at cluster 2 and ends at cluster 5.

+-----------+
| FAT Facts | The FAT normally starts at logical sector 1 in the DOS partition
+-----------+ (eg, you can read it with INT 25H with DX=1).  The only way to
 be sure is to read the boot sector (DX=0), and examine offset 0eH.  This
 tells how many boot and reserved sectors come before the FAT.  Use that
 number (usually 1) in DX to read the FAT via INT 25H.

 There may be more than one copy of the FAT.  There are usually two complete
 copies.  If there are two or more, they will all be adjacent (the second FAT
 directly follows the first).

 You have the following services available to help you determine information
 about the FAT:

   þ Use INT 25H to read the Boot Sector and examine the data fields therein
   þ Use DOS Fn 36H or 1cH to determine total disk sectors and clusters
   þ Use DOS Fn 44H (if the device driver supports Generic IOCTL)  DOS 3.2
   þ Use DOS Fn 32H to get all kinds of useful information.   UNDOCUMENTED

 Note: The boot sector of non-booting disks (such as network block devices
       and very old hard disks) may contain nothing but garbage.

+---------------+
| 12-bit/16-bit | The FAT can be laid out in 12-bit or 16-bit entries. 12-bit
+---------------+ entries are very efficient for media less than 384K--the
 entire FAT can fit in a single 512-byte disk sector.  For larger media, each
 FAT entry must map to a larger and larger cluster size--to the point where a
 20M hard disk would need to allocate in units of 16 sectors in order to use
 the 12-bit format (in other words, a 1-byte file would take up a full 8K
 cluster of a disk).

 16-bit FAT entries were introduced with DOS 3.0 with the necessity of
 efficient handling the AT's 20-Megabyte hard disk.  However, floppy disks
 and 10M hard disks continue to use the 12-bit layout.  You can determine if
 the FAT is laid out with 12-bit or 16-bit elements:

  DOS 3.0 says: If a disk has more than 4086 (0ff6H) clusters, it uses 16 bits
                (4096 is max value for a 12-bit number and >0ff6H is reserved)
  DOS 3.2 says: If a disk has more than 20740 (5104H) SECTORS, it uses 16 bits
                (in other words, any disk over 10 Megabytes uses a 16-bit FAT
                 and all others--including large RAM disks--use 12-bits).

Note: It's a common misconception that the 16-bit FAT allows DOS to work with
      disks larger than 32 Megabytes.  In fact, the limiting factor is that
      INT 25H/26H (through which DOS performs its disk I/O) in unable to
      access a SECTOR number higher than 65535.  Normally, sectors are 512
      bytes («-K), so that sets the 32M limit.

      In DOS 4.0, INT 25H/26H supports a technique for accessing sector
      numbers
      higher than 65535, and thus supports trans-32M DOS partitions.  This
      has no effect on the layout of the FAT itself.  Using 16-bit FAT
      entries and 4-sector clusters, DOS now supports partitions up to 134M
      (twice that for 8-sector clusters, etc.).

+-----------------+
| Reading the FAT | To read the value of any entry in a FAT (as when following
+-----------------+ a FAT chain), first read the entire FAT into memory and
 obtain a starting cluster number from a directory.  Then, for 12-bit entries:
                                                               ==============
þ Multiply the cluster number by 3 =|
þ Divide the result by 2   =========+= (each entry is 1.5 (3/2) bytes long)
þ Read the WORD at the resulting address (as offset from the start of the FAT)
þ If the cluster was even, mask the value by 0fffH (keep the low 12 bits)
  If the cluster number was odd, shift the value right by 4 bits (keep the
  upper 12 bits)
þ The result is the entry for the next cluster in the chain (0fffH=the end).

Note: A 12-bit entry can cross over a sector boundary, so be careful with
      1-sector FAT buffering schemes.

 16-bit entries are simpler--each entry contains the 16-bit offset (from the
 start of the FAT) of the next entry in the chain (0ffffH indicates the end).

+-------------+
| FAT Content | The first byte of the FAT is called the Media Descriptor or
+-------------+ FAT ID byte.  The next 5 bytes (12-bit FATs) or 7 bytes
 (16-bit FATs) are 0ffH.  The rest of the FAT is composed of 12-bit or 16-bit
 cells that each represent one disk cluster.  These cells will contain one of
 the following values:

    þ (0)000H ................... an available cluster
    þ (f)ff0H through (f)ff7H ... a reserved cluster
    þ (f)ff7H ................... a bad cluster
    þ (f)ff8H through (f)fffH ... the end of an allocation chain
    þ (0)002H through (f)fefH ... the number of the next cluster in a chain

Note: the high nibble of the value is used only in 16-bit FATs; eg, a bad
      cluster is marked with 0ff7H in 12-bit FATs, and fff7H with 16-bit FATs.

+------------------------------------------------+
| Converting a Cluster Number to a Sector Number | After you obtain a file's
+------------------------------------------------+ starting cluster number
 from a directory entry you will want to locate to actual disk sector that
 holds the file (or subdirectory) data.

 A diskette (or a DOS partition of a hard disk) is laid out like so:

 þ Boot and reserved sector(s)
 þ FAT #1
 þ FAT #2 (optional -- not used on RAM disks)
 þ root directory
 þ data area (all file data reside here, including files for directories)

 Every section of this layout is variable and the sizes of each section must
 be known in order to perform a correct cluster-to-sector conversion.  The
 following formulae represent the only documented method of determining a DOS
 logical sector number from a cluster number:

       RootDirSectors = sectorBytes / (rootDirEntries * 32)
       FatSectors     = fatCount * sectorsPerFat
       DataStart      = reservedSectors + fatSectors + rootDirSectors

  INT 25h/26h Sector  = DataStart + ((AnyClusterNumber-2) * sectorsPerCluster)

Where the variables:

       sectorBytes      sectorsPerFat      fatCount
       rootDirEntries   reservedSectors    sectorsPerCluster

 are obtained from the Boot Sector or from a BPB (if you can get access).  The
 resulting sector number can be used in DX for INT 25H/26H DOS absolute disk
 access.

 If you are a daring sort of person, you can save trouble by using the
 undocumented DOS Fn 32H (Get Disk Info) which provides a package of pre-
 calculated data, including the sector number of the start of file data (it
 gives you "DataStart", in the above equation).

 Author's note:  The best use I've found for all this information is in
 directory scanning; ie, to bypass the DOS file-searching services and read
 directory sectors directly.  For a program that must obtain a list of all
 files and directories, direct access of directory sectors will work roughly
 twice as fast as DOS Fns 4eH and 4fH.

See also:

• http://www.teleport.com/~brainy/fat16.htm and http://www.teleport.com/~brainy/fat32.htm Some very interesting documentation on FAT16 and FAT32, with a link to the Microsoft FAT32 Technical Whitepaper.
• http://209.67.75.168/hardware/fatgen.htm Microsoft's FAT32 standard. Explains differences between FAT32/16/12
• http://www.microsoft.com/hwdev/specs/ FAT, Long Filename and other neat information
• http://members.aol.com/vindaci/pub/doc/lfn/lfn.html An interesting tutorial on how both short and long filenames, as well as directories, are stored.

  .