lpaq6.hpp

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

144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,144,146,148,150,
152,154,156,158,160,162,164,166,168,170,172,174,160,162,164,166,168,170,172,174,
176,178,180,182,184,186,188,190,192,130,132,134,136,138,140,142,144,146,148,150,
152,154,156,158,194,130,132,134,136,138,140,142,160,162,164,166,168,170,172,174,
144,146,148,150,152,154,156,158,176,178,180,182,184,186,188,174,160,162,164,166,
168,170,172,174,176,178,180,182,184,186,188,190,196,188,198,172,200,188,202,172,
204,188,206,172,208,188,210,172,212,188,214,172,216,188,218,172,220,188,222,172,
224,188,226,172,228,188,230,172,232,188,234,172,236,188,238,172,240,188,242,172,
244,188,246,172,248,188,250,172,252,188,254,172,252,188,254,172,



  2,  5,  6, 10, 12, 13, 14, 19, 23, 24, 25, 27, 28, 29, 30, 33, 35, 35, 35, 35,
 37, 37, 37, 37, 37, 37, 39, 39, 39, 39, 40, 43, 45, 45, 47, 47, 49, 49, 51, 51,
 52, 43, 57, 57, 59, 59, 61, 61, 63, 63, 65, 65, 66, 55, 57, 57, 73, 73, 75, 75,
 77, 77, 79, 79, 81, 81, 82, 69, 71, 71, 73, 73, 59, 59, 61, 61, 49, 49, 89, 89,
 91, 91, 92, 69, 87, 87, 45, 45, 99, 99,101,101,102, 69, 87, 87, 57, 57,109,109,
111,111,112, 85, 87, 87, 57, 57,119,119,121,121,122, 85, 97, 97, 57, 57,129,129,
131,131,132, 85, 97, 97, 57, 57,139,139,141,141,142, 95, 97, 97, 57, 57, 81, 81,
147,147,148, 95,107,107,151,151,152, 95,107,155,156, 95,107,159,160,105,107,163,
164,105,117,167,168,105,117,171,172,105,117,175,176,105,117,179,180,115,117,183,
184,115,127,187,188,115,127,191,192,115,127,195,196,115,127,199,200,115,127,203,
204,115,127,207,208,125,127,211,212,125,137,215,216,125,137,219,220,125,137,223,
224,125,137,227,228,125,137,231,232,125,137,235,236,125,137,239,240,125,137,243,
244,135,137,247,248,135, 69,251,252,135, 69,255,252,135, 69,255,

  3,  3,  5,  7,  9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39,
 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79,
 81, 83, 85, 87, 89, 91, 93, 95, 97, 99,101,103,105,107,109,111,113,115,117,119,
121,123,125,127,129,131,133,135,137,139,141,143,145,147,149,151,153,155,157,159,
161,163,165,167,169,171,173,175,177,179,181,183,185,187,189,191,193,195,197,199,
201,203,205,207,209,211,213,215,217,219,221,223,225,227,229,231,233,235,237,239,
241,243,245,247,249,251,253,255,129,131,133,135,137,139,141,143,145,147,149,151,
153,155,157,159,161,163,165,167,169,171,173,175,177,179,181,183,185,187,189,191,
193,195,197,199,201,203,205,207,209,211,213,215,217,219,221,223,225,227,229,231,
233,235,237,239,241,243,245,247,249,251,253,191,193,131,133,135,137,139,141,143,
145,147,149,151,153,155,157,159,161,163,165,167,169,171,173,175,177,179,181,183,
185,187,189,191,193,195,197,199,201,203,205,207,209,211,213,215,217,219,221,223,
225,227,229,231,233,235,237,239,241,243,245,247,249,251,253,255,

 51, 66, 52,  4, 40,116, 97, 75, 47, 79,141,188,250,238,137,212, 37, 67, 38, 85,
130,102, 89, 61,  9,110,172,219,207,240,182,227, 82, 70,100,130, 41, 84, 55, 21,
131,117,103,104, 90, 76, 62, 63, 80,115, 21, 65, 99, 70, 41,146,132,118,112,105,
 91, 77, 78, 94, 80, 56, 69,114, 85, 71,  6,147,133,119,113,106, 92, 93,109,125,
 42,162,  5,100, 81, 57, 22,148,134,120,121,107,108,124,140,156,163,149,115, 86,
 72, 43,178,164,135,128,122,123,139,155,161,176,150,136,101, 87, 58,  7,179,165,
151,129,138,145,160,171,187,203,137,144, 96, 73, 44,194,180,166,152,153,154,170,
186,202,218,234,169,185, 88, 59, 23,195,181,167,168,184,200,201,217,233,249, 13,
216,232, 74, 45,210,196,182,183,199,215,231,247,248, 28,191,209, 12,175, 60,  8,
211,197,198,214,230,246, 27,159,190,206,222,253,208,237, 46,226,212,213,229,245,
 11,143,174,193,221,252, 30,255,225, 31, 24,227,228,244, 26,127,158,189,205,236,
 14,239,241,152,152,182,242,243, 10,111,142,173,192,220,251,223,254,237,167,197,
212,242, 25, 95,126,157,177,204,235, 29,224, 15,252,167,197,227,

  3,  3,  5,  7,  9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39,
 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79,
 81, 83, 85, 87, 89, 91, 93, 95, 97, 99,101,103,105,107,109,111,113,115,117,119,
121,123,125,127,129,131,133,135,137,139,141,143,145,147,149,151,153,155,157,159,
145,147,149,151,153,155,157,159,161,163,165,167,169,171,173,175,145,147,149,151,
153,155,157,159,161,163,165,167,169,171,173,175,161,163,165,167,169,171,173,175,
177,179,181,183,185,187,189,191,129,131,133,135,137,139,141,143,145,147,149,151,
153,155,157,159,145,131,133,135,137,139,141,143,161,163,165,167,169,171,173,175,
145,147,149,151,153,155,157,159,177,179,181,183,185,187,189,195,161,163,165,167,
169,171,173,175,177,179,181,183,185,187,189,193,131,197,147,199,131,201,147,203,
131,205,147,207,131,209,147,211,131,213,147,215,131,217,147,219,131,221,147,223,
131,225,147,227,131,229,147,231,131,233,147,235,131,237,147,239,131,241,147,243,
131,245,147,247,131,249,147,251,131,253,147,255,131,253,147,255,
};
#define nex(state,sel) *(p+state+sel*256)


//////////////////////////// StateMap, APM //////////////////////////

// A StateMap maps a context to a probability.  Methods:
//
// Statemap sm(n) creates a StateMap with n contexts using 4*n bytes memory.
// sm.p(y, cx, limit) converts state cx (0..n-1) to a probability (0..4095).
//	that the next y=1, updating the previous prediction with y (0..1).
//	limit (1..1023, default 1023) is the maximum count for computing a
//	prediction.  Larger values are better for stationary sources.

class StateMap {
public:
  U32 *t_cxt;	// Context of last prediction
  U32 *t;	// cxt -> prediction in high 22 bits, count in low 10 bits
  StateMap(int n=512);

  // update bit y (0..1), predict next bit in context cx
  inline int p(int cx) {	//, int limit=1023)
  assert(y>>1==0);
  assert(cx>=0 && cx<N);
  assert(cxt>=0 && cxt<N);
    U32 p0=*t_cxt;
    U32 i=p0&1023, pr=p0>>12; // count, prediction
    p0+=(i<TOLIMIT_1a);
    p0+=((y20-(int)pr)*dt[i])&0xfffffc00;
    *t_cxt=p0;
    t_cxt=t+cx;
    return (*t_cxt) >>20;
  }
  inline int q(int cx) {	//, int limit=1023)
  assert(y>>1==0);
  assert(cx>=0 && cx<N);
  assert(cxt>=0 && cxt<N);
    U32 p0=*t_cxt;
    U32 i=p0&1023, pr=p0>>12; // count, prediction
    p0+=(i<TOLIMIT_1b);
    p0+=((y20-(int)pr)*dt[i])&0xfffffc00;
    *t_cxt=p0;
    t_cxt=t+cx;
    return (*t_cxt) >>20;
  }
  inline int r(int cx) {	//, int limit=1023)
  assert(y>>1==0);
  assert(cx>=0 && cx<N);
  assert(cxt>=0 && cxt<N);
    U32 p0=*t_cxt;
    U32 i=p0&1023, pr=p0>>12; // count, prediction
    p0+=(i<400);
    p0+=((y20-(int)pr)*dt[i])&0xfffffc00;
    *t_cxt=p0;
    t_cxt=t+cx;
    return (*t_cxt) >>20;
  }
};

StateMap::StateMap(int n) {
  alloc(t, n);
  t_cxt=t;
  for (int i=0; i<n; ++i)
    t[i]=0x80000000+SM_FIRST;
}

// An APM maps a probability and a context to a new probability.  Methods:
//
// APM a(n) creates with n contexts using 96*n bytes memory.
// a.pp(y, pr, cx, limit) updates and returns a new probability (0..4095)
//     like with StateMap.  pr (0..4095) is considered part of the context.
//     The output is computed by interpolating pr into 24 ranges nonlinearly
//     with smaller ranges near the ends.  The initial output is pr.
//     y=(0..1) is the last bit.  cx=(0..n-1) is the other context.
//     limit=(0..1023) defaults to 255.

class APM {
protected:
  int cxt;	// Context of last prediction
  U32 *t;	// cxt -> prediction in high 22 bits, count in low 10 bits
public:
  APM(int n);

  inline int p1(int pr, int cx) {	//, int limit=1023)
    assert(y>>1==0);
    assert(cx>=0 && cx<N/24);
    assert(cxt>=0 && cxt<N);
  {
    U32 *p=&t[cxt], p0=p[0];
    U32 i=p0&1023, pr=p0>>12; // count, prediction
    p0+=(i<TOLIMIT_2a);
    p0+=((y20-(int)pr)*dta[i]+0x200)&0xfffffc00;
    p[0]=p0;
  }
    int wt=pr&0xfff;  // interpolation weight of next element
    cx=cx*24+(pr>>12);
    cxt=cx+(wt>>11);
    pr=(t[cx]>>13)*(0x1000-wt)+(t[cx+1]>>13)*wt>>19;
    return pr;
  }

  inline int p2(int pr, int cx) {	//, int limit=1023)
    assert(y>>1==0);
    assert(cx>=0 && cx<N/24);
    assert(cxt>=0 && cxt<N);
  {
    U32 *p=&t[cxt], p0=p[0];
    U32 i=p0&1023, pr=p0>>12; // count, prediction
    p0+=(i<TOLIMIT_2b);
    p0+=((y20-(int)pr)*dta[i]+0x200)&0xfffffc00;
    p[0]=p0;
  }
    int wt=pr&0xfff;  // interpolation weight of next element
    cx=cx*24+(pr>>12);
    cxt=cx+(wt>>11);
    pr=(t[cx]>>13)*(0x1000-wt)+(t[cx+1]>>13)*wt>>19;
    return pr;
  }
};

APM::APM(int n): cxt(0) {
  alloc(t, n);
  for (int i=0; i<n; ++i) {
    int p=((i%24*2+1)*4096)/48-2048;
    t[i]=(U32(squash_init(p))<<20)+APM_FIRST;
  }
}

//////////////////////////// Mixer /////////////////////////////

// Mixer m(MI, MC) combines models using MC neural networks with
//	MI inputs each using 4*MC*MI bytes of memory.  It is used as follows:
// m.update(y) trains the network where the expected output is the
//	last bit, y.
// m.add(stretch(p)) inputs prediction from one of MI models.  The
//	prediction should be positive to predict a 1 bit, negative for 0,
//	nominally -2K to 2K.
// m.set(cxt) selects cxt (0..MC-1) as one of MC neural networks to use.
// m.p() returns the output prediction that the next bit is 1 as a
//	12 bit number (0 to 4095).  The normal sequence per prediction is:
//
// - m.add(x) called MI times with input x=(-2047..2047)
// - m.set(cxt) called once with cxt=(0..MC-1)
// - m.p() called once to predict the next bit, returns 0..4095
// - m.update(y) called once for actual bit y=(0..1).

#define MI 8
#define MC 1280
  int mxr_tx[MI];	// MI inputs
  int* mxr_wx;		// MI*MC weights
  int* mxr_cxt;		// context
  int mxr_pr=2048;	// last result (scaled 12 bits)

#if 0			// ATTENTION !  CHANGE this to 1 if you start to use
			//		<mixer max inputs>!=8 in your versions.
inline void train(int err) {
  int *w=mxr_cxt;
  assert(err>=-32768 && err<32768);
  for (int i=0; i<MI; ++i)
    w[i]+=mxr_tx[i]*err+0x4000>>15;
}

inline int dot_product() {
  int *w=mxr_cxt;
  int sum=0;
  for (int i=0; i<MI; ++i)
    sum+=mxr_tx[i]*w[i];
  sum>>=DP_SHIFT;
  if (sum<-2047) sum=-2047;
  if (sum> 2047) sum= 2047;
  return sum;
}

#else
inline void train(int err) {
    int *w=mxr_cxt;
    assert(err>=-32768 && err<32768);
    w[0]+=mxr_tx[0]*err+0x2000>>14;
    w[1]+=mxr_tx[1]*err+0x2000>>14;
    w[2]+=mxr_tx[2]*err+0x2000>>14;
    w[3]+=mxr_tx[3]*err+0x2000>>14;
    w[4]+=mxr_tx[4]*err+0x2000>>14;
    w[5]+=mxr_tx[5]*err+0x2000>>14;
    w[6]+=mxr_tx[6]*err+0x2000>>14;
    w[7]+=	    err+0x20  >>6;
}
inline int dot_product() {
    int *w=mxr_cxt;
    int sum =mxr_tx[0]*w[0];
	sum+=mxr_tx[1]*w[1];
	sum+=mxr_tx[2]*w[2];
	sum+=mxr_tx[3]*w[3];
	sum+=mxr_tx[4]*w[4];
	sum+=mxr_tx[5]*w[5];
	sum+=mxr_tx[6]*w[6];
	sum+=		w[7]<<8;
  sum>>=DP_SHIFT;
  if (sum<-2047) sum=-2047;
  if (sum> 2047) sum= 2047;
  return sum;
}
#endif


///class Mixer {
///public:
///  Mixer(int m);

  // Adjust weights to minimize coding cost of last prediction
#define m_update(y) {			\
    int err=y*0xfff-mxr_pr;		\
    fails<<=1;				\
    fails|=calcfails[err+4096];		\
    train(err);				\
  }

  // Input x (call up to MI times)

#define m_add(a,b) { assert((a)<MI); mxr_tx[a]=stretch_t[b]; }

  // predict next bit
#define m_p	dot_product();

///};

//////////////////////////// HashTable /////////////////////////

// A HashTable maps a 32-bit index to an array of B bytes.
// The first byte is a checksum using the upper 8 bits of the
// index.  The second byte is a priority (0 = empty) for hash
// replacement.  The index need not be a hash.

// HashTable<B> h(n) - create using n bytes  n and B must be
//     powers of 2 with n >= B*4, and B >= 2.
// h[i] returns array [1..B-1] of bytes indexed by i, creating and
//     replacing another element if needed.  Element 0 is the
//     checksum and should not be modified.



template <int B>
HashTable<B>::HashTable(int n): NB(n-B) {
  assert(B>=2 && (B&B-1)==0);
  assert(n>=B*4 && (n&n-1)==0);
  alloc(t, n+512);
  t=(U8*)(((long)t+511)&0xfffffe00)+1;	// align on cache line boundary
}

inline U32 hash1(U32 i) {  i*=234567891; i=i<<21|i>>11; return (i*765432197); }
inline U32 hash2(U32 i) {  i*=234567891; i=i<<19|i>>13; return (i*654321893); }
inline U32 hash3(U32 i) {  i*=234567891; i=i<<21|i>>11; return (i*543210973); }
inline U32 hash4(U32 i) {  i*=234567891; i=i<<19|i>>13; return (i*432109879); }
inline U32 hash5(U32 i) {  i*=234567891; i=i<<21|i>>11; return (i*987654323); }

inline U32 hash6(U32 i) {  i*=345678941; i=i<<19|i>>13; return (i*876543211); }
inline U32 hash7(U32 i) {  i*=345678941; i=i<<21|i>>11; return (i*765432197); }
inline U32 hash8(U32 i) {  i*=345678941; i=i<<19|i>>13; return (i*654321893); }
inline U32 hash9(U32 i) {  i*=345678941; i=i<<21|i>>11; return (i*543210973); }
inline U32 hash0(U32 i) {  i*=345678941; i=i<<19|i>>13; return (i*432109879); }

template <int B>
inline U8* HashTable<B>::get(U32 i) {
  U8 *p=t+(i*B&NB), *q, *r;
  i>>=24;
  U8 c=i;
  if (*(p-1)==c) return p;
  q=(U8*)((U32)p^B);
  if (*(q-1)==c) return q;
  r=(U8*)((U32)p^B*2);
  if (*(r-1)==c) return r;
  if (*p>*q) p=q;
  if (*p>*r) p=r;
#if 0			// ATTENTION !	CHANGE this to 1 if you start to use
			//		HashTable with B!=16 in your versions.
  memset(p-1, 0, B);
  *(p-1)=i;		// This is big-endian-compatible
#else
		*(U32*)(p -1)=i;	// This is NOT big-endian-compatible
		*(U32*)(p+ 3)=0;
		*(U32*)(p+ 7)=0;
		*(U32*)(p+11)=0;
#endif
  return p;
}

#ifdef WIKI
template <int B>
inline U8* HashTable<B>::get0(U32 i) {
  U8 *p=t+(i*B&NB), *q, *r;
  i>>=25;
  U8 c=i;
  if (*(p-1)==c) return p;
  q=(U8*)((U32)p^B);
  if (*(q-1)==c) return q;
  r=(U8*)((U32)p^B*2);
  if (*(r-1)==c) return r;
  if (*p>*q) p=q;
  if (*p>*r) p=r;
	*(U32*)(p -1)=i;	// This is NOT big-endian-compatible
	*(U32*)(p+ 3)=0;
	*(U32*)(p+ 7)=0;
	*(U32*)(p+11)=0;
  return p;
}
template <int B>
inline U8* HashTable<B>::get1(U32 i) {
  U8 *p=t+(i*B&NB), *q, *r;
  i>>=25; i|=128;
  U8 c=i;
  if (*(p-1)==c) return p;
  q=(U8*)((U32)p^B);
  if (*(q-1)==c) return q;
  r=(U8*)((U32)p^B*2);
  if (*(r-1)==c) return r;
  if (*p>*q) p=q;
  if (*p>*r) p=r;
	*(U32*)(p -1)=i;	// This is NOT big-endian-compatible
	*(U32*)(p+ 3)=0;
	*(U32*)(p+ 7)=0;
	*(U32*)(p+11)=0;
  return p;
}
#endif

//////////////////////////// MatchModel ////////////////////////

// MatchModel(n) predicts next bit using most recent context match.
//     using n bytes of memory.  n must be a power of 2 at least 8.
// MatchModel::p(y, m) updates the model with bit y (0..1) and writes
//     a prediction of the next bit to Mixer m.  It returns the length of
//     context matched (0..62).

  U32 h1, h2, h3; // context hashes
  int N, HN; // last hash table index, n/8-1

  enum {MAXLEN=62};   // maximum match length, at most 62
  U32 len2cxt[MAXLEN*2+1];
  U32 len2order[MAXLEN+1];

class MatchModel {
  int* ht;    // context hash -> next byte in buf
  int match;  // pointer to current byte in matched context in buf