pred.c revision 44792
1234287Sdim/*- 2234287Sdim * Copyright (c) 1997 Brian Somers <brian@Awfulhak.org> 3234287Sdim * Ian Donaldson <iand@labtam.labtam.oz.au> 4234287Sdim * Carsten Bormann <cabo@cs.tu-berlin.de> 5234287Sdim * Dave Rand <dlr@bungi.com>/<dave_rand@novell.com> 6234287Sdim * All rights reserved. 7234287Sdim * 8234287Sdim * Redistribution and use in source and binary forms, with or without 9234287Sdim * modification, are permitted provided that the following conditions 10234287Sdim * are met: 11234287Sdim * 1. Redistributions of source code must retain the above copyright 12234287Sdim * notice, this list of conditions and the following disclaimer. 13234287Sdim * 2. Redistributions in binary form must reproduce the above copyright 14234287Sdim * notice, this list of conditions and the following disclaimer in the 15234287Sdim * documentation and/or other materials provided with the distribution. 16234287Sdim * 17234287Sdim * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18234287Sdim * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19234287Sdim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20234287Sdim * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21234287Sdim * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22249423Sdim * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23234287Sdim * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24234287Sdim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25234287Sdim * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26234287Sdim * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27234287Sdim * SUCH DAMAGE. 28234287Sdim * 29234287Sdim * $Id: pred.c,v 1.23 1999/03/11 01:49:15 brian Exp $ 30234287Sdim */ 31234287Sdim 32234287Sdim#include <sys/types.h> 33234287Sdim 34234287Sdim#include <stdlib.h> 35234287Sdim#include <string.h> 36249423Sdim 37249423Sdim#include "defs.h" 38234287Sdim#include "mbuf.h" 39234287Sdim#include "log.h" 40234287Sdim#include "timer.h" 41234287Sdim#include "fsm.h" 42234287Sdim#include "lqr.h" 43234287Sdim#include "hdlc.h" 44234287Sdim#include "lcp.h" 45234287Sdim#include "ccp.h" 46234287Sdim#include "throughput.h" 47234287Sdim#include "link.h" 48234287Sdim#include "pred.h" 49243830Sdim 50234287Sdim/* The following hash code is the heart of the algorithm: 51234287Sdim * It builds a sliding hash sum of the previous 3-and-a-bit characters 52234287Sdim * which will be used to index the guess table. 53234287Sdim * A better hash function would result in additional compression, 54234287Sdim * at the expense of time. 55234287Sdim */ 56234287Sdim#define HASH(state, x) state->hash = (state->hash << 4) ^ (x) 57234287Sdim#define GUESS_TABLE_SIZE 65536 58234287Sdim 59234287Sdimstruct pred1_state { 60249423Sdim u_short hash; 61234287Sdim u_char dict[GUESS_TABLE_SIZE]; 62234287Sdim}; 63234287Sdim 64234287Sdimstatic int 65234287Sdimcompress(struct pred1_state *state, u_char *source, u_char *dest, int len) 66234287Sdim{ 67234287Sdim int i, bitmask; 68234287Sdim unsigned char *flagdest, flags, *orgdest; 69234287Sdim 70239462Sdim orgdest = dest; 71243830Sdim while (len) { 72234287Sdim flagdest = dest++; 73234287Sdim flags = 0; /* All guess wrong initially */ 74234287Sdim for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) { 75234287Sdim if (state->dict[state->hash] == *source) { 76234287Sdim flags |= bitmask; /* Guess was right - don't output */ 77234287Sdim } else { 78234287Sdim state->dict[state->hash] = *source; 79239462Sdim *dest++ = *source; /* Guess wrong, output char */ 80234287Sdim } 81234287Sdim HASH(state, *source++); 82234287Sdim len--; 83234287Sdim } 84239462Sdim *flagdest = flags; 85239462Sdim } 86234287Sdim return (dest - orgdest); 87234287Sdim} 88234287Sdim 89234287Sdimstatic void 90234287SdimSyncTable(struct pred1_state *state, u_char *source, u_char *dest, int len) 91234287Sdim{ 92239462Sdim while (len--) { 93239462Sdim *dest++ = state->dict[state->hash] = *source; 94234287Sdim HASH(state, *source++); 95239462Sdim } 96239462Sdim} 97249423Sdim 98249423Sdimstatic int 99249423Sdimdecompress(struct pred1_state *state, u_char *source, u_char *dest, int len) 100249423Sdim{ 101249423Sdim int i, bitmask; 102249423Sdim unsigned char flags, *orgdest; 103249423Sdim 104234287Sdim orgdest = dest; 105234287Sdim while (len) { 106234287Sdim flags = *source++; 107234287Sdim len--; 108234287Sdim for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 109234287Sdim if (flags & bitmask) { 110234287Sdim *dest = state->dict[state->hash]; /* Guess correct */ 111249423Sdim } else { 112249423Sdim if (!len) 113239462Sdim break; /* we seem to be really done -- cabo */ 114249423Sdim state->dict[state->hash] = *source; /* Guess wrong */ 115249423Sdim *dest = *source++; /* Read from source */ 116249423Sdim len--; 117249423Sdim } 118249423Sdim HASH(state, *dest++); 119249423Sdim } 120249423Sdim } 121249423Sdim return (dest - orgdest); 122249423Sdim} 123249423Sdim 124249423Sdimstatic void 125249423SdimPred1Term(void *v) 126249423Sdim{ 127249423Sdim struct pred1_state *state = (struct pred1_state *)v; 128234287Sdim free(state); 129234287Sdim} 130234287Sdim 131234287Sdimstatic void 132234287SdimPred1ResetInput(void *v) 133234287Sdim{ 134234287Sdim struct pred1_state *state = (struct pred1_state *)v; 135234287Sdim state->hash = 0; 136234287Sdim memset(state->dict, '\0', sizeof state->dict); 137234287Sdim log_Printf(LogCCP, "Predictor1: Input channel reset\n"); 138234287Sdim} 139234287Sdim 140234287Sdimstatic void 141239462SdimPred1ResetOutput(void *v) 142243830Sdim{ 143234287Sdim struct pred1_state *state = (struct pred1_state *)v; 144234287Sdim state->hash = 0; 145234287Sdim memset(state->dict, '\0', sizeof state->dict); 146239462Sdim log_Printf(LogCCP, "Predictor1: Output channel reset\n"); 147234287Sdim} 148234287Sdim 149234287Sdimstatic void * 150234287SdimPred1InitInput(struct lcp_opt *o) 151234287Sdim{ 152234287Sdim struct pred1_state *state; 153234287Sdim state = (struct pred1_state *)malloc(sizeof(struct pred1_state)); 154234287Sdim if (state != NULL) 155234287Sdim Pred1ResetInput(state); 156239462Sdim return state; 157243830Sdim} 158239462Sdim 159234287Sdimstatic void * 160234287SdimPred1InitOutput(struct lcp_opt *o) 161234287Sdim{ 162234287Sdim struct pred1_state *state; 163234287Sdim state = (struct pred1_state *)malloc(sizeof(struct pred1_state)); 164234287Sdim if (state != NULL) 165239462Sdim Pred1ResetOutput(state); 166239462Sdim return state; 167249423Sdim} 168249423Sdim 169249423Sdimstatic int 170249423SdimPred1Output(void *v, struct ccp *ccp, struct link *l, int pri, u_short proto, 171249423Sdim struct mbuf *bp) 172249423Sdim{ 173249423Sdim struct pred1_state *state = (struct pred1_state *)v; 174249423Sdim struct mbuf *mwp; 175249423Sdim u_char *cp, *wp, *hp; 176239462Sdim int orglen, len; 177239462Sdim u_char bufp[MAX_MTU + 2]; 178234287Sdim u_short fcs; 179234287Sdim 180234287Sdim orglen = mbuf_Length(bp) + 2; /* add count of proto */ 181 mwp = mbuf_Alloc((orglen + 2) / 8 * 9 + 12, MB_HDLCOUT); 182 hp = wp = MBUF_CTOP(mwp); 183 cp = bufp; 184 *wp++ = *cp++ = orglen >> 8; 185 *wp++ = *cp++ = orglen & 0377; 186 *cp++ = proto >> 8; 187 *cp++ = proto & 0377; 188 mbuf_Read(bp, cp, orglen - 2); 189 fcs = hdlc_Fcs(INITFCS, bufp, 2 + orglen); 190 fcs = ~fcs; 191 192 len = compress(state, bufp + 2, wp, orglen); 193 log_Printf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len); 194 ccp->uncompout += orglen; 195 if (len < orglen) { 196 *hp |= 0x80; 197 wp += len; 198 ccp->compout += len; 199 } else { 200 memcpy(wp, bufp + 2, orglen); 201 wp += orglen; 202 ccp->compout += orglen; 203 } 204 205 *wp++ = fcs & 0377; 206 *wp++ = fcs >> 8; 207 mwp->cnt = wp - MBUF_CTOP(mwp); 208 hdlc_Output(l, PRI_NORMAL, ccp_Proto(ccp), mwp); 209 return 1; 210} 211 212static struct mbuf * 213Pred1Input(void *v, struct ccp *ccp, u_short *proto, struct mbuf *bp) 214{ 215 struct pred1_state *state = (struct pred1_state *)v; 216 u_char *cp, *pp; 217 int len, olen, len1; 218 struct mbuf *wp; 219 u_char *bufp; 220 u_short fcs; 221 222 wp = mbuf_Alloc(MAX_MRU + 2, MB_IPIN); 223 cp = MBUF_CTOP(bp); 224 olen = mbuf_Length(bp); 225 pp = bufp = MBUF_CTOP(wp); 226 *pp++ = *cp & 0177; 227 len = *cp++ << 8; 228 *pp++ = *cp; 229 len += *cp++; 230 ccp->uncompin += len & 0x7fff; 231 if (len & 0x8000) { 232 len1 = decompress(state, cp, pp, olen - 4); 233 ccp->compin += olen; 234 len &= 0x7fff; 235 if (len != len1) { /* Error is detected. Send reset request */ 236 log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len1, len); 237 fsm_Reopen(&ccp->fsm); 238 mbuf_Free(bp); 239 mbuf_Free(wp); 240 return NULL; 241 } 242 cp += olen - 4; 243 pp += len1; 244 } else if (len + 4 != olen) { 245 log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len + 4, olen); 246 fsm_Reopen(&ccp->fsm); 247 mbuf_Free(wp); 248 mbuf_Free(bp); 249 return NULL; 250 } else { 251 ccp->compin += len; 252 SyncTable(state, cp, pp, len); 253 cp += len; 254 pp += len; 255 } 256 *pp++ = *cp++; /* CRC */ 257 *pp++ = *cp++; 258 fcs = hdlc_Fcs(INITFCS, bufp, wp->cnt = pp - bufp); 259 if (fcs == GOODFCS) { 260 wp->offset += 2; /* skip length */ 261 wp->cnt -= 4; /* skip length & CRC */ 262 pp = MBUF_CTOP(wp); 263 *proto = *pp++; 264 if (*proto & 1) { 265 wp->offset++; 266 wp->cnt--; 267 } else { 268 wp->offset += 2; 269 wp->cnt -= 2; 270 *proto = (*proto << 8) | *pp++; 271 } 272 mbuf_Free(bp); 273 return wp; 274 } else { 275 const char *pre = *MBUF_CTOP(bp) & 0x80 ? "" : "un"; 276 log_Printf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%scompressed), len = 0x%x," 277 " olen = 0x%x\n", fcs, pre, len, olen); 278 log_Printf(LogCCP, "%s: Bad %scompressed CRC-16\n", 279 ccp->fsm.link->name, pre); 280 fsm_Reopen(&ccp->fsm); 281 mbuf_Free(wp); 282 } 283 mbuf_Free(bp); 284 return NULL; 285} 286 287static void 288Pred1DictSetup(void *v, struct ccp *ccp, u_short proto, struct mbuf * bp) 289{ 290} 291 292static const char * 293Pred1DispOpts(struct lcp_opt *o) 294{ 295 return NULL; 296} 297 298static void 299Pred1InitOptsOutput(struct lcp_opt *o, const struct ccp_config *cfg) 300{ 301 o->len = 2; 302} 303 304static int 305Pred1SetOptsOutput(struct lcp_opt *o) 306{ 307 if (o->len != 2) { 308 o->len = 2; 309 return MODE_NAK; 310 } 311 return MODE_ACK; 312} 313 314static int 315Pred1SetOptsInput(struct lcp_opt *o, const struct ccp_config *cfg) 316{ 317 return Pred1SetOptsOutput(o); 318} 319 320const struct ccp_algorithm Pred1Algorithm = { 321 TY_PRED1, 322 CCP_NEG_PRED1, 323 Pred1DispOpts, 324 { 325 Pred1SetOptsInput, 326 Pred1InitInput, 327 Pred1Term, 328 Pred1ResetInput, 329 Pred1Input, 330 Pred1DictSetup 331 }, 332 { 333 Pred1InitOptsOutput, 334 Pred1SetOptsOutput, 335 Pred1InitOutput, 336 Pred1Term, 337 Pred1ResetOutput, 338 Pred1Output 339 }, 340}; 341