2 * Copyright (c) 1997 Brian Somers <brian@Awfulhak.org>
3 * Ian Donaldson <iand@labtam.labtam.oz.au>
4 * Carsten Bormann <cabo@cs.tu-berlin.de>
5 * Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * $FreeBSD: src/usr.sbin/ppp/pred.c,v 1.29.2.3 2002/09/01 02:12:31 brian Exp $
30 * $DragonFly: src/usr.sbin/ppp/pred.c,v 1.3 2008/05/19 10:19:49 corecode Exp $
33 #include <sys/types.h>
34 #include <sys/select.h>
50 #include "throughput.h"
54 /* The following hash code is the heart of the algorithm:
55 * It builds a sliding hash sum of the previous 3-and-a-bit characters
56 * which will be used to index the guess table.
57 * A better hash function would result in additional compression,
58 * at the expense of time.
60 #define HASH(state, x) state->hash = (state->hash << 4) ^ (x)
61 #define GUESS_TABLE_SIZE 65536
65 u_char dict[GUESS_TABLE_SIZE];
69 compress(struct pred1_state *state, u_char *source, u_char *dest, int len)
72 unsigned char *flagdest, flags, *orgdest;
77 flags = 0; /* All guess wrong initially */
78 for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) {
79 if (state->dict[state->hash] == *source) {
80 flags |= bitmask; /* Guess was right - don't output */
82 state->dict[state->hash] = *source;
83 *dest++ = *source; /* Guess wrong, output char */
85 HASH(state, *source++);
90 return (dest - orgdest);
94 SyncTable(struct pred1_state *state, u_char *source, u_char *dest, int len)
97 *dest++ = state->dict[state->hash] = *source;
98 HASH(state, *source++);
103 decompress(struct pred1_state *state, u_char *source, u_char *dest, int len)
106 unsigned char flags, *orgdest;
112 for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
113 if (flags & bitmask) {
114 *dest = state->dict[state->hash]; /* Guess correct */
117 break; /* we seem to be really done -- cabo */
118 state->dict[state->hash] = *source; /* Guess wrong */
119 *dest = *source++; /* Read from source */
122 HASH(state, *dest++);
125 return (dest - orgdest);
131 struct pred1_state *state = (struct pred1_state *)v;
136 Pred1ResetInput(void *v)
138 struct pred1_state *state = (struct pred1_state *)v;
140 memset(state->dict, '\0', sizeof state->dict);
141 log_Printf(LogCCP, "Predictor1: Input channel reset\n");
145 Pred1ResetOutput(void *v)
147 struct pred1_state *state = (struct pred1_state *)v;
149 memset(state->dict, '\0', sizeof state->dict);
150 log_Printf(LogCCP, "Predictor1: Output channel reset\n");
152 return 1; /* Ask FSM to ACK */
156 Pred1InitInput(struct bundle *bundle, struct fsm_opt *o)
158 struct pred1_state *state;
159 state = (struct pred1_state *)malloc(sizeof(struct pred1_state));
161 Pred1ResetInput(state);
166 Pred1InitOutput(struct bundle *bundle, struct fsm_opt *o)
168 struct pred1_state *state;
169 state = (struct pred1_state *)malloc(sizeof(struct pred1_state));
171 Pred1ResetOutput(state);
176 Pred1Output(void *v, struct ccp *ccp, struct link *l, int pri, u_short *proto,
179 struct pred1_state *state = (struct pred1_state *)v;
181 u_char *cp, *wp, *hp;
183 u_char bufp[MAX_MTU + 2];
186 orglen = m_length(bp) + 2; /* add count of proto */
187 mwp = m_get((orglen + 2) / 8 * 9 + 12, MB_CCPOUT);
188 hp = wp = MBUF_CTOP(mwp);
190 *wp++ = *cp++ = orglen >> 8;
191 *wp++ = *cp++ = orglen & 0377;
193 *cp++ = *proto & 0377;
194 mbuf_Read(bp, cp, orglen - 2);
195 fcs = hdlc_Fcs(bufp, 2 + orglen);
198 len = compress(state, bufp + 2, wp, orglen);
199 log_Printf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len);
200 ccp->uncompout += orglen;
206 memcpy(wp, bufp + 2, orglen);
208 ccp->compout += orglen;
213 mwp->m_len = wp - MBUF_CTOP(mwp);
214 *proto = ccp_Proto(ccp);
219 Pred1Input(void *v, struct ccp *ccp, u_short *proto, struct mbuf *bp)
221 struct pred1_state *state = (struct pred1_state *)v;
228 wp = m_get(MAX_MRU + 2, MB_CCPIN);
231 pp = bufp = MBUF_CTOP(wp);
236 ccp->uncompin += len & 0x7fff;
238 len1 = decompress(state, cp, pp, olen - 4);
241 if (len != len1) { /* Error is detected. Send reset request */
242 log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len1, len);
243 fsm_Reopen(&ccp->fsm);
250 } else if (len + 4 != olen) {
251 log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len + 4, olen);
252 fsm_Reopen(&ccp->fsm);
258 SyncTable(state, cp, pp, len);
262 *pp++ = *cp++; /* CRC */
264 fcs = hdlc_Fcs(bufp, wp->m_len = pp - bufp);
265 if (fcs == GOODFCS) {
266 wp->m_offset += 2; /* skip length */
267 wp->m_len -= 4; /* skip length & CRC */
276 *proto = (*proto << 8) | *pp++;
281 const char *pre = *MBUF_CTOP(bp) & 0x80 ? "" : "un";
282 log_Printf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%scompressed), len = 0x%x,"
283 " olen = 0x%x\n", fcs, pre, len, olen);
284 log_Printf(LogCCP, "%s: Bad %scompressed CRC-16\n",
285 ccp->fsm.link->name, pre);
286 fsm_Reopen(&ccp->fsm);
294 Pred1DictSetup(void *v, struct ccp *ccp, u_short proto, struct mbuf *bp)
299 Pred1DispOpts(struct fsm_opt *o)
305 Pred1InitOptsOutput(struct bundle *bundle, struct fsm_opt *o,
306 const struct ccp_config *cfg)
312 Pred1SetOpts(struct bundle *bundle, struct fsm_opt *o,
313 const struct ccp_config *cfg)
315 if (o->hdr.len != 2) {
322 const struct ccp_algorithm Pred1Algorithm = {