util_format.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562
  1. /* Copyright (c) 2001, Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2016, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file util_format.c
  8. *
  9. * \brief Miscellaneous functions for encoding and decoding various things
  10. * in base{16,32,64}.
  11. */
  12. #include "orconfig.h"
  13. #include "torlog.h"
  14. #include "util.h"
  15. #include "util_format.h"
  16. #include "torint.h"
  17. #include <stddef.h>
  18. #include <string.h>
  19. #include <stdlib.h>
  20. /* Return the base32 encoded size in bytes using the source length srclen.
  21. * The NUL terminated byte is added as well since every base32 encoding
  22. * requires enough space for it. */
  23. size_t
  24. base32_encoded_size(size_t srclen)
  25. {
  26. size_t enclen;
  27. enclen = CEIL_DIV(srclen*8, 5) + 1;
  28. tor_assert(enclen < INT_MAX && enclen > srclen);
  29. return enclen;
  30. }
  31. /** Implements base32 encoding as in RFC 4648. */
  32. void
  33. base32_encode(char *dest, size_t destlen, const char *src, size_t srclen)
  34. {
  35. unsigned int i, v, u;
  36. size_t nbits = srclen * 8;
  37. size_t bit;
  38. tor_assert(srclen < SIZE_T_CEILING/8);
  39. /* We need enough space for the encoded data and the extra NUL byte. */
  40. tor_assert(base32_encoded_size(srclen) <= destlen);
  41. tor_assert(destlen < SIZE_T_CEILING);
  42. /* Make sure we leave no uninitialized data in the destination buffer. */
  43. memset(dest, 0, destlen);
  44. for (i=0,bit=0; bit < nbits; ++i, bit+=5) {
  45. /* set v to the 16-bit value starting at src[bits/8], 0-padded. */
  46. v = ((uint8_t)src[bit/8]) << 8;
  47. if (bit+5<nbits)
  48. v += (uint8_t)src[(bit/8)+1];
  49. /* set u to the 5-bit value at the bit'th bit of buf. */
  50. u = (v >> (11-(bit%8))) & 0x1F;
  51. dest[i] = BASE32_CHARS[u];
  52. }
  53. dest[i] = '\0';
  54. }
  55. /** Implements base32 decoding as in RFC 4648.
  56. * Returns 0 if successful, -1 otherwise.
  57. */
  58. int
  59. base32_decode(char *dest, size_t destlen, const char *src, size_t srclen)
  60. {
  61. /* XXXX we might want to rewrite this along the lines of base64_decode, if
  62. * it ever shows up in the profile. */
  63. unsigned int i;
  64. size_t nbits, j, bit;
  65. char *tmp;
  66. nbits = ((srclen * 5) / 8) * 8;
  67. tor_assert(srclen < SIZE_T_CEILING / 5);
  68. tor_assert((nbits/8) <= destlen); /* We need enough space. */
  69. tor_assert(destlen < SIZE_T_CEILING);
  70. /* Make sure we leave no uninitialized data in the destination buffer. */
  71. memset(dest, 0, destlen);
  72. /* Convert base32 encoded chars to the 5-bit values that they represent. */
  73. tmp = tor_malloc_zero(srclen);
  74. for (j = 0; j < srclen; ++j) {
  75. if (src[j] > 0x60 && src[j] < 0x7B) tmp[j] = src[j] - 0x61;
  76. else if (src[j] > 0x31 && src[j] < 0x38) tmp[j] = src[j] - 0x18;
  77. else if (src[j] > 0x40 && src[j] < 0x5B) tmp[j] = src[j] - 0x41;
  78. else {
  79. log_warn(LD_BUG, "illegal character in base32 encoded string");
  80. tor_free(tmp);
  81. return -1;
  82. }
  83. }
  84. /* Assemble result byte-wise by applying five possible cases. */
  85. for (i = 0, bit = 0; bit < nbits; ++i, bit += 8) {
  86. switch (bit % 40) {
  87. case 0:
  88. dest[i] = (((uint8_t)tmp[(bit/5)]) << 3) +
  89. (((uint8_t)tmp[(bit/5)+1]) >> 2);
  90. break;
  91. case 8:
  92. dest[i] = (((uint8_t)tmp[(bit/5)]) << 6) +
  93. (((uint8_t)tmp[(bit/5)+1]) << 1) +
  94. (((uint8_t)tmp[(bit/5)+2]) >> 4);
  95. break;
  96. case 16:
  97. dest[i] = (((uint8_t)tmp[(bit/5)]) << 4) +
  98. (((uint8_t)tmp[(bit/5)+1]) >> 1);
  99. break;
  100. case 24:
  101. dest[i] = (((uint8_t)tmp[(bit/5)]) << 7) +
  102. (((uint8_t)tmp[(bit/5)+1]) << 2) +
  103. (((uint8_t)tmp[(bit/5)+2]) >> 3);
  104. break;
  105. case 32:
  106. dest[i] = (((uint8_t)tmp[(bit/5)]) << 5) +
  107. ((uint8_t)tmp[(bit/5)+1]);
  108. break;
  109. }
  110. }
  111. memset(tmp, 0, srclen); /* on the heap, this should be safe */
  112. tor_free(tmp);
  113. tmp = NULL;
  114. return 0;
  115. }
  116. #define BASE64_OPENSSL_LINELEN 64
  117. /** Return the Base64 encoded size of <b>srclen</b> bytes of data in
  118. * bytes.
  119. *
  120. * If <b>flags</b>&amp;BASE64_ENCODE_MULTILINE is true, return the size
  121. * of the encoded output as multiline output (64 character, `\n' terminated
  122. * lines).
  123. */
  124. size_t
  125. base64_encode_size(size_t srclen, int flags)
  126. {
  127. size_t enclen;
  128. tor_assert(srclen < INT_MAX);
  129. if (srclen == 0)
  130. return 0;
  131. enclen = ((srclen - 1) / 3) * 4 + 4;
  132. if (flags & BASE64_ENCODE_MULTILINE) {
  133. size_t remainder = enclen % BASE64_OPENSSL_LINELEN;
  134. enclen += enclen / BASE64_OPENSSL_LINELEN;
  135. if (remainder)
  136. enclen++;
  137. }
  138. tor_assert(enclen < INT_MAX && enclen > srclen);
  139. return enclen;
  140. }
  141. /** Internal table mapping 6 bit values to the Base64 alphabet. */
  142. static const char base64_encode_table[64] = {
  143. 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
  144. 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
  145. 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
  146. 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
  147. 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
  148. 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
  149. 'w', 'x', 'y', 'z', '0', '1', '2', '3',
  150. '4', '5', '6', '7', '8', '9', '+', '/'
  151. };
  152. /** Base64 encode <b>srclen</b> bytes of data from <b>src</b>. Write
  153. * the result into <b>dest</b>, if it will fit within <b>destlen</b>
  154. * bytes. Return the number of bytes written on success; -1 if
  155. * destlen is too short, or other failure.
  156. *
  157. * If <b>flags</b>&amp;BASE64_ENCODE_MULTILINE is true, return encoded
  158. * output in multiline format (64 character, `\n' terminated lines).
  159. */
  160. int
  161. base64_encode(char *dest, size_t destlen, const char *src, size_t srclen,
  162. int flags)
  163. {
  164. const unsigned char *usrc = (unsigned char *)src;
  165. const unsigned char *eous = usrc + srclen;
  166. char *d = dest;
  167. uint32_t n = 0;
  168. size_t linelen = 0;
  169. size_t enclen;
  170. int n_idx = 0;
  171. if (!src || !dest)
  172. return -1;
  173. /* Ensure that there is sufficient space, including the NUL. */
  174. enclen = base64_encode_size(srclen, flags);
  175. if (destlen < enclen + 1)
  176. return -1;
  177. if (destlen > SIZE_T_CEILING)
  178. return -1;
  179. if (enclen > INT_MAX)
  180. return -1;
  181. /* Make sure we leave no uninitialized data in the destination buffer. */
  182. memset(dest, 0, destlen);
  183. /* XXX/Yawning: If this ends up being too slow, this can be sped up
  184. * by separating the multiline format case and the normal case, and
  185. * processing 48 bytes of input at a time when newlines are desired.
  186. */
  187. #define ENCODE_CHAR(ch) \
  188. STMT_BEGIN \
  189. *d++ = ch; \
  190. if (flags & BASE64_ENCODE_MULTILINE) { \
  191. if (++linelen % BASE64_OPENSSL_LINELEN == 0) { \
  192. linelen = 0; \
  193. *d++ = '\n'; \
  194. } \
  195. } \
  196. STMT_END
  197. #define ENCODE_N(idx) \
  198. ENCODE_CHAR(base64_encode_table[(n >> ((3 - idx) * 6)) & 0x3f])
  199. #define ENCODE_PAD() ENCODE_CHAR('=')
  200. /* Iterate over all the bytes in src. Each one will add 8 bits to the
  201. * value we're encoding. Accumulate bits in <b>n</b>, and whenever we
  202. * have 24 bits, batch them into 4 bytes and flush those bytes to dest.
  203. */
  204. for ( ; usrc < eous; ++usrc) {
  205. n = (n << 8) | *usrc;
  206. if ((++n_idx) == 3) {
  207. ENCODE_N(0);
  208. ENCODE_N(1);
  209. ENCODE_N(2);
  210. ENCODE_N(3);
  211. n_idx = 0;
  212. n = 0;
  213. }
  214. }
  215. switch (n_idx) {
  216. case 0:
  217. /* 0 leftover bits, no pading to add. */
  218. break;
  219. case 1:
  220. /* 8 leftover bits, pad to 12 bits, write the 2 6-bit values followed
  221. * by 2 padding characters.
  222. */
  223. n <<= 4;
  224. ENCODE_N(2);
  225. ENCODE_N(3);
  226. ENCODE_PAD();
  227. ENCODE_PAD();
  228. break;
  229. case 2:
  230. /* 16 leftover bits, pad to 18 bits, write the 3 6-bit values followed
  231. * by 1 padding character.
  232. */
  233. n <<= 2;
  234. ENCODE_N(1);
  235. ENCODE_N(2);
  236. ENCODE_N(3);
  237. ENCODE_PAD();
  238. break;
  239. default:
  240. /* Something went catastrophically wrong. */
  241. tor_fragile_assert(); // LCOV_EXCL_LINE
  242. return -1;
  243. }
  244. #undef ENCODE_N
  245. #undef ENCODE_PAD
  246. #undef ENCODE_CHAR
  247. /* Multiline output always includes at least one newline. */
  248. if (flags & BASE64_ENCODE_MULTILINE && linelen != 0)
  249. *d++ = '\n';
  250. tor_assert(d - dest == (ptrdiff_t)enclen);
  251. *d++ = '\0'; /* NUL terminate the output. */
  252. return (int) enclen;
  253. }
  254. /** As base64_encode, but do not add any internal spaces or external padding
  255. * to the output stream. */
  256. int
  257. base64_encode_nopad(char *dest, size_t destlen,
  258. const uint8_t *src, size_t srclen)
  259. {
  260. int n = base64_encode(dest, destlen, (const char*) src, srclen, 0);
  261. if (n <= 0)
  262. return n;
  263. tor_assert((size_t)n < destlen && dest[n] == 0);
  264. char *in, *out;
  265. in = out = dest;
  266. while (*in) {
  267. if (*in == '=' || *in == '\n') {
  268. ++in;
  269. } else {
  270. *out++ = *in++;
  271. }
  272. }
  273. *out = 0;
  274. tor_assert(out - dest <= INT_MAX);
  275. return (int)(out - dest);
  276. }
  277. /** As base64_decode, but do not require any padding on the input */
  278. int
  279. base64_decode_nopad(uint8_t *dest, size_t destlen,
  280. const char *src, size_t srclen)
  281. {
  282. if (srclen > SIZE_T_CEILING - 4)
  283. return -1;
  284. char *buf = tor_malloc(srclen + 4);
  285. memcpy(buf, src, srclen+1);
  286. size_t buflen;
  287. switch (srclen % 4)
  288. {
  289. case 0:
  290. default:
  291. buflen = srclen;
  292. break;
  293. case 1:
  294. tor_free(buf);
  295. return -1;
  296. case 2:
  297. memcpy(buf+srclen, "==", 3);
  298. buflen = srclen + 2;
  299. break;
  300. case 3:
  301. memcpy(buf+srclen, "=", 2);
  302. buflen = srclen + 1;
  303. break;
  304. }
  305. int n = base64_decode((char*)dest, destlen, buf, buflen);
  306. tor_free(buf);
  307. return n;
  308. }
  309. #undef BASE64_OPENSSL_LINELEN
  310. /** @{ */
  311. /** Special values used for the base64_decode_table */
  312. #define X 255
  313. #define SP 64
  314. #define PAD 65
  315. /** @} */
  316. /** Internal table mapping byte values to what they represent in base64.
  317. * Numbers 0..63 are 6-bit integers. SPs are spaces, and should be
  318. * skipped. Xs are invalid and must not appear in base64. PAD indicates
  319. * end-of-string. */
  320. static const uint8_t base64_decode_table[256] = {
  321. X, X, X, X, X, X, X, X, X, SP, SP, SP, X, SP, X, X, /* */
  322. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  323. SP, X, X, X, X, X, X, X, X, X, X, 62, X, X, X, 63,
  324. 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, X, X, X, PAD, X, X,
  325. X, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
  326. 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, X, X, X, X, X,
  327. X, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
  328. 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, X, X, X, X, X,
  329. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  330. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  331. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  332. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  333. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  334. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  335. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  336. X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
  337. };
  338. /** Base64 decode <b>srclen</b> bytes of data from <b>src</b>. Write
  339. * the result into <b>dest</b>, if it will fit within <b>destlen</b>
  340. * bytes. Return the number of bytes written on success; -1 if
  341. * destlen is too short, or other failure.
  342. *
  343. * NOTE 1: destlen is checked conservatively, as though srclen contained no
  344. * spaces or padding.
  345. *
  346. * NOTE 2: This implementation does not check for the correct number of
  347. * padding "=" characters at the end of the string, and does not check
  348. * for internal padding characters.
  349. */
  350. int
  351. base64_decode(char *dest, size_t destlen, const char *src, size_t srclen)
  352. {
  353. const char *eos = src+srclen;
  354. uint32_t n=0;
  355. int n_idx=0;
  356. char *dest_orig = dest;
  357. /* Max number of bits == srclen*6.
  358. * Number of bytes required to hold all bits == (srclen*6)/8.
  359. * Yes, we want to round down: anything that hangs over the end of a
  360. * byte is padding. */
  361. if (destlen < (srclen*3)/4)
  362. return -1;
  363. if (destlen > SIZE_T_CEILING)
  364. return -1;
  365. /* Make sure we leave no uninitialized data in the destination buffer. */
  366. memset(dest, 0, destlen);
  367. /* Iterate over all the bytes in src. Each one will add 0 or 6 bits to the
  368. * value we're decoding. Accumulate bits in <b>n</b>, and whenever we have
  369. * 24 bits, batch them into 3 bytes and flush those bytes to dest.
  370. */
  371. for ( ; src < eos; ++src) {
  372. unsigned char c = (unsigned char) *src;
  373. uint8_t v = base64_decode_table[c];
  374. switch (v) {
  375. case X:
  376. /* This character isn't allowed in base64. */
  377. return -1;
  378. case SP:
  379. /* This character is whitespace, and has no effect. */
  380. continue;
  381. case PAD:
  382. /* We've hit an = character: the data is over. */
  383. goto end_of_loop;
  384. default:
  385. /* We have an actual 6-bit value. Append it to the bits in n. */
  386. n = (n<<6) | v;
  387. if ((++n_idx) == 4) {
  388. /* We've accumulated 24 bits in n. Flush them. */
  389. *dest++ = (n>>16);
  390. *dest++ = (n>>8) & 0xff;
  391. *dest++ = (n) & 0xff;
  392. n_idx = 0;
  393. n = 0;
  394. }
  395. }
  396. }
  397. end_of_loop:
  398. /* If we have leftover bits, we need to cope. */
  399. switch (n_idx) {
  400. case 0:
  401. default:
  402. /* No leftover bits. We win. */
  403. break;
  404. case 1:
  405. /* 6 leftover bits. That's invalid; we can't form a byte out of that. */
  406. return -1;
  407. case 2:
  408. /* 12 leftover bits: The last 4 are padding and the first 8 are data. */
  409. *dest++ = n >> 4;
  410. break;
  411. case 3:
  412. /* 18 leftover bits: The last 2 are padding and the first 16 are data. */
  413. *dest++ = n >> 10;
  414. *dest++ = n >> 2;
  415. }
  416. tor_assert((dest-dest_orig) <= (ssize_t)destlen);
  417. tor_assert((dest-dest_orig) <= INT_MAX);
  418. return (int)(dest-dest_orig);
  419. }
  420. #undef X
  421. #undef SP
  422. #undef PAD
  423. /** Encode the <b>srclen</b> bytes at <b>src</b> in a NUL-terminated,
  424. * uppercase hexadecimal string; store it in the <b>destlen</b>-byte buffer
  425. * <b>dest</b>.
  426. */
  427. void
  428. base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
  429. {
  430. const char *end;
  431. char *cp;
  432. tor_assert(destlen >= srclen*2+1);
  433. tor_assert(destlen < SIZE_T_CEILING);
  434. /* Make sure we leave no uninitialized data in the destination buffer. */
  435. memset(dest, 0, destlen);
  436. cp = dest;
  437. end = src+srclen;
  438. while (src<end) {
  439. *cp++ = "0123456789ABCDEF"[ (*(const uint8_t*)src) >> 4 ];
  440. *cp++ = "0123456789ABCDEF"[ (*(const uint8_t*)src) & 0xf ];
  441. ++src;
  442. }
  443. *cp = '\0';
  444. }
  445. /** Helper: given a hex digit, return its value, or -1 if it isn't hex. */
  446. static inline int
  447. hex_decode_digit_(char c)
  448. {
  449. switch (c) {
  450. case '0': return 0;
  451. case '1': return 1;
  452. case '2': return 2;
  453. case '3': return 3;
  454. case '4': return 4;
  455. case '5': return 5;
  456. case '6': return 6;
  457. case '7': return 7;
  458. case '8': return 8;
  459. case '9': return 9;
  460. case 'A': case 'a': return 10;
  461. case 'B': case 'b': return 11;
  462. case 'C': case 'c': return 12;
  463. case 'D': case 'd': return 13;
  464. case 'E': case 'e': return 14;
  465. case 'F': case 'f': return 15;
  466. default:
  467. return -1;
  468. }
  469. }
  470. /** Helper: given a hex digit, return its value, or -1 if it isn't hex. */
  471. int
  472. hex_decode_digit(char c)
  473. {
  474. return hex_decode_digit_(c);
  475. }
  476. /** Given a hexadecimal string of <b>srclen</b> bytes in <b>src</b>, decode
  477. * it and store the result in the <b>destlen</b>-byte buffer at <b>dest</b>.
  478. * Return the number of bytes decoded on success, -1 on failure. If
  479. * <b>destlen</b> is greater than INT_MAX or less than half of
  480. * <b>srclen</b>, -1 is returned. */
  481. int
  482. base16_decode(char *dest, size_t destlen, const char *src, size_t srclen)
  483. {
  484. const char *end;
  485. char *dest_orig = dest;
  486. int v1,v2;
  487. if ((srclen % 2) != 0)
  488. return -1;
  489. if (destlen < srclen/2 || destlen > INT_MAX)
  490. return -1;
  491. /* Make sure we leave no uninitialized data in the destination buffer. */
  492. memset(dest, 0, destlen);
  493. end = src+srclen;
  494. while (src<end) {
  495. v1 = hex_decode_digit_(*src);
  496. v2 = hex_decode_digit_(*(src+1));
  497. if (v1<0||v2<0)
  498. return -1;
  499. *(uint8_t*)dest = (v1<<4)|v2;
  500. ++dest;
  501. src+=2;
  502. }
  503. tor_assert((dest-dest_orig) <= (ptrdiff_t) destlen);
  504. return (int) (dest-dest_orig);
  505. }