git.ozlabs.org Git - ccan/blob - ccan/ilog/ilog.c

   1 /*(C) Timothy B. Terriberry (tterribe@xiph.org) 2001-2009 LGPL (v2 or later).*/
   2 #include "ilog.h"
   3 #include <limits.h>
   4
   5 /*The fastest fallback strategy for platforms with fast multiplication appears
   6    to be based on de Bruijn sequences~\cite{LP98}.
   7   Tests confirmed this to be true even on an ARM11, where it is actually faster
   8    than using the native clz instruction.
   9   Define ILOG_NODEBRUIJN to use a simpler fallback on platforms where
  10    multiplication or table lookups are too expensive.
  11
  12   @UNPUBLISHED{LP98,
  13     author="Charles E. Leiserson and Harald Prokop",
  14     title="Using de {Bruijn} Sequences to Index a 1 in a Computer Word",
  15     month=Jun,
  16     year=1998,
  17     note="\url{http://supertech.csail.mit.edu/papers/debruijn.pdf}"
  18   }*/
  19 static UNNEEDED const unsigned char DEBRUIJN_IDX32[32]={
  20    0, 1,28, 2,29,14,24, 3,30,22,20,15,25,17, 4, 8,
  21   31,27,13,23,21,19,16, 7,26,12,18, 6,11, 5,10, 9
  22 };
  23
  24 /* We always compile these in, in case someone takes address of function. */
  25 #undef ilog32_nz
  26 #undef ilog32
  27 #undef ilog64_nz
  28 #undef ilog64
  29
  30 int ilog32(uint32_t _v){
  31 /*On a Pentium M, this branchless version tested as the fastest version without
  32    multiplications on 1,000,000,000 random 32-bit integers, edging out a
  33    similar version with branches, and a 256-entry LUT version.*/
  34 # if defined(ILOG_NODEBRUIJN)
  35   int ret;
  36   int m;
  37   ret=_v>0;
  38   m=(_v>0xFFFFU)<<4;
  39   _v>>=m;
  40   ret|=m;
  41   m=(_v>0xFFU)<<3;
  42   _v>>=m;
  43   ret|=m;
  44   m=(_v>0xFU)<<2;
  45   _v>>=m;
  46   ret|=m;
  47   m=(_v>3)<<1;
  48   _v>>=m;
  49   ret|=m;
  50   ret+=_v>1;
  51   return ret;
  52 /*This de Bruijn sequence version is faster if you have a fast multiplier.*/
  53 # else
  54   int ret;
  55   ret=_v>0;
  56   _v|=_v>>1;
  57   _v|=_v>>2;
  58   _v|=_v>>4;
  59   _v|=_v>>8;
  60   _v|=_v>>16;
  61   _v=(_v>>1)+1;
  62   ret+=DEBRUIJN_IDX32[_v*0x77CB531U>>27&0x1F];
  63   return ret;
  64 # endif
  65 }
  66
  67 int ilog32_nz(uint32_t _v)
  68 {
  69   return ilog32(_v);
  70 }
  71
  72 int ilog64(uint64_t _v){
  73 # if defined(ILOG_NODEBRUIJN)
  74   uint32_t v;
  75   int      ret;
  76   int      m;
  77   ret=_v>0;
  78   m=(_v>0xFFFFFFFFU)<<5;
  79   v=(uint32_t)(_v>>m);
  80   ret|=m;
  81   m=(v>0xFFFFU)<<4;
  82   v>>=m;
  83   ret|=m;
  84   m=(v>0xFFU)<<3;
  85   v>>=m;
  86   ret|=m;
  87   m=(v>0xFU)<<2;
  88   v>>=m;
  89   ret|=m;
  90   m=(v>3)<<1;
  91   v>>=m;
  92   ret|=m;
  93   ret+=v>1;
  94   return ret;
  95 # else
  96 /*If we don't have a 64-bit word, split it into two 32-bit halves.*/
  97 #  if LONG_MAX<9223372036854775807LL
  98   uint32_t v;
  99   int      ret;
 100   int      m;
 101   ret=_v>0;
 102   m=(_v>0xFFFFFFFFU)<<5;
 103   v=(uint32_t)(_v>>m);
 104   ret|=m;
 105   v|=v>>1;
 106   v|=v>>2;
 107   v|=v>>4;
 108   v|=v>>8;
 109   v|=v>>16;
 110   v=(v>>1)+1;
 111   ret+=DEBRUIJN_IDX32[v*0x77CB531U>>27&0x1F];
 112   return ret;
 113 /*Otherwise do it in one 64-bit operation.*/
 114 #  else
 115   static const unsigned char DEBRUIJN_IDX64[64]={
 116      0, 1, 2, 7, 3,13, 8,19, 4,25,14,28, 9,34,20,40,
 117      5,17,26,38,15,46,29,48,10,31,35,54,21,50,41,57,
 118     63, 6,12,18,24,27,33,39,16,37,45,47,30,53,49,56,
 119     62,11,23,32,36,44,52,55,61,22,43,51,60,42,59,58
 120   };
 121   int ret;
 122   ret=_v>0;
 123   _v|=_v>>1;
 124   _v|=_v>>2;
 125   _v|=_v>>4;
 126   _v|=_v>>8;
 127   _v|=_v>>16;
 128   _v|=_v>>32;
 129   _v=(_v>>1)+1;
 130   ret+=DEBRUIJN_IDX64[_v*0x218A392CD3D5DBF>>58&0x3F];
 131   return ret;
 132 #  endif
 133 # endif
 134 }
 135
 136 int ilog64_nz(uint64_t _v)
 137 {
 138   return ilog64(_v);
 139 }
 140