Home | History | Annotate | Download | only in hash 
      1 /* Copyright 2015 The TensorFlow Authors. All Rights Reserved.
      2 
      3 Licensed under the Apache License, Version 2.0 (the "License");
      4 you may not use this file except in compliance with the License.
      5 You may obtain a copy of the License at
      6 
      7     http://www.apache.org/licenses/LICENSE-2.0
      8 
      9 Unless required by applicable law or agreed to in writing, software
     10 distributed under the License is distributed on an "AS IS" BASIS,
     11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 See the License for the specific language governing permissions and
     13 limitations under the License.
     14 ==============================================================================*/
     15 
     16 #include "tensorflow/core/lib/hash/hash.h"
     17 
     18 #include "tensorflow/core/lib/core/raw_coding.h"
     19 #include "tensorflow/core/platform/macros.h"
     20 #include "tensorflow/core/platform/types.h"
     21 
     22 #include <string.h>
     23 
     24 namespace tensorflow {
     25 
     26 // 0xff is in case char is signed.
     27 static inline uint32 ByteAs32(char c) { return static_cast<uint32>(c) & 0xff; }
     28 static inline uint64 ByteAs64(char c) { return static_cast<uint64>(c) & 0xff; }
     29 
     30 uint32 Hash32(const char* data, size_t n, uint32 seed) {
     31   // 'm' and 'r' are mixing constants generated offline.
     32   // They're not really 'magic', they just happen to work well.
     33 
     34   const uint32 m = 0x5bd1e995;
     35   const int r = 24;
     36 
     37   // Initialize the hash to a 'random' value
     38   uint32 h = seed ^ n;
     39 
     40   // Mix 4 bytes at a time into the hash
     41   while (n >= 4) {
     42     uint32 k = core::DecodeFixed32(data);
     43 
     44     k *= m;
     45     k ^= k >> r;
     46     k *= m;
     47 
     48     h *= m;
     49     h ^= k;
     50 
     51     data += 4;
     52     n -= 4;
     53   }
     54 
     55   // Handle the last few bytes of the input array
     56 
     57   switch (n) {
     58     case 3:
     59       h ^= ByteAs32(data[2]) << 16;
     60       TF_FALLTHROUGH_INTENDED;
     61     case 2:
     62       h ^= ByteAs32(data[1]) << 8;
     63       TF_FALLTHROUGH_INTENDED;
     64     case 1:
     65       h ^= ByteAs32(data[0]);
     66       h *= m;
     67   }
     68 
     69   // Do a few final mixes of the hash to ensure the last few
     70   // bytes are well-incorporated.
     71 
     72   h ^= h >> 13;
     73   h *= m;
     74   h ^= h >> 15;
     75 
     76   return h;
     77 }
     78 
     79 uint64 Hash64(const char* data, size_t n, uint64 seed) {
     80   const uint64 m = 0xc6a4a7935bd1e995;
     81   const int r = 47;
     82 
     83   uint64 h = seed ^ (n * m);
     84 
     85   while (n >= 8) {
     86     uint64 k = core::DecodeFixed64(data);
     87     data += 8;
     88     n -= 8;
     89 
     90     k *= m;
     91     k ^= k >> r;
     92     k *= m;
     93 
     94     h ^= k;
     95     h *= m;
     96   }
     97 
     98   switch (n) {
     99     case 7:
    100       h ^= ByteAs64(data[6]) << 48;
    101       TF_FALLTHROUGH_INTENDED;
    102     case 6:
    103       h ^= ByteAs64(data[5]) << 40;
    104       TF_FALLTHROUGH_INTENDED;
    105     case 5:
    106       h ^= ByteAs64(data[4]) << 32;
    107       TF_FALLTHROUGH_INTENDED;
    108     case 4:
    109       h ^= ByteAs64(data[3]) << 24;
    110       TF_FALLTHROUGH_INTENDED;
    111     case 3:
    112       h ^= ByteAs64(data[2]) << 16;
    113       TF_FALLTHROUGH_INTENDED;
    114     case 2:
    115       h ^= ByteAs64(data[1]) << 8;
    116       TF_FALLTHROUGH_INTENDED;
    117     case 1:
    118       h ^= ByteAs64(data[0]);
    119       h *= m;
    120   }
    121 
    122   h ^= h >> r;
    123   h *= m;
    124   h ^= h >> r;
    125 
    126   return h;
    127 }
    128 
    129 bool SerializeToStringDeterministic(const protobuf::MessageLite& msg,
    130                                     string* result) {
    131   const size_t size = msg.ByteSizeLong();
    132   *result = string(size, '\0');
    133   protobuf::io::ArrayOutputStream array_stream(&(*result)[0], size);
    134   protobuf::io::CodedOutputStream output_stream(&array_stream);
    135   output_stream.SetSerializationDeterministic(true);
    136   msg.SerializeWithCachedSizes(&output_stream);
    137   return !output_stream.HadError() && size == output_stream.ByteCount();
    138 }
    139 
    140 }  // namespace tensorflow
    141