/*
 *  Copyright (C) 2013-2019 Cisco Systems, Inc. and/or its affiliates. All rights reserved.
 *  Copyright (C) 2008-2013 Sourcefire, Inc.
 *
 *  Authors: Alberto Wu
 * 
 *  Acknowledgements: Written from scratch based on specs from PKWARE:
 *                    http://www.pkware.com/documents/casestudies/APPNOTE.TXT
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License version 2 as
 *  published by the Free Software Foundation.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 *  MA 02110-1301, USA.
 */

/* 
 * Written from scratch based on specs from PKWARE:
 * see www.pkware.com/documents/casestudies/APPNOTE.TXT
 *
 * To the best of my knowledge, it's patent free:
 * http://www.unisys.com/about__unisys/lzw
*/


/* To Cami and Dario, the only lawyers I can stand */


#if HAVE_CONFIG_H
#include "clamav-config.h"
#endif

#if HAVE_STRING_H
#include <string.h>
#endif

#include "clamav.h"
#include "explode.h"
#include "others.h"

/* NOTE: sorting algo must be stable! */
static void bs(uint8_t *k, uint8_t *v, unsigned int elements) {
  uint8_t tmp;
  unsigned int i=0, l=0, stop=0, r=elements;
  
  while(!stop) {
    stop=1;
    for(; i<r; i++) {
      if(v[k[i]]>v[k[i+1]]) {
	tmp=k[i];
	k[i]=k[i+1];
	k[i+1]=tmp;
	stop=0;
      }
    }
    if(stop) break;
    r--;
    i--;
    for(; i>l; i--) {
      if(v[k[i]]<v[k[i-1]]) {
	tmp=k[i];
	k[i]=k[i-1];
	k[i-1]=tmp;
	stop=0;
      }
    }
    l++;
    i++;
  }
}


static int unpack_tree(struct xplstate *X, uint32_t *tree, unsigned int expected) {
  uint8_t temptree[256], order[256], *ttree=temptree;
  uint8_t *cur=X->window;
  uint8_t packsz;
  unsigned int i;
  uint16_t code=0, codeinc=0, lastlen=0;

  packsz=*cur++;

  for(i=0; i<expected; i++) order[i]=i;

  i=expected;

  do {
    uint8_t values, len;
    values = *cur++;
    len = (values&15) + 1;
    values = (values>>4) + 1;
    if(values>i) return 1;
    i-=values;
    while(values--)
      *ttree++ = len;
  } while(packsz--);

  if(i) return 1;

  bs(order, temptree, expected-1);

  i=expected-1;
  do {
    code=code+codeinc;
    if(temptree[order[i]]!=lastlen) {
      lastlen=temptree[order[i]];
      codeinc=1<<(16-lastlen);
    }
    tree[order[i]]=code | ((uint32_t)lastlen<<16);
  } while(i--);

  return 0;
}

/* bit lame of a lookup, but prolly not worth optimizing */
static int lookup_tree(uint32_t *tree, unsigned int size, uint16_t code, uint8_t len) {
  uint32_t lookup=((uint32_t)(len+1))<<16 | code;
  unsigned int i;
  for(i=0; i<size; i++)
    if(tree[i]==lookup) return i;
  return -1;
}

int explode_init(struct xplstate *X, uint16_t flags) {
  X->bits = X->cur = 0;
  if(flags&2) {
    X->largewin = 1;
    X->mask = 0x1fff;
  } else {
    X->largewin = 0;
    X->mask = 0xfff;
  }
  if(flags&4) {
    X->state = GRABLITS;
    X->litcodes = 1;
    X->minlen=3;
  } else {
    X->state = GRABLENS;
    X->litcodes = 0;
    X->minlen=2;
  }
  X->got=0;
  return EXPLODE_OK;
}

#define GETBIT					\
  if(X->bits) {					\
    X->bits--;					\
    val=X->bitmap&1;				\
    X->bitmap>>=1;				\
  } else {					\
    if(!X->avail_in) return EXPLODE_EBUFF;	\
    if(X->avail_in>=4) {			\
      X->bitmap=cli_readint32(X->next_in);	\
      X->bits=31;				\
      X->next_in+=4;				\
      X->avail_in-=4;				\
    } else {					\
      X->bitmap=*X->next_in;			\
      X->bits=7;				\
      X->next_in++;				\
      X->avail_in--;				\
    }						\
    val=X->bitmap&1;				\
    X->bitmap>>=1;				\
  }


#define GETBITS(NUM)						\
  if(X->bits>=(NUM)) {						\
    val=X->bitmap&((1<<(NUM))-1);				\
    X->bitmap>>=(NUM);						\
    X->bits-=(NUM);						\
  } else {							\
    if(X->avail_in*8+X->bits<(NUM)) return EXPLODE_EBUFF;	\
    val=X->bitmap;						\
    if(X->avail_in>=4) {					\
      X->bitmap=cli_readint32(X->next_in);			\
      X->next_in+=4;						\
      X->avail_in-=4;						\
      val|=(X->bitmap&((1<<((NUM)-X->bits))-1))<<X->bits;	\
      X->bitmap>>=(NUM)-X->bits;				\
      X->bits=32-((NUM)-X->bits);				\
    } else {							\
      X->bitmap=*X->next_in;					\
      X->next_in++;						\
      X->avail_in--;						\
      val|=(X->bitmap&((1<<((NUM)-X->bits))-1))<<X->bits;	\
      X->bitmap>>=(NUM)-X->bits;				\
      X->bits=8-((NUM)-X->bits);				\
    }								\
  }


#define GETCODES(CASE, WHICH, HOWMANY)					\
  case CASE: {								\
    if(!X->avail_in) return EXPLODE_EBUFF;				\
    if(!X->got) need = *X->next_in;					\
    else need = X->window[0];						\
    if(need > HOWMANY - 1) return EXPLODE_ESTREAM; /* too many codes */ \
    need = need + 2 - X->got; /* bytes remaining */			\
    if(need>X->avail_in) { /* if not enuff */				\
      /* just copy what's avail... */					\
      memcpy(&X->window[X->got], X->next_in, X->avail_in);		\
      X->got += X->avail_in;						\
      X->next_in += X->avail_in;					\
      X->avail_in = 0;							\
      return EXPLODE_EBUFF; /* ...and beg for more */			\
    }									\
    /* else fetch what's needed */					\
    memcpy(&X->window[X->got], X->next_in, need);			\
    X->avail_in -= need;						\
    X->next_in += need;							\
    if(unpack_tree(X, X->WHICH, HOWMANY )) return EXPLODE_ESTREAM;	\
    /* and move on */							\
    X->got=0;								\
    X->state++;								\
  }

#define SETCASE(CASE) \
  X->state = (CASE);  \
 case(CASE): \
 {/* FAKE */}

int explode(struct xplstate *X) {
  unsigned int val, need;
  int temp=-1;
  
  switch(X->state) {
    /* grab compressed coded literals, if present */
    GETCODES(GRABLITS, lit_tree, 256);
    /* grab compressed coded lens */
    GETCODES(GRABLENS, len_tree, 64);
    /* grab compressed coded dists */
    GETCODES(GRABDISTS, dist_tree, 64);
    
  case EXPLODE:
    while(X->avail_in || X->bits) {
      GETBIT; /* can't fail */
      if(val) {
	if(X->litcodes) {
	  X->backsize=0;
	  X->state=EXPLODE_LITCODES;
	  for(X->got=0; X->got<=15; X->got++) {
	  case EXPLODE_LITCODES:
	    GETBIT;
	    X->backsize|=val<<(15-X->got);
	    if((temp=lookup_tree(X->lit_tree, 256, X->backsize, X->got))!=-1) break;
	  }
	  if(temp==-1) return EXPLODE_ESTREAM;
	  X->got=temp;
	} else {
	  SETCASE(EXPLODE_LITS);
	  GETBITS(8);
	  X->got=val;
	}
	SETCASE(EXPLODE_WBYTE);
	if(!X->avail_out) return EXPLODE_EBUFF;
	X->avail_out--;
	*X->next_out = X->window[X->cur & X->mask] = X->got;
	X->cur++;
	X->next_out++;
      } else {
	SETCASE(EXPLODE_BASEDIST);
	GETBITS(6u+X->largewin);
	X->backbytes=val;
	X->backsize=0;
	X->state=EXPLODE_DECODEDISTS;
	for(X->got=0; X->got<=15; X->got++) {
	case EXPLODE_DECODEDISTS:
	  GETBIT;
	  X->backsize|=val<<(15-X->got);
	  if((temp=lookup_tree(X->dist_tree, 64, X->backsize, X->got))!=-1) break;
	}
	if(temp==-1) return EXPLODE_ESTREAM;
	X->backbytes|=temp<<(6+X->largewin);
	X->backbytes++;
	X->backsize=0;
	X->state=EXPLODE_DECODELENS;
	for(X->got=0; X->got<=15; X->got++) {
	case EXPLODE_DECODELENS:
	  GETBIT;
	  X->backsize|=val<<(15-X->got);
	  if((temp=lookup_tree(X->len_tree, 64, X->backsize, X->got))!=-1) break;
	}
	if(temp==-1) return EXPLODE_ESTREAM;

	if(temp==63) {
	  SETCASE(EXPLODE_DECODEEXTRA);
	  GETBITS(8);
	  temp=63+val;
	}
	X->backsize=temp+X->minlen;
	X->state=EXPLODE_BACKCOPY;
	while(X->backsize--) {
	case EXPLODE_BACKCOPY:
	  if(!X->avail_out) return EXPLODE_EBUFF;
	  X->avail_out--;
	  if (X->cur>=X->backbytes)
	    *X->next_out = X->window[X->cur & X->mask] = X->window[(X->cur-X->backbytes) & X->mask];
	  else
	    *X->next_out = X->window[X->cur & X->mask] = 0;
	  X->cur++;
	  X->next_out++;
	}
      }
      X->state=EXPLODE;
    }
  }
  return EXPLODE_EBUFF;
}

void explode_shutdown(void) {}