Home | History | Annotate | Download | only in src 
      1 /*-
      2  * Copyright (c) 1997 Brian Somers <brian (at) Awfulhak.org>
      3  *                    Ian Donaldson <iand (at) labtam.labtam.oz.au>
      4  *                    Carsten Bormann <cabo (at) cs.tu-berlin.de>
      5  *                    Dave Rand <dlr (at) bungi.com>/<dave_rand (at) novell.com>
      6  * All rights reserved.
      7  *
      8  * Redistribution and use in source and binary forms, with or without
      9  * modification, are permitted provided that the following conditions
     10  * are met:
     11  * 1. Redistributions of source code must retain the above copyright
     12  *    notice, this list of conditions and the following disclaimer.
     13  * 2. Redistributions in binary form must reproduce the above copyright
     14  *    notice, this list of conditions and the following disclaimer in the
     15  *    documentation and/or other materials provided with the distribution.
     16  *
     17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
     18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
     21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     27  * SUCH DAMAGE.
     28  *
     29  * $FreeBSD: src/usr.sbin/ppp/pred.c,v 1.35.26.1 2010/12/21 17:10:29 kensmith Exp $
     30  */
     31 
     32 #include <sys/types.h>
     33 
     34 #include <stdlib.h>
     35 #include <string.h>
     36 #include <termios.h>
     37 
     38 #include "defs.h"
     39 #include "layer.h"
     40 #include "mbuf.h"
     41 #include "log.h"
     42 #include "timer.h"
     43 #include "fsm.h"
     44 #include "lqr.h"
     45 #include "hdlc.h"
     46 #include "lcp.h"
     47 #include "ccp.h"
     48 #include "throughput.h"
     49 #include "link.h"
     50 #include "pred.h"
     51 
     52 /* The following hash code is the heart of the algorithm:
     53  * It builds a sliding hash sum of the previous 3-and-a-bit characters
     54  * which will be used to index the guess table.
     55  * A better hash function would result in additional compression,
     56  * at the expense of time.
     57  */
     58 #define HASH(state, x) state->hash = (state->hash << 4) ^ (x)
     59 #define GUESS_TABLE_SIZE 65536
     60 
     61 struct pred1_state {
     62   u_short hash;
     63   u_char dict[GUESS_TABLE_SIZE];
     64 };
     65 
     66 static int
     67 compress(struct pred1_state *state, u_char *source, u_char *dest, int len)
     68 {
     69   int i, bitmask;
     70   unsigned char *flagdest, flags, *orgdest;
     71 
     72   orgdest = dest;
     73   while (len) {
     74     flagdest = dest++;
     75     flags = 0;			/* All guess wrong initially */
     76     for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) {
     77       if (state->dict[state->hash] == *source) {
     78 	flags |= bitmask;	/* Guess was right - don't output */
     79       } else {
     80 	state->dict[state->hash] = *source;
     81 	*dest++ = *source;	/* Guess wrong, output char */
     82       }
     83       HASH(state, *source++);
     84       len--;
     85     }
     86     *flagdest = flags;
     87   }
     88   return (dest - orgdest);
     89 }
     90 
     91 static void
     92 SyncTable(struct pred1_state *state, u_char *source, u_char *dest, int len)
     93 {
     94   while (len--) {
     95     *dest++ = state->dict[state->hash] = *source;
     96     HASH(state, *source++);
     97   }
     98 }
     99 
    100 static int
    101 decompress(struct pred1_state *state, u_char *source, u_char *dest, int len)
    102 {
    103   int i, bitmask;
    104   unsigned char flags, *orgdest;
    105 
    106   orgdest = dest;
    107   while (len) {
    108     flags = *source++;
    109     len--;
    110     for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
    111       if (flags & bitmask) {
    112 	*dest = state->dict[state->hash];	/* Guess correct */
    113       } else {
    114 	if (!len)
    115 	  break;		/* we seem to be really done -- cabo */
    116 	state->dict[state->hash] = *source;	/* Guess wrong */
    117 	*dest = *source++;	/* Read from source */
    118 	len--;
    119       }
    120       HASH(state, *dest++);
    121     }
    122   }
    123   return (dest - orgdest);
    124 }
    125 
    126 static void
    127 Pred1Term(void *v)
    128 {
    129   struct pred1_state *state = (struct pred1_state *)v;
    130   free(state);
    131 }
    132 
    133 static void
    134 Pred1ResetInput(void *v)
    135 {
    136   struct pred1_state *state = (struct pred1_state *)v;
    137   state->hash = 0;
    138   memset(state->dict, '\0', sizeof state->dict);
    139   log_Printf(LogCCP, "Predictor1: Input channel reset\n");
    140 }
    141 
    142 static int
    143 Pred1ResetOutput(void *v)
    144 {
    145   struct pred1_state *state = (struct pred1_state *)v;
    146   state->hash = 0;
    147   memset(state->dict, '\0', sizeof state->dict);
    148   log_Printf(LogCCP, "Predictor1: Output channel reset\n");
    149 
    150   return 1;		/* Ask FSM to ACK */
    151 }
    152 
    153 static void *
    154 Pred1InitInput(struct bundle *bundle __unused, struct fsm_opt *o __unused)
    155 {
    156   struct pred1_state *state;
    157   state = (struct pred1_state *)malloc(sizeof(struct pred1_state));
    158   if (state != NULL)
    159     Pred1ResetInput(state);
    160   return state;
    161 }
    162 
    163 static void *
    164 Pred1InitOutput(struct bundle *bundle __unused, struct fsm_opt *o __unused)
    165 {
    166   struct pred1_state *state;
    167   state = (struct pred1_state *)malloc(sizeof(struct pred1_state));
    168   if (state != NULL)
    169     Pred1ResetOutput(state);
    170   return state;
    171 }
    172 
    173 static struct mbuf *
    174 Pred1Output(void *v, struct ccp *ccp, struct link *l __unused,
    175 	    int pri __unused, u_short *proto, struct mbuf *bp)
    176 {
    177   struct pred1_state *state = (struct pred1_state *)v;
    178   struct mbuf *mwp;
    179   u_char *cp, *wp, *hp;
    180   int orglen, len;
    181   u_char bufp[MAX_MTU + 2];
    182   u_short fcs;
    183 
    184   orglen = m_length(bp) + 2;	/* add count of proto */
    185   mwp = m_get((orglen + 2) / 8 * 9 + 12, MB_CCPOUT);
    186   hp = wp = MBUF_CTOP(mwp);
    187   cp = bufp;
    188   *wp++ = *cp++ = orglen >> 8;
    189   *wp++ = *cp++ = orglen & 0377;
    190   *cp++ = *proto >> 8;
    191   *cp++ = *proto & 0377;
    192   mbuf_Read(bp, cp, orglen - 2);
    193   fcs = hdlc_Fcs(bufp, 2 + orglen);
    194   fcs = ~fcs;
    195 
    196   len = compress(state, bufp + 2, wp, orglen);
    197   log_Printf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len);
    198   ccp->uncompout += orglen;
    199   if (len < orglen) {
    200     *hp |= 0x80;
    201     wp += len;
    202     ccp->compout += len;
    203   } else {
    204     memcpy(wp, bufp + 2, orglen);
    205     wp += orglen;
    206     ccp->compout += orglen;
    207   }
    208 
    209   *wp++ = fcs & 0377;
    210   *wp++ = fcs >> 8;
    211   mwp->m_len = wp - MBUF_CTOP(mwp);
    212   *proto = ccp_Proto(ccp);
    213   return mwp;
    214 }
    215 
    216 static struct mbuf *
    217 Pred1Input(void *v, struct ccp *ccp, u_short *proto, struct mbuf *bp)
    218 {
    219   struct pred1_state *state = (struct pred1_state *)v;
    220   u_char *cp, *pp;
    221   int len, olen, len1;
    222   struct mbuf *wp;
    223   u_char *bufp;
    224   u_short fcs;
    225 
    226   wp = m_get(MAX_MRU + 2, MB_CCPIN);
    227   cp = MBUF_CTOP(bp);
    228   olen = m_length(bp);
    229   pp = bufp = MBUF_CTOP(wp);
    230   *pp++ = *cp & 0177;
    231   len = *cp++ << 8;
    232   *pp++ = *cp;
    233   len += *cp++;
    234   ccp->uncompin += len & 0x7fff;
    235   if (len & 0x8000) {
    236     len1 = decompress(state, cp, pp, olen - 4);
    237     ccp->compin += olen;
    238     len &= 0x7fff;
    239     if (len != len1) {		/* Error is detected. Send reset request */
    240       log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len1, len);
    241       fsm_Reopen(&ccp->fsm);
    242       m_freem(bp);
    243       m_freem(wp);
    244       return NULL;
    245     }
    246     cp += olen - 4;
    247     pp += len1;
    248   } else if (len + 4 != olen) {
    249     log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len + 4, olen);
    250     fsm_Reopen(&ccp->fsm);
    251     m_freem(wp);
    252     m_freem(bp);
    253     return NULL;
    254   } else {
    255     ccp->compin += len;
    256     SyncTable(state, cp, pp, len);
    257     cp += len;
    258     pp += len;
    259   }
    260   *pp++ = *cp++;		/* CRC */
    261   *pp++ = *cp++;
    262   fcs = hdlc_Fcs(bufp, wp->m_len = pp - bufp);
    263   if (fcs == GOODFCS) {
    264     wp->m_offset += 2;		/* skip length */
    265     wp->m_len -= 4;		/* skip length & CRC */
    266     pp = MBUF_CTOP(wp);
    267     *proto = *pp++;
    268     if (*proto & 1) {
    269       wp->m_offset++;
    270       wp->m_len--;
    271     } else {
    272       wp->m_offset += 2;
    273       wp->m_len -= 2;
    274       *proto = (*proto << 8) | *pp++;
    275     }
    276     m_freem(bp);
    277     return wp;
    278   } else {
    279     const char *pre = *MBUF_CTOP(bp) & 0x80 ? "" : "un";
    280     log_Printf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%scompressed), len = 0x%x,"
    281 	      " olen = 0x%x\n", fcs, pre, len, olen);
    282     log_Printf(LogCCP, "%s: Bad %scompressed CRC-16\n",
    283                ccp->fsm.link->name, pre);
    284     fsm_Reopen(&ccp->fsm);
    285     m_freem(wp);
    286   }
    287   m_freem(bp);
    288   return NULL;
    289 }
    290 
    291 static void
    292 Pred1DictSetup(void *v __unused, struct ccp *ccp __unused,
    293 	       u_short proto __unused, struct mbuf *bp __unused)
    294 {
    295   /* Nothing to see here */
    296 }
    297 
    298 static const char *
    299 Pred1DispOpts(struct fsm_opt *o __unused)
    300 {
    301   return NULL;
    302 }
    303 
    304 static void
    305 Pred1InitOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o,
    306                     const struct ccp_config *cfg __unused)
    307 {
    308   o->hdr.len = 2;
    309 }
    310 
    311 static int
    312 Pred1SetOpts(struct bundle *bundle __unused, struct fsm_opt *o,
    313              const struct ccp_config *cfg __unused)
    314 {
    315   if (o->hdr.len != 2) {
    316     o->hdr.len = 2;
    317     return MODE_NAK;
    318   }
    319   return MODE_ACK;
    320 }
    321 
    322 const struct ccp_algorithm Pred1Algorithm = {
    323   TY_PRED1,
    324   CCP_NEG_PRED1,
    325   Pred1DispOpts,
    326   ccp_DefaultUsable,
    327   ccp_DefaultRequired,
    328   {
    329     Pred1SetOpts,
    330     Pred1InitInput,
    331     Pred1Term,
    332     Pred1ResetInput,
    333     Pred1Input,
    334     Pred1DictSetup
    335   },
    336   {
    337     0,
    338     Pred1InitOptsOutput,
    339     Pred1SetOpts,
    340     Pred1InitOutput,
    341     Pred1Term,
    342     Pred1ResetOutput,
    343     Pred1Output
    344   },
    345 };
    346