1 /* 2 * Copyright (C) 2017 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 "hash.h" 18 19 #ifndef FALLTHROUGH_INTENDED 20 #define FALLTHROUGH_INTENDED [[fallthrough]] 21 #endif 22 23 namespace android { 24 namespace os { 25 namespace statsd { 26 27 namespace { 28 // Lower-level versions of Get... that read directly from a character buffer 29 // without any bounds checking. 30 inline uint32_t DecodeFixed32(const char *ptr) { 31 return ((static_cast<uint32_t>(static_cast<unsigned char>(ptr[0]))) | 32 (static_cast<uint32_t>(static_cast<unsigned char>(ptr[1])) << 8) | 33 (static_cast<uint32_t>(static_cast<unsigned char>(ptr[2])) << 16) | 34 (static_cast<uint32_t>(static_cast<unsigned char>(ptr[3])) << 24)); 35 } 36 37 inline uint64_t DecodeFixed64(const char* ptr) { 38 uint64_t lo = DecodeFixed32(ptr); 39 uint64_t hi = DecodeFixed32(ptr + 4); 40 return (hi << 32) | lo; 41 } 42 43 // 0xff is in case char is signed. 44 static inline uint32_t ByteAs32(char c) { return static_cast<uint32_t>(c) & 0xff; } 45 static inline uint64_t ByteAs64(char c) { return static_cast<uint64_t>(c) & 0xff; } 46 47 } // namespace 48 49 uint32_t Hash32(const char *data, size_t n, uint32_t seed) { 50 // 'm' and 'r' are mixing constants generated offline. 51 // They're not really 'magic', they just happen to work well. 52 const uint32_t m = 0x5bd1e995; 53 const int r = 24; 54 55 // Initialize the hash to a 'random' value 56 uint32_t h = static_cast<uint32_t>(seed ^ n); 57 58 // Mix 4 bytes at a time into the hash 59 while (n >= 4) { 60 uint32_t k = DecodeFixed32(data); 61 k *= m; 62 k ^= k >> r; 63 k *= m; 64 h *= m; 65 h ^= k; 66 data += 4; 67 n -= 4; 68 } 69 70 // Handle the last few bytes of the input array 71 switch (n) { 72 case 3: 73 h ^= ByteAs32(data[2]) << 16; 74 FALLTHROUGH_INTENDED; 75 case 2: 76 h ^= ByteAs32(data[1]) << 8; 77 FALLTHROUGH_INTENDED; 78 case 1: 79 h ^= ByteAs32(data[0]); 80 h *= m; 81 } 82 83 // Do a few final mixes of the hash to ensure the last few 84 // bytes are well-incorporated. 85 h ^= h >> 13; 86 h *= m; 87 h ^= h >> 15; 88 return h; 89 } 90 91 uint64_t Hash64(const char* data, size_t n, uint64_t seed) { 92 const uint64_t m = 0xc6a4a7935bd1e995; 93 const int r = 47; 94 95 uint64_t h = seed ^ (n * m); 96 97 while (n >= 8) { 98 uint64_t k = DecodeFixed64(data); 99 data += 8; 100 n -= 8; 101 102 k *= m; 103 k ^= k >> r; 104 k *= m; 105 106 h ^= k; 107 h *= m; 108 } 109 110 switch (n) { 111 case 7: 112 h ^= ByteAs64(data[6]) << 48; 113 FALLTHROUGH_INTENDED; 114 case 6: 115 h ^= ByteAs64(data[5]) << 40; 116 FALLTHROUGH_INTENDED; 117 case 5: 118 h ^= ByteAs64(data[4]) << 32; 119 FALLTHROUGH_INTENDED; 120 case 4: 121 h ^= ByteAs64(data[3]) << 24; 122 FALLTHROUGH_INTENDED; 123 case 3: 124 h ^= ByteAs64(data[2]) << 16; 125 FALLTHROUGH_INTENDED; 126 case 2: 127 h ^= ByteAs64(data[1]) << 8; 128 FALLTHROUGH_INTENDED; 129 case 1: 130 h ^= ByteAs64(data[0]); 131 h *= m; 132 } 133 134 h ^= h >> r; 135 h *= m; 136 h ^= h >> r; 137 138 return h; 139 } 140 } // namespace statsd 141 } // namespace os 142 } // namespace android 143
