Run length encoding for arrays. More...

#include <cstdlib>
#include <cstring>
#include "MEM_guardedalloc.h"
#include "BLI_assert.h"
#include "BLI_utildefines.h"
#include "BLI_array_store.h"
#include "BLI_strict_flags.h"

Classes
struct	RLE_Head
struct	RLE_Literal
struct	RLE_Span
struct	RLE_Elem
struct	RLE_ElemChunk
struct	RLE_ElemChunkIter

Functions
Private API
	BLI_STATIC_ASSERT (sizeof(RLE_Span)==sizeof(size_t)+sizeof(uint8_t), "")
	BLI_STATIC_ASSERT (sizeof(RLE_ElemChunk)<=4096 - MEM_SIZE_OVERHEAD, "")
static void	rle_link_chunk_iter_new (RLE_ElemChunk links_block, RLE_ElemChunkIter link_block_iter)
static RLE_Elem *	rle_link_chunk_iter_step (RLE_ElemChunkIter *link_block_iter)
static RLE_ElemChunk *	rle_link_chunk_new ()
static void	rle_link_chunk_free_all (RLE_ElemChunk *link_block)
static RLE_Elem *	rle_link_chunk_elem_new (RLE_ElemChunk **link_block_p)
Public API
uint8_t *	BLI_array_store_rle_encode (const uint8_t data_dec, const size_t data_dec_len, const size_t data_enc_extra_size, size_t r_data_enc_len)
void	BLI_array_store_rle_decode (const uint8_t data_enc, const size_t data_enc_len, void data_dec_v, const size_t data_dec_len)

Internal Utilities
#define	USE_FIND_FASTPATH
static size_t	find_byte_not_equal_to (const uint8_t *data, size_t offset, const size_t size, const uint8_t value)

Detailed Description

Run length encoding for arrays.

The intended use is to pre-process arrays before storing in BArrayStore. This should be used in cases arrays are likely to contain large spans of contiguous data (which doesn't de-duplicate so well).

Intended for byte arrays as there is no special logic to handle alignment. Note that this could be supported and would be useful to de-duplicate repeating patterns of non-byte data.

Notes:

For random data, the size overhead is only sizeof(size_t[4]) (header & footer).
The main down-side in that case of random data is detecting there are no spans to RLE encode, and creating the "encoded" copy.
For an array containing a single value the resulting size will be sizeof(size_t[3]) + sizeof(uint8_t).
This is not intended to be used for compression, it would be possible to use less memory by packing the size of short spans into fewer bits. This isn't done as it requires more computation when encoding.
This RLE implementation is a balance between working well for random bytes as well as arrays containing large contiguous spans.

There is some bias towards performing well with arrays containing contiguous spans mainly because the benefits are greater and the likelihood is that RLE encoding is used because there is a probability the data will be able to take advantage of RLE. Having said this - encoding random bytes must not be slow either.

Definition in file array_store_rle.cc.

Macro Definition Documentation

◆ USE_FIND_FASTPATH

#define USE_FIND_FASTPATH

Use faster method of spanning for change by stepping over larger values.

NOTE(@ideasman42) In practice this gives ~3.5x overall speedup when encoding large arrays. For random data the performance is worse, about ~5% slower.

Definition at line 62 of file array_store_rle.cc.

Function Documentation

◆ BLI_array_store_rle_decode()

void BLI_array_store_rle_decode	(	const uint8_t *	data_enc,
		const size_t	data_enc_len,
		void *	data_dec_v,
		const size_t	data_dec_len )

Decode a run-length encoded array, writing the result into data_dec_v.

Parameters

data_enc	The data to encode (returned by BLI_array_store_rle_encode).
data_enc_len	The size of data_enc.
data_dec	The destination for the decoded data to be written to.
data_dec_len	The size of the destination (as passed to BLI_array_store_rle_encode).

Definition at line 380 of file array_store_rle.cc.

References BLI_assert, e, and UNUSED_VARS_NDEBUG.

Referenced by rle_encode_decode_test(), and um_arraystore_cd_expand().

◆ BLI_array_store_rle_encode()

uint8_t * BLI_array_store_rle_encode	(	const uint8_t *	data_dec,
		size_t	data_dec_len,
		size_t	data_enc_extra_size,
		size_t *	r_data_enc_len )

Return a run-length encoded copy of data_dec.

Parameters

data_dec	The data to encode.
data_dec_len	The size of the data to encode.
data_enc_extra_size	Allocate extra memory at the beginning of the array. This doesn't impact the value of r_data_enc_len. This must be skipped when decoding.
r_data_enc_len	The size of the resulting RLE encoded data.