pred.c revision 31514 
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.17 1997/11/22 03:37:44 brian Exp $
9 *
10 */
11
12#include <sys/param.h>
13#include <netinet/in.h>
14
15#include <stdio.h>
16#include <stdlib.h>
17#include <string.h>
18
19#include "command.h"
20#include "mbuf.h"
21#include "log.h"
22#include "defs.h"
23#include "loadalias.h"
24#include "vars.h"
25#include "timer.h"
26#include "fsm.h"
27#include "hdlc.h"
28#include "lcpproto.h"
29#include "lcp.h"
30#include "ccp.h"
31#include "pred.h"
32
33/* The following hash code is the heart of the algorithm:
34 * It builds a sliding hash sum of the previous 3-and-a-bit characters
35 * which will be used to index the guess table.
36 * A better hash function would result in additional compression,
37 * at the expense of time.
38 */
39#define IHASH(x) do {iHash = (iHash << 4) ^ (x);} while(0)
40#define OHASH(x) do {oHash = (oHash << 4) ^ (x);} while(0)
41#define GUESS_TABLE_SIZE 65536
42
43static unsigned short int iHash, oHash;
44static unsigned char *InputGuessTable;
45static unsigned char *OutputGuessTable;
46
47static int
48compress(u_char * source, u_char * dest, int len)
49{
50  int i, bitmask;
51  unsigned char *flagdest, flags, *orgdest;
52
53  orgdest = dest;
54  while (len) {
55    flagdest = dest++;
56    flags = 0;			/* All guess wrong initially */
57    for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) {
58      if (OutputGuessTable[oHash] == *source) {
59	flags |= bitmask;	/* Guess was right - don't output */
60      } else {
61	OutputGuessTable[oHash] = *source;
62	*dest++ = *source;	/* Guess wrong, output char */
63      }
64      OHASH(*source++);
65      len--;
66    }
67    *flagdest = flags;
68  }
69  return (dest - orgdest);
70}
71
72static void
73SyncTable(u_char * source, u_char * dest, int len)
74{
75
76  while (len--) {
77    if (InputGuessTable[iHash] != *source) {
78      InputGuessTable[iHash] = *source;
79    }
80    IHASH(*dest++ = *source++);
81  }
82}
83
84static int
85decompress(u_char * source, u_char * dest, int len)
86{
87  int i, bitmask;
88  unsigned char flags, *orgdest;
89
90  orgdest = dest;
91  while (len) {
92    flags = *source++;
93    len--;
94    for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
95      if (flags & bitmask) {
96	*dest = InputGuessTable[iHash];	/* Guess correct */
97      } else {
98	if (!len)
99	  break;		/* we seem to be really done -- cabo */
100	InputGuessTable[iHash] = *source;	/* Guess wrong */
101	*dest = *source++;	/* Read from source */
102	len--;
103      }
104      IHASH(*dest++);
105    }
106  }
107  return (dest - orgdest);
108}
109
110static void
111Pred1TermInput(void)
112{
113  if (InputGuessTable != NULL) {
114    free(InputGuessTable);
115    InputGuessTable = NULL;
116  }
117}
118
119static void
120Pred1TermOutput(void)
121{
122  if (OutputGuessTable != NULL) {
123    free(OutputGuessTable);
124    OutputGuessTable = NULL;
125  }
126}
127
128static void
129Pred1ResetInput(void)
130{
131  iHash = 0;
132  memset(InputGuessTable, '\0', GUESS_TABLE_SIZE);
133  LogPrintf(LogCCP, "Predictor1: Input channel reset\n");
134}
135
136static void
137Pred1ResetOutput(void)
138{
139  oHash = 0;
140  memset(OutputGuessTable, '\0', GUESS_TABLE_SIZE);
141  LogPrintf(LogCCP, "Predictor1: Output channel reset\n");
142}
143
144static int
145Pred1InitInput(void)
146{
147  if (InputGuessTable == NULL)
148    if ((InputGuessTable = malloc(GUESS_TABLE_SIZE)) == NULL)
149      return 0;
150  Pred1ResetInput();
151  return 1;
152}
153
154static int
155Pred1InitOutput(void)
156{
157  if (OutputGuessTable == NULL)
158    if ((OutputGuessTable = malloc(GUESS_TABLE_SIZE)) == NULL)
159      return 0;
160  Pred1ResetOutput();
161  return 1;
162}
163
164static int
165Pred1Output(int pri, u_short proto, struct mbuf * bp)
166{
167  struct mbuf *mwp;
168  u_char *cp, *wp, *hp;
169  int orglen, len;
170  u_char bufp[MAX_MTU + 2];
171  u_short fcs;
172
173  orglen = plength(bp) + 2;	/* add count of proto */
174  mwp = mballoc((orglen + 2) / 8 * 9 + 12, MB_HDLCOUT);
175  hp = wp = MBUF_CTOP(mwp);
176  cp = bufp;
177  *wp++ = *cp++ = orglen >> 8;
178  *wp++ = *cp++ = orglen & 0377;
179  *cp++ = proto >> 8;
180  *cp++ = proto & 0377;
181  mbread(bp, cp, orglen - 2);
182  fcs = HdlcFcs(INITFCS, bufp, 2 + orglen);
183  fcs = ~fcs;
184
185  len = compress(bufp + 2, wp, orglen);
186  LogPrintf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len);
187  CcpInfo.uncompout += orglen;
188  if (len < orglen) {
189    *hp |= 0x80;
190    wp += len;
191    CcpInfo.compout += len;
192  } else {
193    memcpy(wp, bufp + 2, orglen);
194    wp += orglen;
195    CcpInfo.compout += orglen;
196  }
197
198  *wp++ = fcs & 0377;
199  *wp++ = fcs >> 8;
200  mwp->cnt = wp - MBUF_CTOP(mwp);
201  HdlcOutput(PRI_NORMAL, PROTO_COMPD, mwp);
202  return 1;
203}
204
205static struct mbuf *
206Pred1Input(u_short *proto, struct mbuf *bp)
207{
208  u_char *cp, *pp;
209  int len, olen, len1;
210  struct mbuf *wp;
211  u_char *bufp;
212  u_short fcs;
213
214  wp = mballoc(MAX_MTU + 2, MB_IPIN);
215  cp = MBUF_CTOP(bp);
216  olen = plength(bp);
217  pp = bufp = MBUF_CTOP(wp);
218  *pp++ = *cp & 0177;
219  len = *cp++ << 8;
220  *pp++ = *cp;
221  len += *cp++;
222  CcpInfo.uncompin += len & 0x7fff;
223  if (len & 0x8000) {
224    len1 = decompress(cp, pp, olen - 4);
225    CcpInfo.compin += olen;
226    len &= 0x7fff;
227    if (len != len1) {		/* Error is detected. Send reset request */
228      LogPrintf(LogCCP, "Pred1: Length error\n");
229      CcpSendResetReq(&CcpFsm);
230      pfree(bp);
231      pfree(wp);
232      return NULL;
233    }
234    cp += olen - 4;
235    pp += len1;
236  } else {
237    CcpInfo.compin += len;
238    SyncTable(cp, pp, len);
239    cp += len;
240    pp += len;
241  }
242  *pp++ = *cp++;		/* CRC */
243  *pp++ = *cp++;
244  fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp);
245  if (fcs != GOODFCS)
246    LogPrintf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%s), len = 0x%x,"
247	      " olen = 0x%x\n", fcs, (fcs == GOODFCS) ? "good" : "bad",
248	      len, olen);
249  if (fcs == GOODFCS) {
250    wp->offset += 2;		/* skip length */
251    wp->cnt -= 4;		/* skip length & CRC */
252    pp = MBUF_CTOP(wp);
253    *proto = *pp++;
254    if (*proto & 1) {
255      wp->offset++;
256      wp->cnt--;
257    } else {
258      wp->offset += 2;
259      wp->cnt -= 2;
260      *proto = (*proto << 8) | *pp++;
261    }
262    return wp;
263  } else {
264    LogDumpBp(LogHDLC, "Bad FCS", wp);
265    CcpSendResetReq(&CcpFsm);
266    pfree(wp);
267  }
268  pfree(bp);
269  return NULL;
270}
271
272static void
273Pred1DictSetup(u_short proto, struct mbuf * bp)
274{
275}
276
277static const char *
278Pred1DispOpts(struct lcp_opt *o)
279{
280  return NULL;
281}
282
283static void
284Pred1GetOpts(struct lcp_opt *o)
285{
286  o->id = TY_PRED1;
287  o->len = 2;
288}
289
290static int
291Pred1SetOpts(struct lcp_opt *o)
292{
293  if (o->id != TY_PRED1 || o->len != 2) {
294    Pred1GetOpts(o);
295    return MODE_NAK;
296  }
297  return MODE_ACK;
298}
299
300const struct ccp_algorithm Pred1Algorithm = {
301  TY_PRED1,
302  ConfPred1,
303  Pred1DispOpts,
304  {
305    Pred1GetOpts,
306    Pred1SetOpts,
307    Pred1InitInput,
308    Pred1TermInput,
309    Pred1ResetInput,
310    Pred1Input,
311    Pred1DictSetup
312  },
313  {
314    Pred1GetOpts,
315    Pred1SetOpts,
316    Pred1InitOutput,
317    Pred1TermOutput,
318    Pred1ResetOutput,
319    Pred1Output
320  },
321};
322