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: releng/11.0/usr.sbin/ppp/pred.c 134789 2004-09-05 01:46:52Z brian $ 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 61struct pred1_state { 62 u_short hash; 63 u_char dict[GUESS_TABLE_SIZE]; 64}; 65 66static int 67compress(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 91static void 92SyncTable(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 100static int 101decompress(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 126static void 127Pred1Term(void *v) 128{ 129 struct pred1_state *state = (struct pred1_state *)v; 130 free(state); 131} 132 133static void 134Pred1ResetInput(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 142static int 143Pred1ResetOutput(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 153static void * 154Pred1InitInput(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 163static void * 164Pred1InitOutput(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 173static struct mbuf * 174Pred1Output(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 216static struct mbuf * 217Pred1Input(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 291static void 292Pred1DictSetup(void *v __unused, struct ccp *ccp __unused, 293 u_short proto __unused, struct mbuf *bp __unused) 294{ 295 /* Nothing to see here */ 296} 297 298static const char * 299Pred1DispOpts(struct fsm_opt *o __unused) 300{ 301 return NULL; 302} 303 304static void 305Pred1InitOptsOutput(struct bundle *bundle __unused, struct fsm_opt *o, 306 const struct ccp_config *cfg __unused) 307{ 308 o->hdr.len = 2; 309} 310 311static int 312Pred1SetOpts(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 322const 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