Browse code

core, lib, modules: restructured source code tree

- new folder src/ to hold the source code for main project applications
- main.c is in src/
- all core files are subfolder are in src/core/
- modules are in src/modules/
- libs are in src/lib/
- application Makefiles are in src/
- application binary is built in src/ (src/kamailio)

Daniel-Constantin Mierla authored on 07/12/2016 11:03:51
Showing 1 changed files
1 1
deleted file mode 100644
... ...
@@ -1,422 +0,0 @@
1
-/* 
2
- * Copyright (C) 2007 iptelorg GmbH
3
- *
4
- * Permission to use, copy, modify, and distribute this software for any
5
- * purpose with or without fee is hereby granted, provided that the above
6
- * copyright notice and this permission notice appear in all copies.
7
- *
8
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15
- */
16
-/*!
17
- * \file
18
- * \brief Kamailio core :: bit scan operations
19
- *
20
- * Copyright (C) 2007 iptelorg GmbH
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
Browse code

core : Update include files - delete IDs, update doxygen, delete history

Olle E. Johansson authored on 03/01/2015 10:55:48
Showing 1 changed files
... ...
@@ -1,6 +1,4 @@
1 1
 /* 
2
- * $Id$
3
- * 
4 2
  * Copyright (C) 2007 iptelorg GmbH
5 3
  *
6 4
  * Permission to use, copy, modify, and distribute this software for any
... ...
@@ -17,7 +15,9 @@
17 15
  */
18 16
 /*!
19 17
  * \file
20
- * \brief SIP-router core :: bit scan operations
18
+ * \brief Kamailio core :: bit scan operations
19
+ *
20
+ * Copyright (C) 2007 iptelorg GmbH
21 21
  * \ingroup core
22 22
  * Module: \ref core
23 23
  *
Browse code

- Doxygen updates on core files - Add project name to doxygen in Makefile

oej authored on 19/10/2009 20:35:43
Showing 1 changed files
... ...
@@ -15,19 +15,25 @@
15 15
  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 16
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 17
  */
18
-/*
18
+/*!
19
+ * \file
20
+ * \brief SIP-router core :: bit scan operations
21
+ * \ingroup core
22
+ * Module: \ref core
23
+ *
19 24
  *  bit scan operations
20
- *  int bit_scan_forward(unsigned long v)   - returns the index of the first
25
+ *
26
+ *  - int bit_scan_forward(unsigned long v)   - returns the index of the first
21 27
  *                                          set bit (undefined value if v==0)
22
- *  int bit_scan_forward32(unsigned int v)   - returns the index of the first
28
+ *  - int bit_scan_forward32(unsigned int v)   - returns the index of the first
23 29
  *                                          set bit (undefined value if v==0)
24
- *  int bit_scan_forward64(long long v)      - returns the index of the first
30
+ *  - int bit_scan_forward64(long long v)      - returns the index of the first
25 31
  *                                          set bit (undefined value if v==0)
26
- *  int bit_scan_reverse(unsigned long v)   - returns the index of the last
32
+ *  - int bit_scan_reverse(unsigned long v)   - returns the index of the last
27 33
  *                                          set bit (undefined value if v==0)
28
- *  int bit_scan_reverse32(unsigned int v)  - returns the index of the last
34
+ *  - int bit_scan_reverse32(unsigned int v)  - returns the index of the last
29 35
  *                                          set bit (undefined value if v==0)
30
- *  int bit_scan_reverse64(long long v)     - returns the index of the last
36
+ *  - int bit_scan_reverse64(long long v)     - returns the index of the last
31 37
  *                                          set bit (undefined value if v==0)
32 38
  *
33 39
  * Config defines:   CC_GCC_LIKE_ASM  - the compiler support gcc style
... ...
@@ -46,7 +52,7 @@
46 52
 
47 53
 #include <limits.h>
48 54
 
49
-/* fix __CPU_i386 -> __CPU_x86 */
55
+/*! \brief fix __CPU_i386 -> __CPU_x86 */
50 56
 #if defined __CPU_i386 && ! defined __CPU_x86
51 57
 #define __CPU_x86
52 58
 #endif
... ...
@@ -59,7 +65,7 @@
59 65
 #endif
60 66
 
61 67
 
62
-/* set default bitscan versions, depending on the architecture
68
+/*! \brief set default bitscan versions, depending on the architecture
63 69
  * In general the order is  asm, debruijn, br, slow for bit_scan_forward
64 70
  *  and asm, br, slow, debruijn for bit_scan_reverse. */
65 71
 #ifdef BIT_SCAN_ASM
... ...
@@ -127,15 +133,15 @@
127 133
 #endif /* __CPU_XXX */
128 134
 
129 135
 
130
-/* try to use the right version for bit_scan_forward(unisgned long l)
136
+/*! \brief try to use the right version for bit_scan_forward(unisgned long l)
131 137
  */
132 138
 #if (defined (ULONG_MAX) && ULONG_MAX > 4294967295) || defined LP64
133
-/* long is 64 bits */
139
+/*! \brief long is 64 bits */
134 140
 #define bit_scan_forward(l)	bit_scan_forward64((unsigned long long)(l))
135 141
 #define bit_scan_reverse(l)	bit_scan_reverse64((unsigned long long)(l))
136 142
 
137 143
 #else
138
-/* long is 32 bits */
144
+/*! \brief long is 32 bits */
139 145
 #define bit_scan_forward(l)	bit_scan_forward32((l))
140 146
 #define bit_scan_reverse(l)	bit_scan_reverse32((l))
141 147
 #endif
... ...
@@ -145,7 +151,7 @@
145 151
 
146 152
 #ifdef BIT_SCAN_DEBRUIJN
147 153
 
148
-/* use a de Bruijn sequence to get the index of the set bit for a number
154
+/*! \brief use a de Bruijn sequence to get the index of the set bit for a number
149 155
  *  of the form 2^k (DEBRUIJN_HASH32() and DEBRUIJN_HASH64()).
150 156
  *  bit_scan_forward & bit_scan_reverse would need first to convert
151 157
  *  the argument to 2^k (where k is the first set bit or last set bit index)-
Browse code

- fix: ifdef __CPU_i386 define __CPU_x86

Andrei Pelinescu-Onciul authored on 17/07/2008 10:12:07
Showing 1 changed files
... ...
@@ -46,6 +46,11 @@
46 46
 
47 47
 #include <limits.h>
48 48
 
49
+/* fix __CPU_i386 -> __CPU_x86 */
50
+#if defined __CPU_i386 && ! defined __CPU_x86
51
+#define __CPU_x86
52
+#endif
53
+
49 54
 
50 55
 #ifdef CC_GCC_LIKE_ASM
51 56
 #if defined __CPU_x86 || defined __CPU_x86_64
Browse code

- switched to unsigned char for the debruijn hash (now the entire lookup table fits into one cacheline; minor performance improvements can be seen on pentiumM and sparc64)

Andrei Pelinescu-Onciul authored on 26/06/2007 13:32:54
Showing 1 changed files
... ...
@@ -150,8 +150,8 @@
150 150
  *  ("Using de Bruijn Sequences to Index a 1 in a Computer Word")
151 151
  */
152 152
 
153
-extern int _debruijn_hash32[32]; /* see bit_scan.c */
154
-extern int _debruijn_hash64[64]; /* see bit_scan.c */
153
+extern unsigned char _debruijn_hash32[32]; /* see bit_scan.c */
154
+extern unsigned char _debruijn_hash64[64]; /* see bit_scan.c */
155 155
 
156 156
 #define DEBRUIJN_CT32  0x04653ADFU
157 157
 #define DEBRUIJN_CT64  0x0218A392CD3D5DBFULL 
Browse code

- added functions to get the index of the first or last bit set in a 32 bit or 64 bit int: bit_scan_forward32(), bit_scan_forward64(), bit_scan_reverse32(), bit_scan_reverse64(), bit_scan_forward(long) and bit_scan_reverse(long). All of them are very fast, they use asm if available (for now only for __CPU_x86 and __CPU_x86_64), and fall back to a de Bruijn based method or binary search (depending on which method was faster in my measurements on a particular cpu). - added test/profile.h - simple measure the cpu cycles between two calls functions (for now support for x86, x86_64 and sparc64)

Andrei Pelinescu-Onciul authored on 25/06/2007 17:20:34
Showing 1 changed files
1 1
new file mode 100644
... ...
@@ -0,0 +1,411 @@
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 int _debruijn_hash32[32]; /* see bit_scan.c */
154
+extern int _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
+