diff options
Diffstat (limited to 'usr.sbin/ppp/pred.c')
| -rw-r--r-- | usr.sbin/ppp/pred.c | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/usr.sbin/ppp/pred.c b/usr.sbin/ppp/pred.c new file mode 100644 index 0000000..3f7bd11 --- /dev/null +++ b/usr.sbin/ppp/pred.c @@ -0,0 +1,237 @@ +/* + * Written by Toshiharu OHNO (tony-o@iij.ad.jp) + * + * Copyright (C) 1993, Internet Initiative Japan, Inc. All rights reserverd. + * + * Redistribution and use in source and binary forms are permitted + * provided that the above copyright notice and this paragraph are + * duplicated in all such forms and that any documentation, + * advertising materials, and other materials related to such + * distribution and use acknowledge that the software was developed + * by the Internet Initiative Japan. The name of the + * IIJ may not be used to endorse or promote products derived + * from this software without specific prior written permission. + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED + * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. + * + * $Id:$ + * + * TODO: + */ + +#include "fsm.h" +#include "hdlc.h" +#include "lcpproto.h" +#include "ccp.h" + +/* + * pred.c -- Test program for Dave Rand's rendition of the + * predictor algorithm + * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) + * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de> + * Original : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com> + */ + +/* The following hash code is the heart of the algorithm: + * It builds a sliding hash sum of the previous 3-and-a-bit characters + * which will be used to index the guess table. + * A better hash function would result in additional compression, + * at the expense of time. + */ +#define IHASH(x) iHash = (iHash << 4) ^ (x) +#define OHASH(x) oHash = (oHash << 4) ^ (x) + +static unsigned short int iHash, oHash; +static unsigned char InputGuessTable[65536]; +static unsigned char OutputGuessTable[65536]; + +static int +compress(source, dest, len) +unsigned char *source, *dest; +int len; +{ + int i, bitmask; + unsigned char *flagdest, flags, *orgdest; + + orgdest = dest; + while (len) { + flagdest = dest++; flags = 0; /* All guess wrong initially */ + for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) { + if (OutputGuessTable[oHash] == *source) { + flags |= bitmask; /* Guess was right - don't output */ + } else { + OutputGuessTable[oHash] = *source; + *dest++ = *source; /* Guess wrong, output char */ + } + OHASH(*source++);len--; + } + *flagdest = flags; + } + return(dest - orgdest); +} + +static void +SyncTable(source, dest, len) +unsigned char *source, *dest; +int len; +{ + int i; + + while (len--) { + if (InputGuessTable[iHash] != *source) { + InputGuessTable[iHash] = *source; + } + IHASH(*dest++ = *source++); + } +} + +static int +decompress(source, dest, len) +unsigned char *source, *dest; +int len; +{ + int i, bitmask; + unsigned char flags, *orgdest; + + orgdest = dest; + while (len) { + flags = *source++; + len--; + for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { + if (flags & bitmask) { + *dest = InputGuessTable[iHash]; /* Guess correct */ + } else { + if (!len) + break; /* we seem to be really done -- cabo */ + InputGuessTable[iHash] = *source; /* Guess wrong */ + *dest = *source++; /* Read from source */ + len--; + } + IHASH(*dest++); + } + } + return(dest - orgdest); +} + +#define SIZ1 2048 + +void +Pred1Init(direction) +int direction; +{ + if (direction & 1) { /* Input part */ + iHash = 0; + bzero(InputGuessTable, sizeof(InputGuessTable)); + } + if (direction & 2) { /* Output part */ + oHash = 0; + bzero(OutputGuessTable, sizeof(OutputGuessTable)); + } +} + +void +Pred1Output(pri, proto, bp) +int pri; +u_short proto; +struct mbuf *bp; +{ + struct mbuf *mwp; + u_char *cp, *wp, *hp; + int orglen, len; + u_char bufp[SIZ1]; + u_short fcs; + + orglen = plength(bp) + 2; /* add count of proto */ + mwp = mballoc((orglen+2)/8*9+12, MB_HDLCOUT); + hp = wp = MBUF_CTOP(mwp); + cp = bufp; + *wp++ = *cp++ = orglen >> 8; + *wp++ = *cp++ = orglen & 0377; + *cp++ = proto >> 8; + *cp++ = proto & 0377; + mbread(bp, cp, orglen-2); + fcs = HdlcFcs(INITFCS, bufp, 2+orglen); + fcs = ~fcs; + + len = compress(bufp + 2, wp, orglen); +#ifdef DEBUG + logprintf("orglen (%d) --> len (%d)\n", orglen, len); +#endif + CcpInfo.orgout += orglen; + if (len < orglen) { + *hp |= 0x80; + wp += len; + CcpInfo.compout += len; + } else { + bcopy(bufp+2, wp, orglen); + wp += orglen; + CcpInfo.compout += orglen; + } + + *wp++ = fcs & 0377; + *wp++ = fcs >> 8; + mwp->cnt = wp - MBUF_CTOP(mwp); + HdlcOutput(pri, PROTO_COMPD, mwp); +} + +void +Pred1Input(bp) +struct mbuf *bp; +{ + u_char *cp, *pp; + int len, olen, len1; + struct mbuf *wp; + u_char *bufp; + u_short fcs, proto; + + wp = mballoc(SIZ1, MB_IPIN); + cp = MBUF_CTOP(bp); + olen = plength(bp); + pp = bufp = MBUF_CTOP(wp); + *pp++ = *cp & 0177; + len = *cp++ << 8; + *pp++ = *cp; + len += *cp++; + CcpInfo.orgin += len & 0x7fff; + if (len & 0x8000) { + len1 = decompress(cp, pp, olen - 4); + CcpInfo.compin += olen; + len &= 0x7fff; + if (len != len1) { /* Error is detected. Send reset request */ + CcpSendResetReq(&CcpFsm); + pfree(bp); + return; + } + cp += olen - 4; + pp += len1; + } else { + CcpInfo.compin += len; + SyncTable(cp, pp, len); + cp += len; + pp += len; + } + *pp++ = *cp++; /* CRC */ + *pp++ = *cp++; + fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp); +#ifdef DEBUG + logprintf("fcs = %04x (%s), len = %x, olen = %x\n", + fcs, (fcs == GOODFCS)? "good" : "bad", len, olen); +#endif + if (fcs == GOODFCS) { + wp->offset += 2; /* skip length */ + wp->cnt -= 4; /* skip length & CRC */ + pp = MBUF_CTOP(wp); + proto = *pp++; + if (proto & 1) { + wp->offset++; + wp->cnt--; + } else { + wp->offset += 2; + wp->cnt -= 2; + proto = (proto << 8) | *pp++; + } + DecodePacket(proto, wp); + } + pfree(bp); +} |
