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