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