455 lines
13 KiB
NASM
455 lines
13 KiB
NASM
|
title "Compression and Decompression Engines"
|
|||
|
|
;++
|
|||
|
|
;
|
|||
|
|
; Copyright (c) 1989 Microsoft Corporation
|
|||
|
|
;
|
|||
|
|
; Module Name:
|
|||
|
|
;
|
|||
|
|
; lzntx86.asm
|
|||
|
|
;
|
|||
|
|
; Abstract:
|
|||
|
|
;
|
|||
|
|
; This module implements the compression and decompression engines needed
|
|||
|
|
; to support file system compression. Functions are provided to
|
|||
|
|
; compress a buffer and decompress a buffer.
|
|||
|
|
;
|
|||
|
|
; Author:
|
|||
|
|
;
|
|||
|
|
; Mark Zbikowski (markz) 15-Mar-1994
|
|||
|
|
;
|
|||
|
|
; Environment:
|
|||
|
|
;
|
|||
|
|
; Any mode.
|
|||
|
|
;
|
|||
|
|
; Revision History:
|
|||
|
|
;
|
|||
|
|
; 15-Mar-1994 markz
|
|||
|
|
;
|
|||
|
|
; 386 version created
|
|||
|
|
;
|
|||
|
|
;--
|
|||
|
|
.386p
|
|||
|
|
|
|||
|
|
.xlist
|
|||
|
|
include ks386.inc
|
|||
|
|
include callconv.inc ; calling convention macros
|
|||
|
|
.list
|
|||
|
|
|
|||
|
|
IFDEF NTOS_KERNEL_RUNTIME
|
|||
|
|
_PAGE SEGMENT DWORD PUBLIC 'CODE'
|
|||
|
|
ELSE
|
|||
|
|
_TEXT SEGMENT DWORD PUBLIC 'CODE'
|
|||
|
|
ENDIF
|
|||
|
|
ASSUME DS:FLAT, ES:FLAT, SS:NOTHING, FS:NOTHING, GS:NOTHING
|
|||
|
|
|
|||
|
|
page
|
|||
|
|
subttl "Decompress a buffer"
|
|||
|
|
|
|||
|
|
;++
|
|||
|
|
;
|
|||
|
|
; NTSTATUS
|
|||
|
|
; LZNT1DecompressChunk (
|
|||
|
|
; OUT PUCHAR UncompressedBuffer,
|
|||
|
|
; IN PUCHAR EndOfUncompressedBufferPlus1,
|
|||
|
|
; IN PUCHAR CompressedBuffer,
|
|||
|
|
; IN PUCHAR EndOfCompressedBufferPlus1,
|
|||
|
|
; OUT PULONG FinalUncompressedChunkSize
|
|||
|
|
; )
|
|||
|
|
;
|
|||
|
|
; Routine Description:
|
|||
|
|
;
|
|||
|
|
; This function decodes a stream of compression tokens and places the
|
|||
|
|
; resultant output into the destination buffer. The format of the input
|
|||
|
|
; is described ..\lznt1.c. As the input is decoded, checks are made to
|
|||
|
|
; ensure that no data is read past the end of the compressed input buffer
|
|||
|
|
; and that no data is stored past the end of the output buffer. Violations
|
|||
|
|
; indicate corrupt input and are indicated by a status return.
|
|||
|
|
;
|
|||
|
|
; The following code takes advantage of two distinct observations.
|
|||
|
|
; First, literal tokens occur at least twice as often as copy tokens.
|
|||
|
|
; This argues for having a "fall-through" being the case where a literal
|
|||
|
|
; token is found. We structure the main decomposition loop in eight
|
|||
|
|
; pieces where the first piece is a sequence of literal-test fall-throughs
|
|||
|
|
; and the remainder are a copy token followed by 7,6,...,0 literal-test
|
|||
|
|
; fall-throughs. Each test examines a particular bit in the tag byte
|
|||
|
|
; and jumps to the relevant code piece.
|
|||
|
|
;
|
|||
|
|
; The second observation involves performing bounds checking only
|
|||
|
|
; when needed. Bounds checking the compressed buffer need only be done
|
|||
|
|
; when fetching the tag byte. If there is not enough room left in the
|
|||
|
|
; input for a tag byte and 8 (worst case) copy tokens, a branch is made
|
|||
|
|
; to a second loop that handles a byte-by-byte "safe" copy to finish
|
|||
|
|
; up the decompression. Similarly, at the head of the loop a check is
|
|||
|
|
; made to ensure that there is enough room in the output buffer for 8
|
|||
|
|
; literal bytes. If not enough room is left, then the second loop is
|
|||
|
|
; used. Finally, after performing each copy, the output-buffer check
|
|||
|
|
; is made as well since a copy may take the destination pointer
|
|||
|
|
; arbitrarily close to the end of the destination.
|
|||
|
|
;
|
|||
|
|
; The register conventions used in the loops below are:
|
|||
|
|
;
|
|||
|
|
; (al) contains the current tag byte
|
|||
|
|
; (ebx) contains the current width in bits of the length given
|
|||
|
|
; the maximum offset
|
|||
|
|
; that can be utilized in a copy token. We update this
|
|||
|
|
; value only prior to performing a copy. This width is used
|
|||
|
|
; both to index a mask table (for extracting the length) as
|
|||
|
|
; well as shifting (for extracting the copy offset)
|
|||
|
|
; (ecx) is used to contain counts during copies
|
|||
|
|
; (edx) is used as a temp variable during copies
|
|||
|
|
; (esi) is used mainly as the source of the next compressed token.
|
|||
|
|
; It is also used for copies.
|
|||
|
|
; (edi) is used as the destination of literals and copies
|
|||
|
|
; (ebp) is used as a frame pointer
|
|||
|
|
;
|
|||
|
|
; Arguments:
|
|||
|
|
;
|
|||
|
|
; UncompressedBuffer (ebp+8) - pointer to destination of uncompression.
|
|||
|
|
;
|
|||
|
|
; EndOfUncompressedBufferPlus1 (ebp+12) - pointer just beyond the
|
|||
|
|
; output buffer. This is used for consistency checking of the stored
|
|||
|
|
; compressed data.
|
|||
|
|
;
|
|||
|
|
; CompressedBuffer (ebp+16) - pointer to compressed source. This pointer
|
|||
|
|
; has been adjusted by the caller to point past the header word, so
|
|||
|
|
; the pointer points to the first tag byte describing which of the
|
|||
|
|
; following tokens are literals and which are copy groups.
|
|||
|
|
;
|
|||
|
|
; EndOfCompressedBufferPlus1 (ebp+20) - pointer just beyond end of input
|
|||
|
|
; buffer. This is used to terminate the decompression.
|
|||
|
|
;
|
|||
|
|
; FinalUncompressedChunkSize (ebp+24) - pointer to a returned decompressed
|
|||
|
|
; size. This has meaningful data ONLY when LZNT1DecompressChunk returns
|
|||
|
|
; STATUS_SUCCESS
|
|||
|
|
;
|
|||
|
|
; Return Value:
|
|||
|
|
;
|
|||
|
|
; STATUS_SUCCESS is returned only if the decompression consumes thee entire
|
|||
|
|
; input buffer and does not exceed the output buffer.
|
|||
|
|
; STATUS_BAD_COMPRESSION_BUFFER is returned when the output buffer would be
|
|||
|
|
; overflowed.
|
|||
|
|
;
|
|||
|
|
;--
|
|||
|
|
|
|||
|
|
; Decompression macros
|
|||
|
|
|
|||
|
|
;** TestLiteralAt - tests to see if there's a literal at a specific
|
|||
|
|
; bit position. If so, it branches to the appropriate copy code
|
|||
|
|
; (decorated by the bit being used).
|
|||
|
|
;
|
|||
|
|
; This code does no bounds checking
|
|||
|
|
|
|||
|
|
TestLiteralAt macro CopyLabel,bit,IsMain
|
|||
|
|
test al,1 SHL bit ; is there a copy token at this position?
|
|||
|
|
jnz CopyLabel&bit ; yes, go copy it
|
|||
|
|
|
|||
|
|
mov dl,[esi+bit+1] ; (dl) = literal byte from compressed stream
|
|||
|
|
ifidn <IsMain>,<Y>
|
|||
|
|
mov [edi+bit],dl ; store literal byte
|
|||
|
|
else
|
|||
|
|
mov [edi],dl ; store literal byte
|
|||
|
|
inc edi ; point to next literal
|
|||
|
|
endif
|
|||
|
|
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
|
|||
|
|
; Jump - allow specific jumps with computed labels.
|
|||
|
|
|
|||
|
|
Jump macro lab,tag
|
|||
|
|
jmp lab&tag
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
;** DoCopy - perform a copy. If a bit position is specified
|
|||
|
|
; then branch to the appropriate point in the "safe" tail when
|
|||
|
|
; the copy takes us too close to the end of the output buffer
|
|||
|
|
;
|
|||
|
|
; This code checks the bounds of the copy token: copying before the
|
|||
|
|
; beginning of the buffer and copying beyond the end of the buffer.
|
|||
|
|
|
|||
|
|
DoCopy macro AdjustLabel,bit,IsMain
|
|||
|
|
|
|||
|
|
ifidn <IsMain>,<Y>
|
|||
|
|
if bit ne 0
|
|||
|
|
add edi,bit
|
|||
|
|
endif
|
|||
|
|
endif
|
|||
|
|
|
|||
|
|
Test&AdjustLabel&bit:
|
|||
|
|
cmp edi,WidthBoundary
|
|||
|
|
ja Adjust&AdjustLabel&bit
|
|||
|
|
|
|||
|
|
xor ecx,ecx
|
|||
|
|
mov cx,word ptr [esi+bit+1] ; (ecx) = encoded length:offset
|
|||
|
|
lea edx,[esi+1] ; (edx) = next token location
|
|||
|
|
mov Temp,edx
|
|||
|
|
|
|||
|
|
mov esi,ecx ; (esi) = encoded length:offset
|
|||
|
|
and ecx,MaskTab[ebx*4] ; (ecx) = length
|
|||
|
|
xchg ebx,ecx ; (ebx) = length/(ecx) = width
|
|||
|
|
shr esi,cl ; (esi) = offset
|
|||
|
|
xchg ebx,ecx ; (ebx) = width, (ecx) = length
|
|||
|
|
|
|||
|
|
neg esi ; (esi) = negative real offset
|
|||
|
|
lea esi,[esi+edi-1] ; (esi) = pointer to previous string
|
|||
|
|
|
|||
|
|
cmp esi,UncompressedBuffer ; off front of buffer?
|
|||
|
|
jb DOA ; yes, error
|
|||
|
|
|
|||
|
|
add ecx,3 ; (ecx) = real length
|
|||
|
|
|
|||
|
|
lea edx,[edi+ecx] ; (edx) = end of copy
|
|||
|
|
ifidn <IsMain>,<Y>
|
|||
|
|
cmp edx,EndOfSpecialDest ; do we exceed buffer?
|
|||
|
|
jae TailAdd&bit ; yes, handle in safe tail
|
|||
|
|
else
|
|||
|
|
cmp edx,EndOfUncompressedBufferPlus1
|
|||
|
|
; do we exceed buffer?
|
|||
|
|
ja DOA ; yes, error
|
|||
|
|
endif
|
|||
|
|
|
|||
|
|
rep movsb ; Copy the bytes
|
|||
|
|
|
|||
|
|
mov esi,Temp ; (esi) = next token location
|
|||
|
|
|
|||
|
|
ifidn <IsMain>,<Y>
|
|||
|
|
sub edi,bit+1
|
|||
|
|
endif
|
|||
|
|
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
;** AdjustWidth - adjust width of length based upon current position of
|
|||
|
|
; input buffer (max offset)
|
|||
|
|
|
|||
|
|
|
|||
|
|
AdjustWidth macro l,i
|
|||
|
|
Adjust&l&i:
|
|||
|
|
dec ebx ; (ebx) = new width pointer
|
|||
|
|
mov edx,UncompressedBuffer ; (edx) = pointer to dest buffer
|
|||
|
|
add edx,WidthTab[ebx*4] ; (edx) = new width boundary
|
|||
|
|
mov WidthBoundary,edx ; save boundary for comparison
|
|||
|
|
jmp Test&l&i
|
|||
|
|
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
|
|||
|
|
;** GenerateBlock - generates the unsafe block of copy/literal pieces.
|
|||
|
|
;
|
|||
|
|
; This code does no checking for simple input/output checking. Only
|
|||
|
|
; the data referred to by the copy tokens is checked.
|
|||
|
|
|
|||
|
|
GenerateBlock macro bit
|
|||
|
|
Copy&bit:
|
|||
|
|
|
|||
|
|
DoCopy Body,bit,Y
|
|||
|
|
|
|||
|
|
j = bit + 1
|
|||
|
|
while j lt 8
|
|||
|
|
TestLiteralAt Copy,%(j),Y
|
|||
|
|
j = j + 1
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
add esi,9
|
|||
|
|
add edi,8
|
|||
|
|
|
|||
|
|
jmp Top
|
|||
|
|
|
|||
|
|
AdjustWidth Body,bit
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
;** GenerateTailBlock - generates safe tail block for compression. This
|
|||
|
|
; code checks everything before each byte stored so it is expected
|
|||
|
|
; to be executed only at the end of the buffer.
|
|||
|
|
|
|||
|
|
|
|||
|
|
GenerateTailBlock macro bit
|
|||
|
|
TailAdd&bit:
|
|||
|
|
add EndOfCompressedBufferPlus1,1+2*8
|
|||
|
|
; restore buffer length to true length
|
|||
|
|
mov esi,Temp ; (esi) = source of copy token block
|
|||
|
|
dec esi
|
|||
|
|
|
|||
|
|
Tail&bit:
|
|||
|
|
lea ecx,[esi+bit+1] ; (ecx) = source of next token
|
|||
|
|
cmp ecx,EndOfCompressedBufferPlus1 ; are we done?
|
|||
|
|
jz Done ; yes - we exactly match end of buffer
|
|||
|
|
; ja DOA ; INTERNAL ERROR only
|
|||
|
|
|
|||
|
|
cmp edi,EndOfUncompressedBufferPlus1
|
|||
|
|
jz Done ; go quit, destination is full
|
|||
|
|
; ja DOA ; INTERNAL ERROR only
|
|||
|
|
|
|||
|
|
TestLiteralAt TailCopy,bit,N
|
|||
|
|
|
|||
|
|
Jump Tail,%(bit+1)
|
|||
|
|
|
|||
|
|
|
|||
|
|
; We expect a copy token to be at [esi+bit+1]. This means that
|
|||
|
|
; esi+bit+1+tokensize must be <= EndOfCompressedBufferPlus1
|
|||
|
|
TailCopy&bit:
|
|||
|
|
lea ecx,[esi+bit+3] ; (ecx) = next input position
|
|||
|
|
cmp ecx,EndOfCompressedBufferPlus1 ; do we go too far
|
|||
|
|
ja DOA ; yes, we are beyond the end of buffer
|
|||
|
|
|
|||
|
|
DoCopy Tail,bit,N ; perform copy
|
|||
|
|
|
|||
|
|
Jump Tail,%(bit+1)
|
|||
|
|
|
|||
|
|
AdjustWidth Tail,bit
|
|||
|
|
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
cPublicProc _LZNT1DecompressChunk ,5
|
|||
|
|
push ebp ; (tos) = saved frame pointer
|
|||
|
|
mov ebp,esp ; (ebp) = frame pointer to arguments
|
|||
|
|
sub esp,12 ; Open up room for locals
|
|||
|
|
|
|||
|
|
Temp equ dword ptr [ebp-12]
|
|||
|
|
WidthBoundary equ dword ptr [ebp-8]
|
|||
|
|
EndOfSpecialDest equ dword ptr [ebp-4]
|
|||
|
|
|
|||
|
|
;SavedEBP equ dword ptr [ebp]
|
|||
|
|
;ReturnAddress equ dword ptr [ebp+4]
|
|||
|
|
|
|||
|
|
UncompressedBuffer equ dword ptr [ebp+8]
|
|||
|
|
EndOfUncompressedBufferPlus1 equ dword ptr [ebp+12]
|
|||
|
|
CompressedBuffer equ dword ptr [ebp+16]
|
|||
|
|
EndOfCompressedBufferPlus1 equ dword ptr [ebp+20]
|
|||
|
|
FinalUncompressedChunkSize equ dword ptr [ebp+24]
|
|||
|
|
|
|||
|
|
|
|||
|
|
push ebx
|
|||
|
|
push esi
|
|||
|
|
push edi
|
|||
|
|
|
|||
|
|
mov edi,UncompressedBuffer ; (edi) = destination of decompress
|
|||
|
|
mov esi,CompressedBuffer ; (esi) = header
|
|||
|
|
sub EndOfCompressedBufferPlus1,1+2*8 ; make room for special source
|
|||
|
|
|
|||
|
|
mov eax,EndOfUncompressedBufferPlus1 ; (eax) = end of destination
|
|||
|
|
sub eax,8 ; (eax) = beginning of special tail
|
|||
|
|
mov EndOfSpecialDest,eax ; store special tail
|
|||
|
|
|
|||
|
|
mov WidthBoundary,edi ; force initial width mismatch
|
|||
|
|
mov ebx,13 ; initial width of output
|
|||
|
|
|
|||
|
|
|
|||
|
|
Top: cmp esi,EndOfCompressedBufferPlus1 ; Will this be the last tag group in source?
|
|||
|
|
jae DoTail ; yes, go handle specially
|
|||
|
|
cmp edi,EndOfSpecialDest ; are we too close to end of buffer?
|
|||
|
|
jae DoTail ; yes, go skip to end
|
|||
|
|
|
|||
|
|
mov al,byte ptr [esi] ; (al) = tag byte, (esi) points to token
|
|||
|
|
|
|||
|
|
irpc i,<01234567>
|
|||
|
|
TestLiteralAt Copy,%(i),Y
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
add esi,9
|
|||
|
|
add edi,8
|
|||
|
|
|
|||
|
|
jmp Top
|
|||
|
|
; ; Width of offset Width of length
|
|||
|
|
WidthTab dd 0FFFFh ; 16 0
|
|||
|
|
dd 0FFFFh ; 15 1
|
|||
|
|
dd 0FFFFh ; 14 2
|
|||
|
|
dd 0FFFFh ; 13 3
|
|||
|
|
dd 0FFFFh ; 12 4
|
|||
|
|
dd 2048 ; 11 5
|
|||
|
|
dd 1024 ; 10 6
|
|||
|
|
dd 512 ; 9 7
|
|||
|
|
dd 256 ; 8 8
|
|||
|
|
dd 128 ; 7 9
|
|||
|
|
dd 64 ; 6 10
|
|||
|
|
dd 32 ; 5 11
|
|||
|
|
dd 16 ; 4 12
|
|||
|
|
dd 0 ; 3 13
|
|||
|
|
dd 0 ; 2 14
|
|||
|
|
dd 0 ; 1 15
|
|||
|
|
dd 0 ; 0 16
|
|||
|
|
|
|||
|
|
|
|||
|
|
; ;
|
|||
|
|
MaskTab dd 0000000000000000b ; 0
|
|||
|
|
dd 0000000000000001b ; 1
|
|||
|
|
dd 0000000000000011b ; 2
|
|||
|
|
dd 0000000000000111b ; 3
|
|||
|
|
dd 0000000000001111b ; 4
|
|||
|
|
dd 0000000000011111b ; 5
|
|||
|
|
dd 0000000000111111b ; 6
|
|||
|
|
dd 0000000001111111b ; 7
|
|||
|
|
dd 0000000011111111b ; 8
|
|||
|
|
dd 0000000111111111b ; 9
|
|||
|
|
dd 0000001111111111b ; 10
|
|||
|
|
dd 0000011111111111b ; 11
|
|||
|
|
dd 0000111111111111b ; 12
|
|||
|
|
dd 0001111111111111b ; 13
|
|||
|
|
dd 0011111111111111b ; 14
|
|||
|
|
dd 0111111111111111b ; 15
|
|||
|
|
dd 1111111111111111b ; 16
|
|||
|
|
|
|||
|
|
|
|||
|
|
irpc i,<01234567>
|
|||
|
|
GenerateBlock %(i)
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
; We're handling a tail specially for this. We must check at all
|
|||
|
|
; spots for running out of input as well as overflowing output.
|
|||
|
|
;
|
|||
|
|
; (esi) = pointer to possible next tag
|
|||
|
|
|
|||
|
|
DoTail: add EndOfCompressedBufferPlus1,1+2*8 ; point to end of compressed input
|
|||
|
|
|
|||
|
|
TailLoop:
|
|||
|
|
cmp esi,EndOfCompressedBufferPlus1 ; are we totally done?
|
|||
|
|
jz Done ; yes, go return
|
|||
|
|
mov al,byte ptr [esi] ; (al) = tag byte
|
|||
|
|
|
|||
|
|
jmp Tail0
|
|||
|
|
|
|||
|
|
irpc i,<01234567>
|
|||
|
|
GenerateTailBlock i
|
|||
|
|
endm
|
|||
|
|
|
|||
|
|
Tail8: add esi,9
|
|||
|
|
jmp TailLoop
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
DOA: mov eax,STATUS_BAD_COMPRESSION_BUFFER
|
|||
|
|
jmp Final
|
|||
|
|
|
|||
|
|
Done: mov eax,edi ; (eax) = pointer to next byte to store
|
|||
|
|
sub eax,UncompressedBuffer ; (eax) = length of uncompressed
|
|||
|
|
mov edi,FinalUncompressedChunkSize ; (edi) = user return value location
|
|||
|
|
mov [edi],eax ; return total transfer size to user
|
|||
|
|
xor eax,eax ; (eax) = STATUS_SUCCESS
|
|||
|
|
|
|||
|
|
Final: pop edi
|
|||
|
|
pop esi
|
|||
|
|
pop ebx
|
|||
|
|
mov esp,ebp
|
|||
|
|
pop ebp
|
|||
|
|
|
|||
|
|
|
|||
|
|
stdRET _LZNT1DecompressChunk
|
|||
|
|
|
|||
|
|
stdENDP _LZNT1DecompressChunk
|
|||
|
|
|
|||
|
|
IFDEF NTOS_KERNEL_RUNTIME
|
|||
|
|
_PAGE ENDS
|
|||
|
|
ELSE
|
|||
|
|
_TEXT ENDS
|
|||
|
|
ENDIF
|
|||
|
|
end
|