|
|
//
// 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;}
|
