pred.c revision 28679
16059Samurai#include "fsm.h" 26059Samurai#include "hdlc.h" 36059Samurai#include "lcpproto.h" 46059Samurai#include "ccp.h" 56059Samurai 66059Samurai/* 78857Srgrimes * 828679Sbrian * $Id: pred.c,v 1.13 1997/06/09 23:38:37 brian Exp $ 98857Srgrimes * 106059Samurai * pred.c -- Test program for Dave Rand's rendition of the 116059Samurai * predictor algorithm 126059Samurai * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) 136059Samurai * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de> 146059Samurai * Original : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com> 156059Samurai */ 166059Samurai 176059Samurai/* The following hash code is the heart of the algorithm: 186059Samurai * It builds a sliding hash sum of the previous 3-and-a-bit characters 196059Samurai * which will be used to index the guess table. 206059Samurai * A better hash function would result in additional compression, 216059Samurai * at the expense of time. 226059Samurai */ 2325630Sbrian#define IHASH(x) do {iHash = (iHash << 4) ^ (x);} while(0) 2425630Sbrian#define OHASH(x) do {oHash = (oHash << 4) ^ (x);} while(0) 256059Samurai 266059Samuraistatic unsigned short int iHash, oHash; 276059Samuraistatic unsigned char InputGuessTable[65536]; 286059Samuraistatic unsigned char OutputGuessTable[65536]; 296059Samurai 306059Samuraistatic int 3128679Sbriancompress(u_char * source, u_char * dest, int len) 326059Samurai{ 3328679Sbrian int i, bitmask; 3428679Sbrian unsigned char *flagdest, flags, *orgdest; 356059Samurai 3628679Sbrian orgdest = dest; 3728679Sbrian while (len) { 3828679Sbrian flagdest = dest++; 3928679Sbrian flags = 0; /* All guess wrong initially */ 4028679Sbrian for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) { 4128679Sbrian if (OutputGuessTable[oHash] == *source) { 4228679Sbrian flags |= bitmask; /* Guess was right - don't output */ 4328679Sbrian } else { 4428679Sbrian OutputGuessTable[oHash] = *source; 4528679Sbrian *dest++ = *source; /* Guess wrong, output char */ 4628679Sbrian } 4728679Sbrian OHASH(*source++); 4828679Sbrian len--; 496059Samurai } 5028679Sbrian *flagdest = flags; 5128679Sbrian } 5228679Sbrian return (dest - orgdest); 536059Samurai} 546059Samurai 556059Samuraistatic void 5628679SbrianSyncTable(u_char * source, u_char * dest, int len) 576059Samurai{ 586059Samurai 5928679Sbrian while (len--) { 6028679Sbrian if (InputGuessTable[iHash] != *source) { 6128679Sbrian InputGuessTable[iHash] = *source; 626059Samurai } 6328679Sbrian IHASH(*dest++ = *source++); 6428679Sbrian } 656059Samurai} 666059Samurai 676059Samuraistatic int 6828679Sbriandecompress(u_char * source, u_char * dest, int len) 696059Samurai{ 7028679Sbrian int i, bitmask; 7128679Sbrian unsigned char flags, *orgdest; 726059Samurai 7328679Sbrian orgdest = dest; 7428679Sbrian while (len) { 7528679Sbrian flags = *source++; 7628679Sbrian len--; 7728679Sbrian for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 7828679Sbrian if (flags & bitmask) { 7928679Sbrian *dest = InputGuessTable[iHash]; /* Guess correct */ 8028679Sbrian } else { 8128679Sbrian if (!len) 8228679Sbrian break; /* we seem to be really done -- cabo */ 8328679Sbrian InputGuessTable[iHash] = *source; /* Guess wrong */ 8428679Sbrian *dest = *source++; /* Read from source */ 8528679Sbrian len--; 8628679Sbrian } 8728679Sbrian IHASH(*dest++); 886059Samurai } 8928679Sbrian } 9028679Sbrian return (dest - orgdest); 916059Samurai} 926059Samurai 936059Samuraivoid 9428679SbrianPred1Init(int direction) 956059Samurai{ 9628679Sbrian if (direction & 1) { /* Input part */ 976059Samurai iHash = 0; 986059Samurai bzero(InputGuessTable, sizeof(InputGuessTable)); 996059Samurai } 10028679Sbrian if (direction & 2) { /* Output part */ 1016059Samurai oHash = 0; 1026059Samurai bzero(OutputGuessTable, sizeof(OutputGuessTable)); 1036059Samurai } 1046059Samurai} 1056059Samurai 1066059Samuraivoid 10728679SbrianPred1Output(int pri, u_short proto, struct mbuf * bp) 1086059Samurai{ 1096059Samurai struct mbuf *mwp; 1106059Samurai u_char *cp, *wp, *hp; 1116059Samurai int orglen, len; 11228679Sbrian u_char bufp[MAX_MTU + 2]; 1136059Samurai u_short fcs; 1146059Samurai 1156059Samurai orglen = plength(bp) + 2; /* add count of proto */ 11628679Sbrian mwp = mballoc((orglen + 2) / 8 * 9 + 12, MB_HDLCOUT); 1176059Samurai hp = wp = MBUF_CTOP(mwp); 1186059Samurai cp = bufp; 1196059Samurai *wp++ = *cp++ = orglen >> 8; 1206059Samurai *wp++ = *cp++ = orglen & 0377; 1216059Samurai *cp++ = proto >> 8; 1226059Samurai *cp++ = proto & 0377; 12328679Sbrian mbread(bp, cp, orglen - 2); 12428679Sbrian fcs = HdlcFcs(INITFCS, bufp, 2 + orglen); 1256059Samurai fcs = ~fcs; 1266059Samurai 1276059Samurai len = compress(bufp + 2, wp, orglen); 12826516Sbrian LogPrintf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len); 1296059Samurai CcpInfo.orgout += orglen; 1306059Samurai if (len < orglen) { 1316059Samurai *hp |= 0x80; 1326059Samurai wp += len; 1336059Samurai CcpInfo.compout += len; 1346059Samurai } else { 13528679Sbrian bcopy(bufp + 2, wp, orglen); 1366059Samurai wp += orglen; 1376059Samurai CcpInfo.compout += orglen; 1386059Samurai } 1396059Samurai 1406059Samurai *wp++ = fcs & 0377; 1416059Samurai *wp++ = fcs >> 8; 1426059Samurai mwp->cnt = wp - MBUF_CTOP(mwp); 14313733Sdfr HdlcOutput(PRI_NORMAL, PROTO_COMPD, mwp); 1446059Samurai} 1456059Samurai 1466059Samuraivoid 14728679SbrianPred1Input(struct mbuf * bp) 1486059Samurai{ 1496059Samurai u_char *cp, *pp; 1506059Samurai int len, olen, len1; 1516059Samurai struct mbuf *wp; 1526059Samurai u_char *bufp; 1536059Samurai u_short fcs, proto; 1546059Samurai 15528679Sbrian wp = mballoc(MAX_MTU + 2, MB_IPIN); 1566059Samurai cp = MBUF_CTOP(bp); 1576059Samurai olen = plength(bp); 1586059Samurai pp = bufp = MBUF_CTOP(wp); 1596059Samurai *pp++ = *cp & 0177; 1606059Samurai len = *cp++ << 8; 1616059Samurai *pp++ = *cp; 1626059Samurai len += *cp++; 1636059Samurai CcpInfo.orgin += len & 0x7fff; 1646059Samurai if (len & 0x8000) { 1656059Samurai len1 = decompress(cp, pp, olen - 4); 1666059Samurai CcpInfo.compin += olen; 1676059Samurai len &= 0x7fff; 16828679Sbrian if (len != len1) { /* Error is detected. Send reset request */ 16926516Sbrian LogPrintf(LogLCP, "%s: Length Error\n", CcpFsm.name); 1706059Samurai CcpSendResetReq(&CcpFsm); 1716059Samurai pfree(bp); 17213733Sdfr pfree(wp); 1736059Samurai return; 1746059Samurai } 1756059Samurai cp += olen - 4; 1766059Samurai pp += len1; 1776059Samurai } else { 1786059Samurai CcpInfo.compin += len; 1796059Samurai SyncTable(cp, pp, len); 1806059Samurai cp += len; 1816059Samurai pp += len; 1826059Samurai } 18328679Sbrian *pp++ = *cp++; /* CRC */ 1846059Samurai *pp++ = *cp++; 1856059Samurai fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp); 18613733Sdfr if (fcs != GOODFCS) 18726516Sbrian LogPrintf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%s), len = 0x%x," 18828679Sbrian " olen = 0x%x\n", fcs, (fcs == GOODFCS) ? "good" : "bad", 18926516Sbrian len, olen); 1906059Samurai if (fcs == GOODFCS) { 1916059Samurai wp->offset += 2; /* skip length */ 1926059Samurai wp->cnt -= 4; /* skip length & CRC */ 1936059Samurai pp = MBUF_CTOP(wp); 1946059Samurai proto = *pp++; 1956059Samurai if (proto & 1) { 1966059Samurai wp->offset++; 1976059Samurai wp->cnt--; 1986059Samurai } else { 1996059Samurai wp->offset += 2; 2006059Samurai wp->cnt -= 2; 2016059Samurai proto = (proto << 8) | *pp++; 2026059Samurai } 2036059Samurai DecodePacket(proto, wp); 20428679Sbrian } else { 20528679Sbrian LogDumpBp(LogHDLC, "Bad FCS", wp); 20628679Sbrian CcpSendResetReq(&CcpFsm); 20728679Sbrian pfree(wp); 2086059Samurai } 2096059Samurai pfree(bp); 2106059Samurai} 211