MiniDeflate.cpp
/*
* Copyright (C) 2010 Regents of the University of Michigan
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include "MiniDeflate.h"
// Convenient constants and macros
//
#define EMPTY_KEY 123
#define uchar unsigned char
#ifndef min
#define min(a,b) (((a)<(b))?(a):(b))
#endif
MiniDeflate::MiniDeflate()
{
buffer = new uchar [BUFFER_SIZE + 5];
hash_keys = new uchar [HASH_SIZE];
hash_values = new uchar * [HASH_SIZE * HASH_DEPTH];
}
MiniDeflate::~MiniDeflate()
{
delete [] buffer;
delete [] hash_keys;
delete [] hash_values;
}
void MiniDeflate::EvaluateMatch(unsigned char * in, int len, int hash,
unsigned char * & best_pos, int & best_match)
{
int max = min(len, 0xFFFF + 66);
for (int i = HASH_DEPTH; i > 0; i--)
// Check each possible match (up to HASH_DEPTH)
{
uchar * pos = hash_values[hash * HASH_DEPTH + ((hash_keys[hash] + i) % HASH_DEPTH)];
if (pos == NULL || in - pos >= 0x4001) break;
int match = 0;
while (match < max && pos[match] == in[match])
match++;
if (match > best_match)
{
best_match = match;
best_pos = pos;
}
}
// If string seems pretty unique, add to hash table
if (best_match < OKAY_MATCH)
{
int delta = hash_keys[hash] = (uchar)((hash_keys[hash] + 1) & 7);
hash_values[hash * 8 + delta] = in;
}
}
void MiniDeflate::QuoteLiterals(unsigned char * & in, int literal,
unsigned char * & out, int & buffer_len,
FILE * output)
{
if (buffer_len < 0)
{
fwrite(buffer, out - buffer, 1, output);
buffer_len = BUFFER_SIZE;
out = buffer;
}
while (buffer_len < literal)
{
literal -= buffer_len;
while (buffer_len--)
{
*out = *in;
in++;
out++;
}
fwrite(buffer, BUFFER_SIZE, 1, output);
buffer_len = BUFFER_SIZE;
out = buffer;
}
while (literal--)
{
*out = *in;
in++;
out++;
buffer_len--;
}
}
void MiniDeflate::OutputLiterals(unsigned char * & in, int literal,
unsigned char * & out, int & buffer_len,
FILE * output)
{
while (literal > 0)
if (literal < 16)
{
*out = (char) literal;
out++;
buffer_len--;
QuoteLiterals(in, literal, out, buffer_len, output);
break;
}
else if (literal < 31)
{
*out = 15;
out++;
buffer_len--;
QuoteLiterals(in, 15, out, buffer_len, output);
*out = (uchar)(literal - 15);
out++;
buffer_len--;
QuoteLiterals(in, literal - 15, out, buffer_len, output);
break;
}
else
{
int length = min(literal, 0xFFFF + 31);
literal -= length;
length -= 31;
*out = 0;
out++;
*out = (uchar)(length >> 8);
out++;
*out = (uchar)(length & 0xFF);
out++;
buffer_len -= 3;
QuoteLiterals(in, length + 31, out, buffer_len, output);
}
}
void MiniDeflate::Deflate(FILE * output, void * void_input, size_t len)
{
uchar * in = (uchar *) void_input;
uchar * out = (uchar *) buffer;
int buffer_len = BUFFER_SIZE;
for (int i = 0; i < HASH_SIZE; i++) hash_keys[i] = EMPTY_KEY;
uchar * in2 = in;
while (len > 2)
{
// Hash the current input value
int hash = ((in[0] << 16) | (in[1] << 8) | in[2]) % HASH_SIZE;
if (hash_keys[hash] != EMPTY_KEY)
// Possible matches in hash table
{
int best_match = 0;
uchar * best_pos = NULL;
EvaluateMatch(in, len, hash, best_pos, best_match);
// If there are no decent matches
if (best_match < 3)
{
in++;
len--;
continue;
}
// Try look ahead if match isn't great
while (best_match < OKAY_MATCH && len > 3)
{
// Peek to see if we could get a better match
int next_hash = ((in[1] << 16) | (in[2] << 8) | in[3]) % HASH_SIZE;
if (hash_keys[next_hash] == EMPTY_KEY) break;
int next_match = 0;
uchar * next_pos = NULL;
EvaluateMatch(in + 1, len - 1, next_hash, next_pos, next_match);
// Didn't find a better match
if (next_match <= best_match + 1) break;
// Found a better match, so try again
in++;
len--;
best_match = next_match;
best_pos = next_pos;
}
int best_offset = in - best_pos - 1;
// This is where we output stuff
// Check if we have some literals to output first
OutputLiterals(in2, in - in2, out, buffer_len, output);
in2 = in += best_match;
len -= best_match;
if (best_match < 17 && best_offset < 0x1000)
{
*out = (uchar)(((best_match - 1) << 4) | (best_offset >> 8));
out++;
*out = (uchar)(best_offset & 0xFF);
out++;
buffer_len -= 2;
}
else if (best_match < 66)
{
*out = (uchar)(16 | (best_offset >> 10));
out++;
*out = (uchar)((best_offset >> 2) & 0xFF);
out++;
*out = (uchar)((best_offset << 6) | (best_match - 2));
out++;
buffer_len -= 3;
}
else
{
*out = (uchar)(16 | (best_offset >> 10));
out++;
*out = (uchar)((best_offset >> 2) & 0xFF);
out++;
*out = (uchar)(best_offset << 6);
out++;
best_match -= 66;
*out = (uchar)(best_match >> 8);
out++;
*out = (uchar)(best_match & 0xFF);
out++;
buffer_len -= 5;
}
if (buffer_len <= 0)
{
fwrite(buffer, out - buffer, 1, output);
buffer_len = BUFFER_SIZE;
out = buffer;
}
}
// Never seen this sequence before
else
{
hash_keys[hash] = 0;
for (int i = 1; i < HASH_DEPTH; i++) hash_values[hash * 8 + i] = NULL;
hash_values[hash * 8] = in;
in++;
len--;
}
}
// Check if we have some trailing literals to output
in += len;
OutputLiterals(in2, in - in2, out, buffer_len, output);
// Flush output
if (out != buffer) fwrite(buffer, out - buffer, 1, output);
}
void MiniDeflate::CiteLiteral(unsigned char * & out, int literal,
unsigned char * & in, int & buffer_len,
FILE * input)
{
while (buffer_len < literal)
{
literal -= buffer_len;
while (buffer_len--)
{
*out = *in;
in++;
out++;
}
buffer_len = fread(buffer + 5, 1, BUFFER_SIZE, input);
in = buffer + 5;
}
while (literal--)
{
*out = *in;
in++;
out++;
buffer_len--;
}
}
void MiniDeflate::Inflate(FILE * input, void * void_output, size_t len)
{
uchar * out = (uchar *) void_output;
uchar * in = (uchar *) buffer + 5;
int buffer_len = BUFFER_SIZE;
buffer_len = fread(buffer + 5, 1, BUFFER_SIZE, input);
while (len)
{
int match_len = *in >> 4;
// Matching a literal
if (match_len == 0)
{
match_len = *in & 0x0F;
in++, buffer_len--;
// If match_len == 0 then string is longer than 30 characters
// Strings of 16 - 30 characters are encoded as two short strings
if (match_len == 0)
{
match_len = (in[0] << 8) + in[1] + 31;
in += 2;
buffer_len -= 2;
}
CiteLiteral(out, match_len, in, buffer_len, input);
len -= match_len;
}
// Long match, 14 bit offset
else if (match_len == 1)
{
int offset = (((in[0] & 0x0F) << 10) | (in[1] << 2) | (in[2] >> 6)) + 1;
match_len = (in[2] & 0x3F) + 2;
in += 3;
buffer_len -= 3;
if (match_len == 2)
{
match_len = ((in[0] << 8) | in[1]) + 66;
in += 2;
buffer_len -= 2;
}
uchar * match_pos = out - offset;
len -= match_len;
while (match_len--)
{
*out = *match_pos;
out++, match_pos++;
}
}
// Typical short match
else
{
int offset = (((in[0] & 0x0F) << 8) | in[1]) + 1;
in += 2;
buffer_len -= 2;
uchar * match_pos = out - offset;
len -= ++match_len;
while (match_len--)
{
*out = *match_pos;
out++, match_pos++;
}
}
if (buffer_len < 5)
{
uchar * in2 = (uchar *) buffer + 5 - buffer_len;
while (in2 != buffer + 5)
{
*in2 = *in;
in2++;
in++;
}
in = buffer + 5 - buffer_len;
buffer_len += fread(buffer + 5, 1, BUFFER_SIZE, input);
}
}
if (buffer_len) fseek(input, -buffer_len, SEEK_CUR);
}