Index: uspace/lib/compress/Makefile =================================================================== --- uspace/lib/compress/Makefile (revision e37ddde16660f8897030fbc536ff4ff973c03065) +++ uspace/lib/compress/Makefile (revision e37ddde16660f8897030fbc536ff4ff973c03065) @@ -0,0 +1,36 @@ +# +# Copyright (c) 2014 Martin Decky +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# + +USPACE_PREFIX = ../.. +LIBRARY = libcompress + +SOURCES = \ + inflate.c \ + gzip.c + +include $(USPACE_PREFIX)/Makefile.common Index: uspace/lib/compress/gzip.c =================================================================== --- uspace/lib/compress/gzip.c (revision e37ddde16660f8897030fbc536ff4ff973c03065) +++ uspace/lib/compress/gzip.c (revision e37ddde16660f8897030fbc536ff4ff973c03065) @@ -0,0 +1,182 @@ +/* + * Copyright (c) 2014 Martin Decky + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include +#include +#include +#include "gzip.h" +#include "inflate.h" + +#define GZIP_ID1 UINT8_C(0x1f) +#define GZIP_ID2 UINT8_C(0x8b) + +#define GZIP_METHOD_DEFLATE UINT8_C(0x08) + +#define GZIP_FLAGS_MASK UINT8_C(0x1f) +#define GZIP_FLAG_FHCRC UINT8_C(1 << 1) +#define GZIP_FLAG_FEXTRA UINT8_C(1 << 2) +#define GZIP_FLAG_FNAME UINT8_C(1 << 3) +#define GZIP_FLAG_FCOMMENT UINT8_C(1 << 4) + +typedef struct { + uint8_t id1; + uint8_t id2; + uint8_t method; + uint8_t flags; + uint32_t mtime; + uint8_t extra_flags; + uint8_t os; +} __attribute__((packed)) gzip_header_t; + +typedef struct { + uint32_t crc32; + uint32_t size; +} __attribute__((packed)) gzip_footer_t; + +/** Expand GZIP compressed data + * + * The routine allocates the output buffer based + * on the size encoded in the input stream. This + * effectively limits the size of the uncompressed + * data to 4 GiB (expanding input streams that actually + * encode more data will always fail). + * + * So far, no CRC is perfomed. + * + * @param[in] src Source data buffer. + * @param[in] srclen Source buffer size (bytes). + * @param[out] dest Destination data buffer. + * @param[out] destlen Destination buffer size (bytes). + * + * @return EOK on success. + * @return ENOENT on distance too large. + * @return EINVAL on invalid Huffman code, invalid deflate data, + * invalid compression method or invalid stream. + * @return ELIMIT on input buffer overrun. + * @return ENOMEM on output buffer overrun. + * + */ +int gzip_expand(void *src, size_t srclen, void **dest, size_t *destlen) +{ + gzip_header_t header; + gzip_footer_t footer; + + if ((srclen < sizeof(header)) || (srclen < sizeof(footer))) + return EINVAL; + + /* Decode header and footer */ + + memcpy(&header, src, sizeof(header)); + memcpy(&footer, src + srclen - sizeof(footer), sizeof(footer)); + + if ((header.id1 != GZIP_ID1) || + (header.id2 != GZIP_ID2) || + (header.method != GZIP_METHOD_DEFLATE) || + ((header.flags & (~GZIP_FLAGS_MASK)) != 0)) + return EINVAL; + + *destlen = footer.size; + + /* Ignore extra metadata */ + + void *stream = src + sizeof(header); + size_t stream_length = srclen - sizeof(header) - sizeof(footer); + + if ((header.flags & GZIP_FLAG_FEXTRA) != 0) { + uint16_t extra_length; + + if (stream_length < sizeof(extra_length)) + return EINVAL; + + memcpy(&extra_length, stream, sizeof(extra_length)); + stream += sizeof(extra_length); + stream_length -= sizeof(extra_length); + + if (stream_length < extra_length) + return EINVAL; + + stream += extra_length; + stream_length -= extra_length; + } + + if ((header.flags & GZIP_FLAG_FNAME) != 0) { + while (*((uint8_t *) stream) != 0) { + if (stream_length == 0) + return EINVAL; + + stream++; + stream_length--; + } + + if (stream_length == 0) + return EINVAL; + + stream++; + stream_length--; + } + + if ((header.flags & GZIP_FLAG_FCOMMENT) != 0) { + while (*((uint8_t *) stream) != 0) { + if (stream_length == 0) + return EINVAL; + + stream++; + stream_length--; + } + + if (stream_length == 0) + return EINVAL; + + stream++; + stream_length--; + } + + if ((header.flags & GZIP_FLAG_FHCRC) != 0) { + if (stream_length < 2) + return EINVAL; + + stream += 2; + stream_length -= 2; + } + + /* Allocate output buffer and inflate the data */ + + *dest = malloc(*destlen); + if (*dest == NULL) + return ENOMEM; + + int ret = inflate(stream, stream_length, *dest, *destlen); + if (ret != EOK) { + free(dest); + return ret; + } + + return EOK; +} Index: uspace/lib/compress/gzip.h =================================================================== --- uspace/lib/compress/gzip.h (revision e37ddde16660f8897030fbc536ff4ff973c03065) +++ uspace/lib/compress/gzip.h (revision e37ddde16660f8897030fbc536ff4ff973c03065) @@ -0,0 +1,36 @@ +/* + * Copyright (c) 2014 Martin Decky + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCOMPRESS_GZIP_H_ +#define LIBCOMPRESS_GZIP_H_ + +#include + +extern int gzip_expand(void *, size_t, void **, size_t *); + +#endif Index: uspace/lib/compress/inflate.c =================================================================== --- uspace/lib/compress/inflate.c (revision e37ddde16660f8897030fbc536ff4ff973c03065) +++ uspace/lib/compress/inflate.c (revision e37ddde16660f8897030fbc536ff4ff973c03065) @@ -0,0 +1,665 @@ +/* + * Copyright (c) 2010 Mark Adler + * Copyright (c) 2010 Martin Decky + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @file + * @brief Implementation of inflate decompression + * + * A simple inflate implementation (decompression of `deflate' stream as + * described by RFC 1951) based on puff.c by Mark Adler. This code is + * currently not optimized for speed but for readability. + * + * All dynamically allocated memory memory is taken from the stack. The + * stack usage should be typically bounded by 2 KB. + * + * Original copyright notice: + * + * Copyright (C) 2002-2010 Mark Adler, all rights reserved + * version 2.1, 4 Apr 2010 + * + * This software is provided 'as-is', without any express or implied + * warranty. In no event will the author be held liable for any damages + * arising from the use of this software. + * + * Permission is granted to anyone to use this software for any purpose, + * including commercial applications, and to alter it and redistribute it + * freely, subject to the following restrictions: + * + * 1. The origin of this software must not be misrepresented; you must not + * claim that you wrote the original software. If you use this software + * in a product, an acknowledgment in the product documentation would be + * appreciated but is not required. + * 2. Altered source versions must be plainly marked as such, and must not + * be misrepresented as being the original software. + * 3. This notice may not be removed or altered from any source + * distribution. + * + * Mark Adler + * + */ + +#include +#include +#include +#include +#include "inflate.h" + +/** Maximum bits in the Huffman code */ +#define MAX_HUFFMAN_BIT 15 + +/** Number of length codes */ +#define MAX_LEN 29 +/** Number of distance codes */ +#define MAX_DIST 30 +/** Number of order codes */ +#define MAX_ORDER 19 +/** Number of literal/length codes */ +#define MAX_LITLEN 286 +/** Number of fixed literal/length codes */ +#define MAX_FIXED_LITLEN 288 + +/** Number of all codes */ +#define MAX_CODE (MAX_LITLEN + MAX_DIST) + +/** Check for input buffer overrun condition */ +#define CHECK_OVERRUN(state) \ + do { \ + if ((state).overrun) \ + return ELIMIT; \ + } while (false) + + +/** Inflate algorithm state + * + */ +typedef struct { + uint8_t *dest; /**< Output buffer */ + size_t destlen; /**< Output buffer size */ + size_t destcnt; /**< Position in the output buffer */ + + uint8_t *src; /**< Input buffer */ + size_t srclen; /**< Input buffer size */ + size_t srccnt; /**< Position in the input buffer */ + + uint16_t bitbuf; /**< Bit buffer */ + size_t bitlen; /**< Number of bits in the bit buffer */ + + bool overrun; /**< Overrun condition */ +} inflate_state_t; + +/** Huffman code description + * + */ +typedef struct { + uint16_t *count; /**< Array of symbol counts */ + uint16_t *symbol; /**< Array of symbols */ +} huffman_t; + +/** Length codes + * + */ +static const uint16_t lens[MAX_LEN] = { + 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, + 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 +}; + +/** Extended length codes + * + */ +static const uint16_t lens_ext[MAX_LEN] = { + 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, + 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 +}; + +/** Distance codes + * + */ +static const uint16_t dists[MAX_DIST] = { + 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, + 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, + 8193, 12289, 16385, 24577 +}; + +/** Extended distance codes + * + */ +static const uint16_t dists_ext[MAX_DIST] = { + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, + 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, + 12, 12, 13, 13 +}; + +/** Order codes + * + */ +static const short order[MAX_ORDER] = { + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 +}; + +/** Static length symbol counts + * + */ +static uint16_t len_count[MAX_HUFFMAN_BIT + 1] = { + 0, 0, 0, 0, 0, 0, 0, 24, 152, 112, 0, 0, 0, 0, 0, 0 +}; + +/** Static length symbols + * + */ +static uint16_t len_symbol[MAX_FIXED_LITLEN] = { + 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, + 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 0, 1, 2, + 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, + 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, + 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, + 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, + 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, + 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, + 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, + 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, + 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, + 140, 141, 142, 143, 280, 281, 282, 283, 284, 285, 286, 287, 144, + 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, + 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, + 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, + 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, + 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, + 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, + 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, + 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, + 249, 250, 251, 252, 253, 254, 255 +}; + +/** Static distance symbol counts + * + */ +static uint16_t dist_count[MAX_HUFFMAN_BIT + 1] = { + 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 +}; + +/** Static distance symbols + * + */ +static uint16_t dist_symbol[MAX_DIST] = { + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, + 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 +}; + +/** Huffman code for lengths + * + */ +static huffman_t len_code = { + .count = len_count, + .symbol = len_symbol +}; + +/** Huffman code for distances + * + */ +static huffman_t dist_code = { + .count = dist_count, + .symbol = dist_symbol +}; + +/** Get bits from the bit buffer + * + * @param state Inflate state. + * @param cnt Number of bits to return (at most 16). + * + * @return Returned bits. + * + */ +static inline uint16_t get_bits(inflate_state_t *state, size_t cnt) +{ + /* Bit accumulator for at least 20 bits */ + uint32_t val = state->bitbuf; + + while (state->bitlen < cnt) { + if (state->srccnt == state->srclen) { + state->overrun = true; + return 0; + } + + /* Load 8 more bits */ + val |= ((uint32_t) state->src[state->srccnt]) << state->bitlen; + state->srccnt++; + state->bitlen += 8; + } + + /* Update bits in the buffer */ + state->bitbuf = (uint16_t) (val >> cnt); + state->bitlen -= cnt; + + return ((uint16_t) (val & ((1 << cnt) - 1))); +} + +/** Decode `stored' block + * + * @param state Inflate state. + * + * @return EOK on success. + * @return ELIMIT on input buffer overrun. + * @return ENOMEM on output buffer overrun. + * @return EINVAL on invalid data. + * + */ +static int inflate_stored(inflate_state_t *state) +{ + /* Discard bits in the bit buffer */ + state->bitbuf = 0; + state->bitlen = 0; + + if (state->srccnt + 4 > state->srclen) + return ELIMIT; + + uint16_t len = + state->src[state->srccnt] | (state->src[state->srccnt + 1] << 8); + uint16_t len_compl = + state->src[state->srccnt + 2] | (state->src[state->srccnt + 3] << 8); + + /* Check block length and its complement */ + if (((int16_t) len) != ~((int16_t) len_compl)) + return EINVAL; + + state->srccnt += 4; + + /* Check input buffer size */ + if (state->srccnt + len > state->srclen) + return ELIMIT; + + /* Check output buffer size */ + if (state->destcnt + len > state->destlen) + return ENOMEM; + + /* Copy data */ + memcpy(state->dest + state->destcnt, state->src + state->srccnt, len); + state->srccnt += len; + state->destcnt += len; + + return EOK; +} + +/** Decode a symbol using the Huffman code + * + * @param state Inflate state. + * @param huffman Huffman code. + * @param symbol Decoded symbol. + * + * @param EOK on success. + * @param EINVAL on invalid Huffman code. + * + */ +static int huffman_decode(inflate_state_t *state, huffman_t *huffman, + uint16_t *symbol) +{ + uint16_t code = 0; /* Decoded bits */ + size_t first = 0; /* First code of the given length */ + size_t index = 0; /* Index of the first code of the given length + in the symbol table */ + + size_t len; /* Current number of bits in the code */ + for (len = 1; len <= MAX_HUFFMAN_BIT; len++) { + /* Get next bit */ + code |= get_bits(state, 1); + CHECK_OVERRUN(*state); + + uint16_t count = huffman->count[len]; + if (code < first + count) { + /* Return decoded symbol */ + *symbol = huffman->symbol[index + code - first]; + return EOK; + } + + /* Update for next length */ + index += count; + first += count; + first <<= 1; + code <<= 1; + } + + return EINVAL; +} + +/** Construct Huffman tables from canonical Huffman code + * + * @param huffman Constructed Huffman tables. + * @param length Lengths of the canonical Huffman code. + * @param n Number of lengths. + * + * @return 0 if the Huffman code set is complete. + * @return Negative value for an over-subscribed code set. + * @return Positive value for an incomplete code set. + * + */ +static int16_t huffman_construct(huffman_t *huffman, uint16_t *length, size_t n) +{ + /* Count number of codes for each length */ + size_t len; + for (len = 0; len <= MAX_HUFFMAN_BIT; len++) + huffman->count[len] = 0; + + /* We assume that the lengths are within bounds */ + size_t symbol; + for (symbol = 0; symbol < n; symbol++) + huffman->count[length[symbol]]++; + + if (huffman->count[0] == n) { + /* The code is complete, but decoding will fail */ + return 0; + } + + /* Check for an over-subscribed or incomplete set of lengths */ + int16_t left = 1; + for (len = 1; len <= MAX_HUFFMAN_BIT; len++) { + left <<= 1; + left -= huffman->count[len]; + if (left < 0) { + /* Over-subscribed */ + return left; + } + } + + /* Generate offsets into symbol table */ + uint16_t offs[MAX_HUFFMAN_BIT + 1]; + + offs[1] = 0; + for (len = 1; len < MAX_HUFFMAN_BIT; len++) + offs[len + 1] = offs[len] + huffman->count[len]; + + for (symbol = 0; symbol < n; symbol++) { + if (length[symbol] != 0) { + huffman->symbol[offs[length[symbol]]] = symbol; + offs[length[symbol]]++; + } + } + + return left; +} + +/** Decode literal/length and distance codes + * + * Decode until end-of-block code. + * + * @param state Inflate state. + * @param len_code Huffman code for literal/length. + * @param dist_code Huffman code for distance. + * + * @return EOK on success. + * @return ENOENT on distance too large. + * @return EINVAL on invalid Huffman code. + * @return ELIMIT on input buffer overrun. + * @return ENOMEM on output buffer overrun. + * + */ +static int inflate_codes(inflate_state_t *state, huffman_t* len_code, + huffman_t* dist_code) +{ + uint16_t symbol; + + do { + int err = huffman_decode(state, len_code, &symbol); + if (err != EOK) { + /* Error decoding */ + return err; + } + + if (symbol < 256) { + /* Write out literal */ + if (state->destcnt == state->destlen) + return ENOMEM; + + state->dest[state->destcnt] = (uint8_t) symbol; + state->destcnt++; + } else if (symbol > 256) { + /* Compute length */ + symbol -= 257; + if (symbol >= 29) + return EINVAL; + + size_t len = lens[symbol] + get_bits(state, lens_ext[symbol]); + CHECK_OVERRUN(*state); + + /* Get distance */ + err = huffman_decode(state, dist_code, &symbol); + if (err != EOK) + return err; + + size_t dist = dists[symbol] + get_bits(state, dists_ext[symbol]); + if (dist > state->destcnt) + return ENOENT; + + if (state->destcnt + len > state->destlen) + return ENOMEM; + + while (len > 0) { + /* Copy len bytes from distance bytes back */ + state->dest[state->destcnt] + = state->dest[state->destcnt - dist]; + state->destcnt++; + len--; + } + } + } while (symbol != 256); + + return EOK; +} + +/** Decode `fixed codes' block + * + * @param state Inflate state. + * @param len_code Huffman code for literal/length. + * @param dist_code Huffman code for distance. + * + * @return EOK on success. + * @return ENOENT on distance too large. + * @return EINVAL on invalid Huffman code. + * @return ELIMIT on input buffer overrun. + * @return ENOMEM on output buffer overrun. + * + */ +static int inflate_fixed(inflate_state_t *state, huffman_t *len_code, + huffman_t *dist_code) +{ + return inflate_codes(state, len_code, dist_code); +} + +/** Decode `dynamic codes' block + * + * @param state Inflate state. + * + * @return EOK on success. + * @return ENOENT on distance too large. + * @return EINVAL on invalid Huffman code. + * @return ELIMIT on input buffer overrun. + * @return ENOMEM on output buffer overrun. + * + */ +static int inflate_dynamic(inflate_state_t *state) +{ + uint16_t length[MAX_CODE]; + uint16_t dyn_len_count[MAX_HUFFMAN_BIT + 1]; + uint16_t dyn_len_symbol[MAX_LITLEN]; + uint16_t dyn_dist_count[MAX_HUFFMAN_BIT + 1]; + uint16_t dyn_dist_symbol[MAX_DIST]; + huffman_t dyn_len_code; + huffman_t dyn_dist_code; + + dyn_len_code.count = dyn_len_count; + dyn_len_code.symbol = dyn_len_symbol; + + dyn_dist_code.count = dyn_dist_count; + dyn_dist_code.symbol = dyn_dist_symbol; + + /* Get number of bits in each table */ + uint16_t nlen = get_bits(state, 5) + 257; + CHECK_OVERRUN(*state); + + uint16_t ndist = get_bits(state, 5) + 1; + CHECK_OVERRUN(*state); + + uint16_t ncode = get_bits(state, 4) + 4; + CHECK_OVERRUN(*state); + + if ((nlen > MAX_LITLEN) || (ndist > MAX_DIST) + || (ncode > MAX_ORDER)) + return EINVAL; + + /* Read code length code lengths */ + uint16_t index; + for (index = 0; index < ncode; index++) { + length[order[index]] = get_bits(state, 3); + CHECK_OVERRUN(*state); + } + + /* Set missing lengths to zero */ + for (index = ncode; index < MAX_ORDER; index++) + length[order[index]] = 0; + + /* Build Huffman code */ + int16_t rc = huffman_construct(&dyn_len_code, length, MAX_ORDER); + if (rc != 0) + return EINVAL; + + /* Read length/literal and distance code length tables */ + index = 0; + while (index < nlen + ndist) { + uint16_t symbol; + int err = huffman_decode(state, &dyn_len_code, &symbol); + if (err != EOK) + return EOK; + + if (symbol < 16) { + length[index] = symbol; + index++; + } else { + uint16_t len = 0; + + if (symbol == 16) { + if (index == 0) + return EINVAL; + + len = length[index - 1]; + symbol = get_bits(state, 2) + 3; + CHECK_OVERRUN(*state); + } else if (symbol == 17) { + symbol = get_bits(state, 3) + 3; + CHECK_OVERRUN(*state); + } else { + symbol = get_bits(state, 7) + 11; + CHECK_OVERRUN(*state); + } + + if (index + symbol > nlen + ndist) + return EINVAL; + + while (symbol > 0) { + length[index] = len; + index++; + symbol--; + } + } + } + + /* Check for end-of-block code */ + if (length[256] == 0) + return EINVAL; + + /* Build Huffman tables for literal/length codes */ + rc = huffman_construct(&dyn_len_code, length, nlen); + if ((rc < 0) || ((rc > 0) && (dyn_len_code.count[0] + 1 != nlen))) + return EINVAL; + + /* Build Huffman tables for distance codes */ + rc = huffman_construct(&dyn_dist_code, length + nlen, ndist); + if ((rc < 0) || ((rc > 0) && (dyn_dist_code.count[0] + 1 != ndist))) + return EINVAL; + + return inflate_codes(state, &dyn_len_code, &dyn_dist_code); +} + +/** Inflate data + * + * @param src Source data buffer. + * @param srclen Source buffer size (bytes). + * @param dest Destination data buffer. + * @param destlen Destination buffer size (bytes). + * + * @return EOK on success. + * @return ENOENT on distance too large. + * @return EINVAL on invalid Huffman code or invalid deflate data. + * @return ELIMIT on input buffer overrun. + * @return ENOMEM on output buffer overrun. + * + */ +int inflate(void *src, size_t srclen, void *dest, size_t destlen) +{ + /* Initialize the state */ + inflate_state_t state; + + state.dest = (uint8_t *) dest; + state.destlen = destlen; + state.destcnt = 0; + + state.src = (uint8_t *) src; + state.srclen = srclen; + state.srccnt = 0; + + state.bitbuf = 0; + state.bitlen = 0; + + state.overrun = false; + + uint16_t last; + int ret = 0; + + do { + /* Last block is indicated by a non-zero bit */ + last = get_bits(&state, 1); + CHECK_OVERRUN(state); + + /* Block type */ + uint16_t type = get_bits(&state, 2); + CHECK_OVERRUN(state); + + switch (type) { + case 0: + ret = inflate_stored(&state); + break; + case 1: + ret = inflate_fixed(&state, &len_code, &dist_code); + break; + case 2: + ret = inflate_dynamic(&state); + break; + default: + ret = EINVAL; + } + } while ((!last) && (ret == 0)); + + return ret; +} Index: uspace/lib/compress/inflate.h =================================================================== --- uspace/lib/compress/inflate.h (revision e37ddde16660f8897030fbc536ff4ff973c03065) +++ uspace/lib/compress/inflate.h (revision e37ddde16660f8897030fbc536ff4ff973c03065) @@ -0,0 +1,36 @@ +/* + * Copyright (c) 2010 Martin Decky + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCOMPRESS_INFLATE_H_ +#define LIBCOMPRESS_INFLATE_H_ + +#include + +extern int inflate(void *, size_t, void *, size_t); + +#endif