1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "lang_id/common/math/hash.h"
18 
19 #include "lang_id/common/lite_base/macros.h"
20 
21 namespace libtextclassifier3 {
22 namespace mobile {
23 namespace utils {
24 
25 namespace {
26 // Lower-level versions of Get... that read directly from a character buffer
27 // without any bounds checking.
DecodeFixed32(const char * ptr)28 inline uint32 DecodeFixed32(const char *ptr) {
29   return ((static_cast<uint32>(static_cast<unsigned char>(ptr[0]))) |
30           (static_cast<uint32>(static_cast<unsigned char>(ptr[1])) << 8) |
31           (static_cast<uint32>(static_cast<unsigned char>(ptr[2])) << 16) |
32           (static_cast<uint32>(static_cast<unsigned char>(ptr[3])) << 24));
33 }
34 
35 // 0xff is in case char is signed.
ByteAs32(char c)36 static inline uint32 ByteAs32(char c) { return static_cast<uint32>(c) & 0xff; }
37 }  // namespace
38 
Hash32(const char * data,size_t n,uint32 seed)39 uint32 Hash32(const char *data, size_t n, uint32 seed) {
40   // 'm' and 'r' are mixing constants generated offline.
41   // They're not really 'magic', they just happen to work well.
42   const uint32 m = 0x5bd1e995;
43   const int r = 24;
44 
45   // Initialize the hash to a 'random' value
46   uint32 h = seed ^ n;
47 
48   // Mix 4 bytes at a time into the hash
49   while (n >= 4) {
50     uint32 k = DecodeFixed32(data);
51     k *= m;
52     k ^= k >> r;
53     k *= m;
54     h *= m;
55     h ^= k;
56     data += 4;
57     n -= 4;
58   }
59 
60   // Handle the last few bytes of the input array
61   switch (n) {
62     case 3:
63       h ^= ByteAs32(data[2]) << 16;
64       SAFTM_FALLTHROUGH_INTENDED;
65     case 2:
66       h ^= ByteAs32(data[1]) << 8;
67       SAFTM_FALLTHROUGH_INTENDED;
68     case 1:
69       h ^= ByteAs32(data[0]);
70       h *= m;
71   }
72 
73   // Do a few final mixes of the hash to ensure the last few
74   // bytes are well-incorporated.
75   h ^= h >> 13;
76   h *= m;
77   h ^= h >> 15;
78   return h;
79 }
80 
81 }  // namespace utils
82 }  // namespace mobile
83 }  // namespace nlp_saft
84