ilog: rework to reduce interface.
authorRusty Russell <rusty@rustcorp.com.au>
Tue, 26 Oct 2010 03:59:36 +0000 (14:29 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Tue, 26 Oct 2010 08:59:58 +0000 (19:29 +1030)
If you've not got gcc, this is a bit of a lose.  But for everyone else,
it's far simpler.

ccan/alloc/_info
ccan/alloc/bitops.c
ccan/ilog/_info
ccan/ilog/ilog.c
ccan/ilog/ilog.h
ccan/ilog/test/run-out-of-line.c [new file with mode: 0644]
ccan/ilog/test/run.c
ccan/isaac/isaac.c
ccan/isaac/isaac64.c
ccan/tdb2/_info
ccan/tdb2/free.c

index 68e40b6d4346db3c10bc4cb4b57b2ec03bcfa559..70c65b7ea50ca935052bbd72535094defa00cfb6 100644 (file)
@@ -104,6 +104,7 @@ int main(int argc, char *argv[])
                printf("ccan/alignof\n");
                printf("ccan/build_assert\n");
                printf("ccan/compiler\n");
+               printf("ccan/ilog\n");
                printf("ccan/likely\n");
                printf("ccan/short_types\n");
                return 0;
index ad4465f93b746555d543c5d83b4e32684d242b62..b408a20f0e579d8ce83228f1fc60a79a6f7e844f 100644 (file)
@@ -1,40 +1,17 @@
 #include "bitops.h"
 #include "config.h"
+#include <ccan/build_assert/build_assert.h>
 #include <ccan/short_types/short_types.h>
+#include <ccan/ilog/ilog.h>
 #include <limits.h>
 
 unsigned int fls(unsigned long val)
 {
-#if HAVE_BUILTIN_CLZL
-       /* This is significantly faster! */
-       return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0;
-#else
-       unsigned int r = 32;
-
-       if (!val)
-               return 0;
-       if (!(val & 0xffff0000u)) {
-               val <<= 16;
-               r -= 16;
-       }
-       if (!(val & 0xff000000u)) {
-               val <<= 8;
-               r -= 8;
-       }
-       if (!(val & 0xf0000000u)) {
-               val <<= 4;
-               r -= 4;
-       }
-       if (!(val & 0xc0000000u)) {
-               val <<= 2;
-               r -= 2;
-       }
-       if (!(val & 0x80000000u)) {
-               val <<= 1;
-               r -= 1;
-       }
-       return r;
-#endif
+       BUILD_ASSERT(sizeof(val) == sizeof(u32) || sizeof(val) == sizeof(u64));
+       if (sizeof(val) == sizeof(u32))
+               return ilog32(val);
+       else
+               return ilog64(val);
 }
 
 /* FIXME: Move to bitops. */
index 59e556656a6e30064db022aad78ba79cd5453efa..066dcb89e0218beff72b1963ff7105f2d7fadfe6 100644 (file)
@@ -1,12 +1,12 @@
 /**
  * ilog - Integer logarithm.
  *
- * ILOG_32() and ILOG_64() compute the minimum number of bits required to store
+ * ilog_32() and ilog_64() compute the minimum number of bits required to store
  *  an unsigned 32-bit or 64-bit value without any leading zero bits.
  * This can also be thought of as the location of the highest set bit, with
  *  counting starting from one (so that 0 returns 0, 1 returns 1, and 2**31
  *  returns 32).
- * When the value is known to be non-zero ILOGNZ_32() and ILOGNZ_64() can
+ * When the value is known to be non-zero ilog32_nz() and ilog64_nz() can
  *  compile into as few as two instructions, one of which may get optimized out
  *  later.
  * STATIC_ILOG_32 and STATIC_ILOG_64 allow computation on compile-time
  *
  *  int main(void){
  *    int i;
- *    printf("ILOG_32(0x%08X)=%i\n",0,ILOG_32(0));
+ *    printf("ilog32(0x%08X)=%i\n",0,ilog32(0));
  *    for(i=1;i<=STATIC_ILOG_32(USHRT_MAX);i++){
  *      uint32_t v;
  *      v=(uint32_t)1U<<(i-1);
- *      //Here we know v is non-zero, so we can use ILOGNZ_32().
- *      printf("ILOG_32(0x%08X)=%i\n",v,ILOGNZ_32(v));
+ *      //Here we know v is non-zero, so we can use ilog32_nz().
+ *      printf("ilog32(0x%08X)=%i\n",v,ilog32_nz(v));
  *    }
  *    return 0;
  *  }
  * License: LGPL (v2 or later)
  */
 #include <string.h>
+#include <stdio.h>
 #include "config.h"
 
 int main(int _argc,const char *_argv[]){
   /*Expect exactly one argument.*/
   if(_argc!=2)return 1;
   if(strcmp(_argv[1],"depends")==0){
-    /*PRINTF-CCAN-PACKAGES-YOU-NEED-ONE-PER-LINE-IF-ANY*/
+    printf("ccan/compiler\n");
     return 0;
   }
   return 1;
index ed39d1922aeda5ae675c5824aa52c3d00c6df97a..17fc14d23bcb136138e253c474a96f61cee54e62 100644 (file)
     year=1998,
     note="\url{http://supertech.csail.mit.edu/papers/debruijn.pdf}"
   }*/
-#if !defined(ILOG_NODEBRUIJN)&& \
- !defined(CLZ32)||!defined(CLZ64)&&LONG_MAX<9223372036854775807LL
-static const unsigned char DEBRUIJN_IDX32[32]={
+static UNNEEDED_ATTRIBUTE const unsigned char DEBRUIJN_IDX32[32]={
    0, 1,28, 2,29,14,24, 3,30,22,20,15,25,17, 4, 8,
   31,27,13,23,21,19,16, 7,26,12,18, 6,11, 5,10, 9
 };
-#endif
+
+/* We always compile these in, in case someone takes address of function. */
+#undef ilog32_nz
+#undef ilog32
+#undef ilog64_nz
+#undef ilog64
 
 int ilog32(uint32_t _v){
-#if defined(CLZ32)
-  return (CLZ32_OFFS-CLZ32(_v))&-!!_v;
-#else
 /*On a Pentium M, this branchless version tested as the fastest version without
    multiplications on 1,000,000,000 random 32-bit integers, edging out a
    similar version with branches, and a 256-entry LUT version.*/
@@ -62,13 +62,14 @@ int ilog32(uint32_t _v){
   ret+=DEBRUIJN_IDX32[_v*0x77CB531U>>27&0x1F];
   return ret;
 # endif
-#endif
+}
+
+int ilog32_nz(uint32_t _v)
+{
+  return ilog32(_v);
 }
 
 int ilog64(uint64_t _v){
-#if defined(CLZ64)
-  return (CLZ64_OFFS-CLZ64(_v))&-!!_v;
-#else
 # if defined(ILOG_NODEBRUIJN)
   uint32_t v;
   int      ret;
@@ -130,5 +131,10 @@ int ilog64(uint64_t _v){
   return ret;
 #  endif
 # endif
-#endif
 }
+
+int ilog64_nz(uint64_t _v)
+{
+  return ilog64(_v);
+}
+
index ed91f4eaf830de7192cf27c84a51b145eb899f2c..fdb9ebab8d70c427d275d28077f3b7a180f8bbb2 100644 (file)
@@ -2,30 +2,8 @@
 # define _ilog_H (1)
 # include "config.h"
 # include <stdint.h>
-# include <ccan/compiler/compiler.h>
 # include <limits.h>
-/*Note the casts to (int) below: this prevents CLZ{32|64}_OFFS from "upgrading"
-   the type of an entire expression to an (unsigned) size_t.*/
-# if HAVE_BUILTIN_CLZ && INT_MAX>=2147483647
-#  define CLZ32_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
-#  define CLZ32(_x) (__builtin_clz(_x))
-# elif HAVE_BUILTIN_CLZL && LONG_MAX>=2147483647L
-#  define CLZ32_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
-#  define CLZ32(_x) (__builtin_clzl(_x))
-# endif
-
-# if HAVE_BUILTIN_CLZ && INT_MAX>=9223372036854775807LL
-#  define CLZ64_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
-#  define CLZ64(_x) (__builtin_clz(_x))
-# elif HAVE_BUILTIN_CLZL && LONG_MAX>=9223372036854775807LL
-#  define CLZ64_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
-#  define CLZ64(_x) (__builtin_clzl(_x))
-# elif HAVE_BUILTIN_CLZLL /* long long must be >= 64 bits according to ISO C */
-#  define CLZ64_OFFS ((int)sizeof(unsigned long long)*CHAR_BIT)
-#  define CLZ64(_x) (__builtin_clzll(_x))
-# endif
-
-
+# include <ccan/compiler/compiler.h>
 
 /**
  * ilog32 - Integer binary logarithm of a 32-bit value.
  * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
- * The ILOG_32() or ILOGNZ_32() macros may be able to use a builtin function
- *  instead, which should be faster.
+ * Note that many uses will resolve to the fast macro version instead.
+ *
+ * See Also:
+ *     ilog32_nz(), ilog64()
+ *
+ * Example:
+ *     // Rounds up to next power of 2 (if not a power of 2).
+ *     static uint32_t round_up32(uint32_t i)
+ *     {
+ *             assert(i != 0);
+ *             return 1U << ilog32(i-1);
+ *     }
  */
 int ilog32(uint32_t _v) IDEMPOTENT_ATTRIBUTE;
+
+/**
+ * ilog32_nz - Integer binary logarithm of a non-zero 32-bit value.
+ * @_v: A 32-bit value.
+ * Returns floor(log2(_v))+1, or undefined if _v==0.
+ * This is the number of bits that would be required to represent _v in two's
+ *  complement notation with all of the leading zeros stripped.
+ * Note that many uses will resolve to the fast macro version instead.
+ * See Also:
+ *     ilog32(), ilog64_nz()
+ * Example:
+ *     // Find Last Set (ie. highest bit set, 0 to 31).
+ *     static uint32_t fls32(uint32_t i)
+ *     {
+ *             assert(i != 0);
+ *             return ilog32_nz(i) - 1;
+ *     }
+ */
+int ilog32_nz(uint32_t _v) IDEMPOTENT_ATTRIBUTE;
+
 /**
  * ilog64 - Integer binary logarithm of a 64-bit value.
  * @_v: A 64-bit value.
  * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
- * The ILOG_64() or ILOGNZ_64() macros may be able to use a builtin function
- *  instead, which should be faster.
+ * Note that many uses will resolve to the fast macro version instead.
+ * See Also:
+ *     ilog64_nz(), ilog32()
  */
 int ilog64(uint64_t _v) IDEMPOTENT_ATTRIBUTE;
 
-
-# if defined(CLZ32)
 /**
- * ILOGNZ_32 - Integer binary logarithm of a non-zero 32-bit value.
- * @_v: A non-zero 32-bit value.
- * Returns floor(log2(_v))+1.
+ * ilog64_nz - Integer binary logarithm of a non-zero 64-bit value.
+ * @_v: A 64-bit value.
+ * Returns floor(log2(_v))+1, or undefined if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
- * If _v is zero, the return value is undefined; use ILOG_32() instead.
+ * Note that many uses will resolve to the fast macro version instead.
+ * See Also:
+ *     ilog64(), ilog32_nz()
  */
-#  define ILOGNZ_32(_v) (CLZ32_OFFS-CLZ32(_v))
+int ilog64_nz(uint64_t _v) IDEMPOTENT_ATTRIBUTE;
+
 /**
- * ILOG_32 - Integer binary logarithm of a 32-bit value.
- * @_v: A 32-bit value.
+ * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
+ * @_v: A non-negative 32-bit constant.
  * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
+ * This macro should only be used when you need a compile-time constant,
+ * otherwise ilog32 or ilog32_nz are just as fast and more flexible.
+ *
+ * Example:
+ *     #define MY_PAGE_SIZE    4096
+ *     #define MY_PAGE_BITS    (STATIC_ILOG_32(PAGE_SIZE) - 1)
  */
-#  define ILOG_32(_v)   (ILOGNZ_32(_v)&-!!(_v))
-# else
-#  define ILOGNZ_32(_v) (ilog32(_v))
-#  define ILOG_32(_v)   (ilog32(_v))
-# endif
+#define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
 
-# if defined(CLZ64)
 /**
- * ILOGNZ_64 - Integer binary logarithm of a non-zero 64-bit value.
- * @_v: A non-zero 64-bit value.
- * Returns floor(log2(_v))+1.
- * This is the number of bits that would be required to represent _v in two's
- *  complement notation with all of the leading zeros stripped.
- * If _v is zero, the return value is undefined; use ILOG_64() instead.
- */
-#  define ILOGNZ_64(_v) (CLZ64_OFFS-CLZ64(_v))
-/**
- * ILOG_64 - Integer binary logarithm of a 64-bit value.
- * @_v: A 64-bit value.
+ * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
+ * @_v: A non-negative 64-bit constant.
  * Returns floor(log2(_v))+1, or 0 if _v==0.
  * This is the number of bits that would be required to represent _v in two's
  *  complement notation with all of the leading zeros stripped.
+ * This macro should only be used when you need a compile-time constant,
+ * otherwise ilog64 or ilog64_nz are just as fast and more flexible.
  */
-#  define ILOG_64(_v)   (ILOGNZ_64(_v)&-!!(_v))
-# else
-#  define ILOGNZ_64(_v) (ilog64(_v))
-#  define ILOG_64(_v)   (ilog64(_v))
-# endif
+#define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
+
+/* Private implementation details */
+
+/*Note the casts to (int) below: this prevents "upgrading"
+   the type of an entire expression to an (unsigned) size_t.*/
+#if INT_MAX>=2147483647 && HAVE_BUILTIN_CLZ
+#define builtin_ilog32_nz(v) \
+       (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
+#elif LONG_MAX>=2147483647L && HAVE_BUILTIN_CLZL
+#define builtin_ilog32_nz(v) \
+       (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clzl(v))
+#endif
+
+#if INT_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZ
+#define builtin_ilog64_nz(v) \
+       (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
+#elif LONG_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZL
+#define builtin_ilog64_nz(v) \
+       (((int)sizeof(unsigned long)*CHAR_BIT) - __builtin_clzl(v))
+#elif HAVE_BUILTIN_CLZLL
+#define builtin_ilog64_nz(v) \
+       (((int)sizeof(unsigned long long)*CHAR_BIT) - __builtin_clzll(v))
+#endif
+
+#ifdef builtin_ilog32_nz
+#define ilog32(_v) (builtin_ilog32_nz(_v)&-!!(_v))
+#define ilog32_nz(_v) builtin_ilog32_nz(_v)
+#else
+#define ilog32_nz(_v) ilog32(_v)
+#define ilog32(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_32(_v) : ilog32(_v))
+#endif /* builtin_ilog32_nz */
+
+#ifdef builtin_ilog64_nz
+#define ilog64(_v) (builtin_ilog64_nz(_v)&-!!(_v))
+#define ilog64_nz(_v) builtin_ilog64_nz(_v)
+#else
+#define ilog64_nz(_v) ilog64(_v)
+#define ilog64(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_64(_v) : ilog64(_v))
+#endif /* builtin_ilog64_nz */
 
+/* Macros for evaluating compile-time constant ilog. */
 # define STATIC_ILOG0(_v) (!!(_v))
 # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v))
 # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v))
@@ -106,27 +146,5 @@ int ilog64(uint64_t _v) IDEMPOTENT_ATTRIBUTE;
  (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v))
 # define STATIC_ILOG6(_v) \
  (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v))
-/**
- * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
- * @_v: A non-negative 32-bit constant.
- * Returns floor(log2(_v))+1, or 0 if _v==0.
- * This is the number of bits that would be required to represent _v in two's
- *  complement notation with all of the leading zeros stripped.
- * This macro is suitable for evaluation at compile time, but it should not be
- *  used on values that can change at runtime, as it operates via exhaustive
- *  search.
- */
-# define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
-/**
- * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
- * @_v: A non-negative 64-bit constant.
- * Returns floor(log2(_v))+1, or 0 if _v==0.
- * This is the number of bits that would be required to represent _v in two's
- *  complement notation with all of the leading zeros stripped.
- * This macro is suitable for evaluation at compile time, but it should not be
- *  used on values that can change at runtime, as it operates via exhaustive
- *  search.
- */
-# define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
 
-#endif
+#endif /* _ilog_H */
diff --git a/ccan/ilog/test/run-out-of-line.c b/ccan/ilog/test/run-out-of-line.c
new file mode 100644 (file)
index 0000000..48205d3
--- /dev/null
@@ -0,0 +1,65 @@
+#include <ccan/ilog/ilog.h>
+#include <ccan/ilog/ilog.c>
+#include <stdio.h>
+#include <ccan/tap/tap.h>
+
+/*Dead simple (but slow) versions to compare against.*/
+
+static int test_ilog32(uint32_t _v){
+  int ret;
+  for(ret=0;_v;ret++)_v>>=1;
+  return ret;
+}
+
+static int test_ilog64(uint64_t _v){
+  int ret;
+  for(ret=0;_v;ret++)_v>>=1;
+  return ret;
+}
+
+#define NTRIALS (64)
+
+int main(int _argc,const char *_argv[]){
+  int i;
+  int j;
+  int (*il32)(uint32_t) = ilog32;
+  int (*il64)(uint64_t) = ilog64;
+  int (*il32_nz)(uint32_t) = ilog32_nz;
+  int (*il64_nz)(uint64_t) = ilog64_nz;
+
+  /*This is how many tests you plan to run.*/
+  plan_tests(33 * NTRIALS * 3 + 65 * NTRIALS * 3);
+  for(i=0;i<=32;i++){
+    uint32_t v;
+    /*Test each bit in turn (and 0).*/
+    v=i?(uint32_t)1U<<(i-1):0;
+    for(j=0;j<NTRIALS;j++){
+      int l;
+      l=test_ilog32(v);
+      ok1(STATIC_ILOG_32(v)==l);
+      ok1(il32(v)==l);
+      ok1(il32_nz(v) == l || v == 0);
+      /*Also try a few more pseudo-random values with at most the same number
+         of bits.*/
+      v=(1103515245U*v+12345U)&0xFFFFFFFFU>>((33-i)>>1)>>((32-i)>>1);
+    }
+  }
+
+  for(i=0;i<=64;i++){
+    uint64_t v;
+    /*Test each bit in turn (and 0).*/
+    v=i?(uint64_t)1U<<(i-1):0;
+    for(j=0;j<NTRIALS;j++){
+      int l;
+      l=test_ilog64(v);
+      ok1(STATIC_ILOG_64(v)==l);
+      ok1(il64(v)==l);
+      ok1(il64_nz(v) == l || v == 0);
+      /*Also try a few more pseudo-random values with at most the same number
+         of bits.*/
+      v=(uint64_t)((2862933555777941757ULL*v+3037000493ULL)
+       &0xFFFFFFFFFFFFFFFFULL>>((65-i)>>1)>>((64-i)>>1));
+    }
+  }
+  return exit_status();
+}
index ce19293aefc1b27d138b72827adf4e40256fff00..bda59f920a33e115958eeff8b91a6a6a8d2eb966 100644 (file)
@@ -20,12 +20,10 @@ static int test_ilog64(uint64_t _v){
 #define NTRIALS (64)
 
 int main(int _argc,const char *_argv[]){
-  int nmatches;
   int i;
   int j;
   /*This is how many tests you plan to run.*/
-  plan_tests(2);
-  nmatches=0;
+  plan_tests(33 * NTRIALS * 3 + 65 * NTRIALS * 3);
   for(i=0;i<=32;i++){
     uint32_t v;
     /*Test each bit in turn (and 0).*/
@@ -33,26 +31,15 @@ int main(int _argc,const char *_argv[]){
     for(j=0;j<NTRIALS;j++){
       int l;
       l=test_ilog32(v);
-      if(ILOG_32(v)!=l){
-        fprintf(stderr,"ILOG_32(0x%08lX): %i != %i\n",(long)v,ILOG_32(v),l);
-      }
-      else nmatches++;
-      if(ilog32(v)!=l){
-        fprintf(stderr,"ilog32(0x%08lX): %i != %i\n",(long)v,ilog32(v),l);
-      }
-      else nmatches++;
-      if(STATIC_ILOG_32(v)!=l){
-        fprintf(stderr,"STATIC_ILOG_32(0x%08lX): %i != %i\n",
-         (long)v,STATIC_ILOG_32(v),l);
-      }
-      else nmatches++;
+      ok1(STATIC_ILOG_32(v)==l);
+      ok1(ilog32(v)==l);
+      ok1(ilog32_nz(v) == l || v == 0);
       /*Also try a few more pseudo-random values with at most the same number
          of bits.*/
       v=(1103515245U*v+12345U)&0xFFFFFFFFU>>((33-i)>>1)>>((32-i)>>1);
     }
   }
-  ok1(nmatches==3*(32+1)*NTRIALS);
-  nmatches=0;
+
   for(i=0;i<=64;i++){
     uint64_t v;
     /*Test each bit in turn (and 0).*/
@@ -60,27 +47,14 @@ int main(int _argc,const char *_argv[]){
     for(j=0;j<NTRIALS;j++){
       int l;
       l=test_ilog64(v);
-      if(ILOG_64(v)!=l){
-        fprintf(stderr,"ILOG_64(0x%016llX): %i != %i\n",
-         (long long)v,ILOG_64(v),l);
-      }
-      else nmatches++;
-      if(ilog64(v)!=l){
-        fprintf(stderr,"ilog64(0x%016llX): %i != %i\n",
-         (long long)v,ilog64(v),l);
-      }
-      else nmatches++;
-      if(STATIC_ILOG_64(v)!=l){
-        fprintf(stderr,"STATIC_ILOG_64(0x%016llX): %i != %i\n",
-         (long long)v,STATIC_ILOG_64(v),l);
-      }
-      else nmatches++;
+      ok1(STATIC_ILOG_64(v)==l);
+      ok1(ilog64(v)==l);
+      ok1(ilog64_nz(v) == l || v == 0);
       /*Also try a few more pseudo-random values with at most the same number
          of bits.*/
       v=(uint64_t)((2862933555777941757ULL*v+3037000493ULL)
        &0xFFFFFFFFFFFFFFFFULL>>((65-i)>>1)>>((64-i)>>1));
     }
   }
-  ok1(nmatches==3*(64+1)*NTRIALS);
   return exit_status();
 }
index 88a1d0d5dadc62506356da6f2b9e7eec3b8ea789..b35ac41700ecd507de51d799b905b10d074f071b 100644 (file)
@@ -170,7 +170,7 @@ static float isaac_float_bits(isaac_ctx *_ctx,uint32_t _bits,int _base){
      FLT_MANT_DIG+1 consecutive one bits.
     Even the fallback C implementation of ILOGNZ_32() yields an implementation
      25% faster than the frexp() method.*/
-  nbits_needed=FLT_MANT_DIG-ILOGNZ_32(_bits);
+  nbits_needed=FLT_MANT_DIG-ilog32_nz(_bits);
 #if FLT_MANT_DIG>32
   ret=ldexpf((float)_bits,_base);
 # if FLT_MANT_DIG>65
@@ -221,7 +221,7 @@ static double isaac_double_bits(isaac_ctx *_ctx,uint32_t _bits,int _base){
     _base-=32;
     _bits=isaac_next_uint32(_ctx);
   }
-  nbits_needed=DBL_MANT_DIG-ILOGNZ_32(_bits);
+  nbits_needed=DBL_MANT_DIG-ilog32_nz(_bits);
 #if DBL_MANT_DIG>32
   ret=ldexp((double)_bits,_base);
 # if DBL_MANT_DIG>65
index 0eb47ff9de8a42767351cb04c3c3f87edc881900..43ab0e6e701127dff0fc496fa49965a4ad00f49b 100644 (file)
@@ -166,7 +166,7 @@ static float isaac64_float_bits(isaac64_ctx *_ctx,uint64_t _bits,int _base){
     _base-=64;
     _bits=isaac64_next_uint64(_ctx);
   }
-  nbits_needed=FLT_MANT_DIG-ILOGNZ_64(_bits);
+  nbits_needed=FLT_MANT_DIG-ilog64_nz(_bits);
 #if FLT_MANT_DIG>64
   ret=ldexpf((float)_bits,_base);
 # if FLT_MANT_DIG>129
@@ -217,7 +217,7 @@ static double isaac64_double_bits(isaac64_ctx *_ctx,uint64_t _bits,int _base){
     _base-=64;
     _bits=isaac64_next_uint64(_ctx);
   }
-  nbits_needed=DBL_MANT_DIG-ILOGNZ_64(_bits);
+  nbits_needed=DBL_MANT_DIG-ilog64_nz(_bits);
 #if DBL_MANT_DIG>64
   ret=ldexp((double)_bits,_base);
 # if DBL_MANT_DIG>129
index 15c68d4bbc005017a93dee97011acc4844638e66..ddb362022e3b1990f33675f6a823d2cccf373c24 100644 (file)
@@ -78,6 +78,7 @@ int main(int argc, char *argv[])
                printf("ccan/asearch\n");
                printf("ccan/compiler\n");
                printf("ccan/build_assert\n");
+               printf("ccan/ilog\n");
                printf("ccan/tally\n");
                return 0;
        }
index 5284510a07fbdfd3aa5341360c29448e3eb9f183..e6d871a58607180c9a81afec54ccbdc7a88c0e2a 100644 (file)
 */
 #include "private.h"
 #include <ccan/likely/likely.h>
+#include <ccan/ilog/ilog.h>
 #include <time.h>
 #include <assert.h>
 #include <limits.h>
 
 static unsigned fls64(uint64_t val)
 {
-#if HAVE_BUILTIN_CLZL
-       if (val <= ULONG_MAX) {
-               /* This is significantly faster! */
-               return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0;
-       } else {
-#endif
-       uint64_t r = 64;
-
-       if (!val)
-               return 0;
-       if (!(val & 0xffffffff00000000ull)) {
-               val <<= 32;
-               r -= 32;
-       }
-       if (!(val & 0xffff000000000000ull)) {
-               val <<= 16;
-               r -= 16;
-       }
-       if (!(val & 0xff00000000000000ull)) {
-               val <<= 8;
-               r -= 8;
-       }
-       if (!(val & 0xf000000000000000ull)) {
-               val <<= 4;
-               r -= 4;
-       }
-       if (!(val & 0xc000000000000000ull)) {
-               val <<= 2;
-               r -= 2;
-       }
-       if (!(val & 0x8000000000000000ull)) {
-               val <<= 1;
-               r -= 1;
-       }
-       return r;
-#if HAVE_BUILTIN_CLZL
-       }
-#endif
+       return ilog64(val);
 }
 
 /* In which bucket would we find a particular record size? (ignoring header) */