lib/base32.c

   1 /* base32.c -- Encode binary data using printable characters.
   2    Copyright (C) 1999-2001, 2004-2006, 2009-2024 Free Software Foundation, Inc.
   3
   4    This file is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU Lesser General Public License as
   6    published by the Free Software Foundation; either version 2.1 of the
   7    License, or (at your option) any later version.
   8
   9    This file is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Adapted from Simon Josefsson's base64 code by Gijs van Tulder.
  18  *
  19  * See also RFC 4648 <https://www.ietf.org/rfc/rfc4648.txt>.
  20  *
  21  * Be careful with error checking.  Here is how you would typically
  22  * use these functions:
  23  *
  24  * bool ok = base32_decode_alloc (in, inlen, &out, &outlen);
  25  * if (!ok)
  26  *   FAIL: input was not valid base32
  27  * if (out == NULL)
  28  *   FAIL: memory allocation error
  29  * OK: data in OUT/OUTLEN
  30  *
  31  * idx_t outlen = base32_encode_alloc (in, inlen, &out);
  32  * if (out == NULL && outlen == 0 && inlen != 0)
  33  *   FAIL: input too long
  34  * if (out == NULL)
  35  *   FAIL: memory allocation error
  36  * OK: data in OUT/OUTLEN.
  37  *
  38  */
  39
  40 #include <config.h>
  41
  42 /* Get prototype. */
  43 #define BASE32_INLINE _GL_EXTERN_INLINE
  44 #include "base32.h"
  45
  46 /* Get imalloc. */
  47 #include <ialloc.h>
  48
  49 #include <stdckdint.h>
  50
  51 #include <string.h>
  52
  53 /* Convert 'char' to 'unsigned char' without casting.  */
  54 static unsigned char
  55 to_uchar (char ch)
  56 {
  57   return ch;
  58 }
  59
  60 /* Base32 encode IN array of size INLEN into OUT array of size OUTLEN.
  61    If OUTLEN is less than BASE32_LENGTH(INLEN), write as many bytes as
  62    possible.  If OUTLEN is larger than BASE32_LENGTH(INLEN), also zero
  63    terminate the output buffer. */
  64 void
  65 base32_encode (const char *restrict in, idx_t inlen,
  66                char *restrict out, idx_t outlen)
  67 {
  68   static const char b32str[32] =
  69     "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
  70
  71   while (inlen && outlen)
  72     {
  73       *out++ = b32str[(to_uchar (in[0]) >> 3) & 0x1f];
  74       if (!--outlen)
  75         break;
  76       *out++ = b32str[((to_uchar (in[0]) << 2)
  77                        + (--inlen ? to_uchar (in[1]) >> 6 : 0))
  78                       & 0x1f];
  79       if (!--outlen)
  80         break;
  81       *out++ =
  82         (inlen
  83          ? b32str[(to_uchar (in[1]) >> 1) & 0x1f]
  84          : '=');
  85       if (!--outlen)
  86         break;
  87       *out++ =
  88         (inlen
  89          ? b32str[((to_uchar (in[1]) << 4)
  90                    + (--inlen ? to_uchar (in[2]) >> 4 : 0))
  91                   & 0x1f]
  92          : '=');
  93       if (!--outlen)
  94         break;
  95       *out++ =
  96         (inlen
  97          ? b32str[((to_uchar (in[2]) << 1)
  98                    + (--inlen ? to_uchar (in[3]) >> 7 : 0))
  99                   & 0x1f]
 100          : '=');
 101       if (!--outlen)
 102         break;
 103       *out++ =
 104         (inlen
 105          ? b32str[(to_uchar (in[3]) >> 2) & 0x1f]
 106          : '=');
 107       if (!--outlen)
 108         break;
 109       *out++ =
 110         (inlen
 111          ? b32str[((to_uchar (in[3]) << 3)
 112                    + (--inlen ? to_uchar (in[4]) >> 5 : 0))
 113                   & 0x1f]
 114          : '=');
 115       if (!--outlen)
 116         break;
 117       *out++ = inlen ? b32str[to_uchar (in[4]) & 0x1f] : '=';
 118       if (!--outlen)
 119         break;
 120       if (inlen)
 121         inlen--;
 122       if (inlen)
 123         in += 5;
 124     }
 125
 126   if (outlen)
 127     *out = '\0';
 128 }
 129
 130 /* Allocate a buffer and store zero terminated base32 encoded data
 131    from array IN of size INLEN, returning BASE32_LENGTH(INLEN), i.e.,
 132    the length of the encoded data, excluding the terminating zero.  On
 133    return, the OUT variable will hold a pointer to newly allocated
 134    memory that must be deallocated by the caller.  If output string
 135    length would overflow, 0 is returned and OUT is set to NULL.  If
 136    memory allocation failed, OUT is set to NULL, and the return value
 137    indicates length of the requested memory block, i.e.,
 138    BASE32_LENGTH(inlen) + 1. */
 139 idx_t
 140 base32_encode_alloc (const char *in, idx_t inlen, char **out)
 141 {
 142   /* Check for overflow in outlen computation.
 143      Treat negative INLEN as overflow, for better compatibility with
 144      pre-2021-08-27 API, which used size_t.  */
 145   idx_t in_over_5 = inlen / 5 + (inlen % 5 != 0), outlen;
 146   if (ckd_mul (&outlen, in_over_5, 8) || inlen < 0)
 147     {
 148       *out = NULL;
 149       return 0;
 150     }
 151   outlen++;
 152
 153   *out = imalloc (outlen);
 154   if (!*out)
 155     return outlen;
 156
 157   base32_encode (in, inlen, *out, outlen);
 158
 159   return outlen - 1;
 160 }
 161
 162 /* With this approach this file works independent of the charset used
 163    (think EBCDIC).  However, it does assume that the characters in the
 164    Base32 alphabet (A-Z2-7) are encoded in 0..255.  POSIX
 165    1003.1-2001 require that char and unsigned char are 8-bit
 166    quantities, though, taking care of that problem.  But this may be a
 167    potential problem on non-POSIX C99 platforms.
 168
 169    IBM C V6 for AIX mishandles "#define B32(x) ...'x'...", so use "_"
 170    as the formal parameter rather than "x".  */
 171 #define B32(_)                                  \
 172   ((_) == 'A' ? 0                               \
 173    : (_) == 'B' ? 1                             \
 174    : (_) == 'C' ? 2                             \
 175    : (_) == 'D' ? 3                             \
 176    : (_) == 'E' ? 4                             \
 177    : (_) == 'F' ? 5                             \
 178    : (_) == 'G' ? 6                             \
 179    : (_) == 'H' ? 7                             \
 180    : (_) == 'I' ? 8                             \
 181    : (_) == 'J' ? 9                             \
 182    : (_) == 'K' ? 10                            \
 183    : (_) == 'L' ? 11                            \
 184    : (_) == 'M' ? 12                            \
 185    : (_) == 'N' ? 13                            \
 186    : (_) == 'O' ? 14                            \
 187    : (_) == 'P' ? 15                            \
 188    : (_) == 'Q' ? 16                            \
 189    : (_) == 'R' ? 17                            \
 190    : (_) == 'S' ? 18                            \
 191    : (_) == 'T' ? 19                            \
 192    : (_) == 'U' ? 20                            \
 193    : (_) == 'V' ? 21                            \
 194    : (_) == 'W' ? 22                            \
 195    : (_) == 'X' ? 23                            \
 196    : (_) == 'Y' ? 24                            \
 197    : (_) == 'Z' ? 25                            \
 198    : (_) == '2' ? 26                            \
 199    : (_) == '3' ? 27                            \
 200    : (_) == '4' ? 28                            \
 201    : (_) == '5' ? 29                            \
 202    : (_) == '6' ? 30                            \
 203    : (_) == '7' ? 31                            \
 204    : -1)
 205
 206 signed char const base32_to_int[256] = {
 207   B32 (0), B32 (1), B32 (2), B32 (3),
 208   B32 (4), B32 (5), B32 (6), B32 (7),
 209   B32 (8), B32 (9), B32 (10), B32 (11),
 210   B32 (12), B32 (13), B32 (14), B32 (15),
 211   B32 (16), B32 (17), B32 (18), B32 (19),
 212   B32 (20), B32 (21), B32 (22), B32 (23),
 213   B32 (24), B32 (25), B32 (26), B32 (27),
 214   B32 (28), B32 (29), B32 (30), B32 (31),
 215   B32 (32), B32 (33), B32 (34), B32 (35),
 216   B32 (36), B32 (37), B32 (38), B32 (39),
 217   B32 (40), B32 (41), B32 (42), B32 (43),
 218   B32 (44), B32 (45), B32 (46), B32 (47),
 219   B32 (48), B32 (49), B32 (50), B32 (51),
 220   B32 (52), B32 (53), B32 (54), B32 (55),
 221   B32 (56), B32 (57), B32 (58), B32 (59),
 222   B32 (60), B32 (61), B32 (62), B32 (63),
 223   B32 (32), B32 (65), B32 (66), B32 (67),
 224   B32 (68), B32 (69), B32 (70), B32 (71),
 225   B32 (72), B32 (73), B32 (74), B32 (75),
 226   B32 (76), B32 (77), B32 (78), B32 (79),
 227   B32 (80), B32 (81), B32 (82), B32 (83),
 228   B32 (84), B32 (85), B32 (86), B32 (87),
 229   B32 (88), B32 (89), B32 (90), B32 (91),
 230   B32 (92), B32 (93), B32 (94), B32 (95),
 231   B32 (96), B32 (97), B32 (98), B32 (99),
 232   B32 (100), B32 (101), B32 (102), B32 (103),
 233   B32 (104), B32 (105), B32 (106), B32 (107),
 234   B32 (108), B32 (109), B32 (110), B32 (111),
 235   B32 (112), B32 (113), B32 (114), B32 (115),
 236   B32 (116), B32 (117), B32 (118), B32 (119),
 237   B32 (120), B32 (121), B32 (122), B32 (123),
 238   B32 (124), B32 (125), B32 (126), B32 (127),
 239   B32 (128), B32 (129), B32 (130), B32 (131),
 240   B32 (132), B32 (133), B32 (134), B32 (135),
 241   B32 (136), B32 (137), B32 (138), B32 (139),
 242   B32 (140), B32 (141), B32 (142), B32 (143),
 243   B32 (144), B32 (145), B32 (146), B32 (147),
 244   B32 (148), B32 (149), B32 (150), B32 (151),
 245   B32 (152), B32 (153), B32 (154), B32 (155),
 246   B32 (156), B32 (157), B32 (158), B32 (159),
 247   B32 (160), B32 (161), B32 (162), B32 (163),
 248   B32 (132), B32 (165), B32 (166), B32 (167),
 249   B32 (168), B32 (169), B32 (170), B32 (171),
 250   B32 (172), B32 (173), B32 (174), B32 (175),
 251   B32 (176), B32 (177), B32 (178), B32 (179),
 252   B32 (180), B32 (181), B32 (182), B32 (183),
 253   B32 (184), B32 (185), B32 (186), B32 (187),
 254   B32 (188), B32 (189), B32 (190), B32 (191),
 255   B32 (192), B32 (193), B32 (194), B32 (195),
 256   B32 (196), B32 (197), B32 (198), B32 (199),
 257   B32 (200), B32 (201), B32 (202), B32 (203),
 258   B32 (204), B32 (205), B32 (206), B32 (207),
 259   B32 (208), B32 (209), B32 (210), B32 (211),
 260   B32 (212), B32 (213), B32 (214), B32 (215),
 261   B32 (216), B32 (217), B32 (218), B32 (219),
 262   B32 (220), B32 (221), B32 (222), B32 (223),
 263   B32 (224), B32 (225), B32 (226), B32 (227),
 264   B32 (228), B32 (229), B32 (230), B32 (231),
 265   B32 (232), B32 (233), B32 (234), B32 (235),
 266   B32 (236), B32 (237), B32 (238), B32 (239),
 267   B32 (240), B32 (241), B32 (242), B32 (243),
 268   B32 (244), B32 (245), B32 (246), B32 (247),
 269   B32 (248), B32 (249), B32 (250), B32 (251),
 270   B32 (252), B32 (253), B32 (254), B32 (255)
 271 };
 272
 273 /* If CTX->i is 0 or 8, there are eight or more bytes in [*IN..IN_END), and
 274    none of those eight is a newline, then return *IN.  Otherwise, copy up to
 275    4 - CTX->i non-newline bytes from that range into CTX->buf, starting at
 276    index CTX->i and setting CTX->i to reflect the number of bytes copied,
 277    and return CTX->buf.  In either case, advance *IN to point to the byte
 278    after the last one processed, and set *N_NON_NEWLINE to the number of
 279    verified non-newline bytes accessible through the returned pointer.  */
 280 static char *
 281 get_8 (struct base32_decode_context *ctx,
 282        char const *restrict *in, char const *restrict in_end,
 283        idx_t *n_non_newline)
 284 {
 285   if (ctx->i == 8)
 286     ctx->i = 0;
 287
 288   if (ctx->i == 0)
 289     {
 290       char const *t = *in;
 291       if (8 <= in_end - *in && memchr (t, '\n', 8) == NULL)
 292         {
 293           /* This is the common case: no newline.  */
 294           *in += 8;
 295           *n_non_newline = 8;
 296           return (char *) t;
 297         }
 298     }
 299
 300   {
 301     /* Copy non-newline bytes into BUF.  */
 302     char const *p = *in;
 303     while (p < in_end)
 304       {
 305         char c = *p++;
 306         if (c != '\n')
 307           {
 308             ctx->buf[ctx->i++] = c;
 309             if (ctx->i == 8)
 310               break;
 311           }
 312       }
 313
 314     *in = p;
 315     *n_non_newline = ctx->i;
 316     return ctx->buf;
 317   }
 318 }
 319
 320 #define return_false                            \
 321   do                                            \
 322     {                                           \
 323       *outp = out;                              \
 324       return false;                             \
 325     }                                           \
 326   while (false)
 327
 328 /* Decode eight bytes of base32-encoded data, IN, of length INLEN
 329    into the output buffer, *OUT, of size *OUTLEN bytes.  Return true if
 330    decoding is successful, false otherwise.  If *OUTLEN is too small,
 331    as many bytes as possible are written to *OUT.  On return, advance
 332    *OUT to point to the byte after the last one written, and decrement
 333    *OUTLEN to reflect the number of bytes remaining in *OUT.  */
 334 static bool
 335 decode_8 (char const *restrict in, idx_t inlen,
 336           char *restrict *outp, idx_t *outleft)
 337 {
 338   char *out = *outp;
 339   if (inlen < 8)
 340     return false;
 341
 342   if (!isbase32 (in[0]) || !isbase32 (in[1]))
 343     return false;
 344
 345   if (*outleft)
 346     {
 347       *out++ = ((base32_to_int[to_uchar (in[0])] << 3)
 348                 | (base32_to_int[to_uchar (in[1])] >> 2));
 349       --*outleft;
 350     }
 351
 352   if (in[2] == '=')
 353     {
 354       if (in[3] != '=' || in[4] != '=' || in[5] != '='
 355           || in[6] != '=' || in[7] != '=')
 356         return_false;
 357
 358       /* Reject non-canonical encodings.  */
 359       if (base32_to_int[to_uchar (in[1])] & 0x03)
 360         return_false;
 361     }
 362   else
 363     {
 364       if (!isbase32 (in[2]) || !isbase32 (in[3]))
 365         return_false;
 366
 367       if (*outleft)
 368         {
 369           *out++ = ((base32_to_int[to_uchar (in[1])] << 6)
 370                     | (base32_to_int[to_uchar (in[2])] << 1)
 371                     | (base32_to_int[to_uchar (in[3])] >> 4));
 372           --*outleft;
 373         }
 374
 375       if (in[4] == '=')
 376         {
 377           if (in[5] != '=' || in[6] != '=' || in[7] != '=')
 378             return_false;
 379
 380           /* Reject non-canonical encodings.  */
 381           if (base32_to_int[to_uchar (in[3])] & 0x0f)
 382             return_false;
 383         }
 384       else
 385         {
 386           if (!isbase32 (in[4]))
 387             return_false;
 388
 389           if (*outleft)
 390             {
 391               *out++ = ((base32_to_int[to_uchar (in[3])] << 4)
 392                         | (base32_to_int[to_uchar (in[4])] >> 1));
 393               --*outleft;
 394             }
 395
 396           if (in[5] == '=')
 397             {
 398               if (in[6] != '=' || in[7] != '=')
 399                 return_false;
 400
 401               /* Reject non-canonical encodings.  */
 402               if (base32_to_int[to_uchar (in[4])] & 0x01)
 403                 return_false;
 404             }
 405           else
 406             {
 407               if (!isbase32 (in[5]) || !isbase32 (in[6]))
 408                 return_false;
 409
 410               if (*outleft)
 411                 {
 412                   *out++ = ((base32_to_int[to_uchar (in[4])] << 7)
 413                             | (base32_to_int[to_uchar (in[5])] << 2)
 414                             | (base32_to_int[to_uchar (in[6])] >> 3));
 415                   --*outleft;
 416                 }
 417
 418               if (in[7] != '=')
 419                 {
 420                   if (!isbase32 (in[7]))
 421                     return_false;
 422
 423                   if (*outleft)
 424                     {
 425                       *out++ = ((base32_to_int[to_uchar (in[6])] << 5)
 426                                 | (base32_to_int[to_uchar (in[7])]));
 427                       --*outleft;
 428                     }
 429                 }
 430               else
 431                 {
 432                   /* Reject non-canonical encodings.  */
 433                   if (base32_to_int[to_uchar (in[6])] & 0x07)
 434                     return_false;
 435                 }
 436             }
 437         }
 438     }
 439
 440   *outp = out;
 441   return true;
 442 }
 443
 444 /* Decode base32-encoded input array IN of length INLEN to output array
 445    OUT that can hold *OUTLEN bytes.  The input data may be interspersed
 446    with newlines.  Return true if decoding was successful, i.e. if the
 447    input was valid base32 data, false otherwise.  If *OUTLEN is too
 448    small, as many bytes as possible will be written to OUT.  On return,
 449    *OUTLEN holds the length of decoded bytes in OUT.  Note that as soon
 450    as any non-alphabet, non-newline character is encountered, decoding
 451    is stopped and false is returned.  If INLEN is zero, then process
 452    only whatever data is stored in CTX.
 453
 454    Initially, CTX must have been initialized via base32_decode_ctx_init.
 455    Subsequent calls to this function must reuse whatever state is recorded
 456    in that buffer.  It is necessary for when a octuple of base32 input
 457    bytes spans two input buffers.
 458
 459    If CTX is NULL then newlines are treated as garbage and the input
 460    buffer is processed as a unit.  */
 461
 462 bool
 463 base32_decode_ctx (struct base32_decode_context *ctx,
 464                    const char *restrict in, idx_t inlen,
 465                    char *restrict out, idx_t *outlen)
 466 {
 467   idx_t outleft = *outlen;
 468   bool ignore_newlines = ctx != NULL;
 469   bool flush_ctx = false;
 470   unsigned int ctx_i = 0;
 471
 472   if (ignore_newlines)
 473     {
 474       ctx_i = ctx->i;
 475       flush_ctx = inlen == 0;
 476     }
 477
 478
 479   while (true)
 480     {
 481       idx_t outleft_save = outleft;
 482       if (ctx_i == 0 && !flush_ctx)
 483         {
 484           while (true)
 485             {
 486               /* Save a copy of outleft, in case we need to re-parse this
 487                  block of four bytes.  */
 488               outleft_save = outleft;
 489               if (!decode_8 (in, inlen, &out, &outleft))
 490                 break;
 491
 492               in += 8;
 493               inlen -= 8;
 494             }
 495         }
 496
 497       if (inlen == 0 && !flush_ctx)
 498         break;
 499
 500       /* Handle the common case of 72-byte wrapped lines.
 501          This also handles any other multiple-of-8-byte wrapping.  */
 502       if (inlen && *in == '\n' && ignore_newlines)
 503         {
 504           ++in;
 505           --inlen;
 506           continue;
 507         }
 508
 509       /* Restore OUT and OUTLEFT.  */
 510       out -= outleft_save - outleft;
 511       outleft = outleft_save;
 512
 513       {
 514         char const *in_end = in + inlen;
 515         char const *non_nl;
 516
 517         if (ignore_newlines)
 518           non_nl = get_8 (ctx, &in, in_end, &inlen);
 519         else
 520           non_nl = in;  /* Might have nl in this case. */
 521
 522         /* If the input is empty or consists solely of newlines (0 non-newlines),
 523            then we're done.  Likewise if there are fewer than 8 bytes when not
 524            flushing context and not treating newlines as garbage.  */
 525         if (inlen == 0 || (inlen < 8 && !flush_ctx && ignore_newlines))
 526           {
 527             inlen = 0;
 528             break;
 529           }
 530         if (!decode_8 (non_nl, inlen, &out, &outleft))
 531           break;
 532
 533         inlen = in_end - in;
 534       }
 535     }
 536
 537   *outlen -= outleft;
 538
 539   return inlen == 0;
 540 }
 541
 542 /* Allocate an output buffer in *OUT, and decode the base32 encoded
 543    data stored in IN of size INLEN to the *OUT buffer.  On return, the
 544    size of the decoded data is stored in *OUTLEN.  OUTLEN may be NULL,
 545    if the caller is not interested in the decoded length.  *OUT may be
 546    NULL to indicate an out of memory error, in which case *OUTLEN
 547    contains the size of the memory block needed.  The function returns
 548    true on successful decoding and memory allocation errors.  (Use the
 549    *OUT and *OUTLEN parameters to differentiate between successful
 550    decoding and memory error.)  The function returns false if the
 551    input was invalid, in which case *OUT is NULL and *OUTLEN is
 552    undefined. */
 553 bool
 554 base32_decode_alloc_ctx (struct base32_decode_context *ctx,
 555                          const char *in, idx_t inlen, char **out,
 556                          idx_t *outlen)
 557 {
 558   /* This may allocate a few bytes too many, depending on input,
 559      but it's not worth the extra CPU time to compute the exact size.
 560      The exact size is 5 * inlen / 8, minus one or more bytes if the
 561      input is padded with one or more "=".
 562      Shifting before multiplying avoids the possibility of overflow.  */
 563   idx_t needlen = 5 * ((inlen >> 3) + 1);
 564
 565   *out = imalloc (needlen);
 566   if (!*out)
 567     return true;
 568
 569   if (!base32_decode_ctx (ctx, in, inlen, *out, &needlen))
 570     {
 571       free (*out);
 572       *out = NULL;
 573       return false;
 574     }
 575
 576   if (outlen)
 577     *outlen = needlen;
 578
 579   return true;
 580 }