git.sip-router.org Git - sip-router/blob - 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