src/xxhash32.c

   1 /*
   2  *  xxHash - Fast Hash algorithm
   3  *  Copyright (C) 2012-2020 Yann Collet
   4  *  Copyright (C) 2019-2020 Devin Hussey (easyaspi314)
   5  *
   6  *  BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
   7  *
   8  *  Redistribution and use in source and binary forms, with or without
   9  *  modification, are permitted provided that the following conditions are
  10  *  met:
  11  *
  12  *  * Redistributions of source code must retain the above copyright
  13  *  notice, this list of conditions and the following disclaimer.
  14  *  * Redistributions in binary form must reproduce the above
  15  *  copyright notice, this list of conditions and the following disclaimer
  16  *  in the documentation and/or other materials provided with the
  17  *  distribution.
  18  *
  19  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  *
  31  *  You can contact the author at :
  32  *  - xxHash homepage: http://www.xxhash.com
  33  *  - xxHash source repository : https://github.com/Cyan4973/xxHash */
  34
  35 /* This is a compact, 100% standalone reference XXH32 single-run implementation.
  36  * Instead of focusing on performance hacks, this focuses on cleanliness,
  37  * conformance, portability and simplicity.
  38  *
  39  * This file aims to be 100% compatible with C90/C++98, with the additional
  40  * requirement of stdint.h. No library functions are used. */
  41
  42 #include <stddef.h> /* size_t, NULL */
  43 #include <stdint.h> /* uint8_t, uint32_t */
  44 #include "xxhash32.h"
  45
  46 static uint32_t const PRIME32_1 = 0x9E3779B1U;   /* 0b10011110001101110111100110110001 */
  47 static uint32_t const PRIME32_2 = 0x85EBCA77U;   /* 0b10000101111010111100101001110111 */
  48 static uint32_t const PRIME32_3 = 0xC2B2AE3DU;   /* 0b11000010101100101010111000111101 */
  49 static uint32_t const PRIME32_4 = 0x27D4EB2FU;   /* 0b00100111110101001110101100101111 */
  50 static uint32_t const PRIME32_5 = 0x165667B1U;   /* 0b00010110010101100110011110110001 */
  51
  52 /* Rotates value left by amt. */
  53 static uint32_t XXH_rotl32(uint32_t const value, uint32_t const amt)
  54 {
  55     return (value << (amt % 32)) | (value >> (32 - (amt % 32)));
  56 }
  57
  58 /* Portably reads a 32-bit little endian integer from data at the given offset. */
  59 static uint32_t XXH_read32(uint8_t const *const data, size_t const offset)
  60 {
  61     return (uint32_t) data[offset + 0]
  62         | ((uint32_t) data[offset + 1] << 8)
  63         | ((uint32_t) data[offset + 2] << 16)
  64         | ((uint32_t) data[offset + 3] << 24);
  65 }
  66
  67 /* Mixes input into acc. */
  68 static uint32_t XXH32_round(uint32_t acc, uint32_t const input)
  69 {
  70     acc += input * PRIME32_2;
  71     acc  = XXH_rotl32(acc, 13);
  72     acc *= PRIME32_1;
  73     return acc;
  74 }
  75
  76 /* Mixes all bits to finalize the hash. */
  77 static uint32_t XXH32_avalanche(uint32_t hash)
  78 {
  79     hash ^= hash >> 15;
  80     hash *= PRIME32_2;
  81     hash ^= hash >> 13;
  82     hash *= PRIME32_3;
  83     hash ^= hash >> 16;
  84     return hash;
  85 }
  86
  87 /* The XXH32 hash function.
  88  * input:   The data to hash.
  89  * length:  The length of input. It is undefined behavior to have length larger than the
  90  *          capacity of input.
  91  * seed:    A 32-bit value to seed the hash with.
  92  * returns: The 32-bit calculated hash value. */
  93 uint32_t XXH32(void const *const input, size_t const length, uint32_t const seed)
  94 {
  95     uint8_t const *const data = (uint8_t const *) input;
  96     uint32_t hash;
  97     size_t remaining = length;
  98     size_t offset = 0;
  99
 100     /* Don't dereference a null pointer. The reference implementation notably doesn't
 101      * check for this by default. */
 102     if (input == NULL) {
 103         return XXH32_avalanche(seed + PRIME32_5);
 104     }
 105
 106     if (remaining >= 16) {
 107         /* Initialize our accumulators */
 108         uint32_t acc1 = seed + PRIME32_1 + PRIME32_2;
 109         uint32_t acc2 = seed + PRIME32_2;
 110         uint32_t acc3 = seed + 0;
 111         uint32_t acc4 = seed - PRIME32_1;
 112
 113         while (remaining >= 16) {
 114             acc1 = XXH32_round(acc1, XXH_read32(data, offset)); offset += 4;
 115             acc2 = XXH32_round(acc2, XXH_read32(data, offset)); offset += 4;
 116             acc3 = XXH32_round(acc3, XXH_read32(data, offset)); offset += 4;
 117             acc4 = XXH32_round(acc4, XXH_read32(data, offset)); offset += 4;
 118             remaining -= 16;
 119         }
 120
 121         hash = XXH_rotl32(acc1, 1) + XXH_rotl32(acc2, 7) + XXH_rotl32(acc3, 12) + XXH_rotl32(acc4, 18);
 122     } else {
 123         /* Not enough data for the main loop, put something in there instead. */
 124         hash = seed + PRIME32_5;
 125     }
 126
 127     hash += (uint32_t) length;
 128
 129     /* Process the remaining data. */
 130     while (remaining >= 4) {
 131         hash += XXH_read32(data, offset) * PRIME32_3;
 132         hash  = XXH_rotl32(hash, 17);
 133         hash *= PRIME32_4;
 134         offset += 4;
 135         remaining -= 4;
 136     }
 137
 138     while (remaining != 0) {
 139         hash += (uint32_t) data[offset] * PRIME32_5;
 140         hash  = XXH_rotl32(hash, 11);
 141         hash *= PRIME32_1;
 142         --remaining;
 143         ++offset;
 144     }
 145     return XXH32_avalanche(hash);
 146 }