/*******************************************************************************
 *
 * Simple LZ77 compressor (c) Texas Instruments, Jesper Pedersem TI-DK    
 *                                                                        
 * File format:                                                          
 * ---------------------------------------------------                   
 * | Tag |   Data   | Tag |   Data   | Tag |   Data    etc...            
 * ---------------------------------------------------                   
 *                                                                        
 * Where TAG is 1 bit indicating how to interpret the following data
 * (0 = uncompressed, 1 = compressed)
 *                                                                        
 * Depending on TAG the Data is:                                         
 *   0 : One uncompressed char of raw data                                
 *   1 : A length of and a pointer to a match in the previous data
 *
 *                    ----------------------------------------        
 * Length + pointer = | Length (3 bits) | Position (12 bits) |        
 *                    ----------------------------------------        
 *                     MSB           LSB MSB              LSB         
 *                                                                        
 * Compression threshold is 1 i.e. add 1 to Length to get the actual Length.
 *                                                                        
 * It has been found that 5+14 bits is the most optimum for our kind of
 * data, but we use only 3+12 bits for improoved speed.  Compression is
 * almost as good because we can set the threshold at 1 instead of 2 (2 char
 * matches can be compressed to 12+3 bits)
 *                                                                        
 * With a 12 bit position we can use 4K for the sliding window.  Position
 * indicates where the match exists as an absolute address into the
 * window. This way we have a very simple "pseudo sliding window" which
 * automatically enables RLE (Run Length Encoding).
 *                                                                        
 * The code performs a "lazy" string search i.e. a match will be dropped if
 * it prevents an even greater match for the very next string. This yeild
 * slightly better compression (approx. 1%) at minor cost of compression
 * speed - decompression time is the same!  A second order lazy match could
 * be implemented, but it gives an insignificant improovement of about 0.1%
 * when compressing executeables
 *                                                                        
 ******************************************************************************/

#if (TARGET == 0)
#include "fluid.h"
#include <stdlib.h>
#endif

#include "lz.h"


/******************************************************************************
 * Globals
 ******************************************************************************/


/******************************************************************************
 * getchar/putchar
 ******************************************************************************/

#define EOF -1

#define LZ_PUTCHAR(data) \
    *plz->buffer_out++ = data; \
    plz->buffer_out_size++;



/******************************************************************************
 * Code
 ******************************************************************************/
uint8 get_byte(struct lz_s *plz)
{
  plz->buffer_in_size--;
  return(*plz->buffer_in++);
}

uint16 get_word(struct lz_s *plz)
{
  uint16 tmp;

  tmp =  (*plz->buffer_in++) << 8;
  tmp |= (*plz->buffer_in++);
  plz->buffer_in_size -= 2;
  return(tmp);
}


void decompress_init(struct lz_s *plz)
{
    plz->window_pos  = 0;
    plz->bitbuf      = 0;
    plz->bitbuf_size = 0;
}

int decompress(struct lz_s *plz,
               unsigned char *outbuf, unsigned char *inbuf, int size)
{
    int16 match_pos;
    int16 match_len, i;
    int8  ch;
    uint8 tag_byte;
    uint8 tag_pos;
    uint16 tmp;


    plz->buffer_out      = outbuf;
    plz->buffer_out_size = 0;
    plz->buffer_in       = inbuf;
    plz->buffer_in_size  = size;

    while(plz->buffer_in_size > 0)
    {
        tag_byte = get_byte(plz);

        for(tag_pos = 0x80; (plz->buffer_in_size > 0) && (tag_pos > 0x00); tag_pos >>= 0x01)
        {
          if(tag_byte & tag_pos) // Compressed?
          {
            tmp    = get_word(plz);
            match_len = (tmp >> POS_BITS) + THRESHOLD + 1;
            match_pos = (tmp & POS_MASK);
            for (i = 0; i < match_len; i++) 
            {
              plz->window[plz->window_pos] = plz->window[WINDOW_MASK & (match_pos + i)];
              LZ_PUTCHAR(plz->window[plz->window_pos]);
              plz->window_pos++;
              plz->window_pos &= WINDOW_MASK;
            }
          }
          else
          {
            ch = get_byte(plz);
            plz->window[plz->window_pos] = ch;
            LZ_PUTCHAR(ch);
            plz->window_pos++;
            plz->window_pos &= WINDOW_MASK;
          }
        }
    }
    return plz->buffer_out_size;
}