You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
352 lines
8.7 KiB
352 lines
8.7 KiB
//
|
|
// optblock.c
|
|
//
|
|
// Outputting blocks
|
|
//
|
|
#include "deflate.h"
|
|
#include <string.h>
|
|
#include <stdio.h>
|
|
#include <crtdbg.h>
|
|
#include "maketbl.h"
|
|
|
|
|
|
//
|
|
// Decode a recorded literal
|
|
//
|
|
#define DECODE_LITERAL(slot) \
|
|
slot = encoder->recording_literal_tree_table[read_bitbuf & REC_LITERALS_DECODING_TABLE_MASK]; \
|
|
while (slot < 0) \
|
|
{ \
|
|
unsigned long mask = 1 << REC_LITERALS_DECODING_TABLE_BITS; \
|
|
do \
|
|
{ \
|
|
slot = -slot; \
|
|
if ((read_bitbuf & mask) == 0) \
|
|
slot = encoder->recording_literal_tree_left[slot]; \
|
|
else \
|
|
slot = encoder->recording_literal_tree_right[slot]; \
|
|
mask <<= 1; \
|
|
} while (slot < 0); \
|
|
}
|
|
|
|
|
|
//
|
|
// Decode a recorded distance slot
|
|
//
|
|
#define DECODE_POS_SLOT(slot) \
|
|
slot = encoder->recording_dist_tree_table[read_bitbuf & REC_DISTANCES_DECODING_TABLE_MASK]; \
|
|
while (slot < 0) \
|
|
{ \
|
|
unsigned long mask = 1 << REC_DISTANCES_DECODING_TABLE_BITS; \
|
|
do \
|
|
{ \
|
|
slot = -slot; \
|
|
if ((read_bitbuf & mask) == 0) \
|
|
slot = encoder->recording_dist_tree_left[slot]; \
|
|
else \
|
|
slot = encoder->recording_dist_tree_right[slot]; \
|
|
mask <<= 1; \
|
|
} while (slot < 0); \
|
|
}
|
|
|
|
|
|
//
|
|
// Remove count bits from the bit buffer
|
|
//
|
|
#define DUMP_READBUF_BITS(count) \
|
|
read_bitbuf >>= count; \
|
|
read_bitcount -= count;
|
|
|
|
|
|
//
|
|
// Read more bits into the read buffer if our bit buffer if we need to
|
|
//
|
|
#define CHECK_MORE_READBUF() \
|
|
if (read_bitcount <= 0) \
|
|
{ \
|
|
read_bitbuf |= ((*read_bufptr++) << (read_bitcount+16)); \
|
|
read_bitcount += 8; \
|
|
if (read_bitcount <= 0) \
|
|
{ \
|
|
read_bitbuf |= ((*read_bufptr++) << (read_bitcount+16)); \
|
|
read_bitcount += 8; \
|
|
} \
|
|
}
|
|
|
|
|
|
// output an element from the literal tree
|
|
#define OUTPUT_LITERAL(element) \
|
|
{ \
|
|
_ASSERT(encoder->literal_tree_len[element] != 0); \
|
|
outputBits(context, encoder->literal_tree_len[element], encoder->literal_tree_code[element]); \
|
|
}
|
|
|
|
|
|
// output an element from the distance tree
|
|
#define OUTPUT_DIST_SLOT(element) \
|
|
{ \
|
|
_ASSERT(encoder->dist_tree_len[element] != 0); \
|
|
outputBits(context, encoder->dist_tree_len[element], encoder->dist_tree_code[element]); \
|
|
}
|
|
|
|
|
|
|
|
//
|
|
// Output a dynamic block
|
|
//
|
|
static BOOL OptimalEncoderOutputDynamicBlock(t_encoder_context *context)
|
|
{
|
|
unsigned long read_bitbuf;
|
|
int read_bitcount;
|
|
byte * read_bufptr;
|
|
t_optimal_encoder *encoder = context->optimal_encoder;
|
|
|
|
if (context->state == STATE_NORMAL)
|
|
{
|
|
//
|
|
// If we haven't started to output a block yet
|
|
//
|
|
read_bufptr = encoder->lit_dist_buffer;
|
|
read_bitbuf = 0;
|
|
read_bitcount = -16;
|
|
|
|
read_bitbuf |= ((*read_bufptr++) << (read_bitcount+16));
|
|
read_bitcount += 8;
|
|
|
|
read_bitbuf |= ((*read_bufptr++) << (read_bitcount+16));
|
|
read_bitcount += 8;
|
|
|
|
context->outputting_block_bitbuf = read_bitbuf;
|
|
context->outputting_block_bitcount = read_bitcount;
|
|
context->outputting_block_bufptr = read_bufptr;
|
|
|
|
outputBits(context, 1, 0); // "final" block flag
|
|
outputBits(context, 2, BLOCKTYPE_DYNAMIC);
|
|
|
|
context->state = STATE_OUTPUTTING_TREE_STRUCTURE;
|
|
}
|
|
|
|
if (context->state == STATE_OUTPUTTING_TREE_STRUCTURE)
|
|
{
|
|
//
|
|
// Make sure there is enough room to output the entire tree structure at once
|
|
//
|
|
if (context->output_curpos > context->output_endpos - MAX_TREE_DATA_SIZE)
|
|
{
|
|
_ASSERT(0); // not enough room to output tree structure, fatal error!
|
|
return FALSE;
|
|
}
|
|
|
|
outputTreeStructure(context, encoder->literal_tree_len, encoder->dist_tree_len);
|
|
|
|
context->state = STATE_OUTPUTTING_BLOCK;
|
|
}
|
|
|
|
_ASSERT(context->state == STATE_OUTPUTTING_BLOCK);
|
|
|
|
// load state into local variables
|
|
read_bufptr = context->outputting_block_bufptr;
|
|
read_bitbuf = context->outputting_block_bitbuf;
|
|
read_bitcount = context->outputting_block_bitcount;
|
|
|
|
// output literals
|
|
while (context->outputting_block_current_literal < context->outputting_block_num_literals)
|
|
{
|
|
int literal;
|
|
|
|
// break when we get near the end of our output buffer
|
|
if (context->output_curpos >= context->output_near_end_threshold)
|
|
break;
|
|
|
|
DECODE_LITERAL(literal);
|
|
DUMP_READBUF_BITS(encoder->recording_literal_tree_len[literal]);
|
|
CHECK_MORE_READBUF();
|
|
|
|
if (literal < NUM_CHARS)
|
|
{
|
|
// it's a char
|
|
OUTPUT_LITERAL(literal);
|
|
}
|
|
else
|
|
{
|
|
// it's a match
|
|
int len_slot, pos_slot, extra_pos_bits;
|
|
|
|
// literal == len_slot + (NUM_CHARS+1)
|
|
_ASSERT(literal != END_OF_BLOCK_CODE);
|
|
|
|
OUTPUT_LITERAL(literal);
|
|
|
|
len_slot = literal - (NUM_CHARS+1);
|
|
|
|
//
|
|
// extra_length_bits[len_slot] > 0 when len_slot >= 8
|
|
// (except when length is MAX_MATCH).
|
|
//
|
|
if (len_slot >= 8)
|
|
{
|
|
int extra_bits = g_ExtraLengthBits[len_slot];
|
|
|
|
if (extra_bits > 0)
|
|
{
|
|
unsigned int extra_data = read_bitbuf & ((1 << extra_bits)-1);
|
|
|
|
outputBits(context, extra_bits, extra_data);
|
|
|
|
DUMP_READBUF_BITS(extra_bits);
|
|
CHECK_MORE_READBUF();
|
|
}
|
|
}
|
|
|
|
DECODE_POS_SLOT(pos_slot);
|
|
DUMP_READBUF_BITS(encoder->recording_dist_tree_len[pos_slot]);
|
|
CHECK_MORE_READBUF();
|
|
|
|
_ASSERT(pos_slot < 30);
|
|
|
|
OUTPUT_DIST_SLOT(pos_slot);
|
|
|
|
extra_pos_bits = g_ExtraDistanceBits[pos_slot];
|
|
|
|
if (extra_pos_bits > 0)
|
|
{
|
|
unsigned int extra_data = read_bitbuf & ((1 << extra_pos_bits)-1);
|
|
|
|
outputBits(context, extra_pos_bits, extra_data);
|
|
|
|
DUMP_READBUF_BITS(extra_pos_bits);
|
|
CHECK_MORE_READBUF();
|
|
}
|
|
}
|
|
|
|
context->outputting_block_current_literal++;
|
|
}
|
|
|
|
// did we output all of our literals without running out of output space?
|
|
if (context->outputting_block_current_literal >= context->outputting_block_num_literals)
|
|
{
|
|
// output the code signifying end-of-block
|
|
OUTPUT_LITERAL(END_OF_BLOCK_CODE);
|
|
|
|
// reset state
|
|
context->state = STATE_NORMAL;
|
|
}
|
|
else
|
|
{
|
|
context->outputting_block_bitbuf = read_bitbuf;
|
|
context->outputting_block_bitcount = read_bitcount;
|
|
context->outputting_block_bufptr = read_bufptr;
|
|
context->state = STATE_OUTPUTTING_BLOCK;
|
|
}
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
|
|
|
|
//
|
|
// Output a block. This routine will resume outputting a block that was already being
|
|
// output if state != STATE_NORMAL.
|
|
//
|
|
BOOL OptimalEncoderOutputBlock(t_encoder_context *context)
|
|
{
|
|
t_optimal_encoder *encoder = context->optimal_encoder;
|
|
|
|
_ASSERT(encoder != NULL);
|
|
|
|
//
|
|
// The tree creation routines cannot >= 65536 literals.
|
|
//
|
|
_ASSERT(context->outputting_block_num_literals < 65536);
|
|
|
|
if (context->state == STATE_NORMAL)
|
|
{
|
|
//
|
|
// Start outputting literals and distances from the beginning
|
|
//
|
|
context->outputting_block_current_literal = 0;
|
|
|
|
//
|
|
// Nothing to output? Then return
|
|
//
|
|
if (context->outputting_block_num_literals == 0)
|
|
return TRUE;
|
|
|
|
// make decoding table so that we can decode recorded items
|
|
makeTable(
|
|
MAX_LITERAL_TREE_ELEMENTS,
|
|
REC_LITERALS_DECODING_TABLE_BITS,
|
|
encoder->recording_literal_tree_len,
|
|
encoder->recording_literal_tree_table,
|
|
encoder->recording_literal_tree_left,
|
|
encoder->recording_literal_tree_right
|
|
);
|
|
|
|
makeTable(
|
|
MAX_DIST_TREE_ELEMENTS,
|
|
REC_DISTANCES_DECODING_TABLE_BITS,
|
|
encoder->recording_dist_tree_len,
|
|
encoder->recording_dist_tree_table,
|
|
encoder->recording_dist_tree_left,
|
|
encoder->recording_dist_tree_right
|
|
);
|
|
|
|
// now make the trees used for encoding
|
|
makeTree(
|
|
MAX_LITERAL_TREE_ELEMENTS,
|
|
15,
|
|
encoder->literal_tree_freq,
|
|
encoder->literal_tree_code,
|
|
encoder->literal_tree_len
|
|
);
|
|
|
|
makeTree(
|
|
MAX_DIST_TREE_ELEMENTS,
|
|
15,
|
|
encoder->dist_tree_freq,
|
|
encoder->dist_tree_code,
|
|
encoder->dist_tree_len
|
|
);
|
|
}
|
|
|
|
//
|
|
// Try outputting as a dynamic block
|
|
//
|
|
if (OptimalEncoderOutputDynamicBlock(context) == FALSE)
|
|
{
|
|
return FALSE;
|
|
}
|
|
|
|
if (context->state == STATE_NORMAL)
|
|
{
|
|
encoder->recording_bufptr = context->optimal_encoder->lit_dist_buffer;
|
|
encoder->recording_bitbuf = 0;
|
|
encoder->recording_bitcount = 0;
|
|
|
|
context->outputting_block_num_literals = 0;
|
|
|
|
// make sure there are no zero frequency items
|
|
NormaliseFrequencies(encoder->literal_tree_freq, encoder->dist_tree_freq);
|
|
|
|
// make tree for recording new items
|
|
makeTree(
|
|
MAX_DIST_TREE_ELEMENTS,
|
|
RECORDING_DIST_MAX_CODE_LEN,
|
|
encoder->dist_tree_freq,
|
|
encoder->recording_dist_tree_code,
|
|
encoder->recording_dist_tree_len
|
|
);
|
|
|
|
makeTree(
|
|
MAX_LITERAL_TREE_ELEMENTS,
|
|
RECORDING_LIT_MAX_CODE_LEN,
|
|
encoder->literal_tree_freq,
|
|
encoder->recording_literal_tree_code,
|
|
encoder->recording_literal_tree_len
|
|
);
|
|
|
|
OptimalEncoderZeroFrequencyCounts(encoder);
|
|
}
|
|
|
|
return TRUE;
|
|
}
|