Technique:Non-cryptographic hashes in file formats
| On this wiki | Facts · Code · Notes · Topics |
|---|
Adler-32, Fletcher-16/32, the Internet checksum, FNV-1/1a, MurmurHash3, xxHash (XXH32, XXH64, XXH3), CityHash and Jenkins one-at-a-time as they appear in file formats, name hashes and archives: constants, algorithm shape and test vectors to recognise them in a binary.
Overview
Besides CRCs (Technique:CRC variants and parameters), file formats and engines use cheap checksums for integrity and cheap hashes for names (a file path in an archive index is stored as a 32 or 64-bit hash, not a string). Recognising which one lets you compute the hash of a candidate name and match it against the table. For cryptographic hashes see Technique:Identifying cryptographic constants.
Checksums
- Adler-32 (RFC 1950, Library:Zlib): two 16-bit sums A (starts at 1) and B (starts at 0), modulo 65521 (0xFFF1, largest prime below 65536); result is B << 16 | A, stored big endian in the zlib trailer. Code loops with NMAX 5552 bytes before taking the modulus. Test:
Wikipediagives 0x11E60398,123456789gives 0x091E01DE, empty input gives 1. - Fletcher-16: A and B modulo 255 (A += byte, B += A), result B << 8 | A. Fletcher-32 sums 16-bit words modulo 65535, result B << 16 | A. Test:
abcdegives Fletcher-16 0xC8F0 and Fletcher-32 0xF04FC729 (little-endian words, zero padded);123456789gives 0x1EDE and 0xDF09D509. Variants differ in word size, endianness and padding. Unverified: these vectors come from the definition and an independent implementation, not from a format's source. - Internet checksum (RFC 1071; IPv4 header, ICMP, UDP, TCP): ones-complement sum of 16-bit big-endian words, carries folded back, then inverted; odd lengths are padded with a zero byte. Verification: summing the data including the checksum gives 0xFFFF. Test: ASCII
123456789gives 0xF62A. Trivial to patch by adjusting any word.
Hashes used for names and tables
- FNV-1 and FNV-1a: 32-bit offset basis 0x811C9DC5, prime 0x01000193; 64-bit offset basis 0xCBF29CE484222325, prime 0x100000001B3. FNV-1 multiplies then XORs the byte, FNV-1a XORs then multiplies. Test FNV-1a 32 of
a: 0xE40C292C; FNV-1 32 ofa: 0x050C5D7E; FNV-1a 64 ofa: 0xAF63DC4C8601EC8C. Empty input gives the offset basis. SMHasher's "FNV" test is FNV-1a 32 with the seed XORed into the basis. - Jenkins one-at-a-time: per byte
h += b; h += h << 10; h ^= h >> 6, thenh += h << 3; h ^= h >> 11; h += h << 15; initial 0. Test:agives 0xCA2E9442,The quick brown fox jumps over the lazy doggives 0x519E91F5. Shift constants 10, 6, 3, 11, 15 are the recognisable shape. lookup3 (hashlittle) seeds with 0xDEADBEEF + length + initval. - MurmurHash3 (Library:MurmurHash): x86_32 constants c1 0xCC9E2D51, c2 0x1B873593, rotations 15 and 13,
h = h*5 + 0xE6546B64, finaliser fmix32 with 0x85EBCA6B and 0xC2B2AE35 (shifts 16, 13, 16). x64_128 uses 0x87C37B91114253D5 and 0x4CF5AD432745937F. Test x86_32: empty seed 0 gives 0; empty seed 1 gives 0x514E28B7;testseed 0 gives 0xBA6BD213;Hello, world!seed 0x9747B28C gives 0x24884CBA. - xxHash (Library:xxHash): XXH32 primes 0x9E3779B1, 0x85EBCA77, 0xC2B2AE3D, 0x27D4EB2F, 0x165667B1; XXH64 primes 0x9E3779B185EBCA87, 0xC2B2AE3D27D4EB4F, 0x165667B19E3779F9, 0x85EBCA77C2B2AE63, 0x27D4EB2F165667C5. XXH32 of empty input seed 0 is 0x02CC5D05, XXH64 of empty input is 0xEF46DB3751D8E999. XXH3 uses a 192-byte secret starting
B8 FE 6C 39 23 A4 4B BE. - CityHash (Google): 64-bit constants k0 0xC3A5C85C97CB3127, k1 0xB492B66FBE98F273, k2 0x9AE16A3B2F90404F, k3 0xC949D7C7509E6557 (as in the copy in SMHasher).
Recognising them in a binary
Hashes show up as immediates in code (imul reg, 0x01000193, 0x9E3779B1) rather than tables; search for the constant in both byte orders, then check seeds and the final mixing. Common 32-bit name hashes in game archives are FNV-1a, CRC-32 of lowercased path, and Jenkins hash; try each on a known name from the executable's strings and compare with the index.
Code & repositories
- https://github.com/Cyan4973/xxHash @
680bf463fa1ca0461b9a7c2dab7556e1f54cf4cf· license: BSD-2-Clause (declared by the contributor for the files used; GitHub reports BSD-2-Clause (read from LICENSE; GitHub's detector did not classify it) for the repository)
xxHash reference implementation and sanity test vectors (library BSD-2-Clause).
Tested on: source read, not run: files read: xxhash.h, tests/sanity_test_vectors.h · checked 2026-10-18; last activity 2026-10-13; Note: the latest release ships binaries; the wiki links only the source, never the binaries - https://github.com/aappleby/smhasher @
07bb4de10a63e8cc2e1724865454eba635742383· license: MIT (declared by the contributor; GitHub's detector did not recognize a license file)
MurmurHash reference code and the SMHasher hash test suite with verification codes (MIT, Murmur public domain).
Tested on: source read, not run: files read: src/MurmurHash3.cpp, src/Hashes.cpp, src/City.cpp, src/main.cpp · checked 2026-10-18; last activity 2026-06-25