1 // SPDX-License-Identifier: 0BSD
2
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file range_decoder.h
6 /// \brief Range Decoder
7 ///
8 // Authors: Igor Pavlov
9 // Lasse Collin
10 //
11 ///////////////////////////////////////////////////////////////////////////////
12
13 #ifndef LZMA_RANGE_DECODER_H
14 #define LZMA_RANGE_DECODER_H
15
16 #include "range_common.h"
17
18
19 // Choose the range decoder variants to use using a bitmask.
20 // If no bits are set, only the basic version is used.
21 // If more than one version is selected for the same feature,
22 // the last one on the list below is used.
23 //
24 // Bitwise-or of the following enable branchless C versions:
25 // 0x01 normal bittrees
26 // 0x02 fixed-sized reverse bittrees
27 // 0x04 variable-sized reverse bittrees (not faster)
28 // 0x08 matched literal (not faster)
29 //
30 // GCC & Clang compatible x86-64 inline assembly:
31 // 0x010 normal bittrees
32 // 0x020 fixed-sized reverse bittrees
33 // 0x040 variable-sized reverse bittrees
34 // 0x080 matched literal
35 // 0x100 direct bits
36 //
37 // The default can be overridden at build time by defining
38 // LZMA_RANGE_DECODER_CONFIG to the desired mask.
39 //
40 // 2024-02-22: Feedback from benchmarks:
41 // - Brancless C (0x003) can be better than basic on x86-64 but often it's
42 // slightly worse on other archs. Since asm is much better on x86-64,
43 // branchless C is not used at all.
44 // - With x86-64 asm, there are slight differences between GCC and Clang
45 // and different processors. Overall 0x1F0 seems to be the best choice.
46 #ifndef LZMA_RANGE_DECODER_CONFIG
47 # if defined(__x86_64__) && !defined(__ILP32__) \
48 && !defined(__arm64ec__) && !defined(_M_ARM64EC) \
49 && !defined(__NVCOMPILER) \
50 && (defined(__GNUC__) || defined(__clang__))
51 # define LZMA_RANGE_DECODER_CONFIG 0x1F0
52 # else
53 # define LZMA_RANGE_DECODER_CONFIG 0
54 # endif
55 #endif
56
57
58 // Negative RC_BIT_MODEL_TOTAL but the lowest RC_MOVE_BITS are flipped.
59 // This is useful for updating probability variables in branchless decoding:
60 //
61 // uint32_t decoded_bit = ...;
62 // probability tmp = RC_BIT_MODEL_OFFSET;
63 // tmp &= decoded_bit - 1;
64 // prob -= (prob + tmp) >> RC_MOVE_BITS;
65 #define RC_BIT_MODEL_OFFSET \
66 ((UINT32_C(1) << RC_MOVE_BITS) - 1 - RC_BIT_MODEL_TOTAL)
67
68
69 typedef struct {
70 uint32_t range;
71 uint32_t code;
72 uint32_t init_bytes_left;
73 } lzma_range_decoder;
74
75
76 /// Reads the first five bytes to initialize the range decoder.
77 static inline lzma_ret
rc_read_init(lzma_range_decoder * rc,const uint8_t * restrict in,size_t * restrict in_pos,size_t in_size)78 rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
79 size_t *restrict in_pos, size_t in_size)
80 {
81 while (rc->init_bytes_left > 0) {
82 if (*in_pos == in_size)
83 return LZMA_OK;
84
85 // The first byte is always 0x00. It could have been omitted
86 // in LZMA2 but it wasn't, so one byte is wasted in every
87 // LZMA2 chunk.
88 if (rc->init_bytes_left == 5 && in[*in_pos] != 0x00)
89 return LZMA_DATA_ERROR;
90
91 rc->code = (rc->code << 8) | in[*in_pos];
92 ++*in_pos;
93 --rc->init_bytes_left;
94 }
95
96 return LZMA_STREAM_END;
97 }
98
99
100 /// Makes local copies of range decoder and *in_pos variables. Doing this
101 /// improves speed significantly. The range decoder macros expect also
102 /// variables 'in' and 'in_size' to be defined.
103 #define rc_to_local(range_decoder, in_pos, fast_mode_in_required) \
104 lzma_range_decoder rc = range_decoder; \
105 const uint8_t *rc_in_ptr = in + (in_pos); \
106 const uint8_t *rc_in_end = in + in_size; \
107 const uint8_t *rc_in_fast_end \
108 = (rc_in_end - rc_in_ptr) <= (fast_mode_in_required) \
109 ? rc_in_ptr \
110 : rc_in_end - (fast_mode_in_required); \
111 (void)rc_in_fast_end; /* Silence a warning with HAVE_SMALL. */ \
112 uint32_t rc_bound
113
114
115 /// Evaluates to true if there is enough input remaining to use fast mode.
116 #define rc_is_fast_allowed() (rc_in_ptr < rc_in_fast_end)
117
118
119 /// Stores the local copes back to the range decoder structure.
120 #define rc_from_local(range_decoder, in_pos) \
121 do { \
122 range_decoder = rc; \
123 in_pos = (size_t)(rc_in_ptr - in); \
124 } while (0)
125
126
127 /// Resets the range decoder structure.
128 #define rc_reset(range_decoder) \
129 do { \
130 (range_decoder).range = UINT32_MAX; \
131 (range_decoder).code = 0; \
132 (range_decoder).init_bytes_left = 5; \
133 } while (0)
134
135
136 /// When decoding has been properly finished, rc.code is always zero unless
137 /// the input stream is corrupt. So checking this can catch some corrupt
138 /// files especially if they don't have any other integrity check.
139 #define rc_is_finished(range_decoder) \
140 ((range_decoder).code == 0)
141
142
143 // Read the next input byte if needed.
144 #define rc_normalize() \
145 do { \
146 if (rc.range < RC_TOP_VALUE) { \
147 rc.range <<= RC_SHIFT_BITS; \
148 rc.code = (rc.code << RC_SHIFT_BITS) | *rc_in_ptr++; \
149 } \
150 } while (0)
151
152
153 /// If more input is needed but there is
154 /// no more input available, "goto out" is used to jump out of the main
155 /// decoder loop. The "_safe" macros are used in the Resumable decoder
156 /// mode in order to save the sequence to continue decoding from that
157 /// point later.
158 #define rc_normalize_safe(seq) \
159 do { \
160 if (rc.range < RC_TOP_VALUE) { \
161 if (rc_in_ptr == rc_in_end) { \
162 coder->sequence = seq; \
163 goto out; \
164 } \
165 rc.range <<= RC_SHIFT_BITS; \
166 rc.code = (rc.code << RC_SHIFT_BITS) | *rc_in_ptr++; \
167 } \
168 } while (0)
169
170
171 /// Start decoding a bit. This must be used together with rc_update_0()
172 /// and rc_update_1():
173 ///
174 /// rc_if_0(prob) {
175 /// rc_update_0(prob);
176 /// // Do something
177 /// } else {
178 /// rc_update_1(prob);
179 /// // Do something else
180 /// }
181 ///
182 #define rc_if_0(prob) \
183 rc_normalize(); \
184 rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
185 if (rc.code < rc_bound)
186
187
188 #define rc_if_0_safe(prob, seq) \
189 rc_normalize_safe(seq); \
190 rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
191 if (rc.code < rc_bound)
192
193
194 /// Update the range decoder state and the used probability variable to
195 /// match a decoded bit of 0.
196 ///
197 /// The x86-64 assembly uses the commented method but it seems that,
198 /// at least on x86-64, the first version is slightly faster as C code.
199 #define rc_update_0(prob) \
200 do { \
201 rc.range = rc_bound; \
202 prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
203 /* prob -= ((prob) + RC_BIT_MODEL_OFFSET) >> RC_MOVE_BITS; */ \
204 } while (0)
205
206
207 /// Update the range decoder state and the used probability variable to
208 /// match a decoded bit of 1.
209 #define rc_update_1(prob) \
210 do { \
211 rc.range -= rc_bound; \
212 rc.code -= rc_bound; \
213 prob -= (prob) >> RC_MOVE_BITS; \
214 } while (0)
215
216
217 /// Decodes one bit and runs action0 or action1 depending on the decoded bit.
218 /// This macro is used as the last step in bittree reverse decoders since
219 /// those don't use "symbol" for anything else than indexing the probability
220 /// arrays.
221 #define rc_bit_last(prob, action0, action1) \
222 do { \
223 rc_if_0(prob) { \
224 rc_update_0(prob); \
225 action0; \
226 } else { \
227 rc_update_1(prob); \
228 action1; \
229 } \
230 } while (0)
231
232
233 #define rc_bit_last_safe(prob, action0, action1, seq) \
234 do { \
235 rc_if_0_safe(prob, seq) { \
236 rc_update_0(prob); \
237 action0; \
238 } else { \
239 rc_update_1(prob); \
240 action1; \
241 } \
242 } while (0)
243
244
245 /// Decodes one bit, updates "symbol", and runs action0 or action1 depending
246 /// on the decoded bit.
247 #define rc_bit(prob, action0, action1) \
248 rc_bit_last(prob, \
249 symbol <<= 1; action0, \
250 symbol = (symbol << 1) + 1; action1)
251
252
253 #define rc_bit_safe(prob, action0, action1, seq) \
254 rc_bit_last_safe(prob, \
255 symbol <<= 1; action0, \
256 symbol = (symbol << 1) + 1; action1, \
257 seq)
258
259 // Unroll fixed-sized bittree decoding.
260 //
261 // A compile-time constant in final_add can be used to get rid of the high bit
262 // from symbol that is used for the array indexing (1U << bittree_bits).
263 // final_add may also be used to add offset to the result (LZMA length
264 // decoder does that).
265 //
266 // The reason to have final_add here is that in the asm code the addition
267 // can be done for free: in x86-64 there is SBB instruction with -1 as
268 // the immediate value, and final_add is combined with that value.
269 #define rc_bittree_bit(prob) \
270 rc_bit(prob, , )
271
272 #define rc_bittree3(probs, final_add) \
273 do { \
274 symbol = 1; \
275 rc_bittree_bit(probs[symbol]); \
276 rc_bittree_bit(probs[symbol]); \
277 rc_bittree_bit(probs[symbol]); \
278 symbol += (uint32_t)(final_add); \
279 } while (0)
280
281 #define rc_bittree6(probs, final_add) \
282 do { \
283 symbol = 1; \
284 rc_bittree_bit(probs[symbol]); \
285 rc_bittree_bit(probs[symbol]); \
286 rc_bittree_bit(probs[symbol]); \
287 rc_bittree_bit(probs[symbol]); \
288 rc_bittree_bit(probs[symbol]); \
289 rc_bittree_bit(probs[symbol]); \
290 symbol += (uint32_t)(final_add); \
291 } while (0)
292
293 #define rc_bittree8(probs, final_add) \
294 do { \
295 symbol = 1; \
296 rc_bittree_bit(probs[symbol]); \
297 rc_bittree_bit(probs[symbol]); \
298 rc_bittree_bit(probs[symbol]); \
299 rc_bittree_bit(probs[symbol]); \
300 rc_bittree_bit(probs[symbol]); \
301 rc_bittree_bit(probs[symbol]); \
302 rc_bittree_bit(probs[symbol]); \
303 rc_bittree_bit(probs[symbol]); \
304 symbol += (uint32_t)(final_add); \
305 } while (0)
306
307
308 // Fixed-sized reverse bittree
309 #define rc_bittree_rev4(probs) \
310 do { \
311 symbol = 0; \
312 rc_bit_last(probs[symbol + 1], , symbol += 1); \
313 rc_bit_last(probs[symbol + 2], , symbol += 2); \
314 rc_bit_last(probs[symbol + 4], , symbol += 4); \
315 rc_bit_last(probs[symbol + 8], , symbol += 8); \
316 } while (0)
317
318
319 // Decode one bit from variable-sized reverse bittree. The loop is done
320 // in the code that uses this macro. This could be changed if the assembly
321 // version benefited from having the loop done in assembly but it didn't
322 // seem so in early 2024.
323 //
324 // Also, if the loop was done here, the loop counter would likely be local
325 // to the macro so that it wouldn't modify yet another input variable.
326 // If a _safe version of a macro with a loop was done then a modifiable
327 // input variable couldn't be avoided though.
328 #define rc_bit_add_if_1(probs, dest, value_to_add_if_1) \
329 rc_bit(probs[symbol], \
330 , \
331 dest += value_to_add_if_1)
332
333
334 // Matched literal
335 #define decode_with_match_bit \
336 t_match_byte <<= 1; \
337 t_match_bit = t_match_byte & t_offset; \
338 t_subcoder_index = t_offset + t_match_bit + symbol; \
339 rc_bit(probs[t_subcoder_index], \
340 t_offset &= ~t_match_bit, \
341 t_offset &= t_match_bit)
342
343 #define rc_matched_literal(probs_base_var, match_byte) \
344 do { \
345 uint32_t t_match_byte = (match_byte); \
346 uint32_t t_match_bit; \
347 uint32_t t_subcoder_index; \
348 uint32_t t_offset = 0x100; \
349 symbol = 1; \
350 decode_with_match_bit; \
351 decode_with_match_bit; \
352 decode_with_match_bit; \
353 decode_with_match_bit; \
354 decode_with_match_bit; \
355 decode_with_match_bit; \
356 decode_with_match_bit; \
357 decode_with_match_bit; \
358 } while (0)
359
360
361 /// Decode a bit without using a probability.
362 //
363 // NOTE: GCC 13 and Clang/LLVM 16 can, at least on x86-64, optimize the bound
364 // calculation to use an arithmetic right shift so there's no need to provide
365 // the alternative code which, according to C99/C11/C23 6.3.1.3-p3 isn't
366 // perfectly portable: rc_bound = (uint32_t)((int32_t)rc.code >> 31);
367 #define rc_direct(dest, count_var) \
368 do { \
369 dest = (dest << 1) + 1; \
370 rc_normalize(); \
371 rc.range >>= 1; \
372 rc.code -= rc.range; \
373 rc_bound = UINT32_C(0) - (rc.code >> 31); \
374 dest += rc_bound; \
375 rc.code += rc.range & rc_bound; \
376 } while (--count_var > 0)
377
378
379
380 #define rc_direct_safe(dest, count_var, seq) \
381 do { \
382 rc_normalize_safe(seq); \
383 rc.range >>= 1; \
384 rc.code -= rc.range; \
385 rc_bound = UINT32_C(0) - (rc.code >> 31); \
386 rc.code += rc.range & rc_bound; \
387 dest = (dest << 1) + (rc_bound + 1); \
388 } while (--count_var > 0)
389
390
391 //////////////////
392 // Branchless C //
393 //////////////////
394
395 /// Decode a bit using a branchless method. This reduces the number of
396 /// mispredicted branches and thus can improve speed.
397 #define rc_c_bit(prob, action_bit, action_neg) \
398 do { \
399 probability *p = &(prob); \
400 rc_normalize(); \
401 rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * *p; \
402 uint32_t rc_mask = rc.code >= rc_bound; /* rc_mask = decoded bit */ \
403 action_bit; /* action when rc_mask is 0 or 1 */ \
404 /* rc_mask becomes 0 if bit is 0 and 0xFFFFFFFF if bit is 1: */ \
405 rc_mask = 0U - rc_mask; \
406 rc.range &= rc_mask; /* If bit 0: set rc.range = 0 */ \
407 rc_bound ^= rc_mask; \
408 rc_bound -= rc_mask; /* If bit 1: rc_bound = 0U - rc_bound */ \
409 rc.range += rc_bound; \
410 rc_bound &= rc_mask; \
411 rc.code += rc_bound; \
412 action_neg; /* action when rc_mask is 0 or 0xFFFFFFFF */ \
413 rc_mask = ~rc_mask; /* If bit 0: all bits are set in rc_mask */ \
414 rc_mask &= RC_BIT_MODEL_OFFSET; \
415 *p -= (*p + rc_mask) >> RC_MOVE_BITS; \
416 } while (0)
417
418
419 // Testing on x86-64 give an impression that only the normal bittrees and
420 // the fixed-sized reverse bittrees are worth the branchless C code.
421 // It should be tested on other archs for which there isn't assembly code
422 // in this file.
423
424 // Using addition in "(symbol << 1) + rc_mask" allows use of x86 LEA
425 // or RISC-V SH1ADD instructions. Compilers might infer it from
426 // "(symbol << 1) | rc_mask" too if they see that mask is 0 or 1 but
427 // the use of addition doesn't require such analysis from compilers.
428 #if LZMA_RANGE_DECODER_CONFIG & 0x01
429 #undef rc_bittree_bit
430 #define rc_bittree_bit(prob) \
431 rc_c_bit(prob, \
432 symbol = (symbol << 1) + rc_mask, \
433 )
434 #endif // LZMA_RANGE_DECODER_CONFIG & 0x01
435
436 #if LZMA_RANGE_DECODER_CONFIG & 0x02
437 #undef rc_bittree_rev4
438 #define rc_bittree_rev4(probs) \
439 do { \
440 symbol = 0; \
441 rc_c_bit(probs[symbol + 1], symbol += rc_mask, ); \
442 rc_c_bit(probs[symbol + 2], symbol += rc_mask << 1, ); \
443 rc_c_bit(probs[symbol + 4], symbol += rc_mask << 2, ); \
444 rc_c_bit(probs[symbol + 8], symbol += rc_mask << 3, ); \
445 } while (0)
446 #endif // LZMA_RANGE_DECODER_CONFIG & 0x02
447
448 #if LZMA_RANGE_DECODER_CONFIG & 0x04
449 #undef rc_bit_add_if_1
450 #define rc_bit_add_if_1(probs, dest, value_to_add_if_1) \
451 rc_c_bit(probs[symbol], \
452 symbol = (symbol << 1) + rc_mask, \
453 dest += (value_to_add_if_1) & rc_mask)
454 #endif // LZMA_RANGE_DECODER_CONFIG & 0x04
455
456
457 #if LZMA_RANGE_DECODER_CONFIG & 0x08
458 #undef decode_with_match_bit
459 #define decode_with_match_bit \
460 t_match_byte <<= 1; \
461 t_match_bit = t_match_byte & t_offset; \
462 t_subcoder_index = t_offset + t_match_bit + symbol; \
463 rc_c_bit(probs[t_subcoder_index], \
464 symbol = (symbol << 1) + rc_mask, \
465 t_offset &= ~t_match_bit ^ rc_mask)
466 #endif // LZMA_RANGE_DECODER_CONFIG & 0x08
467
468
469 ////////////
470 // x86-64 //
471 ////////////
472
473 #if LZMA_RANGE_DECODER_CONFIG & 0x1F0
474
475 // rc_asm_y and rc_asm_n are used as arguments to macros to control which
476 // strings to include or omit.
477 #define rc_asm_y(str) str
478 #define rc_asm_n(str)
479
480 // There are a few possible variations for normalization.
481 // This is the smallest variant which is also used by LZMA SDK.
482 //
483 // - This has partial register write (the MOV from (%[in_ptr])).
484 //
485 // - INC saves one byte in code size over ADD. False dependency on
486 // partial flags from INC shouldn't become a problem on any processor
487 // because the instructions after normalization don't read the flags
488 // until SUB which sets all flags.
489 //
490 #define rc_asm_normalize \
491 "cmp %[top_value], %[range]\n\t" \
492 "jae 1f\n\t" \
493 "shl %[shift_bits], %[code]\n\t" \
494 "mov (%[in_ptr]), %b[code]\n\t" \
495 "shl %[shift_bits], %[range]\n\t" \
496 "inc %[in_ptr]\n" \
497 "1:\n"
498
499 // rc_asm_calc(prob) is roughly equivalent to the C version of rc_if_0(prob)...
500 //
501 // rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob);
502 // if (rc.code < rc_bound)
503 //
504 // ...but the bound is stored in "range":
505 //
506 // t0 = range;
507 // range = (range >> RC_BIT_MODEL_TOTAL_BITS) * (prob);
508 // t0 -= range;
509 // t1 = code;
510 // code -= range;
511 //
512 // The carry flag (CF) from the last subtraction holds the negation of
513 // the decoded bit (if CF==0 then the decoded bit is 1).
514 // The values in t0 and t1 are needed for rc_update_0(prob) and
515 // rc_update_1(prob). If the bit is 0, rc_update_0(prob)...
516 //
517 // rc.range = rc_bound;
518 //
519 // ...has already been done but the "code -= range" has to be reverted using
520 // the old value stored in t1. (Also, prob needs to be updated.)
521 //
522 // If the bit is 1, rc_update_1(prob)...
523 //
524 // rc.range -= rc_bound;
525 // rc.code -= rc_bound;
526 //
527 // ...is already done for "code" but the value for "range" needs to be taken
528 // from t0. (Also, prob needs to be updated here as well.)
529 //
530 // The assignments from t0 and t1 can be done in a branchless manner with CMOV
531 // after the instructions from this macro. The CF from SUB tells which moves
532 // are needed.
533 #define rc_asm_calc(prob) \
534 "mov %[range], %[t0]\n\t" \
535 "shr %[bit_model_total_bits], %[range]\n\t" \
536 "imul %[" prob "], %[range]\n\t" \
537 "sub %[range], %[t0]\n\t" \
538 "mov %[code], %[t1]\n\t" \
539 "sub %[range], %[code]\n\t"
540
541 // Also, prob needs to be updated: The update math depends on the decoded bit.
542 // It can be expressed in a few slightly different ways but this is fairly
543 // convenient here:
544 //
545 // prob -= (prob + (bit ? 0 : RC_BIT_MODEL_OFFSET)) >> RC_MOVE_BITS;
546 //
547 // To do it in branchless way when the negation of the decoded bit is in CF,
548 // both "prob" and "prob + RC_BIT_MODEL_OFFSET" are needed. Then the desired
549 // value can be picked with CMOV. The addition can be done using LEA without
550 // affecting CF.
551 //
552 // (This prob update method is a tiny bit different from LZMA SDK 23.01.
553 // In the LZMA SDK a single register is reserved solely for a constant to
554 // be used with CMOV when updating prob. That is fine since there are enough
555 // free registers to do so. The method used here uses one fewer register,
556 // which is valuable with inline assembly.)
557 //
558 // * * *
559 //
560 // In bittree decoding, each (unrolled) loop iteration decodes one bit
561 // and needs one prob variable. To make it faster, the prob variable of
562 // the iteration N+1 is loaded during iteration N. There are two possible
563 // prob variables to choose from for N+1. Both are loaded from memory and
564 // the correct one is chosen with CMOV using the same CF as is used for
565 // other things described above.
566 //
567 // This preloading/prefetching requires an extra register. To avoid
568 // useless moves from "preloaded prob register" to "current prob register",
569 // the macros swap between the two registers for odd and even iterations.
570 //
571 // * * *
572 //
573 // Finally, the decoded bit has to be stored in "symbol". Since the negation
574 // of the bit is in CF, this can be done with SBB: symbol -= CF - 1. That is,
575 // if the decoded bit is 0 (CF==1) the operation is a no-op "symbol -= 0"
576 // and when bit is 1 (CF==0) the operation is "symbol -= 0 - 1" which is
577 // the same as "symbol += 1".
578 //
579 // The instructions for all things are intertwined for a few reasons:
580 // - freeing temporary registers for new use
581 // - not modifying CF too early
582 // - instruction scheduling
583 //
584 // The first and last iterations can cheat a little. For example,
585 // on the first iteration "symbol" is known to start from 1 so it
586 // doesn't need to be read; it can even be immediately initialized
587 // to 2 to prepare for the second iteration of the loop.
588 //
589 // * * *
590 //
591 // a = number of the current prob variable (0 or 1)
592 // b = number of the next prob variable (1 or 0)
593 // *_only = rc_asm_y or _n to include or exclude code marked with them
594 #define rc_asm_bittree(a, b, first_only, middle_only, last_only) \
595 first_only( \
596 "movzwl 2(%[probs_base]), %[prob" #a "]\n\t" \
597 "mov $2, %[symbol]\n\t" \
598 "movzwl 4(%[probs_base]), %[prob" #b "]\n\t" \
599 ) \
600 middle_only( \
601 /* Note the scaling of 4 instead of 2: */ \
602 "movzwl (%[probs_base], %q[symbol], 4), %[prob" #b "]\n\t" \
603 ) \
604 last_only( \
605 "add %[symbol], %[symbol]\n\t" \
606 ) \
607 \
608 rc_asm_normalize \
609 rc_asm_calc("prob" #a) \
610 \
611 "cmovae %[t0], %[range]\n\t" \
612 \
613 first_only( \
614 "movzwl 6(%[probs_base]), %[t0]\n\t" \
615 "cmovae %[t0], %[prob" #b "]\n\t" \
616 ) \
617 middle_only( \
618 "movzwl 2(%[probs_base], %q[symbol], 4), %[t0]\n\t" \
619 "lea (%q[symbol], %q[symbol]), %[symbol]\n\t" \
620 "cmovae %[t0], %[prob" #b "]\n\t" \
621 ) \
622 \
623 "lea %c[bit_model_offset](%q[prob" #a "]), %[t0]\n\t" \
624 "cmovb %[t1], %[code]\n\t" \
625 "mov %[symbol], %[t1]\n\t" \
626 "cmovae %[prob" #a "], %[t0]\n\t" \
627 \
628 first_only( \
629 "sbb $-1, %[symbol]\n\t" \
630 ) \
631 middle_only( \
632 "sbb $-1, %[symbol]\n\t" \
633 ) \
634 last_only( \
635 "sbb %[last_sbb], %[symbol]\n\t" \
636 ) \
637 \
638 "shr %[move_bits], %[t0]\n\t" \
639 "sub %[t0], %[prob" #a "]\n\t" \
640 /* Scaling of 1 instead of 2 because symbol <<= 1. */ \
641 "mov %w[prob" #a "], (%[probs_base], %q[t1], 1)\n\t"
642
643 // NOTE: The order of variables in __asm__ can affect speed and code size.
644 #define rc_asm_bittree_n(probs_base_var, final_add, asm_str) \
645 do { \
646 uint32_t t0; \
647 uint32_t t1; \
648 uint32_t t_prob0; \
649 uint32_t t_prob1; \
650 \
651 __asm__( \
652 asm_str \
653 : \
654 [range] "+&r"(rc.range), \
655 [code] "+&r"(rc.code), \
656 [t0] "=&r"(t0), \
657 [t1] "=&r"(t1), \
658 [prob0] "=&r"(t_prob0), \
659 [prob1] "=&r"(t_prob1), \
660 [symbol] "=&r"(symbol), \
661 [in_ptr] "+&r"(rc_in_ptr) \
662 : \
663 [probs_base] "r"(probs_base_var), \
664 [last_sbb] "n"(-1 - (final_add)), \
665 [top_value] "n"(RC_TOP_VALUE), \
666 [shift_bits] "n"(RC_SHIFT_BITS), \
667 [bit_model_total_bits] "n"(RC_BIT_MODEL_TOTAL_BITS), \
668 [bit_model_offset] "n"(RC_BIT_MODEL_OFFSET), \
669 [move_bits] "n"(RC_MOVE_BITS) \
670 : \
671 "cc", "memory"); \
672 } while (0)
673
674
675 #if LZMA_RANGE_DECODER_CONFIG & 0x010
676 #undef rc_bittree3
677 #define rc_bittree3(probs_base_var, final_add) \
678 rc_asm_bittree_n(probs_base_var, final_add, \
679 rc_asm_bittree(0, 1, rc_asm_y, rc_asm_n, rc_asm_n) \
680 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_y, rc_asm_n) \
681 rc_asm_bittree(0, 1, rc_asm_n, rc_asm_n, rc_asm_y) \
682 )
683
684 #undef rc_bittree6
685 #define rc_bittree6(probs_base_var, final_add) \
686 rc_asm_bittree_n(probs_base_var, final_add, \
687 rc_asm_bittree(0, 1, rc_asm_y, rc_asm_n, rc_asm_n) \
688 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_y, rc_asm_n) \
689 rc_asm_bittree(0, 1, rc_asm_n, rc_asm_y, rc_asm_n) \
690 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_y, rc_asm_n) \
691 rc_asm_bittree(0, 1, rc_asm_n, rc_asm_y, rc_asm_n) \
692 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_n, rc_asm_y) \
693 )
694
695 #undef rc_bittree8
696 #define rc_bittree8(probs_base_var, final_add) \
697 rc_asm_bittree_n(probs_base_var, final_add, \
698 rc_asm_bittree(0, 1, rc_asm_y, rc_asm_n, rc_asm_n) \
699 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_y, rc_asm_n) \
700 rc_asm_bittree(0, 1, rc_asm_n, rc_asm_y, rc_asm_n) \
701 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_y, rc_asm_n) \
702 rc_asm_bittree(0, 1, rc_asm_n, rc_asm_y, rc_asm_n) \
703 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_y, rc_asm_n) \
704 rc_asm_bittree(0, 1, rc_asm_n, rc_asm_y, rc_asm_n) \
705 rc_asm_bittree(1, 0, rc_asm_n, rc_asm_n, rc_asm_y) \
706 )
707 #endif // LZMA_RANGE_DECODER_CONFIG & 0x010
708
709
710 // Fixed-sized reverse bittree
711 //
712 // This uses the indexing that constructs the final value in symbol directly.
713 // add = 1, 2, 4, 8
714 // dcur = -, 4, 8, 16
715 // dnext0 = 4, 8, 16, -
716 // dnext0 = 6, 12, 24, -
717 #define rc_asm_bittree_rev(a, b, add, dcur, dnext0, dnext1, \
718 first_only, middle_only, last_only) \
719 first_only( \
720 "movzwl 2(%[probs_base]), %[prob" #a "]\n\t" \
721 "xor %[symbol], %[symbol]\n\t" \
722 "movzwl 4(%[probs_base]), %[prob" #b "]\n\t" \
723 ) \
724 middle_only( \
725 "movzwl " #dnext0 "(%[probs_base], %q[symbol], 2), " \
726 "%[prob" #b "]\n\t" \
727 ) \
728 \
729 rc_asm_normalize \
730 rc_asm_calc("prob" #a) \
731 \
732 "cmovae %[t0], %[range]\n\t" \
733 \
734 first_only( \
735 "movzwl 6(%[probs_base]), %[t0]\n\t" \
736 "cmovae %[t0], %[prob" #b "]\n\t" \
737 ) \
738 middle_only( \
739 "movzwl " #dnext1 "(%[probs_base], %q[symbol], 2), %[t0]\n\t" \
740 "cmovae %[t0], %[prob" #b "]\n\t" \
741 ) \
742 \
743 "lea " #add "(%q[symbol]), %[t0]\n\t" \
744 "cmovb %[t1], %[code]\n\t" \
745 middle_only( \
746 "mov %[symbol], %[t1]\n\t" \
747 ) \
748 last_only( \
749 "mov %[symbol], %[t1]\n\t" \
750 ) \
751 "cmovae %[t0], %[symbol]\n\t" \
752 "lea %c[bit_model_offset](%q[prob" #a "]), %[t0]\n\t" \
753 "cmovae %[prob" #a "], %[t0]\n\t" \
754 \
755 "shr %[move_bits], %[t0]\n\t" \
756 "sub %[t0], %[prob" #a "]\n\t" \
757 first_only( \
758 "mov %w[prob" #a "], 2(%[probs_base])\n\t" \
759 ) \
760 middle_only( \
761 "mov %w[prob" #a "], " \
762 #dcur "(%[probs_base], %q[t1], 2)\n\t" \
763 ) \
764 last_only( \
765 "mov %w[prob" #a "], " \
766 #dcur "(%[probs_base], %q[t1], 2)\n\t" \
767 )
768
769 #if LZMA_RANGE_DECODER_CONFIG & 0x020
770 #undef rc_bittree_rev4
771 #define rc_bittree_rev4(probs_base_var) \
772 rc_asm_bittree_n(probs_base_var, 4, \
773 rc_asm_bittree_rev(0, 1, 1, -, 4, 6, rc_asm_y, rc_asm_n, rc_asm_n) \
774 rc_asm_bittree_rev(1, 0, 2, 4, 8, 12, rc_asm_n, rc_asm_y, rc_asm_n) \
775 rc_asm_bittree_rev(0, 1, 4, 8, 16, 24, rc_asm_n, rc_asm_y, rc_asm_n) \
776 rc_asm_bittree_rev(1, 0, 8, 16, -, -, rc_asm_n, rc_asm_n, rc_asm_y) \
777 )
778 #endif // LZMA_RANGE_DECODER_CONFIG & 0x020
779
780
781 #if LZMA_RANGE_DECODER_CONFIG & 0x040
782 #undef rc_bit_add_if_1
783 #define rc_bit_add_if_1(probs_base_var, dest_var, value_to_add_if_1) \
784 do { \
785 uint32_t t0; \
786 uint32_t t1; \
787 uint32_t t2 = (value_to_add_if_1); \
788 uint32_t t_prob; \
789 uint32_t t_index; \
790 \
791 __asm__( \
792 "movzwl (%[probs_base], %q[symbol], 2), %[prob]\n\t" \
793 "mov %[symbol], %[index]\n\t" \
794 \
795 "add %[dest], %[t2]\n\t" \
796 "add %[symbol], %[symbol]\n\t" \
797 \
798 rc_asm_normalize \
799 rc_asm_calc("prob") \
800 \
801 "cmovae %[t0], %[range]\n\t" \
802 "lea %c[bit_model_offset](%q[prob]), %[t0]\n\t" \
803 "cmovb %[t1], %[code]\n\t" \
804 "cmovae %[prob], %[t0]\n\t" \
805 \
806 "cmovae %[t2], %[dest]\n\t" \
807 "sbb $-1, %[symbol]\n\t" \
808 \
809 "sar %[move_bits], %[t0]\n\t" \
810 "sub %[t0], %[prob]\n\t" \
811 "mov %w[prob], (%[probs_base], %q[index], 2)" \
812 : \
813 [range] "+&r"(rc.range), \
814 [code] "+&r"(rc.code), \
815 [t0] "=&r"(t0), \
816 [t1] "=&r"(t1), \
817 [prob] "=&r"(t_prob), \
818 [index] "=&r"(t_index), \
819 [symbol] "+&r"(symbol), \
820 [t2] "+&r"(t2), \
821 [dest] "+&r"(dest_var), \
822 [in_ptr] "+&r"(rc_in_ptr) \
823 : \
824 [probs_base] "r"(probs_base_var), \
825 [top_value] "n"(RC_TOP_VALUE), \
826 [shift_bits] "n"(RC_SHIFT_BITS), \
827 [bit_model_total_bits] "n"(RC_BIT_MODEL_TOTAL_BITS), \
828 [bit_model_offset] "n"(RC_BIT_MODEL_OFFSET), \
829 [move_bits] "n"(RC_MOVE_BITS) \
830 : \
831 "cc", "memory"); \
832 } while (0)
833 #endif // LZMA_RANGE_DECODER_CONFIG & 0x040
834
835
836 // Literal decoding uses a normal 8-bit bittree but literal with match byte
837 // is more complex in picking the probability variable from the correct
838 // subtree. This doesn't use preloading/prefetching of the next prob because
839 // there are four choices instead of two.
840 //
841 // FIXME? The first iteration starts with symbol = 1 so it could be optimized
842 // by a tiny amount.
843 #define rc_asm_matched_literal(nonlast_only) \
844 "add %[offset], %[symbol]\n\t" \
845 "and %[offset], %[match_bit]\n\t" \
846 "add %[match_bit], %[symbol]\n\t" \
847 \
848 "movzwl (%[probs_base], %q[symbol], 2), %[prob]\n\t" \
849 \
850 "add %[symbol], %[symbol]\n\t" \
851 \
852 nonlast_only( \
853 "xor %[match_bit], %[offset]\n\t" \
854 "add %[match_byte], %[match_byte]\n\t" \
855 ) \
856 \
857 rc_asm_normalize \
858 rc_asm_calc("prob") \
859 \
860 "cmovae %[t0], %[range]\n\t" \
861 "lea %c[bit_model_offset](%q[prob]), %[t0]\n\t" \
862 "cmovb %[t1], %[code]\n\t" \
863 "mov %[symbol], %[t1]\n\t" \
864 "cmovae %[prob], %[t0]\n\t" \
865 \
866 nonlast_only( \
867 "cmovae %[match_bit], %[offset]\n\t" \
868 "mov %[match_byte], %[match_bit]\n\t" \
869 ) \
870 \
871 "sbb $-1, %[symbol]\n\t" \
872 \
873 "shr %[move_bits], %[t0]\n\t" \
874 /* Undo symbol += match_bit + offset: */ \
875 "and $0x1FF, %[symbol]\n\t" \
876 "sub %[t0], %[prob]\n\t" \
877 \
878 /* Scaling of 1 instead of 2 because symbol <<= 1. */ \
879 "mov %w[prob], (%[probs_base], %q[t1], 1)\n\t"
880
881
882 #if LZMA_RANGE_DECODER_CONFIG & 0x080
883 #undef rc_matched_literal
884 #define rc_matched_literal(probs_base_var, match_byte_value) \
885 do { \
886 uint32_t t0; \
887 uint32_t t1; \
888 uint32_t t_prob; \
889 uint32_t t_match_byte = (uint32_t)(match_byte_value) << 1; \
890 uint32_t t_match_bit = t_match_byte; \
891 uint32_t t_offset = 0x100; \
892 symbol = 1; \
893 \
894 __asm__( \
895 rc_asm_matched_literal(rc_asm_y) \
896 rc_asm_matched_literal(rc_asm_y) \
897 rc_asm_matched_literal(rc_asm_y) \
898 rc_asm_matched_literal(rc_asm_y) \
899 rc_asm_matched_literal(rc_asm_y) \
900 rc_asm_matched_literal(rc_asm_y) \
901 rc_asm_matched_literal(rc_asm_y) \
902 rc_asm_matched_literal(rc_asm_n) \
903 : \
904 [range] "+&r"(rc.range), \
905 [code] "+&r"(rc.code), \
906 [t0] "=&r"(t0), \
907 [t1] "=&r"(t1), \
908 [prob] "=&r"(t_prob), \
909 [match_bit] "+&r"(t_match_bit), \
910 [symbol] "+&r"(symbol), \
911 [match_byte] "+&r"(t_match_byte), \
912 [offset] "+&r"(t_offset), \
913 [in_ptr] "+&r"(rc_in_ptr) \
914 : \
915 [probs_base] "r"(probs_base_var), \
916 [top_value] "n"(RC_TOP_VALUE), \
917 [shift_bits] "n"(RC_SHIFT_BITS), \
918 [bit_model_total_bits] "n"(RC_BIT_MODEL_TOTAL_BITS), \
919 [bit_model_offset] "n"(RC_BIT_MODEL_OFFSET), \
920 [move_bits] "n"(RC_MOVE_BITS) \
921 : \
922 "cc", "memory"); \
923 } while (0)
924 #endif // LZMA_RANGE_DECODER_CONFIG & 0x080
925
926
927 // Doing the loop in asm instead of C seems to help a little.
928 #if LZMA_RANGE_DECODER_CONFIG & 0x100
929 #undef rc_direct
930 #define rc_direct(dest_var, count_var) \
931 do { \
932 uint32_t t0; \
933 uint32_t t1; \
934 \
935 __asm__( \
936 "2:\n\t" \
937 "add %[dest], %[dest]\n\t" \
938 "lea 1(%q[dest]), %[t1]\n\t" \
939 \
940 rc_asm_normalize \
941 \
942 "shr $1, %[range]\n\t" \
943 "mov %[code], %[t0]\n\t" \
944 "sub %[range], %[code]\n\t" \
945 "cmovns %[t1], %[dest]\n\t" \
946 "cmovs %[t0], %[code]\n\t" \
947 "dec %[count]\n\t" \
948 "jnz 2b\n\t" \
949 : \
950 [range] "+&r"(rc.range), \
951 [code] "+&r"(rc.code), \
952 [t0] "=&r"(t0), \
953 [t1] "=&r"(t1), \
954 [dest] "+&r"(dest_var), \
955 [count] "+&r"(count_var), \
956 [in_ptr] "+&r"(rc_in_ptr) \
957 : \
958 [top_value] "n"(RC_TOP_VALUE), \
959 [shift_bits] "n"(RC_SHIFT_BITS) \
960 : \
961 "cc", "memory"); \
962 } while (0)
963 #endif // LZMA_RANGE_DECODER_CONFIG & 0x100
964
965 #endif // x86_64
966
967 #endif
968