/*
   file rr_simple.c
   (C) 2003 Yann GUIDON <whygee@f-cpu.org>
   version Thu Dec 25 05:28:38 CET 2003

   Example source code for the simple
   Range Reduction encoder/decoder
*/

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

#include "bitstream.c"

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

  printf("\nEncoding %d elements : size=", nb_elements);

  u = t = list[0];

  /* count the number of significant bits */
  while (u > 0) {
    u >>= 1;
    range++;
  }

  /* output the size prefix */
  put_bits(5, range);

  if (range > 0) {
    /* the first number's MSB is
       implicit and discarded : */
    printf("0: ");
    put_bits(range-1, t);

    mask = 1 << (range - 1);

    while (i < nb_elements) {
      printf("%d: ", i);
      t = list[i++];
      put_bits(range, t);

      /* reduce the range */
      while ((t & mask) == 0) {
        range--;
        if (range == 0) {
          printf("[the remaining zeroes are skipped]\n");
          return;
        }
        mask >>= 1;
      }
    }
  }
}

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

  printf("\nDecoding %d elements : size=", nb_elements);

  range = get_bits(5);

  if (range > 0) {
/* get the first word and restore the implicit MSB */
    printf("\n0: ");
    list[0] = get_bits(range-1) | (1 << (range-1));

    mask = 1 << (range - 1);

    while (i<nb_elements) {
      printf("\n%d: ", i);
      t = get_bits(range);
      list[i++] = t;

      /* range reduction */
      while ((t & mask) == 0) {
        range--;

/* clear the rest, in case it was not initialized */
        if (range == 0) {
          if (i < nb_elements) {
            printf("[clearing the rest of the destination]\n");
            memset(&list[i], 0,
               (nb_elements - i) * sizeof(*list));
          }
          return;
        }

        mask >>= 1;
      }
    }
  }
  else {
    memset(&list[0], 0, nb_elements * sizeof(*list));
  }
}