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