include/linux/xxhash.h

   1 /*
   2  * xxHash - Extremely Fast Hash algorithm
   3  * Copyright (C) 2012-2016, Yann Collet.
   4  *
   5  * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions are
   9  * met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following disclaimer
  15  *     in the documentation and/or other materials provided with the
  16  *     distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * This program is free software; you can redistribute it and/or modify it under
  31  * the terms of the GNU General Public License version 2 as published by the
  32  * Free Software Foundation. This program is dual-licensed; you may select
  33  * either version 2 of the GNU General Public License ("GPL") or BSD license
  34  * ("BSD").
  35  *
  36  * You can contact the author at:
  37  * - xxHash homepage: http://cyan4973.github.io/xxHash/
  38  * - xxHash source repository: https://github.com/Cyan4973/xxHash
  39  */
  40
  41 /*
  42  * Notice extracted from xxHash homepage:
  43  *
  44  * xxHash is an extremely fast Hash algorithm, running at RAM speed limits.
  45  * It also successfully passes all tests from the SMHasher suite.
  46  *
  47  * Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2
  48  * Duo @3GHz)
  49  *
  50  * Name            Speed       Q.Score   Author
  51  * xxHash          5.4 GB/s     10
  52  * CrapWow         3.2 GB/s      2       Andrew
  53  * MumurHash 3a    2.7 GB/s     10       Austin Appleby
  54  * SpookyHash      2.0 GB/s     10       Bob Jenkins
  55  * SBox            1.4 GB/s      9       Bret Mulvey
  56  * Lookup3         1.2 GB/s      9       Bob Jenkins
  57  * SuperFastHash   1.2 GB/s      1       Paul Hsieh
  58  * CityHash64      1.05 GB/s    10       Pike & Alakuijala
  59  * FNV             0.55 GB/s     5       Fowler, Noll, Vo
  60  * CRC32           0.43 GB/s     9
  61  * MD5-32          0.33 GB/s    10       Ronald L. Rivest
  62  * SHA1-32         0.28 GB/s    10
  63  *
  64  * Q.Score is a measure of quality of the hash function.
  65  * It depends on successfully passing SMHasher test set.
  66  * 10 is a perfect score.
  67  *
  68  * A 64-bits version, named xxh64 offers much better speed,
  69  * but for 64-bits applications only.
  70  * Name     Speed on 64 bits    Speed on 32 bits
  71  * xxh64       13.8 GB/s            1.9 GB/s
  72  * xxh32        6.8 GB/s            6.0 GB/s
  73  */
  74
  75 #ifndef XXHASH_H
  76 #define XXHASH_H
  77
  78 #include <linux/types.h>
  79
  80 /*-****************************
  81  * Simple Hash Functions
  82  *****************************/
  83
  84 /**
  85  * xxh32() - calculate the 32-bit hash of the input with a given seed.
  86  *
  87  * @input:  The data to hash.
  88  * @length: The length of the data to hash.
  89  * @seed:   The seed can be used to alter the result predictably.
  90  *
  91  * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s
  92  *
  93  * Return:  The 32-bit hash of the data.
  94  */
  95 uint32_t xxh32(const void *input, size_t length, uint32_t seed);
  96
  97 /**
  98  * xxh64() - calculate the 64-bit hash of the input with a given seed.
  99  *
 100  * @input:  The data to hash.
 101  * @length: The length of the data to hash.
 102  * @seed:   The seed can be used to alter the result predictably.
 103  *
 104  * This function runs 2x faster on 64-bit systems, but slower on 32-bit systems.
 105  *
 106  * Return:  The 64-bit hash of the data.
 107  */
 108 uint64_t xxh64(const void *input, size_t length, uint64_t seed);
 109
 110 /**
 111  * xxhash() - calculate wordsize hash of the input with a given seed
 112  * @input:  The data to hash.
 113  * @length: The length of the data to hash.
 114  * @seed:   The seed can be used to alter the result predictably.
 115  *
 116  * If the hash does not need to be comparable between machines with
 117  * different word sizes, this function will call whichever of xxh32()
 118  * or xxh64() is faster.
 119  *
 120  * Return:  wordsize hash of the data.
 121  */
 122
 123 static inline unsigned long xxhash(const void *input, size_t length,
 124                                    uint64_t seed)
 125 {
 126 #if BITS_PER_LONG == 64
 127        return xxh64(input, length, seed);
 128 #else
 129        return xxh32(input, length, seed);
 130 #endif
 131 }
 132
 133 /*-****************************
 134  * Streaming Hash Functions
 135  *****************************/
 136
 137 /*
 138  * These definitions are only meant to allow allocation of XXH state
 139  * statically, on stack, or in a struct for example.
 140  * Do not use members directly.
 141  */
 142
 143 /**
 144  * struct xxh32_state - private xxh32 state, do not use members directly
 145  */
 146 struct xxh32_state {
 147         uint32_t total_len_32;
 148         uint32_t large_len;
 149         uint32_t v1;
 150         uint32_t v2;
 151         uint32_t v3;
 152         uint32_t v4;
 153         uint32_t mem32[4];
 154         uint32_t memsize;
 155 };
 156
 157 /**
 158  * struct xxh32_state - private xxh64 state, do not use members directly
 159  */
 160 struct xxh64_state {
 161         uint64_t total_len;
 162         uint64_t v1;
 163         uint64_t v2;
 164         uint64_t v3;
 165         uint64_t v4;
 166         uint64_t mem64[4];
 167         uint32_t memsize;
 168 };
 169
 170 /**
 171  * xxh32_reset() - reset the xxh32 state to start a new hashing operation
 172  *
 173  * @state: The xxh32 state to reset.
 174  * @seed:  Initialize the hash state with this seed.
 175  *
 176  * Call this function on any xxh32_state to prepare for a new hashing operation.
 177  */
 178 void xxh32_reset(struct xxh32_state *state, uint32_t seed);
 179
 180 /**
 181  * xxh32_update() - hash the data given and update the xxh32 state
 182  *
 183  * @state:  The xxh32 state to update.
 184  * @input:  The data to hash.
 185  * @length: The length of the data to hash.
 186  *
 187  * After calling xxh32_reset() call xxh32_update() as many times as necessary.
 188  *
 189  * Return:  Zero on success, otherwise an error code.
 190  */
 191 int xxh32_update(struct xxh32_state *state, const void *input, size_t length);
 192
 193 /**
 194  * xxh32_digest() - produce the current xxh32 hash
 195  *
 196  * @state: Produce the current xxh32 hash of this state.
 197  *
 198  * A hash value can be produced at any time. It is still possible to continue
 199  * inserting input into the hash state after a call to xxh32_digest(), and
 200  * generate new hashes later on, by calling xxh32_digest() again.
 201  *
 202  * Return: The xxh32 hash stored in the state.
 203  */
 204 uint32_t xxh32_digest(const struct xxh32_state *state);
 205
 206 /**
 207  * xxh64_reset() - reset the xxh64 state to start a new hashing operation
 208  *
 209  * @state: The xxh64 state to reset.
 210  * @seed:  Initialize the hash state with this seed.
 211  */
 212 void xxh64_reset(struct xxh64_state *state, uint64_t seed);
 213
 214 /**
 215  * xxh64_update() - hash the data given and update the xxh64 state
 216  * @state:  The xxh64 state to update.
 217  * @input:  The data to hash.
 218  * @length: The length of the data to hash.
 219  *
 220  * After calling xxh64_reset() call xxh64_update() as many times as necessary.
 221  *
 222  * Return:  Zero on success, otherwise an error code.
 223  */
 224 int xxh64_update(struct xxh64_state *state, const void *input, size_t length);
 225
 226 /**
 227  * xxh64_digest() - produce the current xxh64 hash
 228  *
 229  * @state: Produce the current xxh64 hash of this state.
 230  *
 231  * A hash value can be produced at any time. It is still possible to continue
 232  * inserting input into the hash state after a call to xxh64_digest(), and
 233  * generate new hashes later on, by calling xxh64_digest() again.
 234  *
 235  * Return: The xxh64 hash stored in the state.
 236  */
 237 uint64_t xxh64_digest(const struct xxh64_state *state);
 238
 239 /*-**************************
 240  * Utils
 241  ***************************/
 242
 243 /**
 244  * xxh32_copy_state() - copy the source state into the destination state
 245  *
 246  * @src: The source xxh32 state.
 247  * @dst: The destination xxh32 state.
 248  */
 249 void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src);
 250
 251 /**
 252  * xxh64_copy_state() - copy the source state into the destination state
 253  *
 254  * @src: The source xxh64 state.
 255  * @dst: The destination xxh64 state.
 256  */
 257 void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src);
 258
 259 #endif /* XXHASH_H */