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.
DecodeFixed32(const char * ptr)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
DecodeFixed64(const char * ptr)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.
ByteAs32(char c)44 static inline uint32_t ByteAs32(char c) { return static_cast<uint32_t>(c) & 0xff; }
ByteAs64(char c)45 static inline uint64_t ByteAs64(char c) { return static_cast<uint64_t>(c) & 0xff; }
46
47 } // namespace
48
Hash32(const char * data,size_t n,uint32_t seed)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
Hash64(const char * data,size_t n,uint64_t seed)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