usr.sbin/ppp/deflate.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 1997 Brian Somers <brian@Awfulhak.org>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  * $FreeBSD$
  29  */
  30
  31 #include <sys/types.h>
  32
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <zlib.h>
  36
  37 #include "mbuf.h"
  38 #include "log.h"
  39 #include "timer.h"
  40 #include "fsm.h"
  41 #include "ccp.h"
  42 #include "deflate.h"
  43
  44 /* Our state */
  45 struct deflate_state {
  46     u_short seqno;
  47     int uncomp_rec;
  48     int winsize;
  49     z_stream cx;
  50 };
  51
  52 static char garbage[10];
  53 static u_char EMPTY_BLOCK[4] = { 0x00, 0x00, 0xff, 0xff };
  54
  55 #define DEFLATE_CHUNK_LEN (1536 - sizeof(struct mbuf))
  56
  57 static int
  58 DeflateResetOutput(void *v)
  59 {
  60   struct deflate_state *state = (struct deflate_state *)v;
  61
  62   state->seqno = 0;
  63   state->uncomp_rec = 0;
  64   deflateReset(&state->cx);
  65   log_Printf(LogCCP, "Deflate: Output channel reset\n");
  66
  67   return 1;             /* Ask FSM to ACK */
  68 }
  69
  70 static struct mbuf *
  71 DeflateOutput(void *v, struct ccp *ccp, struct link *l __unused,
  72               int pri __unused, u_short *proto, struct mbuf *mp)
  73 {
  74   struct deflate_state *state = (struct deflate_state *)v;
  75   u_char *wp, *rp;
  76   int olen, ilen, len, res, flush;
  77   struct mbuf *mo_head, *mo, *mi_head, *mi;
  78
  79   ilen = m_length(mp);
  80   log_Printf(LogDEBUG, "DeflateOutput: Proto %02x (%d bytes)\n", *proto, ilen);
  81   log_DumpBp(LogDEBUG, "DeflateOutput: Compress packet:", mp);
  82
  83   /* Stuff the protocol in front of the input */
  84   mi_head = mi = m_get(2, MB_CCPOUT);
  85   mi->m_next = mp;
  86   rp = MBUF_CTOP(mi);
  87   if (*proto < 0x100) {                 /* Compress the protocol */
  88     rp[0] = *proto & 0377;
  89     mi->m_len = 1;
  90   } else {                              /* Don't compress the protocol */
  91     rp[0] = *proto >> 8;
  92     rp[1] = *proto & 0377;
  93     mi->m_len = 2;
  94   }
  95
  96   /* Allocate the initial output mbuf */
  97   mo_head = mo = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT);
  98   mo->m_len = 2;
  99   wp = MBUF_CTOP(mo);
 100   *wp++ = state->seqno >> 8;
 101   *wp++ = state->seqno & 0377;
 102   log_Printf(LogDEBUG, "DeflateOutput: Seq %d\n", state->seqno);
 103   state->seqno++;
 104
 105   /* Set up the deflation context */
 106   state->cx.next_out = wp;
 107   state->cx.avail_out = DEFLATE_CHUNK_LEN - 2;
 108   state->cx.next_in = MBUF_CTOP(mi);
 109   state->cx.avail_in = mi->m_len;
 110   flush = Z_NO_FLUSH;
 111
 112   olen = 0;
 113   while (1) {
 114     if ((res = deflate(&state->cx, flush)) != Z_OK) {
 115       if (res == Z_STREAM_END)
 116         break;                  /* Done */
 117       log_Printf(LogWARN, "DeflateOutput: deflate returned %d (%s)\n",
 118                 res, state->cx.msg ? state->cx.msg : "");
 119       m_freem(mo_head);
 120       m_free(mi_head);
 121       state->seqno--;
 122       return mp;                /* Our dictionary's probably dead now :-( */
 123     }
 124
 125     if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
 126       break;
 127
 128     if (state->cx.avail_in == 0 && mi->m_next != NULL) {
 129       mi = mi->m_next;
 130       state->cx.next_in = MBUF_CTOP(mi);
 131       state->cx.avail_in = mi->m_len;
 132       if (mi->m_next == NULL)
 133         flush = Z_SYNC_FLUSH;
 134     }
 135
 136     if (state->cx.avail_out == 0) {
 137       mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPOUT);
 138       olen += (mo->m_len = DEFLATE_CHUNK_LEN);
 139       mo = mo->m_next;
 140       mo->m_len = 0;
 141       state->cx.next_out = MBUF_CTOP(mo);
 142       state->cx.avail_out = DEFLATE_CHUNK_LEN;
 143     }
 144   }
 145
 146   olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out);
 147   olen -= 4;            /* exclude the trailing EMPTY_BLOCK */
 148
 149   /*
 150    * If the output packet (including seqno and excluding the EMPTY_BLOCK)
 151    * got bigger, send the original.
 152    */
 153   if (olen >= ilen) {
 154     m_freem(mo_head);
 155     m_free(mi_head);
 156     log_Printf(LogDEBUG, "DeflateOutput: %d => %d: Uncompressible (0x%04x)\n",
 157               ilen, olen, *proto);
 158     ccp->uncompout += ilen;
 159     ccp->compout += ilen;       /* We measure this stuff too */
 160     return mp;
 161   }
 162
 163   m_freem(mi_head);
 164
 165   /*
 166    * Lose the last four bytes of our output.
 167    * XXX: We should probably assert that these are the same as the
 168    *      contents of EMPTY_BLOCK.
 169    */
 170   mo = mo_head;
 171   for (len = mo->m_len; len < olen; mo = mo->m_next, len += mo->m_len)
 172     ;
 173   mo->m_len -= len - olen;
 174   if (mo->m_next != NULL) {
 175     m_freem(mo->m_next);
 176     mo->m_next = NULL;
 177   }
 178
 179   ccp->uncompout += ilen;
 180   ccp->compout += olen;
 181
 182   log_Printf(LogDEBUG, "DeflateOutput: %d => %d bytes, proto 0x%04x\n",
 183             ilen, olen, *proto);
 184
 185   *proto = ccp_Proto(ccp);
 186   return mo_head;
 187 }
 188
 189 static void
 190 DeflateResetInput(void *v)
 191 {
 192   struct deflate_state *state = (struct deflate_state *)v;
 193
 194   state->seqno = 0;
 195   state->uncomp_rec = 0;
 196   inflateReset(&state->cx);
 197   log_Printf(LogCCP, "Deflate: Input channel reset\n");
 198 }
 199
 200 static struct mbuf *
 201 DeflateInput(void *v, struct ccp *ccp, u_short *proto, struct mbuf *mi)
 202 {
 203   struct deflate_state *state = (struct deflate_state *)v;
 204   struct mbuf *mo, *mo_head, *mi_head;
 205   u_char *wp;
 206   int ilen, olen;
 207   int seq, flush, res, first;
 208   u_char hdr[2];
 209
 210   log_DumpBp(LogDEBUG, "DeflateInput: Decompress packet:", mi);
 211   mi_head = mi = mbuf_Read(mi, hdr, 2);
 212   ilen = 2;
 213
 214   /* Check the sequence number. */
 215   seq = (hdr[0] << 8) + hdr[1];
 216   log_Printf(LogDEBUG, "DeflateInput: Seq %d\n", seq);
 217   if (seq != state->seqno) {
 218     if (seq <= state->uncomp_rec)
 219       /*
 220        * So the peer's started at zero again - fine !  If we're wrong,
 221        * inflate() will fail.  This is better than getting into a loop
 222        * trying to get a ResetReq to a busy sender.
 223        */
 224       state->seqno = seq;
 225     else {
 226       log_Printf(LogCCP, "DeflateInput: Seq error: Got %d, expected %d\n",
 227                 seq, state->seqno);
 228       m_freem(mi_head);
 229       ccp_SendResetReq(&ccp->fsm);
 230       return NULL;
 231     }
 232   }
 233   state->seqno++;
 234   state->uncomp_rec = 0;
 235
 236   /* Allocate an output mbuf */
 237   mo_head = mo = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN);
 238
 239   /* Our proto starts with 0 if it's compressed */
 240   wp = MBUF_CTOP(mo);
 241   wp[0] = '\0';
 242
 243   /*
 244    * We set avail_out to 1 initially so we can look at the first
 245    * byte of the output and decide whether we have a compressed
 246    * proto field.
 247    */
 248   state->cx.next_in = MBUF_CTOP(mi);
 249   state->cx.avail_in = mi->m_len;
 250   state->cx.next_out = wp + 1;
 251   state->cx.avail_out = 1;
 252   ilen += mi->m_len;
 253
 254   flush = mi->m_next ? Z_NO_FLUSH : Z_SYNC_FLUSH;
 255   first = 1;
 256   olen = 0;
 257
 258   while (1) {
 259     if ((res = inflate(&state->cx, flush)) != Z_OK) {
 260       if (res == Z_STREAM_END)
 261         break;                  /* Done */
 262       log_Printf(LogCCP, "DeflateInput: inflate returned %d (%s)\n",
 263                 res, state->cx.msg ? state->cx.msg : "");
 264       m_freem(mo_head);
 265       m_freem(mi);
 266       ccp_SendResetReq(&ccp->fsm);
 267       return NULL;
 268     }
 269
 270     if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
 271       break;
 272
 273     if (state->cx.avail_in == 0 && mi && (mi = m_free(mi)) != NULL) {
 274       /* underflow */
 275       state->cx.next_in = MBUF_CTOP(mi);
 276       ilen += (state->cx.avail_in = mi->m_len);
 277       if (mi->m_next == NULL)
 278         flush = Z_SYNC_FLUSH;
 279     }
 280
 281     if (state->cx.avail_out == 0) {
 282       /* overflow */
 283       if (first) {
 284         if (!(wp[1] & 1)) {
 285           /* 2 byte proto, shuffle it back in output */
 286           wp[0] = wp[1];
 287           state->cx.next_out--;
 288           state->cx.avail_out = DEFLATE_CHUNK_LEN-1;
 289         } else
 290           state->cx.avail_out = DEFLATE_CHUNK_LEN-2;
 291         first = 0;
 292       } else {
 293         olen += (mo->m_len = DEFLATE_CHUNK_LEN);
 294         mo->m_next = m_get(DEFLATE_CHUNK_LEN, MB_CCPIN);
 295         mo = mo->m_next;
 296         state->cx.next_out = MBUF_CTOP(mo);
 297         state->cx.avail_out = DEFLATE_CHUNK_LEN;
 298       }
 299     }
 300   }
 301
 302   if (mi != NULL)
 303     m_freem(mi);
 304
 305   if (first) {
 306     log_Printf(LogCCP, "DeflateInput: Length error\n");
 307     m_freem(mo_head);
 308     ccp_SendResetReq(&ccp->fsm);
 309     return NULL;
 310   }
 311
 312   olen += (mo->m_len = DEFLATE_CHUNK_LEN - state->cx.avail_out);
 313
 314   *proto = ((u_short)wp[0] << 8) | wp[1];
 315   mo_head->m_offset += 2;
 316   mo_head->m_len -= 2;
 317   olen -= 2;
 318
 319   ccp->compin += ilen;
 320   ccp->uncompin += olen;
 321
 322   log_Printf(LogDEBUG, "DeflateInput: %d => %d bytes, proto 0x%04x\n",
 323             ilen, olen, *proto);
 324
 325   /*
 326    * Simulate an EMPTY_BLOCK so that our dictionary stays in sync.
 327    * The peer will have silently removed this!
 328    */
 329   state->cx.next_out = garbage;
 330   state->cx.avail_out = sizeof garbage;
 331   state->cx.next_in = EMPTY_BLOCK;
 332   state->cx.avail_in = sizeof EMPTY_BLOCK;
 333   inflate(&state->cx, Z_SYNC_FLUSH);
 334
 335   return mo_head;
 336 }
 337
 338 static void
 339 DeflateDictSetup(void *v, struct ccp *ccp, u_short proto, struct mbuf *mi)
 340 {
 341   struct deflate_state *state = (struct deflate_state *)v;
 342   int res, flush, expect_error;
 343   u_char *rp;
 344   struct mbuf *mi_head;
 345   short len;
 346
 347   log_Printf(LogDEBUG, "DeflateDictSetup: Got seq %d\n", state->seqno);
 348
 349   /*
 350    * Stuff an ``uncompressed data'' block header followed by the
 351    * protocol in front of the input
 352    */
 353   mi_head = m_get(7, MB_CCPOUT);
 354   mi_head->m_next = mi;
 355   len = m_length(mi);
 356   mi = mi_head;
 357   rp = MBUF_CTOP(mi);
 358   if (proto < 0x100) {                  /* Compress the protocol */
 359     rp[5] = proto & 0377;
 360     mi->m_len = 6;
 361     len++;
 362   } else {                              /* Don't compress the protocol */
 363     rp[5] = proto >> 8;
 364     rp[6] = proto & 0377;
 365     mi->m_len = 7;
 366     len += 2;
 367   }
 368   rp[0] = 0x80;                         /* BITS: 100xxxxx */
 369   rp[1] = len & 0377;                   /* The length */
 370   rp[2] = len >> 8;
 371   rp[3] = (~len) & 0377;                /* One's compliment of the length */
 372   rp[4] = (~len) >> 8;
 373
 374   state->cx.next_in = rp;
 375   state->cx.avail_in = mi->m_len;
 376   state->cx.next_out = garbage;
 377   state->cx.avail_out = sizeof garbage;
 378   flush = Z_NO_FLUSH;
 379   expect_error = 0;
 380
 381   while (1) {
 382     if ((res = inflate(&state->cx, flush)) != Z_OK) {
 383       if (res == Z_STREAM_END)
 384         break;                  /* Done */
 385       if (expect_error && res == Z_BUF_ERROR)
 386         break;
 387       log_Printf(LogCCP, "DeflateDictSetup: inflate returned %d (%s)\n",
 388                 res, state->cx.msg ? state->cx.msg : "");
 389       log_Printf(LogCCP, "DeflateDictSetup: avail_in %d, avail_out %d\n",
 390                 state->cx.avail_in, state->cx.avail_out);
 391       ccp_SendResetReq(&ccp->fsm);
 392       m_free(mi_head);          /* lose our allocated ``head'' buf */
 393       return;
 394     }
 395
 396     if (flush == Z_SYNC_FLUSH && state->cx.avail_out != 0)
 397       break;
 398
 399     if (state->cx.avail_in == 0 && mi && (mi = mi->m_next) != NULL) {
 400       /* underflow */
 401       state->cx.next_in = MBUF_CTOP(mi);
 402       state->cx.avail_in = mi->m_len;
 403       if (mi->m_next == NULL)
 404         flush = Z_SYNC_FLUSH;
 405     }
 406
 407     if (state->cx.avail_out == 0) {
 408       if (state->cx.avail_in == 0)
 409         /*
 410          * This seems to be a bug in libz !  If inflate() finished
 411          * with 0 avail_in and 0 avail_out *and* this is the end of
 412          * our input *and* inflate() *has* actually written all the
 413          * output it's going to, it *doesn't* return Z_STREAM_END !
 414          * When we subsequently call it with no more input, it gives
 415          * us Z_BUF_ERROR :-(  It seems pretty safe to ignore this
 416          * error (the dictionary seems to stay in sync).  In the worst
 417          * case, we'll drop the next compressed packet and do a
 418          * CcpReset() then.
 419          */
 420         expect_error = 1;
 421       /* overflow */
 422       state->cx.next_out = garbage;
 423       state->cx.avail_out = sizeof garbage;
 424     }
 425   }
 426
 427   ccp->compin += len;
 428   ccp->uncompin += len;
 429
 430   state->seqno++;
 431   state->uncomp_rec++;
 432   m_free(mi_head);              /* lose our allocated ``head'' buf */
 433 }
 434
 435 static const char *
 436 DeflateDispOpts(struct fsm_opt *o)
 437 {
 438   static char disp[7];          /* Must be used immediately */
 439
 440   sprintf(disp, "win %d", (o->data[0]>>4) + 8);
 441   return disp;
 442 }
 443
 444 static void
 445 DeflateInitOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o,
 446                       const struct ccp_config *cfg)
 447 {
 448   o->hdr.len = 4;
 449   o->data[0] = ((cfg->deflate.out.winsize - 8) << 4) + 8;
 450   o->data[1] = '\0';
 451 }
 452
 453 static int
 454 DeflateSetOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o,
 455                      const struct ccp_config *cfg __unused)
 456 {
 457   if (o->hdr.len != 4 || (o->data[0] & 15) != 8 || o->data[1] != '\0')
 458     return MODE_REJ;
 459
 460   if ((o->data[0] >> 4) + 8 > 15) {
 461     o->data[0] = ((15 - 8) << 4) + 8;
 462     return MODE_NAK;
 463   }
 464
 465   return MODE_ACK;
 466 }
 467
 468 static int
 469 DeflateSetOptsInput(struct bundle *bundle __unused, struct fsm_opt *o,
 470                     const struct ccp_config *cfg)
 471 {
 472   int want;
 473
 474   if (o->hdr.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 bundle *bundle __unused, struct fsm_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 bundle *bundle __unused, struct fsm_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 };