/*
   file pi_opt.c
   (C) 2003 Yann GUIDON <whygee@f-cpu.org>
   version Sat Dec 27 11:32:09 CET 2003

   Bitstream insertion/extraction with phasing-in
   codes, used by the Range Reduction and 3R algorithms.
   This is a faster, inlined, optimised version.

   "range" and "high" are both used to avoid
   computing a value that is available somewhere else,
   and their coherency is not checked.
*/

#include <stdio.h>   /* for printf */

/* some global data */
unsigned int stream_length; /* number of bytes */
unsigned int shift_count;   /* number of bits in the reservoir */
unsigned int reservoir;     /* bit accumulator */
unsigned char * stream;


/* The bit insertion routine */
void pi_put_bits(unsigned int data,   /* to be encoded */
                 unsigned int range,  /* number of bits */
                 unsigned int high) { /* maximal value of data + 1 */
  unsigned int t, nb_bits, range2;
  unsigned int pi_trig; /* phasing-in variables */
    signed int pi_var, i;

  printf("Encoding data=%d with high=%d and range=%d",
     data, high, range);

  if (range < 1) {
    printf(" [range < 1]\n");
    return;
  }

  range2 = range - 1;

  /* pi_trig = B = 2^k - b = 2^(k+1) - i */
  pi_trig = (1U << range) - high;
  pi_var = data - pi_trig; /* i - B */

  /* create the phasing-in code: */
  if (pi_var < 0) { /* short code */
    printf(" [-] ");
    nb_bits = range2;
    t = data;
  }
  else { /* long code */
    printf(" [+] ");
    nb_bits = range;
/* Here, the LSB is put in the MSB (rotated) because otherwise
 the decoder would hang when asking for the additional bit !! */
    t = ((pi_var >> 1) + pi_trig)
      | ((pi_var & 1) << range2);
  }

  /* print the number in binary format */
  i=nb_bits-1;
  do {
    putchar(((t >> (i--)) & 1) | '0');
  } while (i >= 0);
  putchar('\n');

  /* merge the input data and the reservoir */
  reservoir |= (t << shift_count);
  shift_count += nb_bits;

  /* sends the bit accumulator, byte per byte */
  while (shift_count >= 8) {
    stream[stream_length++] = reservoir;
    reservoir >>= 8;
    shift_count -= 8;
  }

  /* remove some eventual garbage */
  reservoir &= (1U << shift_count) - 1;
}


/* The bit extraction routine */
unsigned int pi_get_bits(
    unsigned int range,  /* number of bits */
    unsigned int high) { /* maximal value of data + 1 */

  unsigned int result, range2, nb_bits;
  unsigned int pi_trig;  /* phasing-in variables */
    signed int pi_var;

  printf("Decoding with high=%d and range=%d, ", high, range);

  if (range < 1) {
    printf("[ range<1 -> result=0 ]\n");
    return 0; /* shortcut */
  }

  nb_bits = range;
  range2 = range - 1;

  /* speculatively load "range" bits */
  while (shift_count < range) {
    reservoir |= stream[stream_length++] << shift_count;
    shift_count += 8;
  }

  result = reservoir & ((1U << range2) - 1);

  /* pi_trig = B = 2^k - b = 2^(k+1) - i */
  pi_trig = (1U << range) - high;
  pi_var = result - pi_trig; /* i - B */

  if (pi_var < 0) { /* short code */
    printf(" [-] ");
    nb_bits = range2;
  }
  else { /* long code */
    printf(" [+] ");
    nb_bits = range;
    result = (pi_var << 1) + pi_trig +
           + ((reservoir >> range2) & 1);
    nb_bits = range;
  }

  reservoir >>= nb_bits;
  shift_count -= nb_bits;

  printf(" result=%u\n", result);

  return result;
}