src/ppmc/exclusion/ppmcdata.c

   1 /*
   2  Copyright (C) Arturo San Emeterio Campos 1999. All rights reserved.
   3  Permission is granted to make verbatim copies of this file for private
   4  use only. There is ABSOLUTELY NO WARRANTY. Use it at your OWN RISK.
   5
   6  This file is: "ppmcdata.c" (exclusions)
   7  Email: arturo@arturocampos.com
   8  Web: http://www.arturocampos.com
   9
  10  Part of the ppmc encoder and decoder.
  11
  12  This module contains global data.
  13 */
  14
  15 #include "ppmc.h"       //defines
  16 #include "range.h"
  17
  18 // Order-4 uses a hash table which points to the start of a linked list with
  19 // the different context, which has the cump, the number of different symbols
  20 // and a pointer to the linked list with the bytes and frequencies.
  21 // Order-3 is almost the same, both take 262144 bytes.
  22 struct context *order4_hasht[ppmc_order4_hash_size];
  23
  24 struct context *order3_hasht[ppmc_order3_hash_size];
  25
  26
  27 // The array for order-2 is different, as we do directly hashing, and thus
  28 // we have no need to do the stuff of linked lists for the context itself,
  29 // so it contains the context used. This takes 1310720 bytes.
  30 struct context_o2 order2_array[65536];
  31
  32
  33 // Those are the multiple arrays for order-1. It takes 65536 bytes.
  34 unsigned char order1_array[256][256];
  35 unsigned int order1_defined_bytes_array[256]; //the defined bytes in every context
  36 unsigned int order1_max_cump_array[256];  //max cump of every context
  37
  38
  39 // This is the array for order-0. It takes 256 bytes.
  40 unsigned char order0_array[256];
  41 unsigned int order0_defined_bytes;
  42 unsigned int order0_max_cump;
  43
  44
  45 // No need of variables for order-(-1), because it's fixed.
  46
  47
  48
  49 // Those are the pointers and variables used for managing the mem pool for
  50 // both context, and bytes and frequencies.
  51 struct _byte_and_freq *_bytes_pool,     //pointer to pool containing linked
  52                                         //lists with bytes and frequencies
  53                       *_bytes_pool_max; //the maximum of this buffer
  54 struct context *_context_pool;          //pointer to pool containing contexts
  55 struct context *_context_pool_max;      //the same as with _bytes_pool
  56
  57 unsigned long _bytes_pool_index;        //index in array of pointers
  58 unsigned long _context_pool_index;
  59
  60 //the following is an array keeping pointers to different buffers. A new
  61 //buffer is allocated when the current one is full, so we always have a
  62 //buffer for linked lists. (without allocating a buffer for every element)
  63 struct _byte_and_freq *_bytes_pool_array[_mempool_max_index];
  64 struct context *_context_pool_array[_mempool_max_index];
  65
  66 char ppmc_out_of_memory;        //0 if we have enough memory, 1 instead, any
  67                                 //routine that needs to allocate memory must
  68                                 //quit if that's 1.
  69
  70
  71 // Variables which contain current byte to code and order
  72 unsigned long byte,     //current byte to code
  73      o1_byte, //order-1 byte
  74      o2_byte, //order-2 byte
  75      o3_byte, //order-3 byte
  76      o4_byte; //order-4 byte
  77
  78 unsigned long o2_cntxt;  //used in the hash key of order-2
  79 unsigned long o3_cntxt;  //use as hash key for order-3
  80 unsigned long o4_cntxt;  //use as hash key for order-4
  81 unsigned long full_o3_cntxt;   //o1_byte, o2_byte and o3_byte together
  82 unsigned long full_o4_cntxt;   //order-4-3-2-1
  83
  84 unsigned long coded_in_order;   //in which order the last byte was coded
  85                                 //it's for update exclusion
  86                                 //also used for decoding
  87
  88 // Variables used for coding
  89
  90 unsigned long
  91          total_cump,    //the total cumulative probability
  92          symb_cump,      //the symbol cumulative probability
  93          symb_prob;     //the symbol frequency
  94
  95 rangecoder rc_coder;    //state of range coder
  96 rangecoder rc_decoder;  //state of range decoder
  97
  98 // File handles
  99
 100  FILE *file_input,      //file to code
 101       *file_output;     //file where the coded data is placed
 102
 103
 104 // Pointers to linked lists and context structures used for faster updating
 105 // or creation of new nodes, because instead of reading again all the linked
 106 // list till the end (in the case of creation) we have a pointer to the last
 107 // element. In the case that a byte was present in the linked lists but it
 108 // had a 0 count, we just have to update its probability. And in the case
 109 // that it already was present and we coded it under that context or a lower
 110 // one, we just have to update its probability.
 111
 112 struct _byte_and_freq *o2_ll_node;      //pointer to linked lists under order-2
 113                                         //where does it points depends in which
 114                                         //order the byte was coded.
 115 struct _byte_and_freq *o3_ll_node;      //the same but for order-3
 116 struct _byte_and_freq *o4_ll_node;
 117
 118 struct context *o3_context;     //pointer to current order-3 context
 119 struct context *o4_context;     //pointer to current order-3 context
 120
 121
 122 // Those are the variables especially used for exclusion.
 123
 124 // the array for doing exclusion. Every routine from every order can
 125 // use them.
 126 unsigned char excluded[256];     //if 0 it was not present, if it's 1 then
 127                                  //it appeared in a higher order.
 128
 129 unsigned long exc_total_cump,   //total cump of context (after exclusion)
 130               exc_defined_bytes,//defined bytes in context (after exclusion)
 131               exc_max_cump;
 132