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