Make tokenizer throw error on empty char literal, along with some slight cleanups...
[ccan] / 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 #if !defined(ILOG_NODEBRUIJN)&& \
20  !defined(CLZ32)||!defined(CLZ64)&&LONG_MAX<9223372036854775807LL
21 static const unsigned char DEBRUIJN_IDX32[32]={
22    0, 1,28, 2,29,14,24, 3,30,22,20,15,25,17, 4, 8,
23   31,27,13,23,21,19,16, 7,26,12,18, 6,11, 5,10, 9
24 };
25 #endif
26
27 int ilog32(uint32_t _v){
28 #if defined(CLZ32)
29   return (CLZ32_OFFS-CLZ32(_v))&-!!_v;
30 #else
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 #endif
66 }
67
68 int ilog64(uint64_t _v){
69 #if defined(CLZ64)
70   return (CLZ64_OFFS-CLZ64(_v))&-!!_v;
71 #else
72 # if defined(ILOG_NODEBRUIJN)
73   uint32_t v;
74   int      ret;
75   int      m;
76   ret=_v>0;
77   m=(_v>0xFFFFFFFFU)<<5;
78   v=(uint32_t)(_v>>m);
79   ret|=m;
80   m=(v>0xFFFFU)<<4;
81   v>>=m;
82   ret|=m;
83   m=(v>0xFFU)<<3;
84   v>>=m;
85   ret|=m;
86   m=(v>0xFU)<<2;
87   v>>=m;
88   ret|=m;
89   m=(v>3)<<1;
90   v>>=m;
91   ret|=m;
92   ret+=v>1;
93   return ret;
94 # else
95 /*If we don't have a 64-bit word, split it into two 32-bit halves.*/
96 #  if LONG_MAX<9223372036854775807LL
97   uint32_t v;
98   int      ret;
99   int      m;
100   ret=_v>0;
101   m=(_v>0xFFFFFFFFU)<<5;
102   v=(uint32_t)(_v>>m);
103   ret|=m;
104   v|=v>>1;
105   v|=v>>2;
106   v|=v>>4;
107   v|=v>>8;
108   v|=v>>16;
109   v=(v>>1)+1;
110   ret+=DEBRUIJN_IDX32[v*0x77CB531U>>27&0x1F];
111   return ret;
112 /*Otherwise do it in one 64-bit operation.*/
113 #  else
114   static const unsigned char DEBRUIJN_IDX64[64]={
115      0, 1, 2, 7, 3,13, 8,19, 4,25,14,28, 9,34,20,40,
116      5,17,26,38,15,46,29,48,10,31,35,54,21,50,41,57,
117     63, 6,12,18,24,27,33,39,16,37,45,47,30,53,49,56,
118     62,11,23,32,36,44,52,55,61,22,43,51,60,42,59,58
119   };
120   int ret;
121   ret=_v>0;
122   _v|=_v>>1;
123   _v|=_v>>2;
124   _v|=_v>>4;
125   _v|=_v>>8;
126   _v|=_v>>16;
127   _v|=_v>>32;
128   _v=(_v>>1)+1;
129   ret+=DEBRUIJN_IDX64[_v*0x218A392CD3D5DBF>>58&0x3F];
130   return ret;
131 #  endif
132 # endif
133 #endif
134 }