usr.sbin/ppp/deflate.c

   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$
  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 __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
 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 __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
 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
 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 *
 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 *
 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
 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 };