[PATCH] base32, base64: prefer signed to unsigned integers

[Paul Eggert]

* lib/base32.c, lib/base64.c: Include ialloc.h instad of stdlib.h.
Include intprops.h, verify.h.
* lib/base32.c (base32_encode, base32_encode_alloc, get_8, decode_8)
(base32_decode_ctx, base32_decode_alloc_ctx):
* lib/base32.h (struct base32_decode_context):
* lib/base64.c (base64_encode_fast, base64_encode)
(base64_encode_alloc, get_4, decode_4, base64_decode_ctx)
(base64_decode_alloc_ctx):
* lib/base64.h (struct base64_decode_context):
* tests/test-base32.c (main):
* tests/test-base64.c (main):
Prefer signed to unsigned integers.
* lib/base32.c (base32_encode_alloc):
* lib/base64.c (base64_encode_alloc):
Use simpler and more-direct check for overflow, removing a TODO.
* lib/base32.h, lib/base64.h: Include idx.h instead of stddef.h.
* modules/base32, modules/base64 (Depends-on): Add ialloc, verify.
---
 ChangeLog           | 21 ++++++++++++++
 NEWS                |  3 ++
 lib/base32.c        | 61 ++++++++++++++++++++-------------------
 lib/base32.h        | 20 ++++++-------
 lib/base64.c        | 69 ++++++++++++++++++++-------------------------
 lib/base64.h        | 20 ++++++-------
 modules/base32      |  2 ++
 modules/base64      |  2 ++
 tests/test-base32.c |  2 +-
 tests/test-base64.c |  2 +-
 10 files changed, 111 insertions(+), 91 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index adfbcf3e21..498525a242 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,24 @@
+2021-08-27  Paul Eggert  <eggert@cs.ucla.edu>
+
+       base32, base64: prefer signed to unsigned integers
+       * lib/base32.c, lib/base64.c: Include ialloc.h instad of stdlib.h.
+       Include intprops.h, verify.h.
+       * lib/base32.c (base32_encode, base32_encode_alloc, get_8, decode_8)
+       (base32_decode_ctx, base32_decode_alloc_ctx):
+       * lib/base32.h (struct base32_decode_context):
+       * lib/base64.c (base64_encode_fast, base64_encode)
+       (base64_encode_alloc, get_4, decode_4, base64_decode_ctx)
+       (base64_decode_alloc_ctx):
+       * lib/base64.h (struct base64_decode_context):
+       * tests/test-base32.c (main):
+       * tests/test-base64.c (main):
+       Prefer signed to unsigned integers.
+       * lib/base32.c (base32_encode_alloc):
+       * lib/base64.c (base64_encode_alloc):
+       Use simpler and more-direct check for overflow, removing a TODO.
+       * lib/base32.h, lib/base64.h: Include idx.h instead of stddef.h.
+       * modules/base32, modules/base64 (Depends-on): Add ialloc, verify.
+
 2021-08-26  Paul Eggert  <eggert@cs.ucla.edu>
 
        regex: use __attr_access and C99-style array arg
diff --git a/NEWS b/NEWS
index e0f0d836c2..2ce1c73014 100644
--- a/NEWS
+++ b/NEWS
@@ -66,6 +66,9 @@ User visible incompatible changes
 
 Date        Modules         Changes
 
+2021-08-27  base32          These modules now use idx_t instead of size_t
+            base64          for indexes and counts.
+
 2021-07-29  (all)           Due to draft C2x, the following attributes should
                             now appear at the start of a function declaration:
                               _GL_ATTRIBUTE_DEPRECATED
diff --git a/lib/base32.c b/lib/base32.c
index 75d0b296fd..e8feaf1663 100644
--- a/lib/base32.c
+++ b/lib/base32.c
@@ -28,7 +28,7 @@
  *   FAIL: memory allocation error
  * OK: data in OUT/OUTLEN
  *
- * size_t outlen = base32_encode_alloc (in, inlen, &out);
+ * idx_t outlen = base32_encode_alloc (in, inlen, &out);
  * if (out == NULL && outlen == 0 && inlen != 0)
  *   FAIL: input too long
  * if (out == NULL)
@@ -42,15 +42,18 @@
 /* Get prototype. */
 #include "base32.h"
 
-/* Get malloc. */
-#include <stdlib.h>
+/* Get imalloc. */
+#include <ialloc.h>
+
+#include <intprops.h>
+#include <verify.h>
 
 /* Get UCHAR_MAX. */
 #include <limits.h>
 
 #include <string.h>
 
-/* C89 compliant way to cast 'char' to 'unsigned char'. */
+/* Convert 'char' to 'unsigned char' without casting.  */
 static unsigned char
 to_uchar (char ch)
 {
@@ -62,8 +65,8 @@ to_uchar (char ch)
    possible.  If OUTLEN is larger than BASE32_LENGTH(INLEN), also zero
    terminate the output buffer. */
 void
-base32_encode (const char *restrict in, size_t inlen,
-               char *restrict out, size_t outlen)
+base32_encode (const char *restrict in, idx_t inlen,
+               char *restrict out, idx_t outlen)
 {
   static const char b32str[32] =
     "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
@@ -136,24 +139,20 @@ base32_encode (const char *restrict in, size_t inlen,
    memory allocation failed, OUT is set to NULL, and the return value
    indicates length of the requested memory block, i.e.,
    BASE32_LENGTH(inlen) + 1. */
-size_t
-base32_encode_alloc (const char *in, size_t inlen, char **out)
+idx_t
+base32_encode_alloc (const char *in, idx_t inlen, char **out)
 {
-  size_t outlen = 1 + BASE32_LENGTH (inlen);
-
-  /* Check for overflow in outlen computation.
-   *
-   * If there is no overflow, outlen >= inlen.
-   *
-   * TODO Is this a sufficient check?  (See the notes in base64.c.)
-   */
-  if (inlen > outlen)
+  /* Check for overflow in outlen computation.  */
+  assume (0 <= inlen);
+  idx_t in_over_5 = inlen / 5 + (inlen % 5 != 0), outlen;
+  if (! INT_MULTIPLY_OK (in_over_5, 8, &outlen))
     {
       *out = NULL;
       return 0;
     }
+  outlen++;
 
-  *out = malloc (outlen);
+  *out = imalloc (outlen);
   if (!*out)
     return outlen;
 
@@ -305,7 +304,7 @@ base32_decode_ctx_init (struct base32_decode_context *ctx)
 static char *
 get_8 (struct base32_decode_context *ctx,
        char const *restrict *in, char const *restrict in_end,
-       size_t *n_non_newline)
+       idx_t *n_non_newline)
 {
   if (ctx->i == 8)
     ctx->i = 0;
@@ -357,14 +356,14 @@ get_8 (struct base32_decode_context *ctx,
    *OUT to point to the byte after the last one written, and decrement
    *OUTLEN to reflect the number of bytes remaining in *OUT.  */
 static bool
-decode_8 (char const *restrict in, size_t inlen,
-          char *restrict *outp, size_t *outleft)
+decode_8 (char const *restrict in, idx_t inlen,
+          char *restrict *outp, idx_t *outleft)
 {
   char *out = *outp;
   if (inlen < 8)
     return false;
 
-  if (!isbase32 (in[0]) || !isbase32 (in[1]) )
+  if (!isbase32 (in[0]) || !isbase32 (in[1]))
     return false;
 
   if (*outleft)
@@ -468,10 +467,10 @@ decode_8 (char const *restrict in, size_t inlen,
 
 bool
 base32_decode_ctx (struct base32_decode_context *ctx,
-                   const char *restrict in, size_t inlen,
-                   char *restrict out, size_t *outlen)
+                   const char *restrict in, idx_t inlen,
+                   char *restrict out, idx_t *outlen)
 {
-  size_t outleft = *outlen;
+  idx_t outleft = *outlen;
   bool ignore_newlines = ctx != NULL;
   bool flush_ctx = false;
   unsigned int ctx_i = 0;
@@ -485,7 +484,7 @@ base32_decode_ctx (struct base32_decode_context *ctx,
 
   while (true)
     {
-      size_t outleft_save = outleft;
+      idx_t outleft_save = outleft;
       if (ctx_i == 0 && !flush_ctx)
         {
           while (true)
@@ -559,17 +558,17 @@ base32_decode_ctx (struct base32_decode_context *ctx,
    undefined. */
 bool
 base32_decode_alloc_ctx (struct base32_decode_context *ctx,
-                         const char *in, size_t inlen, char **out,
-                         size_t *outlen)
+                         const char *in, idx_t inlen, char **out,
+                         idx_t *outlen)
 {
   /* This may allocate a few bytes too many, depending on input,
      but it's not worth the extra CPU time to compute the exact size.
      The exact size is 5 * inlen / 8, minus one or more bytes if the
      input is padded with one or more "=".
-     Dividing before multiplying avoids the possibility of overflow.  */
-  size_t needlen = 5 * (inlen / 8) + 5;
+     Shifting before multiplying avoids the possibility of overflow.  */
+  idx_t needlen = 5 * ((inlen >> 3) + 1);
 
-  *out = malloc (needlen);
+  *out = imalloc (needlen);
   if (!*out)
     return true;
 
diff --git a/lib/base32.h b/lib/base32.h
index f65e55b0fe..108a5ecd38 100644
--- a/lib/base32.h
+++ b/lib/base32.h
@@ -18,8 +18,8 @@
 #ifndef BASE32_H
 # define BASE32_H
 
-/* Get size_t. */
-# include <stddef.h>
+/* Get idx_t. */
+# include <idx.h>
 
 /* Get bool. */
 # include <stdbool.h>
@@ -30,26 +30,26 @@
 
 struct base32_decode_context
 {
-  unsigned int i;
+  int i;
   char buf[8];
 };
 
 extern bool isbase32 (char ch) _GL_ATTRIBUTE_CONST;
 
-extern void base32_encode (const char *restrict in, size_t inlen,
-                           char *restrict out, size_t outlen);
+extern void base32_encode (const char *restrict in, idx_t inlen,
+                           char *restrict out, idx_t outlen);
 
-extern size_t base32_encode_alloc (const char *in, size_t inlen, char **out);
+extern idx_t base32_encode_alloc (const char *in, idx_t inlen, char **out);
 
 extern void base32_decode_ctx_init (struct base32_decode_context *ctx);
 
 extern bool base32_decode_ctx (struct base32_decode_context *ctx,
-                               const char *restrict in, size_t inlen,
-                               char *restrict out, size_t *outlen);
+                               const char *restrict in, idx_t inlen,
+                               char *restrict out, idx_t *outlen);
 
 extern bool base32_decode_alloc_ctx (struct base32_decode_context *ctx,
-                                     const char *in, size_t inlen,
-                                     char **out, size_t *outlen);
+                                     const char *in, idx_t inlen,
+                                     char **out, idx_t *outlen);
 
 #define base32_decode(in, inlen, out, outlen) \
         base32_decode_ctx (NULL, in, inlen, out, outlen)
diff --git a/lib/base64.c b/lib/base64.c
index 7a6e7af5fc..2a01ed34e9 100644
--- a/lib/base64.c
+++ b/lib/base64.c
@@ -30,7 +30,7 @@
  *   FAIL: memory allocation error
  * OK: data in OUT/OUTLEN
  *
- * size_t outlen = base64_encode_alloc (in, inlen, &out);
+ * idx_t outlen = base64_encode_alloc (in, inlen, &out);
  * if (out == NULL && outlen == 0 && inlen != 0)
  *   FAIL: input too long
  * if (out == NULL)
@@ -44,15 +44,18 @@
 /* Get prototype. */
 #include "base64.h"
 
-/* Get malloc. */
-#include <stdlib.h>
+/* Get imalloc. */
+#include <ialloc.h>
+
+#include <intprops.h>
+#include <verify.h>
 
 /* Get UCHAR_MAX. */
 #include <limits.h>
 
 #include <string.h>
 
-/* C89 compliant way to cast 'char' to 'unsigned char'. */
+/* Convert 'char' to 'unsigned char' without casting.  */
 static unsigned char
 to_uchar (char ch)
 {
@@ -66,7 +69,7 @@ static const char b64c[64] =
    to be of length >= BASE64_LENGTH(INLEN), and INLEN needs to be
    a multiple of 3.  */
 static void
-base64_encode_fast (const char *restrict in, size_t inlen, char *restrict out)
+base64_encode_fast (const char *restrict in, idx_t inlen, char *restrict out)
 {
   while (inlen)
     {
@@ -85,8 +88,8 @@ base64_encode_fast (const char *restrict in, size_t inlen, 
char *restrict out)
    possible.  If OUTLEN is larger than BASE64_LENGTH(INLEN), also zero
    terminate the output buffer. */
 void
-base64_encode (const char *restrict in, size_t inlen,
-               char *restrict out, size_t outlen)
+base64_encode (const char *restrict in, idx_t inlen,
+               char *restrict out, idx_t outlen)
 {
   /* Note this outlen constraint can be enforced at compile time.
      I.E. that the output buffer is exactly large enough to hold
@@ -95,7 +98,7 @@ base64_encode (const char *restrict in, size_t inlen,
      at the end of input.  However the common case when reading
      large inputs is to have both constraints satisfied, so we depend
      on both in base_encode_fast().  */
-  if (outlen % 4 == 0 && inlen == outlen / 4 * 3)
+  if (outlen % 4 == 0 && inlen == (outlen >> 2) * 3)
     {
       base64_encode_fast (in, inlen, out);
       return;
@@ -141,30 +144,20 @@ base64_encode (const char *restrict in, size_t inlen,
    memory allocation failed, OUT is set to NULL, and the return value
    indicates length of the requested memory block, i.e.,
    BASE64_LENGTH(inlen) + 1. */
-size_t
-base64_encode_alloc (const char *in, size_t inlen, char **out)
+idx_t
+base64_encode_alloc (const char *in, idx_t inlen, char **out)
 {
-  size_t outlen = 1 + BASE64_LENGTH (inlen);
-
-  /* Check for overflow in outlen computation.
-   *
-   * If there is no overflow, outlen >= inlen.
-   *
-   * If the operation (inlen + 2) overflows then it yields at most +1, so
-   * outlen is 0.
-   *
-   * If the multiplication overflows, we lose at least half of the
-   * correct value, so the result is < ((inlen + 2) / 3) * 2, which is
-   * less than (inlen + 2) * 0.66667, which is less than inlen as soon as
-   * (inlen > 4).
-   */
-  if (inlen > outlen)
+  /* Check for overflow in outlen computation.  */
+  assume (0 <= inlen);
+  idx_t in_over_3 = inlen / 3 + (inlen % 3 != 0), outlen;
+  if (! INT_MULTIPLY_OK (in_over_3, 4, &outlen))
     {
       *out = NULL;
       return 0;
     }
+  outlen++;
 
-  *out = malloc (outlen);
+  *out = imalloc (outlen);
   if (!*out)
     return outlen;
 
@@ -348,7 +341,7 @@ base64_decode_ctx_init (struct base64_decode_context *ctx)
 static char *
 get_4 (struct base64_decode_context *ctx,
        char const *restrict *in, char const *restrict in_end,
-       size_t *n_non_newline)
+       idx_t *n_non_newline)
 {
   if (ctx->i == 4)
     ctx->i = 0;
@@ -400,8 +393,8 @@ get_4 (struct base64_decode_context *ctx,
    *OUT to point to the byte after the last one written, and decrement
    *OUTLEN to reflect the number of bytes remaining in *OUT.  */
 static bool
-decode_4 (char const *restrict in, size_t inlen,
-          char *restrict *outp, size_t *outleft)
+decode_4 (char const *restrict in, idx_t inlen,
+          char *restrict *outp, idx_t *outleft)
 {
   char *out = *outp;
   if (inlen < 2)
@@ -486,10 +479,10 @@ decode_4 (char const *restrict in, size_t inlen,
 
 bool
 base64_decode_ctx (struct base64_decode_context *ctx,
-                   const char *restrict in, size_t inlen,
-                   char *restrict out, size_t *outlen)
+                   const char *restrict in, idx_t inlen,
+                   char *restrict out, idx_t *outlen)
 {
-  size_t outleft = *outlen;
+  idx_t outleft = *outlen;
   bool ignore_newlines = ctx != NULL;
   bool flush_ctx = false;
   unsigned int ctx_i = 0;
@@ -503,7 +496,7 @@ base64_decode_ctx (struct base64_decode_context *ctx,
 
   while (true)
     {
-      size_t outleft_save = outleft;
+      idx_t outleft_save = outleft;
       if (ctx_i == 0 && !flush_ctx)
         {
           while (true)
@@ -577,17 +570,17 @@ base64_decode_ctx (struct base64_decode_context *ctx,
    undefined. */
 bool
 base64_decode_alloc_ctx (struct base64_decode_context *ctx,
-                         const char *in, size_t inlen, char **out,
-                         size_t *outlen)
+                         const char *in, idx_t inlen, char **out,
+                         idx_t *outlen)
 {
   /* This may allocate a few bytes too many, depending on input,
      but it's not worth the extra CPU time to compute the exact size.
      The exact size is 3 * (inlen + (ctx ? ctx->i : 0)) / 4, minus 1 if the
      input ends with "=" and minus another 1 if the input ends with "==".
-     Dividing before multiplying avoids the possibility of overflow.  */
-  size_t needlen = 3 * (inlen / 4) + 3;
+     Shifting before multiplying avoids the possibility of overflow.  */
+  idx_t needlen = 3 * ((inlen >> 2) + 1);
 
-  *out = malloc (needlen);
+  *out = imalloc (needlen);
   if (!*out)
     return true;
 
diff --git a/lib/base64.h b/lib/base64.h
index e45f1db728..e58ccfb1fb 100644
--- a/lib/base64.h
+++ b/lib/base64.h
@@ -18,8 +18,8 @@
 #ifndef BASE64_H
 # define BASE64_H
 
-/* Get size_t. */
-# include <stddef.h>
+/* Get idx_t.  */
+# include <idx.h>
 
 /* Get bool. */
 # include <stdbool.h>
@@ -34,26 +34,26 @@ extern "C" {
 
 struct base64_decode_context
 {
-  unsigned int i;
+  int i;
   char buf[4];
 };
 
 extern bool isbase64 (char ch) _GL_ATTRIBUTE_CONST;
 
-extern void base64_encode (const char *restrict in, size_t inlen,
-                           char *restrict out, size_t outlen);
+extern void base64_encode (const char *restrict in, idx_t inlen,
+                           char *restrict out, idx_t outlen);
 
-extern size_t base64_encode_alloc (const char *in, size_t inlen, char **out);
+extern idx_t base64_encode_alloc (const char *in, idx_t inlen, char **out);
 
 extern void base64_decode_ctx_init (struct base64_decode_context *ctx);
 
 extern bool base64_decode_ctx (struct base64_decode_context *ctx,
-                               const char *restrict in, size_t inlen,
-                               char *restrict out, size_t *outlen);
+                               const char *restrict in, idx_t inlen,
+                               char *restrict out, idx_t *outlen);
 
 extern bool base64_decode_alloc_ctx (struct base64_decode_context *ctx,
-                                     const char *in, size_t inlen,
-                                     char **out, size_t *outlen);
+                                     const char *in, idx_t inlen,
+                                     char **out, idx_t *outlen);
 
 #define base64_decode(in, inlen, out, outlen) \
         base64_decode_ctx (NULL, in, inlen, out, outlen)
diff --git a/modules/base32 b/modules/base32
index 20f38cf1a0..659081d7e3 100644
--- a/modules/base32
+++ b/modules/base32
@@ -7,8 +7,10 @@ lib/base32.c
 m4/base32.m4
 
 Depends-on:
+ialloc
 stdbool
 memchr
+verify
 
 configure.ac:
 gl_FUNC_BASE32
diff --git a/modules/base64 b/modules/base64
index b1a3513b7d..717c0697d1 100644
--- a/modules/base64
+++ b/modules/base64
@@ -7,8 +7,10 @@ lib/base64.c
 m4/base64.m4
 
 Depends-on:
+ialloc
 stdbool
 memchr
+verify
 
 configure.ac:
 gl_FUNC_BASE64
diff --git a/tests/test-base32.c b/tests/test-base32.c
index 0f7a43894d..24c46567de 100644
--- a/tests/test-base32.c
+++ b/tests/test-base32.c
@@ -34,7 +34,7 @@ main (void)
   const char *in = "abcdefghijklmnop";
   const char *b32in = "MFRGGZDFMZTWQ2LKNNWG23TPOA======";
   char out[255];
-  size_t len;
+  idx_t len;
   bool ok;
   char *p;
 
diff --git a/tests/test-base64.c b/tests/test-base64.c
index c16e50267e..bc75acd95f 100644
--- a/tests/test-base64.c
+++ b/tests/test-base64.c
@@ -33,7 +33,7 @@ main (void)
   const char *in = "abcdefghijklmnop";
   const char *b64in = "YWJjZGVmZw==";
   char out[255];
-  size_t len;
+  idx_t len;
   bool ok;
   char *p;
 
-- 
2.31.1