LLVM 20.0.0git
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"
18
19using namespace llvm;
20
21static 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
60static std::optional<uint32_t> fastCaseFoldingDjbHash(StringRef Buffer,
61 uint32_t H) {
62 bool AllASCII = true;
63 for (unsigned char C : Buffer) {
64 H = H * 33 + ('A' <= C && C <= 'Z' ? C - 'A' + 'a' : C);
65 AllASCII &= C <= 0x7f;
66 }
67 if (AllASCII)
68 return H;
69 return std::nullopt;
70}
71
73 if (std::optional<uint32_t> Result = fastCaseFoldingDjbHash(Buffer, H))
74 return *Result;
75
76 std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;
77 while (!Buffer.empty()) {
79 StringRef Folded = toUTF8(C, Storage);
80 H = djbHash(Folded, H);
81 }
82 return H;
83}
static std::optional< uint32_t > fastCaseFoldingDjbHash(StringRef Buffer, uint32_t H)
Definition: DJB.cpp:60
static UTF32 foldCharDwarf(UTF32 C)
Definition: DJB.cpp:51
static StringRef toUTF8(UTF32 C, MutableArrayRef< UTF8 > Storage)
Definition: DJB.cpp:37
static UTF32 chopOneUTF32(StringRef &Buffer)
Definition: DJB.cpp:21
#define H(x, y, z)
Definition: MD5.cpp:57
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:307
iterator end() const
Definition: ArrayRef.h:357
iterator begin() const
Definition: ArrayRef.h:356
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
constexpr bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:134
StringRef drop_front(size_t N=1) const
Return a StringRef equal to 'this' but with the first N elements dropped.
Definition: StringRef.h:594
iterator begin() const
Definition: StringRef.h:111
iterator end() const
Definition: StringRef.h:113
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
int foldCharSimple(int C)
Fold input unicode character according the Simple unicode case folding rules.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ConversionResult ConvertUTF8toUTF32(const UTF8 **sourceStart, const UTF8 *sourceEnd, UTF32 **targetStart, UTF32 *targetEnd, ConversionFlags flags)
Convert a partial UTF8 sequence to UTF32.
Definition: ConvertUTF.cpp:736
@ lenientConversion
Definition: ConvertUTF.h:157
@ strictConversion
Definition: ConvertUTF.h:156
ConversionResult
Definition: ConvertUTF.h:148
@ conversionOK
Definition: ConvertUTF.h:149
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:72
ConversionResult ConvertUTF32toUTF8(const UTF32 **sourceStart, const UTF32 *sourceEnd, UTF8 **targetStart, UTF8 *targetEnd, ConversionFlags flags)
Definition: ConvertUTF.cpp:333
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
Definition: DJB.h:21
unsigned char UTF8
Definition: ConvertUTF.h:130
unsigned int UTF32
Definition: ConvertUTF.h:128