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