"Fossies" - the Fresh Open Source Software Archive

Member "xxHash-0.8.0/README.md" (27 Jul 2020, 11920 Bytes) of package /linux/misc/xxHash-0.8.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format (assuming markdown format). Alternatively you can here view or download the uninterpreted source code file. A member file download can also be achieved by clicking within a package contents listing on the according byte size field. See also the last Fossies "Diffs" side-by-side code changes report for "README.md": 0.7.3_vs_0.7.4.

xxHash - Extremely fast hash algorithm

xxHash is an Extremely fast Hash algorithm, running at RAM speed limits. It successfully completes the SMHasher test suite which evaluates collision, dispersion and randomness qualities of hash functions. Code is highly portable, and hashes are identical on all platforms (little / big endian).

Branch Status
master Build Status
dev Build Status

Benchmarks

The benchmark uses SMHasher speed test, compiled with Visual 2010 on a Windows Seven 32-bit box. The reference system uses a Core 2 Duo @3GHz

Name Speed Quality Author
xxHash 5.4 GB/s 10 Y.C.
MurmurHash 3a 2.7 GB/s 10 Austin Appleby
SBox 1.4 GB/s 9 Bret Mulvey
Lookup3 1.2 GB/s 9 Bob Jenkins
CityHash64 1.05 GB/s 10 Pike & Alakuijala
FNV 0.55 GB/s 5 Fowler, Noll, Vo
CRC32 0.43 GB/s † 9
MD5-32 0.33 GB/s 10 Ronald L.Rivest
SHA1-32 0.28 GB/s 10

Note †: SMHasher's CRC32 implementation is known to be slow. Faster implementations exist.

Q.Score is a measure of quality of the hash function. It depends on successfully passing SMHasher test set. 10 is a perfect score. Algorithms with a score < 5 are not listed on this table.

A more recent version, XXH64, has been created thanks to Mathias Westerdahl, which offers superior speed and dispersion for 64-bit systems. Note however that 32-bit applications will still run faster using the 32-bit version.

SMHasher speed test, compiled using GCC 4.8.2, on Linux Mint 64-bit. The reference system uses a Core i5-3340M @2.7GHz

Version Speed on 64-bit Speed on 32-bit
XXH64 13.8 GB/s 1.9 GB/s
XXH32 6.8 GB/s 6.0 GB/s

This project also includes a command line utility, named xxhsum, offering similar features to md5sum, thanks to Takayuki Matsuoka's contributions.

License

The library files xxhash.c and xxhash.h are BSD licensed. The utility xxhsum is GPL licensed.

New hash algorithms

Starting with v0.7.0, the library includes a new algorithm named XXH3, which is able to generate 64 and 128-bit hashes.

The new algorithm is much faster than its predecessors for both long and small inputs, which can be observed in the following graphs:

XXH3, bargraph

XXH3, latency, random size

To access these new prototypes, one needs to unlock their declaration, using the build macro XXH_STATIC_LINKING_ONLY.

The algorithm is currently in development, meaning its return values might still change in future versions. However, the API is stable, and can be used in production, typically for generation of ephemeral hashes (produced and consumed in same session).

XXH3 has now reached "release candidate" status. If everything remains fine, its format will be "frozen" and become final. After which, return values of XXH3 and XXH128 will no longer change in future versions. XXH3's return values will be officially finalized upon reaching v0.8.0.

Build modifiers

The following macros can be set at compilation time to modify libxxhash's behavior. They are generally disabled by default.

For the Command Line Interface xxhsum, the following environment variables can also be set :

Building xxHash - Using vcpkg

You can download and install xxHash using the vcpkg dependency manager:

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

The xxHash port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or pull request on the vcpkg repository.

Example

Calling xxhash 64-bit variant from a C program:

#include "xxhash.h"

    (...)
    XXH64_hash_t hash = XXH64(buffer, size, seed);
}

Using streaming variant is more involved, but makes it possible to provide data incrementally:

#include "stdlib.h"   /* abort() */
#include "xxhash.h"


XXH64_hash_t calcul_hash_streaming(FileHandler fh)
{
    /* create a hash state */
    XXH64_state_t* const state = XXH64_createState();
    if (state==NULL) abort();

    size_t const bufferSize = SOME_SIZE;
    void* const buffer = malloc(bufferSize);
    if (buffer==NULL) abort();

    /* Initialize state with selected seed */
    XXH64_hash_t const seed = 0;   /* or any other value */
    if (XXH64_reset(state, seed) == XXH_ERROR) abort();

    /* Feed the state with input data, any size, any number of times */
    (...)
    while ( /* any condition */ ) {
        size_t const length = get_more_data(buffer, bufferSize, fh);
        if (XXH64_update(state, buffer, length) == XXH_ERROR) abort();
        (...)
    }
    (...)

    /* Get the hash */
    XXH64_hash_t const hash = XXH64_digest(state);

    /* State can be re-used; in this example, it is simply freed  */
    free(buffer);
    XXH64_freeState(state);

    return hash;
}

Other programming languages

Aside from the C reference version, xxHash is also available in many different programming languages, thanks to many great contributors. They are listed here.

Branch Policy