SIMD compression (line Simple-9) using Elias delta to encode the selectors. More...

#include <compress_integer_elias_delta_simd.h>

Inheritance diagram for JASS::compress_integer_elias_delta_simd:

Collaboration diagram for JASS::compress_integer_elias_delta_simd:

Public Member Functions
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...

virtual long long	compress (unsigned char destination, long long destination_length, uint32_t source, long long source_integers)

virtual void	decompress (uint32_t destination, unsigned char source, long long destination_integers)

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 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 Types
typedef uint32_t	integer

Protected Member Functions
forceinline void	push_selector (uint32_t *&destination, uint8_t raw)

uint8_t forceinline	decode_selector (const uint32_t *&selector_set)

forceinline void	push_selector (uint32_t *&destination, uint8_t raw, uint32_t &selector_bits_used, uint64_t &accumulated_selector)

uint8_t forceinline	decode_selector (const uint32_t *&selector_set, uint32_t &selector_bits_used, uint64_t &accumulated_selector)

Static Protected Member Functions
static forceinline uint64_t	find_first_set_bit (uint64_t value)
	return the position of the least significant set bit (using a single machine code instruction) More...

static forceinline uint64_t	find_first_set_bit (uint64_t value)
	return the position of the least significant set bit (using a single machine code instruction) More...

Protected Attributes
uint32_t	selector_bits_used

uint64_t	accumulated_selector

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

SIMD compression (line Simple-9) using Elias delta to encode the selectors.

To quote the Wikipedia (https://en.wikipedia.org/wiki/Elias_delta_coding): The selectors are encoded using elias delta and the payload is an AVX-512 word with each integer width being determined by the selector

To code a number X ≥ 1: Let N = floor(log2 X) be the highest power of 2 in X, so 2^N ≤ X < 2^(N+1). Let L = floor(log2 N+1) be the highest power of 2 in N+1, so 2^L ≤ N+1 < 2^(L+1). Write L zeros, followed by the L+1-bit binary representation of N+1, followed by all but the leading bit (i.e. the last N bits) of X. An equivalent way to express the same process: Separate X into the highest power of 2 it contains (2^N) and the remaining N binary digits. Encode N+1 with Elias gamma coding. Append the remaining N binary digits to this representation of N+1. See: P. Elias (1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349.

Member Function Documentation

◆ decode() [1/2]

virtual void JASS::compress_integer_elias_delta_simd::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.

◆ decode() [2/2]

void JASS::compress_integer_elias_delta_simd::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() [1/2]

virtual size_t JASS::compress_integer_elias_delta_simd::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.

◆ encode() [2/2]

size_t JASS::compress_integer_elias_delta_simd::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.

◆ find_first_set_bit() [1/2]

static forceinline uint64_t JASS::compress_integer_elias_delta_simd::find_first_set_bit ( uint64_t value )

inlinestaticprotected

return the position of the least significant set bit (using a single machine code instruction)

Parameters

[in] value the integer to check.

Returns: The position of the lowest set bit (or 0 if no bits are set)

◆ find_first_set_bit() [2/2]

static forceinline uint64_t JASS::compress_integer_elias_delta_simd::find_first_set_bit ( uint64_t value )

inlinestaticprotected

return the position of the least significant set bit (using a single machine code instruction)

Parameters

[in] value the integer to check.

Returns: The position of the lowest set bit (or 0 if no bits are set)

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

JASSv1/compress_integer_elias_delta_simd.h
JASSv1/compress_integer_elias_delta_simd.c
source/compress_integer_elias_delta_simd.cpp

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ decode() [1/2]

◆ decode() [2/2]

◆ encode() [1/2]

◆ encode() [2/2]

◆ find_first_set_bit() [1/2]

◆ find_first_set_bit() [2/2]