path: root/src/filesystem.c

/*
Copyright (c) 2021 Bad Diode

Permission to use, copy, modify, and distribute this software for any
purpose with or without fee is hereby granted, provided that the above
copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE.
*/

// This file implements a filesystem with a minimum block size of 256 bytes. The
// maximum number of files depends on the block size. The default 1KB block size
// will give us 32-64 files depending on the size of MEM_CART. In case we want
// to use a block size of 512 bytes, we will have up to 128 file available.
// Blocks of 256 bytes will give us the maximum of 255 files available, since
// a block index of 0xFF will be considered as a null block.

// A fileblock of 1KB give us a maximum of 64 files.
#define FILE_BLOCK_SIZE KB(1)
#define FILE_MAX_FILES  64
#define FILE_N_BLOCKS   62

// With this file name size sizeof(FileIndex) will be 32 bytes. 32 * 64 files
// give us 2KB spent on file index that we can't use for data (so maximum of 62
// files without accounting for the block index).
#define FILE_NAME_SIZE  30
#define FILE_INDEX_NUM  62

// Since we are reserving the first 2K bytes for the filesystem, we have 60
// blocks available for writing data. If you were to change the previous
// parameters, you *must* recalculate the initial block start location.
#define FILE_DATA_START KB(2)

// We must write to the SRAM using the 8bit bus.
#define SRAM ((vu8*)(MEM_CART))

// Special filesystem constants.
enum { FS_INIT_PATTERN = 0xBA, FS_NULL = 0xFF };

typedef struct FileBlock {
    // Size used in the current block (in bytes). Should be smaller than:
    //     FILE_BLOCK_SIZE - sizeof(FileBlock)
    u16 size;
    // The index for the next block. Set to FS_NULL if there is none.
    u8 next_block;
    u8 prev_block;
} FileBlock;

typedef struct FileIndex {
    // File name.
    char name[FILE_NAME_SIZE + 1];
    // Index to the first block of this file. If set to FS_NULL this file
    // has not yet been written to.
    u8 first_block;
} FileIndex;

// The filesystem header.
typedef struct FileSystem {
    // The first byte of the SRAM can become corrupted in some situations, like
    // changing cartridges for example.
    u8 blank;
    // If the filesystem exists, this will be set to FS_INIT_PATTERN.
    u8 initialized;
    // Number of blocks in use.
    u8 busy_blocks;
    // Number of files currently existing in the filesystem.
    u8 num_files;
    // This stores a bitmap pattern to keep track of the blocks in use by the
    // filesystem. The first byte maps the first 8 blocks and so on.
    u8 used_blocks[FILE_MAX_FILES / 8];
    // The list of possible file indexes.
    FileIndex files[FILE_INDEX_NUM];
} FileSystem;

#define FILE_BLOCK_CAPACITY (FILE_BLOCK_SIZE - sizeof(FileBlock))

EWRAM_BSS
static FileSystem filesystem;

void
_fs_read(u8 *dst, u16 pos, u16 n_bytes) {
    for (size_t i = 0; i < n_bytes; ++i) {
        dst[i] = SRAM[pos + i];
    }
}

void
_fs_write(u8 *src, u16 pos, u16 n_bytes) {
    for (size_t i = 0; i < n_bytes; ++i) {
        SRAM[pos + i] = src[i];
    }
}

void
fs_init(void) {
    // Load filesystem if existing.
    _fs_read(&filesystem, 0, sizeof(FileSystem));
    if (filesystem.initialized != FS_INIT_PATTERN) {
        // Clear SRAM.
        for (size_t i = 0; i < KB(64) / 8; ++i) {
            SRAM[i] = 0x00;
        }

        // Initialize block headers.
        FileBlock block = {
            .size = 0,
            .next_block = FS_NULL,
            .prev_block = FS_NULL,
        };
        for (size_t i = 0; i < FILE_INDEX_NUM; ++i) {
            u16 block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * i;
            _fs_write(&block, block_pos, sizeof(FileBlock));
        }

        // Initialize filesystem.
        dma_fill(&filesystem, 0, sizeof(FileSystem), 3);
        filesystem.initialized = FS_INIT_PATTERN;
        for (size_t i = 0; i < FILE_INDEX_NUM; ++i) {
            filesystem.files[i].first_block = FS_NULL;
        }

        // Write the FS to disk.
        _fs_write(&filesystem, 0, sizeof(FileSystem));
    }
}

void
_fs_update_filesystem_header(void) {
    _fs_write(&filesystem, 0, offsetof(FileSystem, files));
}

void
_fs_update_file_index(u16 index) {
    _fs_write(&filesystem.files[index],
            offsetof(FileSystem, files) + index * sizeof(FileIndex),
            sizeof(FileIndex));
}

typedef enum {
    FS_OPEN_READ   = (1 << 0),
    FS_OPEN_WRITE  = (1 << 1),
    FS_OPEN_APPEND = (1 << 2),
} OpenMode;

typedef struct File {
    // File index offset.
    u8 index;
    // The offset within the file. Must always be valid, and so the File struct
    // shouldn't be manaully modified unless we are sure we know what we are
    // doing.
    u16 offset;
    // The mode of this file (read/write/append).
    OpenMode mode;
} File;

File
fs_open_file(char *name, OpenMode mode) {
    // Try to find an existing file.
    for (size_t i = 0; i < filesystem.num_files; ++i) {
        // TODO: Replace strcmp with vectorized fixed size char comparison.
        if (strcmp(name, filesystem.files[i].name) == 0) {
            return (File){i, 0, mode};
        }
    }

    // If read only.
    if ((mode & (FS_OPEN_WRITE | FS_OPEN_APPEND)) == 0) {
        return (File){FS_NULL, 0, mode};
    }

    // Create a new file if there is space.
    if (filesystem.num_files < FILE_INDEX_NUM) {
        u16 index = filesystem.num_files++;
        u16 k = 0;
        while(*name) {
            filesystem.files[index].name[k++] = *name++;
        }

        // Update file index and filesystem on SRAM.
        _fs_update_file_index(index);
        _fs_update_filesystem_header();

        return (File){index, 0, mode};
    }
    return (File){FS_NULL, 0, mode};
}

u16
fs_file_size(File *file) {
    u16 size = 0;
    FileBlock block;
    u16 blk_id = filesystem.files[file->index].first_block;
    while (blk_id != FS_NULL) {
        u16 block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * blk_id;
        _fs_read(&block, block_pos, sizeof(FileBlock));
        size += block.size;
        blk_id = block.next_block;
    }
    return size;
}

u8
_fs_init_new_block(void) {
    // Find free block.
    u8 block_index = 0;
    for (size_t j = 0; j < LEN(filesystem.used_blocks); ++j) {
        for (size_t i = 0; i < 8; ++i, block_index++) {
            u8 blk = (filesystem.used_blocks[j] >> i) & 0x1;
            if (blk == 0) {
                // Initialize the block.
                filesystem.busy_blocks++;
                filesystem.used_blocks[j] |= (1 << i);
                _fs_update_filesystem_header();
                return block_index;
            }
        }
    }
    return FS_NULL;
}

// Recursively free blocks starting at blk_id. To improve performance, the
// filesystem header is updated in memory but not written to disk. It is
// responsability of the caller to perform the filesystem update.
void
_fs_free_blocks(u8 blk_id) {
    if (blk_id == FS_NULL) {
        return;
    }

    // Read block.
    FileBlock block;
    u16 block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * blk_id;
    _fs_read(&block, block_pos, sizeof(FileBlock));

    // Update block.
    u8 next_block = block.next_block;
    block = (FileBlock){
        .size = 0,
        .next_block =  FS_NULL,
        .prev_block = FS_NULL,
    };
    _fs_write(&block, block_pos, sizeof(FileBlock));

    // Update dirty and busy blocks.
    filesystem.busy_blocks--;
    filesystem.used_blocks[blk_id / 8] &= ~(1 << (blk_id % 8));

    _fs_free_blocks(next_block);
}

void
_fs_write_to_block(u8 *src, u16 n_bytes, u16 blk_offset,
        u8 blk_id, u8 prev_blk, bool append) {
    // Read initial block.
    FileBlock block;
    u16 block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * blk_id;
    _fs_read(&block, block_pos, sizeof(FileBlock));
    u16 block_capacity = FILE_BLOCK_CAPACITY - blk_offset;

    // Write capacity.
    u16 block_bytes = MIN(block_capacity, n_bytes);
    _fs_write(src, block_pos + sizeof(FileBlock) + blk_offset, block_bytes);

    if (n_bytes > block_capacity) {
        if (block.next_block == FS_NULL) {
            // Find new available block and initialize it.
            block.next_block = _fs_init_new_block();
        }
        _fs_write_to_block(src + block_capacity, n_bytes - block_capacity, 0,
                block.next_block, blk_id, append);
    } else if (block.next_block != FS_NULL){
        // Recursively free unused blocks.
        _fs_free_blocks(block.next_block);
        _fs_update_filesystem_header();
        block.next_block = FS_NULL;
    }

    // Update block header.
    if (prev_blk != FS_NULL) {
        block.prev_block = prev_blk;
    }
    block.size = block_bytes;
    _fs_write(&block, block_pos, sizeof(FileBlock));
}

typedef enum {
    FS_SEEK_SET,
    FS_SEEK_CUR,
    FS_SEEK_END,
} SeekMode;

int
fs_seek(File *file, int offset, SeekMode mode) {
    u16 file_size = fs_file_size(file);
    u16 new_offset = 0;
    switch (mode) {
        case FS_SEEK_SET: {
            new_offset = offset;
        } break;
        case FS_SEEK_CUR: {
            new_offset = MAX((int)file->offset + offset, 0);
        } break;
        case FS_SEEK_END: {
            new_offset = MAX((int)file_size - 1 + offset, 0);
        } break;
    }
    if (new_offset != 0 && new_offset >= file_size) {
        return -1;
    }
    file->offset = new_offset;
    return 0;
}

u16
fs_write(u8 *src, u16 n_bytes, File *file) {
    if ((file->mode & (FS_OPEN_WRITE | FS_OPEN_APPEND)) == 0) {
        return 0;
    }

    FileIndex *file_idx = &filesystem.files[file->index];

    u8 blk_id = FS_NULL;
    u8 blk_prev = FS_NULL;
    u16 offset = file->offset;
    if (file_idx->first_block == FS_NULL) {
        // Check how many blocks will this write requires and if we have enough
        // available.
        u16 blocks_required = n_bytes / FILE_BLOCK_CAPACITY;
        u16 blocks_available = FILE_N_BLOCKS - filesystem.busy_blocks;
        if (blocks_required > blocks_available) {
            return 0;
        }

        // Find the first available block.
        blk_id = _fs_init_new_block();
        file_idx->first_block = blk_id;

        // Update file index on SRAM.
        _fs_update_file_index(file->index);
    } else {
        // Check how many blocks will this write requires and if we have
        // enough available.
        u16 file_size = fs_file_size(file);
        u16 blocks_in_file = file_size / FILE_BLOCK_SIZE;
        u16 blocks_available = FILE_N_BLOCKS - filesystem.busy_blocks + blocks_in_file;
        u16 blocks_required = (n_bytes + offset) / FILE_BLOCK_CAPACITY;
        if (blocks_required > blocks_available) {
            return 0;
        }

        blk_id = file_idx->first_block;

        // If there is an offset find the block index and relative offset.
        if (offset >= FILE_BLOCK_CAPACITY) {
            u16 n_blocks_offset = offset / FILE_BLOCK_CAPACITY;
            for (size_t i = 0; i < n_blocks_offset; ++i) {
                FileBlock block;
                u16 block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * blk_id;
                _fs_read(&block, block_pos, sizeof(FileBlock));
                blk_id = block.next_block;
                blk_prev = block.prev_block;
                if (blk_id == FS_NULL) {
                    return 0;
                }
            }
            offset = offset % FILE_BLOCK_CAPACITY;
        }
    }

    // Write to block.
    _fs_write_to_block(src, n_bytes, offset, blk_id, blk_prev,
            file->mode == FS_OPEN_APPEND);

    return n_bytes;
}

void
_fs_read_from_block(u8 *dst, u16 n_bytes, u16 blk_offset, u8 blk_id) {
    // Read initial block.
    FileBlock block;
    u16 block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * blk_id;
    _fs_read(&block, block_pos, sizeof(FileBlock));

    u16 read_bytes = MIN(block.size - blk_offset, n_bytes);
    _fs_read(dst, block_pos + blk_offset + sizeof(FileBlock), read_bytes);

    u16 remaining_bytes = n_bytes - read_bytes;
    if (block.next_block != FS_NULL && remaining_bytes > 0) {
        _fs_read_from_block(dst + read_bytes, remaining_bytes, 0, block.next_block);
    }
}

u16
fs_read(u8 *dst, u16 n_bytes, File *file) {
    if ((file->mode & FS_OPEN_READ) == 0) {
        return 0;
    }

    // If there is an offset find the block index and relative offset.
    u8 blk_id = filesystem.files[file->index].first_block;
    u16 offset = file->offset;

    // Read as much as we can from the file after the offset.
    u16 file_size = fs_file_size(file);
    if (offset + n_bytes >= file_size) {
        n_bytes = file_size - offset;
    }

    if (offset >= FILE_BLOCK_CAPACITY) {
        u16 n_blocks_offset = offset / FILE_BLOCK_CAPACITY;
        for (size_t i = 0; i < n_blocks_offset; ++i) {
            FileBlock block;
            u16 block_pos = FILE_DATA_START + FILE_BLOCK_SIZE * blk_id;
            _fs_read(&block, block_pos, sizeof(FileBlock));
            blk_id = block.next_block;
            if (blk_id == FS_NULL) {
                return 0;
            }
        }
        offset = offset % FILE_BLOCK_CAPACITY;
    }

    // Copy n_bytes to destination.
    _fs_read_from_block(dst, n_bytes, offset, blk_id);

    return n_bytes;
}