65364398e37682fdbfe90fe3f57227c42f97e294
[dragonfly.git] / sys / net / ppp_layer / ppp_deflate.c
1 /* $FreeBSD: src/sys/net/ppp_deflate.c,v 1.12.2.1 2002/04/14 21:41:48 luigi Exp $       */
2 /* $DragonFly: src/sys/net/ppp_layer/ppp_deflate.c,v 1.9 2006/12/22 23:44:57 swildner 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/systm.h>
35 #include <sys/malloc.h>
36 #include <sys/mbuf.h>
37 #include "ppp_defs.h"
38 #include <net/zlib.h>
39
40 #define PACKETPTR       struct mbuf *
41 #include "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     *z_alloc (void *, u_int items, u_int size);
64 static void     z_free (void *, void *ptr);
65 static void     *z_comp_alloc (u_char *options, int opt_len);
66 static void     *z_decomp_alloc (u_char *options, int opt_len);
67 static void     z_comp_free (void *state);
68 static void     z_decomp_free (void *state);
69 static int      z_comp_init (void *state, u_char *options, int opt_len,
70                                  int unit, int hdrlen, int debug);
71 static int      z_decomp_init (void *state, u_char *options, int opt_len,
72                                      int unit, int hdrlen, int mru, int debug);
73 static int      z_compress (void *state, struct mbuf **mret,
74                                   struct mbuf *mp, int slen, int maxolen);
75 static void     z_incomp (void *state, struct mbuf *dmsg);
76 static int      z_decompress (void *state, struct mbuf *cmp,
77                                     struct mbuf **dmpp);
78 static void     z_comp_reset (void *state);
79 static void     z_decomp_reset (void *state);
80 static void     z_comp_stats (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 struct compressor ppp_deflate_draft = {
103     CI_DEFLATE_DRAFT,           /* compress_proto */
104     z_comp_alloc,               /* comp_alloc */
105     z_comp_free,                /* comp_free */
106     z_comp_init,                /* comp_init */
107     z_comp_reset,               /* comp_reset */
108     z_compress,                 /* compress */
109     z_comp_stats,               /* comp_stat */
110     z_decomp_alloc,             /* decomp_alloc */
111     z_decomp_free,              /* decomp_free */
112     z_decomp_init,              /* decomp_init */
113     z_decomp_reset,             /* decomp_reset */
114     z_decompress,               /* decompress */
115     z_incomp,                   /* incomp */
116     z_comp_stats,               /* decomp_stat */
117 };
118
119 /*
120  * Space allocation and freeing routines for use by zlib routines.
121  */
122 void *
123 z_alloc(void *notused, u_int items, u_int size)
124 {
125     void *ptr;
126
127     MALLOC(ptr, void *, items * size, M_DEVBUF, M_WAITOK);
128     return ptr;
129 }
130
131 void
132 z_free(void *notused, void *ptr)
133 {
134     kfree(ptr, M_DEVBUF);
135 }
136
137 /*
138  * Allocate space for a compressor.
139  */
140 static void *
141 z_comp_alloc(u_char *options, int opt_len)
142 {
143     struct deflate_state *state;
144     int w_size;
145
146     if (opt_len != CILEN_DEFLATE
147         || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT)
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     MALLOC(state, struct deflate_state *, sizeof(struct deflate_state),
157            M_DEVBUF, M_WAITOK);
158
159     state->strm.next_in = NULL;
160     state->strm.zalloc = z_alloc;
161     state->strm.zfree = z_free;
162     if (deflateInit2(&state->strm, Z_DEFAULT_COMPRESSION, DEFLATE_METHOD_VAL,
163                      -w_size, 8, Z_DEFAULT_STRATEGY) != Z_OK) {
164         kfree(state, M_DEVBUF);
165         return NULL;
166     }
167
168     state->w_size = w_size;
169     bzero(&state->stats, sizeof(state->stats));
170     return (void *) state;
171 }
172
173 static void
174 z_comp_free(void *arg)
175 {
176     struct deflate_state *state = (struct deflate_state *) arg;
177
178     deflateEnd(&state->strm);
179     kfree(state, M_DEVBUF);
180 }
181
182 static int
183 z_comp_init(void *arg, u_char *options, int opt_len, int unit, int hdrlen,
184             int debug)
185 {
186     struct deflate_state *state = (struct deflate_state *) arg;
187
188     if (opt_len < CILEN_DEFLATE
189         || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT)
190         || options[1] != CILEN_DEFLATE
191         || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL
192         || DEFLATE_SIZE(options[2]) != state->w_size
193         || options[3] != DEFLATE_CHK_SEQUENCE)
194         return 0;
195
196     state->seqno = 0;
197     state->unit = unit;
198     state->hdrlen = hdrlen;
199     state->debug = debug;
200
201     deflateReset(&state->strm);
202
203     return 1;
204 }
205
206 static void
207 z_comp_reset(void *arg)
208 {
209     struct deflate_state *state = (struct deflate_state *) arg;
210
211     state->seqno = 0;
212     deflateReset(&state->strm);
213 }
214
215 /*
216  * Parameters:
217  *      mret:   compressed packet (out)
218  *      mp:     uncompressed packet (in)
219  */
220 int
221 z_compress(void *arg, struct mbuf **mret, struct mbuf *mp, int orig_len,
222            int maxolen)
223 {
224     struct deflate_state *state = (struct deflate_state *) arg;
225     u_char *rptr, *wptr;
226     int proto, olen, wspace, r, flush;
227     struct mbuf *m;
228
229     /*
230      * Check that the protocol is in the range we handle.
231      */
232     rptr = mtod(mp, u_char *);
233     proto = PPP_PROTOCOL(rptr);
234     if (proto > 0x3fff || proto == 0xfd || proto == 0xfb) {
235         *mret = NULL;
236         return orig_len;
237     }
238
239     /* Allocate one mbuf initially. */
240     if (maxolen > orig_len)
241         maxolen = orig_len;
242     MGET(m, MB_DONTWAIT, MT_DATA);
243     *mret = m;
244     if (m != NULL) {
245         m->m_len = 0;
246         if (maxolen + state->hdrlen > MLEN)
247             MCLGET(m, MB_DONTWAIT);
248         wspace = M_TRAILINGSPACE(m);
249         if (state->hdrlen + PPP_HDRLEN + 2 < wspace) {
250             m->m_data += state->hdrlen;
251             wspace -= state->hdrlen;
252         }
253         wptr = mtod(m, u_char *);
254
255         /*
256          * Copy over the PPP header and store the 2-byte sequence number.
257          */
258         wptr[0] = PPP_ADDRESS(rptr);
259         wptr[1] = PPP_CONTROL(rptr);
260         wptr[2] = PPP_COMP >> 8;
261         wptr[3] = PPP_COMP;
262         wptr += PPP_HDRLEN;
263         wptr[0] = state->seqno >> 8;
264         wptr[1] = state->seqno;
265         wptr += 2;
266         state->strm.next_out = wptr;
267         state->strm.avail_out = wspace - (PPP_HDRLEN + 2);
268     } else {
269         state->strm.next_out = NULL;
270         state->strm.avail_out = 1000000;
271         wptr = NULL;
272         wspace = 0;
273     }
274     ++state->seqno;
275
276     rptr += (proto > 0xff)? 2: 3;       /* skip 1st proto byte if 0 */
277     state->strm.next_in = rptr;
278     state->strm.avail_in = mtod(mp, u_char *) + mp->m_len - rptr;
279     mp = mp->m_next;
280     flush = (mp == NULL)? Z_PACKET_FLUSH: Z_NO_FLUSH;
281     olen = 0;
282     for (;;) {
283         r = deflate(&state->strm, flush);
284         if (r != Z_OK) {
285             kprintf("z_compress: deflate returned %d (%s)\n",
286                    r, (state->strm.msg? state->strm.msg: ""));
287             break;
288         }
289         if (flush != Z_NO_FLUSH && state->strm.avail_out != 0)
290             break;              /* all done */
291         if (state->strm.avail_in == 0 && mp != NULL) {
292             state->strm.next_in = mtod(mp, u_char *);
293             state->strm.avail_in = mp->m_len;
294             mp = mp->m_next;
295             if (mp == NULL)
296                 flush = Z_PACKET_FLUSH;
297         }
298         if (state->strm.avail_out == 0) {
299             if (m != NULL) {
300                 m->m_len = wspace;
301                 olen += wspace;
302                 MGET(m->m_next, MB_DONTWAIT, MT_DATA);
303                 m = m->m_next;
304                 if (m != NULL) {
305                     m->m_len = 0;
306                     if (maxolen - olen > MLEN)
307                         MCLGET(m, MB_DONTWAIT);
308                     state->strm.next_out = mtod(m, u_char *);
309                     state->strm.avail_out = wspace = M_TRAILINGSPACE(m);
310                 }
311             }
312             if (m == NULL) {
313                 state->strm.next_out = NULL;
314                 state->strm.avail_out = 1000000;
315             }
316         }
317     }
318     if (m != NULL)
319         olen += (m->m_len = wspace - state->strm.avail_out);
320
321     /*
322      * See if we managed to reduce the size of the packet.
323      */
324     if (m != NULL && olen < orig_len) {
325         state->stats.comp_bytes += olen;
326         state->stats.comp_packets++;
327     } else {
328         if (*mret != NULL) {
329             m_freem(*mret);
330             *mret = NULL;
331         }
332         state->stats.inc_bytes += orig_len;
333         state->stats.inc_packets++;
334         olen = orig_len;
335     }
336     state->stats.unc_bytes += orig_len;
337     state->stats.unc_packets++;
338
339     return olen;
340 }
341
342 static void
343 z_comp_stats(void *arg, struct compstat *stats)
344 {
345     struct deflate_state *state = (struct deflate_state *) arg;
346     u_int out;
347
348     *stats = state->stats;
349     stats->ratio = stats->unc_bytes;
350     out = stats->comp_bytes + stats->inc_bytes;
351     if (stats->ratio <= 0x7ffffff)
352         stats->ratio <<= 8;
353     else
354         out >>= 8;
355     if (out != 0)
356         stats->ratio /= out;
357 }
358
359 /*
360  * Allocate space for a decompressor.
361  */
362 static void *
363 z_decomp_alloc(u_char *options, int opt_len)
364 {
365     struct deflate_state *state;
366     int w_size;
367
368     if (opt_len != CILEN_DEFLATE
369         || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT)
370         || options[1] != CILEN_DEFLATE
371         || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL
372         || options[3] != DEFLATE_CHK_SEQUENCE)
373         return NULL;
374     w_size = DEFLATE_SIZE(options[2]);
375     if (w_size < DEFLATE_MIN_SIZE || w_size > DEFLATE_MAX_SIZE)
376         return NULL;
377
378     MALLOC(state, struct deflate_state *, sizeof(struct deflate_state),
379            M_DEVBUF, M_WAITOK);
380
381     state->strm.next_out = NULL;
382     state->strm.zalloc = z_alloc;
383     state->strm.zfree = z_free;
384     if (inflateInit2(&state->strm, -w_size) != Z_OK) {
385         kfree(state, M_DEVBUF);
386         return NULL;
387     }
388
389     state->w_size = w_size;
390     bzero(&state->stats, sizeof(state->stats));
391     return (void *) state;
392 }
393
394 static void
395 z_decomp_free(void *arg)
396 {
397     struct deflate_state *state = (struct deflate_state *) arg;
398
399     inflateEnd(&state->strm);
400     kfree(state, M_DEVBUF);
401 }
402
403 static int
404 z_decomp_init(void *arg, u_char *options, int opt_len, int unit, int hdrlen,
405               int mru, int debug)
406 {
407     struct deflate_state *state = (struct deflate_state *) arg;
408
409     if (opt_len < CILEN_DEFLATE
410         || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT)
411         || options[1] != CILEN_DEFLATE
412         || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL
413         || DEFLATE_SIZE(options[2]) != state->w_size
414         || options[3] != DEFLATE_CHK_SEQUENCE)
415         return 0;
416
417     state->seqno = 0;
418     state->unit = unit;
419     state->hdrlen = hdrlen;
420     state->debug = debug;
421     state->mru = mru;
422
423     inflateReset(&state->strm);
424
425     return 1;
426 }
427
428 static void
429 z_decomp_reset(void *arg)
430 {
431     struct deflate_state *state = (struct deflate_state *) arg;
432
433     state->seqno = 0;
434     inflateReset(&state->strm);
435 }
436
437 /*
438  * Decompress a Deflate-compressed packet.
439  *
440  * Because of patent problems, we return DECOMP_ERROR for errors
441  * found by inspecting the input data and for system problems, but
442  * DECOMP_FATALERROR for any errors which could possibly be said to
443  * be being detected "after" decompression.  For DECOMP_ERROR,
444  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
445  * infringing a patent of Motorola's if we do, so we take CCP down
446  * instead.
447  *
448  * Given that the frame has the correct sequence number and a good FCS,
449  * errors such as invalid codes in the input most likely indicate a
450  * bug, so we return DECOMP_FATALERROR for them in order to turn off
451  * compression, even though they are detected by inspecting the input.
452  */
453 int
454 z_decompress(void *arg, struct mbuf *mi, struct mbuf **mop)
455 {
456     struct deflate_state *state = (struct deflate_state *) arg;
457     struct mbuf *mo, *mo_head;
458     u_char *rptr, *wptr;
459     int rlen, olen, ospace;
460     int seq, i, flush, r, decode_proto;
461     u_char hdr[PPP_HDRLEN + DEFLATE_OVHD];
462
463     *mop = NULL;
464     rptr = mtod(mi, u_char *);
465     rlen = mi->m_len;
466     for (i = 0; i < PPP_HDRLEN + DEFLATE_OVHD; ++i) {
467         while (rlen <= 0) {
468             mi = mi->m_next;
469             if (mi == NULL)
470                 return DECOMP_ERROR;
471             rptr = mtod(mi, u_char *);
472             rlen = mi->m_len;
473         }
474         hdr[i] = *rptr++;
475         --rlen;
476     }
477
478     /* Check the sequence number. */
479     seq = (hdr[PPP_HDRLEN] << 8) + hdr[PPP_HDRLEN+1];
480     if (seq != state->seqno) {
481         if (state->debug)
482             kprintf("z_decompress%d: bad seq # %d, expected %d\n",
483                    state->unit, seq, state->seqno);
484         return DECOMP_ERROR;
485     }
486     ++state->seqno;
487
488     /* Allocate an output mbuf. */
489     MGETHDR(mo, MB_DONTWAIT, MT_DATA);
490     if (mo == NULL)
491         return DECOMP_ERROR;
492     mo_head = mo;
493     mo->m_len = 0;
494     mo->m_next = NULL;
495     MCLGET(mo, MB_DONTWAIT);
496     ospace = M_TRAILINGSPACE(mo);
497     if (state->hdrlen + PPP_HDRLEN < ospace) {
498         mo->m_data += state->hdrlen;
499         ospace -= state->hdrlen;
500     }
501
502     /*
503      * Fill in the first part of the PPP header.  The protocol field
504      * comes from the decompressed data.
505      */
506     wptr = mtod(mo, u_char *);
507     wptr[0] = PPP_ADDRESS(hdr);
508     wptr[1] = PPP_CONTROL(hdr);
509     wptr[2] = 0;
510
511     /*
512      * Set up to call inflate.  We set avail_out to 1 initially so we can
513      * look at the first byte of the output and decide whether we have
514      * a 1-byte or 2-byte protocol field.
515      */
516     state->strm.next_in = rptr;
517     state->strm.avail_in = rlen;
518     mi = mi->m_next;
519     flush = (mi == NULL)? Z_PACKET_FLUSH: Z_NO_FLUSH;
520     rlen += PPP_HDRLEN + DEFLATE_OVHD;
521     state->strm.next_out = wptr + 3;
522     state->strm.avail_out = 1;
523     decode_proto = 1;
524     olen = PPP_HDRLEN;
525
526     /*
527      * Call inflate, supplying more input or output as needed.
528      */
529     for (;;) {
530         r = inflate(&state->strm, flush);
531         if (r != Z_OK) {
532 #if !DEFLATE_DEBUG
533             if (state->debug)
534 #endif
535                 kprintf("z_decompress%d: inflate returned %d (%s)\n",
536                        state->unit, r, (state->strm.msg? state->strm.msg: ""));
537             m_freem(mo_head);
538             return DECOMP_FATALERROR;
539         }
540         if (flush != Z_NO_FLUSH && state->strm.avail_out != 0)
541             break;              /* all done */
542         if (state->strm.avail_in == 0 && mi != NULL) {
543             state->strm.next_in = mtod(mi, u_char *);
544             state->strm.avail_in = mi->m_len;
545             rlen += mi->m_len;
546             mi = mi->m_next;
547             if (mi == NULL)
548                 flush = Z_PACKET_FLUSH;
549         }
550         if (state->strm.avail_out == 0) {
551             if (decode_proto) {
552                 state->strm.avail_out = ospace - PPP_HDRLEN;
553                 if ((wptr[3] & 1) == 0) {
554                     /* 2-byte protocol field */
555                     wptr[2] = wptr[3];
556                     --state->strm.next_out;
557                     ++state->strm.avail_out;
558                     --olen;
559                 }
560                 decode_proto = 0;
561             } else {
562                 mo->m_len = ospace;
563                 olen += ospace;
564                 MGET(mo->m_next, MB_DONTWAIT, MT_DATA);
565                 mo = mo->m_next;
566                 if (mo == NULL) {
567                     m_freem(mo_head);
568                     return DECOMP_ERROR;
569                 }
570                 MCLGET(mo, MB_DONTWAIT);
571                 state->strm.next_out = mtod(mo, u_char *);
572                 state->strm.avail_out = ospace = M_TRAILINGSPACE(mo);
573             }
574         }
575     }
576     if (decode_proto) {
577         m_freem(mo_head);
578         return DECOMP_ERROR;
579     }
580     olen += (mo->m_len = ospace - state->strm.avail_out);
581 #if DEFLATE_DEBUG
582     if (state->debug && olen > state->mru + PPP_HDRLEN)
583         kprintf("ppp_deflate%d: exceeded mru (%d > %d)\n",
584                state->unit, olen, state->mru + PPP_HDRLEN);
585 #endif
586
587     state->stats.unc_bytes += olen;
588     state->stats.unc_packets++;
589     state->stats.comp_bytes += rlen;
590     state->stats.comp_packets++;
591
592     *mop = mo_head;
593     return DECOMP_OK;
594 }
595
596 /*
597  * Incompressible data has arrived - add it to the history.
598  */
599 static void
600 z_incomp(void *arg, struct mbuf *mi)
601 {
602     struct deflate_state *state = (struct deflate_state *) arg;
603     u_char *rptr;
604     int rlen, proto, r;
605
606     /*
607      * Check that the protocol is one we handle.
608      */
609     rptr = mtod(mi, u_char *);
610     proto = PPP_PROTOCOL(rptr);
611     if (proto > 0x3fff || proto == 0xfd || proto == 0xfb)
612         return;
613
614     ++state->seqno;
615
616     /*
617      * Iterate through the mbufs, adding the characters in them
618      * to the decompressor's history.  For the first mbuf, we start
619      * at the either the 1st or 2nd byte of the protocol field,
620      * depending on whether the protocol value is compressible.
621      */
622     rlen = mi->m_len;
623     state->strm.next_in = rptr + 3;
624     state->strm.avail_in = rlen - 3;
625     if (proto > 0xff) {
626         --state->strm.next_in;
627         ++state->strm.avail_in;
628     }
629     for (;;) {
630         r = inflateIncomp(&state->strm);
631         if (r != Z_OK) {
632             /* gak! */
633 #if !DEFLATE_DEBUG
634             if (state->debug)
635 #endif
636                 kprintf("z_incomp%d: inflateIncomp returned %d (%s)\n",
637                        state->unit, r, (state->strm.msg? state->strm.msg: ""));
638             return;
639         }
640         mi = mi->m_next;
641         if (mi == NULL)
642             break;
643         state->strm.next_in = mtod(mi, u_char *);
644         state->strm.avail_in = mi->m_len;
645         rlen += mi->m_len;
646     }
647
648     /*
649      * Update stats.
650      */
651     state->stats.inc_bytes += rlen;
652     state->stats.inc_packets++;
653     state->stats.unc_bytes += rlen;
654     state->stats.unc_packets++;
655 }
656
657 #endif /* DO_DEFLATE */