frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

Open in hackernews

A compact bitset implementation used in Ocarina of Time save files

https://github.com/jb55/oot_bitset
50•todsacerdoti•4d ago

Comments

brcmthrowaway•5h ago
So there is no compression?
dazzawazza•5h ago
No. This might seem useless to non game coders but it's a very common pattern in videogames. The state of the world is frequently 1000s of yes/no data points.

It's not rocket science but this seems like a decent enough implementation of it. The number of data points rarely goes beyond thousands so compression doesn't have much value.

sandinmyjoints•3h ago
(From a non-game coder) How do teams keep track of which events need to be tracked in state, what their names are, etc.? (Not how as in how is this possible, but rather, what kinds of processes have evolved for this.) Like are state events typically planned out ahead of time, or do devs realize which ones they need as they go? What if I want to add a new event to state, how can I check if someone else has added it -- do I just scan all the names in the code and hope that it was named something that I will recognize?
hbn•2h ago
If you look at the code linked to for the OoT decomplication, it's centralized in a single file everyone would be committing to

https://github.com/zeldaret/oot/blob/4d2bc68bacdff06261f7a89...

AshamedCaptain•1h ago
That is not at all representative of how the original code would have looked like. At all.

I am tired of people assigning pseudo-magical properties to "decompilations" while at the same doublethinking them as a way to launder copyrighted works.

sandinmyjoints•1h ago
Yeah looking at that is what prompted this question. Are the events in order? If so: the index for an event in the bitmap is constant, so if you realize you need to save an event that wasn't previously being saved, how do you insert it to keep order? Do you break all previously saved data by changing all the following indexes? Or are the events not in order, which could make it harder to find if an event is already in it (and just generally be confusing)? Managing a long list of events like this given that it is used for persistent state seems like an interesting process challenge.
kvdveer•4h ago
No compression. In the olden days, storage was scarce. While you could compres the bitset, the worst case compression of that bitset would be larger than the uncompressed size. You likely have no way to guarantee the worst case is impossible, so you'd have to reserve extra space. In the end you'd store more data, in a slower to use format.

These days storage bandwidth is the main limiter, so now compression makes sense. When storage size is the main limiter, compression is ironically not very helpful.

abcd_f•5h ago
How's this notable? It’s literally the most straight-forward, trivial bitset implementation.
rixed•4h ago
After reading your comment, I was expecting some kind of RLE over a bit set. But no, not even that?

So I guess, it is notable because it shows how far coding has been industrialized; ie has been dumbed down so much that a mere bit field can be presented as some esoteric trick.

At this speed AGI is indeed around the corner :-D

convolvatron•4h ago
omg, its so obvious! making computers smart is hard, but making people think less requires no effort at all. I can't believe I missed the plan so thoroughly.
pixelpoet•4h ago
Reminds me of the kerfuffle about https://en.wikipedia.org/wiki/Tai%27s_model, where someone managed to get published what is basically the Trapezoidal Rule for numerical integration, and of course had to name it after themselves.
bangonkeyboard•4h ago
> Tai disagreed that Tai's model is simply the trapezoidal rule, on the basis that her model uses the summed areas of rectangles and triangles rather than trapezoids.

Oh my god.

perching_aix•2h ago
The world is big and rediscoveries are not always going to be so graceful. If stuff is harder / more annoying to find than to figure it out yourself, you're downright reasonable for intentionally attempting so even.

If I remember correctly, in the "Tia's rule" case specifically, her coworkers even defended her for the whole thing - implying of course that she was being ridiculed for this, making neither side of this story look very pretty if you ask me.

Also why people don't "RTFM". Yes, I can read through the pages of prose you wrote how you implemented e.g. bog standard role based auth. Or I can just brute force try using all the related looking commands and see what happens...

dylan604•38m ago
> The world is big and rediscoveries are not always going to be so graceful.

It is telling how someone can think their idea is so novel, and rather than doing research go ahead and announce it like it is something new.

perching_aix•13m ago
But it really isn't. How many e.g. business ideas do you think are thought up every day, only for people to find that they already exist and have well established players? Most times people just catch themselves on time, or go through this with a smaller audience first that they know in person. Has this really never happened to you or anyone you know? Is this concept really that alien to you?
TOGoS•3h ago
The neat thing here is that they did it without involving three package managers, two Docker containers, and an LLM.
dylan604•38m ago
How I converted a C++ bit mover package to Rust
a_e_k•4h ago
Darn. By "compact", I thought there'd be some clever sparsity or compression to get below 1 bit/flag in common cases.
bangonkeyboard•4h ago
Apparently "compact" here refers to the five lines of actual code.

Just use <bitstring.h>.

armada651•4h ago
> The most novel aspect of OoT bitsets is that the first 4 bits in the 16-bit coordinate IDs index which bit is set.

Am I the only one who was trouble parsing this sentence correctly?

curiousgal•4h ago
The coordinates IDS are 16-bit long. The first 4 bits index (verb) which bit is set.
ethan_smith•4h ago
It means the first 4 bits of a 16-bit ID determine which bit position (0-15) to set in the bitset, essentially using part of the ID itself as an index into the bitset.
coldpie•4h ago
No, haha, it took me a while, too. "Index" is operating as a verb here.
jb55•3h ago
prs welcome
jb55•3h ago
i updated the wording, hope its more clear
tacker2000•4h ago
How is this in any way novel? People have been doing this since the dawn of time.
jb55•3h ago
I will remove the novel wording just for the hacker news geniuses. I have been programming for 26 years and have never encountered this pattern, nor could I find it in any libraries, which is why I decided to wrap it up in a library.

If a simple bitset like this exists in a library somewhere I would love to see where! Most implementations I've seen over-complicate it for simple use cases like this.

sumtechguy•3h ago
You may enjoy this page then. https://graphics.stanford.edu/~seander/bithacks.html

Bunches of bit twiddling things people like to do in different places for either speed/space.

jb55•3h ago
I have had the experience of explaining to coworkers how bitwise operators even work more than once. I think sometimes people overestimate the average programmers knowledge when it comes to bit operations. modern programming is so detached from having to use that for day to day work.

I am aware of the bithacks page, but I just found encoding the bit coordinate in the ID itself so clever.

Sesse__•1h ago
Can I ask, how would you do it otherwise? Is there any other way? Or is the supposed novelty here that the two values are packed into the same byte instead of having some zero bits between?
jfyi•24m ago
Yeah, you weren't going to win this. Most developers I've met would have approached this from one of the two extremes:

"Lol, this is the obvious implementation."

or

"Lol, just use a boolean."

That is to say, those that might be interested would already know. I'd expect very little in between.

Fwiw, I do think noticing the id readability is notable from a reverse engineering standpoint.

dooglius•1h ago
C++ std::vector<bool>
orlp•4h ago
> The most novel aspect of OoT bitsets is that the first 4 bits in the 16-bit coordinate IDs index which bit is set. For example, 0xA5 shows that the 5th bit is set in the 10th word of the array of 16-bit integers. This only works in the 16-bit representation! 32 bit words would need 5 bits to index the bit, which wouldn't map cleanly to a nibble for debugging.

There is nothing novel about this really. It's neat that it works with hexadecimal printing to directly read off the sub-limb index but honestly who cares about that.

Outside of that observation there's no advantage to 16-bit limbs and this is just a bog-standard bitset where the first k bits indicate the position within the 2^k bit limb, and the remaining bits give you the limb index.

jb55•3h ago
updated for the hacker news crowd

https://github.com/jb55/oot_bitset#:~:text=Hacker%20news%20f...

lpribis•3h ago
Haha, good to take the classic HN condescension on the chin ;)
TimorousBestie•1h ago
For what it’s worth, I found it interesting. I like your verve.
orlp•36m ago
My comment was worded a bit too harshly, sorry about that, I certainly wouldn't have worded that way in a personal message.

As I mentioned the hexadecimal printing coincidence is a neat fact, I was just excited when clicking the link to find a novel bitset idea. In my disappointment to find the standard bitset (albeit with 16-bit limbs) I reacted a bit too harshly. And as per https://xkcd.com/1053/, just because something isn't new to me doesn't mean it's not new to anyone.

Const-me•3h ago
In C++, std::vector<bool> does pretty much the same thing under the hood.

Sadly, C++ standard library API designers made it impossible to directly access the array of integers stored inside std::vector<bool>. This made serialization/de-serialization of these vectors very inefficient, sometimes prohibitively so.

jamesu•3h ago
Reminds me of the extensive use of bitsets in Starfox Adventures. Not only was object spawning tied to flags, many dynamic effects were too so if you prodded the flags in memory often a lot of funky things would happen like explosions getting triggered and cutscenes.
gurkwart•2h ago
I love this one! Thanks for sharing.

It's not about the bitset itself. It's about how to organize and think about your flags.

The small visualization grid is fantastic for debugging, and the `word:bit` structure lends itself directly to organize your data in categories and display them as such.

firesteelrain•2h ago
I used to work at a Company where I did parking software and it was based on Borland C++ Builder 6 codebase. Up to 2012, when I left, we were using Bit flags to indicate configuration settings. We would store these settings in a config file as binary and recall it back when the application started up. We stored a ton of configuration in each flag and it was easy to add more.

But in retrospect, it wasn't super great if the disc or installation somehow got corrupted. You would lose your entire configuration and parking operators do not have the best IT.

This way of storing configuration was designed back in the 90s at this Company and it survived over 20 years. This was prior to this Zelda game and I never played it.

dylan604•40m ago
wow, then DVD programming must owe Company some due thanks because that's how GPRM/SPRM values were stored as 16bits where we'd XOR the halibut out of it get the specific values we wanted to know about. it's a good thing Company existed as nobody else on the planet would have ever figured out how to bit shift or otherwise use masks to get data out of 16bit int in ways other than just storing an integer.

not really sure why you chose to come down the way you did, but wow, just wow.

warvair•1h ago
This seems quite nice. Simple bit-shifting of the 16-bit ID gives both the index into the array of 16-bit words and the bit in the word and allows up to 65536 bitflags. This makes for a very efficient and easy to implement bitflag set/check system given these constraints.
estebarb•1h ago
It is hard to understand how it works from the explanation, but seems to be only useful for really sparse bitmaps. But in a general case, I don't see how it is better than roaring bitmaps.

Breaking Git with a carriage return and cloning RCE

https://dgl.cx/2025/07/git-clone-submodule-cve-2025-48384
205•dgl•3h ago•55 comments

Radium Music Editor

http://users.notam02.no/~kjetism/radium/
83•ofalkaed•3h ago•23 comments

Bootstrapping a side project into a profitable seven-figure business

https://projectionlab.com/blog/we-reached-1m-arr-with-zero-funding
34•jonkuipers•22h ago•7 comments

Dynamical origin of Theia, the last giant impactor on Earth

https://arxiv.org/abs/2507.01826
43•bikenaga•2h ago•5 comments

Supabase MCP can leak your entire SQL database

https://www.generalanalysis.com/blog/supabase-mcp-blog
290•rexpository•3h ago•125 comments

Smollm3: Smol, multilingual, long-context reasoner LLM

https://huggingface.co/blog/smollm3
162•kashifr•4h ago•29 comments

Taking over 60k spyware user accounts with SQL injection

https://ericdaigle.ca/posts/taking-over-60k-spyware-user-accounts/
114•mtlynch•5d ago•35 comments

The Tradeoffs of SSMs and Transformers

https://goombalab.github.io/blog/2025/tradeoffs/
10•jxmorris12•1h ago•1 comments

TIL you can make "GIFs" with SVGs for GitHub README.md files

https://koaning.io/posts/svg-gifs/
292•cantdutchthis•12h ago•79 comments

GlobalFoundries to Acquire MIPS

https://mips.com/press-releases/gf-mips/
103•mshockwave•4h ago•66 comments

Show HN: OffChess – Offline chess puzzles app

https://offchess.com
273•avadhesh18•12h ago•103 comments

Can an email go 500 miles in 2025?

https://flak.tedunangst.com/post/can-an-email-go-500-miles-in-2025
228•zdw•4d ago•86 comments

Plants monitor the integrity of their barrier by sensing gas diffusion

https://www.nature.com/articles/s41586-025-09223-4
22•Bluestein•3d ago•0 comments

Google can now read your WhatsApp messages

https://www.neowin.net/guides/google-can-now-read-your-whatsapp-messages-heres-how-to-stop-it/
358•bundie•4h ago•231 comments

Show HN: Jukebox – Free, Open Source Group Playlist with Fair Queueing

https://www.jukeboxhq.com/
66•skeptrune•5h ago•30 comments

Brut: A New Web Framework for Ruby

https://naildrivin5.com/blog/2025/07/08/brut-a-new-web-framework-for-ruby.html
56•onnnon•2h ago•24 comments

Show HN: A rain Pomodoro with brown noise, ASMR, and Middle Eastern music

https://forgetoolz.com/rain-pomodoro
14•ShadowUnknown•3h ago•3 comments

On The Meaning of Ritual

https://alicemaz.substack.com/p/on-the-meaning-of-ritual
42•jger15•3d ago•29 comments

Ceramic: A cross-platform and open-source 2D framework in Haxe

https://ceramic-engine.com/
23•-yukari•3d ago•1 comments

Particle Lenia Deluxe Edition

https://www.craftlinks.art/Notebook/particle-lenia/
11•CraftingLinks•3d ago•1 comments

Inertial forces (indirect terms) in problems with a central body

https://astro.theoj.org/article/141682-on-inertial-forces-indirect-terms-in-problems-with-a-central-body
3•raattgift•2d ago•0 comments

New sphere-packing record stems from an unexpected source

https://www.quantamagazine.org/new-sphere-packing-record-stems-from-an-unexpected-source-20250707/
397•pseudolus•1d ago•199 comments

Fast cryptographically safe GUID generator for Go

https://github.com/sdrapkin/guid
12•sdrapkin•2h ago•19 comments

Attimet (YC F24) – Quant Trading Research Lab – Is Hiring Founding Researcher

https://www.ycombinator.com/companies/attimet/jobs/6LaQIc5-founding-researcher-quant
1•kbanothu•9h ago

Mercury: Ultra-fast language models based on diffusion

https://arxiv.org/abs/2506.17298
545•PaulHoule•1d ago•223 comments

I used o3 to profile myself from my saved Pocket links

https://noperator.dev/posts/o3-pocket-profile/
484•noperator•1d ago•185 comments

Berry Script: lightweight embedded scripting language for microcontrollers

https://berry-lang.github.io/
86•hasheddan•3d ago•34 comments

Epanet-JS

https://macwright.com/2025/07/03/epanet-placemark
192•surprisetalk•4d ago•22 comments

Brainwash '72 [video]

https://archive.org/details/Brainwash72
13•petethomas•2h ago•3 comments

Show HN: I built a tool to solve window management

https://aboveaverageuser.com/smartswitcher
34•atommachinist•6h ago•53 comments