?? binary_codec.cpp
字號:
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// ************************* -
// HUFFMAN CODING EXAMPLES -
// ************************* -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// Implementation of periodic-adaptive and static Huffman codes -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// Version 1.00 - January 24, 2005 -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// -
// WARNING -
// ========= -
// -
// The only purpose of this program is to demonstrate the basic principles -
// of Huffman codes. It is provided as is, without any express or implied -
// warranty, without even the warranty of fitness for any particular -
// purpose, or that the implementations are correct. -
// -
// Permission to copy and redistribute this code is hereby granted, provided -
// that this warning and copyright notices are not removed or altered. -
// -
// Copyright (c) 2005 by Amir Said (said@ieee.org) & -
// William A. Pearlman (pearlw@ecse.rpi.edu) -
// -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Inclusion - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#include <stdlib.h>
#include <string.h>
#include "binary_codec.h"
// - - Constants - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// #define TREE_DECODE
const unsigned HC__MaxCount = 1 << 15; // Max. symbol count for adaptive code
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Static functions - - - - - - - - - - - - - - - - - - - - - - - - - - -
static void HC_Error(const char * msg)
{
fprintf(stderr, "\n\n -> Huffman/binary coding error: ");
fputs(msg, stderr);
fputs("\n Execution terminated!\n", stderr);
exit(1);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
static void Form_Huffman_Tree(int number_of_symbols,
unsigned original_count[],
int left_branch[],
int right_branch[])
{
int tc, ts, i, n, nc, it = 0, k = (number_of_symbols >> 1) + 1;
int * count = right_branch - 1, * symbol = left_branch - 1;
for (n = k - 1; n < number_of_symbols; n++) { // second half of the heap
symbol[n+1] = n;
count[n+1] = original_count[n];
}
for (;;) {
if (k > 1) {
ts = (--k) - 1; // add first half to heap
tc = original_count[ts];
}
else
if ((++it) & 1) {
tc = count[n];
ts = symbol[n];
left_branch[--n] = symbol[1]; // set-up merging nodes
if (n == 1) break;
nc = count[1];
}
else {
right_branch[n] = symbol[1]; // finalize merging nodes
ts = -n;
tc = nc + count[1];
}
for (int j = (i = k) << 1; j <= n; j += (i = j)) { // heap sort
if ((j < n) && (count[j] > count[j+1])) ++j;
if (tc <= count[j]) break;
symbol[i] = symbol[j];
count[i] = count[j];
}
symbol[i] = ts;
count[i] = tc;
}
right_branch[1] = ts;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
static void Set_Huffman_Code(int * tree[2],
unsigned codeword[],
unsigned codeword_length[])
{
int stack[32], node, depth = 0, current_code = 0;
for (stack[0] = 1; depth >= 0;) { // transverse tree setting codewords
if ((node = tree[current_code&1][stack[depth]]) < 0)
do {
current_code <<= 1;
stack[++depth] = -node;
} while ((node = tree[0][-node]) < 0);
codeword[node] = current_code; // set codeword to leaf symbol
codeword_length[node] = depth + 1;
while (current_code & 1) { // backtrack
current_code >>= 1;
if (--depth < 0) break;
}
current_code |= 1;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
static void Set_Huffman_Code(int table_bits,
int * tree[2],
int decoder_table[],
unsigned codeword[],
unsigned codeword_length[])
{
int stack[32], node, depth = 0, current_code = 0;
for (stack[0] = 1; depth >= 0;) { // transverse tree setting codewords
if ((node = tree[current_code&1][stack[depth]]) < 0)
do {
if (depth + 1 == table_bits) decoder_table[current_code] = node;
current_code <<= 1;
stack[++depth] = -node;
} while ((node = tree[0][-node]) < 0);
codeword[node] = current_code; // set codeword to leaf symbol
int nb = codeword_length[node] = depth + 1;
if (nb <= table_bits) // add entries to decoder table
if (nb == table_bits)
decoder_table[current_code] = node;
else {
int db = table_bits - nb, sc = current_code << db;
for (int k = 1 << db; k;) decoder_table[sc+--k] = node;
}
while (current_code & 1) { // backtrack
current_code >>= 1;
if (--depth < 0) break;
}
current_code |= 1;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Coding implementations - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Binary_Codec::get_bit(void)
{
#ifdef _DEBUG
if (mode != 2) HC_Error("decoder not initialized");
#endif
// refill bit buffer (32-bit word)
while (bit_position >= 8) {
bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);
}
// next data bit is most-significant bit in 32-bit word
++bit_position;
unsigned data = bit_buffer >> 31;
bit_buffer <<= 1;
return data;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Binary_Codec::get_bits(unsigned bits)
{
#ifdef _DEBUG
if (mode != 2) HC_Error("decoder not initialized");
if ((bits < 1) || (bits > 24)) HC_Error("invalid number of bits");
#endif
// refill bit buffer (32-bit word)
while (bit_position >= 8) {
bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);
}
// next data bits are most-significant bits in 32-bit word
bit_position += bits;
unsigned data = bit_buffer >> (32 - bits);
bit_buffer <<= bits;
return data;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Binary_Codec::put_bit(unsigned bit)
{
#ifdef _DEBUG
if (mode != 1) HC_Error("encoder not initialized");
#endif
// save data bit in most-significant bits of 32-bit word
--bit_position;
if (bit) bit_buffer |= 1U << bit_position;
if (bit_position <= 24) // empty bit buffer (32-bit word)
do {
*bc_pointer++ = (unsigned char) (bit_buffer >> 24);
bit_buffer <<= 8;
} while ((bit_position += 8) <= 24);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Binary_Codec::put_bits(unsigned data,
unsigned bits)
{
#ifdef _DEBUG
if (mode != 1) HC_Error("encoder not initialized");
if ((bits < 1) || (bits > 24)) HC_Error("invalid number of bits");
if (data >= (1U << bits)) HC_Error("invalid data");
#endif
// save data bits in most-significant bits of 32-bit word
bit_buffer |= data << (bit_position -= bits);
if (bit_position <= 24) // empty bit buffer (32-bit word)
do {
*bc_pointer++ = (unsigned char) (bit_buffer >> 24);
bit_buffer <<= 8;
} while ((bit_position += 8) <= 24);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Binary_Codec::encode(unsigned data,
Static_Huffman_Code & C)
{
#ifdef _DEBUG
if (mode != 1) HC_Error("encoder not initialized");
if (data >= C.data_symbols) HC_Error("invalid data symbol");
#endif
bit_buffer |= C.codeword[data] << (bit_position -= C.length[data]); // code
if (bit_position <= 24)
do { // save bytes ready
*bc_pointer++ = (unsigned char) (bit_buffer >> 24);
bit_buffer <<= 8;
} while ((bit_position += 8) <= 24);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void Binary_Codec::encode(unsigned data,
Adaptive_Huffman_Code & C)
{
#ifdef _DEBUG
if (mode != 1) HC_Error("encoder not initialized");
if (data >= C.data_symbols) HC_Error("invalid data symbol");
#endif
bit_buffer |= C.codeword[data] << (bit_position -= C.length[data]); // code
if (bit_position <= 24)
do { // save bytes ready
*bc_pointer++ = (unsigned char) (bit_buffer >> 24);
bit_buffer <<= 8;
} while ((bit_position += 8) <= 24);
++C.symbol_count[data]; // update symbol statistics
if (--C.symbols_until_update == 0) C.update(true); // periodic adaptation
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#ifdef TREE_DECODE
unsigned Binary_Codec::decode(Static_Huffman_Code & C)
{
#ifdef _DEBUG
if (mode != 2) HC_Error("decoder not initialized");
#endif
while (bit_position >= 8) // fill buffer
bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);
int data = -1;
do {
data = C.tree[bit_buffer>>31][-data]; // bit-by-bit decoding
bit_buffer <<= 1;
} while (data < 0);
bit_position += C.length[data];
return data;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Binary_Codec::decode(Adaptive_Huffman_Code & C)
{
#ifdef _DEBUG
if (mode != 2) HC_Error("decoder not initialized");
#endif
while (bit_position >= 8) // fill buffer
bit_buffer |= unsigned(*bc_pointer++) << (bit_position -= 8);
int data = -1;
do {
data = C.tree[bit_buffer>>31][-data]; // bit-by-bit decoding
bit_buffer <<= 1;
} while (data < 0);
bit_position += C.length[data];
++C.symbol_count[data]; // update symbol statistics
if (--C.symbols_until_update == 0) C.update(false); // periodic adaptation
return data;
}
#else
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned Binary_Codec::decode(Static_Huffman_Code & C)
{
#ifdef _DEBUG
if (mode != 2) HC_Error("decoder not initialized");
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -