Variable byte compression for integer sequences. More...

#include <compress_integer_variable_byte.h>

Inheritance diagram for JASS::compress_integer_variable_byte:

Collaboration diagram for JASS::compress_integer_variable_byte:

Public Member Functions
	compress_integer_variable_byte ()
	Constructor.

virtual	~compress_integer_variable_byte ()
	Constructor.

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	static_decode (integer decoded, size_t integers_to_decode, const void source_as_void, size_t source_length)
	Decode a sequence of integers encoded with this codex. More...

static size_t	bytes_needed_for (uint32_t value)
	Return the number of bytes necessary to encode the integer value. More...

static size_t	bytes_needed_for (uint64_t value)
	Return the number of bytes necessary to encode the integer value. More...

template<typename DESTINATION >
static forceinline void	compress_into (DESTINATION &destination, uint32_t value)
	Encode the given integer placing the encoding into destination (whose size is not validated). More...

template<typename DESTINATION >
static forceinline void	compress_into (DESTINATION &destination, uint64_t value)
	Encode the given integer placing the encoding into destination (whose size is not validated). More...

template<typename SOURCE >
static forceinline void	decompress_into (uint16_t *decoded, SOURCE &source)
	Decode the given integer placing the encoding into destination (whose size is not validated). More...

template<typename SOURCE >
static forceinline void	decompress_into (uint32_t *decoded, SOURCE &source)
	Decode the given integer placing the encoding into destination (whose size is not validated). More...

template<typename SOURCE >
static forceinline void	decompress_into (uint64_t *decoded, SOURCE &source)
	Decode the given integer placing the encoding into destination (whose size is not validated). More...

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

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

Variable byte compression for integer sequences.

Variable byte compression is a whole suite of different techniques, for details see: A. Trotman (2014), Compression, SIMD, and Postings Lists. In Proceedings of the 2014 Australasian Document Computing Symposium (ADCS 2014), Pages 50-58. DOI=http://dx.doi.org/10.1145/2682862.2682870 This particular version uses a stop-bit in the high bit of the last byte of the encoded integer, stores the integer big-endian (high byte first), and uses loop unwinding for decoding efficiency. The encoding is straight forward. An integer is broken into 7-bit chunks with the top bit of each chunk being 0, except the last byte which has a 1 in the top bit. So, the integer 1905 (0x771) is the binary sequence 011101110001, which broken into 7-bit chunks is 0001110 1110001. These then get the high bits added, 0 for all except the last byte, [0]0001110 [1]1110001, then write out the byte sequence high byte first 0x0E 0xF1. This implementation works with 32-bit and 64-bit integers. To encode 64-bit integers ensure #define JASS_COMPRESS_INTEGER_BITS_PER_INTEGER 64 is set at compile time.

Member Function Documentation

◆ bytes_needed_for() [1/2]

static size_t JASS::compress_integer_variable_byte::bytes_needed_for ( uint32_t value )

inlinestatic

Return the number of bytes necessary to encode the integer value.

Parameters

value [in] The value whose encoded size is being computed

Returns: the numner of bytes needed to store the enoding of value.

◆ bytes_needed_for() [2/2]

static size_t JASS::compress_integer_variable_byte::bytes_needed_for ( uint64_t value )

inlinestatic

Return the number of bytes necessary to encode the integer value.

Parameters

value [in] The value whose encoded size is being computed

Returns: the numner of bytes needed to store the enoding of value.

◆ compress_into() [1/2]

template<typename DESTINATION >

static forceinline void JASS::compress_integer_variable_byte::compress_into	(	DESTINATION &	destination,
		uint32_t	value
	)

inlinestatic

Encode the given integer placing the encoding into destination (whose size is not validated).

Parameters

destination	[out] The buffer to write into.
value	[in] The value to encode.

◆ compress_into() [2/2]

template<typename DESTINATION >

static forceinline void JASS::compress_integer_variable_byte::compress_into	(	DESTINATION &	destination,
		uint64_t	value
	)

inlinestatic

Encode the given integer placing the encoding into destination (whose size is not validated).

Parameters

destination	[out] The buffer to write into.
value	[in] The value to encode.

◆ decode()

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

inlinevirtual

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.

Reimplemented in JASS::compress_integer_elias_gamma_simd_vb.

◆ decompress_into() [1/3]

template<typename SOURCE >

static forceinline void JASS::compress_integer_variable_byte::decompress_into	(	uint16_t *	decoded,
		SOURCE &	source
	)

inlinestatic

Decode the given integer placing the encoding into destination (whose size is not validated).

Parameters

decoded	[out] The decoded integer.
source	[in] The buffer to decode from.

◆ decompress_into() [2/3]

template<typename SOURCE >

static forceinline void JASS::compress_integer_variable_byte::decompress_into	(	uint32_t *	decoded,
		SOURCE &	source
	)

inlinestatic

Decode the given integer placing the encoding into destination (whose size is not validated).

Parameters

decoded	[out] The decoded integer.
source	[in] The buffer to decode from.

◆ decompress_into() [3/3]

template<typename SOURCE >

static forceinline void JASS::compress_integer_variable_byte::decompress_into	(	uint64_t *	decoded,
		SOURCE &	source
	)

inlinestatic

Decode the given integer placing the encoding into destination (whose size is not validated).

Parameters

decoded	[out] The decoded integer.
source	[in] The buffer to decode from.

◆ encode()

size_t compress_integer_variable_byte::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.

Reimplemented in JASS::compress_integer_elias_gamma_simd_vb.

◆ static_decode()

static void JASS::compress_integer_variable_byte::static_decode	(	integer *	decoded,
		size_t	integers_to_decode,
		const void *	source_as_void,
		size_t	source_length
	)

inlinestatic

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_as_void	[in] The encoded integers.
source_length	[in] The length (in bytes) of the source buffer.

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

source/compress_integer_variable_byte.h
source/compress_integer_variable_byte.cpp

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ bytes_needed_for() [1/2]

◆ bytes_needed_for() [2/2]

◆ compress_into() [1/2]

◆ compress_into() [2/2]

◆ decode()

◆ decompress_into() [1/3]

◆ decompress_into() [2/3]

◆ decompress_into() [3/3]

◆ encode()

◆ static_decode()