include/linux/xxhash.h

   1 /* SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause) */
   2 /*
   3  * xxHash - Extremely Fast Hash algorithm
   4  * Copyright (C) 2012-2016, Yann Collet.
   5  *
   6  * You can contact the author at:
   7  * - xxHash homepage: http://cyan4973.github.io/xxHash/
   8  * - xxHash source repository: https://github.com/Cyan4973/xxHash
   9  */
  10
  11 /*
  12  * Notice extracted from xxHash homepage:
  13  *
  14  * xxHash is an extremely fast Hash algorithm, running at RAM speed limits.
  15  * It also successfully passes all tests from the SMHasher suite.
  16  *
  17  * Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2
  18  * Duo @3GHz)
  19  *
  20  * Name            Speed       Q.Score   Author
  21  * xxHash          5.4 GB/s     10
  22  * CrapWow         3.2 GB/s      2       Andrew
  23  * MumurHash 3a    2.7 GB/s     10       Austin Appleby
  24  * SpookyHash      2.0 GB/s     10       Bob Jenkins
  25  * SBox            1.4 GB/s      9       Bret Mulvey
  26  * Lookup3         1.2 GB/s      9       Bob Jenkins
  27  * SuperFastHash   1.2 GB/s      1       Paul Hsieh
  28  * CityHash64      1.05 GB/s    10       Pike & Alakuijala
  29  * FNV             0.55 GB/s     5       Fowler, Noll, Vo
  30  * CRC32           0.43 GB/s     9
  31  * MD5-32          0.33 GB/s    10       Ronald L. Rivest
  32  * SHA1-32         0.28 GB/s    10
  33  *
  34  * Q.Score is a measure of quality of the hash function.
  35  * It depends on successfully passing SMHasher test set.
  36  * 10 is a perfect score.
  37  *
  38  * A 64-bits version, named xxh64 offers much better speed,
  39  * but for 64-bits applications only.
  40  * Name     Speed on 64 bits    Speed on 32 bits
  41  * xxh64       13.8 GB/s            1.9 GB/s
  42  * xxh32        6.8 GB/s            6.0 GB/s
  43  */
  44
  45 #ifndef XXHASH_H
  46 #define XXHASH_H
  47
  48 #include <linux/types.h>
  49
  50 /*-****************************
  51  * Simple Hash Functions
  52  *****************************/
  53
  54 /**
  55  * xxh32() - calculate the 32-bit hash of the input with a given seed.
  56  *
  57  * @input:  The data to hash.
  58  * @length: The length of the data to hash.
  59  * @seed:   The seed can be used to alter the result predictably.
  60  *
  61  * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s
  62  *
  63  * Return:  The 32-bit hash of the data.
  64  */
  65 uint32_t xxh32(const void *input, size_t length, uint32_t seed);
  66
  67 /**
  68  * xxh64() - calculate the 64-bit hash of the input with a given seed.
  69  *
  70  * @input:  The data to hash.
  71  * @length: The length of the data to hash.
  72  * @seed:   The seed can be used to alter the result predictably.
  73  *
  74  * This function runs 2x faster on 64-bit systems, but slower on 32-bit systems.
  75  *
  76  * Return:  The 64-bit hash of the data.
  77  */
  78 uint64_t xxh64(const void *input, size_t length, uint64_t seed);
  79
  80 /**
  81  * xxhash() - calculate wordsize hash of the input with a given seed
  82  * @input:  The data to hash.
  83  * @length: The length of the data to hash.
  84  * @seed:   The seed can be used to alter the result predictably.
  85  *
  86  * If the hash does not need to be comparable between machines with
  87  * different word sizes, this function will call whichever of xxh32()
  88  * or xxh64() is faster.
  89  *
  90  * Return:  wordsize hash of the data.
  91  */
  92
  93 static inline unsigned long xxhash(const void *input, size_t length,
  94                                    uint64_t seed)
  95 {
  96 #if BITS_PER_LONG == 64
  97        return xxh64(input, length, seed);
  98 #else
  99        return xxh32(input, length, seed);
 100 #endif
 101 }
 102
 103 /*-****************************
 104  * Streaming Hash Functions
 105  *****************************/
 106
 107 /*
 108  * These definitions are only meant to allow allocation of XXH state
 109  * statically, on stack, or in a struct for example.
 110  * Do not use members directly.
 111  */
 112
 113 /**
 114  * struct xxh32_state - private xxh32 state, do not use members directly
 115  */
 116 struct xxh32_state {
 117         uint32_t total_len_32;
 118         uint32_t large_len;
 119         uint32_t v1;
 120         uint32_t v2;
 121         uint32_t v3;
 122         uint32_t v4;
 123         uint32_t mem32[4];
 124         uint32_t memsize;
 125 };
 126
 127 /**
 128  * struct xxh32_state - private xxh64 state, do not use members directly
 129  */
 130 struct xxh64_state {
 131         uint64_t total_len;
 132         uint64_t v1;
 133         uint64_t v2;
 134         uint64_t v3;
 135         uint64_t v4;
 136         uint64_t mem64[4];
 137         uint32_t memsize;
 138 };
 139
 140 /**
 141  * xxh32_reset() - reset the xxh32 state to start a new hashing operation
 142  *
 143  * @state: The xxh32 state to reset.
 144  * @seed:  Initialize the hash state with this seed.
 145  *
 146  * Call this function on any xxh32_state to prepare for a new hashing operation.
 147  */
 148 void xxh32_reset(struct xxh32_state *state, uint32_t seed);
 149
 150 /**
 151  * xxh32_update() - hash the data given and update the xxh32 state
 152  *
 153  * @state:  The xxh32 state to update.
 154  * @input:  The data to hash.
 155  * @length: The length of the data to hash.
 156  *
 157  * After calling xxh32_reset() call xxh32_update() as many times as necessary.
 158  *
 159  * Return:  Zero on success, otherwise an error code.
 160  */
 161 int xxh32_update(struct xxh32_state *state, const void *input, size_t length);
 162
 163 /**
 164  * xxh32_digest() - produce the current xxh32 hash
 165  *
 166  * @state: Produce the current xxh32 hash of this state.
 167  *
 168  * A hash value can be produced at any time. It is still possible to continue
 169  * inserting input into the hash state after a call to xxh32_digest(), and
 170  * generate new hashes later on, by calling xxh32_digest() again.
 171  *
 172  * Return: The xxh32 hash stored in the state.
 173  */
 174 uint32_t xxh32_digest(const struct xxh32_state *state);
 175
 176 /**
 177  * xxh64_reset() - reset the xxh64 state to start a new hashing operation
 178  *
 179  * @state: The xxh64 state to reset.
 180  * @seed:  Initialize the hash state with this seed.
 181  */
 182 void xxh64_reset(struct xxh64_state *state, uint64_t seed);
 183
 184 /**
 185  * xxh64_update() - hash the data given and update the xxh64 state
 186  * @state:  The xxh64 state to update.
 187  * @input:  The data to hash.
 188  * @length: The length of the data to hash.
 189  *
 190  * After calling xxh64_reset() call xxh64_update() as many times as necessary.
 191  *
 192  * Return:  Zero on success, otherwise an error code.
 193  */
 194 int xxh64_update(struct xxh64_state *state, const void *input, size_t length);
 195
 196 /**
 197  * xxh64_digest() - produce the current xxh64 hash
 198  *
 199  * @state: Produce the current xxh64 hash of this state.
 200  *
 201  * A hash value can be produced at any time. It is still possible to continue
 202  * inserting input into the hash state after a call to xxh64_digest(), and
 203  * generate new hashes later on, by calling xxh64_digest() again.
 204  *
 205  * Return: The xxh64 hash stored in the state.
 206  */
 207 uint64_t xxh64_digest(const struct xxh64_state *state);
 208
 209 /*-**************************
 210  * Utils
 211  ***************************/
 212
 213 /**
 214  * xxh32_copy_state() - copy the source state into the destination state
 215  *
 216  * @src: The source xxh32 state.
 217  * @dst: The destination xxh32 state.
 218  */
 219 void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src);
 220
 221 /**
 222  * xxh64_copy_state() - copy the source state into the destination state
 223  *
 224  * @src: The source xxh64 state.
 225  * @dst: The destination xxh64 state.
 226  */
 227 void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src);
 228
 229 #endif /* XXHASH_H */