summaryrefslogtreecommitdiff
path: root/gl
diff options
context:
space:
mode:
Diffstat (limited to 'gl')
-rw-r--r--gl/lib/randperm.c27
-rw-r--r--gl/modules/randperm2
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