pred.c revision 6060
155682Smarkm/* 255682Smarkm * Written by Toshiharu OHNO (tony-o@iij.ad.jp) 355682Smarkm * 455682Smarkm * Copyright (C) 1993, Internet Initiative Japan, Inc. All rights reserverd. 555682Smarkm * 655682Smarkm * Redistribution and use in source and binary forms are permitted 755682Smarkm * provided that the above copyright notice and this paragraph are 855682Smarkm * duplicated in all such forms and that any documentation, 955682Smarkm * advertising materials, and other materials related to such 1055682Smarkm * distribution and use acknowledge that the software was developed 1155682Smarkm * by the Internet Initiative Japan. The name of the 1255682Smarkm * IIJ may not be used to endorse or promote products derived 1355682Smarkm * from this software without specific prior written permission. 1455682Smarkm * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 1555682Smarkm * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 1655682Smarkm * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 1755682Smarkm * 1855682Smarkm * $Id:$ 1955682Smarkm * 2055682Smarkm * TODO: 2155682Smarkm */ 2255682Smarkm 2355682Smarkm#include "fsm.h" 2455682Smarkm#include "hdlc.h" 2555682Smarkm#include "lcpproto.h" 2655682Smarkm#include "ccp.h" 2755682Smarkm 2855682Smarkm/* 2955682Smarkm * pred.c -- Test program for Dave Rand's rendition of the 3055682Smarkm * predictor algorithm 3155682Smarkm * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) 3255682Smarkm * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de> 3355682Smarkm * Original : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com> 3455682Smarkm */ 3555682Smarkm 3655682Smarkm/* The following hash code is the heart of the algorithm: 3755682Smarkm * It builds a sliding hash sum of the previous 3-and-a-bit characters 3855682Smarkm * which will be used to index the guess table. 3955682Smarkm * A better hash function would result in additional compression, 4055682Smarkm * at the expense of time. 4155682Smarkm */ 4255682Smarkm#define IHASH(x) iHash = (iHash << 4) ^ (x) 4355682Smarkm#define OHASH(x) oHash = (oHash << 4) ^ (x) 4455682Smarkm 4555682Smarkmstatic unsigned short int iHash, oHash; 4655682Smarkmstatic unsigned char InputGuessTable[65536]; 4755682Smarkmstatic unsigned char OutputGuessTable[65536]; 4855682Smarkm 4955682Smarkmstatic int 5055682Smarkmcompress(source, dest, len) 5155682Smarkmunsigned char *source, *dest; 5255682Smarkmint len; 5355682Smarkm{ 5455682Smarkm int i, bitmask; 5555682Smarkm unsigned char *flagdest, flags, *orgdest; 5655682Smarkm 5755682Smarkm orgdest = dest; 5855682Smarkm while (len) { 5955682Smarkm flagdest = dest++; flags = 0; /* All guess wrong initially */ 6055682Smarkm for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) { 6155682Smarkm if (OutputGuessTable[oHash] == *source) { 6255682Smarkm flags |= bitmask; /* Guess was right - don't output */ 6355682Smarkm } else { 6455682Smarkm OutputGuessTable[oHash] = *source; 6555682Smarkm *dest++ = *source; /* Guess wrong, output char */ 6655682Smarkm } 6755682Smarkm OHASH(*source++);len--; 6855682Smarkm } 6955682Smarkm *flagdest = flags; 7055682Smarkm } 7155682Smarkm return(dest - orgdest); 7255682Smarkm} 7355682Smarkm 7455682Smarkmstatic void 7555682SmarkmSyncTable(source, dest, len) 7655682Smarkmunsigned char *source, *dest; 7755682Smarkmint len; 7855682Smarkm{ 7955682Smarkm int i; 8055682Smarkm 8155682Smarkm while (len--) { 8255682Smarkm if (InputGuessTable[iHash] != *source) { 8355682Smarkm InputGuessTable[iHash] = *source; 8455682Smarkm } 8555682Smarkm IHASH(*dest++ = *source++); 8655682Smarkm } 8755682Smarkm} 8855682Smarkm 8955682Smarkmstatic int 9055682Smarkmdecompress(source, dest, len) 9155682Smarkmunsigned char *source, *dest; 9255682Smarkmint len; 9355682Smarkm{ 9455682Smarkm int i, bitmask; 9555682Smarkm unsigned char flags, *orgdest; 9655682Smarkm 9755682Smarkm orgdest = dest; 9855682Smarkm while (len) { 9955682Smarkm flags = *source++; 10055682Smarkm len--; 10155682Smarkm for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 10255682Smarkm if (flags & bitmask) { 10355682Smarkm *dest = InputGuessTable[iHash]; /* Guess correct */ 10455682Smarkm } else { 10555682Smarkm if (!len) 10655682Smarkm break; /* we seem to be really done -- cabo */ 10755682Smarkm InputGuessTable[iHash] = *source; /* Guess wrong */ 10855682Smarkm *dest = *source++; /* Read from source */ 10955682Smarkm len--; 11055682Smarkm } 11155682Smarkm IHASH(*dest++); 11255682Smarkm } 11355682Smarkm } 11455682Smarkm return(dest - orgdest); 11555682Smarkm} 11655682Smarkm 11755682Smarkm#define SIZ1 2048 11855682Smarkm 11955682Smarkmvoid 12055682SmarkmPred1Init(direction) 12155682Smarkmint direction; 12255682Smarkm{ 12355682Smarkm if (direction & 1) { /* Input part */ 12455682Smarkm iHash = 0; 12555682Smarkm bzero(InputGuessTable, sizeof(InputGuessTable)); 12655682Smarkm } 12755682Smarkm if (direction & 2) { /* Output part */ 12855682Smarkm oHash = 0; 12955682Smarkm bzero(OutputGuessTable, sizeof(OutputGuessTable)); 13055682Smarkm } 13155682Smarkm} 13255682Smarkm 13355682Smarkmvoid 13455682SmarkmPred1Output(pri, proto, bp) 13555682Smarkmint pri; 13655682Smarkmu_short proto; 13755682Smarkmstruct mbuf *bp; 13855682Smarkm{ 13955682Smarkm struct mbuf *mwp; 14055682Smarkm u_char *cp, *wp, *hp; 14155682Smarkm int orglen, len; 14255682Smarkm u_char bufp[SIZ1]; 14355682Smarkm u_short fcs; 14455682Smarkm 14555682Smarkm orglen = plength(bp) + 2; /* add count of proto */ 14655682Smarkm mwp = mballoc((orglen+2)/8*9+12, MB_HDLCOUT); 14755682Smarkm hp = wp = MBUF_CTOP(mwp); 14855682Smarkm cp = bufp; 14955682Smarkm *wp++ = *cp++ = orglen >> 8; 15055682Smarkm *wp++ = *cp++ = orglen & 0377; 15155682Smarkm *cp++ = proto >> 8; 15255682Smarkm *cp++ = proto & 0377; 15355682Smarkm mbread(bp, cp, orglen-2); 15455682Smarkm fcs = HdlcFcs(INITFCS, bufp, 2+orglen); 15555682Smarkm fcs = ~fcs; 15655682Smarkm 15755682Smarkm len = compress(bufp + 2, wp, orglen); 15855682Smarkm#ifdef DEBUG 15955682Smarkm logprintf("orglen (%d) --> len (%d)\n", orglen, len); 16055682Smarkm#endif 16155682Smarkm CcpInfo.orgout += orglen; 16255682Smarkm if (len < orglen) { 16355682Smarkm *hp |= 0x80; 16455682Smarkm wp += len; 16555682Smarkm CcpInfo.compout += len; 16655682Smarkm } else { 16755682Smarkm bcopy(bufp+2, wp, orglen); 16855682Smarkm wp += orglen; 16955682Smarkm CcpInfo.compout += orglen; 17055682Smarkm } 17155682Smarkm 17255682Smarkm *wp++ = fcs & 0377; 17355682Smarkm *wp++ = fcs >> 8; 17455682Smarkm mwp->cnt = wp - MBUF_CTOP(mwp); 17555682Smarkm HdlcOutput(pri, PROTO_COMPD, mwp); 17655682Smarkm} 17755682Smarkm 17855682Smarkmvoid 17955682SmarkmPred1Input(bp) 18055682Smarkmstruct mbuf *bp; 18155682Smarkm{ 18255682Smarkm u_char *cp, *pp; 18355682Smarkm int len, olen, len1; 18455682Smarkm struct mbuf *wp; 18555682Smarkm u_char *bufp; 18655682Smarkm u_short fcs, proto; 18755682Smarkm 18855682Smarkm wp = mballoc(SIZ1, MB_IPIN); 18955682Smarkm cp = MBUF_CTOP(bp); 19055682Smarkm olen = plength(bp); 19155682Smarkm pp = bufp = MBUF_CTOP(wp); 19255682Smarkm *pp++ = *cp & 0177; 19355682Smarkm len = *cp++ << 8; 19455682Smarkm *pp++ = *cp; 19555682Smarkm len += *cp++; 19655682Smarkm CcpInfo.orgin += len & 0x7fff; 19755682Smarkm if (len & 0x8000) { 19855682Smarkm len1 = decompress(cp, pp, olen - 4); 19955682Smarkm CcpInfo.compin += olen; 20055682Smarkm len &= 0x7fff; 20155682Smarkm if (len != len1) { /* Error is detected. Send reset request */ 20255682Smarkm CcpSendResetReq(&CcpFsm); 20355682Smarkm pfree(bp); 20455682Smarkm return; 20555682Smarkm } 20655682Smarkm cp += olen - 4; 20755682Smarkm pp += len1; 20855682Smarkm } else { 20955682Smarkm CcpInfo.compin += len; 21055682Smarkm SyncTable(cp, pp, len); 21155682Smarkm cp += len; 21255682Smarkm pp += len; 21355682Smarkm } 21455682Smarkm *pp++ = *cp++; /* CRC */ 21555682Smarkm *pp++ = *cp++; 21655682Smarkm fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp); 21755682Smarkm#ifdef DEBUG 21855682Smarkm logprintf("fcs = %04x (%s), len = %x, olen = %x\n", 21955682Smarkm fcs, (fcs == GOODFCS)? "good" : "bad", len, olen); 22055682Smarkm#endif 22155682Smarkm if (fcs == GOODFCS) { 22255682Smarkm wp->offset += 2; /* skip length */ 22355682Smarkm wp->cnt -= 4; /* skip length & CRC */ 22455682Smarkm pp = MBUF_CTOP(wp); 22555682Smarkm proto = *pp++; 22655682Smarkm if (proto & 1) { 22755682Smarkm wp->offset++; 22855682Smarkm wp->cnt--; 22955682Smarkm } else { 23055682Smarkm wp->offset += 2; 23155682Smarkm wp->cnt -= 2; 23255682Smarkm proto = (proto << 8) | *pp++; 23355682Smarkm } 23455682Smarkm DecodePacket(proto, wp); 23555682Smarkm } 23655682Smarkm pfree(bp); 23755682Smarkm} 23855682Smarkm