Subversion Repositories Kolibri OS

Rev

Rev 893 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
589 diamond 1 
; LZMA decoder for *.7z archives.
2 
; Based on C decoder in LZMA SDK (c) Igor Pavlov.
3 
; Portions by Diamond, 2006, 2007.
4 
lzma_decoder:
5 
virtual at 0
6 
.outStream      rb      streamInfo.size
7 
.inStream       dd      ?
8 
 
9 
; RangeDecoder data
10 
.inLen          dd      ?
11 
.inPtr          dd      ?
12 
.code           dd      ?
13 
.range          dd      ?
14 
 
15 
; parameters
16 
.pb             db      ?       ; pos state bits (0 - 4)
17 
.lp             db      ?       ; literal pos state bits (0 - 4)
18 
.lc             db      ?       ; literal context bits (0 - 8)
19 
.previousByte   db      ?
20 
.posStateMask   dd      ?       ; (1 shl .pb)-1
21 
.literalPosMask dd      ?       ; (1 shl .lp)-1
22 
 
23 
; constants
24 
.kNumPosBitsMax	=	4
25 
.kNumPosStatesMax =	(1 shl .kNumPosBitsMax)
26 
 
27 
.kLenNumLowBits         =       3
28 
.kLenNumLowSymbols      =       (1 shl .kLenNumLowBits)
29 
.kLenNumMidBits         =       3
30 
.kLenNumMidSymbols      =       (1 shl .kLenNumMidBits)
31 
.kLenNumHighBits        =       8
32 
.kLenNumHighSymbols     =       (1 shl .kLenNumHighBits)
33 
 
34 
.LenChoice	=	0
35 
.LenChoice2	=	1
36 
.LenLow		=	2
37 
.LenMid		=	(.LenLow + (.kNumPosStatesMax shl .kLenNumLowBits))
38 
.LenHigh	=	(.LenMid + (.kNumPosStatesMax shl .kLenNumMidBits))
39 
.kNumLenProbs	=	(.LenHigh + .kLenNumHighSymbols)
40 
 
41 
.kNumStates	=	12
42 
.kNumLitStates	=	7
43 
.kStartPosModelIndex =	4
44 
.kEndPosModelIndex =	14
45 
.kNumFullDistances =	(1 shl (.kEndPosModelIndex/2))
46 
.kNumPosSlotBits =	6
47 
.kNumLenToPosStates =	4
48 
.kNumAlignBits	=	4
49 
.kAlignTableSize =	(1 shl .kNumAlignBits)
50 
.kMatchMinLen	=	2
51 
 
52 
.IsMatch	=	0
53 
.IsRep		=	(.IsMatch + (.kNumStates shl .kNumPosBitsMax))
54 
.IsRepG0	=	(.IsRep + .kNumStates)
55 
.IsRepG1	=	(.IsRepG0 + .kNumStates)
56 
.IsRepG2	=	(.IsRepG1 + .kNumStates)
57 
.IsRep0Long	=	(.IsRepG2 + .kNumStates)
58 
.PosSlot	=	(.IsRep0Long + (.kNumStates shl .kNumPosBitsMax))
59 
.SpecPos	=	(.PosSlot + (.kNumLenToPosStates shl .kNumPosSlotBits))
60 
.Align_		=	(.SpecPos + .kNumFullDistances - .kEndPosModelIndex)
61 
.Lencoder	=	(.Align_ + .kAlignTableSize)
62 
.RepLencoder	=	(.Lencoder + .kNumLenProbs)
63 
.Literal	=	(.RepLencoder + .kNumLenProbs)
64 
 
65 
LZMA_BASE_SIZE	=	1846	; must be ==Literal
66 
LZMA_LIT_SIZE	=	768
67 
 
68 
.kNumTopBits	=	24
69 
.kTopValue	=	(1 shl .kNumTopBits)
70 
 
71 
.kNumBitModelTotalBits =	11
72 
.kBitModelTotal	=	(1 shl .kNumBitModelTotalBits)
73 
.kNumMoveBits	=	5
74 
 
75 
; variables
76 
.continue       dd      ?
77 
.ecx            dd      ?
78 
.outEnd         dd      ?
79 
.dictSize       dd      ?
80 
.state          dd      ?
81 
.rep0           dd      ?
82 
.rep1           dd      ?
83 
.rep2           dd      ?
84 
.rep3           dd      ?
85 
.p              rd      LZMA_BASE_SIZE
86 
.basesize = $
87 
;               rd      LZMA_LIT_SIZE shl (.lc+.lp)
88 
end virtual
89 
 
90 
.fillBuf:
91 
        mov     ebp, eax
92 
        mov     ebx, [ebp+.state]
93 
	jecxz	.nodata
94 
        add     ecx, edi
95 
        mov     [ebp+.outEnd], ecx
96 
        mov     esi, [ebp+.inPtr]
97 
        jmp     [ebp+.continue]
98 
.nodata:
99 
	popad
100 
	ret
101 
.start:
102 
        mov     eax, [ebp+.inStream]
103 
        call    fillBuf
104 
        mov     esi, [eax+streamInfo.bufPtr]
105 
        mov     eax, [eax+streamInfo.bufDataLen]
106 
        sub     eax, 5
107 
        jb      return.err
108 
        mov     [ebp+.inLen], eax
109 
        inc     esi
110 
	lodsd
111 
        bswap   eax
112 
	mov	[ebp+.code], eax
113 
	or	[ebp+.range], -1
114 
.main_loop:
115 
	cmp	edi, [ebp+.outEnd]
116 
	jae	.main_loop_done
117 
	mov	edx, edi
118 
	and	edx, [ebp+.posStateMask]
119 
	mov	eax, ebx
120 
	shl	eax, .kNumPosBitsMax
121 
        add     eax, edx
122 
	lea	eax, [ebp + .p + .IsMatch*4 + eax*4]
123 
	call	.RangeDecoderBitDecode
124 
	jc	.1
125 
	movzx	eax, [ebp+.previousByte]
126 
	mov	ah, dl
127 
	and	ah, byte [ebp+.literalPosMask]
128 
        mov     cl, 8
129 
        sub     cl, [ebp+.lc]
130 
	shr	eax, cl
131 
	imul	eax, LZMA_LIT_SIZE*4
132 
	lea	eax, [ebp + eax + .p+.Literal*4]
133 
	cmp	ebx, .kNumLitStates
134 
	jb	.literal
893 diamond 135 
	mov	edx, edi
589 diamond 136 
	sub	edx, [ebp+.rep0]
893 diamond 137 
	cmp	edx, [ebp+streamInfo.bufPtr]
138 
	jb	.before_buf
139 
@@:
140 
	mov	dl, [edx]
589 diamond 141 
	call	.LzmaLiteralDecodeMatch
893 diamond 142 
	jmp	.got_byte
143 
.before_buf:
144 
	add	edx, [ebp+streamInfo.bufSize]
145 
	cmp	edx, [ebp+streamInfo.bufPtr]
146 
	jb	return.err
147 
	jmp	@b
589 diamond 148 
.literal:
149 
	call	.LzmaLiteralDecode
893 diamond 150 
.got_byte:
589 diamond 151 
	mov	[ebp+.previousByte], al
152 
	stosb
153 
	mov	al, bl
154 
	cmp	bl, 4
155 
	jb	@f
156 
	mov	al, 3
157 
	cmp	bl, 10
158 
	jb	@f
159 
	mov	al, 6
160 
@@:	sub	bl, al
161 
	jmp	.main_loop
162 
.1:
163 
	lea	eax, [ebp + .p + .IsRep*4 + ebx*4]
164 
	call	.RangeDecoderBitDecode
165 
	jnc	.10
166 
	lea	eax, [ebp + .p + .IsRepG0*4 + ebx*4]
167 
	call	.RangeDecoderBitDecode
168 
	jc	.111
169 
	mov	eax, ebx
170 
	shl	eax, .kNumPosBitsMax
171 
        add     eax, edx
172 
	lea	eax, [ebp + .p + .IsRep0Long*4 + eax*4]
173 
	call	.RangeDecoderBitDecode
174 
	jc	.1101
175 
	cmp	bl, 7
176 
	setae	bl
177 
	lea	ebx, [9 + ebx + ebx]
893 diamond 178 
	mov	edx, edi
589 diamond 179 
	sub	edx, [ebp+.rep0]
893 diamond 180 
	cmp	edx, [ebp+streamInfo.bufPtr]
181 
	jae	@f
182 
	add	edx, [ebp+streamInfo.bufSize]
183 
	cmp	edx, [ebp+streamInfo.bufPtr]
184 
	jb	return.err
185 
@@:
186 
	mov	al, [edx]
589 diamond 187 
	stosb
188 
	mov	[ebp+.previousByte], al
189 
	jmp	.main_loop
190 
.111:
191 
	lea	eax, [ebp + .p + .IsRepG1*4 + ebx*4]
192 
	call	.RangeDecoderBitDecode
193 
	mov	eax, [ebp+.rep1]
194 
	jnc	.l3
195 
.l1:
196 
	lea	eax, [ebp + .p + .IsRepG2*4 + ebx*4]
197 
	call	.RangeDecoderBitDecode
198 
	mov	eax, [ebp+.rep2]
199 
	jnc	.l2
200 
	xchg	[ebp+.rep3], eax
201 
.l2:
202 
	push	[ebp+.rep1]
203 
	pop	[ebp+.rep2]
204 
.l3:
205 
	xchg	eax, [ebp+.rep0]
206 
	mov	[ebp+.rep1], eax
207 
.1101:
208 
	lea	eax, [ebp + .p + .RepLencoder*4]
209 
	call	.LzmaLenDecode
210 
	cmp	bl, 7
211 
	setc	bl
212 
	adc	bl, bl
213 
	xor	bl, 3
214 
	add	bl, 8
215 
	jmp	.repmovsb
216 
.10:
217 
	mov	eax, [ebp+.rep0]
218 
	xchg	eax, [ebp+.rep1]
219 
	xchg	eax, [ebp+.rep2]
220 
	xchg	eax, [ebp+.rep3]
221 
	cmp	bl, 7
222 
	setc	bl
223 
	adc	bl, bl
224 
	xor	bl, 3
225 
	add	bl, 7
226 
	lea	eax, [ebp + .p + .Lencoder*4]
227 
	call	.LzmaLenDecode
228 
	mov	eax, .kNumLenToPosStates-1
229 
	cmp	eax, ecx
230 
	jb	@f
231 
	mov	eax, ecx
232 
@@:
233 
	push	ecx
234 
	mov	ecx, .kNumPosSlotBits
235 
	shl	eax, cl
236 
        lea     eax, [ebp + .p+.PosSlot*4 + eax*4]
237 
	call	.RangeDecoderBitTreeDecode
238 
	mov	[ebp+.rep0], ecx
239 
	cmp	ecx, .kStartPosModelIndex
240 
	jb	.l6
241 
	push	ecx
242 
	mov	eax, ecx
243 
	and	eax, 1
244 
	shr	ecx, 1
245 
	or	eax, 2
246 
	dec	ecx
247 
	shl	eax, cl
248 
	mov	[ebp+.rep0], eax
249 
	pop	edx
250 
	cmp	edx, .kEndPosModelIndex
251 
	jae	.l5
252 
	sub	eax, edx
253 
        lea     eax, [ebp + .p + (.SpecPos - 1)*4 + eax*4]
254 
	call	.RangeDecoderReverseBitTreeDecode
255 
	add	[ebp+.rep0], ecx
256 
	jmp	.l6
257 
.l5:
258 
	sub	ecx, .kNumAlignBits
259 
	call	.RangeDecoderDecodeDirectBits
260 
	mov	ecx, .kNumAlignBits
261 
	shl	eax, cl
262 
	add	[ebp+.rep0], eax
263 
	lea	eax, [ebp+.p+.Align_*4]
264 
	call	.RangeDecoderReverseBitTreeDecode
265 
	add	[ebp+.rep0], ecx
266 
.l6:
267 
	pop	ecx
268 
	inc	[ebp+.rep0]
269 
	jz	.main_loop_done
270 
.repmovsb:
271 
	add	ecx, .kMatchMinLen
272 
.repmovsbz:
273 
	push	esi
274 
.repmovsbr:
275 
        mov     eax, [ebp+.rep0]
276 
        cmp     eax, [ebp+.dictSize]
920 diamond 277 
        ja      return.err
589 diamond 278 
	mov	esi, edi
279 
	sub	esi, eax
280 
        mov     eax, [ebp+streamInfo.bufPtr]
281 
        sub     eax, esi
282 
        ja      .repmovsb0
283 
	mov	eax, [ebp+.outEnd]
284 
        sub     eax, edi
920 diamond 285 
        jz      .done1
589 diamond 286 
        push    ecx
287 
        cmp     ecx, eax
288 
        jb      @f
289 
        mov     ecx, eax
290 
@@:
291 
        sub     [esp], ecx
292 
	rep	movsb
293 
        pop     ecx
294 
        jz      .repmovsb1
920 diamond 295 
.done1:
589 diamond 296 
        pop     [ebp+.inPtr]
297 
	mov	[ebp+.state], ebx
298 
        mov     [ebp+.ecx], ecx
299 
        mov     [ebp+.continue], .restart_repmovsb
300 
        popad
301 
        ret
302 
.repmovsb0:
303 
	mov	edx, [ebp+.dictSize]
920 diamond 304 
;	cmp	edx, [ebp+streamInfo.bufSize]
305 
;	jnz	return.err
589 diamond 306 
        add     esi, edx
307 
        push    ecx
308 
        cmp     ecx, eax
309 
        jb      @f
310 
        mov     ecx, eax
311 
@@:
312 
	mov	eax, [ebp+.outEnd]
313 
	sub	eax, edi
920 diamond 314 
	jz      .done2
589 diamond 315 
	cmp	ecx, eax
316 
	jb	@f
317 
	mov	ecx, eax
318 
@@:
319 
        sub     [esp], ecx
320 
        rep     movsb
321 
        pop     ecx
322 
        jnz     .repmovsbr
323 
.repmovsb1:
324 
        pop     esi
325 
        mov     al, [edi-1]
326 
        mov     [ebp+.previousByte], al
327 
        jmp     .main_loop
920 diamond 328 
.done2:
329 
	pop	ecx
330 
	jmp	.done1
589 diamond 331 
.main_loop_done:
332 
	mov	[ebp+.state], ebx
333 
        mov     [ebp+.continue], .main_loop
334 
        mov     [ebp+.inPtr], esi
335 
        popad
336 
	ret
337 
.restart_repmovsb:
338 
        mov     ecx, [ebp+.ecx]
339 
        jmp     .repmovsbz
340 
 
341 
.RangeDecoderBitDecode:
342 
; in: eax->prob
343 
; out: CF=bit; destroys eax
344 
	push	edx
345 
	mov	edx, [ebp+.range]
346 
	shr	edx, .kNumBitModelTotalBits
347 
	imul	edx, [eax]
348 
	cmp	[ebp+.code], edx
349 
	jae	.ae
350 
	mov	[ebp+.range], edx
351 
	mov	edx, .kBitModelTotal
352 
	sub	edx, [eax]
353 
	shr	edx, .kNumMoveBits
354 
	add	[eax], edx
355 
	clc
356 
.n:
357 
	lahf
358 
	cmp	[ebp+.range], .kTopValue
359 
	jae	@f
360 
	shl	[ebp+.range], 8
361 
	shl	[ebp+.code], 8
362 
        sub     [ebp+.inLen], 1
363 
        js      .refill1
364 
.refilled1:
365 
	lodsb
366 
	mov	byte [ebp+.code], al
367 
@@:
368 
	sahf
369 
	pop	edx
370 
	ret
371 
.ae:
372 
	sub	[ebp+.range], edx
373 
	sub	[ebp+.code], edx
374 
	mov	edx, [eax]
375 
	shr	edx, .kNumMoveBits
376 
	sub	[eax], edx
377 
	stc
378 
	jmp	.n
379 
 
380 
.refill1:
381 
        push    eax
382 
        call    .refill
383 
        pop     eax
384 
        jmp     .refilled1
385 
 
386 
.refill:
387 
        mov     eax, [ebp+.inStream]
388 
        cmp     dword [eax+streamInfo.fullSize+4], 0
389 
        jnz     @f
390 
        cmp     dword [eax+streamInfo.fullSize], 0
391 
        jz      return.err
392 
@@:
393 
        call    fillBuf
394 
        mov     esi, [eax+streamInfo.bufPtr]
395 
        mov     eax, [eax+streamInfo.bufDataLen]
396 
        dec     eax
397 
        js      return.err
398 
        mov     [ebp+.inLen], eax
399 
        ret
400 
 
401 
.refill2:
402 
        call    .refill
403 
        jmp     .refilled2
404 
 
405 
.RangeDecoderDecodeDirectBits:
406 
; in: ecx=numTotalBits
407 
; out: eax=result; destroys edx
408 
	xor	eax, eax
409 
.l:
410 
	shr	[ebp+.range], 1
411 
	shl	eax, 1
412 
	mov	edx, [ebp+.code]
413 
	sub	edx, [ebp+.range]
414 
	jb	@f
415 
	mov	[ebp+.code], edx
416 
	or	eax, 1
417 
@@:
418 
	cmp	[ebp+.range], .kTopValue
419 
	jae	@f
420 
	shl	[ebp+.range], 8
421 
	shl	[ebp+.code], 8
422 
	push	eax
423 
        dec     [ebp+.inLen]
424 
        js      .refill2
425 
.refilled2:
426 
	lodsb
427 
	mov	byte [ebp+.code], al
428 
	pop	eax
429 
@@:
430 
	loop	.l
431 
	ret
432 
 
433 
.LzmaLiteralDecode:
434 
; in: eax->probs
435 
; out: al=byte; destroys edx
436 
	push	ecx
437 
	mov	ecx, 1
438 
@@:
439 
	push	eax
440 
	lea	eax, [eax+ecx*4]
441 
	call	.RangeDecoderBitDecode
442 
	pop	eax
443 
	adc	cl, cl
444 
	jnc	@b
445 
.LzmaLiteralDecode.ret:
446 
	mov	al, cl
447 
	pop	ecx
448 
	ret
449 
.LzmaLiteralDecodeMatch:
450 
; in: eax->probs, dl=matchByte
451 
; out: al=byte; destroys edx
452 
	push	ecx
453 
	mov	ecx, 1
454 
.LzmaLiteralDecodeMatch.1:
455 
	add	dl, dl
456 
	setc	ch
457 
	push	eax
458 
	lea	eax, [eax+ecx*4+0x100*4]
459 
	call	.RangeDecoderBitDecode
460 
	pop	eax
461 
	adc	cl, cl
462 
	jc	.LzmaLiteralDecode.ret
463 
	xor	ch, cl
464 
	test	ch, 1
465 
	mov	ch, 0
466 
	jnz	@b
467 
	jmp	.LzmaLiteralDecodeMatch.1
468 
 
469 
.LzmaLenDecode:
470 
; in: eax->prob, edx=posState
471 
; out: ecx=len
472 
	push	eax
473 
	add	eax, .LenChoice*4
474 
	call	.RangeDecoderBitDecode
475 
	pop	eax
476 
	jnc	.0
477 
	push	eax
478 
	add	eax, .LenChoice2*4
479 
	call	.RangeDecoderBitDecode
480 
	pop	eax
481 
	jc	@f
482 
	mov	ecx, .kLenNumMidBits
483 
	shl	edx, cl
484 
	lea	eax, [eax + .LenMid*4 + edx*4]
485 
	call	.RangeDecoderBitTreeDecode
486 
	add	ecx, .kLenNumLowSymbols
487 
	ret
488 
@@:
489 
	add	eax, .LenHigh*4
490 
	mov	ecx, .kLenNumHighBits
491 
	call	.RangeDecoderBitTreeDecode
492 
	add	ecx, .kLenNumLowSymbols + .kLenNumMidSymbols
493 
	ret
494 
.0:
495 
	mov	ecx, .kLenNumLowBits
496 
	shl	edx, cl
497 
	lea	eax, [eax + .LenLow*4 + edx*4]
498 
.RangeDecoderBitTreeDecode:
499 
; in: eax->probs,ecx=numLevels
500 
; out: ecx=length; destroys edx
501 
	push	ebx
502 
	mov	edx, 1
503 
	mov	ebx, edx
504 
@@:
505 
	push	eax
506 
	lea	eax, [eax+edx*4]
507 
	call	.RangeDecoderBitDecode
508 
	pop	eax
509 
	adc	dl, dl
510 
	add	bl, bl
511 
	loop	@b
512 
	sub	dl, bl
513 
	pop	ebx
514 
	mov	ecx, edx
515 
	ret
516 
.RangeDecoderReverseBitTreeDecode:
517 
; in: eax->probs,ecx=numLevels
518 
; out: ecx=length; destroys edx
519 
	push	ebx ecx
520 
	mov	edx, 1
521 
	xor	ebx, ebx
522 
@@:
523 
	push	eax
524 
	lea	eax, [eax+edx*4]
525 
	call	.RangeDecoderBitDecode
526 
	lahf
527 
	adc	edx, edx
528 
	sahf
529 
	rcr	ebx, 1
530 
	pop	eax
531 
	loop	@b
532 
	pop	ecx
533 
	rol	ebx, cl
534 
	mov	ecx, ebx
535 
	pop	ebx
536 
	ret
537 
 
538 
; LZMA parameters:
539 
;       db      lc + 9 * (lp + 5 * pb)
540 
;       dd      dictionarySize
541 
 
542 
lzma_get_buf_size:
543 
        cmp     dword [esi-4], 5
544 
        jb      return.err
545 
        push    ecx
546 
        lodsb
547 
        aam     9
548 
        mov     cl, al
549 
        mov     al, ah
550 
        aam     5
551 
        add     cl, al
552 
        mov     eax, LZMA_LIT_SIZE
553 
        shl     eax, cl
554 
        lea     eax, [lzma_decoder.basesize+eax*4]
555 
        pop     ecx
556 
        mov     edx, [esi]
557 
        ret
558 
 
559 
lzma_init_decoder:
560 
        lodsb
561 
        aam     9
562 
        mov     [ebp+lzma_decoder.lc], al
563 
        mov     al, ah
564 
        aam     5
565 
        mov     [ebp+lzma_decoder.lp], al
566 
        mov     [ebp+lzma_decoder.pb], ah
567 
        cmp     ah, lzma_decoder.kNumPosBitsMax
568 
        ja      return.err
569 
        mov     cl, ah
570 
        lodsd
571 
        mov     [ebp+lzma_decoder.dictSize], eax
572 
        push    1
573 
        pop     eax
574 
        shl     eax, cl
575 
        dec     eax
576 
        mov     [ebp+lzma_decoder.posStateMask], eax
577 
        mov     cl, [ebp+lzma_decoder.lp]
578 
        push    1
579 
        pop     eax
580 
        shl     eax, cl
581 
        dec     eax
582 
        mov     [ebp+lzma_decoder.literalPosMask], eax
583 
        mov     [ebp+streamInfo.fillBuf], lzma_decoder.fillBuf
584 
        mov     [ebp+lzma_decoder.continue], lzma_decoder.start
585 
        xor     eax, eax
586 
        mov     [ebp+lzma_decoder.previousByte], al
587 
        mov     [ebp+lzma_decoder.state], eax
588 
        inc     eax
589 
        lea     edi, [ebp+lzma_decoder.rep0]
590 
        stosd
591 
        stosd
592 
        stosd
593 
        mov     eax, LZMA_LIT_SIZE
594 
        mov     cl, [ebp+lzma_decoder.lc]
595 
        add     cl, [ebp+lzma_decoder.lp]
596 
        shl     eax, cl
597 
        lea     ecx, [eax+lzma_decoder.Literal]
598 
	mov	eax, lzma_decoder.kBitModelTotal/2
599 
	lea	edi, [ebp+lzma_decoder.p]
600 
	rep	stosd
601 
        ret