115 size_type n_blocks = (m_size + k_block_size - 1) / k_block_size;
116 size_type n_sblocks = (n_blocks + k_sblock_rate - 1) / k_sblock_rate;
117 size_type n_hblocks = (n_blocks + k_hblock_rate - 1) / k_hblock_rate;
124 for (uint32_t i = 1; i < 65536; ++i)
126 runs_lookup[i] = runs_lookup[i >> 1];
129 if ((i & 1) != ((i >> 1) & 1))
134 uint64_t
const * bv_ptr = bv.
data();
135 for (
size_type block_id = 0; block_id < n_blocks; ++block_id)
137 size_type block_beg = block_id * k_block_size;
138 size_type block_end = block_beg + k_block_size;
143 if (block_end <= m_size)
146 uint64_t
const * ptr64 = bv_ptr;
147 for (uint8_t i = 0; i < 4; ++i)
152 for (uint8_t i = 0; i < 4; ++i)
155 for (uint8_t j = 0; j < 4; ++j)
156 runs += runs_lookup[((*ptr64) >> (16 * j)) & 0xffff];
159 for (uint8_t j = 0; j < 3; ++j)
160 runs += ((((*ptr64) >> (16 * j + 15)) & 1) ^ (((*ptr64) >> (16 * j + 16)) & 1));
166 for (uint8_t i = 0; i < 3; ++i)
168 runs += ((((*ptr64) >> 63) & 1) ^ ((*(ptr64 + 1)) & 1));
177 for (
size_type i = block_beg; i < block_end; ++i)
179 uint8_t bit = (i < m_size ? bv[i] : 0);
189 uint32_t minority_enc_size = std::min(ones, k_block_size - ones);
190 uint32_t runs_enc_size = (uint32_t)std::max(0, (int32_t)runs - 2);
191 uint32_t best_enc_size = std::min(minority_enc_size, runs_enc_size);
192 best_enc_size = std::min(best_enc_size, k_block_bytes);
195 trunk_size += best_enc_size;
196 bv_ptr += k_block_size / 64;
200 m_sblock_header =
int_vector<8>(n_sblocks * k_sblock_header_size, 0);
211 for (
size_type block_id = 0; block_id < n_blocks; ++block_id)
213 size_type block_beg = block_id * k_block_size;
214 size_type block_end = block_beg + k_block_size;
215 size_type sblock_id = block_id / k_sblock_rate;
216 size_type hblock_id = block_id / k_hblock_rate;
219 if (!(block_id % k_hblock_rate))
221 m_hblock_header[2 * hblock_id] = trunk_ptr;
222 m_hblock_header[2 * hblock_id + 1] = tot_rank;
226 if (!(block_id % k_sblock_rate))
228 uint32_t * ptr = (uint32_t *)(((uint8_t *)m_sblock_header.
data()) + k_sblock_header_size * sblock_id);
229 *ptr++ = trunk_ptr - m_hblock_header[2 * hblock_id];
230 *ptr = tot_rank - m_hblock_header[2 * hblock_id + 1];
233 if (sblock_id && (!sblock_ones || sblock_ones == k_sblock_size))
235 ptr = (uint32_t *)(((uint8_t *)m_sblock_header.
data()) + k_sblock_header_size * (sblock_id - 1));
247 if (block_end <= m_size)
250 uint64_t
const * ptr64 = bv_ptr;
251 for (uint8_t i = 0; i < 4; ++i)
256 for (uint8_t i = 0; i < 4; ++i)
258 for (uint8_t j = 0; j < 4; ++j)
259 runs += runs_lookup[((*ptr64) >> (16 * j)) & 0xffff];
260 for (uint8_t j = 0; j < 3; ++j)
261 runs += ((((*ptr64) >> (16 * j + 15)) & 1) ^ (((*ptr64) >> (16 * j + 16)) & 1));
265 for (uint8_t i = 0; i < 3; ++i)
267 runs += ((((*ptr64) >> 63) & 1) ^ ((*(ptr64 + 1)) & 1));
276 for (
size_type i = block_beg; i < block_end; ++i)
278 uint8_t bit = (i < m_size ? bv[i] : 0);
286 uint32_t zeros = k_block_size - ones;
289 uint16_t * header_ptr16 =
290 (uint16_t *)(((uint8_t *)m_sblock_header.
data()) + sblock_id * k_sblock_header_size + 8
291 + (block_id % k_sblock_rate) * 2);
293 (*header_ptr16) = ones;
294 if (ones == k_block_size)
295 (*header_ptr16) |= 0x200;
297 if (0 < ones && ones < k_block_size)
299 uint32_t minority_enc_size = std::min(ones, zeros);
300 uint32_t runs_enc_size = (uint32_t)std::max(0, (int32_t)runs - 2);
301 uint32_t best_enc_size = std::min(minority_enc_size, runs_enc_size);
303 if (k_block_bytes <= best_enc_size)
306 (*header_ptr16) |= (k_block_bytes << 10);
309 if (block_end <= m_size)
311 for (uint8_t i = 0; i < 4; ++i)
313 *((uint64_t *)(((uint8_t *)m_trunk.
data()) + trunk_ptr)) = *(bv_ptr + i);
319 for (
size_type i = block_beg; i < block_end; i += 64)
322 for (
size_type j = i; j < std::min(i + 64, block_end); ++j)
324 uint8_t bit = (j < m_size ? bv[j] : 0);
326 w |= ((uint64_t)1 << (j - i));
328 *((uint64_t *)(((uint8_t *)m_trunk.
data()) + trunk_ptr)) = w;
335 if (runs_enc_size < minority_enc_size)
339 (*header_ptr16) |= (runs_enc_size << 10);
340 (*header_ptr16) |= (bv[block_beg] << 9);
342 if (block_end <= m_size)
346 uint64_t
const * ptr64 = bv_ptr;
349 for (uint8_t i = 0; runid < runs_enc_size && i < 4; ++i)
352 if (i > 0 && (w & 1) != ((*ptr64) & 1))
353 m_trunk[trunk_ptr + runid++] = 64 * i - 1;
356 for (uint8_t j = 0; runid < runs_enc_size && j < 63; ++j)
358 if ((w & 1) != ((w >> 1) & 1))
359 m_trunk[trunk_ptr + runid++] = j + i * 64;
371 for (
size_type i = block_beg; runid < runs_enc_size; ++i)
373 uint8_t bit = (i < m_size ? bv[i] : 0);
374 if (bit != prevbit && i != block_beg)
375 m_trunk[trunk_ptr + runid++] = (i - block_beg - 1);
385 (*header_ptr16) |= (minority_enc_size << 10);
387 (*header_ptr16) |= 0x200;
388 uint8_t keybit = (ones < zeros);
391 if (block_end <= m_size)
393 uint64_t
const * ptr64 = bv_ptr;
394 for (uint8_t i = 0; i < 4; ++i)
396 uint64_t w = (*ptr64++);
397 for (uint8_t j = 0; j < 64; ++j)
399 if ((w & 1) == keybit)
400 m_trunk[trunk_ptr++] = j + 64 * i;
407 for (
size_type i = block_beg; i < block_end; ++i)
409 uint8_t bit = (i < m_size ? bv[i] : 0);
412 m_trunk[trunk_ptr++] = i - block_beg;
422 bv_ptr += k_block_size / 64;