Skip to content

Commit

Permalink
Remove no-longer needed C bitvector functions
Browse files Browse the repository at this point in the history
  • Loading branch information
@mbauman
mbauman committed Feb 6, 2017
1 parent bb3198a commit bb78c47
Show file tree
Hide file tree
Showing 2 changed files with 0 additions and 148 deletions.
141 changes: 0 additions & 141 deletions src/support/bitvector.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -56,147 +56,6 @@ uint32_t bitvector_get(uint32_t *b, uint64_t n)
return b[n>>5] & (1<<(n&31));
}

// a mask with n set lo or hi bits
#define lomask(n) (uint32_t)((((uint32_t)1)<<(n))-1)
#define ONES32 ((uint32_t)0xffffffff)

#if defined(__INTEL_COMPILER) && !defined(__clang__)
#define count_bits(b) _popcnt32(b)
#else
STATIC_INLINE uint32_t count_bits(uint32_t b)
{
b = b - ((b>>1)&0x55555555);
b = ((b>>2)&0x33333333) + (b&0x33333333);
b = ((b>>4)+b)&0x0f0f0f0f;
b += (b>>8);
b += (b>>16);
return b & 0x3f;
// here is the non-optimized version, for clarity:
/*
b = ((b>> 1)&0x55555555) + (b&0x55555555);
b = ((b>> 2)&0x33333333) + (b&0x33333333);
b = ((b>> 4)&0x0f0f0f0f) + (b&0x0f0f0f0f);
b = ((b>> 8)&0x00ff00ff) + (b&0x00ff00ff);
b = ((b>>16)&0x0000ffff) + (b&0x0000ffff);
return b & 0x3f;
*/
}
#endif

static int ntz(uint32_t x)
{
int n;

if (x == 0) return 32;
n = 1;
if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;}
if ((x & 0x000000FF) == 0) {n = n + 8; x = x >> 8;}
if ((x & 0x0000000F) == 0) {n = n + 4; x = x >> 4;}
if ((x & 0x00000003) == 0) {n = n + 2; x = x >> 2;}
return n - (x & 1);
}

// given a bitvector of n bits, starting at bit n0 find the next
// set bit, including n0.
// returns n if no set bits.
uint64_t bitvector_next(uint32_t *b, uint64_t n0, uint64_t n)
{
if (n0 >= n) return n;

uint32_t i = n0>>5;
uint32_t nb = n0&31;
uint32_t nw = (n+31)>>5;
uint32_t w;

if (i < nw-1 || (n&31)==0)
w = b[i]>>nb;
else
w = (b[i]&lomask(n&31))>>nb;
if (w != 0)
return ntz(w)+n0;
if (i == nw-1)
return n;
i++;
while (i < nw-1) {
w = b[i];
if (w != 0) {
return ntz(w) + (((uint64_t)i)<<5);
}
i++;
}
w = b[i];
nb = n&31;
i = ntz(w);
if (nb == 0)
return i + (n-32);
if (i >= nb)
return n;
return i + (n-nb);
}

uint64_t bitvector_count(uint32_t *b, uint64_t offs, uint64_t nbits)
{
size_t i, nw;
uint32_t ntail;
uint64_t ans;

if (nbits == 0) return 0;
nw = (offs+nbits+31)>>5;

if (nw == 1) {
if (nbits == 32)
return count_bits(b[0] & (ONES32<<offs));
return count_bits(b[0] & (lomask(nbits)<<offs));
}

ans = count_bits(b[0]>>offs); // first end cap

for(i=1; i < nw-1; i++) {
ans += count_bits(b[i]);
}

ntail = (offs+nbits)&31;
ans += count_bits(b[i]&(ntail>0?lomask(ntail):ONES32)); // last end cap

return ans;
}

uint32_t bitvector_any1(uint32_t *b, uint64_t offs, uint64_t nbits)
{
size_t i;
uint32_t nw, tail;
uint32_t mask;

if (nbits == 0) return 0;
nw = (offs+nbits+31)>>5;

if (nw == 1) {
if (nbits == 32)
mask = (ONES32<<offs);
else
mask = (lomask(nbits)<<offs);
if ((b[0] & mask) != 0) return 1;
return 0;
}

mask = ~lomask(offs);
if ((b[0] & mask) != 0) return 1;

for(i=1; i < nw-1; i++) {
if (b[i] != 0) return 1;
}

tail = (offs+nbits)&31;
if (tail==0) {
if (b[i] != 0) return 1;
}
else {
mask = lomask(tail);
if ((b[i] & mask) != 0) return 1;
}
return 0;
}

#ifdef __cplusplus
}
#endif
7 changes: 0 additions & 7 deletions src/support/bitvector.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -15,13 +15,6 @@ size_t bitvector_nwords(uint64_t nbits);
JL_DLLEXPORT void bitvector_set(uint32_t *b, uint64_t n, uint32_t c);
JL_DLLEXPORT uint32_t bitvector_get(uint32_t *b, uint64_t n);

JL_DLLEXPORT uint64_t bitvector_next(uint32_t *b, uint64_t n0, uint64_t n);

JL_DLLEXPORT
uint64_t bitvector_count(uint32_t *b, uint64_t offs, uint64_t nbits);
JL_DLLEXPORT
uint32_t bitvector_any1(uint32_t *b, uint64_t offs, uint64_t nbits);

#ifdef __cplusplus
}
#endif
Expand Down

0 comments on commit bb78c47

Please sign in to comment.