diff options
Diffstat (limited to 'private/ntos/rtl/lznt1.c')
| -rw-r--r-- | private/ntos/rtl/lznt1.c | 2203 |
1 files changed, 2203 insertions, 0 deletions
diff --git a/private/ntos/rtl/lznt1.c b/private/ntos/rtl/lznt1.c new file mode 100644 index 000000000..9403d387d --- /dev/null +++ b/private/ntos/rtl/lznt1.c @@ -0,0 +1,2203 @@ +/*++ + +Copyright (c) 1989 Microsoft Corporation + +Module Name: + + LZNT1.c + +Abstract: + + This module implements the LZNT1 compression engine. + +Author: + + Gary Kimura [GaryKi] 21-Jan-1994 + +Revision History: + +--*/ + +#include "ntrtlp.h" + +#include <stdio.h> + + +// +// Declare the internal workspace that we need +// + +typedef struct _LZNT1_STANDARD_WORKSPACE { + + PUCHAR UncompressedBuffer; + PUCHAR EndOfUncompressedBufferPlus1; + ULONG MaxLength; + PUCHAR MatchedString; + + PUCHAR IndexPTable[4096][2]; + +} LZNT1_STANDARD_WORKSPACE, *PLZNT1_STANDARD_WORKSPACE; + +typedef struct _LZNT1_MAXIMUM_WORKSPACE { + + PUCHAR UncompressedBuffer; + PUCHAR EndOfUncompressedBufferPlus1; + ULONG MaxLength; + PUCHAR MatchedString; + +} LZNT1_MAXIMUM_WORKSPACE, *PLZNT1_MAXIMUM_WORKSPACE; + +typedef struct _LZNT1_FRAGMENT_WORKSPACE { + + UCHAR Buffer[0x1000]; + +} LZNT1_FRAGMENT_WORKSPACE, *PLZNT1_FRAGMENT_WORKSPACE; + +// +// Now define the local procedure prototypes. +// + +typedef ULONG (*PLZNT1_MATCH_FUNCTION) ( + ); + +NTSTATUS +LZNT1CompressChunk ( + IN PLZNT1_MATCH_FUNCTION MatchFunction, + IN PUCHAR UncompressedBuffer, + IN PUCHAR EndOfUncompressedBufferPlus1, + OUT PUCHAR CompressedBuffer, + IN PUCHAR EndOfCompressedBufferPlus1, + OUT PULONG FinalCompressedChunkSize, + IN PVOID WorkSpace + ); + +NTSTATUS +LZNT1DecompressChunk ( + OUT PUCHAR UncompressedBuffer, + IN PUCHAR EndOfUncompressedBufferPlus1, + IN PUCHAR CompressedBuffer, + IN PUCHAR EndOfCompressedBufferPlus1, + OUT PULONG FinalUncompressedChunkSize + ); + +ULONG +LZNT1FindMatchStandard ( + IN PUCHAR ZivString, + IN PLZNT1_STANDARD_WORKSPACE WorkSpace + ); + +ULONG +LZNT1FindMatchMaximum ( + IN PUCHAR ZivString, + IN PVOID WorkSpace + ); + + +// +// Local data structures +// + +// +// The compressed chunk header is the structure that starts every +// new chunk in the compressed data stream. In our definition here +// we union it with a ushort to make setting and retrieving the chunk +// header easier. The header stores the size of the compressed chunk, +// its signature, and if the data stored in the chunk is compressed or +// not. +// +// Compressed Chunk Size: +// +// The actual size of a compressed chunk ranges from 4 bytes (2 byte +// header, 1 flag byte, and 1 literal byte) to 4098 bytes (2 byte +// header, and 4096 bytes of uncompressed data). The size is encoded +// in a 12 bit field biased by 3. A value of 1 corresponds to a chunk +// size of 4, 2 => 5, ..., 4095 => 4098. A value of zero is special +// because it denotes the ending chunk header. +// +// Chunk Signature: +// +// The only valid signature value is 3. This denotes a 4KB uncompressed +// chunk using with the 4/12 to 12/4 sliding offset/length encoding. +// +// Is Chunk Compressed: +// +// If the data in the chunk is compressed this field is 1 otherwise +// the data is uncompressed and this field is 0. +// +// The ending chunk header in a compressed buffer contains the a value of +// zero (space permitting). +// + +typedef union _COMPRESSED_CHUNK_HEADER { + + struct { + + USHORT CompressedChunkSizeMinus3 : 12; + USHORT ChunkSignature : 3; + USHORT IsChunkCompressed : 1; + + } Chunk; + + USHORT Short; + +} COMPRESSED_CHUNK_HEADER, *PCOMPRESSED_CHUNK_HEADER; + +#define MAX_UNCOMPRESSED_CHUNK_SIZE (4096) + +// +// USHORT +// GetCompressedChunkSize ( +// IN COMPRESSED_CHUNK_HEADER ChunkHeader +// ); +// +// USHORT +// GetUncompressedChunkSize ( +// IN COMPRESSED_CHUNK_HEADER ChunkHeader +// ); +// +// VOID +// SetCompressedChunkHeader ( +// IN OUT COMPRESSED_CHUNK_HEADER ChunkHeader, +// IN USHORT CompressedChunkSize, +// IN BOOLEAN IsChunkCompressed +// ); +// + +#define GetCompressedChunkSize(CH) ( \ + (CH).Chunk.CompressedChunkSizeMinus3 + 3 \ +) + +#define GetUncompressedChunkSize(CH) (MAX_UNCOMPRESSED_CHUNK_SIZE) + +#define SetCompressedChunkHeader(CH,CCS,ICC) { \ + ASSERT((CCS) >= 4 && (CCS) <= 4098); \ + (CH).Chunk.CompressedChunkSizeMinus3 = (CCS) - 3; \ + (CH).Chunk.ChunkSignature = 3; \ + (CH).Chunk.IsChunkCompressed = (ICC); \ +} + + +// +// Local macros +// + +#define FlagOn(F,SF) ((F) & (SF)) +#define SetFlag(F,SF) { (F) |= (SF); } +#define ClearFlag(F,SF) { (F) &= ~(SF); } + +#define Minimum(A,B) ((A) < (B) ? (A) : (B)) +#define Maximum(A,B) ((A) > (B) ? (A) : (B)) + +#if defined(ALLOC_PRAGMA) && defined(NTOS_KERNEL_RUNTIME) + +#pragma alloc_text(PAGE, RtlCompressWorkSpaceSizeLZNT1) +#pragma alloc_text(PAGE, RtlCompressBufferLZNT1) +#pragma alloc_text(PAGE, RtlDecompressBufferLZNT1) +#pragma alloc_text(PAGE, RtlDecompressFragmentLZNT1) +#pragma alloc_text(PAGE, RtlDescribeChunkLZNT1) +#pragma alloc_text(PAGE, RtlReserveChunkLZNT1) + +#pragma alloc_text(PAGE, LZNT1CompressChunk) + +#if !defined(_ALPHA_) +#if !defined(_MIPS_) +#if !defined(_PPC_) +#if !defined(i386) +#pragma alloc_text(PAGE, LZNT1DecompressChunk) +#endif +#endif +#endif +#endif + +#pragma alloc_text(PAGE, LZNT1FindMatchStandard) +#pragma alloc_text(PAGE, LZNT1FindMatchMaximum) + +#endif + + +NTSTATUS +RtlCompressWorkSpaceSizeLZNT1 ( + IN USHORT Engine, + OUT PULONG CompressBufferWorkSpaceSize, + OUT PULONG CompressFragmentWorkSpaceSize + ) + +/*++ + +Routine Description: + +Arguments: + +Return Value: + +--*/ + +{ + if (Engine == COMPRESSION_ENGINE_STANDARD) { + + *CompressBufferWorkSpaceSize = sizeof(LZNT1_STANDARD_WORKSPACE); + *CompressFragmentWorkSpaceSize = sizeof(LZNT1_FRAGMENT_WORKSPACE); + + return STATUS_SUCCESS; + + } else if (Engine == COMPRESSION_ENGINE_MAXIMUM) { + + *CompressBufferWorkSpaceSize = sizeof(LZNT1_MAXIMUM_WORKSPACE); + *CompressFragmentWorkSpaceSize = sizeof(LZNT1_FRAGMENT_WORKSPACE); + + return STATUS_SUCCESS; + + } else { + + return STATUS_NOT_SUPPORTED; + } +} + + +NTSTATUS +RtlCompressBufferLZNT1 ( + IN USHORT Engine, + IN PUCHAR UncompressedBuffer, + IN ULONG UncompressedBufferSize, + OUT PUCHAR CompressedBuffer, + IN ULONG CompressedBufferSize, + IN ULONG UncompressedChunkSize, + OUT PULONG FinalCompressedSize, + IN PVOID WorkSpace + ) + +/*++ + +Routine Description: + + This routine takes as input an uncompressed buffer and produces + its compressed equivalent provided the compressed data fits within + the specified destination buffer. + + An output variable indicates the number of bytes used to store + the compressed buffer. + +Arguments: + + UncompressedBuffer - Supplies a pointer to the uncompressed data. + + UncompressedBufferSize - Supplies the size, in bytes, of the + uncompressed buffer. + + CompressedBuffer - Supplies a pointer to where the compressed data + is to be stored. + + CompressedBufferSize - Supplies the size, in bytes, of the + compressed buffer. + + UncompressedChunkSize - Ignored. + + FinalCompressedSize - Receives the number of bytes needed in + the compressed buffer to store the compressed data. + + WorkSpace - Mind your own business, just give it to me. + +Return Value: + + STATUS_SUCCESS - the compression worked without a hitch. + + STATUS_BUFFER_ALL_ZEROS - the compression worked without a hitch and in + addition the input buffer was all zeros. + + STATUS_BUFFER_TOO_SMALL - the compressed buffer is too small to hold the + compressed data. + +--*/ + +{ + NTSTATUS Status; + + PLZNT1_MATCH_FUNCTION MatchFunction; + + PUCHAR UncompressedChunk; + PUCHAR CompressedChunk; + LONG CompressedChunkSize; + + // + // The following variable is used to tell if we have processed an entire + // buffer of zeros and that we should return an alternate status value + // + + BOOLEAN AllZero = TRUE; + + // + // The following variables are pointers to the byte following the + // end of each appropriate buffer. + // + + PUCHAR EndOfUncompressedBuffer = UncompressedBuffer + UncompressedBufferSize; + PUCHAR EndOfCompressedBuffer = CompressedBuffer + CompressedBufferSize; + + // + // Get the match function we are to be using + // + + if (Engine == COMPRESSION_ENGINE_STANDARD) { + + MatchFunction = LZNT1FindMatchStandard; + + } else if (Engine == COMPRESSION_ENGINE_MAXIMUM) { + + MatchFunction = LZNT1FindMatchMaximum; + + } else { + + return STATUS_NOT_SUPPORTED; + } + + // + // For each uncompressed chunk (even the odd sized ending buffer) we will + // try and compress the chunk + // + + for (UncompressedChunk = UncompressedBuffer, CompressedChunk = CompressedBuffer; + UncompressedChunk < EndOfUncompressedBuffer; + UncompressedChunk += MAX_UNCOMPRESSED_CHUNK_SIZE, CompressedChunk += CompressedChunkSize) { + + ASSERT(EndOfUncompressedBuffer >= UncompressedChunk); + ASSERT(EndOfCompressedBuffer >= CompressedChunk); + + // + // Call the appropriate engine to compress one chunk. and + // return an error if we got one. + // + + if (!NT_SUCCESS(Status = LZNT1CompressChunk( MatchFunction, + UncompressedChunk, + EndOfUncompressedBuffer, + CompressedChunk, + EndOfCompressedBuffer, + &CompressedChunkSize, + WorkSpace ))) { + + return Status; + } + + // + // See if we stay all zeros. If not then all zeros will become + // false and stay that way no matter what we later compress + // + + AllZero = AllZero && (Status == STATUS_BUFFER_ALL_ZEROS); + } + + // + // If we are not within two bytes of the end of the compressed buffer then we + // need to zero out two more for the ending compressed header and update + // the compressed chunk pointer value. Don't include these bytes in + // the count however, as that may force our caller to allocate an unneeded + // cluster, since on decompress we will terminate either on these two + // bytes of 0, or byte count. + // + + if (CompressedChunk <= (EndOfCompressedBuffer - 2)) { + + *(CompressedChunk) = 0; + *(CompressedChunk + 1) = 0; + } + + // + // The final compressed size is the difference between the start of the + // compressed buffer and where the compressed chunk pointer was left + // + + *FinalCompressedSize = CompressedChunk - CompressedBuffer; + + // + // Check if the input buffer was all zeros and return the alternate status + // if appropriate + // + + if (AllZero) { return STATUS_BUFFER_ALL_ZEROS; } + + return STATUS_SUCCESS; +} + + +NTSTATUS +RtlDecompressBufferLZNT1 ( + OUT PUCHAR UncompressedBuffer, + IN ULONG UncompressedBufferSize, + IN PUCHAR CompressedBuffer, + IN ULONG CompressedBufferSize, + OUT PULONG FinalUncompressedSize + ) + +/*++ + +Routine Description: + + This routine takes as input a compressed buffer and produces + its uncompressed equivalent provided the uncompressed data fits + within the specified destination buffer. + + An output variable indicates the number of bytes used to store the + uncompressed data. + +Arguments: + + UncompressedBuffer - Supplies a pointer to where the uncompressed + data is to be stored. + + UncompressedBufferSize - Supplies the size, in bytes, of the + uncompressed buffer. + + CompressedBuffer - Supplies a pointer to the compressed data. + + CompressedBufferSize - Supplies the size, in bytes, of the + compressed buffer. + + FinalUncompressedSize - Receives the number of bytes needed in + the uncompressed buffer to store the uncompressed data. + +Return Value: + + STATUS_SUCCESS - the decompression worked without a hitch. + + STATUS_BAD_COMPRESSION_BUFFER - the input compressed buffer is + ill-formed. + +--*/ + +{ + NTSTATUS Status; + + PUCHAR CompressedChunk = CompressedBuffer; + PUCHAR UncompressedChunk = UncompressedBuffer; + + COMPRESSED_CHUNK_HEADER ChunkHeader; + LONG SavedChunkSize; + + LONG UncompressedChunkSize; + LONG CompressedChunkSize; + + // + // The following to variables are pointers to the byte following the + // end of each appropriate buffer. This saves us from doing the addition + // for each loop check + // + + PUCHAR EndOfUncompressedBuffer = UncompressedBuffer + UncompressedBufferSize; + PUCHAR EndOfCompressedBuffer = CompressedBuffer + CompressedBufferSize; + + // + // Make sure that the compressed buffer is at least four bytes long to + // start with, and then get the first chunk header and make sure it + // is not an ending chunk header. + // + + ASSERT(CompressedChunk <= EndOfCompressedBuffer - 4); + + RtlRetrieveUshort( &ChunkHeader, CompressedChunk ); + + ASSERT(ChunkHeader.Short != 0); + + // + // Now while there is space in the uncompressed buffer to store data + // we will loop through decompressing chunks + // + + while (TRUE) { + + ASSERT(ChunkHeader.Chunk.ChunkSignature == 3); + + CompressedChunkSize = GetCompressedChunkSize(ChunkHeader); + + // + // Check that the chunk actually fits in the buffer supplied + // by the caller + // + + if (CompressedChunk + CompressedChunkSize > EndOfCompressedBuffer) { + + ASSERTMSG("CompressedBuffer is too small", FALSE); + + *FinalUncompressedSize = (ULONG)CompressedChunk; + + return STATUS_BAD_COMPRESSION_BUFFER; + } + + // + // First make sure the chunk contains compressed data + // + + if (ChunkHeader.Chunk.IsChunkCompressed) { + + // + // Decompress a chunk and return if we get an error + // + + if (!NT_SUCCESS(Status = LZNT1DecompressChunk( UncompressedChunk, + EndOfUncompressedBuffer, + CompressedChunk + sizeof(COMPRESSED_CHUNK_HEADER), + CompressedChunk + CompressedChunkSize, + &UncompressedChunkSize ))) { + + *FinalUncompressedSize = UncompressedChunkSize; + + return Status; + } + + } else { + + // + // The chunk does not contain compressed data so we need to simply + // copy over the uncompressed data + // + + UncompressedChunkSize = GetUncompressedChunkSize( ChunkHeader ); + + // + // Make sure the data will fit into the output buffer + // + + if (UncompressedChunk + UncompressedChunkSize > EndOfUncompressedBuffer) { + + UncompressedChunkSize = EndOfUncompressedBuffer - UncompressedChunk; + } + + // + // Check that the compressed chunk has this many bytes to copy. + // + + if (CompressedChunk + sizeof(COMPRESSED_CHUNK_HEADER) + UncompressedChunkSize > EndOfCompressedBuffer) { + + ASSERTMSG("CompressedBuffer is too small", FALSE); + *FinalUncompressedSize = (ULONG)CompressedChunk; + return STATUS_BAD_COMPRESSION_BUFFER; + } + + RtlCopyMemory( UncompressedChunk, + CompressedChunk + sizeof(COMPRESSED_CHUNK_HEADER), + UncompressedChunkSize ); + } + + // + // Now update the compressed and uncompressed chunk pointers with + // the size of the compressed chunk and the number of bytes we + // decompressed into, and then make sure we didn't exceed our buffers + // + + CompressedChunk += CompressedChunkSize; + UncompressedChunk += UncompressedChunkSize; + + ASSERT( CompressedChunk <= EndOfCompressedBuffer ); + ASSERT( UncompressedChunk <= EndOfUncompressedBuffer ); + + // + // Now if the uncompressed is full then we are done + // + + if (UncompressedChunk == EndOfUncompressedBuffer) { break; } + + // + // Otherwise we need to get the next chunk header. We first + // check if there is one, save the old chunk size for the + // chunk we just read in, get the new chunk, and then check + // if it is the ending chunk header + // + + if (CompressedChunk > EndOfCompressedBuffer - 2) { break; } + + SavedChunkSize = GetUncompressedChunkSize(ChunkHeader); + + RtlRetrieveUshort( &ChunkHeader, CompressedChunk ); + if (ChunkHeader.Short == 0) { break; } + + // + // At this point we are not at the end of the uncompressed buffer + // and we have another chunk to process. But before we go on we + // need to see if the last uncompressed chunk didn't fill the full + // uncompressed chunk size. + // + + if (UncompressedChunkSize < SavedChunkSize) { + + LONG t1; + PUCHAR t2; + + // + // Now we only need to zero out data if the really are going + // to process another chunk, to test for that we check if + // the zero will go beyond the end of the uncompressed buffer + // + + if ((t2 = (UncompressedChunk + + (t1 = (SavedChunkSize - + UncompressedChunkSize)))) >= EndOfUncompressedBuffer) { + + break; + } + + RtlZeroMemory( UncompressedChunk, t1); + UncompressedChunk = t2; + } + } + + // + // If we got out of the loop with the compressed chunk pointer beyond the + // end of compressed buffer then the compression buffer is ill formed. + // + + if (CompressedChunk > EndOfCompressedBuffer) { + + *FinalUncompressedSize = (ULONG)CompressedChunk; + + return STATUS_BAD_COMPRESSION_BUFFER; + } + + // + // The final uncompressed size is the difference between the start of the + // uncompressed buffer and where the uncompressed chunk pointer was left + // + + *FinalUncompressedSize = UncompressedChunk - UncompressedBuffer; + + // + // And return to our caller + // + + return STATUS_SUCCESS; +} + + +NTSTATUS +RtlDecompressFragmentLZNT1 ( + OUT PUCHAR UncompressedFragment, + IN ULONG UncompressedFragmentSize, + IN PUCHAR CompressedBuffer, + IN ULONG CompressedBufferSize, + IN ULONG FragmentOffset, + OUT PULONG FinalUncompressedSize, + IN PLZNT1_FRAGMENT_WORKSPACE WorkSpace + ) + +/*++ + +Routine Description: + + This routine takes as input a compressed buffer and extract an + uncompressed fragment. + + Output bytes are copied to the fragment buffer until either the + fragment buffer is full or the end of the uncompressed buffer is + reached. + + An output variable indicates the number of bytes used to store the + uncompressed fragment. + +Arguments: + + UncompressedFragment - Supplies a pointer to where the uncompressed + fragment is to be stored. + + UncompressedFragmentSize - Supplies the size, in bytes, of the + uncompressed fragment buffer. + + CompressedBuffer - Supplies a pointer to the compressed data buffer. + + CompressedBufferSize - Supplies the size, in bytes, of the + compressed buffer. + + FragmentOffset - Supplies the offset (zero based) where the uncompressed + fragment is being extract from. The offset is the position within + the original uncompressed buffer. + + FinalUncompressedSize - Receives the number of bytes needed in + the Uncompressed fragment buffer to store the data. + + WorkSpace - Stop looking. + +Return Value: + + STATUS_SUCCESS - the operation worked without a hitch. + + STATUS_BAD_COMPRESSION_BUFFER - the input compressed buffer is + ill-formed. + +--*/ + +{ + NTSTATUS Status; + + PUCHAR CompressedChunk = CompressedBuffer; + + COMPRESSED_CHUNK_HEADER ChunkHeader; + ULONG UncompressedChunkSize; + ULONG CompressedChunkSize; + + PUCHAR EndOfUncompressedFragment = UncompressedFragment + UncompressedFragmentSize; + PUCHAR EndOfCompressedBuffer = CompressedBuffer + CompressedBufferSize; + PUCHAR CurrentUncompressedFragment; + + ULONG CopySize; + + ASSERT(UncompressedFragmentSize > 0); + + // + // Get the chunk header for the first chunk in the + // compressed buffer and extract the uncompressed and + // the compressed chunk sizes + // + + ASSERT(CompressedChunk <= EndOfCompressedBuffer - 2); + + RtlRetrieveUshort( &ChunkHeader, CompressedChunk ); + + ASSERT(ChunkHeader.Short != 0); + ASSERT(ChunkHeader.Chunk.ChunkSignature == 3); + + UncompressedChunkSize = GetUncompressedChunkSize(ChunkHeader); + CompressedChunkSize = GetCompressedChunkSize(ChunkHeader); + + // + // Now we want to skip over chunks that precede the fragment + // we're after. To do that we'll loop until the fragment + // offset is within the current chunk. If it is not within + // the current chunk then we'll skip to the next chunk and + // subtract the uncompressed chunk size from the fragment offset + // + + while (FragmentOffset >= UncompressedChunkSize) { + + // + // Check that the chunk actually fits in the buffer supplied + // by the caller + // + + if (CompressedChunk + CompressedChunkSize > EndOfCompressedBuffer) { + + ASSERTMSG("CompressedBuffer is too small", FALSE); + + *FinalUncompressedSize = (ULONG)CompressedChunk; + + return STATUS_BAD_COMPRESSION_BUFFER; + } + + // + // Adjust the fragment offset and move the compressed + // chunk pointer to the next chunk + // + + FragmentOffset -= UncompressedChunkSize; + CompressedChunk += CompressedChunkSize; + + // + // Get the next chunk header and if it is not in use + // then the fragment that the user wants is beyond the + // compressed data so we'll return a zero sized fragment + // + + if (CompressedChunk > EndOfCompressedBuffer - 2) { + + *FinalUncompressedSize = 0; + return STATUS_SUCCESS; + } + + RtlRetrieveUshort( &ChunkHeader, CompressedChunk ); + + if (ChunkHeader.Short == 0) { + + *FinalUncompressedSize = 0; + return STATUS_SUCCESS; + } + + ASSERT(ChunkHeader.Chunk.ChunkSignature == 3); + + // + // Decode the chunk sizes for the new current chunk + // + + UncompressedChunkSize = GetUncompressedChunkSize(ChunkHeader); + CompressedChunkSize = GetCompressedChunkSize(ChunkHeader); + } + + // + // At this point the current chunk contains the starting point + // for the fragment. Now we'll loop extracting data until + // we've filled up the uncompressed fragment buffer or until + // we've run out of chunks. Both test are done near the end of + // the loop + // + + CurrentUncompressedFragment = UncompressedFragment; + + while (TRUE) { + + // + // Check that the chunk actually fits in the buffer supplied + // by the caller + // + + if (CompressedChunk + CompressedChunkSize > EndOfCompressedBuffer) { + + ASSERTMSG("CompressedBuffer is too small", FALSE); + + *FinalUncompressedSize = (ULONG)CompressedChunk; + + return STATUS_BAD_COMPRESSION_BUFFER; + } + + + // + // Now we need to compute the amount of data to copy from the + // chunk. It will be based on either to the end of the chunk + // size or the amount of data the user specified + // + + CopySize = Minimum( UncompressedChunkSize - FragmentOffset, UncompressedFragmentSize ); + + // + // Now check if the chunk contains compressed data + // + + if (ChunkHeader.Chunk.IsChunkCompressed) { + + // + // The chunk is compressed but now check if the amount + // we need to get is the entire chunk and if so then + // we can do the decompress straight into the caller's + // buffer + // + + if ((FragmentOffset == 0) && (CopySize == UncompressedChunkSize)) { + + if (!NT_SUCCESS(Status = LZNT1DecompressChunk( CurrentUncompressedFragment, + EndOfUncompressedFragment, + CompressedChunk + sizeof(COMPRESSED_CHUNK_HEADER), + CompressedChunk + CompressedChunkSize, + &CopySize ))) { + + *FinalUncompressedSize = CopySize; + + return Status; + } + + } else { + + // + // The caller wants only a portion of this compressed chunk + // so we need to read it into our work buffer and then copy + // the parts from the work buffer into the caller's buffer + // + + if (!NT_SUCCESS(Status = LZNT1DecompressChunk( (PUCHAR)WorkSpace, + &WorkSpace->Buffer[0] + sizeof(LZNT1_FRAGMENT_WORKSPACE), + CompressedChunk + sizeof(COMPRESSED_CHUNK_HEADER), + CompressedChunk + CompressedChunkSize, + &UncompressedChunkSize ))) { + + *FinalUncompressedSize = UncompressedChunkSize; + + return Status; + } + + // + // If we got less than we were looking for then we are at the + // end of the file. Remember the real uncompressed size and + // break out of the loop. + // + + if ((UncompressedChunkSize - FragmentOffset) < CopySize) { + + RtlCopyMemory( CurrentUncompressedFragment, + &WorkSpace->Buffer[ FragmentOffset ], + (UncompressedChunkSize - FragmentOffset) ); + + CurrentUncompressedFragment += (UncompressedChunkSize - FragmentOffset); + break; + } + + RtlCopyMemory( CurrentUncompressedFragment, + &WorkSpace->Buffer[ FragmentOffset ], + CopySize ); + } + + } else { + + // + // The chunk is not compressed so we can do a simple copy of the + // data. First verify that the compressed buffer holds this much + // data. + // + + if (CompressedChunk + sizeof(COMPRESSED_CHUNK_HEADER) + FragmentOffset + CopySize > EndOfCompressedBuffer) { + + ASSERTMSG("CompressedBuffer is too small", FALSE); + *FinalUncompressedSize = (ULONG)CompressedChunk; + return STATUS_BAD_COMPRESSION_BUFFER; + } + + RtlCopyMemory( CurrentUncompressedFragment, + CompressedChunk + sizeof(COMPRESSED_CHUNK_HEADER) + FragmentOffset, + CopySize ); + } + + // + // Now that we've done at least one copy make sure the fragment + // offset is set to zero so the next time through the loop will + // start at the right offset + // + + FragmentOffset = 0; + + // + // Adjust the uncompressed fragment information by moving the + // pointer up by the copy size and subtracting copy size from + // the amount of data the user wants + // + + CurrentUncompressedFragment += CopySize; + UncompressedFragmentSize -= CopySize; + + // + // Now if the uncompressed fragment size is zero then we're + // done + // + + if (UncompressedFragmentSize == 0) { break; } + + // + // Otherwise the user wants more data so we'll move to the + // next chunk, and then check if the chunk is is use. If + // it is not in use then we the user is trying to read beyond + // the end of compressed data so we'll break out of the loop + // + + CompressedChunk += CompressedChunkSize; + + if (CompressedChunk > EndOfCompressedBuffer - 2) { break; } + + RtlRetrieveUshort( &ChunkHeader, CompressedChunk ); + + if (ChunkHeader.Short == 0) { break; } + + ASSERT(ChunkHeader.Chunk.ChunkSignature == 3); + + // + // Decode the chunk sizes for the new current chunk + // + + UncompressedChunkSize = GetUncompressedChunkSize(ChunkHeader); + CompressedChunkSize = GetCompressedChunkSize(ChunkHeader); + } + + // + // Now either we finished filling up the caller's buffer (and + // uncompressed fragment size is zero) or we've exhausted the + // compresed buffer (and chunk header is zero). In either case + // we're done and we can now compute the size of the fragment + // that we're returning to the caller it is simply the difference + // between the start of the buffer and the current position + // + + *FinalUncompressedSize = CurrentUncompressedFragment - UncompressedFragment; + + return STATUS_SUCCESS; +} + + +NTSTATUS +RtlDescribeChunkLZNT1 ( + IN OUT PUCHAR *CompressedBuffer, + IN PUCHAR EndOfCompressedBufferPlus1, + OUT PUCHAR *ChunkBuffer, + OUT PULONG ChunkSize + ) + +/*++ + +Routine Description: + + This routine takes as input a compressed buffer, and returns + a description of the current chunk in that buffer, updating + the CompressedBuffer pointer to point to the next chunk (if + there is one). + +Arguments: + + CompressedBuffer - Supplies a pointer to the current chunk in + the compressed data, and returns pointing to the next chunk + + EndOfCompressedBufferPlus1 - Points at first byte beyond + compressed buffer + + ChunkBuffer - Receives a pointer to the chunk, if ChunkSize + is nonzero, else undefined + + ChunkSize - Receives the size of the current chunk pointed + to by CompressedBuffer. Returns 0 if STATUS_NO_MORE_ENTRIES. + +Return Value: + + STATUS_SUCCESS - the chunk size is being returned + + STATUS_BAD_COMPRESSION_BUFFER - the input compressed buffer is + ill-formed. + + STATUS_NO_MORE_ENTRIES - There is no chunk at the current pointer. + +--*/ + +{ + COMPRESSED_CHUNK_HEADER ChunkHeader; + NTSTATUS Status = STATUS_NO_MORE_ENTRIES; + + // + // First initialize outputs + // + + *ChunkBuffer = *CompressedBuffer; + *ChunkSize = 0; + + // + // Make sure that the compressed buffer is at least four bytes long to + // start with, otherwise just return a zero chunk. + // + + if (*CompressedBuffer <= EndOfCompressedBufferPlus1 - 4) { + + RtlRetrieveUshort( &ChunkHeader, *CompressedBuffer ); + + // + // Check for end of chunks, terminated by USHORT of 0. + // First assume there are no more. + // + + if (ChunkHeader.Short != 0) { + + Status = STATUS_SUCCESS; + + *ChunkSize = GetCompressedChunkSize(ChunkHeader); + *CompressedBuffer += *ChunkSize; + + // + // Check that the chunk actually fits in the buffer supplied + // by the caller. If not, restore *CompressedBuffer for debug! + // + + if ((*CompressedBuffer > EndOfCompressedBufferPlus1) || + (ChunkHeader.Chunk.ChunkSignature != 3)) { + + ASSERTMSG("CompressedBuffer is bad or too small", FALSE); + + *CompressedBuffer -= *ChunkSize; + + Status = STATUS_BAD_COMPRESSION_BUFFER; + + // + // First make sure the chunk contains compressed data + // + + } else if (!ChunkHeader.Chunk.IsChunkCompressed) { + + // + // The uncompressed chunk must be exactly this size! + // If not, restore *CompressedBuffer for debug! + // + + if (*ChunkSize != MAX_UNCOMPRESSED_CHUNK_SIZE + 2) { + + ASSERTMSG("Uncompressed chunk is wrong size", FALSE); + + *CompressedBuffer -= *ChunkSize; + + Status = STATUS_BAD_COMPRESSION_BUFFER; + + // + // The chunk does not contain compressed data so we need to + // remove the chunk header from the chunk description. + // + + } else { + + *ChunkBuffer += 2; + *ChunkSize -= 2; + } + + // + // Otherwise we have a compressed chunk, and we only need to + // see if it is all zeros! Since the header is already interpreted, + // we only have to see if there is exactly one literal and if it + // is zero - it doesn't matter what the copy token says - we have + // a chunk of zeros! + // + + } else if ((*ChunkSize == 6) && (*(*ChunkBuffer + 2) == 2) && (*(*ChunkBuffer + 3) == 0)) { + + *ChunkSize = 0; + } + } + } + + return Status; +} + + +NTSTATUS +RtlReserveChunkLZNT1 ( + IN OUT PUCHAR *CompressedBuffer, + IN PUCHAR EndOfCompressedBufferPlus1, + OUT PUCHAR *ChunkBuffer, + IN ULONG ChunkSize + ) + +/*++ + +Routine Description: + + This routine reserves space for a chunk of the specified + size in the buffer, writing in a chunk header if necessary + (uncompressed or all zeros case). On return the CompressedBuffer + pointer points to the next chunk. + +Arguments: + + CompressedBuffer - Supplies a pointer to the current chunk in + the compressed data, and returns pointing to the next chunk + + EndOfCompressedBufferPlus1 - Points at first byte beyond + compressed buffer + + ChunkBuffer - Receives a pointer to the chunk, if ChunkSize + is nonzero, else undefined + + ChunkSize - Supplies the compressed size of the chunk to be received. + Two special values are 0 and MAX_UNCOMPRESSED_CHUNK_SIZE (4096). + 0 means the chunk should be filled with a pattern that equates + to 4096 0's. 4096 implies that the compression routine should + prepare to receive all of the data in uncompressed form. + +Return Value: + + STATUS_SUCCESS - the chunk size is being returned + + STATUS_BUFFER_TOO_SMALL - the compressed buffer is too small to hold the + compressed data. + +--*/ + +{ + COMPRESSED_CHUNK_HEADER ChunkHeader; + BOOLEAN Compressed; + PUCHAR Tail, NextChunk, DontCare; + ULONG Size; + NTSTATUS Status; + + ASSERT(ChunkSize <= MAX_UNCOMPRESSED_CHUNK_SIZE); + + // + // Calculate the address of the tail of this buffer and its + // size, so it can be moved before we store anything. + // + + Tail = NextChunk = *CompressedBuffer; + while (NT_SUCCESS(Status = RtlDescribeChunkLZNT1( &NextChunk, + EndOfCompressedBufferPlus1, + &DontCare, + &Size))) { + + // + // First time through the loop, capture the address of the next chunk. + // + + if (Tail == *CompressedBuffer) { + Tail = NextChunk; + } + } + + // + // The buffer could be invalid. + // + + if (Status == STATUS_NO_MORE_ENTRIES) { + + // + // The only way to successfully terminate the loop is by finding a USHORT + // terminator of 0. Now calculate the size including the final USHORT + // we stopped on. + // + + Size = NextChunk - Tail + sizeof(USHORT); + + // + // First initialize outputs + // + + Status = STATUS_BUFFER_TOO_SMALL; + *ChunkBuffer = *CompressedBuffer; + + // + // Make sure that the compressed buffer is at least four bytes long to + // start with, otherwise just return a zero chunk. + // + + if (*CompressedBuffer <= (EndOfCompressedBufferPlus1 - ChunkSize)) { + + // + // If the chunk is uncompressed, then we have to adjust the + // chunk description for the header. + // + + if (ChunkSize == MAX_UNCOMPRESSED_CHUNK_SIZE) { + + // + // Increase ChunkSize to include header. + // + + ChunkSize += 2; + + // + // Move the tail now that we know where to put it. + // + + if ((*CompressedBuffer + ChunkSize + Size) <= EndOfCompressedBufferPlus1) { + + RtlMoveMemory( *CompressedBuffer + ChunkSize, Tail, Size ); + + // + // Build the header and store it for an uncompressed chunk. + // + + SetCompressedChunkHeader( ChunkHeader, + MAX_UNCOMPRESSED_CHUNK_SIZE + 2, + FALSE ); + + RtlStoreUshort( *CompressedBuffer, ChunkHeader.Short ); + + // + // Advance to where the uncompressed data goes. + // + + *ChunkBuffer += 2; + + Status = STATUS_SUCCESS; + } + + // + // Otherwise, if this is a zero chunk we have to build it. + // + + } else if (ChunkSize == 0) { + + // + // It takes 6 bytes to describe a chunk of zeros. + // + + ChunkSize = 6; + + if ((*CompressedBuffer + ChunkSize + Size) <= EndOfCompressedBufferPlus1) { + + // + // Move the tail now that we know where to put it. + // + + RtlMoveMemory( *CompressedBuffer + ChunkSize, Tail, Size ); + + // + // Build the header and store it + // + + SetCompressedChunkHeader( ChunkHeader, + 6, + TRUE ); + + RtlStoreUshort( *CompressedBuffer, ChunkHeader.Short ); + + // + // Now store the mask byte with one literal and the literal + // is 0. + // + + RtlStoreUshort( *CompressedBuffer + 2, (USHORT)2 ); + + // + // Now store the copy token for copying 4095 bytes from + // the preceding byte (stored as offset 0). + // + + RtlStoreUshort( *CompressedBuffer + 4, (USHORT)(4095-3)); + + Status = STATUS_SUCCESS; + } + + // + // Otherwise we have a normal compressed chunk. + // + + } else { + + // + // Move the tail now that we know where to put it. + // + + if ((*CompressedBuffer + ChunkSize + Size) <= EndOfCompressedBufferPlus1) { + + RtlMoveMemory( *CompressedBuffer + ChunkSize, Tail, Size ); + + Status = STATUS_SUCCESS; + } + } + + // + // Advance the *CompressedBuffer before return + // + + *CompressedBuffer += ChunkSize; + } + } + + return Status; +} + + +// +// The Copy token is two bytes in size. +// Our definition uses a union to make it easier to set and retrieve token values. +// +// Copy Token +// +// Length Displacement +// +// 12 bits 3 to 4098 4 bits 1 to 16 +// 11 bits 3 to 2050 5 bits 1 to 32 +// 10 bits 3 to 1026 6 bits 1 to 64 +// 9 bits 3 to 514 7 bits 1 to 128 +// 8 bits 3 to 258 8 bits 1 to 256 +// 7 bits 3 to 130 9 bits 1 to 512 +// 6 bits 3 to 66 10 bits 1 to 1024 +// 5 bits 3 to 34 11 bits 1 to 2048 +// 4 bits 3 to 18 12 bits 1 to 4096 +// + +#define FORMAT412 0 +#define FORMAT511 1 +#define FORMAT610 2 +#define FORMAT79 3 +#define FORMAT88 4 +#define FORMAT97 5 +#define FORMAT106 6 +#define FORMAT115 7 +#define FORMAT124 8 + +// 4/12 5/11 6/10 7/9 8/8 9/7 10/6 11/5 12/4 + +ULONG FormatMaxLength[] = { 4098, 2050, 1026, 514, 258, 130, 66, 34, 18 }; +ULONG FormatMaxDisplacement[] = { 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 }; + +typedef union _LZNT1_COPY_TOKEN { + + struct { USHORT Length : 12; USHORT Displacement : 4; } Fields412; + struct { USHORT Length : 11; USHORT Displacement : 5; } Fields511; + struct { USHORT Length : 10; USHORT Displacement : 6; } Fields610; + struct { USHORT Length : 9; USHORT Displacement : 7; } Fields79; + struct { USHORT Length : 8; USHORT Displacement : 8; } Fields88; + struct { USHORT Length : 7; USHORT Displacement : 9; } Fields97; + struct { USHORT Length : 6; USHORT Displacement : 10; } Fields106; + struct { USHORT Length : 5; USHORT Displacement : 11; } Fields115; + struct { USHORT Length : 4; USHORT Displacement : 12; } Fields124; + + UCHAR Bytes[2]; + +} LZNT1_COPY_TOKEN, *PLZNT1_COPY_TOKEN; + +// +// USHORT +// GetLZNT1Length ( +// IN COPY_TOKEN_FORMAT Format, +// IN LZNT1_COPY_TOKEN CopyToken +// ); +// +// USHORT +// GetLZNT1Displacement ( +// IN COPY_TOKEN_FORMAT Format, +// IN LZNT1_COPY_TOKEN CopyToken +// ); +// +// VOID +// SetLZNT1 ( +// IN COPY_TOKEN_FORMAT Format, +// IN LZNT1_COPY_TOKEN CopyToken, +// IN USHORT Length, +// IN USHORT Displacement +// ); +// + +#define GetLZNT1Length(F,CT) ( \ + ( F == FORMAT412 ? (CT).Fields412.Length + 3 \ + : F == FORMAT511 ? (CT).Fields511.Length + 3 \ + : F == FORMAT610 ? (CT).Fields610.Length + 3 \ + : F == FORMAT79 ? (CT).Fields79.Length + 3 \ + : F == FORMAT88 ? (CT).Fields88.Length + 3 \ + : F == FORMAT97 ? (CT).Fields97.Length + 3 \ + : F == FORMAT106 ? (CT).Fields106.Length + 3 \ + : F == FORMAT115 ? (CT).Fields115.Length + 3 \ + : (CT).Fields124.Length + 3 \ + ) \ +) + +#define GetLZNT1Displacement(F,CT) ( \ + ( F == FORMAT412 ? (CT).Fields412.Displacement + 1 \ + : F == FORMAT511 ? (CT).Fields511.Displacement + 1 \ + : F == FORMAT610 ? (CT).Fields610.Displacement + 1 \ + : F == FORMAT79 ? (CT).Fields79.Displacement + 1 \ + : F == FORMAT88 ? (CT).Fields88.Displacement + 1 \ + : F == FORMAT97 ? (CT).Fields97.Displacement + 1 \ + : F == FORMAT106 ? (CT).Fields106.Displacement + 1 \ + : F == FORMAT115 ? (CT).Fields115.Displacement + 1 \ + : (CT).Fields124.Displacement + 1 \ + ) \ +) + +#define SetLZNT1(F,CT,L,D) { \ + if (F == FORMAT412) { (CT).Fields412.Length = (L) - 3; (CT).Fields412.Displacement = (D) - 1; } \ + else if (F == FORMAT511) { (CT).Fields511.Length = (L) - 3; (CT).Fields511.Displacement = (D) - 1; } \ + else if (F == FORMAT610) { (CT).Fields610.Length = (L) - 3; (CT).Fields610.Displacement = (D) - 1; } \ + else if (F == FORMAT79) { (CT).Fields79.Length = (L) - 3; (CT).Fields79.Displacement = (D) - 1; } \ + else if (F == FORMAT88) { (CT).Fields88.Length = (L) - 3; (CT).Fields88.Displacement = (D) - 1; } \ + else if (F == FORMAT97) { (CT).Fields97.Length = (L) - 3; (CT).Fields97.Displacement = (D) - 1; } \ + else if (F == FORMAT106) { (CT).Fields106.Length = (L) - 3; (CT).Fields106.Displacement = (D) - 1; } \ + else if (F == FORMAT115) { (CT).Fields115.Length = (L) - 3; (CT).Fields115.Displacement = (D) - 1; } \ + else { (CT).Fields124.Length = (L) - 3; (CT).Fields124.Displacement = (D) - 1; } \ +} + + +// +// Local support routine +// + +NTSTATUS +LZNT1CompressChunk ( + IN PLZNT1_MATCH_FUNCTION MatchFunction, + IN PUCHAR UncompressedBuffer, + IN PUCHAR EndOfUncompressedBufferPlus1, + OUT PUCHAR CompressedBuffer, + IN PUCHAR EndOfCompressedBufferPlus1, + OUT PULONG FinalCompressedChunkSize, + IN PVOID WorkSpace + ) + +/*++ + +Routine Description: + + This routine takes as input an uncompressed chunk and produces + one compressed chunk provided the compressed data fits within + the specified destination buffer. + + The LZNT1 format used to store the compressed buffer. + + An output variable indicates the number of bytes used to store + the compressed chunk. + +Arguments: + + UncompressedBuffer - Supplies a pointer to the uncompressed chunk. + + EndOfUncompressedBufferPlus1 - Supplies a pointer to the next byte + following the end of the uncompressed buffer. This is supplied + instead of the size in bytes because our caller and ourselves + test against the pointer and by passing the pointer we get to + skip the code to compute it each time. + + CompressedBuffer - Supplies a pointer to where the compressed chunk + is to be stored. + + EndOfCompressedBufferPlus1 - Supplies a pointer to the next + byte following the end of the compressed buffer. + + FinalCompressedChunkSize - Receives the number of bytes needed in + the compressed buffer to store the compressed chunk. + +Return Value: + + STATUS_SUCCESS - the compression worked without a hitch. + + STATUS_BUFFER_ALL_ZEROS - the compression worked without a hitch and in + addition the input chunk was all zeros. + + STATUS_BUFFER_TOO_SMALL - the compressed buffer is too small to hold the + compressed data. + +--*/ + +{ + PUCHAR EndOfCompressedChunkPlus1; + + PUCHAR InputPointer; + PUCHAR OutputPointer; + + PUCHAR FlagPointer; + UCHAR FlagByte; + ULONG FlagBit; + + LONG Length; + LONG Displacement; + + LZNT1_COPY_TOKEN CopyToken; + + COMPRESSED_CHUNK_HEADER ChunkHeader; + + UCHAR NullCharacter = 0; + + ULONG Format = FORMAT412; + + // + // First adjust the end of the uncompressed buffer pointer to the smaller + // of what we're passed in and the uncompressed chunk size. We use this + // to make sure we never compress more than a chunk worth at a time + // + + if ((UncompressedBuffer + MAX_UNCOMPRESSED_CHUNK_SIZE) < EndOfUncompressedBufferPlus1) { + + EndOfUncompressedBufferPlus1 = UncompressedBuffer + MAX_UNCOMPRESSED_CHUNK_SIZE; + } + + // + // Now set the end of the compressed chunk pointer to be the smaller of the + // compressed size necessary to hold the data in an uncompressed form and + // the compressed buffer size. We use this to decide if we can't compress + // any more because the buffer is too small or just because the data + // doesn't compress very well. + // + + if ((CompressedBuffer + MAX_UNCOMPRESSED_CHUNK_SIZE + sizeof(COMPRESSED_CHUNK_HEADER)) < EndOfCompressedBufferPlus1) { + + EndOfCompressedChunkPlus1 = CompressedBuffer + MAX_UNCOMPRESSED_CHUNK_SIZE + sizeof(COMPRESSED_CHUNK_HEADER); + + } else { + + EndOfCompressedChunkPlus1 = EndOfCompressedBufferPlus1; + } + + // + // Now set the input and output pointers to the next byte we are + // go to process and asser that the user gave use buffers that were + // large enough to hold the minimum size chunks + // + + InputPointer = UncompressedBuffer; + OutputPointer = CompressedBuffer + sizeof(COMPRESSED_CHUNK_HEADER); + + ASSERT(InputPointer < EndOfUncompressedBufferPlus1); + //**** ASSERT(OutputPointer + 2 <= EndOfCompressedChunkPlus1); + + // + // The flag byte stores a copy of the flags for the current + // run and the flag bit denotes the current bit position within + // the flag that we are processing. The Flag pointer denotes + // where in the compressed buffer we will store the current + // flag byte + // + + FlagPointer = OutputPointer++; + FlagBit = 0; + FlagByte = 0; + + ChunkHeader.Short = 0; + + // + // While there is some more data to be compressed we will do the + // following loop + // + + ((PLZNT1_STANDARD_WORKSPACE)WorkSpace)->UncompressedBuffer = UncompressedBuffer; + ((PLZNT1_STANDARD_WORKSPACE)WorkSpace)->EndOfUncompressedBufferPlus1 = EndOfUncompressedBufferPlus1; + ((PLZNT1_STANDARD_WORKSPACE)WorkSpace)->MaxLength = FormatMaxLength[FORMAT412]; + + while (InputPointer < EndOfUncompressedBufferPlus1) { + + while (UncompressedBuffer + FormatMaxDisplacement[Format] < InputPointer) { + + Format += 1; + ((PLZNT1_STANDARD_WORKSPACE)WorkSpace)->MaxLength = FormatMaxLength[Format]; + } + + // + // Search for a string in the Lempel + // + + Length = 0; + if ((InputPointer + 3) <= EndOfUncompressedBufferPlus1) { + + Length = (MatchFunction)( InputPointer, WorkSpace ); + } + + // + // If the return length is zero then we need to output + // a literal. We clear the flag bit to denote the literal + // output the charcter and build up a character bits + // composite that if it is still zero when we are done then + // we know the uncompressed buffer contained only zeros. + // + + if (!Length) { + + // + // There is more data to output now make sure the output + // buffer is not already full and can contain at least one + // more byte + // + + if (OutputPointer >= EndOfCompressedChunkPlus1) { break; } + + ClearFlag(FlagByte, (1 << FlagBit)); + + NullCharacter |= *(OutputPointer++) = *(InputPointer++); + + } else { + + // + // We need to output two byte, now make sure that + // the output buffer can contain at least two more + // bytes. + // + + if ((OutputPointer+1) >= EndOfCompressedChunkPlus1) { break; } + + // + // Compute the displacement from the current pointer + // to the matched string + // + + Displacement = InputPointer - ((PLZNT1_STANDARD_WORKSPACE)WorkSpace)->MatchedString; + + // + // Make sure there is enough room in the output buffer + // for two bytes + // + + if ((OutputPointer + 1) >= EndOfCompressedChunkPlus1) { break; } + + SetFlag(FlagByte, (1 << FlagBit)); + + SetLZNT1(Format, CopyToken, Length, Displacement); + + *(OutputPointer++) = CopyToken.Bytes[0]; + *(OutputPointer++) = CopyToken.Bytes[1]; + + InputPointer += Length; + } + + // + // Now adjust the flag bit and check if the flag byte + // should now be output. If so output the flag byte + // and scarf up a new byte in the output buffer for the + // next flag byte + // + + FlagBit = (FlagBit + 1) % 8; + + if (!FlagBit) { + + *FlagPointer = FlagByte; + FlagByte = 0; + + FlagPointer = (OutputPointer++); + } + } + + // + // We've exited the preceeding loop because either the input buffer is + // all compressed or because we ran out of space in the output buffer. + // Check here if the input buffer is not exhasted (i.e., we ran out + // of space) + // + + if (InputPointer < EndOfUncompressedBufferPlus1) { + + // + // We ran out of space, but now if the total space available + // for the compressed chunk is equal to the uncompressed data plus + // the header then we will make this an uncompressed chunk and copy + // over the uncompressed data + // + + if ((CompressedBuffer + MAX_UNCOMPRESSED_CHUNK_SIZE + sizeof(COMPRESSED_CHUNK_HEADER)) <= EndOfCompressedBufferPlus1) { + + RtlCopyMemory( CompressedBuffer + sizeof(COMPRESSED_CHUNK_HEADER), + UncompressedBuffer, + MAX_UNCOMPRESSED_CHUNK_SIZE ); + + *FinalCompressedChunkSize = MAX_UNCOMPRESSED_CHUNK_SIZE + sizeof(COMPRESSED_CHUNK_HEADER); + + SetCompressedChunkHeader( ChunkHeader, + (LONG)*FinalCompressedChunkSize, + FALSE ); + + RtlStoreUshort( CompressedBuffer, ChunkHeader.Short ); + + return STATUS_SUCCESS; + } + + // + // Otherwise the input buffer really is too small to store the + // compressed chuunk + // + + return STATUS_BUFFER_TOO_SMALL; + } + + // + // At this point the entire input buffer has been compressed so we need + // to output the last flag byte, provided it fits in the compressed buffer, + // set and store the chunk header. Now if the Flag pointer doesn't fit + // in the output buffer that is because it is one beyond the end and + // we incremented output pointer too far so now bring output pointer + // back down. + // + + if (FlagPointer < EndOfCompressedChunkPlus1) { + + *FlagPointer = FlagByte; + + } else { + + OutputPointer--; + } + + *FinalCompressedChunkSize = (OutputPointer - CompressedBuffer); + + SetCompressedChunkHeader( ChunkHeader, + (LONG)*FinalCompressedChunkSize, + TRUE ); + + RtlStoreUshort( CompressedBuffer, ChunkHeader.Short ); + + // + // Now if the only literal we ever output was a null then the + // input buffer was all zeros. + // + + if (!NullCharacter) { + + return STATUS_BUFFER_ALL_ZEROS; + } + + // + // Otherwise return to our caller + // + + return STATUS_SUCCESS; +} + + +#if !defined(_ALPHA_) +#if !defined(_MIPS_) +#if !defined(_PPC_) +#if !defined(i386) +// +// Local support routine +// + +NTSTATUS +LZNT1DecompressChunk ( + OUT PUCHAR UncompressedBuffer, + IN PUCHAR EndOfUncompressedBufferPlus1, + IN PUCHAR CompressedBuffer, + IN PUCHAR EndOfCompressedBufferPlus1, + OUT PULONG FinalUncompressedChunkSize + ) + +/*++ + +Routine Description: + + This routine takes as input a compressed chunk and produces its + uncompressed equivalent chunk provided the uncompressed data fits + within the specified destination buffer. + + The compressed buffer must be stored in the LZNT1 format. + + An output variable indicates the number of bytes used to store the + uncompressed data. + +Arguments: + + UncompressedBuffer - Supplies a pointer to where the uncompressed + chunk is to be stored. + + EndOfUncompressedBufferPlus1 - Supplies a pointer to the next byte + following the end of the uncompressed buffer. This is supplied + instead of the size in bytes because our caller and ourselves + test against the pointer and by passing the pointer we get to + skip the code to compute it each time. + + CompressedBuffer - Supplies a pointer to the compressed chunk. (This + pointer has already been adjusted to point past the chunk header.) + + EndOfCompressedBufferPlus1 - Supplies a pointer to the next + byte following the end of the compressed buffer. + + FinalUncompressedChunkSize - Receives the number of bytes needed in + the uncompressed buffer to store the uncompressed chunk. + +Return Value: + + STATUS_SUCCESS - the decompression worked without a hitch. + + STATUS_BAD_COMPRESSION_BUFFER - the input compressed buffer is + ill-formed. + +--*/ + +{ + PUCHAR OutputPointer; + PUCHAR InputPointer; + + UCHAR FlagByte; + ULONG FlagBit; + + ULONG Format = FORMAT412; + + // + // The two pointers will slide through our input and input buffer. + // For the input buffer we skip over the chunk header. + // + + OutputPointer = UncompressedBuffer; + InputPointer = CompressedBuffer; + + // + // The flag byte stores a copy of the flags for the current + // run and the flag bit denotes the current bit position within + // the flag that we are processing + // + + FlagByte = *(InputPointer++); + FlagBit = 0; + + // + // While we haven't exhausted either the input or output buffer + // we will do some more decompression + // + + while ((OutputPointer < EndOfUncompressedBufferPlus1) && (InputPointer < EndOfCompressedBufferPlus1)) { + + while (UncompressedBuffer + FormatMaxDisplacement[Format] < OutputPointer) { Format += 1; } + + // + // Check the current flag if it is zero then the current + // input token is a literal byte that we simply copy over + // to the output buffer + // + + if (!FlagOn(FlagByte, (1 << FlagBit))) { + + *(OutputPointer++) = *(InputPointer++); + + } else { + + LZNT1_COPY_TOKEN CopyToken; + LONG Displacement; + LONG Length; + + // + // The current input is a copy token so we'll get the + // copy token into our variable and extract the + // length and displacement from the token + // + + if (InputPointer+1 >= EndOfCompressedBufferPlus1) { + + *FinalUncompressedChunkSize = (ULONG)InputPointer; + + return STATUS_BAD_COMPRESSION_BUFFER; + } + + // + // Now grab the next input byte and extract the + // length and displacement from the copy token + // + + CopyToken.Bytes[0] = *(InputPointer++); + CopyToken.Bytes[1] = *(InputPointer++); + + Displacement = GetLZNT1Displacement(Format, CopyToken); + Length = GetLZNT1Length(Format, CopyToken); + + // + // At this point we have the length and displacement + // from the copy token, now we need to make sure that the + // displacement doesn't send us outside the uncompressed buffer + // + + if (Displacement > (OutputPointer - UncompressedBuffer)) { + + *FinalUncompressedChunkSize = (ULONG)InputPointer; + + return STATUS_BAD_COMPRESSION_BUFFER; + } + + // + // We also need to adjust the length to keep the copy from + // overflowing the output buffer + // + + if ((OutputPointer + Length) >= EndOfUncompressedBufferPlus1) { + + Length = EndOfUncompressedBufferPlus1 - OutputPointer; + } + + // + // Now we copy bytes. We cannot use Rtl Move Memory here because + // it does the copy backwards from what the LZ algorithm needs. + // + + while (Length > 0) { + + *(OutputPointer) = *(OutputPointer-Displacement); + + Length -= 1; + OutputPointer += 1; + } + } + + // + // Before we go back to the start of the loop we need to adjust the + // flag bit value (it goes from 0, 1, ... 7) and if the flag bit + // is back to zero we need to read in the next flag byte. In this + // case we are at the end of the input buffer we'll just break out + // of the loop because we're done. + // + + FlagBit = (FlagBit + 1) % 8; + + if (!FlagBit) { + + if (InputPointer >= EndOfCompressedBufferPlus1) { break; } + + FlagByte = *(InputPointer++); + } + } + + // + // The decompression is done so now set the final uncompressed + // chunk size and return success to our caller + // + + *FinalUncompressedChunkSize = OutputPointer - UncompressedBuffer; + + return STATUS_SUCCESS; +} +#endif // i386 +#endif // _MIPS_ +#endif // _PPC_ +#endif // _ALPHA_ + + +// +// Local support routine +// + +ULONG +LZNT1FindMatchStandard ( + IN PUCHAR ZivString, + IN PLZNT1_STANDARD_WORKSPACE WorkSpace + ) + +/*++ + +Routine Description: + + This routine does the compression lookup. It locates + a match for the ziv within a specified uncompressed buffer. + +Arguments: + + ZivString - Supplies a pointer to the Ziv in the uncompressed buffer. + The Ziv is the string we want to try and find a match for. + +Return Value: + + Returns the length of the match if the match is greater than three + characters otherwise return 0. + +--*/ + +{ + PUCHAR UncompressedBuffer = WorkSpace->UncompressedBuffer; + PUCHAR EndOfUncompressedBufferPlus1 = WorkSpace->EndOfUncompressedBufferPlus1; + ULONG MaxLength = WorkSpace->MaxLength; + + ULONG Index; + + PUCHAR FirstEntry; + ULONG FirstLength; + + PUCHAR SecondEntry; + ULONG SecondLength; + + // + // First check if the Ziv is within two bytes of the end of + // the uncompressed buffer, if so then we can't match + // three or more characters + // + + Index = ((40543*((((ZivString[0]<<4)^ZivString[1])<<4)^ZivString[2]))>>4) & 0xfff; + + FirstEntry = WorkSpace->IndexPTable[Index][0]; + FirstLength = 0; + + SecondEntry = WorkSpace->IndexPTable[Index][1]; + SecondLength = 0; + + // + // Check if first entry is good, and if so then get its length + // + + if ((FirstEntry >= UncompressedBuffer) && // is it within the uncompressed buffer? + (FirstEntry < ZivString) && + + (FirstEntry[0] == ZivString[0]) && // do at least 3 characters match? + (FirstEntry[1] == ZivString[1]) && + (FirstEntry[2] == ZivString[2])) { + + FirstLength = 3; + + while ((FirstLength < MaxLength) + + && + + (ZivString + FirstLength < EndOfUncompressedBufferPlus1) + + && + + (ZivString[FirstLength] == FirstEntry[FirstLength])) { + + FirstLength++; + } + } + + // + // Check if second entry is good, and if so then get its length + // + + if ((SecondEntry >= UncompressedBuffer) && // is it within the uncompressed buffer? + (SecondEntry < ZivString) && + + (SecondEntry[0] == ZivString[0]) && // do at least 3 characters match? + (SecondEntry[1] == ZivString[1]) && + (SecondEntry[2] == ZivString[2])) { + + SecondLength = 3; + + while ((SecondLength < MaxLength) + + && + + (ZivString + SecondLength< EndOfUncompressedBufferPlus1) + + && + + (ZivString[SecondLength] == SecondEntry[SecondLength])) { + + SecondLength++; + } + } + + if ((FirstLength >= SecondLength)) { + + WorkSpace->IndexPTable[Index][1] = FirstEntry; + WorkSpace->IndexPTable[Index][0] = ZivString; + + WorkSpace->MatchedString = FirstEntry; + return FirstLength; + } + + WorkSpace->IndexPTable[Index][1] = FirstEntry; + WorkSpace->IndexPTable[Index][0] = ZivString; + + WorkSpace->MatchedString = SecondEntry; + return SecondLength; +} + + +// +// Local support routine +// + +ULONG +LZNT1FindMatchMaximum ( + IN PUCHAR ZivString, + IN PLZNT1_MAXIMUM_WORKSPACE WorkSpace + ) + +/*++ + +Routine Description: + + This routine does the compression lookup. It locates + a match for the ziv within a specified uncompressed buffer. + + If the matched string is two or more characters long then this + routine does not update the lookup state information. + +Arguments: + + ZivString - Supplies a pointer to the Ziv in the uncompressed buffer. + The Ziv is the string we want to try and find a match for. + +Return Value: + + Returns the length of the match if the match is greater than three + characters otherwise return 0. + +--*/ + +{ + PUCHAR UncompressedBuffer = WorkSpace->UncompressedBuffer; + PUCHAR EndOfUncompressedBufferPlus1 = WorkSpace->EndOfUncompressedBufferPlus1; + ULONG MaxLength = WorkSpace->MaxLength; + + ULONG i; + ULONG BestMatchedLength; + PUCHAR q; + + // + // First check if the Ziv is within two bytes of the end of + // the uncompressed buffer, if so then we can't match + // three or more characters + // + + BestMatchedLength = 0; + + for (q = UncompressedBuffer; q < ZivString; q += 1) { + + i = 0; + + while ((i < MaxLength) + + && + + (ZivString + i < EndOfUncompressedBufferPlus1) + + && + + (ZivString[i] == q[i])) { + + i++; + } + + if (i >= BestMatchedLength) { + + BestMatchedLength = i; + WorkSpace->MatchedString = q; + } + } + + if (BestMatchedLength < 3) { + + return 0; + + } else { + + return BestMatchedLength; + } +} + |