ipfs-chromium
basic_algorithm.h
1 /* From: https://github.com/lockblox/multibase
2  * Copyright (c) 2018 markovchainy
3  * MIT License
4  */
5 #pragma once
6 
7 // LCOV_EXCL_START
8 
9 #include <multibase/algorithm.h>
10 #include <multibase/encoding.h>
11 
12 #include <algorithm>
13 #include <array>
14 #include <cmath>
15 #include <ratio>
16 #include <vector>
17 
18 namespace multibase {
19 
20 template <encoding T>
21 struct traits {
22  static const std::array<char, 0> charset;
23  static const char name[];
24  static const char padding = 0;
26 };
27 
30 template <encoding T, typename Traits = traits<T>>
32  public:
33  class encoder : public algorithm {
34  public:
35  size_t output_size() override;
36  size_t block_size() override;
37  std::string process(std::string_view input) override;
38 
39  private:
40  constexpr size_t input_size() { return ratio.den; }
41  };
42 
43  class decoder : public algorithm {
44  public:
45  size_t output_size() override;
46  size_t block_size() override;
47  std::string process(std::string_view input) override;
48 
49  private:
50  constexpr size_t input_size() { return ratio.num; }
51  };
52 
53  private:
54  constexpr static auto first = Traits::charset.cbegin();
55  constexpr static auto last = Traits::charset.cend();
56  using CharsetT = decltype(Traits::charset);
57  using value_type = typename CharsetT::value_type;
58  using iterator = typename CharsetT::const_iterator;
59 
61  constexpr static iterator find(iterator b, iterator e,
62  value_type const& v) noexcept {
63  return (b != e && *b != v) ? find(++b, e, v) : b;
64  }
65 
68  constexpr static unsigned char getval(unsigned char p) noexcept {
69  return find(first, last, p) == last
70  ? static_cast<unsigned char>(255)
71  : static_cast<unsigned char>(
72  std::distance(first, find(first, last, p)));
73  }
74 
76  constexpr static std::intmax_t log2(std::intmax_t n) noexcept {
77  return (n == 1) ? 0 : ((n < 2) ? 1 : 1 + log2(n / 2));
78  }
79 
81  constexpr static auto radix = sizeof(Traits::charset) / sizeof(value_type);
83  constexpr static auto ratio = std::ratio<log2(256), log2(radix)>{};
85  static const std::array<unsigned char, 256> valset;
86 
87  constexpr static auto base = T;
88 };
89 
90 template <encoding T, typename Traits>
91 const std::array<unsigned char, 256> basic_algorithm<T, Traits>::valset = {
92  getval(0), getval(1), getval(2), getval(3), getval(4),
93  getval(5), getval(6), getval(7), getval(8), getval(9),
94  getval(10), getval(11), getval(12), getval(13), getval(14),
95  getval(15), getval(16), getval(17), getval(18), getval(19),
96  getval(20), getval(21), getval(22), getval(23), getval(24),
97  getval(25), getval(26), getval(27), getval(28), getval(29),
98  getval(30), getval(31), getval(32), getval(33), getval(34),
99  getval(35), getval(36), getval(37), getval(38), getval(39),
100  getval(40), getval(41), getval(42), getval(43), getval(44),
101  getval(45), getval(46), getval(47), getval(48), getval(49),
102  getval(50), getval(51), getval(52), getval(53), getval(54),
103  getval(55), getval(56), getval(57), getval(58), getval(59),
104  getval(60), getval(61), getval(62), getval(63), getval(64),
105  getval(65), getval(66), getval(67), getval(68), getval(69),
106  getval(70), getval(71), getval(72), getval(73), getval(74),
107  getval(75), getval(76), getval(77), getval(78), getval(79),
108  getval(80), getval(81), getval(82), getval(83), getval(84),
109  getval(85), getval(86), getval(87), getval(88), getval(89),
110  getval(90), getval(91), getval(92), getval(93), getval(94),
111  getval(95), getval(96), getval(97), getval(98), getval(99),
112  getval(100), getval(101), getval(102), getval(103), getval(104),
113  getval(105), getval(106), getval(107), getval(108), getval(109),
114  getval(110), getval(111), getval(112), getval(113), getval(114),
115  getval(115), getval(116), getval(117), getval(118), getval(119),
116  getval(120), getval(121), getval(122), getval(123), getval(124),
117  getval(125), getval(126), getval(127), getval(128), getval(129),
118  getval(130), getval(131), getval(132), getval(133), getval(134),
119  getval(135), getval(136), getval(137), getval(138), getval(139),
120  getval(140), getval(141), getval(142), getval(143), getval(144),
121  getval(145), getval(146), getval(147), getval(148), getval(149),
122  getval(150), getval(151), getval(152), getval(153), getval(154),
123  getval(155), getval(156), getval(157), getval(158), getval(159),
124  getval(160), getval(161), getval(162), getval(163), getval(164),
125  getval(165), getval(166), getval(167), getval(168), getval(169),
126  getval(170), getval(171), getval(172), getval(173), getval(174),
127  getval(175), getval(176), getval(177), getval(178), getval(179),
128  getval(180), getval(181), getval(182), getval(183), getval(184),
129  getval(185), getval(186), getval(187), getval(188), getval(189),
130  getval(190), getval(191), getval(192), getval(193), getval(194),
131  getval(195), getval(196), getval(197), getval(198), getval(199),
132  getval(200), getval(201), getval(202), getval(203), getval(204),
133  getval(205), getval(206), getval(207), getval(208), getval(209),
134  getval(210), getval(211), getval(212), getval(213), getval(214),
135  getval(215), getval(216), getval(217), getval(218), getval(219),
136  getval(220), getval(221), getval(222), getval(223), getval(224),
137  getval(225), getval(226), getval(227), getval(228), getval(229),
138  getval(230), getval(231), getval(232), getval(233), getval(234),
139  getval(235), getval(236), getval(237), getval(238), getval(239),
140  getval(240), getval(241), getval(242), getval(243), getval(244),
141  getval(245), getval(246), getval(247), getval(248), getval(249),
142  getval(250), getval(251), getval(252), getval(253), getval(254),
143  getval(255)};
144 
145 template <encoding T, typename Traits>
147  std::string_view input) {
148  std::string output;
149  std::size_t isize = input.size();
150  auto partial_blocks = static_cast<float>(input.size()) / input_size();
151  auto num_blocks = static_cast<std::size_t>(partial_blocks);
152  auto osize = static_cast<size_t>(std::ceil(partial_blocks * output_size()));
153  if constexpr (std::is_same_v<typename Traits::execution_style, block_tag>) {
154  num_blocks = static_cast<size_t>(std::ceil(partial_blocks));
155  isize = input_size() * num_blocks;
156  }
157  output.resize(std::max(osize, (output_size() * num_blocks)));
158  auto input_it = std::begin(input);
159  int length = 0;
160  for (std::size_t i = 0; i < isize; ++i, ++input_it) {
161  int carry = i >= input.size() ? 0 : static_cast<unsigned char>(*input_it);
162  int j = 0;
163  for (auto oi = output.rbegin();
164  (oi != output.rend()) && (carry != 0 || j < length); ++oi, ++j) {
165  carry += 256 * (*oi);
166  auto byte = (unsigned char*)(&(*oi));
167  *byte = carry % radix;
168  carry /= radix;
169  }
170  length = j;
171  }
172  std::transform(output.rbegin(), output.rend(), output.rbegin(),
173  [](auto c) { return Traits::charset[c]; });
174  if constexpr (Traits::padding == 0) {
175  output.resize(osize);
176  } else {
177  auto pad_size = output.size() - osize;
178  output.replace(osize, pad_size, pad_size, Traits::padding);
179  }
180  if constexpr (std::is_same_v<typename Traits::execution_style, stream_tag>) {
181  output.erase(0, output.size() % output_size() ? output.size() - length : 0);
182  }
183  return output;
184 }
185 
186 template <encoding T, typename Traits>
188  return std::is_same_v<typename Traits::execution_style, block_tag>
189  ? input_size()
190  : 0;
191 }
192 
193 template <encoding T, typename Traits>
195  return ratio.num;
196 }
197 
198 template <encoding T, typename Traits>
200  return std::is_same_v<typename Traits::execution_style, block_tag>
201  ? input_size()
202  : 0;
203 }
204 
205 template <encoding T, typename Traits>
207  return ratio.den;
208 }
209 
210 template <encoding T, typename Traits>
212  std::string_view input) {
213  std::string output;
214  auto end = std::find(input.begin(), input.end(), Traits::padding);
215  size_t input_size = std::distance(input.begin(), end);
216  auto partial_blocks = static_cast<float>(input_size) / this->input_size();
217  auto output_size = static_cast<size_t>(this->output_size() * partial_blocks);
218  if constexpr (std::is_same_v<typename Traits::execution_style, block_tag>) {
219  std::size_t num_blocks = 0;
220  auto input_size_float = static_cast<float>(input.size());
221  num_blocks =
222  static_cast<size_t>(std::ceil(input_size_float / this->input_size()));
223  output.resize(this->output_size() * num_blocks);
224  input_size = this->input_size() * num_blocks;
225  } else {
226  output.resize(output_size);
227  }
228  auto input_it = input.begin();
229  for (size_t i = 0; i < input_size; ++i, ++input_it) {
230  int carry = i > input.size() || *input_it == Traits::padding
231  ? 0
232  : valset[(unsigned char)(*input_it)];
233  if (carry == 255) {
234  // throw std::invalid_argument(std::string{"Invalid input character
235  // "} + *input_it);
236  return {};
237  }
238  auto j = output.size();
239  while (carry != 0 || j > 0) {
240  auto index = j - 1;
241  carry += radix * static_cast<unsigned char>(output[index]);
242  output[index] = static_cast<unsigned char>(carry % 256);
243  carry /= 256;
244  if (carry > 0 && index == 0) {
245  output.insert(0, 1, 0);
246  } else {
247  j = index;
248  }
249  }
250  }
251  if constexpr (std::is_same_v<typename Traits::execution_style, block_tag>) {
252  output.erase(output_size, output.size());
253  }
254  return output;
255 }
256 
257 template <>
258 struct traits<encoding::base_16> {
259  constexpr static const std::array<char, 16> charset = {
260  '0', '1', '2', '3', '4', '5', '6', '7',
261  '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
262  constexpr static const char name[] = "base_16";
264  constexpr static const char padding = 0;
265 };
267 
268 template <>
269 struct traits<encoding::base_36> {
270  constexpr static const std::array<char, 36> charset = {
271  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
272  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
273  'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
274  'u', 'v', 'w', 'x', 'y', 'z'};
275  constexpr static const char name[] = "base_36";
277  constexpr static const char padding = 0;
278 };
280 
281 
282 template <>
283 struct traits<encoding::base_58_btc> {
284  constexpr static const std::array<char, 58> charset = {
285  '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
286  'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
287  'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'm',
288  'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
289  constexpr static const char name[] = "base_58_btc";
291  constexpr static const char padding = 0;
292 };
294 
295 template <>
296 struct traits<encoding::base_64_pad> {
297  constexpr static const std::array<char, 64> charset = {
298  'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
299  'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
300  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
301  'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
302  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/'};
303  constexpr static const char name[] = "base_64_pad";
305  constexpr static const char padding = '=';
306 };
308 
309 template <>
310 struct traits<encoding::base_64> {
311  constexpr static const std::array<char, 64> charset = {
312  'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
313  'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
314  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
315  'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
316  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/'};
317  constexpr static const char name[] = "base_64";
320  constexpr static const char padding = 0;
321 };
323 
324 } // namespace multibase
325 
326 // LCOV_EXCL_STOP
Definition: algorithm.h:13
Definition: algorithm.h:16
Definition: algorithm.h:10
Definition: basic_algorithm.h:43
size_t block_size() override
Definition: basic_algorithm.h:199
std::string process(std::string_view input) override
Definition: basic_algorithm.h:211
size_t output_size() override
Definition: basic_algorithm.h:206
Definition: basic_algorithm.h:33
size_t output_size() override
Definition: basic_algorithm.h:194
size_t block_size() override
Definition: basic_algorithm.h:187
std::string process(std::string_view input) override
Definition: basic_algorithm.h:146
Definition: basic_algorithm.h:31
Definition: basic_algorithm.h:21