FAT/FAT16 tables - finding the data

Having successfully found the root directory on our sd card, we now need to start actually reading the data back from it. This is the last little link in a chain of

• initialise the sd card
• find the lba (logical block address) by reading sector zero
• read the mbr (master boot record)
• calculate where the root directory starts
• find the file we're interested in
• read the file

The easiest way to find a file is to load a filename into an 11-byte buffer. The easiest format to use is the name, padded with spaces plus the extension, minus the full-stop; so wav001.raw becomes wav001[space][space]raw. Or, perhaps more accurately, WAV001[space][space]RAW (since FAT16 likes to store filenames in uppercase).

A root directory entry looks like this:

• The first eight bytes are the file name - FAT16/MSDOS only supported up to eight characters in a filename.
• The next three bytes are the file extension
• Then there's an attributes byte
• Followed by time stamps for the file creation/modified date.
• The next two bytes are the starting cluster for the data (note, cluster not sector)
• The last four bytes are the total file length (in bytes)
• Every root directory entry uses exactly 32 bytes

It's the first bunch of bytes we're interested in - the file name, starting cluster and total file length:

Now we just read the root directory, comparing the first 11 bytes of each 32-byte entry in the root directory to the bytes in our filename buffer and if they match, we've found the file we're interested in.

Once we've got our file, we need to work out the file-length (in bytes) and the starting sector for the first cluster of data.

Byte 26 of 32 is the least-significant byte of a two-byte word  (e.g. 0x02)

Byte 27 of 32 is the most-significant byte of a two-byte word (e.g. 0x00)

The starting cluster for the file in this example is therefore 0x0002

Bytes 28-31 represent the file length, starting with the least significant byte of a 4-byte value.

In this example:

Byte 28 = 0x43

Byte 29 = 0x5e

Byte 30 = 0x09

Byte 31 = 0x00

The total file length is 0x00095e43 which in decimal works out as 613,955

Looking at the file wav003.raw in Windows Explorer confirms that the file is, indeed, 613,955 bytes in size

Now previously, we worked out a whole heap of important things from our MBR (master boot record) including where the actual data started, and the number of sectors per cluster (in a FAT16 formatted disk, this is usually 32 sectors per cluster, making each cluster 16kb)

If we know which sector the actual data begins from, and which cluster to begin reading from, we can calculate at which sector the cluster begins.

unsigned long clusterToSector(unsigned long cluster){
     // a cluster is a complicated thing:
     // first there's an ofset to the master boot record
     // then some reserved sectors
     // then a fat table (maybe two)
     // then the root directory (fixed length)
     // THEN there's the first data block,
     // which is where we start reading our clusters from
     // BUT there's a catch - clusters start from zero not 2
     // so whichever cluster number we've been given, subtract 2
     
     unsigned il;
     il=cluster-2;
     il=il*sectorsPerCluster;
     il=il+dataStart;
     return(il);     
}

Great stuff!
Convert the cluster number (in this case, cluster 0x0002) into a sector (in this case, because clusters start from 2 - it's an anomaly of the FAT16 format - our first cluster is also the first sector where the data starts. We've already calculated this value)

"The actual data starts at sector 615 + 32 = 647"

If we jump to sector 647 and start reading back the data, we find that there is, indeed, data in there!
But with a file that's 613,955 bytes long, it's not all going to fit into a single cluster (one cluster is 32 sectors and each sector is 512 bytes, so that's only 32x512 = 16,384 bytes - 16kb)

So where's the rest of the data?
That's where the FAT table comes in!

Firstly, take the cluster number and double it. That's the same as bit-shifting the entire value one place to the left. In our example, our starting cluster was 0x02 so we double this and end up with 0x04
This tells us where in our FAT table to find the next (two-byte) cluster number.

Since the FAT tables themselves are written across a number of sectors, we need to convert this cluster_doubled value into a sector and byte offset, to read the actual "next cluster value" back.

Divide the cluster_doubled value by 512 to get the sector number
The remainder is the byte offset.
In our example, this gives us sectors zero, byte offset 4
So we want the first sector (sector zero) in our FAT table, fourth and fifth byte

Since the FAT table begins at sector 143, we add zero to this, open the sector (using our earlier functions) and read back all 512 bytes. When we get byte four, this makes up the least significant byte of a two-byte (16-bit) value. Byte five is the most significant byte.

In fact, when we open our sd card, read back bytes four and five from sector 143, we get
Byte 4 = 0x03
Byte 5 = 0x00

This tells us that the file continues at cluster 0x0003.
Using the same technique, we open and read the data from cluster 0x0003 (sector 647 + (3-2)*sectorsPerCluster = 647 + 32 = 679)

We continue reading data from the sector(s) and calculating the next cluster where the file continues until we've either read back the entire file (total bytes read > file size in bytes) or the FAT table returns 0xFF as the next cluster (this is a special response to say "no more clusters for this file").

This is summarised in the following function (remove comments around UART calls to see what the microcontroller is actually doing when calculating next FAT clusters).

unsigned char openNextBlock(){

     unsigned short iFATSector;

     unsigned short iFATBytes;

     unsigned short iy;

     unsigned short ix;

     

     //UARTPrintLn("opening next block of data");

     

     // the cluster_number_doubled is the location in the FAT table

     // where we can find the next block of data. If this entry is 0xFF

     // it means that there's no more blocks of data, otherwise the entry

     // is the next cluster where the file continues from

     

     iFATBytes=nextFatClusterDoubled & 511;

     iFATSector=nextFatClusterDoubled>>9;

     iFATSector=iFATSector+FATStart;

     

     //UARTPrintLn("look up next cluster in FAT ");

     //UARTPrint("sector ");

     //UARTPrintNumber(iFATSector);

     //UARTPrint(" byte offset ");

     //UARTPrintNumber(iFATBytes);

     //UARTPrintLn(" ");

     

     // check the FAT tables for the next cluster for the current file

     r=sdReadBlock(iFATSector);

     for(iy=0; iy < 512; iy++){

          r=readByte();

          if(iy==iFATBytes){ix=r; nextFatCluster=ix;}

          if(iy==(iFATBytes+1)){ix=r; ix=ix<<8; nextFatCluster=nextFatCluster+ix;}

     } 

          
     // close the currently open sector
     sdSecReadStop();

     nextFatClusterDoubled=nextFatCluster<<1; // this is the same as multiplying by two!


      
     //UARTPrint("next FAT cluster ");
     //UARTPrintNumber(nextFatCluster);
     //UARTPrintLn(" ");          
     
     if(nextFatCluster==0xFFFF){          
          // if we're at the end of the block, send the end of block marker
          //UARTPrintLn("no futher fat clusters to follow");
          return(0xFF);
     }else{
          
          // open the next sector
          iSector=clusterToSector(nextFatCluster);
          sectorCount=0;
          //UARTPrint("file continues at sector ");
          //UARTPrintNumber(iSector);
          //UARTPrintLn(" ");
          
          return(0);
     }
}