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 template <>
58 inline std::tuple<uint32_t, size_t, bool> DecodeUnsigned<uint32_t>(const uint8_t *data)
59 {
60 constexpr size_t LEB128_BYTE2_SHIFT = 7U;
61 constexpr size_t LEB128_BYTE3_SHIFT = 14U;
62 constexpr size_t LEB128_BYTE4_SHIFT = 21U;
63 constexpr size_t LEB128_BYTE5_SHIFT = 28U;
64 constexpr size_t LEB128_BYTE5_BIT_SIZE = 4;
65
66 bool valid = true;
67 const uint8_t *p = data;
68 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
69 uint32_t result = *(p++);
70 if (UNLIKELY(result > PAYLOAD_MASK)) {
71 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
72 uint32_t byte = *(p++);
73 result = (result & PAYLOAD_MASK) | ((byte & PAYLOAD_MASK) << LEB128_BYTE2_SHIFT);
74 if (byte > PAYLOAD_MASK) {
75 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
76 byte = *(p++);
77 result |= (byte & PAYLOAD_MASK) << LEB128_BYTE3_SHIFT;
78 if (byte > PAYLOAD_MASK) {
79 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
80 byte = *(p++);
81 result |= (byte & PAYLOAD_MASK) << LEB128_BYTE4_SHIFT;
82 if (byte > PAYLOAD_MASK) {
83 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
84 byte = *(p++);
85 valid = byte < (1U << LEB128_BYTE5_BIT_SIZE);
86 result |= byte << LEB128_BYTE5_SHIFT;
87 }
88 }
89 }
90 }
91 return {result, p - data, valid};
92 }
93
94 template <class T>
DecodeSigned(const uint8_t * data)95 inline std::tuple<T, size_t, bool> DecodeSigned(const uint8_t *data)
96 {
97 static_assert(std::is_signed_v<T>, "T must be signed");
98
99 T result = 0;
100
101 using unsigned_type = std::make_unsigned_t<T>;
102
103 constexpr size_t BITWIDTH = std::numeric_limits<unsigned_type>::digits;
104 constexpr size_t N = (BITWIDTH + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
105
106 for (size_t i = 0; i < N; i++) {
107 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
108 uint8_t byte = data[i];
109 size_t shift = i * PAYLOAD_WIDTH;
110 // NOLINTNEXTLINE(hicpp-signed-bitwise)
111 result |= static_cast<unsigned_type>(byte & PAYLOAD_MASK) << shift;
112
113 if ((byte & EXTENSION_BIT) == 0) {
114 shift = BITWIDTH - shift;
115 // NOLINTNEXTLINE(hicpp-signed-bitwise)
116 int8_t signed_extended = static_cast<int8_t>(byte << 1) >> 1;
117 // NOLINTNEXTLINE(hicpp-signed-bitwise)
118 uint8_t masked = (signed_extended ^ (signed_extended >> PAYLOAD_WIDTH)) | 1;
119 bool is_full = MinimumBitsToStore(masked) <= shift;
120 if (shift > PAYLOAD_WIDTH) {
121 shift -= PAYLOAD_WIDTH;
122 // NOLINTNEXTLINE(hicpp-signed-bitwise)
123 result = static_cast<T>(result << shift) >> shift;
124 }
125 return {result, i + 1, is_full};
126 }
127 }
128
129 return {result, N, false};
130 }
131
132 template <class T>
EncodeUnsigned(T data,uint8_t * out)133 inline size_t EncodeUnsigned(T data, uint8_t *out)
134 {
135 size_t i = 0;
136 uint8_t byte = data & PAYLOAD_MASK;
137 data >>= PAYLOAD_WIDTH;
138
139 while (data != 0) {
140 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
141 out[i++] = byte | EXTENSION_BIT;
142 byte = data & PAYLOAD_MASK;
143 data >>= PAYLOAD_WIDTH;
144 }
145
146 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
147 return i;
148 }
149
150 template <class T>
EncodeSigned(T data,uint8_t * out)151 inline size_t EncodeSigned(T data, uint8_t *out)
152 {
153 static_assert(std::is_signed_v<T>, "T must be signed");
154
155 size_t i = 0;
156 bool more = true;
157
158 while (more) {
159 auto byte = static_cast<uint8_t>(static_cast<size_t>(data) & PAYLOAD_MASK);
160 // NOLINTNEXTLINE(hicpp-signed-bitwise)
161 data >>= PAYLOAD_WIDTH;
162 more = !((data == 0 && (byte & SIGN_BIT) == 0) || (data == -1 && (byte & SIGN_BIT) != 0));
163 if (more) {
164 byte |= EXTENSION_BIT;
165 }
166 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
167 }
168
169 return i;
170 }
171
172 template <class T>
UnsignedEncodingSize(T data)173 inline size_t UnsignedEncodingSize(T data)
174 {
175 return (MinimumBitsToStore(data | 1U) + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
176 }
177
178 template <class T>
SignedEncodingSize(T data)179 inline size_t SignedEncodingSize(T data)
180 {
181 // NOLINTNEXTLINE(hicpp-signed-bitwise)
182 data = data ^ (data >> (std::numeric_limits<T>::digits - 1));
183 using unsigned_type = std::make_unsigned_t<T>;
184 auto udata = static_cast<unsigned_type>(data);
185 return MinimumBitsToStore(static_cast<unsigned_type>(udata | 1U)) / PAYLOAD_WIDTH + 1;
186 }
187
188 } // namespace panda::leb128
189
190 #endif // LIBPANDABASE_UTILS_LEB128_H
191