ng_mppc(4): Bring netgraph(3) MPPC compression support.

Support for compression has been available from July 2007 but it
was never imported due to concerns with patents once held by
STAC/HiFn. The issues have clearly been resolved so bring it
in now.

Special thanks to Brett Glass for preserving the code and
pointing documentation for the expiration case.

Obtained from:	mav (through Brett Glass)
Relnotes:	yes
MFC after:	2 weeks
Differential Revision:	https://reviews.freebsd.org/D6739

3 files changed, 645 insertions, 0 deletions

diff --git a/sys/net/mppc.h b/sys/net/mppc.h
new file mode 100644
index 0000000..29b5113
--- /dev/null
+++ b/sys/net/mppc.h
@@ -0,0 +1,62 @@
+/*-
+ * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice unmodified, this list of conditions, and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+/*
+ * MPPC decompression library.
+ * Version 1.0
+ *
+ * Note that Hi/Fn (later acquired by Exar Corporation) held US patents
+ * on some implementation-critical aspects of MPPC compression.
+ * These patents lapsed due to non-payment of fees in 2007 and by 2015
+ * expired altogether.
+ */
+
+#ifndef _NET_MPPC_H_
+#define	_NET_MPPC_H_
+
+#define	MPPC_MANDATORY_COMPRESS_FLAGS 0
+#define	MPPC_MANDATORY_DECOMPRESS_FLAGS 0
+
+#define	MPPC_SAVE_HISTORY 1
+
+#define	MPPC_OK 5
+#define	MPPC_EXPANDED 8
+#define	MPPC_RESTART_HISTORY 16
+#define	MPPC_DEST_EXHAUSTED 32
+
+extern size_t MPPC_SizeOfCompressionHistory(void);
+extern size_t MPPC_SizeOfDecompressionHistory(void);
+
+extern void MPPC_InitCompressionHistory(char *history);
+extern void MPPC_InitDecompressionHistory(char *history);
+
+extern int MPPC_Compress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags, int undef);
+extern int MPPC_Decompress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags);
+
+#endif
diff --git a/sys/net/mppcc.c b/sys/net/mppcc.c
new file mode 100644
index 0000000..01ce3ff
--- /dev/null
+++ b/sys/net/mppcc.c
@@ -0,0 +1,299 @@
+/*-
+ * Copyright (c) 2002-2004 Jan Dubiec <jdx@slackware.pl>
+ * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice unmodified, this list of conditions, and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+/*
+ * MPPC decompression library.
+ * Version 1.0
+ *
+ * Note that Hi/Fn (later acquired by Exar Corporation) held US patents
+ * on some implementation-critical aspects of MPPC compression.
+ * These patents lapsed due to non-payment of fees in 2007 and by 2015
+ * expired altogether.
+ */
+
+#include <sys/param.h>
+#include <sys/systm.h>
+
+#include <net/mppc.h>
+
+#define	MPPE_HIST_LEN          8192
+
+#define	HASH(x)		(((40543*(((((x)[0]<<4)^(x)[1])<<4)^(x)[2]))>>4) & 0x1fff)
+
+struct MPPC_comp_state {
+    uint8_t	hist[2*MPPE_HIST_LEN];
+    uint16_t	histptr;
+    uint16_t	hash[MPPE_HIST_LEN];
+};
+
+/* Inserts 1 to 8 bits into the output buffer. */
+static void __inline 
+putbits8(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
+{
+    buf += *i;
+    if (*l >= n) {
+	*l = (*l) - n;
+	val <<= *l;
+	*buf = *buf | (val & 0xff);
+	if (*l == 0) {
+	    *l = 8;
+	    (*i)++;
+	    *(++buf) = 0;
+	}
+    } else {
+	(*i)++;
+	*l = 8 - n + (*l);
+	val <<= *l;
+	*buf = *buf | ((val >> 8) & 0xff);
+	*(++buf) = val & 0xff;
+    }
+}
+
+/* Inserts 9 to 16 bits into the output buffer. */
+static void __inline
+putbits16(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
+{
+    buf += *i;
+    if (*l >= n - 8) {
+	(*i)++;
+	*l = 8 - n + (*l);
+	val <<= *l;
+	*buf = *buf | ((val >> 8) & 0xff);
+	*(++buf) = val & 0xff;
+	if (*l == 0) {
+	    *l = 8;
+	    (*i)++;
+	    *(++buf) = 0;
+	}
+    } else {
+	(*i)++; (*i)++;
+	*l = 16 - n + (*l);
+	val <<= *l;
+	*buf = *buf | ((val >> 16) & 0xff);
+	*(++buf) = (val >> 8) & 0xff;
+	*(++buf) = val & 0xff;
+    }
+}
+
+/* Inserts 17 to 24 bits into the output buffer. */
+static void __inline
+putbits24(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
+{
+    buf += *i;
+    if (*l >= n - 16) {
+	(*i)++; (*i)++;
+	*l = 16 - n + (*l);
+	val <<= *l;
+	*buf = *buf | ((val >> 16) & 0xff);
+	*(++buf) = (val >> 8) & 0xff;
+	*(++buf) = val & 0xff;
+	if (*l == 0) {
+	    *l = 8;
+	    (*i)++;
+	    *(++buf) = 0;
+	}
+    } else {
+	(*i)++; (*i)++; (*i)++;
+	*l = 24 - n + (*l);
+	val <<= *l;
+	*buf = *buf | ((val >> 24) & 0xff);
+	*(++buf) = (val >> 16) & 0xff;
+	*(++buf) = (val >> 8) & 0xff;
+	*(++buf) = val & 0xff;
+    }
+}
+
+size_t MPPC_SizeOfCompressionHistory(void)
+{
+    return (sizeof(struct MPPC_comp_state));
+}
+
+void MPPC_InitCompressionHistory(char *history)
+{
+    struct MPPC_comp_state      *state = (struct MPPC_comp_state*)history;
+
+    bzero(history, sizeof(struct MPPC_comp_state));
+    state->histptr = MPPE_HIST_LEN;
+}
+
+int MPPC_Compress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags, int undef)
+{
+    struct MPPC_comp_state	*state = (struct MPPC_comp_state*)history;
+    uint32_t olen, off, len, idx, i, l;
+    uint8_t *hist, *sbuf, *p, *q, *r, *s;    
+    int	rtn = MPPC_OK;
+
+   /*
+    * At this point, to avoid possible buffer overflow caused by packet
+    * expansion during/after compression, we should make sure we have
+    * space for the worst case.
+
+    * Maximum MPPC packet expansion is 12.5%. This is the worst case when
+    * all octets in the input buffer are >= 0x80 and we cannot find any
+    * repeated tokens.
+    */
+    if (*dstCnt < (*srcCnt * 9 / 8 + 2)) {
+	rtn &= ~MPPC_OK;
+	return (rtn);
+    }
+
+    /* We can't compress more then MPPE_HIST_LEN bytes in a call. */
+    if (*srcCnt > MPPE_HIST_LEN) {
+	rtn &= ~MPPC_OK;
+	return (rtn);
+    }
+
+    hist = state->hist + MPPE_HIST_LEN;
+    /* check if there is enough room at the end of the history */
+    if (state->histptr + *srcCnt >= 2*MPPE_HIST_LEN) {
+	rtn |= MPPC_RESTART_HISTORY;
+	state->histptr = MPPE_HIST_LEN;
+	memcpy(state->hist, hist, MPPE_HIST_LEN);
+    }
+    /* Add packet to the history. */
+    sbuf = state->hist + state->histptr;
+    memcpy(sbuf, *src, *srcCnt);
+    state->histptr += *srcCnt;
+
+    /* compress data */
+    r = sbuf + *srcCnt;
+    **dst = olen = i = 0;
+    l = 8;
+    while (i < *srcCnt - 2) {
+	s = q = sbuf + i;
+
+	/* Prognose matching position using hash function. */
+	idx = HASH(s);
+	p = hist + state->hash[idx];
+	state->hash[idx] = (uint16_t) (s - hist);
+	if (p > s)	/* It was before MPPC_RESTART_HISTORY. */
+	    p -= MPPE_HIST_LEN;	/* Try previous history buffer. */
+	off = s - p;
+
+	/* Check our prognosis. */
+	if (off > MPPE_HIST_LEN - 1 || off < 1 || *p++ != *s++ ||
+	    *p++ != *s++ || *p++ != *s++) {
+	    /* No match found; encode literal byte. */
+	    if ((*src)[i] < 0x80) {		/* literal byte < 0x80 */
+		putbits8(*dst, (uint32_t) (*src)[i], 8, &olen, &l);
+	    } else {				/* literal byte >= 0x80 */
+		putbits16(*dst, (uint32_t) (0x100|((*src)[i]&0x7f)), 9,
+		    &olen, &l);
+	    }
+	    ++i;
+	    continue;
+	}
+
+	/* Find length of the matching fragment */
+#if defined(__amd64__) || defined(__i386__)
+	/* Optimization for CPUs without strict data aligning requirements */
+	while ((*((uint32_t*)p) == *((uint32_t*)s)) && (s < (r - 3))) {
+	    p+=4;
+	    s+=4;
+	}
+#endif
+	while((*p++ == *s++) && (s <= r));
+	len = s - q - 1;
+	i += len;
+
+	/* At least 3 character match found; code data. */
+	/* Encode offset. */
+	if (off < 64) {			/* 10-bit offset; 0 <= offset < 64 */
+	    putbits16(*dst, 0x3c0|off, 10, &olen, &l);
+	} else if (off < 320) {		/* 12-bit offset; 64 <= offset < 320 */
+	    putbits16(*dst, 0xe00|(off-64), 12, &olen, &l);
+	} else if (off < 8192) {	/* 16-bit offset; 320 <= offset < 8192 */
+	    putbits16(*dst, 0xc000|(off-320), 16, &olen, &l);
+	} else {		/* NOTREACHED */
+	    rtn &= ~MPPC_OK;
+	    return rtn;
+	}
+
+	/* Encode length of match. */
+	if (len < 4) {			/* length = 3 */
+	    putbits8(*dst, 0, 1, &olen, &l);
+	} else if (len < 8) {		/* 4 <= length < 8 */
+	    putbits8(*dst, 0x08|(len&0x03), 4, &olen, &l);
+	} else if (len < 16) {		/* 8 <= length < 16 */
+	    putbits8(*dst, 0x30|(len&0x07), 6, &olen, &l);
+	} else if (len < 32) {		/* 16 <= length < 32 */
+	    putbits8(*dst, 0xe0|(len&0x0f), 8, &olen, &l);
+	} else if (len < 64) {		/* 32 <= length < 64 */
+	    putbits16(*dst, 0x3c0|(len&0x1f), 10, &olen, &l);
+	} else if (len < 128) {		/* 64 <= length < 128 */
+	    putbits16(*dst, 0xf80|(len&0x3f), 12, &olen, &l);
+	} else if (len < 256) {		/* 128 <= length < 256 */
+	    putbits16(*dst, 0x3f00|(len&0x7f), 14, &olen, &l);
+	} else if (len < 512) {		/* 256 <= length < 512 */
+	    putbits16(*dst, 0xfe00|(len&0xff), 16, &olen, &l);
+	} else if (len < 1024) {	/* 512 <= length < 1024 */
+	    putbits24(*dst, 0x3fc00|(len&0x1ff), 18, &olen, &l);
+	} else if (len < 2048) {	/* 1024 <= length < 2048 */
+	    putbits24(*dst, 0xff800|(len&0x3ff), 20, &olen, &l);
+	} else if (len < 4096) {	/* 2048 <= length < 4096 */
+	    putbits24(*dst, 0x3ff000|(len&0x7ff), 22, &olen, &l);
+	} else if (len < 8192) {	/* 4096 <= length < 8192 */
+	    putbits24(*dst, 0xffe000|(len&0xfff), 24, &olen, &l);
+	} else {	/* NOTREACHED */
+	    rtn &= ~MPPC_OK;
+	    return (rtn);
+	}
+    }
+
+    /* Add remaining octets to the output. */
+    while(*srcCnt - i > 0) {
+	if ((*src)[i] < 0x80) {	/* literal byte < 0x80 */
+	    putbits8(*dst, (uint32_t) (*src)[i++], 8, &olen, &l);
+	} else {		/* literal byte >= 0x80 */
+	    putbits16(*dst, (uint32_t) (0x100|((*src)[i++]&0x7f)), 9, &olen,
+	        &l);
+	}
+    }
+
+    /* Reset unused bits of the last output octet. */
+    if ((l != 0) && (l != 8)) {
+	putbits8(*dst, 0, l, &olen, &l);
+    }
+
+    /* If result is bigger then original, set flag and flush history. */
+    if ((*srcCnt < olen) || ((flags & MPPC_SAVE_HISTORY) == 0)) {
+	if (*srcCnt < olen)
+	    rtn |= MPPC_EXPANDED;
+	bzero(history, sizeof(struct MPPC_comp_state));
+	state->histptr = MPPE_HIST_LEN;
+    }
+
+    *src += *srcCnt;
+    *srcCnt = 0;
+    *dst += olen;
+    *dstCnt -= olen;
+
+    return (rtn);
+}
diff --git a/sys/net/mppcd.c b/sys/net/mppcd.c
new file mode 100644
index 0000000..c1730e5
--- /dev/null
+++ b/sys/net/mppcd.c
@@ -0,0 +1,284 @@
+/*-
+ * Copyright (c) 2002-2004 Jan Dubiec <jdx@slackware.pl>
+ * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice unmodified, this list of conditions, and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+/*
+ * MPPC decompression library.
+ * Version 1.0
+ *
+ * Note that Hi/Fn (later acquired by Exar Corporation) held US patents
+ * on some implementation-critical aspects of MPPC compression.
+ * These patents lapsed due to non-payment of fees in 2007 and by 2015
+ * expired altogether.
+ */
+
+#include <sys/param.h>
+#include <sys/systm.h>
+
+#include <net/mppc.h>
+
+#define	MPPE_HIST_LEN          8192
+
+struct MPPC_decomp_state {
+    uint8_t	hist[2*MPPE_HIST_LEN];
+    uint16_t	histptr;
+};
+
+static uint32_t __inline
+getbits(const uint8_t *buf, const uint32_t n, uint32_t *i, uint32_t *l)
+{
+    static const uint32_t m[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
+    uint32_t res, ol;
+
+    ol = *l;
+    if (*l >= n) {
+	*l = (*l) - n;
+	res = (buf[*i] & m[ol]) >> (*l);
+	if (*l == 0) {
+	    *l = 8;
+	    (*i)++;
+	}
+    } else {
+	*l = 8 - n + (*l);
+	res = (buf[(*i)++] & m[ol]) << 8;
+	res = (res | buf[*i]) >> (*l);
+    }
+
+    return (res);
+}
+
+static uint32_t __inline
+getbyte(const uint8_t *buf, const uint32_t i, const uint32_t l)
+{
+    if (l == 8) {
+	return (buf[i]);
+    } else {
+	return ((((buf[i] << 8) | buf[i+1]) >> l) & 0xff);
+    }
+}
+
+static void __inline
+lamecopy(uint8_t *dst, uint8_t *src, uint32_t len)
+{
+    while (len--)
+	*dst++ = *src++;
+}
+
+size_t MPPC_SizeOfDecompressionHistory(void)
+{
+    return (sizeof(struct MPPC_decomp_state));
+}
+
+void MPPC_InitDecompressionHistory(char *history)
+{
+    struct MPPC_decomp_state      *state = (struct MPPC_decomp_state*)history;
+
+    bzero(history, sizeof(struct MPPC_decomp_state));
+    state->histptr = MPPE_HIST_LEN;
+}
+
+int MPPC_Decompress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags)
+{
+    struct MPPC_decomp_state      *state = (struct MPPC_decomp_state*)history;
+    uint32_t olen, off, len, bits, val, sig, i, l;
+    uint8_t *hist, *s;
+    u_char *isrc = *src;
+    int	rtn = MPPC_OK;
+
+    if ((flags & MPPC_RESTART_HISTORY) != 0) {
+	memcpy(state->hist, state->hist + MPPE_HIST_LEN, MPPE_HIST_LEN);
+	state->histptr = MPPE_HIST_LEN;
+    }
+
+    hist = state->hist + state->histptr;
+    olen = len = i = 0;
+    l = 8;
+    bits = *srcCnt * 8;
+    while (bits >= 8) {
+	val = getbyte(isrc, i++, l);
+	if (val < 0x80) {		/* literal byte < 0x80 */
+	    if (state->histptr < 2*MPPE_HIST_LEN) {
+		/* Copy uncompressed byte to the history. */
+		(state->hist)[(state->histptr)++] = (uint8_t) val;
+	    } else {
+		/* Buffer overflow; drop packet. */
+		rtn &= ~MPPC_OK;
+		return rtn;
+	    }
+	    olen++;
+	    bits -= 8;
+	    continue;
+	}
+
+	sig = val & 0xc0;
+	if (sig == 0x80) {		/* literal byte >= 0x80 */
+	    if (state->histptr < 2*MPPE_HIST_LEN) {
+		/* Copy uncompressed byte to the history. */
+		(state->hist)[(state->histptr)++] = 
+		    (uint8_t) (0x80|((val&0x3f)<<1)|getbits(isrc, 1 , &i ,&l));
+	    } else {
+		/* buffer overflow; drop packet */
+		rtn &= ~MPPC_OK;
+		return (rtn);
+	    }
+	    olen++;
+	    bits -= 9;
+	    continue;
+	}
+
+	/* Not a literal byte so it must be an (offset,length) pair */
+	/* decode offset */
+	sig = val & 0xf0;
+	if (sig == 0xf0) {		/* 10-bit offset; 0 <= offset < 64 */
+	    off = (((val&0x0f)<<2)|getbits(isrc, 2 , &i ,&l));
+	    bits -= 10;
+	} else {
+	    if (sig == 0xe0) {		/* 12-bit offset; 64 <= offset < 320 */
+		off = ((((val&0x0f)<<4)|getbits(isrc, 4 , &i ,&l))+64);
+		bits -= 12;
+	    } else {
+		if ((sig&0xe0) == 0xc0) {/* 16-bit offset; 320 <= offset < 8192 */
+		    off = ((((val&0x1f)<<8)|getbyte(isrc, i++, l))+320);
+		    bits -= 16;
+		    if (off > MPPE_HIST_LEN - 1) {
+			rtn &= ~MPPC_OK;
+			return (rtn);
+		    }
+		} else {		/* NOTREACHED */
+		    rtn &= ~MPPC_OK;
+		    return (rtn);
+		}
+	    }
+	}
+	/* Decode length of match. */
+	val = getbyte(isrc, i, l);
+	if ((val & 0x80) == 0x00) {			/* len = 3 */
+	    len = 3;
+	    bits--;
+	    getbits(isrc, 1 , &i ,&l);
+	} else if ((val & 0xc0) == 0x80) {		/* 4 <= len < 8 */
+	    len = 0x04 | ((val>>4) & 0x03);
+	    bits -= 4;
+	    getbits(isrc, 4 , &i ,&l);
+	} else if ((val & 0xe0) == 0xc0) {		/* 8 <= len < 16 */
+	    len = 0x08 | ((val>>2) & 0x07);
+	    bits -= 6;
+	    getbits(isrc, 6 , &i ,&l);
+	} else if ((val & 0xf0) == 0xe0) {		/* 16 <= len < 32 */
+	    len = 0x10 | (val & 0x0f);
+	    bits -= 8;
+	    i++;
+	} else {
+	    bits -= 8;
+	    val = (val << 8) | getbyte(isrc, ++i, l);
+	    if ((val & 0xf800) == 0xf000) {		/* 32 <= len < 64 */
+		len = 0x0020 | ((val >> 6) & 0x001f);
+		bits -= 2;
+		getbits(isrc, 2 , &i ,&l);
+	    } else if ((val & 0xfc00) == 0xf800) {	/* 64 <= len < 128 */
+		len = 0x0040 | ((val >> 4) & 0x003f);
+		bits -= 4;
+		getbits(isrc, 4 , &i ,&l);
+	    } else if ((val & 0xfe00) == 0xfc00) {	/* 128 <= len < 256 */
+		len = 0x0080 | ((val >> 2) & 0x007f);
+		bits -= 6;
+		getbits(isrc, 6 , &i ,&l);
+	    } else if ((val & 0xff00) == 0xfe00) {	/* 256 <= len < 512 */
+		len = 0x0100 | (val & 0x00ff);
+		bits -= 8;
+		i++;
+	    } else {
+		bits -= 8;
+		val = (val << 8) | getbyte(isrc, ++i, l);
+		if ((val & 0xff8000) == 0xff0000) {	/* 512 <= len < 1024 */
+		    len = 0x000200 | ((val >> 6) & 0x0001ff);
+		    bits -= 2;
+		    getbits(isrc, 2 , &i ,&l);
+		} else if ((val & 0xffc000) == 0xff8000) {/* 1024 <= len < 2048 */
+		    len = 0x000400 | ((val >> 4) & 0x0003ff);
+		    bits -= 4;
+		    getbits(isrc, 4 , &i ,&l);
+		} else if ((val & 0xffe000) == 0xffc000) {/* 2048 <= len < 4096 */
+		    len = 0x000800 | ((val >> 2) & 0x0007ff);
+		    bits -= 6;
+		    getbits(isrc, 6 , &i ,&l);
+		} else if ((val & 0xfff000) == 0xffe000) {/* 4096 <= len < 8192 */
+		    len = 0x001000 | (val & 0x000fff);
+		    bits -= 8;
+		    i++;
+		} else {				/* NOTREACHED */
+		    rtn &= ~MPPC_OK;
+		    return (rtn);
+		}
+	    }
+	}
+
+	s = state->hist + state->histptr;
+	state->histptr += len;
+	olen += len;
+	if (state->histptr < 2*MPPE_HIST_LEN) {
+	    /* Copy uncompressed bytes to the history. */
+
+	    /*
+	     * In some cases len may be greater than off. It means that memory
+	     * areas pointed by s and s-off overlap. To decode that strange case
+	     * data should be copied exactly by address increasing to make
+	     * some data repeated.
+	     */
+	    lamecopy(s, s - off, len);
+	} else {
+	    /* Buffer overflow; drop packet. */
+	    rtn &= ~MPPC_OK;
+	    return (rtn);
+	}
+    }
+
+    /* Do PFC decompression. */
+    len = olen;
+    if ((hist[0] & 0x01) != 0) {
+	(*dst)[0] = 0;
+	(*dst)++;
+	len++;
+    }
+
+    if (len <= *dstCnt) {
+	/* Copy uncompressed packet to the output buffer. */
+	memcpy(*dst, hist, olen);
+    } else {
+	/* Buffer overflow; drop packet. */
+	rtn |= MPPC_DEST_EXHAUSTED;
+    }
+
+    *src += *srcCnt;
+    *srcCnt = 0;
+    *dst += len;
+    *dstCnt -= len;
+
+    return (rtn);
+}