4 * Copyright (C) 2007 iptelorg GmbH
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.
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.
20 * \brief SIP-router core :: bit scan operations
26 * - int bit_scan_forward(unsigned long v) - returns the index of the first
27 * set bit (undefined value if v==0)
28 * - int bit_scan_forward32(unsigned int v) - returns the index of the first
29 * set bit (undefined value if v==0)
30 * - int bit_scan_forward64(long long v) - returns the index of the first
31 * set bit (undefined value if v==0)
32 * - int bit_scan_reverse(unsigned long v) - returns the index of the last
33 * set bit (undefined value if v==0)
34 * - int bit_scan_reverse32(unsigned int v) - returns the index of the last
35 * set bit (undefined value if v==0)
36 * - int bit_scan_reverse64(long long v) - returns the index of the last
37 * set bit (undefined value if v==0)
39 * Config defines: CC_GCC_LIKE_ASM - the compiler support gcc style
41 * __CPU_x86, __CPU_x86_64,
42 * ULONG_MAX (limits.h)
47 * 2007-06-23 created by andrei
55 /*! \brief fix __CPU_i386 -> __CPU_x86 */
56 #if defined __CPU_i386 && ! defined __CPU_x86
61 #ifdef CC_GCC_LIKE_ASM
62 #if defined __CPU_x86 || defined __CPU_x86_64
68 /*! \brief set default bitscan versions, depending on the architecture
69 * In general the order is asm, debruijn, br, slow for bit_scan_forward
70 * and asm, br, slow, debruijn for bit_scan_reverse. */
72 /* have asm => use it */
74 #define bit_scan_forward32(i) bit_scan_forward_asm32(i)
75 #define bit_scan_forward64(i) bit_scan_forward_asm64(i)
76 #define bit_scan_reverse32(i) bit_scan_reverse_asm32(i)
77 #define bit_scan_reverse64(i) bit_scan_reverse_asm64(i)
79 #elif defined __CPU_x86 || defined __CPU_x86_64
80 /* no asm (e.g. no CC_GCC_LIKE_ASM) => debruijn for bit_scan_forward and
81 * br for bit_scan_reverse */
82 /* make sure debruijn an branch version are enabled */
83 #ifndef BIT_SCAN_DEBRUIJN
84 #define BIT_SCAN_DEBRUIJN
86 #ifndef BIT_SCAN_BRANCH
87 #define BIT_SCAN_BRANCH
90 #define bit_scan_forward32(i) bit_scan_forward_debruijn32(i)
91 #define bit_scan_forward64(i) bit_scan_forward_debruijn64(i)
92 #define bit_scan_reverse32(i) bit_scan_reverse_br32(i)
93 #define bit_scan_reverse64(i) bit_scan_reverse_br64(i)
95 #elif defined __CPU_sparc64
96 /* no asm yet => use branch for everything in 64 bit mode
97 * and debruijn + branch in 32 bit mode
98 * (in 64bit mode the branch method is slightly faster then debruijn,
99 * however note that in 32 bit mode the roles are reversed for _forward)*/
100 #ifndef BIT_SCAN_BRANCH
101 #define BIT_SCAN_BRANCH
104 #define bit_scan_reverse32(i) bit_scan_reverse_br32(i)
105 #define bit_scan_reverse64(i) bit_scan_reverse_br64(i)
107 #define bit_scan_forward32(i) bit_scan_forward_br32(i)
108 #define bit_scan_forward64(i) bit_scan_forward_br64(i)
111 #ifndef BIT_SCAN_DEBRUIJN
112 #define BIT_SCAN_DEBRUIJN
114 #define bit_scan_forward32(i) bit_scan_forward_debruijn32(i)
115 #define bit_scan_forward64(i) bit_scan_forward_debruijn64(i)
118 #else /* __CPU_XXX */
119 /* default - like x86 no asm */
120 /* make sure debruijn an branch version are enabled */
121 #ifndef BIT_SCAN_DEBRUIJN
122 #define BIT_SCAN_DEBRUIJN
124 #ifndef BIT_SCAN_BRANCH
125 #define BIT_SCAN_BRANCH
128 #define bit_scan_forward32(i) bit_scan_forward_debruijn32(i)
129 #define bit_scan_forward64(i) bit_scan_forward_debruijn64(i)
130 #define bit_scan_reverse32(i) bit_scan_reverse_br32(i)
131 #define bit_scan_reverse64(i) bit_scan_reverse_br64(i)
133 #endif /* __CPU_XXX */
136 /*! \brief try to use the right version for bit_scan_forward(unisgned long l)
138 #if (defined (ULONG_MAX) && ULONG_MAX > 4294967295) || defined LP64
139 /*! \brief long is 64 bits */
140 #define bit_scan_forward(l) bit_scan_forward64((unsigned long long)(l))
141 #define bit_scan_reverse(l) bit_scan_reverse64((unsigned long long)(l))
144 /*! \brief long is 32 bits */
145 #define bit_scan_forward(l) bit_scan_forward32((l))
146 #define bit_scan_reverse(l) bit_scan_reverse32((l))
152 #ifdef BIT_SCAN_DEBRUIJN
154 /*! \brief use a de Bruijn sequence to get the index of the set bit for a number
155 * of the form 2^k (DEBRUIJN_HASH32() and DEBRUIJN_HASH64()).
156 * bit_scan_forward & bit_scan_reverse would need first to convert
157 * the argument to 2^k (where k is the first set bit or last set bit index)-
158 * For bit_scan_forward this can be done very fast using x & (-x).
159 * For more info about this method see:
160 * http://citeseer.ist.psu.edu/leiserson98using.html
161 * ("Using de Bruijn Sequences to Index a 1 in a Computer Word")
164 extern unsigned char _debruijn_hash32[32]; /* see bit_scan.c */
165 extern unsigned char _debruijn_hash64[64]; /* see bit_scan.c */
167 #define DEBRUIJN_CT32 0x04653ADFU
168 #define DEBRUIJN_CT64 0x0218A392CD3D5DBFULL
170 #define DEBRUIJN_HASH32(x)\
171 (((x)*DEBRUIJN_CT32)>>(sizeof(x)*8-5))
173 #define DEBRUIJN_HASH64(x)\
174 (((x)*DEBRUIJN_CT64)>>(sizeof(x)*8-6))
176 #define bit_scan_forward_debruijn32(x) \
177 ( _debruijn_hash32[DEBRUIJN_HASH32((x) & (-(x)))])
179 #define bit_scan_forward_debruijn64(x) \
180 ( _debruijn_hash64[DEBRUIJN_HASH64((x) & (-(x)))])
183 static inline int bit_scan_reverse_debruijn32(unsigned int v)
190 }while(v); /* => last is 2^k */
191 return _debruijn_hash32[DEBRUIJN_HASH32(last)];
195 static inline int bit_scan_reverse_debruijn64(unsigned long long v)
197 unsigned long long last;
202 }while(v); /* => last is 2^k */
203 return _debruijn_hash64[DEBRUIJN_HASH64(last)];
207 #endif /* BIT_SCAN_DEBRUIJN */
210 /* only for reference purposes (testing the other versions against it) */
212 static inline int bit_scan_forward_slow32(unsigned int v)
215 for(r=0; r<(sizeof(v)*8); r++, v>>=1)
221 static inline int bit_scan_reverse_slow32(unsigned int v)
224 for(r=sizeof(v)*8-1; r>0; r--, v<<=1)
225 if (v& (1UL<<(sizeof(v)*8-1))) return r;
230 static inline int bit_scan_forward_slow64(unsigned long long v)
233 for(r=0; r<(sizeof(v)*8); r++, v>>=1)
234 if (v&1ULL) return r;
239 static inline int bit_scan_reverse_slow64(unsigned long long v)
242 for(r=sizeof(v)*8-1; r>0; r--, v<<=1)
243 if (v& (1ULL<<(sizeof(v)*8-1))) return r;
248 #endif /* BIT_SCAN_SLOW */
251 #ifdef BIT_SCAN_BRANCH
253 static inline int bit_scan_forward_br32(unsigned int v)
281 static inline int bit_scan_reverse_br32(unsigned int v)
307 static inline int bit_scan_forward_br64(unsigned long long v)
314 if (!(v & 0xffffffffULL)){
318 if (!(v & 0xffffULL)){
339 static inline int bit_scan_reverse_br64(unsigned long long v)
344 if (v & 0xffffffff00000000ULL){
348 if (v & 0xffff0000ULL){
367 #endif /* BIT_SCAN_BRANCH */
372 #if defined __CPU_x86 || defined __CPU_x86_64
373 #define HAS_BIT_SCAN_ASM
375 static inline int bit_scan_forward_asm32(unsigned int v)
378 asm volatile(" bsfl %1, %0": "=r"(r): "rm"(v) );
382 static inline int bit_scan_reverse_asm32(unsigned int v)
385 asm volatile(" bsrl %1, %0": "=r"(r): "rm"(v) );
390 static inline int bit_scan_forward_asm64(unsigned long long v)
393 asm volatile(" bsfq %1, %0": "=r"(r): "rm"(v) );
397 static inline int bit_scan_reverse_asm64(unsigned long long v)
400 asm volatile(" bsrq %1, %0": "=r"(r): "rm"(v) );
404 static inline int bit_scan_forward_asm64(unsigned long long v)
407 return bit_scan_forward_asm32((unsigned int)v);
408 return 32+bit_scan_forward_asm32(*(((unsigned int*)(void*)&v)+1));
411 static inline int bit_scan_reverse_asm64(unsigned long long v)
413 if (v & 0xffffffff00000000ULL)
414 return 32+bit_scan_reverse_asm32(*(((unsigned int*)(void*)&v)+1));
415 return bit_scan_reverse_asm32((unsigned int)v);
417 #endif /* __CPU_x86_64 */
419 #endif /* __CPU_x86 || __CPU_x86_64 */
420 #endif /* BIT_SCAN_ASM */