РГР_Слєпцова_ДА-62. Програмна реалізація методу
 Скачать 145.82 Kb.
|
|
//------------------------------------------------------------ // Обновление модели очередным символом 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 (void) { bits_to_go = 0; garbage_bits = 0; } //------------------------------------------------------------ // Ввод бита int input_bit (void) { int t; if (bits_to_go == 0) { buffer = getc (in); if (buffer == EOF) { garbage_bits += 1; if (garbage_bits > BITS_IN_REGISTER - 2) { printf ("Ошибка в сжатом файле\n"); } } bits_to_go = 8; } t = buffer & 1; buffer >>= 1; bits_to_go -= 1; return t; } //------------------------------------------------------------ // Инициализация побитового вывода void start_outputing_bits (void) { buffer = 0; bits_to_go = 8; } //------------------------------------------------------------ // Вывод бита void output_bit ( int bit) { buffer >>= 1; // делим на два if (bit) buffer |= 0x80; bits_to_go -= 1; if (bits_to_go == 0) { putc ( buffer, out); bits_to_go = 8; } } //------------------------------------------------------------ // Очистка вывода void done_outputing_bits (void) { putc ( buffer >> bits_to_go, out); } //------------------------------------------------------------ // Вывод бита void output_bit_plus_follow ( int bit) { output_bit (bit); while (bits_to_follow > 0) { output_bit (!bit); bits_to_follow--; } } //------------------------------------------------------------ // Инициализация границ void start_encoding (void) { lowLimit = 0l; highLimit = TOP_VALUE; bits_to_follow = 0l; } //------------------------------------------------------------ // Очистка вывода void done_encoding (void) { bits_to_follow++; if (lowLimit < FIRST_QTR) output_bit_plus_follow (0); else output_bit_plus_follow (1); } //------------------------------------------------------------ /* Инициализация регистров перед декодированием. Загрузка начала сжатого сообщения */ void start_decoding (void) { int i; value = 0l; for ( i = 1; i <= BITS_IN_REGISTER; i++) value = 2 * value + input_bit (); lowLimit = 0l; highLimit = TOP_VALUE; } //------------------------------------------------------------ // Кодирование символа void encode_Symbol ( int Symbol) { long limit; // пересчет значений границ limit = (long) (highLimit - lowLimit) + 1; highLimit = lowLimit + (limit * cum_freq [Symbol - 1]) / cum_freq [0] - 1; lowLimit = lowLimit + (limit * cum_freq [Symbol]) / cum_freq [0]; // выдвигание очередных битов for (;;) { if (highLimit < HALF) output_bit_plus_follow (0); else if (lowLimit >= HALF) { output_bit_plus_follow (1); lowLimit -= HALF; highLimit -= HALF; } else if (lowLimit >= FIRST_QTR && highLimit < THIRD_QTR) { bits_to_follow += 1; lowLimit -= FIRST_QTR; highLimit -= FIRST_QTR; } else break; // сдвиг влево с "втягиванием" очередного бита lowLimit = 2 * lowLimit; highLimit = 2 * highLimit + 1; } } //------------------------------------------------------------ // Декодирование символа int decode_Symbol (void) { long limit; int cum, Symbol; // определение текущего масштаба частот limit = (long) (highLimit - lowLimit) + 1; // масштабирование значения в регистре кода cum = (int) ((((long) (value - lowLimit) + 1) * cum_freq [0] - 1) / limit); // поиск соответствующего символа в таблице частот for (Symbol = 1; cum_freq [Symbol] > cum; Symbol++); // пересчет границ highLimit = lowLimit + (limit * cum_freq [Symbol - 1]) / cum_freq [0] - 1; lowLimit = lowLimit + (limit * cum_freq [Symbol]) / cum_freq [0]; // удаление очередного символа из входного потока for (;;) { if (highLimit < HALF) { } else if (lowLimit >= HALF) { value -= HALF; lowLimit -= HALF; highLimit -= HALF; } else if (lowLimit >= FIRST_QTR && highLimit < THIRD_QTR) { value -= FIRST_QTR; lowLimit -= FIRST_QTR; highLimit -= FIRST_QTR; } else break; // сдвиг влево lowLimit = 2 * lowLimit; highLimit = 2 * highLimit + 1; value = 2 * value + input_bit (); } return Symbol; } //------------------------------------------------------------ // кодирование void encode ( char *infile, char *outfile) { int ch, Symbol; in = fopen ( infile, "r+b"); out = fopen ( outfile, "w+b"); if (in == NULL || out == NULL) return; start_model (); start_outputing_bits (); start_encoding (); for (;;) { ch = getc (in); if (ch == EOF) break; Symbol = char_to_index [ch]; encode_Symbol (Symbol); update_model (Symbol); } encode_Symbol (EOF_Symbol); done_encoding (); done_outputing_bits (); fclose (in); fclose (out); } //------------------------------------------------------------ // декодирование void decode ( char *infile, char *outfile) { int ch, Symbol; in = fopen ( infile, "r+b"); out = fopen ( outfile, "w+b"); if (in == NULL || out == NULL) return; start_model (); start_inputing_bits (); start_decoding (); for (;;) { Symbol = decode_Symbol (); if (Symbol == EOF_Symbol) break; ch = index_to_char [Symbol]; putc ( ch, out); update_model (Symbol); } fclose (in); fclose (out); } int main (int argc, char** argv) { encode ( "test.txt", "2.txt"); decode ( "2.txt", "3.txt"); return 0; } |