31 #include "../support/common.hpp"
32 #include "../util/Vector.hpp"
56 static const int log2_zeros_per_inventory = 10;
57 static const int zeros_per_inventory = 1 << log2_zeros_per_inventory;
58 static const uint64_t zeros_per_inventory_mask = zeros_per_inventory - 1;
59 static const int log2_longwords_per_subinventory = 2;
60 static const int longwords_per_subinventory = 1 << log2_longwords_per_subinventory;
61 static const int log2_zeros_per_sub64 = log2_zeros_per_inventory - log2_longwords_per_subinventory;
62 static const int zeros_per_sub64 = 1 << log2_zeros_per_sub64;
63 static const uint64_t zeros_per_sub64_mask = zeros_per_sub64 - 1;
64 static const int log2_zeros_per_sub16 = log2_zeros_per_sub64 - 2;
65 static const int zeros_per_sub16 = 1 << log2_zeros_per_sub16;
66 static const uint64_t zeros_per_sub16_mask = zeros_per_sub16 - 1;
71 uint64_t num_words, inventory_size, num_zeros;
83 num_words = (num_bits + 63) / 64;
87 for (uint64_t i = 0; i < num_words; i++) c += __builtin_popcountll(~bits[i]);
90 if (num_bits % 64 != 0) c -= 64 - num_bits % 64;
91 assert(c <= num_bits);
93 inventory_size = (c + zeros_per_inventory - 1) / zeros_per_inventory;
96 printf(
"Number of bits: %" PRId64
" Number of zeros: %" PRId64
" (%.2f%%)\n", num_bits, c, (c * 100.0) / num_bits);
98 printf(
"Ones per inventory: %d Ones per sub 64: %d sub 16: %d\n", zeros_per_inventory, zeros_per_sub64, zeros_per_sub16);
101 inventory.
size(inventory_size * (longwords_per_subinventory + 1) + 1);
104 const uint64_t mask = zeros_per_inventory - 1;
107 for (uint64_t i = 0; i < num_words; i++)
108 for (
int j = 0; j < 64; j++) {
109 if (i * 64 + j >= num_bits)
break;
110 if (~bits[i] & 1ULL << j) {
111 if ((d & mask) == 0) inventory[(d >> log2_zeros_per_inventory) * (longwords_per_subinventory + 1)] = i * 64 + j;
117 inventory[inventory_size * (longwords_per_subinventory + 1)] = num_bits;
120 printf(
"Inventory entries filled: %" PRId64
"\n", inventory_size + 1);
127 uint64_t exact = 0, start, span, inventory_index;
130 for (uint64_t i = 0; i < num_words; i++)
131 for (
int j = 0; j < 64; j++) {
132 if (i * 64 + j >= num_bits)
break;
133 if (~bits[i] & 1ULL << j) {
134 if ((d & mask) == 0) {
135 inventory_index = (d >> log2_zeros_per_inventory) * (longwords_per_subinventory + 1);
136 start = inventory[inventory_index];
137 span = inventory[inventory_index + longwords_per_subinventory + 1] - start;
138 if (span > (1 << 16)) inventory[inventory_index] = -inventory[inventory_index] - 1;
140 p64 = &inventory[inventory_index + 1];
141 p16 = (uint16_t *)p64;
144 if (span < (1 << 16)) {
145 assert(i * 64 + j - start <= (1 << 16));
146 if ((d & zeros_per_sub16_mask) == 0) {
147 assert(offset < longwords_per_subinventory * 4);
148 p16[offset++] = i * 64 + j - start;
151 if ((d & zeros_per_sub64_mask) == 0) {
152 assert(offset < longwords_per_subinventory);
153 p64[offset++] = i * 64 + j - start;
171 printf(
"Selecting %" PRId64
"\n...", rank);
173 assert(rank < num_zeros);
175 const uint64_t inventory_index = rank >> log2_zeros_per_inventory;
176 assert(inventory_index <= inventory_size);
177 const int64_t *inventory_start = &inventory + (inventory_index << log2_longwords_per_subinventory) + inventory_index;
179 const int64_t inventory_rank = *inventory_start;
180 const int subrank = rank & zeros_per_inventory_mask;
182 printf(
"Rank: %" PRId64
" inventory index: %" PRId64
" inventory rank: %" PRId64
" subrank: %d\n", rank, inventory_index, inventory_rank, subrank);
188 if (inventory_rank >= 0) {
189 start = inventory_rank + ((uint16_t *)(inventory_start + 1))[subrank >> log2_zeros_per_sub16];
190 residual = subrank & zeros_per_sub16_mask;
192 assert((subrank >> log2_zeros_per_sub64) < longwords_per_subinventory);
193 start = -inventory_rank - 1 + *(inventory_start + 1 + (subrank >> log2_zeros_per_sub64));
194 residual = subrank & zeros_per_sub64_mask;
198 printf(
"Differential; start: %" PRId64
" residual: %d\n", start, residual);
199 if (residual == 0) puts(
"No residual; returning start");
202 if (residual == 0)
return start;
204 uint64_t word_index = start / 64;
205 uint64_t word = ~bits[word_index] & -1ULL << start % 64;
208 const int bit_count = __builtin_popcountll(word);
209 if (residual < bit_count)
break;
210 word = ~bits[++word_index];
211 residual -= bit_count;
214 return word_index * 64 +
select64(word, residual);
217 uint64_t
selectZero(
const uint64_t rank, uint64_t *
const next) {
218 const uint64_t s = selectZero(rank);
221 uint64_t window = ~bits[curr] & -1ULL << s;
222 window &= window - 1;
224 while (window == 0) window = ~bits[++curr];
225 *next = curr * 64 + __builtin_ctzll(window);
231 size_t bitCount()
const {
return inventory.
bitCount() -
sizeof(inventory) * 8 +
sizeof(*
this) * 8; };