
#include <stdio.h>
#include <stdlib.h>
#include "RobboLito.h"
#include "RobboTripleBase.h"

int HopTable (uint32* TABLE, TypeSymbols* SYM)
{
  int c, HOP = 0;
  uint8 PREFISSO[256];
  uint32 SA[256];
  uint32 j, k, p, pr;
  for (c = 0; c < 256; c++)
    TABLE[c] = (1 << 24);
  for (c = 0; c < 256; c++)
    PREFISSO[c] = 0;
  for (c = 0; c < 0x100; c++)
    {
      if (!SYM[c].len)
	continue;
      if (SYM[c].len <= 8)
        for (k = SYM[c].bits; k < 256; k += (1 << SYM[c].len))
          TABLE[k] = c | (SYM[c].len << 24);
      else
        PREFISSO[SYM[c].bits & 0xff] = 1;
    }
  for (p = 0; p < 256; p++)
    if (PREFISSO[p])
      {
        SA[HOP] = p;
        TABLE[p] = HOP++;
      }
  for (j = 0; j < HOP; j++)
    {
      pr = SA[j];
      for (c = 0; c < 0x100; c++)
	{
	  if (!SYM[c].len)
	    continue;
	  if (pr == (SYM[c].bits & 255))
	    for (k = (SYM[c].bits >> 8); k < 256; k += (1 << (SYM[c].len - 8)))
	      TABLE[256 * (j + 1) + k] = c | (SYM[c].len << 24);
	}
    }
  TABLE [256 * (HOP + 1)] = 0x87654321; /* HACK */
  return 256 * (HOP + 1); /* size */
}

/********************************/ /* */ /********************************/

#define UINT64 uint64 /* HACK */
static UINT64 bi;

typedef struct
{
  int wt;
  int c1, c2;
} NODO;

typedef struct
{
  int lun;
  int va;
} bits;

typedef struct
{
  int c;
  int r;
} cr;

static int qsort_trie (const void *a, const void *b)
{
  cr *x, *y;
  x = (cr *) a;
  y = (cr *) b;
  if (x->c < y->c)
    return -1;
  if (x->c > y->c)
    return 1;
  return 0;
}

static int estr (char *s, int l)
{
  int x = 0;
  int i;
  for (i = 0; i < l; i++)
    {
      x <<= 1;
      if (s[i] == '1')
	x++;
    }
  return x;
}

static void trie (cr * T, NODO * U, int ue, char *s, int alt, bits * E)
{
  UINT64 w;
  s[alt] = '0';
  s[alt + 1] = 0;
  if (U[ue].c1 > 0)
    trie (T, U, U[ue].c1, s, alt + 1, E);
  else
    {
      w = T[-U[ue].c1].c;
      bi += (alt + 1) * w;
      E[T[-U[ue].c1].r].lun = alt + 1;
      E[T[-U[ue].c1].r].va = estr (s, alt + 1);
    }
  s[alt] = '1';
  s[alt + 1] = 0;
  if (U[ue].c2 > 0)
    trie (T, U, U[ue].c2, s, alt + 1, E);
  else
    {
      w = T[-U[ue].c2].c;
      bi += (alt + 1) * w;
      E[T[-U[ue].c2].r].lun = alt + 1;
      E[T[-U[ue].c2].r].va = estr (s, alt + 1);
    }
}

static void huffman (cr * T, int c, bits * E)
{
  int w, c1, c2, i, u = 1, t = 0, ue = 1, su = 0;
  char s[1024];
  NODO *U;
  qsort (T, c, sizeof (cr), qsort_trie);
  U = malloc ((c + 1) * sizeof (NODO));
  while (c - t + ue - u > 1)
    {
      if (ue == u || (t < c && T[t].c <= U[u].wt))
	{
	  c1 = -t;
	  t++;
	}
      else
	{
	  c1 = u;
	  u++;
	}
      if (ue == u || (t < c && T[t].c <= U[u].wt))
	{
	  c2 = -t;
	  t++;
	}
      else
	{
	  c2 = u;
	  u++;
	}
      U[ue].c1 = c1;
      U[ue].c2 = c2;
      if (c1 <= 0)
	w = T[-c1].c;
      else
	w = U[c1].wt;
      if (c2 <= 0)
	w += T[-c2].c;
      else
	w += U[c2].wt;
      U[ue].wt = w;
      ue++;
    }
  bi = 0;
  trie (T, U, ue - 1, s, 0, E);
  for (i = 0; i < c; i++)
    su += T[i].c;
  free (U);
}

static int INVERSO (int v, int l)
{
  int u = 0, i;
  for (i = 0; i < l; i++)
    if (v & (1 << i))
      u |= (1 << (l - 1 - i));
  return u;
}

int GetHuffmannData (uint8* DATA, int nb, TypeSymbols* SYMBOLS)
{
  int i, y = 0, LK[256], KL[256], B[256];
  cr Y[256];
  bits E[256];
  for (i = 0; i < 256; i++)
    B[i] = SYMBOLS[i].len = SYMBOLS[i].bits = 0;
  B[0x01] = B[0x41] = 1;  /* ensure 0x1 plus 0x41 */ /* HACK */
  for (i = 0; i < nb; i++)
    B[DATA[i]]++;
  y = 0;
  for (i = 0; i < 256; i++)
    Y[i].c = 0;
  for (i = 0; i < 256; i++)
    if (B[i])
      {
	LK[i] = y;
	KL[y] = i;
	Y[y].r = y;
	Y[y++].c = B[i];
      }
  while (TRUE)
    {
      int m = 0;
      huffman (Y, y, E);
      for (i = 0; i < y; i++)
	if (E[i].lun > m)
	  m = E[i].lun;
      if (m <= 16) /* HACK */
	break;
      for (i = 0; i < y; i++)
	Y[i].c = (1 + (Y[i].c >> 9)) << 8;
    }
  for (i = 0; i < y; i++)
    E[i].va = INVERSO (E[i].va, E[i].lun);

  for (i = 0; i < y; i++)
    {
      SYMBOLS[KL[i]].len = E[i].lun;
      SYMBOLS[KL[i]].bits = E[i].va;
    }
  return y;
}
