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