18 #include "MiniDeflate.h"
23 #define uchar unsigned char
26 #define min(a,b) (((a)<(b))?(a):(b))
29 MiniDeflate::MiniDeflate()
31 buffer =
new uchar [BUFFER_SIZE + 5];
32 hash_keys =
new uchar [HASH_SIZE];
33 hash_values =
new uchar * [HASH_SIZE * HASH_DEPTH];
36 MiniDeflate::~MiniDeflate()
40 delete [] hash_values;
43 void MiniDeflate::EvaluateMatch(
unsigned char * in,
int len,
int hash,
44 unsigned char * & best_pos,
int & best_match)
46 int max = min(len, 0xFFFF + 66);
48 for (
int i = HASH_DEPTH; i > 0; i--)
51 uchar * pos = hash_values[hash * HASH_DEPTH + ((hash_keys[hash] + i) % HASH_DEPTH)];
53 if (pos == NULL || in - pos >= 0x4001)
break;
57 while (match < max && pos[match] == in[match])
60 if (match > best_match)
68 if (best_match < OKAY_MATCH)
70 int delta = hash_keys[hash] = (uchar)((hash_keys[hash] + 1) & 7);
71 hash_values[hash * 8 + delta] = in;
75 void MiniDeflate::QuoteLiterals(
unsigned char * & in,
int literal,
76 unsigned char * & out,
int & buffer_len,
81 fwrite(buffer, out - buffer, 1, output);
82 buffer_len = BUFFER_SIZE;
86 while (buffer_len < literal)
88 literal -= buffer_len;
95 fwrite(buffer, BUFFER_SIZE, 1, output);
96 buffer_len = BUFFER_SIZE;
109 void MiniDeflate::OutputLiterals(
unsigned char * & in,
int literal,
110 unsigned char * & out,
int & buffer_len,
116 *out = (char) literal;
119 QuoteLiterals(in, literal, out, buffer_len, output);
122 else if (literal < 31)
127 QuoteLiterals(in, 15, out, buffer_len, output);
128 *out = (uchar)(literal - 15);
131 QuoteLiterals(in, literal - 15, out, buffer_len, output);
136 int length = min(literal, 0xFFFF + 31);
142 *out = (uchar)(length >> 8);
144 *out = (uchar)(length & 0xFF);
148 QuoteLiterals(in, length + 31, out, buffer_len, output);
153 void MiniDeflate::Deflate(FILE * output,
void * void_input,
size_t len)
155 uchar * in = (uchar *) void_input;
156 uchar * out = (uchar *) buffer;
157 int buffer_len = BUFFER_SIZE;
159 for (
int i = 0; i < HASH_SIZE; i++) hash_keys[i] = EMPTY_KEY;
166 int hash = ((in[0] << 16) | (in[1] << 8) | in[2]) % HASH_SIZE;
168 if (hash_keys[hash] != EMPTY_KEY)
172 uchar * best_pos = NULL;
174 EvaluateMatch(in, len, hash, best_pos, best_match);
185 while (best_match < OKAY_MATCH && len > 3)
188 int next_hash = ((in[1] << 16) | (in[2] << 8) | in[3]) % HASH_SIZE;
190 if (hash_keys[next_hash] == EMPTY_KEY)
break;
193 uchar * next_pos = NULL;
195 EvaluateMatch(in + 1, len - 1, next_hash, next_pos, next_match);
198 if (next_match <= best_match + 1)
break;
203 best_match = next_match;
207 int best_offset = in - best_pos - 1;
211 OutputLiterals(in2, in - in2, out, buffer_len, output);
213 in2 = in += best_match;
216 if (best_match < 17 && best_offset < 0x1000)
218 *out = (uchar)(((best_match - 1) << 4) | (best_offset >> 8));
220 *out = (uchar)(best_offset & 0xFF);
224 else if (best_match < 66)
226 *out = (uchar)(16 | (best_offset >> 10));
228 *out = (uchar)((best_offset >> 2) & 0xFF);
230 *out = (uchar)((best_offset << 6) | (best_match - 2));
236 *out = (uchar)(16 | (best_offset >> 10));
238 *out = (uchar)((best_offset >> 2) & 0xFF);
240 *out = (uchar)(best_offset << 6);
243 *out = (uchar)(best_match >> 8);
245 *out = (uchar)(best_match & 0xFF);
252 fwrite(buffer, out - buffer, 1, output);
253 buffer_len = BUFFER_SIZE;
261 for (
int i = 1; i < HASH_DEPTH; i++) hash_values[hash * 8 + i] = NULL;
262 hash_values[hash * 8] = in;
270 OutputLiterals(in2, in - in2, out, buffer_len, output);
273 if (out != buffer) fwrite(buffer, out - buffer, 1, output);
276 void MiniDeflate::CiteLiteral(
unsigned char * & out,
int literal,
277 unsigned char * & in,
int & buffer_len,
280 while (buffer_len < literal)
282 literal -= buffer_len;
289 buffer_len = fread(buffer + 5, 1, BUFFER_SIZE, input);
303 void MiniDeflate::Inflate(FILE * input,
void * void_output,
size_t len)
305 uchar * out = (uchar *) void_output;
306 uchar * in = (uchar *) buffer + 5;
307 int buffer_len = BUFFER_SIZE;
309 buffer_len = fread(buffer + 5, 1, BUFFER_SIZE, input);
313 int match_len = *in >> 4;
318 match_len = *in & 0x0F;
325 match_len = (in[0] << 8) + in[1] + 31;
330 CiteLiteral(out, match_len, in, buffer_len, input);
334 else if (match_len == 1)
336 int offset = (((in[0] & 0x0F) << 10) | (in[1] << 2) | (in[2] >> 6)) + 1;
337 match_len = (in[2] & 0x3F) + 2;
343 match_len = ((in[0] << 8) | in[1]) + 66;
348 uchar * match_pos = out - offset;
359 int offset = (((in[0] & 0x0F) << 8) | in[1]) + 1;
363 uchar * match_pos = out - offset;
374 uchar * in2 = (uchar *) buffer + 5 - buffer_len;
375 while (in2 != buffer + 5)
382 in = buffer + 5 - buffer_len;
383 buffer_len += fread(buffer + 5, 1, BUFFER_SIZE, input);
387 if (buffer_len) fseek(input, -buffer_len, SEEK_CUR);