1 //===-- Support/DJB.cpp ---DJB Hash -----------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains support for the DJ Bernstein hash function.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Support/DJB.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/ConvertUTF.h"
18 #include "llvm/Support/Unicode.h"
22 static UTF32
chopOneUTF32(StringRef
&Buffer
) {
24 const UTF8
*const Begin8Const
=
25 reinterpret_cast<const UTF8
*>(Buffer
.begin());
26 const UTF8
*Begin8
= Begin8Const
;
29 // In lenient mode we will always end up with a "reasonable" value in C for
31 assert(!Buffer
.empty());
32 ConvertUTF8toUTF32(&Begin8
, reinterpret_cast<const UTF8
*>(Buffer
.end()),
33 &Begin32
, &C
+ 1, lenientConversion
);
34 Buffer
= Buffer
.drop_front(Begin8
- Begin8Const
);
38 static StringRef
toUTF8(UTF32 C
, MutableArrayRef
<UTF8
> Storage
) {
39 const UTF32
*Begin32
= &C
;
40 UTF8
*Begin8
= Storage
.begin();
42 // The case-folded output should always be a valid unicode character, so use
44 ConversionResult CR
= ConvertUTF32toUTF8(&Begin32
, &C
+ 1, &Begin8
,
45 Storage
.end(), strictConversion
);
46 assert(CR
== conversionOK
&& "Case folding produced invalid char?");
48 return StringRef(reinterpret_cast<char *>(Storage
.begin()),
49 Begin8
- Storage
.begin());
52 static UTF32
foldCharDwarf(UTF32 C
) {
53 // DWARF v5 addition to the unicode folding rules.
54 // Fold "Latin Small Letter Dotless I" and "Latin Capital Letter I With Dot
56 if (C
== 0x130 || C
== 0x131)
58 return sys::unicode::foldCharSimple(C
);
61 static uint32_t caseFoldingDjbHashCharSlow(StringRef
&Buffer
, uint32_t H
) {
62 UTF32 C
= chopOneUTF32(Buffer
);
66 std::array
<UTF8
, UNI_MAX_UTF8_BYTES_PER_CODE_POINT
> Storage
;
67 StringRef Folded
= toUTF8(C
, Storage
);
68 return djbHash(Folded
, H
);
71 uint32_t llvm::caseFoldingDjbHash(StringRef Buffer
, uint32_t H
) {
72 while (!Buffer
.empty()) {
73 unsigned char C
= Buffer
.front();
74 if (LLVM_LIKELY(C
<= 0x7f)) {
75 // US-ASCII, encoded as one character in utf-8.
76 // This is by far the most common case, so handle this specially.
77 if (C
>= 'A' && C
<= 'Z')
78 C
= 'a' + (C
- 'A'); // fold uppercase into lowercase
80 Buffer
= Buffer
.drop_front();
83 H
= caseFoldingDjbHashCharSlow(Buffer
, H
);