#include "bitarray.h"
#define NDEBUG 1
#include <assert.h>
#define STATIC_INLINE static __inline
STATIC_INLINE unsigned __ffsll(uint64_t xx) {
#if defined(__LP64__)
return __builtin_ffsl(xx);
#else
return __builtin_ffsll(xx);
#endif
}
#define BIT_SET(old,bit) ((old) | (1ULL << (bit)))
#define BIT_GET(old,bit) ((old) & (1ULL << (bit)))
#define BIT_ZAP(old,bit) ((old) & ~ (1ULL << (bit)))
STATIC_INLINE bool word_get_bit_simple(uint64_t *word, unsigned bit) {
uint64_t old = *word;
return BIT_GET(old, bit) != 0;
}
STATIC_INLINE void word_set_bit_simple(uint64_t *word, unsigned bit) {
uint64_t old = *word;
*word = BIT_SET(old, bit);
}
STATIC_INLINE bool word_set_bit_changed(uint64_t *word, unsigned bit) {
uint64_t old = *word;
uint64_t new = BIT_SET(old, bit);
if (old == new) return 0;
*word = new;
return 1;
}
STATIC_INLINE bool word_set_bit_changed_go_down(uint64_t *word, unsigned bit, bool *was_non_zero) {
uint64_t old = *word;
uint64_t new = BIT_SET(old, bit);
if (old == new) return 0;
*word = new;
*was_non_zero = old != 0;
return 1;
}
STATIC_INLINE bool word_set_bit_go_down(uint64_t *word, unsigned bit) {
uint64_t old = *word;
uint64_t new = BIT_SET(old, bit);
if (old == new) return 0;
*word = new;
return !old;
}
STATIC_INLINE void word_zap_bit_simple(uint64_t *word, unsigned bit) {
uint64_t old = *word;
*word = BIT_ZAP(old, bit);
}
STATIC_INLINE bool word_zap_bit_changed(uint64_t *word, unsigned bit) {
uint64_t old = *word;
uint64_t new = BIT_ZAP(old, bit);
if (old == new) return 0;
*word = new;
return 1;
}
STATIC_INLINE bool word_zap_bit_changed_go_down(uint64_t *word, unsigned bit, bool *is_now_zero) {
uint64_t old = *word;
uint64_t new = BIT_ZAP(old, bit);
if (old == new) return 0;
*word = new;
*is_now_zero = ! new;
return 1;
}
STATIC_INLINE bool word_zap_bit_go_down(uint64_t *word, unsigned bit) {
uint64_t old = *word;
uint64_t new = BIT_ZAP(old, bit);
if (old == new) return 0;
*word = new;
return !new;
}
#define NB 9 // number of bits we process at once
#define MASKNB ((1 << NB) - 1) // to just keep these bits
#define NUM_64b (1 << (NB - 6)) // number of 64-bit words we process at once
#define LEVEL0 (NUM_64b)
#define LEVEL1 (LEVEL0 + (1 << NB)*NUM_64b)
#define LEVEL2 (LEVEL1 + (1 << (NB+NB))*NUM_64b)
#define LEVEL3 (LEVEL2 + (1 << (NB+NB+NB))*NUM_64b)
#define MAX_LEVEL 5
static const unsigned levels_num_words[] = {LEVEL0, LEVEL1, LEVEL2, LEVEL3};
STATIC_INLINE bool GET_SIMPLE(uint64_t *word, unsigned bit) {
return word_get_bit_simple(word + (bit >> 6), bit & 63);
}
STATIC_INLINE void SET_SIMPLE(uint64_t *word, unsigned bit) {
word_set_bit_simple(word + (bit >> 6), bit & 63);
}
STATIC_INLINE bool SET_CHANGED(uint64_t *word, unsigned bit) {
return word_set_bit_changed(word + (bit >> 6), bit & 63);
}
STATIC_INLINE bool SET_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *was_non_zero) {
return word_set_bit_changed_go_down(word + (bit >> 6), bit & 63, was_non_zero);
}
STATIC_INLINE bool SET_GO_DOWN(uint64_t *word, unsigned bit) {
return word_set_bit_go_down(word + (bit >> 6), bit & 63);
}
STATIC_INLINE void ZAP_SIMPLE(uint64_t *word, unsigned bit) {
return word_zap_bit_simple(word + (bit >> 6), bit & 63);
}
STATIC_INLINE bool ZAP_CHANGED(uint64_t *word, unsigned bit) {
return word_zap_bit_changed(word + (bit >> 6), bit & 63);
}
STATIC_INLINE bool all_zeros(uint64_t *words) {
for (unsigned w = 0; w < NUM_64b; w++) {
if (words[w]) return 0;
}
return 1;
}
STATIC_INLINE bool ZAP_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *is_now_zero) {
bool changed = word_zap_bit_changed_go_down(word + (bit >> 6), bit & 63, is_now_zero);
if (changed && (NUM_64b != 1)) {
if (!all_zeros(word)) *is_now_zero = 0;
}
return changed;
}
STATIC_INLINE bool ZAP_GO_DOWN(uint64_t *word, unsigned bit) {
bool changed = word_zap_bit_go_down(word + (bit >> 6), bit & 63);
if (changed && (NUM_64b != 1)) {
if (!all_zeros(word)) return 0;
}
return changed;
}
STATIC_INLINE unsigned FFS(uint64_t *word) {
#if NB==6
return __ffsll(*word);
#else
for (unsigned w = 0; w < NUM_64b; w++) {
unsigned f = __ffsll(word[w]);
if (f) return f + (w << 6);
}
return 0;
#endif
}
size_t bitarray_size(unsigned log_size) {
assert(log_size <= MAX_LEVEL * NB);
unsigned num = NUM_64b;
if (log_size > NB) {
unsigned level = (log_size - NB - 1) / NB;
num = levels_num_words[level] + (1 << (log_size - 6));
}
return num * sizeof(uint64_t);
}
bitarray_t bitarray_create(unsigned log_size) {
return calloc(1, bitarray_size(log_size));
}
bool bitarray_get(bitarray_t bits, unsigned log_size, index_t index) {
assert(log_size <= MAX_LEVEL * NB);
assert(index < (1 << log_size));
if (log_size <= NB) return GET_SIMPLE(bits, index);
unsigned level = (log_size - NB - 1) / NB;
unsigned bit;
bit = index & MASKNB; index >>= NB;
return GET_SIMPLE(bits + levels_num_words[level] + index*NUM_64b, bit);
}
bool bitarray_set(bitarray_t bits, unsigned log_size, index_t index) {
assert(log_size <= MAX_LEVEL * NB);
assert(index < (1 << log_size));
if (log_size <= NB) return SET_CHANGED(bits, index);
unsigned level = (log_size - NB - 1) / NB;
bool was_non_zero;
unsigned bit;
bit = index & MASKNB; index >>= NB;
if (!SET_CHANGED_GO_DOWN(bits + levels_num_words[level] + index*NUM_64b, bit, &was_non_zero)) return 0;
if (was_non_zero) return 1;
switch (level) {
case 3:
bit = index & MASKNB; index >>= NB;
if (!SET_GO_DOWN(bits + LEVEL2 + index*NUM_64b, bit)) return 1;
case 2:
bit = index & MASKNB; index >>= NB;
if (!SET_GO_DOWN(bits + LEVEL1 + index*NUM_64b, bit)) return 1;
case 1:
bit = index & MASKNB; index >>= NB;
if (!SET_GO_DOWN(bits + LEVEL0 + index*NUM_64b, bit)) return 1;
case 0:
SET_SIMPLE(bits, index & MASKNB);
return 1;
default: abort();
}
}
bool bitarray_zap(bitarray_t bits, unsigned log_size, index_t index) {
assert(log_size <= MAX_LEVEL * NB);
assert(index < (1 << log_size));
if (log_size <= NB) return ZAP_CHANGED(bits, index);
unsigned level = (log_size - NB - 1) / NB;
bool is_now_zero;
unsigned bit;
bit = index & MASKNB; index >>= NB;
if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + index*NUM_64b, bit, &is_now_zero)) return 0;
if (!is_now_zero) return 1;
switch (level) {
case 3:
bit = index & MASKNB; index >>= NB;
if (!ZAP_GO_DOWN(bits + LEVEL2 + index*NUM_64b, bit)) return 1;
case 2:
bit = index & MASKNB; index >>= NB;
if (!ZAP_GO_DOWN(bits + LEVEL1 + index*NUM_64b, bit)) return 1;
case 1:
bit = index & MASKNB; index >>= NB;
if (!ZAP_GO_DOWN(bits + LEVEL0 + index*NUM_64b, bit)) return 1;
case 0:
ZAP_SIMPLE(bits, index & MASKNB);
return 1;
default: abort();
}
}
#define ADJUST_OFFSET_FOR_FFS(words, base, current_level) { \
words += (1 << (NB * current_level)) * NUM_64b; \
base = (base << NB) + FFS(words + base*NUM_64b) - 1; \
}
#define ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level) {\
switch (level) { \
case 4: \
ADJUST_OFFSET_FOR_FFS(words, base, 0); \
ADJUST_OFFSET_FOR_FFS(words, base, 1); \
ADJUST_OFFSET_FOR_FFS(words, base, 2); \
break; \
case 3: \
ADJUST_OFFSET_FOR_FFS(words, base, 0); \
ADJUST_OFFSET_FOR_FFS(words, base, 1); \
break; \
case 2: \
ADJUST_OFFSET_FOR_FFS(words, base, 0); \
break; \
case 1: \
break; \
default: abort(); \
} \
}
#define ZAP_SUMMARIES(bits, ix, level) {\
unsigned bit; \
switch (level) { \
case 3: \
bit = ix & MASKNB; ix >>= NB; \
if (!ZAP_GO_DOWN(bits + LEVEL2 + ix*NUM_64b, bit)) break; \
case 2: \
bit = ix & MASKNB; ix >>= NB; \
if (!ZAP_GO_DOWN(bits + LEVEL1 + ix*NUM_64b, bit)) break; \
case 1: \
bit = ix & MASKNB; ix >>= NB; \
if (!ZAP_GO_DOWN(bits + LEVEL0 + ix*NUM_64b, bit)) break; \
case 0: \
ZAP_SIMPLE(bits, ix & MASKNB); \
break; \
default: abort(); \
} \
}
index_t bitarray_first_set(const bitarray_t bits, unsigned log_size) {
assert(log_size <= MAX_LEVEL * NB);
uint64_t *words = bits;
unsigned bit = FFS(words);
if (log_size <= NB) return bit;
if (!bit) return 0;
unsigned level = (log_size - 1) / NB;
index_t base = bit - 1; ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
words += (1 << (NB * (level-1))) * NUM_64b;
base = (base << NB) + FFS(words + base*NUM_64b) - 1;
return base+1; }
bool bitarray_zap_first_set(bitarray_t bits, unsigned log_size, index_t *index) {
assert(log_size <= MAX_LEVEL * NB);
uint64_t *words = bits;
index_t ix = FFS(words);
if (!ix) return 0;
unsigned level = (log_size - 1) / NB;
if (! level) {
ix--;
*index = ix;
ZAP_SIMPLE(bits, ix);
return 1;
}
index_t base = ix - 1; ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
words += (1 << (NB * (level-1))) * NUM_64b;
base = (base << NB) + FFS(words + base*NUM_64b) - 1;
ix = base;
*index = ix;
assert(ix < (1 << log_size));
level--;
bool is_now_zero;
unsigned bit;
bit = ix & MASKNB; ix >>= NB;
if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + ix*NUM_64b, bit, &is_now_zero)) return 1;
if (!is_now_zero) return 1;
ZAP_SUMMARIES(bits, ix, level);
return 1;
}
static unsigned FFS_and_zap_word(uint64_t *words, unsigned max, index_t *indices, index_t to_be_added) {
unsigned zapped = 0;
for (unsigned w = 0; w < NUM_64b; w++) {
uint64_t word = words[w];
if (!word) continue;
while (1) {
unsigned f = __ffsll(word);
assert(f);
f--;
indices[zapped++] = f + (w << 6) + to_be_added;
word = BIT_ZAP(word, f);
if (!word) break;
if (zapped >= max) break;
}
words[w] = word;
if (zapped >= max) break;
}
return zapped;
}
unsigned bitarray_zap_first_set_multiple(bitarray_t bits, unsigned log_size, unsigned max, index_t *indices) {
assert(log_size <= MAX_LEVEL * NB);
if (log_size <= NB) return FFS_and_zap_word(bits, max, indices, 0);
unsigned zapped = 0;
unsigned level = (log_size - 1) / NB;
while (zapped < max) {
uint64_t *words = bits;
index_t ix = FFS(words);
if (!ix) return zapped; index_t base = ix - 1; ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
words += (1 << (NB * (level-1))) * NUM_64b; uint64_t *word = words + base*NUM_64b; ix = base;
unsigned z = FFS_and_zap_word(word, max - zapped, indices + zapped, base << NB);
assert(z);
zapped += z;
if ((zapped < max) || all_zeros(word) ) {
ZAP_SUMMARIES(bits, ix, level-1);
}
}
return zapped;
}
#if 0
static void print_ones(const uint64_t *bits, unsigned num_big_words) {
unsigned base = 0;
unsigned num = num_big_words * NUM_64b;
while (num--) {
uint64_t word = *(bits++);
if (word) {
for (unsigned bit = 0; bit < 64; bit++) {
if (word & (1ULL << bit)) printf("%d ", base + bit);
}
}
base += 64;
}
}
void bitarray_print(bitarray_t bits, unsigned log_size) {
assert(log_size <= MAX_LEVEL * NB);
printf("bitarray %p log_size=%d\n", bits, log_size);
if (log_size > 4*NB) {
printf("Level 4: "); print_ones(bits, 1); printf("\n");
printf("Level 3: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
printf("Level 2: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n");
printf("Level 1: "); print_ones(bits + LEVEL2, 1 << NB); printf("\n");
printf("Level 0: "); print_ones(bits + LEVEL3, 1 << (log_size - NB)); printf("\n");
} else if (log_size > 3*NB) {
printf("Level 3: "); print_ones(bits, 1); printf("\n");
printf("Level 2: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
printf("Level 1: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n");
printf("Level 0: "); print_ones(bits + LEVEL2, 1 << (log_size - NB)); printf("\n");
} else if (log_size > 2*NB) {
printf("Level 2: "); print_ones(bits, 1); printf("\n");
printf("Level 1: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
printf("Level 0: "); print_ones(bits + LEVEL1, 1 << (log_size - NB)); printf("\n");
} else if (log_size > NB) {
printf("Level 1: "); print_ones(bits, 1); printf("\n");
printf("Level 0: "); print_ones(bits + LEVEL0, 1 << (log_size - NB)); printf("\n");
} else {
printf("Level 0: "); print_ones(bits, 1); printf("\n");
}
}
bool compare_to_truth(bitarray_t bits, unsigned nbits, const bool *truth) {
uint64_t *start = bits;
if (nbits > NB) {
unsigned level = (nbits - NB - 1) / NB;
start += levels_num_words[level];
}
bool ok = 1;
for (unsigned bit = 0; bit < (1 << nbits); bit++) {
bool expected = truth[bit];
uint64_t word = start[bit >> 6];
bool actual = (word >> (bit & 63)) & 1;
if (actual != expected) {
printf("*** # for bit %d, expected=%d actual=%d\n", bit, expected, actual);
ok = 0;
}
}
return ok;
}
unsigned first_set_in_truth(const bool *truth, unsigned log_size) {
for (unsigned bit = 0; bit < (1 << log_size); bit++) {
if (truth[bit]) return bit+1;
}
return 0;
}
void truth_print(const bool *truth, unsigned log_size) {
printf("Truth: ");
for (unsigned bit = 0; bit < (1 << log_size); bit++) {
if (truth[bit]) printf("%d ", bit);
}
printf("\n");
}
#endif