lib/Support/DJB.cpp

   1 //===-- Support/DJB.cpp ---DJB Hash -----------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains support for the DJ Bernstein hash function.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  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"
  19
  20 using namespace llvm;
  21
  22 static inline uint32_t djbHashChar(unsigned char C, uint32_t H) {
  23   return (H << 5) + H + C;
  24 }
  25
  26 uint32_t llvm::djbHash(StringRef Buffer, uint32_t H) {
  27   for (unsigned char C : Buffer.bytes())
  28     H = djbHashChar(C, H);
  29   return H;
  30 }
  31
  32 static UTF32 chopOneUTF32(StringRef &Buffer) {
  33   UTF32 C;
  34   const UTF8 *const Begin8Const =
  35       reinterpret_cast<const UTF8 *>(Buffer.begin());
  36   const UTF8 *Begin8 = Begin8Const;
  37   UTF32 *Begin32 = &C;
  38
  39   // In lenient mode we will always end up with a "reasonable" value in C for
  40   // non-empty input.
  41   assert(!Buffer.empty());
  42   ConvertUTF8toUTF32(&Begin8, reinterpret_cast<const UTF8 *>(Buffer.end()),
  43                      &Begin32, &C + 1, lenientConversion);
  44   Buffer = Buffer.drop_front(Begin8 - Begin8Const);
  45   return C;
  46 }
  47
  48 static StringRef toUTF8(UTF32 C, MutableArrayRef<UTF8> Storage) {
  49   const UTF32 *Begin32 = &C;
  50   UTF8 *Begin8 = Storage.begin();
  51
  52   // The case-folded output should always be a valid unicode character, so use
  53   // strict mode here.
  54   ConversionResult CR = ConvertUTF32toUTF8(&Begin32, &C + 1, &Begin8,
  55                                            Storage.end(), strictConversion);
  56   assert(CR == conversionOK && "Case folding produced invalid char?");
  57   (void)CR;
  58   return StringRef(reinterpret_cast<char *>(Storage.begin()),
  59                    Begin8 - Storage.begin());
  60 }
  61
  62 static UTF32 foldCharDwarf(UTF32 C) {
  63   // DWARF v5 addition to the unicode folding rules.
  64   // Fold "Latin Small Letter Dotless I" and "Latin Capital Letter I With Dot
  65   // Above" into "i".
  66   if (C == 0x130 || C == 0x131)
  67     return 'i';
  68   return sys::unicode::foldCharSimple(C);
  69 }
  70
  71 static uint32_t caseFoldingDjbHashCharSlow(StringRef &Buffer, uint32_t H) {
  72   UTF32 C = chopOneUTF32(Buffer);
  73
  74   C = foldCharDwarf(C);
  75
  76   std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;
  77   StringRef Folded = toUTF8(C, Storage);
  78   return djbHash(Folded, H);
  79 }
  80
  81 uint32_t llvm::caseFoldingDjbHash(StringRef Buffer, uint32_t H) {
  82   while (!Buffer.empty()) {
  83     unsigned char C = Buffer.front();
  84     if (LLVM_LIKELY(C <= 0x7f)) {
  85       // US-ASCII, encoded as one character in utf-8.
  86       // This is by far the most common case, so handle this specially.
  87       if (C >= 'A' && C <= 'Z')
  88         C = 'a' + (C - 'A'); // fold uppercase into lowercase
  89       H = djbHashChar(C, H);
  90       Buffer = Buffer.drop_front();
  91       continue;
  92     }
  93     H = caseFoldingDjbHashCharSlow(Buffer, H);
  94   }
  95   return H;
  96 }