pred.c revision 6059 
1/*
2 *	    Written by Toshiharu OHNO (tony-o@iij.ad.jp)
3 *
4 *   Copyright (C) 1993, Internet Initiative Japan, Inc. All rights reserverd.
5 *
6 * Redistribution and use in source and binary forms are permitted
7 * provided that the above copyright notice and this paragraph are
8 * duplicated in all such forms and that any documentation,
9 * advertising materials, and other materials related to such
10 * distribution and use acknowledge that the software was developed
11 * by the Internet Initiative Japan.  The name of the
12 * IIJ may not be used to endorse or promote products derived
13 * from this software without specific prior written permission.
14 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
16 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
17 *
18 * $Id:$
19 *
20 *	TODO:
21 */
22
23#include "fsm.h"
24#include "hdlc.h"
25#include "lcpproto.h"
26#include "ccp.h"
27
28/*
29 * pred.c -- Test program for Dave Rand's rendition of the
30 * predictor algorithm
31 * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson)
32 * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de>
33 * Original  : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
34 */
35
36/* The following hash code is the heart of the algorithm:
37 * It builds a sliding hash sum of the previous 3-and-a-bit characters
38 * which will be used to index the guess table.
39 * A better hash function would result in additional compression,
40 * at the expense of time.
41 */
42#define IHASH(x) iHash = (iHash << 4) ^ (x)
43#define OHASH(x) oHash = (oHash << 4) ^ (x)
44
45static unsigned short int iHash, oHash;
46static unsigned char InputGuessTable[65536];
47static unsigned char OutputGuessTable[65536];
48
49static int
50compress(source, dest, len)
51unsigned char *source, *dest;
52int len;
53{
54    int i, bitmask;
55    unsigned char *flagdest, flags, *orgdest;
56
57    orgdest = dest;
58    while (len) {
59        flagdest = dest++; flags = 0;   /* All guess wrong initially */
60        for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
61            if (OutputGuessTable[oHash] == *source) {
62                flags |= bitmask;       /* Guess was right - don't output */
63            } else {
64                OutputGuessTable[oHash] = *source;
65                *dest++ = *source;      /* Guess wrong, output char */
66            }
67            OHASH(*source++);len--;
68        }
69        *flagdest = flags;
70    }
71    return(dest - orgdest);
72}
73
74static void
75SyncTable(source, dest, len)
76unsigned char *source, *dest;
77int len;
78{
79    int i;
80
81    while (len--) {
82        if (InputGuessTable[iHash] != *source) {
83            InputGuessTable[iHash] = *source;
84        }
85        IHASH(*dest++ = *source++);
86    }
87}
88
89static int
90decompress(source, dest, len)
91unsigned char *source, *dest;
92int len;
93{
94    int i, bitmask;
95    unsigned char flags, *orgdest;
96
97    orgdest = dest;
98    while (len) {
99        flags = *source++;
100        len--;
101        for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
102            if (flags & bitmask) {
103                *dest = InputGuessTable[iHash];       /* Guess correct */
104            } else {
105                if (!len)
106                    break;      /* we seem to be really done -- cabo */
107                InputGuessTable[iHash] = *source;     /* Guess wrong */
108                *dest = *source++;              /* Read from source */
109                len--;
110            }
111            IHASH(*dest++);
112        }
113    }
114    return(dest - orgdest);
115}
116
117#define SIZ1 2048
118
119void
120Pred1Init(direction)
121int direction;
122{
123  if (direction & 1) {	/* Input part */
124    iHash = 0;
125    bzero(InputGuessTable, sizeof(InputGuessTable));
126  }
127  if (direction & 2) { /* Output part */
128    oHash = 0;
129    bzero(OutputGuessTable, sizeof(OutputGuessTable));
130  }
131}
132
133void
134Pred1Output(pri, proto, bp)
135int pri;
136u_short proto;
137struct mbuf *bp;
138{
139  struct mbuf *mwp;
140  u_char *cp, *wp, *hp;
141  int orglen, len;
142  u_char bufp[SIZ1];
143  u_short fcs;
144
145  orglen = plength(bp) + 2;	/* add count of proto */
146  mwp = mballoc((orglen+2)/8*9+12, MB_HDLCOUT);
147  hp = wp = MBUF_CTOP(mwp);
148  cp = bufp;
149  *wp++ = *cp++ = orglen >> 8;
150  *wp++ = *cp++ = orglen & 0377;
151  *cp++ = proto >> 8;
152  *cp++ = proto & 0377;
153  mbread(bp, cp, orglen-2);
154  fcs = HdlcFcs(INITFCS, bufp, 2+orglen);
155  fcs = ~fcs;
156
157  len = compress(bufp + 2, wp, orglen);
158#ifdef DEBUG
159  logprintf("orglen (%d) --> len (%d)\n", orglen, len);
160#endif
161  CcpInfo.orgout += orglen;
162  if (len < orglen) {
163    *hp |= 0x80;
164    wp += len;
165    CcpInfo.compout += len;
166  } else {
167    bcopy(bufp+2, wp, orglen);
168    wp += orglen;
169    CcpInfo.compout += orglen;
170  }
171
172  *wp++ = fcs & 0377;
173  *wp++ = fcs >> 8;
174  mwp->cnt = wp - MBUF_CTOP(mwp);
175  HdlcOutput(pri, PROTO_COMPD, mwp);
176}
177
178void
179Pred1Input(bp)
180struct mbuf *bp;
181{
182  u_char *cp, *pp;
183  int len, olen, len1;
184  struct mbuf *wp;
185  u_char *bufp;
186  u_short fcs, proto;
187
188  wp = mballoc(SIZ1, MB_IPIN);
189  cp = MBUF_CTOP(bp);
190  olen = plength(bp);
191  pp = bufp = MBUF_CTOP(wp);
192  *pp++ = *cp & 0177;
193  len = *cp++ << 8;
194  *pp++ = *cp;
195  len += *cp++;
196  CcpInfo.orgin += len & 0x7fff;
197  if (len & 0x8000) {
198    len1 = decompress(cp, pp, olen - 4);
199    CcpInfo.compin += olen;
200    len &= 0x7fff;
201    if (len != len1) {	/* Error is detected. Send reset request */
202      CcpSendResetReq(&CcpFsm);
203      pfree(bp);
204      return;
205    }
206    cp += olen - 4;
207    pp += len1;
208  } else {
209    CcpInfo.compin += len;
210    SyncTable(cp, pp, len);
211    cp += len;
212    pp += len;
213  }
214  *pp++ = *cp++;	/* CRC */
215  *pp++ = *cp++;
216  fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp);
217#ifdef DEBUG
218  logprintf("fcs = %04x (%s), len = %x, olen = %x\n",
219       fcs, (fcs == GOODFCS)? "good" : "bad", len, olen);
220#endif
221  if (fcs == GOODFCS) {
222    wp->offset += 2;		/* skip length */
223    wp->cnt -= 4;		/* skip length & CRC */
224    pp = MBUF_CTOP(wp);
225    proto = *pp++;
226    if (proto & 1) {
227      wp->offset++;
228      wp->cnt--;
229    } else {
230      wp->offset += 2;
231      wp->cnt -= 2;
232      proto = (proto << 8) | *pp++;
233    }
234    DecodePacket(proto, wp);
235  }
236  pfree(bp);
237}
238