kamailio.cfg: removed sample db_mode parameter for domain module
[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  * \file
20  * \brief SIP-router core :: bit scan operations
21  * \ingroup core
22  * Module: \ref core
23  *
24  *  bit scan operations
25  *
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)
38  *
39  * Config defines:   CC_GCC_LIKE_ASM  - the compiler support gcc style
40  *                     inline asm,
41  *                  __CPU_x86, __CPU_x86_64,
42  *                  ULONG_MAX (limits.h)
43  */
44 /* 
45  * History:
46  * --------
47  *  2007-06-23  created by andrei
48  */
49
50 #ifndef _bit_scan_h
51 #define _bit_scan_h
52
53 #include <limits.h>
54
55 /*! \brief fix __CPU_i386 -> __CPU_x86 */
56 #if defined __CPU_i386 && ! defined __CPU_x86
57 #define __CPU_x86
58 #endif
59
60
61 #ifdef CC_GCC_LIKE_ASM
62 #if defined __CPU_x86 || defined __CPU_x86_64
63 #define BIT_SCAN_ASM
64 #endif
65 #endif
66
67
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. */
71 #ifdef BIT_SCAN_ASM
72 /* have asm => use it */
73
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)
78
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
85 #endif
86 #ifndef BIT_SCAN_BRANCH
87 #define BIT_SCAN_BRANCH
88 #endif
89
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)
94
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
102 #endif
103
104 #define bit_scan_reverse32(i)   bit_scan_reverse_br32(i)
105 #define bit_scan_reverse64(i)   bit_scan_reverse_br64(i)
106 #ifdef LP64
107 #define bit_scan_forward32(i)   bit_scan_forward_br32(i)
108 #define bit_scan_forward64(i)   bit_scan_forward_br64(i)
109 #else /* LP64 */
110
111 #ifndef BIT_SCAN_DEBRUIJN
112 #define BIT_SCAN_DEBRUIJN
113 #endif
114 #define bit_scan_forward32(i)   bit_scan_forward_debruijn32(i)
115 #define bit_scan_forward64(i)   bit_scan_forward_debruijn64(i)
116 #endif /* LP64 */
117
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
123 #endif
124 #ifndef BIT_SCAN_BRANCH
125 #define BIT_SCAN_BRANCH
126 #endif
127
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)
132
133 #endif /* __CPU_XXX */
134
135
136 /*! \brief try to use the right version for bit_scan_forward(unisgned long l)
137  */
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))
142
143 #else
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))
147 #endif
148
149
150
151
152 #ifdef BIT_SCAN_DEBRUIJN
153
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")
162  */
163
164 extern unsigned char _debruijn_hash32[32]; /* see bit_scan.c */
165 extern unsigned char _debruijn_hash64[64]; /* see bit_scan.c */
166
167 #define DEBRUIJN_CT32  0x04653ADFU
168 #define DEBRUIJN_CT64  0x0218A392CD3D5DBFULL 
169
170 #define DEBRUIJN_HASH32(x)\
171         (((x)*DEBRUIJN_CT32)>>(sizeof(x)*8-5))
172
173 #define DEBRUIJN_HASH64(x)\
174         (((x)*DEBRUIJN_CT64)>>(sizeof(x)*8-6))
175
176 #define bit_scan_forward_debruijn32(x) \
177         ( _debruijn_hash32[DEBRUIJN_HASH32((x) & (-(x)))])
178
179 #define bit_scan_forward_debruijn64(x) \
180         ( _debruijn_hash64[DEBRUIJN_HASH64((x) & (-(x)))])
181
182
183 static inline int bit_scan_reverse_debruijn32(unsigned int v)
184 {
185         unsigned int last;
186         
187         do{
188                 last=v;
189                 v=v&(v-1);
190         }while(v); /* => last is 2^k */
191         return _debruijn_hash32[DEBRUIJN_HASH32(last)];
192 }
193
194
195 static inline int bit_scan_reverse_debruijn64(unsigned long long v)
196 {
197         unsigned long long last;
198         
199         do{
200                 last=v;
201                 v=v&(v-1);
202         }while(v); /* => last is 2^k */
203         return _debruijn_hash64[DEBRUIJN_HASH64(last)];
204 }
205
206
207 #endif /* BIT_SCAN_DEBRUIJN */
208
209 #ifdef BIT_SCAN_SLOW
210 /* only for reference purposes (testing the other versions against it) */
211
212 static inline int bit_scan_forward_slow32(unsigned int v)
213 {
214         int r;
215         for(r=0; r<(sizeof(v)*8); r++, v>>=1)
216                 if (v&1) return r;
217         return 0;
218 }
219
220
221 static inline int bit_scan_reverse_slow32(unsigned int v)
222 {
223         int r;
224         for(r=sizeof(v)*8-1; r>0; r--, v<<=1)
225                 if (v& (1UL<<(sizeof(v)*8-1))) return r;
226         return 0;
227 }
228
229
230 static inline int bit_scan_forward_slow64(unsigned long long v)
231 {
232         int r;
233         for(r=0; r<(sizeof(v)*8); r++, v>>=1)
234                 if (v&1ULL) return r;
235         return 0;
236 }
237
238
239 static inline int bit_scan_reverse_slow64(unsigned long long v)
240 {
241         int r;
242         for(r=sizeof(v)*8-1; r>0; r--, v<<=1)
243                 if (v& (1ULL<<(sizeof(v)*8-1))) return r;
244         return 0;
245 }
246
247
248 #endif /* BIT_SCAN_SLOW */
249
250
251 #ifdef BIT_SCAN_BRANCH
252
253 static inline int bit_scan_forward_br32(unsigned int v)
254 {
255         int b;
256         
257         b=0;
258         if (v&0x01)
259                 return 0;
260         if (!(v & 0xffff)){
261                 b+=16;
262                 v>>=16;
263         }
264         if (!(v&0xff)){
265                 b+=8;
266                 v>>=8;
267         }
268         if (!(v&0x0f)){
269                 b+=4;
270                 v>>=4;
271         }
272         if (!(v&0x03)){
273                 b+=2;
274                 v>>=2;
275         }
276         b+= !(v&0x01);
277         return b;
278 }
279
280
281 static inline int bit_scan_reverse_br32(unsigned int v)
282 {
283         int b;
284         
285         b=0;
286         if (v & 0xffff0000){
287                 b+=16;
288                 v>>=16;
289         }
290         if (v&0xff00){
291                 b+=8;
292                 v>>=8;
293         }
294         if (v&0xf0){
295                 b+=4;
296                 v>>=4;
297         }
298         if (v&0x0c){
299                 b+=2;
300                 v>>=2;
301         }
302         b+= !!(v&0x02);
303         return b;
304 }
305
306
307 static inline int bit_scan_forward_br64(unsigned long long v)
308 {
309         int b;
310         
311         b=0;
312         if (v&0x01ULL)
313                 return 0;
314         if (!(v & 0xffffffffULL)){
315                 b+=32;
316                 v>>=32;
317         }
318         if (!(v & 0xffffULL)){
319                 b+=16;
320                 v>>=16;
321         }
322         if (!(v&0xffULL)){
323                 b+=8;
324                 v>>=8;
325         }
326         if (!(v&0x0fULL)){
327                 b+=4;
328                 v>>=4;
329         }
330         if (!(v&0x03ULL)){
331                 b+=2;
332                 v>>=2;
333         }
334         b+= !(v&0x01ULL);
335         return b;
336 }
337
338
339 static inline int bit_scan_reverse_br64(unsigned long long v)
340 {
341         int b;
342         
343         b=0;
344         if (v & 0xffffffff00000000ULL){
345                 b+=32;
346                 v>>=32;
347         }
348         if (v & 0xffff0000ULL){
349                 b+=16;
350                 v>>=16;
351         }
352         if (v&0xff00ULL){
353                 b+=8;
354                 v>>=8;
355         }
356         if (v&0xf0ULL){
357                 b+=4;
358                 v>>=4;
359         }
360         if (v&0x0cULL){
361                 b+=2;
362                 v>>=2;
363         }
364         b+= !!(v&0x02ULL);
365         return b;
366 }
367 #endif  /* BIT_SCAN_BRANCH */
368
369
370
371 #ifdef BIT_SCAN_ASM
372 #if defined __CPU_x86 || defined __CPU_x86_64
373 #define HAS_BIT_SCAN_ASM
374
375 static inline int bit_scan_forward_asm32(unsigned int v)
376 {
377         int r;
378         asm volatile(" bsfl %1, %0": "=r"(r): "rm"(v) );
379         return r;
380 }
381
382 static inline int bit_scan_reverse_asm32(unsigned int v)
383 {
384         int r;
385         asm volatile(" bsrl %1, %0": "=r"(r): "rm"(v) );
386         return r;
387 }
388
389 #ifdef __CPU_x86_64
390 static inline int bit_scan_forward_asm64(unsigned long long v)
391 {
392         long r;
393         asm volatile(" bsfq %1, %0": "=r"(r): "rm"(v) );
394         return r;
395 }
396
397 static inline int bit_scan_reverse_asm64(unsigned long long v)
398 {
399         long r;
400         asm volatile(" bsrq %1, %0": "=r"(r): "rm"(v) );
401         return r;
402 }
403 #else
404 static inline int bit_scan_forward_asm64(unsigned long long v)
405 {
406         if ((unsigned int)v)
407                 return bit_scan_forward_asm32((unsigned int)v);
408         return 32+bit_scan_forward_asm32(*(((unsigned int*)(void*)&v)+1));
409 }
410
411 static inline int bit_scan_reverse_asm64(unsigned long long v)
412 {
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);
416 }
417 #endif /* __CPU_x86_64 */
418
419 #endif /* __CPU_x86 || __CPU_x86_64 */
420 #endif /* BIT_SCAN_ASM */
421
422 #endif