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 "lqr.h"
  42 #include "hdlc.h"
  43 #include "lcp.h"
  44 #include "ccp.h"
  45 #include "deflate.h"
  46
  47 /* Our state */
  48 struct deflate_state {
  49     u_short seqno;
  50     int uncomp_rec;
  51     int winsize;
  52     z_stream cx;
  53 };
  54
  55 static char garbage[10];
  56 static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff };
  57
  58 #define DEFLATE_CHUNK_LEN (1536 - sizeof(struct mbuf))
  59
  60 static int
  61 DeflateResetOutput(void *v)
  62 {
  63   struct deflate_state *state = (struct deflate_state *)v;
  64
  65   state->seqno = 0;
  66   state->uncomp_rec = 0;
  67   deflateReset(&state->cx);
  68   log_Printf(LogCCP, "Deflate: Output channel reset\n");
  69
  70   return 1;             /* Ask FSM to ACK */
  71 }
  72
  73 static struct mbuf *
  74 DeflateOutput(void *v, struct ccp *ccp, struct link *l, int pri, u_short *proto,
  75               struct mbuf *mp)
  76 {
  77   struct deflate_state *state = (struct deflate_state *)v;
  78   u_char *wp, *rp;
  79   int olen, ilen, len, res, flush;
  80   struct mbuf *mo_head, *mo, *mi_head, *mi;
  81
  82   ilen = m_length(mp);
  83   log_Printf(LogDEBUG, "DeflateOutput: Proto %02x (%d bytes)\n", *proto, ilen);
  84   log_DumpBp(LogDEBUG, "DeflateOutput: Compress packet:", mp);
  85
  86   /* Stuff the protocol in front of the input */
  87   mi_head = mi = m_get(2, MB_CCPOUT);
  88   mi->m_next = mp;
  89   rp = MBUF_CTOP(mi);
  90   if (*proto < 0x100) {                 /* Compress the protocol */
  91     rp[0] = *proto & 0377;
  92     mi->m_len = 1;
  93   } else {                              /* Don't compress the protocol */
  94     rp[0] = *proto >> 8;
  95     rp[1] = *proto & 0377;
  96     mi->m_len = 2;
  97   }
  98
  99   /* Allocate the initial output mbuf */
 100   mo_head = mo = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT);
 101   mo->m_len = 2;
 102   wp = MBUF_CTOP(mo);
 103   *wp++ = state->seqno >> 8;
 104   *wp++ = state->seqno & 0377;
 105   log_Printf(LogDEBUG, "DeflateOutput: Seq %d\n", state->seqno);
 106   state->seqno++;
 107
 108   /* Set up the deflation context */
 109   state->cx.next_out = wp;
 110   state->cx.avail_out = DEFLATE_CHUNK_LEN - 2;
 111   state->cx.next_in = MBUF_CTOP(mi);
 112   state->cx.avail_in = mi->m_len;
 113   flush = Z_NO_FLUSH;
 114
 115   olen = 0;
 116   while (1) {
 117     if ((res = deflate(&state->cx, flush)) != Z_OK) {
 118       if (res == Z_STREAM_END)
 119         break;                  /* Done */
 120       log_Printf(LogWARN, "DeflateOutput: deflate returned %d (%s)\n",
 121                 res, state->cx.msg ? state->cx.msg : "");
 122       m_freem(mo_head);
 123       m_free(mi_head);
 124       state->seqno--;
 125       return mp;                /* Our dictionary's probably dead now :-( */
 126     }
 127
 128     if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
 129       break;
 130
 131     if (state->cx.avail_in == 0 && mi->m_next != NULL) {
 132       mi = mi->m_next;
 133       state->cx.next_in = MBUF_CTOP(mi);
 134       state->cx.avail_in = mi->m_len;
 135       if (mi->m_next == NULL)
 136         flush = Z_SYNC_FLUSH;
 137     }
 138
 139     if (state->cx.avail_out == 0) {
 140       mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT);
 141       olen += (mo->m_len = DEFLATE_CHUNK_LEN);
 142       mo = mo->m_next;
 143       mo->m_len = 0;
 144       state->cx.next_out = MBUF_CTOP(mo);
 145       state->cx.avail_out = DEFLATE_CHUNK_LEN;
 146     }
 147   }
 148
 149   olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out);
 150   olen -= 4;            /* exclude the trailing EMPTY_BLOCK */
 151
 152   /*
 153    * If the output packet (including seqno and excluding the EMPTY_BLOCK)
 154    * got bigger, send the original.
 155    */
 156   if (olen >= ilen) {
 157     m_freem(mo_head);
 158     m_free(mi_head);
 159     log_Printf(LogDEBUG, "DeflateOutput: %d => %d: Uncompressible (0x%04x)\n",
 160               ilen, olen, *proto);
 161     ccp->uncompout += ilen;
 162     ccp->compout += ilen;       /* We measure this stuff too */
 163     return mp;
 164   }
 165
 166   m_freem(mi_head);
 167
 168   /*
 169    * Lose the last four bytes of our output.
 170    * XXX: We should probably assert that these are the same as the
 171    *      contents of EMPTY_BLOCK.
 172    */
 173   mo = mo_head;
 174   for (len = mo->m_len; len < olen; mo = mo->m_next, len += mo->m_len)
 175     ;
 176   mo->m_len -= len - olen;
 177   if (mo->m_next != NULL) {
 178     m_freem(mo->m_next);
 179     mo->m_next = NULL;
 180   }
 181
 182   ccp->uncompout += ilen;
 183   ccp->compout += olen;
 184
 185   log_Printf(LogDEBUG, "DeflateOutput: %d => %d bytes, proto 0x%04x\n",
 186             ilen, olen, *proto);
 187
 188   *proto = ccp_Proto(ccp);
 189   return mo_head;
 190 }
 191
 192 static void
 193 DeflateResetInput(void *v)
 194 {
 195   struct deflate_state *state = (struct deflate_state *)v;
 196
 197   state->seqno = 0;
 198   state->uncomp_rec = 0;
 199   inflateReset(&state->cx);
 200   log_Printf(LogCCP, "Deflate: Input channel reset\n");
 201 }
 202
 203 static struct mbuf *
 204 DeflateInput(void *v, struct ccp *ccp, u_short *proto, struct mbuf *mi)
 205 {
 206   struct deflate_state *state = (struct deflate_state *)v;
 207   struct mbuf *mo, *mo_head, *mi_head;
 208   u_char *wp;
 209   int ilen, olen;
 210   int seq, flush, res, first;
 211   u_char hdr[2];
 212
 213   log_DumpBp(LogDEBUG, "DeflateInput: Decompress packet:", mi);
 214   mi_head = mi = mbuf_Read(mi, hdr, 2);
 215   ilen = 2;
 216
 217   /* Check the sequence number. */
 218   seq = (hdr[0] << 8) + hdr[1];
 219   log_Printf(LogDEBUG, "DeflateInput: Seq %d\n", seq);
 220   if (seq != state->seqno) {
 221     if (seq <= state->uncomp_rec)
 222       /*
 223        * So the peer's started at zero again - fine !  If we're wrong,
 224        * inflate() will fail.  This is better than getting into a loop
 225        * trying to get a ResetReq to a busy sender.
 226        */
 227       state->seqno = seq;
 228     else {
 229       log_Printf(LogCCP, "DeflateInput: Seq error: Got %d, expected %d\n",
 230                 seq, state->seqno);
 231       m_freem(mi_head);
 232       ccp_SendResetReq(&ccp->fsm);
 233       return NULL;
 234     }
 235   }
 236   state->seqno++;
 237   state->uncomp_rec = 0;
 238
 239   /* Allocate an output mbuf */
 240   mo_head = mo = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN);
 241
 242   /* Our proto starts with 0 if it's compressed */
 243   wp = MBUF_CTOP(mo);
 244   wp[0] = '\0';
 245
 246   /*
 247    * We set avail_out to 1 initially so we can look at the first
 248    * byte of the output and decide whether we have a compressed
 249    * proto field.
 250    */
 251   state->cx.next_in = MBUF_CTOP(mi);
 252   state->cx.avail_in = mi->m_len;
 253   state->cx.next_out = wp + 1;
 254   state->cx.avail_out = 1;
 255   ilen += mi->m_len;
 256
 257   flush = mi->m_next ? Z_NO_FLUSH : Z_SYNC_FLUSH;
 258   first = 1;
 259   olen = 0;
 260
 261   while (1) {
 262     if ((res = inflate(&state->cx, flush)) != Z_OK) {
 263       if (res == Z_STREAM_END)
 264         break;                  /* Done */
 265       log_Printf(LogCCP, "DeflateInput: inflate returned %d (%s)\n",
 266                 res, state->cx.msg ? state->cx.msg : "");
 267       m_freem(mo_head);
 268       m_freem(mi);
 269       ccp_SendResetReq(&ccp->fsm);
 270       return NULL;
 271     }
 272
 273     if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
 274       break;
 275
 276     if (state->cx.avail_in == 0 && mi && (mi = m_free(mi)) != NULL) {
 277       /* underflow */
 278       state->cx.next_in = MBUF_CTOP(mi);
 279       ilen += (state->cx.avail_in = mi->m_len);
 280       if (mi->m_next == NULL)
 281         flush = Z_SYNC_FLUSH;
 282     }
 283
 284     if (state->cx.avail_out == 0) {
 285       /* overflow */
 286       if (first) {
 287         if (!(wp[1] & 1)) {
 288           /* 2 byte proto, shuffle it back in output */
 289           wp[0] = wp[1];
 290           state->cx.next_out--;
 291           state->cx.avail_out = DEFLATE_CHUNK_LEN-1;
 292         } else
 293           state->cx.avail_out = DEFLATE_CHUNK_LEN-2;
 294         first = 0;
 295       } else {
 296         olen += (mo->m_len = DEFLATE_CHUNK_LEN);
 297         mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN);
 298         mo = mo->m_next;
 299         state->cx.next_out = MBUF_CTOP(mo);
 300         state->cx.avail_out = DEFLATE_CHUNK_LEN;
 301       }
 302     }
 303   }
 304
 305   if (mi != NULL)
 306     m_freem(mi);
 307
 308   if (first) {
 309     log_Printf(LogCCP, "DeflateInput: Length error\n");
 310     m_freem(mo_head);
 311     ccp_SendResetReq(&ccp->fsm);
 312     return NULL;
 313   }
 314
 315   olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out);
 316
 317   *proto = ((u_short)wp[0] << 8) | wp[1];
 318   mo_head->m_offset += 2;
 319   mo_head->m_len -= 2;
 320   olen -= 2;
 321
 322   ccp->compin += ilen;
 323   ccp->uncompin += olen;
 324
 325   log_Printf(LogDEBUG, "DeflateInput: %d => %d bytes, proto 0x%04x\n",
 326             ilen, olen, *proto);
 327
 328   /*
 329    * Simulate an EMPTY_BLOCK so that our dictionary stays in sync.
 330    * The peer will have silently removed this!
 331    */
 332   state->cx.next_out = garbage;
 333   state->cx.avail_out = sizeof garbage;
 334   state->cx.next_in = EMPTY_BLOCK;
 335   state->cx.avail_in = sizeof EMPTY_BLOCK;
 336   inflate(&state->cx, Z_SYNC_FLUSH);
 337
 338   return mo_head;
 339 }
 340
 341 static void
 342 DeflateDictSetup(void *v, struct ccp *ccp, u_short proto, struct mbuf *mi)
 343 {
 344   struct deflate_state *state = (struct deflate_state *)v;
 345   int res, flush, expect_error;
 346   u_char *rp;
 347   struct mbuf *mi_head;
 348   short len;
 349
 350   log_Printf(LogDEBUG, "DeflateDictSetup: Got seq %d\n", state->seqno);
 351
 352   /*
 353    * Stuff an ``uncompressed data'' block header followed by the
 354    * protocol in front of the input
 355    */
 356   mi_head = m_get(7, MB_CCPOUT);
 357   mi_head->m_next = mi;
 358   len = m_length(mi);
 359   mi = mi_head;
 360   rp = MBUF_CTOP(mi);
 361   if (proto < 0x100) {                  /* Compress the protocol */
 362     rp[5] = proto & 0377;
 363     mi->m_len = 6;
 364     len++;
 365   } else {                              /* Don't compress the protocol */
 366     rp[5] = proto >> 8;
 367     rp[6] = proto & 0377;
 368     mi->m_len = 7;
 369     len += 2;
 370   }
 371   rp[0] = 0x80;                         /* BITS: 100xxxxx */
 372   rp[1] = len & 0377;                   /* The length */
 373   rp[2] = len >> 8;
 374   rp[3] = (~len) & 0377;                /* One's compliment of the length */
 375   rp[4] = (~len) >> 8;
 376
 377   state->cx.next_in = rp;
 378   state->cx.avail_in = mi->m_len;
 379   state->cx.next_out = garbage;
 380   state->cx.avail_out = sizeof garbage;
 381   flush = Z_NO_FLUSH;
 382   expect_error = 0;
 383
 384   while (1) {
 385     if ((res = inflate(&state->cx, flush)) != Z_OK) {
 386       if (res == Z_STREAM_END)
 387         break;                  /* Done */
 388       if (expect_error && res == Z_BUF_ERROR)
 389         break;
 390       log_Printf(LogCCP, "DeflateDictSetup: inflate returned %d (%s)\n",
 391                 res, state->cx.msg ? state->cx.msg : "");
 392       log_Printf(LogCCP, "DeflateDictSetup: avail_in %d, avail_out %d\n",
 393                 state->cx.avail_in, state->cx.avail_out);
 394       ccp_SendResetReq(&ccp->fsm);
 395       m_free(mi_head);          /* lose our allocated ``head'' buf */
 396       return;
 397     }
 398
 399     if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
 400       break;
 401
 402     if (state->cx.avail_in == 0 && mi && (mi = mi->m_next) != NULL) {
 403       /* underflow */
 404       state->cx.next_in = MBUF_CTOP(mi);
 405       state->cx.avail_in = mi->m_len;
 406       if (mi->m_next == NULL)
 407         flush = Z_SYNC_FLUSH;
 408     }
 409
 410     if (state->cx.avail_out == 0) {
 411       if (state->cx.avail_in == 0)
 412         /*
 413          * This seems to be a bug in libz !  If inflate() finished
 414          * with 0 avail_in and 0 avail_out *and* this is the end of
 415          * our input *and* inflate() *has* actually written all the
 416          * output it's going to, it *doesn't* return Z_STREAM_END !
 417          * When we subsequently call it with no more input, it gives
 418          * us Z_BUF_ERROR :-(  It seems pretty safe to ignore this
 419          * error (the dictionary seems to stay in sync).  In the worst
 420          * case, we'll drop the next compressed packet and do a
 421          * CcpReset() then.
 422          */
 423         expect_error = 1;
 424       /* overflow */
 425       state->cx.next_out = garbage;
 426       state->cx.avail_out = sizeof garbage;
 427     }
 428   }
 429
 430   ccp->compin += len;
 431   ccp->uncompin += len;
 432
 433   state->seqno++;
 434   state->uncomp_rec++;
 435   m_free(mi_head);              /* lose our allocated ``head'' buf */
 436 }
 437
 438 static const char *
 439 DeflateDispOpts(struct lcp_opt *o)
 440 {
 441   static char disp[7];          /* Must be used immediately */
 442
 443   sprintf(disp, "win %d", (o->data[0]>>4) + 8);
 444   return disp;
 445 }
 446
 447 static void
 448 DeflateInitOptsOutput(struct lcp_opt *o, const struct ccp_config *cfg)
 449 {
 450   o->len = 4;
 451   o->data[0] = ((cfg->deflate.out.winsize - 8) << 4) + 8;
 452   o->data[1] = '\0';
 453 }
 454
 455 static int
 456 DeflateSetOptsOutput(struct lcp_opt *o, const struct ccp_config *cfg)
 457 {
 458   if (o->len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0')
 459     return MODE_REJ;
 460
 461   if ((o->data[0] >> 4) + 8 > 15) {
 462     o->data[0] = ((15 - 8) << 4) + 8;
 463     return MODE_NAK;
 464   }
 465
 466   return MODE_ACK;
 467 }
 468
 469 static int
 470 DeflateSetOptsInput(struct lcp_opt *o, const struct ccp_config *cfg)
 471 {
 472   int want;
 473
 474   if (o->len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0')
 475     return MODE_REJ;
 476
 477   want = (o->data[0] >> 4) + 8;
 478   if (cfg->deflate.in.winsize == 0) {
 479     if (want < 8 || want > 15) {
 480       o->data[0] = ((15 - 8) << 4) + 8;
 481     }
 482   } else if (want != cfg->deflate.in.winsize) {
 483     o->data[0] = ((cfg->deflate.in.winsize - 8) << 4) + 8;
 484     return MODE_NAK;
 485   }
 486
 487   return MODE_ACK;
 488 }
 489
 490 static void *
 491 DeflateInitInput(struct lcp_opt *o)
 492 {
 493   struct deflate_state *state;
 494
 495   state = (struct deflate_state *)malloc(sizeof(struct deflate_state));
 496   if (state != NULL) {
 497     state->winsize = (o->data[0] >> 4) + 8;
 498     state->cx.zalloc = NULL;
 499     state->cx.opaque = NULL;
 500     state->cx.zfree = NULL;
 501     state->cx.next_out = NULL;
 502     if (inflateInit2(&state->cx, -state->winsize) == Z_OK)
 503       DeflateResetInput(state);
 504     else {
 505       free(state);
 506       state = NULL;
 507     }
 508   }
 509
 510   return state;
 511 }
 512
 513 static void *
 514 DeflateInitOutput(struct lcp_opt *o)
 515 {
 516   struct deflate_state *state;
 517
 518   state = (struct deflate_state *)malloc(sizeof(struct deflate_state));
 519   if (state != NULL) {
 520     state->winsize = (o->data[0] >> 4) + 8;
 521     state->cx.zalloc = NULL;
 522     state->cx.opaque = NULL;
 523     state->cx.zfree = NULL;
 524     state->cx.next_in = NULL;
 525     if (deflateInit2(&state->cx, Z_DEFAULT_COMPRESSION, 8,
 526                      -state->winsize, 8, Z_DEFAULT_STRATEGY) == Z_OK)
 527       DeflateResetOutput(state);
 528     else {
 529       free(state);
 530       state = NULL;
 531     }
 532   }
 533
 534   return state;
 535 }
 536
 537 static void
 538 DeflateTermInput(void *v)
 539 {
 540   struct deflate_state *state = (struct deflate_state *)v;
 541
 542   inflateEnd(&state->cx);
 543   free(state);
 544 }
 545
 546 static void
 547 DeflateTermOutput(void *v)
 548 {
 549   struct deflate_state *state = (struct deflate_state *)v;
 550
 551   deflateEnd(&state->cx);
 552   free(state);
 553 }
 554
 555 const struct ccp_algorithm PppdDeflateAlgorithm = {
 556   TY_PPPD_DEFLATE,      /* Older versions of pppd expected this ``type'' */
 557   CCP_NEG_DEFLATE24,
 558   DeflateDispOpts,
 559   ccp_DefaultUsable,
 560   ccp_DefaultRequired,
 561   {
 562     DeflateSetOptsInput,
 563     DeflateInitInput,
 564     DeflateTermInput,
 565     DeflateResetInput,
 566     DeflateInput,
 567     DeflateDictSetup
 568   },
 569   {
 570     0,
 571     DeflateInitOptsOutput,
 572     DeflateSetOptsOutput,
 573     DeflateInitOutput,
 574     DeflateTermOutput,
 575     DeflateResetOutput,
 576     DeflateOutput
 577   },
 578 };
 579
 580 const struct ccp_algorithm DeflateAlgorithm = {
 581   TY_DEFLATE,           /* rfc 1979 */
 582   CCP_NEG_DEFLATE,
 583   DeflateDispOpts,
 584   ccp_DefaultUsable,
 585   ccp_DefaultRequired,
 586   {
 587     DeflateSetOptsInput,
 588     DeflateInitInput,
 589     DeflateTermInput,
 590     DeflateResetInput,
 591     DeflateInput,
 592     DeflateDictSetup
 593   },
 594   {
 595     0,
 596     DeflateInitOptsOutput,
 597     DeflateSetOptsOutput,
 598     DeflateInitOutput,
 599     DeflateTermOutput,
 600     DeflateResetOutput,
 601     DeflateOutput
 602   },
 603 };