1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 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 * $FreeBSD$ 32 */ 33 34 #include <sys/types.h> 35 36 #include <stdlib.h> 37 #include <string.h> 38 #include <termios.h> 39 40 #include "defs.h" 41 #include "layer.h" 42 #include "mbuf.h" 43 #include "log.h" 44 #include "timer.h" 45 #include "fsm.h" 46 #include "lqr.h" 47 #include "hdlc.h" 48 #include "lcp.h" 49 #include "ccp.h" 50 #include "throughput.h" 51 #include "link.h" 52 #include "pred.h" 53 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. 59 */ 60 #define HASH(state, x) state->hash = (state->hash << 4) ^ (x) 61 #define GUESS_TABLE_SIZE 65536 62 63 struct pred1_state { 64 u_short hash; 65 u_char dict[GUESS_TABLE_SIZE]; 66 }; 67 68 static int 69 compress(struct pred1_state *state, u_char *source, u_char *dest, int len) 70 { 71 int i, bitmask; 72 unsigned char *flagdest, flags, *orgdest; 73 74 orgdest = dest; 75 while (len) { 76 flagdest = dest++; 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 */ 81 } else { 82 state->dict[state->hash] = *source; 83 *dest++ = *source; /* Guess wrong, output char */ 84 } 85 HASH(state, *source++); 86 len--; 87 } 88 *flagdest = flags; 89 } 90 return (dest - orgdest); 91 } 92 93 static void 94 SyncTable(struct pred1_state *state, u_char *source, u_char *dest, int len) 95 { 96 while (len--) { 97 *dest++ = state->dict[state->hash] = *source; 98 HASH(state, *source++); 99 } 100 } 101 102 static int 103 decompress(struct pred1_state *state, u_char *source, u_char *dest, int len) 104 { 105 int i, bitmask; 106 unsigned char flags, *orgdest; 107 108 orgdest = dest; 109 while (len) { 110 flags = *source++; 111 len--; 112 for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 113 if (flags & bitmask) { 114 *dest = state->dict[state->hash]; /* Guess correct */ 115 } else { 116 if (!len) 117 break; /* we seem to be really done -- cabo */ 118 state->dict[state->hash] = *source; /* Guess wrong */ 119 *dest = *source++; /* Read from source */ 120 len--; 121 } 122 HASH(state, *dest++); 123 } 124 } 125 return (dest - orgdest); 126 } 127 128 static void 129 Pred1Term(void *v) 130 { 131 struct pred1_state *state = (struct pred1_state *)v; 132 free(state); 133 } 134 135 static void 136 Pred1ResetInput(void *v) 137 { 138 struct pred1_state *state = (struct pred1_state *)v; 139 state->hash = 0; 140 memset(state->dict, '\0', sizeof state->dict); 141 log_Printf(LogCCP, "Predictor1: Input channel reset\n"); 142 } 143 144 static int 145 Pred1ResetOutput(void *v) 146 { 147 struct pred1_state *state = (struct pred1_state *)v; 148 state->hash = 0; 149 memset(state->dict, '\0', sizeof state->dict); 150 log_Printf(LogCCP, "Predictor1: Output channel reset\n"); 151 152 return 1; /* Ask FSM to ACK */ 153 } 154 155 static void * 156 Pred1InitInput(struct bundle *bundle __unused, struct fsm_opt *o __unused) 157 { 158 struct pred1_state *state; 159 state = (struct pred1_state *)malloc(sizeof(struct pred1_state)); 160 if (state != NULL) 161 Pred1ResetInput(state); 162 return state; 163 } 164 165 static void * 166 Pred1InitOutput(struct bundle *bundle __unused, struct fsm_opt *o __unused) 167 { 168 struct pred1_state *state; 169 state = (struct pred1_state *)malloc(sizeof(struct pred1_state)); 170 if (state != NULL) 171 Pred1ResetOutput(state); 172 return state; 173 } 174 175 static struct mbuf * 176 Pred1Output(void *v, struct ccp *ccp, struct link *l __unused, 177 int pri __unused, u_short *proto, struct mbuf *bp) 178 { 179 struct pred1_state *state = (struct pred1_state *)v; 180 struct mbuf *mwp; 181 u_char *cp, *wp, *hp; 182 int orglen, len; 183 u_char bufp[MAX_MTU + 2]; 184 u_short fcs; 185 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); 189 cp = bufp; 190 *wp++ = *cp++ = orglen >> 8; 191 *wp++ = *cp++ = orglen & 0377; 192 *cp++ = *proto >> 8; 193 *cp++ = *proto & 0377; 194 mbuf_Read(bp, cp, orglen - 2); 195 fcs = hdlc_Fcs(bufp, 2 + orglen); 196 fcs = ~fcs; 197 198 len = compress(state, bufp + 2, wp, orglen); 199 log_Printf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len); 200 ccp->uncompout += orglen; 201 if (len < orglen) { 202 *hp |= 0x80; 203 wp += len; 204 ccp->compout += len; 205 } else { 206 memcpy(wp, bufp + 2, orglen); 207 wp += orglen; 208 ccp->compout += orglen; 209 } 210 211 *wp++ = fcs & 0377; 212 *wp++ = fcs >> 8; 213 mwp->m_len = wp - MBUF_CTOP(mwp); 214 *proto = ccp_Proto(ccp); 215 return mwp; 216 } 217 218 static struct mbuf * 219 Pred1Input(void *v, struct ccp *ccp, u_short *proto, struct mbuf *bp) 220 { 221 struct pred1_state *state = (struct pred1_state *)v; 222 u_char *cp, *pp; 223 int len, olen, len1; 224 struct mbuf *wp; 225 u_char *bufp; 226 u_short fcs; 227 228 wp = m_get(MAX_MRU + 2, MB_CCPIN); 229 cp = MBUF_CTOP(bp); 230 olen = m_length(bp); 231 pp = bufp = MBUF_CTOP(wp); 232 *pp++ = *cp & 0177; 233 len = *cp++ << 8; 234 *pp++ = *cp; 235 len += *cp++; 236 ccp->uncompin += len & 0x7fff; 237 if (len & 0x8000) { 238 len1 = decompress(state, cp, pp, olen - 4); 239 ccp->compin += olen; 240 len &= 0x7fff; 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); 244 m_freem(bp); 245 m_freem(wp); 246 return NULL; 247 } 248 cp += olen - 4; 249 pp += len1; 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); 253 m_freem(wp); 254 m_freem(bp); 255 return NULL; 256 } else { 257 ccp->compin += len; 258 SyncTable(state, cp, pp, len); 259 cp += len; 260 pp += len; 261 } 262 *pp++ = *cp++; /* CRC */ 263 *pp++ = *cp++; 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 */ 268 pp = MBUF_CTOP(wp); 269 *proto = *pp++; 270 if (*proto & 1) { 271 wp->m_offset++; 272 wp->m_len--; 273 } else { 274 wp->m_offset += 2; 275 wp->m_len -= 2; 276 *proto = (*proto << 8) | *pp++; 277 } 278 m_freem(bp); 279 return wp; 280 } else { 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); 287 m_freem(wp); 288 } 289 m_freem(bp); 290 return NULL; 291 } 292 293 static void 294 Pred1DictSetup(void *v __unused, struct ccp *ccp __unused, 295 u_short proto __unused, struct mbuf *bp __unused) 296 { 297 /* Nothing to see here */ 298 } 299 300 static const char * 301 Pred1DispOpts(struct fsm_opt *o __unused) 302 { 303 return NULL; 304 } 305 306 static void 307 Pred1InitOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o, 308 const struct ccp_config *cfg __unused) 309 { 310 o->hdr.len = 2; 311 } 312 313 static int 314 Pred1SetOpts(struct bundle *bundle __unused, struct fsm_opt *o, 315 const struct ccp_config *cfg __unused) 316 { 317 if (o->hdr.len != 2) { 318 o->hdr.len = 2; 319 return MODE_NAK; 320 } 321 return MODE_ACK; 322 } 323 324 const struct ccp_algorithm Pred1Algorithm = { 325 TY_PRED1, 326 CCP_NEG_PRED1, 327 Pred1DispOpts, 328 ccp_DefaultUsable, 329 ccp_DefaultRequired, 330 { 331 Pred1SetOpts, 332 Pred1InitInput, 333 Pred1Term, 334 Pred1ResetInput, 335 Pred1Input, 336 Pred1DictSetup 337 }, 338 { 339 0, 340 Pred1InitOptsOutput, 341 Pred1SetOpts, 342 Pred1InitOutput, 343 Pred1Term, 344 Pred1ResetOutput, 345 Pred1Output 346 }, 347 }; 348