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.10 1998/06/16 19:40:36 brian Exp $ 27 */ 28 29 #include <sys/types.h> 30 31 #include <stdio.h> 32 #include <stdlib.h> 33 #include <zlib.h> 34 35 #include "defs.h" 36 #include "mbuf.h" 37 #include "log.h" 38 #include "timer.h" 39 #include "lqr.h" 40 #include "hdlc.h" 41 #include "fsm.h" 42 #include "lcp.h" 43 #include "ccp.h" 44 #include "deflate.h" 45 46 /* Our state */ 47 struct deflate_state { 48 u_short seqno; 49 int uncomp_rec; 50 int winsize; 51 z_stream cx; 52 }; 53 54 static char garbage[10]; 55 static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff }; 56 57 #define DEFLATE_CHUNK_LEN 1024 /* Allocate mbufs this size */ 58 59 static void 60 DeflateResetOutput(void *v) 61 { 62 struct deflate_state *state = (struct deflate_state *)v; 63 64 state->seqno = 0; 65 state->uncomp_rec = 0; 66 deflateReset(&state->cx); 67 log_Printf(LogCCP, "Deflate: Output channel reset\n"); 68 } 69 70 static int 71 DeflateOutput(void *v, struct ccp *ccp, struct link *l, int pri, u_short proto, 72 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 = mbuf_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 = mbuf_Alloc(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 = mbuf_Alloc(DEFLATE_CHUNK_LEN, MB_HDLCOUT); 98 mo->cnt = 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->cnt; 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 mbuf_Free(mo_head); 120 mbuf_FreeSeg(mi_head); 121 state->seqno--; 122 return 1; /* packet dropped */ 123 } 124 125 if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0) 126 break; 127 128 if (state->cx.avail_in == 0 && mi->next != NULL) { 129 mi = mi->next; 130 state->cx.next_in = MBUF_CTOP(mi); 131 state->cx.avail_in = mi->cnt; 132 if (mi->next == NULL) 133 flush = Z_SYNC_FLUSH; 134 } 135 136 if (state->cx.avail_out == 0) { 137 mo->next = mbuf_Alloc(DEFLATE_CHUNK_LEN, MB_HDLCOUT); 138 olen += (mo->cnt = DEFLATE_CHUNK_LEN); 139 mo = mo->next; 140 mo->cnt = 0; 141 state->cx.next_out = MBUF_CTOP(mo); 142 state->cx.avail_out = DEFLATE_CHUNK_LEN; 143 } 144 } 145 146 olen += (mo->cnt = 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 mbuf_Free(mo_head); 155 mbuf_FreeSeg(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 0; 161 } 162 163 mbuf_Free(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 for (mo = mo_head, len = mo->cnt; len < olen; mo = mo->next, len += mo->cnt) 171 ; 172 mo->cnt -= len - olen; 173 if (mo->next != NULL) { 174 mbuf_Free(mo->next); 175 mo->next = NULL; 176 } 177 178 ccp->uncompout += ilen; 179 ccp->compout += olen; 180 181 log_Printf(LogDEBUG, "DeflateOutput: %d => %d bytes, proto 0x%04x\n", 182 ilen, olen, proto); 183 184 hdlc_Output(l, PRI_NORMAL, ccp_Proto(ccp), mo_head); 185 return 1; 186 } 187 188 static void 189 DeflateResetInput(void *v) 190 { 191 struct deflate_state *state = (struct deflate_state *)v; 192 193 state->seqno = 0; 194 state->uncomp_rec = 0; 195 inflateReset(&state->cx); 196 log_Printf(LogCCP, "Deflate: Input channel reset\n"); 197 } 198 199 static struct mbuf * 200 DeflateInput(void *v, struct ccp *ccp, u_short *proto, struct mbuf *mi) 201 { 202 struct deflate_state *state = (struct deflate_state *)v; 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 log_DumpBp(LogDEBUG, "DeflateInput: Decompress packet:", mi); 210 mi_head = mi = mbuf_Read(mi, hdr, 2); 211 ilen = 2; 212 213 /* Check the sequence number. */ 214 seq = (hdr[0] << 8) + hdr[1]; 215 log_Printf(LogDEBUG, "DeflateInput: Seq %d\n", seq); 216 if (seq != state->seqno) { 217 if (seq <= state->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 state->seqno = seq; 224 else { 225 log_Printf(LogWARN, "DeflateInput: Seq error: Got %d, expected %d\n", 226 seq, state->seqno); 227 mbuf_Free(mi_head); 228 ccp_SendResetReq(&ccp->fsm); 229 return NULL; 230 } 231 } 232 state->seqno++; 233 state->uncomp_rec = 0; 234 235 /* Allocate an output mbuf */ 236 mo_head = mo = mbuf_Alloc(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 state->cx.next_in = MBUF_CTOP(mi); 248 state->cx.avail_in = mi->cnt; 249 state->cx.next_out = wp + 1; 250 state->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(&state->cx, flush)) != Z_OK) { 259 if (res == Z_STREAM_END) 260 break; /* Done */ 261 log_Printf(LogWARN, "DeflateInput: inflate returned %d (%s)\n", 262 res, state->cx.msg ? state->cx.msg : ""); 263 mbuf_Free(mo_head); 264 mbuf_Free(mi); 265 ccp_SendResetReq(&ccp->fsm); 266 return NULL; 267 } 268 269 if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0) 270 break; 271 272 if (state->cx.avail_in == 0 && mi && (mi = mbuf_FreeSeg(mi)) != NULL) { 273 /* underflow */ 274 state->cx.next_in = MBUF_CTOP(mi); 275 ilen += (state->cx.avail_in = mi->cnt); 276 if (mi->next == NULL) 277 flush = Z_SYNC_FLUSH; 278 } 279 280 if (state->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 state->cx.next_out--; 287 state->cx.avail_out = DEFLATE_CHUNK_LEN-1; 288 } else 289 state->cx.avail_out = DEFLATE_CHUNK_LEN-2; 290 first = 0; 291 } else { 292 olen += (mo->cnt = DEFLATE_CHUNK_LEN); 293 mo->next = mbuf_Alloc(DEFLATE_CHUNK_LEN, MB_IPIN); 294 mo = mo->next; 295 state->cx.next_out = MBUF_CTOP(mo); 296 state->cx.avail_out = DEFLATE_CHUNK_LEN; 297 } 298 } 299 } 300 301 if (mi != NULL) 302 mbuf_Free(mi); 303 304 if (first) { 305 log_Printf(LogWARN, "DeflateInput: Length error\n"); 306 mbuf_Free(mo_head); 307 ccp_SendResetReq(&ccp->fsm); 308 return NULL; 309 } 310 311 olen += (mo->cnt = DEFLATE_CHUNK_LEN - state->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 ccp->compin += ilen; 319 ccp->uncompin += olen; 320 321 log_Printf(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 state->cx.next_out = garbage; 329 state->cx.avail_out = sizeof garbage; 330 state->cx.next_in = EMPTY_BLOCK; 331 state->cx.avail_in = sizeof EMPTY_BLOCK; 332 inflate(&state->cx, Z_SYNC_FLUSH); 333 334 return mo_head; 335 } 336 337 static void 338 DeflateDictSetup(void *v, struct ccp *ccp, u_short proto, struct mbuf *mi) 339 { 340 struct deflate_state *state = (struct deflate_state *)v; 341 int res, flush, expect_error; 342 u_char *rp; 343 struct mbuf *mi_head; 344 short len; 345 346 log_Printf(LogDEBUG, "DeflateDictSetup: Got seq %d\n", state->seqno); 347 348 /* 349 * Stuff an ``uncompressed data'' block header followed by the 350 * protocol in front of the input 351 */ 352 mi_head = mbuf_Alloc(7, MB_HDLCOUT); 353 mi_head->next = mi; 354 len = mbuf_Length(mi); 355 mi = mi_head; 356 rp = MBUF_CTOP(mi); 357 if (proto < 0x100) { /* Compress the protocol */ 358 rp[5] = proto & 0377; 359 mi->cnt = 6; 360 len++; 361 } else { /* Don't compress the protocol */ 362 rp[5] = proto >> 8; 363 rp[6] = proto & 0377; 364 mi->cnt = 7; 365 len += 2; 366 } 367 rp[0] = 0x80; /* BITS: 100xxxxx */ 368 rp[1] = len & 0377; /* The length */ 369 rp[2] = len >> 8; 370 rp[3] = (~len) & 0377; /* One's compliment of the length */ 371 rp[4] = (~len) >> 8; 372 373 state->cx.next_in = rp; 374 state->cx.avail_in = mi->cnt; 375 state->cx.next_out = garbage; 376 state->cx.avail_out = sizeof garbage; 377 flush = Z_NO_FLUSH; 378 expect_error = 0; 379 380 while (1) { 381 if ((res = inflate(&state->cx, flush)) != Z_OK) { 382 if (res == Z_STREAM_END) 383 break; /* Done */ 384 if (expect_error && res == Z_BUF_ERROR) 385 break; 386 log_Printf(LogERROR, "DeflateDictSetup: inflate returned %d (%s)\n", 387 res, state->cx.msg ? state->cx.msg : ""); 388 log_Printf(LogERROR, "DeflateDictSetup: avail_in %d, avail_out %d\n", 389 state->cx.avail_in, state->cx.avail_out); 390 ccp_SendResetReq(&ccp->fsm); 391 mbuf_FreeSeg(mi_head); /* lose our allocated ``head'' buf */ 392 return; 393 } 394 395 if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0) 396 break; 397 398 if (state->cx.avail_in == 0 && mi && (mi = mi->next) != NULL) { 399 /* underflow */ 400 state->cx.next_in = MBUF_CTOP(mi); 401 state->cx.avail_in = mi->cnt; 402 if (mi->next == NULL) 403 flush = Z_SYNC_FLUSH; 404 } 405 406 if (state->cx.avail_out == 0) { 407 if (state->cx.avail_in == 0) 408 /* 409 * This seems to be a bug in libz ! If inflate() finished 410 * with 0 avail_in and 0 avail_out *and* this is the end of 411 * our input *and* inflate() *has* actually written all the 412 * output it's going to, it *doesn't* return Z_STREAM_END ! 413 * When we subsequently call it with no more input, it gives 414 * us Z_BUF_ERROR :-( It seems pretty safe to ignore this 415 * error (the dictionary seems to stay in sync). In the worst 416 * case, we'll drop the next compressed packet and do a 417 * CcpReset() then. 418 */ 419 expect_error = 1; 420 /* overflow */ 421 state->cx.next_out = garbage; 422 state->cx.avail_out = sizeof garbage; 423 } 424 } 425 426 ccp->compin += len; 427 ccp->uncompin += len; 428 429 state->seqno++; 430 state->uncomp_rec++; 431 mbuf_FreeSeg(mi_head); /* lose our allocated ``head'' buf */ 432 } 433 434 static const char * 435 DeflateDispOpts(struct lcp_opt *o) 436 { 437 static char disp[7]; /* Must be used immediately */ 438 439 sprintf(disp, "win %d", (o->data[0]>>4) + 8); 440 return disp; 441 } 442 443 static void 444 DeflateInitOptsOutput(struct lcp_opt *o, const struct ccp_config *cfg) 445 { 446 o->len = 4; 447 o->data[0] = ((cfg->deflate.out.winsize - 8) << 4) + 8; 448 o->data[1] = '\0'; 449 } 450 451 static int 452 DeflateSetOptsOutput(struct lcp_opt *o) 453 { 454 if (o->len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0') 455 return MODE_REJ; 456 457 if ((o->data[0] >> 4) + 8 > 15) { 458 o->data[0] = ((15 - 8) << 4) + 8; 459 return MODE_NAK; 460 } 461 462 return MODE_ACK; 463 } 464 465 static int 466 DeflateSetOptsInput(struct lcp_opt *o, const struct ccp_config *cfg) 467 { 468 int want; 469 470 if (o->len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0') 471 return MODE_REJ; 472 473 want = (o->data[0] >> 4) + 8; 474 if (cfg->deflate.in.winsize == 0) { 475 if (want < 8 || want > 15) { 476 o->data[0] = ((15 - 8) << 4) + 8; 477 } 478 } else if (want != cfg->deflate.in.winsize) { 479 o->data[0] = ((cfg->deflate.in.winsize - 8) << 4) + 8; 480 return MODE_NAK; 481 } 482 483 return MODE_ACK; 484 } 485 486 static void * 487 DeflateInitInput(struct lcp_opt *o) 488 { 489 struct deflate_state *state; 490 491 state = (struct deflate_state *)malloc(sizeof(struct deflate_state)); 492 if (state != NULL) { 493 state->winsize = (o->data[0] >> 4) + 8; 494 state->cx.zalloc = NULL; 495 state->cx.opaque = NULL; 496 state->cx.zfree = NULL; 497 state->cx.next_out = NULL; 498 if (inflateInit2(&state->cx, -state->winsize) == Z_OK) 499 DeflateResetInput(state); 500 else { 501 free(state); 502 state = NULL; 503 } 504 } 505 506 return state; 507 } 508 509 static void * 510 DeflateInitOutput(struct lcp_opt *o) 511 { 512 struct deflate_state *state; 513 514 state = (struct deflate_state *)malloc(sizeof(struct deflate_state)); 515 if (state != NULL) { 516 state->winsize = (o->data[0] >> 4) + 8; 517 state->cx.zalloc = NULL; 518 state->cx.opaque = NULL; 519 state->cx.zfree = NULL; 520 state->cx.next_in = NULL; 521 if (deflateInit2(&state->cx, Z_DEFAULT_COMPRESSION, 8, 522 -state->winsize, 8, Z_DEFAULT_STRATEGY) == Z_OK) 523 DeflateResetOutput(state); 524 else { 525 free(state); 526 state = NULL; 527 } 528 } 529 530 return state; 531 } 532 533 static void 534 DeflateTermInput(void *v) 535 { 536 struct deflate_state *state = (struct deflate_state *)v; 537 538 inflateEnd(&state->cx); 539 free(state); 540 } 541 542 static void 543 DeflateTermOutput(void *v) 544 { 545 struct deflate_state *state = (struct deflate_state *)v; 546 547 deflateEnd(&state->cx); 548 free(state); 549 } 550 551 const struct ccp_algorithm PppdDeflateAlgorithm = { 552 TY_PPPD_DEFLATE, /* pppd (wrongly) expects this ``type'' field */ 553 CCP_NEG_DEFLATE24, 554 DeflateDispOpts, 555 { 556 DeflateSetOptsInput, 557 DeflateInitInput, 558 DeflateTermInput, 559 DeflateResetInput, 560 DeflateInput, 561 DeflateDictSetup 562 }, 563 { 564 DeflateInitOptsOutput, 565 DeflateSetOptsOutput, 566 DeflateInitOutput, 567 DeflateTermOutput, 568 DeflateResetOutput, 569 DeflateOutput 570 }, 571 }; 572 573 const struct ccp_algorithm DeflateAlgorithm = { 574 TY_DEFLATE, /* rfc 1979 */ 575 CCP_NEG_DEFLATE, 576 DeflateDispOpts, 577 { 578 DeflateSetOptsInput, 579 DeflateInitInput, 580 DeflateTermInput, 581 DeflateResetInput, 582 DeflateInput, 583 DeflateDictSetup 584 }, 585 { 586 DeflateInitOptsOutput, 587 DeflateSetOptsOutput, 588 DeflateInitOutput, 589 DeflateTermOutput, 590 DeflateResetOutput, 591 DeflateOutput 592 }, 593 }; 594