Hashing and checksums

Use std/hash.fnv1a64 for a stable fingerprint of trusted bytes and std/checksum.crc32 for accidental-corruption checks. These separate portable imports use only fixed-size state and do not request an allocator or entropy.

A hash condenses input into a fixed-width integer. Different inputs can produce the same integer: this is a collision. A hash map therefore uses both a hash and an equality test. A checksum helps detect accidental changes in bytes; it does not prove who created them. Match the algorithm to that purpose before copying a hash into a file format or using it as an identifier.

Quickstart

Save this as hash_start.dodo:

package hash_start
import "std/hash"
import "std/checksum"

fn main() -> i32 {
    assert_eq(hash.fnv1a64(b"hello"), 0xa430d84680aabd0bu64)
    assert_eq(checksum.crc32(b"123456789"), 0xcbf43926u32)
    return 0
}

dodo run hash_start.dodo

Expected output: none; exit 0 confirms both known results. These one-shot functions cannot fail. A checksum mismatch in an application means you should reject or reacquire the damaged data. Neither checksum nor FNV authenticates it. For hash tables accepting untrusted keys, use SipHash with an unpredictable caller-supplied key; if key acquisition fails, stop that operation. The library has no general OS entropy adapter and a fixed example seed is not a substitute.

API and contracts

std/hash provides allocation-free byte hashing and statically dispatched map policies. std/checksum is an independent import for accidental-corruption checks. Neither package imports collections, allocators, an operating system, or an entropy provider. Both use fixed-size state and O(n) time for n input bytes; there are no large tables or native-layout reads.

Algorithms and stable results

Choose an algorithm

Results are stable across architectures and future releases for the same named algorithm, exact input bytes, and seed/key. An algorithm change requires a new name. Return values are integers; serialize them explicitly with the desired protocol byte order. No algorithm reads padding or a native struct layout. All algorithm arithmetic is explicitly modular where specified, independently of Dodo’s ordinary checked integer arithmetic.

Hash chunks without joining them

All state types expose update(&mut self, &[u8]), finish(&self), and reset(&mut self). finish returns a snapshot without consuming, modifying, or resetting state; repeated calls agree, and further updates continue the original stream. Empty updates have no effect. reset restores the initial seed/key. Fnv1a64.new() uses the standard offset basis; Fnv1a64.seeded(seed) replaces it exactly. The seed does not make FNV secure. The one-shot helpers produce the same result as new, update, finish. SipHash accepts any stream length and encodes the length modulo 256 in its final block as specified by the algorithm.

The following complete example hashes two input chunks as one stream. It also checks that taking a snapshot does not consume the state.

package hash_chunks
import "std/hash"

fn main() -> i32 {
    state := hash.Fnv1a64.new()
    state.update(b"he")
    assert_eq(state.finish(), hash.fnv1a64(b"he"))
    state.update(b"llo")
    assert_eq(state.finish(), hash.fnv1a64(b"hello"))
    state.reset()
    assert_eq(state.finish(), hash.fnv1a64(b""))
    return 0
}

Save as hash_chunks.dodo and run dodo run hash_chunks.dodo; success exits with zero and prints nothing. Chunk boundaries have no effect on the result. The checksum state types work the same way, but return u32 rather than u64.

Keyed hashing and caller-supplied keys

SipHash24.new(k0, k1) and siphash24(data, k0, k1) interpret the two key words as the little-endian encodings of key bytes 0..7 and 8..15. The caller supplies all 128 bits. For maps exposed to untrusted input, obtain an unpredictable key through an application-selected entropy adapter and retain it for the map’s lifetime. Independent map keys can limit the scope of a leaked key. These packages do not acquire entropy, create a process-global key, or silently replace missing entropy with a fixed seed. Fixed keys in examples and tests serve reproducibility only.

Key128.new(k0, k1) holds explicit key words, exposed through word0 and word1. Its hasher, i32_policy, and u64_policy methods construct keyed states/policies. obtain_key(&mut source) invokes the statically dispatched capability source.next_key(&mut self) -> Key128!KeyError exactly once. The source type and its next_key method must be public for dispatch from the hash package. KeyError.Unavailable propagates unchanged: there is no retry, fallback, implicit seed, or entropy access. The application implements the source and is responsible for unpredictable production keys. A source can return a fresh key per request or apply an explicit application key-management policy. Failure may advance source state according to that source’s contract, but never returns a usable key. The library provides no deterministic source as a production default; fixtures/examples define clearly named deterministic test sources.

SipHash is used here as a keyed table hash with a 64-bit output. It is not an unkeyed collision-resistant digest, password hash, general-purpose message authentication API, or encryption algorithm. No cryptographic API is provided; there is no constant-time or key-erasure guarantee. Checksums and FNV provide no protection against an adversary who can choose or alter the bytes.

Statically dispatched contracts and value encodings

Encode composite keys unambiguously

Generic hashing helpers expect H.update(&mut self, data: &[u8]). A complete incremental state additionally supplies finish(&self) -> u64 and reset(&mut self). Calls are monomorphized; there are no traits, closures, reflection, implicit hashing, or vtables.

write_u64(state, value) emits exactly eight little-endian bytes. write_i32(state, value) emits exactly four little-endian two’s-complement bytes, including for negative values. write_bytes(state, data) prefixes a variable-sized field with its length encoded as a little-endian u64, then emits its bytes. This framing distinguishes, for example, the two fields ab,c from a,bc. User-defined records should hash logical fields explicitly, including a discriminant where variants require one; never hash their memory representation. Floating-point keys need an explicit equality policy and matching treatment of signed zero and NaNs; no default floating policy exists.

The important distinction is between a byte stream and a sequence of fields. Updating with b"ab" and then b"c" hashes the same stream as b"a" and then b"bc". Use write_bytes for each field when that boundary is part of the key:

package framed_hash
import "std/hash"

fn main() -> i32 {
    first := hash.Fnv1a64.new()
    hash.write_bytes(&mut first, b"ab")
    hash.write_bytes(&mut first, b"c")
    second := hash.Fnv1a64.new()
    hash.write_bytes(&mut second, b"a")
    hash.write_bytes(&mut second, b"bc")
    assert_ne(first.finish(), second.finish())
    return 0
}

Save as framed_hash.dodo and run dodo run framed_hash.dodo. These particular inputs have different hashes. Framing prevents ambiguous field encodings; it does not eliminate collisions in the finite hash output.

Use policies in collections

Map policies provide hash(&self, key: &K) -> u64 and equal(&self, a: &K, b: &K) -> bool. Equal keys must hash equally; equality must be an equivalence relation. Policy state and key equality/hash behavior must remain stable while keys are stored. I32 {} and U64 {} use FNV and ordinary integer equality. SipI32.new(k0, k1) and SipU64.new(k0, k1) provide the same encodings with SipHash. Colliding unequal keys are allowed and handled by collections.

For UTF-8 keys, hash.Str {} handles &str and hash.Text {} handles text.Text; both compare bytes lexicographically and hash contents with FNV. hash.SipStr.new(k0, k1) supplies caller-keyed hashing for &str keys. text_shared.Key {} provides comparison, equality, and FNV hashing for owned text_shared.String keys. See the string-keyed map example and collection lifetime restrictions.

Hashing a string means hashing its UTF-8 bytes, not its address. These policies do not normalize Unicode or ignore case. Prepare a normalized representation yourself if the application’s equality rules require one, and use that same representation for both equality and hashing. See the API reference for state constructors, policy methods, and key-source declarations.

Attribution and validation

FNV follows Fowler/Noll/Vo’s algorithm and the IETF FNV specification. SipHash follows Jean-Philippe Aumasson and Daniel J. Bernstein’s SipHash specification; the fixture contains all 64 official 64-bit reference vectors, interpreted as little-endian integers. CRC-32 follows RFC 1952, and Adler-32 follows RFC 1950. These are direct Dodo implementations of the algorithms, without C or libc dependencies.

tests/stdlib/hash_checks.dodo checks published vectors, independent Python zlib checksum results, every split position in a 513-byte input, zero-length updates, repeated finalization, reset, seeds, integer/framed encodings, and caller-key-source success/failure without fallback or retries. tests/hash_library.rs runs it at -O0 and -O3 and emits WebAssembly and Cortex-M0 objects. See examples/hash.dodo for a complete program.