1 // Copyright 2002 Google Inc. 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 //
17 // Derived from code by Moses Charikar
18
19 #include "s2/util/bits/bits.h"
20
21 #include <cassert>
22 #include "absl/numeric/int128.h"
23
24 using absl::uint128;
25
26 // this array gives the number of bits for any number from 0 to 255
27 // (We could make these ints. The tradeoff is size (eg does it overwhelm
28 // the cache?) vs efficiency in referencing sub-word-sized array elements)
29 const char Bits::num_bits[] = {
30 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
31 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
32 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
33 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
34 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
35 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
36 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
37 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
38 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
39 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
40 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
41 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
42 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
43 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
44 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
45 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };
46
Count(const void * m,int num_bytes)47 int Bits::Count(const void *m, int num_bytes) {
48 int nbits = 0;
49 const uint8 *s = (const uint8 *) m;
50 for (int i = 0; i < num_bytes; i++)
51 nbits += num_bits[*s++];
52 return nbits;
53 }
54
Difference(const void * m1,const void * m2,int num_bytes)55 int Bits::Difference(const void *m1, const void *m2, int num_bytes) {
56 int nbits = 0;
57 const uint8 *s1 = (const uint8 *) m1;
58 const uint8 *s2 = (const uint8 *) m2;
59 for (int i = 0; i < num_bytes; i++)
60 nbits += num_bits[(*s1++) ^ (*s2++)];
61 return nbits;
62 }
63
CappedDifference(const void * m1,const void * m2,int num_bytes,int cap)64 int Bits::CappedDifference(const void *m1, const void *m2,
65 int num_bytes, int cap) {
66 int nbits = 0;
67 const uint8 *s1 = (const uint8 *) m1;
68 const uint8 *s2 = (const uint8 *) m2;
69 for (int i = 0; i < num_bytes && nbits <= cap; i++)
70 nbits += num_bits[(*s1++) ^ (*s2++)];
71 return nbits;
72 }
73
Log2Floor_Portable(uint32 n)74 int Bits::Log2Floor_Portable(uint32 n) {
75 if (n == 0)
76 return -1;
77 int log = 0;
78 uint32 value = n;
79 for (int i = 4; i >= 0; --i) {
80 int shift = (1 << i);
81 uint32 x = value >> shift;
82 if (x != 0) {
83 value = x;
84 log += shift;
85 }
86 }
87 assert(value == 1);
88 return log;
89 }
90
Log2Ceiling(uint32 n)91 int Bits::Log2Ceiling(uint32 n) {
92 int floor = Log2Floor(n);
93 if ((n & (n - 1)) == 0) // zero or a power of two
94 return floor;
95 else
96 return floor + 1;
97 }
98
Log2Ceiling64(uint64 n)99 int Bits::Log2Ceiling64(uint64 n) {
100 int floor = Log2Floor64(n);
101 if ((n & (n - 1)) == 0) // zero or a power of two
102 return floor;
103 else
104 return floor + 1;
105 }
106
Log2Ceiling128(absl::uint128 n)107 int Bits::Log2Ceiling128(absl::uint128 n) {
108 int floor = Log2Floor128(n);
109 if ((n & (n - 1)) == 0) // zero or a power of two
110 return floor;
111 else
112 return floor + 1;
113 }
114
FindLSBSetNonZero_Portable(uint32 n)115 int Bits::FindLSBSetNonZero_Portable(uint32 n) {
116 int rc = 31;
117 for (int i = 4, shift = 1 << 4; i >= 0; --i) {
118 const uint32 x = n << shift;
119 if (x != 0) {
120 n = x;
121 rc -= shift;
122 }
123 shift >>= 1;
124 }
125 return rc;
126 }
127
CountLeadingZeros32_Portable(uint32 n)128 int Bits::CountLeadingZeros32_Portable(uint32 n) {
129 int bits = 1;
130 if (n == 0)
131 return 32;
132 if ((n >> 16) == 0) {
133 bits += 16;
134 n <<= 16;
135 }
136 if ((n >> 24) == 0) {
137 bits += 8;
138 n <<= 8;
139 }
140 if ((n >> 28) == 0) {
141 bits += 4;
142 n <<= 4;
143 }
144 if ((n >> 30) == 0) {
145 bits += 2;
146 n <<= 2;
147 }
148 return bits - (n >> 31);
149 }
150
CountLeadingZeros64_Portable(uint64 n)151 int Bits::CountLeadingZeros64_Portable(uint64 n) {
152 return ((n >> 32)
153 ? Bits::CountLeadingZeros32_Portable(n >> 32)
154 : 32 + Bits::CountLeadingZeros32_Portable(n));
155 }
156