Blender V5.3
array_store_rle.cc File Reference

Run length encoding for arrays. More...

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

Go to the source code of this file.

Classes

struct  blender::RLE_Head
struct  blender::RLE_Literal
struct  blender::RLE_Span
struct  blender::RLE_Elem
struct  blender::RLE_ElemChunk
struct  blender::RLE_ElemChunkIter

Namespaces

namespace  blender
 BMesh Iterators.

Functions

Private API
 blender::BLI_STATIC_ASSERT (sizeof(RLE_Span)==sizeof(size_t)+sizeof(uint8_t), "")
 blender::BLI_STATIC_ASSERT (sizeof(RLE_ElemChunk)<=4096 - MEM_SIZE_OVERHEAD, "")
static void blender::rle_link_chunk_iter_new (RLE_ElemChunk *links_block, RLE_ElemChunkIter *link_block_iter)
static RLE_Elem * blender::rle_link_chunk_iter_step (RLE_ElemChunkIter *link_block_iter)
static RLE_ElemChunk * blender::rle_link_chunk_new ()
static void blender::rle_link_chunk_free_all (RLE_ElemChunk *link_block)
static RLE_Elem * blender::rle_link_chunk_elem_new (RLE_ElemChunk **link_block_p)
Public API
uint8_t * blender::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)
void blender::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 blender::find_byte_not_equal_to (const uint8_t *data, size_t offset, const size_t size, const uint8_t value)
static bool blender::all_bytes_homogeneous (const uintptr_t x)
template<size_t RLE_SKIP_THRESHOLD>
static size_t blender::find_next_rle_span_start (const uint8_t *data, const size_t offset, const size_t size, size_t *span_skip_next_p)

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 64 of file array_store_rle.cc.