/*- * 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. *//* * MPPC decompression library. * Version 1.0 * * Please note that Hi/Fn (http://www.hifn.com) holds US patents on some  * implementation critical aspects of MPPC so you should check if those  * patents are valid in your country in order to avoid legal problems. */#include <sys/param.h>#include <sys/systm.h>#include <net/mppc.h>#define MPPE_HIST_LEN          8192struct MPPC_decomp_state {    uint8_t	hist[2*MPPE_HIST_LEN];    uint16_t	histptr;};static uint32_t __inlinegetbits(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 __inlinegetbyte(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 __inlinelamecopy(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 {		/* this shouldn't happen */		    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 {				/* this shouldn't happen */		    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;}