DOCSEARCHbyAlgolia
Submit Docs

xxHash

repository·dev·Indexed 11 days ago

https://github.com/cyan4973/xxhash

An extremely fast, portable non-cryptographic hash algorithm designed to operate at RAM speed limits. It provides multiple variants including XXH32, XXH64, and XXH3/XXH128. The library includes a one-shot API for buffers and a streaming API for incremental hashing, along with the xxhsum command-line utility for computing and verifying checksums.

Tokens
5.9K
Snippets
18
Records
28
Agent score
89%

What's inside xxHash

  1. Overview of xxHash algorithms

    dev

    xxHash is an extremely fast hash algorithm that processes data at RAM speed limits. It is highly portable and produces identical hashes across all platforms (little and big endian). The library provides several variants depending on your requirements for hash width and speed:

    • XXH32: Generates 32-bit hashes using 32-bit arithmetic.
    • XXH64: Generates 64-bit hashes using 64-bit arithmetic.
    • XXH3: Generates 64-bit or 128-bit hashes (the 128-bit variant is called XXH128) using vectorized arithmetic. This is the most modern and fastest variant for large data.

  2. Overview of xxHash digest algorithms

    dev

    xxHash is a non-cryptographic, extremely fast hash algorithm designed to produce a unique 'fingerprint' or digest for messages of arbitrary length. It supports several variants optimized for different architectures and output requirements:

    • XXH32: Optimized for 32-bit machines; produces a 32-bit digest.
    • XXH64: Optimized for 64-bit machines; produces a 64-bit digest.
    • XXH3: A modern, high-performance variant that comes in two versions: XXH3-64 (64-bit output) and XXH3-128 (128-bit output).

    Important Security Note: xxHash is non-cryptographic. It is not designed to resist intentional collisions or to prevent the creation of messages with predefined digests.

  3. Understand the xxHash algorithm specification

    dev

    The xxHash algorithm is defined in a formal specification document. For a deep dive into the mathematical and logical implementation of the hash algorithm, refer to the xxhash_spec.md file within the repository.

    If you are looking to understand the algorithm's logic through a readable implementation rather than the high-performance reference implementation, you can consult the xxhash-clean educational library by @easyaspi314, which is designed for readability.

  4. Use the xxhsum command line utility

    dev

    The xxhsum command line utility is a user program provided by libxxhash. It allows you to compute xxHash checksums directly from the terminal.

    Note on Licensing: While libxxhash is typically distributed under a permissive license, the xxhsum command line utility is licensed under GPLv2.

  5. How XXH32 works

    dev

    XXH32 is a 32-bit hash algorithm designed for speed on 32-bit architectures.

    Core Mechanics:

    • Parallelism: It processes input in 16-byte stripes, updating 4 independent 32-bit accumulators in parallel to leverage multiple CPU execution units.
    • Stripes and Lanes: Each 16-byte stripe is divided into 4 lanes (4 bytes each). Each lane updates one accumulator using a specific round of modular addition, multiplication, and rotation.
    • Small Inputs: For inputs < 16 bytes, it bypasses parallel accumulators and uses a single accumulator initialized with seed + PRIME32_5.
    • Convergence and Mixing: After processing stripes, the 4 accumulators are merged (converged) into one, the input length is added, any remaining bytes (< 16) are digested, and a final 'avalanche' step is applied to ensure bit distribution.
    // XXH32 Prime Constants
static const u32 PRIME32_1 = 0x9E3779B1U;
static const u32 PRIME32_2 = 0x85EBCA77U;
static const u32 PRIME32_3 = 0xC2B2AE3DU;
static const u32 PRIME32_4 = 0x27D4EB2FU;
static const u32 PRIME32_5 = 0x165667B1U;

  6. How XXH3 works (Small, Medium, and Large inputs)

    dev

    XXH3 is a high-performance variant that adapts its algorithm based on the input size to maximize throughput.

    Input Size Strategies

    • Small (0-16 bytes): Uses specialized logic for empty, 1-3, 4-8, and 9-16 byte inputs, heavily utilizing byte-swap operations.
    • Medium (17-240 bytes): Uses 1 or 2 64-bit accumulators. It processes input using a mixStep operation that combines 16-byte data segments with segments of a secret and the seed.
    • Large (241+ bytes): Uses 8 64-bit accumulators. It processes data in large blocks (default 1024 bytes). Each block involves a round_accumulate step (using stripes and the secret) followed by a round_scramble step (using the last 64 bytes of the secret).

    Seed and Secret

    XXH3 supports seeded hashing via a seed (64-bit) and a secret (at least 136 bytes).

    • You can use *_withSeed or *_withSecret functions.
    • For large inputs (> 240 bytes), providing a seed automatically derives a new secret from the default secret using a specific derivation procedure.
    • Note: You cannot specify both a custom seed and a custom secret simultaneously in the same call; one will default if the other is provided.

  7. How XXH64 works

    dev

    XXH64 is a 64-bit hash algorithm optimized for 64-bit architectures. It follows a structure similar to XXH32 but uses 64-bit arithmetic and larger data chunks.

    Core Mechanics:

    • Parallelism: It processes input in 32-byte stripes, updating 4 independent 64-bit accumulators in parallel.
    • Stripes and Lanes: Each 32-byte stripe is divided into 4 lanes (8 bytes each). Each lane updates one accumulator using 64-bit modular operations.
    • Small Inputs: For inputs < 32 bytes, it uses a single accumulator initialized with seed + PRIME64_5.
    • Convergence: The 4 accumulators are merged using a complex mergeAccumulator function involving multiple rounds of XOR and multiplication before the final avalanche step.
    // XXH64 Prime Constants
static const u64 PRIME64_1 = 0x9E3779B185EBCA87ULL;
static const u64 PRIME64_2 = 0xC2B2AE3D27D4EB4FULL;
static const u64 PRIME64_3 = 0x165667B19E3779F9ULL;
static const u64 PRIME64_4 = 0x85EBCA77C2B2AE63ULL;
static const u64 PRIME64_5 = 0x27D4EB2F165667C5ULL;

  8. Generate hashes from a list of files

    dev

    Instead of passing filenames as arguments, you can use --files-from or --filelist to read filenames from a file or standard input. This is useful for handling large numbers of files or files with complex names.

    Format requirements:

    • One filename per line.
    • Supports embedded spaces without quotes or escapes.
    • A line starting with \ enables a special encoding convention where \\, \n, and \r are converted to 0x5C, 0x0A, and 0x0D respectively.
    # Generate hashes from a text file containing filenames
xxhsum --files-from c-files.txt

# Generate hashes from a list piped from another command
find . -type f -name '*.[ch]' | xxhsum --files-from -

  9. Performance considerations for choosing a variant

    dev

    When choosing an xxHash variant, consider your target architecture and performance requirements:

    • 64-bit Systems: XXH64 is generally faster than XXH32. If you only need a 32-bit hash, it is often still recommended to use XXH64 for better performance.
    • 32-bit Systems: XXH32 is the faster variant. XXH64 performance is reduced due to the overhead of 64-bit arithmetic.
    • Vectorization: If your hardware supports vector operations (SIMD), XXH3 is likely to be the fastest variant available.

  10. Install xxHash using vcpkg

    dev

    You can install xxHash using the vcpkg dependency manager by following these steps:

    git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install xxhash

  11. Use xxhsum to print checksums

    dev

    The xxhsum CLI tool prints xxHash non-cryptographic checksums for files or standard input. By default, it uses XXH64. You can specify different hash types using the -H flag. If no files are provided, it reads from standard input (unless it is a console). To read from standard input even when it is a console, use - as the filename.

    # Output XXH64 checksums for specific files
xxhsum -H1 foo bar baz

# Output XXH32 checksums and redirect to a file
xxhsum -H0 foo bar baz > xyz.xxh32

  12. Use the xxhsum CLI tool

    dev

    The xxhsum command-line tool provides a way to calculate xxHash checksums for files, lists of files, or data from stdin. It supports multiple algorithms including XXH32, XXH64, XXH128, and XXH3. By default, the tool displays hash values in Big Endian format.

    Common use cases include:

    • Generating checksums for a single file.
    • Generating checksums for multiple files.
    • Piping data into the tool via stdin to calculate its hash.
    • Verifying existing checksum files (checksum mode).
    # Example: Hash a file (default XXH64)
xxhsum filename.txt

# Example: Hash from stdin
cat filename.txt | xxhsum