examples/ppmc/exclusion/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" (exclusion)
   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
  25 /*
  26   Inits the range coder state. Must be called before encoding any symbol.
  27   It uses a magic number 0xB3 as the first byte outputted.
  28   -rangecoder *rc, the range coder to be used.
  29
  30   Shoulde be called like that:
  31   range_coder_init(&o0_rc_state,file_output);
  32 */
  33 void range_coder_init(rangecoder *rc, FILE *stream)
  34 {
  35  rc_file=stream;
  36  rc->low=0;     //define state
  37  rc->range=0x80000000;
  38  rc->byte_buffer=0xB3;  //magic number
  39  rc->help=0;            //temp value
  40 }
  41
  42
  43 /*
  44   Encodes a symbol.
  45   -rangecoder *rc, the range coder to be used.
  46   -unsigned long tot_f, the maximum cumulative frequency
  47   -unsigned long lt_f, the cumulative probabilty of the symbol
  48   -unsigned long sy_f, the probability of the symbol
  49 */
  50 void range_coder_encode(rangecoder *rc,unsigned long tot_f, unsigned long lt_f,unsigned long sy_f)
  51 {
  52  unsigned long temp, r;
  53
  54  if(lt_f>tot_f)
  55    {
  56    printf("BUG!!");
  57    exit(1);
  58    }
  59
  60 // printf("\nc> %d,%d,%d  ",tot_f,lt_f,sy_f);
  61
  62  range_coder_renormalize(rc);   //&rc?
  63
  64  r=rc->range/tot_f;
  65  temp=r*lt_f;
  66  if(lt_f+sy_f<tot_f)
  67    rc->range=r*sy_f;
  68  else
  69    rc->range-=temp;
  70  rc->low+=temp;
  71 }
  72
  73 /*
  74   Renormalizes the state when coding.
  75   -rangecoder *rc, the range coder to be used.
  76 */
  77
  78 void range_coder_renormalize(rangecoder *rc)
  79 {
  80  while(rc->range<=(unsigned long)0x00800000)
  81    {
  82    if(rc->low<(unsigned long)0x7F800000)
  83      {
  84      putc(rc->byte_buffer,rc_file);
  85      for(;rc->help;rc->help--)
  86        putc(0xFF,rc_file);
  87      rc->byte_buffer=(unsigned char)(rc->low>>23);
  88      }
  89    else
  90      {
  91      if(rc->low&(unsigned long)0x80000000)
  92        {
  93        putc(rc->byte_buffer+1,rc_file);
  94        for(;rc->help;rc->help--)
  95          putc(0x00,rc_file);
  96        rc->byte_buffer=(unsigned char)(rc->low>>23);
  97        }
  98      else
  99        rc->help++;
 100      }
 101    rc->range<<=8;
 102    rc->low=(rc->low<<8)&(unsigned long)(0x7FFFFFFF);
 103    }
 104 }
 105
 106
 107 /*
 108   Flushes the encoder. Must be called when the coding is done.
 109   -rangecoder *rc, the range coder to be used.
 110
 111   Shoulde be called like that:
 112   range_coder_flush(&o0_rc_state);
 113 */
 114 void range_coder_flush(rangecoder *rc)
 115 {
 116  unsigned long tmp;
 117
 118  range_coder_renormalize(rc);
 119  tmp = rc->low >> 23;
 120  if (tmp > 0xff)
 121    {
 122    putc(rc->byte_buffer+1,rc_file);
 123    for(; rc->help; rc->help--)
 124      putc(0,rc_file);
 125    }
 126  else
 127    {
 128    putc(rc->byte_buffer,rc_file);
 129    for(; rc->help; rc->help--)
 130      putc(0xff,rc_file);
 131    }
 132
 133  putc(tmp & 0xff,rc_file);
 134  putc((tmp = rc->low >> (23-8)) & 0xff,rc_file);
 135 }
 136
 137
 138 /*
 139   Inits the range decoder state. Also checks for the magic number, and
 140   quits in case it isn't the first, so be careful.
 141   -rangecoder *rc, the range coder to be used.
 142 */
 143 void range_decoder_init(rangecoder *rc, FILE *stream)
 144 {
 145  unsigned int _rd_c;
 146
 147  rc_file=stream;
 148  if((_rd_c=getc(rc_file))!=0xB3)
 149    {
 150    printf("\nThis is not range coded data. Magic number not found. Exiting.");
 151    exit(1);
 152    }
 153  rc->byte_buffer=getc(rc_file);
 154  rc->low=rc->byte_buffer>>1;
 155  rc->range=0x80;
 156 }
 157
 158
 159 /*
 160   Decode a symbol, get its cumulative probability.
 161   Input:
 162   -rangecoder *rc, the range coder to be used.
 163   -unsigned long tot_f, the maximum cumulative probability
 164   Output:
 165   -unsigned long, cumulative probability of the current symbol
 166   Should be called like that:
 167    current_cump=range_decoder_decode(&o0_rc_state,o0_tot_f);
 168 */
 169 unsigned long range_decoder_decode(rangecoder *rc, unsigned long tot_f)
 170 {
 171  unsigned long temp;
 172
 173  range_decoder_renormalize(rc);
 174  rc->help=rc->range/tot_f;
 175  temp=rc->low/rc->help;
 176  if(temp>=tot_f)
 177    return tot_f-1;
 178  else
 179    return temp;
 180 }
 181
 182
 183 /*
 184   Updates the state so next symbol can be decoded.
 185   Input:
 186   -rangecoder *rc, the range coder to be used.
 187   -unsigned long tot_f, the maximum cumulative probability
 188   -unsigned long lt_f, the cumulative probabilty of the symbol
 189   -unsigned long sy_f, the probability of the symbol
 190
 191 */
 192 void range_decoder_update(rangecoder *rc, unsigned long tot_f, unsigned long lt_f,unsigned long sy_f)
 193 {
 194  unsigned long temp;
 195
 196 // printf("\nd> %d,%d,%d  ",tot_f,lt_f,sy_f);
 197
 198  temp=rc->help*lt_f;
 199  rc->low-=temp;
 200  if(lt_f+sy_f<tot_f)
 201    rc->range=rc->help*sy_f;
 202  else
 203    rc->range-=temp;
 204 }
 205
 206
 207 /*
 208   Renormalizes the state while decoding.
 209   -rangecoder *rc, the range coder to be used.
 210 */
 211 void range_decoder_renormalize(rangecoder *rc)
 212 {
 213  while(rc->range<=0x00800000)
 214    {
 215    rc->low=(rc->low<<8)|((rc->byte_buffer<<7)&0xFF);
 216    rc->byte_buffer=getc(rc_file);
 217    rc->low |= rc->byte_buffer >> (1);
 218    rc->range<<=8;
 219    }
 220 }
 221