1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
namespace System.IO.Compression {
using System;
using System.Diagnostics;
using System.Globalization;
internal class FastEncoder {
private FastEncoderWindow inputWindow; // input history window
private Match currentMatch; // current match in history window
private double lastCompressionRatio;
public FastEncoder() {
inputWindow = new FastEncoderWindow();
currentMatch = new Match();
}
internal int BytesInHistory {
get {
return inputWindow.BytesAvailable;
}
}
internal DeflateInput UnprocessedInput {
get {
return inputWindow.UnprocessedInput;
}
}
internal void FlushInput() {
inputWindow.FlushWindow();
}
internal Double LastCompressionRatio {
get { return lastCompressionRatio; }
}
// Copy the compressed bytes to output buffer as a block. maxBytesToCopy limits the number of
// bytes we can copy from input. Set to any value < 1 if no limit
internal void GetBlock(DeflateInput input, OutputBuffer output, int maxBytesToCopy) {
Debug.Assert(InputAvailable(input), "call SetInput before trying to compress!");
WriteDeflatePreamble(output);
GetCompressedOutput(input, output, maxBytesToCopy);
WriteEndOfBlock(output);
}
// Compress data but don't format as block (doesn't have header and footer)
internal void GetCompressedData(DeflateInput input, OutputBuffer output) {
GetCompressedOutput(input, output, -1);
}
internal void GetBlockHeader(OutputBuffer output) {
WriteDeflatePreamble(output);
}
internal void GetBlockFooter(OutputBuffer output) {
WriteEndOfBlock(output);
}
// maxBytesToCopy limits the number of bytes we can copy from input. Set to any value < 1 if no limit
private void GetCompressedOutput(DeflateInput input, OutputBuffer output, int maxBytesToCopy) {
// snapshot for compression ratio stats
int bytesWrittenPre = output.BytesWritten;
int bytesConsumedFromInput = 0;
int inputBytesPre = BytesInHistory + input.Count;
do {
// read more input data into the window if there is space available
int bytesToCopy = (input.Count < inputWindow.FreeWindowSpace) ?
input.Count : inputWindow.FreeWindowSpace;
if (maxBytesToCopy >= 1) {
bytesToCopy = Math.Min(bytesToCopy, maxBytesToCopy - bytesConsumedFromInput);
}
if (bytesToCopy > 0) {
// copy data into history window
inputWindow.CopyBytes(input.Buffer, input.StartIndex, bytesToCopy);
input.ConsumeBytes(bytesToCopy);
bytesConsumedFromInput += bytesToCopy;
}
GetCompressedOutput(output);
} while (SafeToWriteTo(output) && InputAvailable(input) && (maxBytesToCopy < 1 || bytesConsumedFromInput < maxBytesToCopy));
// determine compression ratio, save
int bytesWrittenPost = output.BytesWritten;
int bytesWritten = bytesWrittenPost - bytesWrittenPre;
int inputBytesPost = BytesInHistory + input.Count;
int totalBytesConsumed = inputBytesPre - inputBytesPost;
if (bytesWritten != 0) {
lastCompressionRatio = (double)bytesWritten / (double)totalBytesConsumed;
}
}
// compress the bytes in input history window
private void GetCompressedOutput(OutputBuffer output) {
while (inputWindow.BytesAvailable > 0 && SafeToWriteTo(output)) {
// Find next match. A match can be a symbol,
// a distance/length pair, a symbol followed by a distance/Length pair
inputWindow.GetNextSymbolOrMatch(currentMatch);
if (currentMatch.State == MatchState.HasSymbol) {
WriteChar(currentMatch.Symbol, output);
}
else if (currentMatch.State == MatchState.HasMatch) {
WriteMatch(currentMatch.Length, currentMatch.Position, output);
}
else {
WriteChar(currentMatch.Symbol, output);
WriteMatch(currentMatch.Length, currentMatch.Position, output);
}
}
}
private bool InputAvailable(DeflateInput input) {
return input.Count > 0 || BytesInHistory > 0;
}
private bool SafeToWriteTo(OutputBuffer output) { // can we safely continue writing to output buffer
return output.FreeBytes > FastEncoderStatics.MaxCodeLen;
}
private void WriteEndOfBlock(OutputBuffer output) {
// The fast encoder outputs one long block, so it just needs to terminate this block
const int EndOfBlockCode = 256;
uint code_info = FastEncoderStatics.FastEncoderLiteralCodeInfo[EndOfBlockCode];
int code_len = (int)(code_info & 31);
output.WriteBits(code_len, code_info >> 5);
}
static internal void WriteMatch(int matchLen, int matchPos, OutputBuffer output) {
Debug.Assert(matchLen >= FastEncoderWindow.MinMatch && matchLen <= FastEncoderWindow.MaxMatch, "Illegal currentMatch length!");
Debug.WriteLineIf(CompressionTracingSwitch.Verbose, String.Format(CultureInfo.InvariantCulture, "Match: {0}:{1}", matchLen, matchPos), "Compression");
// Get the code information for a match code
uint codeInfo = FastEncoderStatics.FastEncoderLiteralCodeInfo[(FastEncoderStatics.NumChars + 1 - FastEncoderWindow.MinMatch) + matchLen];
int codeLen = (int)codeInfo & 31;
Debug.Assert(codeLen != 0, "Invalid Match Length!");
if (codeLen <= 16) {
output.WriteBits(codeLen, codeInfo >> 5);
}
else {
output.WriteBits(16, (codeInfo >> 5) & 65535);
output.WriteBits(codeLen - 16, codeInfo >> (5 + 16));
}
// Get the code information for a distance code
codeInfo = FastEncoderStatics.FastEncoderDistanceCodeInfo[FastEncoderStatics.GetSlot(matchPos)];
output.WriteBits((int)(codeInfo & 15), codeInfo >> 8);
int extraBits = (int)(codeInfo >> 4) & 15;
if (extraBits != 0) {
output.WriteBits(extraBits, (uint)matchPos & FastEncoderStatics.BitMask[extraBits]);
}
}
static internal void WriteChar(byte b, OutputBuffer output) {
Debug.WriteLineIf(CompressionTracingSwitch.Verbose, String.Format(CultureInfo.InvariantCulture, "Literal: {0}", b ), "Compression");
uint code = FastEncoderStatics.FastEncoderLiteralCodeInfo[b];
output.WriteBits((int)code & 31, code >> 5);
}
// Output the block type and tree structure for our hard-coded trees.
// Contains following data:
// "final" block flag 1 bit
// BLOCKTYPE_DYNAMIC 2 bits
// FastEncoderLiteralTreeLength
// FastEncoderDistanceTreeLength
//
static internal void WriteDeflatePreamble(OutputBuffer output) {
//Debug.Assert( bitCount == 0, "bitCount must be zero before writing tree bit!");
output.WriteBytes(FastEncoderStatics.FastEncoderTreeStructureData, 0, FastEncoderStatics.FastEncoderTreeStructureData.Length);
output.WriteBits(FastEncoderStatics.FastEncoderPostTreeBitCount, FastEncoderStatics.FastEncoderPostTreeBitBuf);
}
}
}
|
