bsd-comp.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* Copyright (c) 2000 by Sun Microsystems, Inc.
* All rights reserved.
*
* Because this code is derived from the 4.3BSD compress source:
*
* Copyright (c) 1985, 1986 The Regents of the University of California.
* All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* James A. Woods, derived from original work by Spencer Thomas
* and Joseph Orost.
*
* 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, 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
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* This version is for use with STREAMS in Solaris 2
*
* $Id: bsd-comp.c,v 1.20 1996/08/28 06:31:57 paulus Exp $
*/
#include <sys/byteorder.h>
#include <net/ppp_defs.h>
/* Defined for platform-neutral include file */
#include <net/ppp-comp.h>
#include "s_common.h"
#ifndef _BIG_ENDIAN
#define BSD_LITTLE_ENDIAN
#endif
#if DO_BSD_COMPRESS
/*
* PPP "BSD compress" compression
*
* The differences between this compression and the classic BSD LZW
* source are obvious from the requirement that the classic code worked
* with files while this handles arbitrarily long streams that
* are broken into packets. They are:
*
* When the code size expands, a block of junk is not emitted by
* the compressor and not expected by the decompressor.
*
* New codes are not necessarily assigned every time an old
* code is output by the compressor. This is because a packet
* end forces a code to be emitted, but does not imply that a
* new sequence has been seen.
*
* The compression ratio is checked at the first end of a packet
* after the appropriate gap. Besides simplifying and speeding
* things up, this makes it more likely that the transmitter
* and receiver will agree when the dictionary is cleared when
* compression is not going well.
*/
/*
* A dictionary for doing BSD compress.
*/
struct bsd_db {
int totlen; /* length of this structure */
struct bsd_dict {
union { /* hash value */
struct {
#ifdef BSD_LITTLE_ENDIAN
#else
#endif
} hs;
} f;
} dict[1];
};
#define BSD_INIT_BITS BSD_MIN_BITS
/* db->flags values */
#define DS_DEBUG 0x01
#define DS_TESTIN 0x02
#define DS_TESTOUT 0x04
/*
* Procedures exported to ppp_comp.c.
*/
struct compressor ppp_bsd_compress = {
CI_BSD_COMPRESS, /* compress_proto */
bsd_comp_alloc, /* comp_alloc */
bsd_free, /* comp_free */
bsd_comp_init, /* comp_init */
bsd_reset, /* comp_reset */
bsd_compress, /* compress */
bsd_comp_stats, /* comp_stat */
bsd_decomp_alloc, /* decomp_alloc */
bsd_free, /* decomp_free */
bsd_decomp_init, /* decomp_init */
bsd_reset, /* decomp_reset */
bsd_decompress, /* decompress */
bsd_incomp, /* incomp */
bsd_comp_stats, /* decomp_stat */
bsd_set_effort, /* set_effort */
};
/*
* the next two codes should not be changed lightly, as they must not
* lie within the contiguous general code space.
*/
#define LAST 255
#define RATIO_SCALE_LOG 8
#define DECOMP_CHUNK 256
/*
* bsd_clear()
*
* clear the dictionary
*/
static void
{
db->clear_count++;
}
/*
* bsd_check()
*
* If the dictionary is full, then see if it is time to reset it.
*
* Compute the compression ratio using fixed-point arithmetic
* with 8 fractional bits.
*
* Since we have an infinite stream instead of a single file,
* watch only the local compression ratio.
*
* Since both peers must reset the dictionary at the same time even in
* the absence of CLEAR codes (while packets are incompressible), they
* must compute the same ratio.
*/
static int /* 1=output CLEAR */
{
/*
* age the ratio by limiting the size of the counts
*/
}
/*
* Reset the dictionary only if the ratio is worse,
* or if it looks as if it has been poisoned
* by incompressible data.
*
* This does not overflow, because
* db->in_count <= RATIO_MAX.
*/
}
return (1);
}
}
}
return (0);
}
/*
* bsd_comp_stats()
*
* Return statistics.
*/
static void
{
} else {
out >>= 8;
}
if (out != 0) {
}
}
/*
* bsd_reset()
*
* Reset state, as on a CCP ResetReq.
*/
static void
{
db->clear_count = 0;
}
}
/*
* bsd_alloc()
*
* Allocate space for a (de) compressor.
*/
static void *
{
int bits;
if (opt_len != 3 ||
options[0] != CI_BSD_COMPRESS ||
return (NULL);
}
switch (bits) {
case 9: /* needs 82152 for both directions */
case 10: /* needs 84144 */
case 11: /* needs 88240 */
case 12: /* needs 96432 */
hsize = 5003;
hshift = 4;
break;
case 13: /* needs 176784 */
hsize = 9001;
hshift = 5;
break;
case 14: /* needs 353744 */
hsize = 18013;
hshift = 6;
break;
case 15: /* needs 691440 */
hsize = 35023;
hshift = 7;
break;
/* XXX: this falls thru - it was originally commented */
case 16: /* needs 1366160--far too much, */
/* hsize = 69001; */ /* and 69001 is too big for cptr */
/* hshift = 8; */ /* in struct bsd_db */
/* break; */
default:
return (NULL);
}
if (decomp)
if (!db) {
return (NULL);
}
if (!decomp) {
} else {
}
return ((void *)db);
}
/*
* bsd_free()
*/
static void
{
/* XXX feeble attempt to catch bad references. */
}
}
/*
* bsd_comp_alloc()
*/
static void *
{
}
/*
* bsd_decomp_alloc()
*/
static void *
{
}
/*
* bsd_init()
*
* Initialize the database.
*/
static int
{
int i;
options[0] != CI_BSD_COMPRESS ||
return (0);
}
if (decomp) {
i = LAST + 1;
while (i != 0) {
}
}
while (i != 0) {
}
if (debug) {
}
return (1);
}
/*
* bsd_comp_init()
*/
static int
int debug)
{
}
/*
* bsd_decomp_init()
*/
static int
{
}
/*
* bsd_compress()
*
* compress a packet
* One change from the BSD compress command is that when the
* code size expands, we do not output a bunch of padding.
*
* N.B. at present, we ignore the hdrlen specified in the comp_init call.
*/
static int /* new slen */
{
uchar_t c;
int hval;
int disp;
int ent;
int olen;
mblk_t *m;
#else
#endif
#define PUTBYTE(v) { \
if (wptr) { \
*wptr++ = (v); \
m = m->b_cont; \
if (m) { \
} else { \
} \
} \
} \
++olen; \
}
do { \
accm <<= 8; \
bitno += 8; \
} while (bitno <= 24); \
}
#define ADJRPTR() { \
break; \
} \
} \
} \
}
#define GETBYTE(v) { \
(v) = *rptr++; \
} \
}
return (-1);
/*
* First get the protocol and check that we're
* interested in this packet.
*/
/* We CANNOT do a pullup here; it's not our buffer to toy with. */
ADJRPTR();
ADJRPTR();
ADJRPTR();
ADJRPTR();
/*
* Per RFC 1977, the protocol field must be compressed using a
* PFC-like procedure. Also, all protocols between 0000-3FFF
* except the two compression protocols must be LZ compressed.
*/
if (ent == 0) {
return (0);
} else {
if (ent > 0x3F)
return (0);
ilen++;
}
/*
* Don't generate compressed packets that are larger than the
* source (uncompressed) packet.
*/
}
if (maxolen < 6)
maxolen = 6;
/*
* Allocate enough message blocks to give maxolen total space
*/
*mnp = m;
if (m == NULL) {
return (0);
/* We allocated some; hope for the best. */
break;
}
}
m = mret;
olen = 0;
/*
* Copy the PPP header over, changing the protocol,
* and install the 2-byte sequence number
*/
#ifdef DEBUG
/*
* If testing output, just garbling the sequence here does the
* trick.
*/
#endif
for (;;) {
ADJRPTR();
break;
GETBYTE(c);
/*
* Validate and then check the entry
*/
goto nomatch;
}
/*
* found (prefix,suffix)
*/
continue;
}
/*
* continue probing until a match or invalid entry
*/
do {
"bsd_comp%d: internal "
"error\n",
}
/* Caller will free it all */
return (-1);
}
}
goto nomatch;
}
/*
* finally found (prefix,suffix)
*/
continue;
/*
* output the prefix
*/
/*
* code -> hashtable
*/
/*
* expand code size if needed
*/
}
/*
* Invalidate old hash table entry using
* this code, and then take it over.
*/
}
}
ent = c;
}
/*
* output the last code
*/
}
/*
* Pad dribble bits of last code with ones.
* Do not emit a completely useless byte of ones.
*/
if (bitno != 32) {
}
/*
* Increase code size if we would have without the packet
* boundary and as the decompressor will.
*/
}
++db->uncomp_count;
/*
* throw away the compressed stuff if it is longer
* than uncompressed
*/
++db->incomp_count;
} else {
if (m->b_cont) {
}
++db->comp_count;
}
}
/*
* bsd_incomp()
*
* Update the "BSD Compress" dictionary on the receiver for
* incompressible data by pretending to compress the incoming data.
*/
static int
{
uchar_t c;
long hval;
long disp;
int slen;
int ilen;
return (-1);
ADJRPTR();
ADJRPTR();
ADJRPTR();
ADJRPTR();
/*
* Per RFC 1977, the protocol field must be compressed using a
* PFC-like procedure. Also, all protocols between 0000-3FFF
* except the two compression protocols must be LZ compressed.
*/
if (ent == 0) {
return (0);
} else {
if (ent > 0x3F)
return (0);
ilen++;
}
for (;;) {
if (slen <= 0) {
if (!mp) {
break;
}
continue; /* skip zero-length buffers */
}
do {
c = *rptr++;
/*
* validate and then check the entry
*/
goto nomatch;
}
continue; /* found (prefix,suffix) */
}
/*
* continue probing until a match or invalid entry
*/
do {
"bsd_incomp%d: "
"internal error\n",
}
return (-1);
}
}
goto nomatch;
}
continue; /* finally found (prefix,suffix) */
nomatch: /* output (count) the prefix */
/*
* code -> hashtable
*/
/*
* expand code size if needed
*/
}
/*
* Invalidate previous hash table entry
* assigned this code, and then take it over.
*/
}
}
ent = c;
} while (--slen != 0);
}
++db->incomp_count;
++db->uncomp_count;
/*
* Increase code size if we would have without the packet
* boundary and as the decompressor will.
*/
}
return (0);
}
/*
* bsd_decompress()
*
* Decompress "BSD Compress"
*
* Because of patent problems, we return DECOMP_ERROR for errors
* found by inspecting the input data and for system problems, but
* DECOMP_FATALERROR for any errors which could possibly be said to
* be being detected "after" decompression. For DECOMP_ERROR,
* we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
* infringing a patent of Motorola's if we do, so we take CCP down
* instead.
*
* Given that the frame has the correct sequence number and a good FCS,
* errors such as invalid codes in the input most likely indicate a
* bug, so we return DECOMP_FATALERROR for them in order to turn off
* compression, even though they are detected by inspecting the input.
*/
static int
{
int explen;
int seq;
uchar_t *p;
int ilen;
int dlen;
int codelen;
int extra;
int decode_proto;
int blockctr;
int outlen;
#else
#endif
/* Note: spppcomp already did a pullup to fix the first buffer. */
ilen = 0;
/*
* Note that we free as we go. If we fail to decompress,
* there's nothing good that the caller can do.
*/
#define ADJRPTR() \
break; \
} \
}
/*
* and then get the sequence number.
*/
rptr += 4;
ADJRPTR();
ADJRPTR();
}
return (DECOMP_ERROR);
}
#ifdef DEBUG
/*
* If testing input, just pretending the sequence is bad here
* does the trick.
*/
seq ^= 0x55;
#endif
/*
* Check the sequence number and give up if it is not what we expect.
*/
}
return (DECOMP_ERROR);
}
/*
* Allocate one message block to start with.
*/
"bsd_decomp%d: can't allocate first buffer\n",
}
return (DECOMP_ERROR);
}
/*
* Avoid an error that might cause us to allocate all available memory.
* Enforce a maximum number of blocks to allocate for message. We add
* a fudge factor of 5 extra blocks, in order to avoid unnecessary
* DECOMP_ERROR when the code size is small (9).
*/
/*
* Insert PPP header. This shouldn't be needed!
*/
*wptr++ = 0;
outlen = 0;
decode_proto = 1;
for (;;) {
ADJRPTR();
break;
/*
* Accumulate bytes until we have a complete code.
* Then get the next code, relying on the 32-bit,
* unsigned accm to mask the result.
*/
bitno -= 8;
continue;
}
/*
* The dictionary must only be cleared at
* the end of a packet. But there could be an
* empty message block at the end.
*/
ADJRPTR();
"bsd_decomp%d: bad CLEAR\n",
}
return (DECOMP_FATALERROR);
}
/* Have to keep cleared state variables! */
ilen = 0;
break;
}
/*
* Special case for KwKwK string
*/
/* probably a bug if we get here */
"bsd_decomp%d: bad code 0x%x "
oldcode);
}
return (DECOMP_FATALERROR);
}
extra = 1;
} else {
extra = 0;
}
/*
* Decode this code and install it in the decompressed buffer
*/
if (explen < 0) {
/*
* Allocate another message block
*/
if (dlen < DECOMP_CHUNK) {
dlen = DECOMP_CHUNK;
}
if ((--blockctr < 0) ||
"bsd_decomp%d: %s output "
"buffers; outlen %d+%d\n",
(blockctr < 0 ? "too many" :
"can't allocate"),
}
return (DECOMP_ERROR);
}
}
}
*--p = finchar;
if (decode_proto) {
decode_proto = 0;
/* Wow, is *this* ugly! */
if (!(finchar & 1)) {
if (p == prepos+1) {
wptr--;
explen++;
} else {
/* This is safe, but doesn't look it */
*prepos = *p++;
}
}
}
if (extra) { /* the KwKwK case again */
}
/*
* If not first code in a packet, and
* if not out of code space, then allocate a new code.
*
* Keep the hash table correct so it can be used
* with uncompressed packets.
*/
int hval;
int disp;
/*
* look for a free hash table entry
*/
do {
DS_DEBUG) {
}
return
}
}
}
/*
* Invalidate previous hash table entry
* assigned this code, and then take it over
*/
}
/*
* Expand code size if needed
*/
}
}
}
/*
* Keep the checkpoint right so that incompressible packets
* clear the dictionary at the right times.
*/
"bsd_decomp%d: peer should have cleared dictionary\n",
}
++db->comp_count;
++db->uncomp_count;
return (DECOMP_OK);
}
/* ARGSUSED */
static int
{
#ifdef DEBUG
/* corrupt received data. */
}
if (effortlevel != 2112)
return (0);
}
/* corrupt transmitted data. */
}
return (0);
}
#endif
return (0);
}
#endif /* DO_BSD_COMPRESS */