1 /* 2 * Written by Toshiharu OHNO (tony-o@iij.ad.jp) 3 * 4 * Copyright (C) 1993, Internet Initiative Japan, Inc. All rights reserverd. 5 * 6 * Redistribution and use in source and binary forms are permitted 7 * provided that the above copyright notice and this paragraph are 8 * duplicated in all such forms and that any documentation, 9 * advertising materials, and other materials related to such 10 * distribution and use acknowledge that the software was developed 11 * by the Internet Initiative Japan. The name of the 12 * IIJ may not be used to endorse or promote products derived 13 * from this software without specific prior written permission. 14 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 15 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 16 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 17 * 18 * $Id:$ 19 * 20 * TODO: 21 */ 22 23 #include "fsm.h" 24 #include "hdlc.h" 25 #include "lcpproto.h" 26 #include "ccp.h" 27 28 /* 29 * pred.c -- Test program for Dave Rand's rendition of the 30 * predictor algorithm 31 * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) 32 * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de> 33 * Original : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com> 34 */ 35 36 /* The following hash code is the heart of the algorithm: 37 * It builds a sliding hash sum of the previous 3-and-a-bit characters 38 * which will be used to index the guess table. 39 * A better hash function would result in additional compression, 40 * at the expense of time. 41 */ 42 #define IHASH(x) iHash = (iHash << 4) ^ (x) 43 #define OHASH(x) oHash = (oHash << 4) ^ (x) 44 45 static unsigned short int iHash, oHash; 46 static unsigned char InputGuessTable[65536]; 47 static unsigned char OutputGuessTable[65536]; 48 49 static int 50 compress(source, dest, len) 51 unsigned char *source, *dest; 52 int len; 53 { 54 int i, bitmask; 55 unsigned char *flagdest, flags, *orgdest; 56 57 orgdest = dest; 58 while (len) { 59 flagdest = dest++; flags = 0; /* All guess wrong initially */ 60 for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) { 61 if (OutputGuessTable[oHash] == *source) { 62 flags |= bitmask; /* Guess was right - don't output */ 63 } else { 64 OutputGuessTable[oHash] = *source; 65 *dest++ = *source; /* Guess wrong, output char */ 66 } 67 OHASH(*source++);len--; 68 } 69 *flagdest = flags; 70 } 71 return(dest - orgdest); 72 } 73 74 static void 75 SyncTable(source, dest, len) 76 unsigned char *source, *dest; 77 int len; 78 { 79 int i; 80 81 while (len--) { 82 if (InputGuessTable[iHash] != *source) { 83 InputGuessTable[iHash] = *source; 84 } 85 IHASH(*dest++ = *source++); 86 } 87 } 88 89 static int 90 decompress(source, dest, len) 91 unsigned char *source, *dest; 92 int len; 93 { 94 int i, bitmask; 95 unsigned char flags, *orgdest; 96 97 orgdest = dest; 98 while (len) { 99 flags = *source++; 100 len--; 101 for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 102 if (flags & bitmask) { 103 *dest = InputGuessTable[iHash]; /* Guess correct */ 104 } else { 105 if (!len) 106 break; /* we seem to be really done -- cabo */ 107 InputGuessTable[iHash] = *source; /* Guess wrong */ 108 *dest = *source++; /* Read from source */ 109 len--; 110 } 111 IHASH(*dest++); 112 } 113 } 114 return(dest - orgdest); 115 } 116 117 #define SIZ1 2048 118 119 void 120 Pred1Init(direction) 121 int direction; 122 { 123 if (direction & 1) { /* Input part */ 124 iHash = 0; 125 bzero(InputGuessTable, sizeof(InputGuessTable)); 126 } 127 if (direction & 2) { /* Output part */ 128 oHash = 0; 129 bzero(OutputGuessTable, sizeof(OutputGuessTable)); 130 } 131 } 132 133 void 134 Pred1Output(pri, proto, bp) 135 int pri; 136 u_short proto; 137 struct mbuf *bp; 138 { 139 struct mbuf *mwp; 140 u_char *cp, *wp, *hp; 141 int orglen, len; 142 u_char bufp[SIZ1]; 143 u_short fcs; 144 145 orglen = plength(bp) + 2; /* add count of proto */ 146 mwp = mballoc((orglen+2)/8*9+12, MB_HDLCOUT); 147 hp = wp = MBUF_CTOP(mwp); 148 cp = bufp; 149 *wp++ = *cp++ = orglen >> 8; 150 *wp++ = *cp++ = orglen & 0377; 151 *cp++ = proto >> 8; 152 *cp++ = proto & 0377; 153 mbread(bp, cp, orglen-2); 154 fcs = HdlcFcs(INITFCS, bufp, 2+orglen); 155 fcs = ~fcs; 156 157 len = compress(bufp + 2, wp, orglen); 158 #ifdef DEBUG 159 logprintf("orglen (%d) --> len (%d)\n", orglen, len); 160 #endif 161 CcpInfo.orgout += orglen; 162 if (len < orglen) { 163 *hp |= 0x80; 164 wp += len; 165 CcpInfo.compout += len; 166 } else { 167 bcopy(bufp+2, wp, orglen); 168 wp += orglen; 169 CcpInfo.compout += orglen; 170 } 171 172 *wp++ = fcs & 0377; 173 *wp++ = fcs >> 8; 174 mwp->cnt = wp - MBUF_CTOP(mwp); 175 HdlcOutput(pri, PROTO_COMPD, mwp); 176 } 177 178 void 179 Pred1Input(bp) 180 struct mbuf *bp; 181 { 182 u_char *cp, *pp; 183 int len, olen, len1; 184 struct mbuf *wp; 185 u_char *bufp; 186 u_short fcs, proto; 187 188 wp = mballoc(SIZ1, MB_IPIN); 189 cp = MBUF_CTOP(bp); 190 olen = plength(bp); 191 pp = bufp = MBUF_CTOP(wp); 192 *pp++ = *cp & 0177; 193 len = *cp++ << 8; 194 *pp++ = *cp; 195 len += *cp++; 196 CcpInfo.orgin += len & 0x7fff; 197 if (len & 0x8000) { 198 len1 = decompress(cp, pp, olen - 4); 199 CcpInfo.compin += olen; 200 len &= 0x7fff; 201 if (len != len1) { /* Error is detected. Send reset request */ 202 CcpSendResetReq(&CcpFsm); 203 pfree(bp); 204 return; 205 } 206 cp += olen - 4; 207 pp += len1; 208 } else { 209 CcpInfo.compin += len; 210 SyncTable(cp, pp, len); 211 cp += len; 212 pp += len; 213 } 214 *pp++ = *cp++; /* CRC */ 215 *pp++ = *cp++; 216 fcs = HdlcFcs(INITFCS, bufp, wp->cnt = pp - bufp); 217 #ifdef DEBUG 218 logprintf("fcs = %04x (%s), len = %x, olen = %x\n", 219 fcs, (fcs == GOODFCS)? "good" : "bad", len, olen); 220 #endif 221 if (fcs == GOODFCS) { 222 wp->offset += 2; /* skip length */ 223 wp->cnt -= 4; /* skip length & CRC */ 224 pp = MBUF_CTOP(wp); 225 proto = *pp++; 226 if (proto & 1) { 227 wp->offset++; 228 wp->cnt--; 229 } else { 230 wp->offset += 2; 231 wp->cnt -= 2; 232 proto = (proto << 8) | *pp++; 233 } 234 DecodePacket(proto, wp); 235 } 236 pfree(bp); 237 } 238