1 // Copyright (C) 2019 Google LLC
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 // Copyright 2012 Google Inc. All Rights Reserved.
16 // Author: [email protected] (Ulas Kirazci)
17 //
18 // Utilities for fiddling bits.
19
20 #ifndef ICING_LEGACY_INDEX_ICING_BIT_UTIL_H_
21 #define ICING_LEGACY_INDEX_ICING_BIT_UTIL_H_
22
23 #include <cstdint>
24 #include <cstdio>
25 #include <limits>
26 #include <vector>
27
28 namespace icing {
29 namespace lib {
30
31 // Manipulating bit fields.
32 //
33 // x value containing the bit field(s)
34 // offset offset of bit field in x
35 // len len of bit field in x
36 //
37 // REQUIREMENTS
38 //
39 // - x an unsigned integer <= 64 bits
40 // - offset + len <= sizeof(x) * 8
41 //
42 // There is no error checking so you will get garbage if you don't
43 // ensure the above.
44 //
45 // To set a value, use BITFIELD_CLEAR then BITFIELD_OR.
46
47 // Shifting by more than the word length is undefined (on ARM it has the
48 // intended effect, but on Intel it shifts by % word length), so check the
49 // length).
50 #define BITFIELD_MASK(len) ((len == 0) ? 0U : ((~uint64_t{0}) >> (64 - (len))))
51 #define BITFIELD_GET(x, offset, len) (((x) >> (offset)) & BITFIELD_MASK(len))
52 // The following modify x.
53 #define BITFIELD_CLEAR(x, offset, len) (x) &= ~(BITFIELD_MASK(len) << (offset))
54 // We conservatively mask val at len so x won't be corrupted if val >=
55 // 1 << len.
56 #define BITFIELD_OR(x, offset, len, val) \
57 (x) |= (uint64_t{val} & BITFIELD_MASK(len)) << (offset)
58
59 // Number of bits needed to store the range [0, n).
BitsToStore(uint32_t n)60 inline uint8_t BitsToStore(uint32_t n) {
61 if (n <= 1) {
62 return 0;
63 } else {
64 return 32 - __builtin_clz(n - 1);
65 }
66 }
67
68 #define ALIGN_UP(n, alignment) \
69 ((((n) + (alignment)-1) / (alignment)) * (alignment))
70
71 // Align up to a multiple.
AlignUp(uint64_t n,uint64_t alignment)72 inline uint64_t AlignUp(uint64_t n, uint64_t alignment) {
73 return ALIGN_UP(n, alignment);
74 }
75
SumOverflowsUint32(std::vector<uint64_t> values)76 inline bool SumOverflowsUint32(std::vector<uint64_t> values) {
77 uint64_t sum = 0L;
78 for (uint64_t value : values) {
79 sum += value;
80 }
81 return sum > std::numeric_limits<uint32_t>::max();
82 }
83
84 // VarInt (See
85 // https://developers.google.com/protocol-buffers/docs/encoding)
86 #define VAR_INT_MAX_ENCODED_LEN(n_size) (ALIGN_UP(8 * (n_size), 7) / 7)
87
88 class VarInt {
89 public:
90 // 7 bits per byte.
MaxEncodedLen(size_t n_size)91 static size_t MaxEncodedLen(size_t n_size) {
92 return VAR_INT_MAX_ENCODED_LEN(n_size);
93 }
94 static const int kMaxEncodedLen64 = VAR_INT_MAX_ENCODED_LEN(8);
95
96 // Encode n into buf. Return encoded len. buf must be at least
97 // kMaxEncodedLen64 long.
Encode(uint64_t n,uint8_t * buf)98 static size_t Encode(uint64_t n, uint8_t *buf) {
99 uint8_t *start = buf;
100 do {
101 *buf = 0x80 | (n & 0x7f);
102 n >>= 7;
103 buf++;
104 } while (n);
105 // buf is one past last byte. Last byte must have MSB cleared.
106 *(buf - 1) &= 0x7f;
107 return buf - start;
108 }
109
110 // Decode buf into unsigned integral type pn. Return length
111 // decoded. buf must terminate with a byte with MSB cleared. No
112 // error checking is done but if buf is null-terminated, Decode
113 // won't crash. If decoded doesn't fit into *pn higher order bits
114 // will be dropped.
115 template <class T>
Decode(const uint8_t * buf,T * pn)116 static size_t Decode(const uint8_t *buf, T *pn) {
117 const uint8_t *start = buf;
118 *pn = 0;
119 int offset = 0;
120 while ((*buf & 0x80)) {
121 *pn |= static_cast<T>(*buf & 0x7f) << offset;
122 offset += 7;
123 buf++;
124 }
125 // Last byte.
126 *pn |= static_cast<T>(*buf) << offset;
127 // Buf is pointing to last byte, not one off the end.
128 return buf - start + 1;
129 }
130 };
131
132 } // namespace lib
133 } // namespace icing
134
135 #endif // ICING_LEGACY_INDEX_ICING_BIT_UTIL_H_
136