src/ppmc/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"
   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 // Those are the pointers and variables used for managing the mem pool for
  49 // both context, and bytes and frequencies.
  50 struct _byte_and_freq *_bytes_pool,     //pointer to pool containing linked
  51                       //lists with bytes and frequencies
  52                       *_bytes_pool_max; //the maximum of this buffer
  53                       struct context *_context_pool;          //pointer to pool containing contexts
  54                       struct context *_context_pool_max;      //the same as with _bytes_pool
  55
  56                       unsigned long _bytes_pool_index;        //index in array of pointers
  57                       unsigned long _context_pool_index;
  58
  59                       //the following is an array keeping pointers to different buffers. A new
  60                       //buffer is allocated when the current one is full, so we always have a
  61                       //buffer for linked lists. (without allocating a buffer for every element)
  62                       struct _byte_and_freq *_bytes_pool_array[_mempool_max_index];
  63                       struct context *_context_pool_array[_mempool_max_index];
  64
  65                       char ppmc_out_of_memory;        //0 if we have enough memory, 1 instead, any
  66                       //routine that needs to allocate memory must
  67                       //quit if that's 1.
  68
  69
  70                       // Variables which contain current byte to code and order
  71                       unsigned long byte,     //current byte to code
  72                       o1_byte, //order-1 byte
  73                       o2_byte, //order-2 byte
  74                       o3_byte, //order-3 byte
  75                       o4_byte; //order-4 byte
  76
  77 unsigned long o2_cntxt;  //used in the hash key of order-2
  78 unsigned long o3_cntxt;  //use as hash key for order-3
  79 unsigned long o4_cntxt;  //use as hash key for order-4
  80 unsigned long full_o3_cntxt;   //o1_byte, o2_byte and o3_byte together
  81 unsigned long full_o4_cntxt;   //order-4-3-2-1
  82
  83 unsigned long coded_in_order;   //in which order the last byte was coded
  84 //it's for update exclusion
  85 //also used for decoding
  86
  87 // Variables used for coding
  88
  89 unsigned long
  90 total_cump,    //the total cumulative probability
  91         symb_cump,      //the symbol cumulative probability
  92         symb_prob;     //the symbol frequency
  93
  94 rangecoder rc_coder;    //state of range coder
  95 rangecoder rc_decoder;  //state of range decoder
  96
  97 // File handles
  98
  99 FILE *file_input,      //file to code
 100      *file_output;     //file where the coded data is placed
 101
 102
 103 // Pointers to linked lists and context structures used for faster updating
 104 // or creation of new nodes, because instead of reading again all the linked
 105 // list till the end (in the case of creation) we have a pointer to the last
 106 // element. In the case that a byte was present in the linked lists but it
 107 // had a 0 count, we just have to update its probability. And in the case
 108 // that it already was present and we coded it under that context or a lower
 109 // one, we just have to update its probability.
 110
 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