pred.c revision 31921
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 * $Id$ 30 */ 31 32#include <sys/param.h> 33#include <netinet/in.h> 34 35#include <stdio.h> 36#include <stdlib.h> 37#include <string.h> 38 39#include "command.h" 40#include "mbuf.h" 41#include "log.h" 42#include "defs.h" 43#include "loadalias.h" 44#include "vars.h" 45#include "timer.h" 46#include "fsm.h" 47#include "hdlc.h" 48#include "lcpproto.h" 49#include "lcp.h" 50#include "ccp.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 IHASH(x) do {iHash = (iHash << 4) ^ (x);} while(0) 60#define OHASH(x) do {oHash = (oHash << 4) ^ (x);} while(0) 61#define GUESS_TABLE_SIZE 65536 62 63static unsigned short int iHash, oHash; 64static unsigned char *InputGuessTable; 65static unsigned char *OutputGuessTable; 66 67static int 68compress(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 (OutputGuessTable[oHash] == *source) { 79 flags |= bitmask; /* Guess was right - don't output */ 80 } else { 81 OutputGuessTable[oHash] = *source; 82 *dest++ = *source; /* Guess wrong, output char */ 83 } 84 OHASH(*source++); 85 len--; 86 } 87 *flagdest = flags; 88 } 89 return (dest - orgdest); 90} 91 92static void 93SyncTable(u_char * source, u_char * dest, int len) 94{ 95 96 while (len--) { 97 if (InputGuessTable[iHash] != *source) { 98 InputGuessTable[iHash] = *source; 99 } 100 IHASH(*dest++ = *source++); 101 } 102} 103 104static int 105decompress(u_char * source, u_char * dest, int len) 106{ 107 int i, bitmask; 108 unsigned char flags, *orgdest; 109 110 orgdest = dest; 111 while (len) { 112 flags = *source++; 113 len--; 114 for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 115 if (flags & bitmask) { 116 *dest = InputGuessTable[iHash]; /* Guess correct */ 117 } else { 118 if (!len) 119 break; /* we seem to be really done -- cabo */ 120 InputGuessTable[iHash] = *source; /* Guess wrong */ 121 *dest = *source++; /* Read from source */ 122 len--; 123 } 124 IHASH(*dest++); 125 } 126 } 127 return (dest - orgdest); 128} 129 130static void 131Pred1TermInput(void) 132{ 133 if (InputGuessTable != NULL) { 134 free(InputGuessTable); 135 InputGuessTable = NULL; 136 } 137} 138 139static void 140Pred1TermOutput(void) 141{ 142 if (OutputGuessTable != NULL) { 143 free(OutputGuessTable); 144 OutputGuessTable = NULL; 145 } 146} 147 148static void 149Pred1ResetInput(void) 150{ 151 iHash = 0; 152 memset(InputGuessTable, '\0', GUESS_TABLE_SIZE); 153 LogPrintf(LogCCP, "Predictor1: Input channel reset\n"); 154} 155 156static void 157Pred1ResetOutput(void) 158{ 159 oHash = 0; 160 memset(OutputGuessTable, '\0', GUESS_TABLE_SIZE); 161 LogPrintf(LogCCP, "Predictor1: Output channel reset\n"); 162} 163 164static int 165Pred1InitInput(void) 166{ 167 if (InputGuessTable == NULL) 168 if ((InputGuessTable = malloc(GUESS_TABLE_SIZE)) == NULL) 169 return 0; 170 Pred1ResetInput(); 171 return 1; 172} 173 174static int 175Pred1InitOutput(void) 176{ 177 if (OutputGuessTable == NULL) 178 if ((OutputGuessTable = malloc(GUESS_TABLE_SIZE)) == NULL) 179 return 0; 180 Pred1ResetOutput(); 181 return 1; 182} 183 184static int 185Pred1Output(int pri, u_short proto, struct mbuf * bp) 186{ 187 struct mbuf *mwp; 188 u_char *cp, *wp, *hp; 189 int orglen, len; 190 u_char bufp[MAX_MTU + 2]; 191 u_short fcs; 192 193 orglen = plength(bp) + 2; /* add count of proto */ 194 mwp = mballoc((orglen + 2) / 8 * 9 + 12, MB_HDLCOUT); 195 hp = wp = MBUF_CTOP(mwp); 196 cp = bufp; 197 *wp++ = *cp++ = orglen >> 8; 198 *wp++ = *cp++ = orglen & 0377; 199 *cp++ = proto >> 8; 200 *cp++ = proto & 0377; 201 mbread(bp, cp, orglen - 2); 202 fcs = HdlcFcs(INITFCS, bufp, 2 + orglen); 203 fcs = ~fcs; 204 205 len = compress(bufp + 2, wp, orglen); 206 LogPrintf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len); 207 CcpInfo.uncompout += orglen; 208 if (len < orglen) { 209 *hp |= 0x80; 210 wp += len; 211 CcpInfo.compout += len; 212 } else { 213 memcpy(wp, bufp + 2, orglen); 214 wp += orglen; 215 CcpInfo.compout += orglen; 216 } 217 218 *wp++ = fcs & 0377; 219 *wp++ = fcs >> 8; 220 mwp->cnt = wp - MBUF_CTOP(mwp); 221 HdlcOutput(PRI_NORMAL, PROTO_COMPD, mwp); 222 return 1; 223} 224 225static struct mbuf * 226Pred1Input(u_short *proto, struct mbuf *bp) 227{ 228 u_char *cp, *pp; 229 int len, olen, len1; 230 struct mbuf *wp; 231 u_char *bufp; 232 u_short fcs; 233 234 wp = mballoc(MAX_MTU + 2, MB_IPIN); 235 cp = MBUF_CTOP(bp); 236 olen = plength(bp); 237 pp = bufp = MBUF_CTOP(wp); 238 *pp++ = *cp & 0177; 239 len = *cp++ << 8; 240 *pp++ = *cp; 241 len += *cp++; 242 CcpInfo.uncompin += len & 0x7fff; 243 if (len & 0x8000) { 244 len1 = decompress(cp, pp, olen - 4); 245 CcpInfo.compin += olen; 246 len &= 0x7fff; 247 if (len != len1) { /* Error is detected. Send reset request */ 248 LogPrintf(LogCCP, "Pred1: Length error\n"); 249 CcpSendResetReq(&CcpFsm); 250 pfree(bp); 251 pfree(wp); 252 return NULL; 253 } 254 cp += olen - 4; 255 pp += len1; 256 } else { 257 CcpInfo.compin += len; 258 SyncTable(cp, pp, len); 259 cp += len; 260 pp += len; 261 } 262 *pp++ = *cp++; /* CRC */ 263 *pp++ = *cp++; 264 fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp); 265 if (fcs != GOODFCS) 266 LogPrintf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%s), len = 0x%x," 267 " olen = 0x%x\n", fcs, (fcs == GOODFCS) ? "good" : "bad", 268 len, olen); 269 if (fcs == GOODFCS) { 270 wp->offset += 2; /* skip length */ 271 wp->cnt -= 4; /* skip length & CRC */ 272 pp = MBUF_CTOP(wp); 273 *proto = *pp++; 274 if (*proto & 1) { 275 wp->offset++; 276 wp->cnt--; 277 } else { 278 wp->offset += 2; 279 wp->cnt -= 2; 280 *proto = (*proto << 8) | *pp++; 281 } 282 return wp; 283 } else { 284 LogDumpBp(LogHDLC, "Bad FCS", wp); 285 CcpSendResetReq(&CcpFsm); 286 pfree(wp); 287 } 288 pfree(bp); 289 return NULL; 290} 291 292static void 293Pred1DictSetup(u_short proto, struct mbuf * bp) 294{ 295} 296 297static const char * 298Pred1DispOpts(struct lcp_opt *o) 299{ 300 return NULL; 301} 302 303static void 304Pred1GetOpts(struct lcp_opt *o) 305{ 306 o->id = TY_PRED1; 307 o->len = 2; 308} 309 310static int 311Pred1SetOpts(struct lcp_opt *o) 312{ 313 if (o->id != TY_PRED1 || o->len != 2) { 314 Pred1GetOpts(o); 315 return MODE_NAK; 316 } 317 return MODE_ACK; 318} 319 320const struct ccp_algorithm Pred1Algorithm = { 321 TY_PRED1, 322 ConfPred1, 323 Pred1DispOpts, 324 { 325 Pred1GetOpts, 326 Pred1SetOpts, 327 Pred1InitInput, 328 Pred1TermInput, 329 Pred1ResetInput, 330 Pred1Input, 331 Pred1DictSetup 332 }, 333 { 334 Pred1GetOpts, 335 Pred1SetOpts, 336 Pred1InitOutput, 337 Pred1TermOutput, 338 Pred1ResetOutput, 339 Pred1Output 340 }, 341}; 342