Electroneum
base58.cpp
Go to the documentation of this file.
1 // Copyrights(c) 2017-2021, The Electroneum Project
2 // Copyrights(c) 2014-2019, The Monero Project
3 //
4 // All rights reserved.
5 //
6 // Redistribution and use in source and binary forms, with or without modification, are
7 // permitted provided that the following conditions are met:
8 //
9 // 1. Redistributions of source code must retain the above copyright notice, this list of
10 // conditions and the following disclaimer.
11 //
12 // 2. Redistributions in binary form must reproduce the above copyright notice, this list
13 // of conditions and the following disclaimer in the documentation and/or other
14 // materials provided with the distribution.
15 //
16 // 3. Neither the name of the copyright holder nor the names of its contributors may be
17 // used to endorse or promote products derived from this software without specific
18 // prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
21 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
22 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers
31 
32 #include "base58.h"
33 
34 #include <assert.h>
35 #include <string>
36 #include <vector>
37 
38 #include "crypto/hash.h"
39 #include "int-util.h"
40 #include "varint.h"
41 
42 namespace tools
43 {
44  namespace base58
45  {
46  namespace
47  {
48  const char alphabet[] = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
49  const size_t alphabet_size = sizeof(alphabet) - 1;
50  const size_t encoded_block_sizes[] = {0, 2, 3, 5, 6, 7, 9, 10, 11};
51  const size_t full_block_size = sizeof(encoded_block_sizes) / sizeof(encoded_block_sizes[0]) - 1;
52  const size_t full_encoded_block_size = encoded_block_sizes[full_block_size];
53  const size_t addr_checksum_size = 4;
54 
55  struct reverse_alphabet
56  {
57  reverse_alphabet()
58  {
59  m_data.resize(alphabet[alphabet_size - 1] - alphabet[0] + 1, -1);
60 
61  for (size_t i = 0; i < alphabet_size; ++i)
62  {
63  size_t idx = static_cast<size_t>(alphabet[i] - alphabet[0]);
64  m_data[idx] = static_cast<int8_t>(i);
65  }
66  }
67 
68  int operator()(char letter) const
69  {
70  size_t idx = static_cast<size_t>(letter - alphabet[0]);
71  return idx < m_data.size() ? m_data[idx] : -1;
72  }
73 
74  static reverse_alphabet instance;
75 
76  private:
77  std::vector<int8_t> m_data;
78  };
79 
80  reverse_alphabet reverse_alphabet::instance;
81 
82  struct decoded_block_sizes
83  {
84  decoded_block_sizes()
85  {
86  m_data.resize(encoded_block_sizes[full_block_size] + 1, -1);
87  for (size_t i = 0; i <= full_block_size; ++i)
88  {
89  m_data[encoded_block_sizes[i]] = static_cast<int>(i);
90  }
91  }
92 
93  int operator()(size_t encoded_block_size) const
94  {
95  assert(encoded_block_size <= full_encoded_block_size);
96  return m_data[encoded_block_size];
97  }
98 
99  static decoded_block_sizes instance;
100 
101  private:
102  std::vector<int> m_data;
103  };
104 
105  decoded_block_sizes decoded_block_sizes::instance;
106 
107  uint64_t uint_8be_to_64(const uint8_t* data, size_t size)
108  {
109  assert(1 <= size && size <= sizeof(uint64_t));
110 
111  uint64_t res = 0;
112  memcpy(reinterpret_cast<uint8_t*>(&res) + sizeof(uint64_t) - size, data, size);
113  return SWAP64BE(res);
114  }
115 
116  void uint_64_to_8be(uint64_t num, size_t size, uint8_t* data)
117  {
118  assert(1 <= size && size <= sizeof(uint64_t));
119 
120  uint64_t num_be = SWAP64BE(num);
121  memcpy(data, reinterpret_cast<uint8_t*>(&num_be) + sizeof(uint64_t) - size, size);
122  }
123 
124  void encode_block(const char* block, size_t size, char* res)
125  {
126  assert(1 <= size && size <= full_block_size);
127 
128  uint64_t num = uint_8be_to_64(reinterpret_cast<const uint8_t*>(block), size);
129  int i = static_cast<int>(encoded_block_sizes[size]) - 1;
130  while (0 < num)
131  {
132  uint64_t remainder = num % alphabet_size;
133  num /= alphabet_size;
134  res[i] = alphabet[remainder];
135  --i;
136  }
137  }
138 
139  bool decode_block(const char* block, size_t size, char* res)
140  {
141  assert(1 <= size && size <= full_encoded_block_size);
142 
143  int res_size = decoded_block_sizes::instance(size);
144  if (res_size <= 0)
145  return false; // Invalid block size
146 
147  uint64_t res_num = 0;
148  uint64_t order = 1;
149  for (size_t i = size - 1; i < size; --i)
150  {
151  int digit = reverse_alphabet::instance(block[i]);
152  if (digit < 0)
153  return false; // Invalid symbol
154 
155  uint64_t product_hi;
156  uint64_t tmp = res_num + mul128(order, digit, &product_hi);
157  if (tmp < res_num || 0 != product_hi)
158  return false; // Overflow
159 
160  res_num = tmp;
161  order *= alphabet_size; // Never overflows, 58^10 < 2^64
162  }
163 
164  if (static_cast<size_t>(res_size) < full_block_size && (UINT64_C(1) << (8 * res_size)) <= res_num)
165  return false; // Overflow
166 
167  uint_64_to_8be(res_num, res_size, reinterpret_cast<uint8_t*>(res));
168 
169  return true;
170  }
171  }
172 
174  {
175  if (data.empty())
176  return std::string();
177 
178  size_t full_block_count = data.size() / full_block_size;
179  size_t last_block_size = data.size() % full_block_size;
180  size_t res_size = full_block_count * full_encoded_block_size + encoded_block_sizes[last_block_size];
181 
182  std::string res(res_size, alphabet[0]);
183  for (size_t i = 0; i < full_block_count; ++i)
184  {
185  encode_block(data.data() + i * full_block_size, full_block_size, &res[i * full_encoded_block_size]);
186  }
187 
188  if (0 < last_block_size)
189  {
190  encode_block(data.data() + full_block_count * full_block_size, last_block_size, &res[full_block_count * full_encoded_block_size]);
191  }
192 
193  return res;
194  }
195 
196  bool decode(const std::string& enc, std::string& data)
197  {
198  if (enc.empty())
199  {
200  data.clear();
201  return true;
202  }
203 
204  size_t full_block_count = enc.size() / full_encoded_block_size;
205  size_t last_block_size = enc.size() % full_encoded_block_size;
206  int last_block_decoded_size = decoded_block_sizes::instance(last_block_size);
207  if (last_block_decoded_size < 0)
208  return false; // Invalid enc length
209  size_t data_size = full_block_count * full_block_size + last_block_decoded_size;
210 
211  data.resize(data_size, 0);
212  for (size_t i = 0; i < full_block_count; ++i)
213  {
214  if (!decode_block(enc.data() + i * full_encoded_block_size, full_encoded_block_size, &data[i * full_block_size]))
215  return false;
216  }
217 
218  if (0 < last_block_size)
219  {
220  if (!decode_block(enc.data() + full_block_count * full_encoded_block_size, last_block_size,
221  &data[full_block_count * full_block_size]))
222  return false;
223  }
224 
225  return true;
226  }
227 
229  {
231  buf += data;
232  crypto::hash hash = crypto::cn_fast_hash(buf.data(), buf.size());
233  const char* hash_data = reinterpret_cast<const char*>(&hash);
234  buf.append(hash_data, addr_checksum_size);
235  return encode(buf);
236  }
237 
238  bool decode_addr(const std::string &addr, uint64_t& tag, std::string& data)
239  {
240  std::string addr_data;
241  bool r = decode(addr, addr_data);
242  if (!r) return false;
243  if (addr_data.size() <= addr_checksum_size) return false;
244 
245  std::string checksum(addr_checksum_size, '\0');
246  checksum = addr_data.substr(addr_data.size() - addr_checksum_size);
247 
248  addr_data.resize(addr_data.size() - addr_checksum_size);
249  crypto::hash hash = crypto::cn_fast_hash(addr_data.data(), addr_data.size());
250  std::string expected_checksum(reinterpret_cast<const char*>(&hash), addr_checksum_size);
251  if (expected_checksum != checksum) return false;
252 
253  int read = tools::read_varint(addr_data.begin(), addr_data.end(), tag);
254  if (read <= 0) return false;
255 
256  data = addr_data.substr(read);
257  return true;
258  }
259  }
260 }
const char * res
Definition: hmac_keccak.cpp:41
#define SWAP64BE
Definition: int-util.h:251
::std::string string
Definition: gtest-port.h:1097
bool decode(const std::string &enc, std::string &data)
Definition: base58.cpp:196
provides the implementation of varint&#39;s
unsigned char uint8_t
Definition: stdint.h:124
std::string encode(const std::string &data)
Definition: base58.cpp:173
Various Tools.
Definition: tools.cpp:31
std::string get_varint_data(const T &v)
Returns the string that represents the varint.
Definition: varint.h:85
unsigned __int64 uint64_t
Definition: stdint.h:136
std::string encode_addr(uint64_t tag, const std::string &data)
Definition: base58.cpp:228
signed char int8_t
Definition: stdint.h:121
#define UINT64_C(val)
Definition: stdint.h:284
const char * buf
Definition: slow_memmem.cpp:74
void cn_fast_hash(const void *data, size_t length, char *hash)
void * memcpy(void *a, const void *b, size_t c)
bool decode_addr(const std::string &addr, uint64_t &tag, std::string &data)
Definition: base58.cpp:238
POD_CLASS hash
Definition: hash.h:50