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