1 //===--- SipHash.cpp - An ABI-stable string hash --------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Support/SipHash.h" 10 #include "llvm/ADT/ArrayRef.h" 11 #include "llvm/Support/Compiler.h" 12 #include "llvm/Support/Endian.h" 13 #include <cstdint> 14 15 using namespace llvm; 16 using namespace support; 17 18 // Lightly adapted from the SipHash reference C implementation: 19 // https://github.com/veorq/SipHash 20 // by Jean-Philippe Aumasson and Daniel J. Bernstein 21 22 #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) 23 24 #define SIPROUND \ 25 do { \ 26 v0 += v1; \ 27 v1 = ROTL(v1, 13); \ 28 v1 ^= v0; \ 29 v0 = ROTL(v0, 32); \ 30 v2 += v3; \ 31 v3 = ROTL(v3, 16); \ 32 v3 ^= v2; \ 33 v0 += v3; \ 34 v3 = ROTL(v3, 21); \ 35 v3 ^= v0; \ 36 v2 += v1; \ 37 v1 = ROTL(v1, 17); \ 38 v1 ^= v2; \ 39 v2 = ROTL(v2, 32); \ 40 } while (0) 41 42 namespace { 43 44 /// Computes a SipHash value 45 /// 46 /// \param in: pointer to input data (read-only) 47 /// \param inlen: input data length in bytes (any size_t value) 48 /// \param k: reference to the key data 16-byte array (read-only) 49 /// \returns output data, must be 8 or 16 bytes 50 /// 51 template <int cROUNDS, int dROUNDS, size_t outlen> 52 void siphash(const unsigned char *in, uint64_t inlen, 53 const unsigned char (&k)[16], unsigned char (&out)[outlen]) { 54 55 const unsigned char *ni = (const unsigned char *)in; 56 const unsigned char *kk = (const unsigned char *)k; 57 58 static_assert(outlen == 8 || outlen == 16, "result should be 8 or 16 bytes"); 59 60 uint64_t v0 = UINT64_C(0x736f6d6570736575); 61 uint64_t v1 = UINT64_C(0x646f72616e646f6d); 62 uint64_t v2 = UINT64_C(0x6c7967656e657261); 63 uint64_t v3 = UINT64_C(0x7465646279746573); 64 uint64_t k0 = endian::read64le(kk); 65 uint64_t k1 = endian::read64le(kk + 8); 66 uint64_t m; 67 int i; 68 const unsigned char *end = ni + inlen - (inlen % sizeof(uint64_t)); 69 const int left = inlen & 7; 70 uint64_t b = ((uint64_t)inlen) << 56; 71 v3 ^= k1; 72 v2 ^= k0; 73 v1 ^= k1; 74 v0 ^= k0; 75 76 if (outlen == 16) 77 v1 ^= 0xee; 78 79 for (; ni != end; ni += 8) { 80 m = endian::read64le(ni); 81 v3 ^= m; 82 83 for (i = 0; i < cROUNDS; ++i) 84 SIPROUND; 85 86 v0 ^= m; 87 } 88 89 switch (left) { 90 case 7: 91 b |= ((uint64_t)ni[6]) << 48; 92 LLVM_FALLTHROUGH; 93 case 6: 94 b |= ((uint64_t)ni[5]) << 40; 95 LLVM_FALLTHROUGH; 96 case 5: 97 b |= ((uint64_t)ni[4]) << 32; 98 LLVM_FALLTHROUGH; 99 case 4: 100 b |= ((uint64_t)ni[3]) << 24; 101 LLVM_FALLTHROUGH; 102 case 3: 103 b |= ((uint64_t)ni[2]) << 16; 104 LLVM_FALLTHROUGH; 105 case 2: 106 b |= ((uint64_t)ni[1]) << 8; 107 LLVM_FALLTHROUGH; 108 case 1: 109 b |= ((uint64_t)ni[0]); 110 break; 111 case 0: 112 break; 113 } 114 115 v3 ^= b; 116 117 for (i = 0; i < cROUNDS; ++i) 118 SIPROUND; 119 120 v0 ^= b; 121 122 if (outlen == 16) 123 v2 ^= 0xee; 124 else 125 v2 ^= 0xff; 126 127 for (i = 0; i < dROUNDS; ++i) 128 SIPROUND; 129 130 b = v0 ^ v1 ^ v2 ^ v3; 131 endian::write64le(out, b); 132 133 if (outlen == 8) 134 return; 135 136 v1 ^= 0xdd; 137 138 for (i = 0; i < dROUNDS; ++i) 139 SIPROUND; 140 141 b = v0 ^ v1 ^ v2 ^ v3; 142 endian::write64le(out + 8, b); 143 } 144 145 } // end anonymous namespace 146 147 void llvm::getSipHash_2_4_64(ArrayRef<uint8_t> In, const uint8_t (&K)[16], 148 uint8_t (&Out)[8]) { 149 siphash<2, 4>(In.data(), In.size(), K, Out); 150 } 151 152 void llvm::getSipHash_2_4_128(ArrayRef<uint8_t> In, const uint8_t (&K)[16], 153 uint8_t (&Out)[16]) { 154 siphash<2, 4>(In.data(), In.size(), K, Out); 155 } 156