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 */
43 struct deflate_state {
44 u_short seqno;
45 int uncomp_rec;
46 int winsize;
47 z_stream cx;
48 };
49
50 static char garbage[10];
51 static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff };
52
53 #define DEFLATE_CHUNK_LEN (1536 - sizeof(struct mbuf))
54
55 static int
DeflateResetOutput(void * v)56 DeflateResetOutput(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
68 static struct mbuf *
DeflateOutput(void * v,struct ccp * ccp,struct link * l __unused,int pri __unused,u_short * proto,struct mbuf * mp)69 DeflateOutput(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
187 static void
DeflateResetInput(void * v)188 DeflateResetInput(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
198 static struct mbuf *
DeflateInput(void * v,struct ccp * ccp,u_short * proto,struct mbuf * mi)199 DeflateInput(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
336 static void
DeflateDictSetup(void * v,struct ccp * ccp,u_short proto,struct mbuf * mi)337 DeflateDictSetup(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
433 static const char *
DeflateDispOpts(struct fsm_opt * o)434 DeflateDispOpts(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
442 static void
DeflateInitOptsOutput(struct bundle * bundle __unused,struct fsm_opt * o,const struct ccp_config * cfg)443 DeflateInitOptsOutput(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
451 static int
DeflateSetOptsOutput(struct bundle * bundle __unused,struct fsm_opt * o,const struct ccp_config * cfg __unused)452 DeflateSetOptsOutput(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
466 static int
DeflateSetOptsInput(struct bundle * bundle __unused,struct fsm_opt * o,const struct ccp_config * cfg)467 DeflateSetOptsInput(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
488 static void *
DeflateInitInput(struct bundle * bundle __unused,struct fsm_opt * o)489 DeflateInitInput(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
511 static void *
DeflateInitOutput(struct bundle * bundle __unused,struct fsm_opt * o)512 DeflateInitOutput(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
535 static void
DeflateTermInput(void * v)536 DeflateTermInput(void *v)
537 {
538 struct deflate_state *state = (struct deflate_state *)v;
539
540 inflateEnd(&state->cx);
541 free(state);
542 }
543
544 static void
DeflateTermOutput(void * v)545 DeflateTermOutput(void *v)
546 {
547 struct deflate_state *state = (struct deflate_state *)v;
548
549 deflateEnd(&state->cx);
550 free(state);
551 }
552
553 const 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
578 const 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