LLVM  9.0.0svn
DJB.cpp
Go to the documentation of this file.
1 //===-- Support/DJB.cpp ---DJB Hash -----------------------------*- C++ -*-===//
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 // This file contains support for the DJ Bernstein hash function.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/Support/DJB.h"
14 #include "llvm/ADT/ArrayRef.h"
15 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/Unicode.h"
18 
19 using namespace llvm;
20 
21 static UTF32 chopOneUTF32(StringRef &Buffer) {
22  UTF32 C;
23  const UTF8 *const Begin8Const =
24  reinterpret_cast<const UTF8 *>(Buffer.begin());
25  const UTF8 *Begin8 = Begin8Const;
26  UTF32 *Begin32 = &C;
27 
28  // In lenient mode we will always end up with a "reasonable" value in C for
29  // non-empty input.
30  assert(!Buffer.empty());
31  ConvertUTF8toUTF32(&Begin8, reinterpret_cast<const UTF8 *>(Buffer.end()),
32  &Begin32, &C + 1, lenientConversion);
33  Buffer = Buffer.drop_front(Begin8 - Begin8Const);
34  return C;
35 }
36 
38  const UTF32 *Begin32 = &C;
39  UTF8 *Begin8 = Storage.begin();
40 
41  // The case-folded output should always be a valid unicode character, so use
42  // strict mode here.
43  ConversionResult CR = ConvertUTF32toUTF8(&Begin32, &C + 1, &Begin8,
44  Storage.end(), strictConversion);
45  assert(CR == conversionOK && "Case folding produced invalid char?");
46  (void)CR;
47  return StringRef(reinterpret_cast<char *>(Storage.begin()),
48  Begin8 - Storage.begin());
49 }
50 
52  // DWARF v5 addition to the unicode folding rules.
53  // Fold "Latin Small Letter Dotless I" and "Latin Capital Letter I With Dot
54  // Above" into "i".
55  if (C == 0x130 || C == 0x131)
56  return 'i';
58 }
59 
61  UTF32 C = chopOneUTF32(Buffer);
62 
63  C = foldCharDwarf(C);
64 
65  std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;
66  StringRef Folded = toUTF8(C, Storage);
67  return djbHash(Folded, H);
68 }
69 
71  while (!Buffer.empty()) {
72  unsigned char C = Buffer.front();
73  if (LLVM_LIKELY(C <= 0x7f)) {
74  // US-ASCII, encoded as one character in utf-8.
75  // This is by far the most common case, so handle this specially.
76  if (C >= 'A' && C <= 'Z')
77  C = 'a' + (C - 'A'); // fold uppercase into lowercase
78  H = (H << 5) + H + C;
79  Buffer = Buffer.drop_front();
80  continue;
81  }
82  H = caseFoldingDjbHashCharSlow(Buffer, H);
83  }
84  return H;
85 }
unsigned int UTF32
Definition: ConvertUTF.h:109
uint64_t CallInst * C
static UTF32 foldCharDwarf(UTF32 C)
Definition: DJB.cpp:51
static uint32_t caseFoldingDjbHashCharSlow(StringRef &Buffer, uint32_t H)
Definition: DJB.cpp:60
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:190
ConversionResult
Definition: ConvertUTF.h:126
ConversionResult ConvertUTF8toUTF32(const UTF8 **sourceStart, const UTF8 *sourceEnd, UTF32 **targetStart, UTF32 *targetEnd, ConversionFlags flags)
Convert a partial UTF8 sequence to UTF32.
Definition: ConvertUTF.cpp:710
LLVM_NODISCARD StringRef drop_front(size_t N=1) const
Return a StringRef equal to &#39;this&#39; but with the first N elements dropped.
Definition: StringRef.h:620
unsigned char UTF8
Definition: ConvertUTF.h:111
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:126
static UTF32 chopOneUTF32(StringRef &Buffer)
Definition: DJB.cpp:21
int foldCharSimple(int C)
Fold input unicode character according the Simple unicode case folding rules.
ConversionResult ConvertUTF32toUTF8(const UTF32 **sourceStart, const UTF32 *sourceEnd, UTF8 **targetStart, UTF8 *targetEnd, ConversionFlags flags)
Definition: ConvertUTF.cpp:317
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:290
#define H(x, y, z)
Definition: MD5.cpp:57
static StringRef toUTF8(UTF32 C, MutableArrayRef< UTF8 > Storage)
Definition: DJB.cpp:37
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
Definition: DJB.h:21
uint32_t caseFoldingDjbHash(StringRef Buffer, uint32_t H=5381)
Computes the Bernstein hash after folding the input according to the Dwarf 5 standard case folding ru...
Definition: DJB.cpp:70
iterator begin() const
Definition: ArrayRef.h:330
iterator begin() const
Definition: StringRef.h:101
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM_NODISCARD char front() const
front - Get the first character in the string.
Definition: StringRef.h:134
iterator end() const
Definition: ArrayRef.h:331
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
iterator end() const
Definition: StringRef.h:103