From 70a801a43c16fd7a5f61e8d876e5d5c2db48ebe8 Mon Sep 17 00:00:00 2001 From: Miquel Sabaté Solà Date: Wed, 16 Sep 2026 22:34:56 +0200 Subject: Initial commit MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Miquel Sabaté Solà --- README.md | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) create mode 100644 README.md (limited to 'README.md') diff --git a/README.md b/README.md new file mode 100644 index 0000000..c87a374 --- /dev/null +++ b/README.md @@ -0,0 +1,59 @@ +Manipulate B-Trees with your NES/Famicom controller. This is basically an +implementation of COW-friendly B-Trees in pure 6502 assembly, with a little UI +on top of it just to showcase it. + +## The "game" + +The "game" is just a file explorer. Use the arrow keys to go up/down the list, +and press A or Start to edit one of the files. There's +also the option to create a new file. Press A or Start and +it will prompt you to give it a unique name. With that, a file will be created +and you will jump into edit mode. + +You can edit the file currently selected with the following button mapping: + +- B: change the character. +- A: write the character in place. +- Arrows: move around the document. +- Start: save the file. +- Select: go back to the file explorer. + +## Internal design +### The data structure + +The main data structure is a COW-friendly B-tree (just like filesystems like +[btrfs](https://btrfs.readthedocs.io/en/latest/)). You can read all about them +[here](https://btrfs.readthedocs.io/en/latest/dev/dev-btrfs-design.html). To sum +things up, these are B+-trees which: + +1. Are updated top-down. +2. Leaf nodes are not chained. +3. Storage management is done via delayed reference counting. + +Here we have the invariant that a node has between 2 to 5 elements before it +gets split or merged. When a modification happens, it's done top-down, and all +modified elements are copied in a new location: the update is not done in-place. + +### On top of the NES/Famicom + +The storage is covered via the 8KB battery-backed PRG-RAM that some chips +allowed. In particular, here the MMC1 chip is being used just because it's the +one that allows for this and it's simple enough. This chip allows for having a +swappable bank, and here's where I've written my code, inside of the "LIBTREE" +segment and on the `lib.s` file. There is no good reason to have the library +into another segment, but it felt like a good way to have separation of +concerns. + +In the context of operating systems, we would be manipulating at the page +level. Out of simplicity here the same is done, the size of which will be the +one native to the 6502 platform: 256B. Hence, on PRG-RAM we have 32 pages in +total. + +## But, why? + +Just for fun :) + +## License + +Released under the [GPLv3+](http://www.gnu.org/licenses/gpl-3.0.txt), Copyright +(C) 2026-Ω Miquel Sabaté Solà. -- cgit v1.2.3