HikoGUI
A low latency retained GUI
Loading...
Searching...
No Matches
base_n.hpp
1// Copyright Take Vos 2020-2022.
2// Distributed under the Boost Software License, Version 1.0.
3// (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
4
5#pragma once
6
7#include "../container/container.hpp"
8#include "../utility/utility.hpp"
9#include "../macros.hpp"
10#include <span>
11#include <cstdint>
12#include <array>
13#include <string>
14#include <string_view>
15#include <bit>
16#include <iterator>
17#include <format>
18
19hi_export_module(hikogui.codec.base_n);
20
21hi_export namespace hi::inline v1 {
22namespace detail {
23
25 long long radix;
26 bool case_insensitive;
27 char padding_char;
28 std::array<int8_t, 256> int_from_char_table = {};
29 std::array<char, 127> char_from_int_table = {};
30
36 template<std::size_t StringLength>
37 constexpr base_n_alphabet(
38 char const (&str)[StringLength],
39 bool case_insensitive = StringLength <= 33,
40 char padding_char = '\0') noexcept :
41 radix(narrow_cast<long long>(StringLength - 1)), case_insensitive(case_insensitive), padding_char(padding_char)
42 {
43 static_assert(StringLength < 128);
44
45 // Mark the int_from_char_table to have invalid characters.
46 for (long long i = 0; i != 256; ++i) {
47 int_from_char_table[i] = -2;
48 }
49
50 // Mark white-space in the int_from_char_table as white-space.
51 int_from_char_table[std::bit_cast<uint8_t>(' ')] = -1;
52 int_from_char_table[std::bit_cast<uint8_t>('\t')] = -1;
53 int_from_char_table[std::bit_cast<uint8_t>('\r')] = -1;
54 int_from_char_table[std::bit_cast<uint8_t>('\n')] = -1;
55 int_from_char_table[std::bit_cast<uint8_t>('\f')] = -1;
56
57 if (padding_char != 0) {
58 int_from_char_table[std::bit_cast<uint8_t>(padding_char)] = -1;
59 }
60
61 for (long long i = 0; i != radix; ++i) {
62 auto c = str[i];
63 char_from_int_table[i] = c;
64
65 int_from_char_table[std::bit_cast<uint8_t>(c)] = narrow_cast<int8_t>(i);
66 if constexpr (StringLength <= 33) {
67 // Add an extra entry for case folded form.
68 if (c >= 'a' && c <= 'z') {
69 int_from_char_table[narrow_cast<uint8_t>((c - 'a') + 'A')] = narrow_cast<int8_t>(i);
70 } else if (c >= 'A' && c <= 'Z') {
71 int_from_char_table[narrow_cast<uint8_t>((c - 'A') + 'a')] = narrow_cast<int8_t>(i);
72 }
73 }
74 }
75 }
76
80 constexpr char char_from_int(int8_t x) const noexcept
81 {
82 hi_axiom(x < radix);
83 return char_from_int_table[x];
84 }
85
86 constexpr int8_t int_from_char(char c) const noexcept
87 {
88 return int_from_char_table[std::bit_cast<uint8_t>(c)];
89 }
90};
91
92constexpr auto base2_alphabet = base_n_alphabet{"01"};
93
94constexpr auto base8_alphabet = base_n_alphabet{"01234567"};
95
96constexpr auto base10_alphabet = base_n_alphabet{"0123456789"};
97
98constexpr auto base16_alphabet = base_n_alphabet{"0123456789ABCDEF"};
99
100constexpr auto base32_rfc4648_alphabet = base_n_alphabet{"ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"};
101
102constexpr auto base32hex_rfc4648_alphabet = base_n_alphabet{"0123456789ABCDEFGHIJKLMNOPQRSTUV"};
103
104constexpr auto base64_rfc4648_alphabet =
105 base_n_alphabet{"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/", false, '='};
106
107constexpr auto base64url_rfc4648_alphabet =
108 base_n_alphabet{"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_", false, '='};
109
110constexpr auto base85_rfc1924_alphabet =
111 base_n_alphabet{"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~"};
112
113constexpr auto base85_btoa_alphabet =
114 base_n_alphabet{"!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstu"};
115
116} // namespace detail
117
118template<detail::base_n_alphabet Alphabet, int CharsPerBlock, int BytesPerBlock>
119class base_n {
120public:
121 constexpr static detail::base_n_alphabet alphabet = Alphabet;
122 constexpr static char padding_char = alphabet.padding_char;
123 constexpr static long long radix = alphabet.radix;
124 constexpr static long long bytes_per_block = BytesPerBlock;
125 constexpr static long long chars_per_block = CharsPerBlock;
126 static_assert(bytes_per_block != 0, "radix must be 16, 32, 64 or 85");
127 static_assert(chars_per_block != 0, "radix must be 16, 32, 64 or 85");
128
129 template<typename T>
130 constexpr static T int_from_char(char c) noexcept
131 {
132 return narrow_cast<T>(alphabet.int_from_char(c));
133 }
134
135 template<typename T>
136 constexpr static char char_from_int(T x) noexcept
137 {
138 return alphabet.char_from_int(narrow_cast<int8_t>(x));
139 }
140
147 template<typename ItIn, typename ItOut>
148 constexpr static void encode(ItIn ptr, ItIn last, ItOut output)
149 {
150 long long byte_index_in_block = 0;
151 long long block = 0;
152
153 while (ptr != last) {
154 // Construct a block in big endian.
155 auto const shift = 8 * ((bytes_per_block - 1) - byte_index_in_block);
156 block |= static_cast<long long>(*(ptr++)) << shift;
157
158 if (++byte_index_in_block == bytes_per_block) {
159 encode_block(block, bytes_per_block, output);
160 block = 0;
161 byte_index_in_block = 0;
162 }
163 }
164
165 if (byte_index_in_block != 0) {
166 encode_block(block, byte_index_in_block, output);
167 }
168 }
169
176 template<typename ItIn>
177 static std::string encode(ItIn first, ItIn last) noexcept
178 {
179 std::string r;
180 encode(first, last, std::back_inserter(r));
181 return r;
182 }
183
189 constexpr static std::string encode(std::span<std::byte const> bytes) noexcept
190 {
191 return encode(begin(bytes), end(bytes));
192 }
193
201 template<typename ItIn, typename ItOut>
202 constexpr static ItIn decode(ItIn ptr, ItIn last, ItOut output)
203 {
204 int char_index_in_block = 0;
205 long long block = 0;
206
207 for (; ptr != last; ++ptr) {
208 auto const digit = int_from_char<long long>(*ptr);
209 if (digit == -1) {
210 // Whitespace is ignored.
211 continue;
212
213 } else if (digit == -2) {
214 // Other character means end
215 return ptr;
216
217 } else {
218 block *= radix;
219 block += digit;
220
221 if (++char_index_in_block == chars_per_block) {
222 decode_block(block, chars_per_block, output);
223 block = 0;
224 char_index_in_block = 0;
225 }
226 }
227 }
228
229 if (char_index_in_block != 0) {
230 // pad the block with zeros.
231 for (auto i = char_index_in_block; i != chars_per_block; ++i) {
232 block *= radix;
233 }
234 decode_block(block, char_index_in_block, output);
235 }
236 return ptr;
237 }
238
239 static bstring decode(std::string_view str)
240 {
241 auto r = bstring{};
242 auto i = decode(begin(str), end(str), std::back_inserter(r));
243 hi_check(i == end(str), "base-n encoded string not completely decoded");
244 return r;
245 }
246
247private:
248 template<typename ItOut>
249 static void encode_block(long long block, long long nr_bytes, ItOut output) noexcept
250 {
251 auto const padding = bytes_per_block - nr_bytes;
252
253 // Construct a block in little-endian, using easy division/modulo.
254 auto char_block = std::string{};
255 for (long long i = 0; i != chars_per_block; ++i) {
256 auto const v = block % radix;
257 block /= radix;
258
259 if (i < padding) {
260 hi_assume(v != 0);
261 if (padding_char != 0) {
262 char_block += padding_char;
263 }
264 } else {
265 char_block += char_from_int(v);
266 }
267 }
268
269 // A block should be output as a big-endian radix-number.
270 std::copy(rbegin(char_block), rend(char_block), output);
271 }
272
273 template<typename ItOut>
274 constexpr static void decode_block(long long block, long long nr_chars, ItOut output)
275 {
276 auto const padding = chars_per_block - nr_chars;
277
278 if (block and bytes_per_block == padding) {
279 throw parse_error("Invalid number of character to decode.");
280 }
281
282 // Construct a block in little-endian, using easy division/modulo.
283 for (long long i = 0; i != (bytes_per_block - padding); ++i) {
284 auto const shift = 8 * ((bytes_per_block - 1) - i);
285 auto const byte = static_cast<std::byte>((block >> shift) & 0xff);
286
287 *(output++) = byte;
288 }
289
290 // The output data will not contain the padding.
291 }
292};
293
294// Alphabet, CharsPerBlock, BytesPerBlock
295hi_export using base2 = base_n<detail::base2_alphabet, 8, 1>;
296hi_export using base8 = base_n<detail::base8_alphabet, 8, 3>;
297hi_export using base16 = base_n<detail::base16_alphabet, 2, 1>;
298hi_export using base32 = base_n<detail::base32_rfc4648_alphabet, 8, 5>;
299hi_export using base32hex = base_n<detail::base32hex_rfc4648_alphabet, 8, 5>;
300hi_export using base64 = base_n<detail::base64_rfc4648_alphabet, 4, 3>;
301hi_export using base64url = base_n<detail::base64url_rfc4648_alphabet, 4, 3>;
302hi_export using base85 = base_n<detail::base85_rfc1924_alphabet, 5, 4>;
303hi_export using ascii85 = base_n<detail::base85_btoa_alphabet, 5, 4>;
304
305} // namespace hi::inline v1
DOXYGEN BUG.
Definition algorithm_misc.hpp:20
@ shift
The shift key is being held.
Definition base_n.hpp:24
constexpr base_n_alphabet(char const (&str)[StringLength], bool case_insensitive=StringLength<=33, char padding_char='\0') noexcept
Construct an alphabet.
Definition base_n.hpp:37
constexpr char char_from_int(int8_t x) const noexcept
Get a character from an integer.
Definition base_n.hpp:80
Definition base_n.hpp:119
static constexpr void encode(ItIn ptr, ItIn last, ItOut output)
Encode bytes into a string.
Definition base_n.hpp:148
static std::string encode(ItIn first, ItIn last) noexcept
Encode bytes into a string.
Definition base_n.hpp:177
static constexpr std::string encode(std::span< std::byte const > bytes) noexcept
Encode bytes into a string.
Definition base_n.hpp:189
static constexpr ItIn decode(ItIn ptr, ItIn last, ItOut output)
Decodes a UTF-8 string into bytes.
Definition base_n.hpp:202
T back_inserter(T... args)
T copy(T... args)