Home | History | Annotate | Line # | Download | only in Support 
      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 static 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 
     37 static 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 
     51 static 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 
     60 static 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 
     71 uint32_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