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 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
Indexes created Sat Sep 12 00:25:55 UTC 2026