Annotation of embedaddon/mpd/src/ccp_pred1.c, revision 1.1.1.1
1.1 misho 1:
2: /*
3: * ccp_pred1.c
4: *
5: * Rewritten by Alexander Motin <mav@FreeBSD.org>
6: * Written by Archie Cobbs <archie@freebsd.org>
7: * Copyright (c) 1995-1999 Whistle Communications, Inc. All rights reserved.
8: * See ``COPYRIGHT.whistle''
9: */
10:
11: /*
12: * pred1.c
13: *
14: * Test program for Dave Rand's rendition of the predictor algorithm
15: *
16: * Updated by: archie@freebsd.org (Archie Cobbs)
17: * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson)
18: * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de>
19: * Original : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
20: */
21:
22: #include "ppp.h"
23: #include "ccp.h"
24: #include "util.h"
25: #include "ngfunc.h"
26:
27: #ifdef USE_NG_PRED1
28: #include <netgraph/ng_message.h>
29: #include <netgraph.h>
30: #endif
31:
32: /*
33: * DEFINITIONS
34: */
35:
36: #define PRED1_DECOMP_BUF_SIZE 4096
37:
38: #define PRED1_MAX_BLOWUP(n) ((n) * 9 / 8 + 24)
39:
40: /*
41: * The following hash code is the heart of the algorithm:
42: * It builds a sliding hash sum of the previous 3-and-a-bit characters
43: * which will be used to index the guess table.
44: * A better hash function would result in additional compression,
45: * at the expense of time.
46: */
47:
48: #define IHASH(x) p->iHash = (p->iHash << 4) ^ (x)
49: #define OHASH(x) p->oHash = (p->oHash << 4) ^ (x)
50:
51: /*
52: * INTERNAL FUNCTIONS
53: */
54:
55: static int Pred1Init(Bund b, int direction);
56: static void Pred1Cleanup(Bund b, int direction);
57: #ifndef USE_NG_PRED1
58: static Mbuf Pred1Compress(Bund b, Mbuf plain);
59: static Mbuf Pred1Decompress(Bund b, Mbuf comp);
60: #endif
61:
62: static u_char *Pred1BuildConfigReq(Bund b, u_char *cp, int *ok);
63: static void Pred1DecodeConfigReq(Fsm fp, FsmOption opt, int mode);
64: static Mbuf Pred1RecvResetReq(Bund b, int id, Mbuf bp, int *noAck);
65: static Mbuf Pred1SendResetReq(Bund b);
66: static void Pred1RecvResetAck(Bund b, int id, Mbuf bp);
67: static int Pred1Negotiated(Bund b, int xmit);
68: static int Pred1SubtractBloat(Bund b, int size);
69: static int Pred1Stat(Context ctx, int dir);
70:
71: #ifndef USE_NG_PRED1
72: static int Compress(Bund b, u_char *source, u_char *dest, int len);
73: static int Decompress(Bund b, u_char *source, u_char *dest, int slen, int dlen);
74: static void SyncTable(Bund b, u_char *source, u_char *dest, int len);
75: #endif
76:
77: /*
78: * GLOBAL VARIABLES
79: */
80:
81: const struct comptype gCompPred1Info =
82: {
83: "pred1",
84: CCP_TY_PRED1,
85: 1,
86: Pred1Init,
87: NULL,
88: NULL,
89: NULL,
90: Pred1SubtractBloat,
91: Pred1Cleanup,
92: Pred1BuildConfigReq,
93: Pred1DecodeConfigReq,
94: Pred1SendResetReq,
95: Pred1RecvResetReq,
96: Pred1RecvResetAck,
97: Pred1Negotiated,
98: Pred1Stat,
99: #ifndef USE_NG_PRED1
100: Pred1Compress,
101: Pred1Decompress,
102: #else
103: NULL,
104: NULL,
105: #endif
106: };
107:
108: /*
109: * Pred1Init()
110: */
111:
112: static int
113: Pred1Init(Bund b, int dir)
114: {
115: #ifndef USE_NG_PRED1
116: Pred1Info p = &b->ccp.pred1;
117:
118: if (dir == COMP_DIR_XMIT) {
119: p->oHash = 0;
120: p->OutputGuessTable = Malloc(MB_COMP, PRED1_TABLE_SIZE);
121: } else {
122: p->iHash = 0;
123: p->InputGuessTable = Malloc(MB_COMP, PRED1_TABLE_SIZE);
124: }
125: #else
126: struct ngm_mkpeer mp;
127: struct ng_pred1_config conf;
128: const char *pred1hook, *ppphook;
129: char path[NG_PATHSIZ];
130: ng_ID_t id;
131:
132: memset(&conf, 0, sizeof(conf));
133: conf.enable = 1;
134: if (dir == COMP_DIR_XMIT) {
135: ppphook = NG_PPP_HOOK_COMPRESS;
136: pred1hook = NG_PRED1_HOOK_COMP;
137: } else {
138: ppphook = NG_PPP_HOOK_DECOMPRESS;
139: pred1hook = NG_PRED1_HOOK_DECOMP;
140: }
141:
142: /* Attach a new PRED1 node to the PPP node */
143: snprintf(path, sizeof(path), "[%x]:", b->nodeID);
144: strcpy(mp.type, NG_PRED1_NODE_TYPE);
145: strcpy(mp.ourhook, ppphook);
146: strcpy(mp.peerhook, pred1hook);
147: if (NgSendMsg(gCcpCsock, path,
148: NGM_GENERIC_COOKIE, NGM_MKPEER, &mp, sizeof(mp)) < 0) {
149: Perror("[%s] can't create %s node", b->name, mp.type);
150: return(-1);
151: }
152:
153: strlcat(path, ppphook, sizeof(path));
154:
155: id = NgGetNodeID(-1, path);
156: if (dir == COMP_DIR_XMIT) {
157: b->ccp.comp_node_id = id;
158: } else {
159: b->ccp.decomp_node_id = id;
160: }
161:
162: /* Configure PRED1 node */
163: snprintf(path, sizeof(path), "[%x]:", id);
164: if (NgSendMsg(gCcpCsock, path,
165: NGM_PRED1_COOKIE, NGM_PRED1_CONFIG, &conf, sizeof(conf)) < 0) {
166: Perror("[%s] can't config %s node at %s",
167: b->name, NG_PRED1_NODE_TYPE, path);
168: NgFuncShutdownNode(gCcpCsock, b->name, path);
169: return(-1);
170: }
171: #endif
172: return 0;
173: }
174:
175: /*
176: * Pred1Cleanup()
177: */
178:
179: void
180: Pred1Cleanup(Bund b, int dir)
181: {
182: #ifndef USE_NG_PRED1
183: Pred1Info p = &b->ccp.pred1;
184:
185: if (dir == COMP_DIR_XMIT) {
186: assert(p->OutputGuessTable);
187: Freee(p->OutputGuessTable);
188: p->OutputGuessTable = NULL;
189: memset(&p->xmit_stats, 0, sizeof(p->xmit_stats));
190: } else {
191: assert(p->InputGuessTable);
192: Freee(p->InputGuessTable);
193: p->InputGuessTable = NULL;
194: memset(&p->recv_stats, 0, sizeof(p->recv_stats));
195: }
196: #else
197: char path[NG_PATHSIZ];
198:
199: /* Remove node */
200: if (dir == COMP_DIR_XMIT) {
201: snprintf(path, sizeof(path), "[%x]:", b->ccp.comp_node_id);
202: b->ccp.comp_node_id = 0;
203: } else {
204: snprintf(path, sizeof(path), "[%x]:", b->ccp.decomp_node_id);
205: b->ccp.decomp_node_id = 0;
206: }
207: NgFuncShutdownNode(gCcpCsock, b->name, path);
208: #endif
209: }
210:
211: #ifndef USE_NG_PRED1
212: /*
213: * Pred1Compress()
214: *
215: * Compress a packet and return a compressed version.
216: * The original is untouched.
217: */
218:
219: Mbuf
220: Pred1Compress(Bund b, Mbuf plain)
221: {
222: u_char *wp, *uncomp, *comp;
223: u_int16_t fcs;
224: int len;
225: Mbuf res;
226: int orglen;
227: Pred1Info p = &b->ccp.pred1;
228:
229: orglen = MBLEN(plain);
230: uncomp = MBDATA(plain);
231:
232: p->xmit_stats.InOctets += orglen;
233: p->xmit_stats.FramesPlain++;
234:
235: res = mballoc(PRED1_MAX_BLOWUP(orglen + 2));
236: comp = MBDATA(res);
237:
238: wp = comp;
239:
240: *wp++ = (orglen >> 8) & 0x7F;
241: *wp++ = orglen & 0xFF;
242:
243: /* Compute FCS */
244:
245: fcs = Crc16(PPP_INITFCS, comp, 2);
246: fcs = Crc16(fcs, uncomp, orglen);
247: fcs = ~fcs;
248:
249: /* Compress data */
250:
251: len = Compress(b, uncomp, wp, orglen);
252:
253: /* What happened? */
254:
255: if (len < orglen)
256: {
257: *comp |= 0x80;
258: wp += len;
259: p->xmit_stats.FramesComp++;
260: }
261: else
262: {
263: memcpy(wp, uncomp, orglen);
264: wp += orglen;
265: p->xmit_stats.FramesUncomp++;
266: }
267:
268: /* Add FCS */
269:
270: *wp++ = fcs & 0xFF;
271: *wp++ = fcs >> 8;
272:
273: res->cnt = (wp - comp);
274:
275: mbfree(plain);
276: Log(LG_CCP2, ("[%s] Pred1: orig (%d) --> comp (%d)", b->name, orglen, res->cnt));
277:
278: p->xmit_stats.OutOctets += res->cnt;
279:
280: return res;
281: }
282:
283: /*
284: * Pred1Decompress()
285: *
286: * Decompress a packet and return a compressed version.
287: * The original is untouched.
288: */
289:
290: Mbuf
291: Pred1Decompress(Bund b, Mbuf mbcomp)
292: {
293: u_char *uncomp, *comp;
294: u_char *cp;
295: u_int16_t len, len1, cf, lenn;
296: u_int16_t fcs;
297: int orglen;
298: Mbuf mbuncomp;
299: Pred1Info p = &b->ccp.pred1;
300:
301: orglen = MBLEN(mbcomp);
302: comp = MBDATA(mbcomp);
303: cp = comp;
304:
305: p->recv_stats.InOctets += orglen;
306:
307: mbuncomp = mballoc(PRED1_DECOMP_BUF_SIZE);
308: uncomp = MBDATA(mbuncomp);
309:
310: /* Get initial length value */
311: len = *cp++ << 8;
312: len += *cp++;
313:
314: cf = (len & 0x8000);
315: len &= 0x7fff;
316:
317: /* Is data compressed or not really? */
318: if (cf)
319: {
320: p->recv_stats.FramesComp++;
321: len1 = Decompress(b, cp, uncomp, orglen - 4, PRED1_DECOMP_BUF_SIZE);
322: if (len != len1) /* Error is detected. Send reset request */
323: {
324: Log(LG_CCP2, ("[%s] Length error (%d) --> len (%d)", b->name, len, len1));
325: p->recv_stats.Errors++;
326: mbfree(mbcomp);
327: mbfree(mbuncomp);
328: CcpSendResetReq(b);
329: return NULL;
330: }
331: cp += orglen - 4;
332: }
333: else
334: {
335: p->recv_stats.FramesUncomp++;
336: SyncTable(b, cp, uncomp, len);
337: cp += len;
338: }
339:
340: mbuncomp->cnt = len;
341:
342: /* Check CRC */
343: lenn = htons(len);
344: fcs = Crc16(PPP_INITFCS, (u_char *)&lenn, 2);
345: fcs = Crc16(fcs, uncomp, len);
346: fcs = Crc16(fcs, cp, 2);
347:
348: #ifdef DEBUG
349: if (fcs != PPP_GOODFCS)
350: Log(LG_CCP2, ("fcs = %04x (%s), len = %x, olen = %x",
351: fcs, (fcs == PPP_GOODFCS)? "good" : "bad", len, orglen));
352: #endif
353:
354: if (fcs != PPP_GOODFCS)
355: {
356: Log(LG_CCP2, ("[%s] Pred1: Bad CRC-16", b->name));
357: p->recv_stats.Errors++;
358: mbfree(mbcomp);
359: mbfree(mbuncomp);
360: CcpSendResetReq(b);
361: return NULL;
362: }
363:
364: Log(LG_CCP2, ("[%s] Pred1: orig (%d) <-- comp (%d)", b->name, mbuncomp->cnt, orglen));
365: mbfree(mbcomp);
366:
367: p->recv_stats.FramesPlain++;
368: p->recv_stats.OutOctets += mbuncomp->cnt;
369:
370: return mbuncomp;
371: }
372: #endif
373:
374: /*
375: * Pred1RecvResetReq()
376: */
377:
378: static Mbuf
379: Pred1RecvResetReq(Bund b, int id, Mbuf bp, int *noAck)
380: {
381: #ifndef USE_NG_PRED1
382: Pred1Info p = &b->ccp.pred1;
383: Pred1Init(b, COMP_DIR_XMIT);
384: p->xmit_stats.Errors++;
385: #else
386: char path[NG_PATHSIZ];
387: /* Forward ResetReq to the Predictor1 compression node */
388: snprintf(path, sizeof(path), "[%x]:", b->ccp.comp_node_id);
389: if (NgSendMsg(gCcpCsock, path,
390: NGM_PRED1_COOKIE, NGM_PRED1_RESETREQ, NULL, 0) < 0) {
391: Perror("[%s] reset to %s node", b->name, NG_PRED1_NODE_TYPE);
392: }
393: #endif
394: return(NULL);
395: }
396:
397: /*
398: * Pred1SendResetReq()
399: */
400:
401: static Mbuf
402: Pred1SendResetReq(Bund b)
403: {
404: #ifndef USE_NG_PRED1
405: Pred1Init(b, COMP_DIR_RECV);
406: #endif
407: return(NULL);
408: }
409:
410: /*
411: * Pred1RecvResetAck()
412: */
413:
414: static void
415: Pred1RecvResetAck(Bund b, int id, Mbuf bp)
416: {
417: #ifndef USE_NG_PRED1
418: Pred1Init(b, COMP_DIR_RECV);
419: #else
420: char path[NG_PATHSIZ];
421: /* Forward ResetReq to the Predictor1 decompression node */
422: snprintf(path, sizeof(path), "[%x]:", b->ccp.decomp_node_id);
423: if (NgSendMsg(gCcpCsock, path,
424: NGM_PRED1_COOKIE, NGM_PRED1_RESETREQ, NULL, 0) < 0) {
425: Perror("[%s] reset to %s node", b->name, NG_PRED1_NODE_TYPE);
426: }
427: #endif
428: }
429:
430: /*
431: * Pred1BuildConfigReq()
432: */
433:
434: static u_char *
435: Pred1BuildConfigReq(Bund b, u_char *cp, int *ok)
436: {
437: cp = FsmConfValue(cp, CCP_TY_PRED1, 0, NULL);
438: *ok = 1;
439: return (cp);
440: }
441:
442: /*
443: * Pred1DecodeConfigReq()
444: */
445:
446: static void
447: Pred1DecodeConfigReq(Fsm fp, FsmOption opt, int mode)
448: {
449: /* Deal with it */
450: switch (mode) {
451: case MODE_REQ:
452: FsmAck(fp, opt);
453: break;
454:
455: case MODE_NAK:
456: break;
457: }
458: }
459:
460: /*
461: * Pred1Negotiated()
462: */
463:
464: static int
465: Pred1Negotiated(Bund b, int dir)
466: {
467: return 1;
468: }
469:
470: /*
471: * Pred1SubtractBloat()
472: */
473:
474: static int
475: Pred1SubtractBloat(Bund b, int size)
476: {
477: return(size - 4);
478: }
479:
480: static int
481: Pred1Stat(Context ctx, int dir)
482: {
483: #ifndef USE_NG_PRED1
484: Pred1Info p = &ctx->bund->ccp.pred1;
485:
486: switch (dir) {
487: case COMP_DIR_XMIT:
488: Printf("\tBytes\t: %llu -> %llu (%+lld%%)\r\n",
489: (unsigned long long)p->xmit_stats.InOctets,
490: (unsigned long long)p->xmit_stats.OutOctets,
491: ((p->xmit_stats.InOctets!=0)?
492: ((long long)(p->xmit_stats.OutOctets - p->xmit_stats.InOctets)
493: *100/(long long)p->xmit_stats.InOctets):
494: 0));
495: Printf("\tFrames\t: %llu -> %lluc + %lluu\r\n",
496: (unsigned long long)p->xmit_stats.FramesPlain,
497: (unsigned long long)p->xmit_stats.FramesComp,
498: (unsigned long long)p->xmit_stats.FramesUncomp);
499: Printf("\tErrors\t: %llu\r\n",
500: (unsigned long long)p->recv_stats.Errors);
501: break;
502: case COMP_DIR_RECV:
503: Printf("\tBytes\t: %llu <- %llu (%+lld%%)\r\n",
504: (unsigned long long)p->recv_stats.OutOctets,
505: (unsigned long long)p->recv_stats.InOctets,
506: ((p->recv_stats.OutOctets!=0)?
507: ((long long)(p->recv_stats.InOctets - p->recv_stats.OutOctets)
508: *100/(long long)p->recv_stats.OutOctets):
509: 0));
510: Printf("\tFrames\t: %llu <- %lluc + %lluu\r\n",
511: (unsigned long long)p->xmit_stats.FramesPlain,
512: (unsigned long long)p->xmit_stats.FramesComp,
513: (unsigned long long)p->xmit_stats.FramesUncomp);
514: Printf("\tErrors\t: %llu\r\n",
515: (unsigned long long)p->recv_stats.Errors);
516: break;
517: default:
518: assert(0);
519: }
520: return (0);
521: #else
522: Bund b = ctx->bund;
523: char path[NG_PATHSIZ];
524: struct ng_pred1_stats stats;
525: union {
526: u_char buf[sizeof(struct ng_mesg) + sizeof(stats)];
527: struct ng_mesg reply;
528: } u;
529:
530: switch (dir) {
531: case COMP_DIR_XMIT:
532: snprintf(path, sizeof(path), "mpd%d-%s:%s", gPid, b->name,
533: NG_PPP_HOOK_COMPRESS);
534: break;
535: case COMP_DIR_RECV:
536: snprintf(path, sizeof(path), "mpd%d-%s:%s", gPid, b->name,
537: NG_PPP_HOOK_DECOMPRESS);
538: break;
539: default:
540: assert(0);
541: }
542: if (NgFuncSendQuery(path, NGM_PRED1_COOKIE, NGM_PRED1_GET_STATS, NULL, 0,
543: &u.reply, sizeof(u), NULL) < 0) {
544: Perror("[%s] can't get %s stats", b->name, NG_PRED1_NODE_TYPE);
545: return(0);
546: }
547: memcpy(&stats, u.reply.data, sizeof(stats));
548: switch (dir) {
549: case COMP_DIR_XMIT:
550: Printf("\tBytes\t: %llu -> %llu (%+lld%%)\r\n",
551: stats.InOctets,
552: stats.OutOctets,
553: ((stats.InOctets!=0)?
554: ((int64_t)(stats.OutOctets - stats.InOctets)*100/(int64_t)stats.InOctets):
555: 0));
556: Printf("\tFrames\t: %llu -> %lluc + %lluu\r\n",
557: stats.FramesPlain,
558: stats.FramesComp,
559: stats.FramesUncomp);
560: Printf("\tErrors\t: %llu\r\n",
561: stats.Errors);
562: break;
563: case COMP_DIR_RECV:
564: Printf("\tBytes\t: %llu <- %llu (%+lld%%)\r\n",
565: stats.OutOctets,
566: stats.InOctets,
567: ((stats.OutOctets!=0)?
568: ((int64_t)(stats.InOctets - stats.OutOctets)*100/(int64_t)stats.OutOctets):
569: 0));
570: Printf("\tFrames\t: %llu <- %lluc + %lluu\r\n",
571: stats.FramesPlain,
572: stats.FramesComp,
573: stats.FramesUncomp);
574: Printf("\tErrors\t: %llu\r\n",
575: stats.Errors);
576: break;
577: default:
578: assert(0);
579: }
580: return (0);
581: #endif
582: }
583:
584: #ifndef USE_NG_PRED1
585: /*
586: * Compress()
587: */
588:
589: static int
590: Compress(Bund b, u_char *source, u_char *dest, int len)
591: {
592: Pred1Info p = &b->ccp.pred1;
593: int i, bitmask;
594: u_char flags;
595: u_char *flagdest, *orgdest;
596:
597: orgdest = dest;
598: while (len)
599: {
600: flagdest = dest++; flags = 0; /* All guess wrong initially */
601: for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
602: if (p->OutputGuessTable[p->oHash] == *source)
603: flags |= bitmask; /* Guess was right - don't output */
604: else
605: {
606: p->OutputGuessTable[p->oHash] = *source;
607: *dest++ = *source; /* Guess wrong, output char */
608: }
609: OHASH(*source++);
610: len--;
611: }
612: *flagdest = flags;
613: }
614: return(dest - orgdest);
615: }
616:
617: /*
618: * Decompress()
619: *
620: * Returns decompressed size, or -1 if we ran out of space
621: */
622:
623: static int
624: Decompress(Bund b, u_char *source, u_char *dest, int slen, int dlen)
625: {
626: Pred1Info p = &b->ccp.pred1;
627: int i, bitmask;
628: u_char flags, *orgdest;
629:
630: orgdest = dest;
631: while (slen)
632: {
633: flags = *source++;
634: slen--;
635: for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1)
636: {
637: if (dlen <= 0)
638: return(-1);
639: if (flags & bitmask)
640: *dest = p->InputGuessTable[p->iHash]; /* Guess correct */
641: else
642: {
643: if (!slen)
644: break; /* we seem to be really done -- cabo */
645: p->InputGuessTable[p->iHash] = *source; /* Guess wrong */
646: *dest = *source++; /* Read from source */
647: slen--;
648: }
649: IHASH(*dest++);
650: dlen--;
651: }
652: }
653: return(dest - orgdest);
654: }
655:
656: /*
657: * SyncTable()
658: */
659:
660: static void
661: SyncTable(Bund b, u_char *source, u_char *dest, int len)
662: {
663: Pred1Info p = &b->ccp.pred1;
664:
665: while (len--)
666: {
667: if (p->InputGuessTable[p->iHash] != *source)
668: p->InputGuessTable[p->iHash] = *source;
669: IHASH(*dest++ = *source++);
670: }
671: }
672: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ccp_pred1.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mpd / src