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