-/*
- Copyright (C) Arturo San Emeterio Campos 1999. All rights reserved.
- Permission is granted to make verbatim copies of this file for private
- use only. There is ABSOLUTELY NO WARRANTY. Use it at your OWN RISK.
-
- This file is: "ppmc.c"
- Email: arturo@arturocampos.com
- Web: http://www.arturocampos.com
-
- Part of the ppmc encoder and decoder.
-
- This module contains the whole ppmc encoder. It uses hash tables for
- managing most of the orders. And a maximum order of 4. It codes bytes.
- Order-1-0-(-1) are all handled in tables. Order-2 has a table with
- direct hashing with pointers to the linked lists. Order-4 and order-3
- both have hash tables with pointers to contexts in a linked lists which
- finally have a pointer to the start of the linked list with the
- probability distribution. Update exclusion is used, but exclusion is not.
-
- Please, note that if the machine where the decoder is run doesn't has as
- much memory as the computer where the encoder was ran, the decoder will
- not be able to properly decode the file, because it will not be able to
- keep track of new statistics, in this case it will just exit.
-
- For applications where the loss of data is not admisible, I suggest you to
- limit both encoder and decoder's memory requeriments to a given minimum
- which both machines have.
-*/
-
-
-#include <stdio.h>
-#include <stdlib.h>
-#include "range.h"
-#include "ppmcdata.h"
-
-static unsigned ordern1_table[] = {
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 4303574, 88451153, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 143318, 9172380, 1146547, 100, 143318, 573273, 859910, 10318928,
- 10318928, 6019374, 573273, 26657231, 1576502, 43138853, 10462246, 3439642,
- 6162693, 6162693, 6162693, 6162693, 6162693, 6162693, 6162693, 6162693,
- 6162693, 6162693, 8742425, 4299553, 14188526, 3439642, 9888973, 429955,
- 143318, 27230505, 2436413, 22357678, 10892202, 40989076, 1576502, 1433184,
- 286636, 37406115, 573273, 286636, 19204672, 13901889, 19491309, 10462246,
- 16481621, 1003229, 21211130, 13615252, 17914806, 2866368, 4012916, 429955,
- 1719821, 1146547, 143318, 286636, 143318, 286636, 143318, 1576502,
- 143318, 315013952, 32246651, 165962764, 171122228, 418203235, 23790862, 26800550,
- 17054895, 230742703, 7452559, 1003229, 163669669, 75385504, 225153284, 261412851,
- 88140846, 24794091, 215837585, 223003507, 162523121, 110355206, 38122707, 5302782,
- 7595877, 18918035, 8885743, 859910, 100, 859910, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
- 100, 100, 100, 100, 100, 100, 100, 100,
-};
-#define ordern1_total_cump 3651941255u
-
-// Ruotines used by ppmc. Not including the range coder.
-//
-// They are for initializing of both encoder and decoder, and unless there
-// are two version, both encoder and decoder use the same routines. Like
-// "ppmc_initialize_contexts".
-
-
-// This one allocs the memory needed by ppmc, and adjust some pointers used
-// for allocating elements in the linked lists. The mempool arrays must be
-// initialized now.
-void ppmc_alloc_memory(void)
-{
- unsigned long counter;
-
-
- // Init mempool buffers
-
- for(counter=0;counter!=_mempool_max_index;++counter)
- {
- _bytes_pool_array[counter]=0;
- _context_pool_array[counter]=0;
- }
-
- _bytes_pool_index=1; //first entry will be used now
- _context_pool_index=1;
-
-
- // Allocate memory for ppmc structures and adjust some variables
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
-
- //save pointers in the array for freeing
- _bytes_pool_array[0]=_bytes_pool;
- _context_pool_array[0]=_context_pool;
-
-
- //adjust variables
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements;
- _context_pool_max=_context_pool+_context_pool_elements;
-
- ppmc_out_of_memory=0; //we still have memory
-}
-
-
-// This routine initializes all the contexts, and all the tables including
-// those who care about the number of bytes defined in a context.
-void ppmc_initialize_contexts(void)
-{
- unsigned long counter, counter2;
-
-
- // Order-0
- for(counter=0;counter!=256;++counter) //clear table
- order0_array[counter]=0;
-
- order0_defined_bytes=0; //adjust variables
- order0_max_cump=0;
-
-
- // Order-1
- for(counter=0;counter!=256;++counter) //erase every table of every context
- for(counter2=0;counter2!=256;++counter2)
- order1_array[counter][counter2]=0;
-
- for(counter=0;counter!=256;++counter) //adjust variables
- {
- order1_defined_bytes_array[counter]=0;
- order1_max_cump_array[counter]=0;
- }
-
-
- // Order-2
- for(counter=0;counter!=65536;++counter)
- {
- //order2_array[counter].prob=0; //clear pointer to bytes and frequencies
- //order2_array[counter].max_cump=0;
- order2_array[counter].defined_bytes=0;
- }
-
-
- // Order-4-3
- for(counter=0;counter!=65536;++counter) //order-4-3
- {
- order4_hasht[counter]=0;
- order3_hasht[counter]=0;
- }
-}
-
-
-// This routine initializes the encode model by outputting as many bytes as
-// needed to prepare the models. This should be called before the main loop
-// and after the memory has been allocated and tables initialized.
-//
-// It does not need uses the range coder. It output the first 1 bytes.
-void ppmc_encoder_initialize(void)
-{
-
- // Initialize order-0 and prepare different bytes for orders
- fputc((byte=fgetc(file_input)),file_output);
- o4_byte=byte; //order-4
-
- fputc((byte=fgetc(file_input)),file_output);
- o3_byte=byte; //order-3
-
- fputc((byte=fgetc(file_input)),file_output);
- o2_byte=byte; //order-2
- ppmc_update_order0();
-
- fputc((byte=fgetc(file_input)),file_output);
- o1_byte=byte;
-
-}
-
-
-// This routine initializes the decoder model, should be called to do the same
-// changes as "ppmc_encoder_initialize()" did.
-void ppmc_decoder_initialize(void)
-{
-
- // Initialize order-0 and context bytes
- byte=fgetc(file_input);
- o4_byte=byte; //order-4
- fputc(byte,file_output);
-
- byte=fgetc(file_input);
- o3_byte=byte; //order-3
- fputc(byte,file_output);
-
- byte=fgetc(file_input);
- o2_byte=byte; //order-2
-
- fputc(byte,file_output); //output first byte
- ppmc_update_order0();
-
- byte=fgetc(file_input);
- o1_byte=byte; //order-1
- fputc(byte,file_output);
-}
-
-
-// Once coding or decoding is finished you have to call this routine.
-// It must be called when done.
-void ppmc_free_memory(void)
-{
- unsigned long counter;
-
- // Free the memory buffers
-
- for(counter=0;counter!=_mempool_max_index;++counter)
- {
- if(_bytes_pool_array[counter]!=0)
- free(_bytes_pool_array[counter]);
-
- if(_context_pool_array[counter]!=0)
- free(_context_pool_array[counter]);
- }
-
-}
-
-
-// This routine flushes the memory and restarts all the tables of
-// probabilities, current order bytes are not modified, this function
-// is called when we ran out of memory. We have to output the code
-// number 256 which means memory flushing, for doing this we have to go
-// to order-(-1) so we have to output an escape code in all the orders
-// till we reach order-(-1) where we can code it. Then we free all the
-// memory, alloc it again, and reinitialize all the orders.
-//
-// However we may find the case when the current order is not initialized,
-// in this case we don't need to output an escape code.
-void ppmc_flush_mem_enc(void)
-{
-
- // Code an escape code in order-4
- if(ppmc_get_totf_order4()!=0) //if 0 no need of escape code
- {
-
- ppmc_get_escape_prob_order4(); //get prob and cump
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- }
-
-
- // Code an escape code in order-3
- if(ppmc_get_totf_order3()!=0) //if 0 no need of escape code
- {
-
- ppmc_get_escape_prob_order3(); //get prob and cump
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- }
-
-
- // Code an escape code in order-2
-
- o2_cntxt=ppmc_order2_hash_key(o1_byte,o2_byte);
-
- // First check if current order-2 context is empty
- if(order2_array[o2_cntxt].defined_bytes!=0) //it's not empty
- {
- ppmc_get_totf_order2();
- ppmc_get_escape_prob_order2();
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
- }
-
-
- // Code an escape code in order-1
-
- // First check if current order-1 table is empty
- if(order1_defined_bytes_array[o1_byte]!=0) //it's not empty
- {
- ppmc_get_totf_order1();
- ppmc_get_escape_prob_order1();
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
- }
-
-
- // Code an escape code in order-0. Order-0 always has at least one symbol
-
- ppmc_get_totf_order0();
- ppmc_get_escape_prob_order0();
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
-
-
- // Now we can code the code 256
-
- symb_prob=1;
- symb_cump=256;
- total_cump=257;
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
-
- // Now that decoder knows the flushing, free memory and reinit
-
- ppmc_free_memory();
- ppmc_alloc_memory();
- ppmc_initialize_contexts();
-
-
- // Be sure that order-0 has at least one probability
-
- order0_array[o1_byte]++;
- order0_max_cump++;
- order0_defined_bytes++;
-
-}
-
-
-// When the decoder gets the symbol of flushing, most of the job is done
-// because we already got all the escape codes, so we only have to reinit.
-void ppmc_flush_mem_dec(void)
-{
-
- // Free memory and reinit
-
- ppmc_free_memory();
- ppmc_alloc_memory();
- ppmc_initialize_contexts();
-
-
- // Be sure that order-0 has at least one probability
-
- order0_array[o1_byte]++;
- order0_max_cump++;
- order0_defined_bytes++;
-
-
-}
-
-
-
-// ORDER-(-1) functions, also called ordern1 (Negative1) in functions
-//
-// Because order-(-1) does not need to update its probability tables, it
-// has no tables, and relies on the fact that the cump of byte is its own
-// value, and the probability is fixed, 1, and the total cump is 257.
-//
-// The alphabet has the following distribution: 0-255 the bytes. 256 is
-// an special symbol which means that we have flushed the encoder tables,
-// and thus the encoder must flush its tables too.
-//
-// The rest of the tables only have 256 symbols, because we have no need
-// of assign a symbol to the flush code (which already is the order-(-1)
-// table) nor to the escape code.
-
-
-// Gets the probability for a given symbol in the order-(-1) (ordern1)
-void ppmc_get_prob_ordern1(void)
-{
- int i;
- unsigned acum = 0;
- for (i = 0; i < 256 || i == byte; ++i)
- acum += ordern1_table[i];
- symb_cump=acum;
- symb_prob=ordern1_table[i];
- total_cump=ordern1_total_cump;
-}
-
-
-// Returns in the variable "total_cump" the current total cump of
-// order-(-1)
-void ppmc_get_totf_ordern1(void)
-{
- total_cump=ordern1_total_cump;
-}
-
-
-// Returns the symbol for a given cump under order-(-1)
-unsigned long ppmc_get_symbol_ordern1 (void)
-{
- return symb_cump;
-}
-
-
-
-// ORDER-0 functions
-//
-// Due to the fact that order-0 has no context, I use an array for all the
-// probabilities under order-0, just as you could do in a basic model for
-// arithmetic coding.
-//
-// The main array is: order0_array. Where order0_array[byte] contains the
-// probability for a given byte. The same applies to order-1.
-//
-// To ensure that the updating and coding is done correctly, "byte" can't
-// be changed till all the coding and updating is done.
-
-
-// Returns in the variable "total_cump" the current total cump of
-// order-0
-void ppmc_get_totf_order0(void)
-{
- // Total cump is current total cump plus the escape for the escape code
- total_cump=order0_defined_bytes+order0_max_cump;
-}
-
-
-// Codes a byte under order-0 and returns 1, otherwise it returns a 0 and
-// has coded an escape code. In this case further coding is needed.
-//
-// Returns: 1 in case a byte was coded. 0 in case of escape code.
-char ppmc_code_byte_order0(void)
-{
- unsigned long counter;
-
- ppmc_get_totf_order0(); //get total cump
-
- // See if the byte is present
- if(order0_array[byte]==0) //a probability of 0
- {
-
- // Because it was not present, output an escape code, prepare variables
-
- symb_cump=order0_max_cump; //obviously its cump is current max_cump
- //without escape code's space
-
- symb_prob=order0_defined_bytes; //the number of defined bytes
-
- // Code the escape code
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 0; //byte not coded
- }
- else
- {
-
- coded_in_order=0;
-
- // The symbol is present, code it under order-0
-
- symb_prob=order0_array[byte]; //get probability directly
-
- // Make cump for current symbol
-
- symb_cump=0; //for first symbol is 0
- for(counter=0; counter!=byte ; ++counter)
- symb_cump+=order0_array[counter]; //sum probabilities before our symbol
-
- // Code the symbol
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 1; //symbol coded under order-0
- }
-}
-
-
-// This functions update order-0 probabilities with current byte, also takes
-// care about updating variables, and renormalizing.
-void ppmc_update_order0(void)
-{
- if(order0_array[byte]==0)
- {
- // It had a zero probability
- order0_array[byte]++; //increment symbol probability
- ++order0_defined_bytes; //new byte defined
- ++order0_max_cump; //total cump
- return;
- }
- else
- {
- // It had a non-zero probability
-
- // Increment its probability
- order0_array[byte]++; //increment symbol probability
- ++order0_max_cump; //total cump
-
- // Check to see if its the maximum in this case renormalize
- if(order0_array[byte]==255)
- ppmc_renormalize_order0();
-
- return;
- }
-}
-
-
-// This functions renormalizes the probabilities at order-0 updating variables
-void ppmc_renormalize_order0(void)
-{
- unsigned long counter;
-
- // Initialize variables
- order0_defined_bytes=0; //clear them
- order0_max_cump=0;
-
- // Loop over all probabilities, divide them by a factor of 2 and update variables
- for(counter=0 ; counter!=256 ; ++counter)
- {
- order0_array[counter]>>=1; //divide by a factor of 2
-
- if(order0_array[counter]!=0) //see if it has a non zero probability
- order0_defined_bytes++;
-
- order0_max_cump+=order0_array[counter]; //sum to the total cump
- }
-}
-
-
-// Decodes the symbol correspoding to the current order, it returns the byte
-// or in case of a escape code it returns -1
-void ppmc_decode_order0(void)
-{
- unsigned long current_cump, counter;
-
-
- // Get the total cump needed for decoding symbol
- ppmc_get_totf_order0(); //total cump needed for decoding
- symb_cump=range_decoder_decode(&rc_decoder,total_cump); //decode it
-
- // Now check if it's an escape code
- if(symb_cump>=order0_max_cump) //the defined code space for the escape code
- {
-
- // Update coding values
-
- ppmc_get_escape_prob_order0();
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Mark as escape code
-
- byte=-1;
-
- return; //an escape code
- }
- else
- {
- // Now we have to check what symbol it is
-
- current_cump=0; //cump of the current symbol
-
- for(counter=0 ; counter!= 256 ; ++counter)
- {
- if(symb_cump<current_cump)
- break; //symbol found, break search loop
- current_cump+=order0_array[counter]; //update cump
- }
-
- counter--; //-1 (see ac_ppmc.html, searching for a given symbol)
-
- byte=counter; //update the variable with the found symbol
-
-
- // Get the cump and prob of byte
-
- symb_prob=order0_array[byte]; //the probabilty
- symb_cump=current_cump-order0_array[byte]; //using the cump which was
- //already made
-
- // Update coding state
-
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- coded_in_order=0; //decoded under order-0
-
- return;
- }
-
-}
-
-
-// This function returns the probability for the escape codes in the variables
-void ppmc_get_escape_prob_order0(void)
-{
- // To understand that remember that the escape allocated for the escape code
- // is above the current maximum cump and that it has a probability determined
- // by the scheme C.
- symb_prob=order0_defined_bytes;
- symb_cump=order0_max_cump;
- total_cump=order0_defined_bytes+order0_max_cump;
-}
-
-
-
-// ORDER-1 functions
-//
-// Order-1 uses 256 arrays one for every context, obviously they are accessed
-// like that: order1_array[o1_byte][byte]
-//
-// Also for computing the value of the current escape code in a given context
-// we need to know how many bytes are defined in a given context, they are
-// stored in an array, and you use them like that:
-// order1_defined_bytes_array[o1_byte]
-//
-// The same goes for the maximum cump of a given context:
-// order1_max_cump_array[o1_byte]
-//
-// Read the order-0 explanation.
-//
-// To ensure that the updating and coding is done correctly, "byte" and
-// "o1_byte" can't be changed till all the coding and updating is done.
-
-
-// Returns in the variable "total_cump" the current total cump of
-// order-1. o1_byte should contain the order-1
-void ppmc_get_totf_order1(void)
-{
- // Total cump is current total cump plus the escape for the escape code
- total_cump=order1_defined_bytes_array[o1_byte]+order1_max_cump_array[o1_byte];
-}
-
-
-// Codes a byte under order-1 and returns 1.
-// Otherwise it returns a 0 it may be that it has coded an escape code, or
-// that current table was empty, in this case nothing is outputted
-// In both cases further coding is needed.
-//
-// Returns: 1 in case a byte was coded. 0 in case of escape code or empty table.
-// In case the byte is coded under this context, coded_in_order=1.
-char ppmc_code_byte_order1(void)
-{
- unsigned long counter;
-
-
- // First check if current order-1 table is empty
- if(order1_defined_bytes_array[o1_byte]==0) //it's empty
- {
- return 0; //byte not coded, nothing done
- }
-
-
- // Now try to code this byte under order-1
-
- ppmc_get_totf_order1(); //get total cump
-
- // See if the byte is present
- if(order1_array[o1_byte][byte]==0) //a probability of 0
- {
-
- // Because it was not present, output an escape code, prepare variables
-
- symb_cump=order1_max_cump_array[o1_byte];//obviously its cump is current max_cump
- //without escape code's space
-
- symb_prob=order1_defined_bytes_array[o1_byte];//the number of defined bytes
-
- // Code the escape code
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 0; //byte not coded, escape coded
- }
- else
- {
-
- coded_in_order=1; //because we coded it under order-1
-
- // The symbol is present, code it under order-1
-
- symb_prob=order1_array[o1_byte][byte]; //get probability directly
-
- // Make cump for current symbol
-
- symb_cump=0; //for first symbol is 0
- for(counter=0; counter!=byte ; ++counter)
- symb_cump+=order1_array[o1_byte][counter]; //sum probabilities before our symbol
-
- // Code the symbol
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 1; //symbol coded under order-1
- }
-}
-
-
-// This functions update order-1 probabilities with current byte, also takes
-// care about updating variables, and renormalizing. o1_byte must be filled.
-void ppmc_update_order1(void)
-{
- if(order1_array[o1_byte][byte]==0)
- {
- // It had a zero probability
- order1_array[o1_byte][byte]++; //increment symbol probability
- ++order1_defined_bytes_array[o1_byte]; //new byte defined
- ++order1_max_cump_array[o1_byte]; //total cump
- return;
- }
- else
- {
- // It had a non-zero probability
-
- // Increment its probability
- order1_array[o1_byte][byte]++; //increment symbol probability
- ++order1_max_cump_array[o1_byte]; //total cump
-
- // Check to see if its the maximum in this case renormalize
- if(order1_array[o1_byte][byte]==255)
- ppmc_renormalize_order1();
-
- return;
- }
-}
-
-
-// This functions renormalizes the probabilities at order-1 updating variables
-void ppmc_renormalize_order1(void)
-{
- unsigned long counter;
-
- // Initialize variables
- order1_defined_bytes_array[o1_byte]=0; //clear them
- order1_max_cump_array[o1_byte]=0;
-
- // Loop over all probabilities, divide them by a factor of 2 and update variables
- for(counter=0 ; counter!=256 ; ++counter)
- {
- order1_array[o1_byte][counter]>>=1; //divide by a factor of 2
-
- if(order1_array[o1_byte][counter]!=0) //see if it has a non zero probability
- order1_defined_bytes_array[o1_byte]++;
-
- order1_max_cump_array[o1_byte]+=order1_array[o1_byte][counter]; //sum to the total cump
- }
-}
-
-
-// Decodes the symbol correspoding to the current order, it returns the byte
-// or in case of an escape code or empty table it returns -1.
-// It updates "coded_in_order".
-void ppmc_decode_order1(void)
-{
- unsigned long current_cump, counter;
-
-
- // First check if current order-1 table is empty
- if(order1_defined_bytes_array[o1_byte]==0) //it's empty
- {
- byte=-1; //byte not coded, nothing done
- return;
- }
-
-
- // Get the total cump needed for decoding symbol
- ppmc_get_totf_order1(); //total cump needed for decoding
- symb_cump=range_decoder_decode(&rc_decoder,total_cump); //decode it
-
- // Now check if it's an escape code
- if(symb_cump>=order1_max_cump_array[o1_byte]) //the defined code space for the escape code
- {
-
- // Update coding values
-
- ppmc_get_escape_prob_order1();
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Mark as escape code
-
- byte=-1;
-
- return; //an escape code
- }
- else
- {
- // Now we have to check what symbol it is
-
- current_cump=0; //cump of the current symbol
-
- for(counter=0 ; counter!= 256 ; ++counter)
- {
- if(symb_cump<current_cump)
- break; //symbol found, break search loop
- current_cump+=order1_array[o1_byte][counter]; //update cump
- }
-
- counter--; //-1 (see ac_ppmc.html, searching for a given symbol)
-
- byte=counter; //update the variable with the found symbol
-
-
- // Get the cump and prob of byte
-
- symb_prob=order1_array[o1_byte][byte]; //the probabilty
- symb_cump=current_cump-order1_array[o1_byte][byte]; //using the cump which was
- //already made
-
- // Update coding state
-
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
-
- // Update coded_in_order used for update exclusion
-
- coded_in_order=1;
-
- return;
- }
-
-}
-
-
-// This function returns the probability for the escape codes in the variables
-void ppmc_get_escape_prob_order1(void)
-{
- // To understand that remember that the escape allocated for the escape code
- // is above the current maximum cump and that it has a probability determined
- // by the scheme C.
- symb_prob=order1_defined_bytes_array[o1_byte];
- symb_cump=order1_max_cump_array[o1_byte];
- total_cump=order1_defined_bytes_array[o1_byte]+order1_max_cump_array[o1_byte];
-}
-
-
-
-// ORDER-2 functions
-//
-// Order-2 uses a table which holds the contexts data structure of every
-// structure, its accessed with "ppmc_order2_hash_key(o1_byte, o2_byte)"
-// and because it uses direct addressing there's no need to check for hash
-// collisions, which makes it faster. The variable "o2_cntxt" contains o1_byte
-// and o2_byte used directly to index the order-2 array.
-//
-// Though order-2 uses the same routines as lower orders they are rather
-// different, because we can't allocate memory for all the probabilities
-// tables, we have to use linked lists for the bytes and probabilities.
-//
-// Under order-2 we don't let a probability to be lower than 1, that is,
-// there can't be a symbol in a linked list with a 0 probability, I choosed
-// this for three factors: the code is easier to read (it isn't messy)
-// we gain some speed, and the loss of compression seems little.
-//
-// To ensure that the updating is done correctly, "o2_cntxt" and
-// "o2_ll_node" must not be modified by any routine except those who manage
-// order-2.
-
-
-// Returns in the variable "total_cump" the current total cump of
-// order-2. cntxt must have o1_byte and o2_byte hashed with the hash key
-// for order-2.
-void ppmc_get_totf_order2(void)
-{
- // Total cump is current total cump plus the escape for the escape code
- total_cump=order2_array[o2_cntxt].defined_bytes+order2_array[o2_cntxt].max_cump;
-}
-
-
-// Codes a byte under order-2 and returns 1.
-// Otherwise it returns a 0. It may be that it has coded an escape code, or
-// that current table was empty.
-//
-// Returns: 1 in case a byte was coded. 0 in case of escape code or empty table.
-// In case the byte is coded under this context, coded_in_order=2.
-char ppmc_code_byte_order2(void)
-{
- unsigned long counter;
- struct _byte_and_freq *node;
-
-
- // Initialize o2_cntxt
-
- o2_cntxt=ppmc_order2_hash_key(o1_byte,o2_byte);
-
-
- // First check if current order-2 context is empty
- if(order2_array[o2_cntxt].defined_bytes==0) //it's empty
- {
- return 0; //byte not coded, nothing done
- }
-
-
- // Now try to code this byte under order-2
-
- ppmc_get_totf_order2(); //get total cump
-
-
- // See if the byte is present and compute its cump at the same time
-
- node=order2_array[o2_cntxt].prob; //pointer to first element in the linked list
-
- symb_cump=0; //the first symbol always has a 0 cump
-
-
- // Now search the byte in the linked list
-
- do{
- if(node->byte==byte)
- goto ppmc_o2_byte_found; //bad thing, I know, anyone has a better idea?
- symb_cump+=node->freq; //add the probability of this byte to the cump
- if(node->next==0)
- break;
- node=node->next; //next element in the linked list
- }while(1);
-
-
- // If we reach that point, the byte was not found in the linked list
- // so we don't need the cump, we have to output an escape code, whose
- // probabilities are know using the context structure in the table.
-
- // Byte was not present in the linked list, current node is the last one,
- // and that's the node needed for creating a new node, save it.
-
- o2_ll_node=node;
-
- // Now get the probability and cump of the escape code
-
- symb_cump=order2_array[o2_cntxt].max_cump;
- symb_prob=order2_array[o2_cntxt].defined_bytes;
-
- // Code the escape code
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 0;
-
-
- // That code is executed when the byte is found in the linked list
-
-ppmc_o2_byte_found:
-
-
- // Everything has been tested, now we can feel free to code the byte,
- // the symb_cump is already computed, now get its probability and code
- // the byte, also save pointer to this element in the linked lists for
- // updating.
-
- coded_in_order=2; //successfully coded under order-2
-
- o2_ll_node=node; //save it for updating
-
- symb_prob=node->freq; //get the probability of the byte
-
- // Code it.
-
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 1; //byte coded under order-2
-}
-
-
-// This functions update order-2 probabilities with current byte, also takes
-// care about updating variables, and renormalizing.
-// Of course "o2_ll_node" must point to the element to update or the last one,
-// based on the "coded_in_order" and checking the pointer of the element we
-// can decide what to do.
-//
-// This updating is only for encoding.
-void ppmc_update_order2(void)
-{
-
- // First of all check if that's the first byte in this context, in that case
- // we have to initialize some variables in the context structure.
-
- if(order2_array[o2_cntxt].defined_bytes==0) //no byte defined yet
- {
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
- order2_array[o2_cntxt].defined_bytes=1;
- order2_array[o2_cntxt].max_cump=1;
- order2_array[o2_cntxt].prob=_bytes_pool;
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- return; //nothing else to do
- }
-
-
- // The byte was coded under order two, otherwise it was coded under a
- // lower order (never higher ones, remember that we are using update
- // exclusion) in this case we have to create a new node in the list.
-
- if(coded_in_order==2) //coded under order-2
- {
-
- // Update its count and variables of this context and check for renormalization
-
- o2_ll_node->freq++; //increment its frequency (rather probability)
-
- order2_array[o2_cntxt].max_cump++; //total cump
-
- if(o2_ll_node->freq==255) //do we have to renormalize?
- ppmc_renormalize_order2(); //renormalize
-
- }
- else
- {
-
- // Once every paranoid check has been done we are sure that this byte
- // did not existed and so we have to create a new node in the linked
- // list. Also we have to take care of memory issues.
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate mem
-
- o2_ll_node->next=_bytes_pool; //put it in the next free entry
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- order2_array[o2_cntxt].max_cump++; //total cump
- order2_array[o2_cntxt].defined_bytes++; //total cump
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- }
-
-}
-
-
-// This functions renormalizes the probabilities at order-2 updating context
-// variables.
-void ppmc_renormalize_order2(void)
-{
- unsigned long counter;
- struct _byte_and_freq *node;
-
- // Initialize variables. Defined bytes remain the same.
- order2_array[o2_cntxt].max_cump=0; //clear them
-
- node=order2_array[o2_cntxt].prob; //get pointer to lined lists
-
- // Divide all the probabilities by 2 and update context variables
- while(1)
- {
- node->freq>>=1; //divide by a factor of 2
-
- if(node->freq==0) //don't allow a probability to be 0
- node->freq=1;
-
- order2_array[o2_cntxt].max_cump+=node->freq; //sum to the total cump
-
- if(node->next==0) //last element
- break;
- node=node->next;
- }
-
-
- //printf("\nRenormalization, context:%c%c",o2_byte,o1_byte);
-
-}
-
-
-// Decodes the symbol correspoding to the current order, it returns the byte
-// or in case of an escape code or empty table it returns -1.
-// It updates "coded_in_order".
-//
-// If we decode an escape code, we don't modify "o2_ll_node" and thus its
-// work of the updating routine to read till the end of the linked list
-// (for adding a new element) however if we decode a byte, we save on
-// "o2_ll_node" the pointer to its node. (so updating is faster)
-void ppmc_decode_order2(void)
-{
- unsigned long current_cump, counter;
- struct _byte_and_freq *node;
-
- // Initialize o2_cntxt
-
- o2_cntxt=ppmc_order2_hash_key(o1_byte,o2_byte);
-
-
- // First check if current order-2 context is empty
- if(order2_array[o2_cntxt].defined_bytes==0) //it's empty
- {
- byte=-1; //byte not coded, nothing done
- return;
- }
-
-
- // Get the total cump needed for decoding symbol
- ppmc_get_totf_order2(); //total cump needed for decoding
- symb_cump=range_decoder_decode(&rc_decoder,total_cump); //decode it
-
- // Now check if it's an escape code
- if(symb_cump>=order2_array[o2_cntxt].max_cump) //the defined code space for the escape code
- {
-
- // Update coding values
-
- ppmc_get_escape_prob_order2();
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Mark as escape code
-
- byte=-1;
-
- return; //an escape code
- }
- else
- {
- // Now we have to check what symbol it is
-
- current_cump=0; //cump of the current symbol
-
- node=order2_array[o2_cntxt].prob; //get pointer to linked lists
-
- while(1)
- {
- current_cump+=node->freq; //update cump
- if(symb_cump<current_cump)
- break; //symbol found, break search loop
-
- node=node->next; //next element
- //we have no need to check for the last symbol, we'll never read further
- //the end of the linked lists, before we'll found the last byte.
- }
-
-
- //read byte value and probability
-
- symb_prob=node->freq; //get the probability for updating the state
- byte=node->byte; //get byte
- o2_ll_node=node; //used for updating
-
-
- // Get the cump of byte
-
- symb_cump=current_cump-symb_prob;
-
- // Update coding state
-
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Update coded_in_order used for update exclusion
-
- coded_in_order=2;
-
- return;
- }
-
-}
-
-
-// This is the routine for updating while decoding. We have to search the byte
-// in the linked list, if it's present, update its count, otherwise we have
-// hitted the end of the linked list, and there we have to create a new node.
-//
-// Of course if the byte was matched in order-2 we'll have a pointer to it
-// in "o2_ll_node" so we don't need to read the linked list. (we already did
-// in decoding)
-//
-// Another case which we also have to specially deal with, this is the case
-// when the context has not been initalized yet.
-void ppmc_update_dec_order2(void)
-{
- struct _byte_and_freq *node;
-
-
- // Handle the case when the context is not initialized
- // This code is the same as the one for the encoding.
-
- if(order2_array[o2_cntxt].defined_bytes==0) //no byte defined yet
- {
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
- order2_array[o2_cntxt].defined_bytes=1;
- order2_array[o2_cntxt].max_cump=1;
- order2_array[o2_cntxt].prob=_bytes_pool;
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
-
- return; //nothing else to do
- }
-
-
- // Current context is initalized, proceed
-
- if(coded_in_order==2) //check if it was decoded under order-2
- {
-
- // We can be sure that the pointer "o2_ll_node" points to its entry, and
- // it has a non 0 probability (otherwise it couldn't be coded) so just
- // update its probability and max_cump
-
- o2_ll_node->freq++; //the probability of the byte
- order2_array[o2_cntxt].max_cump++; //the max_cump
-
- if(o2_ll_node->freq==255) //check for renormalization
- ppmc_renormalize_order2();
-
- }
- else
- {
-
- // An escape code was decoded under order-2, we have to read till the
- // end of the linked list so we can add a new node for this new byte.
-
- node=order2_array[o2_cntxt].prob; //get pointer to linked list
-
- while(1)
- {
- if(node->next==0) //check for the end of the linked list
- break;
- node=node->next; //next node
- }
-
-
- // We reached the end of the linked list, add a new node if possible,
- // we are using the same code of "ppmc_update_order2()" with the
- // difference that the pointer to the linked list is "node"
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate mem
-
- node->next=_bytes_pool; //put it in the next free entry
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- order2_array[o2_cntxt].max_cump++; //total cump
- order2_array[o2_cntxt].defined_bytes++; //total cump
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- return; //we are finished updating
-
- }
-
-}
-
-
-// This function returns the probability for the escape codes in the variables
-void ppmc_get_escape_prob_order2(void)
-{
- // To understand that remember that the escape allocated for the escape code
- // is above the current maximum cump and that it has a probability determined
- // by the scheme C.
-
- symb_prob=order2_array[o2_cntxt].defined_bytes;
- symb_cump=order2_array[o2_cntxt].max_cump;
-}
-
-
-
-// ORDER-3 functions
-//
-// The difference between order-3 and order-3 are just a few, instead of
-// keeping a table with the context structures, we keep a hash table with
-// pointers to linked lists with the context, so it's only a matter of
-// searching current context in the linked list corresponding to its hash
-// entry. This is done in "ppmc_get_totf_order3" because that's the first
-// routine that both encoding and decoding routines call.
-
-
-// Returns in the variable "total_cump" the current total cump of
-// order-3. Must be called while encoding or decoding before anything else
-// because it initializes the pointers to the context structure in
-// "o3_context" and o3_cntxt.
-//
-// If the hash entry is not initialized it returns "o3_context"=0
-// If the context is not present in the linked list of context, "o3_context"
-// will point to the last element in the linked list.
-// If the context is present "o3_context" will point to the context to use.
-// One can distinguish the last two by checking the context value of the
-// structure, if it's not the same, is the last element.
-//
-// The routine returns 0 if the hash entry is not initialized or if the
-// the context was not present. Otherwise it returns 1, meaning that we
-// have to code under this context.
-char ppmc_get_totf_order3(void)
-{
- struct context *cntxt_node;
-
-
- // First make the hash key for order-3
-
- o3_cntxt=ppmc_order3_hash_key(o1_byte,o2_byte,o3_byte);
- full_o3_cntxt=(o1_byte)+(o2_byte<<8)+(o3_byte<<16); //order-3
-
-
- // Now check the hash entry in the table
-
- if(order3_hasht[o3_cntxt]==0) //if 0, not initialized
- {
-
- o3_context=0; //no hash entry
-
- return 0; //hash entry not initialized
- }
-
-
- // Now read trough the linked list of context searching current one
-
- cntxt_node=order3_hasht[o3_cntxt];
-
- while(1)
- {
-
- if(cntxt_node->order4321==full_o3_cntxt) //compare context
- goto ppmc_gtf_cntxt_found;
-
- if(cntxt_node->next==0) //end of context's linked list
- break;
-
- cntxt_node=cntxt_node->next; //next element
-
- }
-
-
- // Once there the context was not found
- o3_context=cntxt_node; //pointer to last element in the linked list
-
- return 0; //it was not present
-
-
- // The context is found, so return pointer and cump
-
-ppmc_gtf_cntxt_found:
-
- o3_context=cntxt_node;
-
- // Total cump is current total cump plus the escape for the escape code
-
- total_cump=o3_context->defined_bytes+o3_context->max_cump;
-
- return 1; //context found
-
-}
-
-
-// Codes a byte under order-3 and returns 1.
-// Otherwise it returns a 0.
-//
-// In case the byte is coded under this context, coded_in_order=3.
-char ppmc_code_byte_order3(void)
-{
- unsigned long counter;
- struct _byte_and_freq *node;
-
-
- // Get current context (if present) and total cump.
-
- if(ppmc_get_totf_order3()==0)
- return 0;
-
-
- // See if the byte is present and compute its cump at the same time
-
- node=o3_context->prob; //pointer to first element in the linked list
-
- symb_cump=0; //the first symbol always has a 0 cump
-
-
- // Now search the byte in the linked list
-
- do{
- if(node->byte==byte)
- goto ppmc_o3_byte_found; //bad thing, I know, anyone has a better idea?
- symb_cump+=node->freq; //add the probability of this byte to the cump
- if(node->next==0)
- break;
- node=node->next; //next element in the linked list
- }while(1);
-
-
- // If we reach that point, the byte was not found in the linked list
- // so we don't need the cump, we have to output an escape code, whose
- // probabilities are know using the context structure in the table.
-
- // Byte was not present in the linked list, current node is the last one,
- // and that's the node needed for creating a new node, save it.
-
- o3_ll_node=node;
-
- // Now get the probability and cump of the escape code
-
- symb_cump=o3_context->max_cump;
- symb_prob=o3_context->defined_bytes;
-
- // Code the escape code
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 0;
-
-
- // That code is executed when the byte is found in the linked list
-
-ppmc_o3_byte_found:
-
-
- // Everything has been tested, now we can feel free to code the byte,
- // the symb_cump is already computed, now get its probability and code
- // the byte, also save pointer to this element in the linked lists for
- // updating.
-
- coded_in_order=3; //successfully coded under order-3
-
- o3_ll_node=node; //save it for updating
-
- symb_prob=node->freq; //get the probability of the byte
-
- // Code it.
-
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 1; //byte coded under order-3
-}
-
-
-// This functions update order-3 probabilities with current byte, also takes
-// care about updating variables, and renormalizing.
-//
-// "o3_ll_node" must point to the element to update or the last one,
-// based on the "coded_in_order" and checking the pointer of the element we
-// can decide what to do. Also "o3_context" must be initialized.
-//
-// This updating is only for encoding.
-void ppmc_update_order3(void)
-{
-
- // First thing first, check if the hash entry is initialized
-
- if(order3_hasht[o3_cntxt]==0) //no pointer to linked list defined yet
- {
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- order3_hasht[o3_cntxt]=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o3_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- return; //nothing else to do
- }
-
-
-
-
- // The byte was coded under order three, otherwise it was coded under a
- // lower order (never higher ones, remember that we are using update
- // exclusion) in this case we have to create a new node in the list.
-
- if(coded_in_order==3) //coded under order-3
- {
-
- // Update its count and variables of this context and check for renormalization
-
- o3_ll_node->freq++; //increment its frequency (rather probability)
-
- o3_context->max_cump++; //total cump
-
- if(o3_ll_node->freq==255) //do we have to renormalize?
- ppmc_renormalize_order3(); //renormalize
-
- }
- else
- {
-
- // Now we have two cases, under a given context (which we actually found)
- // we coded an escape coded, in that case just create a new node in the
- // linked list of bytes and probabilities. Otherwise we didn't find the
- // same node so we have to create it in the linked list for context.
- // And we can be sure that it at least has one element and that
- // "o3_context" points to the last element, so we can put the new element.
-
- if(o3_context->order4321==full_o3_cntxt) //chech if that's the last
- { //element or the a context found
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate mem
-
- o3_ll_node->next=_bytes_pool; //put it in the next free entry
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- o3_context->max_cump++; //total cump
- o3_context->defined_bytes++; //total cump
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
- }
- else
- {
-
- // We have to create a new context node
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- o3_context->next=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o3_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- }
-
- }
-
-}
-
-
-// This functions renormalizes the probabilities at order-3 updating context
-// variables.
-void ppmc_renormalize_order3(void)
-{
- unsigned long counter;
- struct _byte_and_freq *node;
-
-
- // Initialize variables. Defined bytes remain the same.
- o3_context->max_cump=0; //clear them
-
- node=o3_context->prob; //get pointer to lined lists
-
- // Divide all the probabilities by 2 and update context variables
- while(1)
- {
- node->freq>>=1; //divide by a factor of 2
-
- if(node->freq==0) //don't allow a probability to be 0
- node->freq=1;
-
- o3_context->max_cump+=node->freq; //sum to the total cump
-
- if(node->next==0) //last element
- break;
- node=node->next;
- }
-
-
-}
-
-
-// Decodes the symbol correspoding to the current order, it returns the byte
-// or in case of an escape code or empty table it returns -1.
-// It updates "coded_in_order".
-//
-// If we decode an escape code, we don't modify "o3_ll_node" and thus its
-// work of the updating routine to read till the end of the linked list
-// (for adding a new element) however if we decode a byte, we save on
-// "o3_ll_node" the pointer to its node. (so updating is faster)
-void ppmc_decode_order3(void)
-{
- unsigned long current_cump, counter;
- struct _byte_and_freq *node;
-
-
- // Get current context (if present) and total cump.
-
- if(ppmc_get_totf_order3()==0)
- {
- byte=-1;
- return;
- }
-
-
- // Decode current cump
-
- symb_cump=range_decoder_decode(&rc_decoder,total_cump); //decode it
-
- // Now check if it's an escape code
- if(symb_cump>=o3_context->max_cump) //the defined code space for the escape code
- {
-
- // Update coding values
-
- ppmc_get_escape_prob_order3();
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Mark as escape code
-
- byte=-1;
-
- return; //an escape code
- }
- else
- {
- // Now we have to check what symbol it is
-
- current_cump=0; //cump of the current symbol
-
- node=o3_context->prob; //get pointer to linked lists
-
- while(1)
- {
- current_cump+=node->freq; //update cump
- if(symb_cump<current_cump)
- break; //symbol found, break search loop
-
- node=node->next; //next element
- //we have no need to check for the last symbol, we'll never read further
- //the end of the linked lists, before we'll found the last byte.
- }
-
-
- //read byte value and probability
-
- symb_prob=node->freq; //get the probability for updating the state
- byte=node->byte; //get byte
- o3_ll_node=node; //used for updating
-
-
- // Get the cump of byte
-
- symb_cump=current_cump-symb_prob;
-
- // Update coding state
-
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Update coded_in_order used for update exclusion
-
- coded_in_order=3;
-
- return;
- }
-
-}
-
-
-// This is the routine for updating while decoding. The only difference with
-// the routine for coding is that when an escape code was coded, "o3_ll_node"
-// is not initialized so we have to read till the end of the linked list.
-// Fortunately "o3_context" will be initialized so we don't need to read its
-// linked list.
-void ppmc_update_dec_order3(void)
-{
- struct _byte_and_freq *node;
-
- // First thing first, check if the hash entry is initialized
-
- if(order3_hasht[o3_cntxt]==0) //no pointer to linked list defined yet
- {
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- order3_hasht[o3_cntxt]=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o3_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- return; //nothing else to do
- }
-
-
- // The byte was coded under order three, otherwise it was coded under a
- // lower order (never higher ones, remember that we are using update
- // exclusion) in this case we have to create a new node in the list.
-
- if(coded_in_order==3) //coded under order-3
- {
-
- // Update its count and variables of this context and check for renormalization
-
- o3_ll_node->freq++; //increment its frequency (rather probability)
-
- o3_context->max_cump++; //total cump
-
- if(o3_ll_node->freq==255) //do we have to renormalize?
- ppmc_renormalize_order3(); //renormalize
-
- }
- else
- {
-
- // Now we have two cases, under a given context (which we actually found)
- // we coded an escape coded, in that case just create a new node in the
- // linked list of bytes and probabilities. Otherwise we didn't find the
- // same node so we have to create it in the linked list for context.
- // And we can be sure that it at least has one element and that
- // "o3_context" points to the last element, so we can put the new element.
-
- if(o3_context->order4321==full_o3_cntxt) //chech if that's the last
- { //element or the a context found
-
- // Read till the end of the linked list
-
- node=o3_context->prob; //get pointer to linked list
-
- while(1)
- {
- if(node->next==0) //check for the end of the linked list
- break;
- node=node->next; //next node
- }
-
- // Now add element
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate mem
-
- node->next=_bytes_pool; //put it in the next free entry
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- o3_context->max_cump++; //total cump
- o3_context->defined_bytes++; //total cump
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
- }
- else
- {
-
- // We have to create a new context node
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- o3_context->next=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o3_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- }
-
- }
-
-}
-
-
-
-// This function returns the probability for the escape codes in the variables
-void ppmc_get_escape_prob_order3(void)
-{
- // To understand that remember that the escape allocated for the escape code
- // is above the current maximum cump and that it has a probability determined
- // by the scheme C.
-
- symb_prob=o3_context->defined_bytes;
- symb_cump=o3_context->max_cump;
-}
-
-
-
-// ORDER-4 functions
-//
-// The routines for order-4 are *equal* to those for order-3, there are a few
-// changes like different global variables, and different hash keys.
-//
-// If you want to go to higher orders, you'd use the same code and data
-// structures, with the difference of the context bytes (order4321)
-// stored in every context's linked list.
-
-
-// Returns in the variable "total_cump" the current total cump of
-// order-4. Must be called while encoding or decoding before anything else
-// because it initializes the pointers to the context structure in
-// "o4_context" and o4_cntxt.
-//
-// If the hash entry is not initialized it returns "o4_context"=0
-// If the context is not present in the linked list of context, "o4_context"
-// will point to the last element in the linked list.
-// If the context is present "o4_context" will point to the context to use.
-// One can distinguish the last two by checking the context value of the
-// structure, if it's not the same, is the last element.
-//
-// The routine returns 0 if the hash entry is not initialized or if the
-// the context was not present. Otherwise it returns 1, meaning that we
-// have to code under this context.
-char ppmc_get_totf_order4(void)
-{
- struct context *cntxt_node;
-
-
- // First make the hash key for order-4
-
- o4_cntxt=ppmc_order4_hash_key(o1_byte,o2_byte,o3_byte,o4_byte);
- full_o4_cntxt=(o1_byte)+(o2_byte<<8)+(o3_byte<<16)+(o4_byte<<24); //order-4
-
-
- // Now check the hash entry in the table
-
- if(order4_hasht[o4_cntxt]==0) //if 0, not initialized
- {
-
- o4_context=0; //no hash entry
-
- return 0; //hash entry not initialized
- }
-
-
- // Now read trough the linked list of context searching current one
-
- cntxt_node=order4_hasht[o4_cntxt];
-
- while(1)
- {
-
- if(cntxt_node->order4321==full_o4_cntxt) //compare context
- goto ppmc_gtfo4_cntxt_found;
-
- if(cntxt_node->next==0) //end of context's linked list
- break;
-
- cntxt_node=cntxt_node->next; //next element
-
- }
-
-
- // Once there the context was not found
- o4_context=cntxt_node; //pointer to last element in the linked list
-
- return 0; //it was not present
-
-
- // The context is found, so return pointer and cump
-
-ppmc_gtfo4_cntxt_found:
-
- o4_context=cntxt_node;
-
- // Total cump is current total cump plus the escape for the escape code
-
- total_cump=o4_context->defined_bytes+o4_context->max_cump;
-
- return 1; //context found
-
-}
-
-
-// Codes a byte under order-4 and returns 1.
-// Otherwise it returns a 0.
-//
-// In case the byte is coded under this context, coded_in_order=4.
-char ppmc_code_byte_order4(void)
-{
- unsigned long counter;
- struct _byte_and_freq *node;
-
-
- // Get current context (if present) and total cump.
-
- if(ppmc_get_totf_order4()==0)
- return 0;
-
-
- // See if the byte is present and compute its cump at the same time
-
- node=o4_context->prob; //pointer to first element in the linked list
-
- symb_cump=0; //the first symbol always has a 0 cump
-
-
- // Now search the byte in the linked list
-
- do{
- if(node->byte==byte)
- goto ppmc_o4_byte_found; //bad thing, I know, anyone has a better idea?
- symb_cump+=node->freq; //add the probability of this byte to the cump
- if(node->next==0)
- break;
- node=node->next; //next element in the linked list
- }while(1);
-
-
- // If we reach that point, the byte was not found in the linked list
- // so we don't need the cump, we have to output an escape code, whose
- // probabilities are know using the context structure in the table.
-
- // Byte was not present in the linked list, current node is the last one,
- // and that's the node needed for creating a new node, save it.
-
- o4_ll_node=node;
-
- // Now get the probability and cump of the escape code
-
- symb_cump=o4_context->max_cump;
- symb_prob=o4_context->defined_bytes;
-
- // Code the escape code
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 0;
-
-
- // That code is executed when the byte is found in the linked list
-
-ppmc_o4_byte_found:
-
-
- // Everything has been tested, now we can feel free to code the byte,
- // the symb_cump is already computed, now get its probability and code
- // the byte, also save pointer to this element in the linked lists for
- // updating.
-
- coded_in_order=4; //successfully coded under order-4
-
- o4_ll_node=node; //save it for updating
-
- symb_prob=node->freq; //get the probability of the byte
-
- // Code it.
-
- range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
-
- return 1; //byte coded under order-4
-}
-
-
-// This functions update order-4 probabilities with current byte, also takes
-// care about updating variables, and renormalizing.
-//
-// "o4_ll_node" must point to the element to update or the last one,
-// based on the "coded_in_order" and checking the pointer of the element we
-// can decide what to do. Also "o4_context" must be initialized.
-//
-// This updating is only for encoding.
-void ppmc_update_order4(void)
-{
-
- // First thing first, check if the hash entry is initialized
-
- if(order4_hasht[o4_cntxt]==0) //no pointer to linked list defined yet
- {
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- order4_hasht[o4_cntxt]=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o4_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- return; //nothing else to do
- }
-
-
-
-
- // The byte was coded under order three, otherwise it was coded under a
- // lower order (never higher ones, remember that we are using update
- // exclusion) in this case we have to create a new node in the list.
-
- if(coded_in_order==4) //coded under order-4
- {
-
- // Update its count and variables of this context and check for renormalization
-
- o4_ll_node->freq++; //increment its frequency (rather probability)
-
- o4_context->max_cump++; //total cump
-
- if(o4_ll_node->freq==255) //do we have to renormalize?
- ppmc_renormalize_order4(); //renormalize
-
- }
- else
- {
-
- // Now we have two cases, under a given context (which we actually found)
- // we coded an escape coded, in that case just create a new node in the
- // linked list of bytes and probabilities. Otherwise we didn't find the
- // same node so we have to create it in the linked list for context.
- // And we can be sure that it at least has one element and that
- // "o4_context" points to the last element, so we can put the new element.
-
- if(o4_context->order4321==full_o4_cntxt) //chech if that's the last
- { //element or the a context found
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate mem
-
- o4_ll_node->next=_bytes_pool; //put it in the next free entry
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- o4_context->max_cump++; //total cump
- o4_context->defined_bytes++; //total cump
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
- }
- else
- {
-
- // We have to create a new context node
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- o4_context->next=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o4_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- }
-
- }
-
-}
-
-
-// This functions renormalizes the probabilities at order-4 updating context
-// variables.
-void ppmc_renormalize_order4(void)
-{
- unsigned long counter;
- struct _byte_and_freq *node;
-
-
- // Initialize variables. Defined bytes remain the same.
- o4_context->max_cump=0; //clear them
-
- node=o4_context->prob; //get pointer to lined lists
-
- // Divide all the probabilities by 2 and update context variables
- while(1)
- {
- node->freq>>=1; //divide by a factor of 2
-
- if(node->freq==0) //don't allow a probability to be 0
- node->freq=1;
-
- o4_context->max_cump+=node->freq; //sum to the total cump
-
- if(node->next==0) //last element
- break;
- node=node->next;
- }
-
-
-}
-
-
-// Decodes the symbol correspoding to the current order, it returns the byte
-// or in case of an escape code or empty table it returns -1.
-// It updates "coded_in_order".
-//
-// If we decode an escape code, we don't modify "o4_ll_node" and thus its
-// work of the updating routine to read till the end of the linked list
-// (for adding a new element) however if we decode a byte, we save on
-// "o4_ll_node" the pointer to its node. (so updating is faster)
-void ppmc_decode_order4(void)
-{
- unsigned long current_cump, counter;
- struct _byte_and_freq *node;
-
-
- // Get current context (if present) and total cump.
-
- if(ppmc_get_totf_order4()==0)
- {
- byte=-1;
- return;
- }
-
-
- // Decode current cump
-
- symb_cump=range_decoder_decode(&rc_decoder,total_cump); //decode it
-
- // Now check if it's an escape code
- if(symb_cump>=o4_context->max_cump) //the defined code space for the escape code
- {
-
- // Update coding values
-
- ppmc_get_escape_prob_order4();
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Mark as escape code
-
- byte=-1;
-
- return; //an escape code
- }
- else
- {
- // Now we have to check what symbol it is
-
- current_cump=0; //cump of the current symbol
-
- node=o4_context->prob; //get pointer to linked lists
-
- while(1)
- {
- current_cump+=node->freq; //update cump
- if(symb_cump<current_cump)
- break; //symbol found, break search loop
-
- node=node->next; //next element
- //we have no need to check for the last symbol, we'll never read further
- //the end of the linked lists, before we'll found the last byte.
- }
-
-
- //read byte value and probability
-
- symb_prob=node->freq; //get the probability for updating the state
- byte=node->byte; //get byte
- o4_ll_node=node; //used for updating
-
-
- // Get the cump of byte
-
- symb_cump=current_cump-symb_prob;
-
- // Update coding state
-
- range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);
-
- // Update coded_in_order used for update exclusion
-
- coded_in_order=4;
-
- return;
- }
-
-}
-
-
-// This is the routine for updating while decoding. The only difference with
-// the routine for coding is that when an escape code was coded, "o4_ll_node"
-// is not initialized so we have to read till the end of the linked list.
-// Fortunately "o4_context" will be initialized so we don't need to read its
-// linked list.
-void ppmc_update_dec_order4(void)
-{
- struct _byte_and_freq *node;
-
- // First thing first, check if the hash entry is initialized
-
- if(order4_hasht[o4_cntxt]==0) //no pointer to linked list defined yet
- {
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- order4_hasht[o4_cntxt]=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o4_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- return; //nothing else to do
- }
-
-
- // The byte was coded under order four, otherwise it was coded under a
- // lower order (never higher ones, remember that we are using update
- // exclusion) in this case we have to create a new node in the list.
-
- if(coded_in_order==4) //coded under order-4
- {
-
- // Update its count and variables of this context and check for renormalization
-
- o4_ll_node->freq++; //increment its frequency (rather probability)
-
- o4_context->max_cump++; //total cump
-
- if(o4_ll_node->freq==255) //do we have to renormalize?
- ppmc_renormalize_order4(); //renormalize
-
- }
- else
- {
-
- // Now we have two cases, under a given context (which we actually found)
- // we coded an escape coded, in that case just create a new node in the
- // linked list of bytes and probabilities. Otherwise we didn't find the
- // same node so we have to create it in the linked list for context.
- // And we can be sure that it at least has one element and that
- // "o4_context" points to the last element, so we can put the new element.
-
- if(o4_context->order4321==full_o4_cntxt) //chech if that's the last
- { //element or the a context found
-
- // Read till the end of the linked list
-
- node=o4_context->prob; //get pointer to linked list
-
- while(1)
- {
- if(node->next==0) //check for the end of the linked list
- break;
- node=node->next; //next node
- }
-
- // Now add element
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate mem
-
- node->next=_bytes_pool; //put it in the next free entry
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- o4_context->max_cump++; //total cump
- o4_context->defined_bytes++; //total cump
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
- }
- else
- {
-
- // We have to create a new context node
-
- if(ppmc_out_of_memory==1)
- return; //exit this function, we can't allocate memory
-
-
- // First create the context
-
- o4_context->next=_context_pool;
-
- _context_pool->next=0; //this is the last element
- _context_pool->order4321=full_o4_cntxt; //put context
- _context_pool->prob=_bytes_pool; //pointer to linked list
- _context_pool->max_cump=1;
- _context_pool->defined_bytes=1;
-
-
- // Do update of linked list variables and memory use of contexts
-
- ++_context_pool; //next time use next entry (this is a pointer)
-
- if(_context_pool==_context_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_context_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_context_pool=(struct context *)malloc
- (sizeof(struct context)*_context_pool_elements_inc))==NULL)
- {
- printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _context_pool_array[_context_pool_index]=_context_pool;
-
- _context_pool_max=_context_pool+_context_pool_elements_inc;
-
- _context_pool_index++;
-
- }
-
- // Now care about the first (and last) linked list element
-
- _bytes_pool->byte=byte; //initialize byte to current one
- _bytes_pool->freq=1; //it appeared once
- _bytes_pool->next=0; //now this is last element in ll
-
- // Do update of linked list variables and memory use
-
- ++_bytes_pool; //next time use next entry (this is a pointer)
-
- if(_bytes_pool==_bytes_pool_max) //maximum reached
- {
-
- // First check to see that we still have entries in the array
-
- if(_bytes_pool_index==_mempool_max_index)
- {
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- // Allocate memory for new buffer
-
- if((_bytes_pool=(struct _byte_and_freq *)malloc
- (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
- {
- printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
- ppmc_out_of_memory=1; //flush
- return;
- }
-
- _bytes_pool_array[_bytes_pool_index]=_bytes_pool;
-
- _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;
-
- _bytes_pool_index++;
-
- }
-
- }
-
- }
-
-}
-
-
-
-// This function returns the probability for the escape codes in the variables
-void ppmc_get_escape_prob_order4(void)
-{
- // To understand that remember that the escape allocated for the escape code
- // is above the current maximum cump and that it has a probability determined
- // by the scheme C.
-
- symb_prob=o4_context->defined_bytes;
- symb_cump=o4_context->max_cump;
-}
-
projects / z.facultad / 75.06 / jacu.git / commitdiff