1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
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 #ifndef LIBPANDABASE_UTILS_LEB128_H
17 #define LIBPANDABASE_UTILS_LEB128_H
18
19 #include "bit_helpers.h"
20 #include "bit_utils.h"
21
22 #include <limits>
23 #include <tuple>
24
25 namespace panda::leb128 {
26
27 constexpr size_t PAYLOAD_WIDTH = 7;
28 constexpr size_t PAYLOAD_MASK = 0x7f;
29 constexpr size_t EXTENSION_BIT = 0x80;
30 constexpr size_t SIGN_BIT = 0x40;
31
32 template <class T>
DecodeUnsigned(const uint8_t * data)33 inline std::tuple<T, size_t, bool> DecodeUnsigned(const uint8_t *data)
34 {
35 static_assert(std::is_unsigned_v<T>, "T must be unsigned");
36
37 T result = 0;
38
39 constexpr size_t BITWIDTH = std::numeric_limits<T>::digits;
40 constexpr size_t N = (BITWIDTH + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
41
42 for (size_t i = 0; i < N; i++) {
43 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
44 uint8_t byte = data[i] & PAYLOAD_MASK;
45 size_t shift = i * PAYLOAD_WIDTH;
46 result |= static_cast<T>(byte) << shift;
47 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
48 if ((data[i] & EXTENSION_BIT) == 0) {
49 bool is_full = MinimumBitsToStore(byte) <= (BITWIDTH - shift);
50 return {result, i + 1, is_full};
51 }
52 }
53
54 return {result, N, false};
55 }
56
57 #if defined(PANDA_TARGET_ARM64) && !(PANDA_TARGET_MACOS)
58
59 template <>
60 inline std::tuple<uint32_t, size_t, bool> DecodeUnsigned<uint32_t>(const uint8_t *data)
61 {
62 if (LIKELY(!(data[0] & 0x80))) {
63 return {data[0], 1, true};
64 }
65
66 uint64_t rev = 0;
67 constexpr size_t LEB128_PAGE_SIZE = 4096;
68 constexpr size_t LEB128_PREFETCH_SIZE = 8;
69 constexpr size_t LEB128_BITS_PER_BYTE = 8;
70 bool read_pass_end_of_page = ((uintptr_t)data & (LEB128_PAGE_SIZE-1)) > LEB128_PAGE_SIZE - LEB128_PREFETCH_SIZE;
71 if (UNLIKELY(read_pass_end_of_page)) {
72 int i = -1;
73 do {
74 i++;
75 rev |= (uint64_t)(data[i]) << (LEB128_BITS_PER_BYTE * i);
76 } while (data[i] & 0x80);
77 } else {
78 rev = ((uint64_t *)data)[0];
79 }
80 uint64_t lenbit = (~rev) & (0x8080808080);
81 uint64_t len = (__builtin_ctz(lenbit) >> 3) + 1;
82 uint64_t valid_rev = rev & (lenbit ^ (lenbit - 1));
83
84 uint32_t result = (valid_rev & 0x7f) | ((valid_rev & 0x7f00) >> 1) | ((valid_rev & 0x7f0000) >> 2) |
85 ((valid_rev & 0x7f000000) >> 3) | ((valid_rev & 0x0f00000000) >> 4);
86 return {result, len, !(valid_rev & 0xf000000000)};
87 }
88
89 #else
90
91 template <>
92 inline std::tuple<uint32_t, size_t, bool> DecodeUnsigned<uint32_t>(const uint8_t *data)
93 {
94 constexpr size_t LEB128_BYTE2_SHIFT = 7U;
95 constexpr size_t LEB128_BYTE3_SHIFT = 14U;
96 constexpr size_t LEB128_BYTE4_SHIFT = 21U;
97 constexpr size_t LEB128_BYTE5_SHIFT = 28U;
98 constexpr size_t LEB128_BYTE5_BIT_SIZE = 4;
99
100 bool valid = true;
101 const uint8_t *p = data;
102 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
103 uint32_t result = *(p++);
104 if (UNLIKELY(result > PAYLOAD_MASK)) {
105 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
106 uint32_t byte = *(p++);
107 result = (result & PAYLOAD_MASK) | ((byte & PAYLOAD_MASK) << LEB128_BYTE2_SHIFT);
108 if (byte > PAYLOAD_MASK) {
109 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
110 byte = *(p++);
111 result |= (byte & PAYLOAD_MASK) << LEB128_BYTE3_SHIFT;
112 if (byte > PAYLOAD_MASK) {
113 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
114 byte = *(p++);
115 result |= (byte & PAYLOAD_MASK) << LEB128_BYTE4_SHIFT;
116 if (byte > PAYLOAD_MASK) {
117 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
118 byte = *(p++);
119 valid = byte < (1U << LEB128_BYTE5_BIT_SIZE);
120 result |= byte << LEB128_BYTE5_SHIFT;
121 }
122 }
123 }
124 }
125 return {result, p - data, valid};
126 }
127
128 #endif
129
130 template <class T>
DecodeSigned(const uint8_t * data)131 inline std::tuple<T, size_t, bool> DecodeSigned(const uint8_t *data)
132 {
133 static_assert(std::is_signed_v<T>, "T must be signed");
134
135 T result = 0;
136
137 using unsigned_type = std::make_unsigned_t<T>;
138
139 constexpr size_t BITWIDTH = std::numeric_limits<unsigned_type>::digits;
140 constexpr size_t N = (BITWIDTH + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
141
142 for (size_t i = 0; i < N; i++) {
143 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
144 uint8_t byte = data[i];
145 size_t shift = i * PAYLOAD_WIDTH;
146 // NOLINTNEXTLINE(hicpp-signed-bitwise)
147 result |= static_cast<unsigned_type>(byte & PAYLOAD_MASK) << shift;
148
149 if ((byte & EXTENSION_BIT) == 0) {
150 shift = BITWIDTH - shift;
151 // NOLINTNEXTLINE(hicpp-signed-bitwise)
152 int8_t signed_extended = static_cast<int8_t>(byte << 1) >> 1;
153 // NOLINTNEXTLINE(hicpp-signed-bitwise)
154 uint8_t masked = (signed_extended ^ (signed_extended >> PAYLOAD_WIDTH)) | 1;
155 bool is_full = MinimumBitsToStore(masked) <= shift;
156 if (shift > PAYLOAD_WIDTH) {
157 shift -= PAYLOAD_WIDTH;
158 // NOLINTNEXTLINE(hicpp-signed-bitwise)
159 result = static_cast<T>(result << shift) >> shift;
160 }
161 return {result, i + 1, is_full};
162 }
163 }
164
165 return {result, N, false};
166 }
167
168 template <class T>
EncodeUnsigned(T data,uint8_t * out)169 inline size_t EncodeUnsigned(T data, uint8_t *out)
170 {
171 size_t i = 0;
172 uint8_t byte = data & PAYLOAD_MASK;
173 data >>= PAYLOAD_WIDTH;
174
175 while (data != 0) {
176 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
177 out[i++] = byte | EXTENSION_BIT;
178 byte = data & PAYLOAD_MASK;
179 data >>= PAYLOAD_WIDTH;
180 }
181
182 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
183 return i;
184 }
185
186 template <class T>
EncodeSigned(T data,uint8_t * out)187 inline size_t EncodeSigned(T data, uint8_t *out)
188 {
189 static_assert(std::is_signed_v<T>, "T must be signed");
190
191 size_t i = 0;
192 bool more = true;
193
194 while (more) {
195 auto byte = static_cast<uint8_t>(static_cast<size_t>(data) & PAYLOAD_MASK);
196 // NOLINTNEXTLINE(hicpp-signed-bitwise)
197 data >>= PAYLOAD_WIDTH;
198 more = !((data == 0 && (byte & SIGN_BIT) == 0) || (data == -1 && (byte & SIGN_BIT) != 0));
199 if (more) {
200 byte |= EXTENSION_BIT;
201 }
202 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
203 }
204
205 return i;
206 }
207
208 template <class T>
UnsignedEncodingSize(T data)209 inline size_t UnsignedEncodingSize(T data)
210 {
211 return (MinimumBitsToStore(data | 1U) + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
212 }
213
214 template <class T>
SignedEncodingSize(T data)215 inline size_t SignedEncodingSize(T data)
216 {
217 // NOLINTNEXTLINE(hicpp-signed-bitwise)
218 data = data ^ (data >> (std::numeric_limits<T>::digits - 1));
219 using unsigned_type = std::make_unsigned_t<T>;
220 auto udata = static_cast<unsigned_type>(data);
221 return MinimumBitsToStore(static_cast<unsigned_type>(udata | 1U)) / PAYLOAD_WIDTH + 1;
222 }
223
224 } // namespace panda::leb128
225
226 #endif // LIBPANDABASE_UTILS_LEB128_H
227