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