qemu/roms/ipxe/src/arch/i386/prefix/unlzma.S

   1 /*
   2  * Copyright (C) 2015 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  *
  19  * You can also choose to distribute this program under the terms of
  20  * the Unmodified Binary Distribution Licence (as given in the file
  21  * COPYING.UBDL), provided that you have satisfied its requirements.
  22  */
  23
  24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  25
  26 /****************************************************************************
  27  *
  28  * This file provides the decompress() and decompress16() functions
  29  * which can be called in order to decompress an LZMA-compressed
  30  * image.  The code is modelled on the public-domain "XZ Embedded"
  31  * implementation as used by the Linux kernel.  Symbol names are
  32  * chosen to match the XZ Embedded implementation where possible, for
  33  * ease of reference.
  34  *
  35  * This code is optimised for size rather than speed, since the amount
  36  * of data to be decompressed is trivially small by modern standards.
  37  *
  38  * The same basic assembly code is used to compile both decompress()
  39  * and decompress16().
  40  *
  41  * Note that these functions require large amounts of stack space.
  42  *
  43  ****************************************************************************
  44  */
  45
  46         .text
  47         .arch i586
  48         .section ".prefix.lib", "ax", @progbits
  49
  50 #ifdef CODE16
  51 #define ADDR16
  52 #define ADDR32 addr32
  53 #define decompress decompress16
  54         .code16
  55 #else /* CODE16 */
  56 #define ADDR16 addr16
  57 #define ADDR32
  58         .code32
  59 #endif /* CODE16 */
  60
  61 /****************************************************************************
  62  * Debugging
  63  ****************************************************************************
  64  *
  65  * This code will usually run in 16-bit protected mode, in which case
  66  * only the 0xe9 debug port (present on some virtual machines) can be
  67  * used.
  68  *
  69  * To debug on real hardware, build with DEBUG=libprefix.  This will
  70  * cause this code to be called in flat real mode, and so DEBUG_INT10
  71  * may be used.
  72  */
  73
  74 /* Enable debugging via 0xe9 debug port */
  75 #define DEBUG_E9 0
  76
  77 /* Enable debugging via BIOS INT 10 (works only when in flat real mode) */
  78 #define DEBUG_INT10 0
  79
  80 #if ( DEBUG_E9 || DEBUG_INT10 )
  81         .macro  print_character, reg
  82         pushfl
  83         pushw   %ax
  84         pushw   %bx
  85         pushw   %bp
  86         movb    \reg, %al
  87         movw    $0x0007, %bx
  88         movb    $0x0e, %ah
  89 #if DEBUG_E9
  90         outb    %al, $0xe9
  91 #endif
  92 #if DEBUG_INT10
  93         cmpb    $('\n'), %al
  94         jne     L\@
  95         int     $0x10
  96         movb    $('\r'), %al
  97 L\@:    int     $0x10
  98 #endif
  99         popw    %bp
 100         popw    %bx
 101         popw    %ax
 102         popfl
 103         .endm
 104
 105         .macro  print_hex_nibble
 106         pushfl
 107         pushw   %ax
 108         cmpb    $10, %al
 109         sbb     $0x69, %al
 110         das
 111         print_character %al
 112         popw    %ax
 113         popfl
 114         .endm
 115
 116         .macro  print_hex_byte, reg
 117         pushfl
 118         pushw   %ax
 119         movb    \reg, %al
 120         pushw   %ax
 121         shrb    $4, %al
 122         print_hex_nibble
 123         popw    %ax
 124         andb    $0x0f, %al
 125         print_hex_nibble
 126         popw    %ax
 127         popfl
 128         .endm
 129
 130         .macro  print_hex_word, reg
 131         pushw   %ax
 132         movw    \reg, %ax
 133         print_hex_byte %ah
 134         print_hex_byte %al
 135         popw    %ax
 136         .endm
 137
 138         .macro  print_hex_dword, reg
 139         pushl   %eax
 140         movl    \reg, %eax
 141         rorl    $16, %eax
 142         print_hex_word %ax
 143         rorl    $16, %eax
 144         print_hex_word %ax
 145         popl    %eax
 146         .endm
 147 #else
 148         .macro  print_character, char
 149         .endm
 150         .macro  print_hex_byte, reg
 151         .endm
 152         .macro  print_hex_word, reg
 153         .endm
 154         .macro  print_hex_dword, reg
 155         .endm
 156 #endif
 157
 158 /****************************************************************************
 159  * LZMA parameters and data structures
 160  ****************************************************************************
 161  */
 162
 163 /* LZMA decompressor states (as used in XZ Embedded) */
 164 #define STATE_LIT_LIT 0x00
 165 #define STATE_MATCH_LIT_LIT 0x01
 166 #define STATE_REP_LIT_LIT 0x02
 167 #define STATE_SHORTREP_LIT_LIT 0x03
 168 #define STATE_MATCH_LIT 0x04
 169 #define STATE_REP_LIT 0x05
 170 #define STATE_SHORTREP_LIT 0x06
 171 #define STATE_LIT_MATCH 0x07
 172 #define STATE_LIT_LONGREP 0x08
 173 #define STATE_LIT_SHORTREP 0x09
 174 #define STATE_NONLIT_MATCH 0x0a
 175 #define STATE_NONLIT_REP 0x0b
 176
 177 /* LZMA maximum decompressor state in which most recent symbol was a literal */
 178 #define STATE_LIT_MAX 0x06
 179
 180 /* LZMA number of literal context bits ("lc=" parameter) */
 181 #define LZMA_LC 2
 182
 183         .struct 0
 184 lzma_len_dec:
 185 choice:         .word   0
 186 choice2:        .word   0
 187 low:            .rept   ( 1 << 3 )
 188                 .word   0
 189                 .endr
 190 mid:            .rept   ( 1 << 3 )
 191                 .word   0
 192                 .endr
 193 high:           .rept   ( 1 << 8 )
 194                 .word   0
 195                 .endr
 196         .equ    sizeof__lzma_len_dec, . - lzma_len_dec
 197         .previous
 198
 199         .struct 0
 200 lzma_dec:
 201 out_start:      .long   0
 202 rc_code:        .long   0
 203 rc_range:       .long   0
 204 len:            .word   0
 205 reps:
 206 rep0:           .long   0
 207 rep1:           .long   0
 208 rep2:           .long   0
 209 rep3:           .long   0
 210 probs:
 211 is_match:       .word   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 212 is_rep:         .word   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 213 is_rep0:        .word   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 214 is_rep1:        .word   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 215 is_rep2:        .word   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 216 is_rep0_long:   .word   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 217 dist_slot:      .rept   ( 4 * ( 1 << 6 ) )
 218                 .word   0
 219                 .endr
 220 dist_special:   .rept   ( ( 1 << ( 14 / 2 ) ) - 14 )
 221                 .word   0
 222                 .endr
 223 dist_align:     .rept   ( 1 << 4 )
 224                 .word   0
 225                 .endr
 226 match_len_dec:  .space  sizeof__lzma_len_dec
 227 rep_len_dec:    .space  sizeof__lzma_len_dec
 228 literal:        .rept   ( ( 1 << LZMA_LC ) * 0x300 )
 229                 .word   0
 230                 .endr
 231         .align  4
 232         .equ    sizeof__lzma_dec, . - lzma_dec
 233         .previous
 234
 235         /* Some binutils versions seem not to handle .struct/.previous */
 236         .section ".prefix.lib", "ax", @progbits
 237
 238 /*****************************************************************************
 239  * Normalise range encoder
 240  *
 241  * Parameters:
 242  *   %ss:%ebp : LZMA parameter block
 243  *   %ds:%esi : compressed input data pointer
 244  * Returns:
 245  *   %ds:%esi : compressed input data pointer (possibly updated)
 246  *   %eax : current range
 247  *****************************************************************************
 248  */
 249 rc_normalise:
 250         /* Check if rc_range is less than 1<<24 */
 251         testb   $0xff, (rc_range+3)(%ebp)
 252         jnz     1f
 253         /* If it is, shift in a new byte from the compressed input data */
 254         shll    $8, rc_range(%ebp)
 255         shll    $8, rc_code(%ebp)
 256         ADDR32 lodsb
 257         movb    %al, (rc_code+0)(%ebp)
 258 1:      /* Return current range */
 259         movl    rc_range(%ebp), %eax
 260         ret
 261         .size   rc_normalise, . - rc_normalise
 262
 263 /*****************************************************************************
 264  * Decode single range-encoded bit using a probability estimate
 265  *
 266  * Parameters:
 267  *   %ss:%ebp : LZMA parameter block
 268  *   %ds:%esi : compressed input data pointer
 269  *   %ebx : probability estimate pointer (offset from %ebp)
 270  * Returns:
 271  *   %ds:%esi : compressed input data pointer (possibly updated)
 272  *   CF : decoded bit
 273  *   ZF : inverse of decoded bit
 274  * Corrupts:
 275  *   none
 276  *****************************************************************************
 277  */
 278 rc_bit:
 279         /* Preserve registers */
 280         pushl   %eax
 281         pushl   %edx
 282         /* Perform normalisation */
 283         call    rc_normalise
 284         /* Calculate bound in %eax and probability estimate in %dx */
 285         shrl    $11, %eax
 286         movzwl  (%ebp,%ebx), %edx
 287         mul     %edx /* will zero %edx */
 288         movw    (%ebp,%ebx), %dx
 289         /* Compare code against bound */
 290         cmpl    %eax, rc_code(%ebp)
 291         jae     2f
 292 1:      /* Code is less than bound */
 293         movl    %eax, rc_range(%ebp)
 294         negw    %dx
 295         addw    $(1<<11), %dx
 296         shrw    $5, %dx
 297         addw    %dx, (%ebp,%ebx)
 298         xorw    %ax, %ax        /* Clear CF, set ZF */
 299         jmp     99f
 300 2:      /* Code is greater than or equal to bound */
 301         subl    %eax, rc_range(%ebp)
 302         subl    %eax, rc_code(%ebp)
 303         shrw    $5, %dx
 304         subw    %dx, (%ebp,%ebx)
 305         incw    %dx             /* Clear ZF (%dx is 11-bit; can never wrap) */
 306         stc                     /* Set CF */
 307 99:     /* Restore registers and return */
 308         popl    %edx
 309         popl    %eax
 310         ret
 311         .size   rc_bit, . - rc_bit
 312
 313 /*****************************************************************************
 314  * Decode MSB-first bittree
 315  *
 316  * Parameters:
 317  *   %ss:%ebp : LZMA parameter block
 318  *   %ds:%esi : compressed input data pointer
 319  *   %ebx : probability estimate set pointer (offset from %ebp)
 320  *   %cx : number of bits to decode
 321  * Returns:
 322  *   %ds:%esi : compressed input data pointer (possibly updated)
 323  *   %eax : decoded bittree
 324  * Corrupts:
 325  *   none
 326  *****************************************************************************
 327  */
 328 rc_bittree:
 329         /* Preserve registers */
 330         pushl   %edi
 331         pushw   %cx
 332         movl    %ebx, %edi
 333         /* Initialise registers */
 334         movl    $1, %eax
 335 1:      /* Decode bit */
 336         leaw    (%edi,%eax,2), %bx      /* high word always zero anyway */
 337         call    rc_bit
 338         rclw    %ax
 339         ADDR16 loop 1b
 340         /* Restore registers, clear unwanted high bit of result, and return */
 341         movl    %edi, %ebx
 342         popw    %cx
 343         popl    %edi
 344         btrw    %cx, %ax
 345         ret
 346         .size   rc_bittree, . - rc_bittree
 347
 348 /*****************************************************************************
 349  * Decode LSB-first bittree
 350  *
 351  * Parameters:
 352  *   %ss:%ebp : LZMA parameter block
 353  *   %ds:%esi : compressed input data pointer
 354  *   %ebx : probability estimate set pointer (offset from %ebp)
 355  *   %cx : number of bits to decode
 356  * Returns:
 357  *   %ds:%esi : compressed input data pointer (possibly updated)
 358  *   %eax : decoded bittree
 359  * Corrupts:
 360  *   none
 361  *****************************************************************************
 362  */
 363 rc_bittree_reverse:
 364         /* Preserve registers */
 365         pushw   %cx
 366         /* Decode bittree */
 367         call    rc_bittree
 368 1:      /* Reverse result */
 369         rcrb    %al
 370         rclb    %ah
 371         ADDR16 loop 1b
 372         shrw    $8, %ax
 373         /* Restore registers and return */
 374         popw    %cx
 375         ret
 376         .size   rc_bittree_reverse, . - rc_bittree_reverse
 377
 378 /*****************************************************************************
 379  * Decode MSB-first bittree with optional match byte
 380  *
 381  * Parameters:
 382  *   %ss:%ebp : LZMA parameter block
 383  *   %ds:%esi : compressed input data pointer
 384  *   %ebx : probability estimate set pointer (offset from %ebp)
 385  *   %cl : match byte
 386  *   %ch : 1 to use match byte, 0 to ignore match byte
 387  * Returns:
 388  *   %ds:%esi : compressed input data pointer (possibly updated)
 389  *   %eax : decoded bittree
 390  * Corrupts:
 391  *   none
 392  *****************************************************************************
 393  */
 394 rc_bittree_match:
 395         /* Preserve registers */
 396         pushl   %edi
 397         pushw   %cx
 398         pushw   %dx
 399         movl    %ebx, %edi
 400         /* Initialise registers */
 401         movl    $1, %eax
 402 1:      /* Decode bit */
 403         rolb    $1, %cl
 404         movw    %cx, %dx
 405         andb    %dh, %dl                /* match_bit in %dl */
 406         movw    %dx, %bx
 407         addb    %bl, %bh
 408         xorb    %bl, %bl
 409         addw    %ax, %bx                /* offset + match_bit + symbol */
 410         leaw    (%edi,%ebx,2), %bx      /* high word always zero anyway */
 411         call    rc_bit
 412         rclw    %ax
 413         movb    %al, %dh
 414         notb    %dh
 415         xorb    %dh, %dl
 416         andb    %dl, %ch                /* offset &= ( match_bit ^ bit ) */
 417         testb   %ah, %ah
 418         jz      1b
 419         /* Restore registers, clear unwanted high bit of result, and return */
 420         movl    %edi, %ebx
 421         popw    %dx
 422         popw    %cx
 423         popl    %edi
 424         xorb    %ah, %ah
 425         ret
 426         .size   rc_bittree_match, . - rc_bittree_match
 427
 428 /*****************************************************************************
 429  * Decode direct bits (no probability estimates)
 430  *
 431  * Parameters:
 432  *   %ss:%ebp : LZMA parameter block
 433  *   %ds:%esi : compressed input data pointer
 434  *   %cx : number of bits to decode
 435  * Returns:
 436  *   %ds:%esi : compressed input data pointer (possibly updated)
 437  *   %eax : decoded bits
 438  * Corrupts:
 439  *   none
 440  *****************************************************************************
 441  */
 442 rc_direct:
 443         /* Preserve registers */
 444         pushl   %ebx
 445         pushw   %cx
 446         pushl   %edx
 447         /* Initialise registers */
 448         xorl    %edx, %edx
 449 1:      /* Perform normalisation */
 450         call    rc_normalise
 451         /* Decode bit */
 452         shrl    $1, %eax
 453         movl    %eax, rc_range(%ebp)
 454         movl    rc_code(%ebp), %ebx
 455         subl    %eax, %ebx
 456         js      2f
 457         movl    %ebx, rc_code(%ebp)
 458 2:      rcll    %ebx
 459         rcll    %edx
 460         xorb    $1, %dl
 461         ADDR16 loop 1b
 462         /* Restore registers and return */
 463         movl    %edx, %eax
 464         popl    %edx
 465         popw    %cx
 466         popl    %ebx
 467         ret
 468         .size   rc_direct, . - rc_direct
 469
 470 /*****************************************************************************
 471  * Decode an LZMA literal
 472  *
 473  * Parameters:
 474  *   %ss:%ebp : LZMA parameter block
 475  *   %ds:%esi : compressed input data pointer
 476  *   %es:%edi : uncompressed output data pointer
 477  *   %edx : LZMA state
 478  * Returns:
 479  *   %ds:%esi : compressed input data pointer (possibly updated)
 480  *   %es:%edi : uncompressed output data pointer (updated)
 481  *   %edx : LZMA state
 482  *   CF : end of payload marker found (always zero)
 483  * Corrupts:
 484  *   %eax
 485  *   %ebx
 486  *   %ecx
 487  *****************************************************************************
 488  *
 489  * Literals are coded as an eight-bit tree, using a match byte if the
 490  * previous symbol was not a literal.
 491  *
 492  */
 493 lzma_literal:
 494         /* Get most recent output byte, if available */
 495         xorl    %ebx, %ebx
 496         cmpl    %edi, out_start(%ebp)
 497         je      1f
 498         movb    %es:-1(%edi), %bh
 499 1:      /* Locate probability estimate set */
 500         shrb    $( 8 - LZMA_LC ), %bh
 501         shlb    $1, %bh
 502         leaw    literal(%ebx,%ebx,2), %bx
 503         /* Get match byte, if applicable */
 504         xorw    %cx, %cx
 505         cmpb    $STATE_LIT_MAX, %dl
 506         jbe     1f
 507         movl    rep0(%ebp), %eax
 508         notl    %eax
 509         movb    %es:(%edi,%eax), %cl
 510         movb    $1, %ch
 511 1:      /* Decode bittree */
 512         call    rc_bittree_match
 513         /* Store output byte */
 514         ADDR32 stosb
 515         print_hex_byte %al
 516         print_character $(' ')
 517         /* Update LZMA state */
 518         subb    $3, %dl
 519         jns     1f
 520         xorb    %dl, %dl
 521 1:      cmpb    $7, %dl
 522         jb      1f
 523         subb    $3, %dl
 524 1:      /* Clear CF and return */
 525         clc
 526         ret
 527         .size   lzma_literal, . - lzma_literal
 528
 529 /*****************************************************************************
 530  * Decode an LZMA length
 531  *
 532  * Parameters:
 533  *   %ss:%ebp : LZMA parameter block
 534  *   %ds:%esi : compressed input data pointer
 535  *   %ebx : length parameter pointer (offset from %ebp)
 536  * Returns:
 537  *   %ds:%esi : compressed input data pointer (possibly updated)
 538  * Corrupts:
 539  *   %ebx
 540  *****************************************************************************
 541  *
 542  * Lengths are encoded as:
 543  *
 544  *   "0" + 3 bits    : lengths 2-9 ("low")
 545  *   "10" + 3 bits   : lengths 10-17 ("mid")
 546  *   "11" + 8 bits   : lengths 18-273 ("high")
 547  */
 548 lzma_len:
 549         /* Preserve registers */
 550         pushl   %eax
 551         pushl   %ecx
 552         pushl   %edi
 553         movl    %ebx, %edi
 554         /* Start by assuming three bits and a base length of 2 */
 555         movw    $3, %cx
 556         movw    $2, len(%ebp)
 557         /* Check low-length choice bit */
 558         leal    choice(%edi), %ebx
 559         call    rc_bit
 560         leal    low(%edi), %ebx
 561         jz      1f
 562         /* Check high-length choice bit */
 563         leal    choice2(%edi), %ebx
 564         call    rc_bit
 565         leal    mid(%edi), %ebx
 566         movb    $10, len(%ebp)
 567         jz      1f
 568         leal    high(%edi), %ebx
 569         movb    $8, %cl
 570         movb    $18, len(%ebp)
 571 1:      /* Get encoded length */
 572         call    rc_bittree
 573         addw    %ax, len(%ebp)
 574         /* Restore registers and return */
 575         movl    %edi, %ebx
 576         popl    %edi
 577         popl    %ecx
 578         popl    %eax
 579         ret
 580         .size   lzma_len, . - lzma_len
 581
 582 /*****************************************************************************
 583  * Copy (possibly repeated) matched data
 584  *
 585  * Parameters:
 586  *   %ss:%ebp : LZMA parameter block
 587  *   %ds:%esi : compressed input data pointer
 588  *   %es:%edi : uncompressed output data pointer
 589  *   %cl : repeated match distance index (for repeated matches)
 590  *   %eax : match distance (for non-repeated matches)
 591  * Returns:
 592  *   %ds:%esi : compressed input data pointer (possibly updated)
 593  *   %es:%edi : uncompressed output data pointer
 594  *   CF : match distance is out of range
 595  * Corrupts:
 596  *   %eax
 597  *   %ebx
 598  *   %ecx
 599  *****************************************************************************
 600  */
 601 match:  /* Update repeated match list */
 602         print_character $('[')
 603         movl    $3, %ecx
 604         jmp     1f
 605 match_rep:
 606         print_character $('[')
 607         print_character $('R')
 608         print_hex_byte %cl
 609         print_character $('=')
 610         movzbl  %cl, %ecx
 611         movl    reps(%ebp,%ecx,4), %eax
 612         jcxz    2f
 613 1:      movl    (reps-4)(%ebp,%ecx,4), %ebx
 614         movl    %ebx, reps(%ebp,%ecx,4)
 615         loop    1b
 616         movl    %eax, rep0(%ebp)
 617 2:      /* Preserve registers */
 618         pushl   %esi
 619         /* Get stored match length */
 620         movzwl  len(%ebp), %ecx
 621         print_hex_dword %eax
 622         print_character $('+')
 623         print_hex_word %cx
 624         print_character $(']')
 625         print_character $(' ')
 626         /* Abort with CF set if match distance is out of range */
 627         movl    out_start(%ebp), %esi
 628         negl    %esi
 629         leal    -1(%edi,%esi), %esi
 630         cmpl    %eax, %esi
 631         jc      99f
 632         /* Perform copy */
 633         notl    %eax
 634         leal    (%edi,%eax), %esi
 635         ADDR32 es rep movsb
 636 99:     /* Restore registers and return */
 637         popl    %esi
 638         ret
 639         .size   match, . - match
 640
 641 /*****************************************************************************
 642  * Decode an LZMA match
 643  *
 644  * Parameters:
 645  *   %ss:%ebp : LZMA parameter block
 646  *   %ds:%esi : compressed input data pointer
 647  *   %es:%edi : uncompressed output data pointer
 648  *   %edx : LZMA state
 649  * Returns:
 650  *   %ds:%esi : compressed input data pointer (possibly updated)
 651  *   %es:%edi : uncompressed output data pointer
 652  *   %edx : LZMA state
 653  *   CF : end of payload marker found
 654  * Corrupts:
 655  *   %eax
 656  *   %ebx
 657  *   %ecx
 658  *****************************************************************************
 659  *
 660  * Matches are encoded as an LZMA length followed by a 6-bit "distance
 661  * slot" code, 0-26 fixed-probability bits, and 0-5 context encoded
 662  * bits.
 663  */
 664 lzma_match:
 665         /* Preserve registers */
 666         pushl   %edi
 667         /* Update LZMA state */
 668         cmpb    $STATE_LIT_MAX, %dl
 669         movb    $STATE_LIT_MATCH, %dl
 670         jbe     1f
 671         movb    $STATE_NONLIT_MATCH, %dl
 672 1:      /* Decode length */
 673         movl    $match_len_dec, %ebx
 674         call    lzma_len
 675         /* Decode distance slot */
 676         movw    len(%ebp), %bx
 677         subw    $2, %bx
 678         cmpw    $4, %bx
 679         jb      1f
 680         movw    $3, %bx
 681 1:      shlw    $7, %bx
 682         addw    $dist_slot, %bx
 683         movw    $6, %cx
 684         call    rc_bittree
 685         /* Distance slots 0-3 are literal distances */
 686         cmpb    $4, %al
 687         jb      99f
 688         /* Determine initial bits: 10/11 for even/odd distance codes */
 689         movl    %eax, %edi
 690         andw    $1, %di
 691         orw     $2, %di
 692         /* Determine number of context-encoded bits */
 693         movw    %ax, %cx
 694         shrb    $1, %cl
 695         decb    %cl
 696         /* Select context to be used in absence of fixed-probability bits */
 697         movl    %edi, %ebx
 698         shlw    %cl, %bx
 699         subw    %ax, %bx
 700         leaw    (dist_special-2)(%ebx,%ebx), %bx
 701         /* Decode fixed-probability bits, if any */
 702         cmpb    $6, %cl
 703         jb      1f
 704         subb    $4, %cl
 705         shll    %cl, %edi
 706         call    rc_direct
 707         orl     %eax, %edi
 708         /* Select context to be used in presence of fixed-probability bits */
 709         movb    $4, %cl
 710         movl    $dist_align, %ebx
 711 1:      /* Decode context-encoded bits */
 712         shll    %cl, %edi
 713         call    rc_bittree_reverse
 714         orl     %edi, %eax
 715 99:     /* Restore registers and tail-call */
 716         popl    %edi
 717         jmp     match
 718         .size   lzma_match, . - lzma_match
 719
 720 /*****************************************************************************
 721  * Decode an LZMA repeated match
 722  *
 723  * Parameters:
 724  *   %ss:%ebp : LZMA parameter block
 725  *   %ds:%esi : compressed input data pointer
 726  *   %es:%edi : uncompressed output data pointer
 727  *   %edx : LZMA state
 728  * Returns:
 729  *   %ds:%esi : compressed input data pointer (possibly updated)
 730  *   %es:%edi : uncompressed output data pointer
 731  *   %edx : LZMA state
 732  *   CF : end of payload marker found
 733  * Corrupts:
 734  *   %eax
 735  *   %ebx
 736  *   %ecx
 737  *****************************************************************************
 738  *
 739  * Repeated matches are encoded as:
 740  *
 741  *   "00"        : shortrep0 (implicit length 1)
 742  *   "01" + len  : longrep0
 743  *   "10" + len  : longrep1
 744  *   "110" + len : longrep2
 745  *   "111" + len : longrep3
 746  */
 747 lzma_rep_match:
 748         /* Initially assume longrep0 */
 749         movw    $(STATE_LIT_LONGREP << 8), %cx
 750         /* Get is_rep0 bit */
 751         leal    is_rep0(,%edx,2), %ebx
 752         call    rc_bit
 753         jnz     1f
 754         /* Get is_rep0_long bit */
 755         leal    is_rep0_long(,%edx,2), %ebx
 756         call    rc_bit
 757         jnz     98f
 758         movw    $1, len(%ebp)
 759         movb    $STATE_LIT_SHORTREP, %ch
 760         jmp     99f
 761 1:      /* Get is_rep1 bit */
 762         incb    %cl
 763         leal    is_rep1(,%edx,2), %ebx
 764         call    rc_bit
 765         jz      98f
 766         /* Get is_rep2 bit */
 767         incb    %cl
 768         leal    is_rep2(,%edx,2), %ebx
 769         call    rc_bit
 770         adcb    $0, %cl
 771 98:     /* Decode length */
 772         movl    $rep_len_dec, %ebx
 773         call    lzma_len
 774 99:     /* Update LZMA state */
 775         cmpb    $STATE_LIT_MAX, %dl
 776         movb    %ch, %dl
 777         jbe     1f
 778         movb    $STATE_NONLIT_REP, %dl
 779 1:      /* Tail call */
 780         jmp     match_rep
 781         .size   lzma_match, . - lzma_match
 782
 783 /*****************************************************************************
 784  * Decode one LZMA symbol
 785  *
 786  * Parameters:
 787  *   %ss:%ebp : LZMA parameter block
 788  *   %ds:%esi : compressed input data pointer
 789  *   %es:%edi : uncompressed output data pointer
 790  *   %edx : LZMA state
 791  * Returns:
 792  *   %ds:%esi : compressed input data pointer (possibly updated)
 793  *   %es:%edi : uncompressed output data pointer (updated)
 794  *   %edx : LZMA state
 795  *   CF : end of payload marker found
 796  * Corrupts:
 797  *   %eax
 798  *   %ebx
 799  *   %ecx
 800  *****************************************************************************
 801  */
 802 lzma_decode:
 803         /* Get is_match bit */
 804         leal    is_match(,%edx,2), %ebx
 805         call    rc_bit
 806         jz      lzma_literal
 807         /* Get is_rep bit */
 808         leal    is_rep(,%edx,2), %ebx
 809         call    rc_bit
 810         jz      lzma_match
 811         jmp     lzma_rep_match
 812         .size   lzma_decode, . - lzma_decode
 813
 814 /****************************************************************************
 815  * Undo effect of branch-call-jump (BCJ) filter
 816  *
 817  * Parameters:
 818  *   %es:%esi : start of uncompressed output data (note %es)
 819  *   %es:%edi : end of uncompressed output data
 820  * Returns:
 821  * Corrupts:
 822  *   %eax
 823  *   %ebx
 824  *   %ecx
 825  *   %edx
 826  *   %esi
 827  *****************************************************************************
 828  */
 829 bcj_filter:
 830         /* Store (negative) start of data in %edx */
 831         movl    %esi, %edx
 832         negl    %edx
 833         /* Calculate limit in %ecx */
 834         leal    -5(%edi,%edx), %ecx
 835 1:      /* Calculate offset in %ebx */
 836         leal    (%esi,%edx), %ebx
 837         /* Check for end of data */
 838         cmpl    %ecx, %ebx
 839         ja      99f
 840         /* Check for an opcode which would be followed by a rel32 address */
 841         ADDR32 es lodsb
 842         andb    $0xfe, %al
 843         cmpb    $0xe8, %al
 844         jne     1b
 845         /* Get current jump target value in %eax */
 846         ADDR32 es lodsl
 847         /* Convert absolute addresses in the range [0,limit) back to
 848          * relative addresses in the range [-offset,limit-offset).
 849          */
 850         cmpl    %ecx, %eax
 851         jae     2f
 852         subl    %ebx,%es:-4(%esi)
 853 2:      /* Convert negative numbers in the range [-offset,0) back to
 854          * positive numbers in the range [limit-offset,limit).
 855          */
 856         notl    %eax    /* Range is now [0,offset) */
 857         cmpl    %ebx, %eax
 858         jae     1b
 859         addl    %ecx,%es:-4(%esi)
 860         jmp     1b
 861 99:     /* Return */
 862         ret
 863         .size   bcj_filter, . - bcj_filter
 864
 865 /****************************************************************************
 866  * decompress (real-mode or 16/32-bit protected-mode near call)
 867  *
 868  * Decompress data
 869  *
 870  * Parameters (passed via registers):
 871  *   %ds:%esi : Start of compressed input data
 872  *   %es:%edi : Start of output buffer
 873  * Returns:
 874  *   %ds:%esi - End of compressed input data
 875  *   %es:%edi - End of decompressed output data
 876  *   All other registers are preserved
 877  *
 878  * NOTE: It would be possible to build a smaller version of the
 879  * decompression code for -DKEEP_IT_REAL by using 16-bit registers
 880  * where possible.
 881  ****************************************************************************
 882  */
 883         .globl  decompress
 884 decompress:
 885         /* Preserve registers */
 886         pushl   %eax
 887         pushl   %ebx
 888         pushl   %ecx
 889         pushl   %edx
 890         pushl   %ebp
 891         /* Allocate parameter block */
 892         subl    $sizeof__lzma_dec, %esp
 893         movl    %esp, %ebp
 894         /* Zero parameter block and set all probabilities to 0.5 */
 895         pushl   %edi
 896         pushw   %es
 897         pushw   %ss
 898         popw    %es
 899         movl    %ebp, %edi
 900         xorl    %eax, %eax
 901         movl    $( sizeof__lzma_dec / 4 ), %ecx
 902         ADDR32 rep stosl
 903         leal    probs(%ebp), %edi
 904         movw    $( ( 1 << 11 ) / 2 ), %ax
 905         movl    $( ( sizeof__lzma_dec - probs ) / 2 ), %ecx
 906         ADDR32 rep stosw
 907         popw    %es
 908         popl    %edi
 909         /* Initialise remaining parameters */
 910         movl    %edi, out_start(%ebp)
 911         print_character $('\n')
 912         ADDR32 lodsb    /* discard initial byte */
 913         print_hex_byte %al
 914         ADDR32 lodsl
 915         bswapl  %eax
 916         print_hex_dword %eax
 917         print_character $('\n')
 918         movl    %eax, rc_code(%ebp)
 919         decl    rc_range(%ebp)
 920         movl    $STATE_LIT_LIT, %edx
 921 1:      /* Decompress until we reach end of buffer */
 922         call    lzma_decode
 923         jnc     1b
 924         call    rc_normalise
 925         print_character $('\n')
 926         /* Undo BCJ filter */
 927         pushl   %esi
 928         movl    out_start(%ebp), %esi
 929         call    bcj_filter
 930         popl    %esi
 931         /* Restore registers and return */
 932         addl    $sizeof__lzma_dec, %esp
 933         popl    %ebp
 934         popl    %edx
 935         popl    %ecx
 936         popl    %ebx
 937         popl    %eax
 938         ret
 939
 940         /* Specify minimum amount of stack space required */
 941         .globl  _min_decompress_stack
 942         .equ    _min_decompress_stack, ( sizeof__lzma_dec + 512 /* margin */ )