pred.c revision 28679 
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
26static unsigned short int iHash, oHash;
27static unsigned char InputGuessTable[65536];
28static unsigned char OutputGuessTable[65536];
29
30static int
31compress(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
55static void
56SyncTable(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
67static int
68decompress(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
93void
94Pred1Init(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
106void
107Pred1Output(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
146void
147Pred1Input(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