1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 1997 Brian Somers <brian@Awfulhak.org>
5 * Ian Donaldson <iand@labtam.labtam.oz.au>
6 * Carsten Bormann <cabo@cs.tu-berlin.de>
7 * Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32 #include <sys/types.h>
33
34 #include <stdlib.h>
35 #include <string.h>
36 #include <termios.h>
37
38 #include "defs.h"
39 #include "layer.h"
40 #include "mbuf.h"
41 #include "log.h"
42 #include "timer.h"
43 #include "fsm.h"
44 #include "lqr.h"
45 #include "hdlc.h"
46 #include "lcp.h"
47 #include "ccp.h"
48 #include "throughput.h"
49 #include "link.h"
50 #include "pred.h"
51
52 /* The following hash code is the heart of the algorithm:
53 * It builds a sliding hash sum of the previous 3-and-a-bit characters
54 * which will be used to index the guess table.
55 * A better hash function would result in additional compression,
56 * at the expense of time.
57 */
58 #define HASH(state, x) state->hash = (state->hash << 4) ^ (x)
59 #define GUESS_TABLE_SIZE 65536
60
61 struct pred1_state {
62 u_short hash;
63 u_char dict[GUESS_TABLE_SIZE];
64 };
65
66 static int
compress(struct pred1_state * state,u_char * source,u_char * dest,int len)67 compress(struct pred1_state *state, u_char *source, u_char *dest, int len)
68 {
69 int i, bitmask;
70 unsigned char *flagdest, flags, *orgdest;
71
72 orgdest = dest;
73 while (len) {
74 flagdest = dest++;
75 flags = 0; /* All guess wrong initially */
76 for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) {
77 if (state->dict[state->hash] == *source) {
78 flags |= bitmask; /* Guess was right - don't output */
79 } else {
80 state->dict[state->hash] = *source;
81 *dest++ = *source; /* Guess wrong, output char */
82 }
83 HASH(state, *source++);
84 len--;
85 }
86 *flagdest = flags;
87 }
88 return (dest - orgdest);
89 }
90
91 static void
SyncTable(struct pred1_state * state,u_char * source,u_char * dest,int len)92 SyncTable(struct pred1_state *state, u_char *source, u_char *dest, int len)
93 {
94 while (len--) {
95 *dest++ = state->dict[state->hash] = *source;
96 HASH(state, *source++);
97 }
98 }
99
100 static int
decompress(struct pred1_state * state,u_char * source,u_char * dest,int len)101 decompress(struct pred1_state *state, u_char *source, u_char *dest, int len)
102 {
103 int i, bitmask;
104 unsigned char flags, *orgdest;
105
106 orgdest = dest;
107 while (len) {
108 flags = *source++;
109 len--;
110 for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
111 if (flags & bitmask) {
112 *dest = state->dict[state->hash]; /* Guess correct */
113 } else {
114 if (!len)
115 break; /* we seem to be really done -- cabo */
116 state->dict[state->hash] = *source; /* Guess wrong */
117 *dest = *source++; /* Read from source */
118 len--;
119 }
120 HASH(state, *dest++);
121 }
122 }
123 return (dest - orgdest);
124 }
125
126 static void
Pred1Term(void * v)127 Pred1Term(void *v)
128 {
129 struct pred1_state *state = (struct pred1_state *)v;
130 free(state);
131 }
132
133 static void
Pred1ResetInput(void * v)134 Pred1ResetInput(void *v)
135 {
136 struct pred1_state *state = (struct pred1_state *)v;
137 state->hash = 0;
138 memset(state->dict, '\0', sizeof state->dict);
139 log_Printf(LogCCP, "Predictor1: Input channel reset\n");
140 }
141
142 static int
Pred1ResetOutput(void * v)143 Pred1ResetOutput(void *v)
144 {
145 struct pred1_state *state = (struct pred1_state *)v;
146 state->hash = 0;
147 memset(state->dict, '\0', sizeof state->dict);
148 log_Printf(LogCCP, "Predictor1: Output channel reset\n");
149
150 return 1; /* Ask FSM to ACK */
151 }
152
153 static void *
Pred1InitInput(struct bundle * bundle __unused,struct fsm_opt * o __unused)154 Pred1InitInput(struct bundle *bundle __unused, struct fsm_opt *o __unused)
155 {
156 struct pred1_state *state;
157 state = (struct pred1_state *)malloc(sizeof(struct pred1_state));
158 if (state != NULL)
159 Pred1ResetInput(state);
160 return state;
161 }
162
163 static void *
Pred1InitOutput(struct bundle * bundle __unused,struct fsm_opt * o __unused)164 Pred1InitOutput(struct bundle *bundle __unused, struct fsm_opt *o __unused)
165 {
166 struct pred1_state *state;
167 state = (struct pred1_state *)malloc(sizeof(struct pred1_state));
168 if (state != NULL)
169 Pred1ResetOutput(state);
170 return state;
171 }
172
173 static struct mbuf *
Pred1Output(void * v,struct ccp * ccp,struct link * l __unused,int pri __unused,u_short * proto,struct mbuf * bp)174 Pred1Output(void *v, struct ccp *ccp, struct link *l __unused,
175 int pri __unused, u_short *proto, struct mbuf *bp)
176 {
177 struct pred1_state *state = (struct pred1_state *)v;
178 struct mbuf *mwp;
179 u_char *cp, *wp, *hp;
180 int orglen, len;
181 u_char bufp[MAX_MTU + 2];
182 u_short fcs;
183
184 orglen = m_length(bp) + 2; /* add count of proto */
185 mwp = m_get((orglen + 2) / 8 * 9 + 12, MB_CCPOUT);
186 hp = wp = MBUF_CTOP(mwp);
187 cp = bufp;
188 *wp++ = *cp++ = orglen >> 8;
189 *wp++ = *cp++ = orglen & 0377;
190 *cp++ = *proto >> 8;
191 *cp++ = *proto & 0377;
192 mbuf_Read(bp, cp, orglen - 2);
193 fcs = hdlc_Fcs(bufp, 2 + orglen);
194 fcs = ~fcs;
195
196 len = compress(state, bufp + 2, wp, orglen);
197 log_Printf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len);
198 ccp->uncompout += orglen;
199 if (len < orglen) {
200 *hp |= 0x80;
201 wp += len;
202 ccp->compout += len;
203 } else {
204 memcpy(wp, bufp + 2, orglen);
205 wp += orglen;
206 ccp->compout += orglen;
207 }
208
209 *wp++ = fcs & 0377;
210 *wp++ = fcs >> 8;
211 mwp->m_len = wp - MBUF_CTOP(mwp);
212 *proto = ccp_Proto(ccp);
213 return mwp;
214 }
215
216 static struct mbuf *
Pred1Input(void * v,struct ccp * ccp,u_short * proto,struct mbuf * bp)217 Pred1Input(void *v, struct ccp *ccp, u_short *proto, struct mbuf *bp)
218 {
219 struct pred1_state *state = (struct pred1_state *)v;
220 u_char *cp, *pp;
221 int len, olen, len1;
222 struct mbuf *wp;
223 u_char *bufp;
224 u_short fcs;
225
226 wp = m_get(MAX_MRU + 2, MB_CCPIN);
227 cp = MBUF_CTOP(bp);
228 olen = m_length(bp);
229 pp = bufp = MBUF_CTOP(wp);
230 *pp++ = *cp & 0177;
231 len = *cp++ << 8;
232 *pp++ = *cp;
233 len += *cp++;
234 ccp->uncompin += len & 0x7fff;
235 if (len & 0x8000) {
236 len1 = decompress(state, cp, pp, olen - 4);
237 ccp->compin += olen;
238 len &= 0x7fff;
239 if (len != len1) { /* Error is detected. Send reset request */
240 log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len1, len);
241 fsm_Reopen(&ccp->fsm);
242 m_freem(bp);
243 m_freem(wp);
244 return NULL;
245 }
246 cp += olen - 4;
247 pp += len1;
248 } else if (len + 4 != olen) {
249 log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len + 4, olen);
250 fsm_Reopen(&ccp->fsm);
251 m_freem(wp);
252 m_freem(bp);
253 return NULL;
254 } else {
255 ccp->compin += len;
256 SyncTable(state, cp, pp, len);
257 cp += len;
258 pp += len;
259 }
260 *pp++ = *cp++; /* CRC */
261 *pp++ = *cp++;
262 fcs = hdlc_Fcs(bufp, wp->m_len = pp - bufp);
263 if (fcs == GOODFCS) {
264 wp->m_offset += 2; /* skip length */
265 wp->m_len -= 4; /* skip length & CRC */
266 pp = MBUF_CTOP(wp);
267 *proto = *pp++;
268 if (*proto & 1) {
269 wp->m_offset++;
270 wp->m_len--;
271 } else {
272 wp->m_offset += 2;
273 wp->m_len -= 2;
274 *proto = (*proto << 8) | *pp++;
275 }
276 m_freem(bp);
277 return wp;
278 } else {
279 const char *pre = *MBUF_CTOP(bp) & 0x80 ? "" : "un";
280 log_Printf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%scompressed), len = 0x%x,"
281 " olen = 0x%x\n", fcs, pre, len, olen);
282 log_Printf(LogCCP, "%s: Bad %scompressed CRC-16\n",
283 ccp->fsm.link->name, pre);
284 fsm_Reopen(&ccp->fsm);
285 m_freem(wp);
286 }
287 m_freem(bp);
288 return NULL;
289 }
290
291 static void
Pred1DictSetup(void * v __unused,struct ccp * ccp __unused,u_short proto __unused,struct mbuf * bp __unused)292 Pred1DictSetup(void *v __unused, struct ccp *ccp __unused,
293 u_short proto __unused, struct mbuf *bp __unused)
294 {
295 /* Nothing to see here */
296 }
297
298 static const char *
Pred1DispOpts(struct fsm_opt * o __unused)299 Pred1DispOpts(struct fsm_opt *o __unused)
300 {
301 return NULL;
302 }
303
304 static void
Pred1InitOptsOutput(struct bundle * bundle __unused,struct fsm_opt * o,const struct ccp_config * cfg __unused)305 Pred1InitOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o,
306 const struct ccp_config *cfg __unused)
307 {
308 o->hdr.len = 2;
309 }
310
311 static int
Pred1SetOpts(struct bundle * bundle __unused,struct fsm_opt * o,const struct ccp_config * cfg __unused)312 Pred1SetOpts(struct bundle *bundle __unused, struct fsm_opt *o,
313 const struct ccp_config *cfg __unused)
314 {
315 if (o->hdr.len != 2) {
316 o->hdr.len = 2;
317 return MODE_NAK;
318 }
319 return MODE_ACK;
320 }
321
322 const struct ccp_algorithm Pred1Algorithm = {
323 TY_PRED1,
324 CCP_NEG_PRED1,
325 Pred1DispOpts,
326 ccp_DefaultUsable,
327 ccp_DefaultRequired,
328 {
329 Pred1SetOpts,
330 Pred1InitInput,
331 Pred1Term,
332 Pred1ResetInput,
333 Pred1Input,
334 Pred1DictSetup
335 },
336 {
337 0,
338 Pred1InitOptsOutput,
339 Pred1SetOpts,
340 Pred1InitOutput,
341 Pred1Term,
342 Pred1ResetOutput,
343 Pred1Output
344 },
345 };
346