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.12 1997/06/09 03:27:35 brian 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) do {iHash = (iHash << 4) ^ (x);} while(0) 24 #define OHASH(x) do {oHash = (oHash << 4) ^ (x);} while(0) 25 26 static unsigned short int iHash, oHash; 27 static unsigned char InputGuessTable[65536]; 28 static unsigned char OutputGuessTable[65536]; 29 30 static int 31 compress(source, dest, len) 32 unsigned char *source, *dest; 33 int 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 55 static void 56 SyncTable(source, dest, len) 57 unsigned char *source, *dest; 58 int len; 59 { 60 61 while (len--) { 62 if (InputGuessTable[iHash] != *source) { 63 InputGuessTable[iHash] = *source; 64 } 65 IHASH(*dest++ = *source++); 66 } 67 } 68 69 static int 70 decompress(source, dest, len) 71 unsigned char *source, *dest; 72 int len; 73 { 74 int i, bitmask; 75 unsigned char flags, *orgdest; 76 77 orgdest = dest; 78 while (len) { 79 flags = *source++; 80 len--; 81 for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 82 if (flags & bitmask) { 83 *dest = InputGuessTable[iHash]; /* Guess correct */ 84 } else { 85 if (!len) 86 break; /* we seem to be really done -- cabo */ 87 InputGuessTable[iHash] = *source; /* Guess wrong */ 88 *dest = *source++; /* Read from source */ 89 len--; 90 } 91 IHASH(*dest++); 92 } 93 } 94 return(dest - orgdest); 95 } 96 97 void 98 Pred1Init(direction) 99 int direction; 100 { 101 if (direction & 1) { /* Input part */ 102 iHash = 0; 103 bzero(InputGuessTable, sizeof(InputGuessTable)); 104 } 105 if (direction & 2) { /* Output part */ 106 oHash = 0; 107 bzero(OutputGuessTable, sizeof(OutputGuessTable)); 108 } 109 } 110 111 void 112 Pred1Output(int pri, u_short proto, struct mbuf *bp) 113 { 114 struct mbuf *mwp; 115 u_char *cp, *wp, *hp; 116 int orglen, len; 117 u_char bufp[MAX_MTU+2]; 118 u_short fcs; 119 120 orglen = plength(bp) + 2; /* add count of proto */ 121 mwp = mballoc((orglen+2)/8*9+12, MB_HDLCOUT); 122 hp = wp = MBUF_CTOP(mwp); 123 cp = bufp; 124 *wp++ = *cp++ = orglen >> 8; 125 *wp++ = *cp++ = orglen & 0377; 126 *cp++ = proto >> 8; 127 *cp++ = proto & 0377; 128 mbread(bp, cp, orglen-2); 129 fcs = HdlcFcs(INITFCS, bufp, 2+orglen); 130 fcs = ~fcs; 131 132 len = compress(bufp + 2, wp, orglen); 133 LogPrintf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len); 134 CcpInfo.orgout += orglen; 135 if (len < orglen) { 136 *hp |= 0x80; 137 wp += len; 138 CcpInfo.compout += len; 139 } else { 140 bcopy(bufp+2, wp, orglen); 141 wp += orglen; 142 CcpInfo.compout += orglen; 143 } 144 145 *wp++ = fcs & 0377; 146 *wp++ = fcs >> 8; 147 mwp->cnt = wp - MBUF_CTOP(mwp); 148 HdlcOutput(PRI_NORMAL, PROTO_COMPD, mwp); 149 } 150 151 void 152 Pred1Input(bp) 153 struct mbuf *bp; 154 { 155 u_char *cp, *pp; 156 int len, olen, len1; 157 struct mbuf *wp; 158 u_char *bufp; 159 u_short fcs, proto; 160 161 wp = mballoc(MAX_MTU+2, MB_IPIN); 162 cp = MBUF_CTOP(bp); 163 olen = plength(bp); 164 pp = bufp = MBUF_CTOP(wp); 165 *pp++ = *cp & 0177; 166 len = *cp++ << 8; 167 *pp++ = *cp; 168 len += *cp++; 169 CcpInfo.orgin += len & 0x7fff; 170 if (len & 0x8000) { 171 len1 = decompress(cp, pp, olen - 4); 172 CcpInfo.compin += olen; 173 len &= 0x7fff; 174 if (len != len1) { /* Error is detected. Send reset request */ 175 LogPrintf(LogLCP, "%s: Length Error\n", CcpFsm.name); 176 CcpSendResetReq(&CcpFsm); 177 pfree(bp); 178 pfree(wp); 179 return; 180 } 181 cp += olen - 4; 182 pp += len1; 183 } else { 184 CcpInfo.compin += len; 185 SyncTable(cp, pp, len); 186 cp += len; 187 pp += len; 188 } 189 *pp++ = *cp++; /* CRC */ 190 *pp++ = *cp++; 191 fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp); 192 if (fcs != GOODFCS) 193 LogPrintf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%s), len = 0x%x," 194 " olen = 0x%x\n", fcs, (fcs == GOODFCS)? "good" : "bad", 195 len, olen); 196 if (fcs == GOODFCS) { 197 wp->offset += 2; /* skip length */ 198 wp->cnt -= 4; /* skip length & CRC */ 199 pp = MBUF_CTOP(wp); 200 proto = *pp++; 201 if (proto & 1) { 202 wp->offset++; 203 wp->cnt--; 204 } else { 205 wp->offset += 2; 206 wp->cnt -= 2; 207 proto = (proto << 8) | *pp++; 208 } 209 DecodePacket(proto, wp); 210 } 211 else 212 { 213 LogDumpBp(LogHDLC, "Bad FCS", wp); 214 CcpSendResetReq(&CcpFsm); 215 pfree(wp); 216 } 217 pfree(bp); 218 } 219