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