crblib/farithc.c
/*
 * FileArith Encoding using the generalized BitQueue
 *
 * encoding is done in the "trivial" manner - i.e. simple
 *  arithmetic is done.  No handling of underflow or overflow
 *  is needed, because we are just doing arithmetic.
 * bits are output as they become invariant (i.e. when
 *  MSBit(reglow) == MSBit(reglow+regrange) )
 * however, we also write a 0 bit out when they still have
 *  a chance of becoming a 1 later (aka underflow problem)
 * in order to handle this we keep a queue of bits between
 *  the arithcoder and the output, i.e. :
 *
 *  arithcoder -> queue -> output
 *
 * thus, if the arithcoder needs to add to a bit it has already
 *  sent, this may be done in the queue
 * the queue always has the form:
 *  01111... , i.e. a single zero bit followed by N one bits
 * Qlength counts the number of 1 bits plus the zero bit
 *  ( Qlength == 0 is an empty queue , Qlength == 1 is just a zero bit )
 * 
 * a 'carry' is handled by adding 1 to the Queue
 *
 * this changes 01111 to 10000 , at which time the queue may be sent 
 *
 * It is a property of arithmetic coding that if a carry reaches
 *  a certain position, no later carry may again reach that position.
 * It is this property which allows the Queue to be kept as such a
 *  simple form.
 *
 *   (btw this property comes very simply from the fact that the
 *    'range' - the number added to the coded - is constantly being
 *    shrunk (in our minds, anyway).  For the same bit to be reached
 *    again, we must add a range of the same value, but since the
 *    range is smaller, this cannot happen)
 *
 * note that the decoder is trivially simple, because the bits sent
 *  by the queue are identical to those that would have been sent
 *  had infinite precision coding been used.
 *
 * note also that it is possible to have a queue of the form
 *  1111 , (i.e. no leading zero) but we need not keep this data
 *  in the queue, because no carry-over will ever touch it.  Thus,
 *  any 1 bits sent to an empty queue may be flushed immediately.
 * (an empty queue is only created by a carry-over, so any 1 bits
 *  added to that queue cannot receive a carry because then that
 *  carry would be propagated through to a point which had
 *  already received a carry).
 * thus we need not track "QueueZeroFlag" as was originally 
 *  suggested in my VirtualQueue-SkewCoder paper
 *
 */
FileArith Encoding using the generalized BitQueue
encoding is done in the "trivial" manner - i.e. simple
arithmetic is done.  No handling of underflow or overflow
is needed, because we are just doing arithmetic.
bits are output as they become invariant  == MSBit(reglow+regrange) )
however, we also write a 0 bit out when they still have
a chance of becoming a 1 later (aka underflow problem)
in order to handle this we keep a queue of bits between
the arithcoder and the output, i.e.

> queue -> output

thus, if the arithcoder needs to add to a bit it has already
sent, this may be done in the queue
the queue always has the form:
01111...

a 'carry' is handled by adding 1 to the Queue

this changes 01111 to 10000 , at which time the queue may be sent

It is a property of arithmetic coding that if a carry reaches
a certain position, no later carry may again reach that position.
It is this property which allows the Queue to be kept as such a
simple form.

(btw this property comes very simply from the fact that the
'range' - the number added to the coded - is constantly being
shrunk (in our minds, anyway).  For the same bit to be reached
again, we must add a range of the same value, but since the
range is smaller, this cannot happen)

note that the decoder is trivially simple, because the bits sent
by the queue are identical to those that would have been sent
had infinite precision coding been used.

note also that it is possible to have a queue of the form
1111 ,  but we need not keep this data
in the queue, because no carry-over will ever touch it.  Thus,
any 1 bits sent to an empty queue may be flushed immediately.
(an empty queue is only created by a carry-over, so any 1 bits
added to that queue cannot receive a carry because then that
carry would be propagated through to a point which had
already received a carry).
thus we need not track "QueueZeroFlag" as was originally
suggested in my VirtualQueue-SkewCoder paper
FileArith Encoding using the generalized BitQueue encoding is done in the " trivial " manner - i . e . simple arithmetic is done . No handling of underflow or overflow is needed because we are just doing arithmetic . bits are output as they become invariant == MSBit ( reglow + regrange ) ) however we also write a 0 bit out when they still have a chance of becoming a 1 later ( aka underflow problem ) in order to handle this we keep a queue of bits between the arithcoder and the output i . e . > queue - > output thus if the arithcoder needs to add to a bit it has already sent this may be done in the queue the queue always has the form : 01111 ... a ' carry ' is handled by adding 1 to the Queue this changes 01111 to 10000 at which time the queue may be sent It is a property of arithmetic coding that if a carry reaches a certain position no later carry may again reach that position . It is this property which allows the Queue to be kept as such a simple form . ( btw this property comes very simply from the fact that the ' range ' - the number added to the coded - is constantly being shrunk ( in our minds anyway ) . For the same bit to be reached again we must add a range of the same value but since the range is smaller this cannot happen ) note that the decoder is trivially simple because the bits sent by the queue are identical to those that would have been sent had infinite precision coding been used . note also that it is possible to have a queue of the form 1111 but we need not keep this data in the queue because no carry - over will ever touch it . Thus any 1 bits sent to an empty queue may be flushed immediately . ( an empty queue is only created by a carry - over so any 1 bits added to that queue cannot receive a carry because then that carry would be propagated through to a point which had already received a carry ) . thus we need not track " QueueZeroFlag " as was originally suggested in my VirtualQueue - SkewCoder paper
void FileArithEncodeRange(struct FileAI * FileAI,long symlow,long symhigh,long symtot)
{
ulong lowincr;
register ulong regcode,regrange,regQlength;
register ulong reghalf = Half;
regcode    = FileAI->code;
regrange   = FileAI->range;
regQlength = FileAI->Qlength;
lowincr = ( regrange * symlow ) / symtot;
regcode += lowincr;
regrange = (( regrange * symhigh ) / symtot ) - lowincr;
if ( regcode & One )
  {
  regcode -= One; 
  FileBitIO_WriteBit(FileAI->BII,1);
  while ( --regQlength ) FileBitIO_WriteZeroBit(FileAI->BII);
  }
while( regrange <= Half )
  {
  if ( regcode >= reghalf )
    {
    if ( regQlength == 0 ) 
      {
      FileBitIO_WriteBit(FileAI->BII,1);
      }
    else
      {
      regQlength ++; 
      }
    regcode -= reghalf;
    }
  else
    {
    if ( regQlength )
      {
      FileBitIO_WriteZeroBit(FileAI->BII);
      while ( --regQlength ) FileBitIO_WriteBit(FileAI->BII,1);
      }
    regQlength = 1;
    }
  regcode  += regcode;
  regrange += regrange;
  }
FileAI->code  = regcode;
FileAI->range = regrange;
FileAI->Qlength = regQlength;
}
void FileArithEncodeRange ( struct FileAI * FileAI , long symlow , long symhigh , long symtot ) { ulong lowincr ; register ulong regcode , regrange , regQlength ; register ulong reghalf = Half ; regcode = FileAI -> code ; regrange = FileAI -> range ; regQlength = FileAI -> Qlength ; lowincr = ( regrange * symlow ) / symtot ; regcode += lowincr ; regrange = ( ( regrange * symhigh ) / symtot ) - lowincr ; if ( regcode & One ) { regcode -= One ; FileBitIO_WriteBit ( FileAI -> BII , 1 ) ; while ( -- regQlength ) FileBitIO_WriteZeroBit ( FileAI -> BII ) ; } while ( regrange <= Half ) { if ( regcode >= reghalf ) { if ( regQlength == 0 ) { FileBitIO_WriteBit ( FileAI -> BII , 1 ) ; } else { regQlength ++ ; } regcode -= reghalf ; } else { if ( regQlength ) { FileBitIO_WriteZeroBit ( FileAI -> BII ) ; while ( -- regQlength ) FileBitIO_WriteBit ( FileAI -> BII , 1 ) ; } regQlength = 1 ; } regcode += regcode ; regrange += regrange ; } FileAI -> code = regcode ; FileAI -> range = regrange ; FileAI -> Qlength = regQlength ; }
FileArith Encoding using the generalized BitQueue
 encoding is done in the "trivial" manner - i.e.
FileArith Encoding using the generalized BitQueue encoding is done in the " trivial " manner - i . e .
/* regrange *= (symhigh - symlow) / symtot ; */ /* we've added more to regcode than expected; now we must
    propagate a 'carry' into the already-queued bits */ /* Qlength never == 0 at this point */ /* turn off the One */ /* queue was 01111... , add one (carry) makes it 10000...

  FileBitIO_WriteBit(FileAI->BII,1); regQlength--;
  while ( regQlength-- ) FileBitIO_WriteZeroBit(FileAI->BII);

  however, a tad bit faster is:

  **/ /* FileBitIO_WriteBit(FileAI->BII,1); */ /* instead of writing a 1 bit directly, put it in the queue */ /* queue was 01..1 , make it 01..11 */ /* no leading zero */ /* tack a 1 on the queue */ /* FileBitIO_WriteZeroBit(FileAI->BII); */ /* instead of writing a 0 bit directly, put it in the queue */ /* queue was 01111 , make it 011110 , flush 01111 */ /* send old queue */ /* send one (0-bit) and (Qlength - 1) (1-bit)s */ /* now put a zero bit in the queue */