A Rapid Entropy-Coding Algorithm
by Wm. Douglas Withers


Listing One
int b; 
int Threshold[10] = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256};
int A[] = Threshold+1; /* For expository purposes only */
FILE *external_in;
unsigned char x;
int decode_Bit(){
   if (x ( Threshold[b]){
       x-= Threshold[b];
       if (--b ( 0)
           decode_import();
       return 1;
   }else{
       if (- -b ( 0)
             decode_import();
       return 0;
   }
}
void decode_import(){
   x = fgetc(external_in);
    + =  8;
}

Listing Two
#define F 15
unsigned short A[2*F] = {1, 2, 3, 4, 5, 7, 10, 14, 20, 28, 41, 59, 85, 123, 177, 256, 371, 536, 776, 1123, 1625, 2353, 3405, 4928, 7132, 10321, 14938, 21619, 31288, 45283};

struct{
    unsigned short *Threshold;
    short c0;
    short c1; 
    } Ladder[3] = {{A+14, 1, 4}, {A+13, 2, 2}, {A+11, 4, 1}};
unsigned short x;
int j;
FILE *external_in;

int decode_bit(char rung){
     if (>= Ladder[rung].Threshold[j]){
       x -=  Ladder[rung].Threshold[j];
       if ((j -= Ladder[rung].c1) ( 0)
          decode_import();
       return 1;
     }else{
       if ((j -= Ladder[rung].c0) ( 0)
          decode_import();
       return 0;
     }
}
void decode_import(){
  j += F;
  x << = 8;
  x |= fgetc(external_in);
}

Listing Three
unsigned long x_min;
int j;
int n;
FILE *external_out;
void encode_bit(unsigned char rung, int bit){
   if (bit){
      /* Encode a 1 */
      x_min  +=  Ladder[rung].Threshold[j];
      j  -=  Ladder[rung].c1;
   }else{
      /* Encode a 0. */
      j  -=  Ladder[rung].c0;
   }
if (j ( 0)
      encode_export();
}

Listing Four
void encode_export(){
    unsigned long diff_bits;
    /* First check for bytes becoming postactive; diff_bits marks differences between max and min consistent values */
    j  +=  JPB;
    diff_bits = (x_min + A[j] - 1) ^ x_min;
    switch (n){
    default: /* 2 or greater */
        if (diff_bits&0xFF000000)
        break;
    fputc(x_min>>24, external_out);
    while (-- n > 1)
    fputc((x_min>>16)&0xFF, external_out);
case 1:
    if (diff_bits & 0x00FF0000)
        break;
    fputc((x_min>>16)&0xFF, external_out);
    n -- ;
case 0:
    if (diff_bits & 0x0000FF00)
        break;
    fputc((x_min>>8) & 0xFF, external_out);
    n --;
    }
}
/* Move a byte from preactive to active. */
if (++ n > 2)
   x_min = (x_min&0xFF000000)| ((x_min&0x0000FFFF)<< 8);
else
   x_min <<= 8;
}

1


