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