1/*-
2 * Copyright (c) 1997 Brian Somers <brian@Awfulhak.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD: src/usr.sbin/ppp/deflate.c,v 1.26.26.1 2010/12/21 17:10:29 kensmith Exp $
27 */
28
29#include <sys/types.h>
30
31#include <stdio.h>
32#include <stdlib.h>
33#include <zlib.h>
34
35#include "mbuf.h"
36#include "log.h"
37#include "timer.h"
38#include "fsm.h"
39#include "ccp.h"
40#include "deflate.h"
41
42/* Our state */
43struct deflate_state {
44    u_short seqno;
45    int uncomp_rec;
46    int winsize;
47    z_stream cx;
48};
49
50static char garbage[10];
51static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff };
52
53#define DEFLATE_CHUNK_LEN (1536 - sizeof(struct mbuf))
54
55static int
56DeflateResetOutput(void *v)
57{
58  struct deflate_state *state = (struct deflate_state *)v;
59
60  state->seqno = 0;
61  state->uncomp_rec = 0;
62  deflateReset(&state->cx);
63  log_Printf(LogCCP, "Deflate: Output channel reset\n");
64
65  return 1;		/* Ask FSM to ACK */
66}
67
68static struct mbuf *
69DeflateOutput(void *v, struct ccp *ccp, struct link *l __unused,
70	      int pri __unused, u_short *proto, struct mbuf *mp)
71{
72  struct deflate_state *state = (struct deflate_state *)v;
73  u_char *wp, *rp;
74  int olen, ilen, len, res, flush;
75  struct mbuf *mo_head, *mo, *mi_head, *mi;
76
77  ilen = m_length(mp);
78  log_Printf(LogDEBUG, "DeflateOutput: Proto %02x (%d bytes)\n", *proto, ilen);
79  log_DumpBp(LogDEBUG, "DeflateOutput: Compress packet:", mp);
80
81  /* Stuff the protocol in front of the input */
82  mi_head = mi = m_get(2, MB_CCPOUT);
83  mi->m_next = mp;
84  rp = MBUF_CTOP(mi);
85  if (*proto < 0x100) {			/* Compress the protocol */
86    rp[0] = *proto & 0377;
87    mi->m_len = 1;
88  } else {				/* Don't compress the protocol */
89    rp[0] = *proto >> 8;
90    rp[1] = *proto & 0377;
91    mi->m_len = 2;
92  }
93
94  /* Allocate the initial output mbuf */
95  mo_head = mo = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT);
96  mo->m_len = 2;
97  wp = MBUF_CTOP(mo);
98  *wp++ = state->seqno >> 8;
99  *wp++ = state->seqno & 0377;
100  log_Printf(LogDEBUG, "DeflateOutput: Seq %d\n", state->seqno);
101  state->seqno++;
102
103  /* Set up the deflation context */
104  state->cx.next_out = wp;
105  state->cx.avail_out = DEFLATE_CHUNK_LEN - 2;
106  state->cx.next_in = MBUF_CTOP(mi);
107  state->cx.avail_in = mi->m_len;
108  flush = Z_NO_FLUSH;
109
110  olen = 0;
111  while (1) {
112    if ((res = deflate(&state->cx, flush)) != Z_OK) {
113      if (res == Z_STREAM_END)
114        break;			/* Done */
115      log_Printf(LogWARN, "DeflateOutput: deflate returned %d (%s)\n",
116                res, state->cx.msg ? state->cx.msg : "");
117      m_freem(mo_head);
118      m_free(mi_head);
119      state->seqno--;
120      return mp;		/* Our dictionary's probably dead now :-( */
121    }
122
123    if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
124      break;
125
126    if (state->cx.avail_in == 0 && mi->m_next != NULL) {
127      mi = mi->m_next;
128      state->cx.next_in = MBUF_CTOP(mi);
129      state->cx.avail_in = mi->m_len;
130      if (mi->m_next == NULL)
131        flush = Z_SYNC_FLUSH;
132    }
133
134    if (state->cx.avail_out == 0) {
135      mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT);
136      olen += (mo->m_len = DEFLATE_CHUNK_LEN);
137      mo = mo->m_next;
138      mo->m_len = 0;
139      state->cx.next_out = MBUF_CTOP(mo);
140      state->cx.avail_out = DEFLATE_CHUNK_LEN;
141    }
142  }
143
144  olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out);
145  olen -= 4;		/* exclude the trailing EMPTY_BLOCK */
146
147  /*
148   * If the output packet (including seqno and excluding the EMPTY_BLOCK)
149   * got bigger, send the original.
150   */
151  if (olen >= ilen) {
152    m_freem(mo_head);
153    m_free(mi_head);
154    log_Printf(LogDEBUG, "DeflateOutput: %d => %d: Uncompressible (0x%04x)\n",
155              ilen, olen, *proto);
156    ccp->uncompout += ilen;
157    ccp->compout += ilen;	/* We measure this stuff too */
158    return mp;
159  }
160
161  m_freem(mi_head);
162
163  /*
164   * Lose the last four bytes of our output.
165   * XXX: We should probably assert that these are the same as the
166   *      contents of EMPTY_BLOCK.
167   */
168  mo = mo_head;
169  for (len = mo->m_len; len < olen; mo = mo->m_next, len += mo->m_len)
170    ;
171  mo->m_len -= len - olen;
172  if (mo->m_next != NULL) {
173    m_freem(mo->m_next);
174    mo->m_next = NULL;
175  }
176
177  ccp->uncompout += ilen;
178  ccp->compout += olen;
179
180  log_Printf(LogDEBUG, "DeflateOutput: %d => %d bytes, proto 0x%04x\n",
181            ilen, olen, *proto);
182
183  *proto = ccp_Proto(ccp);
184  return mo_head;
185}
186
187static void
188DeflateResetInput(void *v)
189{
190  struct deflate_state *state = (struct deflate_state *)v;
191
192  state->seqno = 0;
193  state->uncomp_rec = 0;
194  inflateReset(&state->cx);
195  log_Printf(LogCCP, "Deflate: Input channel reset\n");
196}
197
198static struct mbuf *
199DeflateInput(void *v, struct ccp *ccp, u_short *proto, struct mbuf *mi)
200{
201  struct deflate_state *state = (struct deflate_state *)v;
202  struct mbuf *mo, *mo_head, *mi_head;
203  u_char *wp;
204  int ilen, olen;
205  int seq, flush, res, first;
206  u_char hdr[2];
207
208  log_DumpBp(LogDEBUG, "DeflateInput: Decompress packet:", mi);
209  mi_head = mi = mbuf_Read(mi, hdr, 2);
210  ilen = 2;
211
212  /* Check the sequence number. */
213  seq = (hdr[0] << 8) + hdr[1];
214  log_Printf(LogDEBUG, "DeflateInput: Seq %d\n", seq);
215  if (seq != state->seqno) {
216    if (seq <= state->uncomp_rec)
217      /*
218       * So the peer's started at zero again - fine !  If we're wrong,
219       * inflate() will fail.  This is better than getting into a loop
220       * trying to get a ResetReq to a busy sender.
221       */
222      state->seqno = seq;
223    else {
224      log_Printf(LogCCP, "DeflateInput: Seq error: Got %d, expected %d\n",
225                seq, state->seqno);
226      m_freem(mi_head);
227      ccp_SendResetReq(&ccp->fsm);
228      return NULL;
229    }
230  }
231  state->seqno++;
232  state->uncomp_rec = 0;
233
234  /* Allocate an output mbuf */
235  mo_head = mo = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN);
236
237  /* Our proto starts with 0 if it's compressed */
238  wp = MBUF_CTOP(mo);
239  wp[0] = '\0';
240
241  /*
242   * We set avail_out to 1 initially so we can look at the first
243   * byte of the output and decide whether we have a compressed
244   * proto field.
245   */
246  state->cx.next_in = MBUF_CTOP(mi);
247  state->cx.avail_in = mi->m_len;
248  state->cx.next_out = wp + 1;
249  state->cx.avail_out = 1;
250  ilen += mi->m_len;
251
252  flush = mi->m_next ? Z_NO_FLUSH : Z_SYNC_FLUSH;
253  first = 1;
254  olen = 0;
255
256  while (1) {
257    if ((res = inflate(&state->cx, flush)) != Z_OK) {
258      if (res == Z_STREAM_END)
259        break;			/* Done */
260      log_Printf(LogCCP, "DeflateInput: inflate returned %d (%s)\n",
261                res, state->cx.msg ? state->cx.msg : "");
262      m_freem(mo_head);
263      m_freem(mi);
264      ccp_SendResetReq(&ccp->fsm);
265      return NULL;
266    }
267
268    if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
269      break;
270
271    if (state->cx.avail_in == 0 && mi && (mi = m_free(mi)) != NULL) {
272      /* underflow */
273      state->cx.next_in = MBUF_CTOP(mi);
274      ilen += (state->cx.avail_in = mi->m_len);
275      if (mi->m_next == NULL)
276        flush = Z_SYNC_FLUSH;
277    }
278
279    if (state->cx.avail_out == 0) {
280      /* overflow */
281      if (first) {
282        if (!(wp[1] & 1)) {
283          /* 2 byte proto, shuffle it back in output */
284          wp[0] = wp[1];
285          state->cx.next_out--;
286          state->cx.avail_out = DEFLATE_CHUNK_LEN-1;
287        } else
288          state->cx.avail_out = DEFLATE_CHUNK_LEN-2;
289        first = 0;
290      } else {
291        olen += (mo->m_len = DEFLATE_CHUNK_LEN);
292        mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN);
293        mo = mo->m_next;
294        state->cx.next_out = MBUF_CTOP(mo);
295        state->cx.avail_out = DEFLATE_CHUNK_LEN;
296      }
297    }
298  }
299
300  if (mi != NULL)
301    m_freem(mi);
302
303  if (first) {
304    log_Printf(LogCCP, "DeflateInput: Length error\n");
305    m_freem(mo_head);
306    ccp_SendResetReq(&ccp->fsm);
307    return NULL;
308  }
309
310  olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out);
311
312  *proto = ((u_short)wp[0] << 8) | wp[1];
313  mo_head->m_offset += 2;
314  mo_head->m_len -= 2;
315  olen -= 2;
316
317  ccp->compin += ilen;
318  ccp->uncompin += olen;
319
320  log_Printf(LogDEBUG, "DeflateInput: %d => %d bytes, proto 0x%04x\n",
321            ilen, olen, *proto);
322
323  /*
324   * Simulate an EMPTY_BLOCK so that our dictionary stays in sync.
325   * The peer will have silently removed this!
326   */
327  state->cx.next_out = garbage;
328  state->cx.avail_out = sizeof garbage;
329  state->cx.next_in = EMPTY_BLOCK;
330  state->cx.avail_in = sizeof EMPTY_BLOCK;
331  inflate(&state->cx, Z_SYNC_FLUSH);
332
333  return mo_head;
334}
335
336static void
337DeflateDictSetup(void *v, struct ccp *ccp, u_short proto, struct mbuf *mi)
338{
339  struct deflate_state *state = (struct deflate_state *)v;
340  int res, flush, expect_error;
341  u_char *rp;
342  struct mbuf *mi_head;
343  short len;
344
345  log_Printf(LogDEBUG, "DeflateDictSetup: Got seq %d\n", state->seqno);
346
347  /*
348   * Stuff an ``uncompressed data'' block header followed by the
349   * protocol in front of the input
350   */
351  mi_head = m_get(7, MB_CCPOUT);
352  mi_head->m_next = mi;
353  len = m_length(mi);
354  mi = mi_head;
355  rp = MBUF_CTOP(mi);
356  if (proto < 0x100) {			/* Compress the protocol */
357    rp[5] = proto & 0377;
358    mi->m_len = 6;
359    len++;
360  } else {				/* Don't compress the protocol */
361    rp[5] = proto >> 8;
362    rp[6] = proto & 0377;
363    mi->m_len = 7;
364    len += 2;
365  }
366  rp[0] = 0x80;				/* BITS: 100xxxxx */
367  rp[1] = len & 0377;			/* The length */
368  rp[2] = len >> 8;
369  rp[3] = (~len) & 0377;		/* One's compliment of the length */
370  rp[4] = (~len) >> 8;
371
372  state->cx.next_in = rp;
373  state->cx.avail_in = mi->m_len;
374  state->cx.next_out = garbage;
375  state->cx.avail_out = sizeof garbage;
376  flush = Z_NO_FLUSH;
377  expect_error = 0;
378
379  while (1) {
380    if ((res = inflate(&state->cx, flush)) != Z_OK) {
381      if (res == Z_STREAM_END)
382        break;			/* Done */
383      if (expect_error && res == Z_BUF_ERROR)
384        break;
385      log_Printf(LogCCP, "DeflateDictSetup: inflate returned %d (%s)\n",
386                res, state->cx.msg ? state->cx.msg : "");
387      log_Printf(LogCCP, "DeflateDictSetup: avail_in %d, avail_out %d\n",
388                state->cx.avail_in, state->cx.avail_out);
389      ccp_SendResetReq(&ccp->fsm);
390      m_free(mi_head);		/* lose our allocated ``head'' buf */
391      return;
392    }
393
394    if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
395      break;
396
397    if (state->cx.avail_in == 0 && mi && (mi = mi->m_next) != NULL) {
398      /* underflow */
399      state->cx.next_in = MBUF_CTOP(mi);
400      state->cx.avail_in = mi->m_len;
401      if (mi->m_next == NULL)
402        flush = Z_SYNC_FLUSH;
403    }
404
405    if (state->cx.avail_out == 0) {
406      if (state->cx.avail_in == 0)
407        /*
408         * This seems to be a bug in libz !  If inflate() finished
409         * with 0 avail_in and 0 avail_out *and* this is the end of
410         * our input *and* inflate() *has* actually written all the
411         * output it's going to, it *doesn't* return Z_STREAM_END !
412         * When we subsequently call it with no more input, it gives
413         * us Z_BUF_ERROR :-(  It seems pretty safe to ignore this
414         * error (the dictionary seems to stay in sync).  In the worst
415         * case, we'll drop the next compressed packet and do a
416         * CcpReset() then.
417         */
418        expect_error = 1;
419      /* overflow */
420      state->cx.next_out = garbage;
421      state->cx.avail_out = sizeof garbage;
422    }
423  }
424
425  ccp->compin += len;
426  ccp->uncompin += len;
427
428  state->seqno++;
429  state->uncomp_rec++;
430  m_free(mi_head);		/* lose our allocated ``head'' buf */
431}
432
433static const char *
434DeflateDispOpts(struct fsm_opt *o)
435{
436  static char disp[7];		/* Must be used immediately */
437
438  sprintf(disp, "win %d", (o->data[0]>>4) + 8);
439  return disp;
440}
441
442static void
443DeflateInitOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o,
444                      const struct ccp_config *cfg)
445{
446  o->hdr.len = 4;
447  o->data[0] = ((cfg->deflate.out.winsize - 8) << 4) + 8;
448  o->data[1] = '\0';
449}
450
451static int
452DeflateSetOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o,
453                     const struct ccp_config *cfg __unused)
454{
455  if (o->hdr.len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0')
456    return MODE_REJ;
457
458  if ((o->data[0] >> 4) + 8 > 15) {
459    o->data[0] = ((15 - 8) << 4) + 8;
460    return MODE_NAK;
461  }
462
463  return MODE_ACK;
464}
465
466static int
467DeflateSetOptsInput(struct bundle *bundle __unused, struct fsm_opt *o,
468                    const struct ccp_config *cfg)
469{
470  int want;
471
472  if (o->hdr.len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0')
473    return MODE_REJ;
474
475  want = (o->data[0] >> 4) + 8;
476  if (cfg->deflate.in.winsize == 0) {
477    if (want < 8 || want > 15) {
478      o->data[0] = ((15 - 8) << 4) + 8;
479    }
480  } else if (want != cfg->deflate.in.winsize) {
481    o->data[0] = ((cfg->deflate.in.winsize - 8) << 4) + 8;
482    return MODE_NAK;
483  }
484
485  return MODE_ACK;
486}
487
488static void *
489DeflateInitInput(struct bundle *bundle __unused, struct fsm_opt *o)
490{
491  struct deflate_state *state;
492
493  state = (struct deflate_state *)malloc(sizeof(struct deflate_state));
494  if (state != NULL) {
495    state->winsize = (o->data[0] >> 4) + 8;
496    state->cx.zalloc = NULL;
497    state->cx.opaque = NULL;
498    state->cx.zfree = NULL;
499    state->cx.next_out = NULL;
500    if (inflateInit2(&state->cx, -state->winsize) == Z_OK)
501      DeflateResetInput(state);
502    else {
503      free(state);
504      state = NULL;
505    }
506  }
507
508  return state;
509}
510
511static void *
512DeflateInitOutput(struct bundle *bundle __unused, struct fsm_opt *o)
513{
514  struct deflate_state *state;
515
516  state = (struct deflate_state *)malloc(sizeof(struct deflate_state));
517  if (state != NULL) {
518    state->winsize = (o->data[0] >> 4) + 8;
519    state->cx.zalloc = NULL;
520    state->cx.opaque = NULL;
521    state->cx.zfree = NULL;
522    state->cx.next_in = NULL;
523    if (deflateInit2(&state->cx, Z_DEFAULT_COMPRESSION, 8,
524                     -state->winsize, 8, Z_DEFAULT_STRATEGY) == Z_OK)
525      DeflateResetOutput(state);
526    else {
527      free(state);
528      state = NULL;
529    }
530  }
531
532  return state;
533}
534
535static void
536DeflateTermInput(void *v)
537{
538  struct deflate_state *state = (struct deflate_state *)v;
539
540  inflateEnd(&state->cx);
541  free(state);
542}
543
544static void
545DeflateTermOutput(void *v)
546{
547  struct deflate_state *state = (struct deflate_state *)v;
548
549  deflateEnd(&state->cx);
550  free(state);
551}
552
553const struct ccp_algorithm PppdDeflateAlgorithm = {
554  TY_PPPD_DEFLATE,	/* Older versions of pppd expected this ``type'' */
555  CCP_NEG_DEFLATE24,
556  DeflateDispOpts,
557  ccp_DefaultUsable,
558  ccp_DefaultRequired,
559  {
560    DeflateSetOptsInput,
561    DeflateInitInput,
562    DeflateTermInput,
563    DeflateResetInput,
564    DeflateInput,
565    DeflateDictSetup
566  },
567  {
568    0,
569    DeflateInitOptsOutput,
570    DeflateSetOptsOutput,
571    DeflateInitOutput,
572    DeflateTermOutput,
573    DeflateResetOutput,
574    DeflateOutput
575  },
576};
577
578const struct ccp_algorithm DeflateAlgorithm = {
579  TY_DEFLATE,		/* rfc 1979 */
580  CCP_NEG_DEFLATE,
581  DeflateDispOpts,
582  ccp_DefaultUsable,
583  ccp_DefaultRequired,
584  {
585    DeflateSetOptsInput,
586    DeflateInitInput,
587    DeflateTermInput,
588    DeflateResetInput,
589    DeflateInput,
590    DeflateDictSetup
591  },
592  {
593    0,
594    DeflateInitOptsOutput,
595    DeflateSetOptsOutput,
596    DeflateInitOutput,
597    DeflateTermOutput,
598    DeflateResetOutput,
599    DeflateOutput
600  },
601};
602