From f6686f1e86927f038086023362251ebe78ce5ad6 Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Wed, 2 Jun 2021 17:26:08 +0200 Subject: Init repo with basic BG framebuffer renderer --- src/filesystem.c | 409 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 409 insertions(+) create mode 100644 src/filesystem.c (limited to 'src/filesystem.c') diff --git a/src/filesystem.c b/src/filesystem.c new file mode 100644 index 0000000..00c0605 --- /dev/null +++ b/src/filesystem.c @@ -0,0 +1,409 @@ +/* +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. +*/ + +#include + +#include "filesystem.h" + +// 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)); +} + +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)); +} + +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; +} -- cgit v1.2.1