/* -*- Mode: C; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/*******************************************************************************
 *              Copyright 2000,2001,2002,2003 Element 14 Inc                   *
 *                                                                             *
 * This material is the confidential trade secret and proprietary information  *
 * of Element 14 Inc.  It may not be reproduced, used, sold or transferred to  *
 * any third party  without the prior written  consent of Element 14 Inc. All  *
 * rights reserved.                                                            *
 *                                                                             *
 ******************************************************************************/

/* $Id: bcm_lz77.c,v 1.2 2004/11/10 14:32:25 eduymeli Exp $  */

#include <string.h>
#include "bcm_lz77.h"
#include <stdio.h>

/*bits/symbol*/
#define CHARBITS 8

/* minimum match length & maximum match length */
#define THRESHOLD 2
#define MATCHBITS 4
#define MAXMATCH ((1<<MATCHBITS) + THRESHOLD - 1)

/* sliding dictionary size*/
#define DICTBITS 14
#define DICTSIZE (1<<DICTBITS)

/* CAUTION: no simultaneous access possible */
static uint32 bitbuf = 0;
static uint32 bitsin = 0;
static uint8 dict[DICTSIZE + MAXMATCH];

int Lz77_step(Lz77 *self);

void Lz77_init(Lz77 *self, uint8 *data) {
  memset(self, 0, sizeof(Lz77));
  self->data = data;
  self->currPtr = self->data;
}

static uint32 Lz77_getBits(Lz77 *self, uint32 numBits) {
  uint32 i = bitbuf >> (8-bitsin);
  while (numBits > bitsin) {
    bitbuf = (uint32)*(self->currPtr++);
    i |= bitbuf << bitsin;
    bitsin += 8;
  }

  bitsin -= numBits;
  return (i & ((1<<numBits)-1));
}

static void Lz77_outCopy(Lz77 *self, int length) {
  self->i = 0; /* reuse for counter in getByte */
  self->dataAvailable = length;
}

int Lz77_getByte(Lz77 *self, uint8 *data) {
  while (!self->dataAvailable && !self->done) {
    self->done = Lz77_step(self);
  }
  if (self->dataAvailable) {
    *data = dict[self->i++];
    self->dataAvailable--;
    if (self->dataAvailable == 0) {
      /* reuse for counter in step */
      self->i = 0;
    }
  }
  return self->done && !self->dataAvailable;
}

int Lz77_step(Lz77 *self) {

  if (self->done) {
    return 1;
  }

  if (!self->longCopy && Lz77_getBits(self, 1) == 0) /*char or match?*/ {
    dict[self->i++] = (uint8)Lz77_getBits(self, CHARBITS);
    if (self->i == DICTSIZE) {
      Lz77_outCopy(self, DICTSIZE);
    }
  }
  else {

    /*Get match length*/
    if (!self->longCopy) {
      self->k = (THRESHOLD + 1) + Lz77_getBits(self, MATCHBITS);
      
      if (self->k == (MAXMATCH + 1)) {
        Lz77_outCopy(self, self->i);
        return 1;
      }
    
      /*Get match position*/
      self->j = ((self->i - Lz77_getBits(self, DICTBITS)) & (DICTSIZE - 1));
    }

    if (self->longCopy || (self->i+self->k) >= DICTSIZE) {
      /* if longCopy == TRUE we fall through all ifs and continue 
         the loop which was going on */
      dict[self->i++] = dict[self->j++];
      self->j &= (DICTSIZE - 1);
      if (self->i == DICTSIZE) {
        Lz77_outCopy(self, DICTSIZE);
      }
      if (--self->k) {
        self->longCopy = TRUE;
      }
      else {
        self->longCopy = FALSE;
      }
      return 0;
    }
    else {
      if ((self->j+self->k) >= DICTSIZE) {
        do {
          dict[self->i++] = dict[self->j++];
          self->j &= (DICTSIZE - 1);
        } while (--self->k);
      }
      else {
        do {
          dict[self->i++] = dict[self->j++];
        } while (--self->k);
      }
    }
  }
  return 0;
}

