Subversion Repositories Kolibri OS

Rev

Rev 589 | Rev 920 | 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]
277 
        jae     return.err
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
285 
        push    ecx
286 
        cmp     ecx, eax
287 
        jb      @f
288 
        mov     ecx, eax
289 
@@:
290 
        sub     [esp], ecx
291 
	rep	movsb
292 
        pop     ecx
293 
        jz      .repmovsb1
294 
        pop     [ebp+.inPtr]
295 
	mov	[ebp+.state], ebx
296 
        mov     [ebp+.ecx], ecx
297 
        mov     [ebp+.continue], .restart_repmovsb
298 
        popad
299 
        ret
300 
.repmovsb0:
301 
	mov	edx, [ebp+.dictSize]
302 
	cmp	edx, [ebp+streamInfo.bufSize]
303 
	jnz	return.err
304 
        add     esi, edx
305 
        push    ecx
306 
        cmp     ecx, eax
307 
        jb      @f
308 
        mov     ecx, eax
309 
@@:
310 
	mov	eax, [ebp+.outEnd]
311 
	sub	eax, edi
312 
	cmp	ecx, eax
313 
	jb	@f
314 
	mov	ecx, eax
315 
@@:
316 
        sub     [esp], ecx
317 
        rep     movsb
318 
        pop     ecx
319 
        jnz     .repmovsbr
320 
.repmovsb1:
321 
        pop     esi
322 
        mov     al, [edi-1]
323 
        mov     [ebp+.previousByte], al
324 
        jmp     .main_loop
325 
.main_loop_done:
326 
	mov	[ebp+.state], ebx
327 
        mov     [ebp+.continue], .main_loop
328 
        mov     [ebp+.inPtr], esi
329 
        popad
330 
	ret
331 
.restart_repmovsb:
332 
        mov     ecx, [ebp+.ecx]
333 
        jmp     .repmovsbz
334 
 
335 
.RangeDecoderBitDecode:
336 
; in: eax->prob
337 
; out: CF=bit; destroys eax
338 
	push	edx
339 
	mov	edx, [ebp+.range]
340 
	shr	edx, .kNumBitModelTotalBits
341 
	imul	edx, [eax]
342 
	cmp	[ebp+.code], edx
343 
	jae	.ae
344 
	mov	[ebp+.range], edx
345 
	mov	edx, .kBitModelTotal
346 
	sub	edx, [eax]
347 
	shr	edx, .kNumMoveBits
348 
	add	[eax], edx
349 
	clc
350 
.n:
351 
	lahf
352 
	cmp	[ebp+.range], .kTopValue
353 
	jae	@f
354 
	shl	[ebp+.range], 8
355 
	shl	[ebp+.code], 8
356 
        sub     [ebp+.inLen], 1
357 
        js      .refill1
358 
.refilled1:
359 
	lodsb
360 
	mov	byte [ebp+.code], al
361 
@@:
362 
	sahf
363 
	pop	edx
364 
	ret
365 
.ae:
366 
	sub	[ebp+.range], edx
367 
	sub	[ebp+.code], edx
368 
	mov	edx, [eax]
369 
	shr	edx, .kNumMoveBits
370 
	sub	[eax], edx
371 
	stc
372 
	jmp	.n
373 
 
374 
.refill1:
375 
        push    eax
376 
        call    .refill
377 
        pop     eax
378 
        jmp     .refilled1
379 
 
380 
.refill:
381 
        mov     eax, [ebp+.inStream]
382 
        cmp     dword [eax+streamInfo.fullSize+4], 0
383 
        jnz     @f
384 
        cmp     dword [eax+streamInfo.fullSize], 0
385 
        jz      return.err
386 
@@:
387 
        call    fillBuf
388 
        mov     esi, [eax+streamInfo.bufPtr]
389 
        mov     eax, [eax+streamInfo.bufDataLen]
390 
        dec     eax
391 
        js      return.err
392 
        mov     [ebp+.inLen], eax
393 
        ret
394 
 
395 
.refill2:
396 
        call    .refill
397 
        jmp     .refilled2
398 
 
399 
.RangeDecoderDecodeDirectBits:
400 
; in: ecx=numTotalBits
401 
; out: eax=result; destroys edx
402 
	xor	eax, eax
403 
.l:
404 
	shr	[ebp+.range], 1
405 
	shl	eax, 1
406 
	mov	edx, [ebp+.code]
407 
	sub	edx, [ebp+.range]
408 
	jb	@f
409 
	mov	[ebp+.code], edx
410 
	or	eax, 1
411 
@@:
412 
	cmp	[ebp+.range], .kTopValue
413 
	jae	@f
414 
	shl	[ebp+.range], 8
415 
	shl	[ebp+.code], 8
416 
	push	eax
417 
        dec     [ebp+.inLen]
418 
        js      .refill2
419 
.refilled2:
420 
	lodsb
421 
	mov	byte [ebp+.code], al
422 
	pop	eax
423 
@@:
424 
	loop	.l
425 
	ret
426 
 
427 
.LzmaLiteralDecode:
428 
; in: eax->probs
429 
; out: al=byte; destroys edx
430 
	push	ecx
431 
	mov	ecx, 1
432 
@@:
433 
	push	eax
434 
	lea	eax, [eax+ecx*4]
435 
	call	.RangeDecoderBitDecode
436 
	pop	eax
437 
	adc	cl, cl
438 
	jnc	@b
439 
.LzmaLiteralDecode.ret:
440 
	mov	al, cl
441 
	pop	ecx
442 
	ret
443 
.LzmaLiteralDecodeMatch:
444 
; in: eax->probs, dl=matchByte
445 
; out: al=byte; destroys edx
446 
	push	ecx
447 
	mov	ecx, 1
448 
.LzmaLiteralDecodeMatch.1:
449 
	add	dl, dl
450 
	setc	ch
451 
	push	eax
452 
	lea	eax, [eax+ecx*4+0x100*4]
453 
	call	.RangeDecoderBitDecode
454 
	pop	eax
455 
	adc	cl, cl
456 
	jc	.LzmaLiteralDecode.ret
457 
	xor	ch, cl
458 
	test	ch, 1
459 
	mov	ch, 0
460 
	jnz	@b
461 
	jmp	.LzmaLiteralDecodeMatch.1
462 
 
463 
.LzmaLenDecode:
464 
; in: eax->prob, edx=posState
465 
; out: ecx=len
466 
	push	eax
467 
	add	eax, .LenChoice*4
468 
	call	.RangeDecoderBitDecode
469 
	pop	eax
470 
	jnc	.0
471 
	push	eax
472 
	add	eax, .LenChoice2*4
473 
	call	.RangeDecoderBitDecode
474 
	pop	eax
475 
	jc	@f
476 
	mov	ecx, .kLenNumMidBits
477 
	shl	edx, cl
478 
	lea	eax, [eax + .LenMid*4 + edx*4]
479 
	call	.RangeDecoderBitTreeDecode
480 
	add	ecx, .kLenNumLowSymbols
481 
	ret
482 
@@:
483 
	add	eax, .LenHigh*4
484 
	mov	ecx, .kLenNumHighBits
485 
	call	.RangeDecoderBitTreeDecode
486 
	add	ecx, .kLenNumLowSymbols + .kLenNumMidSymbols
487 
	ret
488 
.0:
489 
	mov	ecx, .kLenNumLowBits
490 
	shl	edx, cl
491 
	lea	eax, [eax + .LenLow*4 + edx*4]
492 
.RangeDecoderBitTreeDecode:
493 
; in: eax->probs,ecx=numLevels
494 
; out: ecx=length; destroys edx
495 
	push	ebx
496 
	mov	edx, 1
497 
	mov	ebx, edx
498 
@@:
499 
	push	eax
500 
	lea	eax, [eax+edx*4]
501 
	call	.RangeDecoderBitDecode
502 
	pop	eax
503 
	adc	dl, dl
504 
	add	bl, bl
505 
	loop	@b
506 
	sub	dl, bl
507 
	pop	ebx
508 
	mov	ecx, edx
509 
	ret
510 
.RangeDecoderReverseBitTreeDecode:
511 
; in: eax->probs,ecx=numLevels
512 
; out: ecx=length; destroys edx
513 
	push	ebx ecx
514 
	mov	edx, 1
515 
	xor	ebx, ebx
516 
@@:
517 
	push	eax
518 
	lea	eax, [eax+edx*4]
519 
	call	.RangeDecoderBitDecode
520 
	lahf
521 
	adc	edx, edx
522 
	sahf
523 
	rcr	ebx, 1
524 
	pop	eax
525 
	loop	@b
526 
	pop	ecx
527 
	rol	ebx, cl
528 
	mov	ecx, ebx
529 
	pop	ebx
530 
	ret
531 
 
532 
; LZMA parameters:
533 
;       db      lc + 9 * (lp + 5 * pb)
534 
;       dd      dictionarySize
535 
 
536 
lzma_get_buf_size:
537 
        cmp     dword [esi-4], 5
538 
        jb      return.err
539 
        push    ecx
540 
        lodsb
541 
        aam     9
542 
        mov     cl, al
543 
        mov     al, ah
544 
        aam     5
545 
        add     cl, al
546 
        mov     eax, LZMA_LIT_SIZE
547 
        shl     eax, cl
548 
        lea     eax, [lzma_decoder.basesize+eax*4]
549 
        pop     ecx
550 
        mov     edx, [esi]
551 
        ret
552 
 
553 
lzma_init_decoder:
554 
        lodsb
555 
        aam     9
556 
        mov     [ebp+lzma_decoder.lc], al
557 
        mov     al, ah
558 
        aam     5
559 
        mov     [ebp+lzma_decoder.lp], al
560 
        mov     [ebp+lzma_decoder.pb], ah
561 
        cmp     ah, lzma_decoder.kNumPosBitsMax
562 
        ja      return.err
563 
        mov     cl, ah
564 
        lodsd
565 
        mov     [ebp+lzma_decoder.dictSize], eax
566 
        push    1
567 
        pop     eax
568 
        shl     eax, cl
569 
        dec     eax
570 
        mov     [ebp+lzma_decoder.posStateMask], eax
571 
        mov     cl, [ebp+lzma_decoder.lp]
572 
        push    1
573 
        pop     eax
574 
        shl     eax, cl
575 
        dec     eax
576 
        mov     [ebp+lzma_decoder.literalPosMask], eax
577 
        mov     [ebp+streamInfo.fillBuf], lzma_decoder.fillBuf
578 
        mov     [ebp+lzma_decoder.continue], lzma_decoder.start
579 
        xor     eax, eax
580 
        mov     [ebp+lzma_decoder.previousByte], al
581 
        mov     [ebp+lzma_decoder.state], eax
582 
        inc     eax
583 
        lea     edi, [ebp+lzma_decoder.rep0]
584 
        stosd
585 
        stosd
586 
        stosd
587 
        mov     eax, LZMA_LIT_SIZE
588 
        mov     cl, [ebp+lzma_decoder.lc]
589 
        add     cl, [ebp+lzma_decoder.lp]
590 
        shl     eax, cl
591 
        lea     ecx, [eax+lzma_decoder.Literal]
592 
	mov	eax, lzma_decoder.kBitModelTotal/2
593 
	lea	edi, [ebp+lzma_decoder.p]
594 
	rep	stosd
595 
        ret