bit_scan.h File Reference

SIP-router core :: bit scan operationsModule: SIP-router core. More...

#include <limits.h>

Include dependency graph for bit_scan.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines

• #define BIT_SCAN_DEBRUIJN

  fix __CPU_i386 -> __CPU_x86
  

• #define bit_scan_forward(l)   bit_scan_forward32((l))

  try to use the right version for bit_scan_forward(unisgned long l)
  

Variables

• unsigned char _debruijn_hash32 [32]

  use a de Bruijn sequence to get the index of the set bit for a number of the form 2^k (DEBRUIJN_HASH32() and DEBRUIJN_HASH64()).
  

---

Detailed Description

bit scan operations

• int bit_scan_forward(unsigned long v) - returns the index of the first set bit (undefined value if v==0)
• int bit_scan_forward32(unsigned int v) - returns the index of the first set bit (undefined value if v==0)
• int bit_scan_forward64(long long v) - returns the index of the first set bit (undefined value if v==0)
• int bit_scan_reverse(unsigned long v) - returns the index of the last set bit (undefined value if v==0)
• int bit_scan_reverse32(unsigned int v) - returns the index of the last set bit (undefined value if v==0)
• int bit_scan_reverse64(long long v) - returns the index of the last set bit (undefined value if v==0)

Config defines: CC_GCC_LIKE_ASM - the compiler support gcc style inline asm, __CPU_x86, __CPU_x86_64, ULONG_MAX (limits.h)

Definition in file bit_scan.h.

---

Define Documentation

#define BIT_SCAN_DEBRUIJN

set default bitscan versions, depending on the architecture In general the order is asm, debruijn, br, slow for bit_scan_forward and asm, br, slow, debruijn for bit_scan_reverse.

Definition at line 122 of file bit_scan.h.

#define bit_scan_forward

(

l

)

bit_scan_forward32((l))

long is 32 bits

Definition at line 145 of file bit_scan.h.

---

Variable Documentation

unsigned char _debruijn_hash32[32]

bit_scan_forward & bit_scan_reverse would need first to convert the argument to 2^k (where k is the first set bit or last set bit index)- For bit_scan_forward this can be done very fast using x & (-x). For more info about this method see: http://citeseer.ist.psu.edu/leiserson98using.html ("Using de Bruijn Sequences to Index a 1 in a Computer Word")

Definition at line 36 of file bit_scan.c.