84 lines · cpp
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-exception6//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 for29 // 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 use42 // 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 Dot54 // Above" into "i".55 if (C == 0x130 || C == 0x131)56 return 'i';57 return sys::unicode::foldCharSimple(C);58}59 60static std::optional<uint32_t> fastCaseFoldingDjbHash(StringRef Buffer,61 uint32_t H) {62 bool AllASCII = true;63 for (unsigned char C : Buffer) {64 H = H * 33 + ('A' <= C && C <= 'Z' ? C - 'A' + 'a' : C);65 AllASCII &= C <= 0x7f;66 }67 if (AllASCII)68 return H;69 return std::nullopt;70}71 72uint32_t llvm::caseFoldingDjbHash(StringRef Buffer, uint32_t H) {73 if (std::optional<uint32_t> Result = fastCaseFoldingDjbHash(Buffer, H))74 return *Result;75 76 std::array<UTF8, UNI_MAX_UTF8_BYTES_PER_CODE_POINT> Storage;77 while (!Buffer.empty()) {78 UTF32 C = foldCharDwarf(chopOneUTF32(Buffer));79 StringRef Folded = toUTF8(C, Storage);80 H = djbHash(Folded, H);81 }82 return H;83}84