pred.c revision 79165
131921Sbrian/*- 231921Sbrian * Copyright (c) 1997 Brian Somers <brian@Awfulhak.org> 331921Sbrian * Ian Donaldson <iand@labtam.labtam.oz.au> 431921Sbrian * Carsten Bormann <cabo@cs.tu-berlin.de> 531921Sbrian * Dave Rand <dlr@bungi.com>/<dave_rand@novell.com> 631921Sbrian * All rights reserved. 730715Sbrian * 831921Sbrian * Redistribution and use in source and binary forms, with or without 931921Sbrian * modification, are permitted provided that the following conditions 1031921Sbrian * are met: 1131921Sbrian * 1. Redistributions of source code must retain the above copyright 1231921Sbrian * notice, this list of conditions and the following disclaimer. 1331921Sbrian * 2. Redistributions in binary form must reproduce the above copyright 1431921Sbrian * notice, this list of conditions and the following disclaimer in the 1531921Sbrian * documentation and/or other materials provided with the distribution. 1630715Sbrian * 1731921Sbrian * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1831921Sbrian * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1931921Sbrian * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2031921Sbrian * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 2131921Sbrian * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2231921Sbrian * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2331921Sbrian * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2431921Sbrian * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2531921Sbrian * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2631921Sbrian * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2731921Sbrian * SUCH DAMAGE. 2831921Sbrian * 2950479Speter * $FreeBSD: head/usr.sbin/ppp/pred.c 79165 2001-07-03 22:20:19Z brian $ 306059Samurai */ 316059Samurai 3236285Sbrian#include <sys/types.h> 3330715Sbrian 3431514Sbrian#include <stdlib.h> 3530715Sbrian#include <string.h> 3646686Sbrian#include <termios.h> 3730715Sbrian 3838174Sbrian#include "defs.h" 3946686Sbrian#include "layer.h" 4030715Sbrian#include "mbuf.h" 4130715Sbrian#include "log.h" 4230715Sbrian#include "timer.h" 4330715Sbrian#include "fsm.h" 4436285Sbrian#include "lqr.h" 4530715Sbrian#include "hdlc.h" 4631514Sbrian#include "lcp.h" 4730715Sbrian#include "ccp.h" 4844650Sbrian#include "throughput.h" 4944650Sbrian#include "link.h" 5030715Sbrian#include "pred.h" 5130715Sbrian 526059Samurai/* The following hash code is the heart of the algorithm: 536059Samurai * It builds a sliding hash sum of the previous 3-and-a-bit characters 546059Samurai * which will be used to index the guess table. 556059Samurai * A better hash function would result in additional compression, 566059Samurai * at the expense of time. 576059Samurai */ 5836285Sbrian#define HASH(state, x) state->hash = (state->hash << 4) ^ (x) 5931514Sbrian#define GUESS_TABLE_SIZE 65536 606059Samurai 6136285Sbrianstruct pred1_state { 6236285Sbrian u_short hash; 6336285Sbrian u_char dict[GUESS_TABLE_SIZE]; 6436285Sbrian}; 656059Samurai 666059Samuraistatic int 6736285Sbriancompress(struct pred1_state *state, u_char *source, u_char *dest, int len) 686059Samurai{ 6928679Sbrian int i, bitmask; 7028679Sbrian unsigned char *flagdest, flags, *orgdest; 716059Samurai 7228679Sbrian orgdest = dest; 7328679Sbrian while (len) { 7428679Sbrian flagdest = dest++; 7528679Sbrian flags = 0; /* All guess wrong initially */ 7628679Sbrian for (bitmask = 1, i = 0; i < 8 && len; i++, bitmask <<= 1) { 7736285Sbrian if (state->dict[state->hash] == *source) { 7828679Sbrian flags |= bitmask; /* Guess was right - don't output */ 7928679Sbrian } else { 8036285Sbrian state->dict[state->hash] = *source; 8128679Sbrian *dest++ = *source; /* Guess wrong, output char */ 8228679Sbrian } 8336285Sbrian HASH(state, *source++); 8428679Sbrian len--; 856059Samurai } 8628679Sbrian *flagdest = flags; 8728679Sbrian } 8828679Sbrian return (dest - orgdest); 896059Samurai} 906059Samurai 916059Samuraistatic void 9244792SbrianSyncTable(struct pred1_state *state, u_char *source, u_char *dest, int len) 936059Samurai{ 9428679Sbrian while (len--) { 9544792Sbrian *dest++ = state->dict[state->hash] = *source; 9644792Sbrian HASH(state, *source++); 9728679Sbrian } 986059Samurai} 996059Samurai 1006059Samuraistatic int 10144792Sbriandecompress(struct pred1_state *state, u_char *source, u_char *dest, int len) 1026059Samurai{ 10328679Sbrian int i, bitmask; 10428679Sbrian unsigned char flags, *orgdest; 1056059Samurai 10628679Sbrian orgdest = dest; 10728679Sbrian while (len) { 10828679Sbrian flags = *source++; 10928679Sbrian len--; 11028679Sbrian for (i = 0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 11128679Sbrian if (flags & bitmask) { 11236285Sbrian *dest = state->dict[state->hash]; /* Guess correct */ 11328679Sbrian } else { 11428679Sbrian if (!len) 11528679Sbrian break; /* we seem to be really done -- cabo */ 11636285Sbrian state->dict[state->hash] = *source; /* Guess wrong */ 11728679Sbrian *dest = *source++; /* Read from source */ 11828679Sbrian len--; 11928679Sbrian } 12036285Sbrian HASH(state, *dest++); 1216059Samurai } 12228679Sbrian } 12328679Sbrian return (dest - orgdest); 1246059Samurai} 1256059Samurai 12631514Sbrianstatic void 12736285SbrianPred1Term(void *v) 1286059Samurai{ 12936285Sbrian struct pred1_state *state = (struct pred1_state *)v; 13036285Sbrian free(state); 13131514Sbrian} 13231514Sbrian 13331514Sbrianstatic void 13436285SbrianPred1ResetInput(void *v) 13531514Sbrian{ 13636285Sbrian struct pred1_state *state = (struct pred1_state *)v; 13736285Sbrian state->hash = 0; 13836285Sbrian memset(state->dict, '\0', sizeof state->dict); 13936285Sbrian log_Printf(LogCCP, "Predictor1: Input channel reset\n"); 1406059Samurai} 1416059Samurai 14278411Sbrianstatic int 14336285SbrianPred1ResetOutput(void *v) 14431514Sbrian{ 14536285Sbrian struct pred1_state *state = (struct pred1_state *)v; 14636285Sbrian state->hash = 0; 14736285Sbrian memset(state->dict, '\0', sizeof state->dict); 14836285Sbrian log_Printf(LogCCP, "Predictor1: Output channel reset\n"); 14978411Sbrian 15078411Sbrian return 1; /* Ask FSM to ACK */ 15131514Sbrian} 15231514Sbrian 15336285Sbrianstatic void * 15436285SbrianPred1InitInput(struct lcp_opt *o) 15531514Sbrian{ 15636285Sbrian struct pred1_state *state; 15736285Sbrian state = (struct pred1_state *)malloc(sizeof(struct pred1_state)); 15836285Sbrian if (state != NULL) 15936285Sbrian Pred1ResetInput(state); 16036285Sbrian return state; 16131514Sbrian} 16231514Sbrian 16336285Sbrianstatic void * 16436285SbrianPred1InitOutput(struct lcp_opt *o) 16531514Sbrian{ 16636285Sbrian struct pred1_state *state; 16736285Sbrian state = (struct pred1_state *)malloc(sizeof(struct pred1_state)); 16836285Sbrian if (state != NULL) 16936285Sbrian Pred1ResetOutput(state); 17036285Sbrian return state; 17131514Sbrian} 17231514Sbrian 17346686Sbrianstatic struct mbuf * 17446686SbrianPred1Output(void *v, struct ccp *ccp, struct link *l, int pri, u_short *proto, 17536285Sbrian struct mbuf *bp) 17631514Sbrian{ 17736285Sbrian struct pred1_state *state = (struct pred1_state *)v; 1786059Samurai struct mbuf *mwp; 1796059Samurai u_char *cp, *wp, *hp; 1806059Samurai int orglen, len; 18128679Sbrian u_char bufp[MAX_MTU + 2]; 1826059Samurai u_short fcs; 1836059Samurai 18454912Sbrian orglen = m_length(bp) + 2; /* add count of proto */ 18554912Sbrian mwp = m_get((orglen + 2) / 8 * 9 + 12, MB_CCPOUT); 1866059Samurai hp = wp = MBUF_CTOP(mwp); 1876059Samurai cp = bufp; 1886059Samurai *wp++ = *cp++ = orglen >> 8; 1896059Samurai *wp++ = *cp++ = orglen & 0377; 19046686Sbrian *cp++ = *proto >> 8; 19146686Sbrian *cp++ = *proto & 0377; 19236285Sbrian mbuf_Read(bp, cp, orglen - 2); 19346686Sbrian fcs = hdlc_Fcs(bufp, 2 + orglen); 1946059Samurai fcs = ~fcs; 1956059Samurai 19636285Sbrian len = compress(state, bufp + 2, wp, orglen); 19736285Sbrian log_Printf(LogDEBUG, "Pred1Output: orglen (%d) --> len (%d)\n", orglen, len); 19836285Sbrian ccp->uncompout += orglen; 1996059Samurai if (len < orglen) { 2006059Samurai *hp |= 0x80; 2016059Samurai wp += len; 20236285Sbrian ccp->compout += len; 2036059Samurai } else { 20430715Sbrian memcpy(wp, bufp + 2, orglen); 2056059Samurai wp += orglen; 20636285Sbrian ccp->compout += orglen; 2076059Samurai } 2086059Samurai 2096059Samurai *wp++ = fcs & 0377; 2106059Samurai *wp++ = fcs >> 8; 21154912Sbrian mwp->m_len = wp - MBUF_CTOP(mwp); 21246686Sbrian *proto = ccp_Proto(ccp); 21346686Sbrian return mwp; 2146059Samurai} 2156059Samurai 21631514Sbrianstatic struct mbuf * 21736285SbrianPred1Input(void *v, struct ccp *ccp, u_short *proto, struct mbuf *bp) 2186059Samurai{ 21936285Sbrian struct pred1_state *state = (struct pred1_state *)v; 2206059Samurai u_char *cp, *pp; 2216059Samurai int len, olen, len1; 2226059Samurai struct mbuf *wp; 2236059Samurai u_char *bufp; 22431514Sbrian u_short fcs; 2256059Samurai 22654912Sbrian wp = m_get(MAX_MRU + 2, MB_CCPIN); 2276059Samurai cp = MBUF_CTOP(bp); 22854912Sbrian olen = m_length(bp); 2296059Samurai pp = bufp = MBUF_CTOP(wp); 2306059Samurai *pp++ = *cp & 0177; 2316059Samurai len = *cp++ << 8; 2326059Samurai *pp++ = *cp; 2336059Samurai len += *cp++; 23436285Sbrian ccp->uncompin += len & 0x7fff; 2356059Samurai if (len & 0x8000) { 23636285Sbrian len1 = decompress(state, cp, pp, olen - 4); 23736285Sbrian ccp->compin += olen; 2386059Samurai len &= 0x7fff; 23928679Sbrian if (len != len1) { /* Error is detected. Send reset request */ 24044650Sbrian log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len1, len); 24144650Sbrian fsm_Reopen(&ccp->fsm); 24254912Sbrian m_freem(bp); 24354912Sbrian m_freem(wp); 24431514Sbrian return NULL; 2456059Samurai } 2466059Samurai cp += olen - 4; 2476059Samurai pp += len1; 24844792Sbrian } else if (len + 4 != olen) { 24944792Sbrian log_Printf(LogCCP, "Pred1: Length error (got %d, not %d)\n", len + 4, olen); 25044792Sbrian fsm_Reopen(&ccp->fsm); 25154912Sbrian m_freem(wp); 25254912Sbrian m_freem(bp); 25344792Sbrian return NULL; 2546059Samurai } else { 25536285Sbrian ccp->compin += len; 25636285Sbrian SyncTable(state, cp, pp, len); 2576059Samurai cp += len; 2586059Samurai pp += len; 2596059Samurai } 26028679Sbrian *pp++ = *cp++; /* CRC */ 2616059Samurai *pp++ = *cp++; 26254912Sbrian fcs = hdlc_Fcs(bufp, wp->m_len = pp - bufp); 2636059Samurai if (fcs == GOODFCS) { 26454912Sbrian wp->m_offset += 2; /* skip length */ 26554912Sbrian wp->m_len -= 4; /* skip length & CRC */ 2666059Samurai pp = MBUF_CTOP(wp); 26731514Sbrian *proto = *pp++; 26831514Sbrian if (*proto & 1) { 26954912Sbrian wp->m_offset++; 27054912Sbrian wp->m_len--; 2716059Samurai } else { 27254912Sbrian wp->m_offset += 2; 27354912Sbrian wp->m_len -= 2; 27431514Sbrian *proto = (*proto << 8) | *pp++; 2756059Samurai } 27654912Sbrian m_freem(bp); 27731514Sbrian return wp; 27828679Sbrian } else { 27944792Sbrian const char *pre = *MBUF_CTOP(bp) & 0x80 ? "" : "un"; 28044792Sbrian log_Printf(LogDEBUG, "Pred1Input: fcs = 0x%04x (%scompressed), len = 0x%x," 28144792Sbrian " olen = 0x%x\n", fcs, pre, len, olen); 28244792Sbrian log_Printf(LogCCP, "%s: Bad %scompressed CRC-16\n", 28344792Sbrian ccp->fsm.link->name, pre); 28444650Sbrian fsm_Reopen(&ccp->fsm); 28554912Sbrian m_freem(wp); 2866059Samurai } 28754912Sbrian m_freem(bp); 28831514Sbrian return NULL; 2896059Samurai} 29031514Sbrian 29131514Sbrianstatic void 29246828SbrianPred1DictSetup(void *v, struct ccp *ccp, u_short proto, struct mbuf *bp) 29331514Sbrian{ 29431514Sbrian} 29531514Sbrian 29631514Sbrianstatic const char * 29731514SbrianPred1DispOpts(struct lcp_opt *o) 29831514Sbrian{ 29931514Sbrian return NULL; 30031514Sbrian} 30131514Sbrian 30231514Sbrianstatic void 30336285SbrianPred1InitOptsOutput(struct lcp_opt *o, const struct ccp_config *cfg) 30431514Sbrian{ 30531514Sbrian o->len = 2; 30631514Sbrian} 30731514Sbrian 30831514Sbrianstatic int 30978411SbrianPred1SetOptsOutput(struct lcp_opt *o, const struct ccp_config *cfg) 31031514Sbrian{ 31136285Sbrian if (o->len != 2) { 31236285Sbrian o->len = 2; 31331514Sbrian return MODE_NAK; 31431514Sbrian } 31531514Sbrian return MODE_ACK; 31631514Sbrian} 31731514Sbrian 31836285Sbrianstatic int 31936285SbrianPred1SetOptsInput(struct lcp_opt *o, const struct ccp_config *cfg) 32036285Sbrian{ 32178411Sbrian if (o->len != 2) { 32278411Sbrian o->len = 2; 32378411Sbrian return MODE_NAK; 32478411Sbrian } 32578411Sbrian return MODE_ACK; 32636285Sbrian} 32736285Sbrian 32831514Sbrianconst struct ccp_algorithm Pred1Algorithm = { 32931514Sbrian TY_PRED1, 33036285Sbrian CCP_NEG_PRED1, 33131514Sbrian Pred1DispOpts, 33278411Sbrian ccp_DefaultUsable, 33378411Sbrian ccp_DefaultRequired, 33431514Sbrian { 33536285Sbrian Pred1SetOptsInput, 33631514Sbrian Pred1InitInput, 33736285Sbrian Pred1Term, 33831514Sbrian Pred1ResetInput, 33931514Sbrian Pred1Input, 34031514Sbrian Pred1DictSetup 34131514Sbrian }, 34231514Sbrian { 34379165Sbrian 0, 34436285Sbrian Pred1InitOptsOutput, 34536285Sbrian Pred1SetOptsOutput, 34631514Sbrian Pred1InitOutput, 34736285Sbrian Pred1Term, 34831514Sbrian Pred1ResetOutput, 34931514Sbrian Pred1Output 35031514Sbrian }, 35131514Sbrian}; 352