pred.c revision 31921 
1/*-
2 * Copyright (c) 1997 Brian Somers <brian@Awfulhak.org>
3 *                    Ian Donaldson <iand@labtam.labtam.oz.au>
4 *                    Carsten Bormann <cabo@cs.tu-berlin.de>
5 *                    Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 *	$Id$
30 */
31
32#include <sys/param.h>
33#include <netinet/in.h>
34
35#include <stdio.h>
36#include <stdlib.h>
37#include <string.h>
38
39#include "command.h"
40#include "mbuf.h"
41#include "log.h"
42#include "defs.h"
43#include "loadalias.h"
44#include "vars.h"
45#include "timer.h"
46#include "fsm.h"
47#include "hdlc.h"
48#include "lcpproto.h"
49#include "lcp.h"
50#include "ccp.h"
51#include "pred.h"
52
53/* The following hash code is the heart of the algorithm:
54 * It builds a sliding hash sum of the previous 3-and-a-bit characters
55 * which will be used to index the guess table.
56 * A better hash function would result in additional compression,
57 * at the expense of time.
58 */
59#define IHASH(x) do {iHash = (iHash << 4) ^ (x);} while(0)
60#define OHASH(x) do {oHash = (oHash << 4) ^ (x);} while(0)
61#define GUESS_TABLE_SIZE 65536
62
63static unsigned short int iHash, oHash;
64static unsigned char *InputGuessTable;
65static unsigned char *OutputGuessTable;
66
67static int
68compress(u_char * source, u_char * dest, int len)
69{
70  int i, bitmask;
71  unsigned char *flagdest, flags, *orgdest;
72
73  orgdest = dest;
74  while (len) {
75    flagdest = dest++;
76    flags = 0;			/* All guess wrong initially */
77    for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) {
78      if (OutputGuessTable[oHash] == *source) {
79	flags |= bitmask;	/* Guess was right - don't output */
80      } else {
81	OutputGuessTable[oHash] = *source;
82	*dest++ = *source;	/* Guess wrong, output char */
83      }
84      OHASH(*source++);
85      len--;
86    }
87    *flagdest = flags;
88  }
89  return (dest - orgdest);
90}
91
92static void
93SyncTable(u_char * source, u_char * dest, int len)
94{
95
96  while (len--) {
97    if (InputGuessTable[iHash] != *source) {
98      InputGuessTable[iHash] = *source;
99    }
100    IHASH(*dest++ = *source++);
101  }
102}
103
104static int
105decompress(u_char * source, u_char * dest, int len)
106{
107  int i, bitmask;
108  unsigned char flags, *orgdest;
109
110  orgdest = dest;
111  while (len) {
112    flags = *source++;
113    len--;
114    for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
115      if (flags & bitmask) {
116	*dest = InputGuessTable[iHash];	/* Guess correct */
117      } else {
118	if (!len)
119	  break;		/* we seem to be really done -- cabo */
120	InputGuessTable[iHash] = *source;	/* Guess wrong */
121	*dest = *source++;	/* Read from source */
122	len--;
123      }
124      IHASH(*dest++);
125    }
126  }
127  return (dest - orgdest);
128}
129
130static void
131Pred1TermInput(void)
132{
133  if (InputGuessTable != NULL) {
134    free(InputGuessTable);
135    InputGuessTable = NULL;
136  }
137}
138
139static void
140Pred1TermOutput(void)
141{
142  if (OutputGuessTable != NULL) {
143    free(OutputGuessTable);
144    OutputGuessTable = NULL;
145  }
146}
147
148static void
149Pred1ResetInput(void)
150{
151  iHash = 0;
152  memset(InputGuessTable, '\0', GUESS_TABLE_SIZE);
153  LogPrintf(LogCCP, "Predictor1: Input channel reset\n");
154}
155
156static void
157Pred1ResetOutput(void)
158{
159  oHash = 0;
160  memset(OutputGuessTable, '\0', GUESS_TABLE_SIZE);
161  LogPrintf(LogCCP, "Predictor1: Output channel reset\n");
162}
163
164static int
165Pred1InitInput(void)
166{
167  if (InputGuessTable == NULL)
168    if ((InputGuessTable = malloc(GUESS_TABLE_SIZE)) == NULL)
169      return 0;
170  Pred1ResetInput();
171  return 1;
172}
173
174static int
175Pred1InitOutput(void)
176{
177  if (OutputGuessTable == NULL)
178    if ((OutputGuessTable = malloc(GUESS_TABLE_SIZE)) == NULL)
179      return 0;
180  Pred1ResetOutput();
181  return 1;
182}
183
184static int
185Pred1Output(int pri, u_short proto, struct mbuf * bp)
186{
187  struct mbuf *mwp;
188  u_char *cp, *wp, *hp;
189  int orglen, len;
190  u_char bufp[MAX_MTU + 2];
191  u_short fcs;
192
193  orglen = plength(bp) + 2;	/* add count of proto */
194  mwp = mballoc((orglen + 2) / 8 * 9 + 12, MB_HDLCOUT);
195  hp = wp = MBUF_CTOP(mwp);
196  cp = bufp;
197  *wp++ = *cp++ = orglen >> 8;
198  *wp++ = *cp++ = orglen & 0377;
199  *cp++ = proto >> 8;
200  *cp++ = proto & 0377;
201  mbread(bp, cp, orglen - 2);
202  fcs = HdlcFcs(INITFCS, bufp, 2 + orglen);
203  fcs = ~fcs;
204
205  len = compress(bufp + 2, wp, orglen);
206  LogPrintf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len);
207  CcpInfo.uncompout += orglen;
208  if (len < orglen) {
209    *hp |= 0x80;
210    wp += len;
211    CcpInfo.compout += len;
212  } else {
213    memcpy(wp, bufp + 2, orglen);
214    wp += orglen;
215    CcpInfo.compout += orglen;
216  }
217
218  *wp++ = fcs & 0377;
219  *wp++ = fcs >> 8;
220  mwp->cnt = wp - MBUF_CTOP(mwp);
221  HdlcOutput(PRI_NORMAL, PROTO_COMPD, mwp);
222  return 1;
223}
224
225static struct mbuf *
226Pred1Input(u_short *proto, struct mbuf *bp)
227{
228  u_char *cp, *pp;
229  int len, olen, len1;
230  struct mbuf *wp;
231  u_char *bufp;
232  u_short fcs;
233
234  wp = mballoc(MAX_MTU + 2, MB_IPIN);
235  cp = MBUF_CTOP(bp);
236  olen = plength(bp);
237  pp = bufp = MBUF_CTOP(wp);
238  *pp++ = *cp & 0177;
239  len = *cp++ << 8;
240  *pp++ = *cp;
241  len += *cp++;
242  CcpInfo.uncompin += len & 0x7fff;
243  if (len & 0x8000) {
244    len1 = decompress(cp, pp, olen - 4);
245    CcpInfo.compin += olen;
246    len &= 0x7fff;
247    if (len != len1) {		/* Error is detected. Send reset request */
248      LogPrintf(LogCCP, "Pred1: Length error\n");
249      CcpSendResetReq(&CcpFsm);
250      pfree(bp);
251      pfree(wp);
252      return NULL;
253    }
254    cp += olen - 4;
255    pp += len1;
256  } else {
257    CcpInfo.compin += len;
258    SyncTable(cp, pp, len);
259    cp += len;
260    pp += len;
261  }
262  *pp++ = *cp++;		/* CRC */
263  *pp++ = *cp++;
264  fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp);
265  if (fcs != GOODFCS)
266    LogPrintf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%s), len = 0x%x,"
267	      " olen = 0x%x\n", fcs, (fcs == GOODFCS) ? "good" : "bad",
268	      len, olen);
269  if (fcs == GOODFCS) {
270    wp->offset += 2;		/* skip length */
271    wp->cnt -= 4;		/* skip length & CRC */
272    pp = MBUF_CTOP(wp);
273    *proto = *pp++;
274    if (*proto & 1) {
275      wp->offset++;
276      wp->cnt--;
277    } else {
278      wp->offset += 2;
279      wp->cnt -= 2;
280      *proto = (*proto << 8) | *pp++;
281    }
282    return wp;
283  } else {
284    LogDumpBp(LogHDLC, "Bad FCS", wp);
285    CcpSendResetReq(&CcpFsm);
286    pfree(wp);
287  }
288  pfree(bp);
289  return NULL;
290}
291
292static void
293Pred1DictSetup(u_short proto, struct mbuf * bp)
294{
295}
296
297static const char *
298Pred1DispOpts(struct lcp_opt *o)
299{
300  return NULL;
301}
302
303static void
304Pred1GetOpts(struct lcp_opt *o)
305{
306  o->id = TY_PRED1;
307  o->len = 2;
308}
309
310static int
311Pred1SetOpts(struct lcp_opt *o)
312{
313  if (o->id != TY_PRED1 || o->len != 2) {
314    Pred1GetOpts(o);
315    return MODE_NAK;
316  }
317  return MODE_ACK;
318}
319
320const struct ccp_algorithm Pred1Algorithm = {
321  TY_PRED1,
322  ConfPred1,
323  Pred1DispOpts,
324  {
325    Pred1GetOpts,
326    Pred1SetOpts,
327    Pred1InitInput,
328    Pred1TermInput,
329    Pred1ResetInput,
330    Pred1Input,
331    Pred1DictSetup
332  },
333  {
334    Pred1GetOpts,
335    Pred1SetOpts,
336    Pred1InitOutput,
337    Pred1TermOutput,
338    Pred1ResetOutput,
339    Pred1Output
340  },
341};
342