1 /*
2 * Copyright (c) 2021 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 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 <class T>
DecodeSigned(const uint8_t * data)58 inline std::tuple<T, size_t, bool> DecodeSigned(const uint8_t *data)
59 {
60 static_assert(std::is_signed_v<T>, "T must be signed");
61
62 T result = 0;
63
64 using unsigned_type = std::make_unsigned_t<T>;
65
66 constexpr size_t BITWIDTH = std::numeric_limits<unsigned_type>::digits;
67 constexpr size_t N = (BITWIDTH + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
68
69 for (size_t i = 0; i < N; i++) {
70 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
71 uint8_t byte = data[i];
72 size_t shift = i * PAYLOAD_WIDTH;
73 // NOLINTNEXTLINE(hicpp-signed-bitwise)
74 result |= static_cast<unsigned_type>(byte & PAYLOAD_MASK) << shift;
75
76 if ((byte & EXTENSION_BIT) == 0) {
77 shift = BITWIDTH - shift;
78 // NOLINTNEXTLINE(hicpp-signed-bitwise)
79 int8_t signed_extended = static_cast<int8_t>(byte << 1) >> 1;
80 // NOLINTNEXTLINE(hicpp-signed-bitwise)
81 uint8_t masked = (signed_extended ^ (signed_extended >> PAYLOAD_WIDTH)) | 1;
82 bool is_full = MinimumBitsToStore(masked) <= shift;
83 if (shift > PAYLOAD_WIDTH) {
84 shift -= PAYLOAD_WIDTH;
85 // NOLINTNEXTLINE(hicpp-signed-bitwise)
86 result = static_cast<T>(result << shift) >> shift;
87 }
88 return {result, i + 1, is_full};
89 }
90 }
91
92 return {result, N, false};
93 }
94
95 template <class T>
EncodeUnsigned(T data,uint8_t * out)96 inline size_t EncodeUnsigned(T data, uint8_t *out)
97 {
98 static_assert(std::is_unsigned_v<T>, "T must be unsigned");
99
100 size_t i = 0;
101 uint8_t byte = data & PAYLOAD_MASK;
102 data >>= PAYLOAD_WIDTH;
103
104 while (data != 0) {
105 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
106 out[i++] = byte | EXTENSION_BIT;
107 byte = data & PAYLOAD_MASK;
108 data >>= PAYLOAD_WIDTH;
109 }
110
111 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
112 return i;
113 }
114
115 template <class T>
EncodeSigned(T data,uint8_t * out)116 inline size_t EncodeSigned(T data, uint8_t *out)
117 {
118 static_assert(std::is_signed_v<T>, "T must be signed");
119
120 size_t i = 0;
121 bool more = true;
122
123 while (more) {
124 auto byte = static_cast<uint8_t>(static_cast<size_t>(data) & PAYLOAD_MASK);
125 // NOLINTNEXTLINE(hicpp-signed-bitwise)
126 data >>= PAYLOAD_WIDTH;
127 more = !((data == 0 && (byte & SIGN_BIT) == 0) || (data == -1 && (byte & SIGN_BIT) != 0));
128 if (more) {
129 byte |= EXTENSION_BIT;
130 }
131 out[i++] = byte; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
132 }
133
134 return i;
135 }
136
137 template <class T>
UnsignedEncodingSize(T data)138 inline size_t UnsignedEncodingSize(T data)
139 {
140 return (MinimumBitsToStore(data | 1U) + PAYLOAD_WIDTH - 1) / PAYLOAD_WIDTH;
141 }
142
143 template <class T>
SignedEncodingSize(T data)144 inline size_t SignedEncodingSize(T data)
145 {
146 // NOLINTNEXTLINE(hicpp-signed-bitwise)
147 data = data ^ (data >> (std::numeric_limits<T>::digits - 1));
148 using unsigned_type = std::make_unsigned_t<T>;
149 auto udata = static_cast<unsigned_type>(data);
150 return MinimumBitsToStore(static_cast<unsigned_type>(udata | 1U)) / PAYLOAD_WIDTH + 1;
151 }
152
153 } // namespace panda::leb128
154
155 #endif // PANDA_LIBPANDABASE_UTILS_LEB128_H_
156