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.18.2.4 2002/09/01 02:12:26 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 "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 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 * 69 DeflateOutput(void *v, struct ccp *ccp, struct link *l, int pri, u_short *proto, 70 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 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 * 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 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 * 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 443 DeflateInitOptsOutput(struct bundle *bundle, 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 452 DeflateSetOptsOutput(struct bundle *bundle, struct fsm_opt *o, 453 const struct ccp_config *cfg) 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 467 DeflateSetOptsInput(struct bundle *bundle, 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 * 489 DeflateInitInput(struct bundle *bundle, 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 * 512 DeflateInitOutput(struct bundle *bundle, 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 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 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