Article Community improvements enabled

Read a Fragmented FAT16 File in C

Daniel McCarthy published 2 weeks ago 7 min read 149 views
New post
Daniel McCarthy remains the original author. Improvements are attributed to their editors and reviewed by the original author before publication.

A file's first cluster tells you where its first bytes live. The next part of the file might be several clusters away. To read a fragmented FAT16 file, follow the links in the File Allocation Table and use the directory entry's byte count to decide how much data to copy.

Suppose a 520-byte file starts at cluster 2 on a volume with 512-byte clusters. Its chain is 2 → 7 → end. The file contains all 512 bytes from cluster 2 and the first eight bytes from cluster 7. A reader that advances from cluster 2 to cluster 3 reads the wrong data.

Start with a decoded file entry

The C reader below takes three inputs:

  • A view of one FAT and the data region, with their actual buffer lengths, the cluster size in bytes, and the number of data clusters.
  • The first cluster and byte count from an already decoded regular-file directory entry.
  • A destination buffer and its capacity.

A volume parser must establish FAT16 geometry and identify the directory entry before calling this component. The input memory stays unchanged during the read. The destination must be separate from the input buffers and the view itself. The six-cluster example is a fixture for the reader, so it can exercise fragmentation without constructing a complete mountable volume.

Convert cluster numbers to offsets

Two different offsets come from each cluster number n:

Buffer Offset What you get
FAT 2 * n The two-byte link for cluster n
Data region (n - 2) * cluster_bytes The first byte of cluster n

The data view starts at cluster 2. On disk, its start comes after the reserved region, the FAT copies, and the fixed FAT16 root directory. A FAT16 directory entry supplies the first cluster and the logical file size. Microsoft FAT on-disk format

A FAT link is a little-endian integer. Decode its two bytes explicitly so the reader works without aligned loads or a little-endian host assumption. The highest cluster number comes from the volume geometry, cluster_count + 1. Microsoft FAT Specification, sections 3.5 and 4

Check the link against the bytes remaining

For a nonempty regular file, use the following rules at each cluster:

FAT entry Handling
0x0000 Reject because the current cluster is marked free
0x0001 Reject the reserved value
2 through cluster_count + 1 Continue if the file still needs another cluster
Above the volume's highest cluster through 0xFFF6 Reject an out-of-range or reserved link
0xFFF7 Reject the bad-cluster marker
0xFFF8 through 0xFFFF Accept the end marker if this cluster supplies the last requested bytes

An empty regular file has first cluster 0 and needs no FAT lookup. Microsoft FAT on-disk format

For nonempty files, this reader requires the end marker to appear at the last cluster implied by the file size.

A runnable C11 example

Save the following as fat16_read.c. It uses standard C headers and runs in a hosted environment. Build and run it from a shell with GCC.

gcc -std=c11 -Wall -Wextra -Wconversion fat16_read.c -o fat16_read
./fat16_read
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

enum Fat16Result {
    FAT16_OK,
    FAT16_BAD_VIEW,
    FAT16_SMALL_OUTPUT,
    FAT16_BAD_LENGTH,
    FAT16_INVALID_LINK,
    FAT16_EARLY_END,
    FAT16_CHAIN_CONTINUES
};

struct Fat16View {
    const uint8_t *fat;
    size_t fat_bytes;
    const uint8_t *data;       /* Starts at cluster 2. */
    size_t data_bytes;
    size_t cluster_bytes;
    size_t cluster_count;
};

static uint16_t load_le16(const uint8_t *bytes)
{
    return (uint16_t)(bytes[0] | ((uint16_t)bytes[1] << 8));
}

static int is_data_cluster(uint16_t cluster, size_t cluster_count)
{
    return cluster >= 2 && (size_t)cluster <= cluster_count + 1;
}

/* On failure, discard the output. Its prefix may have been written. */
enum Fat16Result fat16_read(const struct Fat16View *volume,
                           uint16_t first_cluster, uint32_t file_size,
                           uint8_t *output, size_t output_capacity)
{
    if (file_size == 0) {
        return first_cluster == 0 ? FAT16_OK : FAT16_BAD_LENGTH;
    }

    if (volume == NULL || volume->fat == NULL || volume->data == NULL ||
        volume->cluster_bytes == 0 || volume->cluster_count == 0 ||
        volume->cluster_count > 65524) {
        return FAT16_BAD_VIEW;
    }

    const size_t count = volume->cluster_count;
    const size_t cluster_bytes = volume->cluster_bytes;
    if (volume->fat_bytes / 2 < count + 2 ||
        volume->data_bytes / cluster_bytes < count) {
        return FAT16_BAD_VIEW;
    }
    if (file_size > count * cluster_bytes) {
        return FAT16_BAD_LENGTH;
    }
    if (output == NULL || file_size > output_capacity) {
        return FAT16_SMALL_OUTPUT;
    }

    size_t remaining = (size_t)file_size;
    size_t written = 0;
    uint16_t cluster = first_cluster;

    while (remaining != 0) {
        if (!is_data_cluster(cluster, count)) {
            return FAT16_INVALID_LINK;
        }

        const size_t fat_offset = (size_t)cluster * 2;
        const uint16_t next = load_le16(volume->fat + fat_offset);
        const size_t take = remaining < cluster_bytes ? remaining : cluster_bytes;

        if (next >= 0xfff8u) {
            if (take != remaining) {
                return FAT16_EARLY_END;
            }
        } else {
            if (!is_data_cluster(next, count)) {
                return FAT16_INVALID_LINK;
            }
            if (take == remaining) {
                return FAT16_CHAIN_CONTINUES;
            }
        }

        const size_t data_offset = ((size_t)cluster - 2) * cluster_bytes;
        memcpy(output + written, volume->data + data_offset, take);
        remaining -= take;
        written += take;
        cluster = next;
    }

    return FAT16_OK;
}

int main(void)
{
    enum { CLUSTERS = 6, CLUSTER_BYTES = 512, FILE_BYTES = 520 };
    uint8_t fat[(CLUSTERS + 2) * 2] = {0};
    uint8_t data[CLUSTERS * CLUSTER_BYTES] = {0};
    uint8_t output[FILE_BYTES];

    fat[2 * 2] = 7;           /* FAT[2] = 0x0007 */
    fat[7 * 2] = 0xff;        /* FAT[7] = 0xffff */
    fat[7 * 2 + 1] = 0xff;
    memset(data, 'A', CLUSTER_BYTES);
    memset(data + (7 - 2) * CLUSTER_BYTES, 'B', CLUSTER_BYTES);

    const struct Fat16View volume = {
        .fat = fat,
        .fat_bytes = sizeof fat,
        .data = data,
        .data_bytes = sizeof data,
        .cluster_bytes = CLUSTER_BYTES,
        .cluster_count = CLUSTERS
    };
    const enum Fat16Result result =
        fat16_read(&volume, 2, FILE_BYTES, output, sizeof output);
    if (result != FAT16_OK) {
        fprintf(stderr, "FAT16 read failed (%d)\n", (int)result);
        return 1;
    }
    printf("Copied %zu bytes. Cluster boundary %c -> %c\n",
           sizeof output, output[511], output[512]);
    return 0;
}

The example prints:

Copied 520 bytes. Cluster boundary A -> B

Cluster 2 has its link at FAT byte offset 4. The bytes 07 00 direct the reader to cluster 7. Cluster 7 starts at data byte offset 2,560 and has FF FF at FAT byte offset 14. Only eight bytes remain by then, so the copy stops inside that cluster.

Why the bounds checks work

The FAT needs entries for the data clusters plus entries 0 and 1. Dividing its byte length by two before checking the entry count avoids a potentially overflowing size calculation. Likewise, data_bytes / cluster_bytes >= cluster_count establishes that every full cluster fits and that multiplying the cluster count by the cluster size is safe.

Each cluster number is checked before either offset is formed. This makes the subtraction of two safe and keeps both reads inside their respective buffers. The function checks destination capacity up front and copies at most the number of bytes remaining, including in the final partial cluster.

The byte count also bounds the loop. After the last expected cluster, another ordinary cluster link is an error. Because the FAT is held constant during the read, revisiting a cluster means the same links would repeat. Such a cycle cannot reach a valid end marker and therefore fails the final check. This detects that a chain continued without identifying the particular repeated cluster.

Discard the destination if the function reports an error. It can encounter a broken link after it has copied earlier clusters. A caller that needs all-or-nothing output can stage the read into a temporary buffer and use the bytes only on success.

Verify the failure cases

The example was compiled with GCC as C11, with warnings treated as errors. Nineteen checks covered the fragmented copy, the partial final cluster, both ends of the accepted end-marker range, empty files, a cycle, premature termination, invalid links, truncated input spans, an undersized destination, and a valid link to the highest cluster number in the Microsoft FAT16 range. A sentinel byte immediately after the file also confirmed that the final cluster's unused bytes stayed out of the destination.

A kernel driver can use this same chain traversal while fetching FAT entries and data through its block I/O interface. My kernel development course covers FAT16 on-disk structures, the driver, and file reads as part of building a multitasking kernel. Developing a Multithreaded Kernel From Scratch

Discussion 0

No comments yet. Start a thoughtful discussion.

Join the discussion

You need an account to contribute.

Sign in