+/*
+ 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