arch/common/boot/grub2/kern/i386/pc/lzma_decode.S

   1 /*
   2  *  GRUB  --  GRand Unified Bootloader
   3  *  Copyright (C) 2008  Free Software Foundation, Inc.
   4  *
   5  *  GRUB is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation, either version 3 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  GRUB is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #define FIXED_PROPS
  20
  21 #define LZMA_BASE_SIZE 1846
  22 #define LZMA_LIT_SIZE 768
  23
  24 #define LZMA_PROPERTIES_SIZE 5
  25
  26 #define kNumTopBits 24
  27 #define kTopValue (1 << kNumTopBits)
  28
  29 #define kNumBitModelTotalBits 11
  30 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  31 #define kNumMoveBits 5
  32
  33
  34 #define kNumPosBitsMax 4
  35 #define kNumPosStatesMax (1 << kNumPosBitsMax)
  36
  37 #define kLenNumLowBits 3
  38 #define kLenNumLowSymbols (1 << kLenNumLowBits)
  39 #define kLenNumMidBits 3
  40 #define kLenNumMidSymbols (1 << kLenNumMidBits)
  41 #define kLenNumHighBits 8
  42 #define kLenNumHighSymbols (1 << kLenNumHighBits)
  43
  44 #define LenChoice 0
  45 #define LenChoice2 (LenChoice + 1)
  46 #define LenLow (LenChoice2 + 1)
  47 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
  48 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
  49 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
  50
  51
  52 #define kNumStates 12
  53 #define kNumLitStates 7
  54
  55 #define kStartPosModelIndex 4
  56 #define kEndPosModelIndex 14
  57 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
  58
  59 #define kNumPosSlotBits 6
  60 #define kNumLenToPosStates 4
  61
  62 #define kNumAlignBits 4
  63 #define kAlignTableSize (1 << kNumAlignBits)
  64
  65 #define kMatchMinLen 2
  66
  67 #define IsMatch 0
  68 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
  69 #define IsRepG0 (IsRep + kNumStates)
  70 #define IsRepG1 (IsRepG0 + kNumStates)
  71 #define IsRepG2 (IsRepG1 + kNumStates)
  72 #define IsRep0Long (IsRepG2 + kNumStates)
  73 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
  74 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
  75 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
  76 #define LenCoder (Align + kAlignTableSize)
  77 #define RepLenCoder (LenCoder + kNumLenProbs)
  78 #define Literal (RepLenCoder + kNumLenProbs)
  79
  80
  81 #if 0
  82
  83 DbgOut:
  84         pushf
  85         pushl   %ebp
  86         pushl   %edi
  87         pushl   %esi
  88         pushl   %edx
  89         pushl   %ecx
  90         pushl   %ebx
  91         pushl   %eax
  92
  93         call    _DebugPrint
  94
  95         popl    %eax
  96         popl    %ebx
  97         popl    %ecx
  98         popl    %edx
  99         popl    %esi
 100         popl    %edi
 101         popl    %ebp
 102         popf
 103
 104         ret
 105
 106
 107 /*
 108  * int LzmaDecodeProperties(CLzmaProperties *propsRes,
 109  *                          const unsigned char *propsData,
 110  *                          int size);
 111  */
 112
 113 _LzmaDecodePropertiesA:
 114         movb    (%edx), %dl
 115
 116         xorl    %ecx, %ecx
 117 1:
 118         cmpb    $45, %dl
 119         jb      2f
 120         incl    %ecx
 121         subb    $45, %dl
 122         jmp     1b
 123 2:
 124         movl    %ecx, 8(%eax)           /* pb */
 125         xorl    %ecx, %ecx
 126 1:
 127         cmpb    $9, %dl
 128         jb      2f
 129         incl    %ecx
 130         subb    $9, %dl
 131 2:
 132         movl    %ecx, 4(%eax)           /* lp */
 133         movb    %dl, %cl
 134         movl    %ecx, (%eax)            /* lc */
 135
 136 #endif
 137
 138 #ifndef ASM_FILE
 139         xorl    %eax, %eax
 140 #endif
 141         ret
 142
 143 #define out_size        8(%ebp)
 144
 145 #define now_pos         -4(%ebp)
 146 #define prev_byte       -8(%ebp)
 147 #define range           -12(%ebp)
 148 #define code            -16(%ebp)
 149 #define state           -20(%ebp)
 150 #define rep0            -24(%ebp)
 151 #define rep1            -28(%ebp)
 152 #define rep2            -32(%ebp)
 153 #define rep3            -36(%ebp)
 154
 155 #ifdef FIXED_PROPS
 156
 157 #define FIXED_LC        3
 158 #define FIXED_LP        0
 159 #define FIXED_PB        2
 160
 161 #define POS_STATE_MASK  ((1 << (FIXED_PB)) - 1)
 162 #define LIT_POS_MASK    ((1 << (FIXED_LP)) - 1)
 163
 164 #define LOCAL_SIZE      36
 165
 166 #else
 167
 168 #define lc              (%ebx)
 169 #define lp              4(%ebx)
 170 #define pb              8(%ebx)
 171 #define probs           12(%ebx)
 172
 173 #define pos_state_mask  -40(%ebp)
 174 #define lit_pos_mask    -44(%ebp)
 175
 176 #define LOCAL_SIZE      44
 177
 178 #endif
 179
 180 RangeDecoderBitDecode:
 181 #ifdef FIXED_PROPS
 182         leal    (%ebx, %eax, 4), %eax
 183 #else
 184         shll    $2, %eax
 185         addl    probs, %eax
 186 #endif
 187
 188         movl    %eax, %ecx
 189         movl    (%ecx), %eax
 190
 191         movl    range, %edx
 192         shrl    $kNumBitModelTotalBits, %edx
 193         mull    %edx
 194
 195         cmpl    code, %eax
 196         jbe     1f
 197
 198         movl    %eax, range
 199         movl    $kBitModelTotal, %edx
 200         subl    (%ecx), %edx
 201         shrl    $kNumMoveBits, %edx
 202         addl    %edx, (%ecx)
 203         clc
 204 3:
 205         pushf
 206         cmpl    $kTopValue, range
 207         jnc     2f
 208         shll    $8, code
 209         lodsb
 210         movb    %al, code
 211         shll    $8, range
 212 2:
 213         popf
 214         ret
 215 1:
 216         subl    %eax, range
 217         subl    %eax, code
 218         movl    (%ecx), %edx
 219         shrl    $kNumMoveBits, %edx
 220         subl    %edx, (%ecx)
 221         stc
 222         jmp     3b
 223
 224 RangeDecoderBitTreeDecode:
 225 RangeDecoderReverseBitTreeDecode:
 226         movzbl  %cl, %ecx
 227         xorl    %edx, %edx
 228         pushl   %edx
 229         incl    %edx
 230         pushl   %edx
 231
 232 1:
 233         pushl   %eax
 234         pushl   %ecx
 235         pushl   %edx
 236
 237         addl    %edx, %eax
 238         call    RangeDecoderBitDecode
 239
 240         popl    %edx
 241         popl    %ecx
 242
 243         jnc     2f
 244         movl    4(%esp), %eax
 245         orl     %eax, 8(%esp)
 246         stc
 247
 248 2:
 249         adcl    %edx, %edx
 250         popl    %eax
 251
 252         shll    $1, (%esp)
 253         loop    1b
 254
 255         popl    %ecx
 256         subl    %ecx, %edx              /* RangeDecoderBitTreeDecode */
 257         popl    %ecx                    /* RangeDecoderReverseBitTreeDecode */
 258         ret
 259
 260 LzmaLenDecode:
 261         pushl   %eax
 262         addl    $LenChoice, %eax
 263         call    RangeDecoderBitDecode
 264         popl    %eax
 265         jc      1f
 266         pushl   $0
 267         movb    $kLenNumLowBits, %cl
 268         addl    $LenLow, %eax
 269 2:
 270         movl    12(%esp), %edx
 271         shll    %cl, %edx
 272         addl    %edx, %eax
 273 3:
 274
 275         call    RangeDecoderBitTreeDecode
 276         popl    %eax
 277         addl    %eax, %edx
 278         ret
 279
 280 1:
 281         pushl   %eax
 282         addl    $LenChoice2, %eax
 283         call    RangeDecoderBitDecode
 284         popl    %eax
 285         jc      1f
 286         pushl   $kLenNumLowSymbols
 287         movb    $kLenNumMidBits, %cl
 288         addl    $LenMid, %eax
 289         jmp     2b
 290
 291 1:
 292         pushl   $(kLenNumLowSymbols + kLenNumMidSymbols)
 293         addl    $LenHigh, %eax
 294         movb    $kLenNumHighBits, %cl
 295         jmp     3b
 296
 297 WriteByte:
 298         movb    %al, prev_byte
 299         stosb
 300         incl    now_pos
 301         ret
 302
 303 /*
 304  * int LzmaDecode(CLzmaDecoderState *vs,
 305  *                const unsigned char *inStream,
 306  *                unsigned char *outStream,
 307  *                SizeT outSize);
 308  */
 309
 310 _LzmaDecodeA:
 311
 312         pushl   %ebp
 313         movl    %esp, %ebp
 314         subl    $LOCAL_SIZE, %esp
 315
 316 #ifndef ASM_FILE
 317         pushl   %esi
 318         pushl   %edi
 319         pushl   %ebx
 320
 321         movl    %eax, %ebx
 322         movl    %edx, %esi
 323         pushl   %ecx
 324 #else
 325         pushl   %edi
 326 #endif
 327
 328         cld
 329
 330 #ifdef FIXED_PROPS
 331         movl    %ebx, %edi
 332         movl    $(Literal + (LZMA_LIT_SIZE << (FIXED_LC + FIXED_LP))), %ecx
 333 #else
 334         movl    $LZMA_LIT_SIZE, %eax
 335         movb    lc, %cl
 336         addb    lp, %cl
 337         shll    %cl, %eax
 338         addl    $Literal, %eax
 339         movl    %eax, %ecx
 340         movl    probs, %edi
 341 #endif
 342
 343         movl    $(kBitModelTotal >> 1), %eax
 344
 345         rep
 346         stosl
 347
 348         popl    %edi
 349
 350         xorl    %eax, %eax
 351         movl    %eax, now_pos
 352         movl    %eax, prev_byte
 353         movl    %eax, state
 354
 355         incl    %eax
 356         movl    %eax, rep0
 357         movl    %eax, rep1
 358         movl    %eax, rep2
 359         movl    %eax, rep3
 360
 361 #ifndef FIXED_PROPS
 362         movl    %eax, %edx
 363         movb    pb, %cl
 364         shll    %cl, %edx
 365         decl    %edx
 366         movl    %edx, pos_state_mask
 367
 368         movl    %eax, %edx
 369         movb    lp, %cl
 370         shll    %cl, %edx
 371         decl    %edx
 372         movl    %edx, lit_pos_mask;
 373 #endif
 374
 375         /* RangeDecoderInit */
 376         negl    %eax
 377         movl    %eax, range
 378
 379         incl    %eax
 380         movb    $5, %cl
 381
 382 1:
 383         shll    $8, %eax
 384         lodsb
 385         loop    1b
 386
 387         movl    %eax, code
 388
 389 lzma_decode_loop:
 390         movl    now_pos, %eax
 391         cmpl    out_size, %eax
 392
 393         jb      1f
 394
 395 #ifndef ASM_FILE
 396         xorl    %eax, %eax
 397
 398         popl    %ebx
 399         popl    %edi
 400         popl    %esi
 401 #endif
 402
 403         movl    %ebp, %esp
 404         popl    %ebp
 405         ret
 406
 407 1:
 408 #ifdef FIXED_PROPS
 409         andl    $POS_STATE_MASK, %eax
 410 #else
 411         andl    pos_state_mask, %eax
 412 #endif
 413         pushl   %eax                            /* posState */
 414         movl    state, %edx
 415         shll    $kNumPosBitsMax, %edx
 416         addl    %edx, %eax
 417         pushl   %eax                            /* (state << kNumPosBitsMax) + posState */
 418
 419         call    RangeDecoderBitDecode
 420         jc      1f
 421
 422         movl    now_pos, %eax
 423
 424 #ifdef FIXED_PROPS
 425         andl    $LIT_POS_MASK, %eax
 426         shll    $FIXED_LC, %eax
 427         movl    prev_byte, %edx
 428         shrl    $(8 - FIXED_LC), %edx
 429 #else
 430         andl    lit_pos_mask, %eax
 431         movb    lc, %cl
 432         shll    %cl, %eax
 433         negb    %cl
 434         addb    $8, %cl
 435         movl    prev_byte, %edx
 436         shrl    %cl, %edx
 437 #endif
 438
 439         addl    %edx, %eax
 440         movl    $LZMA_LIT_SIZE, %edx
 441         mull    %edx
 442         addl    $Literal, %eax
 443         pushl   %eax
 444
 445         incl    %edx                    /* edx = 1 */
 446
 447         movl    rep0, %eax
 448         negl    %eax
 449         pushl   (%edi, %eax)            /* matchByte */
 450
 451         cmpb    $kNumLitStates, state
 452         jb      5f
 453
 454         /* LzmaLiteralDecodeMatch */
 455
 456 3:
 457         cmpl    $0x100, %edx
 458         jae     4f
 459
 460         xorl    %eax, %eax
 461         shlb    $1, (%esp)
 462         adcl    %eax, %eax
 463
 464         pushl   %eax
 465         pushl   %edx
 466
 467         shll    $8, %eax
 468         leal    0x100(%edx, %eax), %eax
 469         addl    12(%esp), %eax
 470         call    RangeDecoderBitDecode
 471
 472         setc    %al
 473         popl    %edx
 474         adcl    %edx, %edx
 475
 476         popl    %ecx
 477         cmpb    %cl, %al
 478         jz      3b
 479
 480 5:
 481
 482         /* LzmaLiteralDecode */
 483
 484         cmpl    $0x100, %edx
 485         jae     4f
 486
 487         pushl   %edx
 488         movl    %edx, %eax
 489         addl    8(%esp), %eax
 490         call    RangeDecoderBitDecode
 491         popl    %edx
 492         adcl    %edx, %edx
 493         jmp     5b
 494
 495 4:
 496         addl    $16, %esp
 497
 498         movb    %dl, %al
 499         call    WriteByte
 500
 501         movb    state, %al
 502         cmpb    $4, %al
 503         jae     2f
 504         xorb    %al, %al
 505         jmp     3f
 506 2:
 507         subb    $3, %al
 508         cmpb    $7, %al
 509         jb      3f
 510         subb    $3, %al
 511 3:
 512         movb    %al, state
 513         jmp     lzma_decode_loop
 514
 515 1:
 516         movl    state, %eax
 517         addl    $IsRep, %eax
 518         call    RangeDecoderBitDecode
 519         jnc     1f
 520
 521         movl    state, %eax
 522         addl    $IsRepG0, %eax
 523         call    RangeDecoderBitDecode
 524         jc      10f
 525
 526         movl    (%esp), %eax
 527         addl    $IsRep0Long, %eax
 528         call    RangeDecoderBitDecode
 529         jc      20f
 530
 531         cmpb    $7, state
 532         movb    $9, state
 533         jb      100f
 534         addb    $2, state
 535 100:
 536
 537         movl    $1, %ecx
 538
 539 3:
 540         movl    rep0, %edx
 541         negl    %edx
 542
 543 4:
 544         movb    (%edi, %edx), %al
 545         call    WriteByte
 546         loop    4b
 547
 548         popl    %eax
 549         popl    %eax
 550         jmp     lzma_decode_loop
 551
 552 10:
 553         movl    state, %eax
 554         addl    $IsRepG1, %eax
 555         call    RangeDecoderBitDecode
 556         movl    rep1, %edx
 557         jnc     100f
 558
 559         movl    state, %eax
 560         addl    $IsRepG2, %eax
 561         call    RangeDecoderBitDecode
 562         movl    rep2, %edx
 563         jnc     1000f
 564         movl    rep2, %edx
 565         xchgl   rep3, %edx
 566 1000:
 567         pushl   rep1
 568         popl    rep2
 569 100:
 570         xchg    rep0, %edx
 571         movl    %edx, rep1
 572 20:
 573
 574         movl    $RepLenCoder, %eax
 575         call    LzmaLenDecode
 576
 577         cmpb    $7, state
 578         movb    $8, state
 579         jb      100f
 580         addb    $3, state
 581 100:
 582         jmp     2f
 583
 584 1:
 585         movl    rep0, %eax
 586         xchgl   rep1, %eax
 587         xchgl   rep2, %eax
 588         movl    %eax, rep3
 589
 590         cmpb    $7, state
 591         movb    $7, state
 592         jb      10f
 593         addb    $3, state
 594 10:
 595
 596         movl    $LenCoder, %eax
 597         call    LzmaLenDecode
 598         pushl   %edx
 599
 600         movl    $(kNumLenToPosStates - 1), %eax
 601         cmpl    %eax, %edx
 602         jbe     100f
 603         movl    %eax, %edx
 604 100:
 605         movb    $kNumPosSlotBits, %cl
 606         shll    %cl, %edx
 607         leal    PosSlot(%edx), %eax
 608         call    RangeDecoderBitTreeDecode
 609
 610         movl    %edx, rep0
 611         cmpl    $kStartPosModelIndex, %edx
 612         jb      100f
 613
 614         movl    %edx, %ecx
 615         shrl    $1, %ecx
 616         decl    %ecx
 617
 618         movzbl  %dl, %eax
 619         andb    $1, %al
 620         orb     $2, %al
 621         shll    %cl, %eax
 622         movl    %eax, rep0
 623
 624         cmpl    $kEndPosModelIndex, %edx
 625         jae     200f
 626         movl    rep0, %eax
 627         addl    $(SpecPos - 1), %eax
 628         subl    %edx, %eax
 629         jmp     300f
 630 200:
 631
 632         subb    $kNumAlignBits, %cl
 633
 634         /* RangeDecoderDecodeDirectBits */
 635         xorl    %edx, %edx
 636
 637 1000:
 638         shrl    $1, range
 639         shll    $1, %edx
 640
 641         movl    range, %eax
 642         cmpl    %eax, code
 643         jb      2000f
 644         subl    %eax, code
 645         orb     $1, %dl
 646 2000:
 647
 648         cmpl    $kTopValue, %eax
 649         jae     3000f
 650         shll    $8, range
 651         shll    $8, code
 652         lodsb
 653         movb    %al, code
 654
 655 3000:
 656         loop    1000b
 657
 658         movb    $kNumAlignBits, %cl
 659         shll    %cl, %edx
 660         addl    %edx, rep0
 661
 662         movl    $Align, %eax
 663
 664 300:
 665         call    RangeDecoderReverseBitTreeDecode
 666         addl    %ecx, rep0
 667
 668 100:
 669         incl    rep0
 670         popl    %edx
 671
 672 2:
 673
 674         addl    $kMatchMinLen, %edx
 675         movl    %edx, %ecx
 676
 677         jmp     3b