diff options
Diffstat (limited to 'lib/compression')
| -rw-r--r-- | lib/compression/lzxpress.c | 312 | ||||
| -rw-r--r-- | lib/compression/lzxpress.h | 50 | ||||
| -rw-r--r-- | lib/compression/mszip.c | 676 | ||||
| -rw-r--r-- | lib/compression/mszip.h | 33 | ||||
| -rw-r--r-- | lib/compression/testsuite.c | 30 |
5 files changed, 1101 insertions, 0 deletions
diff --git a/lib/compression/lzxpress.c b/lib/compression/lzxpress.c new file mode 100644 index 0000000000..0abbfc4d3d --- /dev/null +++ b/lib/compression/lzxpress.c @@ -0,0 +1,312 @@ +/* + * Copyright (C) Matthieu Suiche 2008 + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. 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. + * + * 3. Neither the name of the author nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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 "replace.h" +#include "lzxpress.h" + + +#define __BUF_POS_CONST(buf,ofs)(((const uint8_t *)buf)+(ofs)) +#define __PULL_BYTE(buf,ofs) \ + ((uint8_t)((*__BUF_POS_CONST(buf,ofs)) & 0xFF)) + +#ifndef PULL_LE_UINT16 +#define PULL_LE_UINT16(buf,ofs) ((uint16_t)( \ + ((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+0))) << 0)) | \ + ((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+1))) << 8)) \ +)) +#endif + +#ifndef PULL_LE_UINT32 +#define PULL_LE_UINT32(buf,ofs) ((uint32_t)( \ + ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+0))) << 0)) | \ + ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+1))) << 8)) | \ + ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+2))) << 16)) | \ + ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+3))) << 24)) \ +)) +#endif + +ssize_t lzxpress_compress(const uint8_t *uncompressed, + uint32_t uncompressed_size, + uint8_t *compressed, + uint32_t max_compressed_size) +{ + uint32_t uncompressed_pos, compressed_pos, byte_left; + uint32_t max_offset, best_offset; + int32_t offset; + uint32_t max_len, len, best_len; + const uint8_t *str1, *str2; + uint32_t indic; + uint8_t *indic_pos; + uint32_t indic_bit, nibble_index; + + uint32_t metadata_size; + uint16_t metadata; + uint16_t *dest; + + if (!uncompressed_size) { + return 0; + } + + uncompressed_pos = 0; + indic = 0; + compressed_pos = sizeof(uint32_t); + indic_pos = &compressed[0]; + + byte_left = uncompressed_size; + indic_bit = 0; + nibble_index = 0; + + if (uncompressed_pos > XPRESS_BLOCK_SIZE) + return 0; + + do { + bool found = false; + + max_offset = uncompressed_pos; + + str1 = &uncompressed[uncompressed_pos]; + + best_len = 2; + best_offset = 0; + + max_offset = MIN(0x1FFF, max_offset); + + /* search for the longest match in the window for the lookahead buffer */ + for (offset = 1; (uint32_t)offset <= max_offset; offset++) { + str2 = &str1[-offset]; + + /* maximum len we can encode into metadata */ + max_len = MIN((255 + 15 + 7 + 3), byte_left); + + for (len = 0; (len < max_len) && (str1[len] == str2[len]); len++); + + /* + * We check if len is better than the value found before, including the + * sequence of identical bytes + */ + if (len > best_len) { + found = true; + best_len = len; + best_offset = offset; + } + } + + if (found) { + metadata_size = 0; + dest = (uint16_t *)&compressed[compressed_pos]; + + if (best_len < 10) { + /* Classical meta-data */ + metadata = (uint16_t)(((best_offset - 1) << 3) | (best_len - 3)); + dest[metadata_size / sizeof(uint16_t)] = metadata; + metadata_size += sizeof(uint16_t); + } else { + metadata = (uint16_t)(((best_offset - 1) << 3) | 7); + dest[metadata_size / sizeof(uint16_t)] = metadata; + metadata_size = sizeof(uint16_t); + + if (best_len < (15 + 7 + 3)) { + /* Shared byte */ + if (!nibble_index) { + compressed[compressed_pos + metadata_size] = (best_len - (3 + 7)) & 0xF; + metadata_size += sizeof(uint8_t); + } else { + compressed[nibble_index] &= 0xF; + compressed[nibble_index] |= (best_len - (3 + 7)) * 16; + } + } else if (best_len < (3 + 7 + 15 + 255)) { + /* Shared byte */ + if (!nibble_index) { + compressed[compressed_pos + metadata_size] = 15; + metadata_size += sizeof(uint8_t); + } else { + compressed[nibble_index] &= 0xF; + compressed[nibble_index] |= (15 * 16); + } + + /* Additionnal best_len */ + compressed[compressed_pos + metadata_size] = (best_len - (3 + 7 + 15)) & 0xFF; + metadata_size += sizeof(uint8_t); + } else { + /* Shared byte */ + if (!nibble_index) { + compressed[compressed_pos + metadata_size] |= 15; + metadata_size += sizeof(uint8_t); + } else { + compressed[nibble_index] |= 15 << 4; + } + + /* Additionnal best_len */ + compressed[compressed_pos + metadata_size] = 255; + + metadata_size += sizeof(uint8_t); + + compressed[compressed_pos + metadata_size] = (best_len - 3) & 0xFF; + compressed[compressed_pos + metadata_size + 1] = ((best_len - 3) >> 8) & 0xFF; + metadata_size += sizeof(uint16_t); + } + } + + indic |= 1 << (32 - ((indic_bit % 32) + 1)); + + if (best_len > 9) { + if (nibble_index == 0) { + nibble_index = compressed_pos + sizeof(uint16_t); + } else { + nibble_index = 0; + } + } + + compressed_pos += metadata_size; + uncompressed_pos += best_len; + byte_left -= best_len; + } else { + compressed[compressed_pos++] = uncompressed[uncompressed_pos++]; + byte_left--; + } + indic_bit++; + + if ((indic_bit - 1) % 32 > (indic_bit % 32)) { + *(uint32_t *)indic_pos = indic; + indic = 0; + indic_pos = &compressed[compressed_pos]; + compressed_pos += sizeof(uint32_t); + } + } while (byte_left > 3); + + do { + compressed[compressed_pos] = uncompressed[uncompressed_pos]; + indic_bit++; + + uncompressed_pos++; + compressed_pos++; + if (((indic_bit - 1) % 32) > (indic_bit % 32)){ + *(uint32_t *)indic_pos = indic; + indic = 0; + indic_pos = &compressed[compressed_pos]; + compressed_pos += sizeof(uint32_t); + } + } while (uncompressed_pos < uncompressed_size); + + if ((indic_bit % 32) > 0) { + for (; (indic_bit % 32) != 0; indic_bit++) + indic |= 0 << (32 - ((indic_bit % 32) + 1)); + + *(uint32_t *)indic_pos = indic; + compressed_pos += sizeof(uint32_t); + } + + return compressed_pos; +} + +ssize_t lzxpress_decompress(const uint8_t *input, + uint32_t input_size, + uint8_t *output, + uint32_t max_output_size) +{ + uint32_t output_index, input_index; + uint32_t indicator, indicator_bit; + uint32_t length; + uint32_t offset; + uint32_t nibble_index; + + output_index = 0; + input_index = 0; + indicator = 0; + indicator_bit = 0; + length = 0; + offset = 0; + nibble_index = 0; + + do { + if (indicator_bit == 0) { + indicator = PULL_LE_UINT32(input, input_index); + input_index += sizeof(uint32_t); + indicator_bit = 32; + } + indicator_bit--; + + /* + * check whether the bit specified by indicator_bit is set or not + * set in indicator. For example, if indicator_bit has value 4 + * check whether the 4th bit of the value in indicator is set + */ + if (((indicator >> indicator_bit) & 1) == 0) { + output[output_index] = input[input_index]; + input_index += sizeof(uint8_t); + output_index += sizeof(uint8_t); + } else { + length = PULL_LE_UINT16(input, input_index); + input_index += sizeof(uint16_t); + offset = length / 8; + length = length % 8; + + if (length == 7) { + if (nibble_index == 0) { + nibble_index = input_index; + length = input[input_index] % 16; + input_index += sizeof(uint8_t); + } else { + length = input[nibble_index] / 16; + nibble_index = 0; + } + + if (length == 15) { + length = input[input_index]; + input_index += sizeof(uint8_t); + if (length == 255) { + length = PULL_LE_UINT16(input, input_index); + input_index += sizeof(uint16_t); + length -= (15 + 7); + } + length += 15; + } + length += 7; + } + + length += 3; + + do { + if ((output_index >= max_output_size) || ((offset + 1) > output_index)) break; + + output[output_index] = output[output_index - offset - 1]; + + output_index += sizeof(uint8_t); + length -= sizeof(uint8_t); + } while (length != 0); + } + } while ((output_index < max_output_size) && (input_index < (input_size))); + + return output_index; +} diff --git a/lib/compression/lzxpress.h b/lib/compression/lzxpress.h new file mode 100644 index 0000000000..df0ee59a0e --- /dev/null +++ b/lib/compression/lzxpress.h @@ -0,0 +1,50 @@ +/* + * Copyright (C) Matthieu Suiche 2008 + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. 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. + * + * 3. Neither the name of the author nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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 _LZXPRESS_H +#define _LZXPRESS_H + +#define XPRESS_BLOCK_SIZE 0x10000 + +ssize_t lzxpress_compress(const uint8_t *uncompressed, + uint32_t uncompressed_size, + uint8_t *compressed, + uint32_t max_compressed_size); + +ssize_t lzxpress_decompress(const uint8_t *input, + uint32_t input_size, + uint8_t *output, + uint32_t max_output_size); + +#endif /* _LZXPRESS_H */ diff --git a/lib/compression/mszip.c b/lib/compression/mszip.c new file mode 100644 index 0000000000..9aa1772414 --- /dev/null +++ b/lib/compression/mszip.c @@ -0,0 +1,676 @@ +/* mszip decompression - based on cabextract.c code from + * Stuart Caie + * + * adapted for Samba by Andrew Tridgell and Stefan Metzmacher 2005 + * + * (C) 2000-2001 Stuart Caie <kyzer@4u.net> + * reaktivate-specifics by Malte Starostik <malte@kde.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, see <http://www.gnu.org/licenses/>. + */ + +#include "includes.h" +#include "../compression/mszip.h" + +/*--------------------------------------------------------------------------*/ +/* our archiver information / state */ + +/* MSZIP stuff */ +#define ZIPWSIZE 0x8000 /* window size */ +#define ZIPLBITS 9 /* bits in base literal/length lookup table */ +#define ZIPDBITS 6 /* bits in base distance lookup table */ +#define ZIPBMAX 16 /* maximum bit length of any code */ +#define ZIPN_MAX 288 /* maximum number of codes in any set */ + +struct Ziphuft { + uint8_t e; /* number of extra bits or operation */ + uint8_t b; /* number of bits in this code or subcode */ + union { + uint16_t n; /* literal, length base, or distance base */ + struct Ziphuft *t; /* pointer to next level of table */ + } v; +}; + +struct ZIPstate { + uint32_t window_posn; /* current offset within the window */ + uint32_t bb; /* bit buffer */ + uint32_t bk; /* bits in bit buffer */ + uint32_t ll[288+32]; /* literal/length and distance code lengths */ + uint32_t c[ZIPBMAX+1]; /* bit length count table */ + int32_t lx[ZIPBMAX+1]; /* memory for l[-1..ZIPBMAX-1] */ + struct Ziphuft *u[ZIPBMAX]; /* table stack */ + uint32_t v[ZIPN_MAX]; /* values in order of bit length */ + uint32_t x[ZIPBMAX+1]; /* bit offsets, then code stack */ + uint8_t *inpos; +}; + +/* generic stuff */ +#define CAB(x) (decomp_state->x) +#define ZIP(x) (decomp_state->methods.zip.x) + +/* CAB data blocks are <= 32768 bytes in uncompressed form. Uncompressed + * blocks have zero growth. MSZIP guarantees that it won't grow above + * uncompressed size by more than 12 bytes. LZX guarantees it won't grow + * more than 6144 bytes. + */ +#define CAB_BLOCKMAX (32768) +#define CAB_INPUTMAX (CAB_BLOCKMAX+6144) + +struct decomp_state { + struct folder *current; /* current folder we're extracting from */ + uint32_t offset; /* uncompressed offset within folder */ + uint8_t *outpos; /* (high level) start of data to use up */ + uint16_t outlen; /* (high level) amount of data to use up */ + uint16_t split; /* at which split in current folder? */ + int (*decompress)(int, int); /* the chosen compression func */ + uint8_t inbuf[CAB_INPUTMAX+2]; /* +2 for lzx bitbuffer overflows! */ + uint8_t outbuf[CAB_BLOCKMAX]; + union { + struct ZIPstate zip; + } methods; +}; + + +/* MSZIP decruncher */ + +/* Dirk Stoecker wrote the ZIP decoder, based on the InfoZip deflate code */ + +/* Tables for deflate from PKZIP's appnote.txt. */ +static const uint8_t Zipborder[] = /* Order of the bit length code lengths */ +{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; +static const uint16_t Zipcplens[] = /* Copy lengths for literal codes 257..285 */ +{ 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, 0, 0}; +static const uint16_t Zipcplext[] = /* Extra bits for literal codes 257..285 */ +{ 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, 99, 99}; /* 99==invalid */ +static const uint16_t Zipcpdist[] = /* Copy offsets for distance codes 0..29 */ +{ 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}; +static const uint16_t Zipcpdext[] = /* Extra bits for distance codes */ +{ 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}; + +/* And'ing with Zipmask[n] masks the lower n bits */ +static const uint16_t Zipmask[17] = { + 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, + 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff +}; + +#define ZIPNEEDBITS(n) {while(k<(n)){int32_t c=*(ZIP(inpos)++);\ + b|=((uint32_t)c)<<k;k+=8;}} +#define ZIPDUMPBITS(n) {b>>=(n);k-=(n);} + +static void Ziphuft_free(struct Ziphuft *t) +{ + register struct Ziphuft *p, *q; + + /* Go through linked list, freeing from the allocated (t[-1]) address. */ + p = t; + while (p != (struct Ziphuft *)NULL) + { + q = (--p)->v.t; + free(p); + p = q; + } +} + +static int32_t Ziphuft_build(struct decomp_state *decomp_state, + uint32_t *b, uint32_t n, uint32_t s, const uint16_t *d, const uint16_t *e, + struct Ziphuft **t, int32_t *m) +{ + uint32_t a; /* counter for codes of length k */ + uint32_t el; /* length of EOB code (value 256) */ + uint32_t f; /* i repeats in table every f entries */ + int32_t g; /* maximum code length */ + int32_t h; /* table level */ + register uint32_t i; /* counter, current code */ + register uint32_t j; /* counter */ + register int32_t k; /* number of bits in current code */ + int32_t *l; /* stack of bits per table */ + register uint32_t *p; /* pointer into ZIP(c)[],ZIP(b)[],ZIP(v)[] */ + register struct Ziphuft *q; /* points to current table */ + struct Ziphuft r; /* table entry for structure assignment */ + register int32_t w; /* bits before this table == (l * h) */ + uint32_t *xp; /* pointer into x */ + int32_t y; /* number of dummy codes added */ + uint32_t z; /* number of entries in current table */ + + l = ZIP(lx)+1; + + /* Generate counts for each bit length */ + el = n > 256 ? b[256] : ZIPBMAX; /* set length of EOB code, if any */ + + for(i = 0; i < ZIPBMAX+1; ++i) + ZIP(c)[i] = 0; + p = b; i = n; + do + { + ZIP(c)[*p]++; p++; /* assume all entries <= ZIPBMAX */ + } while (--i); + if (ZIP(c)[0] == n) /* null input--all zero length codes */ + { + *t = (struct Ziphuft *)NULL; + *m = 0; + return 0; + } + + /* Find minimum and maximum length, bound *m by those */ + for (j = 1; j <= ZIPBMAX; j++) + if (ZIP(c)[j]) + break; + k = j; /* minimum code length */ + if ((uint32_t)*m < j) + *m = j; + for (i = ZIPBMAX; i; i--) + if (ZIP(c)[i]) + break; + g = i; /* maximum code length */ + if ((uint32_t)*m > i) + *m = i; + + /* Adjust last length count to fill out codes, if needed */ + for (y = 1 << j; j < i; j++, y <<= 1) + if ((y -= ZIP(c)[j]) < 0) + return 2; /* bad input: more codes than bits */ + if ((y -= ZIP(c)[i]) < 0) + return 2; + ZIP(c)[i] += y; + + /* Generate starting offsets int32_to the value table for each length */ + ZIP(x)[1] = j = 0; + p = ZIP(c) + 1; xp = ZIP(x) + 2; + while (--i) + { /* note that i == g from above */ + *xp++ = (j += *p++); + } + + /* Make a table of values in order of bit lengths */ + p = b; i = 0; + do{ + if ((j = *p++) != 0) + ZIP(v)[ZIP(x)[j]++] = i; + } while (++i < n); + + + /* Generate the Huffman codes and for each, make the table entries */ + ZIP(x)[0] = i = 0; /* first Huffman code is zero */ + p = ZIP(v); /* grab values in bit order */ + h = -1; /* no tables yet--level -1 */ + w = l[-1] = 0; /* no bits decoded yet */ + ZIP(u)[0] = (struct Ziphuft *)NULL; /* just to keep compilers happy */ + q = (struct Ziphuft *)NULL; /* ditto */ + z = 0; /* ditto */ + + /* go through the bit lengths (k already is bits in shortest code) */ + for (; k <= g; k++) + { + a = ZIP(c)[k]; + while (a--) + { + /* here i is the Huffman code of length k bits for value *p */ + /* make tables up to required level */ + while (k > w + l[h]) + { + w += l[h++]; /* add bits already decoded */ + + /* compute minimum size table less than or equal to *m bits */ + z = (z = g - w) > (uint32_t)*m ? *m : z; /* upper limit */ + if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ + { /* too few codes for k-w bit table */ + f -= a + 1; /* deduct codes from patterns left */ + xp = ZIP(c) + k; + while (++j < z) /* try smaller tables up to z bits */ + { + if ((f <<= 1) <= *++xp) + break; /* enough codes to use up j bits */ + f -= *xp; /* else deduct codes from patterns */ + } + } + if ((uint32_t)w + j > el && (uint32_t)w < el) + j = el - w; /* make EOB code end at table */ + z = 1 << j; /* table entries for j-bit table */ + l[h] = j; /* set table size in stack */ + + /* allocate and link in new table */ + if (!(q = (struct Ziphuft *)SMB_MALLOC((z + 1)*sizeof(struct Ziphuft)))) + { + if(h) + Ziphuft_free(ZIP(u)[0]); + return 3; /* not enough memory */ + } + *t = q + 1; /* link to list for Ziphuft_free() */ + *(t = &(q->v.t)) = (struct Ziphuft *)NULL; + ZIP(u)[h] = ++q; /* table starts after link */ + + /* connect to last table, if there is one */ + if (h) + { + ZIP(x)[h] = i; /* save pattern for backing up */ + r.b = (uint8_t)l[h-1]; /* bits to dump before this table */ + r.e = (uint8_t)(16 + j); /* bits in this table */ + r.v.t = q; /* pointer to this table */ + j = (i & ((1 << w) - 1)) >> (w - l[h-1]); + ZIP(u)[h-1][j] = r; /* connect to last table */ + } + } + + /* set up table entry in r */ + r.b = (uint8_t)(k - w); + if (p >= ZIP(v) + n) + r.e = 99; /* out of values--invalid code */ + else if (*p < s) + { + r.e = (uint8_t)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ + r.v.n = *p++; /* simple code is just the value */ + } + else + { + r.e = (uint8_t)e[*p - s]; /* non-simple--look up in lists */ + r.v.n = d[*p++ - s]; + } + + /* fill code-like entries with r */ + f = 1 << (k - w); + for (j = i >> w; j < z; j += f) + q[j] = r; + + /* backwards increment the k-bit code i */ + for (j = 1 << (k - 1); i & j; j >>= 1) + i ^= j; + i ^= j; + + /* backup over finished tables */ + while ((i & ((1 << w) - 1)) != ZIP(x)[h]) + w -= l[--h]; /* don't need to update q */ + } + } + + /* return actual size of base table */ + *m = l[0]; + + /* Return true (1) if we were given an incomplete table */ + return y != 0 && g != 1; +} + +static int32_t Zipinflate_codes(struct decomp_state *decomp_state, + struct Ziphuft *tl, struct Ziphuft *td, + int32_t bl, int32_t bd) +{ + register uint32_t e; /* table entry flag/number of extra bits */ + uint32_t n, d; /* length and index for copy */ + uint32_t w; /* current window position */ + struct Ziphuft *t; /* pointer to table entry */ + uint32_t ml, md; /* masks for bl and bd bits */ + register uint32_t b; /* bit buffer */ + register uint32_t k; /* number of bits in bit buffer */ + + DEBUG(10,("Zipinflate_codes\n")); + + /* make local copies of globals */ + b = ZIP(bb); /* initialize bit buffer */ + k = ZIP(bk); + w = ZIP(window_posn); /* initialize window position */ + + /* inflate the coded data */ + ml = Zipmask[bl]; /* precompute masks for speed */ + md = Zipmask[bd]; + + for(;;) + { + ZIPNEEDBITS((uint32_t)bl) + if((e = (t = tl + ((uint32_t)b & ml))->e) > 16) + do + { + if (e == 99) + return 1; + ZIPDUMPBITS(t->b) + e -= 16; + ZIPNEEDBITS(e) + } while ((e = (t = t->v.t + ((uint32_t)b & Zipmask[e]))->e) > 16); + ZIPDUMPBITS(t->b) + if (w >= CAB_BLOCKMAX) break; + if (e == 16) /* then it's a literal */ + CAB(outbuf)[w++] = (uint8_t)t->v.n; + else /* it's an EOB or a length */ + { + /* exit if end of block */ + if(e == 15) + break; + + /* get length of block to copy */ + ZIPNEEDBITS(e) + n = t->v.n + ((uint32_t)b & Zipmask[e]); + ZIPDUMPBITS(e); + + /* decode distance of block to copy */ + ZIPNEEDBITS((uint32_t)bd) + if ((e = (t = td + ((uint32_t)b & md))->e) > 16) + do { + if (e == 99) + return 1; + ZIPDUMPBITS(t->b) + e -= 16; + ZIPNEEDBITS(e) + } while ((e = (t = t->v.t + ((uint32_t)b & Zipmask[e]))->e) > 16); + ZIPDUMPBITS(t->b) + ZIPNEEDBITS(e) + d = w - t->v.n - ((uint32_t)b & Zipmask[e]); + ZIPDUMPBITS(e) + do + { + n -= (e = (e = ZIPWSIZE - ((d &= ZIPWSIZE-1) > w ? d : w)) > n ?n:e); + do + { + CAB(outbuf)[w++] = CAB(outbuf)[d++]; + } while (--e); + } while (n); + } + } + + /* restore the globals from the locals */ + ZIP(window_posn) = w; /* restore global window pointer */ + ZIP(bb) = b; /* restore global bit buffer */ + ZIP(bk) = k; + + /* done */ + return 0; +} + +/* "decompress" an inflated type 0 (stored) block. */ +static int32_t Zipinflate_stored(struct decomp_state *decomp_state) +{ + uint32_t n; /* number of bytes in block */ + uint32_t w; /* current window position */ + register uint32_t b; /* bit buffer */ + register uint32_t k; /* number of bits in bit buffer */ + + /* make local copies of globals */ + b = ZIP(bb); /* initialize bit buffer */ + k = ZIP(bk); + w = ZIP(window_posn); /* initialize window position */ + + /* go to byte boundary */ + n = k & 7; + ZIPDUMPBITS(n); + + /* get the length and its complement */ + ZIPNEEDBITS(16) + n = ((uint32_t)b & 0xffff); + ZIPDUMPBITS(16) + ZIPNEEDBITS(16) + if (n != (uint32_t)((~b) & 0xffff)) + return 1; /* error in compressed data */ + ZIPDUMPBITS(16) + + /* read and output the compressed data */ + while(n--) + { + ZIPNEEDBITS(8) + CAB(outbuf)[w++] = (uint8_t)b; + ZIPDUMPBITS(8) + } + + /* restore the globals from the locals */ + ZIP(window_posn) = w; /* restore global window pointer */ + ZIP(bb) = b; /* restore global bit buffer */ + ZIP(bk) = k; + return 0; +} + +static int32_t Zipinflate_fixed(struct decomp_state *decomp_state) +{ + struct Ziphuft *fixed_tl; + struct Ziphuft *fixed_td; + int32_t fixed_bl, fixed_bd; + int32_t i; /* temporary variable */ + uint32_t *l; + + l = ZIP(ll); + + /* literal table */ + for(i = 0; i < 144; i++) + l[i] = 8; + for(; i < 256; i++) + l[i] = 9; + for(; i < 280; i++) + l[i] = 7; + for(; i < 288; i++) /* make a complete, but wrong code set */ + l[i] = 8; + fixed_bl = 7; + if((i = Ziphuft_build(decomp_state, l, 288, 257, Zipcplens, Zipcplext, &fixed_tl, &fixed_bl))) + return i; + + /* distance table */ + for(i = 0; i < 30; i++) /* make an incomplete code set */ + l[i] = 5; + fixed_bd = 5; + if((i = Ziphuft_build(decomp_state, l, 30, 0, Zipcpdist, Zipcpdext, &fixed_td, &fixed_bd)) > 1) + { + Ziphuft_free(fixed_tl); + return i; + } + + /* decompress until an end-of-block code */ + i = Zipinflate_codes(decomp_state, fixed_tl, fixed_td, fixed_bl, fixed_bd); + + Ziphuft_free(fixed_td); + Ziphuft_free(fixed_tl); + return i; +} + +/* decompress an inflated type 2 (dynamic Huffman codes) block. */ +static int32_t Zipinflate_dynamic(struct decomp_state *decomp_state) +{ + int32_t i; /* temporary variables */ + uint32_t j; + uint32_t *ll; + uint32_t l; /* last length */ + uint32_t m; /* mask for bit lengths table */ + uint32_t n; /* number of lengths to get */ + struct Ziphuft *tl; /* literal/length code table */ + struct Ziphuft *td; /* distance code table */ + int32_t bl; /* lookup bits for tl */ + int32_t bd; /* lookup bits for td */ + uint32_t nb; /* number of bit length codes */ + uint32_t nl; /* number of literal/length codes */ + uint32_t nd; /* number of distance codes */ + register uint32_t b; /* bit buffer */ + register uint32_t k; /* number of bits in bit buffer */ + + /* make local bit buffer */ + b = ZIP(bb); + k = ZIP(bk); + ll = ZIP(ll); + + /* read in table lengths */ + ZIPNEEDBITS(5) + nl = 257 + ((uint32_t)b & 0x1f); /* number of literal/length codes */ + ZIPDUMPBITS(5) + ZIPNEEDBITS(5) + nd = 1 + ((uint32_t)b & 0x1f); /* number of distance codes */ + ZIPDUMPBITS(5) + ZIPNEEDBITS(4) + nb = 4 + ((uint32_t)b & 0xf); /* number of bit length codes */ + ZIPDUMPBITS(4) + if(nl > 288 || nd > 32) + return 1; /* bad lengths */ + + /* read in bit-length-code lengths */ + for(j = 0; j < nb; j++) + { + ZIPNEEDBITS(3) + ll[Zipborder[j]] = (uint32_t)b & 7; + ZIPDUMPBITS(3) + } + for(; j < 19; j++) + ll[Zipborder[j]] = 0; + + /* build decoding table for trees--single level, 7 bit lookup */ + bl = 7; + if((i = Ziphuft_build(decomp_state, ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) + { + if(i == 1) + Ziphuft_free(tl); + return i; /* incomplete code set */ + } + + /* read in literal and distance code lengths */ + n = nl + nd; + m = Zipmask[bl]; + i = l = 0; + while((uint32_t)i < n) + { + ZIPNEEDBITS((uint32_t)bl) + j = (td = tl + ((uint32_t)b & m))->b; + ZIPDUMPBITS(j) + j = td->v.n; + if (j < 16) /* length of code in bits (0..15) */ + ll[i++] = l = j; /* save last length in l */ + else if (j == 16) /* repeat last length 3 to 6 times */ + { + ZIPNEEDBITS(2) + j = 3 + ((uint32_t)b & 3); + ZIPDUMPBITS(2) + if((uint32_t)i + j > n) + return 1; + while (j--) + ll[i++] = l; + } + else if (j == 17) /* 3 to 10 zero length codes */ + { + ZIPNEEDBITS(3) + j = 3 + ((uint32_t)b & 7); + ZIPDUMPBITS(3) + if ((uint32_t)i + j > n) + return 1; + while (j--) + ll[i++] = 0; + l = 0; + } + else /* j == 18: 11 to 138 zero length codes */ + { + ZIPNEEDBITS(7) + j = 11 + ((uint32_t)b & 0x7f); + ZIPDUMPBITS(7) + if ((uint32_t)i + j > n) + return 1; + while (j--) + ll[i++] = 0; + l = 0; + } + } + + /* free decoding table for trees */ + Ziphuft_free(tl); + + /* restore the global bit buffer */ + ZIP(bb) = b; + ZIP(bk) = k; + + /* build the decoding tables for literal/length and distance codes */ + bl = ZIPLBITS; + if((i = Ziphuft_build(decomp_state, ll, nl, 257, Zipcplens, Zipcplext, &tl, &bl)) != 0) + { + if(i == 1) + Ziphuft_free(tl); + return i; /* incomplete code set */ + } + bd = ZIPDBITS; + Ziphuft_build(decomp_state, ll + nl, nd, 0, Zipcpdist, Zipcpdext, &td, &bd); + + /* decompress until an end-of-block code */ + if(Zipinflate_codes(decomp_state, tl, td, bl, bd)) + return 1; + + /* free the decoding tables, return */ + Ziphuft_free(tl); + Ziphuft_free(td); + return 0; +} + +/* e == last block flag */ +static int32_t Zipinflate_block(struct decomp_state *decomp_state, int32_t *e) +{ /* decompress an inflated block */ + uint32_t t; /* block type */ + register uint32_t b; /* bit buffer */ + register uint32_t k; /* number of bits in bit buffer */ + + DEBUG(10,("Zipinflate_block\n")); + + /* make local bit buffer */ + b = ZIP(bb); + k = ZIP(bk); + + /* read in last block bit */ + ZIPNEEDBITS(1) + *e = (int32_t)b & 1; + ZIPDUMPBITS(1) + + /* read in block type */ + ZIPNEEDBITS(2) + t = (uint32_t)b & 3; + ZIPDUMPBITS(2) + + /* restore the global bit buffer */ + ZIP(bb) = b; + ZIP(bk) = k; + + DEBUG(10,("inflate type %d\n", t)); + + /* inflate that block type */ + if(t == 2) + return Zipinflate_dynamic(decomp_state); + if(t == 0) + return Zipinflate_stored(decomp_state); + if(t == 1) + return Zipinflate_fixed(decomp_state); + /* bad block type */ + return 2; +} + +_PUBLIC_ struct decomp_state *ZIPdecomp_state(TALLOC_CTX *mem_ctx) +{ + return talloc_zero(mem_ctx, struct decomp_state); +} + +int ZIPdecompress(struct decomp_state *decomp_state, DATA_BLOB *inbuf, DATA_BLOB *outbuf) +{ + int32_t e = 0;/* last block flag */ + + ZIP(inpos) = CAB(inbuf); + ZIP(bb) = ZIP(bk) = ZIP(window_posn) = 0; + + if (inbuf->length > sizeof(decomp_state->inbuf)) return DECR_INPUT; + + if (outbuf->length > sizeof(decomp_state->outbuf)) return DECR_OUTPUT; + + if (outbuf->length > ZIPWSIZE) return DECR_DATAFORMAT; + + memcpy(decomp_state->inbuf, inbuf->data, inbuf->length); + + /* CK = Chris Kirmse, official Microsoft purloiner */ + if (ZIP(inpos)[0] != 'C' || ZIP(inpos)[1] != 'K') return DECR_ILLEGALDATA; + ZIP(inpos) += 2; + + while (!e) { + if (Zipinflate_block(decomp_state, &e)) { + return DECR_ILLEGALDATA; + } + } + + memcpy(outbuf->data, decomp_state->outbuf, outbuf->length); + + return DECR_OK; +} diff --git a/lib/compression/mszip.h b/lib/compression/mszip.h new file mode 100644 index 0000000000..bb835f2595 --- /dev/null +++ b/lib/compression/mszip.h @@ -0,0 +1,33 @@ +/* mszip decompression - based on cabextract.c code from + * Stuart Caie + * + * adapted for Samba by Andrew Tridgell and Stefan Metzmacher 2005 + * + * (C) 2000-2001 Stuart Caie <kyzer@4u.net> + * reaktivate-specifics by Malte Starostik <malte@kde.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, see <http://www.gnu.org/licenses/>. + */ + +struct decomp_state; +struct decomp_state *ZIPdecomp_state(TALLOC_CTX *mem_ctx); + +#define DECR_OK (0) +#define DECR_DATAFORMAT (1) +#define DECR_ILLEGALDATA (2) +#define DECR_NOMEMORY (3) +#define DECR_CHECKSUM (4) +#define DECR_INPUT (5) +#define DECR_OUTPUT (6) +int ZIPdecompress(struct decomp_state *decomp_state, DATA_BLOB *inbuf, DATA_BLOB *outbuf); diff --git a/lib/compression/testsuite.c b/lib/compression/testsuite.c new file mode 100644 index 0000000000..b9cebb2e8d --- /dev/null +++ b/lib/compression/testsuite.c @@ -0,0 +1,30 @@ +/* + Unix SMB/CIFS implementation. + test suite for the compression functions + + Copyright (C) Jelmer Vernooij 2007 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#include "includes.h" +#include "torture/torture.h" +#include "../compression/mszip.h" + +struct torture_suite *torture_local_compression(TALLOC_CTX *mem_ctx) +{ + struct torture_suite *suite = torture_suite_create(mem_ctx, "COMPRESSION"); + + return suite; +} |