Simple-9 optimally packed into words. More...

#include <compress_integer_simple_9_packed.h>

Inheritance diagram for JASS::compress_integer_simple_9_packed:

Collaboration diagram for JASS::compress_integer_simple_9_packed:

Public Member Functions
	compress_integer_simple_9_packed ()
	Constructor.

virtual	~compress_integer_simple_9_packed ()
	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
	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
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...

Protected Attributes
int64_t *	blocks_needed
	The optimal number of blocks needed to encode from here to the end of the sequence.

uint8_t *	masks
	Possible ways to encode this integer in the sequence.

size_t	blocks_length
	Length of the block_needed and masks dynamic arrays.

Static Protected Attributes
static const size_t	ints_packed_table []
	Number of integers packed into a word, given its mask type. More...

static const size_t	can_pack_table []
	Bitmask map for valid masks at an offset (column) for some num_bits_needed (row) More...

static const size_t	row_for_bits_needed []
	Translates the 'bits_needed' to the appropriate 'row' offset for use with can_pack table. More...

static const size_t	invalid_masks_for_offset []
	We AND out masks for offsets where we don't know if we can fully pack for that offset. More...

static const size_t	simple9_packed_shift_table []
	Number of bits to shift across when packing – is sum of prior packed ints (see above) 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

Simple-9 optimally packed into words.

Simple-9 (and other Simple encodings) are normally packed into words left to right, which is not optimal in pathalogical cases. Those cases do occur, primarility because there are so many postings lists and they are often long. This version of Simple-9 optimally packs integers into words.

See: Trotman A, Albert M, Burgess B (2015), Optimal Packing in Simple-Family Codecs, Proceedings of the 2015 International Conference on The Theory of Information Retrieval (ICTIR 2015), pp. 337-340

Member Function Documentation

◆ decode()

void JASS::compress_integer_simple_9_packed::decode	(	integer *	decoded,
		size_t	integers_to_decode,
		const void *	source,
		size_t	source_length
	)

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.

Implements JASS::compress_integer.

◆ encode()

size_t JASS::compress_integer_simple_9_packed::encode	(	void *	encoded,
		size_t	encoded_buffer_length,
		const integer *	source,
		size_t	source_integers
	)

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).

Implements JASS::compress_integer.

Member Data Documentation

◆ can_pack_table

const size_t JASS::compress_integer_simple_9_packed::can_pack_table

staticprotected

Initial value:

=
        {
        0x01ff, 0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x000f, 0x0007, 0x0007, 0x0003, 0x0003, 0x0003, 0x0003, 0x0003, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001, 0x0001,
        0x01fe, 0x00fe, 0x007e, 0x003e, 0x001e, 0x000e, 0x000e, 0x0006, 0x0006, 0x0002, 0x0002, 0x0002, 0x0002, 0x0002, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x01fc, 0x00fc, 0x007c, 0x003c, 0x001c, 0x000c, 0x000c, 0x0004, 0x0004, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x01f8, 0x00f8, 0x0078, 0x0038, 0x0018, 0x0008, 0x0008, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x01f0, 0x00f0, 0x0070, 0x0030, 0x0010, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x01e0, 0x00e0, 0x0060, 0x0020, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x01c0, 0x00c0, 0x0040, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x0180, 0x0080, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x0100, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
        0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000
        }

Bitmask map for valid masks at an offset (column) for some num_bits_needed (row)

◆ ints_packed_table

const size_t JASS::compress_integer_simple_9_packed::ints_packed_table

staticprotected

Initial value:

=
        {
        28, 14, 9, 7, 5, 4, 3, 2, 1
        }

Number of integers packed into a word, given its mask type.

◆ invalid_masks_for_offset

const size_t JASS::compress_integer_simple_9_packed::invalid_masks_for_offset

staticprotected

Initial value:

=
        {
        0x0000, 0x0100, 0x0180, 0x01c0, 0x01e0, 0x01f0, 0x01f0, 0x01f8, 0x01f8, 0x01fc, 0x01fc, 0x01fc, 0x01fc, 0x01fc, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01fe, 0x01ff
        }

We AND out masks for offsets where we don't know if we can fully pack for that offset.

◆ row_for_bits_needed

const size_t JASS::compress_integer_simple_9_packed::row_for_bits_needed

staticprotected

Initial value:

=
        {
        0, 0, 28, 56, 84, 112, 140, 140, 168, 168, 196, 196, 196, 196, 196, 224, 224, 224, 224, 224, 224, 224, 224, 224, 224, 224, 224, 224, 224,       
        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252      
        }

Translates the 'bits_needed' to the appropriate 'row' offset for use with can_pack table.

◆ simple9_packed_shift_table

const size_t JASS::compress_integer_simple_9_packed::simple9_packed_shift_table

staticprotected

Initial value:

=
        {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
        0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
        0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
        0, 4, 8, 12, 16, 20, 24, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
        0, 5, 10, 15, 20, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
        0, 7, 14, 21, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
        0, 9, 18, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
        0, 14, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
        0, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28
        }

Number of bits to shift across when packing – is sum of prior packed ints (see above)

The documentation for this class was generated from the following files:

source/compress_integer_simple_9_packed.h
source/compress_integer_simple_9_packed.cpp

Public Member Functions

Static Public Member Functions

Protected Attributes

Static Protected Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ decode()

◆ encode()

Member Data Documentation

◆ can_pack_table

◆ ints_packed_table

◆ invalid_masks_for_offset

◆ row_for_bits_needed

◆ simple9_packed_shift_table