diff options
Diffstat (limited to 'private/utils/ufat/src/mrcf.c')
| -rw-r--r-- | private/utils/ufat/src/mrcf.c | 1726 |
1 files changed, 1726 insertions, 0 deletions
diff --git a/private/utils/ufat/src/mrcf.c b/private/utils/ufat/src/mrcf.c new file mode 100644 index 000000000..39816b175 --- /dev/null +++ b/private/utils/ufat/src/mrcf.c @@ -0,0 +1,1726 @@ +/*++ + +Copyright (c) 1989 Microsoft Corporation + +Module Name: + + Mrcf.c + +Abstract: + + This module implements the Compress routines for the Double Space File System + +Author: + + Gary Kimura [GaryKi] 26-May-1993 + +Revision History: + +--*/ + +#include <stdio.h> +#include <nt.h> +#include "mrcf.h" + +//XXX.mjb: +#define DbgAssert(x) /* nothing */ + +// +// The debug macros +// + +#ifdef MRCFDBG + +#define DbgDoit(X) {X;} +#define ChPrint(b) (isprint(b) ? b : '.') +#define DbgPrint printf + +#else + +#define DbgDoit(X) {NOTHING;} + +#endif // MRCFDBG + + +// +// Compress this much before each EOS +// + +#define cbCOMPRESSCHUNK (512) + +// +// Maximum back-pointer value, also used to indicate end of compressed stream! +// + +#define wBACKPOINTERMAX (4415) + +// +// bitsEND_OF_STREAM - bits that mark end of compressed stream (EOS) +// +// This pattern is used to indicate the end of a "chunk" in a compressed +// data stream. The Compress code compresses up to 512 bytes, writes +// this pattern, and continues. +// +// NOTE: This diagram is interpreted right to left. +// +// ? ---offset---- +// +// ?.111-1111-1111-1.1.11 +// +// \---7F---/ \----FF---/ +// +// This is a 12-bit "match" code with a maximum offset. +// NOTE: There is no length component! +// +// Define the EOS and also say how many bits it is. +// + +#define bitsEND_OF_STREAM (0x7FFF) +#define cbitsEND_OF_STREAM (15) + +// +// MDSIGNATURE - Signature at start of each compressed block +// +// This 4-byte signature is used as a check to ensure that we +// are decompressing data we compressed, and also to indicate +// which compression method was used. +// +// NOTE: A compressed block consists of one or more "chunks", separated +// by the bitsEND_OF_STREAM pattern. +// +// Byte Word +// ----------- --------- +// 0 1 2 3 0 1 Meaning +// -- -- -- -- ---- ---- ---------------- +// 44 53 00 01 5344 0100 MaxCompression +// 44 53 00 02 5344 0200 StandardCompression +// +// NOTE: The *WORD* values are listed to be clear about the +// byte ordering! +// + +typedef struct _MDSIGNATURE { + + // + // Must be MD_STAMP + // + + USHORT sigStamp; + + // + // mdsSTANDARD or mdsMAX + // + + USHORT sigType; + +} MDSIGNATURE; +typedef MDSIGNATURE *PMDSIGNATURE; + +#define MD_STAMP 0x5344 // Signature stamp at start of compressed blk +#define mdsSTANDARD 0x0200 // StandardCompressed block +#define MASK_VALID_mds 0x0300 // All other bits must be zero + + +// +// Local procedure declarations and macros +// + +#define min(a,b) (a < b ? a : b) + +// +// PFNFINDMATCH - Lookup function type for XxxxCompression routines +// + +typedef ULONG (*PFNFINDMATCH) ( + ULONG UncompressedIndex, + PUCHAR UncompressedBuffer, + ULONG UncompressedLength, + PULONG MatchedStringIndex, + PMRCF_STANDARD_COMPRESS WorkSpace + ); + +// +// Local procedure prototypes +// + +ULONG +MrcfDoCompress ( + PUCHAR CompressedBuffer, + ULONG CompressedLength, + PUCHAR UncompressedBuffer, + ULONG UncompressedLength, + PFNFINDMATCH FindMatchFunction, + PMRCF_STANDARD_COMPRESS WorkSpace + ); + +ULONG +MrcfCompressChunk ( + PUCHAR UncompressedBuffer, + ULONG UncompressedIndex, + ULONG UncompressedLength, + PFNFINDMATCH FindMatchFunction, + PMRCF_STANDARD_COMPRESS WorkSpace + ); + +ULONG +MrcfFindMatchStandard ( + ULONG UncompressedIndex, + PUCHAR UncompressedBuffer, + ULONG UncompressedLength, + PULONG MatchedStringIndex, + PMRCF_STANDARD_COMPRESS WorkSpace + ); + +ULONG +MrcfGetMatchLength ( + PUCHAR UncompressedBuffer, + ULONG MatchIndex, + ULONG CurrentIndex, + ULONG UncompressedLength + ); + +BOOLEAN +MrcfEncodeByte ( + UCHAR b, + PMRCF_BIT_IO BitIo + ); + +BOOLEAN +MrcfEncodeMatch ( + ULONG off, + ULONG cb, + PMRCF_BIT_IO BitIo + ); + +VOID +MrcfSetBitBuffer ( + PUCHAR pb, + ULONG cb, + PMRCF_BIT_IO BitIo + ); + +VOID +MrcfFillBitBuffer ( + PMRCF_BIT_IO BitIo + ); + +USHORT +MrcfReadBit ( + PMRCF_BIT_IO BitIo + ); + +USHORT +MrcfReadNBits ( + LONG cbits, + PMRCF_BIT_IO BitIo + ); + +BOOLEAN +MrcfWriteBit ( + ULONG bit, + PMRCF_BIT_IO BitIo + ); + +BOOLEAN +MrcfWriteNBits ( + ULONG abits, + LONG cbits, + PMRCF_BIT_IO BitIo + ); + +ULONG +MrcfFlushBitBuffer ( + PMRCF_BIT_IO BitIo + ); + +//**** unconverted routines **** + +VOID +MrcfDoInterMaxPairs ( + ULONG ibU, + PUCHAR pbU, + ULONG cbMatch, + PVOID WorkSpace + ); + +ULONG +MrcfDoMaxPairLookup ( + ULONG ibU, + PUCHAR pbU, + PVOID WorkSpace + ); + +ULONG +MrcfFindMatchMax ( + ULONG ibU, + PUCHAR pbU, + ULONG cbU, + PULONG piPrev, + BOOLEAN fLast, + PVOID WorkSpace + ); + + +ULONG +MrcfDecompress ( + PUCHAR UncompressedBuffer, + ULONG UncompressedLength, + PUCHAR CompressedBuffer, + ULONG CompressedLength, + PMRCF_DECOMPRESS WorkSpace + ) + +/*++ + +Routine Description: + + This routine decompresses a buffer of StandardCompressed or MaxCompressed + data. + +Arguments: + + UncompressedBuffer - buffer to receive uncompressed data + + UncompressedLength - length of UncompressedBuffer + + NOTE: UncompressedLength must be the EXACT length of the uncompressed + data, as Decompress uses this information to detect + when decompression is complete. If this value is + incorrect, Decompress may crash! + + CompressedBuffer - buffer containing compressed data + + CompressedLength - length of CompressedBuffer + + WorkSpace - pointer to a private work area for use by this operation + +Return Value: + + ULONG - Returns the size of the decompressed data in bytes. Returns 0 if + there was an error in the decompress. + +--*/ + +{ + ULONG cbMatch; // Length of match string + ULONG i; // Index in UncompressedBuffer to receive decoded data + ULONG iMatch; // Index in UncompressedBuffer of matched string + ULONG k; // Number of bits in length string + ULONG off; // Offset from i in UncompressedBuffer of match string + USHORT x; // Current bit being examined + ULONG y; + + // + // verify that compressed data starts with proper signature + // + + if (CompressedLength < sizeof(MDSIGNATURE) || // Must have signature + ((PMDSIGNATURE)CompressedBuffer)->sigStamp != MD_STAMP || // Stamp must be OK + ((PMDSIGNATURE)CompressedBuffer)->sigType & (~MASK_VALID_mds)) { // Type must be OK + + return 0; + } + + // + // Skip over the valid signature + // + + CompressedLength -= sizeof(MDSIGNATURE); + CompressedBuffer += sizeof(MDSIGNATURE); + + // + // Set up for decompress, start filling UncompressedBuffer at front + // + + i = 0; + + // + // Set statics to save parm passing + // + + MrcfSetBitBuffer(CompressedBuffer,CompressedLength,&WorkSpace->BitIo); + + while (TRUE) { + + DbgDoit( DbgPrint("UncompressedOffset i = %3x ",i) ); + DbgDoit( DbgPrint("CompressedOffset = (%3x.%2x) ", WorkSpace->BitIo.cbBBInitial - WorkSpace->BitIo.cbBB, 16 - WorkSpace->BitIo.cbitsBB) ); + + y = MrcfReadNBits(2,&WorkSpace->BitIo); + + // + // Check if next 7 bits are a byte + // 1 if 128..255 (0x80..0xff), 2 if 0..127 (0x00..0x7f) + // + + if (y == 1 || y == 2) { + + DbgAssert(i<UncompressedLength); + + UncompressedBuffer[i] = (UCHAR)((y == 1 ? 0x80 : 0) | MrcfReadNBits(7,&WorkSpace->BitIo)); + + DbgDoit( DbgPrint("byte: %02x = '%c'\n",(USHORT)UncompressedBuffer[i],ChPrint(UncompressedBuffer[i])) ); + + i++; + + } else { + + // + // Have match sequence + // + + DbgDoit( DbgPrint("offset(") ); + + // + // Get the offset + // + + if (y == 0) { + + // + // next 6 bits are offset + // + + off = MrcfReadNBits(6,&WorkSpace->BitIo); + + DbgDoit( DbgPrint("%x): %x",6,off) ); + + DbgAssert(off != 0); + + } else { + + x = MrcfReadBit(&WorkSpace->BitIo); + + if (x == 0) { + + // + // next 8 bits are offset-64 (0x40) + // + + off = MrcfReadNBits(8, &WorkSpace->BitIo) + 64; + + DbgDoit( DbgPrint("%x): %x",8,off) ); + + } else { + + // + // next 12 bits are offset-320 (0x140) + // + + off = MrcfReadNBits(12, &WorkSpace->BitIo) + 320; + + DbgDoit( DbgPrint("%x): %x",12,off) ); + + if (off == wBACKPOINTERMAX) { + + // + // EOS marker + // + + DbgDoit( DbgPrint("; EOS\n") ); + + if (i >= UncompressedLength) { + + // + // Done with entire buffer + // + + DbgDoit( DbgPrint("Uncompressed Length = %x\n",i) ); + + return i; + + } else { + + // + // More to do + // Done with a 512-byte chunk + // + + continue; + } + } + } + } + + DbgAssert(i<UncompressedLength); + DbgAssert(off <= i); + + // + // Get the length - logarithmically encoded + // + + for (k=0; (x=MrcfReadBit(&WorkSpace->BitIo)) == 0; k++) { NOTHING; } + + DbgAssert(k <= 8); + + if (k == 0) { + + // + // All matches at least 2 chars long + // + + cbMatch = 2; + + } else { + + cbMatch = (1 << k) + 1 + MrcfReadNBits(k, &WorkSpace->BitIo); + } + + DbgDoit( DbgPrint("; length=%x; '",cbMatch) ); + + DbgAssert((i - off + cbMatch - 1) <= UncompressedLength); + + // + // Copy the matched string + // + + iMatch = i - off; + + while ( (cbMatch > 0) && (i<UncompressedLength) ) { + + DbgDoit( DbgPrint("%c",ChPrint(UncompressedBuffer[iMatch])) ); + + UncompressedBuffer[i++] = UncompressedBuffer[iMatch++]; + cbMatch--; + } + + DbgDoit( DbgPrint("'\n") ); + + DbgAssert(cbMatch == 0); + } + } +} + + +ULONG +MrcfStandardCompress ( + PUCHAR CompressedBuffer, + ULONG CompressedLength, + PUCHAR UncompressedBuffer, + ULONG UncompressedLength, + PMRCF_STANDARD_COMPRESS WorkSpace + ) + +/*++ + +Routine Description: + + This routine compresses a buffer using the standard compression algorithm. + +Arguments: + + CompressedBuffer - buffer to receive compressed data + + CompressedLength - length of CompressedBuffer + + UncompressedBuffer - buffer containing uncompressed data + + UncompressedLength - length of UncompressedBuffer + + WorkSpace - pointer to a private work area for use by this operation + +Return Value: + + ULONG - Returns the size of the compressed data in bytes. Returns 0 if + the data is not compressible + +--*/ + +{ + ULONG i,j; + + // + // Fill lookup tables with initial values + // + + for (i=0; i<256; i++) { + + for (j = 0; j < cMAXSLOTS; j++) { + + WorkSpace->ltX[i][j] = ltUNUSED; // Mark offset look-up entries unused + WorkSpace->abChar[i][j] = bRARE; // Mark match char entries unused + } + + WorkSpace->abMRUX[i] = mruUNUSED; // MRU pointer = unused + } + + // + // Do compression, first set type and then do the compression + // + + ((PMDSIGNATURE)CompressedBuffer)->sigType = mdsSTANDARD; + + return MrcfDoCompress( CompressedBuffer, + CompressedLength, + UncompressedBuffer, + UncompressedLength, + MrcfFindMatchStandard, + WorkSpace ); +} + + +// +// Internal Support Routine +// + +ULONG +MrcfDoCompress ( + PUCHAR CompressedBuffer, + ULONG CompressedLength, + PUCHAR UncompressedBuffer, + ULONG UncompressedLength, + PFNFINDMATCH FindMatchFunction, + PMRCF_STANDARD_COMPRESS WorkSpace + ) + +/*++ + +Routine Description: + + This routine compresses a data buffer + +Arguments: + + CompressedBuffer - buffer to receive compressed data + + CompressedLength - length of CompressedBuffer + + UncompressedBuffer - buffer containing uncompressed data + + UncompressedLength - length of UncompressedBuffer + + FindMatchFunction - matching function + + WorkSpace - Supplies a pointer to the bit buffer statics + +Return Value: + + ULONG - Returns the size of the compressed data in bytes. Returns 0 if + the data is not compressible + +--*/ + +{ + ULONG cbDone; // Count of uncompressed bytes processed so far + ULONG cb; // Count of bytes processed in a chunk + + DbgAssert(CompressedLength >= UncompressedLength); + + // + // Treat zero-length request specially as Not compressible + // + + if (UncompressedLength == 0) { return 0; } + + // + // Write signature to compressed data block + // + + ((PMDSIGNATURE)CompressedBuffer)->sigStamp = MD_STAMP; + + CompressedLength -= sizeof(MDSIGNATURE); + CompressedBuffer += sizeof(MDSIGNATURE); + + // + // Set statics to save parm passing + // + + MrcfSetBitBuffer(CompressedBuffer, CompressedLength, &WorkSpace->BitIo); + + // + // Start with first chunk + // and process entire buffer + // + + cbDone = 0; + + while (cbDone < UncompressedLength) { + + // + // Compress a chunk + // + + cb = MrcfCompressChunk( UncompressedBuffer, + cbDone, + UncompressedLength, + FindMatchFunction, + WorkSpace ); + + // + // Check if we could not compress, i.e., Not compressible + // + + if (cb == 0) { return 0; } + + cbDone += cb; + + if (FALSE) { //**** if (WorkSpace->fMaxCmp) { + + // + // MAXCMP check + // + + if ((cbDone < UncompressedLength) && (WorkSpace->BitIo.cbBB < 586)) { return 0; } + + } else { + + // + // RCOMP check + // + + //**** if (WorkSpace->BitIo.cbBB <= 586) { return 0; } + } + } + + DbgAssert(cbDone == UncompressedLength); + + // + // Make sure we saved some space + // + + cb = sizeof(MDSIGNATURE) + MrcfFlushBitBuffer( &WorkSpace->BitIo ); + + if (TRUE) { //**** if (!WorkSpace->fMaxCmp) { + + if (cb+8 >= UncompressedLength) { return 0; } + } + + if (cb < UncompressedLength) { + + return cb; + + } else { + + return 0; + } +} + + +// +// Internal Support Routine +// + +ULONG +MrcfCompressChunk ( + PUCHAR UncompressedBuffer, + ULONG UncompressedIndex, + ULONG UncompressedLength, + PFNFINDMATCH FindMatchFunction, + PMRCF_STANDARD_COMPRESS WorkSpace + ) + +/*++ + +Routine Description: + + This routine compresses a chunk of uncompressed data + +Arguments: + + UncompressedBuffer - buffer containing uncompressed data + + UncompressedIndex - index in UncompressedBuffer to start compressing (0 => first byte) + + UncompressedLength - length of UncompressedBuffer + + FindMatchFunction - matching function + + WorkSpace - Supplies a pointer to the bit buffer statics + +Return Value: + + ULONG - Returns the non-zero count of uncompressed bytes processed. + Returns 0 if the data is not compressible + +--*/ + +{ + UCHAR b1; // First byte of pair + UCHAR b2; // Second byte of pair + ULONG cbChunk; // Count of bytes in chunk to compress + ULONG cbMatch; // Count of bytes matched + ULONG cbUChunk; // Phony buffer length, for compressing this chunk + BOOLEAN fLast; // TRUE if this is the last chunk + ULONG i; // Index in byte stream being compressed + ULONG iPrev; // Previous table entry + + DbgAssert(UncompressedLength > 0); + DbgAssert(UncompressedBuffer != 0); + DbgAssert(UncompressedIndex < UncompressedLength); + + // + // Only compress one chunk + // + + cbChunk = min((UncompressedLength-UncompressedIndex),cbCOMPRESSCHUNK); + + // + // Limit to chunk length + // + + cbUChunk = UncompressedIndex + cbChunk; + + DbgAssert(cbUChunk <= UncompressedLength); + + // + // TRUE if last chunk of buffer + // + + fLast = (cbUChunk == UncompressedLength); + + // + // Limit to chunk length + // + + UncompressedLength = cbUChunk; + + // + // Scan each pair of bytes + // + + // + // First byte of input + // + + b2 = UncompressedBuffer[UncompressedIndex]; + + // + // Process all bytes in chunk + // + + for (i=UncompressedIndex+1; i<UncompressedLength; ) { + + // + // Set Last byte, Next byte, and find a match + // + + b1 = b2; + b2 = UncompressedBuffer[i]; + + cbMatch = (*FindMatchFunction)(i,UncompressedBuffer,UncompressedLength,&iPrev,WorkSpace); + + // + // Check if we got match + // + + if (cbMatch >= 2) { + + DbgDoit( DbgPrint("<Match>: '%c%c' at offset %x for length %x\n", + ChPrint(UncompressedBuffer[i-1]),ChPrint(UncompressedBuffer[i]),i-1, cbMatch) ); + + // + // Pass offset and length, and check for failure (i.e., data incompressible) + // + + if (!MrcfEncodeMatch(i-iPrev,cbMatch,&WorkSpace->BitIo)) { + + return 0; + } + + // + // Now we have to continue with the first pair of bytes + // after the string we matched: mmmmmmm12 + // + + // + // i is index of 2nd byte after match! + // + + i += cbMatch; + + // + // Check if at least 1 byte still to compress, if so + // get 1st byte after match, for loop, otherwise put out EOS + // + + if (i <= UncompressedLength) { + + b2 = UncompressedBuffer[i-1]; + + } else { + + goto WriteEOS; + } + + } else { + + // + // No match found, Store one byte and continue, and check + // for failure (i.e., data incompressible) + // + + if (!MrcfEncodeByte(b1,&WorkSpace->BitIo)) { + return 0; + } + + // + // Advance to next byte + // + + i++; + } + } + + // + // Store last byte, and again check for failure + // + + if (!MrcfEncodeByte(b2,&WorkSpace->BitIo)) { + + return 0; + } + +WriteEOS: + + // + // write out EOS, and check for failure otherwise return how much + // data we processed + // + + if (!MrcfWriteNBits( bitsEND_OF_STREAM, + cbitsEND_OF_STREAM, + &WorkSpace->BitIo )) { + + return 0; + + } else { + + return cbChunk; + } +} + + +// +// Internal Support Routine +// + +ULONG +MrcfFindMatchStandard ( + ULONG UncompressedIndex, + PUCHAR UncompressedBuffer, + ULONG UncompressedLength, + PULONG MatchedStringIndex, + PMRCF_STANDARD_COMPRESS WorkSpace + ) + +/*++ + +Routine Description: + + This routine does a standard compression lookup + +Arguments: + + UncompressedIndex - index into UncompressedBuffer[] of *2nd* byte of pair to match + + UncompressedBuffer - buffer containing uncompressed data + + UncompressedLength - length of UncompressedBuffer + + MatchedStringIndex - pointer to int to receive index of start of matched string + + WorkSpace - Supplies a pointer to the bit buffer statics + +Return Value: + + ULONG - Returns length of match. If the return value is >= 2 then + *MatchedStringIndex = index of matched string (*2nd* byte in pair). + Otherwise the match length is 0 or 1 + +--*/ + +{ + ULONG i; + ULONG iMRU; + ULONG iChar; + ULONG iPrev; + + // + // Are there exactly two bytes left? If so then do not check for match. + // + + if (UncompressedIndex == (UncompressedLength-1)) { return 0; } + + // + // 1st char is index to look-up tables + // + + iChar = UncompressedBuffer[UncompressedIndex-1]; + + // + // Can't match if 1st MRU ent is unused + // + + if (WorkSpace->abMRUX[iChar] != mruUNUSED) { + + for (i = 0; i < cMAXSLOTS; i++) { + + if (WorkSpace->abChar[iChar][i] == UncompressedBuffer[UncompressedIndex]) { + + iPrev = WorkSpace->ltX[iChar][i]; + WorkSpace->ltX[iChar][i] = UncompressedIndex; + + if ((UncompressedIndex - iPrev) >= wBACKPOINTERMAX) { return 0; } + + *MatchedStringIndex = iPrev; + + return MrcfGetMatchLength( UncompressedBuffer, + iPrev, + UncompressedIndex, + UncompressedLength ); + } + } + } + + // + // Cycle MRU index for char + // Update char match table + // Location of this char pair + // + + iMRU = (WorkSpace->abMRUX[iChar] += 1) & (cMAXSLOTS - 1); + WorkSpace->abChar[iChar][iMRU] = UncompressedBuffer[UncompressedIndex]; + WorkSpace->ltX[iChar][iMRU] = UncompressedIndex; + + return 0; +} + + +// +// Internal Support Routine +// + +ULONG +MrcfGetMatchLength ( + PUCHAR UncompressedBuffer, + ULONG MatchIndex, + ULONG CurrentIndex, + ULONG UncompressedLength + ) + +/*++ + +Routine Description: + + Find length of matching strings + +Arguments: + + UncompressedBuffer - uncompressed data buffer + + MatchIndex - index of 2nd byte in UncompressedBuffer of match (MatchIndex < CurrentIndex) + + CurrentIndex - index of 2nd byte in UncompressedBuffer that is being compressed + + UncompressedLength - length of UncompressedBuffer + +Return Value: + + ULONG - Returns length of matching strings (0, or 2 or greater) + +--*/ + +{ + ULONG cb; + + DbgAssert(MatchIndex >= 0); + DbgAssert(MatchIndex < CurrentIndex); + DbgAssert(CurrentIndex < UncompressedLength); + + // + // Point back to start of both strings + // + + MatchIndex--; + CurrentIndex--; + + // + // No bytes matched, yet + // + + cb = 0; + + // + // Scan for end of match, or end of buffer + // + + while ((CurrentIndex<UncompressedLength) && (UncompressedBuffer[MatchIndex] == UncompressedBuffer[CurrentIndex])) { + + MatchIndex++; + CurrentIndex++; + cb++; + } + + return cb; +} + + +// +// Internal Support Routine +// + +BOOLEAN +MrcfEncodeByte ( + UCHAR b, + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Write one byte to compressed bit stream + +Arguments: + + b - byte to write + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + BOOLEAN - TRUE if the bit stream was updated and FALSE if overran buffer + +--*/ + +{ + ULONG abits; + + DbgDoit( DbgPrint("<MrcfEncodeByte>: byte=%02x '%c'\n",b,ChPrint(b)) ); + + abits = ((b & 0x7F) << 2) | ((b < 128) ? 2 : 1); + + // + // Write to bitstream + // + + return MrcfWriteNBits(abits, 9, BitIo); +} + + +// +// Internal Support Routine +// + +BOOLEAN +MrcfEncodeMatch ( + ULONG off, + ULONG cb, + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Write a match to compressed bit stream + +Arguments: + + off - offset of match (must be greater than 0) + + cb - length of match (must be at least 2) + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + BOOLEAN - TRUE if the compress stream was updated and FALSE if overran buffer + +--*/ + +{ + ULONG abits; + ULONG cbits; + ULONG cbSave; + ULONG mask; + + DbgAssert(off > 0); + DbgAssert(off < wBACKPOINTERMAX); + DbgAssert(cb >= 2); + + DbgDoit( DbgPrint("<MrcfEncodeMatch>: off=%x len=%x\n",off,cb) ); + + // + // Encode the match bits and offset portion + // + + if (off < 64) { + + // + // Use 6-bit offset encoding + // + + abits = (off << 2) | 0x0; // .00 = <offset>+<6-bit>+<match> + + if (!MrcfWriteNBits(abits,6+2,BitIo)) { + + // + // Opps overran the compression buffer + // + + return FALSE; + } + + } else if (off < 320) { + + // + // Use 8-bit offset encoding + // + + abits = ((off - 64) << 3) | 0x3; // 0.11 = <offset>+<8-bit>+<match> + + if (!MrcfWriteNBits(abits,8+3,BitIo)) { + + // + // Opps overran the compression buffer + // + + return FALSE; + } + + } else { // (off >= 320) + + // + // Use 12-bit offset encoding + // + + abits = ((off - 320) << 3) | 0x7; // 1.11 = <offset>+<12-bit>+<match> + + if (!MrcfWriteNBits(abits,12+3,BitIo)) { + + // + // Opps overran the compression buffer + // + + return FALSE; + } + } + + // + // Encode the length logarithmically + // + + cb -= 1; + cbSave = cb; // Save to get remainder later + cbits = 0; + + while (cb > 1) { + + cbits++; + + // + // Put out another 0 for the length, and + // watch for buffer overflow + // + + if (!MrcfWriteBit(0, BitIo)) { + + return FALSE; + } + + // + // Shift count right (avoid sign bit) + // + + ((USHORT)cb) >>= 1; + } + + // + // Terminate length bit string + // + + if (!MrcfWriteBit(1, BitIo)) { + + return FALSE; + } + + if (cbits > 0) { + + // + // Mask for bits we want, and get remainder + // + + mask = (1 << cbits) - 1; + abits = cbSave & mask; + + if (!MrcfWriteNBits(abits,cbits,BitIo)) { + + return FALSE; + } + } + + return TRUE; +} + + +// +// Internal Support Routine +// + +VOID +MrcfSetBitBuffer ( + PUCHAR pb, + ULONG cb, + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Set statics with coded buffer pointer and length + +Arguments: + + pb - pointer to compressed data buffer + + cb - length of compressed data buffer + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + None. + +--*/ + +{ + BitIo->pbBB = pb; + BitIo->cbBB = cb; + BitIo->cbBBInitial = cb; + BitIo->cbitsBB = 0; + BitIo->abitsBB = 0; +} + + +// +// Internal Support Routine +// + +VOID +MrcfFillBitBuffer ( + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Fill abitsBB from static bit buffer + +Arguments: + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + None. + +--*/ + +{ + DbgAssert((BitIo->cbitsBB) == 0); + + switch (BitIo->cbBB) { + + case 0: + + DbgAssert(FALSE); + + break; + + case 1: + + // + // Get last byte and adjust count + // + + BitIo->cbitsBB = 8; + BitIo->abitsBB = *(BitIo->pbBB)++; + BitIo->cbBB--; + + break; + + default: + + // + // Get word and adjust count + // + + BitIo->cbitsBB = 16; + BitIo->abitsBB = *((USHORT *)(BitIo->pbBB))++; + BitIo->cbBB -= 2; + + break; + } +} + + +// +// Internal Support Routine +// + +USHORT +MrcfReadBit ( + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Get next bit from bit buffer + +Arguments: + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + USHORT - Returns next bit (0 or 1) + +--*/ + +{ + USHORT bit; + + // + // Check if no bits available + // + + if ((BitIo->cbitsBB) == 0) { + + MrcfFillBitBuffer(BitIo); + } + + // + // Decrement the bit count + // get the bit, remove it, and return the bit + // + + (BitIo->cbitsBB)--; + bit = (BitIo->abitsBB) & 1; + (BitIo->abitsBB) >>= 1; + + return bit; +} + + +// +// Internal Support Routine +// + +USHORT +MrcfReadNBits ( + LONG cbits, + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Get next N bits from bit buffer + +Arguments: + + cbits - count of bits to get + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + USHORT - Returns next cbits bits. + +--*/ + +{ + ULONG abits; // Bits to return + LONG cbitsPart; // Partial count of bits + ULONG cshift; // Shift count + ULONG mask; // Mask + + // + // Largest number of bits we should read at one time is 12 bits for + // a 12-bit offset. The largest length field component that we + // read is 8 bits. If this routine were used for some other purpose, + // it can support up to 15 (NOT 16) bit reads, due to how the masking + // code works. + // + + DbgAssert(cbits <= 12); + + // + // No shift and no bits yet + // + + cshift = 0; + abits = 0; + + while (cbits > 0) { + + // + // If not bits available get some bits + // + + if ((BitIo->cbitsBB) == 0) { + + MrcfFillBitBuffer(BitIo); + } + + // + // Number of bits we can read + // + + cbitsPart = min((BitIo->cbitsBB), cbits); + + // + // Mask for bits we want, extract and store them + // + + mask = (1 << cbitsPart) - 1; + abits |= ((BitIo->abitsBB) & mask) << cshift; + + // + // Remember the next chunk of bits + // + + cshift = cbitsPart; + + // + // Update bit buffer, move remaining bits down and + // update count of bits left + // + + (BitIo->abitsBB) >>= cbitsPart; + (BitIo->cbitsBB) -= cbitsPart; + + // + // Update count of bits left to read + // + + cbits -= cbitsPart; + } + + // + // Return requested bits + // + + return (USHORT)abits; +} + + +// +// Internal Support Routine +// + +BOOLEAN +MrcfWriteBit ( + ULONG bit, + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Write a bit to the bit buffer + +Arguments: + + bit - bit to write (0 or 1) + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + BOOLEAN - returns TRUE if the compresed bit stream was updated and + FALSE if overran buffer. + +--*/ + +{ + DbgAssert((bit == 0) || (bit == 1)); + DbgAssert((BitIo->cbitsBB) < 16); + + DbgDoit( DbgPrint("<MrcfWriteBit>: bit=%x\n",bit) ); + + // + // Write one bit + // + + (BitIo->abitsBB) |= bit << (BitIo->cbitsBB); + (BitIo->cbitsBB)++; + + // + // Check if abitsBB is full and write compressed data buffer + // + + if ((BitIo->cbitsBB) >= 16) { + + return (MrcfFlushBitBuffer(BitIo) != 0); + + } else { + + return TRUE; + } +} + + +// +// Internal Support Routine +// + +BOOLEAN +MrcfWriteNBits ( + ULONG abits, + LONG cbits, + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Write N bits to the bit buffer + +Arguments: + + abits - bits to write + + cbits - count of bits write + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + BOOLEAN - returns TRUE if the compressed bit stream was updated and + FALSE if overran buffer + +--*/ + +{ + LONG cbitsPart; + ULONG mask; + + DbgAssert(cbits > 0); + DbgAssert(cbits <= 16); + DbgAssert((BitIo->cbitsBB) < 16); + + DbgDoit( DbgPrint("<MrcfWriteNBits>: bits=%04x count=%x\n",abits,cbits) ); + + while (cbits > 0) { + + // + // Number of bits we can write + // + + cbitsPart = min(16-(BitIo->cbitsBB), cbits); + + mask = (1 << cbitsPart) - 1; + + // + // Move part of bits to buffer + // + + (BitIo->abitsBB) |= (abits & mask) << (BitIo->cbitsBB); + + // + // Update count of bits written + // + + (BitIo->cbitsBB) += cbitsPart; + + // + // Check if buffer if full + // + + if ((BitIo->cbitsBB) >= 16) { + + // + // Write compressed data buffer + // + + if (!MrcfFlushBitBuffer(BitIo)) { + + return FALSE; + } + } + + // + // Reduce number of bits left to write and move remaining bits over + // + + cbits -= cbitsPart; + abits >>= cbitsPart; + } + + return TRUE; +} + + +// +// Internal Support Routine +// + +ULONG +MrcfFlushBitBuffer ( + PMRCF_BIT_IO BitIo + ) + +/*++ + +Routine Description: + + Write remaining bits to compressed data buffer + +Arguments: + + BitIo - Supplies a pointer to the bit buffer statics + +Return Value: + + ULONG - Returns total count of bytes written to the compressed data + buffer since the last call to MrcfSetBitBuffer(). Returns 0 if + overran buffer + +--*/ + +{ + DbgAssert((BitIo->cbitsBB) >= 0); + DbgAssert((BitIo->cbitsBB) <= 16); + + // + // Move bits to the compressed data buffer + // + + while ((BitIo->cbitsBB) > 0) { + + // + // Process low and high half. + // Check if output buffer is out of room + // + + if ((BitIo->cbBB) == 0) { return 0; } + + // + // Store a byte, adjust the count, get high half, nd adjust + // count of bits remaining + // + + *(BitIo->pbBB)++ = (UCHAR)((BitIo->abitsBB) & 0xFF); + (BitIo->cbBB)--; + (BitIo->abitsBB) >>= 8; + (BitIo->cbitsBB) -= 8; + } + + // + // Reset bit buffer, "abitsBB >>= 8" guarantees abitsBB is clear + // + + DbgAssert((BitIo->abitsBB) == 0); + + (BitIo->cbitsBB) = 0; + + return (BitIo->cbBBInitial)-(BitIo->cbBB); +} + |