diff options
Diffstat (limited to 'gl')
-rw-r--r-- | gl/lib/randperm.c | 27 | ||||
-rw-r--r-- | 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 |