SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
coder_fibonacci.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef SDSL_CODER_FIBONACCI_INCLUDED
9#define SDSL_CODER_FIBONACCI_INCLUDED
10
11#include <stdint.h>
12
13#include <sdsl/bits.hpp>
14#include <sdsl/config.hpp>
15
16namespace sdsl
17{
18
19namespace coder
20{
21
23template <typename T = void>
25{
26public:
27 static struct impl
28 {
29 uint64_t fib12bit_to_bin[(1 << 12) * 8];
31
36 uint8_t fib2bin_shift[(1 << 13)];
38
43 uint16_t fib2bin_16_greedy[(1 << 16)];
44
46 uint64_t fib2bin_0_95[(1 << 12) * 8];
47
48 impl()
49 {
50 for (uint32_t x = 0; x <= 0x1FFF; ++x)
51 {
52 if (bits::cnt11(x))
53 {
54 fib2bin_shift[x] = bits::sel11(x, 1) + 1;
55 }
56 else
57 {
58 fib2bin_shift[x] = 0;
59 }
60 }
61 for (uint32_t x = 0; x < 1 << 16; ++x)
62 {
63 uint16_t w = 0;
64 uint32_t offset = 0;
65 if (uint32_t cnt = bits::cnt11(x))
66 {
67 uint32_t y = x;
68 uint32_t fib_pos = 1;
69 do
70 {
71 if (y & 1)
72 {
73 w += bits::lt_fib[fib_pos - 1];
74 if (y & 2)
75 {
76 --cnt;
77 ++offset;
78 fib_pos = 0;
79 y >>= 1;
80 }
81 }
82 ++fib_pos;
83 ++offset;
84 y >>= 1;
85 }
86 while (cnt);
87 }
88 fib2bin_16_greedy[x] = (offset << 11) | w;
89 }
90 for (uint32_t p = 0; p < 8; ++p)
91 {
92 for (uint32_t x = 0; x <= 0xFFF; ++x)
93 {
94 uint64_t w = 0;
95 for (uint32_t j = 0; j < 12 and 12 * p + j < 92; ++j)
96 {
97 if ((x >> j) & 1ULL)
98 {
99 w += bits::lt_fib[12 * p + j];
100 if (x >> (j + 1) & 1ULL)
101 {
102 break;
103 }
104 }
105 }
106 fib2bin_0_95[(p << 12) | x] = w;
107 }
108 }
109 }
110 } data;
111
112 typedef uint64_t size_type;
113
114 static const uint8_t min_codeword_length = 2; // 11 represents 1 and is the code word with minimum length
116
118 static uint8_t encoding_length(uint64_t w);
120 /* \param data Bitstring
121 * \param start_idx Starting index of the decoding.
122 * \param n Number of values to decode from the bitstring.
123 * \param it Iterator
124 */
125 template <bool t_sumup, bool t_inc, class t_iter>
126 static uint64_t decode(uint64_t const * data, const size_type start_idx, size_type n, t_iter it = (t_iter) nullptr);
127
128 template <bool t_sumup, bool t_inc, class t_iter>
129 static uint64_t
130 decode1(uint64_t const * data, const size_type start_idx, size_type n, t_iter it = (t_iter) nullptr);
131
134
139 static uint64_t decode_prefix_sum(uint64_t const * d, const size_type start_idx, size_type n);
140
143
145 static uint64_t
146 decode_prefix_sum(uint64_t const * d, const size_type start_idx, const size_type end_idx, size_type n);
147
148 template <class int_vector1, class int_vector2>
149 static bool encode(int_vector1 const & v, int_vector2 & z);
150
151 template <class int_vector>
152 static uint64_t * raw_data(int_vector & v)
153 {
154 return v.m_data;
155 }
156
158
162 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
163
164 template <class int_vector1, class int_vector2>
165 static bool decode(int_vector1 const & z, int_vector2 & v);
166};
167
168template <typename T>
169inline uint8_t fibonacci<T>::encoding_length(uint64_t w)
170{
171 if (w == 0)
172 {
173 return 93;
174 }
175 // This limit for the leftmost 1bit in the resulting fib code could be improved using a table
176 uint8_t len_1 = bits::hi(w); // len-1 of the fib code
177 while (++len_1 < (uint8_t)(sizeof(bits::lt_fib) / sizeof(bits::lt_fib[0])) && w >= bits::lt_fib[len_1])
178 ;
179 return len_1 + 1;
180}
181
182template <typename T>
183template <class int_vector1, class int_vector2>
184inline bool fibonacci<T>::encode(int_vector1 const & v, int_vector2 & z)
185{
186 uint64_t z_bit_size = 0;
187 uint64_t w;
188 const uint64_t zero_val = v.width() < 64 ? (1ULL) << v.width() : 0;
189 for (typename int_vector1::const_iterator it = v.begin(), end = v.end(); it != end; ++it)
190 {
191 if ((w = *it) == 0)
192 {
193 if (v.width() < 64)
194 {
195 w = zero_val;
196 }
197 }
198 z_bit_size += encoding_length(w);
199 }
200 z.bit_resize(z_bit_size);
201 z.shrink_to_fit();
202 if (z_bit_size & 0x3F)
203 { // if z_bit_size % 64 != 0
204 *(z.m_data + (z_bit_size >> 6)) = 0; // initialize last word
205 }
206 uint64_t * z_data = z.m_data;
207 uint8_t offset = 0;
208 uint64_t fibword_high = 0x0000000000000001ULL, fibword_low;
209 uint64_t t;
210 for (typename int_vector1::const_iterator it = v.begin(), end = v.end(); it != end; ++it)
211 {
212 w = *it;
213 if (w == 0)
214 {
215 w = zero_val;
216 }
217 int8_t len_1 = encoding_length(w) - 1, j;
218 fibword_low = 0x0000000000000001ULL;
219
220 if (len_1 >= 64)
221 { // length > 65
222 fibword_high = 0x0000000000000001ULL;
223 j = len_1 - 1;
224 if (w == 0)
225 { // handle special case
226 fibword_high <<= 1;
227 fibword_high |= 1;
228 fibword_high <<= 1;
229 w -= bits::lt_fib[len_1 - 1];
230 j -= 2;
231 }
232 for (; j > 63; --j)
233 {
234 fibword_high <<= 1;
235 if (w >= (t = bits::lt_fib[j]))
236 {
237 w -= t;
238 fibword_high |= 1;
239 if (w and j > 64)
240 {
241 fibword_high <<= 1;
242 --j;
243 }
244 else
245 {
246 fibword_high <<= (64 - j);
247 break;
248 }
249 }
250 }
251 j = 64;
252 }
253 else
254 {
255 j = len_1 - 1;
256 }
257
258 for (; j >= 0; --j)
259 {
260 fibword_low <<= 1;
261 if (w >= (t = bits::lt_fib[j]))
262 {
263 w -= t;
264 fibword_low |= 1;
265 if (w)
266 {
267 fibword_low <<= 1;
268 --j;
269 }
270 else
271 {
272 fibword_low <<= (j);
273 break;
274 }
275 }
276 }
277 if (len_1 >= 64)
278 {
279 bits::write_int_and_move(z_data, fibword_low, offset, 64);
280 bits::write_int_and_move(z_data, fibword_high, offset, len_1 - 63);
281 }
282 else
283 {
284 bits::write_int_and_move(z_data, fibword_low, offset, (len_1 & 0x3F) + 1);
285 }
286 }
287 z.width(v.width());
288 return true;
289}
290
291template <typename T>
292inline void fibonacci<T>::encode(uint64_t x, uint64_t *& z, uint8_t & offset)
293{
294 uint64_t fibword_high = 0x0000000000000001ULL, fibword_low;
295 uint64_t t;
296 int8_t len_1 = encoding_length(x) - 1, j;
297 fibword_low = 0x0000000000000001ULL;
298
299 if (len_1 >= 64)
300 { // length > 65
301 fibword_high = 0x0000000000000001ULL;
302 j = len_1 - 1;
303 if (x == 0)
304 { // handle special case
305 fibword_high <<= 1;
306 fibword_high |= 1;
307 fibword_high <<= 1;
308 x -= bits::lt_fib[len_1 - 1];
309 j -= 2;
310 }
311 for (; j > 63; --j)
312 {
313 fibword_high <<= 1;
314 if (x >= (t = bits::lt_fib[j]))
315 {
316 x -= t;
317 fibword_high |= 1;
318 if (x and j > 64)
319 {
320 fibword_high <<= 1;
321 --j;
322 }
323 else
324 {
325 fibword_high <<= (64 - j);
326 break;
327 }
328 }
329 }
330 j = 64;
331 }
332 else
333 {
334 j = len_1 - 1;
335 }
336 for (; j >= 0; --j)
337 {
338 fibword_low <<= 1;
339 if (x >= (t = bits::lt_fib[j]))
340 {
341 x -= t;
342 fibword_low |= 1;
343 if (x)
344 {
345 fibword_low <<= 1;
346 --j;
347 }
348 else
349 {
350 fibword_low <<= (j);
351 break;
352 }
353 }
354 }
355 if (len_1 >= 64)
356 {
357 bits::write_int_and_move(z, fibword_low, offset, 64);
358 bits::write_int_and_move(z, fibword_high, offset, len_1 - 63);
359 }
360 else
361 {
362 bits::write_int_and_move(z, fibword_low, offset, (len_1 & 0x3F) + 1);
363 }
364}
365
366template <typename T>
367template <class int_vector1, class int_vector2>
368inline bool fibonacci<T>::decode(int_vector1 const & z, int_vector2 & v)
369{
370 uint64_t n = 0, carry = 0; // n = number of values to be decoded
371 uint64_t const * data = z.data();
372 // Determine size of v
373 if (z.empty())
374 { // if z is empty we are ready with decoding
375 v.width(z.width());
376 v.resize(0);
377 v.shrink_to_fit();
378 return true;
379 }
380 for (typename int_vector1::size_type i = 0; i < z.bit_data_size() - 1; ++i, ++data)
381 {
382 n += bits::cnt11(*data, carry);
383 }
384 if (z.bit_data_size() << 6 != z.bit_size())
385 {
386 n += bits::cnt11((*data) & bits::lo_set[z.bit_size() & 0x3F], carry);
387 }
388 else
389 {
390 n += bits::cnt11(*data, carry);
391 }
392 v.width(z.width());
393 v.resize(n);
394 v.shrink_to_fit();
395 return decode<false, true>(z.data(), 0, n, v.begin());
396}
397
398template <typename T>
399template <bool t_sumup, bool t_inc, class t_iter>
400inline uint64_t fibonacci<T>::decode(uint64_t const * data, const size_type start_idx, size_type n, t_iter it)
401{
402 data += (start_idx >> 6);
403 uint64_t w = 0, value = 0;
404 int8_t buffered = 0; // bits buffered in w, in 0..64
405 int8_t read = start_idx & 0x3F; // read bits in current *data 0..63
406 int8_t shift = 0;
407 uint32_t fibtable = 0;
408 while (n)
409 { // while not all values are decoded
410 while (buffered < 13 and bits::cnt11(w) < n)
411 {
412 w |= (((*data) >> read) << buffered);
413 if (read >= buffered)
414 {
415 ++data;
416 buffered += 64 - read;
417 read = 0;
418 }
419 else
420 { // read < buffered
421 read += 64 - buffered;
422 buffered = 64;
423 }
424 }
425 value += fibonacci<T>::data.fib2bin_0_95[(fibtable << 12) | (w & 0xFFF)];
426 shift = fibonacci<T>::data.fib2bin_shift[w & 0x1FFF];
427 if (shift > 0)
428 { // if end of decoding
429 w >>= shift;
430 buffered -= shift;
431 if (t_inc)
432 *(it++) = value;
433 if (!t_sumup and n != 1)
434 value = 0;
435 fibtable = 0;
436 --n;
437 }
438 else
439 { // not end of decoding
440 w >>= 12;
441 buffered -= 12;
442 ++fibtable;
443 }
444 }
445 return value;
446}
447
448template <typename T>
449template <bool t_sumup, bool t_inc, class t_iter>
450inline uint64_t fibonacci<T>::decode1(uint64_t const * d, const size_type start_idx, size_type n, t_iter it)
451{
452 d += (start_idx >> 6);
453 uint64_t w = 0, value = 0;
454 int8_t buffered = 0; // bits buffered in w, in 0..64
455 int8_t read = start_idx & 0x3F; // read bits in current *data 0..63
456 int8_t shift = 0;
457 uint32_t fibtable = 0;
458 uint8_t blocknr = (start_idx >> 6) % 9;
459 while (n)
460 { // while not all values are decoded
461 while (buffered < 13 and bits::cnt11(w) < n)
462 {
463 w |= (((*d) >> read) << buffered);
464 if (read >= buffered)
465 {
466 ++blocknr;
467 ++d;
468 if (blocknr == 8)
469 {
470 ++d;
471 blocknr = 0;
472 }
473 buffered += 64 - read;
474 read = 0;
475 }
476 else
477 { // read < buffered
478 read += 64 - buffered;
479 buffered = 64;
480 }
481 }
482 value += fibonacci<T>::data.fib2bin_0_95[(fibtable << 12) | (w & 0xFFF)];
483 shift = fibonacci<T>::data.fib2bin_shift[w & 0x1FFF];
484 if (shift > 0)
485 { // if end of decoding
486 w >>= shift;
487 buffered -= shift;
488 if (t_inc)
489 *(it++) = value;
490 if (!t_sumup)
491 value = 0;
492 fibtable = 0;
493 --n;
494 }
495 else
496 { // not end of decoding
497 w >>= 12;
498 buffered -= 12;
499 ++fibtable;
500 }
501 }
502 return value;
503}
504
505template <typename T>
506inline uint64_t fibonacci<T>::decode_prefix_sum(uint64_t const * d, const size_type start_idx, size_type n)
507{
508 if (n == 0)
509 return 0;
510 // return decode<true,false,int*>(data, start_idx, n);
511 d += (start_idx >> 6);
512 size_type i = 0;
513 int32_t bits_to_decode = 0;
514 uint64_t w = 0, value = 0;
515 int16_t buffered = 0, read = start_idx & 0x3F, shift = 0;
516 uint16_t temp = 0;
517 uint64_t carry = 0;
518 i = bits::cnt11(*d & ~bits::lo_set[read], carry);
519 if (i < n)
520 {
521 uint64_t oldcarry;
522 w = 0;
523 do
524 {
525 oldcarry = carry;
526 i += (temp = bits::cnt11(*(d + (++w)), carry));
527 }
528 while (i < n);
529 bits_to_decode += ((w - 1) << 6) + bits::sel11(*(d + w), n - (i - temp), oldcarry) + 65 - read;
530 w = 0;
531 }
532 else
533 { // i>=n
534 bits_to_decode = bits::sel11(*d >> read, n) + 1;
535 }
536 if (((size_type)bits_to_decode) == n << 1)
537 return n;
538 if (((size_type)bits_to_decode) == (n << 1) + 1)
539 return n + 1;
540 i = 0;
541 // while( bits_to_decode > 0 or buffered > 0){// while not all values are decoded
542 do
543 {
544 while (buffered < 64 and bits_to_decode > 0)
545 {
546 w |= (((*d) >> read) << buffered);
547 if (read >= buffered)
548 {
549 ++d;
550 buffered += 64 - read;
551 bits_to_decode -= (64 - read);
552 read = 0;
553 }
554 else
555 { // read buffered
556 read += 64 - buffered;
557 bits_to_decode -= (64 - buffered);
558 buffered = 64;
559 }
560 if (bits_to_decode < 0)
561 {
562 buffered += bits_to_decode;
563 w &= bits::lo_set[buffered];
564 bits_to_decode = 0;
565 }
566 }
567 if (!i)
568 { // try do decode multiple values
569 if ((w & 0xFFFFFF) == 0xFFFFFF)
570 {
571 value += 12;
572 w >>= 24;
573 buffered -= 24;
574 if ((w & 0xFFFFFF) == 0xFFFFFF)
575 {
576 value += 12;
577 w >>= 24;
578 buffered -= 24;
579 }
580 }
581 do
582 {
583 temp = fibonacci<T>::data.fib2bin_16_greedy[w & 0xFFFF];
584 if ((shift = (temp >> 11)) > 0)
585 {
586 value += (temp & 0x7FFULL);
587 w >>= shift;
588 buffered -= shift;
589 }
590 else
591 {
592 value += fibonacci<T>::data.fib2bin_0_95[w & 0xFFF];
593 w >>= 12;
594 buffered -= 12;
595 i = 1;
596 break;
597 }
598 }
599 while (buffered > 15);
600 }
601 else
602 { // i > 0
603 value += fibonacci<T>::data.fib2bin_0_95[(i << 12) | (w & 0xFFF)];
604 shift = fibonacci<T>::data.fib2bin_shift[w & 0x1FFF];
605 if (shift > 0)
606 { // if end of decoding
607 w >>= shift;
608 buffered -= shift;
609 i = 0;
610 }
611 else
612 { // not end of decoding
613 w >>= 12;
614 buffered -= 12;
615 ++i;
616 }
617 }
618 }
619 while (bits_to_decode > 0 or buffered > 0);
620 return value;
621}
622
623template <typename T>
624inline uint64_t fibonacci<T>::decode_prefix_sum(uint64_t const * d,
625 const size_type start_idx,
626 SDSL_UNUSED const size_type end_idx,
627 size_type n)
628{
629 return decode_prefix_sum(d, start_idx, n);
630}
631
632template <typename T>
633typename fibonacci<T>::impl fibonacci<T>::data;
634
635} // end namespace coder
636} // end namespace sdsl
637#endif
bits.hpp contains the sdsl::bits class.
A class to encode and decode between Fibonacci and binary code.
static uint64_t * raw_data(int_vector &v)
static uint64_t decode(uint64_t const *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
Decode n Fibonacci encoded bits beginning at start_idx in the bitstring "data".
static bool encode(int_vector1 const &v, int_vector2 &z)
static uint64_t decode1(uint64_t const *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
static struct sdsl::coder::fibonacci::impl data
static const uint8_t min_codeword_length
static uint64_t decode_prefix_sum(uint64_t const *d, const size_type start_idx, const size_type end_idx, size_type n)
Decode n Fibonacci encoded integers beginning at start_idx and ending at end_idx (exclusive) in the b...
static uint8_t encoding_length(uint64_t w)
Get the number of bits that are necessary to encode the value w in Fibonacci code.
static uint64_t decode_prefix_sum(uint64_t const *d, const size_type start_idx, size_type n)
Decode n Fibonacci encoded integers beginning at start_idx in the bitstring "data" and return the sum...
A generic vector class for integers of width .
#define SDSL_UNUSED
Definition config.hpp:12
Namespace for the succinct data structure library.
static constexpr uint64_t lt_fib[92]
Array containing Fibonacci numbers less than .
Definition bits.hpp:78
static constexpr uint32_t sel11(uint64_t x, uint32_t i, uint32_t c=0)
Calculates the position of the i-th rightmost 11-bit-pattern which terminates a Fibonacci coded integ...
Definition bits.hpp:718
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
static constexpr void write_int_and_move(uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len)
Writes value x to an bit position in an array and moves the bit-pointer.
Definition bits.hpp:749
static constexpr uint32_t cnt11(uint64_t x, uint64_t &c)
Count the number of consecutive and distinct 11 in the 64bit integer x.
Definition bits.hpp:543
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition bits.hpp:194