Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Support/DJB.cpp
Line
Count
Source
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
19
using namespace llvm;
20
21
40
static UTF32 chopOneUTF32(StringRef &Buffer) {
22
40
  UTF32 C;
23
40
  const UTF8 *const Begin8Const =
24
40
      reinterpret_cast<const UTF8 *>(Buffer.begin());
25
40
  const UTF8 *Begin8 = Begin8Const;
26
40
  UTF32 *Begin32 = &C;
27
40
28
40
  // In lenient mode we will always end up with a "reasonable" value in C for
29
40
  // non-empty input.
30
40
  assert(!Buffer.empty());
31
40
  ConvertUTF8toUTF32(&Begin8, reinterpret_cast<const UTF8 *>(Buffer.end()),
32
40
                     &Begin32, &C + 1, lenientConversion);
33
40
  Buffer = Buffer.drop_front(Begin8 - Begin8Const);
34
40
  return C;
35
40
}
36
37
40
static StringRef toUTF8(UTF32 C, MutableArrayRef<UTF8> Storage) {
38
40
  const UTF32 *Begin32 = &C;
39
40
  UTF8 *Begin8 = Storage.begin();
40
40
41
40
  // The case-folded output should always be a valid unicode character, so use
42
40
  // strict mode here.
43
40
  ConversionResult CR = ConvertUTF32toUTF8(&Begin32, &C + 1, &Begin8,
44
40
                                           Storage.end(), strictConversion);
45
40
  assert(CR == conversionOK && "Case folding produced invalid char?");
46
40
  (void)CR;
47
40
  return StringRef(reinterpret_cast<char *>(Storage.begin()),
48
40
                   Begin8 - Storage.begin());
49
40
}
50
51
40
static UTF32 foldCharDwarf(UTF32 C) {
52
40
  // DWARF v5 addition to the unicode folding rules.
53
40
  // Fold "Latin Small Letter Dotless I" and "Latin Capital Letter I With Dot
54
40
  // Above" into "i".
55
40
  if (C == 0x130 || 
C == 0x13137
)
56
5
    return 'i';
57
35
  return sys::unicode::foldCharSimple(C);
58
35
}
59
60
1.21k
static Optional<uint32_t> fastCaseFoldingDjbHash(StringRef Buffer, uint32_t H) {
61
1.21k
  bool AllASCII = true;
62
9.14k
  for (unsigned char C : Buffer) {
63
9.14k
    H = H * 33 + ('A' <= C && 
C <= 'Z'6.93k
?
C - 'A' + 'a'550
:
C8.59k
);
64
9.14k
    AllASCII &= C <= 0x7f;
65
9.14k
  }
66
1.21k
  if (AllASCII)
67
1.19k
    return H;
68
21
  return None;
69
21
}
70
71
1.21k
uint32_t llvm::caseFoldingDjbHash(StringRef Buffer, uint32_t H) {
72
1.21k
  if (Optional<uint32_t> Result = fastCaseFoldingDjbHash(Buffer, H))
73
1.19k
    return *Result;
74
21
75
21
  std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;
76
61
  while (!Buffer.empty()) {
77
40
    UTF32 C = foldCharDwarf(chopOneUTF32(Buffer));
78
40
    StringRef Folded = toUTF8(C, Storage);
79
40
    H = djbHash(Folded, H);
80
40
  }
81
21
  return H;
82
21
}