0.13.0

Version 0.13.0

Changelog

• Added DiffOptions::ignore_missing_final_newline (the mbo::diff --ignore_missing_final_newline flag and the diff_test ignore_missing_final_newline attribute): a file with and one without a trailing newline compare equal (the \ No newline at end of file marker is suppressed). It only ignores the terminator, so an empty file stays distinct from a single empty line. Honored identically by all three algorithms (shared Data preprocessing).
• mbo::diff now treats an empty DiffOptions::time_format as "omit the timestamp": the unified/context file header becomes a git-style --- name / +++ name (name only, no per-file mtime), so the output is reproducible across machines and time zones. A non-empty time_format is unchanged, and time_format stays library-only.
• Added a Myers diff algorithm (mbo::diff::DiffMyers, "An O(ND) Difference Algorithm and Its Variations", the algorithm behind GNU diff and git) and made it the default (DiffOptions::Algorithm::kMyers, --algorithm=myers). Lines are interned into integer tokens (honoring all ignore/strip/replace options), the linear-space middle-snake divide and conquer produces minimal diffs, and past a cost cap of max(64, sqrt(L+R)) a git-style furthest-reaching split bounds pathological inputs. Compared to the previous default the common scattered-edits case is >2x faster and the disjoint-files worst case drops from ~16s to <1ms (2k lines, //mbo/diff:diff_benchmark).
• Sped up the myers tokenizer: interning keys are now std::string_views into the preprocessed line cache hashed with mbo::hash::GetHash64 (previously every line was copied into a std::string-keyed map), and ignore_case folds each line once into a reused buffer with stable storage only for distinct lines. Tokenize-heavy inputs (20k distinct 120-char lines) run ~16% faster; see the tokenize_* cases in //mbo/diff:diff_benchmark (whitespace-ignore variants included; ignore_all_space now also builds its stripped line in place instead of via an extra copy).
• The mbo::diff binary follows the POSIX diff exit code contract: 0 = equal, 1 = different, 2 = trouble (unreadable input, internal error, bad usage; previously conflated with 1). The bazel diff_test rule gained the minimal attribute, and mbo/diff/TODO.md records the remaining optional features and explicit non-goals.
• Rounded out the mbo::diff CLI/test surface: new --minimal flag (DiffOptions::minimal) guaranteeing minimal myers diffs by disabling the cost cap (like GNU diff --minimal); the usage message names all algorithms and formats; the bazel diff_test rule gained width and skip_left_deletions attributes; and a CLI bashtest now checks the full algorithm x format matrix against per-engine expected outputs, so an untested or unsupported combination fails by name. max_diff_chunk_length and time_format intentionally stay library-only.
• Renamed the previous default mbo::diff algorithm from unified to what it is: naive (DiffOptions::Algorithm::kNaive, mbo::diff::DiffNaive, mbo/diff/impl/diff_naive.*). It greedily resynchronizes on the closest matching line and does not produce minimal diffs. The flag/attribute value unified remains supported as a deprecated alias that now selects myers - matching its historic "like diff -u" promise - and enforces --format=unified.
• Verified the mbo::diff feature/algorithm support matrix with tests: all comparison options (ignore_case, ignore_all_space, ignore_consecutive_space, ignore_trailing_space, ignore_blank_lines, ignore_matching_lines, strip_comments, regex_replace_*) work identically under naive, myers and direct, and all three output formats work with every algorithm. One documented corner case: combining ignore_case with a case-sensitive ignore_matching_lines expression - a matching and a non-matching line differing only in case compare equal under naive but not under the token-based myers; write such expressions case-insensitively ((?i)...). max_diff_chunk_length only applies to naive (myers uses an internal cost cap, direct needs no bound).
• Added mbo::diff output formats: next to the default unified format, DiffOptions::output_format selects context format (diff -c) or normal format (plain diff). The diff binary and the diff_test bazel rule gained the matching --format=unified|context|normal flag / format attribute (normal format defaults --context to 0 and emits no file headers; context format uses ***/--- file headers). Both new formats reproduce GNU diff output byte for byte and apply cleanly with patch.
• Fixed mbo::diff unified output for empty ranges (pure insertions or deletions, visible with --context=0): the chunk header now references the line preceding the gap (e.g. @@ -2,0 +3 @@ instead of @@ -3,0 +3 @@), matching GNU diff. Previously patch applied such hunks one line too late.
• Split the mbo::diff chunk rendering out of mbo/diff/internal/chunk.cc into mbo/diff/internal/output.{h,cc} (diff_internal::AppendChunk); Chunk now only accumulates and filters.
• Added mbo::hash::GetHash64(std::string_view) / GetHash128(std::string_view) and the mbo::hash::Hash128 result type - constexpr-safe, non-cryptographic hashing; the default algorithm is the in-house mumbo (see below).
• Renamed the legacy in-house hash mbo::hash::simple to mbo::hash::dumbo and redesigned it into a compact single-lane MUM hash. Nothing-up-my-sleeve constants (golden ratio, sqrt-prime fractions), a widening Mul128Fold64 step over 8-byte words, and a two-multiply seed-injected finalizer take it from the legacy SMHasher3 40/188 to a clean PASS 188/188 (all three in-house hashes are now clean), ~2-3x faster than the legacy hash for >=8 B, and the fastest hash in the suite for tiny keys - single-lane, so it slows on large keys; a deliberately minimal companion to mumbo, not a replacement (see mbo/hash/README.md for the measured design iterations). The deprecated simple::GetHash wrapper and the mbo::hash::simple namespace are removed outright - pre-1.0, so no compatibility alias is kept and existing mbo::hash::simple::* users must migrate. Use mbo::hash::GetHash64 (mumbo) as the default; mbo::hash::dumbo::GetHash64(data, seed) is the seeded, SMHasher3-clean minimal option. Values are not stable across library versions.
• All mbo::hash entry points (GetHash64, GetHash128, GetHash) are now templates over an algorithm struct (default DefaultHashAlgorithm, i.e. mbo::hash::mumbo). Every algorithm provides a <ns>::Algorithm struct with static GetHash64/GetHash128 members; the concepts HasGetHash64/HasGetHash128/IsHashAlgorithm detect what is available, and Hasher<Algo> completes partial algorithms with fallbacks (128->64 fold; for a missing 128 two decorrelated 64-bit passes where the second skips the first up-to-8 bytes and injects them via the seed, so both lanes cover every byte and differ even for seed-ignoring algorithms).
• Added constexpr-safe, canonical implementations of further hash algorithms, all usable as algorithm structs with GetHash64<Algo>: mbo::hash::fnv1a::GetHash64 (FNV-1a 64), mbo::hash::xxh64::GetHash64 (XXH64), mbo::hash::xxh3::GetHash64 (XXH3 64-bit, scalar), and mbo::hash::murmur3::GetHash64/GetHash128 (MurmurHash3 x64 128). All produce the published reference values on every platform (little-endian defined).
• Exposed mbo::hash::Hash128To64(Hash128): folds a 128-bit hash into a well-mixed 64-bit one, e.g. to derive a fold-mixed 64-bit value from murmur3::GetHash128 (whose GetHash64 is the canonical h1 truncation instead).
• Added the build-seed mangle as its own entry point mbo/hash/hash_mangle.h (//mbo/hash:hash_mangle_cc): GetHash<Algo, Seed> and MangledHasher<Algo> XOR ONE build-selected constant into GetHash64 values (still constexpr), so values deliberately do not compare across independently configured builds; plain hash.h / :hash_cc stays fully deterministic and is never exposed to (or rebuilt for) seed variation. The constant lives in one generated header per configuration (consistent per program by construction), folding the module's own version (read from MODULE.bazel via native.module_version() - no duplicated version declaration, correct also when consumed via BCR - so every release rotates mangled values at zero marginal cost: a release recompiles dependents anyway) with the custom Bazel flags --//mbo/hash:mangle_seed (any printable-ASCII string; folded to a bucket inside the header-generation rule, so build/remote caches see a bounded set of variants no matter what rotates through the flag) and --//mbo/hash:mangle_seed_buckets (default 8; 0 disables the mangle making GetHash == GetHash64, 1 pins one stable constant across releases and seeds).
• Runtime loads use memcpy (gcc never folded the byte-assembly loads - roughly 3x on gcc for all algorithms) and tail loads use branch-lite overlapping reads; constant evaluation keeps the byte-assembly path (values identical, guarded by tests).
• Hasher<Algo> is also a transparent functor, usable directly as the hash parameter of absl/std hash containers with heterogeneous std::string_view lookup.
• Added mbo::hash::CombineHashes(uint64_t, uint64_t) (order-dependent, well-mixed combine) and hash_internal::Mul128Fold64 (constexpr 64x64->128 fold, xxh3/wyhash family core).
• Test framework additions: seed-bit avalanche (SMHasher-style; skipped for seedless algorithms) and structured/sparse-key distinctness (all-zero lengths, single-bit keys, cyclic patterns).
• Added canonical, constexpr-safe mbo::hash::xxh3::GetHash128 (XXH3_128bits[_withSeed], the modern fast file-checksum format), verified against reference vectors and differentially against libxxhash; xxh3::Algorithm is now 128-bit native.
• Added canonical, constexpr-safe mbo::hash::rapidhash::GetHash64 (rapidhash V3, wyhash family - best small-key latency) and mbo::hash::siphash::GetHash64 / SipHash<C, D> (SipHash-2-4/-1-3, the keyed hash-flooding-resistant PRF), both verified against reference vectors.
• Added a differential test comparing the xxh64/xxh3 implementations bit-for-bit against the actual reference library (test-only xxhash archive) over randomized inputs, seeds, and lengths.
• Added mbo::hash::Hash64To32(uint64_t): XOR-fold shrink to 32 bits (all 64 bits contribute; the official FNV shrinking recommendation, safe for every algorithm).
• Added mbo::hash::GetHash32<Algo>(data, seed) and Hasher<Algo>::GetHash32 with the HasGetHash32 concept: algorithms may provide a native 32-bit variant; otherwise the XOR-fold of the 64-bit hash is synthesized.
• Added a mixed-length latency benchmark (BmHash64Latency): unpredictable key sizes with a serialized dependency chain, measuring what hash-table workloads actually pay.
• Added streaming/incremental hashing: the HasStreaming concept and Streamer<Algo> wrapper (Update(...).Finalize(), non-destructive, constexpr-safe), with chunked results guaranteed equal to the one-shot value. Implemented for mumbo, xxh64 (canonical streaming semantics), and siphash; rapidhash has no canonical streaming form and honestly opts out.
• Added a repository-root NOTICE file reproducing the upstream notices of the transcribed algorithms (rapidhash MIT, xxHash BSD-2, MurmurHash3/SipHash/FNV public domain or CC0); README links it.
• Added mumbo, the library's own hash algorithm and the default behind GetHash64/GetHash128/GetHash32/GetHash and streaming: built on the widening 64x64->128 multiply ("MUM" - one multiply absorbs 16 bytes and diffuses full-width both directions), with fully unrolled per-length small-key loads (data in both product operands), a 128-byte 8-chain bulk fetch window, a native dual-lane 128-bit form, and a finalizer that keeps both widening-product halves with the length folded into the product operands (which is also what enables streaming). Secrets are the sqrt fractions of the first 16 primes. SMHasher3: PASS 188/188 in both widths - the only clean native-128 result measured on our rig - plus best-in-class mixed-length latency at <= 16 bytes and bulk throughput (measured design iterations and full tables: mbo/hash/README.md).
• Split the NOTICE-bearing transcriptions into //mbo/hash:hash_extra_cc (mbo/hash/hash_extra.h): rapidhash (MIT) and xxh64/xxh3 (BSD-2-Clause) now require an explicit dependency (and shipping the repository-root NOTICE); the default //mbo/hash:hash_cc contains only notice-free code. All extras remain fully supported IsHashAlgorithm plug-ins.
• Hash values are not guaranteed stable across library versions and are not intended for persistence or cryptographic use.
• Added the mbo/digest library (charter: mbo/digest/README.md): spec-transcribed, constexpr-safe message digests with identical compile-time and runtime values (static_assert-proven). Algorithms: SHA-224/256/384/512, SHA-512/224, SHA-512/256 (FIPS 180-4; the SHA-512/t IVs rederived programmatically per the spec), SHA3-224/256/384/512 and the SHAKE128/256 XOFs (FIPS 202; Digest<N> for any output length; different lengths share their prefix), BLAKE2b/blake2b_256 (RFC 7693, incl. native keying via DigestKeyed/StreamInitKeyed - BLAKE2 is its own MAC), BLAKE3 with the full Merkle-tree structure (plain/DigestXof<N>, keyed, and DeriveKey KDF modes; pinned against the official test-vector suite, all 35 lengths x 3 modes), and SHA-1 + MD5 for legacy interop (both loudly marked collision-broken). Every value pinned against independently generated reference vectors (FIPS/RFC examples, per-algorithm padding boundaries, million-byte inputs).
• The digest API mirrors mbo/hash's plug-in architecture: per-algorithm Algorithm structs with the IsDigestAlgorithm/HasStreaming concepts, the incremental mbo::digest::Streamer (peekable finalize), Hmac<Algo>/HmacStreamer (RFC 2104, generic over any streaming digest incl. HMAC-SHA3 with rate-sized blocks), and ToHexString. Digests take no seed - keying is native (BLAKE2b/BLAKE3) or HMAC's job.
• Added the digest binary (//mbo/digest:digest): checksum-style <hash> <file> lines (sha256sum/shasum format, byte-compatible; --reverse swaps the columns), -a/--algorithm selects any of the 17 library algorithms (default sha256), - reads stdin, directories are errors (-d/--ignore_directories skips them silently); streaming chunked reads (no whole-file buffering). Tested by a bashtest matrix diffing every algorithm's output against independently generated expected files.
• Added --check (short: -c) to the digest binary: verifies checksum files (OK / FAILED per listed file, coreutils-style warnings and exit codes; accepts * binary markers and uppercase hex, so sum files are interchangeable with sha256sum/shasum in both directions), with the companions --quiet, --status, --ignore_missing, and --strict.
• Added the bazel verify_digest_test rule (//mbo/digest:digest.bzl): given an algorithm and files mapped to a saved digest - either digests (a checksum sidecar file) or checksums (an inline hex digest in the BUILD file) - it re-digests each file with //mbo/digest:digest --check, so a file may only change when its saved digest is updated in the same commit and nothing drifts unnoticed. The digests sidecar form is preferred: the sidecar stays an independent, externally verifiable artifact anyone can re-check with stock sha256sum -c, no Bazel required. It pins mbo/hash/hash_test_vectors.inc (the generated known-answer vectors) alongside a diff_test that fails if that file is stale versus its generator.
• Factored the shared load primitives into the new //mbo/hash:hash_internal_util target (used by mbo/digest) and added the big-endian hash_internal::Load32BE/Load64BE loads (digest specifications are big-endian) with the same memcpy-based runtime path as the little-endian loads.

For Bazel MODULES.bazel

bazel_dep(name = "helly25_mbo", version = "0.13.0")

Using the provided LLVM

Copy llvm.MODULE.bazel to your repository's root directory and add the following line to your MODULES.bazel file or paste the whole contents into it.

include("//:llvm.MODULE.bazel")

Using the provided development modules

Copy dev.MODULE.bazel to your repository's root directory and add the following line to your MODULES.bazel file or paste the whole contents into it. It provides the dev-only Hedron compile-commands extractor (generates compile_commands.json for clangd) and depend_on_what_you_use.

include("//:dev.MODULE.bazel")

What's Changed

• Bump version from 0.12.0 to 0.12.1 by @helly25 in #205
• ci: grant release dispatcher pull-requests: write by @helly25 in #206
• ci: let pre-commit own git hooks (disable trunk hook actions) by @helly25 in #207
• feat(hash): faster constexpr hash (mbo::hash::mh) + hardening & tests by @helly25 in #208
• feat(hash): add canonical FNV-1a, XXH64, and MurmurHash3 implementations by @helly25 in #209
• ci: run the hash benchmark per-OS as an informational job by @helly25 in #210
• perf(hash): memcpy loads, overlap tails, 4-lane stripes for mh by @helly25 in #211
• docs: list all public mbo::hash functions and types in README by @helly25 in #212
• feat(hash): algorithm structs, concepts, and the Hasher interface generator by @helly25 in #213
• feat(hash): decorrelate the synthesized GetHash128 fallback lanes by @helly25 in #214
• feat(hash): XXH3-64, container functor adapters, CombineHashes, TODO roadmap by @helly25 in #215
• feat(diff): context/normal output formats, Myers algorithm as new default by @helly25 in #216
• feat(hash): seed-avalanche + structured-key tests; fix sparse-key collisions in mh by @helly25 in #217
• perf(diff): zero-copy interning in the Myers tokenizer by @helly25 in #218
• perf(diff): view-based LineCache::processed, no per-line copies by @helly25 in #220
• feat(diff): side-by-side output format (diff -y style) by @helly25 in #223
• feat(hash): SipHash, rapidhash V3, differential test vs libxxhash, latency benchmark by @helly25 in #219
• feat(hash): canonical XXH3-128 (XXH3_128bits) by @helly25 in #221
• feat(hash): streaming/incremental hashing (HasStreaming + Streamer) by @helly25 in #222
• feat(hash): rapidhash is the default; mh seed hardening; NOTICE attributions by @helly25 in #225
• docs(hash): SMHASHER3.md leads with current state; add same-rig comparison table by @helly25 in #226
• Add mbo/digest: constexpr SHA-224/SHA-256 (FIPS 180-4) + hash lint cleanup by @helly25 in #227
• feat(diff): audit batch - --minimal, CLI matrix bashtest, bzl attrs, coverage by @helly25 in #228
• mbo/digest: complete the algorithm set (SHA-512 family, SHA-3, BLAKE2b, HMAC, SHA-1, MD5) by @helly25 in #229
• fix(diff): POSIX exit codes; bzl minimal attr; TODO roadmap by @helly25 in #231
• mbo/digest: BLAKE3 (all modes), SHAKE128/256 XOFs, native BLAKE2b keying by @helly25 in #230
• docs: hash/digest documentation pass (CHANGELOG, README, NOTICE classes) by @helly25 in #232
• mbo/digest: --check mode for the digest CLI by @helly25 in #233
• diff: EOL/header normalization - empty time_format (git-style header), ignore_missing_final_newline by @helly25 in #234
• mbo/hash: mumbo/jumbo - in-house MUM hash family takes the defaults; hash_extra_cc split; full same-rig data by @helly25 in #235
• mbo/hash: cross-platform CI performance tables by @helly25 in #236
• docs(hash): release-audit tidy-up by @helly25 in #237
• mbo/hash: flag-driven build-seed mangle - hash_mangle_cc split, module-version rotation by @helly25 in #238
• mbo/hash: small-key perf - boundary benchmark data + if-ladder LoadSmall by @helly25 in #239
• mbo/hash: SMHasher3 in-house plugin + verified quality (mumbo/jumbo PASS 188/188) by @helly25 in #240
• mbo/hash: redesign dumbo-64 into a compact single-lane MUM hash (40 -> 188/188, 2-3x faster) by @helly25 in #241
• mbo/hash/measurements: one-shot authoritative runner + parallel SMHasher batteries by @helly25 in #242
• mbo/hash: authoritative perf dataset + log-log throughput charts by @helly25 in #243
• mbo/hash: known-answer tests + SMHasher3 include-order fix; verify_digest_test bzl rule by @helly25 in #244
• mbo/hash: per-machine LFS measurement bundles + verifiable charts; complete benchmark sizes by @helly25 in #245
• mbo/hash/measurements: tag build compiler into bundle name + provenance; drop placeholder bundle by @helly25 in #246
• mbo/hash: measurements --config pass-through + bump hermetic LLVM/clang to 22.1.8 by @helly25 in #247
• mbo/hash/measurements: README-table sizes from the data (single source of truth) by @helly25 in #249
• mbo/hash/measurements: decouple measure/publish; labeled multi-machine README from data bundles by @helly25 in #250
• mbo/hash: authoritative M5 Pro + Zen5 measurements; published multi-machine README by @helly25 in #251

Full Changelog: 0.12.0...0.13.0