LLVM  14.0.0git
xxhash.cpp
Go to the documentation of this file.
1 /*
2 * xxHash - 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 * You can contact the author at :
31 * - xxHash homepage: http://www.xxhash.com
32 * - xxHash source repository : https://github.com/Cyan4973/xxHash
33 */
34 
35 /* based on revision d2df04efcbef7d7f6886d345861e5dfda4edacc1 Removed
36  * everything but a simple interface for computing XXh64. */
37 
38 #include "llvm/Support/xxhash.h"
39 #include "llvm/Support/Endian.h"
40 
41 #include <stdlib.h>
42 #include <string.h>
43 
44 using namespace llvm;
45 using namespace support;
46 
47 static uint64_t rotl64(uint64_t X, size_t R) {
48  return (X << R) | (X >> (64 - R));
49 }
50 
51 static const uint64_t PRIME64_1 = 11400714785074694791ULL;
52 static const uint64_t PRIME64_2 = 14029467366897019727ULL;
53 static const uint64_t PRIME64_3 = 1609587929392839161ULL;
54 static const uint64_t PRIME64_4 = 9650029242287828579ULL;
55 static const uint64_t PRIME64_5 = 2870177450012600261ULL;
56 
57 static uint64_t round(uint64_t Acc, uint64_t Input) {
58  Acc += Input * PRIME64_2;
59  Acc = rotl64(Acc, 31);
60  Acc *= PRIME64_1;
61  return Acc;
62 }
63 
65  Val = round(0, Val);
66  Acc ^= Val;
67  Acc = Acc * PRIME64_1 + PRIME64_4;
68  return Acc;
69 }
70 
72  size_t Len = Data.size();
73  uint64_t Seed = 0;
74  const unsigned char *P = Data.bytes_begin();
75  const unsigned char *const BEnd = Data.bytes_end();
76  uint64_t H64;
77 
78  if (Len >= 32) {
79  const unsigned char *const Limit = BEnd - 32;
82  uint64_t V3 = Seed + 0;
84 
85  do {
86  V1 = round(V1, endian::read64le(P));
87  P += 8;
89  P += 8;
90  V3 = round(V3, endian::read64le(P));
91  P += 8;
93  P += 8;
94  } while (P <= Limit);
95 
96  H64 = rotl64(V1, 1) + rotl64(V2, 7) + rotl64(V3, 12) + rotl64(V4, 18);
97  H64 = mergeRound(H64, V1);
98  H64 = mergeRound(H64, V2);
99  H64 = mergeRound(H64, V3);
100  H64 = mergeRound(H64, V4);
101 
102  } else {
103  H64 = Seed + PRIME64_5;
104  }
105 
106  H64 += (uint64_t)Len;
107 
108  while (P + 8 <= BEnd) {
109  uint64_t const K1 = round(0, endian::read64le(P));
110  H64 ^= K1;
111  H64 = rotl64(H64, 27) * PRIME64_1 + PRIME64_4;
112  P += 8;
113  }
114 
115  if (P + 4 <= BEnd) {
116  H64 ^= (uint64_t)(endian::read32le(P)) * PRIME64_1;
117  H64 = rotl64(H64, 23) * PRIME64_2 + PRIME64_3;
118  P += 4;
119  }
120 
121  while (P < BEnd) {
122  H64 ^= (*P) * PRIME64_5;
123  H64 = rotl64(H64, 11) * PRIME64_1;
124  P++;
125  }
126 
127  H64 ^= H64 >> 33;
128  H64 *= PRIME64_2;
129  H64 ^= H64 >> 29;
130  H64 *= PRIME64_3;
131  H64 ^= H64 >> 32;
132 
133  return H64;
134 }
135 
137  return xxHash64({(const char *)Data.data(), Data.size()});
138 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
PRIME64_2
static const uint64_t PRIME64_2
Definition: xxhash.cpp:52
round
static uint64_t round(uint64_t Acc, uint64_t Input)
Definition: xxhash.cpp:57
mergeRound
static uint64_t mergeRound(uint64_t Acc, uint64_t Val)
Definition: xxhash.cpp:64
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::NVPTX::PTXLdStInstCode::V4
@ V4
Definition: NVPTX.h:124
Seed
static ManagedStatic< cl::opt< uint64_t >, CreateSeed > Seed
Definition: RandomNumberGenerator.cpp:40
rotl64
static uint64_t rotl64(uint64_t X, size_t R)
Definition: xxhash.cpp:47
uint64_t
PRIME64_3
static const uint64_t PRIME64_3
Definition: xxhash.cpp:53
xxhash.h
llvm::ArrayRef< uint8_t >
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
PRIME64_4
static const uint64_t PRIME64_4
Definition: xxhash.cpp:54
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
PRIME64_5
static const uint64_t PRIME64_5
Definition: xxhash.cpp:55
PRIME64_1
static const uint64_t PRIME64_1
Definition: xxhash.cpp:51
llvm::support::endian::read64le
uint64_t read64le(const void *P)
Definition: Endian.h:382
llvm::support::endian::read32le
uint32_t read32le(const void *P)
Definition: Endian.h:381
support
Reimplement select in terms of SEL *We would really like to support but we need to prove that the add doesn t need to overflow between the two bit chunks *Implement pre post increment support(e.g. PR935) *Implement smarter const ant generation for binops with large immediates. A few ARMv6T2 ops should be pattern matched
Definition: README.txt:10
Endian.h
llvm::xxHash64
uint64_t xxHash64(llvm::StringRef Data)
Definition: xxhash.cpp:71