Relative-10 integer compression. More...
#include <compress_integer_relative_10.h>
Inheritance diagram for JASS::compress_integer_relative_10:
Collaboration diagram for JASS::compress_integer_relative_10:
Classes | |
| class | relative_10_lookup |
| lookup table storing how many integers are encoded and how they are encoded, More... | |
Public Member Functions | |
| compress_integer_relative_10 () | |
| Constructor. | |
| virtual | ~compress_integer_relative_10 () |
| Destructor. | |
| virtual size_t | encode (void *encoded, size_t encoded_buffer_length, const integer *source, size_t source_integers) |
| Encode a sequence of integers returning the number of bytes used for the encoding, or 0 if the encoded sequence doesn't fit in the buffer. More... | |
| virtual void | decode (integer *decoded, size_t integers_to_decode, const void *source, size_t source_length) |
| Decode a sequence of integers encoded with this codex. More... | |
 Public Member Functions inherited from JASS::compress_integer_simple_9 | |
| compress_integer_simple_9 () | |
| Consructor. | |
| virtual | ~compress_integer_simple_9 () |
| Destructor. | |
| Public Member Functions inherited from JASS::compress_integer | |
| compress_integer () | |
| Constructor. | |
| virtual | ~compress_integer () |
| Destructor. | |
Static Public Member Functions | |
| static void | unittest (void) |
| Unit test this class. | |
| Static Public Member Functions inherited from JASS::compress_integer_simple_9 | |
| static void | unittest (void) |
| Unit test this class. | |
| Static Public Member Functions inherited from JASS::compress_integer | |
| static size_t | d1_encode (integer *encoded, const integer *source, size_t source_integers) |
| Convert an array of integers into an array of D1 (delta, d-gap) encoded integers. More... | |
| static size_t | d1_decode (integer *decoded, const integer *source, size_t source_integers) |
| Convert a D1 encoded array of integers into an array of integers. More... | |
| static size_t | dn_encode (integer *encoded, const integer *source, size_t source_integers, size_t n=1) |
| Convert an array of integers into an array of Dn (delta, d-gap) encoded integers with a gap of n. More... | |
| static size_t | dn_decode (integer *decoded, const integer *source, size_t source_integers, size_t n=1) |
| Convert a Dn encoded array of integers into an array of integers. More... | |
| static void | unittest_one (compress_integer &encoder, const std::vector< uint32_t > &sequence) |
| Test one sequence to make sure it encodes and decodes to the same thing. Assert if not. More... | |
| static void | unittest (compress_integer &compressor, uint32_t staring_from=0) |
| Unit test this class, assert on failure. More... | |
Static Protected Attributes | |
| static const relative_10_lookup | relative10_table [] |
| The Relative-10 selector table explaining how the encoding works. More... | |
| static const uint32_t | bits_to_use10 [] |
| The number of bits that Relative-10 will be used to store an integer of the given the number of bits in length. More... | |
| static const uint32_t | table_row10 [] |
| The row of the table to use given the number of integers to can pack into the word. More... | |
| Static Protected Attributes inherited from JASS::compress_integer_simple_9 | |
| static const lookup | simple9_table [] |
| The table mapping bits to slectors and masks. More... | |
| static const uint32_t | bits_to_use [] |
| The number of bits used to store an integer of the given the number of bits in length. More... | |
| static const uint32_t | table_row [] |
| Given the number of bits, which row of simple9_table should be used? More... | |
| static const uint32_t | ints_packed_table [] |
| Number of integers packed into a 32-bit word, given its mask type. More... | |
| static const uint32_t | can_pack_table [] |
| Bitmask map for valid masks at an offset (column) for some num_bits_needed (row). More... | |
| static const uint32_t | row_for_bits_needed [] |
| Translates the 'bits_needed' to the appropriate 'row' offset for use with can_pack table. More... | |
| static const uint32_t | invalid_masks_for_offset [] |
| AND out masks for offsets where we don't know if we can fully pack for that offset. More... | |
| static const uint32_t | simple9_shift_table [] |
| Number of bits to shift when packing - 9 rows for simple-9. More... | |
Additional Inherited Members | |
| Public Types inherited from JASS::compress_integer | |
| typedef uint32_t | integer |
| This class and descendants will work on integers of this size. Do not change without also changing JASS_COMPRESS_INTEGER_BITS_PER_INTEGER. | |
Detailed Description
Relative-10 integer compression.
Relative-10 is an encoding almost identical to Simple-9, exceot that the selector encodes realtive to the previous selector - with the first encoding being in Simple-9. In this way the selector can be encoded in 2 bits rather than 4, and hence it is more effective than Simple-9. The largest integet that can be encoded is 2^28.
The encodings are: 1 * 30-bit 2 * 15-bit 3 * 10-bit 4 * 7-bit 5 * 6-bit 6 * 5-bit 7 * 4-bit 10 * 3-bit 15 * 2-bit 30 * 1-bit
See: V. Anh, A. Moffat (2005), Inverted Index Compression Using Word-Aligned Binary Codes, Information Retrieval, 8(1):151-166
Member Function Documentation
◆ decode()
|
virtual |
Decode a sequence of integers encoded with this codex.
- Parameters
-
decoded [out] The sequence of decoded integers. integers_to_decode [in] The minimum number of integers to decode (it may decode more). source [in] The encoded integers. source_length [in] The length (in bytes) of the source buffer.
Reimplemented from JASS::compress_integer_simple_9.
◆ encode()
|
virtual |
Encode a sequence of integers returning the number of bytes used for the encoding, or 0 if the encoded sequence doesn't fit in the buffer.
- Parameters
-
encoded [out] The sequence of bytes that is the encoded sequence. encoded_buffer_length [in] The length (in bytes) of the output buffer, encoded. source [in] The sequence of integers to encode. source_integers [in] The length (in integers) of the source buffer.
- Returns
- The number of bytes used to encode the integer sequence, or 0 on error (i.e. overflow).
Reimplemented from JASS::compress_integer_simple_9.
Member Data Documentation
◆ bits_to_use10
|
staticprotected |
Initial value:
=
{
1, 1, 2, 3, 4, 5, 6, 7,
10, 10, 10, 15, 15, 15, 15, 15,
30, 30, 30, 30, 30, 30, 30, 30,
30, 30, 30, 30, 30, 30, 30, 64,
64, 64, 64, 64, 64, 64, 64, 64,
64, 64, 64, 64, 64, 64, 64, 64,
64, 64, 64, 64, 64, 64, 64, 64,
64, 64, 64, 64, 64, 64, 64, 64
}
The number of bits that Relative-10 will be used to store an integer of the given the number of bits in length.
◆ relative10_table
|
staticprotected |
Initial value:
=
{
{1, 30, 0x3FFFFFFF, {3, 2, 1, 0, 0, 0, 0, 0, 0, 0}, {3, 2, 1, 0}},
{2, 15, 0x7FFF, {3, 2, 1, 0, 0, 0, 0, 0, 0, 0}, {3, 2, 1, 0}},
{3, 10, 0x3FF, {3, 2, 1, 0, 0, 0, 0, 0, 0, 0}, {3, 2, 1, 0}},
{4, 7, 0x7F, {3, 3, 2, 1, 0, 0, 0, 0, 0, 0}, {4, 3, 2, 0}},
{5, 6, 0x3F, {3, 3, 3, 2, 1, 0, 0, 0, 0, 0}, {5, 4, 3, 0}},
{6, 5, 0x1F, {3, 3, 3, 3, 2, 1, 0, 0, 0, 0}, {6, 5, 4, 0}},
{7, 4, 0xF, {3, 3, 3, 3, 3, 2, 1, 0, 0, 0}, {7, 6, 5, 0}},
{10, 3, 0x7, {3, 3, 3, 3, 3, 3, 2, 1, 0, 0}, {8, 7, 6, 0}},
{15, 2, 0x3, {3, 3, 3, 3, 3, 3, 3, 2, 1, 0}, {9, 8, 7, 0}},
{30, 1, 0x1, {3, 3, 3, 3, 3, 3, 3, 2, 1, 0}, {9, 8, 7, 0}}
}
The Relative-10 selector table explaining how the encoding works.
◆ table_row10
|
staticprotected |
Initial value:
=
{
0, 1, 2, 3, 4, 5, 6, 6, 6,
7, 7, 7, 7, 7, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 9, 9, 9
}
The row of the table to use given the number of integers to can pack into the word.
The documentation for this class was generated from the following files:
- source/compress_integer_relative_10.h
- source/compress_integer_relative_10.cpp
