mppc.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

#include <u.h>
#include <libc.h>
#include <libsec.h>
#include <ip.h>
#include <auth.h>
#include "ppp.h"

enum {
	HistorySize=	8*1024,
	Cminmatch	= 3,		/* sintest match possible */
	Chshift		= 4,		/* nice compromise between space & time */
	Cnhash		= 1<<(Chshift*Cminmatch),
	HMASK		= Cnhash-1,
};

typedef struct Carena Carena;
struct Carena
{
	uchar	*pos;			/* current place, also amount of history filled */
	uchar	buf[HistorySize];
};

typedef struct Cstate Cstate;
struct Cstate
{
	QLock;
	int	count;
	int	reset;		/* compressor has been reset */
	int	front;		/* move to begining of history */
	ulong	sreg;		/* output shift reg */
	int	bits;		/* number of bits in sreg */
	Block	*b; 		/* output block */

	/*
	 * state for hashing compressor
	 */
	Carena	arenas[2];
	Carena	*hist;
	Carena	*ohist;
	ulong	hash[Cnhash];
	int	h;
	ulong	me;
	ulong	split;

	int	encrypt;
	uchar	startkey[16];
	uchar	key[16];
	RC4state rc4key;
};

typedef struct Uncstate Uncstate;
struct Uncstate
{
	int	count;	 	/* packet count - detects missing packets */
	int	resetid;	/* id of reset requests */
	uchar	his[HistorySize];
	int	indx;		/* current indx in history */
	int	size;		/* current history size */
	uchar	startkey[16];
	uchar	key[16];
	RC4state rc4key;
};

/* packet flags */
enum {
	Preset=		(1<<15),	/* reset history */
	Pfront=		(1<<14),	/* move packet to front of history */
	Pcompress=	(1<<13),	/* packet is compressed */
	Pencrypt=	(1<<12),	/* packet is encrypted */
};

enum {
	Lit7,		/* seven bit literal */
	Lit8,		/* eight bit literal */
	Off6,		/* six bit offset */
	Off8,		/* eight bit offset */
	Off13,		/* thirteen bit offset */
};

/* decode first four bits */
int decode[16] = {
	Lit7,	
	Lit7,
	Lit7,
	Lit7,
	Lit7,
	Lit7,
	Lit7,
	Lit7,
	Lit8,
	Lit8,	
	Lit8,
	Lit8,	
	Off13,
	Off13,
	Off8,
	Off6,
};
	

static	void		*compinit(PPP*);
static	Block*		comp(PPP*, ushort, Block*, int*);
static	void		comp2(Cstate*, uchar*, int);
static	Block		*compresetreq(void*, Block*);
static	void		compfini(void*);
static	void		complit(Cstate*, int);
static	void		compcopy(Cstate*, int, int);
static	void		compout(Cstate*, ulong, int);
static	void		compfront(Cstate*);
static	void		hashcheck(Cstate*);
static	void		compreset(Cstate*);
static	int		hashit(uchar*);


static	void		*uncinit(PPP*);
static	Block*		uncomp(PPP*, Block*, int *protop, Block**);
static	Block		*uncomp2(Uncstate *s, Block*, ushort);
static	void		uncfini(void*);
static	void		uncresetack(void*, Block*);
static  int		ipcheck(uchar*, int);
static  void		hischeck(Uncstate*);

static	void		setkey(uchar *key, uchar *startkey);

Comptype cmppc = {
	compinit,
	comp,
	compresetreq,
	compfini
};

Uncomptype uncmppc = {
	uncinit,
	uncomp,
	uncresetack,
	uncfini
};

static void *
compinit(PPP *ppp)
{
	Cstate *cs;

	cs = mallocz(sizeof(Cstate), 1);
	cs->hist = &cs->arenas[0];
	cs->ohist = &cs->arenas[1];
	compreset(cs);
	/*
	 * make reset clear the hash table
	 */
	cs->me = ~0;
	compreset(cs);

	cs->reset = 0;

	if(ppp->sendencrypted) {
		cs->encrypt = 1;
		memmove(cs->startkey, ppp->key, 16);
		memmove(cs->key, ppp->key, 16);
		setkey(cs->key, cs->startkey);
		setupRC4state(&cs->rc4key, cs->key, 16);
	}

	return cs;
}

static void
compfini(void *as)
{
	Cstate *cs;

	cs = as;
	free(cs);
}


static Block*
comp(PPP *ppp, ushort proto, Block *b, int *protop)
{
	Cstate *s;
	int n, n2;
	ushort count;

	s = ppp->cstate;
	*protop = 0;

	qlock(s);

	/* put protocol into b */
	b->rptr -= 2;
	if(b->rptr < b->base)
		sysfatal("mppc: not enough header in block");
	b->rptr[0] = proto>>8;
	b->rptr[1] = proto;

	n = BLEN(b);
	s->bits = 0;
	s->b = allocb(n*9/8+20);
	s->b->wptr += 2;	/* leave room for mppc header */

	comp2(s, b->rptr, n);
		
	/* flush sreg */
	if(s->bits)
		*s->b->wptr++ = s->sreg<<(8-s->bits);
	if(s->b->wptr > s->b->lim)
		sysfatal("mppc: comp: output block overflowed");

	n2 = BLEN(s->b);

	if(n2 > n-2 && !s->encrypt) {
		/* expened and not excrypting so send as a regular packet */
//netlog("mppc: comp: expanded\n"); 
		compreset(s);
		freeb(s->b);
		b->rptr += 2;
		qunlock(s);
		*protop = proto;
		return b;
	}

	count = s->count++;
	s->count &= 0xfff;
	if(s->front)
		count |= Pfront;
	if(s->reset)
		count |= Preset;
	s->reset = 0;
	s->front = 0;

	if(n2 > n) {
//netlog("mppc: comp: expanded\n"); 
		freeb(s->b);
		/* make room for count */
		compreset(s);
		b->rptr -= 2;
	} else {
		freeb(b);
		b = s->b;
		count |= Pcompress;
	}
	s->b = nil;

	if(s->encrypt) {
		count |= Pencrypt;
		if((count&0xff) == 0xff) {
//netlog("mppc: comp: changing key\n"); 
			setkey(s->key, s->startkey);
			setupRC4state(&s->rc4key, s->key, 16);
			rc4(&s->rc4key, s->key, 16);
			setupRC4state(&s->rc4key, s->key, 16);
		} else if(count&Preset)
			setupRC4state(&s->rc4key, s->key, 16);
		rc4(&s->rc4key, b->rptr+2, BLEN(b)-2);
//netlog("mppc: encrypt %ux\n", count);
	}

	b->rptr[0] = count>>8;
	b->rptr[1] = count;
	
	qunlock(s);

	*protop = Pcdata;
	return b;
}

static Block *
compresetreq(void *as, Block *b)
{
	Cstate *cs;

	cs = as;
netlog("mppc: comp: reset request\n");
	qlock(cs);
	compreset(cs);
	qunlock(cs);

	freeb(b);

	return nil;
}

static void
comp2(Cstate *cs, uchar *p, int n)
{
	Carena *hist, *ohist;
	ulong *hash, me, split, you, last;
	uchar *s, *t, *et, *buf, *obuf, *pos, *opos;
	int i, h, m;

	/*
	 * check for wrap
	 */
	if(cs->me + n < cs->me)
		compreset(cs);

	if(cs->hist->pos + n > cs->hist->buf + HistorySize)
		compfront(cs);

	hist = cs->hist;
	ohist = cs->ohist;

	hash = cs->hash;
	me = cs->me;
	split = cs->split;

	memmove(hist->pos, p, n);
	p = hist->pos;
	hist->pos = pos = p + n;

	m = Cminmatch;
	if(m > n)
		m = n;
	h = cs->h;
	for(i = 0; i < m; i++) {
		h = (((h)<<Chshift) ^ p[i]) & HMASK;
		last = me + (i - (Cminmatch-1));
		if(last >= split && last != me)
			hash[h] = last;
	}

	buf = hist->buf - split;
	obuf = ohist->buf + HistorySize - split;
	opos = ohist->pos;
	while(p < pos) {
		you = hash[h];
		if(you < split) {
			if(me - you >= HistorySize)
				t = opos;
			else
				t = obuf + you;
			et = opos;
		} else {
			t = buf + you;
			et = pos;
		}
		m = pos - p;
		if(m < et - t)
			et = t + m;
		for(s = p; t < et; t++) {
			if(*s != *t)
				break;
			s++;
		}
		m = s - p;
		if(m < Cminmatch) {
			complit(cs, *p);
			s = p + 1;
		} else
			compcopy(cs, me - you, m);

		for(; p != s; p++) {
			if(p + Cminmatch <= pos) {
				hash[h] = me;
				if(p + Cminmatch < pos)
					h = (((h)<<Chshift) ^ p[Cminmatch]) & HMASK;
			}
			me++;
		}
	}

	cs->h = h;
	cs->me = me;
}

static void
compfront(Cstate *cs)
{
	Carena *th;

	cs->front = 1;

	th = cs->ohist;
	cs->ohist = cs->hist;
	cs->hist = th;
	cs->hist->pos = cs->hist->buf;
	cs->h = 0;
	cs->me = cs->split + HistorySize;
	cs->split = cs->me;
}

static void
compreset(Cstate *cs)
{
	ulong me;

	cs->reset = 1;

	me = cs->me;
	if(me + 2 * HistorySize < me){
		me = 0;
		memset(cs->hash, 0, sizeof(cs->hash));
	}
	cs->me = me + 2 * HistorySize;
	cs->split = cs->me;
	cs->hist->pos = cs->hist->buf;
	cs->ohist->pos = cs->ohist->buf;
}

static void
complit(Cstate *s, int c)
{
	if(c&0x80)
		compout(s, 0x100|(c&0x7f), 9);
	else
		compout(s, c, 8);
}

static void
compcopy(Cstate *s, int off, int len)
{
	int i;
	ulong mask;

	if(off<64)
		compout(s, 0x3c0|off, 10);
	else if(off<320)
		compout(s, 0xe00|(off-64), 12);
	else
		compout(s, 0xc000|(off-320), 16);
	if(len < 3)
		sysfatal("compcopy: bad len: %d", len);
	if(len == 3)
		compout(s, 0, 1);
	else {
		for(i=3; (1<<i) <= len; i++)
			;
		mask = (1<<(i-1))-1;
		compout(s, (((1<<(i-2))-1)<<i) | len&mask, (i-1)<<1);
	}
}

static void
compout(Cstate *s, ulong data, int bits)
{
	ulong sreg;

	sreg = s->sreg;
	sreg <<= bits;
	sreg |= data;
	bits += s->bits;
	while(bits >= 8) {
		*s->b->wptr++ = sreg>>(bits-8);
		bits -= 8;
	}
	s->sreg = sreg;
	s->bits = bits;
}

void
printkey(uchar *key)
{
	char buf[200], *p;
	int i;

	p = buf;
	for(i=0; i<16; i++)
		p += sprint(p, "%.2ux ", key[i]);
//netlog("key = %s\n", buf);
}

static	void *
uncinit(PPP *ppp)
{
	Uncstate *s;