Agrego makefile y algunas .h para sacar warnings.

[z.facultad/75.06/jacu.git] / src / ppmc / 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"
 Email: arturo@arturocampos.com
 Web: http://www.arturocampos.com

 Part of the ppmc encoder and decoder.

 This module contains the whole ppmc encoder. It uses hash tables for
 managing most of the orders. And a maximum order of 4. It codes bytes.
 Order-1-0-(-1) are all handled in tables. Order-2 has a table with
 direct hashing with pointers to the linked lists. Order-4 and order-3
 both have hash tables with pointers to contexts in a linked lists which
 finally have a pointer to the start of the linked list with the
 probability distribution. Update exclusion is used, but exclusion is not.

 Please, note that if the machine where the decoder is run doesn't has as
 much memory as the computer where the encoder was ran, the decoder will
 not be able to properly decode the file, because it will not be able to
 keep track of new statistics, in this case it will just exit.

 For applications where the loss of data is not admisible, I suggest you to
 limit both encoder and decoder's memory requeriments to a given minimum
 which both machines have.
*/


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



// Ruotines used by ppmc. Not including the range coder.
//
// They are for initializing of both encoder and decoder, and unless there
// are two version, both encoder and decoder use the same routines. Like
// "ppmc_initialize_contexts".


// This one allocs the memory needed by ppmc, and adjust some pointers used
// for allocating elements in the linked lists. The mempool arrays must be
// initialized now.
void ppmc_alloc_memory(void)
{
        unsigned long counter;


        // Init mempool buffers

        for(counter=0;counter!=_mempool_max_index;++counter)
        {
                _bytes_pool_array[counter]=0;
                _context_pool_array[counter]=0;
        }

        _bytes_pool_index=1;   //first entry will be used now
        _context_pool_index=1;


        // Allocate memory for ppmc structures and adjust some variables
        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements))==NULL)
        {
                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                ppmc_out_of_memory=1;    //flush
                return;
        }

        if((_context_pool=(struct context *)malloc
                                (sizeof(struct context)*_context_pool_elements))==NULL)
        {
                printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                ppmc_out_of_memory=1;    //flush
                return;
        }


        //save pointers in the array for freeing
        _bytes_pool_array[0]=_bytes_pool;
        _context_pool_array[0]=_context_pool;


        //adjust variables
        _bytes_pool_max=_bytes_pool+_bytes_pool_elements;
        _context_pool_max=_context_pool+_context_pool_elements;

        ppmc_out_of_memory=0;  //we still have memory
}


// This routine initializes all the contexts, and all the tables including
// those who care about the number of bytes defined in a context.
void ppmc_initialize_contexts(void)
{
        unsigned long counter, counter2;


        // Order-0
        for(counter=0;counter!=256;++counter) //clear table
                order0_array[counter]=0;

        order0_defined_bytes=0;       //adjust variables
        order0_max_cump=0;


        // Order-1
        for(counter=0;counter!=256;++counter)  //erase every table of every context
                for(counter2=0;counter2!=256;++counter2)
                        order1_array[counter][counter2]=0;

        for(counter=0;counter!=256;++counter) //adjust variables
        {
                order1_defined_bytes_array[counter]=0;
                order1_max_cump_array[counter]=0;
        }


        // Order-2
        for(counter=0;counter!=65536;++counter)
        {
                //order2_array[counter].prob=0;     //clear pointer to bytes and frequencies
                //order2_array[counter].max_cump=0;
                order2_array[counter].defined_bytes=0;
        }


        // Order-4-3
        for(counter=0;counter!=65536;++counter) //order-4-3
        {
                order4_hasht[counter]=0;
                order3_hasht[counter]=0;
        }
}


// This routine initializes the encode model by outputting as many bytes as
// needed to prepare the models. This should be called before the main loop
// and after the memory has been allocated and tables initialized.
//
// It does not need uses the range coder. It output the first 1 bytes.
void ppmc_encoder_initialize(void)
{

        // Initialize order-0 and prepare different bytes for orders
        fputc((byte=fgetc(file_input)),file_output);
        o4_byte=byte;    //order-4

        fputc((byte=fgetc(file_input)),file_output);
        o3_byte=byte;    //order-3

        fputc((byte=fgetc(file_input)),file_output);
        o2_byte=byte;    //order-2
        ppmc_update_order0();

        fputc((byte=fgetc(file_input)),file_output);
        o1_byte=byte;

}


// This routine initializes the decoder model, should be called to do the same
// changes as "ppmc_encoder_initialize()" did.
void ppmc_decoder_initialize(void)
{

        // Initialize order-0 and context bytes
        byte=fgetc(file_input);
        o4_byte=byte;    //order-4
        fputc(byte,file_output);

        byte=fgetc(file_input);
        o3_byte=byte;    //order-3
        fputc(byte,file_output);

        byte=fgetc(file_input);
        o2_byte=byte;    //order-2

        fputc(byte,file_output);   //output first byte
        ppmc_update_order0();

        byte=fgetc(file_input);
        o1_byte=byte;    //order-1
        fputc(byte,file_output);
}


// Once coding or decoding is finished you have to call this routine.
// It must be called when done.
void ppmc_free_memory(void)
{
        unsigned long counter;

        // Free the memory buffers

        for(counter=0;counter!=_mempool_max_index;++counter)
        {
                if(_bytes_pool_array[counter]!=0)
                        free(_bytes_pool_array[counter]);

                if(_context_pool_array[counter]!=0)
                        free(_context_pool_array[counter]);
        }

}


// This routine flushes the memory and restarts all the tables of
// probabilities, current order bytes are not modified, this function
// is called when we ran out of memory. We have to output the code
// number 256 which means memory flushing, for doing this we have to go
// to order-(-1) so we have to output an escape code in all the orders
// till we reach order-(-1) where we can code it. Then we free all the
// memory, alloc it again, and reinitialize all the orders.
//
// However we may find the case when the current order is not initialized,
// in this case we don't need to output an escape code.
void ppmc_flush_mem_enc(void)
{

        // Code an escape code in order-4
        if(ppmc_get_totf_order4()!=0)  //if 0 no need of escape code
        {

                ppmc_get_escape_prob_order4();       //get prob and cump
                range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);

        }


        // Code an escape code in order-3
        if(ppmc_get_totf_order3()!=0)  //if 0 no need of escape code
        {

                ppmc_get_escape_prob_order3();       //get prob and cump
                range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);

        }


        // Code an escape code in order-2

        o2_cntxt=ppmc_order2_hash_key(o1_byte,o2_byte);

        // First check if current order-2 context is empty
        if(order2_array[o2_cntxt].defined_bytes!=0)  //it's not empty
        {
                ppmc_get_totf_order2();
                ppmc_get_escape_prob_order2();
                range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
        }


        // Code an escape code in order-1

        // First check if current order-1 table is empty
        if(order1_defined_bytes_array[o1_byte]!=0)  //it's not empty
        {
                ppmc_get_totf_order1();
                ppmc_get_escape_prob_order1();
                range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);
        }


        // Code an escape code in order-0. Order-0 always has at least one symbol

        ppmc_get_totf_order0();
        ppmc_get_escape_prob_order0();
        range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);



        // Now we can code the code 256

        symb_prob=1;
        symb_cump=256;
        total_cump=257;
        range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);


        // Now that decoder knows the flushing, free memory and reinit

        ppmc_free_memory();
        ppmc_alloc_memory();
        ppmc_initialize_contexts();


        // Be sure that order-0 has at least one probability

        order0_array[o1_byte]++;
        order0_max_cump++;
        order0_defined_bytes++;

}


// When the decoder gets the symbol of flushing, most of the job is done
// because we already got all the escape codes, so we only have to reinit.
void ppmc_flush_mem_dec(void)
{

        // Free memory and reinit

        ppmc_free_memory();
        ppmc_alloc_memory();
        ppmc_initialize_contexts();


        // Be sure that order-0 has at least one probability

        order0_array[o1_byte]++;
        order0_max_cump++;
        order0_defined_bytes++;


}



// ORDER-(-1) functions, also called ordern1 (Negative1) in functions
//
// Because order-(-1) does not need to update its probability tables, it
// has no tables, and relies on the fact that the cump of byte is its own
// value, and the probability is fixed, 1, and the total cump is 257.
//
// The alphabet has the following distribution: 0-255 the bytes. 256 is
// an special symbol which means that we have flushed the encoder tables,
// and thus the encoder must flush its tables too.
//
// The rest of the tables only have 256 symbols, because we have no need
// of assign a symbol to the flush code (which already is the order-(-1)
// table) nor to the escape code.


// Gets the probability for a given symbol in the order-(-1) (ordern1)
void ppmc_get_prob_ordern1(void)
{
        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.


// Returns in the variable "total_cump" the current total cump of
// order-0
void ppmc_get_totf_order0(void)
{
        // Total cump is current total cump plus the escape for the escape code
        total_cump=order0_defined_bytes+order0_max_cump;
}


// Codes a byte under order-0 and returns 1, otherwise it returns a 0 and
// has coded an escape code. In this case further coding is needed.
//
// Returns: 1 in case a byte was coded. 0 in case of escape code.
char ppmc_code_byte_order0(void)
{
        unsigned long counter;

        ppmc_get_totf_order0();      //get total cump

        // See if the byte is present
        if(order0_array[byte]==0)      //a probability of 0
        {

                // Because it was not present, output an escape code, prepare variables

                symb_cump=order0_max_cump;   //obviously its cump is current max_cump
                //without escape code's space

                symb_prob=order0_defined_bytes;  //the number of defined bytes

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

                return 0;    //byte not coded
        }
        else
        {

                coded_in_order=0;

                // The symbol is present, code it under order-0

                symb_prob=order0_array[byte];        //get probability directly

                // Make cump for current symbol

                symb_cump=0;         //for first symbol is 0
                for(counter=0; counter!=byte ; ++counter)
                        symb_cump+=order0_array[counter];  //sum probabilities before our symbol

                // Code the symbol
                range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);

                return 1;    //symbol coded under order-0
        }
}


// This functions update order-0 probabilities with current byte, also takes
// care about updating variables, and renormalizing.
void ppmc_update_order0(void)
{
        if(order0_array[byte]==0)
        {
                // It had a zero probability
                order0_array[byte]++;       //increment symbol probability
                ++order0_defined_bytes;     //new byte defined
                ++order0_max_cump;          //total cump
                return;
        }
        else
        {
                // It had a non-zero probability

                // Increment its probability
                order0_array[byte]++;      //increment symbol probability
                ++order0_max_cump;         //total cump

                // Check to see if its the maximum in this case renormalize
                if(order0_array[byte]==255)
                        ppmc_renormalize_order0();

                return;
        }
}


// This functions renormalizes the probabilities at order-0 updating variables
void ppmc_renormalize_order0(void)
{
        unsigned long counter;

        // Initialize variables
        order0_defined_bytes=0;        //clear them
        order0_max_cump=0;

        // Loop over all probabilities, divide them by a factor of 2 and update variables
        for(counter=0 ; counter!=256 ; ++counter)
        {
                order0_array[counter]>>=1;   //divide by a factor of 2

                if(order0_array[counter]!=0) //see if it has a non zero probability
                        order0_defined_bytes++;

                order0_max_cump+=order0_array[counter];      //sum to the total cump
        }
}


// Decodes the symbol correspoding to the current order, it returns the byte
// or in case of a escape code it returns -1
void ppmc_decode_order0(void)
{
        unsigned long current_cump, counter;


        // Get the total cump needed for decoding symbol
        ppmc_get_totf_order0();      //total cump needed for decoding
        symb_cump=range_decoder_decode(&rc_decoder,total_cump);        //decode it

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

                // Update coding values

                ppmc_get_escape_prob_order0();
                range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);

                // Mark as escape code

                byte=-1;

                return;   //an escape code
        }
        else
        {
                // Now we have to check what symbol it is

                current_cump=0;      //cump of the current symbol

                for(counter=0 ; counter!= 256 ; ++counter)
                {
                        if(symb_cump<current_cump)
                                break;                  //symbol found, break search loop
                        current_cump+=order0_array[counter];       //update cump
                }

                counter--;           //-1 (see ac_ppmc.html, searching for a given symbol)

                byte=counter;        //update the variable with the found symbol


                // Get the cump and prob of byte

                symb_prob=order0_array[byte];        //the probabilty
                symb_cump=current_cump-order0_array[byte]; //using the cump which was
                //already made

                // Update coding state

                range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);

                coded_in_order=0;    //decoded under order-0

                return;
        }

}


// This function returns the probability for the escape codes in the variables
void ppmc_get_escape_prob_order0(void)
{
        // To understand that remember that the escape allocated for the escape code
        // is above the current maximum cump and that it has a probability determined
        // by the scheme C.
        symb_prob=order0_defined_bytes;
        symb_cump=order0_max_cump;
        total_cump=order0_defined_bytes+order0_max_cump;
}



// ORDER-1 functions
//
// Order-1 uses 256 arrays one for every context, obviously they are accessed
// like that: order1_array[o1_byte][byte]
//
// Also for computing the value of the current escape code in a given context
// we need to know how many bytes are defined in a given context, they are
// stored in an array, and you use them like that:
// order1_defined_bytes_array[o1_byte]
//
// The same goes for the maximum cump of a given context:
// order1_max_cump_array[o1_byte]
//
// Read the order-0 explanation.
//
// To ensure that the updating and coding is done correctly, "byte" and
// "o1_byte" can't be changed till all the coding and updating is done.


// Returns in the variable "total_cump" the current total cump of
// order-1. o1_byte should contain the order-1
void ppmc_get_totf_order1(void)
{
        // Total cump is current total cump plus the escape for the escape code
        total_cump=order1_defined_bytes_array[o1_byte]+order1_max_cump_array[o1_byte];
}


// Codes a byte under order-1 and returns 1.
// Otherwise it returns a 0 it may be that it has coded an escape code, or
// that current table was empty, in this case nothing is outputted
// In both cases further coding is needed.
//
// Returns: 1 in case a byte was coded. 0 in case of escape code or empty table.
// In case the byte is coded under this context, coded_in_order=1.
char ppmc_code_byte_order1(void)
{
        unsigned long counter;


        // First check if current order-1 table is empty
        if(order1_defined_bytes_array[o1_byte]==0)  //it's empty
        {
                return 0;    //byte not coded, nothing done
        }


        // Now try to code this byte under order-1

        ppmc_get_totf_order1();      //get total cump

        // See if the byte is present
        if(order1_array[o1_byte][byte]==0)      //a probability of 0
        {

                // Because it was not present, output an escape code, prepare variables

                symb_cump=order1_max_cump_array[o1_byte];//obviously its cump is current max_cump
                //without escape code's space

                symb_prob=order1_defined_bytes_array[o1_byte];//the number of defined bytes

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

                return 0;    //byte not coded, escape coded
        }
        else
        {

                coded_in_order=1;            //because we coded it under order-1

                // The symbol is present, code it under order-1

                symb_prob=order1_array[o1_byte][byte];        //get probability directly

                // Make cump for current symbol

                symb_cump=0;         //for first symbol is 0
                for(counter=0; counter!=byte ; ++counter)
                        symb_cump+=order1_array[o1_byte][counter];  //sum probabilities before our symbol

                // Code the symbol
                range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);

                return 1;    //symbol coded under order-1
        }
}


// This functions update order-1 probabilities with current byte, also takes
// care about updating variables, and renormalizing. o1_byte must be filled.
void ppmc_update_order1(void)
{
        if(order1_array[o1_byte][byte]==0)
        {
                // It had a zero probability
                order1_array[o1_byte][byte]++;       //increment symbol probability
                ++order1_defined_bytes_array[o1_byte];     //new byte defined
                ++order1_max_cump_array[o1_byte];          //total cump
                return;
        }
        else
        {
                // It had a non-zero probability

                // Increment its probability
                order1_array[o1_byte][byte]++;      //increment symbol probability
                ++order1_max_cump_array[o1_byte];         //total cump

                // Check to see if its the maximum in this case renormalize
                if(order1_array[o1_byte][byte]==255)
                        ppmc_renormalize_order1();

                return;
        }
}


// This functions renormalizes the probabilities at order-1 updating variables
void ppmc_renormalize_order1(void)
{
        unsigned long counter;

        // Initialize variables
        order1_defined_bytes_array[o1_byte]=0;        //clear them
        order1_max_cump_array[o1_byte]=0;

        // Loop over all probabilities, divide them by a factor of 2 and update variables
        for(counter=0 ; counter!=256 ; ++counter)
        {
                order1_array[o1_byte][counter]>>=1;   //divide by a factor of 2

                if(order1_array[o1_byte][counter]!=0) //see if it has a non zero probability
                        order1_defined_bytes_array[o1_byte]++;

                order1_max_cump_array[o1_byte]+=order1_array[o1_byte][counter];      //sum to the total cump
        }
}


// Decodes the symbol correspoding to the current order, it returns the byte
// or in case of an escape code or empty table it returns -1.
// It updates "coded_in_order".
void ppmc_decode_order1(void)
{
        unsigned long current_cump, counter;


        // First check if current order-1 table is empty
        if(order1_defined_bytes_array[o1_byte]==0)  //it's empty
        {
                byte=-1;   //byte not coded, nothing done
                return;
        }


        // Get the total cump needed for decoding symbol
        ppmc_get_totf_order1();      //total cump needed for decoding
        symb_cump=range_decoder_decode(&rc_decoder,total_cump);        //decode it

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

                // Update coding values

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

                // Mark as escape code

                byte=-1;

                return;   //an escape code
        }
        else
        {
                // Now we have to check what symbol it is

                current_cump=0;      //cump of the current symbol

                for(counter=0 ; counter!= 256 ; ++counter)
                {
                        if(symb_cump<current_cump)
                                break;                  //symbol found, break search loop
                        current_cump+=order1_array[o1_byte][counter];       //update cump
                }

                counter--;           //-1 (see ac_ppmc.html, searching for a given symbol)

                byte=counter;        //update the variable with the found symbol


                // Get the cump and prob of byte

                symb_prob=order1_array[o1_byte][byte];        //the probabilty
                symb_cump=current_cump-order1_array[o1_byte][byte]; //using the cump which was
                //already made

                // Update coding state

                range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);


                // Update coded_in_order used for update exclusion

                coded_in_order=1;

                return;
        }

}


// This function returns the probability for the escape codes in the variables
void ppmc_get_escape_prob_order1(void)
{
        // To understand that remember that the escape allocated for the escape code
        // is above the current maximum cump and that it has a probability determined
        // by the scheme C.
        symb_prob=order1_defined_bytes_array[o1_byte];
        symb_cump=order1_max_cump_array[o1_byte];
        total_cump=order1_defined_bytes_array[o1_byte]+order1_max_cump_array[o1_byte];
}



// ORDER-2 functions
//
// Order-2 uses a table which holds the contexts data structure of every
// structure, its accessed with "ppmc_order2_hash_key(o1_byte, o2_byte)"
// and because it uses direct addressing there's no need to check for hash
// collisions, which makes it faster. The variable "o2_cntxt" contains o1_byte
// and o2_byte used directly to index the order-2 array.
//
// Though order-2 uses the same routines as lower orders they are rather
// different, because we can't allocate memory for all the probabilities
// tables, we have to use linked lists for the bytes and probabilities.
//
// Under order-2 we don't let a probability to be lower than 1, that is,
// there can't be a symbol in a linked list with a 0 probability, I choosed
// this for three factors: the code is easier to read (it isn't messy)
// we gain some speed, and the loss of compression seems little.
//
// To ensure that the updating is done correctly, "o2_cntxt" and
// "o2_ll_node" must not be modified by any routine except those who manage
// order-2.


// Returns in the variable "total_cump" the current total cump of
// order-2. cntxt must have o1_byte and o2_byte hashed with the hash key
// for order-2.
void ppmc_get_totf_order2(void)
{
        // Total cump is current total cump plus the escape for the escape code
        total_cump=order2_array[o2_cntxt].defined_bytes+order2_array[o2_cntxt].max_cump;
}


// Codes a byte under order-2 and returns 1.
// Otherwise it returns a 0. It may be that it has coded an escape code, or
// that current table was empty.
//
// Returns: 1 in case a byte was coded. 0 in case of escape code or empty table.
// In case the byte is coded under this context, coded_in_order=2.
char ppmc_code_byte_order2(void)
{
        unsigned long counter;
        struct _byte_and_freq *node;


        // Initialize o2_cntxt

        o2_cntxt=ppmc_order2_hash_key(o1_byte,o2_byte);


        // First check if current order-2 context is empty
        if(order2_array[o2_cntxt].defined_bytes==0)  //it's empty
        {
                return 0;   //byte not coded, nothing done
        }


        // Now try to code this byte under order-2

        ppmc_get_totf_order2();      //get total cump


        // See if the byte is present and compute its cump at the same time

        node=order2_array[o2_cntxt].prob; //pointer to first element in the linked list

        symb_cump=0;   //the first symbol always has a 0 cump


        // Now search the byte in the linked list

        do{
                if(node->byte==byte)
                        goto ppmc_o2_byte_found;   //bad thing, I know, anyone has a better idea?
                symb_cump+=node->freq;       //add the probability of this byte to the cump
                if(node->next==0)
                        break;
                node=node->next;             //next element in the linked list
        }while(1);


        // If we reach that point, the byte was not found in the linked list
        // so we don't need the cump, we have to output an escape code, whose
        // probabilities are know using the context structure in the table.

        // Byte was not present in the linked list, current node is the last one,
        // and that's the node needed for creating a new node, save it.

        o2_ll_node=node;

        // Now get the probability and cump of the escape code

        symb_cump=order2_array[o2_cntxt].max_cump;
        symb_prob=order2_array[o2_cntxt].defined_bytes;

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

        return 0;


        // That code is executed when the byte is found in the linked list

ppmc_o2_byte_found:


        // Everything has been tested, now we can feel free to code the byte,
        // the symb_cump is already computed, now get its probability and code
        // the byte, also save pointer to this element in the linked lists for
        // updating.

        coded_in_order=2;      //successfully coded under order-2

        o2_ll_node=node;       //save it for updating

        symb_prob=node->freq;  //get the probability of the byte

        // Code it.

        range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);

        return 1;      //byte coded under order-2
}


// This functions update order-2 probabilities with current byte, also takes
// care about updating variables, and renormalizing.
// Of course "o2_ll_node" must point to the element to update or the last one,
// based on the "coded_in_order" and checking the pointer of the element we
// can decide what to do.
//
// This updating is only for encoding.
void ppmc_update_order2(void)
{

        // First of all check if that's the first byte in this context, in that case
        // we have to initialize some variables in the context structure.

        if(order2_array[o2_cntxt].defined_bytes==0)    //no byte defined yet
        {

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate memory

                order2_array[o2_cntxt].defined_bytes=1;
                order2_array[o2_cntxt].max_cump=1;
                order2_array[o2_cntxt].prob=_bytes_pool;

                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }

                return;      //nothing else to do
        }


        // The byte was coded under order two, otherwise it was coded under a
        // lower order (never higher ones, remember that we are using update
        // exclusion) in this case we have to create a new node in the list.

        if(coded_in_order==2)  //coded under order-2
        {

                // Update its count and variables of this context and check for renormalization

                o2_ll_node->freq++;  //increment its frequency (rather probability)

                order2_array[o2_cntxt].max_cump++;   //total cump

                if(o2_ll_node->freq==255)    //do we have to renormalize?
                        ppmc_renormalize_order2(); //renormalize

        }
        else
        {

                // Once every paranoid check has been done we are sure that this byte
                // did not existed and so we have to create a new node in the linked
                // list. Also we have to take care of memory issues.

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate mem

                o2_ll_node->next=_bytes_pool;    //put it in the next free entry
                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                order2_array[o2_cntxt].max_cump++;   //total cump
                order2_array[o2_cntxt].defined_bytes++;   //total cump

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }

        }

}


// This functions renormalizes the probabilities at order-2 updating context
// variables.
void ppmc_renormalize_order2(void)
{
        unsigned long counter;
        struct _byte_and_freq *node;

        // Initialize variables. Defined bytes remain the same.
        order2_array[o2_cntxt].max_cump=0;        //clear them

        node=order2_array[o2_cntxt].prob;      //get pointer to lined lists

        // Divide all the probabilities by 2 and update context variables
        while(1)
        {
                node->freq>>=1;                      //divide by a factor of 2

                if(node->freq==0)    //don't allow a probability to be 0
                        node->freq=1;

                order2_array[o2_cntxt].max_cump+=node->freq; //sum to the total cump

                if(node->next==0)    //last element
                        break;
                node=node->next;
        }


        //printf("\nRenormalization, context:%c%c",o2_byte,o1_byte);

}


// Decodes the symbol correspoding to the current order, it returns the byte
// or in case of an escape code or empty table it returns -1.
// It updates "coded_in_order".
//
// If we decode an escape code, we don't modify "o2_ll_node" and thus its
// work of the updating routine to read till the end of the linked list
// (for adding a new element) however if we decode a byte, we save on
// "o2_ll_node" the pointer to its node. (so updating is faster)
void ppmc_decode_order2(void)
{
        unsigned long current_cump, counter;
        struct _byte_and_freq *node;

        // Initialize o2_cntxt

        o2_cntxt=ppmc_order2_hash_key(o1_byte,o2_byte);


        // First check if current order-2 context is empty
        if(order2_array[o2_cntxt].defined_bytes==0)  //it's empty
        {
                byte=-1;   //byte not coded, nothing done
                return;
        }


        // Get the total cump needed for decoding symbol
        ppmc_get_totf_order2();      //total cump needed for decoding
        symb_cump=range_decoder_decode(&rc_decoder,total_cump);        //decode it

        // Now check if it's an escape code
        if(symb_cump>=order2_array[o2_cntxt].max_cump)     //the defined code space for the escape code
        {

                // Update coding values

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

                // Mark as escape code

                byte=-1;

                return;   //an escape code
        }
        else
        {
                // Now we have to check what symbol it is

                current_cump=0;      //cump of the current symbol

                node=order2_array[o2_cntxt].prob;    //get pointer to linked lists

                while(1)
                {
                        current_cump+=node->freq; //update cump
                        if(symb_cump<current_cump)
                                break;                  //symbol found, break search loop

                        node=node->next;          //next element
                        //we have no need to check for the last symbol, we'll never read further
                        //the end of the linked lists, before we'll found the last byte.
                }


                //read byte value and probability

                symb_prob=node->freq;     //get the probability for updating the state
                byte=node->byte;          //get byte
                o2_ll_node=node;          //used for updating


                // Get the cump of byte

                symb_cump=current_cump-symb_prob;

                // Update coding state

                range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);

                // Update coded_in_order used for update exclusion

                coded_in_order=2;

                return;
        }

}


// This is the routine for updating while decoding. We have to search the byte
// in the linked list, if it's present, update its count, otherwise we have
// hitted the end of the linked list, and there we have to create a new node.
//
// Of course if the byte was matched in order-2 we'll have a pointer to it
// in "o2_ll_node" so we don't need to read the linked list. (we already did
// in decoding)
//
// Another case which we also have to specially deal with, this is the case
// when the context has not been initalized yet.
void ppmc_update_dec_order2(void)
{
        struct _byte_and_freq *node;


        // Handle the case when the context is not initialized
        // This code is the same as the one for the encoding.

        if(order2_array[o2_cntxt].defined_bytes==0)    //no byte defined yet
        {

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate memory

                order2_array[o2_cntxt].defined_bytes=1;
                order2_array[o2_cntxt].max_cump=1;
                order2_array[o2_cntxt].prob=_bytes_pool;

                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }


                return;      //nothing else to do
        }


        // Current context is initalized, proceed

        if(coded_in_order==2)          //check if it was decoded under order-2
        {

                // We can be sure that the pointer "o2_ll_node" points to its entry, and
                // it has a non 0 probability (otherwise it couldn't be coded) so just
                // update its probability and max_cump

                o2_ll_node->freq++;          //the probability of the byte
                order2_array[o2_cntxt].max_cump++; //the max_cump

                if(o2_ll_node->freq==255)    //check for renormalization
                        ppmc_renormalize_order2();

        }
        else
        {

                // An escape code was decoded under order-2, we have to read till the
                // end of the linked list so we can add a new node for this new byte.

                node=order2_array[o2_cntxt].prob;    //get pointer to linked list

                while(1)
                {
                        if(node->next==0)          //check for the end of the linked list
                                break;
                        node=node->next;           //next node
                }


                // We reached the end of the linked list, add a new node if possible,
                // we are using the same code of "ppmc_update_order2()" with the
                // difference that the pointer to the linked list is "node"

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate mem

                node->next=_bytes_pool;          //put it in the next free entry
                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                order2_array[o2_cntxt].max_cump++;   //total cump
                order2_array[o2_cntxt].defined_bytes++;   //total cump

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }

                return;      //we are finished updating

        }

}


// This function returns the probability for the escape codes in the variables
void ppmc_get_escape_prob_order2(void)
{
        // To understand that remember that the escape allocated for the escape code
        // is above the current maximum cump and that it has a probability determined
        // by the scheme C.

        symb_prob=order2_array[o2_cntxt].defined_bytes;
        symb_cump=order2_array[o2_cntxt].max_cump;
}



// ORDER-3 functions
//
// The difference between order-3 and order-3 are just a few, instead of
// keeping a table with the context structures, we keep a hash table with
// pointers to linked lists with the context, so it's only a matter of
// searching current context in the linked list corresponding to its hash
// entry. This is done in "ppmc_get_totf_order3" because that's the first
// routine that both encoding and decoding routines call.


// Returns in the variable "total_cump" the current total cump of
// order-3. Must be called while encoding or decoding before anything else
// because it initializes the pointers to the context structure in
// "o3_context" and o3_cntxt.
//
// If the hash entry is not initialized it returns "o3_context"=0
// If the context is not present in the linked list of context, "o3_context"
// will point to the last element in the linked list.
// If the context is present "o3_context" will point to the context to use.
// One can distinguish the last two by checking the context value of the
// structure, if it's not the same, is the last element.
//
// The routine returns 0 if the hash entry is not initialized or if the
// the context was not present. Otherwise it returns 1, meaning that we
// have to code under this context.
char ppmc_get_totf_order3(void)
{
        struct context *cntxt_node;


        // First make the hash key for order-3

        o3_cntxt=ppmc_order3_hash_key(o1_byte,o2_byte,o3_byte);
        full_o3_cntxt=(o1_byte)+(o2_byte<<8)+(o3_byte<<16);    //order-3


        // Now check the hash entry in the table

        if(order3_hasht[o3_cntxt]==0)  //if 0, not initialized
        {

                o3_context=0;        //no hash entry

                return 0;    //hash entry not initialized
        }


        // Now read trough the linked list of context searching current one

        cntxt_node=order3_hasht[o3_cntxt];

        while(1)
        {

                if(cntxt_node->order4321==full_o3_cntxt)     //compare context
                        goto ppmc_gtf_cntxt_found;

                if(cntxt_node->next==0)      //end of context's linked list
                        break;

                cntxt_node=cntxt_node->next; //next element

        }


        // Once there the context was not found
        o3_context=cntxt_node;    //pointer to last element in the linked list

        return 0;      //it was not present


        // The context is found, so return pointer and cump

ppmc_gtf_cntxt_found:

        o3_context=cntxt_node;

        // Total cump is current total cump plus the escape for the escape code

        total_cump=o3_context->defined_bytes+o3_context->max_cump;

        return 1;      //context found

}


// Codes a byte under order-3 and returns 1.
// Otherwise it returns a 0.
//
// In case the byte is coded under this context, coded_in_order=3.
char ppmc_code_byte_order3(void)
{
        unsigned long counter;
        struct _byte_and_freq *node;


        // Get current context (if present) and total cump.

        if(ppmc_get_totf_order3()==0)
                return 0;


        // See if the byte is present and compute its cump at the same time

        node=o3_context->prob; //pointer to first element in the linked list

        symb_cump=0;   //the first symbol always has a 0 cump


        // Now search the byte in the linked list

        do{
                if(node->byte==byte)
                        goto ppmc_o3_byte_found;   //bad thing, I know, anyone has a better idea?
                symb_cump+=node->freq;       //add the probability of this byte to the cump
                if(node->next==0)
                        break;
                node=node->next;             //next element in the linked list
        }while(1);


        // If we reach that point, the byte was not found in the linked list
        // so we don't need the cump, we have to output an escape code, whose
        // probabilities are know using the context structure in the table.

        // Byte was not present in the linked list, current node is the last one,
        // and that's the node needed for creating a new node, save it.

        o3_ll_node=node;

        // Now get the probability and cump of the escape code

        symb_cump=o3_context->max_cump;
        symb_prob=o3_context->defined_bytes;

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

        return 0;


        // That code is executed when the byte is found in the linked list

ppmc_o3_byte_found:


        // Everything has been tested, now we can feel free to code the byte,
        // the symb_cump is already computed, now get its probability and code
        // the byte, also save pointer to this element in the linked lists for
        // updating.

        coded_in_order=3;      //successfully coded under order-3

        o3_ll_node=node;       //save it for updating

        symb_prob=node->freq;  //get the probability of the byte

        // Code it.

        range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);

        return 1;      //byte coded under order-3
}


// This functions update order-3 probabilities with current byte, also takes
// care about updating variables, and renormalizing.
//
// "o3_ll_node" must point to the element to update or the last one,
// based on the "coded_in_order" and checking the pointer of the element we
// can decide what to do. Also "o3_context" must be initialized.
//
// This updating is only for encoding.
void ppmc_update_order3(void)
{

        // First thing first, check if the hash entry is initialized

        if(order3_hasht[o3_cntxt]==0)    //no pointer to linked list defined yet
        {

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate memory


                // First create the context

                order3_hasht[o3_cntxt]=_context_pool;

                _context_pool->next=0;       //this is the last element
                _context_pool->order4321=full_o3_cntxt;      //put context
                _context_pool->prob=_bytes_pool;             //pointer to linked list
                _context_pool->max_cump=1;
                _context_pool->defined_bytes=1;


                // Do update of linked list variables and memory use of contexts

                ++_context_pool;           //next time use next entry (this is a pointer)

                if(_context_pool==_context_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_context_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_context_pool=(struct context *)malloc
                                                (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                        {
                                printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _context_pool_array[_context_pool_index]=_context_pool;

                        _context_pool_max=_context_pool+_context_pool_elements_inc;

                        _context_pool_index++;

                }


                // Now care about the first (and last) linked list element

                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }

                return;      //nothing else to do
        }




        // The byte was coded under order three, otherwise it was coded under a
        // lower order (never higher ones, remember that we are using update
        // exclusion) in this case we have to create a new node in the list.

        if(coded_in_order==3)  //coded under order-3
        {

                // Update its count and variables of this context and check for renormalization

                o3_ll_node->freq++;  //increment its frequency (rather probability)

                o3_context->max_cump++;   //total cump

                if(o3_ll_node->freq==255)    //do we have to renormalize?
                        ppmc_renormalize_order3(); //renormalize

        }
        else
        {

                // Now we have two cases, under a given context (which we actually found)
                // we coded an escape coded, in that case just create a new node in the
                // linked list of bytes and probabilities. Otherwise we didn't find the
                // same node so we have to create it in the linked list for context.
                // And we can be sure that it at least has one element and that
                // "o3_context" points to the last element, so we can put the new element.

                if(o3_context->order4321==full_o3_cntxt) //chech if that's the last
                {                                      //element or the a context found

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate mem

                        o3_ll_node->next=_bytes_pool;    //put it in the next free entry
                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        o3_context->max_cump++;   //total cump
                        o3_context->defined_bytes++;   //total cump

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }
                }
                else
                {

                        // We have to create a new context node

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate memory


                        // First create the context

                        o3_context->next=_context_pool;

                        _context_pool->next=0;       //this is the last element
                        _context_pool->order4321=full_o3_cntxt;      //put context
                        _context_pool->prob=_bytes_pool;             //pointer to linked list
                        _context_pool->max_cump=1;
                        _context_pool->defined_bytes=1;


                        // Do update of linked list variables and memory use of contexts

                        ++_context_pool;           //next time use next entry (this is a pointer)

                        if(_context_pool==_context_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_context_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_context_pool=(struct context *)malloc
                                                        (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                                {
                                        printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _context_pool_array[_context_pool_index]=_context_pool;

                                _context_pool_max=_context_pool+_context_pool_elements_inc;

                                _context_pool_index++;

                        }

                        // Now care about the first (and last) linked list element

                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }

                }

        }

}


// This functions renormalizes the probabilities at order-3 updating context
// variables.
void ppmc_renormalize_order3(void)
{
        unsigned long counter;
        struct _byte_and_freq *node;


        // Initialize variables. Defined bytes remain the same.
        o3_context->max_cump=0;        //clear them

        node=o3_context->prob;      //get pointer to lined lists

        // Divide all the probabilities by 2 and update context variables
        while(1)
        {
                node->freq>>=1;                      //divide by a factor of 2

                if(node->freq==0)    //don't allow a probability to be 0
                        node->freq=1;

                o3_context->max_cump+=node->freq; //sum to the total cump

                if(node->next==0)    //last element
                        break;
                node=node->next;
        }


}


// Decodes the symbol correspoding to the current order, it returns the byte
// or in case of an escape code or empty table it returns -1.
// It updates "coded_in_order".
//
// If we decode an escape code, we don't modify "o3_ll_node" and thus its
// work of the updating routine to read till the end of the linked list
// (for adding a new element) however if we decode a byte, we save on
// "o3_ll_node" the pointer to its node. (so updating is faster)
void ppmc_decode_order3(void)
{
        unsigned long current_cump, counter;
        struct _byte_and_freq *node;


        // Get current context (if present) and total cump.

        if(ppmc_get_totf_order3()==0)
        {
                byte=-1;
                return;
        }


        // Decode current cump

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

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

                // Update coding values

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

                // Mark as escape code

                byte=-1;

                return;   //an escape code
        }
        else
        {
                // Now we have to check what symbol it is

                current_cump=0;      //cump of the current symbol

                node=o3_context->prob;    //get pointer to linked lists

                while(1)
                {
                        current_cump+=node->freq; //update cump
                        if(symb_cump<current_cump)
                                break;                  //symbol found, break search loop

                        node=node->next;          //next element
                        //we have no need to check for the last symbol, we'll never read further
                        //the end of the linked lists, before we'll found the last byte.
                }


                //read byte value and probability

                symb_prob=node->freq;     //get the probability for updating the state
                byte=node->byte;          //get byte
                o3_ll_node=node;          //used for updating


                // Get the cump of byte

                symb_cump=current_cump-symb_prob;

                // Update coding state

                range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);

                // Update coded_in_order used for update exclusion

                coded_in_order=3;

                return;
        }

}


// This is the routine for updating while decoding. The only difference with
// the routine for coding is that when an escape code was coded, "o3_ll_node"
// is not initialized so we have to read till the end of the linked list.
// Fortunately "o3_context" will be initialized so we don't need to read its
// linked list.
void ppmc_update_dec_order3(void)
{
        struct _byte_and_freq *node;

        // First thing first, check if the hash entry is initialized

        if(order3_hasht[o3_cntxt]==0)    //no pointer to linked list defined yet
        {

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate memory


                // First create the context

                order3_hasht[o3_cntxt]=_context_pool;

                _context_pool->next=0;       //this is the last element
                _context_pool->order4321=full_o3_cntxt;      //put context
                _context_pool->prob=_bytes_pool;             //pointer to linked list
                _context_pool->max_cump=1;
                _context_pool->defined_bytes=1;


                // Do update of linked list variables and memory use of contexts

                ++_context_pool;           //next time use next entry (this is a pointer)

                if(_context_pool==_context_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_context_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_context_pool=(struct context *)malloc
                                                (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                        {
                                printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _context_pool_array[_context_pool_index]=_context_pool;

                        _context_pool_max=_context_pool+_context_pool_elements_inc;

                        _context_pool_index++;

                }

                // Now care about the first (and last) linked list element

                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }

                return;      //nothing else to do
        }


        // The byte was coded under order three, otherwise it was coded under a
        // lower order (never higher ones, remember that we are using update
        // exclusion) in this case we have to create a new node in the list.

        if(coded_in_order==3)  //coded under order-3
        {

                // Update its count and variables of this context and check for renormalization

                o3_ll_node->freq++;  //increment its frequency (rather probability)

                o3_context->max_cump++;   //total cump

                if(o3_ll_node->freq==255)    //do we have to renormalize?
                        ppmc_renormalize_order3(); //renormalize

        }
        else
        {

                // Now we have two cases, under a given context (which we actually found)
                // we coded an escape coded, in that case just create a new node in the
                // linked list of bytes and probabilities. Otherwise we didn't find the
                // same node so we have to create it in the linked list for context.
                // And we can be sure that it at least has one element and that
                // "o3_context" points to the last element, so we can put the new element.

                if(o3_context->order4321==full_o3_cntxt) //chech if that's the last
                {                                      //element or the a context found

                        // Read till the end of the linked list

                        node=o3_context->prob;    //get pointer to linked list

                        while(1)
                        {
                                if(node->next==0)          //check for the end of the linked list
                                        break;
                                node=node->next;           //next node
                        }

                        // Now add element

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate mem

                        node->next=_bytes_pool;          //put it in the next free entry
                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        o3_context->max_cump++;   //total cump
                        o3_context->defined_bytes++;   //total cump

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }
                }
                else
                {

                        // We have to create a new context node

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate memory


                        // First create the context

                        o3_context->next=_context_pool;

                        _context_pool->next=0;       //this is the last element
                        _context_pool->order4321=full_o3_cntxt;      //put context
                        _context_pool->prob=_bytes_pool;             //pointer to linked list
                        _context_pool->max_cump=1;
                        _context_pool->defined_bytes=1;


                        // Do update of linked list variables and memory use of contexts

                        ++_context_pool;           //next time use next entry (this is a pointer)

                        if(_context_pool==_context_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_context_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_context_pool=(struct context *)malloc
                                                        (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                                {
                                        printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _context_pool_array[_context_pool_index]=_context_pool;

                                _context_pool_max=_context_pool+_context_pool_elements_inc;

                                _context_pool_index++;

                        }

                        // Now care about the first (and last) linked list element

                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }

                }

        }

}



// This function returns the probability for the escape codes in the variables
void ppmc_get_escape_prob_order3(void)
{
        // To understand that remember that the escape allocated for the escape code
        // is above the current maximum cump and that it has a probability determined
        // by the scheme C.

        symb_prob=o3_context->defined_bytes;
        symb_cump=o3_context->max_cump;
}



// ORDER-4 functions
//
// The routines for order-4 are *equal* to those for order-3, there are a few
// changes like different global variables, and different hash keys.
//
// If you want to go to higher orders, you'd use the same code and data
// structures, with the difference of the context bytes (order4321)
// stored in every context's linked list.


// Returns in the variable "total_cump" the current total cump of
// order-4. Must be called while encoding or decoding before anything else
// because it initializes the pointers to the context structure in
// "o4_context" and o4_cntxt.
//
// If the hash entry is not initialized it returns "o4_context"=0
// If the context is not present in the linked list of context, "o4_context"
// will point to the last element in the linked list.
// If the context is present "o4_context" will point to the context to use.
// One can distinguish the last two by checking the context value of the
// structure, if it's not the same, is the last element.
//
// The routine returns 0 if the hash entry is not initialized or if the
// the context was not present. Otherwise it returns 1, meaning that we
// have to code under this context.
char ppmc_get_totf_order4(void)
{
        struct context *cntxt_node;


        // First make the hash key for order-4

        o4_cntxt=ppmc_order4_hash_key(o1_byte,o2_byte,o3_byte,o4_byte);
        full_o4_cntxt=(o1_byte)+(o2_byte<<8)+(o3_byte<<16)+(o4_byte<<24);    //order-4


        // Now check the hash entry in the table

        if(order4_hasht[o4_cntxt]==0)  //if 0, not initialized
        {

                o4_context=0;        //no hash entry

                return 0;    //hash entry not initialized
        }


        // Now read trough the linked list of context searching current one

        cntxt_node=order4_hasht[o4_cntxt];

        while(1)
        {

                if(cntxt_node->order4321==full_o4_cntxt)     //compare context
                        goto ppmc_gtfo4_cntxt_found;

                if(cntxt_node->next==0)      //end of context's linked list
                        break;

                cntxt_node=cntxt_node->next; //next element

        }


        // Once there the context was not found
        o4_context=cntxt_node;    //pointer to last element in the linked list

        return 0;      //it was not present


        // The context is found, so return pointer and cump

ppmc_gtfo4_cntxt_found:

        o4_context=cntxt_node;

        // Total cump is current total cump plus the escape for the escape code

        total_cump=o4_context->defined_bytes+o4_context->max_cump;

        return 1;      //context found

}


// Codes a byte under order-4 and returns 1.
// Otherwise it returns a 0.
//
// In case the byte is coded under this context, coded_in_order=4.
char ppmc_code_byte_order4(void)
{
        unsigned long counter;
        struct _byte_and_freq *node;


        // Get current context (if present) and total cump.

        if(ppmc_get_totf_order4()==0)
                return 0;


        // See if the byte is present and compute its cump at the same time

        node=o4_context->prob; //pointer to first element in the linked list

        symb_cump=0;   //the first symbol always has a 0 cump


        // Now search the byte in the linked list

        do{
                if(node->byte==byte)
                        goto ppmc_o4_byte_found;   //bad thing, I know, anyone has a better idea?
                symb_cump+=node->freq;       //add the probability of this byte to the cump
                if(node->next==0)
                        break;
                node=node->next;             //next element in the linked list
        }while(1);


        // If we reach that point, the byte was not found in the linked list
        // so we don't need the cump, we have to output an escape code, whose
        // probabilities are know using the context structure in the table.

        // Byte was not present in the linked list, current node is the last one,
        // and that's the node needed for creating a new node, save it.

        o4_ll_node=node;

        // Now get the probability and cump of the escape code

        symb_cump=o4_context->max_cump;
        symb_prob=o4_context->defined_bytes;

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

        return 0;


        // That code is executed when the byte is found in the linked list

ppmc_o4_byte_found:


        // Everything has been tested, now we can feel free to code the byte,
        // the symb_cump is already computed, now get its probability and code
        // the byte, also save pointer to this element in the linked lists for
        // updating.

        coded_in_order=4;      //successfully coded under order-4

        o4_ll_node=node;       //save it for updating

        symb_prob=node->freq;  //get the probability of the byte

        // Code it.

        range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);

        return 1;      //byte coded under order-4
}


// This functions update order-4 probabilities with current byte, also takes
// care about updating variables, and renormalizing.
//
// "o4_ll_node" must point to the element to update or the last one,
// based on the "coded_in_order" and checking the pointer of the element we
// can decide what to do. Also "o4_context" must be initialized.
//
// This updating is only for encoding.
void ppmc_update_order4(void)
{

        // First thing first, check if the hash entry is initialized

        if(order4_hasht[o4_cntxt]==0)    //no pointer to linked list defined yet
        {

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate memory


                // First create the context

                order4_hasht[o4_cntxt]=_context_pool;

                _context_pool->next=0;       //this is the last element
                _context_pool->order4321=full_o4_cntxt;      //put context
                _context_pool->prob=_bytes_pool;             //pointer to linked list
                _context_pool->max_cump=1;
                _context_pool->defined_bytes=1;


                // Do update of linked list variables and memory use of contexts

                ++_context_pool;           //next time use next entry (this is a pointer)

                if(_context_pool==_context_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_context_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_context_pool=(struct context *)malloc
                                                (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                        {
                                printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _context_pool_array[_context_pool_index]=_context_pool;

                        _context_pool_max=_context_pool+_context_pool_elements_inc;

                        _context_pool_index++;

                }


                // Now care about the first (and last) linked list element

                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }

                return;      //nothing else to do
        }




        // The byte was coded under order three, otherwise it was coded under a
        // lower order (never higher ones, remember that we are using update
        // exclusion) in this case we have to create a new node in the list.

        if(coded_in_order==4)  //coded under order-4
        {

                // Update its count and variables of this context and check for renormalization

                o4_ll_node->freq++;  //increment its frequency (rather probability)

                o4_context->max_cump++;   //total cump

                if(o4_ll_node->freq==255)    //do we have to renormalize?
                        ppmc_renormalize_order4(); //renormalize

        }
        else
        {

                // Now we have two cases, under a given context (which we actually found)
                // we coded an escape coded, in that case just create a new node in the
                // linked list of bytes and probabilities. Otherwise we didn't find the
                // same node so we have to create it in the linked list for context.
                // And we can be sure that it at least has one element and that
                // "o4_context" points to the last element, so we can put the new element.

                if(o4_context->order4321==full_o4_cntxt) //chech if that's the last
                {                                      //element or the a context found

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate mem

                        o4_ll_node->next=_bytes_pool;    //put it in the next free entry
                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        o4_context->max_cump++;   //total cump
                        o4_context->defined_bytes++;   //total cump

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }
                }
                else
                {

                        // We have to create a new context node

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate memory


                        // First create the context

                        o4_context->next=_context_pool;

                        _context_pool->next=0;       //this is the last element
                        _context_pool->order4321=full_o4_cntxt;      //put context
                        _context_pool->prob=_bytes_pool;             //pointer to linked list
                        _context_pool->max_cump=1;
                        _context_pool->defined_bytes=1;


                        // Do update of linked list variables and memory use of contexts

                        ++_context_pool;           //next time use next entry (this is a pointer)

                        if(_context_pool==_context_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_context_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_context_pool=(struct context *)malloc
                                                        (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                                {
                                        printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _context_pool_array[_context_pool_index]=_context_pool;

                                _context_pool_max=_context_pool+_context_pool_elements_inc;

                                _context_pool_index++;

                        }

                        // Now care about the first (and last) linked list element

                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }

                }

        }

}


// This functions renormalizes the probabilities at order-4 updating context
// variables.
void ppmc_renormalize_order4(void)
{
        unsigned long counter;
        struct _byte_and_freq *node;


        // Initialize variables. Defined bytes remain the same.
        o4_context->max_cump=0;        //clear them

        node=o4_context->prob;      //get pointer to lined lists

        // Divide all the probabilities by 2 and update context variables
        while(1)
        {
                node->freq>>=1;                      //divide by a factor of 2

                if(node->freq==0)    //don't allow a probability to be 0
                        node->freq=1;

                o4_context->max_cump+=node->freq; //sum to the total cump

                if(node->next==0)    //last element
                        break;
                node=node->next;
        }


}


// Decodes the symbol correspoding to the current order, it returns the byte
// or in case of an escape code or empty table it returns -1.
// It updates "coded_in_order".
//
// If we decode an escape code, we don't modify "o4_ll_node" and thus its
// work of the updating routine to read till the end of the linked list
// (for adding a new element) however if we decode a byte, we save on
// "o4_ll_node" the pointer to its node. (so updating is faster)
void ppmc_decode_order4(void)
{
        unsigned long current_cump, counter;
        struct _byte_and_freq *node;


        // Get current context (if present) and total cump.

        if(ppmc_get_totf_order4()==0)
        {
                byte=-1;
                return;
        }


        // Decode current cump

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

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

                // Update coding values

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

                // Mark as escape code

                byte=-1;

                return;   //an escape code
        }
        else
        {
                // Now we have to check what symbol it is

                current_cump=0;      //cump of the current symbol

                node=o4_context->prob;    //get pointer to linked lists

                while(1)
                {
                        current_cump+=node->freq; //update cump
                        if(symb_cump<current_cump)
                                break;                  //symbol found, break search loop

                        node=node->next;          //next element
                        //we have no need to check for the last symbol, we'll never read further
                        //the end of the linked lists, before we'll found the last byte.
                }


                //read byte value and probability

                symb_prob=node->freq;     //get the probability for updating the state
                byte=node->byte;          //get byte
                o4_ll_node=node;          //used for updating


                // Get the cump of byte

                symb_cump=current_cump-symb_prob;

                // Update coding state

                range_decoder_update(&rc_decoder,total_cump,symb_cump,symb_prob);

                // Update coded_in_order used for update exclusion

                coded_in_order=4;

                return;
        }

}


// This is the routine for updating while decoding. The only difference with
// the routine for coding is that when an escape code was coded, "o4_ll_node"
// is not initialized so we have to read till the end of the linked list.
// Fortunately "o4_context" will be initialized so we don't need to read its
// linked list.
void ppmc_update_dec_order4(void)
{
        struct _byte_and_freq *node;

        // First thing first, check if the hash entry is initialized

        if(order4_hasht[o4_cntxt]==0)    //no pointer to linked list defined yet
        {

                if(ppmc_out_of_memory==1)
                        return;                //exit this function, we can't allocate memory


                // First create the context

                order4_hasht[o4_cntxt]=_context_pool;

                _context_pool->next=0;       //this is the last element
                _context_pool->order4321=full_o4_cntxt;      //put context
                _context_pool->prob=_bytes_pool;             //pointer to linked list
                _context_pool->max_cump=1;
                _context_pool->defined_bytes=1;


                // Do update of linked list variables and memory use of contexts

                ++_context_pool;           //next time use next entry (this is a pointer)

                if(_context_pool==_context_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_context_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_context_pool=(struct context *)malloc
                                                (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                        {
                                printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _context_pool_array[_context_pool_index]=_context_pool;

                        _context_pool_max=_context_pool+_context_pool_elements_inc;

                        _context_pool_index++;

                }

                // Now care about the first (and last) linked list element

                _bytes_pool->byte=byte;          //initialize byte to current one
                _bytes_pool->freq=1;             //it appeared once
                _bytes_pool->next=0;             //now this is last element in ll

                // Do update of linked list variables and memory use

                ++_bytes_pool;           //next time use next entry (this is a pointer)

                if(_bytes_pool==_bytes_pool_max)    //maximum reached
                {

                        // First check to see that we still have entries in the array

                        if(_bytes_pool_index==_mempool_max_index)
                        {
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        // Allocate memory for new buffer

                        if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                        {
                                printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                ppmc_out_of_memory=1;    //flush
                                return;
                        }

                        _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                        _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                        _bytes_pool_index++;

                }

                return;      //nothing else to do
        }


        // The byte was coded under order four, otherwise it was coded under a
        // lower order (never higher ones, remember that we are using update
        // exclusion) in this case we have to create a new node in the list.

        if(coded_in_order==4)  //coded under order-4
        {

                // Update its count and variables of this context and check for renormalization

                o4_ll_node->freq++;  //increment its frequency (rather probability)

                o4_context->max_cump++;   //total cump

                if(o4_ll_node->freq==255)    //do we have to renormalize?
                        ppmc_renormalize_order4(); //renormalize

        }
        else
        {

                // Now we have two cases, under a given context (which we actually found)
                // we coded an escape coded, in that case just create a new node in the
                // linked list of bytes and probabilities. Otherwise we didn't find the
                // same node so we have to create it in the linked list for context.
                // And we can be sure that it at least has one element and that
                // "o4_context" points to the last element, so we can put the new element.

                if(o4_context->order4321==full_o4_cntxt) //chech if that's the last
                {                                      //element or the a context found

                        // Read till the end of the linked list

                        node=o4_context->prob;    //get pointer to linked list

                        while(1)
                        {
                                if(node->next==0)          //check for the end of the linked list
                                        break;
                                node=node->next;           //next node
                        }

                        // Now add element

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate mem

                        node->next=_bytes_pool;          //put it in the next free entry
                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        o4_context->max_cump++;   //total cump
                        o4_context->defined_bytes++;   //total cump

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }
                }
                else
                {

                        // We have to create a new context node

                        if(ppmc_out_of_memory==1)
                                return;                //exit this function, we can't allocate memory


                        // First create the context

                        o4_context->next=_context_pool;

                        _context_pool->next=0;       //this is the last element
                        _context_pool->order4321=full_o4_cntxt;      //put context
                        _context_pool->prob=_bytes_pool;             //pointer to linked list
                        _context_pool->max_cump=1;
                        _context_pool->defined_bytes=1;


                        // Do update of linked list variables and memory use of contexts

                        ++_context_pool;           //next time use next entry (this is a pointer)

                        if(_context_pool==_context_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_context_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_context_pool=(struct context *)malloc
                                                        (sizeof(struct context)*_context_pool_elements_inc))==NULL)
                                {
                                        printf("Can't allocate memory for context's memory pool.\nIndex: %d",_context_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _context_pool_array[_context_pool_index]=_context_pool;

                                _context_pool_max=_context_pool+_context_pool_elements_inc;

                                _context_pool_index++;

                        }

                        // Now care about the first (and last) linked list element

                        _bytes_pool->byte=byte;          //initialize byte to current one
                        _bytes_pool->freq=1;             //it appeared once
                        _bytes_pool->next=0;             //now this is last element in ll

                        // Do update of linked list variables and memory use

                        ++_bytes_pool;           //next time use next entry (this is a pointer)

                        if(_bytes_pool==_bytes_pool_max)    //maximum reached
                        {

                                // First check to see that we still have entries in the array

                                if(_bytes_pool_index==_mempool_max_index)
                                {
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                // Allocate memory for new buffer

                                if((_bytes_pool=(struct _byte_and_freq *)malloc
                                                        (sizeof(struct _byte_and_freq)*_bytes_pool_elements_inc))==NULL)
                                {
                                        printf("\nCan't allocate memory for bytes memory pool.\nIndex: %d",_bytes_pool_index);
                                        ppmc_out_of_memory=1;    //flush
                                        return;
                                }

                                _bytes_pool_array[_bytes_pool_index]=_bytes_pool;

                                _bytes_pool_max=_bytes_pool+_bytes_pool_elements_inc;

                                _bytes_pool_index++;

                        }

                }

        }

}



// This function returns the probability for the escape codes in the variables
void ppmc_get_escape_prob_order4(void)
{
        // To understand that remember that the escape allocated for the escape code
        // is above the current maximum cump and that it has a probability determined
        // by the scheme C.

        symb_prob=o4_context->defined_bytes;
        symb_cump=o4_context->max_cump;
}