Modifying the return value of cfg_set* functions, in order to make
[sip-router] / bit_scan.h
1 /* 
2  * $Id$
3  * 
4  * Copyright (C) 2007 iptelorg GmbH
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 /*
19  *  bit scan operations
20  *  int bit_scan_forward(unsigned long v)   - returns the index of the first
21  *                                          set bit (undefined value if v==0)
22  *  int bit_scan_forward32(unsigned int v)   - returns the index of the first
23  *                                          set bit (undefined value if v==0)
24  *  int bit_scan_forward64(long long v)      - returns the index of the first
25  *                                          set bit (undefined value if v==0)
26  *  int bit_scan_reverse(unsigned long v)   - returns the index of the last
27  *                                          set bit (undefined value if v==0)
28  *  int bit_scan_reverse32(unsigned int v)  - returns the index of the last
29  *                                          set bit (undefined value if v==0)
30  *  int bit_scan_reverse64(long long v)     - returns the index of the last
31  *                                          set bit (undefined value if v==0)
32  *
33  * Config defines:   CC_GCC_LIKE_ASM  - the compiler support gcc style
34  *                     inline asm,
35  *                  __CPU_x86, __CPU_x86_64,
36  *                  ULONG_MAX (limits.h)
37  */
38 /* 
39  * History:
40  * --------
41  *  2007-06-23  created by andrei
42  */
43
44 #ifndef _bit_scan_h
45 #define _bit_scan_h
46
47 #include <limits.h>
48
49
50 #ifdef CC_GCC_LIKE_ASM
51 #if defined __CPU_x86 || defined __CPU_x86_64
52 #define BIT_SCAN_ASM
53 #endif
54 #endif
55
56
57 /* set default bitscan versions, depending on the architecture
58  * In general the order is  asm, debruijn, br, slow for bit_scan_forward
59  *  and asm, br, slow, debruijn for bit_scan_reverse. */
60 #ifdef BIT_SCAN_ASM
61 /* have asm => use it */
62
63 #define bit_scan_forward32(i)   bit_scan_forward_asm32(i)
64 #define bit_scan_forward64(i)   bit_scan_forward_asm64(i)
65 #define bit_scan_reverse32(i)   bit_scan_reverse_asm32(i)
66 #define bit_scan_reverse64(i)   bit_scan_reverse_asm64(i)
67
68 #elif defined __CPU_x86 || defined __CPU_x86_64
69 /* no asm (e.g. no CC_GCC_LIKE_ASM) => debruijn for bit_scan_forward and
70  *  br for bit_scan_reverse */
71 /* make sure debruijn an branch version are enabled */
72 #ifndef BIT_SCAN_DEBRUIJN
73 #define BIT_SCAN_DEBRUIJN
74 #endif
75 #ifndef BIT_SCAN_BRANCH
76 #define BIT_SCAN_BRANCH
77 #endif
78
79 #define bit_scan_forward32(i)   bit_scan_forward_debruijn32(i)
80 #define bit_scan_forward64(i)   bit_scan_forward_debruijn64(i)
81 #define bit_scan_reverse32(i)   bit_scan_reverse_br32(i)
82 #define bit_scan_reverse64(i)   bit_scan_reverse_br64(i)
83
84 #elif defined __CPU_sparc64
85 /* no asm yet => use branch for everything in 64 bit mode
86  *               and debruijn + branch in 32 bit mode
87  *  (in 64bit mode the branch method is slightly faster then debruijn,
88  *   however note that in 32 bit mode the roles are reversed for _forward)*/
89 #ifndef BIT_SCAN_BRANCH
90 #define BIT_SCAN_BRANCH
91 #endif
92
93 #define bit_scan_reverse32(i)   bit_scan_reverse_br32(i)
94 #define bit_scan_reverse64(i)   bit_scan_reverse_br64(i)
95 #ifdef LP64
96 #define bit_scan_forward32(i)   bit_scan_forward_br32(i)
97 #define bit_scan_forward64(i)   bit_scan_forward_br64(i)
98 #else /* LP64 */
99
100 #ifndef BIT_SCAN_DEBRUIJN
101 #define BIT_SCAN_DEBRUIJN
102 #endif
103 #define bit_scan_forward32(i)   bit_scan_forward_debruijn32(i)
104 #define bit_scan_forward64(i)   bit_scan_forward_debruijn64(i)
105 #endif /* LP64 */
106
107 #else /* __CPU_XXX */
108 /* default - like x86 no asm */
109 /* make sure debruijn an branch version are enabled */
110 #ifndef BIT_SCAN_DEBRUIJN
111 #define BIT_SCAN_DEBRUIJN
112 #endif
113 #ifndef BIT_SCAN_BRANCH
114 #define BIT_SCAN_BRANCH
115 #endif
116
117 #define bit_scan_forward32(i)   bit_scan_forward_debruijn32(i)
118 #define bit_scan_forward64(i)   bit_scan_forward_debruijn64(i)
119 #define bit_scan_reverse32(i)   bit_scan_reverse_br32(i)
120 #define bit_scan_reverse64(i)   bit_scan_reverse_br64(i)
121
122 #endif /* __CPU_XXX */
123
124
125 /* try to use the right version for bit_scan_forward(unisgned long l)
126  */
127 #if (defined (ULONG_MAX) && ULONG_MAX > 4294967295) || defined LP64
128 /* long is 64 bits */
129 #define bit_scan_forward(l)     bit_scan_forward64((unsigned long long)(l))
130 #define bit_scan_reverse(l)     bit_scan_reverse64((unsigned long long)(l))
131
132 #else
133 /* long is 32 bits */
134 #define bit_scan_forward(l)     bit_scan_forward32((l))
135 #define bit_scan_reverse(l)     bit_scan_reverse32((l))
136 #endif
137
138
139
140
141 #ifdef BIT_SCAN_DEBRUIJN
142
143 /* use a de Bruijn sequence to get the index of the set bit for a number
144  *  of the form 2^k (DEBRUIJN_HASH32() and DEBRUIJN_HASH64()).
145  *  bit_scan_forward & bit_scan_reverse would need first to convert
146  *  the argument to 2^k (where k is the first set bit or last set bit index)-
147  *  For bit_scan_forward this can be done very fast using x & (-x).
148  *  For more info about this method see:
149  *  http://citeseer.ist.psu.edu/leiserson98using.html
150  *  ("Using de Bruijn Sequences to Index a 1 in a Computer Word")
151  */
152
153 extern unsigned char _debruijn_hash32[32]; /* see bit_scan.c */
154 extern unsigned char _debruijn_hash64[64]; /* see bit_scan.c */
155
156 #define DEBRUIJN_CT32  0x04653ADFU
157 #define DEBRUIJN_CT64  0x0218A392CD3D5DBFULL 
158
159 #define DEBRUIJN_HASH32(x)\
160         (((x)*DEBRUIJN_CT32)>>(sizeof(x)*8-5))
161
162 #define DEBRUIJN_HASH64(x)\
163         (((x)*DEBRUIJN_CT64)>>(sizeof(x)*8-6))
164
165 #define bit_scan_forward_debruijn32(x) \
166         ( _debruijn_hash32[DEBRUIJN_HASH32((x) & (-(x)))])
167
168 #define bit_scan_forward_debruijn64(x) \
169         ( _debruijn_hash64[DEBRUIJN_HASH64((x) & (-(x)))])
170
171
172 static inline int bit_scan_reverse_debruijn32(unsigned int v)
173 {
174         unsigned int last;
175         
176         do{
177                 last=v;
178                 v=v&(v-1);
179         }while(v); /* => last is 2^k */
180         return _debruijn_hash32[DEBRUIJN_HASH32(last)];
181 }
182
183
184 static inline int bit_scan_reverse_debruijn64(unsigned long long v)
185 {
186         unsigned long long last;
187         
188         do{
189                 last=v;
190                 v=v&(v-1);
191         }while(v); /* => last is 2^k */
192         return _debruijn_hash64[DEBRUIJN_HASH64(last)];
193 }
194
195
196 #endif /* BIT_SCAN_DEBRUIJN */
197
198 #ifdef BIT_SCAN_SLOW
199 /* only for reference purposes (testing the other versions against it) */
200
201 static inline int bit_scan_forward_slow32(unsigned int v)
202 {
203         int r;
204         for(r=0; r<(sizeof(v)*8); r++, v>>=1)
205                 if (v&1) return r;
206         return 0;
207 }
208
209
210 static inline int bit_scan_reverse_slow32(unsigned int v)
211 {
212         int r;
213         for(r=sizeof(v)*8-1; r>0; r--, v<<=1)
214                 if (v& (1UL<<(sizeof(v)*8-1))) return r;
215         return 0;
216 }
217
218
219 static inline int bit_scan_forward_slow64(unsigned long long v)
220 {
221         int r;
222         for(r=0; r<(sizeof(v)*8); r++, v>>=1)
223                 if (v&1ULL) return r;
224         return 0;
225 }
226
227
228 static inline int bit_scan_reverse_slow64(unsigned long long v)
229 {
230         int r;
231         for(r=sizeof(v)*8-1; r>0; r--, v<<=1)
232                 if (v& (1ULL<<(sizeof(v)*8-1))) return r;
233         return 0;
234 }
235
236
237 #endif /* BIT_SCAN_SLOW */
238
239
240 #ifdef BIT_SCAN_BRANCH
241
242 static inline int bit_scan_forward_br32(unsigned int v)
243 {
244         int b;
245         
246         b=0;
247         if (v&0x01)
248                 return 0;
249         if (!(v & 0xffff)){
250                 b+=16;
251                 v>>=16;
252         }
253         if (!(v&0xff)){
254                 b+=8;
255                 v>>=8;
256         }
257         if (!(v&0x0f)){
258                 b+=4;
259                 v>>=4;
260         }
261         if (!(v&0x03)){
262                 b+=2;
263                 v>>=2;
264         }
265         b+= !(v&0x01);
266         return b;
267 }
268
269
270 static inline int bit_scan_reverse_br32(unsigned int v)
271 {
272         int b;
273         
274         b=0;
275         if (v & 0xffff0000){
276                 b+=16;
277                 v>>=16;
278         }
279         if (v&0xff00){
280                 b+=8;
281                 v>>=8;
282         }
283         if (v&0xf0){
284                 b+=4;
285                 v>>=4;
286         }
287         if (v&0x0c){
288                 b+=2;
289                 v>>=2;
290         }
291         b+= !!(v&0x02);
292         return b;
293 }
294
295
296 static inline int bit_scan_forward_br64(unsigned long long v)
297 {
298         int b;
299         
300         b=0;
301         if (v&0x01ULL)
302                 return 0;
303         if (!(v & 0xffffffffULL)){
304                 b+=32;
305                 v>>=32;
306         }
307         if (!(v & 0xffffULL)){
308                 b+=16;
309                 v>>=16;
310         }
311         if (!(v&0xffULL)){
312                 b+=8;
313                 v>>=8;
314         }
315         if (!(v&0x0fULL)){
316                 b+=4;
317                 v>>=4;
318         }
319         if (!(v&0x03ULL)){
320                 b+=2;
321                 v>>=2;
322         }
323         b+= !(v&0x01ULL);
324         return b;
325 }
326
327
328 static inline int bit_scan_reverse_br64(unsigned long long v)
329 {
330         int b;
331         
332         b=0;
333         if (v & 0xffffffff00000000ULL){
334                 b+=32;
335                 v>>=32;
336         }
337         if (v & 0xffff0000ULL){
338                 b+=16;
339                 v>>=16;
340         }
341         if (v&0xff00ULL){
342                 b+=8;
343                 v>>=8;
344         }
345         if (v&0xf0ULL){
346                 b+=4;
347                 v>>=4;
348         }
349         if (v&0x0cULL){
350                 b+=2;
351                 v>>=2;
352         }
353         b+= !!(v&0x02ULL);
354         return b;
355 }
356 #endif  /* BIT_SCAN_BRANCH */
357
358
359
360 #ifdef BIT_SCAN_ASM
361 #if defined __CPU_x86 || defined __CPU_x86_64
362 #define HAS_BIT_SCAN_ASM
363
364 static inline int bit_scan_forward_asm32(unsigned int v)
365 {
366         int r;
367         asm volatile(" bsfl %1, %0": "=r"(r): "rm"(v) );
368         return r;
369 }
370
371 static inline int bit_scan_reverse_asm32(unsigned int v)
372 {
373         int r;
374         asm volatile(" bsrl %1, %0": "=r"(r): "rm"(v) );
375         return r;
376 }
377
378 #ifdef __CPU_x86_64
379 static inline int bit_scan_forward_asm64(unsigned long long v)
380 {
381         long r;
382         asm volatile(" bsfq %1, %0": "=r"(r): "rm"(v) );
383         return r;
384 }
385
386 static inline int bit_scan_reverse_asm64(unsigned long long v)
387 {
388         long r;
389         asm volatile(" bsrq %1, %0": "=r"(r): "rm"(v) );
390         return r;
391 }
392 #else
393 static inline int bit_scan_forward_asm64(unsigned long long v)
394 {
395         if ((unsigned int)v)
396                 return bit_scan_forward_asm32((unsigned int)v);
397         return 32+bit_scan_forward_asm32(*(((unsigned int*)(void*)&v)+1));
398 }
399
400 static inline int bit_scan_reverse_asm64(unsigned long long v)
401 {
402         if (v & 0xffffffff00000000ULL)
403                 return 32+bit_scan_reverse_asm32(*(((unsigned int*)(void*)&v)+1));
404         return bit_scan_reverse_asm32((unsigned int)v);
405 }
406 #endif /* __CPU_x86_64 */
407
408 #endif /* __CPU_x86 || __CPU_x86_64 */
409 #endif /* BIT_SCAN_ASM */
410
411 #endif