include/linux/xxhash.h

0001 /*
0002  * xxHash - Extremely Fast Hash algorithm
0003  * Copyright (C) 2012-2016, Yann Collet.
0004  *
0005  * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
0006  *
0007  * Redistribution and use in source and binary forms, with or without
0008  * modification, are permitted provided that the following conditions are
0009  * met:
0010  *
0011  *   * Redistributions of source code must retain the above copyright
0012  *     notice, this list of conditions and the following disclaimer.
0013  *   * Redistributions in binary form must reproduce the above
0014  *     copyright notice, this list of conditions and the following disclaimer
0015  *     in the documentation and/or other materials provided with the
0016  *     distribution.
0017  *
0018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0019  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0020  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
0021  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0022  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0023  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0024  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0028  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0029  *
0030  * This program is free software; you can redistribute it and/or modify it under
0031  * the terms of the GNU General Public License version 2 as published by the
0032  * Free Software Foundation. This program is dual-licensed; you may select
0033  * either version 2 of the GNU General Public License ("GPL") or BSD license
0034  * ("BSD").
0035  *
0036  * You can contact the author at:
0037  * - xxHash homepage: https://cyan4973.github.io/xxHash/
0038  * - xxHash source repository: https://github.com/Cyan4973/xxHash
0039  */
0040
0041 /*
0042  * Notice extracted from xxHash homepage:
0043  *
0044  * xxHash is an extremely fast Hash algorithm, running at RAM speed limits.
0045  * It also successfully passes all tests from the SMHasher suite.
0046  *
0047  * Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2
0048  * Duo @3GHz)
0049  *
0050  * Name            Speed       Q.Score   Author
0051  * xxHash          5.4 GB/s     10
0052  * CrapWow         3.2 GB/s      2       Andrew
0053  * MumurHash 3a    2.7 GB/s     10       Austin Appleby
0054  * SpookyHash      2.0 GB/s     10       Bob Jenkins
0055  * SBox            1.4 GB/s      9       Bret Mulvey
0056  * Lookup3         1.2 GB/s      9       Bob Jenkins
0057  * SuperFastHash   1.2 GB/s      1       Paul Hsieh
0058  * CityHash64      1.05 GB/s    10       Pike & Alakuijala
0059  * FNV             0.55 GB/s     5       Fowler, Noll, Vo
0060  * CRC32           0.43 GB/s     9
0061  * MD5-32          0.33 GB/s    10       Ronald L. Rivest
0062  * SHA1-32         0.28 GB/s    10
0063  *
0064  * Q.Score is a measure of quality of the hash function.
0065  * It depends on successfully passing SMHasher test set.
0066  * 10 is a perfect score.
0067  *
0068  * A 64-bits version, named xxh64 offers much better speed,
0069  * but for 64-bits applications only.
0070  * Name     Speed on 64 bits    Speed on 32 bits
0071  * xxh64       13.8 GB/s            1.9 GB/s
0072  * xxh32        6.8 GB/s            6.0 GB/s
0073  */
0074
0075 #ifndef XXHASH_H
0076 #define XXHASH_H
0077
0078 #include <linux/types.h>
0079
0080 /*-****************************
0081  * Simple Hash Functions
0082  *****************************/
0083
0084 /**
0085  * xxh32() - calculate the 32-bit hash of the input with a given seed.
0086  *
0087  * @input:  The data to hash.
0088  * @length: The length of the data to hash.
0089  * @seed:   The seed can be used to alter the result predictably.
0090  *
0091  * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s
0092  *
0093  * Return:  The 32-bit hash of the data.
0094  */
0095 uint32_t xxh32(const void *input, size_t length, uint32_t seed);
0096
0097 /**
0098  * xxh64() - calculate the 64-bit hash of the input with a given seed.
0099  *
0100  * @input:  The data to hash.
0101  * @length: The length of the data to hash.
0102  * @seed:   The seed can be used to alter the result predictably.
0103  *
0104  * This function runs 2x faster on 64-bit systems, but slower on 32-bit systems.
0105  *
0106  * Return:  The 64-bit hash of the data.
0107  */
0108 uint64_t xxh64(const void *input, size_t length, uint64_t seed);
0109
0110 /**
0111  * xxhash() - calculate wordsize hash of the input with a given seed
0112  * @input:  The data to hash.
0113  * @length: The length of the data to hash.
0114  * @seed:   The seed can be used to alter the result predictably.
0115  *
0116  * If the hash does not need to be comparable between machines with
0117  * different word sizes, this function will call whichever of xxh32()
0118  * or xxh64() is faster.
0119  *
0120  * Return:  wordsize hash of the data.
0121  */
0122
0123 static inline unsigned long xxhash(const void *input, size_t length,
0124                    uint64_t seed)
0125 {
0126 #if BITS_PER_LONG == 64
0127        return xxh64(input, length, seed);
0128 #else
0129        return xxh32(input, length, seed);
0130 #endif
0131 }
0132
0133 /*-****************************
0134  * Streaming Hash Functions
0135  *****************************/
0136
0137 /*
0138  * These definitions are only meant to allow allocation of XXH state
0139  * statically, on stack, or in a struct for example.
0140  * Do not use members directly.
0141  */
0142
0143 /**
0144  * struct xxh32_state - private xxh32 state, do not use members directly
0145  */
0146 struct xxh32_state {
0147     uint32_t total_len_32;
0148     uint32_t large_len;
0149     uint32_t v1;
0150     uint32_t v2;
0151     uint32_t v3;
0152     uint32_t v4;
0153     uint32_t mem32[4];
0154     uint32_t memsize;
0155 };
0156
0157 /**
0158  * struct xxh32_state - private xxh64 state, do not use members directly
0159  */
0160 struct xxh64_state {
0161     uint64_t total_len;
0162     uint64_t v1;
0163     uint64_t v2;
0164     uint64_t v3;
0165     uint64_t v4;
0166     uint64_t mem64[4];
0167     uint32_t memsize;
0168 };
0169
0170 /**
0171  * xxh32_reset() - reset the xxh32 state to start a new hashing operation
0172  *
0173  * @state: The xxh32 state to reset.
0174  * @seed:  Initialize the hash state with this seed.
0175  *
0176  * Call this function on any xxh32_state to prepare for a new hashing operation.
0177  */
0178 void xxh32_reset(struct xxh32_state *state, uint32_t seed);
0179
0180 /**
0181  * xxh32_update() - hash the data given and update the xxh32 state
0182  *
0183  * @state:  The xxh32 state to update.
0184  * @input:  The data to hash.
0185  * @length: The length of the data to hash.
0186  *
0187  * After calling xxh32_reset() call xxh32_update() as many times as necessary.
0188  *
0189  * Return:  Zero on success, otherwise an error code.
0190  */
0191 int xxh32_update(struct xxh32_state *state, const void *input, size_t length);
0192
0193 /**
0194  * xxh32_digest() - produce the current xxh32 hash
0195  *
0196  * @state: Produce the current xxh32 hash of this state.
0197  *
0198  * A hash value can be produced at any time. It is still possible to continue
0199  * inserting input into the hash state after a call to xxh32_digest(), and
0200  * generate new hashes later on, by calling xxh32_digest() again.
0201  *
0202  * Return: The xxh32 hash stored in the state.
0203  */
0204 uint32_t xxh32_digest(const struct xxh32_state *state);
0205
0206 /**
0207  * xxh64_reset() - reset the xxh64 state to start a new hashing operation
0208  *
0209  * @state: The xxh64 state to reset.
0210  * @seed:  Initialize the hash state with this seed.
0211  */
0212 void xxh64_reset(struct xxh64_state *state, uint64_t seed);
0213
0214 /**
0215  * xxh64_update() - hash the data given and update the xxh64 state
0216  * @state:  The xxh64 state to update.
0217  * @input:  The data to hash.
0218  * @length: The length of the data to hash.
0219  *
0220  * After calling xxh64_reset() call xxh64_update() as many times as necessary.
0221  *
0222  * Return:  Zero on success, otherwise an error code.
0223  */
0224 int xxh64_update(struct xxh64_state *state, const void *input, size_t length);
0225
0226 /**
0227  * xxh64_digest() - produce the current xxh64 hash
0228  *
0229  * @state: Produce the current xxh64 hash of this state.
0230  *
0231  * A hash value can be produced at any time. It is still possible to continue
0232  * inserting input into the hash state after a call to xxh64_digest(), and
0233  * generate new hashes later on, by calling xxh64_digest() again.
0234  *
0235  * Return: The xxh64 hash stored in the state.
0236  */
0237 uint64_t xxh64_digest(const struct xxh64_state *state);
0238
0239 /*-**************************
0240  * Utils
0241  ***************************/
0242
0243 /**
0244  * xxh32_copy_state() - copy the source state into the destination state
0245  *
0246  * @src: The source xxh32 state.
0247  * @dst: The destination xxh32 state.
0248  */
0249 void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src);
0250
0251 /**
0252  * xxh64_copy_state() - copy the source state into the destination state
0253  *
0254  * @src: The source xxh64 state.
0255  * @dst: The destination xxh64 state.
0256  */
0257 void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src);
0258
0259 #endif /* XXHASH_H */