Roaring bitmap library in pure Zig. Wire-compatible with CRoaring (serialized bitmaps interoperate across implementations). No C dependencies.

rawr supports mutation, set operations, positional queries (rank/select), inclusive range operations, n-way union/xor, bulk add/remove/extract, and zero-copy reads. See API.md for the full reference and footgun notes.

Implements the RoaringFormatSpec portable serialization format. Bitmaps serialized by rawr can be read by CRoaring, Java RoaringBitmap, Go roaring, and any other compliant implementation — and vice versa. Validated by zig build validate which round-trips through both rawr and CRoaring.

Roaring64Bitmap uses CRoaring's roaring64 portable format and is validated by zig build validate64. Java's 64-bit Roaring layouts differ and are not supported or tested by rawr's 64-bit serializer.

See API.md for the full API reference.

const rawr = @import("rawr");
const RoaringBitmap = rawr.RoaringBitmap;

// Create and populate
var bm = try RoaringBitmap.init(std.heap.smp_allocator);
defer bm.deinit();

_ = try bm.add(1);
_ = try bm.add(2);
_ = try bm.add(3);
_ = try bm.addRange(100, 200);  // adds 100..200 inclusive

// Query
assert(bm.contains(150));
assert(!bm.contains(50));
const card = bm.cardinality(); // 104

// Iterate
var it = bm.iterator();
while (it.next()) |value| {
    // values in sorted order: 1, 2, 3, 100, 101, ..., 200
}

// Set operations (allocate new bitmap)
var other = try RoaringBitmap.init(std.heap.smp_allocator);
defer other.deinit();
_ = try other.addRange(150, 250);

var intersection = try bm.bitwiseAnd(std.heap.smp_allocator, &other);
defer intersection.deinit();
// intersection contains 150..200

// Set operations (in-place, no allocation)
try bm.bitwiseOrInPlace(&other);
// bm now contains 1, 2, 3, 100..250

// Serialize (CRoaring-compatible wire format)
const bytes = try bm.serialize(std.heap.smp_allocator);
defer std.heap.smp_allocator.free(bytes);

// Deserialize trusted bytes
var restored = try RoaringBitmap.deserialize(std.heap.smp_allocator, bytes);
defer restored.deinit();

// Deserialize untrusted bytes with semantic validation
var safe = try RoaringBitmap.deserializeSafe(std.heap.smp_allocator, bytes);
defer safe.deinit();

Range APIs are inclusive. addRange(100, 200) adds 101 values.

OwnedBitmap uses arena allocation internally — all container memory is freed in one operation. Faster for deserialize and set operations, but no individual remove().

const OwnedBitmap = rawr.OwnedBitmap;

// Deserialize with arena allocation
var owned = try RoaringBitmap.deserializeOwned(std.heap.smp_allocator, bytes);
defer owned.deinit(); // frees everything at once

assert(owned.contains(42));
const card = owned.cardinality();
const min = owned.asBitmap().minimum(); // full read-only RoaringBitmap API
var it = owned.iterator();

// Set operations
var result = try bm.bitwiseAndOwned(std.heap.smp_allocator, &other);
defer result.deinit();

Operates directly on a serialized byte buffer. No deserialization, no heap allocation. Read-only.

const FrozenBitmap = rawr.FrozenBitmap;

var frozen = try FrozenBitmap.init(bytes);
defer frozen.deinit();

assert(frozen.contains(42));
const card = frozen.cardinality();
var it = frozen.iterator();

Avoid std.heap.c_allocator — it is 10-40x slower than alternatives for rawr's allocation patterns (many small containers). Measured on macOS M4; gap may vary on other platforms.

Recommended allocators, fastest to most flexible:

For hot loops with bounded lifetime (evaluation rounds, request handling), pre-allocate a FixedBufferAllocator and reuse it across iterations.

Requires Zig 0.16.0+.

zig build              # build library
zig build test         # run tests
zig build validate     # CRoaring interop validation
zig build bench        # rawr-only benchmarks
zig build bench-compare # rawr vs CRoaring comparison
zig build bench-alloc  # allocator matrix experiment

The vendored CRoaring reference build disables AVX512 by default for portable Zig 0.16 builds. Use -Dcroaring-avx512=true when comparing against an AVX512 CRoaring build on a compatible target/toolchain.

Run benchmarks (results saved to misc/):

./scripts/run-bench.sh           # rawr benchmarks
./scripts/run-compare-bench.sh   # rawr vs CRoaring comparison
./scripts/run-bench-alloc.sh     # allocator matrix experiment

~9400 lines of Zig across 18 source files. Three container types per the Roaring spec:

• Array containers — sorted u16 arrays for sparse chunks (<4096 values)
• Bitset containers — 8KB bitmaps for dense chunks, SIMD via @Vector(8, u64)
• Run containers — run-length encoded for sequential ranges

Key implementation details:

• SIMD bitset operations (OR/AND/XOR/ANDNOT) via @Vector, lowers to AVX-512/AVX2/NEON depending on target
• Branchless merge walks for array container intersection/union
• Run-aware addRange — creates run containers directly instead of element-by-element insertion
• Bulk I/O serialization — descriptive headers and container data written in single operations, no per-element loops
• Arena-friendly allocation — all container init/deinit goes through std.mem.Allocator, works with any Zig allocator

src/
  bitmap.zig          # RoaringBitmap, OwnedBitmap (public API)
  bitmap_tests.zig    # unit tests for bitmap.zig
  array_container.zig # sorted u16 array container
  bitset_container.zig# 8KB bitset container (SIMD)
  run_container.zig   # run-length encoded container
  container.zig       # tagged union over container types
  container_ops.zig   # cross-container set operations (9 type pairs)
  serialize.zig       # RoaringFormatSpec serialize/deserialize
  frozen.zig          # FrozenBitmap (zero-copy)
  optimize.zig        # runOptimize, container type conversions
  compare.zig         # isSubsetOf, equals
  format.zig          # format constants
  roaring.zig         # public module root
  bench.zig           # standalone benchmarks
  bench_croaring.zig  # CRoaring comparison benchmarks
  bench_allocators.zig# allocator matrix experiment
  validate_croaring.zig# CRoaring interop validation
  property_tests.zig  # randomized property tests
tools/
  croaring_wrapper.h  # rawr-owned translate-c adapter for development tools
vendor/
  roaring.c, roaring.h # CRoaring amalgamation (for benchmarks/validation only)
  LICENSE-CRoaring     # upstream Apache-2.0/MIT license text

The downstream Zig package contains the library and its unit-test sources. The CRoaring amalgamation, translate-C adapter, validation executables, differential tests, and benchmark drivers are repository-only development tooling.

Original rawr code is licensed under the Mozilla Public License 2.0. When MPL-covered rawr files are distributed with modifications, those files and their modifications must remain available under MPL-2.0. Separate applications and source files that merely import, link to, or use rawr may remain proprietary or use another license.

Third-party files under vendor/ retain their upstream licenses and are not covered by rawr's MPL-2.0 license. See THIRD_PARTY_NOTICES.md for details.