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