1 /**
2 * Copyright (c) 2021-2025 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 PANDA_LIBPANDABASE_UTILS_LEB128_H_
17 #define PANDA_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 ark::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>
33 // CC-OFFNXT(G.FUD.06) perf critical
DecodeUnsigned(const uint8_t * data)34 inline std::tuple<T, size_t, bool> DecodeUnsigned(const uint8_t *data)
35 {
36 static_assert(std::is_unsigned_v<T>, "T must be unsigned");
37
38 T result = 0;
39
40 constexpr size_t BITWIDTH = std::numeric_limits<T>::digits;
41 constexpr size_t N = (BITWIDTH + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
42
43 for (size_t i = 0; i < N; i++) {
44 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
45 uint8_t byte = data[i] & PAYLOAD_MASK;
46 size_t shift = i * PAYLOAD_WIDTH;
47 // NOLINTNEXTLINE(hicpp-signed-bitwise)
48 result |= static_cast<T>(byte) << shift;
49 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
50 if ((data[i] & EXTENSION_BIT) == 0) {
51 bool isFull = MinimumBitsToStore(byte) <= (BITWIDTH - shift);
52 return {result, i + 1, isFull};
53 }
54 }
55
56 return {result, N, false};
57 }
58
59 template <>
60 // CC-OFFNXT(G.FUD.06) perf critical
61 inline std::tuple<uint32_t, size_t, bool> DecodeUnsigned<uint32_t>(const uint8_t *data)
62 {
63 constexpr size_t LEB128_BYTE2_SHIFT = 7U;
64 constexpr size_t LEB128_BYTE3_SHIFT = 14U;
65 constexpr size_t LEB128_BYTE4_SHIFT = 21U;
66 constexpr size_t LEB128_BYTE5_SHIFT = 28U;
67 constexpr size_t LEB128_BYTE5_BIT_SIZE = 4;
68
69 bool valid = true;
70 const uint8_t *p = data;
71 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
72 uint32_t result = *(p++);
73 if (UNLIKELY(result > PAYLOAD_MASK)) {
74 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
75 uint32_t byte = *(p++);
76 result = (result & PAYLOAD_MASK) | ((byte & PAYLOAD_MASK) << LEB128_BYTE2_SHIFT);
77
78 if (byte <= PAYLOAD_MASK) {
79 return {result, p - data, valid};
80 }
81 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
82 byte = *(p++);
83 result |= (byte & PAYLOAD_MASK) << LEB128_BYTE3_SHIFT;
84 if (byte <= PAYLOAD_MASK) {
85 return {result, p - data, valid};
86 }
87 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
88 byte = *(p++);
89 result |= (byte & PAYLOAD_MASK) << LEB128_BYTE4_SHIFT;
90 if (byte <= PAYLOAD_MASK) {
91 return {result, p - data, valid};
92 }
93 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
94 byte = *(p++);
95 valid = byte < (1U << LEB128_BYTE5_BIT_SIZE);
96 result |= byte << LEB128_BYTE5_SHIFT;
97 }
98 return {result, p - data, valid};
99 }
100
101 template <class T>
102 // CC-OFFNXT(G.FUD.06) perf critical
DecodeSigned(const uint8_t * data)103 inline std::tuple<T, size_t, bool> DecodeSigned(const uint8_t *data)
104 {
105 static_assert(std::is_signed_v<T>, "T must be signed");
106
107 T result = 0;
108
109 using UnsignedType = std::make_unsigned_t<T>;
110
111 constexpr size_t BITWIDTH = std::numeric_limits<UnsignedType>::digits;
112 constexpr size_t N = (BITWIDTH + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
113
114 for (size_t i = 0; i < N; i++) {
115 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
116 uint8_t byte = data[i];
117 size_t shift = i * PAYLOAD_WIDTH;
118 // NOLINTNEXTLINE(hicpp-signed-bitwise)
119 result |= static_cast<UnsignedType>(byte & PAYLOAD_MASK) << shift;
120
121 if ((byte & EXTENSION_BIT) == 0) {
122 shift = BITWIDTH - shift;
123 // NOLINTNEXTLINE(hicpp-signed-bitwise)
124 auto signedExtended = static_cast<int8_t>(static_cast<int8_t>(byte << 1) >> 1);
125 // NOLINTNEXTLINE(hicpp-signed-bitwise)
126 auto masked = static_cast<uint8_t>((signedExtended ^ (signedExtended >> PAYLOAD_WIDTH)) | 1);
127 bool isFull = MinimumBitsToStore(masked) <= shift;
128 if (shift > PAYLOAD_WIDTH) {
129 shift -= PAYLOAD_WIDTH;
130 // NOLINTNEXTLINE(hicpp-signed-bitwise)
131 result = static_cast<T>(result << shift) >> shift;
132 }
133 return {result, i + 1, isFull};
134 }
135 }
136
137 return {result, N, false};
138 }
139
140 template <class T>
EncodeUnsigned(T data,uint8_t * out)141 inline size_t EncodeUnsigned(T data, uint8_t *out)
142 {
143 size_t i = 0;
144 uint8_t byte = data & PAYLOAD_MASK;
145 data >>= PAYLOAD_WIDTH;
146
147 while (data != 0) {
148 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
149 out[i++] = byte | EXTENSION_BIT;
150 byte = data & PAYLOAD_MASK;
151 data >>= PAYLOAD_WIDTH;
152 }
153
154 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
155 return i;
156 }
157
158 template <class T>
159 // CC-OFFNXT(G.FUD.06) perf critical
EncodeSigned(T data,uint8_t * out)160 inline size_t EncodeSigned(T data, uint8_t *out)
161 {
162 static_assert(std::is_signed_v<T>, "T must be signed");
163
164 size_t i = 0;
165 bool more = true;
166
167 while (more) {
168 auto byte = static_cast<uint8_t>(static_cast<size_t>(data) & PAYLOAD_MASK);
169 // NOLINTNEXTLINE(hicpp-signed-bitwise)
170 data >>= PAYLOAD_WIDTH;
171 more = !((data == 0 && (byte & SIGN_BIT) == 0) || (data == -1 && (byte & SIGN_BIT) != 0));
172 if (more) {
173 byte |= EXTENSION_BIT;
174 }
175 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
176 }
177
178 return i;
179 }
180
181 template <class T>
UnsignedEncodingSize(T data)182 inline size_t UnsignedEncodingSize(T data)
183 {
184 return (MinimumBitsToStore(data | 1U) + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
185 }
186
187 template <class T>
SignedEncodingSize(T data)188 inline size_t SignedEncodingSize(T data)
189 {
190 // NOLINTNEXTLINE(hicpp-signed-bitwise)
191 data = data ^ (data >> (std::numeric_limits<T>::digits - 1));
192 using UnsignedType = std::make_unsigned_t<T>;
193 auto udata = static_cast<UnsignedType>(data);
194 return MinimumBitsToStore(static_cast<UnsignedType>(udata | 1U)) / PAYLOAD_WIDTH + 1;
195 }
196
197 } // namespace ark::leb128
198
199 #endif // PANDA_LIBPANDABASE_UTILS_LEB128_H_
200