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 <termios.h>
  34 #include <zlib.h>
  35
  36 #include "defs.h"
  37 #include "mbuf.h"
  38 #include "log.h"
  39 #include "timer.h"
  40 #include "fsm.h"
  41 #include "lcp.h"
  42 #include "ccp.h"
  43 #include "deflate.h"
  44
  45 /* Our state */
  46 struct deflate_state {
  47     u_short seqno;
  48     int uncomp_rec;
  49     int winsize;
  50     z_stream cx;
  51 };
  52
  53 static char garbage[10];
  54 static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff };
  55
  56 #define DEFLATE_CHUNK_LEN (1536 - sizeof(struct mbuf))
  57
  58 static void
  59 DeflateResetOutput(void *v)
  60 {
  61   struct deflate_state *state = (struct deflate_state *)v;
  62
  63   state->seqno = 0;
  64   state->uncomp_rec = 0;
  65   deflateReset(&state->cx);
  66   log_Printf(LogCCP, "Deflate: Output channel reset\n");
  67 }
  68
  69 static struct mbuf *
  70 DeflateOutput(void *v, struct ccp *ccp, struct link *l, int pri, u_short *proto,
  71               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 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 };