Decoding a 12-bit File Allocation Table

In this section we present a simple program that loads the file allocation table and root directory from a diskette (in drive A), and displays the list of clusters owned by each file. Let's look at part of a sample 12-bit FAT in raw form (shown by Debug) so we can decode its structure:

 F0 FF FF FF 4F 00 05 60-00 07 80 00 09 A0 00 0B
 C0 00 0D E0 00 0F 00 01-11 20 01 13 40 01 15 60 

A decoded form of entries 2 through 9 is shown here:
Entry: 2 3 4 5 6 7 8 9 ...
Value: <FFF> <004> <005> <006> <007> <008> <009> <00A> ...

You can can track down all clusters allocated to a particular file by following what is called a cluster chain. Let's follow the cluster chain starting with cluster 3. Here is how we find its matching entry in the FAT, using three steps:

  1. Divide the cluster number by 2, resulting in an integer quotient. Add the same cluster number to this quotient, producing the offset of the cluster's entry in the FAT. Using cluster 3 as a sample, this results in Int(3 /2) + 3 = 4, so we look at offset 4 in the FAT.
  2. The 16-bit word at offset 4 contains 004Fh (0000 0000 0100 1111). We need to examine this entry to determine the next cluster number allocated to the file.
  3. If the current cluster number is even, keep the lowest 12 bits of the 16-bit word. If the current cluster number is odd, keep the highest 12 bits of the 16-bit word. For example, our cluster number (3) is odd, so we keep the highest 12 bits (0000 0000 0100), and this indicates that cluster 4 is the next cluster.

We return to step 1 and calculate the offset of cluster 4 in the FAT table: The current cluster number is 4, so we calculate Int(4 /2) + 4 = 6. The word at offset 6 is 6005h (0110 0000 0000 0101). The value 6 is even, so we take the lowest 12 bits of 6005h, producing a new cluster number of 5. Therefore, FAT entry 4 contains the number 5.

Fortunately, a 16-bit FAT is easier to decode, because entries do not cross byte boundaries. In a 16-bit FAT, cluster n is represented by the entry at offset n * 2 in the table.

Finding the Starting Sector

Given a cluster number, we need to know how to calculate its starting sector number:

  1. Subtract 2 from the cluster number and multiply the result by the disk's sectors per cluster. A 1.44MB disk has one sector per cluster, so we multiply by 1.
  2. Add the starting sector number of the data area. On a 1.44MB disk, this is sector 33. For example, cluster number 3 is located at sector 34: ((3 - 2) * 1) + 33 = 34

Cluster Display Program

In this section, we will demonstrate a program that reads a 1.44MB diskette in drive A, loads its file allocation table and root directory into a buffer, and displays each filename along with a list of all clusters allocated to the file. The following is a sample of the program’s output:

The main procedure displays a greeting, loads the directory and FAT into memory, and loops through each directory entry. The most important task here is to check the first character of each directory entry to see if it refers to a filename. If it does, we check the file's attribute byte at offset 0Bh to make sure the entry is not a volume label or directory name. We screen out directory entries with attributes of 00h, E5h, 2Eh, and 18h.

Regarding the attribute byte: Bit 3 is set if the entry is a volume name, and bit 4 is set if it is a directory name. The TEST instruction used here sets the Zero flag only if both bits are clear.

LoadFATandDir loads the disk directory into dirbuf, and it loads the FAT into fattable. DisplayClusters contains a loop that displays all cluster numbers allocated to a single file. The disk directory has already been read into dirbuf, and we assume that SI points to the current directory entry.

The Next_FAT_Entry procedure uses the current cluster number (passed in AX) to calculate the next cluster number, which it returns in AX. The SHR instruction in this procedure checks to see if the cluster number is even by shifting its lowest bit into the Carry flag. If it is, we retain the low 12 bits of DX; otherwise, we keep the high 12 bits. The new cluster number is returned in AX.

Here is the complete program listing:

TITLE Cluster Display Program (Cluster.asm)
; This program reads the directory of drive A, decodes
; the file allocation table, and displays the list of
; clusters allocated to each file.
; Attributes specific to 1.44MB diskettes:
   FATSectors = 9 		; num sectors, first copy of FAT
   DIRSectors = 14 		; num sectors, root directory
   DIR_START = 19 		; starting directory sector num
   DRIVE_A = 0
   FAT_START = 1 		; starting sector of FAT
   EOLN equ <0dh,0ah>
Directory STRUCT
   fileName BYTE 8 dup(?)
   extension BYTE 3 dup(?)
   attribute BYTE ?
   reserved BYTE 10 dup(?)
   time WORD ?
   date WORD ?
   startingCluster WORD ?
   fileSize DWORD ?
   Directory ENDS
   ENTRIES_PER_SECTOR = SECTOR_SIZE / (size Directory)
   heading LABEL byte
   BYTE 'Cluster Display Program (CLUSTER.EXE)'
   BYTE EOLN,EOLN,'The following clusters are allocated '
   BYTE 'to each file:',EOLN,EOLN,0
fattable WORD ((FATSectors * SECTOR_SIZE) / 2) DUP(?)
   dirbuf Directory (DIRSectors * ENTRIES_PER_SECTOR) DUP(<>)
   driveNumber BYTE ?
   main PROC
   call Initialize
   mov ax,OFFSET dirbuf
   mov ax,OFFSET driveNumber
   call LoadFATandDir
   jc A3 						; quit if we failed
   mov si,OFFSET dirbuf 		; index into the directory
A1: cmp (Directory PTR [si]).filename,0 	; entry never used?
   je A3 						; yes: must be the end
   cmp (Directory PTR [si]).filename,0E5h 	; entry deleted?
   je A2 						; yes: skip to next entry
   cmp (Directory PTR [si]).filename,2Eh 	; parent directory?
   je A2 						; yes: skip to next entry
   cmp (Directory PTR [si]).attribute,0Fh 	; extended filename?
   je A2
   test (Directory PTR [si]).attribute,18h 	; vol or directory name?
   jnz A2 						; yes: skip to next entry
   call displayClusters 				; must be a valid entry
A2: add si,32 					; point to next entry
   jmp A1
   A3: exit
main ENDP
LoadFATandDir PROC
; Load FAT and root directory sectors.
; Receives: nothing
; Returns: nothing
   ; Load the FAT
   mov al,DRIVE_A
   mov cx,FATsectors
   mov dx,FAT_START
   mov bx,OFFSET fattable
   int 25h 					; read sectors
   add sp,2 				; pop old flags off stack
   ; Load the Directory
   mov cx,DIRsectors
   mov dx,DIR_START
   mov bx,OFFSET dirbuf
   int 25h
   add sp,2
LoadFATandDir ENDP
DisplayClusters PROC
; Display all clusters allocated to a single file.
; Receives: SI contains the offset of the directory entry.
   push ax
   call displayFilename 			; display the filename
   mov ax,[si+1Ah] 				; get first cluster
   C1: cmp ax,0FFFh 			; last cluster?
   je C2 					; yes: quit
   mov bx,10 					; choose decimal radix
   call WriteDec 				; display the number
   call writeSpace 				; display a space
   call next_FAT_entry 			; returns cluster # in AX
   jmp C1 					; find next cluster
   C2: call Crlf
   pop ax
DisplayClusters ENDP
WriteSpace PROC
; Write a single space to standard output.
   push ax
   mov ah,2 					; function: display character
   mov dl,20h 				; 20h = space
   int 21h
   pop ax
WriteSpace ENDP
Next_FAT_entry PROC
; Find the next cluster in the FAT.
; Receives: AX = current cluster number
; Returns: AX = new cluster number
   push bx 				; save regs
   push cx
   mov bx,ax 			; copy the number
   shr bx,1 			; divide by 2
   add bx,ax 			; new cluster OFFSET
   mov dx,fattable[bx] ; DX = new cluster value
   shr ax,1 			; old cluster even?
   jc E1 				; no: keep high 12 bits
   and dx,0FFFh 		; yes: keep low 12 bits
   jmp E2
   E1: shr dx,4 		; shift 4 bits to the right
   E2: mov ax,dx 		; return new cluster number
   pop cx 				; restore regs
   pop bx
Next_FAT_entry ENDP
DisplayFilename PROC
; Display the file name.
   mov byte ptr [si+11],0 ; SI points to filename
   mov dx,si
   call Writestring
   mov ah,2 			; display a space
   mov dl,20h
   int 21h
DisplayFilename ENDP
Initialize PROC
; Set upt DS, clear screen, display a heading.
   mov ax,@data
   mov ds,ax
   call ClrScr
   mov dx,OFFSET heading 	; display program heading
   call Writestring
Initialize ENDP
END main