/*
   file rr_phasing-in.c
   (C) 2003 Yann GUIDON <whygee@f-cpu.org>
   version Sat Dec 27 11:47:02 CET 2003

   Source code for the Range Reduction
   encoder/decoder using phasing-in codes.
*/

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

#ifndef OPT
#include "phasing-in.c"
#else
#include "pi_opt.c"
#endif

/* The encoding routine : */

void encode_RR(unsigned int nb_elements,
               unsigned int *list) {
    signed int range = 0;
  unsigned int i = 1, t, u, mask, high;

  printf("\nEncoding %d numbers:\nprefix:\n", nb_elements);

  /* create the header */
  u = t = list[0];

  /* count the number of significant bits */
  while (u > 0) {
    u >>= 1;  /* a binary search */
    range++;  /* should be faster... */
  }

  /* output the size prefix with a phasing-in code :
     maximal values are 24-bit */
  pi_put_bits(range, 5, 25);

  if (range > 0) {
    /* the first number's MSB is implicit and discarded : */
    printf("Initial number (without MSB):\n");
    mask = 1U << (range - 1);

    pi_put_bits(t & ~mask, range - 1, mask);

    /* Start the main loop */

    while (i < nb_elements) {
      high = t + 1;
      t = list[i++];  /* get a new value to encode */
      pi_put_bits(t, range, high);

      /* reduce the range */
      while ((t & mask) == 0) {
        range--;
        mask >>= 1;
        if (mask == 0) {
          return;
        }
      }
    }
  }
}

/* The decoding routine : */

void decode_RR(unsigned int nb_elements,
               unsigned int *list) {
  unsigned int t, mask, i = 1, range;

  printf("\nDecoding %d numbers:\nprefix:\n", nb_elements);

  /* get the size prefix */
  range = pi_get_bits(5, 25);

  if (range > 0) {
    mask = 1U << (range -1);

    /* get the first word and restore the implicit MSB */
    printf("Initial number (without MSB):\n");
    t = pi_get_bits(range - 1, mask) | mask;
    list[0] = t;

    while (i<nb_elements) {
      t = pi_get_bits(range, t + 1);
      list[i++] = t;

      /* range reduction */
      while ((t & mask) == 0) {
        range--;
        mask >>= 1;
        if (mask == 0) {
          if (i < nb_elements)
            /* clear the rest, in case it was not initialized */
            memset(&list[i], 0, (nb_elements - i) * sizeof(*list));
          return;
        }
      }
    }
  }
  else {
    memset(&list[0], 0, nb_elements * sizeof(*list));
  }
}