>From 95c705bdc03c89cdf774f90ee68452ebd46b400a Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Tue, 22 Oct 2019 12:58:07 -0700
Subject: [PATCH 3/5] shuf: improve randperm overflow checking
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* gl/lib/randperm.c: Include randperm.h first, since it’s the API.
Include stdint.h, count-leading-zeros.h, verify.h.
(floor_lg): Rename from ceil_log (which was not actually
implementing the ceiling!) and implement the floor using
count_leading_zeros.
(randperm_bound): Use floor_lg, not ceil_log.  Use uintmax_t
instead of size_t in case the size gets large on a 32-bit host.
* gl/modules/randperm (Depends-on): Add count-leading-zeros, stdint.
---
 gl/lib/randperm.c   | 27 ++++++++++++++++-----------
 gl/modules/randperm |  2 ++
 2 files changed, 18 insertions(+), 11 deletions(-)

diff --git a/gl/lib/randperm.c b/gl/lib/randperm.c
index ce69222e9..b079aba33 100644
--- a/gl/lib/randperm.c
+++ b/gl/lib/randperm.c
@@ -19,24 +19,29 @@
 
 #include <config.h>
 
-#include "hash.h"
 #include "randperm.h"
 
 #include <limits.h>
+#include <stdint.h>
 #include <stdlib.h>
 
+#include "count-leading-zeros.h"
+#include "hash.h"
+#include "verify.h"
 #include "xalloc.h"
 
-/* Return the ceiling of the log base 2 of N.  If N is zero, return
-   an unspecified value.  */
+/* Return the floor of the log base 2 of N.  If N is zero, return -1.  */
 
-static size_t _GL_ATTRIBUTE_CONST
-ceil_lg (size_t n)
+static int _GL_ATTRIBUTE_CONST
+floor_lg (size_t n)
 {
-  size_t b = 0;
-  for (n--; n != 0; n /= 2)
-    b++;
-  return b;
+  verify (SIZE_WIDTH <= ULLONG_WIDTH);
+  return (n == 0 ? -1
+          : SIZE_WIDTH <= UINT_WIDTH
+          ? UINT_WIDTH - 1 - count_leading_zeros (n)
+          : SIZE_WIDTH <= ULONG_WIDTH
+          ? ULONG_WIDTH - 1 - count_leading_zeros_l (n)
+          : ULLONG_WIDTH - 1 - count_leading_zeros_ll (n));
 }
 
 /* Return an upper bound on the number of random bytes needed to
@@ -48,10 +53,10 @@ randperm_bound (size_t h, size_t n)
 {
   /* Upper bound on number of bits needed to generate the first number
      of the permutation.  */
-  size_t lg_n = ceil_lg (n);
+  uintmax_t lg_n = floor_lg (n) + 1;
 
   /* Upper bound on number of bits needed to generated the first H elements.  */
-  size_t ar = lg_n * h;
+  uintmax_t ar = lg_n * h;
 
   /* Convert the bit count to a byte count.  */
   size_t bound = (ar + CHAR_BIT - 1) / CHAR_BIT;
diff --git a/gl/modules/randperm b/gl/modules/randperm
index 1fa261290..e3b347140 100644
--- a/gl/modules/randperm
+++ b/gl/modules/randperm
@@ -6,7 +6,9 @@ lib/randperm.c
 lib/randperm.h
 
 Depends-on:
+count-leading-zeros
 randint
+stdint
 xalloc
 hash
 
-- 
2.21.0