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