OoT Bitset

The simple, no‑frills flag system used in The Legend of Zelda: Ocarina of Time

Implemented in C / C++, and Rust

Need to pack hundreds (or thousands) of one‑bit flags—“talked to an NPC”, “opened a chest”, etc.—into a save file without wasting bytes? Ocarina of Time solved this by storing flags in an array of uint16_t words. oot_bitset offers the same trick!

I learned about this technique from reading the OoT decompilation project source code. See the original code that implements these flags for OoT's save file event information tables.

Why use it?

The bitset used in OoT is the simplest possible implementation of a bitset. It is not new or novel. It is not fancy or full of features, but it has some nice properties that is good enough for many use cases.

• Simple, header‑only, zero deps – drop a header (C) or add a tiny dependency (Rust). No heap, no alloc.
• Space‑efficient – 1 × u16 word = 16 flags. Scale from 1 to 4096 words (65 536 flags).
• Fast – branch‑free bit‑twiddling; compiles to a handful of instructions.
• Scalable – need 10 flags or 10 000? Just resize the array.
• Intuitive IDs for debugging – 0x12 maps to first word, second bit.

I wrapped this into a library because I haven't seen this pattern implemented anywhere, and wanted to have a library I could use in my projects. I also thought it was a neat bit of OoT lore for software engineer zelda enjoyers.

Why its cool

One clever aspect of how Ocarina of Time uses bitsets is that the first 4 bits of a 16-bit flag ID directly indicate which bit is set. For example, the ID 0xA5 means “set the 5th bit of the 10th 16-bit word” — the A (10 in decimal) selects the 10th word, and the 5 selects the 5th bit within that word.

This works neatly because the word size is 16 bits: 4 bits are enough to index any bit within a 16-bit word, and it also aligns nicely with a nibble for debugging. If you switched to 32-bit words, you’d need 5 bits to index the bits within the word, which no longer fits cleanly into a single nibble.

TL;DR: The flag ID encodes both the word and the bit — it’s the coordinate of the bit!

Bits	15…4 (12 bits)	3…0 (4 bits)
Use	word index	bit index
Max	0–4095 words	0–15 bits

These form a grid, and you can create UIs that visually map these coordinates to a visual editor:

Hacker news folks say this is not that new or interesting, but I thought it was! I hope some others find it interesting as well.

Quick start

C example

#include "oot_bitset.h"
#include <stdio.h>

enum GameEvents {
    FLAG_MET_RUTO_FIRST_TIME        = 0x00, // word 0, bit 0
    FLAG_TALKED_TO_MALON_FIRST_TIME = 0x02, // word 0, bit 2
    ..
    FLAG_SAW_BOB                    = 0x10, // word 1, bit 0
    FLAG_SAW_ALICE                  = 0x1A  // word 1, bit 10
};

int main(void) {
    uint16_t flags[30] = {0};   // 30 words ⇒ 480 flags

    bitset_set(flags, FLAG_SAW_BOB);
    printf("Saw Bob? %s\n", bitset_get(flags, FLAG_SAW_BOB) ? "yes" : "no");
}

Compile:

cc -std=c99 demo.c -o demo

Rust example

use oot_bitset::{bitset_get, bitset_set};

#[repr(u16)]
enum GameEvents {
    MetRutoFirstTime        = 0x00, // word 0, bit 0
    TalkedToMalonFirstTime  = 0x02, // word 0, bit 2
    SawBob                  = 0x10, // word 1, bit 0
    SawAlice                = 0x1A, // word 1, bit 10
}

fn main() {
    let mut flags = [0u16; 30]; // 30 words ⇒ 480 flags

    bitset_set(&mut flags, GameEvents::SawBob as u16);
    println!("Saw Bob? {}", bitset_get(&flags, GameEvents::SawBob as u16));
}

Run:

cargo run --example basic

API reference

C functions & macros

#define bitset_word(set, flag)  ((set)[bitset_index(flag)])
static inline uint16_t bitset_index(uint16_t flag); // word (0–4095)
static inline uint16_t bitset_mask(uint16_t flag);  // bit  (0–15)
static inline bool     bitset_get (uint16_t *set, uint16_t flag);
static inline void     bitset_set (uint16_t *set, uint16_t flag);
static inline void     bitset_clear(uint16_t *set, uint16_t flag);

Rust equivalents

pub const fn bitset_index(flag: u16) -> usize;
pub const fn bitset_mask(flag: u16) -> u16;

pub fn bitset_get  (set: &[u16],   flag: u16) -> bool;
pub fn bitset_set  (set: &mut [u16], flag: u16);
pub fn bitset_clear(set: &mut [u16], flag: u16);
pub fn bitset_word_mut(set: &mut [u16], flag: u16) -> &mut u16;

All functions are #[inline(always)] and panic if the slice is too short.

Installation

C / C++

1. Copy oot_bitset.h somewhere in your include path.
2. Compile with any C99 (or later) compiler—no extra flags required.

cc -std=c99 my_game.c -o my_game

Rust

Add the crate to your Cargo.toml:

[dependencies]
oot_bitset = "0.1"

Sizing the array

max_flags = words × 16
words     = ceil(max_flags / 16)

Use as few or as many words as your project needs. OoT used 30 words (480 flags), but nothing stops you from using 1 word (16 flags) or 4 096 words (65 536 flags).