sys/net/mppcc.c

   1 /*-
   2  * Copyright (c) 2002-2004 Jan Dubiec <jdx@slackware.pl>
   3  * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice unmodified, this list of conditions, and the following
  11  *    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 /*
  32  * MPPC decompression library.
  33  * Version 1.0
  34  *
  35  * Note that Hi/Fn (later acquired by Exar Corporation) held US patents
  36  * on some implementation-critical aspects of MPPC compression.
  37  * These patents lapsed due to non-payment of fees in 2007 and by 2015
  38  * expired altogether.
  39  */
  40
  41 #include <sys/param.h>
  42 #include <sys/systm.h>
  43
  44 #include <net/mppc.h>
  45
  46 #define MPPE_HIST_LEN          8192
  47
  48 #define HASH(x)         (((40543*(((((x)[0]<<4)^(x)[1])<<4)^(x)[2]))>>4) & 0x1fff)
  49
  50 struct MPPC_comp_state {
  51     uint8_t     hist[2*MPPE_HIST_LEN];
  52     uint16_t    histptr;
  53     uint16_t    hash[MPPE_HIST_LEN];
  54 };
  55
  56 /* Inserts 1 to 8 bits into the output buffer. */
  57 static void __inline
  58 putbits8(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
  59 {
  60     buf += *i;
  61     if (*l >= n) {
  62         *l = (*l) - n;
  63         val <<= *l;
  64         *buf = *buf | (val & 0xff);
  65         if (*l == 0) {
  66             *l = 8;
  67             (*i)++;
  68             *(++buf) = 0;
  69         }
  70     } else {
  71         (*i)++;
  72         *l = 8 - n + (*l);
  73         val <<= *l;
  74         *buf = *buf | ((val >> 8) & 0xff);
  75         *(++buf) = val & 0xff;
  76     }
  77 }
  78
  79 /* Inserts 9 to 16 bits into the output buffer. */
  80 static void __inline
  81 putbits16(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
  82 {
  83     buf += *i;
  84     if (*l >= n - 8) {
  85         (*i)++;
  86         *l = 8 - n + (*l);
  87         val <<= *l;
  88         *buf = *buf | ((val >> 8) & 0xff);
  89         *(++buf) = val & 0xff;
  90         if (*l == 0) {
  91             *l = 8;
  92             (*i)++;
  93             *(++buf) = 0;
  94         }
  95     } else {
  96         (*i)++; (*i)++;
  97         *l = 16 - n + (*l);
  98         val <<= *l;
  99         *buf = *buf | ((val >> 16) & 0xff);
 100         *(++buf) = (val >> 8) & 0xff;
 101         *(++buf) = val & 0xff;
 102     }
 103 }
 104
 105 /* Inserts 17 to 24 bits into the output buffer. */
 106 static void __inline
 107 putbits24(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
 108 {
 109     buf += *i;
 110     if (*l >= n - 16) {
 111         (*i)++; (*i)++;
 112         *l = 16 - n + (*l);
 113         val <<= *l;
 114         *buf = *buf | ((val >> 16) & 0xff);
 115         *(++buf) = (val >> 8) & 0xff;
 116         *(++buf) = val & 0xff;
 117         if (*l == 0) {
 118             *l = 8;
 119             (*i)++;
 120             *(++buf) = 0;
 121         }
 122     } else {
 123         (*i)++; (*i)++; (*i)++;
 124         *l = 24 - n + (*l);
 125         val <<= *l;
 126         *buf = *buf | ((val >> 24) & 0xff);
 127         *(++buf) = (val >> 16) & 0xff;
 128         *(++buf) = (val >> 8) & 0xff;
 129         *(++buf) = val & 0xff;
 130     }
 131 }
 132
 133 size_t MPPC_SizeOfCompressionHistory(void)
 134 {
 135     return (sizeof(struct MPPC_comp_state));
 136 }
 137
 138 void MPPC_InitCompressionHistory(char *history)
 139 {
 140     struct MPPC_comp_state      *state = (struct MPPC_comp_state*)history;
 141
 142     bzero(history, sizeof(struct MPPC_comp_state));
 143     state->histptr = MPPE_HIST_LEN;
 144 }
 145
 146 int MPPC_Compress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags, int undef)
 147 {
 148     struct MPPC_comp_state      *state = (struct MPPC_comp_state*)history;
 149     uint32_t olen, off, len, idx, i, l;
 150     uint8_t *hist, *sbuf, *p, *q, *r, *s;
 151     int rtn = MPPC_OK;
 152
 153    /*
 154     * At this point, to avoid possible buffer overflow caused by packet
 155     * expansion during/after compression, we should make sure we have
 156     * space for the worst case.
 157
 158     * Maximum MPPC packet expansion is 12.5%. This is the worst case when
 159     * all octets in the input buffer are >= 0x80 and we cannot find any
 160     * repeated tokens.
 161     */
 162     if (*dstCnt < (*srcCnt * 9 / 8 + 2)) {
 163         rtn &= ~MPPC_OK;
 164         return (rtn);
 165     }
 166
 167     /* We can't compress more then MPPE_HIST_LEN bytes in a call. */
 168     if (*srcCnt > MPPE_HIST_LEN) {
 169         rtn &= ~MPPC_OK;
 170         return (rtn);
 171     }
 172
 173     hist = state->hist + MPPE_HIST_LEN;
 174     /* check if there is enough room at the end of the history */
 175     if (state->histptr + *srcCnt >= 2*MPPE_HIST_LEN) {
 176         rtn |= MPPC_RESTART_HISTORY;
 177         state->histptr = MPPE_HIST_LEN;
 178         memcpy(state->hist, hist, MPPE_HIST_LEN);
 179     }
 180     /* Add packet to the history. */
 181     sbuf = state->hist + state->histptr;
 182     memcpy(sbuf, *src, *srcCnt);
 183     state->histptr += *srcCnt;
 184
 185     /* compress data */
 186     r = sbuf + *srcCnt;
 187     **dst = olen = i = 0;
 188     l = 8;
 189     while (i < *srcCnt - 2) {
 190         s = q = sbuf + i;
 191
 192         /* Prognose matching position using hash function. */
 193         idx = HASH(s);
 194         p = hist + state->hash[idx];
 195         state->hash[idx] = (uint16_t) (s - hist);
 196         if (p > s)      /* It was before MPPC_RESTART_HISTORY. */
 197             p -= MPPE_HIST_LEN; /* Try previous history buffer. */
 198         off = s - p;
 199
 200         /* Check our prognosis. */
 201         if (off > MPPE_HIST_LEN - 1 || off < 1 || *p++ != *s++ ||
 202             *p++ != *s++ || *p++ != *s++) {
 203             /* No match found; encode literal byte. */
 204             if ((*src)[i] < 0x80) {             /* literal byte < 0x80 */
 205                 putbits8(*dst, (uint32_t) (*src)[i], 8, &olen, &l);
 206             } else {                            /* literal byte >= 0x80 */
 207                 putbits16(*dst, (uint32_t) (0x100|((*src)[i]&0x7f)), 9,
 208                     &olen, &l);
 209             }
 210             ++i;
 211             continue;
 212         }
 213
 214         /* Find length of the matching fragment */
 215 #if defined(__amd64__) || defined(__i386__)
 216         /* Optimization for CPUs without strict data aligning requirements */
 217         while ((*((uint32_t*)p) == *((uint32_t*)s)) && (s < (r - 3))) {
 218             p+=4;
 219             s+=4;
 220         }
 221 #endif
 222         while((*p++ == *s++) && (s <= r));
 223         len = s - q - 1;
 224         i += len;
 225
 226         /* At least 3 character match found; code data. */
 227         /* Encode offset. */
 228         if (off < 64) {                 /* 10-bit offset; 0 <= offset < 64 */
 229             putbits16(*dst, 0x3c0|off, 10, &olen, &l);
 230         } else if (off < 320) {         /* 12-bit offset; 64 <= offset < 320 */
 231             putbits16(*dst, 0xe00|(off-64), 12, &olen, &l);
 232         } else if (off < 8192) {        /* 16-bit offset; 320 <= offset < 8192 */
 233             putbits16(*dst, 0xc000|(off-320), 16, &olen, &l);
 234         } else {                /* NOTREACHED */
 235             rtn &= ~MPPC_OK;
 236             return rtn;
 237         }
 238
 239         /* Encode length of match. */
 240         if (len < 4) {                  /* length = 3 */
 241             putbits8(*dst, 0, 1, &olen, &l);
 242         } else if (len < 8) {           /* 4 <= length < 8 */
 243             putbits8(*dst, 0x08|(len&0x03), 4, &olen, &l);
 244         } else if (len < 16) {          /* 8 <= length < 16 */
 245             putbits8(*dst, 0x30|(len&0x07), 6, &olen, &l);
 246         } else if (len < 32) {          /* 16 <= length < 32 */
 247             putbits8(*dst, 0xe0|(len&0x0f), 8, &olen, &l);
 248         } else if (len < 64) {          /* 32 <= length < 64 */
 249             putbits16(*dst, 0x3c0|(len&0x1f), 10, &olen, &l);
 250         } else if (len < 128) {         /* 64 <= length < 128 */
 251             putbits16(*dst, 0xf80|(len&0x3f), 12, &olen, &l);
 252         } else if (len < 256) {         /* 128 <= length < 256 */
 253             putbits16(*dst, 0x3f00|(len&0x7f), 14, &olen, &l);
 254         } else if (len < 512) {         /* 256 <= length < 512 */
 255             putbits16(*dst, 0xfe00|(len&0xff), 16, &olen, &l);
 256         } else if (len < 1024) {        /* 512 <= length < 1024 */
 257             putbits24(*dst, 0x3fc00|(len&0x1ff), 18, &olen, &l);
 258         } else if (len < 2048) {        /* 1024 <= length < 2048 */
 259             putbits24(*dst, 0xff800|(len&0x3ff), 20, &olen, &l);
 260         } else if (len < 4096) {        /* 2048 <= length < 4096 */
 261             putbits24(*dst, 0x3ff000|(len&0x7ff), 22, &olen, &l);
 262         } else if (len < 8192) {        /* 4096 <= length < 8192 */
 263             putbits24(*dst, 0xffe000|(len&0xfff), 24, &olen, &l);
 264         } else {        /* NOTREACHED */
 265             rtn &= ~MPPC_OK;
 266             return (rtn);
 267         }
 268     }
 269
 270     /* Add remaining octets to the output. */
 271     while(*srcCnt - i > 0) {
 272         if ((*src)[i] < 0x80) { /* literal byte < 0x80 */
 273             putbits8(*dst, (uint32_t) (*src)[i++], 8, &olen, &l);
 274         } else {                /* literal byte >= 0x80 */
 275             putbits16(*dst, (uint32_t) (0x100|((*src)[i++]&0x7f)), 9, &olen,
 276                 &l);
 277         }
 278     }
 279
 280     /* Reset unused bits of the last output octet. */
 281     if ((l != 0) && (l != 8)) {
 282         putbits8(*dst, 0, l, &olen, &l);
 283     }
 284
 285     /* If result is bigger then original, set flag and flush history. */
 286     if ((*srcCnt < olen) || ((flags & MPPC_SAVE_HISTORY) == 0)) {
 287         if (*srcCnt < olen)
 288             rtn |= MPPC_EXPANDED;
 289         bzero(history, sizeof(struct MPPC_comp_state));
 290         state->histptr = MPPE_HIST_LEN;
 291     }
 292
 293     *src += *srcCnt;
 294     *srcCnt = 0;
 295     *dst += olen;
 296     *dstCnt -= olen;
 297
 298     return (rtn);
 299 }