base58.c (10000B)
1 2 #include "base58.h" 3 #include "sha256.h" 4 #include "endian.h" 5 #include "short_types.h" 6 #include "compiler.h" 7 8 #include <strings.h> 9 10 /* Temporary stack buffer sizes */ 11 #define BIGNUM_WORDS 128u 12 #define BIGNUM_BYTES (BIGNUM_WORDS * sizeof(uint32_t)) 13 #define BASE58_ALL_DEFINED_FLAGS (BASE58_FLAG_CHECKSUM) 14 15 static const unsigned char base58_to_byte[256] = { 16 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 17 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 18 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 19 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 20 21 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 22 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 23 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, /* .1234567 */ 24 0x08, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* 89...... */ 25 26 0x00, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10, /* .ABCDEFG */ 27 0x11, 0x00, 0x12, 0x13, 0x14, 0x15, 0x16, 0x00, /* H.JKLMN. */ 28 0x17, 0x18, 0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, /* PQRSTUVW */ 29 0x1F, 0x20, 0x21, 0x00, 0x00, 0x00, 0x00, 0x00, /* XYZ..... */ 30 31 0x00, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, /* .abcdefg */ 32 0x29, 0x2A, 0x2B, 0x2C, 0x00, 0x2D, 0x2E, 0x2F, /* hijk.mno */ 33 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, /* pqrstuvx */ 34 0x38, 0x39, 0x3A, 0x00, 0x00, 0x00, 0x00, 0x00, /* xyz..... */ 35 36 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 37 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 38 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 39 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 40 41 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 42 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 43 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 44 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 45 46 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 47 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 48 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 49 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 50 51 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 52 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 53 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 54 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ........ */ 55 }; 56 57 static const char byte_to_base58[58] = { 58 '1', '2', '3', '4', '5', '6', '7', '8', 59 '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 60 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 61 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 62 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 63 'h', 'i', 'j', 'k', 'm', 'n', 'o', 'p', 64 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 65 'y','z' 66 }; 67 68 /* Returns non-zero on error. If 0 is returned then: 69 * *len <= input value - OK, bytes_out contains data. 70 * *len > input value - Failed and bytes_out untouched. 71 */ 72 static int base58_decode(const char *base58, size_t base58_len, 73 unsigned char *bytes_out, size_t *len) 74 { 75 uint32_t bn_buf[BIGNUM_WORDS]; 76 uint32_t *bn = bn_buf, *top_word, *bn_p; 77 size_t bn_words = 0, ones, cp_len, i; 78 unsigned char *cp; 79 int ret = WALLY_EINVAL; 80 81 if (!base58 || !base58_len) 82 return WALLY_EINVAL; /* Empty string can't be decoded or represented */ 83 84 /* Process leading '1's */ 85 for (ones = 0; ones < base58_len && base58[ones] == '1'; ++ones) 86 ; /* no-op*/ 87 88 if (!(base58_len -= ones)) { 89 if (bytes_out && ones <= *len) 90 memset(bytes_out, 0, ones); 91 *len = ones; 92 return WALLY_OK; /* String of all '1's */ 93 } 94 base58 += ones; /* Skip over leading '1's */ 95 96 /* Take 6 bits to store each 58 bit number, rounded up to the next byte, 97 * then round that up to a uint32_t word boundary. */ 98 bn_words = ((base58_len * 6 + 7) / 8 + 3) / 4; 99 100 /* Allocate our bignum buffer if it won't fit on the stack */ 101 if (bn_words > BIGNUM_WORDS) 102 if (!(bn = malloc(bn_words * sizeof(*bn)))) { 103 ret = WALLY_ENOMEM; 104 goto cleanup; 105 } 106 107 /* Iterate through the characters adding them to our bignum. We keep 108 * track of the current top word to avoid iterating over words that 109 * we know are zero. */ 110 top_word = bn + bn_words - 1; 111 *top_word = 0; 112 113 for (i = 0; i < base58_len; ++i) { 114 unsigned char byte = base58_to_byte[((unsigned char *)base58)[i]]; 115 if (!byte--) 116 goto cleanup; /* Invalid char */ 117 118 for (bn_p = bn + bn_words - 1; bn_p >= top_word; --bn_p) { 119 uint64_t mult = *bn_p * 58ull + byte; 120 *bn_p = mult & 0xffffffff; 121 byte = (mult >> 32) & 0xff; 122 if (byte && bn_p == top_word) { 123 *--top_word = byte; /* Increase bignum size */ 124 break; 125 } 126 } 127 } 128 129 /* We have our bignum stored from top_word to bn + bn_words - 1. Convert 130 * its words to big-endian so we can simply memcpy it to bytes_out. */ 131 for (bn_p = top_word; bn_p < bn + bn_words; ++bn_p) 132 *bn_p = cpu_to_be32(*bn_p); /* No-op on big-endian machines */ 133 134 for (cp = (unsigned char *)top_word; !*cp; ++cp) 135 ; /* Skip leading zero bytes in our bignum */ 136 137 /* Copy the result if it fits, cleanup and return */ 138 cp_len = (unsigned char *)(bn + bn_words) - cp; 139 140 if (bytes_out && ones + cp_len <= *len) { 141 memset(bytes_out, 0, ones); 142 memcpy(bytes_out + ones, cp, cp_len); 143 } 144 145 *len = ones + cp_len; 146 ret = WALLY_OK; 147 148 cleanup: 149 wally_clear(bn, bn_words * sizeof(*bn)); 150 if (bn != bn_buf) 151 free(bn); 152 return ret; 153 } 154 155 uint32_t base58_get_checksum(const unsigned char *bytes, size_t bytes_len) 156 { 157 struct sha256 sha; 158 uint32_t checksum; 159 160 sha256d(bytes, bytes_len, (unsigned char *)&sha, sizeof(sha)); 161 checksum = sha.u.u32[0]; 162 wally_clear(&sha, sizeof(sha)); 163 return checksum; 164 } 165 166 167 int wally_base58_from_bytes(const unsigned char *bytes, size_t bytes_len, 168 uint32_t flags, char **output) 169 { 170 uint32_t checksum, *cs_p = NULL; 171 unsigned char bn_buf[BIGNUM_BYTES]; 172 unsigned char *bn = bn_buf, *top_byte, *bn_p; 173 size_t bn_bytes = 0, zeros, i, orig_len = bytes_len; 174 int ret = WALLY_EINVAL; 175 176 if (output) 177 *output = NULL; 178 179 if (!bytes || !bytes_len || (flags & ~BASE58_ALL_DEFINED_FLAGS) || !output) 180 goto cleanup; /* Invalid argument */ 181 182 if (flags & BASE58_FLAG_CHECKSUM) { 183 checksum = base58_get_checksum(bytes, bytes_len); 184 cs_p = &checksum; 185 bytes_len += 4; 186 } 187 188 #define b(n) (n < orig_len ? bytes[n] : ((unsigned char *)cs_p)[n - orig_len]) 189 190 /* Process leading zeros */ 191 for (zeros = 0; zeros < bytes_len && !b(zeros); ++zeros) 192 ; /* no-op*/ 193 194 if (zeros == bytes_len) { 195 if (!(*output = malloc(zeros + 1))) { 196 ret = WALLY_ENOMEM; 197 goto cleanup; 198 } 199 200 memset(*output, '1', zeros); 201 (*output)[zeros] = '\0'; 202 return WALLY_OK; /* All 0's */ 203 } 204 205 bn_bytes = (bytes_len - zeros) * 138 / 100 + 1; /* log(256)/log(58) rounded up */ 206 207 /* Allocate our bignum buffer if it won't fit on the stack */ 208 if (bn_bytes > BIGNUM_BYTES) 209 if (!(bn = malloc(bn_bytes))) { 210 ret = WALLY_ENOMEM; 211 goto cleanup; 212 } 213 214 top_byte = bn + bn_bytes - 1; 215 *top_byte = 0; 216 217 for (i = zeros; i < bytes_len; ++i) { 218 uint32_t carry = b(i); 219 for (bn_p = bn + bn_bytes - 1; bn_p >= top_byte; --bn_p) { 220 carry = *bn_p * 256 + carry; 221 *bn_p = carry % 58; 222 carry = carry / 58; 223 if (carry && bn_p == top_byte) 224 *--top_byte = 0; /* Increase bignum size */ 225 } 226 } 227 228 while (!*top_byte && top_byte < bn + bn_bytes - 1) 229 ++top_byte; /* Skip leading zero bytes in our bignum */ 230 231 /* Copy the result */ 232 bn_bytes = bn + bn_bytes - top_byte; 233 234 if (!(*output = malloc(zeros + bn_bytes + 1))) { 235 ret = WALLY_ENOMEM; 236 goto cleanup; 237 } 238 239 memset(*output, '1', zeros); 240 for (i = 0; i < bn_bytes; ++i) 241 (*output)[zeros + i] = byte_to_base58[top_byte[i]]; 242 (*output)[zeros + bn_bytes] = '\0'; 243 244 ret = WALLY_OK; 245 246 cleanup: 247 wally_clear(bn, bn_bytes); 248 if (bn != bn_buf) 249 free(bn); 250 return ret; 251 #undef b 252 } 253 254 255 int wally_base58_get_length(const char *str_in, size_t *written) 256 { 257 return base58_decode(str_in, strlen(str_in), NULL, written); 258 } 259 260 int wally_base58_to_bytes(const char *str_in, uint32_t flags, 261 unsigned char *bytes_out, size_t len, 262 size_t *written) 263 { 264 size_t offset; 265 uint32_t checksum; 266 int ret; 267 268 if (written) 269 *written = 0; 270 271 if (!str_in || flags & ~BASE58_ALL_DEFINED_FLAGS || 272 !bytes_out || !len || !written) 273 return WALLY_EINVAL; 274 275 if (flags & BASE58_FLAG_CHECKSUM && len <= BASE58_CHECKSUM_LEN) 276 return WALLY_EINVAL; /* No room for checksum */ 277 278 *written = len; 279 ret = base58_decode(str_in, strlen(str_in), bytes_out, written); 280 if (!ret && *written > len) 281 return WALLY_OK; /* not enough space, return required amount */ 282 283 if (!ret && (flags & BASE58_FLAG_CHECKSUM)) { 284 if (*written <= BASE58_CHECKSUM_LEN) { 285 wally_clear(bytes_out, len); 286 return WALLY_EINVAL; /* Input not long enough to contain a checksum */ 287 } 288 289 offset = *written - BASE58_CHECKSUM_LEN; 290 checksum = base58_get_checksum(bytes_out, offset); 291 292 if (memcmp(bytes_out + offset, &checksum, sizeof(checksum))) { 293 wally_clear(bytes_out, len); 294 return WALLY_EINVAL; /* Checksum mismatch */ 295 } 296 297 wally_clear(bytes_out + offset, BASE58_CHECKSUM_LEN); 298 *written -= BASE58_CHECKSUM_LEN; 299 } 300 return ret; 301 }