# 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.```
`INCLUDE Irvine16.inc`
```; 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```
```SECTOR_SIZE = 512
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)```
```.data
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 ?```
```.code
main PROC
call Initialize
mov ax,OFFSET dirbuf
mov ax,OFFSET driveNumber
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?
cmp (Directory PTR [si]).filename,2Eh 	; parent directory?
cmp (Directory PTR [si]).attribute,0Fh 	; extended filename?
je A2
test (Directory PTR [si]).attribute,18h 	; vol or directory name?
call displayClusters 				; must be a valid entry```
```A2: add si,32 					; point to next entry
jmp A1
A3: exit
main ENDP```
```;----------------------------------------------------------
; Load FAT and root directory sectors.
; Returns: nothing
;----------------------------------------------------------
pusha
mov al,DRIVE_A
mov cx,FATsectors
mov dx,FAT_START
mov bx,OFFSET fattable
add sp,2 				; pop old flags off stack
mov cx,DIRsectors
mov dx,DIR_START
mov bx,OFFSET dirbuf
int 25h
popa
ret
```;----------------------------------------------------------
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
ret
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
ret
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
ret
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
ret
DisplayFilename ENDP```
```;----------------------------------------------------------
Initialize PROC
; Set upt DS, clear screen, display a heading.
;----------------------------------------------------------
mov ax,@data
mov ds,ax
call ClrScr