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 * $DragonFly: src/usr.sbin/ppp/deflate.c,v 1.2 2003/06/17 04:30:00 dillon Exp $ 28 */ 29 30 #include <sys/types.h> 31 32 #include <stdio.h> 33 #include <stdlib.h> 34 #include <zlib.h> 35 36 #include "mbuf.h" 37 #include "log.h" 38 #include "timer.h" 39 #include "fsm.h" 40 #include "ccp.h" 41 #include "deflate.h" 42 43 /* Our state */ 44 struct deflate_state { 45 u_short seqno; 46 int uncomp_rec; 47 int winsize; 48 z_stream cx; 49 }; 50 51 static char garbage[10]; 52 static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff }; 53 54 #define DEFLATE_CHUNK_LEN (1536 - sizeof(struct mbuf)) 55 56 static int 57 DeflateResetOutput(void *v) 58 { 59 struct deflate_state *state = (struct deflate_state *)v; 60 61 state->seqno = 0; 62 state->uncomp_rec = 0; 63 deflateReset(&state->cx); 64 log_Printf(LogCCP, "Deflate: Output channel reset\n"); 65 66 return 1; /* Ask FSM to ACK */ 67 } 68 69 static struct mbuf * 70 DeflateOutput(void *v, struct ccp *ccp, struct link *l __unused, 71 int pri __unused, u_short *proto, struct mbuf *mp) 72 { 73 struct deflate_state *state = (struct deflate_state *)v; 74 u_char *wp, *rp; 75 int olen, ilen, len, res, flush; 76 struct mbuf *mo_head, *mo, *mi_head, *mi; 77 78 ilen = m_length(mp); 79 log_Printf(LogDEBUG, "DeflateOutput: Proto %02x (%d bytes)\n", *proto, ilen); 80 log_DumpBp(LogDEBUG, "DeflateOutput: Compress packet:", mp); 81 82 /* Stuff the protocol in front of the input */ 83 mi_head = mi = m_get(2, MB_CCPOUT); 84 mi->m_next = mp; 85 rp = MBUF_CTOP(mi); 86 if (*proto < 0x100) { /* Compress the protocol */ 87 rp[0] = *proto & 0377; 88 mi->m_len = 1; 89 } else { /* Don't compress the protocol */ 90 rp[0] = *proto >> 8; 91 rp[1] = *proto & 0377; 92 mi->m_len = 2; 93 } 94 95 /* Allocate the initial output mbuf */ 96 mo_head = mo = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT); 97 mo->m_len = 2; 98 wp = MBUF_CTOP(mo); 99 *wp++ = state->seqno >> 8; 100 *wp++ = state->seqno & 0377; 101 log_Printf(LogDEBUG, "DeflateOutput: Seq %d\n", state->seqno); 102 state->seqno++; 103 104 /* Set up the deflation context */ 105 state->cx.next_out = wp; 106 state->cx.avail_out = DEFLATE_CHUNK_LEN - 2; 107 state->cx.next_in = MBUF_CTOP(mi); 108 state->cx.avail_in = mi->m_len; 109 flush = Z_NO_FLUSH; 110 111 olen = 0; 112 while (1) { 113 if ((res = deflate(&state->cx, flush)) != Z_OK) { 114 if (res == Z_STREAM_END) 115 break; /* Done */ 116 log_Printf(LogWARN, "DeflateOutput: deflate returned %d (%s)\n", 117 res, state->cx.msg ? state->cx.msg : ""); 118 m_freem(mo_head); 119 m_free(mi_head); 120 state->seqno--; 121 return mp; /* Our dictionary's probably dead now :-( */ 122 } 123 124 if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0) 125 break; 126 127 if (state->cx.avail_in == 0 && mi->m_next != NULL) { 128 mi = mi->m_next; 129 state->cx.next_in = MBUF_CTOP(mi); 130 state->cx.avail_in = mi->m_len; 131 if (mi->m_next == NULL) 132 flush = Z_SYNC_FLUSH; 133 } 134 135 if (state->cx.avail_out == 0) { 136 mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT); 137 olen += (mo->m_len = DEFLATE_CHUNK_LEN); 138 mo = mo->m_next; 139 mo->m_len = 0; 140 state->cx.next_out = MBUF_CTOP(mo); 141 state->cx.avail_out = DEFLATE_CHUNK_LEN; 142 } 143 } 144 145 olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out); 146 olen -= 4; /* exclude the trailing EMPTY_BLOCK */ 147 148 /* 149 * If the output packet (including seqno and excluding the EMPTY_BLOCK) 150 * got bigger, send the original. 151 */ 152 if (olen >= ilen) { 153 m_freem(mo_head); 154 m_free(mi_head); 155 log_Printf(LogDEBUG, "DeflateOutput: %d => %d: Uncompressible (0x%04x)\n", 156 ilen, olen, *proto); 157 ccp->uncompout += ilen; 158 ccp->compout += ilen; /* We measure this stuff too */ 159 return mp; 160 } 161 162 m_freem(mi_head); 163 164 /* 165 * Lose the last four bytes of our output. 166 * XXX: We should probably assert that these are the same as the 167 * contents of EMPTY_BLOCK. 168 */ 169 mo = mo_head; 170 for (len = mo->m_len; len < olen; mo = mo->m_next, len += mo->m_len) 171 ; 172 mo->m_len -= len - olen; 173 if (mo->m_next != NULL) { 174 m_freem(mo->m_next); 175 mo->m_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 *proto = ccp_Proto(ccp); 185 return mo_head; 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(LogCCP, "DeflateInput: Seq error: Got %d, expected %d\n", 226 seq, state->seqno); 227 m_freem(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 = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN); 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->m_len; 249 state->cx.next_out = wp + 1; 250 state->cx.avail_out = 1; 251 ilen += mi->m_len; 252 253 flush = mi->m_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(LogCCP, "DeflateInput: inflate returned %d (%s)\n", 262 res, state->cx.msg ? state->cx.msg : ""); 263 m_freem(mo_head); 264 m_freem(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 = m_free(mi)) != NULL) { 273 /* underflow */ 274 state->cx.next_in = MBUF_CTOP(mi); 275 ilen += (state->cx.avail_in = mi->m_len); 276 if (mi->m_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->m_len = DEFLATE_CHUNK_LEN); 293 mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN); 294 mo = mo->m_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 m_freem(mi); 303 304 if (first) { 305 log_Printf(LogCCP, "DeflateInput: Length error\n"); 306 m_freem(mo_head); 307 ccp_SendResetReq(&ccp->fsm); 308 return NULL; 309 } 310 311 olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out); 312 313 *proto = ((u_short)wp[0] << 8) | wp[1]; 314 mo_head->m_offset += 2; 315 mo_head->m_len -= 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 = m_get(7, MB_CCPOUT); 353 mi_head->m_next = mi; 354 len = m_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->m_len = 6; 360 len++; 361 } else { /* Don't compress the protocol */ 362 rp[5] = proto >> 8; 363 rp[6] = proto & 0377; 364 mi->m_len = 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->m_len; 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(LogCCP, "DeflateDictSetup: inflate returned %d (%s)\n", 387 res, state->cx.msg ? state->cx.msg : ""); 388 log_Printf(LogCCP, "DeflateDictSetup: avail_in %d, avail_out %d\n", 389 state->cx.avail_in, state->cx.avail_out); 390 ccp_SendResetReq(&ccp->fsm); 391 m_free(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->m_next) != NULL) { 399 /* underflow */ 400 state->cx.next_in = MBUF_CTOP(mi); 401 state->cx.avail_in = mi->m_len; 402 if (mi->m_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 m_free(mi_head); /* lose our allocated ``head'' buf */ 432 } 433 434 static const char * 435 DeflateDispOpts(struct fsm_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 bundle *bundle __unused, struct fsm_opt *o, 445 const struct ccp_config *cfg) 446 { 447 o->hdr.len = 4; 448 o->data[0] = ((cfg->deflate.out.winsize - 8) << 4) + 8; 449 o->data[1] = '\0'; 450 } 451 452 static int 453 DeflateSetOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o, 454 const struct ccp_config *cfg __unused) 455 { 456 if (o->hdr.len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0') 457 return MODE_REJ; 458 459 if ((o->data[0] >> 4) + 8 > 15) { 460 o->data[0] = ((15 - 8) << 4) + 8; 461 return MODE_NAK; 462 } 463 464 return MODE_ACK; 465 } 466 467 static int 468 DeflateSetOptsInput(struct bundle *bundle __unused, struct fsm_opt *o, 469 const struct ccp_config *cfg) 470 { 471 int want; 472 473 if (o->hdr.len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0') 474 return MODE_REJ; 475 476 want = (o->data[0] >> 4) + 8; 477 if (cfg->deflate.in.winsize == 0) { 478 if (want < 8 || want > 15) { 479 o->data[0] = ((15 - 8) << 4) + 8; 480 } 481 } else if (want != cfg->deflate.in.winsize) { 482 o->data[0] = ((cfg->deflate.in.winsize - 8) << 4) + 8; 483 return MODE_NAK; 484 } 485 486 return MODE_ACK; 487 } 488 489 static void * 490 DeflateInitInput(struct bundle *bundle __unused, struct fsm_opt *o) 491 { 492 struct deflate_state *state; 493 494 state = (struct deflate_state *)malloc(sizeof(struct deflate_state)); 495 if (state != NULL) { 496 state->winsize = (o->data[0] >> 4) + 8; 497 state->cx.zalloc = NULL; 498 state->cx.opaque = NULL; 499 state->cx.zfree = NULL; 500 state->cx.next_out = NULL; 501 if (inflateInit2(&state->cx, -state->winsize) == Z_OK) 502 DeflateResetInput(state); 503 else { 504 free(state); 505 state = NULL; 506 } 507 } 508 509 return state; 510 } 511 512 static void * 513 DeflateInitOutput(struct bundle *bundle __unused, struct fsm_opt *o) 514 { 515 struct deflate_state *state; 516 517 state = (struct deflate_state *)malloc(sizeof(struct deflate_state)); 518 if (state != NULL) { 519 state->winsize = (o->data[0] >> 4) + 8; 520 state->cx.zalloc = NULL; 521 state->cx.opaque = NULL; 522 state->cx.zfree = NULL; 523 state->cx.next_in = NULL; 524 if (deflateInit2(&state->cx, Z_DEFAULT_COMPRESSION, 8, 525 -state->winsize, 8, Z_DEFAULT_STRATEGY) == Z_OK) 526 DeflateResetOutput(state); 527 else { 528 free(state); 529 state = NULL; 530 } 531 } 532 533 return state; 534 } 535 536 static void 537 DeflateTermInput(void *v) 538 { 539 struct deflate_state *state = (struct deflate_state *)v; 540 541 inflateEnd(&state->cx); 542 free(state); 543 } 544 545 static void 546 DeflateTermOutput(void *v) 547 { 548 struct deflate_state *state = (struct deflate_state *)v; 549 550 deflateEnd(&state->cx); 551 free(state); 552 } 553 554 const struct ccp_algorithm PppdDeflateAlgorithm = { 555 TY_PPPD_DEFLATE, /* Older versions of pppd expected this ``type'' */ 556 CCP_NEG_DEFLATE24, 557 DeflateDispOpts, 558 ccp_DefaultUsable, 559 ccp_DefaultRequired, 560 { 561 DeflateSetOptsInput, 562 DeflateInitInput, 563 DeflateTermInput, 564 DeflateResetInput, 565 DeflateInput, 566 DeflateDictSetup 567 }, 568 { 569 0, 570 DeflateInitOptsOutput, 571 DeflateSetOptsOutput, 572 DeflateInitOutput, 573 DeflateTermOutput, 574 DeflateResetOutput, 575 DeflateOutput 576 }, 577 }; 578 579 const struct ccp_algorithm DeflateAlgorithm = { 580 TY_DEFLATE, /* rfc 1979 */ 581 CCP_NEG_DEFLATE, 582 DeflateDispOpts, 583 ccp_DefaultUsable, 584 ccp_DefaultRequired, 585 { 586 DeflateSetOptsInput, 587 DeflateInitInput, 588 DeflateTermInput, 589 DeflateResetInput, 590 DeflateInput, 591 DeflateDictSetup 592 }, 593 { 594 0, 595 DeflateInitOptsOutput, 596 DeflateSetOptsOutput, 597 DeflateInitOutput, 598 DeflateTermOutput, 599 DeflateResetOutput, 600 DeflateOutput 601 }, 602 }; 603