Blender V5.3
array_store_rle.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
39
40#include <cstdlib>
41#include <cstring>
42
43#include "MEM_guardedalloc.h"
44
45#include "BLI_assert.hh"
46#include "BLI_utildefines.hh"
47
48#include "BLI_array_store.hh" /* Own include. */
49
50#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
51
52namespace blender {
53
54/* -------------------------------------------------------------------- */
57
64#define USE_FIND_FASTPATH
65
71static size_t find_byte_not_equal_to(const uint8_t *data,
72 size_t offset,
73 const size_t size,
74 const uint8_t value)
75{
76 BLI_assert(offset <= size);
77
78#ifdef USE_FIND_FASTPATH
79 using fast_int = uintptr_t;
80
81 /* In the case of random data, early exit without entering more involved steps. */
82
83 /* Calculate the minimum size which may use an optimized search. */
84 constexpr size_t min_size_for_fast_path = (
85 /* Pass 1: scans a fixed size. */
86 sizeof(size_t[2]) +
87 /* Pass 2: scans a fixed size but aligns to `fast_int`. */
88 sizeof(size_t) + sizeof(fast_int) +
89 /* Pass 3: trims the end of `data` by `fast_int`
90 * add to ensure there is at least one item to read. */
91 sizeof(fast_int));
92
93 if (size - offset > min_size_for_fast_path) [[likely]] {
94
95 /* Pass 1: Scan forward with a fixed size to check if an early exit
96 * is needed (this may exit on the first few bytes). */
97 const uint8_t *p = data + offset;
98 const uint8_t *p_end = p + sizeof(size_t[2]);
99 do {
100 if (*p != value) [[likely]] {
101 return size_t(p - data);
102 }
103 p++;
104 } while (p < p_end);
105 /* `offset` is no longer valid and needs to be updated from `p` before use. */
106
107 /* Pass 2: Scan forward at least `sizeof(size_t)` bytes,
108 * aligned to the next `sizeof(fast_int)` aligned boundary. */
109 p_end = reinterpret_cast<const uint8_t *>(
110 ((uintptr_t(p) + sizeof(size_t) + sizeof(fast_int)) & ~(sizeof(fast_int) - 1)));
111 do {
112 if (*p != value) [[likely]] {
113 return size_t(p - data);
114 }
115 p++;
116 } while (p < p_end);
117
118 /* Pass 3: Scan forward the `fast_int` aligned chunks (the fast path).
119 * This block is responsible for scanning over large spans of contiguous bytes. */
120
121 /* There are at least `sizeof(size_t[2])` number of bytes all equal.
122 * Use `fast_int` aligned reads for a faster search. */
123 BLI_assert((uintptr_t(p) & (sizeof(fast_int) - 1)) == 0);
124 const fast_int *p_fast = reinterpret_cast<const fast_int *>(p);
125 /* Not aligned, but this doesn't matter as it's only used for comparison. */
126 const fast_int *p_fast_last = reinterpret_cast<const fast_int *>(data +
127 (size - sizeof(fast_int)));
128 BLI_assert(p_fast <= p_fast_last);
129 fast_int value_fast;
130 memset(&value_fast, value, sizeof(value_fast));
131 do {
132 /* Use unlikely given many of the previous bytes match. */
133 if (*p_fast != value_fast) [[unlikely]] {
134 break;
135 }
136 p_fast++;
137 } while (p_fast <= p_fast_last);
138 offset = size_t(reinterpret_cast<const uint8_t *>(p_fast) - data);
139 /* Perform byte level check with any trailing data. */
140 }
141#endif /* USE_FIND_FASTPATH */
142
143 while ((offset < size) && (value == data[offset])) {
144 offset += 1;
145 }
146 return offset;
147}
148
149#ifdef USE_FIND_FASTPATH
154static inline bool all_bytes_homogeneous(const uintptr_t x)
155{
156 /* Pattern of 0x01 in each byte position (0x01010101... for any word size).
157 * Multiplying a byte value by this spreads it to all byte positions. */
158 constexpr uintptr_t byte_spread = ~uintptr_t(0) / 255;
159
160 const uintptr_t first_byte = x & 0xFF;
161 return x == first_byte * byte_spread;
162}
163#endif /* USE_FIND_FASTPATH */
164
173template<size_t RLE_SKIP_THRESHOLD>
175 const size_t offset,
176 const size_t size,
177 size_t *span_skip_next_p)
178{
179 /* The default expected value, no need to assign here. */
180 BLI_assert(*span_skip_next_p == 1);
181
182 constexpr size_t rle_skip_threshold = RLE_SKIP_THRESHOLD;
183 size_t ofs_test_start = offset;
184
185#ifdef USE_FIND_FASTPATH
186 using fast_int = uintptr_t;
187
188 /* Calculate the minimum size which may use an optimized search. */
189 constexpr size_t min_size_for_fast_path = (
190 /* Worst case advances one full `fast_int` to reach aligned boundary. */
191 sizeof(fast_int) +
192 /* Reads one `fast_int` to detect dense runs early. */
193 sizeof(fast_int) +
194 /* At least one `fast_int` read in the skip loop. */
195 sizeof(fast_int) +
196 /* `p_end` reserves `sizeof(fast_int)` for safe reads. */
197 sizeof(fast_int) +
198 /* Backtrack margin: `rle_skip_threshold - 1` bytes, rounded up to `fast_int`. */
199 (((rle_skip_threshold - 1) + (sizeof(fast_int) - 1)) & ~(sizeof(fast_int) - 1)));
200
201 /* Fast path: skip regions that cannot contain an RLE span. */
202 if (size - offset > min_size_for_fast_path) {
203 constexpr size_t ALIGN_BITS = sizeof(fast_int) - 1;
204
205 /* Align to next fast_int boundary. */
206 const fast_int *p = reinterpret_cast<const fast_int *>(
207 ((uintptr_t(data + offset) + sizeof(fast_int)) & ~ALIGN_BITS));
208 const fast_int *p_end = reinterpret_cast<const fast_int *>(
209 ((uintptr_t(data + size) - sizeof(fast_int)) & ~ALIGN_BITS));
210
211 /* Early check: if the first chunk is homogeneous, this region likely has
212 * dense runs. Skip the fast path to avoid overhead. */
213 if (p < p_end && !all_bytes_homogeneous(*p)) {
214 p++;
215
216 /* Skip non-homogeneous chunks. */
217 while (p < p_end && !all_bytes_homogeneous(*p)) {
218 p++;
219 }
220
221 /* Move back `rle_skip_threshold - 1` bytes from where we stopped to catch spans
222 * that may have started just before the homogeneous region. */
223 const size_t stop_pos = size_t(reinterpret_cast<const uint8_t *>(p) - data);
224 const size_t backtrack = rle_skip_threshold - 1;
225 if (stop_pos > offset + backtrack) {
226 ofs_test_start = stop_pos - backtrack;
227 }
228 }
229 }
230#endif /* USE_FIND_FASTPATH */
231
232 /* Byte-level scan. */
233 size_t ofs_test = ofs_test_start + 1;
234 /* Check the offset isn't at the very end of the array. */
235 if (ofs_test < size) [[likely]] {
236 /* The first value that changed, start searching here. */
237 uint8_t value = data[ofs_test_start];
238 do {
239 if (value == data[ofs_test]) {
240 ofs_test += 1;
241 const size_t span_test = ofs_test - ofs_test_start;
242 BLI_assert(span_test <= rle_skip_threshold);
243 if (span_test == rle_skip_threshold) {
244 /* Write the span of non-RLE data,
245 * then start scanning the magnitude of the RLE span at the start of the loop. */
246 *span_skip_next_p = span_test;
247 return ofs_test_start;
248 }
249 }
250 else {
251 BLI_assert(ofs_test - ofs_test_start < rle_skip_threshold);
252 value = data[ofs_test];
253 ofs_test_start = ofs_test;
254 ofs_test += 1;
255 }
256 } while (LIKELY(ofs_test < size));
257 }
258 return size;
259}
260
262
263/* -------------------------------------------------------------------- */
266
267struct RLE_Head {
273 size_t span_size;
274};
275
277 uint8_t _span_size_pad[sizeof(size_t)];
278 size_t value;
279};
280
281struct RLE_Span {
282 uint8_t _span_size_pad[sizeof(size_t)];
284};
285BLI_STATIC_ASSERT(sizeof(RLE_Span) == sizeof(size_t) + sizeof(uint8_t), "");
286
287struct RLE_Elem {
288 union {
292 };
293};
294
297 size_t links_num;
299 RLE_Elem links[(4096 / sizeof(RLE_Elem)) -
300 (sizeof(RLE_ElemChunk *) + sizeof(size_t) + MEM_SIZE_OVERHEAD)];
301};
303
308
309static void rle_link_chunk_iter_new(RLE_ElemChunk *links_block, RLE_ElemChunkIter *link_block_iter)
310{
311 link_block_iter->iter = links_block;
312 link_block_iter->link_curr = 0;
313}
314
316{
317 RLE_ElemChunk *link_block = link_block_iter->iter;
318 if (link_block_iter->link_curr < link_block->links_num) {
319 return &link_block->links[link_block_iter->link_curr++];
320 }
321 if (link_block->next) {
322 link_block = link_block_iter->iter = link_block->next;
323 link_block_iter->link_curr = 1;
324 return &link_block->links[0];
325 }
326 return nullptr;
327}
328
330{
332 link_block->next = nullptr;
333 link_block->links_num = 0;
334 return link_block;
335}
336
338{
339 while (RLE_ElemChunk *link_iter = link_block) {
340 link_block = link_iter->next;
341 MEM_delete(link_iter);
342 }
343}
344
346{
347 RLE_ElemChunk *link_block = *link_block_p;
348 if (link_block->links_num == ARRAY_SIZE(link_block->links)) [[unlikely]] {
349 RLE_ElemChunk *link_block_next = rle_link_chunk_new();
350 link_block->next = link_block_next;
351 link_block = link_block_next;
352 *link_block_p = link_block_next;
353 }
354 return &link_block->links[link_block->links_num++];
355}
356
358
359/* -------------------------------------------------------------------- */
362
364 const size_t data_dec_len,
365 const size_t data_enc_extra_size,
366 size_t *r_data_enc_len)
367{
368 size_t data_enc_alloc_size = data_enc_extra_size +
369 sizeof(RLE_Literal); /* A single null terminator. */
370
371 /* Notes on the threshold for choosing when to include literal data or RLE encode.
372 * From testing a ~4 million array of booleans.
373 *
374 * Regarding space efficiency:
375 *
376 * - For data with fewer changes: `sizeof(RLE_Literal)` (16 on a 64bit system) is optimal.
377 * The improvement varies, between 5-20%.
378 * - For random data: `sizeof(RLE_Literal) + sizeof(size_t)` (24 on a 64bit system) is optimal.
379 * The improvement is only ~5% though.
380 *
381 * The time difference between each is roughly the same.
382 */
383 constexpr size_t rle_skip_threshold = sizeof(RLE_Literal);
384
385 RLE_ElemChunk *link_blocks = rle_link_chunk_new();
386 RLE_ElemChunk *link_blocks_first = link_blocks;
387
388 /* Re-use results from scanning ahead (as needed). */
389 for (size_t ofs_dec = 0, span_skip_next = 1; ofs_dec < data_dec_len;) {
390 /* Scan ahead to detect the size of the non-RLE span. */
391 size_t ofs_dec_next = ofs_dec + span_skip_next;
392 span_skip_next = 1;
393
394 /* Detect and use the `span` if possible. */
395 uint8_t value_start = data_dec[ofs_dec];
396 ofs_dec_next = find_byte_not_equal_to(data_dec, ofs_dec_next, data_dec_len, value_start);
397
398 RLE_Elem *e = rle_link_chunk_elem_new(&link_blocks);
399 const size_t span = ofs_dec_next - ofs_dec;
400 if (span >= rle_skip_threshold) {
401 /* Catch off by one errors. */
402 BLI_assert(data_dec[ofs_dec] == data_dec[(ofs_dec + span) - 1]);
403 BLI_assert((ofs_dec + span == data_dec_len) ||
404 (data_dec[ofs_dec] != data_dec[(ofs_dec + span)]));
405 e->head.span_size = span;
406 e->span.value = value_start;
407 data_enc_alloc_size += sizeof(RLE_Span);
408 }
409 else {
410 /* A large enough span was not found,
411 * scan ahead to detect the size of the non-RLE span. */
413 data_dec, ofs_dec_next, data_dec_len, &span_skip_next);
414
415 /* Interleave the #RLE_Literal. */
416 const size_t non_rle_span = ofs_dec_next - ofs_dec;
417 e->head.span_size = 0;
418 e->literal.value = non_rle_span;
419 data_enc_alloc_size += sizeof(RLE_Literal) + non_rle_span;
420 }
421
422 ofs_dec = ofs_dec_next;
423 }
424
425 /* Encode RLE and literal data into this flat buffer. */
426 uint8_t *data_enc = MEM_new_array_uninitialized<uint8_t>(data_enc_alloc_size, __func__);
427 data_enc += data_enc_extra_size;
428
429 size_t ofs_enc = 0;
430 size_t ofs_dec = 0;
431
432 RLE_ElemChunkIter link_block_iter;
433 rle_link_chunk_iter_new(link_blocks_first, &link_block_iter);
434 while (RLE_Elem *e = rle_link_chunk_iter_step(&link_block_iter)) {
435 BLI_assert(ofs_dec <= data_dec_len);
436
437 if (e->head.span_size) {
438 memcpy(data_enc + ofs_enc, &e->span, sizeof(RLE_Span));
439 ofs_enc += sizeof(RLE_Span);
440 ofs_dec += e->head.span_size;
441 }
442 else {
443 memcpy(data_enc + ofs_enc, &e->literal, sizeof(RLE_Literal));
444 ofs_enc += sizeof(RLE_Literal);
445 BLI_assert(e->literal.value > 0);
446 const size_t non_rle_span = e->literal.value;
447 memcpy(data_enc + ofs_enc, data_dec + ofs_dec, non_rle_span);
448 ofs_enc += non_rle_span;
449 ofs_dec += non_rle_span;
450 }
451 }
452 rle_link_chunk_free_all(link_blocks_first);
453 BLI_assert(data_enc_extra_size + ofs_enc + sizeof(RLE_Literal) == data_enc_alloc_size);
454 BLI_assert(ofs_dec == data_dec_len);
455
456 /* Set the `RLE_Literal` span & value to 0 to terminate. */
457 memset(data_enc + ofs_enc, 0x0, sizeof(RLE_Literal));
458
459 *r_data_enc_len = data_enc_alloc_size - data_enc_extra_size;
460
461 data_enc -= data_enc_extra_size;
462 return data_enc;
463}
464
466 const size_t data_enc_len,
467 void *data_dec_v,
468 const size_t data_dec_len)
469{
470 /* NOTE: `data_enc_len` & `data_dec_len` could be omitted.
471 * They're just to ensure data isn't corrupt. */
472 uint8_t *data_dec = reinterpret_cast<uint8_t *>(data_dec_v);
473 size_t ofs_enc = 0;
474 size_t ofs_dec = 0;
475
476 while (true) {
477 /* Copy as this may not be aligned. */
478 RLE_Head e;
479 memcpy(&e, data_enc + ofs_enc, sizeof(RLE_Head));
480 ofs_enc += sizeof(RLE_Head);
481 if (e.span_size != 0) {
482 /* Read #RLE_Span::value directly from memory. */
483 const uint8_t value = *reinterpret_cast<const uint8_t *>(data_enc + ofs_enc);
484 memset(data_dec + ofs_dec, int(value), e.span_size);
485 ofs_enc += sizeof(uint8_t);
486 ofs_dec += e.span_size;
487 }
488 else {
489 /* Read #RLE_Literal::value directly from memory. */
490 size_t non_rle_span;
491 memcpy(&non_rle_span, data_enc + ofs_enc, sizeof(size_t));
492 ofs_enc += sizeof(size_t);
493 if (non_rle_span) {
494 memcpy(data_dec + ofs_dec, data_enc + ofs_enc, non_rle_span);
495 ofs_enc += non_rle_span;
496 ofs_dec += non_rle_span;
497 }
498 else {
499 /* Both are zero - an end-of-buffer signal. */
500 break;
501 }
502 }
503 }
504 BLI_assert(ofs_enc == data_enc_len);
505 BLI_assert(ofs_dec == data_dec_len);
506 UNUSED_VARS_NDEBUG(data_enc_len, data_dec_len);
507}
508
510
511} // namespace blender
Efficient in-memory storage of multiple similar arrays.
Read Blender memory allocation and freeing.
#define UNUSED_VARS_NDEBUG(...)
#define LIKELY(x)
#define MEM_SIZE_OVERHEAD
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
BLI_STATIC_ASSERT(ARRAY_SIZE(data_mode_strings)==CTX_MODE_NUM+1, "Must have a string for each context mode") const char *CTX_data_mode_string(const bContext *C)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static size_t find_byte_not_equal_to(const uint8_t *data, size_t offset, const size_t size, const uint8_t value)
static void rle_link_chunk_free_all(RLE_ElemChunk *link_block)
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)
static RLE_ElemChunk * rle_link_chunk_new()
BMesh const char void * data
unsigned char uint8_t
Definition BKE_text.h:79
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
_W64 unsigned int uintptr_t
Definition BKE_text.h:120
static RLE_Elem * rle_link_chunk_iter_step(RLE_ElemChunkIter *link_block_iter)
static RLE_Elem * rle_link_chunk_elem_new(RLE_ElemChunk **link_block_p)
static void rle_link_chunk_iter_new(RLE_ElemChunk *links_block, RLE_ElemChunkIter *link_block_iter)
static bool all_bytes_homogeneous(const uintptr_t x)
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)
static size_t find_next_rle_span_start(const uint8_t *data, const size_t offset, const size_t size, size_t *span_skip_next_p)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
RLE_Elem links[(4096/sizeof(RLE_Elem)) -(sizeof(RLE_ElemChunk *)+sizeof(size_t)+MEM_SIZE_OVERHEAD)]
uint8_t _span_size_pad[sizeof(size_t)]
uint8_t _span_size_pad[sizeof(size_t)]