/src/CMake/Utilities/cmliblzma/liblzma/rangecoder/range_encoder.h

Source
// SPDX-License-Identifier: 0BSD

///////////////////////////////////////////////////////////////////////////////
//
/// \file       range_encoder.h
/// \brief      Range Encoder
///
//  Authors:    Igor Pavlov
//              Lasse Collin
//
///////////////////////////////////////////////////////////////////////////////

#ifndef LZMA_RANGE_ENCODER_H
#define LZMA_RANGE_ENCODER_H

#include "range_common.h"
#include "price.h"


/// Maximum number of symbols that can be put pending into lzma_range_encoder
/// structure between calls to lzma_rc_encode(). For LZMA, 48+5 is enough
/// (match with big distance and length followed by range encoder flush).
#define RC_SYMBOLS_MAX 53


typedef struct {
  uint64_t low;
  uint64_t cache_size;
  uint32_t range;
  uint8_t cache;

  /// Number of bytes written out by rc_encode() -> rc_shift_low()
  uint64_t out_total;

  /// Number of symbols in the tables
  size_t count;

  /// rc_encode()'s position in the tables
  size_t pos;

  /// Symbols to encode
  enum {
    RC_BIT_0,
    RC_BIT_1,
    RC_DIRECT_0,
    RC_DIRECT_1,
    RC_FLUSH,
  } symbols[RC_SYMBOLS_MAX];

  /// Probabilities associated with RC_BIT_0 or RC_BIT_1
  probability *probs[RC_SYMBOLS_MAX];

} lzma_range_encoder;


static inline void
rc_reset(lzma_range_encoder *rc)
{
  rc->low = 0;
  rc->cache_size = 1;
  rc->range = UINT32_MAX;
  rc->cache = 0;
  rc->out_total = 0;
  rc->count = 0;
  rc->pos = 0;
}


static inline void
rc_forget(lzma_range_encoder *rc)
{
  // This must not be called when rc_encode() is partially done.
  assert(rc->pos == 0);
  rc->count = 0;
}


static inline void
rc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit)
{
  rc->symbols[rc->count] = bit;
  rc->probs[rc->count] = prob;
  ++rc->count;
}


static inline void
rc_bittree(lzma_range_encoder *rc, probability *probs,
    uint32_t bit_count, uint32_t symbol)
{
  uint32_t model_index = 1;

  do {
    const uint32_t bit = (symbol >> --bit_count) & 1;
    rc_bit(rc, &probs[model_index], bit);
    model_index = (model_index << 1) + bit;
  } while (bit_count != 0);
}


static inline void
rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
    uint32_t bit_count, uint32_t symbol)
{
  uint32_t model_index = 1;

  do {
    const uint32_t bit = symbol & 1;
    symbol >>= 1;
    rc_bit(rc, &probs[model_index], bit);
    model_index = (model_index << 1) + bit;
  } while (--bit_count != 0);
}


static inline void
rc_direct(lzma_range_encoder *rc,
    uint32_t value, uint32_t bit_count)
{
  do {
    rc->symbols[rc->count++]
        = RC_DIRECT_0 + ((value >> --bit_count) & 1);
  } while (bit_count != 0);
}


static inline void
rc_flush(lzma_range_encoder *rc)
{
  for (size_t i = 0; i < 5; ++i)
    rc->symbols[rc->count++] = RC_FLUSH;
}


static inline bool
rc_shift_low(lzma_range_encoder *rc,
    uint8_t *out, size_t *out_pos, size_t out_size)
{
  if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
      || (uint32_t)(rc->low >> 32) != 0) {
    do {
      if (*out_pos == out_size)
        return true;

      out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
      ++*out_pos;
      ++rc->out_total;
      rc->cache = 0xFF;

    } while (--rc->cache_size != 0);

    rc->cache = (rc->low >> 24) & 0xFF;
  }

  ++rc->cache_size;
  rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;

  return false;
}


// NOTE: The last two arguments are uint64_t instead of size_t because in
// the dummy version these refer to the size of the whole range-encoded
// output stream, not just to the currently available output buffer space.
static inline bool
rc_shift_low_dummy(uint64_t *low, uint64_t *cache_size, uint8_t *cache,
    uint64_t *out_pos, uint64_t out_size)
{
  if ((uint32_t)(*low) < (uint32_t)(0xFF000000)
      || (uint32_t)(*low >> 32) != 0) {
    do {
      if (*out_pos == out_size)
        return true;

      ++*out_pos;
      *cache = 0xFF;

    } while (--*cache_size != 0);

    *cache = (*low >> 24) & 0xFF;
  }

  ++*cache_size;
  *low = (*low & 0x00FFFFFF) << RC_SHIFT_BITS;

  return false;
}


static inline bool
rc_encode(lzma_range_encoder *rc,
    uint8_t *out, size_t *out_pos, size_t out_size)
{
  assert(rc->count <= RC_SYMBOLS_MAX);

  while (rc->pos < rc->count) {
    // Normalize
    if (rc->range < RC_TOP_VALUE) {
      if (rc_shift_low(rc, out, out_pos, out_size))
        return true;

      rc->range <<= RC_SHIFT_BITS;
    }

    // Encode a bit
    switch (rc->symbols[rc->pos]) {
    case RC_BIT_0: {
      probability prob = *rc->probs[rc->pos];
      rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
          * prob;
      prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
      *rc->probs[rc->pos] = prob;
      break;
    }

    case RC_BIT_1: {
      probability prob = *rc->probs[rc->pos];
      const uint32_t bound = prob * (rc->range
          >> RC_BIT_MODEL_TOTAL_BITS);
      rc->low += bound;
      rc->range -= bound;
      prob -= prob >> RC_MOVE_BITS;
      *rc->probs[rc->pos] = prob;
      break;
    }

    case RC_DIRECT_0:
      rc->range >>= 1;
      break;

    case RC_DIRECT_1:
      rc->range >>= 1;
      rc->low += rc->range;
      break;

    case RC_FLUSH:
      // Prevent further normalizations.
      rc->range = UINT32_MAX;

      // Flush the last five bytes (see rc_flush()).
      do {
        if (rc_shift_low(rc, out, out_pos, out_size))
          return true;
      } while (++rc->pos < rc->count);

      // Reset the range encoder so we are ready to continue
      // encoding if we weren't finishing the stream.
      rc_reset(rc);
      return false;

    default:
      assert(0);
      break;
    }

    ++rc->pos;
  }

  rc->count = 0;
  rc->pos = 0;

  return false;
}


static inline bool
rc_encode_dummy(const lzma_range_encoder *rc, uint64_t out_limit)
{
  assert(rc->count <= RC_SYMBOLS_MAX);

  uint64_t low = rc->low;
  uint64_t cache_size = rc->cache_size;
  uint32_t range = rc->range;
  uint8_t cache = rc->cache;
  uint64_t out_pos = rc->out_total;

  size_t pos = rc->pos;

  while (true) {
    // Normalize
    if (range < RC_TOP_VALUE) {
      if (rc_shift_low_dummy(&low, &cache_size, &cache,
          &out_pos, out_limit))
        return true;

      range <<= RC_SHIFT_BITS;
    }

    // This check is here because the normalization above must
    // be done before flushing the last bytes.
    if (pos == rc->count)
      break;

    // Encode a bit
    switch (rc->symbols[pos]) {
    case RC_BIT_0: {
      probability prob = *rc->probs[pos];
      range = (range >> RC_BIT_MODEL_TOTAL_BITS)
          * prob;
      break;
    }

    case RC_BIT_1: {
      probability prob = *rc->probs[pos];
      const uint32_t bound = prob * (range
          >> RC_BIT_MODEL_TOTAL_BITS);
      low += bound;
      range -= bound;
      break;
    }

    case RC_DIRECT_0:
      range >>= 1;
      break;

    case RC_DIRECT_1:
      range >>= 1;
      low += range;
      break;

    case RC_FLUSH:
    default:
      assert(0);
      break;
    }

    ++pos;
  }

  // Flush the last bytes. This isn't in rc->symbols[] so we do
  // it after the above loop to take into account the size of
  // the flushing that will be done at the end of the stream.
  for (pos = 0; pos < 5; ++pos) {
    if (rc_shift_low_dummy(&low, &cache_size,
        &cache, &out_pos, out_limit))
      return true;
  }

  return false;
}


static inline uint64_t
rc_pending(const lzma_range_encoder *rc)
{
  return rc->cache_size + 5 - 1;
}

#endif

Coverage Report

Created: 2026-03-12 06:35

Line	Count	Source
1		// SPDX-License-Identifier: 0BSD
2
3		///////////////////////////////////////////////////////////////////////////////
4		//
5		/// \file range_encoder.h
6		/// \brief Range Encoder
7		///
8		// Authors: Igor Pavlov
9		// Lasse Collin
10		//
11		///////////////////////////////////////////////////////////////////////////////
12
13		#ifndef LZMA_RANGE_ENCODER_H
14		#define LZMA_RANGE_ENCODER_H
15
16		#include "range_common.h"
17		#include "price.h"
18
19
20		/// Maximum number of symbols that can be put pending into lzma_range_encoder
21		/// structure between calls to lzma_rc_encode(). For LZMA, 48+5 is enough
22		/// (match with big distance and length followed by range encoder flush).
23		#define RC_SYMBOLS_MAX 53
24
25
26		typedef struct {
27		uint64_t low;
28		uint64_t cache_size;
29		uint32_t range;
30		uint8_t cache;
31
32		/// Number of bytes written out by rc_encode() -> rc_shift_low()
33		uint64_t out_total;
34
35		/// Number of symbols in the tables
36		size_t count;
37
38		/// rc_encode()'s position in the tables
39		size_t pos;
40
41		/// Symbols to encode
42		enum {
43		RC_BIT_0,
44		RC_BIT_1,
45		RC_DIRECT_0,
46		RC_DIRECT_1,
47		RC_FLUSH,
48		} symbols[RC_SYMBOLS_MAX];
49
50		/// Probabilities associated with RC_BIT_0 or RC_BIT_1
51		probability *probs[RC_SYMBOLS_MAX];
52
53		} lzma_range_encoder;
54
55
56		static inline void
57		rc_reset(lzma_range_encoder *rc)
58	0	{
59	0	rc->low = 0;
60	0	rc->cache_size = 1;
61	0	rc->range = UINT32_MAX;
62	0	rc->cache = 0;
63	0	rc->out_total = 0;
64	0	rc->count = 0;
65	0	rc->pos = 0;
66	0	} Unexecuted instantiation: lzma_encoder.c:rc_reset Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_reset Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_reset Unexecuted instantiation: price_table.c:rc_reset
67
68
69		static inline void
70		rc_forget(lzma_range_encoder *rc)
71	0	{
72		// This must not be called when rc_encode() is partially done.
73	0	assert(rc->pos == 0);
74	0	rc->count = 0;
75	0	} Unexecuted instantiation: lzma_encoder.c:rc_forget Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_forget Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_forget Unexecuted instantiation: price_table.c:rc_forget
76
77
78		static inline void
79		rc_bit(lzma_range_encoder rc, probability prob, uint32_t bit)
80	0	{
81	0	rc->symbols[rc->count] = bit;
82	0	rc->probs[rc->count] = prob;
83	0	++rc->count;
84	0	} Unexecuted instantiation: lzma_encoder.c:rc_bit Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_bit Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_bit Unexecuted instantiation: price_table.c:rc_bit
85
86
87		static inline void
88		rc_bittree(lzma_range_encoder rc, probability probs,
89		uint32_t bit_count, uint32_t symbol)
90	0	{
91	0	uint32_t model_index = 1;
92
93	0	do {
94	0	const uint32_t bit = (symbol >> --bit_count) & 1;
95	0	rc_bit(rc, &probs[model_index], bit);
96	0	model_index = (model_index << 1) + bit;
97	0	} while (bit_count != 0);
98	0	} Unexecuted instantiation: lzma_encoder.c:rc_bittree Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_bittree Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_bittree Unexecuted instantiation: price_table.c:rc_bittree
99
100
101		static inline void
102		rc_bittree_reverse(lzma_range_encoder rc, probability probs,
103		uint32_t bit_count, uint32_t symbol)
104	0	{
105	0	uint32_t model_index = 1;
106
107	0	do {
108	0	const uint32_t bit = symbol & 1;
109	0	symbol >>= 1;
110	0	rc_bit(rc, &probs[model_index], bit);
111	0	model_index = (model_index << 1) + bit;
112	0	} while (--bit_count != 0);
113	0	} Unexecuted instantiation: lzma_encoder.c:rc_bittree_reverse Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_bittree_reverse Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_bittree_reverse Unexecuted instantiation: price_table.c:rc_bittree_reverse
114
115
116		static inline void
117		rc_direct(lzma_range_encoder *rc,
118		uint32_t value, uint32_t bit_count)
119	0	{
120	0	do {
121	0	rc->symbols[rc->count++]
122	0	= RC_DIRECT_0 + ((value >> --bit_count) & 1);
123	0	} while (bit_count != 0);
124	0	} Unexecuted instantiation: lzma_encoder.c:rc_direct Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_direct Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_direct Unexecuted instantiation: price_table.c:rc_direct
125
126
127		static inline void
128		rc_flush(lzma_range_encoder *rc)
129	0	{
130	0	for (size_t i = 0; i < 5; ++i)
131	0	rc->symbols[rc->count++] = RC_FLUSH;
132	0	} Unexecuted instantiation: lzma_encoder.c:rc_flush Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_flush Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_flush Unexecuted instantiation: price_table.c:rc_flush
133
134
135		static inline bool
136		rc_shift_low(lzma_range_encoder *rc,
137		uint8_t out, size_t out_pos, size_t out_size)
138	0	{
139	0	if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
140	0	\|\| (uint32_t)(rc->low >> 32) != 0) {
141	0	do {
142	0	if (*out_pos == out_size)
143	0	return true;
144
145	0	out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
146	0	++*out_pos;
147	0	++rc->out_total;
148	0	rc->cache = 0xFF;
149
150	0	} while (--rc->cache_size != 0);
151
152	0	rc->cache = (rc->low >> 24) & 0xFF;
153	0	}
154
155	0	++rc->cache_size;
156	0	rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
157
158	0	return false;
159	0	} Unexecuted instantiation: lzma_encoder.c:rc_shift_low Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_shift_low Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_shift_low Unexecuted instantiation: price_table.c:rc_shift_low
160
161
162		// NOTE: The last two arguments are uint64_t instead of size_t because in
163		// the dummy version these refer to the size of the whole range-encoded
164		// output stream, not just to the currently available output buffer space.
165		static inline bool
166		rc_shift_low_dummy(uint64_t low, uint64_t cache_size, uint8_t *cache,
167		uint64_t *out_pos, uint64_t out_size)
168	0	{
169	0	if ((uint32_t)(*low) < (uint32_t)(0xFF000000)
170	0	\|\| (uint32_t)(*low >> 32) != 0) {
171	0	do {
172	0	if (*out_pos == out_size)
173	0	return true;
174
175	0	++*out_pos;
176	0	*cache = 0xFF;
177
178	0	} while (--*cache_size != 0);
179
180	0	cache = (low >> 24) & 0xFF;
181	0	}
182
183	0	++*cache_size;
184	0	low = (low & 0x00FFFFFF) << RC_SHIFT_BITS;
185
186	0	return false;
187	0	} Unexecuted instantiation: lzma_encoder.c:rc_shift_low_dummy Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_shift_low_dummy Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_shift_low_dummy Unexecuted instantiation: price_table.c:rc_shift_low_dummy
188
189
190		static inline bool
191		rc_encode(lzma_range_encoder *rc,
192		uint8_t out, size_t out_pos, size_t out_size)
193	0	{
194	0	assert(rc->count <= RC_SYMBOLS_MAX);
195
196	0	while (rc->pos < rc->count) {
197		// Normalize
198	0	if (rc->range < RC_TOP_VALUE) {
199	0	if (rc_shift_low(rc, out, out_pos, out_size))
200	0	return true;
201
202	0	rc->range <<= RC_SHIFT_BITS;
203	0	}
204
205		// Encode a bit
206	0	switch (rc->symbols[rc->pos]) {
207	0	case RC_BIT_0: {
208	0	probability prob = *rc->probs[rc->pos];
209	0	rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
210	0	* prob;
211	0	prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
212	0	*rc->probs[rc->pos] = prob;
213	0	break;
214	0	}
215
216	0	case RC_BIT_1: {
217	0	probability prob = *rc->probs[rc->pos];
218	0	const uint32_t bound = prob * (rc->range
219	0	>> RC_BIT_MODEL_TOTAL_BITS);
220	0	rc->low += bound;
221	0	rc->range -= bound;
222	0	prob -= prob >> RC_MOVE_BITS;
223	0	*rc->probs[rc->pos] = prob;
224	0	break;
225	0	}
226
227	0	case RC_DIRECT_0:
228	0	rc->range >>= 1;
229	0	break;
230
231	0	case RC_DIRECT_1:
232	0	rc->range >>= 1;
233	0	rc->low += rc->range;
234	0	break;
235
236	0	case RC_FLUSH:
237		// Prevent further normalizations.
238	0	rc->range = UINT32_MAX;
239
240		// Flush the last five bytes (see rc_flush()).
241	0	do {
242	0	if (rc_shift_low(rc, out, out_pos, out_size))
243	0	return true;
244	0	} while (++rc->pos < rc->count);
245
246		// Reset the range encoder so we are ready to continue
247		// encoding if we weren't finishing the stream.
248	0	rc_reset(rc);
249	0	return false;
250
251	0	default:
252	0	assert(0);
253	0	break;
254	0	}
255
256	0	++rc->pos;
257	0	}
258
259	0	rc->count = 0;
260	0	rc->pos = 0;
261
262	0	return false;
263	0	} Unexecuted instantiation: lzma_encoder.c:rc_encode Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_encode Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_encode Unexecuted instantiation: price_table.c:rc_encode
264
265
266		static inline bool
267		rc_encode_dummy(const lzma_range_encoder *rc, uint64_t out_limit)
268	0	{
269	0	assert(rc->count <= RC_SYMBOLS_MAX);
270
271	0	uint64_t low = rc->low;
272	0	uint64_t cache_size = rc->cache_size;
273	0	uint32_t range = rc->range;
274	0	uint8_t cache = rc->cache;
275	0	uint64_t out_pos = rc->out_total;
276
277	0	size_t pos = rc->pos;
278
279	0	while (true) {
280		// Normalize
281	0	if (range < RC_TOP_VALUE) {
282	0	if (rc_shift_low_dummy(&low, &cache_size, &cache,
283	0	&out_pos, out_limit))
284	0	return true;
285
286	0	range <<= RC_SHIFT_BITS;
287	0	}
288
289		// This check is here because the normalization above must
290		// be done before flushing the last bytes.
291	0	if (pos == rc->count)
292	0	break;
293
294		// Encode a bit
295	0	switch (rc->symbols[pos]) {
296	0	case RC_BIT_0: {
297	0	probability prob = *rc->probs[pos];
298	0	range = (range >> RC_BIT_MODEL_TOTAL_BITS)
299	0	* prob;
300	0	break;
301	0	}
302
303	0	case RC_BIT_1: {
304	0	probability prob = *rc->probs[pos];
305	0	const uint32_t bound = prob * (range
306	0	>> RC_BIT_MODEL_TOTAL_BITS);
307	0	low += bound;
308	0	range -= bound;
309	0	break;
310	0	}
311
312	0	case RC_DIRECT_0:
313	0	range >>= 1;
314	0	break;
315
316	0	case RC_DIRECT_1:
317	0	range >>= 1;
318	0	low += range;
319	0	break;
320
321	0	case RC_FLUSH:
322	0	default:
323	0	assert(0);
324	0	break;
325	0	}
326
327	0	++pos;
328	0	}
329
330		// Flush the last bytes. This isn't in rc->symbols[] so we do
331		// it after the above loop to take into account the size of
332		// the flushing that will be done at the end of the stream.
333	0	for (pos = 0; pos < 5; ++pos) {
334	0	if (rc_shift_low_dummy(&low, &cache_size,
335	0	&cache, &out_pos, out_limit))
336	0	return true;
337	0	}
338
339	0	return false;
340	0	} Unexecuted instantiation: lzma_encoder.c:rc_encode_dummy Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_encode_dummy Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_encode_dummy Unexecuted instantiation: price_table.c:rc_encode_dummy
341
342
343		static inline uint64_t
344		rc_pending(const lzma_range_encoder *rc)
345	0	{
346	0	return rc->cache_size + 5 - 1;
347	0	} Unexecuted instantiation: lzma_encoder.c:rc_pending Unexecuted instantiation: lzma_encoder_optimum_fast.c:rc_pending Unexecuted instantiation: lzma_encoder_optimum_normal.c:rc_pending Unexecuted instantiation: price_table.c:rc_pending
348
349		#endif