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"
16#include "llvm/Support/ConvertUTF.h"
17#include "llvm/Support/Unicode.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
37static StringRef toUTF8(UTF32 C, MutableArrayRef<UTF8> Storage) {
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
51static UTF32 foldCharDwarf(UTF32 C) {
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';
57  return sys::unicode::foldCharSimple(C);
58}
59
60static Optional<uint32_t> fastCaseFoldingDjbHash(StringRef Buffer, uint32_t H) {
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
71uint32_t llvm::caseFoldingDjbHash(StringRef Buffer, uint32_t H) {
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}
83