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