/* PPP "Predictor" compression */
struct pred_db {
	u_short	hash;
	u_short mru;
	char	debug;
	u_char  unit;
	u_char	tbl[65536];
};
#define PRED_OVHD (4+2)			/* Predictor 1 overhead/packet */
extern struct pred_db *pf_pred1_init(struct pred_db*,int,int);
extern int pf_pred1_comp(struct pred_db*, u_char*,int,struct mbuf*,int,int);




#define PRED_HASH(h,x) ((u_short)(((h)<<4) ^ (x)))

#define PRED_LEN_MASK	0x7fff
#define PRED_COMP_BIT	0x8000


/* Initialize the database.
 */
struct pred_db *
pf_pred1_init(struct pred_db *db, int unit, int mru)
{
	if (!db) {
		db = KSALLOC(pred_db,1);
		if (!db)
			return 0;
	}

	bzero(db, sizeof(*db));
	db->unit = unit;
	db->mru = mru;
	return db;
}


/* compress a packet using Predictor Type 1.
 *	Assume the protocol is known to be >= 0x21 and < 0xff.
 */
int
pf_pred1_comp(struct pred_db *db,
	      u_char *cp_buf,		/* compress into here */
	      int proto,		/* this original PPP protocol */
	      struct mbuf *m,		/* from here */
	      int len,			/* data not counting protocol */
	      int pc)			/* !=0 to compress protocol field */
{
	register int index;
	register u_short hash;
	register u_short fcs;
	register u_char flags, *flagsp;
	register int mlim, slim;
	register u_char *rptr, *wptr, *wptr0;
	u_char c_proto[2];
	struct mbuf *n;


	if (pc) {
		c_proto[0] = proto;
		mlim = 1;
	} else {
		c_proto[0] = proto>>8;
		c_proto[1] = proto;
		mlim = 2;
	}
	rptr = c_proto;			/* real protocol ID at packet start */

	len += mlim;
	fcs = PPP_FCS_INIT;
	fcs = PPP_FCS(fcs,len>>8);
	fcs = PPP_FCS(fcs,len);

	hash = db->hash;
	n = m;
	wptr = &cp_buf[2];
	wptr0 = wptr+mlim;
	flags = 0;
	flagsp = wptr++;
	index = 8;
	for (;;) {
		if (!mlim) {
			if (!n) {
				*flagsp = flags >> index;
				db->hash = hash;
				break;
			}
			mlim = n->m_len;
			rptr = mtod(n, u_char*);
			n = n->m_next;
			if (!mlim)
				continue;   /* skip empty mbufs */
		}
		if (!index) {
			*flagsp = flags;
			flagsp = wptr++;
			index = 8;
		}
		slim = MIN(mlim, index);
		index -= slim;
		mlim -= slim;
		do {
			u_char b = *rptr++;
			fcs = PPP_FCS(fcs,b);
			flags >>= 1;
			if (db->tbl[hash] == b) {
				flags |= 0x80;
			} else {
				db->tbl[hash] = b;
				*wptr++ = b;
			}
			hash = PRED_HASH(hash,b);
		} while (--slim != 0);
	}

	/* If compressing made it larger, then send the original.
	 */
	if (wptr - wptr0 < len) {
		*(u_short*)cp_buf = len | PRED_COMP_BIT;
	} else {
		*(u_short*)cp_buf = len;
		if (pc) {
			cp_buf[2] = proto;
			(void)m_datacopy(m, 0,len-1, &cp_buf[3]);
			wptr = &cp_buf[len-1+3];
		} else {
			cp_buf[2] = proto>>8;
			cp_buf[3] = proto;
			(void)m_datacopy(m, 0,len-2, &cp_buf[4]);
			wptr = &cp_buf[len-2+4];
		}
	}

	fcs ^= PPP_FCS_INIT;
	*wptr++ = fcs;
	*wptr++ = fcs >> 8;

	return (wptr - cp_buf);
}


/* Decompress Predictor Type 1.
 *	It would be nice to de-compress from stream buffers directly
 *	to mbufs, but we cannot know until we decompress that the
 *	packet contains an IP packet.
 */
static mblk_t*
pf_pred1_decomp(struct pred_db *db,
		mblk_t *cmsg)		/* compressed input */
{
	register u_char flags, b;
	register int comp, explen, slen, index;
	register u_char *rptr, *wptr;
	register u_short fcs;
	register int dlen;
	register u_short hash = db->hash;
	register struct ppp_buf *pb;
	mblk_t *dmsg;

	/* Get at least the Predictor length first buffer */
	rptr = cmsg->b_rptr;
	if (rptr + PPP_BUF_HEAD_INFO+PRED_OVHD <= cmsg->b_wptr) {
		if (!pullupmsg(cmsg, PPP_BUF_HEAD_INFO+PRED_OVHD)) {
			freemsg(cmsg);
			if (db->debug)
				printf("pred1_decomp%d: failed to pullup\n",
				       db->unit);
			return 0;
		}
		rptr = cmsg->b_rptr;
	}

	comp = ((((struct ppp_buf*)rptr)->un.info[0]<<8)
		  + ((struct ppp_buf*)rptr)->un.info[1]);
	explen = comp & PRED_LEN_MASK;

	if (explen > db->mru || explen == 0) {
		/* give up if the length is impossible */
		freemsg(cmsg);
		if (db->debug)
			printf("pred_1_decomp%d: bad length 0x%x\n",
			       db->unit, comp);
		return 0;
	}

	dmsg = allocb(explen+PPP_BUF_HEAD_INFO, BPRI_HI);
	if (!dmsg) {
		/* give up if cannot get an uncompressed buffer */
		freemsg(cmsg);
		if (db->debug)
			printf("pred_1_decomp%d: buffer allocation failed\n",
			       db->unit);
		return 0;
	}
	wptr = dmsg->b_wptr;
	pb = (struct ppp_buf*)wptr;
	pb->type = BEEP_FRAME;
	/* assume the protocol field is compressed */
	pb->proto = 0;
	wptr += PPP_BUF_HEAD_PROTO+1;

	/* skip PPP header */
	rptr += PPP_BUF_HEAD_INFO+2;

	fcs = PPP_FCS_INIT;
	fcs = PPP_FCS(fcs,explen>>8);
	fcs = PPP_FCS(fcs,explen);
	index = 0;
	do {
		slen = cmsg->b_wptr - rptr;
		if (slen <= 0) {
			mblk_t *bp = cmsg;
			cmsg = cmsg->b_cont;
			freeb(bp);
			if (!cmsg) {
				/* Give up on bad packet length.  There should
				 * have been 2 bytes remaining for the FCS.
				 */
				freemsg(cmsg);
				freemsg(dmsg);
				if (db->debug)
					printf("pred1_decomp%d: packet too "
					       "short (comp=0x%x)\n",
					       db->unit, comp);
				return 0;
			}
			rptr = cmsg->b_rptr;
			continue;
		}

		if (!(comp & PRED_COMP_BIT)) {
			/* update dictionary for incompressible data */
			do {
				b = *rptr++;
				fcs = PPP_FCS(fcs,b);
				*wptr++ = b;
				db->tbl[hash] = b;
				hash = PRED_HASH(hash,b);
				if (--explen == 0)
					goto fin;
			} while (--slen != 0);
			continue;
		}

		if (index == 0) {
			/* be quick about most of the packet
			 */
			while (slen >= 9 && explen >= 8) {
				flags = *rptr++;
				--slen;
				for (index = 8; index != 0; index--) {
					if (flags & 1) {
						b = db->tbl[hash];
					} else {
						--slen;
						b = *rptr++;
						db->tbl[hash] = b;
					}
					fcs = PPP_FCS(fcs,b);
					hash = PRED_HASH(hash,b);
					*wptr++ = b;
					flags >>= 1;
				}
				if ((explen -= 8) == 0)
					goto fin;
			}
		}

		/* Handle last dribble at the end of an input buffer
		 * or the partial block at the start of an input buffer.
		 */
		if (index != 0 || slen < 9 || explen < 8) {
			dlen = MAX(index,8);
			while (dlen != 0) {
				if (index == 0) {
					if (!slen)
						break;
					--slen;
					flags = *rptr++;
					index = 8;
				}
				if (flags & 1) {
					b = db->tbl[hash];
				} else {
					if (!slen)
						break;
					--slen;
					b = *rptr++;
					db->tbl[hash] = b;
				}
				--index;
				flags >>= 1;
				hash = PRED_HASH(hash,b);
				fcs = PPP_FCS(fcs,b);
				*wptr++ = b;
				if (--explen == 0)
					goto fin;
				--dlen;
			}
		}
	} while (explen != 0);
fin:
	db->hash = hash;

	if (rptr+2 > cmsg->b_wptr) {
		cmsg->b_rptr = rptr;
		if (!pullupmsg(cmsg, 2)
		    || (rptr = cmsg->b_rptr,
			rptr+2 != cmsg->b_wptr)) {
			/* give up if CCP FCS is missing */
			freemsg(cmsg);
			freemsg(dmsg);
			if (db->debug)
				printf("pred1_decomp%d: %d bytes of FCS "
				       "too few (comp=0x%x)\n",
				       db->unit, cmsg->b_wptr - rptr, comp);
			return 0;
		}
	}
	fcs = PPP_FCS(fcs,*rptr);
	rptr++;
	fcs = PPP_FCS(fcs,*rptr);
#ifdef DEBUG
	if (db->debug
	    && (++rptr != cmsg->b_wptr || cmsg->b_cont != 0)) {
		cmsg->b_rptr = rptr;
		slen = msgdsize(cmsg);
		if (slen != 0)
			printf("pred1_decomp%d: %d bytes of padding "
			       "after 0x%x\n",
			       db->unit, slen, comp);
	}
#endif
	freemsg(cmsg);

	if (fcs != PPP_FCS_GOOD) {
		freemsg(dmsg);
		if (db->debug)
			printf("pred1_decomp%d: bad FCS (comp=0x%x)\n",
			       db->unit, comp);
		return 0;
	}

	/* handle uncompressed PPP protocol field */
	if (pb->proto == 0) {
		bcopy(pb->un.info,1+(char*)&pb->proto,
		      wptr - pb->un.info);
		wptr--;
	}
	dmsg->b_wptr = wptr;
	CK_WPTR(dmsg);
	return dmsg;
}