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