paniq

The .bag File Format

A .bag file (short for "Blobby/Binary/Boxed/Bagged Atom Graph") file describes a directed graph of atoms, which can be either blob (array of bytes) or cell (array of atoms) in topological order of ownership, leaves first, root last. This renders the format particularly append/overlay-friendly, as the root can be rewritten without changing the existing file or removing unused nodes.

.bag is comparable to RIFF in scope but fixes two major problems with it, namely that RIFF can only encode trees and isn't topologically ordered, requiring the use of a stack when reading it.

The format can be read as a binary stream of 64-bit words. It begins with the magic 4-character sequence .bag and a 32-bit version which must be 1 (hence .bag\x01\0\0\0 or 0x000000016761622e), and is then only followed by atoms until the file ends.

An atom begins with a header word, followed by its contents, aligned t

pervognsen

// This can grow a Robin Hood linear probing hash table near word-at-a-time memcpy speeds. If you're confused why I use 'keys'
// to describe the hash values, it's because my favorite perspective on Robin Hood (which I learned from Paul Khuong)
// is that it's just a sorted gap array which is MSB bucketed and insertion sorted per chain:
// https://pvk.ca/Blog/2019/09/29/a-couple-of-probabilistic-worst-case-bounds-for-robin-hood-linear-probing/
// The more widely known "max displacement" picture of Robin Hood hashing also has strengths since the max displacement
// can be stored very compactly. You can see a micro-optimized example of that here for small tables where the max displacement
// can fit in 4 bits: Sub-nanosecond Searches Using Vector Instructions, https://www.youtube.com/watch?v=paxIkKBzqBU
void grow(Table *table) {
	u64 exp = 64 - table->shift;
	// We grow the table downward in place by a factor of 2 (not counting the overflow area at table->end).

rygorous

// float->sRGB8 conversions - two variants.
// by Fabian "ryg" Giesen
//
// I hereby place this code in the public domain.
//
// Both variants come with absolute error bounds and a reversibility and monotonicity
// guarantee (see test driver code below). They should pass D3D10 conformance testing
// (not that you can verify this, but still). They are verified against a clean reference
// implementation provided below, and the test driver checks all floats exhaustively.
//