src/ppmc/range.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: "range.c"
   7 Email: arturo@arturocampos.com
   8 Web: http://www.arturocampos.com
   9
  10 This module contains the routines of both the range coder and decoder.
  11
  12 The range coder works internally in 32 bits, and uses bytes as symbols.
  13 Also the end of message symbol is used. So z=257.
  14
  15 Both input and output use rc_file as the file stream. Of course we can't
  16 code and decode at the same time. All the input or output comes from the
  17 same file, no matter what range coder structure are we using. The modules
  18 here provided don't manage the io except for reading and writing, they
  19 don't open nor close the files. The reading and writing is done via
  20 putc and getc.
  21 */
  22
  23 #include "range.h"
  24 #include <stdlib.h>
  25
  26 /*
  27    Inits the range coder state. Must be called before encoding any symbol.
  28    It uses a magic number 0xB3 as the first byte outputted.
  29    -rangecoder *rc, the range coder to be used.
  30
  31    Shoulde be called like that:
  32    range_coder_init(&o0_rc_state,file_output);
  33    */
  34 void range_coder_init(rangecoder *rc, FILE *stream)
  35 {
  36         rc_file=stream;
  37         rc->low=0;     //define state
  38         rc->range=0x80000000;
  39         rc->byte_buffer=0xB3;  //magic number
  40         rc->help=0;            //temp value
  41 }
  42
  43
  44 /*
  45    Encodes a symbol.
  46    -rangecoder *rc, the range coder to be used.
  47    -unsigned long tot_f, the maximum cumulative frequency
  48    -unsigned long lt_f, the cumulative probabilty of the symbol
  49    -unsigned long sy_f, the probability of the symbol
  50    */
  51 void range_coder_encode(rangecoder *rc,unsigned long tot_f, unsigned long lt_f,unsigned long sy_f)
  52 {
  53         unsigned long temp, r;
  54
  55         range_coder_renormalize(rc);   //&rc?
  56
  57         r=rc->range/tot_f;
  58         temp=r*lt_f;
  59         if(lt_f+sy_f<tot_f)
  60                 rc->range=r*sy_f;
  61         else
  62                 rc->range-=temp;
  63         rc->low+=temp;
  64 }
  65
  66 /*
  67    Renormalizes the state when coding.
  68    -rangecoder *rc, the range coder to be used.
  69    */
  70
  71 void range_coder_renormalize(rangecoder *rc)
  72 {
  73         while(rc->range<=(unsigned long)0x00800000)
  74         {
  75                 if(rc->low<(unsigned long)0x7F800000)
  76                 {
  77                         putc(rc->byte_buffer,rc_file);
  78                         for(;rc->help;rc->help--)
  79                                 putc(0xFF,rc_file);
  80                         rc->byte_buffer=(unsigned char)(rc->low>>23);
  81                 }
  82                 else
  83                 {
  84                         if(rc->low&(unsigned long)0x80000000)
  85                         {
  86                                 putc(rc->byte_buffer+1,rc_file);
  87                                 for(;rc->help;rc->help--)
  88                                         putc(0x00,rc_file);
  89                                 rc->byte_buffer=(unsigned char)(rc->low>>23);
  90                         }
  91                         else
  92                                 rc->help++;
  93                 }
  94                 rc->range<<=8;
  95                 rc->low=(rc->low<<8)&(unsigned long)(0x7FFFFFFF);
  96         }
  97 }
  98
  99
 100 /*
 101    Flushes the encoder. Must be called when the coding is done.
 102    -rangecoder *rc, the range coder to be used.
 103
 104    Shoulde be called like that:
 105    range_coder_flush(&o0_rc_state);
 106    */
 107 void range_coder_flush(rangecoder *rc)
 108 {
 109         unsigned long tmp;
 110
 111         range_coder_renormalize(rc);
 112         tmp = rc->low >> 23;
 113         if (tmp > 0xff)
 114         {
 115                 putc(rc->byte_buffer+1,rc_file);
 116                 for(; rc->help; rc->help--)
 117                         putc(0,rc_file);
 118         }
 119         else
 120         {
 121                 putc(rc->byte_buffer,rc_file);
 122                 for(; rc->help; rc->help--)
 123                         putc(0xff,rc_file);
 124         }
 125
 126         putc(tmp & 0xff,rc_file);
 127         putc((tmp = rc->low >> (23-8)) & 0xff,rc_file);
 128 }
 129
 130
 131 /*
 132    Inits the range decoder state. Also checks for the magic number, and
 133    quits in case it isn't the first, so be careful.
 134    -rangecoder *rc, the range coder to be used.
 135    */
 136 void range_decoder_init(rangecoder *rc, FILE *stream)
 137 {
 138         unsigned int _rd_c;
 139
 140         rc_file=stream;
 141         if((_rd_c=getc(rc_file))!=0xB3)
 142         {
 143                 printf("\nThis is not range coded data. Magic number not found. Exiting.");
 144                 exit(1);
 145         }
 146         rc->byte_buffer=getc(rc_file);
 147         rc->low=rc->byte_buffer>>1;
 148         rc->range=0x80;
 149 }
 150
 151
 152 /*
 153    Decode a symbol, get its cumulative probability.
 154 Input:
 155 -rangecoder *rc, the range coder to be used.
 156 -unsigned long tot_f, the maximum cumulative probability
 157 Output:
 158 -unsigned long, cumulative probability of the current symbol
 159 Should be called like that:
 160 current_cump=range_decoder_decode(&o0_rc_state,o0_tot_f);
 161 */
 162 unsigned long range_decoder_decode(rangecoder *rc, unsigned long tot_f)
 163 {
 164         unsigned long temp;
 165
 166         range_decoder_renormalize(rc);
 167         rc->help=rc->range/tot_f;
 168         temp=rc->low/rc->help;
 169         if(temp>=tot_f)
 170                 return tot_f-1;
 171         else
 172                 return temp;
 173 }
 174
 175
 176 /*
 177    Updates the state so next symbol can be decoded.
 178 Input:
 179 -rangecoder *rc, the range coder to be used.
 180 -unsigned long tot_f, the maximum cumulative probability
 181 -unsigned long lt_f, the cumulative probabilty of the symbol
 182 -unsigned long sy_f, the probability of the symbol
 183
 184 */
 185 void range_decoder_update(rangecoder *rc, unsigned long tot_f, unsigned long lt_f,unsigned long sy_f)
 186 {
 187         unsigned long temp;
 188
 189         temp=rc->help*lt_f;
 190         rc->low-=temp;
 191         if(lt_f+sy_f<tot_f)
 192                 rc->range=rc->help*sy_f;
 193         else
 194                 rc->range-=temp;
 195 }
 196
 197
 198 /*
 199    Renormalizes the state while decoding.
 200    -rangecoder *rc, the range coder to be used.
 201    */
 202 void range_decoder_renormalize(rangecoder *rc)
 203 {
 204         while(rc->range<=0x00800000)
 205         {
 206                 rc->low=(rc->low<<8)|((rc->byte_buffer<<7)&0xFF);
 207                 rc->byte_buffer=getc(rc_file);
 208                 rc->low |= rc->byte_buffer >> (1);
 209                 rc->range<<=8;
 210         }
 211 }
 212