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