pred.c revision 8857
1#include "fsm.h" 2#include "hdlc.h" 3#include "lcpproto.h" 4#include "ccp.h" 5 6/* 7 * 8 * $Id: pred.c,v 1.2 1995/02/26 12:17:55 amurai Exp $ 9 * 10 * pred.c -- Test program for Dave Rand's rendition of the 11 * predictor algorithm 12 * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) 13 * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de> 14 * Original : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com> 15 */ 16 17/* The following hash code is the heart of the algorithm: 18 * It builds a sliding hash sum of the previous 3-and-a-bit characters 19 * which will be used to index the guess table. 20 * A better hash function would result in additional compression, 21 * at the expense of time. 22 */ 23#define IHASH(x) iHash = (iHash << 4) ^ (x) 24#define OHASH(x) oHash = (oHash << 4) ^ (x) 25 26static unsigned short int iHash, oHash; 27static unsigned char InputGuessTable[65536]; 28static unsigned char OutputGuessTable[65536]; 29 30static int 31compress(source, dest, len) 32unsigned char *source, *dest; 33int len; 34{ 35 int i, bitmask; 36 unsigned char *flagdest, flags, *orgdest; 37 38 orgdest = dest; 39 while (len) { 40 flagdest = dest++; flags = 0; /* All guess wrong initially */ 41 for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) { 42 if (OutputGuessTable[oHash] == *source) { 43 flags |= bitmask; /* Guess was right - don't output */ 44 } else { 45 OutputGuessTable[oHash] = *source; 46 *dest++ = *source; /* Guess wrong, output char */ 47 } 48 OHASH(*source++);len--; 49 } 50 *flagdest = flags; 51 } 52 return(dest - orgdest); 53} 54 55static void 56SyncTable(source, dest, len) 57unsigned char *source, *dest; 58int len; 59{ 60 int i; 61 62 while (len--) { 63 if (InputGuessTable[iHash] != *source) { 64 InputGuessTable[iHash] = *source; 65 } 66 IHASH(*dest++ = *source++); 67 } 68} 69 70static int 71decompress(source, dest, len) 72unsigned char *source, *dest; 73int len; 74{ 75 int i, bitmask; 76 unsigned char flags, *orgdest; 77 78 orgdest = dest; 79 while (len) { 80 flags = *source++; 81 len--; 82 for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 83 if (flags & bitmask) { 84 *dest = InputGuessTable[iHash]; /* Guess correct */ 85 } else { 86 if (!len) 87 break; /* we seem to be really done -- cabo */ 88 InputGuessTable[iHash] = *source; /* Guess wrong */ 89 *dest = *source++; /* Read from source */ 90 len--; 91 } 92 IHASH(*dest++); 93 } 94 } 95 return(dest - orgdest); 96} 97 98#define SIZ1 2048 99 100void 101Pred1Init(direction) 102int direction; 103{ 104 if (direction & 1) { /* Input part */ 105 iHash = 0; 106 bzero(InputGuessTable, sizeof(InputGuessTable)); 107 } 108 if (direction & 2) { /* Output part */ 109 oHash = 0; 110 bzero(OutputGuessTable, sizeof(OutputGuessTable)); 111 } 112} 113 114void 115Pred1Output(pri, proto, bp) 116int pri; 117u_short proto; 118struct mbuf *bp; 119{ 120 struct mbuf *mwp; 121 u_char *cp, *wp, *hp; 122 int orglen, len; 123 u_char bufp[SIZ1]; 124 u_short fcs; 125 126 orglen = plength(bp) + 2; /* add count of proto */ 127 mwp = mballoc((orglen+2)/8*9+12, MB_HDLCOUT); 128 hp = wp = MBUF_CTOP(mwp); 129 cp = bufp; 130 *wp++ = *cp++ = orglen >> 8; 131 *wp++ = *cp++ = orglen & 0377; 132 *cp++ = proto >> 8; 133 *cp++ = proto & 0377; 134 mbread(bp, cp, orglen-2); 135 fcs = HdlcFcs(INITFCS, bufp, 2+orglen); 136 fcs = ~fcs; 137 138 len = compress(bufp + 2, wp, orglen); 139#ifdef DEBUG 140 logprintf("orglen (%d) --> len (%d)\n", orglen, len); 141#endif 142 CcpInfo.orgout += orglen; 143 if (len < orglen) { 144 *hp |= 0x80; 145 wp += len; 146 CcpInfo.compout += len; 147 } else { 148 bcopy(bufp+2, wp, orglen); 149 wp += orglen; 150 CcpInfo.compout += orglen; 151 } 152 153 *wp++ = fcs & 0377; 154 *wp++ = fcs >> 8; 155 mwp->cnt = wp - MBUF_CTOP(mwp); 156 HdlcOutput(pri, PROTO_COMPD, mwp); 157} 158 159void 160Pred1Input(bp) 161struct mbuf *bp; 162{ 163 u_char *cp, *pp; 164 int len, olen, len1; 165 struct mbuf *wp; 166 u_char *bufp; 167 u_short fcs, proto; 168 169 wp = mballoc(SIZ1, MB_IPIN); 170 cp = MBUF_CTOP(bp); 171 olen = plength(bp); 172 pp = bufp = MBUF_CTOP(wp); 173 *pp++ = *cp & 0177; 174 len = *cp++ << 8; 175 *pp++ = *cp; 176 len += *cp++; 177 CcpInfo.orgin += len & 0x7fff; 178 if (len & 0x8000) { 179 len1 = decompress(cp, pp, olen - 4); 180 CcpInfo.compin += olen; 181 len &= 0x7fff; 182 if (len != len1) { /* Error is detected. Send reset request */ 183 CcpSendResetReq(&CcpFsm); 184 pfree(bp); 185 return; 186 } 187 cp += olen - 4; 188 pp += len1; 189 } else { 190 CcpInfo.compin += len; 191 SyncTable(cp, pp, len); 192 cp += len; 193 pp += len; 194 } 195 *pp++ = *cp++; /* CRC */ 196 *pp++ = *cp++; 197 fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp); 198#ifdef DEBUG 199 logprintf("fcs = %04x (%s), len = %x, olen = %x\n", 200 fcs, (fcs == GOODFCS)? "good" : "bad", len, olen); 201#endif 202 if (fcs == GOODFCS) { 203 wp->offset += 2; /* skip length */ 204 wp->cnt -= 4; /* skip length & CRC */ 205 pp = MBUF_CTOP(wp); 206 proto = *pp++; 207 if (proto & 1) { 208 wp->offset++; 209 wp->cnt--; 210 } else { 211 wp->offset += 2; 212 wp->cnt -= 2; 213 proto = (proto << 8) | *pp++; 214 } 215 DecodePacket(proto, wp); 216 } 217 pfree(bp); 218} 219