]> git.ozlabs.org Git - ppp.git/blob - modules/deflate.c
priority queueing stuff
[ppp.git] / modules / deflate.c
1 /*
2  * ppp_deflate.c - interface the zlib procedures for Deflate compression
3  * and decompression (as used by gzip) to the PPP code.
4  * This version is for use with STREAMS under SunOS 4.x, Solaris 2,
5  * SVR4, OSF/1 and AIX 4.x.
6  *
7  * Copyright (c) 1994 The Australian National University.
8  * All rights reserved.
9  *
10  * Permission to use, copy, modify, and distribute this software and its
11  * documentation is hereby granted, provided that the above copyright
12  * notice appears in all copies.  This software is provided without any
13  * warranty, express or implied. The Australian National University
14  * makes no representations about the suitability of this software for
15  * any purpose.
16  *
17  * IN NO EVENT SHALL THE AUSTRALIAN NATIONAL UNIVERSITY BE LIABLE TO ANY
18  * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
19  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
20  * THE AUSTRALIAN NATIONAL UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY
21  * OF SUCH DAMAGE.
22  *
23  * THE AUSTRALIAN NATIONAL UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
24  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
25  * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
26  * ON AN "AS IS" BASIS, AND THE AUSTRALIAN NATIONAL UNIVERSITY HAS NO
27  * OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS,
28  * OR MODIFICATIONS.
29  *
30  * $Id: deflate.c,v 1.4 1996/08/28 06:34:56 paulus Exp $
31  */
32
33 #ifdef AIX4
34 #include <net/net_globals.h>
35 #endif
36 #include <sys/param.h>
37 #include <sys/types.h>
38 #include <sys/stream.h>
39 #include <net/ppp_defs.h>
40 #include "ppp_mod.h"
41
42 #define PACKETPTR       mblk_t *
43 #include <net/ppp-comp.h>
44
45 #ifdef __osf__
46 #include "zlib.h"
47 #else
48 #include "common/zlib.h"
49 #endif
50
51 #if DO_DEFLATE
52
53 #define DEFLATE_DEBUG   1
54
55 /*
56  * State for a Deflate (de)compressor.
57  */
58 struct deflate_state {
59     int         seqno;
60     int         w_size;
61     int         unit;
62     int         hdrlen;
63     int         mru;
64     int         debug;
65     z_stream    strm;
66     struct compstat stats;
67 };
68
69 #define DEFLATE_OVHD    2               /* Deflate overhead/packet */
70
71 static void     *z_alloc __P((void *, u_int items, u_int size));
72 static void     z_free __P((void *, void *ptr, u_int nb));
73 static void     *z_comp_alloc __P((u_char *options, int opt_len));
74 static void     *z_decomp_alloc __P((u_char *options, int opt_len));
75 static void     z_comp_free __P((void *state));
76 static void     z_decomp_free __P((void *state));
77 static int      z_comp_init __P((void *state, u_char *options, int opt_len,
78                                  int unit, int hdrlen, int debug));
79 static int      z_decomp_init __P((void *state, u_char *options, int opt_len,
80                                      int unit, int hdrlen, int mru, int debug));
81 static int      z_compress __P((void *state, mblk_t **mret,
82                                   mblk_t *mp, int slen, int maxolen));
83 static void     z_incomp __P((void *state, mblk_t *dmsg));
84 static int      z_decompress __P((void *state, mblk_t *cmp,
85                                     mblk_t **dmpp));
86 static void     z_comp_reset __P((void *state));
87 static void     z_decomp_reset __P((void *state));
88 static void     z_comp_stats __P((void *state, struct compstat *stats));
89
90 /*
91  * Procedures exported to if_ppp.c.
92  */
93 struct compressor ppp_deflate = {
94     CI_DEFLATE,                 /* compress_proto */
95     z_comp_alloc,               /* comp_alloc */
96     z_comp_free,                /* comp_free */
97     z_comp_init,                /* comp_init */
98     z_comp_reset,               /* comp_reset */
99     z_compress,                 /* compress */
100     z_comp_stats,               /* comp_stat */
101     z_decomp_alloc,             /* decomp_alloc */
102     z_decomp_free,              /* decomp_free */
103     z_decomp_init,              /* decomp_init */
104     z_decomp_reset,             /* decomp_reset */
105     z_decompress,               /* decompress */
106     z_incomp,                   /* incomp */
107     z_comp_stats,               /* decomp_stat */
108 };
109
110 #define DECOMP_CHUNK    512
111
112 /*
113  * Space allocation and freeing routines for use by zlib routines.
114  */
115 static void *
116 z_alloc(notused, items, size)
117     void *notused;
118     u_int items, size;
119 {
120 #ifdef __osf__
121     return ALLOC_SLEEP(items * size);
122 #else
123     return ALLOC_NOSLEEP(items * size);
124 #endif
125 }
126
127 static void
128 z_free(notused, ptr, nbytes)
129     void *notused;
130     void *ptr;
131     u_int nbytes;
132 {
133     FREE(ptr, nbytes);
134 }
135
136 /*
137  * Allocate space for a compressor.
138  */
139 static void *
140 z_comp_alloc(options, opt_len)
141     u_char *options;
142     int opt_len;
143 {
144     struct deflate_state *state;
145     int w_size;
146
147     if (opt_len != CILEN_DEFLATE || options[0] != CI_DEFLATE
148         || options[1] != CILEN_DEFLATE
149         || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL
150         || options[3] != DEFLATE_CHK_SEQUENCE)
151         return NULL;
152     w_size = DEFLATE_SIZE(options[2]);
153     if (w_size < DEFLATE_MIN_SIZE || w_size > DEFLATE_MAX_SIZE)
154         return NULL;
155
156     state = (struct deflate_state *) ALLOC_NOSLEEP(sizeof(*state));
157     if (state == NULL)
158         return NULL;
159
160     state->strm.next_in = NULL;
161     state->strm.zalloc = (alloc_func) z_alloc;
162     state->strm.zfree = (free_func) z_free;
163     if (deflateInit2(&state->strm, Z_DEFAULT_COMPRESSION, DEFLATE_METHOD_VAL,
164                      -w_size, 8, Z_DEFAULT_STRATEGY, DEFLATE_OVHD+2) != Z_OK) {
165         FREE(state, sizeof(*state));
166         return NULL;
167     }
168
169     state->w_size = w_size;
170     bzero(&state->stats, sizeof(state->stats));
171     return (void *) state;
172 }
173
174 static void
175 z_comp_free(arg)
176     void *arg;
177 {
178     struct deflate_state *state = (struct deflate_state *) arg;
179
180     deflateEnd(&state->strm);
181     FREE(state, sizeof(*state));
182 }
183
184 static int
185 z_comp_init(arg, options, opt_len, unit, hdrlen, debug)
186     void *arg;
187     u_char *options;
188     int opt_len, unit, hdrlen, debug;
189 {
190     struct deflate_state *state = (struct deflate_state *) arg;
191
192     if (opt_len < CILEN_DEFLATE || options[0] != CI_DEFLATE
193         || options[1] != CILEN_DEFLATE
194         || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL
195         || DEFLATE_SIZE(options[2]) != state->w_size
196         || options[3] != DEFLATE_CHK_SEQUENCE)
197         return 0;
198
199     state->seqno = 0;
200     state->unit = unit;
201     state->hdrlen = hdrlen;
202     state->debug = debug;
203
204     deflateReset(&state->strm);
205
206     return 1;
207 }
208
209 static void
210 z_comp_reset(arg)
211     void *arg;
212 {
213     struct deflate_state *state = (struct deflate_state *) arg;
214
215     state->seqno = 0;
216     deflateReset(&state->strm);
217 }
218
219 static int
220 z_compress(arg, mret, mp, orig_len, maxolen)
221     void *arg;
222     mblk_t **mret;              /* compressed packet (out) */
223     mblk_t *mp;         /* uncompressed packet (in) */
224     int orig_len, maxolen;
225 {
226     struct deflate_state *state = (struct deflate_state *) arg;
227     u_char *rptr, *wptr;
228     int proto, olen, wspace, r, flush;
229     mblk_t *m;
230
231     /*
232      * Check that the protocol is in the range we handle.
233      */
234     *mret = NULL;
235     rptr = mp->b_rptr;
236     if (rptr + PPP_HDRLEN > mp->b_wptr) {
237         if (!pullupmsg(mp, PPP_HDRLEN))
238             return 0;
239         rptr = mp->b_rptr;
240     }
241     proto = PPP_PROTOCOL(rptr);
242     if (proto > 0x3fff || proto == 0xfd || proto == 0xfb)
243         return orig_len;
244
245     /* Allocate one mblk initially. */
246     if (maxolen > orig_len)
247         maxolen = orig_len;
248     wspace = maxolen < 4096? maxolen: 4096;
249     m = allocb(wspace, BPRI_MED);
250     if (m != NULL) {
251         *mret = m;
252         if (state->hdrlen + PPP_HDRLEN + 2 < wspace) {
253             m->b_rptr += state->hdrlen;
254             m->b_wptr = m->b_rptr;
255             wspace -= state->hdrlen;
256         }
257         wptr = m->b_wptr;
258
259         /*
260          * Copy over the PPP header and store the 2-byte sequence number.
261          */
262         wptr[0] = PPP_ADDRESS(rptr);
263         wptr[1] = PPP_CONTROL(rptr);
264         wptr[2] = PPP_COMP >> 8;
265         wptr[3] = PPP_COMP;
266         wptr += PPP_HDRLEN;
267         wptr[0] = state->seqno >> 8;
268         wptr[1] = state->seqno;
269         wptr += 2;
270         state->strm.next_out = wptr;
271         state->strm.avail_out = wspace - (PPP_HDRLEN + 2);
272     } else {
273         state->strm.next_out = NULL;
274         state->strm.avail_out = 1000000;
275     }
276     ++state->seqno;
277
278     rptr += (proto > 0xff)? 2: 3;       /* skip 1st proto byte if 0 */
279     state->strm.next_in = rptr;
280     state->strm.avail_in = mp->b_wptr - rptr;
281     mp = mp->b_cont;
282     flush = (mp == NULL)? Z_PACKET_FLUSH: Z_NO_FLUSH;
283     olen = 0;
284     for (;;) {
285         r = deflate(&state->strm, flush);
286         if (r != Z_OK) {
287             printf("z_compress: deflate returned %d (%s)\n",
288                    r, (state->strm.msg? state->strm.msg: ""));
289             break;
290         }
291         if (flush != Z_NO_FLUSH && state->strm.avail_out != 0)
292             break;              /* all done */
293         if (state->strm.avail_in == 0 && mp != NULL) {
294             state->strm.next_in = mp->b_rptr;
295             state->strm.avail_in = mp->b_wptr - mp->b_rptr;
296             mp = mp->b_cont;
297             if (mp == NULL)
298                 flush = Z_PACKET_FLUSH;
299         }
300         if (state->strm.avail_out == 0) {
301             if (m != NULL) {
302                 m->b_wptr += wspace;
303                 olen += wspace;
304                 wspace = maxolen - olen;
305                 if (wspace < 32)
306                     wspace = 32;
307                 else if (wspace > 4096)
308                     wspace = 4096;
309                 m->b_cont = allocb(wspace, BPRI_MED);
310                 m = m->b_cont;
311                 if (m != NULL) {
312                     state->strm.next_out = m->b_wptr;
313                     state->strm.avail_out = wspace;
314                 }
315             }
316             if (m == NULL) {
317                 state->strm.next_out = NULL;
318                 state->strm.avail_out = 1000000;
319             }
320         }
321     }
322     m->b_wptr += wspace - state->strm.avail_out;
323     olen += wspace - state->strm.avail_out;
324
325     /*
326      * See if we managed to reduce the size of the packet.
327      * If the compressor just gave us a single zero byte, it means
328      * the packet was incompressible.
329      */
330     if (olen < orig_len && m != NULL
331         && !(olen == PPP_HDRLEN + 3 && *wptr == 0)) {
332         state->stats.comp_bytes += olen;
333         state->stats.comp_packets++;
334     } else {
335         if (*mret != NULL) {
336             freemsg(*mret);
337             *mret = NULL;
338         }
339         state->stats.inc_bytes += orig_len;
340         state->stats.inc_packets++;
341         olen = orig_len;
342     }
343     state->stats.unc_bytes += orig_len;
344     state->stats.unc_packets++;
345
346     return olen;
347 }
348
349 static void
350 z_comp_stats(arg, stats)
351     void *arg;
352     struct compstat *stats;
353 {
354     struct deflate_state *state = (struct deflate_state *) arg;
355     u_int out;
356
357     *stats = state->stats;
358     stats->ratio = stats->unc_bytes;
359     out = stats->comp_bytes + stats->unc_bytes;
360     if (stats->ratio <= 0x7ffffff)
361         stats->ratio <<= 8;
362     else
363         out >>= 8;
364     if (out != 0)
365         stats->ratio /= out;
366 }
367
368 /*
369  * Allocate space for a decompressor.
370  */
371 static void *
372 z_decomp_alloc(options, opt_len)
373     u_char *options;
374     int opt_len;
375 {
376     struct deflate_state *state;
377     int w_size;
378
379     if (opt_len != CILEN_DEFLATE || options[0] != CI_DEFLATE
380         || options[1] != CILEN_DEFLATE
381         || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL
382         || options[3] != DEFLATE_CHK_SEQUENCE)
383         return NULL;
384     w_size = DEFLATE_SIZE(options[2]);
385     if (w_size < DEFLATE_MIN_SIZE || w_size > DEFLATE_MAX_SIZE)
386         return NULL;
387
388     state = (struct deflate_state *) ALLOC_NOSLEEP(sizeof(*state));
389     if (state == NULL)
390         return NULL;
391
392     state->strm.next_out = NULL;
393     state->strm.zalloc = (alloc_func) z_alloc;
394     state->strm.zfree = (free_func) z_free;
395     if (inflateInit2(&state->strm, -w_size) != Z_OK) {
396         FREE(state, sizeof(*state));
397         return NULL;
398     }
399
400     state->w_size = w_size;
401     bzero(&state->stats, sizeof(state->stats));
402     return (void *) state;
403 }
404
405 static void
406 z_decomp_free(arg)
407     void *arg;
408 {
409     struct deflate_state *state = (struct deflate_state *) arg;
410
411     inflateEnd(&state->strm);
412     FREE(state, sizeof(*state));
413 }
414
415 static int
416 z_decomp_init(arg, options, opt_len, unit, hdrlen, mru, debug)
417     void *arg;
418     u_char *options;
419     int opt_len, unit, hdrlen, mru, debug;
420 {
421     struct deflate_state *state = (struct deflate_state *) arg;
422
423     if (opt_len < CILEN_DEFLATE || options[0] != CI_DEFLATE
424         || options[1] != CILEN_DEFLATE
425         || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL
426         || DEFLATE_SIZE(options[2]) != state->w_size
427         || options[3] != DEFLATE_CHK_SEQUENCE)
428         return 0;
429
430     state->seqno = 0;
431     state->unit = unit;
432     state->hdrlen = hdrlen;
433     state->debug = debug;
434     state->mru = mru;
435
436     inflateReset(&state->strm);
437
438     return 1;
439 }
440
441 static void
442 z_decomp_reset(arg)
443     void *arg;
444 {
445     struct deflate_state *state = (struct deflate_state *) arg;
446
447     state->seqno = 0;
448     inflateReset(&state->strm);
449 }
450
451 /*
452  * Decompress a Deflate-compressed packet.
453  *
454  * Because of patent problems, we return DECOMP_ERROR for errors
455  * found by inspecting the input data and for system problems, but
456  * DECOMP_FATALERROR for any errors which could possibly be said to
457  * be being detected "after" decompression.  For DECOMP_ERROR,
458  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
459  * infringing a patent of Motorola's if we do, so we take CCP down
460  * instead.
461  *
462  * Given that the frame has the correct sequence number and a good FCS,
463  * errors such as invalid codes in the input most likely indicate a
464  * bug, so we return DECOMP_FATALERROR for them in order to turn off
465  * compression, even though they are detected by inspecting the input.
466  */
467 static int
468 z_decompress(arg, mi, mop)
469     void *arg;
470     mblk_t *mi, **mop;
471 {
472     struct deflate_state *state = (struct deflate_state *) arg;
473     mblk_t *mo, *mo_head;
474     u_char *rptr, *wptr;
475     int rlen, olen, ospace;
476     int seq, i, flush, r, decode_proto;
477     u_char hdr[PPP_HDRLEN + DEFLATE_OVHD];
478
479     *mop = NULL;
480     rptr = mi->b_rptr;
481     for (i = 0; i < PPP_HDRLEN + DEFLATE_OVHD; ++i) {
482         while (rptr >= mi->b_wptr) {
483             mi = mi->b_cont;
484             if (mi == NULL)
485                 return DECOMP_ERROR;
486             rptr = mi->b_rptr;
487         }
488         hdr[i] = *rptr++;
489     }
490
491     /* Check the sequence number. */
492     seq = (hdr[PPP_HDRLEN] << 8) + hdr[PPP_HDRLEN+1];
493     if (seq != state->seqno) {
494 #if !DEFLATE_DEBUG
495         if (state->debug)
496 #endif
497             printf("z_decompress%d: bad seq # %d, expected %d\n",
498                    state->unit, seq, state->seqno);
499         return DECOMP_ERROR;
500     }
501     ++state->seqno;
502
503     /* Allocate an output message block. */
504     mo = allocb(DECOMP_CHUNK + state->hdrlen, BPRI_MED);
505     if (mo == NULL)
506         return DECOMP_ERROR;
507     mo_head = mo;
508     mo->b_cont = NULL;
509     mo->b_rptr += state->hdrlen;
510     mo->b_wptr = wptr = mo->b_rptr;
511     ospace = DECOMP_CHUNK;
512
513     /*
514      * Fill in the first part of the PPP header.  The protocol field
515      * comes from the decompressed data.
516      */
517     wptr[0] = PPP_ADDRESS(hdr);
518     wptr[1] = PPP_CONTROL(hdr);
519     wptr[2] = 0;
520
521     /*
522      * Set up to call inflate.  We set avail_out to 1 initially so we can
523      * look at the first byte of the output and decide whether we have
524      * a 1-byte or 2-byte protocol field.
525      */
526     state->strm.next_in = rptr;
527     state->strm.avail_in = mi->b_wptr - rptr;
528     mi = mi->b_cont;
529     flush = (mi == NULL)? Z_PACKET_FLUSH: Z_NO_FLUSH;
530     rlen = state->strm.avail_in + PPP_HDRLEN + DEFLATE_OVHD;
531     state->strm.next_out = wptr + 3;
532     state->strm.avail_out = 1;
533     decode_proto = 1;
534     olen = PPP_HDRLEN;
535
536     /*
537      * Call inflate, supplying more input or output as needed.
538      */
539     for (;;) {
540         r = inflate(&state->strm, flush);
541         if (r != Z_OK) {
542 #if !DEFLATE_DEBUG
543             if (state->debug)
544 #endif
545                 printf("z_decompress%d: inflate returned %d (%s)\n",
546                        state->unit, r, (state->strm.msg? state->strm.msg: ""));
547             freemsg(mo_head);
548             return DECOMP_FATALERROR;
549         }
550         if (flush != Z_NO_FLUSH && state->strm.avail_out != 0)
551             break;              /* all done */
552         if (state->strm.avail_in == 0 && mi != NULL) {
553             state->strm.next_in = mi->b_rptr;
554             state->strm.avail_in = mi->b_wptr - mi->b_rptr;
555             rlen += state->strm.avail_in;
556             mi = mi->b_cont;
557             if (mi == NULL)
558                 flush = Z_PACKET_FLUSH;
559         }
560         if (state->strm.avail_out == 0) {
561             if (decode_proto) {
562                 state->strm.avail_out = ospace - PPP_HDRLEN;
563                 if ((wptr[3] & 1) == 0) {
564                     /* 2-byte protocol field */
565                     wptr[2] = wptr[3];
566                     --state->strm.next_out;
567                     ++state->strm.avail_out;
568                     --olen;
569                 }
570                 decode_proto = 0;
571             } else {
572                 mo->b_wptr += ospace;
573                 olen += ospace;
574                 mo->b_cont = allocb(DECOMP_CHUNK, BPRI_MED);
575                 mo = mo->b_cont;
576                 if (mo == NULL) {
577                     freemsg(mo_head);
578                     return DECOMP_ERROR;
579                 }
580                 state->strm.next_out = mo->b_rptr;
581                 state->strm.avail_out = ospace = DECOMP_CHUNK;
582             }
583         }
584     }
585     if (decode_proto) {
586         freemsg(mo_head);
587         return DECOMP_ERROR;
588     }
589     mo->b_wptr += ospace - state->strm.avail_out;
590     olen += ospace - state->strm.avail_out;
591
592 #if DEFLATE_DEBUG
593     if (olen > state->mru + PPP_HDRLEN)
594         printf("ppp_deflate%d: exceeded mru (%d > %d)\n",
595                state->unit, olen, state->mru + PPP_HDRLEN);
596 #endif
597
598     state->stats.unc_bytes += olen;
599     state->stats.unc_packets++;
600     state->stats.comp_bytes += rlen;
601     state->stats.comp_packets++;
602
603     *mop = mo_head;
604     return DECOMP_OK;
605 }
606
607 /*
608  * Incompressible data has arrived - add it to the history.
609  */
610 static void
611 z_incomp(arg, mi)
612     void *arg;
613     mblk_t *mi;
614 {
615     struct deflate_state *state = (struct deflate_state *) arg;
616     u_char *rptr;
617     int rlen, proto, r;
618
619     /*
620      * Check that the protocol is one we handle.
621      */
622     rptr = mi->b_rptr;
623     if (rptr + PPP_HDRLEN > mi->b_wptr) {
624         if (!pullupmsg(mi, PPP_HDRLEN))
625             return;
626         rptr = mi->b_rptr;
627     }
628     proto = PPP_PROTOCOL(rptr);
629     if (proto > 0x3fff || proto == 0xfd || proto == 0xfb)
630         return;
631
632     ++state->seqno;
633
634     /*
635      * Iterate through the message blocks, adding the characters in them
636      * to the decompressor's history.  For the first block, we start
637      * at the either the 1st or 2nd byte of the protocol field,
638      * depending on whether the protocol value is compressible.
639      */
640     rlen = mi->b_wptr - mi->b_rptr;
641     state->strm.next_in = rptr + 3;
642     state->strm.avail_in = rlen - 3;
643     if (proto > 0xff) {
644         --state->strm.next_in;
645         ++state->strm.avail_in;
646     }
647     for (;;) {
648         r = inflateIncomp(&state->strm);
649         if (r != Z_OK) {
650             /* gak! */
651 #if !DEFLATE_DEBUG
652             if (state->debug)
653 #endif
654                 printf("z_incomp%d: inflateIncomp returned %d (%s)\n",
655                        state->unit, r, (state->strm.msg? state->strm.msg: ""));
656             return;
657         }
658         mi = mi->b_cont;
659         if (mi == NULL)
660             break;
661         state->strm.next_in = mi->b_rptr;
662         state->strm.avail_in = mi->b_wptr - mi->b_rptr;
663         rlen += state->strm.avail_in;
664     }
665
666     /*
667      * Update stats.
668      */
669     state->stats.inc_bytes += rlen;
670     state->stats.inc_packets++;
671     state->stats.unc_bytes += rlen;
672     state->stats.unc_packets++;
673 }
674
675 #endif /* DO_DEFLATE */