deflate.c revision 34536 
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 *	$Id: deflate.c,v 1.6 1998/01/10 01:55:09 brian Exp $
27 */
28
29#include <sys/param.h>
30#include <netinet/in.h>
31
32#include <stdio.h>
33#include <stdlib.h>
34#include <zlib.h>
35
36#include "command.h"
37#include "mbuf.h"
38#include "log.h"
39#include "defs.h"
40#include "loadalias.h"
41#include "vars.h"
42#include "hdlc.h"
43#include "lcp.h"
44#include "ccp.h"
45#include "lcpproto.h"
46#include "timer.h"
47#include "fsm.h"
48#include "deflate.h"
49
50/* Our state */
51struct deflate_state {
52    u_short seqno;
53    int uncomp_rec;
54    z_stream cx;
55};
56
57static int iWindowSize = 15;
58static int oWindowSize = 15;
59static struct deflate_state InputState, OutputState;
60static char garbage[10];
61static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff };
62
63#define DEFLATE_CHUNK_LEN 1024		/* Allocate mbufs this size */
64
65static void
66DeflateResetOutput(void)
67{
68  OutputState.seqno = 0;
69  OutputState.uncomp_rec = 0;
70  deflateReset(&OutputState.cx);
71  LogPrintf(LogCCP, "Deflate: Output channel reset\n");
72}
73
74static int
75DeflateOutput(int pri, u_short proto, struct mbuf *mp)
76{
77  u_char *wp, *rp;
78  int olen, ilen, len, res, flush;
79  struct mbuf *mo_head, *mo, *mi_head, *mi;
80
81  ilen = plength(mp);
82  LogPrintf(LogDEBUG, "DeflateOutput: Proto %02x (%d bytes)\n", proto, ilen);
83  LogDumpBp(LogDEBUG, "DeflateOutput: Compress packet:", mp);
84
85  /* Stuff the protocol in front of the input */
86  mi_head = mi = mballoc(2, MB_HDLCOUT);
87  mi->next = mp;
88  rp = MBUF_CTOP(mi);
89  if (proto < 0x100) {			/* Compress the protocol */
90    rp[0] = proto & 0377;
91    mi->cnt = 1;
92  } else {				/* Don't compress the protocol */
93    rp[0] = proto >> 8;
94    rp[1] = proto & 0377;
95    mi->cnt = 2;
96  }
97
98  /* Allocate the initial output mbuf */
99  mo_head = mo = mballoc(DEFLATE_CHUNK_LEN, MB_HDLCOUT);
100  mo->cnt = 2;
101  wp = MBUF_CTOP(mo);
102  *wp++ = OutputState.seqno >> 8;
103  *wp++ = OutputState.seqno & 0377;
104  LogPrintf(LogDEBUG, "DeflateOutput: Seq %d\n", OutputState.seqno);
105  OutputState.seqno++;
106
107  /* Set up the deflation context */
108  OutputState.cx.next_out = wp;
109  OutputState.cx.avail_out = DEFLATE_CHUNK_LEN - 2;
110  OutputState.cx.next_in = MBUF_CTOP(mi);
111  OutputState.cx.avail_in = mi->cnt;
112  flush = Z_NO_FLUSH;
113
114  olen = 0;
115  while (1) {
116    if ((res = deflate(&OutputState.cx, flush)) != Z_OK) {
117      if (res == Z_STREAM_END)
118        break;			/* Done */
119      LogPrintf(LogERROR, "DeflateOutput: deflate returned %d (%s)\n",
120                res, OutputState.cx.msg ? OutputState.cx.msg : "");
121      pfree(mo_head);
122      mbfree(mi_head);
123      OutputState.seqno--;
124      return 1;			/* packet dropped */
125    }
126
127    if (flush == Z_SYNC_FLUSH && OutputState.cx.avail_out != 0)
128      break;
129
130    if (OutputState.cx.avail_in == 0 && mi->next != NULL) {
131      mi = mi->next;
132      OutputState.cx.next_in = MBUF_CTOP(mi);
133      OutputState.cx.avail_in = mi->cnt;
134      if (mi->next == NULL)
135        flush = Z_SYNC_FLUSH;
136    }
137
138    if (OutputState.cx.avail_out == 0) {
139      mo->next = mballoc(DEFLATE_CHUNK_LEN, MB_HDLCOUT);
140      olen += (mo->cnt = DEFLATE_CHUNK_LEN);
141      mo = mo->next;
142      mo->cnt = 0;
143      OutputState.cx.next_out = MBUF_CTOP(mo);
144      OutputState.cx.avail_out = DEFLATE_CHUNK_LEN;
145    }
146  }
147
148  olen += (mo->cnt = DEFLATE_CHUNK_LEN - OutputState.cx.avail_out);
149  olen -= 4;		/* exclude the trailing EMPTY_BLOCK */
150
151  /*
152   * If the output packet (including seqno and excluding the EMPTY_BLOCK)
153   * got bigger, send the original - returning 0 to HdlcOutput() will
154   * continue to send ``mp''.
155   */
156  if (olen >= ilen) {
157    pfree(mo_head);
158    mbfree(mi_head);
159    LogPrintf(LogDEBUG, "DeflateOutput: %d => %d: Uncompressible (0x%04x)\n",
160              ilen, olen, proto);
161    CcpInfo.uncompout += ilen;
162    CcpInfo.compout += ilen;	/* We measure this stuff too */
163    return 0;
164  }
165
166  pfree(mi_head);
167
168  /*
169   * Lose the last four bytes of our output.
170   * XXX: We should probably assert that these are the same as the
171   *      contents of EMPTY_BLOCK.
172   */
173  for (mo = mo_head, len = mo->cnt; len < olen; mo = mo->next, len += mo->cnt)
174    ;
175  mo->cnt -= len - olen;
176  if (mo->next != NULL) {
177    pfree(mo->next);
178    mo->next = NULL;
179  }
180
181  CcpInfo.uncompout += ilen;
182  CcpInfo.compout += olen;
183
184  LogPrintf(LogDEBUG, "DeflateOutput: %d => %d bytes, proto 0x%04x\n",
185            ilen, olen, proto);
186
187  HdlcOutput(PRI_NORMAL, PROTO_COMPD, mo_head);
188  return 1;
189}
190
191static void
192DeflateResetInput(void)
193{
194  InputState.seqno = 0;
195  InputState.uncomp_rec = 0;
196  inflateReset(&InputState.cx);
197  LogPrintf(LogCCP, "Deflate: Input channel reset\n");
198}
199
200static struct mbuf *
201DeflateInput(u_short *proto, struct mbuf *mi)
202{
203  struct mbuf *mo, *mo_head, *mi_head;
204  u_char *wp;
205  int ilen, olen;
206  int seq, flush, res, first;
207  u_char hdr[2];
208
209  LogDumpBp(LogDEBUG, "DeflateInput: Decompress packet:", mi);
210  mi_head = mi = mbread(mi, hdr, 2);
211  ilen = 2;
212
213  /* Check the sequence number. */
214  seq = (hdr[0] << 8) + hdr[1];
215  LogPrintf(LogDEBUG, "DeflateInput: Seq %d\n", seq);
216  if (seq != InputState.seqno) {
217    if (seq <= InputState.uncomp_rec)
218      /*
219       * So the peer's started at zero again - fine !  If we're wrong,
220       * inflate() will fail.  This is better than getting into a loop
221       * trying to get a ResetReq to a busy sender.
222       */
223      InputState.seqno = seq;
224    else {
225      LogPrintf(LogERROR, "DeflateInput: Seq error: Got %d, expected %d\n",
226                seq, InputState.seqno);
227      pfree(mi_head);
228      CcpSendResetReq(&CcpFsm);
229      return NULL;
230    }
231  }
232  InputState.seqno++;
233  InputState.uncomp_rec = 0;
234
235  /* Allocate an output mbuf */
236  mo_head = mo = mballoc(DEFLATE_CHUNK_LEN, MB_IPIN);
237
238  /* Our proto starts with 0 if it's compressed */
239  wp = MBUF_CTOP(mo);
240  wp[0] = '\0';
241
242  /*
243   * We set avail_out to 1 initially so we can look at the first
244   * byte of the output and decide whether we have a compressed
245   * proto field.
246   */
247  InputState.cx.next_in = MBUF_CTOP(mi);
248  InputState.cx.avail_in = mi->cnt;
249  InputState.cx.next_out = wp + 1;
250  InputState.cx.avail_out = 1;
251  ilen += mi->cnt;
252
253  flush = mi->next ? Z_NO_FLUSH : Z_SYNC_FLUSH;
254  first = 1;
255  olen = 0;
256
257  while (1) {
258    if ((res = inflate(&InputState.cx, flush)) != Z_OK) {
259      if (res == Z_STREAM_END)
260        break;			/* Done */
261      LogPrintf(LogERROR, "DeflateInput: inflate returned %d (%s)\n",
262                res, InputState.cx.msg ? InputState.cx.msg : "");
263      pfree(mo_head);
264      pfree(mi);
265      CcpSendResetReq(&CcpFsm);
266      return NULL;
267    }
268
269    if (flush == Z_SYNC_FLUSH && InputState.cx.avail_out != 0)
270      break;
271
272    if (InputState.cx.avail_in == 0 && mi && (mi = mbfree(mi)) != NULL) {
273      /* underflow */
274      InputState.cx.next_in = MBUF_CTOP(mi);
275      ilen += (InputState.cx.avail_in = mi->cnt);
276      if (mi->next == NULL)
277        flush = Z_SYNC_FLUSH;
278    }
279
280    if (InputState.cx.avail_out == 0) {
281      /* overflow */
282      if (first) {
283        if (!(wp[1] & 1)) {
284          /* 2 byte proto, shuffle it back in output */
285          wp[0] = wp[1];
286          InputState.cx.next_out--;
287          InputState.cx.avail_out = DEFLATE_CHUNK_LEN-1;
288        } else
289          InputState.cx.avail_out = DEFLATE_CHUNK_LEN-2;
290        first = 0;
291      } else {
292        olen += (mo->cnt = DEFLATE_CHUNK_LEN);
293        mo->next = mballoc(DEFLATE_CHUNK_LEN, MB_IPIN);
294        mo = mo->next;
295        InputState.cx.next_out = MBUF_CTOP(mo);
296        InputState.cx.avail_out = DEFLATE_CHUNK_LEN;
297      }
298    }
299  }
300
301  if (mi != NULL)
302    pfree(mi);
303
304  if (first) {
305    LogPrintf(LogERROR, "DeflateInput: Length error\n");
306    pfree(mo_head);
307    CcpSendResetReq(&CcpFsm);
308    return NULL;
309  }
310
311  olen += (mo->cnt = DEFLATE_CHUNK_LEN - InputState.cx.avail_out);
312
313  *proto = ((u_short)wp[0] << 8) | wp[1];
314  mo_head->offset += 2;
315  mo_head->cnt -= 2;
316  olen -= 2;
317
318  CcpInfo.compin += ilen;
319  CcpInfo.uncompin += olen;
320
321  LogPrintf(LogDEBUG, "DeflateInput: %d => %d bytes, proto 0x%04x\n",
322            ilen, olen, *proto);
323
324  /*
325   * Simulate an EMPTY_BLOCK so that our dictionary stays in sync.
326   * The peer will have silently removed this!
327   */
328  InputState.cx.next_out = garbage;
329  InputState.cx.avail_out = sizeof garbage;
330  InputState.cx.next_in = EMPTY_BLOCK;
331  InputState.cx.avail_in = sizeof EMPTY_BLOCK;
332  inflate(&InputState.cx, Z_SYNC_FLUSH);
333
334  return mo_head;
335}
336
337static void
338DeflateDictSetup(u_short proto, struct mbuf *mi)
339{
340  int res, flush, expect_error;
341  u_char *rp;
342  struct mbuf *mi_head;
343  short len;
344
345  LogPrintf(LogDEBUG, "DeflateDictSetup: Got seq %d\n", InputState.seqno);
346
347  /*
348   * Stuff an ``uncompressed data'' block header followed by the
349   * protocol in front of the input
350   */
351  mi_head = mballoc(7, MB_HDLCOUT);
352  mi_head->next = mi;
353  len = plength(mi);
354  mi = mi_head;
355  rp = MBUF_CTOP(mi);
356  if (proto < 0x100) {			/* Compress the protocol */
357    rp[5] = proto & 0377;
358    mi->cnt = 6;
359    len++;
360  } else {				/* Don't compress the protocol */
361    rp[5] = proto >> 8;
362    rp[6] = proto & 0377;
363    mi->cnt = 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  InputState.cx.next_in = rp;
373  InputState.cx.avail_in = mi->cnt;
374  InputState.cx.next_out = garbage;
375  InputState.cx.avail_out = sizeof garbage;
376  flush = Z_NO_FLUSH;
377  expect_error = 0;
378
379  while (1) {
380    if ((res = inflate(&InputState.cx, flush)) != Z_OK) {
381      if (res == Z_STREAM_END)
382        break;			/* Done */
383      if (expect_error && res == Z_BUF_ERROR)
384        break;
385      LogPrintf(LogERROR, "DeflateDictSetup: inflate returned %d (%s)\n",
386                res, InputState.cx.msg ? InputState.cx.msg : "");
387      LogPrintf(LogERROR, "DeflateDictSetup: avail_in %d, avail_out %d\n",
388                InputState.cx.avail_in, InputState.cx.avail_out);
389      CcpSendResetReq(&CcpFsm);
390      mbfree(mi_head);		/* lose our allocated ``head'' buf */
391      return;
392    }
393
394    if (flush == Z_SYNC_FLUSH && InputState.cx.avail_out != 0)
395      break;
396
397    if (InputState.cx.avail_in == 0 && mi && (mi = mi->next) != NULL) {
398      /* underflow */
399      InputState.cx.next_in = MBUF_CTOP(mi);
400      InputState.cx.avail_in = mi->cnt;
401      if (mi->next == NULL)
402        flush = Z_SYNC_FLUSH;
403    }
404
405    if (InputState.cx.avail_out == 0) {
406      if (InputState.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      InputState.cx.next_out = garbage;
421      InputState.cx.avail_out = sizeof garbage;
422    }
423  }
424
425  CcpInfo.compin += len;
426  CcpInfo.uncompin += len;
427
428  InputState.seqno++;
429  InputState.uncomp_rec++;
430  mbfree(mi_head);		/* lose our allocated ``head'' buf */
431}
432
433static const char *
434DeflateDispOpts(struct lcp_opt *o)
435{
436  static char disp[7];
437
438  sprintf(disp, "win %d", (o->data[0]>>4) + 8);
439  return disp;
440}
441
442static void
443DeflateGetInputOpts(struct lcp_opt *o)
444{
445  o->id = TY_DEFLATE;
446  o->len = 4;
447  o->data[0] = ((iWindowSize-8)<<4)+8;
448  o->data[1] = '\0';
449}
450
451static void
452DeflateGetOutputOpts(struct lcp_opt *o)
453{
454  o->id = TY_DEFLATE;
455  o->len = 4;
456  o->data[0] = ((oWindowSize-8)<<4)+8;
457  o->data[1] = '\0';
458}
459
460static void
461PppdDeflateGetInputOpts(struct lcp_opt *o)
462{
463  o->id = TY_PPPD_DEFLATE;
464  o->len = 4;
465  o->data[0] = ((iWindowSize-8)<<4)+8;
466  o->data[1] = '\0';
467}
468
469static void
470PppdDeflateGetOutputOpts(struct lcp_opt *o)
471{
472  o->id = TY_PPPD_DEFLATE;
473  o->len = 4;
474  o->data[0] = ((oWindowSize-8)<<4)+8;
475  o->data[1] = '\0';
476}
477
478static int
479DeflateSetOpts(struct lcp_opt *o, int *sz)
480{
481  if (o->len != 4 || (o->data[0]&15) != 8 || o->data[1] != '\0') {
482    return MODE_REJ;
483  }
484  *sz = (o->data[0] >> 4) + 8;
485  if (*sz > 15) {
486    *sz = 15;
487    return MODE_NAK;
488  }
489
490  return MODE_ACK;
491}
492
493static int
494DeflateSetInputOpts(struct lcp_opt *o)
495{
496  int res;
497  res = DeflateSetOpts(o, &iWindowSize);
498  if (res != MODE_ACK)
499    DeflateGetInputOpts(o);
500  return res;
501}
502
503static int
504DeflateSetOutputOpts(struct lcp_opt *o)
505{
506  int res;
507  res = DeflateSetOpts(o, &oWindowSize);
508  if (res != MODE_ACK)
509    DeflateGetOutputOpts(o);
510  return res;
511}
512
513static int
514PppdDeflateSetInputOpts(struct lcp_opt *o)
515{
516  int res;
517  res = DeflateSetOpts(o, &iWindowSize);
518  if (res != MODE_ACK)
519    PppdDeflateGetInputOpts(o);
520  return res;
521}
522
523static int
524PppdDeflateSetOutputOpts(struct lcp_opt *o)
525{
526  int res;
527  res = DeflateSetOpts(o, &oWindowSize);
528  if (res != MODE_ACK)
529    PppdDeflateGetOutputOpts(o);
530  return res;
531}
532
533static int
534DeflateInitInput(void)
535{
536  InputState.cx.zalloc = NULL;
537  InputState.cx.opaque = NULL;
538  InputState.cx.zfree = NULL;
539  InputState.cx.next_out = NULL;
540  if (inflateInit2(&InputState.cx, -iWindowSize) != Z_OK)
541    return 0;
542  DeflateResetInput();
543  return 1;
544}
545
546static int
547DeflateInitOutput(void)
548{
549  OutputState.cx.zalloc = NULL;
550  OutputState.cx.opaque = NULL;
551  OutputState.cx.zfree = NULL;
552  OutputState.cx.next_in = NULL;
553  if (deflateInit2(&OutputState.cx, Z_DEFAULT_COMPRESSION, 8,
554                   -oWindowSize, 8, Z_DEFAULT_STRATEGY) != Z_OK)
555    return 0;
556  DeflateResetOutput();
557  return 1;
558}
559
560static void
561DeflateTermInput(void)
562{
563  iWindowSize = 15;
564  inflateEnd(&InputState.cx);
565}
566
567static void
568DeflateTermOutput(void)
569{
570  oWindowSize = 15;
571  deflateEnd(&OutputState.cx);
572}
573
574const struct ccp_algorithm PppdDeflateAlgorithm = {
575  TY_PPPD_DEFLATE,	/* pppd (wrongly) expects this ``type'' field */
576  ConfPppdDeflate,
577  DeflateDispOpts,
578  {
579    PppdDeflateGetInputOpts,
580    PppdDeflateSetInputOpts,
581    DeflateInitInput,
582    DeflateTermInput,
583    DeflateResetInput,
584    DeflateInput,
585    DeflateDictSetup
586  },
587  {
588    PppdDeflateGetOutputOpts,
589    PppdDeflateSetOutputOpts,
590    DeflateInitOutput,
591    DeflateTermOutput,
592    DeflateResetOutput,
593    DeflateOutput
594  },
595};
596
597const struct ccp_algorithm DeflateAlgorithm = {
598  TY_DEFLATE,		/* rfc 1979 */
599  ConfDeflate,
600  DeflateDispOpts,
601  {
602    DeflateGetInputOpts,
603    DeflateSetInputOpts,
604    DeflateInitInput,
605    DeflateTermInput,
606    DeflateResetInput,
607    DeflateInput,
608    DeflateDictSetup
609  },
610  {
611    DeflateGetOutputOpts,
612    DeflateSetOutputOpts,
613    DeflateInitOutput,
614    DeflateTermOutput,
615    DeflateResetOutput,
616    DeflateOutput
617  },
618};
619