LLVM  10.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  bool AllASCII = true;
62  for (unsigned char C : Buffer) {
63  H = H * 33 + ('A' <= C && C <= 'Z' ? C - 'A' + 'a' : C);
64  AllASCII &= C <= 0x7f;
65  }
66  if (AllASCII)
67  return H;
68  return None;
69 }
70 
72  if (Optional<uint32_t> Result = fastCaseFoldingDjbHash(Buffer, H))
73  return *Result;
74 
75  std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;
76  while (!Buffer.empty()) {
77  UTF32 C = foldCharDwarf(chopOneUTF32(Buffer));
78  StringRef Folded = toUTF8(C, Storage);
79  H = djbHash(Folded, H);
80  }
81  return H;
82 }
unsigned int UTF32
Definition: ConvertUTF.h:109
const NoneType None
Definition: None.h:23
uint64_t CallInst * C
static UTF32 foldCharDwarf(UTF32 C)
Definition: DJB.cpp:51
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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
static Optional< uint32_t > fastCaseFoldingDjbHash(StringRef Buffer, uint32_t H)
Definition: DJB.cpp:60
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:634
unsigned char UTF8
Definition: ConvertUTF.h:111
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:140
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:71
iterator begin() const
Definition: ArrayRef.h:330
iterator begin() const
Definition: StringRef.h:115
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:117