Se agrega documentación y una implementación de prueba de PPMC.

[z.facultad/75.06/jacu.git] / src / ppmc / exclusion / ppmc.c

/*
 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" (exclusion)
 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.

 Using exclusion. It's up to the main encoding routine to clear this table
 for every new byte.
*/


#include <stdio.h>
#include <stdlib.h>
#include "range.h"
#include "ppmcdata.h"



// 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)
{
 unsigned long counter;


 // Clear exclusion table
 for(counter=0;counter!=256;++counter)
   excluded[counter]=0;


 // 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.
//
// For order-(-1) we don't use exclusion.


// Gets the probability for a given symbol in the order-(-1) (ordern1)
void ppmc_get_prob_ordern1(void)
{
 symb_cump=byte;    //its value
 symb_prob=1;      //flat probability
 total_cump=257;   //total cump
}


// Returns in the variable "total_cump" the current total cump of
// order-(-1)
void ppmc_get_totf_ordern1(void)
{
 total_cump=257;        //this is fixed
}


// 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.
//
// Order-0 uses exclusions. Exclusion values are always prepared in "get_totf"
// so there's no need to get them again. However order-0 doesn't have to
// update exclude table, because order-(-1) will not use it


// Returns in the variable "total_cump" the current total cump of
// order-0. We have to read the whole array because we can't
// guarante that all the bytes are used.
void ppmc_get_totf_order0(void)
{
 unsigned long temp_cump,       //temp value for the cump
               counter;

 exc_defined_bytes=0;
 exc_max_cump=0;

 // Read the number of defined bytes by reading the count of every byte
 // and if it's present in the exclusion table.
 for(counter=0;counter!=256;++counter)
   {
   if(excluded[counter]==0) //only if it's not excluded
     if(order0_array[counter]!=0)  //if it has a nonzero count, then it's present
       {
       ++exc_defined_bytes;
       exc_max_cump+=order0_array[counter];
       }
   }

 // Total cump is current total cump plus the probability for the escape code
 exc_total_cump=exc_max_cump+exc_defined_bytes;
}


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

 // It's possible that due to excluding, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   return 0;

 // 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=exc_max_cump;   //obviously its cump is current max_cump
                                //without escape code's space

   symb_prob=exc_defined_bytes;  //the number of defined bytes

   total_cump=exc_total_cump;

   // 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)
     {
     if(excluded[counter]==0)
       symb_cump+=order0_array[counter];  //sum probabilities before our symbol
     }

   total_cump=exc_total_cump;

   // 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)
   {
   if(order0_array[counter]!=0)
     {
     order0_array[counter]>>=1;   //divide by a factor of 2
     if(order0_array[counter]==0)
       order0_array[counter]=1;
     }

   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

 // It's possible that due to excluding, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   {
   byte=-1;
   return;
   }

 symb_cump=range_decoder_decode(&rc_decoder,exc_total_cump);        //decode it

 // Now check if it's an escape code
 if(symb_cump>=exc_max_cump)     //the defined code space for the escape code
   {

   // Update coding values

   ppmc_get_escape_prob_order0();
   range_decoder_update(&rc_decoder,exc_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
     if(excluded[counter]==0)
       current_cump+=order0_array[counter];       //update cump
     }

   counter--;           //-1 (see ac_ppmc.html)

   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,exc_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=exc_defined_bytes;
 symb_cump=exc_max_cump;
 total_cump=exc_defined_bytes+exc_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.
//
// Order-1 uses exclusions. Exclusion values are always prepared in "get_totf"
// so there's no need to get them again. It does update the exclude table.


// 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)
{
 unsigned long temp_cump,       //temp value for the cump
               counter;

 exc_defined_bytes=0;
 exc_max_cump=0;

 // Read the number of defined bytes by reading the count of every byte
 // and if it's present in the exclusion table.
 for(counter=0;counter!=256;++counter)
   {
   if(excluded[counter]==0) //only if it's not excluded
     if(order1_array[o1_byte][counter]!=0)  //if it has a nonzero count, then it's present
       {
       ++exc_defined_bytes;
       exc_max_cump+=order1_array[o1_byte][counter];
       }
   }

 // Total cump is current total cump plus the probability for the escape code
 exc_total_cump=exc_max_cump+exc_defined_bytes;
}


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

 // It's possible that due to excluding, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   return 0;


 // 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=exc_max_cump;

   symb_prob=exc_defined_bytes;

   // Code the escape code
   range_coder_encode(&rc_coder,exc_total_cump,symb_cump,symb_prob);

   // Now update "exclude" table
   for(counter=0;counter!=256;++counter)
     if(order1_array[o1_byte][counter]!=0)
       excluded[counter]=1;               //occurred but was not code, now exclude

   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)
     {
     if(excluded[counter]==0)
       symb_cump+=order1_array[o1_byte][counter];  //sum probabilities before our symbol
     }

   // Code the symbol
   range_coder_encode(&rc_coder,exc_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)
   {
   if(order1_array[o1_byte][counter]!=0)
     {
     order1_array[o1_byte][counter]>>=1;   //divide by a factor of 2
     if(order1_array[o1_byte][counter]==0)
       order1_array[o1_byte][counter]=1;  //don't let it have a 0 count
     }

   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

 // It's possible that due to excluding, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   {
   byte=-1;
   return;
   }

 symb_cump=range_decoder_decode(&rc_decoder,exc_total_cump);        //decode it

 // Now check if it's an escape code
 if(symb_cump>=exc_max_cump)     //the defined code space for the escape code
   {

   // Update coding values

   ppmc_get_escape_prob_order1();
   range_decoder_update(&rc_decoder,exc_total_cump,symb_cump,symb_prob);


   // Now update "exclude" table
   for(counter=0;counter!=256;++counter)
     if(order1_array[o1_byte][counter]!=0)
       excluded[counter]=1;               //occurred but was not code, now exclude

   // Mark as escape code (in fact nothing coded)

   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
     if(excluded[counter]==0)
       current_cump+=order1_array[o1_byte][counter];       //update cump
     }

   counter--;           //-1 (see ppmc.txt, 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,exc_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=exc_defined_bytes;
 symb_cump=exc_max_cump;
 total_cump=exc_defined_bytes+exc_max_cump;
}



// 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.
//
// Order-2 uses exclusions. Exclusion values are always prepared in "get_totf"
// so there's no need to get them again. It does update the exclude table.


// 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.
//
// Here we have to compute both "exc_defined_bytes" and "exc_max_cump"
void ppmc_get_totf_order2(void)
{
 struct _byte_and_freq *node;


 // Read the whole linked list for making the values
 node=order2_array[o2_cntxt].prob;
 exc_max_cump=0;
 exc_defined_bytes=0;

 do{
   if(excluded[node->byte]==0)
     {
     exc_defined_bytes++;
     exc_max_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);


 // Total cump is current total cump plus the probability for the escape code
 exc_total_cump=exc_max_cump+exc_defined_bytes;

}


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


 // It's possible that due to exclusion, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   return 0;


 // 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?
   if(excluded[node->byte]==0)
     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=exc_max_cump;
 symb_prob=exc_defined_bytes;

 // Code the escape code
 range_coder_encode(&rc_coder,exc_total_cump,symb_cump,symb_prob);

 // Then, update "excluded" table

 node=order2_array[o2_cntxt].prob;

 do{
   excluded[node->byte]=1;
   if(node->next==0)
     break;
   node=node->next;             //next element in the linked list
   }while(1);

 return 0;      //now exit


 // 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,exc_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)
{
 struct _byte_and_freq *node;


 // 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.
   //
   // However due to the use of exclusion, we have to ensure that "o2_ll_node"
   // points to the last element in the linked lists of this context

   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
     }

   o2_ll_node=node;


   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


 // It's possible that due to exclusion, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   {
   byte=-1;
   return;   //byte not coded, nothing done
   }


 symb_cump=range_decoder_decode(&rc_decoder,exc_total_cump);        //decode it

 // Now check if it's an escape code
 if(symb_cump>=exc_max_cump)     //the defined code space for the escape code
   {

   // Update coding values

   ppmc_get_escape_prob_order2();
   range_decoder_update(&rc_decoder,exc_total_cump,symb_cump,symb_prob);

   // Mark as escape code

   byte=-1;

   // Then, update "excluded" table

   node=order2_array[o2_cntxt].prob;

   do{
     excluded[node->byte]=1;
     if(node->next==0)
       break;
     node=node->next;             //next element in the linked list
     }while(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)
     {
     if(excluded[node->byte]==0)        //only if it's not excluded
       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,exc_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=exc_defined_bytes;
 symb_cump=exc_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;
 struct _byte_and_freq *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;

 // Read the whole linked list for making the values
 node=o3_context->prob;
 exc_max_cump=0;
 exc_defined_bytes=0;

 do{
   if(excluded[node->byte]==0)
     {
     exc_defined_bytes++;
     exc_max_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);


 // Total cump is current total cump plus the probability for the escape code
 exc_total_cump=exc_max_cump+exc_defined_bytes;


 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;


 // It's possible that due to exclusion, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==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?
   if(excluded[node->byte]==0)
     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=exc_max_cump;
 symb_prob=exc_defined_bytes;

 // Code the escape code
 range_coder_encode(&rc_coder,exc_total_cump,symb_cump,symb_prob);

 // Then, update "excluded" table

 node=o3_context->prob;

 do{
   excluded[node->byte]=1;
   if(node->next==0)
     break;
   node=node->next;             //next element in the linked list
   }while(1);

 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,exc_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)
{
 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 a context found

     // However due to the use of exclusion, we have to ensure that "o3_ll_node"
     // points to the last element in the linked lists of this context

     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
       }

     o3_ll_node=node;

     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
     {

     // Ensure that we are at the end of the linked list of contexts
     o3_context=order3_hasht[o3_cntxt];

     do{
       if(o3_context->next==0)
         break;
       o3_context=o3_context->next;
       }while(1);

     // 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;
   }

 // It's possible that due to exclusion, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   {
   byte=-1;
   return;
   }



 // Decode current cump

 symb_cump=range_decoder_decode(&rc_decoder,exc_total_cump);        //decode it

 // Now check if it's an escape code
 if(symb_cump>=exc_max_cump)     //the defined code space for the escape code
   {

   // Update coding values

   ppmc_get_escape_prob_order3();
   range_decoder_update(&rc_decoder,exc_total_cump,symb_cump,symb_prob);

   // Mark as escape code

   byte=-1;

   // Then, update "excluded" table

   node=o3_context->prob;

   do{
     excluded[node->byte]=1;
     if(node->next==0)
       break;
     node=node->next;             //next element in the linked list
     }while(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)
     {
     if(excluded[node->byte]==0)
       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,exc_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.");
         exit(1);
         }

       _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=exc_defined_bytes;
 symb_cump=exc_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;
 struct _byte_and_freq *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;

 // Read the whole linked list for making the values
 node=o4_context->prob;
 exc_max_cump=0;
 exc_defined_bytes=0;

 do{
   if(excluded[node->byte]==0)
     {
     exc_defined_bytes++;
     exc_max_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);


 // Total cump is current total cump plus the probability for the escape code
 exc_total_cump=exc_max_cump+exc_defined_bytes;


 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;


 // It's possible that due to exclusion, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==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?
   if(excluded[node->byte]==0)
     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=exc_max_cump;
 symb_prob=exc_defined_bytes;

 // Code the escape code
 range_coder_encode(&rc_coder,exc_total_cump,symb_cump,symb_prob);

 // Then, update "excluded" table

 node=o4_context->prob;

 do{
   excluded[node->byte]=1;
   if(node->next==0)
     break;
   node=node->next;             //next element in the linked list
   }while(1);

 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,exc_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.");
       exit(1);
       }

     _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.");
         exit(1);
         }

       _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;
   }


 // It's possible that due to exclusion, there's no byte left, in that case
 // return.
 if(exc_defined_bytes==0)
   {
   byte=-1;
   return;
   }


 // Decode current cump

 symb_cump=range_decoder_decode(&rc_decoder,exc_total_cump);        //decode it

 // Now check if it's an escape code
 if(symb_cump>=exc_max_cump)     //the defined code space for the escape code
   {

   // Update coding values

   ppmc_get_escape_prob_order4();
   range_decoder_update(&rc_decoder,exc_total_cump,symb_cump,symb_prob);

   // Mark as escape code

   byte=-1;

   // Then, update "excluded" table

   node=o4_context->prob;

   do{
     excluded[node->byte]=1;
     if(node->next==0)
       break;
     node=node->next;             //next element in the linked list
     }while(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)
     {
     if(excluded[node->byte]==0)
       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,exc_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.");
       exit(1);
       }

     _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.");
         exit(1);
         }

       _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=exc_defined_bytes;
 symb_cump=exc_max_cump;
}