Saturday, 3 November 2012

Understanding FAT tables

While it's possible to simply read and write data to and from our SD card serially (treating the card as one big eeprom chip) the most useful way to use the card is to format it using FAT16.
This will allow the card to be removed from the microcontroller and the data either read back or written to using a PC. This is far more useful that having to use some dedicated hardware to stream read/write data to/from the card and report it's finding back over UART/serial.

FAT is quite a complicated structure and needs careful understanding; it's very easy to get lost and end up reading chunks of data from the wrong sector and mangling files - especially if files on the card are frequently added or deleted and the files end up fragmented (i.e. written over a number of non-consecutive sectors).

To get started, download a hex editor (we used HxD) and format your sd card to FAT or FAT16 (not FAT32) format.


Here's your first gotcha:
When you mount an sd card into a hex editor to view the entire file contents, the hex editor usually starts from the LBA (logical block address). It will often call this sector zero.
But on the SD card, this may not actually be physical sector zero. If you use the previous card reading functions and write out the contents of sector zero over serial, you'll see it doesn't look like a boot record - it's mostly zeros. Sector zero usually just contains information about where you'll find the actual master boot record (and where the hex editor will call sector zero).

We found the easiest thing to do was use the UART tool on the PicKit2 software to view the serial data as it was read back from the sd card. We used the "save to disk" option and then read through the file after it had been saved as a text file. You can use whichever serial-based tools you're happy with for debugging at this point:


The last two bytes of the entire sector were 0x55 and 0xAA
This is the FAT signature to say that we're reading a FAT-formatted drive. We just double-checked that our code was working and actually reading back sensible data by looking for this signature at the end of the sector-ful of data.

Most of our sector zero data was zero - 0x00.
Having read up a little about FAT tables and file layouts, we were expecting a bit more than this - we were told to expect things like the OS name/type, volume label and so on, but nothing here looked anything like it. But that's because we weren't looking at "logical sector zero" - the first sector in the file structure - we were looking at physical sector zero.

So our first job was to find the logical block address LBA.
In amongst all the zeros, there was a little bit of data, starting at byte 447.
This is the data describing the actual drive itself - sectors, clusters, heads and cylinders (used in older drives). The data we're after is the two bytes at 454 (0x1C6) and 455 (0x1C7).
This is the sector number containing our master boot record MBR.

Another gotcha coming up - where data is written using two or more bytes, the order of bytes is back-to-front to what you'd expect: the least significant byte comes first. So in our example, we've got 0x87 followed by 0x00. But this actually translates to 0x0087.

Using the same routines as we did for reading sector zero, we get the PIC to read back the contents of sector 0x87 (135 decimal).


Straight away we can see that this has some useful information. Already, we can see the name MSDOS5.0 being spelled out. So what about all the other junk in there? Here's how the boot record is laid out:

  • Jump instruction (3 bytes)
  • Operating system (8 bytes)
  • Bytes per sector (2 bytes)
  • Sectors per cluster (1 byte)
  • Number of reserved sectors (2 bytes)
  • Number of file allocation tables (1 byte)
  • Max number of possible root entries (2 bytes)
  • Small sectors (2 bytes)
  • Media type (1 byte)
  • Sectors per file allocation table (2 bytes)
  • More stuff we're not particularly interested in

The bits of information we're interested in are the bytes per sector (11 bytes into the record), sectors per cluster (13 bytes in) number of reserved sectors (14 bytes in) number of FAT tables (16 bytes in) the maximum possible number of entries in the root directory (17 bytes in) and the number of sectors used by each FAT table (22 bytes into the record).

Looking at our log files, we find entries 11 and 12 are 0x00 and 0x02 respectively.
But we have to remember that data is stored back-to-front, so the bytes per sector value is actually 0x0200 which is 512 in decimal. This looks like a sensible value so we can assume we're correctly reading the data back.

Sectors per cluster (a single byte) returns 0x20 which in decimal is 32. Again, a sensible-looking value and one we'd expect (32 sectors of 512 bytes = 16kb per sector, which is the FAT16 standard).

Number of reserved sectors is important for us to work out where the FAT tables and data actually reside on the card. Reading bytes 14 and 15 we get the (don't forget to flip them around) value of 0x0008 - i.e. there are eight reserved sectors following this boot record.

Usually FAT tables are duplicated to help provide a means of data recovery should one table become corrupted. Although very few people ever use the second table (and in fact, should either of the tables become corrupt, the host machine should stop reading/writing to the sd card and report a FAT mismatch error) it still takes up space and needs to be accounted for when working out where the data starts on the disk. Byte 16 is 0x02 - ie the FAT table is duplicated once; there are two working copies of the FAT system on our card - again, the expected value.

Maximum possible number of entries in the root directory is important - we can work out where the root directory is, and the data is stored immediately after it, so we need to know how many sectors the root directory takes up. Bytes 17 and 18 tell us that the max number of records in our root directory is 0x0200 or 512 in decimal.

The number of sectors used by each FAT table is in bytes 22 and 23.
In our case, we have the value 0x00ec or 236 in decimal.

From all this information we can deduce:

  • Our boot record is at sector 135 (in your hex editor, this is sector zero)
  • After 8 reserved sectors, the FAT tables begin at physical sector 143 (in your hex editor, these would start at sector 8 - we're going to stick with physical sectors to avoid confusion, but be aware that your sectors will be offset in the hex editor)
  • Each FAT table is 236 sectors in size
  • There are two FAT tables
  • Our root directory starts at sector 135 + 8 + (2*236) = 615
  • The root directory can hold up to 512 entries. Since this is FAT16 (each entry uses 16 bytes) this means our root directory takes up 512/16 = 32 sectors
  • The actual data starts at sector 615 + 32 = 647


Our SD card already contains a few files.
Since we're going to (eventually) be playing audio, we put some RAW audio data on there (files imaginatively called wav001.raw, wav002.raw etc.) and a short text file called FAT16.txt



From our deductions, we run our "read-sector" routines on sector 615 and see what we get:
(your card may have different offset values for the boot record, reserved sectors, FAT table sizes etc, so use the equations above, but substitute with your card's values to get the actual sector to read from - your card may not have the root directory starting at sector 615. In fact, we're not sure that ours does yet.....)


Holy cow Batman, it looks like we've found our root directory........