#include "arithmetic_encoding.h"

static void bit_plus_follow();

/* Поточний стан кодування */

static code_value low, high;

static long bits_to_follow;

/* Початок кодування потока символів */

start_encoding()

{ low = 0;

high = Top_value;

bits_to_follow = 0;

}

/* Кодування символу */

encode_symbol(symbol,cum_freq)

int symbol;

int cum_freq[];

{ 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) {

bit_plus_follow(0);

}

else if (low>=Half) {

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;

}

}

/* Завершення кодування потоку */

done_encoding()

{ bits_to_follow += 1;

if (low<First_qtr) bits_plus_follow(0);

else bit_plus_follow(1);

}

/* вивод біта разом з наступними за ним, оберненими до нього */

static void bit_plus_follow(bit)

int bit;

{ output_bit(bit);

while (bits_to_follow>0) {

output_bit(!bit);

bits_to_follow -= 1;

}

}

decode.c

/* Головна процедура для декодування */

#include <stdio.h>

#include "model.h"

main()

{ start_model();

start_inputing_bits();

start_decoding();

for (;;) {

int ch; int symbol;

symbol = decode_symbol(cum_freq);

if (symbol == EOF_symbol) break;

ch = index_to_char[symbol];

putc(ch,stdout);

update_model(symbol);

}

exit(0);

}

arithmetic_decode.c

/* Алгоритм арифметичного декодування */

#include "arithmetic_coding.h"

/* Потоковий стан декодування */

static code_value value;

static code_value low, high;

/* Початок декодування потока символів */

start_decoding();

{ int i;

value = 0;

for (i = 1; i<=Code_value_bits; i++) {

value = 2*value+input_bit();

}

low = 0;

high = Top_value;

}

/* Декодування наступного символа */

int decode_symbol(cum_freq)

int cum_freq[];

long range;

int cum;

int symbol;

range = (long)(high - low)+1;

cum = (((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) {/*nothing*/}

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;

}

return symbol;

}

bit_input.c

/* Процедури вводу бітів */

#include <stdio.h>

#include "arithmetic_coding"

/* Бітовий буфер */

static int buffer;

static int bits_to_go;

static int garbage_bits;

/* Ініціацізація побітового вводу */

start_inputing_bits();

{ bits_to_go = 0;

garbage_bits = 0;

}

/* Ввод біта */

int input_bit();

{ int t;

if (bits_to_go==0) {

buffer = getc(stdin);

if (buffer==EOF) {

garbage_bits +=1;

if (garbage_bits>Code_value_bits-2) {

fprintf(stderr,"Bad input file\n");

exit(-1);

}

}

bits_to_go = 8;

}

t = buffer&1;

buffer >>= 1;

bits_to_go -= 1;

return t;

}

bit_output.c

/* Процедура виводу бітів */

#include <stdio.h>

/* Бітовий буфер */

static int buffer;

static int bits_to_go;

/* Ініціалізація бітового буфера */

start_outputing_bits()

{ buffer = 0;

bits_to_go = 8;

}

/* Вивід біта */

output_bit(bit)

int bit;

{ buffer >>=1;

if (bit) buffer |= 0x80;

bits_to_go -= 1;

if (bits_to_go==0) {

putc(buffer,stdout);

bits_to_go = 8;

}

}

/* Вимивання останніх бітів */

done_outputing_bits()

{ putc(buffer>>bits_to_go,stdout);

}

adaptive_model.c

/* Модель з адаптивним джерелом */

#include "model.h"

int freq[No_of_symbols+1];

/* Ініціалізація моделі */

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;

/* Оновлення моделі у відповідності з новим символом */

update_model(symbol)

int symbol;

{ int i;

if (cum_freq[0]==Max_frequency) {

int cum;

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) {

int ch_i, ch_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;

}

}

Література.

Rubin F. Arithmetic stream coding using fixed precision registers, IEEE Transactions IT-25, #6, Nov79, pp. 672 – 675.

Кричевский Р. Е. Сжатие и поиск информации., Москва, 1989 г.

Кохманюк Д. Сжатие информации: как это делаеться., IndexPRO, Киев, №№1,2.