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: if ((id = NgGetNodeID(-1, path)) == 0) {
156: Perror("[%s] Cannot get %s node id", b->name, NG_PRED1_NODE_TYPE);
157: goto fail;
158: }
159:
160: if (dir == COMP_DIR_XMIT) {
161: b->ccp.comp_node_id = id;
162: } else {
163: b->ccp.decomp_node_id = id;
164: }
165:
166: /* Configure PRED1 node */
167: snprintf(path, sizeof(path), "[%x]:", id);
168: if (NgSendMsg(gCcpCsock, path,
169: NGM_PRED1_COOKIE, NGM_PRED1_CONFIG, &conf, sizeof(conf)) < 0) {
170: Perror("[%s] can't config %s node at %s",
171: b->name, NG_PRED1_NODE_TYPE, path);
172: goto fail;
173: }
174: #endif
175: return 0;
176:
177: fail:
178: NgFuncShutdownNode(gCcpCsock, b->name, path);
179: return(-1);
180: }
181:
182: /*
183: * Pred1Cleanup()
184: */
185:
186: void
187: Pred1Cleanup(Bund b, int dir)
188: {
189: #ifndef USE_NG_PRED1
190: Pred1Info p = &b->ccp.pred1;
191:
192: if (dir == COMP_DIR_XMIT) {
193: assert(p->OutputGuessTable);
194: Freee(p->OutputGuessTable);
195: p->OutputGuessTable = NULL;
196: memset(&p->xmit_stats, 0, sizeof(p->xmit_stats));
197: } else {
198: assert(p->InputGuessTable);
199: Freee(p->InputGuessTable);
200: p->InputGuessTable = NULL;
201: memset(&p->recv_stats, 0, sizeof(p->recv_stats));
202: }
203: #else
204: char path[NG_PATHSIZ];
205:
206: /* Remove node */
207: if (dir == COMP_DIR_XMIT) {
208: snprintf(path, sizeof(path), "[%x]:", b->ccp.comp_node_id);
209: b->ccp.comp_node_id = 0;
210: } else {
211: snprintf(path, sizeof(path), "[%x]:", b->ccp.decomp_node_id);
212: b->ccp.decomp_node_id = 0;
213: }
214: NgFuncShutdownNode(gCcpCsock, b->name, path);
215: #endif
216: }
217:
218: #ifndef USE_NG_PRED1
219: /*
220: * Pred1Compress()
221: *
222: * Compress a packet and return a compressed version.
223: * The original is untouched.
224: */
225:
226: Mbuf
227: Pred1Compress(Bund b, Mbuf plain)
228: {
229: u_char *wp, *uncomp, *comp;
230: u_int16_t fcs;
231: int len;
232: Mbuf res;
233: int orglen;
234: Pred1Info p = &b->ccp.pred1;
235:
236: orglen = MBLEN(plain);
237: uncomp = MBDATA(plain);
238:
239: p->xmit_stats.InOctets += orglen;
240: p->xmit_stats.FramesPlain++;
241:
242: res = mballoc(PRED1_MAX_BLOWUP(orglen + 2));
243: comp = MBDATA(res);
244:
245: wp = comp;
246:
247: *wp++ = (orglen >> 8) & 0x7F;
248: *wp++ = orglen & 0xFF;
249:
250: /* Compute FCS */
251:
252: fcs = Crc16(PPP_INITFCS, comp, 2);
253: fcs = Crc16(fcs, uncomp, orglen);
254: fcs = ~fcs;
255:
256: /* Compress data */
257:
258: len = Compress(b, uncomp, wp, orglen);
259:
260: /* What happened? */
261:
262: if (len < orglen)
263: {
264: *comp |= 0x80;
265: wp += len;
266: p->xmit_stats.FramesComp++;
267: }
268: else
269: {
270: memcpy(wp, uncomp, orglen);
271: wp += orglen;
272: p->xmit_stats.FramesUncomp++;
273: }
274:
275: /* Add FCS */
276:
277: *wp++ = fcs & 0xFF;
278: *wp++ = fcs >> 8;
279:
280: res->cnt = (wp - comp);
281:
282: mbfree(plain);
283: Log(LG_CCP2, ("[%s] Pred1: orig (%d) --> comp (%d)", b->name, orglen, res->cnt));
284:
285: p->xmit_stats.OutOctets += res->cnt;
286:
287: return res;
288: }
289:
290: /*
291: * Pred1Decompress()
292: *
293: * Decompress a packet and return a compressed version.
294: * The original is untouched.
295: */
296:
297: Mbuf
298: Pred1Decompress(Bund b, Mbuf mbcomp)
299: {
300: u_char *uncomp, *comp;
301: u_char *cp;
302: u_int16_t len, len1, cf, lenn;
303: u_int16_t fcs;
304: int orglen;
305: Mbuf mbuncomp;
306: Pred1Info p = &b->ccp.pred1;
307:
308: orglen = MBLEN(mbcomp);
309: comp = MBDATA(mbcomp);
310: cp = comp;
311:
312: p->recv_stats.InOctets += orglen;
313:
314: mbuncomp = mballoc(PRED1_DECOMP_BUF_SIZE);
315: uncomp = MBDATA(mbuncomp);
316:
317: /* Get initial length value */
318: len = *cp++ << 8;
319: len += *cp++;
320:
321: cf = (len & 0x8000);
322: len &= 0x7fff;
323:
324: /* Is data compressed or not really? */
325: if (cf)
326: {
327: p->recv_stats.FramesComp++;
328: len1 = Decompress(b, cp, uncomp, orglen - 4, PRED1_DECOMP_BUF_SIZE);
329: if (len != len1) /* Error is detected. Send reset request */
330: {
331: Log(LG_CCP2, ("[%s] Length error (%d) --> len (%d)", b->name, len, len1));
332: p->recv_stats.Errors++;
333: mbfree(mbcomp);
334: mbfree(mbuncomp);
335: CcpSendResetReq(b);
336: return NULL;
337: }
338: cp += orglen - 4;
339: }
340: else
341: {
342: p->recv_stats.FramesUncomp++;
343: SyncTable(b, cp, uncomp, len);
344: cp += len;
345: }
346:
347: mbuncomp->cnt = len;
348:
349: /* Check CRC */
350: lenn = htons(len);
351: fcs = Crc16(PPP_INITFCS, (u_char *)&lenn, 2);
352: fcs = Crc16(fcs, uncomp, len);
353: fcs = Crc16(fcs, cp, 2);
354:
355: #ifdef DEBUG
356: if (fcs != PPP_GOODFCS)
357: Log(LG_CCP2, ("fcs = %04x (%s), len = %x, olen = %x",
358: fcs, (fcs == PPP_GOODFCS)? "good" : "bad", len, orglen));
359: #endif
360:
361: if (fcs != PPP_GOODFCS)
362: {
363: Log(LG_CCP2, ("[%s] Pred1: Bad CRC-16", b->name));
364: p->recv_stats.Errors++;
365: mbfree(mbcomp);
366: mbfree(mbuncomp);
367: CcpSendResetReq(b);
368: return NULL;
369: }
370:
371: Log(LG_CCP2, ("[%s] Pred1: orig (%d) <-- comp (%d)", b->name, mbuncomp->cnt, orglen));
372: mbfree(mbcomp);
373:
374: p->recv_stats.FramesPlain++;
375: p->recv_stats.OutOctets += mbuncomp->cnt;
376:
377: return mbuncomp;
378: }
379: #endif
380:
381: /*
382: * Pred1RecvResetReq()
383: */
384:
385: static Mbuf
386: Pred1RecvResetReq(Bund b, int id, Mbuf bp, int *noAck)
387: {
388: (void)id;
389: (void)bp;
390: (void)noAck;
391: #ifndef USE_NG_PRED1
392: Pred1Info p = &b->ccp.pred1;
393:
394: (void)id;
395: (void)bp;
396: (void)noAck;
397:
398: Pred1Init(b, COMP_DIR_XMIT);
399: p->xmit_stats.Errors++;
400: #else
401: char path[NG_PATHSIZ];
402:
403: (void)id;
404: (void)bp;
405: (void)noAck;
406:
407: /* Forward ResetReq to the Predictor1 compression node */
408: snprintf(path, sizeof(path), "[%x]:", b->ccp.comp_node_id);
409: if (NgSendMsg(gCcpCsock, path,
410: NGM_PRED1_COOKIE, NGM_PRED1_RESETREQ, NULL, 0) < 0) {
411: Perror("[%s] reset to %s node", b->name, NG_PRED1_NODE_TYPE);
412: }
413: #endif
414: return(NULL);
415: }
416:
417: /*
418: * Pred1SendResetReq()
419: */
420:
421: static Mbuf
422: Pred1SendResetReq(Bund b)
423: {
424: #ifndef USE_NG_PRED1
425: Pred1Init(b, COMP_DIR_RECV);
426: #else
427: (void)b;
428: #endif
429: return(NULL);
430: }
431:
432: /*
433: * Pred1RecvResetAck()
434: */
435:
436: static void
437: Pred1RecvResetAck(Bund b, int id, Mbuf bp)
438: {
439: #ifndef USE_NG_PRED1
440: (void)id;
441: (void)bp;
442: Pred1Init(b, COMP_DIR_RECV);
443: #else
444: char path[NG_PATHSIZ];
445:
446: (void)id;
447: (void)bp;
448:
449: /* Forward ResetReq to the Predictor1 decompression node */
450: snprintf(path, sizeof(path), "[%x]:", b->ccp.decomp_node_id);
451: if (NgSendMsg(gCcpCsock, path,
452: NGM_PRED1_COOKIE, NGM_PRED1_RESETREQ, NULL, 0) < 0) {
453: Perror("[%s] reset to %s node", b->name, NG_PRED1_NODE_TYPE);
454: }
455: #endif
456: }
457:
458: /*
459: * Pred1BuildConfigReq()
460: */
461:
462: static u_char *
463: Pred1BuildConfigReq(Bund b, u_char *cp, int *ok)
464: {
465: (void)b;
466: cp = FsmConfValue(cp, CCP_TY_PRED1, 0, NULL);
467: *ok = 1;
468: return (cp);
469: }
470:
471: /*
472: * Pred1DecodeConfigReq()
473: */
474:
475: static void
476: Pred1DecodeConfigReq(Fsm fp, FsmOption opt, int mode)
477: {
478: /* Deal with it */
479: switch (mode) {
480: case MODE_REQ:
481: FsmAck(fp, opt);
482: break;
483:
484: case MODE_NAK:
485: break;
486: }
487: }
488:
489: /*
490: * Pred1Negotiated()
491: */
492:
493: static int
494: Pred1Negotiated(Bund b, int dir)
495: {
496: (void)b;
497: (void)dir;
498:
499: return 1;
500: }
501:
502: /*
503: * Pred1SubtractBloat()
504: */
505:
506: static int
507: Pred1SubtractBloat(Bund b, int size)
508: {
509: (void)b;
510: return(size - 4);
511: }
512:
513: static int
514: Pred1Stat(Context ctx, int dir)
515: {
516: #ifndef USE_NG_PRED1
517: Pred1Info p = &ctx->bund->ccp.pred1;
518:
519: switch (dir) {
520: case COMP_DIR_XMIT:
521: Printf("\tBytes\t: %llu -> %llu (%+lld%%)\r\n",
522: (unsigned long long)p->xmit_stats.InOctets,
523: (unsigned long long)p->xmit_stats.OutOctets,
524: ((p->xmit_stats.InOctets!=0)?
525: ((long long)(p->xmit_stats.OutOctets - p->xmit_stats.InOctets)
526: *100/(long long)p->xmit_stats.InOctets):
527: 0));
528: Printf("\tFrames\t: %llu -> %lluc + %lluu\r\n",
529: (unsigned long long)p->xmit_stats.FramesPlain,
530: (unsigned long long)p->xmit_stats.FramesComp,
531: (unsigned long long)p->xmit_stats.FramesUncomp);
532: Printf("\tErrors\t: %llu\r\n",
533: (unsigned long long)p->recv_stats.Errors);
534: break;
535: case COMP_DIR_RECV:
536: Printf("\tBytes\t: %llu <- %llu (%+lld%%)\r\n",
537: (unsigned long long)p->recv_stats.OutOctets,
538: (unsigned long long)p->recv_stats.InOctets,
539: ((p->recv_stats.OutOctets!=0)?
540: ((long long)(p->recv_stats.InOctets - p->recv_stats.OutOctets)
541: *100/(long long)p->recv_stats.OutOctets):
542: 0));
543: Printf("\tFrames\t: %llu <- %lluc + %lluu\r\n",
544: (unsigned long long)p->xmit_stats.FramesPlain,
545: (unsigned long long)p->xmit_stats.FramesComp,
546: (unsigned long long)p->xmit_stats.FramesUncomp);
547: Printf("\tErrors\t: %llu\r\n",
548: (unsigned long long)p->recv_stats.Errors);
549: break;
550: default:
551: assert(0);
552: }
553: return (0);
554: #else
555: Bund b = ctx->bund;
556: char path[NG_PATHSIZ];
557: struct ng_pred1_stats stats;
558: union {
559: u_char buf[sizeof(struct ng_mesg) + sizeof(stats)];
560: struct ng_mesg reply;
561: } u;
562:
563: switch (dir) {
564: case COMP_DIR_XMIT:
565: snprintf(path, sizeof(path), "mpd%d-%s:%s", gPid, b->name,
566: NG_PPP_HOOK_COMPRESS);
567: break;
568: case COMP_DIR_RECV:
569: snprintf(path, sizeof(path), "mpd%d-%s:%s", gPid, b->name,
570: NG_PPP_HOOK_DECOMPRESS);
571: break;
572: default:
573: assert(0);
574: }
575: if (NgFuncSendQuery(path, NGM_PRED1_COOKIE, NGM_PRED1_GET_STATS, NULL, 0,
576: &u.reply, sizeof(u), NULL) < 0) {
577: Perror("[%s] can't get %s stats", b->name, NG_PRED1_NODE_TYPE);
578: return(0);
579: }
580: memcpy(&stats, u.reply.data, sizeof(stats));
581: switch (dir) {
582: case COMP_DIR_XMIT:
583: Printf("\tBytes\t: %llu -> %llu (%+lld%%)\r\n",
584: stats.InOctets,
585: stats.OutOctets,
586: ((stats.InOctets!=0)?
587: ((int64_t)(stats.OutOctets - stats.InOctets)*100/(int64_t)stats.InOctets):
588: 0));
589: Printf("\tFrames\t: %llu -> %lluc + %lluu\r\n",
590: stats.FramesPlain,
591: stats.FramesComp,
592: stats.FramesUncomp);
593: Printf("\tErrors\t: %llu\r\n",
594: stats.Errors);
595: break;
596: case COMP_DIR_RECV:
597: Printf("\tBytes\t: %llu <- %llu (%+lld%%)\r\n",
598: stats.OutOctets,
599: stats.InOctets,
600: ((stats.OutOctets!=0)?
601: ((int64_t)(stats.InOctets - stats.OutOctets)*100/(int64_t)stats.OutOctets):
602: 0));
603: Printf("\tFrames\t: %llu <- %lluc + %lluu\r\n",
604: stats.FramesPlain,
605: stats.FramesComp,
606: stats.FramesUncomp);
607: Printf("\tErrors\t: %llu\r\n",
608: stats.Errors);
609: break;
610: default:
611: assert(0);
612: }
613: return (0);
614: #endif
615: }
616:
617: #ifndef USE_NG_PRED1
618: /*
619: * Compress()
620: */
621:
622: static int
623: Compress(Bund b, u_char *source, u_char *dest, int len)
624: {
625: Pred1Info p = &b->ccp.pred1;
626: int i, bitmask;
627: u_char flags;
628: u_char *flagdest, *orgdest;
629:
630: orgdest = dest;
631: while (len)
632: {
633: flagdest = dest++; flags = 0; /* All guess wrong initially */
634: for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
635: if (p->OutputGuessTable[p->oHash] == *source)
636: flags |= bitmask; /* Guess was right - don't output */
637: else
638: {
639: p->OutputGuessTable[p->oHash] = *source;
640: *dest++ = *source; /* Guess wrong, output char */
641: }
642: OHASH(*source++);
643: len--;
644: }
645: *flagdest = flags;
646: }
647: return(dest - orgdest);
648: }
649:
650: /*
651: * Decompress()
652: *
653: * Returns decompressed size, or -1 if we ran out of space
654: */
655:
656: static int
657: Decompress(Bund b, u_char *source, u_char *dest, int slen, int dlen)
658: {
659: Pred1Info p = &b->ccp.pred1;
660: int i, bitmask;
661: u_char flags, *orgdest;
662:
663: orgdest = dest;
664: while (slen)
665: {
666: flags = *source++;
667: slen--;
668: for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1)
669: {
670: if (dlen <= 0)
671: return(-1);
672: if (flags & bitmask)
673: *dest = p->InputGuessTable[p->iHash]; /* Guess correct */
674: else
675: {
676: if (!slen)
677: break; /* we seem to be really done -- cabo */
678: p->InputGuessTable[p->iHash] = *source; /* Guess wrong */
679: *dest = *source++; /* Read from source */
680: slen--;
681: }
682: IHASH(*dest++);
683: dlen--;
684: }
685: }
686: return(dest - orgdest);
687: }
688:
689: /*
690: * SyncTable()
691: */
692:
693: static void
694: SyncTable(Bund b, u_char *source, u_char *dest, int len)
695: {
696: Pred1Info p = &b->ccp.pred1;
697:
698: while (len--)
699: {
700: if (p->InputGuessTable[p->iHash] != *source)
701: p->InputGuessTable[p->iHash] = *source;
702: IHASH(*dest++ = *source++);
703: }
704: }
705: #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