/usr/include/kmer/util/bitOperations.h is in libkmer-dev 0~20150903+r2013-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 | #ifndef BRI_BITS_H
#define BRI_BITS_H
// For dealing with the bits in bytes.
// I wish I could claim these.
//
// Freed, Edwin E. 1983. "Binary Magic Number" Dr. Dobbs Journal
// Vol. 78 (April) pp. 24-37
//
// Supposedly tells us how to reverse the bits in a word, count the number
// of set bits in a words and more.
//
// A bit of verbage on counting the number of set bits. The naive way
// is to loop and shift:
//
// uint32 r = uint32ZERO;
// while (x) {
// r++;
// x >>= 1;
// }
// return(r);
//
// http://remus.rutgers.edu/~rhoads/Code/bitcount3.c has an optimized
// method:
//
// x -= (0xaaaaaaaa & x) >> 1;
// x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
// x += x >> 4;
// x &= 0x0f0f0f0f;
// x += x >> 8;
// x += x >> 16;
// x &= 0x000000ff;
// return(x);
//
// No loops!
//
// Freed's methods are easier to understand, and just as fast.
//
// Using our bit counting routines, Ross Lippert suggested a nice
// way of computing log2 -- use log2 shifts to fill up the lower
// bits, then count bits. See logBaseTwo*()
//
inline
uint32
reverseBits32(uint32 x) {
x = ((x >> 1) & uint32NUMBER(0x55555555)) | ((x << 1) & uint32NUMBER(0xaaaaaaaa));
x = ((x >> 2) & uint32NUMBER(0x33333333)) | ((x << 2) & uint32NUMBER(0xcccccccc));
x = ((x >> 4) & uint32NUMBER(0x0f0f0f0f)) | ((x << 4) & uint32NUMBER(0xf0f0f0f0));
x = ((x >> 8) & uint32NUMBER(0x00ff00ff)) | ((x << 8) & uint32NUMBER(0xff00ff00));
x = ((x >> 16) & uint32NUMBER(0x0000ffff)) | ((x << 16) & uint32NUMBER(0xffff0000));
return(x);
}
inline
uint64
reverseBits64(uint64 x) {
x = ((x >> 1) & uint64NUMBER(0x5555555555555555)) | ((x << 1) & uint64NUMBER(0xaaaaaaaaaaaaaaaa));
x = ((x >> 2) & uint64NUMBER(0x3333333333333333)) | ((x << 2) & uint64NUMBER(0xcccccccccccccccc));
x = ((x >> 4) & uint64NUMBER(0x0f0f0f0f0f0f0f0f)) | ((x << 4) & uint64NUMBER(0xf0f0f0f0f0f0f0f0));
x = ((x >> 8) & uint64NUMBER(0x00ff00ff00ff00ff)) | ((x << 8) & uint64NUMBER(0xff00ff00ff00ff00));
x = ((x >> 16) & uint64NUMBER(0x0000ffff0000ffff)) | ((x << 16) & uint64NUMBER(0xffff0000ffff0000));
x = ((x >> 32) & uint64NUMBER(0x00000000ffffffff)) | ((x << 32) & uint64NUMBER(0xffffffff00000000));
return(x);
}
#if (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
#define PREFETCH(x) __builtin_prefetch((x), 0, 0)
#else
#define PREFETCH(x)
#endif
// Amazingingly, this is slower. From what I can google, the builtin
// is using the 2^16 lookup table method - so a 64-bit popcount does
// 4 lookups in the table and sums. Bad cache performance in codes
// that already have bad cache performance, I'd guess.
//
//#if (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
//#define BUILTIN_POPCOUNT
//#endif
#ifdef BUILTIN_POPCOUNT
inline
uint32
countNumberOfSetBits32(uint32 x) {
return(__builtin_popcount(x));
}
inline
uint64
countNumberOfSetBits64(uint64 x) {
return(__builtin_popcountll(x));
}
#else
inline
uint32
countNumberOfSetBits32(uint32 x) {
x = ((x >> 1) & uint32NUMBER(0x55555555)) + (x & uint32NUMBER(0x55555555));
x = ((x >> 2) & uint32NUMBER(0x33333333)) + (x & uint32NUMBER(0x33333333));
x = ((x >> 4) & uint32NUMBER(0x0f0f0f0f)) + (x & uint32NUMBER(0x0f0f0f0f));
x = ((x >> 8) & uint32NUMBER(0x00ff00ff)) + (x & uint32NUMBER(0x00ff00ff));
x = ((x >> 16) & uint32NUMBER(0x0000ffff)) + (x & uint32NUMBER(0x0000ffff));
return(x);
}
inline
uint64
countNumberOfSetBits64(uint64 x) {
x = ((x >> 1) & uint64NUMBER(0x5555555555555555)) + (x & uint64NUMBER(0x5555555555555555));
x = ((x >> 2) & uint64NUMBER(0x3333333333333333)) + (x & uint64NUMBER(0x3333333333333333));
x = ((x >> 4) & uint64NUMBER(0x0f0f0f0f0f0f0f0f)) + (x & uint64NUMBER(0x0f0f0f0f0f0f0f0f));
x = ((x >> 8) & uint64NUMBER(0x00ff00ff00ff00ff)) + (x & uint64NUMBER(0x00ff00ff00ff00ff));
x = ((x >> 16) & uint64NUMBER(0x0000ffff0000ffff)) + (x & uint64NUMBER(0x0000ffff0000ffff));
x = ((x >> 32) & uint64NUMBER(0x00000000ffffffff)) + (x & uint64NUMBER(0x00000000ffffffff));
return(x);
}
#endif
inline
uint32
logBaseTwo32(uint32 x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return(countNumberOfSetBits32(x));
}
inline
uint64
logBaseTwo64(uint64 x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return(countNumberOfSetBits64(x));
}
#endif // BRI_BITS_H
|