lpaq6.hpp

x-wrt is the GUI config tool for openwrt,which is a open project about wireless Router

  int buf_match;  // buf[match]+256
  int len;    // length of match
  StateMap sm;  // len, bit, last byte -> prediction
public:
  MatchModel(int n);  // n must be a power of 2 at least 8.
  int p();	// predict next bit to m
  void upd();	// update bit y (0..1)
};

MatchModel::MatchModel(int n): sm(55<<8) {
  N=n/2-1;
  HN=n/8-1;
  pos=h1=h2=h3=match=len=0;
  assert(n>=8 && (n&n-1)==0);
  alloc(buf, N+1);
  alloc(ht, HN+1);
}

#define SEARCH(hsh) {	\
	len=1;		\
	match=ht[hsh];	\
	if (match!=pos) {\
	  while (len<MAXLEN+1 && buf[match-len&N]==buf[pos-len&N])	++len; \
	}		\
}
#define SEARCH2(hsh) {	\
	len=1;		\
	match=ht[hsh];	\
	if (match!=pos) {\
	  p=p1;		\
	  while (len<MAXLEN+1 && buf[match-len&N]==*p)		--p, ++len; \
	}		\
}

void MatchModel::upd() {
    // find or extend match
    if (len>2) {
      ++match;
      match&=N;
      if (len<MAXLEN)	++len;
    }
    else {
	if (pos>=MAXLEN) {
		U8 *p1=buf+pos-1, *p;
			   SEARCH2(h1)
		if (len<3) SEARCH2(h2)
#ifndef WIKI
		if (len<3) SEARCH2(h3)
#endif
	}
	else {
			   SEARCH(h1)
		if (len<3) SEARCH(h2)
#ifndef WIKI
		if (len<3) SEARCH(h3)
#endif
	}

	--len;
    }
    buf_match=buf[match]+256;

    // update index
#ifdef WIKI
  if ( (pos&1) || (len>11) )
#endif
    ht[h1]=pos;
    ht[h2]=pos;
#ifndef WIKI
    ht[h3]=pos;
#endif
}

int MatchModel::p() {

  int cxt=c0;
  if (len>0) {
    int b=buf_match>>bcount;
    if ((b>>1)==cxt)
      b=b&1,	// next bit
      cxt=len2cxt[len*2-b] + c1;
    else
	len=0;
  }

#ifdef WIKI
  m_add(0, sm.r(cxt));
#else
  m_add(0, sm.p(cxt));
#endif
  return len;
}

//////////////////////////// Predictor /////////////////////////

// A Predictor estimates the probability that the next bit of
// uncompressed data is 1.  Methods:
// Predictor(n) creates with 3*n bytes of memory.
// p() returns P(1) as a 12 bit number (0-4095).
// update(y) trains the predictor with the actual bit (0 or 1).

int MEM=0;	// Global memory usage = 3*MEM bytes (1<<20 .. 1<<29)

  U8 t0[0x10000];  // order 1 cxt -> state
  U8 *t0c1=t0, *cp[6]={t0, t0, t0, t0, t0, t0}; // pointer to bit history
  U32 h[6], pw=0, c8=0, cc=0, prevfail=0;
  U8 fails=0;
  StateMap sm[6];
  APM a1(24 * 0x10000), a2(24 * 0x800);

//////////////////////////// Encoder ////////////////////////////

// An Encoder does arithmetic encoding.  Methods:
// Encoder(COMPRESS, f) creates encoder for compression to archive f, which
//     must be open past any header for writing in binary mode.
// Encoder(DECOMPRESS, f) creates encoder for decompression from archive f,
//     which must be open past any header for reading in binary mode.
// code(i) in COMPRESS mode compresses bit i (0 or 1) to file f.
// code() in DECOMPRESS mode returns the next decompressed bit from file f.
// compress(c) in COMPRESS mode compresses one byte.
// decompress() in DECOMPRESS mode decompresses and returns one byte.
// flush() should be called exactly once after compression is done and
//     before closing f.  It does nothing in DECOMPRESS mode.



#define cp_update(m0,m1,m2,m3,m4,m5)\
  assert(y==0 || y==1);	\
  y20=y<<20;		\
  {                     \
  const U8 *p=&State_table[0]; if(y) p+=256*4;	\
  *cp[0]=nex(*cp[0], m0);  \
  *cp[1]=nex(*cp[1], m1);  \
  *cp[2]=nex(*cp[2], m2);  \
  *cp[3]=nex(*cp[3], m3);  \
  *cp[4]=nex(*cp[4], m4);  \
  *cp[5]=nex(*cp[5], m5);  \
  }                        \
  c0+=c0+y;

#define upd0(m0,m1,m2,m3,m4,m5,bc,sh) \
  assert(y==0 || y==1);	\
  y20=y<<20;		\
	bcount=bc;		\
	add2order+=MI*10;       \
	{                       \
	  const U8 *p=&State_table[0]; if(y) p+=256*4; \
	  int j=y+1<<sh;	\
	  *cp[1]=nex(*cp[1], m1); cp[1]+=j; \
	  *cp[2]=nex(*cp[2], m2); cp[2]+=j; \
	  *cp[3]=nex(*cp[3], m3); cp[3]+=j; \
	  *cp[4]=nex(*cp[4], m4); cp[4]+=j; \
	  *cp[5]=nex(*cp[5], m5); cp[5]+=j; \
	  *cp[0]=nex(*cp[0], m0);\
	}			\
  c0+=c0+y;

#define upd3(m0,m1,m2,m3,m4,m5,bc) \
  cp_update(m0,m1,m2,m3,m4,m5)	\
	bcount=bc;		\
	add2order+=MI*10;       \
	  cp[1]=t1b.get0(hash6(c0   -h[1]));\
	  upd3_cp			    \
	  cp[5]=t2b.get0(hash0(c0*37-h[5]));\

#define upd7(m0,m1,m2,m3,m4,m5) \
  cp_update(m0,m1,m2,m3,m4,m5)		\
    {					\
    int c=c0-256;			\
    add2order=mxr_wx+MI*10*add2order0*8;\
    c1=(c1>>4)+(c&240);			\
    buf[pos]=c;				\
    pos=(pos+1)&N;			\
    cc=(cc<<8)+(c8>>24);		\
    c8=(c8<<8)+(c4>>24);                \
    c4=c4<<8|c;                         \
    upd7_h123				\
    h[0]=c<<8;			/* order 1 */\
    h[1]=(c4&0xffff)*8191;	/* order 2 */\
    cp[1]=t1b.get1(hash1(h[1]));	\
    upd7_cp				\
    if (c>=65 && c<=90) c+=32;		/* lowercase unigram word order */    \
    if (c>=97 && c<=122) h[5]=(h[5]+c)*(191<<1);\
    else pw=h[5]*241, h[5]=0;		\
    cp[5]=t2a.get1(hash5(h[5]-pw));	\
    c0=1;		\
    bcount=7;		\
    mm->upd();		\
    }

U32 Encoder::Predictor_upd(int y) {
  m_update(y);

  // predict
  int len=mm->p(), pr;
  if (len==0)
	len=((*cp[1]!=0)+(*cp[2]!=0)+(*cp[3]!=0)+(*cp[4]!=0))*MI;
   else len=len2order[len];
  mxr_cxt=add2order+len;
  m_add(1, sm[1].q(*cp[1]));
  m_add(2, sm[2].q(*cp[2]));
  m_add(3, sm[3].p(*cp[3]));
  m_add(4, sm[4].p(*cp[4]));
  m_add(5, sm[5].p(*cp[5]));

#ifdef WIKI
  int h0c0=h[0]+c0, xx;
  cp[0]=t0+h0c0;
  m_add(6, sm[0].r(*cp[0]));
  pr=m_p;
  xx=a1.p1((pr+2047)*23, h0c0);
  mxr_pr=squash(pr) + 7*xx >>3;
  pr=mxr_pr	+7*a2.p2(stretch_t2[xx], fails*8+bcount)+4 >>3;
#else
  cp[0]=t0c1+c0;
  m_add(6, sm[0].p(*cp[0]));
  pr=m_p;
  pr=squash(pr)	+3*a1.p1((pr+2047)*23, h[0]+c0) >>2;
  mxr_pr=pr;
  pr=pr*3	+5*a2.p2(stretch_t2[pr], fails+prevfail)+4 >>3;
#endif
  return pr+(pr<2048);
}


  // Compress bit y
#define enc1(k)\
    int y=(c>>k)&1;\
    U32 xmid=x1 + (x2-x1>>12)*p + ((x2-x1&0xfff)*p>>12);\
    assert(xmid>=x1 && xmid<x2);                        \
    y ? (x2=xmid) : (x1=xmid+1);

#define enc2 \
    while (((x1^x2)&0xff000000)==0) {  /* pass equal leading bytes of range */ \
      putc(x2>>24, archive); \
      x1<<=8;                \
      x2=(x2<<8)+255;        \
    }

  // Return decompressed bit
#define dec1(k) \
    U32 xmid=x1 + (x2-x1>>12)*p + ((x2-x1&0xfff)*p>>12);\
    assert(xmid>=x1 && xmid<x2);                        \
    int y=x<=xmid;                                      \
    y ? (x2=xmid) : (x1=xmid+1);

#define dec2 \
    while (((x1^x2)&0xff000000)==0) {  /* pass equal leading bytes of range */ \
      x=(x<<8)+(getc(archive)&255);	/* EOF is OK */ \
      x1<<=8;                                           \
      x2=(x2<<8)+255;                                   \
    }


#ifdef WIKI
#define eight_bits(part1,part2) \
    sm[0].t+=256;\
    { part1(7); upd0(3,3,1,0,0,0, 6,0); p=Predictor_upd(y); } part2;\
    { part1(6); upd0(1,3,1,0,0,0, 5,1); p=Predictor_upd(y); } part2;\
    sm[1].t+=256;\
    { part1(5); upd0(1,3,1,0,0,0, 4,2); p=Predictor_upd(y); } part2;\
    sm[2].t+=256;\
    sm[5].t+=256;\
    { part1(4); upd3(1,3,1,0,0,0, 3  ); p=Predictor_upd(y); } part2;\
    sm[4].t+=256;\
    { part1(3); upd0(1,3,0,0,0,1, 2,0); p=Predictor_upd(y); } part2;\
    { part1(2); upd0(1,3,0,0,2,1, 1,1); p=Predictor_upd(y); } part2;\
    { part1(1); upd0(1,3,0,0,2,1, 0,2); p=Predictor_upd(y); } part2;\
    sm[0].t-=256;\
    sm[1].t-=256;\
    sm[2].t-=256;\
    sm[4].t-=256;\
    sm[5].t-=256;\
    { part1(0); upd7(1,3,0,0,2,1     ); p=Predictor_upd(y); } part2;
#else
#define eight_bits(part1,part2) \
    sm[4].t+=256;\
    { part1(7); upd0(1,0,0,2,0,1, 6,0); p=Predictor_upd(y); } part2;\
    sm[5].t+=256;\
    { part1(6); upd0(1,0,0,2,0,1, 5,1); p=Predictor_upd(y); } part2;\
    sm[2].t+=256;\
    { part1(5); upd0(1,0,0,2,0,3, 4,2); p=Predictor_upd(y); } part2;\
    sm[1].t+=256;\
    { part1(4); upd3(1,0,3,2,0,3, 3  ); p=Predictor_upd(y); } part2;\
    sm[0].t+=256;\
    { part1(3); upd0(1,0,3,2,0,3, 2,0); p=Predictor_upd(y); } part2;\
    { part1(2); upd0(1,0,3,2,0,3, 1,1); p=Predictor_upd(y); } part2;\
    { part1(1); upd0(1,0,3,2,0,3, 0,2); p=Predictor_upd(y); } part2;\
    sm[0].t-=256;\
    sm[1].t-=256;\
    sm[2].t-=256;\
    sm[4].t-=256;\
    sm[5].t-=256;\
    { part1(0); upd7(1,0,3,2,0,3     ); p=Predictor_upd(y); } part2;
#endif

  // Compress one byte
void Encoder::compress(int c) {
    ///assert(mode==COMPRESS);
    if (TextFlag)
	if (c==0x20||c==0x1f) c^=0x3f;
    eight_bits(enc1,enc2)

	if ( (pos&(256*1024-1))==0 )
	if ( (pos==7*1024*1024 && DP_SHIFT==16) || (pos==1280*1024 && DP_SHIFT==15) || DP_SHIFT==14 )
		for (DP_SHIFT++, c=0; c<MI*MC; ++c)	mxr_wx[c] *= 2;
  }

  // Decompress and return one byte
int Encoder::decompress() {
    eight_bits(dec1,dec2)
    int c=c4&255;
    if (TextFlag)
	if (c==0x20||c==0x1f) c^=0x3f;

	if ( (pos&(256*1024-1))==0 )
	if ( (pos==7*1024*1024 && DP_SHIFT==16) || (pos==1280*1024 && DP_SHIFT==15) || DP_SHIFT==14 )
	{
		int c2;
		for (DP_SHIFT++, c2=0; c2<MI*MC; ++c2)	mxr_wx[c2] *= 2;
	}

	return c;
  }

Encoder::~Encoder()
{
	delete(mm);
}

Encoder::Encoder(int m, FILE* f):
#ifdef WIKI
    t4a(MEM), t4b(MEM),
#else
    t1(MEM/2), t2(MEM), t3(MEM/2),
#endif
    x1(0), x2(0xffffffff), x(0), p(2048) {

  archive=f;
  if (m==DECOMPRESS) {  // x = first 4 bytes of archive
    for (int i=0; i<4; ++i)
      x=(x<<8)+(getc(archive)&255);
  }
//  TextFlag=1;
  mm=new MatchModel(MEM);
  int i, pi=0;
  for (int x=-2047; x<=2047; ++x) {  // invert squash()
    int i=squash_init(x);
    squash(x)=i+SQUARD;	//rounding,  needed at the end of Predictor::update()
    for (int j=pi; j<=i; ++j)
      stretch_t[j]=x, stretch_t2[j]=(x+2047)*23;
    pi=i+1;
  }
  stretch_t[4095]=2047;
  stretch_t2[4095]=4094*23;

  for (i=0; i<1024; ++i)
#ifdef WIKI
    dt[i]=18432/(i+i+8),
    dta[i]=8192/(i+i+6);
#else
    dt[i]=9216/(i+i+3),
    dta[i]=(10240+1536)/(i+i+8);

  for (i=0; i<256; ++i) {
    pi=(i&  1)<<10;
    if (i&  6) pi+=512;
    if (i&248) pi+=256;
    calcprevfail[i]=pi;
  }
#endif

  for (i=-4096; i<4096; ++i) {
    int e=i, v=0;
    if (e<0) e=-e;
    if (e > 1024  ) v=1;
    if (e > 2624  ) v=3;
    calcfails[i+4096]=v;
  }

  for (i=2; i<=MAXLEN*2; i+=2) {
      int c;
      if (i<32) c=i;
      else c=(i>>3)*2+24;
      c*=256;
	 len2cxt[i]=c;
	 len2cxt[i-1]=c-256;
	c=i>>1;
	len2order[c]=(5+(c>=8)+(c>=12)+(c>=16)+(c>=32))*MI;
  }

  alloc(mxr_wx, MI*MC);
  for (i=0; i<MI*MC; ++i)	mxr_wx[i] = (1<<(DP_SHIFT-2));
  mxr_cxt=mxr_wx;
  add2order=mxr_wx;
}

void Encoder::flush() {
  ///if (mode==COMPRESS)
    putc(x1>>24, archive);  // Flush first unequal byte of range
}

void set_PAQ_level(int PAQ_level)
{
	MEM=1<<(PAQ_level+20);
}