/*
* ccp_pred1.c
*
* Copyright (c) 1997-1999 Whistle Communications, Inc.
* All rights reserved.
*/
/*
* pred1.c
*
* Test program for Dave Rand's rendition of the predictor algorithm
*
* Updated by: archie@freebsd.org (Archie Cobbs)
* Updated by: iand@labtam.labtam.oz.au (Ian Donaldson)
* Updated by: Carsten Bormann <cabo@cs.tu-berlin.de>
* Original : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
*/
#include "ppp.h"
#include "ccp.h"
/*
* DEFINITIONS
*/
#define PRED1_COMP_BUF_SIZE 2048
#define PRED1_DECOMP_BUF_SIZE 1600
#define PRED1_MAX_BLOWUP(n) ((n) * 9 / 8 + 24)
/*
* The following hash code is the heart of the algorithm:
* It builds a sliding hash sum of the previous 3-and-a-bit characters
* which will be used to index the guess table.
* A better hash function would result in additional compression,
* at the expense of time.
*/
#define IHASH(x) p->iHash = (p->iHash << 4) ^ (x)
#define OHASH(x) p->oHash = (p->oHash << 4) ^ (x)
/*
* INTERNAL FUNCTIONS
*/
static void Pred1Init(int direction);
static void Pred1Cleanup(int direction);
static Mbuf Pred1Compress(int proto, Mbuf bp);
static Mbuf Pred1Decompress(Mbuf bp, int *proto);
static u_char *Pred1BuildConfigReq(CompInfo comp, u_char *cp);
static Mbuf Pred1RecvResetReq(int id, Mbuf bp);
static Mbuf Pred1SendResetReq(void);
static int Compress(u_char *source, u_char *dest, int len);
static int Decompress(u_char *source, u_char *dest, int slen, int dlen);
static void SyncTable(u_char *source, u_char *dest, int len);
/*
* GLOBAL VARIABLES
*/
const struct compinfo gCompPred1Info =
{
TY_PRED1,
Pred1Init,
Pred1Cleanup,
Pred1Compress,
Pred1Decompress,
NULL,
Pred1BuildConfigReq,
NULL,
Pred1RecvResetReq,
Pred1SendResetReq,
NULL,
};
/*
* Pred1Init()
*/
void
Pred1Init(int directions)
{
Pred1Info p = &bund->ccp.pred1;
if (directions & CCP_DIR_INPUT)
{
p->iHash = 0;
if (p->InputGuessTable == NULL)
p->InputGuessTable = Malloc(MB_COMP, PRED1_TABLE_SIZE);
memset(p->InputGuessTable, 0, PRED1_TABLE_SIZE);
}
if (directions & CCP_DIR_OUTPUT)
{
p->oHash = 0;
if (p->OutputGuessTable == NULL)
p->OutputGuessTable = Malloc(MB_COMP, PRED1_TABLE_SIZE);
memset(p->OutputGuessTable, 0, PRED1_TABLE_SIZE);
}
}
/*
* Pred1Cleanup()
*/
void
Pred1Cleanup(int direction)
{
Pred1Info p = &bund->ccp.pred1;
if (direction & CCP_DIR_INPUT)
{
assert(p->InputGuessTable);
Freee(p->InputGuessTable);
p->InputGuessTable = NULL;
}
if (direction & CCP_DIR_OUTPUT)
{
assert(p->OutputGuessTable);
Freee(p->OutputGuessTable);
p->OutputGuessTable = NULL;
}
}
/*
* Pred1Compress()
*
* Compress a packet and return a compressed version.
* The original is untouched.
*/
Mbuf
Pred1Compress(int proto, Mbuf uncomp)
{
Mbuf comp;
u_char *cp, *wp, *hp;
int orglen, len;
u_char bufp[PRED1_COMP_BUF_SIZE];
u_short fcs;
orglen = plength(uncomp) + 2; /* add count of proto */
comp = mballoc(MB_FRAME_OUT, PRED1_MAX_BLOWUP(orglen + 2));
comp->prio = uncomp->prio;
hp = wp = MBDATA(comp);
/* Stick in original length and protocol */
cp = bufp;
*wp++ = *cp++ = orglen >> 8;
*wp++ = *cp++ = orglen & 0377;
*cp++ = proto >> 8;
*cp++ = proto & 0xff;
/* Copy data into buffer and compute FCS */
mbcopy(uncomp, cp, orglen - 2);
fcs = Crc16(INITFCS, bufp, orglen + 2);
fcs = ~fcs;
/* Compress data */
len = Compress(bufp + 2, wp, orglen);
#ifdef DEBUG
Log(LG_CCP2, ("orglen (%d) --> len (%d)", orglen, len));
#endif
/* What happened? */
if (len < orglen)
{
*hp |= 0x80;
wp += len;
}
else
{
memcpy(wp, bufp + 2, orglen);
wp += orglen;
}
/* Add FCS */
*wp++ = fcs & 0377;
*wp++ = fcs >> 8;
comp->cnt = wp - MBDATA(comp);
/* Done */
return(comp);
}
/*
* Pred1Decompress()
*
* Decompress packet, set *protop accordingly. Returns NULL if
* packet failed to decompress. In any case, it doesn't alter "comp".
*/
Mbuf
Pred1Decompress(Mbuf comp, int *protop)
{
u_char *cp, *pp;
int len, olen, len1;
Mbuf uncomp;
u_char *bufp;
u_short fcs, proto;
/* "comp" is compressed data */
olen = plength(comp);
cp = MBDATA(comp);
/* "uncomp" is uncompressed data */
uncomp = mballoc(MB_IPIN, PRED1_DECOMP_BUF_SIZE);
uncomp->prio = comp->prio;
pp = bufp = MBDATA(uncomp);
/* Get initial length value */
*pp++ = *cp & 0x7F;
len = *cp++ << 8;
*pp++ = *cp;
len += *cp++;
/* Is data compressed or not really? */
if (len & 0x8000)
{
len &= 0x7fff;
len1 = Decompress(cp, pp, olen - 4, PRED1_DECOMP_BUF_SIZE);
if (len != len1) /* Error is detected. Send reset request */
{
PFREE(uncomp);
return(NULL);
}
cp += olen - 4;
pp += len1;
}
else
{
SyncTable(cp, pp, len);
cp += len;
pp += len;
}
/* Copy CRC value */
*pp++ = *cp++; /* CRC */
*pp++ = *cp++;
/* Check CRC */
fcs = Crc16(INITFCS, bufp, (uncomp->cnt = pp - bufp));
#ifdef DEBUG
if (fcs != GOODFCS)
Log(LG_CCP2, ("fcs = %04x (%s), len = %x, olen = %x",
fcs, (fcs == GOODFCS)? "good" : "bad", len, olen));
#endif
if (fcs != GOODFCS)
{
PFREE(uncomp);
return(NULL);
}
/* Get protocol */
uncomp->offset += 2; /* skip length */
uncomp->cnt -= 4; /* skip length & CRC */
pp = MBDATA(uncomp);
proto = *pp++;
if (proto & 1)
{
uncomp->offset++;
uncomp->cnt--;
}
else
{
uncomp->offset += 2;
uncomp->cnt -= 2;
proto = (proto << 8) | *pp++;
}
/* Return decompressed packet */
*protop = proto;
return(uncomp);
}
/*
* Pred1RecvResetReq()
*/
static Mbuf
Pred1RecvResetReq(int id, Mbuf bp)
{
Pred1Init(CCP_DIR_OUTPUT);
return(NULL);
}
/*
* Pred1SendResetReq()
*/
static Mbuf
Pred1SendResetReq(void)
{
Pred1Init(CCP_DIR_INPUT);
return(NULL);
}
/*
* Pred1BuildConfigReq()
*/
static u_char *
Pred1BuildConfigReq(CompInfo comp, u_char *cp)
{
return(FsmConfValue(cp, comp->proto, 0, NULL));
}
/*
* Compress()
*/
static int
Compress(u_char *source, u_char *dest, int len)
{
Pred1Info p = &bund->ccp.pred1;
int i, bitmask;
u_char flags;
u_char *flagdest, *orgdest;
orgdest = dest;
while (len)
{
flagdest = dest++; flags = 0; /* All guess wrong initially */
for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
if (p->OutputGuessTable[p->oHash] == *source)
flags |= bitmask; /* Guess was right - don't output */
else
{
p->OutputGuessTable[p->oHash] = *source;
*dest++ = *source; /* Guess wrong, output char */
}
OHASH(*source++);
len--;
}
*flagdest = flags;
}
return(dest - orgdest);
}
/*
* Decompress()
*
* Returns decompressed size, or -1 if we ran out of space
*/
static int
Decompress(u_char *source, u_char *dest, int slen, int dlen)
{
Pred1Info p = &bund->ccp.pred1;
int i, bitmask;
u_char flags, *orgdest;
orgdest = dest;
while (slen)
{
flags = *source++;
slen--;
for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1)
{
if (dlen <= 0)
return(-1);
if (flags & bitmask)
*dest = p->InputGuessTable[p->iHash]; /* Guess correct */
else
{
if (!slen)
break; /* we seem to be really done -- cabo */
p->InputGuessTable[p->iHash] = *source; /* Guess wrong */
*dest = *source++; /* Read from source */
slen--;
}
IHASH(*dest++);
dlen--;
}
}
return(dest - orgdest);
}
/*
* SyncTable()
*/
static void
SyncTable(u_char *source, u_char *dest, int len)
{
Pred1Info p = &bund->ccp.pred1;
while (len--)
{
if (p->InputGuessTable[p->iHash] != *source)
p->InputGuessTable[p->iHash] = *source;
IHASH(*dest++ = *source++);
}
}
syntax highlighted by Code2HTML, v. 0.9.1