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