|
Blender V5.3
|
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) |
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:
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.
| #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.