Bitcoin ABC  0.26.3 P2P Digital Currency
Go to the documentation of this file.
1 // Copyright (c) 2017 Pieter Wuille
2 // Copyright (c) 2017-2019 The Bitcoin developers
5
7 #include <util/vector.h>
8
9 namespace {
10
11 typedef std::vector<uint8_t> data;
12
16 const char *CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
17
21 const int8_t CHARSET_REV[128] = {
22  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
23  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
24  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1, 10, 17, 21, 20, 26, 30, 7,
25  5, -1, -1, -1, -1, -1, -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22,
26  31, 27, 19, -1, 1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1,
27  -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1, 1, 0,
28  3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1};
29
35 uint64_t PolyMod(const data &v) {
69  uint64_t c = 1;
70  for (uint8_t d : v) {
94  // First, determine the value of c0:
95  uint8_t c0 = c >> 35;
96
97  // Then compute c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d:
98  c = ((c & 0x07ffffffff) << 5) ^ d;
99
100  // Finally, for each set bit n in c0, conditionally add {2^n}k(x):
101  if (c0 & 0x01) {
102  // k(x) = {19}*x^7 + {3}*x^6 + {25}*x^5 + {11}*x^4 + {25}*x^3 +
103  // {3}*x^2 + {19}*x + {1}
104  c ^= 0x98f2bc8e61;
105  }
106
107  if (c0 & 0x02) {
108  // {2}k(x) = {15}*x^7 + {6}*x^6 + {27}*x^5 + {22}*x^4 + {27}*x^3 +
109  // {6}*x^2 + {15}*x + {2}
110  c ^= 0x79b76d99e2;
111  }
112
113  if (c0 & 0x04) {
114  // {4}k(x) = {30}*x^7 + {12}*x^6 + {31}*x^5 + {5}*x^4 + {31}*x^3 +
115  // {12}*x^2 + {30}*x + {4}
116  c ^= 0xf33e5fb3c4;
117  }
118
119  if (c0 & 0x08) {
120  // {8}k(x) = {21}*x^7 + {24}*x^6 + {23}*x^5 + {10}*x^4 + {23}*x^3 +
121  // {24}*x^2 + {21}*x + {8}
122  c ^= 0xae2eabe2a8;
123  }
124
125  if (c0 & 0x10) {
126  // {16}k(x) = {3}*x^7 + {25}*x^6 + {7}*x^5 + {20}*x^4 + {7}*x^3 +
127  // {25}*x^2 + {3}*x + {16}
128  c ^= 0x1e4f43e470;
129  }
130  }
131
139  return c ^ 1;
140 }
141
147 inline uint8_t LowerCase(uint8_t c) {
148  // ASCII black magic.
149  return c | 0x20;
150 }
151
155 data ExpandPrefix(const std::string &prefix) {
156  data ret;
157  ret.resize(prefix.size() + 1);
158  for (size_t i = 0; i < prefix.size(); ++i) {
159  ret[i] = prefix[i] & 0x1f;
160  }
161
162  ret[prefix.size()] = 0;
163  return ret;
164 }
165
169 bool VerifyChecksum(const std::string &prefix, const data &payload) {
170  return PolyMod(Cat(ExpandPrefix(prefix), payload)) == 0;
171 }
172
176 data CreateChecksum(const std::string &prefix, const data &payload) {
177  data enc = Cat(ExpandPrefix(prefix), payload);
178  // Append 8 zeroes.
179  enc.resize(enc.size() + 8);
180  // Determine what to XOR into those 8 zeroes.
181  uint64_t mod = PolyMod(enc);
182  data ret(8);
183  for (size_t i = 0; i < 8; ++i) {
184  // Convert the 5-bit groups in mod to checksum values.
185  ret[i] = (mod >> (5 * (7 - i))) & 0x1f;
186  }
187
188  return ret;
189 }
190
191 } // namespace
192
194
198 std::string Encode(const std::string &prefix, const data &payload) {
199  data checksum = CreateChecksum(prefix, payload);
200  data combined = Cat(payload, checksum);
201  std::string ret = prefix + ':';
202
203  ret.reserve(ret.size() + combined.size());
204  for (uint8_t c : combined) {
205  ret += CHARSET[c];
206  }
207
208  return ret;
209 }
210
214 std::pair<std::string, data> Decode(const std::string &str,
215  const std::string &default_prefix) {
216  // Go over the string and do some sanity checks.
217  bool lower = false, upper = false, hasNumber = false;
218  size_t prefixSize = 0;
219  for (size_t i = 0; i < str.size(); ++i) {
220  uint8_t c = str[i];
221  if (c >= 'a' && c <= 'z') {
222  lower = true;
223  continue;
224  }
225
226  if (c >= 'A' && c <= 'Z') {
227  upper = true;
228  continue;
229  }
230
231  if (c >= '0' && c <= '9') {
232  // We cannot have numbers in the prefix.
233  hasNumber = true;
234  continue;
235  }
236
237  if (c == ':') {
238  // The separator cannot be the first character, cannot have number
239  // and there must not be 2 separators.
240  if (hasNumber || i == 0 || prefixSize != 0) {
241  return {};
242  }
243
244  prefixSize = i;
245  continue;
246  }
247
248  // We have an unexpected character.
249  return {};
250  }
251
252  // We can't have both upper case and lowercase.
253  if (upper && lower) {
254  return {};
255  }
256
257  // Get the prefix.
258  std::string prefix;
259  if (prefixSize == 0) {
260  prefix = default_prefix;
261  } else {
262  prefix.reserve(prefixSize);
263  for (size_t i = 0; i < prefixSize; ++i) {
264  prefix += LowerCase(str[i]);
265  }
266
267  // Now add the ':' in the size.
268  prefixSize++;
269  }
270
271  // Decode values.
272  const size_t valuesSize = str.size() - prefixSize;
273  data values(valuesSize);
274  for (size_t i = 0; i < valuesSize; ++i) {
275  uint8_t c = str[i + prefixSize];
276  // We have an invalid char in there.
277  if (c > 127 || CHARSET_REV[c] == -1) {
278  return {};
279  }
280
281  values[i] = CHARSET_REV[c];
282  }
283
284  // Verify the checksum.
285  if (!VerifyChecksum(prefix, values)) {
286  return {};
287  }
288
289  return {std::move(prefix), data(values.begin(), values.end() - 8)};
290 }
291