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 _TEXT$01 SEGMENT DWORD PUBLIC 'CODE' 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 , 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 , 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 , 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 , 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 _TEXT$01 ends end