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