#include <setjmp.h>
#include "compress.h"
//--------------------------------------------------------------------------------
/*
(C) ─. ╠рёЄЁ■ъют, "╠юэшЄюЁ", N1, 1994.
└ыуюЁшЄь√ ёцрЄш шэЇюЁьрЎшш
*/
// ╩юышўхёЄтю сшЄют т ЁхушёЄЁх
#define BITS_IN_REGISTER 16
// ╠ръёшьры№эю тючьюцэюх чэрўхэшх т ЁхушёЄЁх
#define TOP_VALUE (((long) 1 << BITS_IN_REGISTER) - 1)
// ─шрярчюэ√
#define FIRST_QTR (TOP_VALUE / 4 + 1)
#define HALF (2 * FIRST_QTR)
#define THIRD_QTR (3 * FIRST_QTR)
// ╩юышўхёЄтю ёшьтюыют рыЇртшЄр
#define NO_OF_CHARS 256
// ╤яхЎшры№э√щ ёшьтюы ╩юэхЎ╘рщыр
#define EOF_SYMBOL (NO_OF_CHARS + 1)
// ┬ёхую ёшьтюыют т ьюфхыш
#define NO_OF_SYMBOLS (NO_OF_CHARS + 1)
// ╧юЁюу ўрёЄюЄ√ фы ьрё°ЄрсшЁютрэш
#define MAX_FREQUENCY 16383
// ╥рсышЎ√ яхЁхъюфшЁютъш
static unsigned char index_to_char [NO_OF_SYMBOLS];
static int char_to_index [NO_OF_CHARS];
// ╥рсышЎ√ ўрёЄюЄ
static int cum_freq [NO_OF_SYMBOLS + 1];
static int freq[NO_OF_SYMBOLS + 1];
// ╨хушёЄЁ√ уЁрэшЎ ш ъюфр
static long low, high;
static long value;
// ╧юффхЁцър яюсшЄыт√ї юяхЁрЎшщ ё Їрщырьш
static long bits_to_follow;
static int buffer;
static int bits_to_go;
static int garbage_bits;
// ┬їюфэющ ш т√їюфэющ сєЇхЁр
static unsigned long inbuf_pos;
static unsigned long inbuf_size;
static unsigned char *outbuf;
static unsigned long outbuf_pos;
static read_func_type read_byte_func;
// setjmp/longjmp
static jmp_buf mark;
int input_bit(void);
void start_model(void);
//////////////////////////////////////////////////
// ╚эшЎшрышчрЎш рфряЄштэющ ьюфхыш
static void start_model()
{
int i;
for ( i = 0; i < NO_OF_CHARS; i++)
{
char_to_index[i] = i + 1;
index_to_char[i + 1] = i;
}
for (i = 0; i <= NO_OF_SYMBOLS; i++)
{
freq[i] = 1;
cum_freq[i] = NO_OF_SYMBOLS - i;
}
freq [0] = 0;
}
//////////////////////////////////////////////////
// ╬сэютыхэшх ьюфхыш юўхЁхфэ√ь ёшьтюыюь
static void update_model (int symbol)
{
int i;
int ch_i, ch_symbol;
int cum;
// яЁютхЁър эр яхЁхяюыэхэшх ёўхЄўшър ўрёЄюЄ√
if (cum_freq [0] == MAX_FREQUENCY)
{
cum = 0;
// ьрё°ЄрсшЁютрэшх ўрёЄюЄ яЁш яхЁхяюыэхэшш
for ( i = NO_OF_SYMBOLS; i >= 0; i--)
{
freq [i] = (freq [i] + 1) / 2;
cum_freq [i] = cum;
cum += freq [i];
}
}
for ( i = symbol; freq [i] == freq [i - 1]; i--);
if (i < symbol)
{
ch_i = index_to_char [i];
ch_symbol = index_to_char [symbol];
index_to_char [i] = ch_symbol;
index_to_char [symbol] = ch_i;
char_to_index [ch_i] = symbol;
char_to_index [ch_symbol] = i;
}
// юсэютыхэшх чэрўхэшщ т ЄрсышЎрї ўрёЄюЄ
freq [i] += 1;
while (i > 0)
{
i -= 1;
cum_freq [i] += 1;
}
}
//////////////////////////////////////////////////
// ╚эшЎшрышчрЎш яюсшЄютюую ттюфр
void start_inputing_bits()
{
bits_to_go = 0;
garbage_bits = 0;
}
//////////////////////////////////////////////////
// ┬тюф юўхЁхфэюую сшЄр ёцрЄющ шэЇюЁьрЎшш
static int input_bit()
{
int t;
if (bits_to_go == 0)
{
buffer = (*read_byte_func)(inbuf_pos++);
if (inbuf_pos == inbuf_size)
{
garbage_bits += 1;
if (garbage_bits > BITS_IN_REGISTER - 2)
{
}
}
bits_to_go = 8;
}
t = buffer & 1;
buffer >>= 1;
bits_to_go -= 1;
return t;
}
#ifndef __KEIL__
//////////////////////////////////////////////////
// ╚эшЎшрышчрЎш яюсшЄютюую т√тюфр
static void start_outputing_bits()
{
buffer = 0;
bits_to_go = 8;
}
//////////////////////////////////////////////////
// ┬√тюф юўхЁхфэюую сшЄр ёцрЄющ шэЇюЁьрЎшш
static void output_bit(int bt)
{
buffer >>= 1;
if (bt)
buffer |= 0x80;
bits_to_go -= 1;
if (bits_to_go == 0)
{
outbuf[outbuf_pos++] = buffer;
bits_to_go = 8;
}
}
//////////////////////////////////////////////////
// ╬ўшёЄър сєЇхЁр яюсшЄютюую т√тюфр
static void done_outputing_bits()
{
outbuf[outbuf_pos++] = buffer >> bits_to_go;
}
//////////////////////////////////////////////////
// ┬√тюф єърчрээюую сшЄр ш юЄыюцхээ√ї Ёрэхх
static void output_bit_plus_follow(int bt)
{
output_bit(bt);
while (bits_to_follow > 0)
{
output_bit(!bt);
bits_to_follow--;
}
}
//////////////////////////////////////////////////
// ╚эшЎшрышчрЎш ЁхушёЄЁют уЁрэшЎ ш ъюфр яхЁхф эрўрыюь ёцрЄш
static void start_encoding()
{
low = 0l;
high = TOP_VALUE;
bits_to_follow = 0l;
}
//////////////////////////////////////////////////
// ╬ўшёЄър яюсшЄютюую т√тюфр
static void done_encoding()
{
bits_to_follow++;
if (low < FIRST_QTR)
output_bit_plus_follow(0);
else
output_bit_plus_follow(1);
}
//////////////////////////////////////////////////
// ╩юфшЁютрэшх юўхЁхфэюую ёшьтюыр
static void encode_symbol ( int symbol)
{
long range;
// яхЁхёўхЄ чэрўхэшщ уЁрэшЎ
range = (long) (high - low) + 1;
high = low + (range * cum_freq [symbol - 1]) / cum_freq [0] - 1;
low = low + (range * cum_freq [symbol]) / cum_freq [0];
// т√фтшурэшх юўхЁхфэ√ї сшЄют
for (;;)
{
if (high < HALF)
output_bit_plus_follow(0);
else if (low >= HALF)
{
output_bit_plus_follow(1);
low -= HALF;
high -= HALF;
}
else if (low >= FIRST_QTR && high < THIRD_QTR)
{
bits_to_follow += 1;
low -= FIRST_QTR;
high -= FIRST_QTR;
}
else
break;
// ёфтшу тыхтю ё "тЄ уштрэшхь" юўхЁхфэюую сшЄр
low = 2 * low;
high = 2 * high + 1;
}
}
#endif //__KEIL__
//////////////////////////////////////////////////
// ╚эшЎшрышчрЎш ЁхушёЄЁют яхЁхф фхъюфшЁютрэшхь.
// ╟руЁєчър эрўрыр ёцрЄюую ёююс∙хэш
static void start_decoding()
{
int i;
value = 0l;
for ( i = 1; i <= BITS_IN_REGISTER; i++)
value = 2 * value + input_bit ();
low = 0l;
high = TOP_VALUE;
}
//////////////////////////////////////////////////
// ─хъюфшЁютрэшх юўхЁхфэюую ёшьтюыр
static int decode_symbol()
{
long range;
int cum, symbol;
// юяЁхфхыхэшх Єхъє∙хую ьрё°Єрср ўрёЄюЄ
range = (long) (high - low) + 1;
// ьрё°ЄрсшЁютрэшх чэрўхэш т ЁхушёЄЁх ъюфр
cum = (int)
((((long) (value - low) + 1) * cum_freq [0] - 1) / range);
// яюшёъ ёююЄтхЄёЄтє■∙хую ёшьтюыр т ЄрсышЎх ўрёЄюЄ
for (symbol = 1; cum_freq [symbol] > cum; symbol++);
// яхЁхёўхЄ уЁрэшЎ
high = low + (range * cum_freq [symbol - 1]) / cum_freq [0] - 1;
low = low + (range * cum_freq [symbol]) / cum_freq [0];
// єфрыхэшх юўхЁхфэюую ёшьтюыр шч тїюфэюую яюЄюър
for (;;)
{
if (high < HALF)
{
}
else if (low >= HALF)
{
value -= HALF;
low -= HALF;
high -= HALF;
}
else if (low >= FIRST_QTR && high < THIRD_QTR)
{
value -= FIRST_QTR;
low -= FIRST_QTR;
high -= FIRST_QTR;
}
else
break;
// ёфтшу тыхтю ё "тЄ уштрэшхь юўхЁхфэюую сшЄр
low = 2 * low;
high = 2 * high + 1;
value = 2 * value + input_bit ();
}
return symbol;
}
#ifndef __KEIL__
//////////////////////////////////////////////////
// └фряЄштэюх рЁшЇьхЄшўхёъюх ъюфшЁютрэшх
// ╧рЁрьхЄЁ√:
// buf - тїюфэющ сєЇхЁ;
// buf_size - ЁрчьхЁ тїюфэюую сєЇхЁр;
// cbuf - сєЇхЁ фы ёцрЄ√ї фрээ√ї;
// cbuf_size - ЁрчьхЁ ёцрЄ√ї фрээ√ї.
void arithmetic_compress(const unsigned char* buf, unsigned long buf_size, unsigned char* cbuf, unsigned long* cbuf_size)
{
unsigned long i;
int ch, symbol;
outbuf = cbuf;
outbuf_pos = 0;
start_model();
start_outputing_bits();
start_encoding();
for (i = 0; i < buf_size; i++)
{
ch = buf[i];
symbol = char_to_index[ch];
encode_symbol(symbol);
update_model(symbol);
}
encode_symbol(EOF_SYMBOL);
done_encoding();
done_outputing_bits();
*cbuf_size = outbuf_pos;
}
#endif //__KEIL__
//////////////////////////////////////////////////
// arithmetic_decompress_init()
// ╚эшЎшрышчрЎш ЁрчцрЄш
// read_func - ЇєэЎш ўЄхэш шч сєЇхЁр ёю ёцрЄ√ьш фрээ√ьш;
//
// !!!! KEIL C WORKAROUND !!!
// ╙ърчрЄхыш эр ЇєэъЎшш ЄЁхсє■Є юёюсюую юсЁр∙хэш :
// http://www.keil.com/appnotes/files/apnt_129.pdf
// !!!! END OF WORKAROUND !!!
//
// cbuf_size - ЁрчьхЁ сєЇхЁр ёю ёцрЄ√ьш фрээ√ьш.
unsigned char arithmetic_decompress_init(read_func_type read_func, unsigned long cbuf_size)
{
{
return 0;
}
read_byte_func = read_func;
inbuf_pos = 0;
inbuf_size = cbuf_size;
start_model();
start_inputing_bits();
start_decoding();
return 1;
}
//////////////////////////////////////////////////
// arithmetic_decompress_done
//
void arithmetic_decompress_done()
{
// nothing to do
}
//////////////////////////////////////////////////
// └фряЄштэюх рЁшЇьхЄшўхёъюх фхъюфшЁютрэшх
// ╧рЁрьхЄЁ√:
// chunk - сєЇхЁ фы ЁрчцрЄ√ї фрээ√ї;
// chunk_size - ЁрчьхЁ сєЇхЁр;
// decompressed - ЁрчьхЁ ЁрчцрЄ√ї фрээ√ї.
void arithmetic_decompress_chunk(unsigned char* chunk, volatile unsigned int chunk_size, unsigned int* decompressed)
{
unsigned long i;
int ch, symbol;
if (inbuf_pos >= inbuf_size)
{
*decompressed = 0;
return;
}
{
*decompressed = 0;
return;
}
outbuf = chunk;
outbuf_pos = 0;
for (i = 0; i < chunk_size; i++)
{
symbol = decode_symbol();
if (symbol == EOF_SYMBOL)
break;
ch = index_to_char[symbol];
outbuf[outbuf_pos++] = ch;
update_model(symbol);
}
*decompressed = outbuf_pos;
}
//////////////////////////////////////////////////