From 2c8dc0b855c38c5204d398ad306fa9cf43be1ada Mon Sep 17 00:00:00 2001 From: Petr Mrázek Date: Thu, 26 Sep 2013 02:58:09 +0200 Subject: Compression algo dependencies, still need hackery... --- depends/lzma/CMakeLists.txt | 54 + depends/lzma/LICENSE.txt | 9 + depends/lzma/easylzma_test.c | 282 ++ depends/lzma/elzma.c | 557 ++++ depends/lzma/include/common.h | 118 + depends/lzma/include/compress.h | 77 + depends/lzma/include/decompress.h | 58 + depends/lzma/include/simple.h | 37 + depends/lzma/pavlov/7zCrc.c | 35 + depends/lzma/pavlov/7zCrc.h | 24 + depends/lzma/pavlov/LzFind.c | 779 +++++ depends/lzma/pavlov/LzFind.h | 107 + depends/lzma/pavlov/LzHash.h | 62 + depends/lzma/pavlov/LzmaDec.c | 1076 +++++++ depends/lzma/pavlov/LzmaDec.h | 220 ++ depends/lzma/pavlov/LzmaEnc.c | 2349 +++++++++++++++ depends/lzma/pavlov/LzmaEnc.h | 71 + depends/lzma/pavlov/LzmaLib.c | 41 + depends/lzma/pavlov/LzmaLib.h | 137 + depends/lzma/pavlov/Types.h | 87 + depends/lzma/wrapper/common_internal.c | 46 + depends/lzma/wrapper/common_internal.h | 60 + depends/lzma/wrapper/compress.c | 297 ++ depends/lzma/wrapper/decompress.c | 263 ++ depends/lzma/wrapper/lzip_header.c | 96 + depends/lzma/wrapper/lzip_header.h | 11 + depends/lzma/wrapper/lzma_header.c | 134 + depends/lzma/wrapper/lzma_header.h | 10 + depends/lzma/wrapper/simple.c | 139 + depends/pack200/CMakeLists.txt | 43 + depends/pack200/include/unpack200.h | 1 + depends/pack200/src/bands.cpp | 451 +++ depends/pack200/src/bands.h | 492 +++ depends/pack200/src/bytes.cpp | 217 ++ depends/pack200/src/bytes.h | 284 ++ depends/pack200/src/coding.cpp | 1049 +++++++ depends/pack200/src/coding.h | 270 ++ depends/pack200/src/constants.h | 442 +++ depends/pack200/src/defines.h | 136 + depends/pack200/src/main.cpp | 489 +++ depends/pack200/src/unpack.cpp | 5105 ++++++++++++++++++++++++++++++++ depends/pack200/src/unpack.h | 585 ++++ depends/pack200/src/utils.cpp | 91 + depends/pack200/src/utils.h | 54 + depends/pack200/src/zip.cpp | 610 ++++ depends/pack200/src/zip.h | 130 + 46 files changed, 17685 insertions(+) create mode 100644 depends/lzma/CMakeLists.txt create mode 100644 depends/lzma/LICENSE.txt create mode 100644 depends/lzma/easylzma_test.c create mode 100644 depends/lzma/elzma.c create mode 100644 depends/lzma/include/common.h create mode 100644 depends/lzma/include/compress.h create mode 100644 depends/lzma/include/decompress.h create mode 100644 depends/lzma/include/simple.h create mode 100755 depends/lzma/pavlov/7zCrc.c create mode 100755 depends/lzma/pavlov/7zCrc.h create mode 100755 depends/lzma/pavlov/LzFind.c create mode 100755 depends/lzma/pavlov/LzFind.h create mode 100755 depends/lzma/pavlov/LzHash.h create mode 100755 depends/lzma/pavlov/LzmaDec.c create mode 100755 depends/lzma/pavlov/LzmaDec.h create mode 100755 depends/lzma/pavlov/LzmaEnc.c create mode 100755 depends/lzma/pavlov/LzmaEnc.h create mode 100755 depends/lzma/pavlov/LzmaLib.c create mode 100755 depends/lzma/pavlov/LzmaLib.h create mode 100755 depends/lzma/pavlov/Types.h create mode 100644 depends/lzma/wrapper/common_internal.c create mode 100644 depends/lzma/wrapper/common_internal.h create mode 100644 depends/lzma/wrapper/compress.c create mode 100644 depends/lzma/wrapper/decompress.c create mode 100644 depends/lzma/wrapper/lzip_header.c create mode 100644 depends/lzma/wrapper/lzip_header.h create mode 100644 depends/lzma/wrapper/lzma_header.c create mode 100644 depends/lzma/wrapper/lzma_header.h create mode 100644 depends/lzma/wrapper/simple.c create mode 100644 depends/pack200/CMakeLists.txt create mode 100644 depends/pack200/include/unpack200.h create mode 100644 depends/pack200/src/bands.cpp create mode 100644 depends/pack200/src/bands.h create mode 100644 depends/pack200/src/bytes.cpp create mode 100644 depends/pack200/src/bytes.h create mode 100644 depends/pack200/src/coding.cpp create mode 100644 depends/pack200/src/coding.h create mode 100644 depends/pack200/src/constants.h create mode 100644 depends/pack200/src/defines.h create mode 100644 depends/pack200/src/main.cpp create mode 100644 depends/pack200/src/unpack.cpp create mode 100644 depends/pack200/src/unpack.h create mode 100644 depends/pack200/src/utils.cpp create mode 100644 depends/pack200/src/utils.h create mode 100644 depends/pack200/src/zip.cpp create mode 100644 depends/pack200/src/zip.h (limited to 'depends') diff --git a/depends/lzma/CMakeLists.txt b/depends/lzma/CMakeLists.txt new file mode 100644 index 00000000..4df2b762 --- /dev/null +++ b/depends/lzma/CMakeLists.txt @@ -0,0 +1,54 @@ +CMAKE_MINIMUM_REQUIRED(VERSION 2.6) + +PROJECT(lzma) + +IF (WIN32) + ADD_DEFINITIONS(-DWIN32) +ENDIF (WIN32) + +SET(SRCS +# original code by Igor Pavlov +# Lzma version 4.63 +# Minified ~_~ +pavlov/7zCrc.c +pavlov/7zCrc.h +pavlov/LzFind.c +pavlov/LzFind.h +pavlov/LzHash.h +pavlov/LzmaDec.c +pavlov/LzmaDec.h +pavlov/LzmaEnc.c +pavlov/LzmaEnc.h +pavlov/LzmaLib.c +pavlov/LzmaLib.h +pavlov/Types.h + +# Public headers +include/common.h +include/compress.h +include/decompress.h +include/simple.h + +# Wrapper by Lloyd Hilaiel (lloyd@hilaiel.com) +wrapper/common_internal.c +wrapper/common_internal.h +wrapper/compress.c +wrapper/decompress.c +wrapper/simple.c +wrapper/lzip_header.c +wrapper/lzip_header.h +wrapper/lzma_header.c +wrapper/lzma_header.h +) + +# an include directory to allow easylzma implementation to find public +# headers +INCLUDE_DIRECTORIES(include) +ADD_LIBRARY(lzma STATIC ${SRCS}) + +# lzma compress/decompress tool +ADD_EXECUTABLE(elzma elzma.c) +TARGET_LINK_LIBRARIES(elzma lzma) +# a simple test... +ADD_EXECUTABLE(easylzma_test easylzma_test.c) +TARGET_LINK_LIBRARIES(easylzma_test lzma) diff --git a/depends/lzma/LICENSE.txt b/depends/lzma/LICENSE.txt new file mode 100644 index 00000000..a8a34e6a --- /dev/null +++ b/depends/lzma/LICENSE.txt @@ -0,0 +1,9 @@ +# Written in 2009 by Lloyd Hilaiel +# Butchered in 2013 by Petr Mrazek +# +# License +# +# All the cruft you find here is public domain. You don't have to credit +# anyone to use this code, but my personal request is that you mention +# Igor Pavlov for his hard, high quality work. +# diff --git a/depends/lzma/easylzma_test.c b/depends/lzma/easylzma_test.c new file mode 100644 index 00000000..69858728 --- /dev/null +++ b/depends/lzma/easylzma_test.c @@ -0,0 +1,282 @@ +/* + * Written in 2009 by Lloyd Hilaiel + * + * License + * + * All the cruft you find here is public domain. You don't have to credit + * anyone to use this code, but my personal request is that you mention + * Igor Pavlov for his hard, high quality work. + * + * Various compiled-in tests for the easylzma library which excercise + * API correctness and handling of corrupt data. + */ + +#include "simple.h" + +#include +#include + +static const char *sampleData = + "Overview\n" + "\n" + "Easylzma is a C library and command line tools for LZMA compression and \n" + "decompression. It uses a Igor Pavlov's reference implementation and SDK\n" + "written in C.\n" + "\n" + "License\n" + "\n" + "All the cruft you find here is public domain. You don't have to credit\n" + "anyone to use this code, but my personal request is that you mention\n" + "Igor Pavlov for his hard, high quality work.\n" + "\n" + "Project Goals\n" + "\n" + "1. A tiny C wrapper and portable build system around a subset of\n" + " Igor Pavlov's public domain LZMA compression and decompression\n" + " implementation.\n" + "2. A tiny and straighforward API\n" + "3. Support for multiple different prominent LZMA file formats (see section on\n" + " file formats below)\n" + "4. easy to build and use everywhere (doze and nix alike)\n" + "5. public domain licensing through and through. (hats off to Igor)\n" + "\n" + "Current State:\n" + "\n" + "THIS IS A WORK IN PROGRESS. The code here should be considered pre-alpha,\n" + "and this should only be used by tinkerers or hackers at this point. Once\n" + "feature completion is attained this message will be updated. See the\n" + "TODO file distributed with the source for remaining work to be done.\n" + "\n" + "Platforms Supported\n" + "\n" + "0.0.2 has been successfully compiled and run basic round trip testing\n" + "on the following platforms & compilers:\n" + "\n" + " * win32 - visual studio 2005\n" + " * osx - 10.4 & 10.5 (intel)\n" + " * netbsd ppc - 4.0.1 with gcc 4.1.2\n" + " (NOTE: memory allocation errors when dict size is default)\n" + " * freebsd 6.1 - amd64 gcc 3.4.4\n" + "\n" + "Features\n" + "\n" + "XXX: write me (and the code)\n" + "\n" + "Usage\n" + "\n" + "XXX: write me (and the code)\n" + "\n" + "The Saga of LZMA File Formats, and a couple cents.\n" + "\n" + "As far as I can tell, there are at least four different ways to put LZMA\n" + "compressed data in a stream:\n" + "\n" + "1. The LZMA-Alone format, which consists of a 13 byte header including\n" + " compression properties, dictionary size, and the uncompressed size of\n" + " the file, followed by compressed data. This format has some support\n" + " in Igor Pavlov's reference implementation and is in widespread use, as\n" + " it's supported by lzmautils: http://tukaani.org/lzma/\n" + "\n" + " The canonical (afaict) implementation of this format (lzmautis) is\n" + " BSD licensed.\n" + "\n" + "2. The lzip format (http://www.nongnu.org/lzip/lzip.html) - which\n" + " includes a CRC footer and leading \"magic number\". The former\n" + " affords data integrity gaurantees, while the latter simplifies\n" + " heuristic determination of file format. This format looks to have\n" + " reasonably widespread usage, though not quite as significant as\n" + " LZMA-Alone.\n" + "\n" + " The only implementation of this format I can find (lzip) is GPL licensed.\n" + "\n" + "3. the xz format ( http://tukaani.org/xz/xz-file-format.txt ) which is\n" + " a more complex representation that includes CRC support and a magic\n" + " number. This format is to be supported by the next iteration of\n" + " XZ Utils which is currently in beta. The source may be obtained\n" + " here: git://ctrl.tukaani.org/xz.git\n" + "\n" + " This format will address some criticisms to the LZMA-Alone format and\n" + " was developed collaboratively by Lasse Collin (the current maintainer\n" + " of XZ utils) and Igor Pavlov (the author of 7zip and the refrence\n" + " implementation of LZMA).\n" + "\n" + " The xz format will employ LZMA2 which consists of extensions on top\n" + " of LZMA, in the xz utils maintainer's words:\n" + "\n" + " \"The primary compression algorithm in .xz is currently LZMA2, which\n" + " is an extension on top of the orignal LZMA to fix a few practical\n" + " issues, like adding support for flushing the encoder (equivalent\n" + " to zlib's Z_SYNC_FLUSH), which isn't possible with the original\n" + " LZMA.\"\n" + "\n" + " Again, maintainers words, regarding licensing:\n" + "\n" + " \"XZ Utils currently contains a zlib-like compression library and a \n" + " gzip-like command line tool. It's currently under LGPLv2.1+ but I will \n" + " put it into the public domain before the first stable release.\"\n" + "\n" + "4. The 7zip disk format which can contain multiple files possibly stored in\n" + " LZMA compressed format.\n" + "\n" + "Given the state of things, the goal of this project is to develop something\n" + "based on the existing formats, and quickly leverage code generated by the XZ\n" + "Utils project, or simply kill this thing if that project produces something\n" + "that's easy to embed and has a clean API at a similar level of abstraction\n" + "as easylzma.\n" + "\n" + "lloyd - sometime in oh nine.\n"; + +/* a test that we can round trip compress/decompress data using LZMA or LZIP + * formats */ +static int roundTripTest(elzma_file_format format) +{ + int rc; + unsigned char *compressed; + unsigned char *decompressed; + size_t sz; + + rc = simpleCompress(format, (unsigned char *)sampleData, strlen(sampleData), &compressed, + &sz); + + if (rc != ELZMA_E_OK) + return rc; + + /* gross assurance that compression is actually compressing */ + if (sz > strlen(sampleData)) + { + free(compressed); + return 1; + } + + rc = simpleDecompress(format, compressed, sz, &decompressed, &sz); + + free(compressed); + + if (rc != ELZMA_E_OK) + return rc; + + if (sz != strlen(sampleData) || 0 != memcmp(decompressed, sampleData, sz)) + { + free(decompressed); + return 1; + } + + return ELZMA_E_OK; +} + +/* "correct" lzip generated from the lzip program */ +/*|LZIP...3.?..????|*/ +/*|....?e2~........|*/ +static unsigned char correctLzip[] = { + 0x4c, 0x5a, 0x49, 0x50, 0x01, 0x0c, 0x00, 0x33, 0x1b, 0xec, 0x15, 0x07, 0xff, 0xff, + 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0xa8, 0x65, 0x32, 0x7e, 0x04, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; + +/* "correct" lzip generated from lzma utils */ +static unsigned char correctLzma[] = {0x5d, 0x00, 0x00, 0x80, 0x00, 0x04, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x33, 0x1b, 0xec, 0x14, 0x00, 0x00, 0x00}; + +/* lzip with a bad CRC */ +static unsigned char corruptCRC[] = { + 0x4c, 0x5a, 0x49, 0x50, 0x01, 0x0c, 0x00, 0x33, 0x1b, 0xec, 0x15, 0x07, 0xff, 0xff, + 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0xa8, 0x65, 0x31, 0x7e, 0x04, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; + +/* lzip with a bad uncompressed size */ +static unsigned char corruptSize[] = { + 0x4c, 0x5a, 0x49, 0x50, 0x01, 0x0c, 0x00, 0x33, 0x1b, 0xec, 0x15, 0x07, 0xff, 0xff, + 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0xa8, 0x65, 0x32, 0x7e, 0x04, 0x01, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; + +/* lzma with a bad uncompressed size */ +static unsigned char corruptSizeLzma[] = {0x5d, 0x00, 0x00, 0x80, 0x00, 0x04, 0x01, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x33, 0x1b, 0xec, 0x14, 0x00, 0x00, 0x00}; + +/* lzma with a bad uncompressed size */ +static unsigned char corruptSizeLzma2[] = {0x5d, 0x00, 0x00, 0x80, 0x00, 0x03, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x33, 0x1b, 0xec, 0x14, 0x00, 0x00, 0x00}; + +/* tests */ +static struct +{ + const char *testName; /* the name of the test */ + int expectedCode; /* the expected output of the test */ + elzma_file_format format; + unsigned char *data; /* input data */ + unsigned int dataSize; +} tests[] = { + {"correct lzip", ELZMA_E_OK, ELZMA_lzip, correctLzip, sizeof(correctLzip)}, + {"lzip as lzma", ELZMA_E_DECOMPRESS_ERROR, ELZMA_lzma, correctLzip, sizeof(correctLzip)}, + {"correct lzma", ELZMA_E_OK, ELZMA_lzma, correctLzma, sizeof(correctLzma)}, + {"lzma as lzip", ELZMA_E_CORRUPT_HEADER, ELZMA_lzip, correctLzma, sizeof(correctLzma)}, + {"corrupt crc", ELZMA_E_CRC32_MISMATCH, ELZMA_lzip, corruptCRC, sizeof(corruptCRC)}, + {"bad lzip size", ELZMA_E_SIZE_MISMATCH, ELZMA_lzip, corruptSize, sizeof(corruptSize)}, + {"bad lzma size", ELZMA_E_INSUFFICIENT_INPUT, ELZMA_lzma, + corruptSizeLzma, sizeof(corruptSizeLzma)}, + {"bad lzma size 2", ELZMA_E_SIZE_MISMATCH, ELZMA_lzma, + corruptSizeLzma2, sizeof(corruptSizeLzma2)}}; + +int main(void) +{ + unsigned int i; + unsigned int testsPassed = 0; + unsigned int testsRun = 0; + + int rc = 0; + + printf("round trip lzma test: "); + fflush(stdout); + testsRun++; + if (ELZMA_E_OK != (rc = roundTripTest(ELZMA_lzma))) + { + printf("fail! (%d)\n", rc); + } + else + { + testsPassed++; + printf("ok\n"); + } + + printf("round trip lzip test: "); + fflush(stdout); + testsRun++; + if (ELZMA_E_OK != (rc = roundTripTest(ELZMA_lzip))) + { + printf("fail (%d)!\n", rc); + } + else + { + testsPassed++; + printf("ok\n"); + } + + /* now run through the tests table */ + for (i = 0; i < sizeof(tests) / sizeof(tests[0]); i++) + { + unsigned char *decompressed = NULL; + size_t sz = 0; + + printf("%s test: ", tests[i].testName); + rc = simpleDecompress(tests[i].format, tests[i].data, tests[i].dataSize, &decompressed, + &sz); + + testsRun++; + if (rc != tests[i].expectedCode) + { + printf("fail - got %d - expected %d\n", rc, tests[i].expectedCode); + } + else + { + testsPassed++; + printf("ok\n"); + free(decompressed); + } + } + + printf("\n%d/%d tests passed\n", testsPassed, testsRun); + + return (testsPassed == testsRun) ? 0 : 1; +} diff --git a/depends/lzma/elzma.c b/depends/lzma/elzma.c new file mode 100644 index 00000000..f715a7b2 --- /dev/null +++ b/depends/lzma/elzma.c @@ -0,0 +1,557 @@ +/* + * Written in 2009 by Lloyd Hilaiel + * + * License + * + * All the cruft you find here is public domain. You don't have to credit + * anyone to use this code, but my personal request is that you mention + * Igor Pavlov for his hard, high quality work. + * + * command line elzma tool for lzma compression + * + * At time of writing, the primary purpose of this tool is to test the + * easylzma library. + * + * TODO: + * - stdin/stdout support + * - multiple file support + * - much more + */ + +#include "include/compress.h" +#include "include/decompress.h" + +#include +#include +#include + +#ifdef WIN32 +#include +#define unlink _unlink +#else +#include +#endif + +int deleteFile(const char *path) +{ + return unlink(path); +} + +/* a utility to open a pair of files */ +/* XXX: respect overwrite flag */ +static int openFiles(const char *ifname, FILE **inFile, const char *ofname, FILE **outFile, + int overwrite) +{ + *inFile = fopen(ifname, "rb"); + if (*inFile == NULL) + { + fprintf(stderr, "couldn't open '%s' for reading\n", ifname); + return 1; + } + + *outFile = fopen(ofname, "wb"); + if (*outFile == NULL) + { + fprintf(stderr, "couldn't open '%s' for writing\n", ofname); + return 1; + } + + return 0; +} + +#define ELZMA_COMPRESS_USAGE \ + "Compress files using the LZMA algorithm (in place by default).\n" \ + "\n" \ + "Usage: elzma [options] [file]\n" \ + " -1 .. -9 compression level, -1 is fast, -9 is best (default 5)\n" \ + " -f, --force overwrite output files if they exist\n" \ + " -h, --help output this message and exit\n" \ + " -k, --keep don't delete input files\n" \ + " --lzip compress to lzip disk format (.lz extension)\n" \ + " --lzma compress to LZMA-Alone disk format (.lzma extension)\n" \ + " -v, --verbose output verbose status information while compressing\n" \ + " -z, --compress compress files (default when invoking elzma program)\n" \ + " -d, --decompress decompress files (default when invoking unelzma program)\n" \ + "\n" \ + "Advanced Options:\n" \ + " -s --set-max-dict (advanced) specify maximum dictionary size in bytes\n" + +/* parse arguments populating output parameters, return nonzero on failure */ +static int parseCompressArgs(int argc, char **argv, unsigned char *level, char **fname, + unsigned int *maxDictSize, unsigned int *verbose, + unsigned int *keep, unsigned int *overwrite, + elzma_file_format *format) +{ + int i; + + if (argc < 2) + return 1; + + for (i = 1; i < argc; i++) + { + if (argv[i][0] == '-') + { + char *val = NULL; + char *arg = &(argv[i][1]); + if (arg[0] == '-') + arg++; + + /* now see what argument this is */ + if (!strcmp(arg, "h") || !strcmp(arg, "help")) + { + return 1; + } + else if (!strcmp(arg, "s") || !strcmp(arg, "set-max-dict")) + { + unsigned int j = 0; + val = argv[++i]; + + /* validate argument is numeric */ + for (j = 0; j < strlen(val); j++) + { + if (val[j] < '0' || val[j] > '9') + return 1; + } + + *maxDictSize = strtoul(val, (char **)NULL, 10); + + /* don't allow dictionary sizes less than 8k */ + if (*maxDictSize < (1 < 13)) + *maxDictSize = 1 < 13; + else + { + /* make sure dict size is compatible with lzip, + * this will effectively collapse it to a close power + * of 2 */ + *maxDictSize = elzma_get_dict_size(*maxDictSize); + } + } + else if (!strcmp(arg, "v") || !strcmp(arg, "verbose")) + { + *verbose = 1; + } + else if (!strcmp(arg, "f") || !strcmp(arg, "force")) + { + *overwrite = 1; + } + else if (!strcmp(arg, "k") || !strcmp(arg, "keep")) + { + *keep = 1; + } + else if (strlen(arg) == 1 && arg[0] >= '1' && arg[0] <= '9') + { + *level = arg[0] - '0'; + } + else if (!strcmp(arg, "lzma")) + { + *format = ELZMA_lzma; + } + else if (!strcmp(arg, "lzip")) + { + *format = ELZMA_lzip; + } + else if (!strcmp(arg, "z") || !strcmp(arg, "d") || !strcmp(arg, "compress") || + !strcmp(arg, "decompress")) + { + /* noop */ + } + else + { + return 1; + } + } + else + { + *fname = argv[i]; + break; + } + } + + /* proper number of arguments? */ + if (i != argc - 1 || *fname == NULL) + return 1; + + return 0; +} + +/* callbacks for streamed input and output */ +static size_t elzmaWriteFunc(void *ctx, const void *buf, size_t size) +{ + size_t wt; + FILE *f = (FILE *)ctx; + assert(f != NULL); + + wt = fwrite(buf, 1, size, f); + + return wt; +} + +static int elzmaReadFunc(void *ctx, void *buf, size_t *size) +{ + FILE *f = (FILE *)ctx; + assert(f != NULL); + *size = fread(buf, 1, *size, f); + + return 0; +} + +static void printProgressHeader(void) +{ + printf("|0%% 50%% 100%%|\n"); +} + +static void endProgress(int pCtx) +{ + while (pCtx++ < 64) + { + printf("."); + } + printf("|\n"); +} + +static void elzmaProgressFunc(void *ctx, size_t complete, size_t total) +{ + int *dots = (int *)ctx; + int wantDots = (int)(64 * (double)complete / (double)total); + if (*dots == 0) + { + printf("|"); + (*dots)++; + } + while (wantDots > *dots) + { + printf("."); + (*dots)++; + } + fflush(stdout); +} + +static int doCompress(int argc, char **argv) +{ + /* default compression parameters, some of which may be overridded by + * command line arguments */ + unsigned char level = 5; + unsigned char lc = ELZMA_LC_DEFAULT; + unsigned char lp = ELZMA_LP_DEFAULT; + unsigned char pb = ELZMA_PB_DEFAULT; + unsigned int maxDictSize = ELZMA_DICT_SIZE_DEFAULT_MAX; + unsigned int dictSize = 0; + elzma_file_format format = ELZMA_lzma; + char *ext = ".lzma"; + char *ifname = NULL; + char *ofname = NULL; + unsigned int verbose = 0; + FILE *inFile = NULL; + FILE *outFile = NULL; + elzma_compress_handle hand = NULL; + /* XXX: large file support */ + unsigned int uncompressedSize = 0; + unsigned int keep = 0; + unsigned int overwrite = 0; + + if (0 != parseCompressArgs(argc, argv, &level, &ifname, &maxDictSize, &verbose, &keep, + &overwrite, &format)) + { + fprintf(stderr, ELZMA_COMPRESS_USAGE); + return 1; + } + + /* extension switching based on compression type*/ + if (format == ELZMA_lzip) + ext = ".lz"; + + /* generate output file name */ + { + ofname = malloc(strlen(ifname) + strlen(ext) + 1); + ofname[0] = 0; + strcat(ofname, ifname); + strcat(ofname, ext); + } + + /* now attempt to open input and ouput files */ + /* XXX: stdin/stdout support */ + if (0 != openFiles(ifname, &inFile, ofname, &outFile, overwrite)) + { + return 1; + } + + /* set uncompressed size */ + if (0 != fseek(inFile, 0, SEEK_END) || 0 == (uncompressedSize = ftell(inFile)) || + 0 != fseek(inFile, 0, SEEK_SET)) + { + fprintf(stderr, "error seeking input file (%s) - zero length?\n", ifname); + deleteFile(ofname); + return 1; + } + + /* determine a reasonable dictionary size given input size */ + dictSize = elzma_get_dict_size(uncompressedSize); + if (dictSize > maxDictSize) + dictSize = maxDictSize; + + if (verbose) + { + printf("compressing '%s' to '%s'\n", ifname, ofname); + printf("lc/lp/pb = %u/%u/%u | dictionary size = %u bytes\n", lc, lp, pb, dictSize); + printf("input file is %u bytes\n", uncompressedSize); + } + + /* allocate a compression handle */ + hand = elzma_compress_alloc(); + if (hand == NULL) + { + fprintf(stderr, "couldn't allocate compression object\n"); + deleteFile(ofname); + return 1; + } + + if (ELZMA_E_OK != + elzma_compress_config(hand, lc, lp, pb, level, dictSize, format, uncompressedSize)) + { + fprintf(stderr, "couldn't configure compression with " + "provided parameters\n"); + deleteFile(ofname); + return 1; + } + + { + int rv; + int pCtx = 0; + + if (verbose) + printProgressHeader(); + + rv = elzma_compress_run(hand, elzmaReadFunc, (void *)inFile, elzmaWriteFunc, + (void *)outFile, (verbose ? elzmaProgressFunc : NULL), &pCtx); + + if (verbose) + endProgress(pCtx); + + if (ELZMA_E_OK != rv) + { + fprintf(stderr, "error compressing\n"); + deleteFile(ofname); + return 1; + } + } + + /* clean up */ + elzma_compress_free(&hand); + fclose(inFile); + fclose(outFile); + free(ofname); + + if (!keep) + deleteFile(ifname); + + return 0; +} + +#define ELZMA_DECOMPRESS_USAGE \ + "Decompress files compressed using the LZMA algorithm (in place by default).\n" \ + "\n" \ + "Usage: unelzma [options] [file]\n" \ + " -f, --force overwrite output files if they exist\n" \ + " -h, --help output this message and exit\n" \ + " -k, --keep don't delete input files\n" \ + " -v, --verbose output verbose status information while decompressing\n" \ + " -z, --compress compress files (default when invoking elzma program)\n" \ + " -d, --decompress decompress files (default when invoking unelzma program)\n" \ + "\n" +/* parse arguments populating output parameters, return nonzero on failure */ +static int parseDecompressArgs(int argc, char **argv, char **fname, unsigned int *verbose, + unsigned int *keep, unsigned int *overwrite) +{ + int i; + + if (argc < 2) + return 1; + + for (i = 1; i < argc; i++) + { + if (argv[i][0] == '-') + { + char *arg = &(argv[i][1]); + if (arg[0] == '-') + arg++; + + /* now see what argument this is */ + if (!strcmp(arg, "h") || !strcmp(arg, "help")) + { + return 1; + } + else if (!strcmp(arg, "v") || !strcmp(arg, "verbose")) + { + *verbose = 1; + } + else if (!strcmp(arg, "k") || !strcmp(arg, "keep")) + { + *keep = 1; + } + else if (!strcmp(arg, "f") || !strcmp(arg, "force")) + { + *overwrite = 1; + } + else if (!strcmp(arg, "z") || !strcmp(arg, "d") || !strcmp(arg, "compress") || + !strcmp(arg, "decompress")) + { + /* noop */ + } + else + { + return 1; + } + } + else + { + *fname = argv[i]; + break; + } + } + + /* proper number of arguments? */ + if (i != argc - 1 || *fname == NULL) + return 1; + + return 0; +} + +static int doDecompress(int argc, char **argv) +{ + char *ifname = NULL; + char *ofname = NULL; + unsigned int verbose = 0; + FILE *inFile = NULL; + FILE *outFile = NULL; + elzma_decompress_handle hand = NULL; + unsigned int overwrite = 0; + unsigned int keep = 0; + elzma_file_format format; + const char *lzmaExt = ".lzma"; + const char *lzipExt = ".lz"; + const char *ext = ".lz"; + + if (0 != parseDecompressArgs(argc, argv, &ifname, &verbose, &keep, &overwrite)) + { + fprintf(stderr, ELZMA_DECOMPRESS_USAGE); + return 1; + } + + /* generate output file name */ + if (strlen(ifname) > strlen(lzmaExt) && + 0 == strcmp(lzmaExt, ifname + strlen(ifname) - strlen(lzmaExt))) + { + format = ELZMA_lzma; + ext = lzmaExt; + } + else if (strlen(ifname) > strlen(lzipExt) && + 0 == strcmp(lzipExt, ifname + strlen(ifname) - strlen(lzipExt))) + { + format = ELZMA_lzip; + ext = lzipExt; + } + else + { + fprintf(stderr, "input file extension not recognized (expected either " + "%s or %s)", + lzmaExt, lzipExt); + return 1; + } + + ofname = malloc(strlen(ifname) - strlen(ext)); + ofname[0] = 0; + strncat(ofname, ifname, strlen(ifname) - strlen(ext)); + + /* now attempt to open input and ouput files */ + /* XXX: stdin/stdout support */ + if (0 != openFiles(ifname, &inFile, ofname, &outFile, overwrite)) + { + return 1; + } + + hand = elzma_decompress_alloc(); + if (hand == NULL) + { + fprintf(stderr, "couldn't allocate decompression object\n"); + deleteFile(ofname); + return 1; + } + + if (ELZMA_E_OK != elzma_decompress_run(hand, elzmaReadFunc, (void *)inFile, elzmaWriteFunc, + (void *)outFile, format)) + { + fprintf(stderr, "error decompressing\n"); + deleteFile(ofname); + return 1; + } + + elzma_decompress_free(&hand); + + if (!keep) + deleteFile(ifname); + + return 0; +} + +int main(int argc, char **argv) +{ + const char *unelzma = "unelzma"; + const char *unelzmaLose = "unelzma.exe"; + const char *elzma = "elzma"; + const char *elzmaLose = "elzma.exe"; + + enum + { + RM_NONE, + RM_COMPRESS, + RM_DECOMPRESS + } runmode = RM_NONE; + + /* first we'll determine the mode we're running in, indicated by + * the binary name (argv[0]) or by the presence of a flag: + * one of -z, -d, -compress, --decompress */ + if ((strlen(argv[0]) >= strlen(unelzma) && + !strcmp((argv[0] + strlen(argv[0]) - strlen(unelzma)), unelzma)) || + (strlen(argv[0]) >= strlen(unelzmaLose) && + !strcmp((argv[0] + strlen(argv[0]) - strlen(unelzmaLose)), unelzmaLose))) + { + runmode = RM_DECOMPRESS; + } + else if ((strlen(argv[0]) >= strlen(elzma) && + !strcmp((argv[0] + strlen(argv[0]) - strlen(elzma)), elzma)) || + (strlen(argv[0]) >= strlen(elzmaLose) && + !strcmp((argv[0] + strlen(argv[0]) - strlen(elzmaLose)), elzmaLose))) + { + runmode = RM_COMPRESS; + } + + /* allow runmode to be overridded by a command line flag, first flag + * wins */ + { + int i; + for (i = 1; i < argc; i++) + { + if (!strcmp(argv[i], "-d") || !strcmp(argv[i], "--decompress")) + { + runmode = RM_DECOMPRESS; + break; + } + else if (!strcmp(argv[i], "-z") || !strcmp(argv[i], "--compress")) + { + runmode = RM_COMPRESS; + break; + } + } + } + + if (runmode != RM_COMPRESS && runmode != RM_DECOMPRESS) + { + fprintf(stderr, "couldn't determine whether " + "you want to compress or decompress\n"); + return 1; + } + + if (runmode == RM_COMPRESS) + return doCompress(argc, argv); + return doDecompress(argc, argv); +} diff --git a/depends/lzma/include/common.h b/depends/lzma/include/common.h new file mode 100644 index 00000000..f02bdb4d --- /dev/null +++ b/depends/lzma/include/common.h @@ -0,0 +1,118 @@ +/* + * Written in 2009 by Lloyd Hilaiel + * + * License + * + * All the cruft you find here is public domain. You don't have to credit + * anyone to use this code, but my personal request is that you mention + * Igor Pavlov for his hard, high quality work. + * + * easylzma/common.h - definitions common to both compression and + * decompression + */ + +#pragma once + +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/* msft dll export gunk. To build a DLL on windows, you + * must define WIN32, EASYLZMA_SHARED, and EASYLZMA_BUILD. To use a + * DLL, you must define EASYLZMA_SHARED and WIN32 */ +#if defined(WIN32) && defined(EASYLZMA_SHARED) +#ifdef EASYLZMA_BUILD +#define EASYLZMA_API __declspec(dllexport) +#else +#define EASYLZMA_API __declspec(dllimport) +#endif +#else +#define EASYLZMA_API +#endif + +/** error codes */ + +/** no error */ +#define ELZMA_E_OK 0 +/** bad parameters passed to an ELZMA function */ +#define ELZMA_E_BAD_PARAMS 10 +/** could not initialize the encode with configured parameters. */ +#define ELZMA_E_ENCODING_PROPERTIES_ERROR 11 +/** an error occured during compression (XXX: be more specific) */ +#define ELZMA_E_COMPRESS_ERROR 12 +/** currently unsupported lzma file format was specified*/ +#define ELZMA_E_UNSUPPORTED_FORMAT 13 +/** an error occured when reading input */ +#define ELZMA_E_INPUT_ERROR 14 +/** an error occured when writing output */ +#define ELZMA_E_OUTPUT_ERROR 15 +/** LZMA header couldn't be parsed */ +#define ELZMA_E_CORRUPT_HEADER 16 +/** an error occured during decompression (XXX: be more specific) */ +#define ELZMA_E_DECOMPRESS_ERROR 17 +/** the input stream returns EOF before the decompression could complete */ +#define ELZMA_E_INSUFFICIENT_INPUT 18 +/** for formats which have an emebedded crc, this error would indicated that + * what came out was not what went in, i.e. data corruption */ +#define ELZMA_E_CRC32_MISMATCH 19 +/** for formats which have an emebedded uncompressed content length, + * this error indicates that the amount we read was not what we expected */ +#define ELZMA_E_SIZE_MISMATCH 20 + +/** Supported file formats */ +typedef enum +{ + ELZMA_lzip, /**< the lzip format which includes a magic number and + * CRC check */ + ELZMA_lzma /**< the LZMA-Alone format, originally designed by + * Igor Pavlov and in widespread use due to lzmautils, + * lacking both aforementioned features of lzip */ + /* XXX: future, potentially , + ELZMA_xz + */ +} elzma_file_format; + +/** + * A callback invoked during elzma_[de]compress_run when the [de]compression + * process has generated [de]compressed output. + * + * the size parameter indicates how much data is in buf to be written. + * it is required that the write callback consume all data, and a return + * value not equal to input size indicates and error. + */ +typedef size_t (*elzma_write_callback)(void *ctx, const void *buf, size_t size); + +/** + * A callback invoked during elzma_[de]compress_run when the [de]compression + * process requires more [un]compressed input. + * + * the size parameter is an in/out argument. on input it indicates + * the buffer size. on output it indicates the amount of data read into + * buf. when *size is zero on output it indicates EOF. + * + * \returns the read callback should return nonzero on failure. + */ +typedef int (*elzma_read_callback)(void *ctx, void *buf, size_t *size); + +/** + * A callback invoked during elzma_[de]compress_run to report progress + * on the [de]compression. + * + * \returns the read callback should return nonzero on failure. + */ +typedef void (*elzma_progress_callback)(void *ctx, size_t complete, size_t total); + +/** pointer to a malloc function, supporting client overriding memory + * allocation routines */ +typedef void *(*elzma_malloc)(void *ctx, unsigned int sz); + +/** pointer to a free function, supporting client overriding memory + * allocation routines */ +typedef void (*elzma_free)(void *ctx, void *ptr); + +#ifdef __cplusplus +} +; +#endif diff --git a/depends/lzma/include/compress.h b/depends/lzma/include/compress.h new file mode 100644 index 00000000..46c81d75 --- /dev/null +++ b/depends/lzma/include/compress.h @@ -0,0 +1,77 @@ +/* + * Written in 2009 by Lloyd Hilaiel + * + * License + * + * All the cruft you find here is public domain. You don't have to credit + * anyone to use this code, but my personal request is that you mention + * Igor Pavlov for his hard, high quality work. + * + * compress.h - the API for LZMA compression using easylzma + */ + +#pragma once + +#include "common.h" +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/** suggested default values */ +#define ELZMA_LC_DEFAULT 3 +#define ELZMA_LP_DEFAULT 0 +#define ELZMA_PB_DEFAULT 2 +#define ELZMA_DICT_SIZE_DEFAULT_MAX (1 << 24) + +/** an opaque handle to an lzma compressor */ +typedef struct _elzma_compress_handle *elzma_compress_handle; + +/** + * Allocate a handle to an LZMA compressor object. + */ +elzma_compress_handle EASYLZMA_API elzma_compress_alloc(); + +/** + * set allocation routines (optional, if not called malloc & free will + * be used) + */ +void EASYLZMA_API +elzma_compress_set_allocation_callbacks(elzma_compress_handle hand, elzma_malloc mallocFunc, + void *mallocFuncContext, elzma_free freeFunc, + void *freeFuncContext); + +/** + * Free all data associated with an LZMA compressor object. + */ +void EASYLZMA_API elzma_compress_free(elzma_compress_handle *hand); + +/** + * Set configuration paramters for a compression run. If not called, + * reasonable defaults will be used. + */ +int EASYLZMA_API elzma_compress_config(elzma_compress_handle hand, unsigned char lc, + unsigned char lp, unsigned char pb, unsigned char level, + unsigned int dictionarySize, elzma_file_format format, + unsigned long long uncompressedSize); + +/** + * Run compression + */ +int EASYLZMA_API +elzma_compress_run(elzma_compress_handle hand, elzma_read_callback inputStream, + void *inputContext, elzma_write_callback outputStream, void *outputContext, + elzma_progress_callback progressCallback, void *progressContext); + +/** + * a heuristic utility routine to guess a dictionary size that gets near + * optimal compression while reducing memory usage. + * accepts a size in bytes, returns a proposed dictionary size + */ +unsigned int EASYLZMA_API elzma_get_dict_size(unsigned long long size); + +#ifdef __cplusplus +} +; +#endif diff --git a/depends/lzma/include/decompress.h b/depends/lzma/include/decompress.h new file mode 100644 index 00000000..cb10b2ba --- /dev/null +++ b/depends/lzma/include/decompress.h @@ -0,0 +1,58 @@ +/* + * Written in 2009 by Lloyd Hilaiel + * + * License + * + * All the cruft you find here is public domain. You don't have to credit + * anyone to use this code, but my personal request is that you mention + * Igor Pavlov for his hard, high quality work. + * + * easylzma/decompress.h - The API for LZMA decompression using easylzma + */ + +#pragma once + +#include "include/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** an opaque handle to an lzma decompressor */ +typedef struct _elzma_decompress_handle *elzma_decompress_handle; + +/** + * Allocate a handle to an LZMA decompressor object. + */ +elzma_decompress_handle EASYLZMA_API elzma_decompress_alloc(); + +/** + * set allocation routines (optional, if not called malloc & free will + * be used) + */ +void EASYLZMA_API +elzma_decompress_set_allocation_callbacks(elzma_decompress_handle hand, elzma_malloc mallocFunc, + void *mallocFuncContext, elzma_free freeFunc, + void *freeFuncContext); + +/** + * Free all data associated with an LZMA decompressor object. + */ +void EASYLZMA_API elzma_decompress_free(elzma_decompress_handle *hand); + +/** + * Perform decompression + * + * XXX: should the library automatically detect format by reading stream? + * currently it's based on data external to stream (such as extension + * or convention) + */ +int EASYLZMA_API elzma_decompress_run(elzma_decompress_handle hand, + elzma_read_callback inputStream, void *inputContext, + elzma_write_callback outputStream, void *outputContext, + elzma_file_format format); + +#ifdef __cplusplus +} +; +#endif diff --git a/depends/lzma/include/simple.h b/depends/lzma/include/simple.h new file mode 100644 index 00000000..83f7b2d2 --- /dev/null +++ b/depends/lzma/include/simple.h @@ -0,0 +1,37 @@ +/* + * Written in 2009 by Lloyd Hilaiel + * + * License + * + * All the cruft you find here is public domain. You don't have to credit + * anyone to use this code, but my personal request is that you mention + * Igor Pavlov for his hard, high quality work. + * + * simple.h - a wrapper around easylzma to compress/decompress to memory + */ + +#pragma once + +#include "include/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +#include "include/compress.h" +#include "include/decompress.h" + +/* compress a chunk of memory and return a dynamically allocated buffer + * if successful. return value is an easylzma error code */ +int EASYLZMA_API simpleCompress(elzma_file_format format, const unsigned char *inData, + size_t inLen, unsigned char **outData, size_t *outLen); + +/* decompress a chunk of memory and return a dynamically allocated buffer + * if successful. return value is an easylzma error code */ +int EASYLZMA_API simpleDecompress(elzma_file_format format, const unsigned char *inData, + size_t inLen, unsigned char **outData, size_t *outLen); + +#ifdef __cplusplus +} +; +#endif \ No newline at end of file diff --git a/depends/lzma/pavlov/7zCrc.c b/depends/lzma/pavlov/7zCrc.c new file mode 100755 index 00000000..c1598ce2 --- /dev/null +++ b/depends/lzma/pavlov/7zCrc.c @@ -0,0 +1,35 @@ +/* 7zCrc.c -- CRC32 calculation +2008-08-05 +Igor Pavlov +Public domain */ + +#include "7zCrc.h" + +#define kCrcPoly 0xEDB88320 +uint32_t g_CrcTable[256]; + +void MY_FAST_CALL CrcGenerateTable(void) +{ + uint32_t i; + for (i = 0; i < 256; i++) + { + uint32_t r = i; + int j; + for (j = 0; j < 8; j++) + r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1)); + g_CrcTable[i] = r; + } +} + +uint32_t MY_FAST_CALL CrcUpdate(uint32_t v, const void *data, size_t size) +{ + const uint8_t *p = (const uint8_t *)data; + for (; size > 0; size--, p++) + v = CRC_UPDATE_BYTE(v, *p); + return v; +} + +uint32_t MY_FAST_CALL CrcCalc(const void *data, size_t size) +{ + return CrcUpdate(CRC_INIT_VAL, data, size) ^ 0xFFFFFFFF; +} diff --git a/depends/lzma/pavlov/7zCrc.h b/depends/lzma/pavlov/7zCrc.h new file mode 100755 index 00000000..0609cb87 --- /dev/null +++ b/depends/lzma/pavlov/7zCrc.h @@ -0,0 +1,24 @@ +/* 7zCrc.h -- CRC32 calculation +2008-03-13 +Igor Pavlov +Public domain */ + +#ifndef __7Z_CRC_H +#define __7Z_CRC_H + +#include + +#include "Types.h" + +extern uint32_t g_CrcTable[]; + +void MY_FAST_CALL CrcGenerateTable(void); + +#define CRC_INIT_VAL 0xFFFFFFFF +#define CRC_GET_DIGEST(crc) ((crc) ^ 0xFFFFFFFF) +#define CRC_UPDATE_BYTE(crc, b) (g_CrcTable[((crc) ^ (b)) & 0xFF] ^ ((crc) >> 8)) + +uint32_t MY_FAST_CALL CrcUpdate(uint32_t crc, const void *data, size_t size); +uint32_t MY_FAST_CALL CrcCalc(const void *data, size_t size); + +#endif diff --git a/depends/lzma/pavlov/LzFind.c b/depends/lzma/pavlov/LzFind.c new file mode 100755 index 00000000..75003ac1 --- /dev/null +++ b/depends/lzma/pavlov/LzFind.c @@ -0,0 +1,779 @@ +/* LzFind.c -- Match finder for LZ algorithms +2008-10-04 : Igor Pavlov : Public domain */ + +#include +#include + +#include "LzFind.h" +#include "LzHash.h" + +#define kEmptyHashValue 0 +#define kMaxValForNormalize ((uint32_t)0xFFFFFFFF) +#define kNormalizeStepMin (1 << 10) /* it must be power of 2 */ +#define kNormalizeMask (~(kNormalizeStepMin - 1)) +#define kMaxHistorySize ((uint32_t)3 << 30) + +#define kStartMaxLen 3 + +static void LzInWindow_Free(CMatchFinder *p) +{ + if (!p->directInput) + { + free(p->bufferBase); + p->bufferBase = 0; + } +} + +/* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */ + +static int LzInWindow_Create(CMatchFinder *p, uint32_t keepSizeReserv) +{ + uint32_t blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv; + if (p->directInput) + { + p->blockSize = blockSize; + return 1; + } + if (p->bufferBase == 0 || p->blockSize != blockSize) + { + LzInWindow_Free(p); + p->blockSize = blockSize; + p->bufferBase = (uint8_t *)malloc((size_t)blockSize); + } + return (p->bufferBase != 0); +} + +uint8_t *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) +{ + return p->buffer; +} +uint8_t MatchFinder_GetIndexByte(CMatchFinder *p, int32_t index) +{ + return p->buffer[index]; +} + +uint32_t MatchFinder_GetNumAvailableBytes(CMatchFinder *p) +{ + return p->streamPos - p->pos; +} + +void MatchFinder_ReduceOffsets(CMatchFinder *p, uint32_t subValue) +{ + p->posLimit -= subValue; + p->pos -= subValue; + p->streamPos -= subValue; +} + +static void MatchFinder_ReadBlock(CMatchFinder *p) +{ + if (p->streamEndWasReached || p->result != SZ_OK) + return; + for (;;) + { + uint8_t *dest = p->buffer + (p->streamPos - p->pos); + size_t size = (p->bufferBase + p->blockSize - dest); + if (size == 0) + return; + p->result = p->stream->Read(p->stream, dest, &size); + if (p->result != SZ_OK) + return; + if (size == 0) + { + p->streamEndWasReached = 1; + return; + } + p->streamPos += (uint32_t)size; + if (p->streamPos - p->pos > p->keepSizeAfter) + return; + } +} + +void MatchFinder_MoveBlock(CMatchFinder *p) +{ + memmove(p->bufferBase, p->buffer - p->keepSizeBefore, + (size_t)(p->streamPos - p->pos + p->keepSizeBefore)); + p->buffer = p->bufferBase + p->keepSizeBefore; +} + +int MatchFinder_NeedMove(CMatchFinder *p) +{ + /* if (p->streamEndWasReached) return 0; */ + return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter); +} + +void MatchFinder_ReadIfRequired(CMatchFinder *p) +{ + if (p->streamEndWasReached) + return; + if (p->keepSizeAfter >= p->streamPos - p->pos) + MatchFinder_ReadBlock(p); +} + +static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p) +{ + if (MatchFinder_NeedMove(p)) + MatchFinder_MoveBlock(p); + MatchFinder_ReadBlock(p); +} + +static void MatchFinder_SetDefaultSettings(CMatchFinder *p) +{ + p->cutValue = 32; + p->btMode = 1; + p->numHashBytes = 4; + /* p->skipModeBits = 0; */ + p->directInput = 0; + p->bigHash = 0; +} + +#define kCrcPoly 0xEDB88320 + +void MatchFinder_Construct(CMatchFinder *p) +{ + uint32_t i; + p->bufferBase = 0; + p->directInput = 0; + p->hash = 0; + MatchFinder_SetDefaultSettings(p); + + for (i = 0; i < 256; i++) + { + uint32_t r = i; + int j; + for (j = 0; j < 8; j++) + r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1)); + p->crc[i] = r; + } +} + +static void MatchFinder_FreeThisClassMemory(CMatchFinder *p) +{ + free(p->hash); + p->hash = 0; +} + +void MatchFinder_Free(CMatchFinder *p) +{ + MatchFinder_FreeThisClassMemory(p); + LzInWindow_Free(p); +} + +static CLzRef *AllocRefs(uint32_t num) +{ + size_t sizeInBytes = (size_t)num * sizeof(CLzRef); + if (sizeInBytes / sizeof(CLzRef) != num) + return 0; + return (CLzRef *)malloc(sizeInBytes); +} + +int MatchFinder_Create(CMatchFinder *p, uint32_t historySize, uint32_t keepAddBufferBefore, + uint32_t matchMaxLen, uint32_t keepAddBufferAfter) +{ + uint32_t sizeReserv; + if (historySize > kMaxHistorySize) + { + MatchFinder_Free(p); + return 0; + } + sizeReserv = historySize >> 1; + if (historySize > ((uint32_t)2 << 30)) + sizeReserv = historySize >> 2; + sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19); + + p->keepSizeBefore = historySize + keepAddBufferBefore + 1; + p->keepSizeAfter = matchMaxLen + keepAddBufferAfter; + /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary + * using */ + if (LzInWindow_Create(p, sizeReserv)) + { + uint32_t newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1; + uint32_t hs; + p->matchMaxLen = matchMaxLen; + { + p->fixedHashSize = 0; + if (p->numHashBytes == 2) + hs = (1 << 16) - 1; + else + { + hs = historySize - 1; + hs |= (hs >> 1); + hs |= (hs >> 2); + hs |= (hs >> 4); + hs |= (hs >> 8); + hs >>= 1; + /* hs >>= p->skipModeBits; */ + hs |= 0xFFFF; /* don't change it! It's required for Deflate */ + if (hs > (1 << 24)) + { + if (p->numHashBytes == 3) + hs = (1 << 24) - 1; + else + hs >>= 1; + } + } + p->hashMask = hs; + hs++; + if (p->numHashBytes > 2) + p->fixedHashSize += kHash2Size; + if (p->numHashBytes > 3) + p->fixedHashSize += kHash3Size; + if (p->numHashBytes > 4) + p->fixedHashSize += kHash4Size; + hs += p->fixedHashSize; + } + + { + uint32_t prevSize = p->hashSizeSum + p->numSons; + uint32_t newSize; + p->historySize = historySize; + p->hashSizeSum = hs; + p->cyclicBufferSize = newCyclicBufferSize; + p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize); + newSize = p->hashSizeSum + p->numSons; + if (p->hash != 0 && prevSize == newSize) + return 1; + MatchFinder_FreeThisClassMemory(p); + p->hash = AllocRefs(newSize); + if (p->hash != 0) + { + p->son = p->hash + p->hashSizeSum; + return 1; + } + } + } + MatchFinder_Free(p); + return 0; +} + +static void MatchFinder_SetLimits(CMatchFinder *p) +{ + uint32_t limit = kMaxValForNormalize - p->pos; + uint32_t limit2 = p->cyclicBufferSize - p->cyclicBufferPos; + if (limit2 < limit) + limit = limit2; + limit2 = p->streamPos - p->pos; + if (limit2 <= p->keepSizeAfter) + { + if (limit2 > 0) + limit2 = 1; + } + else + limit2 -= p->keepSizeAfter; + if (limit2 < limit) + limit = limit2; + { + uint32_t lenLimit = p->streamPos - p->pos; + if (lenLimit > p->matchMaxLen) + lenLimit = p->matchMaxLen; + p->lenLimit = lenLimit; + } + p->posLimit = p->pos + limit; +} + +void MatchFinder_Init(CMatchFinder *p) +{ + uint32_t i; + for (i = 0; i < p->hashSizeSum; i++) + p->hash[i] = kEmptyHashValue; + p->cyclicBufferPos = 0; + p->buffer = p->bufferBase; + p->pos = p->streamPos = p->cyclicBufferSize; + p->result = SZ_OK; + p->streamEndWasReached = 0; + MatchFinder_ReadBlock(p); + MatchFinder_SetLimits(p); +} + +static uint32_t MatchFinder_GetSubValue(CMatchFinder *p) +{ + return (p->pos - p->historySize - 1) & kNormalizeMask; +} + +void MatchFinder_Normalize3(uint32_t subValue, CLzRef *items, uint32_t numItems) +{ + uint32_t i; + for (i = 0; i < numItems; i++) + { + uint32_t value = items[i]; + if (value <= subValue) + value = kEmptyHashValue; + else + value -= subValue; + items[i] = value; + } +} + +static void MatchFinder_Normalize(CMatchFinder *p) +{ + uint32_t subValue = MatchFinder_GetSubValue(p); + MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons); + MatchFinder_ReduceOffsets(p, subValue); +} + +static void MatchFinder_CheckLimits(CMatchFinder *p) +{ + if (p->pos == kMaxValForNormalize) + MatchFinder_Normalize(p); + if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos) + MatchFinder_CheckAndMoveAndRead(p); + if (p->cyclicBufferPos == p->cyclicBufferSize) + p->cyclicBufferPos = 0; + MatchFinder_SetLimits(p); +} + +static uint32_t *Hc_GetMatchesSpec(uint32_t lenLimit, uint32_t curMatch, uint32_t pos, + const uint8_t *cur, CLzRef *son, uint32_t _cyclicBufferPos, + uint32_t _cyclicBufferSize, uint32_t cutValue, + uint32_t *distances, uint32_t maxLen) +{ + son[_cyclicBufferPos] = curMatch; + for (;;) + { + uint32_t delta = pos - curMatch; + if (cutValue-- == 0 || delta >= _cyclicBufferSize) + return distances; + { + const uint8_t *pb = cur - delta; + curMatch = son[_cyclicBufferPos - delta + + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)]; + if (pb[maxLen] == cur[maxLen] && *pb == *cur) + { + uint32_t len = 0; + while (++len != lenLimit) + if (pb[len] != cur[len]) + break; + if (maxLen < len) + { + *distances++ = maxLen = len; + *distances++ = delta - 1; + if (len == lenLimit) + return distances; + } + } + } + } +} + +uint32_t *GetMatchesSpec1(uint32_t lenLimit, uint32_t curMatch, uint32_t pos, + const uint8_t *cur, CLzRef *son, uint32_t _cyclicBufferPos, + uint32_t _cyclicBufferSize, uint32_t cutValue, uint32_t *distances, + uint32_t maxLen) +{ + CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1; + CLzRef *ptr1 = son + (_cyclicBufferPos << 1); + uint32_t len0 = 0, len1 = 0; + for (;;) + { + uint32_t delta = pos - curMatch; + if (cutValue-- == 0 || delta >= _cyclicBufferSize) + { + *ptr0 = *ptr1 = kEmptyHashValue; + return distances; + } + { + CLzRef *pair = son + ((_cyclicBufferPos - delta + + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) + << 1); + const uint8_t *pb = cur - delta; + uint32_t len = (len0 < len1 ? len0 : len1); + if (pb[len] == cur[len]) + { + if (++len != lenLimit && pb[len] == cur[len]) + while (++len != lenLimit) + if (pb[len] != cur[len]) + break; + if (maxLen < len) + { + *distances++ = maxLen = len; + *distances++ = delta - 1; + if (len == lenLimit) + { + *ptr1 = pair[0]; + *ptr0 = pair[1]; + return distances; + } + } + } + if (pb[len] < cur[len]) + { + *ptr1 = curMatch; + ptr1 = pair + 1; + curMatch = *ptr1; + len1 = len; + } + else + { + *ptr0 = curMatch; + ptr0 = pair; + curMatch = *ptr0; + len0 = len; + } + } + } +} + +static void SkipMatchesSpec(uint32_t lenLimit, uint32_t curMatch, uint32_t pos, + const uint8_t *cur, CLzRef *son, uint32_t _cyclicBufferPos, + uint32_t _cyclicBufferSize, uint32_t cutValue) +{ + CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1; + CLzRef *ptr1 = son + (_cyclicBufferPos << 1); + uint32_t len0 = 0, len1 = 0; + for (;;) + { + uint32_t delta = pos - curMatch; + if (cutValue-- == 0 || delta >= _cyclicBufferSize) + { + *ptr0 = *ptr1 = kEmptyHashValue; + return; + } + { + CLzRef *pair = son + ((_cyclicBufferPos - delta + + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) + << 1); + const uint8_t *pb = cur - delta; + uint32_t len = (len0 < len1 ? len0 : len1); + if (pb[len] == cur[len]) + { + while (++len != lenLimit) + if (pb[len] != cur[len]) + break; + { + if (len == lenLimit) + { + *ptr1 = pair[0]; + *ptr0 = pair[1]; + return; + } + } + } + if (pb[len] < cur[len]) + { + *ptr1 = curMatch; + ptr1 = pair + 1; + curMatch = *ptr1; + len1 = len; + } + else + { + *ptr0 = curMatch; + ptr0 = pair; + curMatch = *ptr0; + len0 = len; + } + } + } +} + +#define MOVE_POS \ + ++p->cyclicBufferPos; \ + p->buffer++; \ + if (++p->pos == p->posLimit) \ + MatchFinder_CheckLimits(p); + +#define MOVE_POS_RET MOVE_POS return offset; + +static void MatchFinder_MovePos(CMatchFinder *p) +{ + MOVE_POS; +} + +#define GET_MATCHES_HEADER2(minLen, ret_op) \ + uint32_t lenLimit; \ + uint32_t hashValue; \ + const uint8_t *cur; \ + uint32_t curMatch; \ + lenLimit = p->lenLimit; \ + { \ + if (lenLimit < minLen) \ + { \ + MatchFinder_MovePos(p); \ + ret_op; \ + } \ + } \ + cur = p->buffer; + +#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0) +#define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue) + +#define MF_PARAMS(p) \ + p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue + +#define GET_MATCHES_FOOTER(offset, maxLen) \ + offset = (uint32_t)( \ + GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), distances + offset, maxLen) - \ + distances); \ + MOVE_POS_RET; + +#define SKIP_FOOTER \ + SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); \ + MOVE_POS; + +static uint32_t Bt2_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances) +{ + uint32_t offset; + GET_MATCHES_HEADER(2) + HASH2_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + offset = 0; + GET_MATCHES_FOOTER(offset, 1) +} + +uint32_t Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances) +{ + uint32_t offset; + GET_MATCHES_HEADER(3) + HASH_ZIP_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + offset = 0; + GET_MATCHES_FOOTER(offset, 2) +} + +static uint32_t Bt3_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances) +{ + uint32_t hash2Value, delta2, maxLen, offset; + GET_MATCHES_HEADER(3) + + HASH3_CALC; + + delta2 = p->pos - p->hash[hash2Value]; + curMatch = p->hash[kFix3HashSize + hashValue]; + + p->hash[hash2Value] = p->hash[kFix3HashSize + hashValue] = p->pos; + + maxLen = 2; + offset = 0; + if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur) + { + for (; maxLen != lenLimit; maxLen++) + if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen]) + break; + distances[0] = maxLen; + distances[1] = delta2 - 1; + offset = 2; + if (maxLen == lenLimit) + { + SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); + MOVE_POS_RET; + } + } + GET_MATCHES_FOOTER(offset, maxLen) +} + +static uint32_t Bt4_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances) +{ + uint32_t hash2Value, hash3Value, delta2, delta3, maxLen, offset; + GET_MATCHES_HEADER(4) + + HASH4_CALC; + + delta2 = p->pos - p->hash[hash2Value]; + delta3 = p->pos - p->hash[kFix3HashSize + hash3Value]; + curMatch = p->hash[kFix4HashSize + hashValue]; + + p->hash[hash2Value] = p->hash[kFix3HashSize + hash3Value] = + p->hash[kFix4HashSize + hashValue] = p->pos; + + maxLen = 1; + offset = 0; + if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur) + { + distances[0] = maxLen = 2; + distances[1] = delta2 - 1; + offset = 2; + } + if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur) + { + maxLen = 3; + distances[offset + 1] = delta3 - 1; + offset += 2; + delta2 = delta3; + } + if (offset != 0) + { + for (; maxLen != lenLimit; maxLen++) + if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen]) + break; + distances[offset - 2] = maxLen; + if (maxLen == lenLimit) + { + SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); + MOVE_POS_RET; + } + } + if (maxLen < 3) + maxLen = 3; + GET_MATCHES_FOOTER(offset, maxLen) +} + +static uint32_t Hc4_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances) +{ + uint32_t hash2Value, hash3Value, delta2, delta3, maxLen, offset; + GET_MATCHES_HEADER(4) + + HASH4_CALC; + + delta2 = p->pos - p->hash[hash2Value]; + delta3 = p->pos - p->hash[kFix3HashSize + hash3Value]; + curMatch = p->hash[kFix4HashSize + hashValue]; + + p->hash[hash2Value] = p->hash[kFix3HashSize + hash3Value] = + p->hash[kFix4HashSize + hashValue] = p->pos; + + maxLen = 1; + offset = 0; + if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur) + { + distances[0] = maxLen = 2; + distances[1] = delta2 - 1; + offset = 2; + } + if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur) + { + maxLen = 3; + distances[offset + 1] = delta3 - 1; + offset += 2; + delta2 = delta3; + } + if (offset != 0) + { + for (; maxLen != lenLimit; maxLen++) + if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen]) + break; + distances[offset - 2] = maxLen; + if (maxLen == lenLimit) + { + p->son[p->cyclicBufferPos] = curMatch; + MOVE_POS_RET; + } + } + if (maxLen < 3) + maxLen = 3; + offset = (uint32_t)( + Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p), distances + offset, maxLen) - + (distances)); + MOVE_POS_RET +} + +uint32_t Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances) +{ + uint32_t offset; + GET_MATCHES_HEADER(3) + HASH_ZIP_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + offset = (uint32_t)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p), distances, 2) - + (distances)); + MOVE_POS_RET +} + +static void Bt2_MatchFinder_Skip(CMatchFinder *p, uint32_t num) +{ + do + { + SKIP_HEADER(2) + HASH2_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + SKIP_FOOTER + } while (--num != 0); +} + +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, uint32_t num) +{ + do + { + SKIP_HEADER(3) + HASH_ZIP_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + SKIP_FOOTER + } while (--num != 0); +} + +static void Bt3_MatchFinder_Skip(CMatchFinder *p, uint32_t num) +{ + do + { + uint32_t hash2Value; + SKIP_HEADER(3) + HASH3_CALC; + curMatch = p->hash[kFix3HashSize + hashValue]; + p->hash[hash2Value] = p->hash[kFix3HashSize + hashValue] = p->pos; + SKIP_FOOTER + } while (--num != 0); +} + +static void Bt4_MatchFinder_Skip(CMatchFinder *p, uint32_t num) +{ + do + { + uint32_t hash2Value, hash3Value; + SKIP_HEADER(4) + HASH4_CALC; + curMatch = p->hash[kFix4HashSize + hashValue]; + p->hash[hash2Value] = p->hash[kFix3HashSize + hash3Value] = p->pos; + p->hash[kFix4HashSize + hashValue] = p->pos; + SKIP_FOOTER + } while (--num != 0); +} + +static void Hc4_MatchFinder_Skip(CMatchFinder *p, uint32_t num) +{ + do + { + uint32_t hash2Value, hash3Value; + SKIP_HEADER(4) + HASH4_CALC; + curMatch = p->hash[kFix4HashSize + hashValue]; + p->hash[hash2Value] = p->hash[kFix3HashSize + hash3Value] = + p->hash[kFix4HashSize + hashValue] = p->pos; + p->son[p->cyclicBufferPos] = curMatch; + MOVE_POS + } while (--num != 0); +} + +void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, uint32_t num) +{ + do + { + SKIP_HEADER(3) + HASH_ZIP_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + p->son[p->cyclicBufferPos] = curMatch; + MOVE_POS + } while (--num != 0); +} + +void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable) +{ + vTable->Init = (Mf_Init_Func)MatchFinder_Init; + vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte; + vTable->GetNumAvailableBytes = + (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes; + vTable->GetPointerToCurrentPos = + (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos; + if (!p->btMode) + { + vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches; + vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip; + } + else if (p->numHashBytes == 2) + { + vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches; + vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip; + } + else if (p->numHashBytes == 3) + { + vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches; + vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip; + } + else + { + vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches; + vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip; + } +} diff --git a/depends/lzma/pavlov/LzFind.h b/depends/lzma/pavlov/LzFind.h new file mode 100755 index 00000000..12d89aac --- /dev/null +++ b/depends/lzma/pavlov/LzFind.h @@ -0,0 +1,107 @@ +/* LzFind.h -- Match finder for LZ algorithms +2008-10-04 : Igor Pavlov : Public domain */ + +#ifndef __LZFIND_H +#define __LZFIND_H + +#include "Types.h" + +typedef uint32_t CLzRef; + +typedef struct _CMatchFinder +{ + uint8_t *buffer; + uint32_t pos; + uint32_t posLimit; + uint32_t streamPos; + uint32_t lenLimit; + + uint32_t cyclicBufferPos; + uint32_t cyclicBufferSize; /* it must be = (historySize + 1) */ + + uint32_t matchMaxLen; + CLzRef *hash; + CLzRef *son; + uint32_t hashMask; + uint32_t cutValue; + + uint8_t *bufferBase; + ISeqInStream *stream; + int streamEndWasReached; + + uint32_t blockSize; + uint32_t keepSizeBefore; + uint32_t keepSizeAfter; + + uint32_t numHashBytes; + int directInput; + int btMode; + /* int skipModeBi