/***********************************************************************
  This file is part of HA, a general purpose file archiver.
  Copyright (C) 1995 Harri Hirvola

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  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., 675 Mass Ave, Cambridge, MA 02139, USA.
************************************************************************
	HA sliding window dictionary
***********************************************************************/

#include <proto/exec.h>
#include "ha.h"
#include "haio.h"
#include "swdict.h"


#define HSIZE	16384
#define HSHIFT	3
#define HASH(p) ((swd->b[p]^((swd->b[p+1]^(swd->b[p+2]<<HSHIFT))<<HSHIFT))&(HSIZE-1))
#define MAXCNT	1024	


void swd_cleanup(struct swdict *swd) {

    if (swd->ll!=NULL) FreeVec(swd->ll);
    if (swd->best!=NULL) FreeVec(swd->best);	
    if (swd->ccnt!=NULL) FreeVec(swd->ccnt);
    if (swd->cr!=NULL) FreeVec(swd->cr);
    if (swd->b!=NULL) FreeVec(swd->b);	

	 FreeVec(swd);
}

struct swdict *swd_init(struct haio *haio, U16B maxl, U16B bufl) {
	
	 struct swdict *swd;
    register S16B i;

	 if (swd = (struct swdict *)AllocVec(sizeof(struct swdict),0))
	 {
		 swd->iblen=maxl; 
		 swd->cblen=bufl;
		 swd->blen=swd->cblen+swd->iblen;
		 swd->ll=AllocVec(swd->blen*sizeof(*swd->ll),0);
		 swd->best=AllocVec(swd->blen*sizeof(*swd->best),0);
		 swd->ccnt=AllocVec(HSIZE*sizeof(*swd->ccnt),0);
		 swd->cr=AllocVec(HSIZE*sizeof(*swd->cr),0);
		 swd->b=AllocVec((swd->blen+swd->iblen-1)*sizeof(*swd->b),0);
		 if (swd->ll==NULL || swd->best==NULL || swd->ccnt==NULL || swd->cr==NULL || swd->b==NULL) {
		swd_cleanup(swd);
		return NULL;
		 }
		 for (i=0;i<HSIZE;++i) swd->ccnt[i]=0; 
		 swd->binb=swd->bbf=swd->bbl=swd->inptr=0;
		 while (swd->bbl<swd->iblen) {
		if ((i=getbyte(haio))<0) break;
		swd->b[swd->inptr++]=i;
		swd->bbl++;
		 }
		 swd->swd_mlf=MINLEN-1;
	 }

	 return swd;
}

void swd_accept(struct swdict *swd, struct haio *haio) {

    register S16B i,j;
    
    j=swd->swd_mlf-2;
    do {   		/* Relies on non changed swd->swd_mlf !!! */
	if (swd->binb==swd->cblen) --swd->ccnt[HASH(swd->inptr)];
	else ++swd->binb;
	i=HASH(swd->bbf);
	swd->ll[swd->bbf]=swd->cr[i];
	swd->cr[i]=swd->bbf;
	swd->best[swd->bbf]=30000;
	swd->ccnt[i]++;
	if (++swd->bbf==swd->blen) swd->bbf=0;
	if ((i=getbyte(haio))<0) {
	    --swd->bbl;
	    if(++swd->inptr==swd->blen) swd->inptr=0;
	    continue;
	}
	if (swd->inptr<swd->iblen-1) {
	    swd->b[swd->inptr+swd->blen]=swd->b[swd->inptr]=i;
	    ++swd->inptr;
	}
	else {
	    swd->b[swd->inptr]=i;
	    if(++swd->inptr==swd->blen) swd->inptr=0;
	}
    } while (--j);
    swd->swd_mlf=MINLEN-1;
}

void swd_findbest(struct swdict *swd, struct haio *haio) {

    register U16B i,ref,cnt,ptr,start_len;
    register S16B c;
    
    i=HASH(swd->bbf);
    if ((cnt=swd->ccnt[i]++)>MAXCNT) cnt=MAXCNT;
    ptr=swd->ll[swd->bbf]=swd->cr[i];
    swd->cr[i]=swd->bbf;
    swd->swd_char=swd->b[swd->bbf];
    if ((start_len=swd->swd_mlf)>=swd->bbl) {
	if (swd->bbl==0) swd->swd_char=-1;
	swd->best[swd->bbf]=30000;
    }
    else {
	for (ref=swd->b[swd->bbf+swd->swd_mlf-1];cnt--;ptr=swd->ll[ptr]) {
	    if (swd->b[ptr+swd->swd_mlf-1]==ref && 
		swd->b[ptr]==swd->b[swd->bbf] && swd->b[ptr+1]==swd->b[swd->bbf+1]) {
		{
		    register unsigned char *p1=swd->b+ptr+3,*p2=swd->b+swd->bbf+3;
		    for (i=3;i<swd->bbl;++i) {
			if (*p1++!=*p2++) break; 
		    }
		}
		if (i<=swd->swd_mlf) continue;
		swd->swd_bpos=ptr;				
		if ((swd->swd_mlf=i)==swd->bbl || swd->best[ptr]<i) break;
		ref=swd->b[swd->bbf+swd->swd_mlf-1];
	    }
	}
	swd->best[swd->bbf]=swd->swd_mlf;
	if (swd->swd_mlf>start_len) {
	    if (swd->swd_bpos<swd->bbf) swd->swd_bpos=swd->bbf-swd->swd_bpos-1;
	    else swd->swd_bpos=swd->blen-1-swd->swd_bpos+swd->bbf;
	}
    }
    if (swd->binb==swd->cblen) --swd->ccnt[HASH(swd->inptr)];
    else ++swd->binb;
    if (++swd->bbf==swd->blen) swd->bbf=0;
    if ((c=getbyte(haio))<0) {
	--swd->bbl;
	if(++swd->inptr==swd->blen) swd->inptr=0;
	return;
    }
    if (swd->inptr<swd->iblen-1) {
	swd->b[swd->inptr+swd->blen]=swd->b[swd->inptr]=c;
	++swd->inptr;
    }
    else {
	swd->b[swd->inptr]=c;
	if (++swd->inptr==swd->blen) swd->inptr=0;
    }
}

struct swdict *swd_dinit(struct haio *haio, U16B bufl) {

	 struct swdict *swd;

	 if (swd = (struct swdict *)AllocVec(sizeof(struct swdict),0))
	 {
		 swd->cblen=bufl;
		 swd->ll=NULL;
		 swd->best=NULL;
		 swd->ccnt=NULL;
		 swd->cr=NULL;
		 swd->b=AllocVec(swd->cblen*sizeof(unsigned char),0);	
		 if (swd->b==NULL) {
		swd_cleanup(swd);
		return NULL;
		 }
		 swd->bbf=0;
	 }

	 return swd;
}

void swd_dpair(struct swdict *swd, struct haio *haio, U16B l, U16B p) {
	
    if (swd->bbf>p) p=swd->bbf-1-p;
    else p=swd->cblen-1-p+swd->bbf;
    while (l--) {
	swd->b[swd->bbf]=swd->b[p];
	putbyte(haio,swd->b[p]);
	if (++swd->bbf==swd->cblen) swd->bbf=0;
	if (++p==swd->cblen) p=0;
    }
}

void swd_dchar(struct swdict *swd, struct haio *haio, S16B c) {

    swd->b[swd->bbf]=c;
    putbyte(haio,c);
    if (++swd->bbf==swd->cblen) swd->bbf=0;
}