sys/opencrypto/deflate.c

   1 /*      $NetBSD: deflate.c,v 1.12 2009/03/14 15:36:24 dsl Exp $ */
   2 /*      $FreeBSD: src/sys/opencrypto/deflate.c,v 1.1.2.1 2002/11/21 23:34:23 sam Exp $  */
   3 /* $OpenBSD: deflate.c,v 1.3 2001/08/20 02:45:22 hugh Exp $ */
   4
   5 /*
   6  * Copyright (c) 2001 Jean-Jacques Bernard-Gundol (jj@wabbitt.org)
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *   notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *   notice, this list of conditions and the following disclaimer in the
  16  *   documentation and/or other materials provided with the distribution.
  17  * 3. The name of the author may not be used to endorse or promote products
  18  *   derived from this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  21  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  22  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  23  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  29  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*
  33  * This file contains a wrapper around the deflate algo compression
  34  * functions using the zlib library (see net/zlib.{c,h})
  35  */
  36
  37 #include <sys/cdefs.h>
  38 __KERNEL_RCSID(0, "$NetBSD: deflate.c,v 1.12 2009/03/14 15:36:24 dsl Exp $");
  39
  40 #include <sys/types.h>
  41 #include <sys/malloc.h>
  42 #include <sys/param.h>
  43 #include <sys/systm.h>
  44 #include <net/zlib.h>
  45
  46 #include <opencrypto/cryptodev.h>
  47 #include <opencrypto/deflate.h>
  48
  49
  50 int window_inflate = -1 * MAX_WBITS;
  51 int window_deflate = -12;
  52
  53 /*
  54  * This function takes a block of data and (de)compress it using the deflate
  55  * algorithm
  56  */
  57
  58 static void *
  59 ocf_zalloc(void *nil, u_int type, u_int size)
  60 {
  61         void *ptr;
  62
  63         ptr = malloc(type *size, M_CRYPTO_DATA, M_NOWAIT);
  64         return ptr;
  65 }
  66
  67 static void
  68 ocf_zfree(void *nil, void *ptr)
  69 {
  70         free(ptr, M_CRYPTO_DATA);
  71 }
  72
  73 u_int32_t
  74 deflate_global(u_int8_t *data, u_int32_t size, int decomp, u_int8_t **out)
  75 {
  76         /* decomp indicates whether we compress (0) or decompress (1) */
  77
  78         z_stream zbuf;
  79         u_int8_t *output;
  80         u_int32_t count, result;
  81         int error, i = 0, j;
  82         struct deflate_buf *buf, *tmp;
  83         size_t len, old_len;
  84
  85         DPRINTF(("deflate_global: size %d\n", size));
  86
  87         len = ZBUF;
  88         buf = malloc(len*sizeof(struct deflate_buf), M_CRYPTO_DATA, M_NOWAIT);
  89         if (buf == NULL)
  90                 return 0;
  91
  92         memset(&zbuf, 0, sizeof(z_stream));
  93         for (j = 0; j < len; j++)
  94                 buf[j].flag = 0;
  95
  96         zbuf.next_in = data;    /* data that is going to be processed */
  97         zbuf.zalloc = ocf_zalloc;
  98         zbuf.zfree = ocf_zfree;
  99         zbuf.opaque = Z_NULL;
 100         zbuf.avail_in = size;   /* Total length of data to be processed */
 101
 102         if (!decomp) {
 103                 buf[i].out = malloc(size, M_CRYPTO_DATA, M_NOWAIT);
 104                 if (buf[i].out == NULL)
 105                         goto bad;
 106                 buf[i].size = size;
 107                 buf[i].flag = 1;
 108                 i++;
 109         } else {
 110                 /*
 111                  * Choose a buffer with 4x the size of the input buffer
 112                  * for the size of the output buffer in the case of
 113                  * decompression. If it's not sufficient, it will need to be
 114                  * updated while the decompression is going on
 115                  */
 116
 117                 buf[i].size = size * 4;
 118                 buf[i].out = malloc(buf[i].size, M_CRYPTO_DATA, M_NOWAIT);
 119                 if (buf[i].out == NULL)
 120                         goto bad;
 121                 buf[i].flag = 1;
 122                 i++;
 123         }
 124
 125         zbuf.next_out = buf[0].out;
 126         zbuf.avail_out = buf[0].size;
 127
 128         error = decomp ? inflateInit2(&zbuf, window_inflate) :
 129             deflateInit2(&zbuf, Z_DEFAULT_COMPRESSION, Z_METHOD,
 130                     window_deflate, Z_MEMLEVEL, Z_DEFAULT_STRATEGY);
 131
 132         if (error != Z_OK)
 133                 goto bad;
 134         for (;;) {
 135                 error = decomp ? inflate(&zbuf, Z_PARTIAL_FLUSH) :
 136                                  deflate(&zbuf, Z_PARTIAL_FLUSH);
 137                 if (error != Z_OK && error != Z_STREAM_END)
 138                         goto bad;
 139                 else if (zbuf.avail_in == 0 && zbuf.avail_out != 0)
 140                         goto end;
 141                 else if (zbuf.avail_out == 0) {
 142                         if (i == (len-1)) {
 143                                 old_len = i;
 144                                 len += ZBUF;
 145                                 tmp = realloc(buf,len*sizeof(struct deflate_buf),
 146                                                           M_CRYPTO_DATA, M_NOWAIT);
 147                                 if (tmp == NULL)
 148                                         goto bad;
 149                                 buf = tmp;
 150                                 for (j = old_len; j < len; j++)
 151                                         buf[j].flag = 0;
 152                         }
 153                         /* we need more output space, allocate size */
 154                         buf[i].out = malloc(size, M_CRYPTO_DATA, M_NOWAIT);
 155                         if (buf[i].out == NULL)
 156                                 goto bad;
 157                         zbuf.next_out = buf[i].out;
 158                         buf[i].size = size;
 159                         buf[i].flag = 1;
 160                         zbuf.avail_out = buf[i].size;
 161                         i++;
 162                 } else
 163                         goto bad;
 164         }
 165
 166 end:
 167         result = count = zbuf.total_out;
 168
 169         *out = malloc(result, M_CRYPTO_DATA, M_NOWAIT);
 170         if (*out == NULL)
 171                 goto bad;
 172         if (decomp)
 173                 inflateEnd(&zbuf);
 174         else
 175                 deflateEnd(&zbuf);
 176         output = *out;
 177         for (j = 0; buf[j].flag != 0; j++) {
 178                 if (count > buf[j].size) {
 179                         memcpy(*out, buf[j].out, buf[j].size);
 180                         *out += buf[j].size;
 181                         free(buf[j].out, M_CRYPTO_DATA);
 182                         count -= buf[j].size;
 183                 } else {
 184                         /* it should be the last buffer */
 185                         memcpy(*out, buf[j].out, count);
 186                         *out += count;
 187                         free(buf[j].out, M_CRYPTO_DATA);
 188                         count = 0;
 189                 }
 190         }
 191         free(buf, M_CRYPTO_DATA);
 192         *out = output;
 193         return result;
 194
 195 bad:
 196         *out = NULL;
 197         for (j = 0; buf[j].flag != 0; j++)
 198                 free(buf[j].out, M_CRYPTO_DATA);
 199         free(buf, M_CRYPTO_DATA);
 200         if (decomp)
 201                 inflateEnd(&zbuf);
 202         else
 203                 deflateEnd(&zbuf);
 204         return 0;
 205 }
 206
 207 /*
 208  * Initial version will perform a single gzip encapsulation,
 209  * filling in the header,
 210  * and appending the crc and uncompressed length.
 211  *
 212  * Later version will support multiple buffers with
 213  * a flag indication final buffer.  The crc is maintained
 214  * over all buffers and appended to the output along with
 215  * the uncompressed length after the final data buffer
 216  * has been compressed and output.
 217  *
 218  * Ditto for uncompress - CRC is extracted from the final packed
 219  * and compared against CRC of uncompressed data.
 220  *
 221  */
 222
 223 /* constant header for the gzip */
 224 static const char gzip_header[10] = {
 225         0x1f, 0x8b,     /* ID1 ID2      */
 226         Z_DEFLATED,     /* CM           */
 227         0,              /* FLG          */
 228         0, 0, 0, 0,     /* MTIME        */
 229         0,              /* XFL          */
 230         0x03            /* OS (Unix)    */
 231 };
 232
 233 /* Followed by compressed payload */
 234 /* Followed by uint32_t CRC32 and uint32_t ISIZE */
 235 #define GZIP_TAIL_SIZE  8
 236
 237 u_int32_t
 238 gzip_global(u_int8_t *data, u_int32_t size,
 239         int decomp, u_int8_t **out)
 240 {
 241         /* decomp indicates whether we compress (0) or decompress (1) */
 242         z_stream zbuf;
 243         u_int8_t *output;
 244         u_int32_t count, result;
 245         int error, i = 0, j;
 246         struct deflate_buf *buf, *tmp;
 247         size_t nbufs, old_nbufs;
 248         u_int32_t crc;
 249         u_int32_t isize;
 250
 251         DPRINTF(("gzip_global: decomp %d, size %d\n", decomp, size));
 252
 253         nbufs = ZBUF;
 254         buf = malloc(nbufs*sizeof(struct deflate_buf), M_CRYPTO_DATA, M_NOWAIT);
 255         if (buf == NULL) {
 256                 DPRINTF(("gzip_global.%d: failed to malloc %d\n",
 257                                 __LINE__, nbufs*sizeof(struct deflate_buf)));
 258                 return 0;
 259         }
 260
 261         memset(&zbuf, 0, sizeof(z_stream));
 262         for (j = 0; j < nbufs; j++)
 263                 buf[j].flag = 0;
 264
 265         zbuf.zalloc = ocf_zalloc;
 266         zbuf.zfree = ocf_zfree;
 267         zbuf.opaque = Z_NULL;
 268
 269         crc = crc32(0, NULL, 0);        /* get initial crc value */
 270
 271         zbuf.avail_in = size;   /* Total length of data to be processed */
 272         zbuf.next_in = data;    /* data that is going to be processed */
 273
 274         if (!decomp) {
 275                 /* compress */
 276                 DPRINTF(("gzip_global: compress[%d] malloc %d + %d + %d = %d\n",
 277                                 i, size, sizeof(gzip_header), GZIP_TAIL_SIZE,
 278                                 size + sizeof(gzip_header) + GZIP_TAIL_SIZE));
 279
 280                 buf[i].out = malloc(size, M_CRYPTO_DATA, M_NOWAIT);
 281                 if (buf[i].out == NULL)
 282                         goto bad2;
 283                 buf[i].size = size;
 284                 buf[i].flag = 1;
 285
 286                 zbuf.next_out = buf[i].out;
 287                 zbuf.avail_out = buf[i].size;
 288                 i++;
 289
 290                 crc = crc32(crc, data, size);
 291                 DPRINTF(("gzip_compress: size %d, crc 0x%x\n", size, crc));
 292         } else {
 293                 /* decompress */
 294                 /* check the gzip header */
 295                 if (zbuf.avail_in <= 0) {
 296                         /* Not enough data for the header & tail */
 297                         DPRINTF(("gzip_global: not enough data (%d)\n",
 298                                         size));
 299                         goto bad2;
 300                 }
 301
 302                 /* XXX this is pretty basic,
 303                  * needs to be expanded to ignore MTIME, OS,
 304                  * but still ensure flags are 0.
 305                  * Q. Do we need to support the flags and
 306                  * optional header fields? Likely.
 307                  * XXX add flag and field support too.
 308                  */
 309                 if (memcmp(data, gzip_header, sizeof(gzip_header)) != 0) {
 310                         DPRINTF(("gzip_global: unsupported gzip header (%02x%02x)\n",
 311                                         data[0], data[1]));
 312                         goto bad2;
 313                 } else {
 314                         DPRINTF(("gzip_global.%d: gzip header ok\n",__LINE__));
 315                 }
 316
 317                 isize = *((uint32_t *)&data[size-sizeof(uint32_t)]);
 318
 319                 DPRINTF(("gzip_global: isize = %d (%02x %02x %02x %02x)\n",
 320                                 isize,
 321                                 data[size-4],
 322                                 data[size-3],
 323                                 data[size-2],
 324                                 data[size-1]));
 325
 326                 buf[i].size = isize;
 327                 buf[i].out = malloc(buf[i].size, M_CRYPTO_DATA, M_NOWAIT);
 328                 if (buf[i].out == NULL)
 329                         goto bad2;
 330                 buf[i].flag = 1;
 331                 zbuf.next_out = buf[i].out;
 332                 zbuf.avail_out = buf[i].size;
 333                 i++;
 334
 335                 /* skip over the gzip header */
 336                 zbuf.next_in = data + sizeof(gzip_header);
 337
 338                 /* actual payload size stripped of gzip header and tail */
 339                 zbuf.avail_in = size - sizeof(gzip_header) - GZIP_TAIL_SIZE;
 340                 DPRINTF(("zbuf avail_in %d, avail_out %d\n",
 341                                         zbuf.avail_in, zbuf.avail_out));
 342
 343         }
 344
 345
 346         error = decomp ? inflateInit2(&zbuf, window_inflate) :
 347             deflateInit2(&zbuf, Z_DEFAULT_COMPRESSION, Z_METHOD,
 348                     window_deflate, Z_MEMLEVEL, Z_DEFAULT_STRATEGY);
 349
 350         if (error != Z_OK) {
 351                 printf("deflateInit2() failed\n");
 352                 goto bad;
 353         }
 354         for (;;) {
 355                 DPRINTF(("pre: %s in:%d out:%d\n", decomp ? "deflate()" : "inflate()",
 356                                 zbuf.avail_in, zbuf.avail_out));
 357                 error = decomp ? inflate(&zbuf, Z_PARTIAL_FLUSH) :
 358                                  deflate(&zbuf, Z_PARTIAL_FLUSH);
 359                 DPRINTF(("post: %s in:%d out:%d\n", decomp ? "deflate()" : "inflate()",
 360                                 zbuf.avail_in, zbuf.avail_out));
 361                 if (error != Z_OK && error != Z_STREAM_END) {
 362                         printf("deflate() or inflate() failed, error=%d\n", error);
 363                         goto bad;
 364                 } else if (zbuf.avail_in == 0 && zbuf.avail_out != 0) {
 365                         DPRINTF(("gzip_global: avail_in == 0, ending\n"));
 366                         goto end;
 367                 } else if (zbuf.avail_in == 0 && zbuf.avail_out == 0) {
 368                         DPRINTF(("gzip_global: avail_in == 0, avail_out == 0, ending\n"));
 369                         goto end;
 370                 } else if (zbuf.avail_out == 0) {
 371                         if (i == (nbufs-1)) {
 372                                 old_nbufs = i;
 373                                 nbufs += ZBUF;
 374                                 tmp = realloc(buf,nbufs*sizeof(struct deflate_buf),
 375                                                           M_CRYPTO_DATA, M_NOWAIT);
 376                                 if (tmp == NULL)
 377                                         goto bad;
 378                                 buf = tmp;
 379                                 for (j = old_nbufs; j < nbufs; j++)
 380                                         buf[j].flag = 0;
 381                         }
 382                         /* we need more output space, allocate size */
 383                         buf[i].out = malloc(size, M_CRYPTO_DATA, M_NOWAIT);
 384                         if (buf[i].out == NULL)
 385                                 goto bad;
 386                         zbuf.next_out = buf[i].out;
 387                         buf[i].size = size;
 388                         buf[i].flag = 1;
 389                         zbuf.avail_out = buf[i].size;
 390                         i++;
 391                 } else
 392                         goto bad;
 393         }
 394
 395 end:
 396         if (decomp) {
 397                 count = result = zbuf.total_out;
 398         } else {
 399                 /* need room for header, CRC, and ISIZE */
 400                 result = zbuf.total_out + sizeof(gzip_header) + GZIP_TAIL_SIZE;
 401                 count = zbuf.total_out;
 402         }
 403
 404         DPRINTF(("gzip_global: in %d -> out %d\n", size, result));
 405
 406         *out = malloc(result, M_CRYPTO_DATA, M_NOWAIT);
 407         if (*out == NULL)
 408                 goto bad;
 409         output = *out;
 410         if (decomp)
 411                 inflateEnd(&zbuf);
 412         else {
 413                 deflateEnd(&zbuf);
 414
 415                 /* fill in gzip header */
 416                 memcpy(output, gzip_header, sizeof(gzip_header));
 417                 output += sizeof(gzip_header);
 418         }
 419         for (j = 0; buf[j].flag != 0; j++) {
 420                 if (decomp) {
 421                         /* update crc for decompressed data */
 422                         crc = crc32(crc, buf[j].out, buf[j].size);
 423                 }
 424                 if (count > buf[j].size) {
 425                         memcpy(output, buf[j].out, buf[j].size);
 426                         output += buf[j].size;
 427                         free(buf[j].out, M_CRYPTO_DATA);
 428                         count -= buf[j].size;
 429                 } else {
 430                         /* it should be the last buffer */
 431                         memcpy(output, buf[j].out, count);
 432                         output += count;
 433                         free(buf[j].out, M_CRYPTO_DATA);
 434                         count = 0;
 435                 }
 436         }
 437         free(buf, M_CRYPTO_DATA);
 438
 439         if (!decomp) {
 440                 /* fill in CRC and ISIZE */
 441                 ((uint32_t *)output)[0] = crc;
 442                 ((uint32_t *)output)[1] = size;
 443
 444                 DPRINTF(("gzip_global: size = 0x%x (%02x %02x %02x %02x)\n",
 445                                 size,
 446                                 output[7],
 447                                 output[3],
 448                                 output[5],
 449                                 output[4]));
 450         }
 451
 452         return result;
 453
 454 bad:
 455         if (decomp)
 456                 inflateEnd(&zbuf);
 457         else
 458                 deflateEnd(&zbuf);
 459 bad2:
 460         *out = NULL;
 461         for (j = 0; buf[j].flag != 0; j++)
 462                 free(buf[j].out, M_CRYPTO_DATA);
 463         free(buf, M_CRYPTO_DATA);
 464         return 0;
 465 }