Home | History | Annotate | Download | only in math 
      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.
     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.
     36 static inline uint32 ByteAs32(char c) { return static_cast<uint32>(c) & 0xff; }
     37 }  // namespace
     38 
     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