From 2c8dc0b855c38c5204d398ad306fa9cf43be1ada Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Petr=20Mr=C3=A1zek?= 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 ++ 29 files changed, 7236 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 (limited to 'depends/lzma') 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 skipModeBits; */ + int bigHash; + uint32_t historySize; + uint32_t fixedHashSize; + uint32_t hashSizeSum; + uint32_t numSons; + SRes result; + uint32_t crc[256]; +} CMatchFinder; + +#define Inline_MatchFinder_GetPointerToCurrentPos(p) ((p)->buffer) +#define Inline_MatchFinder_GetIndexByte(p, index) ((p)->buffer[(Int32)(index)]) + +#define Inline_MatchFinder_GetNumAvailableBytes(p) ((p)->streamPos - (p)->pos) + +int MatchFinder_NeedMove(CMatchFinder *p); +uint8_t *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p); +void MatchFinder_MoveBlock(CMatchFinder *p); +void MatchFinder_ReadIfRequired(CMatchFinder *p); + +void MatchFinder_Construct(CMatchFinder *p); + +/* Conditions: + historySize <= 3 GB + keepAddBufferBefore + matchMaxLen + keepAddBufferAfter < 511MB +*/ +int MatchFinder_Create(CMatchFinder *p, uint32_t historySize, uint32_t keepAddBufferBefore, + uint32_t matchMaxLen, uint32_t keepAddBufferAfter); +void MatchFinder_Free(CMatchFinder *p); +void MatchFinder_Normalize3(uint32_t subValue, CLzRef *items, uint32_t numItems); +void MatchFinder_ReduceOffsets(CMatchFinder *p, uint32_t subValue); + +uint32_t *GetMatchesSpec1(uint32_t lenLimit, uint32_t curMatch, uint32_t pos, + const uint8_t *buffer, CLzRef *son, uint32_t _cyclicBufferPos, + uint32_t _cyclicBufferSize, uint32_t _cutValue, uint32_t *distances, + uint32_t maxLen); + +/* +Conditions: + Mf_GetNumAvailableBytes_Func must be called before each Mf_GetMatchLen_Func. + Mf_GetPointerToCurrentPos_Func's result must be used only before any other function +*/ + +typedef void (*Mf_Init_Func)(void *object); +typedef uint8_t (*Mf_GetIndexByte_Func)(void *object, int32_t index); +typedef uint32_t (*Mf_GetNumAvailableBytes_Func)(void *object); +typedef const uint8_t *(*Mf_GetPointerToCurrentPos_Func)(void *object); +typedef uint32_t (*Mf_GetMatches_Func)(void *object, uint32_t *distances); +typedef void (*Mf_Skip_Func)(void *object, uint32_t); + +typedef struct _IMatchFinder +{ + Mf_Init_Func Init; + Mf_GetIndexByte_Func GetIndexByte; + Mf_GetNumAvailableBytes_Func GetNumAvailableBytes; + Mf_GetPointerToCurrentPos_Func GetPointerToCurrentPos; + Mf_GetMatches_Func GetMatches; + Mf_Skip_Func Skip; +} IMatchFinder; + +void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable); + +void MatchFinder_Init(CMatchFinder *p); +uint32_t Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances); +uint32_t Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, uint32_t *distances); +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, uint32_t num); +void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, uint32_t num); + +#endif diff --git a/depends/lzma/pavlov/LzHash.h b/depends/lzma/pavlov/LzHash.h new file mode 100755 index 00000000..22cb0430 --- /dev/null +++ b/depends/lzma/pavlov/LzHash.h @@ -0,0 +1,62 @@ +/* LzHash.h -- HASH functions for LZ algorithms +2008-10-04 : Igor Pavlov : Public domain */ + +#pragma once + +#define kHash2Size (1 << 10) +#define kHash3Size (1 << 16) +#define kHash4Size (1 << 20) + +#define kFix3HashSize (kHash2Size) +#define kFix4HashSize (kHash2Size + kHash3Size) +#define kFix5HashSize (kHash2Size + kHash3Size + kHash4Size) + +#define HASH2_CALC hashValue = cur[0] | ((uint32_t)cur[1] << 8); + +#define HASH3_CALC \ + { \ + uint32_t temp = p->crc[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hashValue = (temp ^ ((uint32_t)cur[2] << 8)) & p->hashMask; \ + } + +#define HASH4_CALC \ + { \ + uint32_t temp = p->crc[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((uint32_t)cur[2] << 8)) & (kHash3Size - 1); \ + hashValue = (temp ^ ((uint32_t)cur[2] << 8) ^ (p->crc[cur[3]] << 5)) & p->hashMask; \ + } + +#define HASH5_CALC \ + { \ + uint32_t temp = p->crc[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((uint32_t)cur[2] << 8)) & (kHash3Size - 1); \ + hash4Value = (temp ^ ((uint32_t)cur[2] << 8) ^ (p->crc[cur[3]] << 5)); \ + hashValue = (hash4Value ^ (p->crc[cur[4]] << 3)) & p->hashMask; \ + hash4Value &= (kHash4Size - 1); \ + } + +/* #define HASH_ZIP_CALC hashValue = ((cur[0] | ((uint32_t)cur[1] << 8)) ^ p->crc[cur[2]]) & + * 0xFFFF; */ +#define HASH_ZIP_CALC \ + hashValue = ((cur[2] | ((uint32_t)cur[0] << 8)) ^ p->crc[cur[1]]) & 0xFFFF; + +#define MT_HASH2_CALC hash2Value = (p->crc[cur[0]] ^ cur[1]) & (kHash2Size - 1); + +#define MT_HASH3_CALC \ + { \ + uint32_t temp = p->crc[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((uint32_t)cur[2] << 8)) & (kHash3Size - 1); \ + } + +#define MT_HASH4_CALC \ + { \ + uint32_t temp = p->crc[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((uint32_t)cur[2] << 8)) & (kHash3Size - 1); \ + hash4Value = \ + (temp ^ ((uint32_t)cur[2] << 8) ^ (p->crc[cur[3]] << 5)) & (kHash4Size - 1); \ + } diff --git a/depends/lzma/pavlov/LzmaDec.c b/depends/lzma/pavlov/LzmaDec.c new file mode 100755 index 00000000..1a44dd00 --- /dev/null +++ b/depends/lzma/pavlov/LzmaDec.c @@ -0,0 +1,1076 @@ +/* LzmaDec.c -- LZMA Decoder +2008-11-06 : Igor Pavlov : Public domain */ + +#include "LzmaDec.h" + +#include +#include + +#define kNumTopBits 24 +#define kTopValue ((uint32_t)1 << kNumTopBits) + +#define kNumBitModelTotalBits 11 +#define kBitModelTotal (1 << kNumBitModelTotalBits) +#define kNumMoveBits 5 + +#define RC_INIT_SIZE 5 + +#define NORMALIZE \ + if (range < kTopValue) \ + { \ + range <<= 8; \ + code = (code << 8) | (*buf++); \ + } + +#define IF_BIT_0(p) \ + ttt = *(p); \ + NORMALIZE; \ + bound = (range >> kNumBitModelTotalBits) * ttt; \ + if (code < bound) +#define UPDATE_0(p) \ + range = bound; \ + *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits)); +#define UPDATE_1(p) \ + range -= bound; \ + code -= bound; \ + *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits)); +#define GET_BIT2(p, i, A0, A1) \ + IF_BIT_0(p) \ + { \ + UPDATE_0(p); \ + i = (i + i); \ + A0; \ + } \ + else \ + { \ + UPDATE_1(p); \ + i = (i + i) + 1; \ + A1; \ + } +#define GET_BIT(p, i) GET_BIT2(p, i, ;, ;) + +#define TREE_GET_BIT(probs, i) \ + { \ + GET_BIT((probs + i), i); \ + } +#define TREE_DECODE(probs, limit, i) \ + { \ + i = 1; \ + do \ + { \ + TREE_GET_BIT(probs, i); \ + } while (i < limit); \ + i -= limit; \ + } + +/* #define _LZMA_SIZE_OPT */ + +#ifdef _LZMA_SIZE_OPT +#define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i) +#else +#define TREE_6_DECODE(probs, i) \ + { \ + i = 1; \ + TREE_GET_BIT(probs, i); \ + TREE_GET_BIT(probs, i); \ + TREE_GET_BIT(probs, i); \ + TREE_GET_BIT(probs, i); \ + TREE_GET_BIT(probs, i); \ + TREE_GET_BIT(probs, i); \ + i -= 0x40; \ + } +#endif + +#define NORMALIZE_CHECK \ + if (range < kTopValue) \ + { \ + if (buf >= bufLimit) \ + return DUMMY_ERROR; \ + range <<= 8; \ + code = (code << 8) | (*buf++); \ + } + +#define IF_BIT_0_CHECK(p) \ + ttt = *(p); \ + NORMALIZE_CHECK; \ + bound = (range >> kNumBitModelTotalBits) * ttt; \ + if (code < bound) +#define UPDATE_0_CHECK range = bound; +#define UPDATE_1_CHECK \ + range -= bound; \ + code -= bound; +#define GET_BIT2_CHECK(p, i, A0, A1) \ + IF_BIT_0_CHECK(p) \ + { \ + UPDATE_0_CHECK; \ + i = (i + i); \ + A0; \ + } \ + else \ + { \ + UPDATE_1_CHECK; \ + i = (i + i) + 1; \ + A1; \ + } +#define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ;, ;) +#define TREE_DECODE_CHECK(probs, limit, i) \ + { \ + i = 1; \ + do \ + { \ + GET_BIT_CHECK(probs + i, i) \ + } while (i < limit); \ + i -= limit; \ + } + +#define kNumPosBitsMax 4 +#define kNumPosStatesMax (1 << kNumPosBitsMax) + +#define kLenNumLowBits 3 +#define kLenNumLowSymbols (1 << kLenNumLowBits) +#define kLenNumMidBits 3 +#define kLenNumMidSymbols (1 << kLenNumMidBits) +#define kLenNumHighBits 8 +#define kLenNumHighSymbols (1 << kLenNumHighBits) + +#define LenChoice 0 +#define LenChoice2 (LenChoice + 1) +#define LenLow (LenChoice2 + 1) +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) +#define kNumLenProbs (LenHigh + kLenNumHighSymbols) + +#define kNumStates 12 +#define kNumLitStates 7 + +#define kStartPosModelIndex 4 +#define kEndPosModelIndex 14 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) + +#define kNumPosSlotBits 6 +#define kNumLenToPosStates 4 + +#define kNumAlignBits 4 +#define kAlignTableSize (1 << kNumAlignBits) + +#define kMatchMinLen 2 +#define kMatchSpecLenStart \ + (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols) + +#define IsMatch 0 +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) +#define IsRepG0 (IsRep + kNumStates) +#define IsRepG1 (IsRepG0 + kNumStates) +#define IsRepG2 (IsRepG1 + kNumStates) +#define IsRep0Long (IsRepG2 + kNumStates) +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) +#define LenCoder (Align + kAlignTableSize) +#define RepLenCoder (LenCoder + kNumLenProbs) +#define Literal (RepLenCoder + kNumLenProbs) + +#define LZMA_BASE_SIZE 1846 +#define LZMA_LIT_SIZE 768 + +#define LzmaProps_GetNumProbs(p) \ + ((uint32_t)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp))) + +#if Literal != LZMA_BASE_SIZE +StopCompilingDueBUG +#endif + static const uint8_t kLiteralNextStates[kNumStates * 2] = { + 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5, 7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10}; + +#define LZMA_DIC_MIN (1 << 12) + +/* First LZMA-symbol is always decoded. +And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization +Out: + Result: + SZ_OK - OK + SZ_ERROR_DATA - Error + p->remainLen: + < kMatchSpecLenStart : normal remain + = kMatchSpecLenStart : finished + = kMatchSpecLenStart + 1 : Flush marker + = kMatchSpecLenStart + 2 : State Init Marker +*/ + +static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, size_t limit, const uint8_t *bufLimit) +{ + CLzmaProb *probs = p->probs; + + unsigned state = p->state; + uint32_t rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3]; + unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1; + unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1; + unsigned lc = p->prop.lc; + + uint8_t *dic = p->dic; + size_t dicBufSize = p->dicBufSize; + size_t dicPos = p->dicPos; + + uint32_t processedPos = p->processedPos; + uint32_t checkDicSize = p->checkDicSize; + unsigned len = 0; + + const uint8_t *buf = p->buf; + uint32_t range = p->range; + uint32_t code = p->code; + + do + { + CLzmaProb *prob; + uint32_t bound; + unsigned ttt; + unsigned posState = processedPos & pbMask; + + prob = probs + IsMatch + (state << kNumPosBitsMax) + posState; + IF_BIT_0(prob) + { + unsigned symbol; + UPDATE_0(prob); + prob = probs + Literal; + if (checkDicSize != 0 || processedPos != 0) + prob += (LZMA_LIT_SIZE * + (((processedPos & lpMask) << lc) + + (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc)))); + + if (state < kNumLitStates) + { + symbol = 1; + do + { + GET_BIT(prob + symbol, symbol) + } while (symbol < 0x100); + } + else + { + unsigned matchByte = + p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; + unsigned offs = 0x100; + symbol = 1; + do + { + unsigned bit; + CLzmaProb *probLit; + matchByte <<= 1; + bit = (matchByte & offs); + probLit = prob + offs + bit + symbol; + GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit) + } while (symbol < 0x100); + } + dic[dicPos++] = (uint8_t)symbol; + processedPos++; + + state = kLiteralNextStates[state]; + /* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */ + continue; + } + else + { + UPDATE_1(prob); + prob = probs + IsRep + state; + IF_BIT_0(prob) + { + UPDATE_0(prob); + state += kNumStates; + prob = probs + LenCoder; + } + else + { + UPDATE_1(prob); + if (checkDicSize == 0 && processedPos == 0) + return SZ_ERROR_DATA; + prob = probs + IsRepG0 + state; + IF_BIT_0(prob) + { + UPDATE_0(prob); + prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState; + IF_BIT_0(prob) + { + UPDATE_0(prob); + dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; + dicPos++; + processedPos++; + state = state < kNumLitStates ? 9 : 11; + continue; + } + UPDATE_1(prob); + } + else + { + uint32_t distance; + UPDATE_1(prob); + prob = probs + IsRepG1 + state; + IF_BIT_0(prob) + { + UPDATE_0(prob); + distance = rep1; + } + else + { + UPDATE_1(prob); + prob = probs + IsRepG2 + state; + IF_BIT_0(prob) + { + UPDATE_0(prob); + distance = rep2; + } + else + { + UPDATE_1(prob); + distance = rep3; + rep3 = rep2; + } + rep2 = rep1; + } + rep1 = rep0; + rep0 = distance; + } + state = state < kNumLitStates ? 8 : 11; + prob = probs + RepLenCoder; + } + { + unsigned limit, offset; + CLzmaProb *probLen = prob + LenChoice; + IF_BIT_0(probLen) + { + UPDATE_0(probLen); + probLen = prob + LenLow + (posState << kLenNumLowBits); + offset = 0; + limit = (1 << kLenNumLowBits); + } + else + { + UPDATE_1(probLen); + probLen = prob + LenChoice2; + IF_BIT_0(probLen) + { + UPDATE_0(probLen); + probLen = prob + LenMid + (posState << kLenNumMidBits); + offset = kLenNumLowSymbols; + limit = (1 << kLenNumMidBits); + } + else + { + UPDATE_1(probLen); + probLen = prob + LenHigh; + offset = kLenNumLowSymbols + kLenNumMidSymbols; + limit = (1 << kLenNumHighBits); + } + } + TREE_DECODE(probLen, limit, len); + len += offset; + } + + if (state >= kNumStates) + { + uint32_t distance; + prob = + probs + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) + << kNumPosSlotBits); + TREE_6_DECODE(prob, distance); + if (distance >= kStartPosModelIndex) + { + unsigned posSlot = (unsigned)distance; + int numDirectBits = (int)(((distance >> 1) - 1)); + distance = (2 | (distance & 1)); + if (posSlot < kEndPosModelIndex) + { + distance <<= numDirectBits; + prob = probs + SpecPos + distance - posSlot - 1; + { + uint32_t mask = 1; + unsigned i = 1; + do + { + GET_BIT2(prob + i, i, ;, distance |= mask); + mask <<= 1; + } while (--numDirectBits != 0); + } + } + else + { + numDirectBits -= kNumAlignBits; + do + { + NORMALIZE + range >>= 1; + + { + uint32_t t; + code -= range; + t = (0 - + ((uint32_t)code >> 31)); /* (UInt32)((Int32)code >> 31) */ + distance = (distance << 1) + (t + 1); + code += range & t; + } + /* + distance <<= 1; + if (code >= range) + { + code -= range; + distance |= 1; + } + */ + } while (--numDirectBits != 0); + prob = probs + Align; + distance <<= kNumAlignBits; + { + unsigned i = 1; + GET_BIT2(prob + i, i, ;, distance |= 1); + GET_BIT2(prob + i, i, ;, distance |= 2); + GET_BIT2(prob + i, i, ;, distance |= 4); + GET_BIT2(prob + i, i, ;, distance |= 8); + } + if (distance == (uint32_t)0xFFFFFFFF) + { + len += kMatchSpecLenStart; + state -= kNumStates; + break; + } + } + } + rep3 = rep2; + rep2 = rep1; + rep1 = rep0; + rep0 = distance + 1; + if (checkDicSize == 0) + { + if (distance >= processedPos) + return SZ_ERROR_DATA; + } + else if (distance >= checkDicSize) + return SZ_ERROR_DATA; + state = + (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3; + /* state = kLiteralNextStates[state]; */ + } + + len += kMatchMinLen; + + if (limit == dicPos) + return SZ_ERROR_DATA; + { + size_t rem = limit - dicPos; + unsigned curLen = ((rem < len) ? (unsigned)rem : len); + size_t pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0); + + processedPos += curLen; + + len -= curLen; + if (pos + curLen <= dicBufSize) + { + uint8_t *dest = dic + dicPos; + ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos; + const uint8_t *lim = dest + curLen; + dicPos += curLen; + do + *(dest) = (uint8_t) * (dest + src); + while (++dest != lim); + } + else + { + do + { + dic[dicPos++] = dic[pos]; + if (++pos == dicBufSize) + pos = 0; + } while (--curLen != 0); + } + } + } + } while (dicPos < limit && buf < bufLimit); + NORMALIZE; + p->buf = buf; + p->range = range; + p->code = code; + p->remainLen = len; + p->dicPos = dicPos; + p->processedPos = processedPos; + p->reps[0] = rep0; + p->reps[1] = rep1; + p->reps[2] = rep2; + p->reps[3] = rep3; + p->state = state; + + return SZ_OK; +} + +static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, size_t limit) +{ + if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart) + { + uint8_t *dic = p->dic; + size_t dicPos = p->dicPos; + size_t dicBufSize = p->dicBufSize; + unsigned len = p->remainLen; + uint32_t rep0 = p->reps[0]; + if (limit - dicPos < len) + len = (unsigned)(limit - dicPos); + + if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len) + p->checkDicSize = p->prop.dicSize; + + p->processedPos += len; + p->remainLen -= len; + while (len-- != 0) + { + dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; + dicPos++; + } + p->dicPos = dicPos; + } +} + +static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, size_t limit, const uint8_t *bufLimit) +{ + do + { + size_t limit2 = limit; + if (p->checkDicSize == 0) + { + uint32_t rem = p->prop.dicSize - p->processedPos; + if (limit - p->dicPos > rem) + limit2 = p->dicPos + rem; + } + RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit)); + if (p->processedPos >= p->prop.dicSize) + p->checkDicSize = p->prop.dicSize; + LzmaDec_WriteRem(p, limit); + } while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart); + + if (p->remainLen > kMatchSpecLenStart) + { + p->remainLen = kMatchSpecLenStart; + } + return 0; +} + +typedef enum +{ + DUMMY_ERROR, /* unexpected end of input stream */ + DUMMY_LIT, + DUMMY_MATCH, + DUMMY_REP +} ELzmaDummy; + +static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const uint8_t *buf, size_t inSize) +{ + uint32_t range = p->range; + uint32_t code = p->code; + const uint8_t *bufLimit = buf + inSize; + CLzmaProb *probs = p->probs; + unsigned state = p->state; + ELzmaDummy res; + + { + CLzmaProb *prob; + uint32_t bound; + unsigned ttt; + unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1); + + prob = probs + IsMatch + (state << kNumPosBitsMax) + posState; + IF_BIT_0_CHECK(prob) + { + UPDATE_0_CHECK + + /* if (bufLimit - buf >= 7) return DUMMY_LIT; */ + + prob = probs + Literal; + if (p->checkDicSize != 0 || p->processedPos != 0) + prob += (LZMA_LIT_SIZE * + ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) + + (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> + (8 - p->prop.lc)))); + + if (state < kNumLitStates) + { + unsigned symbol = 1; + do + { + GET_BIT_CHECK(prob + symbol, symbol) + } while (symbol < 0x100); + } + else + { + unsigned matchByte = p->dic[p->dicPos - p->reps[0] + + ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)]; + unsigned offs = 0x100; + unsigned symbol = 1; + do + { + unsigned bit; + CLzmaProb *probLit; + matchByte <<= 1; + bit = (matchByte & offs); + probLit = prob + offs + bit + symbol; + GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit) + } while (symbol < 0x100); + } + res = DUMMY_LIT; + } + else + { + unsigned len; + UPDATE_1_CHECK; + + prob = probs + IsRep + state; + IF_BIT_0_CHECK(prob) + { + UPDATE_0_CHECK; + state = 0; + prob = probs + LenCoder; + res = DUMMY_MATCH; + } + else + { + UPDATE_1_CHECK; + res = DUMMY_REP; + prob = probs + IsRepG0 + state; + IF_BIT_0_CHECK(prob) + { + UPDATE_0_CHECK; + prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState; + IF_BIT_0_CHECK(prob) + { + UPDATE_0_CHECK; + NORMALIZE_CHECK; + return DUMMY_REP; + } + else + { + UPDATE_1_CHECK; + } + } + else + { + UPDATE_1_CHECK; + prob = probs + IsRepG1 + state; + IF_BIT_0_CHECK(prob) + { + UPDATE_0_CHECK; + } + else + { + UPDATE_1_CHECK; + prob = probs + IsRepG2 + state; + IF_BIT_0_CHECK(prob) + { + UPDATE_0_CHECK; + } + else + { + UPDATE_1_CHECK; + } + } + } + state = kNumStates; + prob = probs + RepLenCoder; + } + { + unsigned limit, offset; + CLzmaProb *probLen = prob + LenChoice; + IF_BIT_0_CHECK(probLen) + { + UPDATE_0_CHECK; + probLen = prob + LenLow + (posState << kLenNumLowBits); + offset = 0; + limit = 1 << kLenNumLowBits; + } + else + { + UPDATE_1_CHECK; + probLen = prob + LenChoice2; + IF_BIT_0_CHECK(probLen) + { + UPDATE_0_CHECK; + probLen = prob + LenMid + (posState << kLenNumMidBits); + offset = kLenNumLowSymbols; + limit = 1 << kLenNumMidBits; + } + else + { + UPDATE_1_CHECK; + probLen = prob + LenHigh; + offset = kLenNumLowSymbols + kLenNumMidSymbols; + limit = 1 << kLenNumHighBits; + } + } + TREE_DECODE_CHECK(probLen, limit, len); + len += offset; + } + + if (state < 4) + { + unsigned posSlot; + prob = + probs + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) + << kNumPosSlotBits); + TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot); + if (posSlot >= kStartPosModelIndex) + { + int numDirectBits = ((posSlot >> 1) - 1); + + /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */ + + if (posSlot < kEndPosModelIndex) + { + prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - + posSlot - 1; + } + else + { + numDirectBits -= kNumAlignBits; + do + { + NORMALIZE_CHECK + range >>= 1; + code -= range & (((code - range) >> 31) - 1); + /* if (code >= range) code -= range; */ + } while (--numDirectBits != 0); + prob = probs + Align; + numDirectBits = kNumAlignBits; + } + { + unsigned i = 1; + do + { + GET_BIT_CHECK(prob + i, i); + } while (--numDirectBits != 0); + } + } + } + } + } + NORMALIZE_CHECK; + return res; +} + +static void LzmaDec_InitRc(CLzmaDec *p, const uint8_t *data) +{ + p->code = ((uint32_t)data[1] << 24) | ((uint32_t)data[2] << 16) | ((uint32_t)data[3] << 8) | + ((uint32_t)data[4]); + p->range = 0xFFFFFFFF; + p->needFlush = 0; +} + +void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState) +{ + p->needFlush = 1; + p->remainLen = 0; + p->tempBufSize = 0; + + if (initDic) + { + p->processedPos = 0; + p->checkDicSize = 0; + p->needInitState = 1; + } + if (initState) + p->needInitState = 1; +} + +void LzmaDec_Init(CLzmaDec *p) +{ + p->dicPos = 0; + LzmaDec_InitDicAndState(p, True, True); +} + +static void LzmaDec_InitStateReal(CLzmaDec *p) +{ + uint32_t numProbs = Literal + ((uint32_t)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp)); + uint32_t i; + CLzmaProb *probs = p->probs; + for (i = 0; i < numProbs; i++) + probs[i] = kBitModelTotal >> 1; + p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1; + p->state = 0; + p->needInitState = 0; +} + +SRes LzmaDec_DecodeToDic(CLzmaDec *p, size_t dicLimit, const uint8_t *src, size_t *srcLen, + ELzmaFinishMode finishMode, ELzmaStatus *status) +{ + size_t inSize = *srcLen; + (*srcLen) = 0; + LzmaDec_WriteRem(p, dicLimit); + + *status = LZMA_STATUS_NOT_SPECIFIED; + + while (p->remainLen != kMatchSpecLenStart) + { + int checkEndMarkNow; + + if (p->needFlush != 0) + { + for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--) + p->tempBuf[p->tempBufSize++] = *src++; + if (p->tempBufSize < RC_INIT_SIZE) + { + *status = LZMA_STATUS_NEEDS_MORE_INPUT; + return SZ_OK; + } + if (p->tempBuf[0] != 0) + return SZ_ERROR_DATA; + + LzmaDec_InitRc(p, p->tempBuf); + p->tempBufSize = 0; + } + + checkEndMarkNow = 0; + if (p->dicPos >= dicLimit) + { + if (p->remainLen == 0 && p->code == 0) + { + *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK; + return SZ_OK; + } + if (finishMode == LZMA_FINISH_ANY) + { + *status = LZMA_STATUS_NOT_FINISHED; + return SZ_OK; + } + if (p->remainLen != 0) + { + *status = LZMA_STATUS_NOT_FINISHED; + return SZ_ERROR_DATA; + } + checkEndMarkNow = 1; + } + + if (p->needInitState) + LzmaDec_InitStateReal(p); + + if (p->tempBufSize == 0) + { + size_t processed; + const uint8_t *bufLimit; + if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) + { + int dummyRes = LzmaDec_TryDummy(p, src, inSize); + if (dummyRes == DUMMY_ERROR) + { + memcpy(p->tempBuf, src, inSize); + p->tempBufSize = (unsigned)inSize; + (*srcLen) += inSize; + *status = LZMA_STATUS_NEEDS_MORE_INPUT; + return SZ_OK; + } + if (checkEndMarkNow && dummyRes != DUMMY_MATCH) + { + *status = LZMA_STATUS_NOT_FINISHED; + return SZ_ERROR_DATA; + } + bufLimit = src; + } + else + bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX; + p->buf = src; + if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0) + return SZ_ERROR_DATA; + processed = (size_t)(p->buf - src); + (*srcLen) += processed; + src += processed; + inSize -= processed; + } + else + { + unsigned rem = p->tempBufSize, lookAhead = 0; + while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize) + p->tempBuf[rem++] = src[lookAhead++]; + p->tempBufSize = rem; + if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) + { + int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem); + if (dummyRes == DUMMY_ERROR) + { + (*srcLen) += lookAhead; + *status = LZMA_STATUS_NEEDS_MORE_INPUT; + return SZ_OK; + } + if (checkEndMarkNow && dummyRes != DUMMY_MATCH) + { + *status = LZMA_STATUS_NOT_FINISHED; + return SZ_ERROR_DATA; + } + } + p->buf = p->tempBuf; + if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0) + return SZ_ERROR_DATA; + lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf)); + (*srcLen) += lookAhead; + src += lookAhead; + inSize -= lookAhead; + p->tempBufSize = 0; + } + } + if (p->code == 0) + *status = LZMA_STATUS_FINISHED_WITH_MARK; + return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA; +} + +SRes LzmaDec_DecodeToBuf(CLzmaDec *p, uint8_t *dest, size_t *destLen, const uint8_t *src, + size_t *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status) +{ + size_t outSize = *destLen; + size_t inSize = *srcLen; + *srcLen = *destLen = 0; + for (;;) + { + size_t inSizeCur = inSize, outSizeCur, dicPos; + ELzmaFinishMode curFinishMode; + SRes res; + if (p->dicPos == p->dicBufSize) + p->dicPos = 0; + dicPos = p->dicPos; + if (outSize > p->dicBufSize - dicPos) + { + outSizeCur = p->dicBufSize; + curFinishMode = LZMA_FINISH_ANY; + } + else + { + outSizeCur = dicPos + outSize; + curFinishMode = finishMode; + } + + res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status); + src += inSizeCur; + inSize -= inSizeCur; + *srcLen += inSizeCur; + outSizeCur = p->dicPos - dicPos; + memcpy(dest, p->dic + dicPos, outSizeCur); + dest += outSizeCur; + outSize -= outSizeCur; + *destLen += outSizeCur; + if (res != 0) + return res; + if (outSizeCur == 0 || outSize == 0) + return SZ_OK; + } +} + +void LzmaDec_FreeProbs(CLzmaDec *p) +{ + free(p->probs); + p->probs = 0; +} + +static void LzmaDec_FreeDict(CLzmaDec *p) +{ + free(p->dic); + p->dic = 0; +} + +void LzmaDec_Free(CLzmaDec *p) +{ + LzmaDec_FreeProbs(p); + LzmaDec_FreeDict(p); +} + +SRes LzmaProps_Decode(CLzmaProps *p, const uint8_t *data, unsigned size) +{ + uint32_t dicSize; + uint8_t d; + + if (size < LZMA_PROPS_SIZE) + return SZ_ERROR_UNSUPPORTED; + else + dicSize = data[1] | ((uint32_t)data[2] << 8) | ((uint32_t)data[3] << 16) | + ((uint32_t)data[4] << 24); + + if (dicSize < LZMA_DIC_MIN) + dicSize = LZMA_DIC_MIN; + p->dicSize = dicSize; + + d = data[0]; + if (d >= (9 * 5 * 5)) + return SZ_ERROR_UNSUPPORTED; + + p->lc = d % 9; + d /= 9; + p->pb = d / 5; + p->lp = d % 5; + + return SZ_OK; +} + +static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew) +{ + uint32_t numProbs = LzmaProps_GetNumProbs(propNew); + if (p->probs == 0 || numProbs != p->numProbs) + { + LzmaDec_FreeProbs(p); + p->probs = (CLzmaProb *)malloc(numProbs * sizeof(CLzmaProb)); + p->numProbs = numProbs; + if (p->probs == 0) + return SZ_ERROR_MEM; + } + return SZ_OK; +} + +SRes LzmaDec_AllocateProbs(CLzmaDec *p, const uint8_t *props, unsigned propsSize) +{ + CLzmaProps propNew; + RINOK(LzmaProps_Decode(&propNew, props, propsSize)); + RINOK(LzmaDec_AllocateProbs2(p, &propNew)); + p->prop = propNew; + return SZ_OK; +} + +SRes LzmaDec_Allocate(CLzmaDec *p, const uint8_t *props, unsigned propsSize) +{ + CLzmaProps propNew; + size_t dicBufSize; + RINOK(LzmaProps_Decode(&propNew, props, propsSize)); + RINOK(LzmaDec_AllocateProbs2(p, &propNew)); + dicBufSize = propNew.dicSize; + if (p->dic == 0 || dicBufSize != p->dicBufSize) + { + LzmaDec_FreeDict(p); + p->dic = (uint8_t *)malloc(dicBufSize); + if (p->dic == 0) + { + LzmaDec_FreeProbs(p); + return SZ_ERROR_MEM; + } + } + p->dicBufSize = dicBufSize; + p->prop = propNew; + return SZ_OK; +} + +SRes LzmaDecode(uint8_t *dest, size_t *destLen, const uint8_t *src, size_t *srcLen, + const uint8_t *propData, unsigned propSize, ELzmaFinishMode finishMode, + ELzmaStatus *status) +{ + CLzmaDec p; + SRes res; + size_t inSize = *srcLen; + size_t outSize = *destLen; + *srcLen = *destLen = 0; + if (inSize < RC_INIT_SIZE) + return SZ_ERROR_INPUT_EOF; + + LzmaDec_Construct(&p); + res = LzmaDec_AllocateProbs(&p, propData, propSize); + if (res != 0) + return res; + p.dic = dest; + p.dicBufSize = outSize; + + LzmaDec_Init(&p); + + *srcLen = inSize; + res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status); + + if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT) + res = SZ_ERROR_INPUT_EOF; + + (*destLen) = p.dicPos; + LzmaDec_FreeProbs(&p); + return res; +} diff --git a/depends/lzma/pavlov/LzmaDec.h b/depends/lzma/pavlov/LzmaDec.h new file mode 100755 index 00000000..25cb7e94 --- /dev/null +++ b/depends/lzma/pavlov/LzmaDec.h @@ -0,0 +1,220 @@ +/* LzmaDec.h -- LZMA Decoder +2008-10-04 : Igor Pavlov : Public domain */ + +#pragma once + +#include "Types.h" + +/* #define _LZMA_PROB32 */ +/* _LZMA_PROB32 can increase the speed on some CPUs, + but memory usage for CLzmaDec::probs will be doubled in that case */ + +#ifdef _LZMA_PROB32 +#define CLzmaProb UInt32 +#else +#define CLzmaProb uint16_t +#endif + +/* ---------- LZMA Properties ---------- */ + +#define LZMA_PROPS_SIZE 5 + +typedef struct _CLzmaProps +{ + unsigned lc, lp, pb; + uint32_t dicSize; +} CLzmaProps; + +/* LzmaProps_Decode - decodes properties +Returns: + SZ_OK + SZ_ERROR_UNSUPPORTED - Unsupported properties +*/ + +SRes LzmaProps_Decode(CLzmaProps *p, const uint8_t *data, unsigned size); + +/* ---------- LZMA Decoder state ---------- */ + +/* LZMA_REQUIRED_INPUT_MAX = number of required input bytes for worst case. + Num bits = log2((2^11 / 31) ^ 22) + 26 < 134 + 26 = 160; */ + +#define LZMA_REQUIRED_INPUT_MAX 20 + +typedef struct +{ + CLzmaProps prop; + CLzmaProb *probs; + uint8_t *dic; + const uint8_t *buf; + uint32_t range, code; + size_t dicPos; + size_t dicBufSize; + uint32_t processedPos; + uint32_t checkDicSize; + unsigned state; + uint32_t reps[4]; + unsigned remainLen; + int needFlush; + int needInitState; + uint32_t numProbs; + unsigned tempBufSize; + uint8_t tempBuf[LZMA_REQUIRED_INPUT_MAX]; +} CLzmaDec; + +#define LzmaDec_Construct(p) \ + { \ + (p)->dic = 0; \ + (p)->probs = 0; \ + } + +void LzmaDec_Init(CLzmaDec *p); + +/* There are two types of LZMA streams: + 0) Stream with end mark. That end mark adds about 6 bytes to compressed size. + 1) Stream without end mark. You must know exact uncompressed size to decompress such + stream. */ + +typedef enum +{ + LZMA_FINISH_ANY, /* finish at any point */ + LZMA_FINISH_END /* block must be finished at the end */ +} ELzmaFinishMode; + +/* ELzmaFinishMode has meaning only if the decoding reaches output limit !!! + + You must use LZMA_FINISH_END, when you know that current output buffer + covers last bytes of block. In other cases you must use LZMA_FINISH_ANY. + + If LZMA decoder sees end marker before reaching output limit, it returns SZ_OK, + and output value of destLen will be less than output buffer size limit. + You can check status result also. + + You can use multiple checks to test data integrity after full decompression: + 1) Check Result and "status" variable. + 2) Check that output(destLen) = uncompressedSize, if you know real uncompressedSize. + 3) Check that output(srcLen) = compressedSize, if you know real compressedSize. + You must use correct finish mode in that case. */ + +typedef enum +{ + LZMA_STATUS_NOT_SPECIFIED, /* use main error code instead */ + LZMA_STATUS_FINISHED_WITH_MARK, /* stream was finished with end mark. */ + LZMA_STATUS_NOT_FINISHED, /* stream was not finished */ + LZMA_STATUS_NEEDS_MORE_INPUT, /* you must provide more input bytes */ + LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK /* there is probability that stream was finished + without end mark */ +} ELzmaStatus; + +/* ELzmaStatus is used only as output value for function call */ + +/* ---------- Interfaces ---------- */ + +/* There are 3 levels of interfaces: + 1) Dictionary Interface + 2) Buffer Interface + 3) One Call Interface + You can select any of these interfaces, but don't mix functions from different + groups for same object. */ + +/* There are two variants to allocate state for Dictionary Interface: + 1) LzmaDec_Allocate / LzmaDec_Free + 2) LzmaDec_AllocateProbs / LzmaDec_FreeProbs + You can use variant 2, if you set dictionary buffer manually. + For Buffer Interface you must always use variant 1. + +LzmaDec_Allocate* can return: + SZ_OK + SZ_ERROR_MEM - Memory allocation error + SZ_ERROR_UNSUPPORTED - Unsupported properties +*/ + +SRes LzmaDec_AllocateProbs(CLzmaDec *p, const uint8_t *props, unsigned propsSize); +void LzmaDec_FreeProbs(CLzmaDec *p); + +SRes LzmaDec_Allocate(CLzmaDec *state, const uint8_t *prop, unsigned propsSize); +void LzmaDec_Free(CLzmaDec *state); + +/* ---------- Dictionary Interface ---------- */ + +/* You can use it, if you want to eliminate the overhead for data copying from + dictionary to some other external buffer. + You must work with CLzmaDec variables directly in this interface. + + STEPS: + LzmaDec_Constr() + LzmaDec_Allocate() + for (each new stream) + { + LzmaDec_Init() + while (it needs more decompression) + { + LzmaDec_DecodeToDic() + use data from CLzmaDec::dic and update CLzmaDec::dicPos + } + } + LzmaDec_Free() +*/ + +/* LzmaDec_DecodeToDic + + The decoding to internal dictionary buffer (CLzmaDec::dic). + You must manually update CLzmaDec::dicPos, if it reaches CLzmaDec::dicBufSize !!! + +finishMode: + It has meaning only if the decoding reaches output limit (dicLimit). + LZMA_FINISH_ANY - Decode just dicLimit bytes. + LZMA_FINISH_END - Stream must be finished after dicLimit. + +Returns: + SZ_OK + status: + LZMA_STATUS_FINISHED_WITH_MARK + LZMA_STATUS_NOT_FINISHED + LZMA_STATUS_NEEDS_MORE_INPUT + LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK + SZ_ERROR_DATA - Data error +*/ + +SRes LzmaDec_DecodeToDic(CLzmaDec *p, size_t dicLimit, const uint8_t *src, size_t *srcLen, + ELzmaFinishMode finishMode, ELzmaStatus *status); + +/* ---------- Buffer Interface ---------- */ + +/* It's zlib-like interface. + See LzmaDec_DecodeToDic description for information about STEPS and return results, + but you must use LzmaDec_DecodeToBuf instead of LzmaDec_DecodeToDic and you don't need + to work with CLzmaDec variables manually. + +finishMode: + It has meaning only if the decoding reaches output limit (*destLen). + LZMA_FINISH_ANY - Decode just destLen bytes. + LZMA_FINISH_END - Stream must be finished after (*destLen). +*/ + +SRes LzmaDec_DecodeToBuf(CLzmaDec *p, uint8_t *dest, size_t *destLen, const uint8_t *src, + size_t *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status); + +/* ---------- One Call Interface ---------- */ + +/* LzmaDecode + +finishMode: + It has meaning only if the decoding reaches output limit (*destLen). + LZMA_FINISH_ANY - Decode just destLen bytes. + LZMA_FINISH_END - Stream must be finished after (*destLen). + +Returns: + SZ_OK + status: + LZMA_STATUS_FINISHED_WITH_MARK + LZMA_STATUS_NOT_FINISHED + LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK + SZ_ERROR_DATA - Data error + SZ_ERROR_MEM - Memory allocation error + SZ_ERROR_UNSUPPORTED - Unsupported properties + SZ_ERROR_INPUT_EOF - It needs more bytes in input buffer (src). +*/ + +SRes LzmaDecode(uint8_t *dest, size_t *destLen, const uint8_t *src, size_t *srcLen, + const uint8_t *propData, unsigned propSize, ELzmaFinishMode finishMode, + ELzmaStatus *status); diff --git a/depends/lzma/pavlov/LzmaEnc.c b/depends/lzma/pavlov/LzmaEnc.c new file mode 100755 index 00000000..ac34eb45 --- /dev/null +++ b/depends/lzma/pavlov/LzmaEnc.c @@ -0,0 +1,2349 @@ +/* LzmaEnc.c -- LZMA Encoder +2008-10-04 : Igor Pavlov : Public domain */ + +#include +#include + +/* #define SHOW_STAT */ +/* #define SHOW_STAT2 */ + +#if defined(SHOW_STAT) || defined(SHOW_STAT2) +#include +#endif + +#include "LzmaEnc.h" + +#include "LzFind.h" +#ifdef COMPRESS_MF_MT +#include "LzFindMt.h" +#endif + +#ifdef SHOW_STAT +static int ttt = 0; +#endif + +#define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1) + +#define kBlockSize (9 << 10) +#define kUnpackBlockSize (1 << 18) +#define kMatchArraySize (1 << 21) +#define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX) + +#define kNumMaxDirectBits (31) + +#define kNumTopBits 24 +#define kTopValue ((uint32_t)1 << kNumTopBits) + +#define kNumBitModelTotalBits 11 +#define kBitModelTotal (1 << kNumBitModelTotalBits) +#define kNumMoveBits 5 +#define kProbInitValue (kBitModelTotal >> 1) + +#define kNumMoveReducingBits 4 +#define kNumBitPriceShiftBits 4 +#define kBitPrice (1 << kNumBitPriceShiftBits) + +void LzmaEncProps_Init(CLzmaEncProps *p) +{ + p->level = 5; + p->dictSize = p->mc = 0; + p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1; + p->writeEndMark = 0; +} + +void LzmaEncProps_Normalize(CLzmaEncProps *p) +{ + int level = p->level; + if (level < 0) + level = 5; + p->level = level; + if (p->dictSize == 0) + p->dictSize = + (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26))); + if (p->lc < 0) + p->lc = 3; + if (p->lp < 0) + p->lp = 0; + if (p->pb < 0) + p->pb = 2; + if (p->algo < 0) + p->algo = (level < 5 ? 0 : 1); + if (p->fb < 0) + p->fb = (level < 7 ? 32 : 64); + if (p->btMode < 0) + p->btMode = (p->algo == 0 ? 0 : 1); + if (p->numHashBytes < 0) + p->numHashBytes = 4; + if (p->mc == 0) + p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1); + if (p->numThreads < 0) + p->numThreads = ((p->btMode && p->algo) ? 2 : 1); +} + +uint32_t LzmaEncProps_GetDictSize(const CLzmaEncProps *props2) +{ + CLzmaEncProps props = *props2; + LzmaEncProps_Normalize(&props); + return props.dictSize; +} + +/* #define LZMA_LOG_BSR */ +/* Define it for Intel's CPU */ + +#ifdef LZMA_LOG_BSR + +#define kDicLogSizeMaxCompress 30 + +#define BSR2_RET(pos, res) \ + { \ + unsigned long i; \ + _BitScanReverse(&i, (pos)); \ + res = (i + i) + ((pos >> (i - 1)) & 1); \ + } + +uint32_t GetPosSlot1(uint32_t pos) +{ + uint32_t res; + BSR2_RET(pos, res); + return res; +} +#define GetPosSlot2(pos, res) \ + { \ + BSR2_RET(pos, res); \ + } +#define GetPosSlot(pos, res) \ + { \ + if (pos < 2) \ + res = pos; \ + else \ + BSR2_RET(pos, res); \ + } + +#else + +#define kNumLogBits (9 + (int)sizeof(size_t) / 2) +#define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7) + +void LzmaEnc_FastPosInit(uint8_t *g_FastPos) +{ + int c = 2, slotFast; + g_FastPos[0] = 0; + g_FastPos[1] = 1; + + for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++) + { + uint32_t k = (1 << ((slotFast >> 1) - 1)); + uint32_t j; + for (j = 0; j < k; j++, c++) + g_FastPos[c] = (uint8_t)slotFast; + } +} + +#define BSR2_RET(pos, res) \ + { \ + uint32_t i = 6 + ((kNumLogBits - 1) & \ + (0 - (((((uint32_t)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \ + res = p->g_FastPos[pos >> i] + (i * 2); \ + } +/* +#define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \ + p->g_FastPos[pos >> 6] + 12 : \ + p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; } +*/ + +#define GetPosSlot1(pos) p->g_FastPos[pos] +#define GetPosSlot2(pos, res) \ + { \ + BSR2_RET(pos, res); \ + } +#define GetPosSlot(pos, res) \ + { \ + if (pos < kNumFullDistances) \ + res = p->g_FastPos[pos]; \ + else \ + BSR2_RET(pos, res); \ + } + +#endif + +#define LZMA_NUM_REPS 4 + +typedef unsigned CState; + +typedef struct _COptimal +{ + uint32_t price; + + CState state; + int prev1IsChar; + int prev2; + + uint32_t posPrev2; + uint32_t backPrev2; + + uint32_t posPrev; + uint32_t backPrev; + uint32_t backs[LZMA_NUM_REPS]; +} COptimal; + +#define kNumOpts (1 << 12) + +#define kNumLenToPosStates 4 +#define kNumPosSlotBits 6 +#define kDicLogSizeMin 0 +#define kDicLogSizeMax 32 +#define kDistTableSizeMax (kDicLogSizeMax * 2) + +#define kNumAlignBits 4 +#define kAlignTableSize (1 << kNumAlignBits) +#define kAlignMask (kAlignTableSize - 1) + +#define kStartPosModelIndex 4 +#define kEndPosModelIndex 14 +#define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex) + +#define kNumFullDistances (1 << (kEndPosModelIndex / 2)) + +#ifdef _LZMA_PROB32 +#define CLzmaProb uint32_t +#else +#define CLzmaProb uint16_t +#endif + +#define LZMA_PB_MAX 4 +#define LZMA_LC_MAX 8 +#define LZMA_LP_MAX 4 + +#define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX) + +#define kLenNumLowBits 3 +#define kLenNumLowSymbols (1 << kLenNumLowBits) +#define kLenNumMidBits 3 +#define kLenNumMidSymbols (1 << kLenNumMidBits) +#define kLenNumHighBits 8 +#define kLenNumHighSymbols (1 << kLenNumHighBits) + +#define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols) + +#define LZMA_MATCH_LEN_MIN 2 +#define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1) + +#define kNumStates 12 + +typedef struct +{ + CLzmaProb choice; + CLzmaProb choice2; + CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits]; + CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits]; + CLzmaProb high[kLenNumHighSymbols]; +} CLenEnc; + +typedef struct +{ + CLenEnc p; + uint32_t prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal]; + uint32_t tableSize; + uint32_t counters[LZMA_NUM_PB_STATES_MAX]; +} CLenPriceEnc; + +typedef struct _CRangeEnc +{ + uint32_t range; + uint8_t cache; + uint64_t low; + uint64_t cacheSize; + uint8_t *buf; + uint8_t *bufLim; + uint8_t *bufBase; + ISeqOutStream *outStream; + uint64_t processed; + SRes res; +} CRangeEnc; + +typedef struct _CSeqInStreamBuf +{ + ISeqInStream funcTable; + const uint8_t *data; + size_t rem; +} CSeqInStreamBuf; + +static SRes MyRead(void *pp, void *data, size_t *size) +{ + size_t curSize = *size; + CSeqInStreamBuf *p = (CSeqInStreamBuf *)pp; + if (p->rem < curSize) + curSize = p->rem; + memcpy(data, p->data, curSize); + p->rem -= curSize; + p->data += curSize; + *size = curSize; + return SZ_OK; +} + +typedef struct +{ + CLzmaProb *litProbs; + + CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; + CLzmaProb isRep[kNumStates]; + CLzmaProb isRepG0[kNumStates]; + CLzmaProb isRepG1[kNumStates]; + CLzmaProb isRepG2[kNumStates]; + CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; + + CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; + CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex]; + CLzmaProb posAlignEncoder[1 << kNumAlignBits]; + + CLenPriceEnc lenEnc; + CLenPriceEnc repLenEnc; + + uint32_t reps[LZMA_NUM_REPS]; + uint32_t state; +} CSaveState; + +typedef struct _CLzmaEnc +{ + IMatchFinder matchFinder; + void *matchFinderObj; + +#ifdef COMPRESS_MF_MT + Bool mtMode; + CMatchFinderMt matchFinderMt; +#endif + + CMatchFinder matchFinderBase; + +#ifdef COMPRESS_MF_MT + Byte pad[128]; +#endif + + uint32_t optimumEndIndex; + uint32_t optimumCurrentIndex; + + uint32_t longestMatchLength; + uint32_t numPairs; + uint32_t numAvail; + COptimal opt[kNumOpts]; + +#ifndef LZMA_LOG_BSR + uint8_t g_FastPos[1 << kNumLogBits]; +#endif + + uint32_t ProbPrices[kBitModelTotal >> kNumMoveReducingBits]; + uint32_t matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1]; + uint32_t numFastBytes; + uint32_t additionalOffset; + uint32_t reps[LZMA_NUM_REPS]; + uint32_t state; + + uint32_t posSlotPrices[kNumLenToPosStates][kDistTableSizeMax]; + uint32_t distancesPrices[kNumLenToPosStates][kNumFullDistances]; + uint32_t alignPrices[kAlignTableSize]; + uint32_t alignPriceCount; + + uint32_t distTableSize; + + unsigned lc, lp, pb; + unsigned lpMask, pbMask; + + CLzmaProb *litProbs; + + CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; + CLzmaProb isRep[kNumStates]; + CLzmaProb isRepG0[kNumStates]; + CLzmaProb isRepG1[kNumStates]; + CLzmaProb isRepG2[kNumStates]; + CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; + + CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; + CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex]; + CLzmaProb posAlignEncoder[1 << kNumAlignBits]; + + CLenPriceEnc lenEnc; + CLenPriceEnc repLenEnc; + + unsigned lclp; + + Bool fastMode; + + CRangeEnc rc; + + Bool writeEndMark; + uint64_t nowPos64; + uint32_t matchPriceCount; + Bool finished; + Bool multiThread; + + SRes result; + uint32_t dictSize; + uint32_t matchFinderCycles; + + ISeqInStream *inStream; + CSeqInStreamBuf seqBufInStream; + + CSaveState saveState; +} CLzmaEnc; + +void LzmaEnc_SaveState(CLzmaEncHandle pp) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + CSaveState *dest = &p->saveState; + int i; + dest->lenEnc = p->lenEnc; + dest->repLenEnc = p->repLenEnc; + dest->state = p->state; + + for (i = 0; i < kNumStates; i++) + { + memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i])); + memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i])); + } + for (i = 0; i < kNumLenToPosStates; i++) + memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i])); + memcpy(dest->isRep, p->isRep, sizeof(p->isRep)); + memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0)); + memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1)); + memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2)); + memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders)); + memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder)); + memcpy(dest->reps, p->reps, sizeof(p->reps)); + memcpy(dest->litProbs, p->litProbs, (0x300 << p->lclp) * sizeof(CLzmaProb)); +} + +void LzmaEnc_RestoreState(CLzmaEncHandle pp) +{ + CLzmaEnc *dest = (CLzmaEnc *)pp; + const CSaveState *p = &dest->saveState; + int i; + dest->lenEnc = p->lenEnc; + dest->repLenEnc = p->repLenEnc; + dest->state = p->state; + + for (i = 0; i < kNumStates; i++) + { + memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i])); + memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i])); + } + for (i = 0; i < kNumLenToPosStates; i++) + memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i])); + memcpy(dest->isRep, p->isRep, sizeof(p->isRep)); + memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0)); + memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1)); + memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2)); + memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders)); + memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder)); + memcpy(dest->reps, p->reps, sizeof(p->reps)); + memcpy(dest->litProbs, p->litProbs, (0x300 << dest->lclp) * sizeof(CLzmaProb)); +} + +SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + CLzmaEncProps props = *props2; + LzmaEncProps_Normalize(&props); + + if (props.lc > LZMA_LC_MAX || props.lp > LZMA_LP_MAX || props.pb > LZMA_PB_MAX || + props.dictSize > (1 << kDicLogSizeMaxCompress) || props.dictSize > (1 << 30)) + return SZ_ERROR_PARAM; + p->dictSize = props.dictSize; + p->matchFinderCycles = props.mc; + { + unsigned fb = props.fb; + if (fb < 5) + fb = 5; + if (fb > LZMA_MATCH_LEN_MAX) + fb = LZMA_MATCH_LEN_MAX; + p->numFastBytes = fb; + } + p->lc = props.lc; + p->lp = props.lp; + p->pb = props.pb; + p->fastMode = (props.algo == 0); + p->matchFinderBase.btMode = props.btMode; + { + uint32_t numHashBytes = 4; + if (props.btMode) + { + if (props.numHashBytes < 2) + numHashBytes = 2; + else if (props.numHashBytes < 4) + numHashBytes = props.numHashBytes; + } + p->matchFinderBase.numHashBytes = numHashBytes; + } + + p->matchFinderBase.cutValue = props.mc; + + p->writeEndMark = props.writeEndMark; + +#ifdef COMPRESS_MF_MT + /* + if (newMultiThread != _multiThread) + { + ReleaseMatchFinder(); + _multiThread = newMultiThread; + } + */ + p->multiThread = (props.numThreads > 1); +#endif + + return SZ_OK; +} + +static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5}; +static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10}; +static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11}; +static const int kShortRepNextStates[kNumStates] = {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11}; + +#define IsCharState(s) ((s) < 7) + +#define GetLenToPosState(len) \ + (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1) + +#define kInfinityPrice (1 << 30) + +static void RangeEnc_Construct(CRangeEnc *p) +{ + p->outStream = 0; + p->bufBase = 0; +} + +#define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize) + +#define RC_BUF_SIZE (1 << 16) +static int RangeEnc_Alloc(CRangeEnc *p) +{ + if (p->bufBase == 0) + { + p->bufBase = malloc(RC_BUF_SIZE); + if (p->bufBase == 0) + return 0; + p->bufLim = p->bufBase + RC_BUF_SIZE; + } + return 1; +} + +static void RangeEnc_Free(CRangeEnc *p) +{ + free(p->bufBase); + p->bufBase = 0; +} + +static void RangeEnc_Init(CRangeEnc *p) +{ + /* Stream.Init(); */ + p->low = 0; + p->range = 0xFFFFFFFF; + p->cacheSize = 1; + p->cache = 0; + + p->buf = p->bufBase; + + p->processed = 0; + p->res = SZ_OK; +} + +static void RangeEnc_FlushStream(CRangeEnc *p) +{ + size_t num; + if (p->res != SZ_OK) + return; + num = p->buf - p->bufBase; + if (num != p->outStream->Write(p->outStream, p->bufBase, num)) + p->res = SZ_ERROR_WRITE; + p->processed += num; + p->buf = p->bufBase; +} + +static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p) +{ + if ((uint32_t)p->low < (uint32_t)0xFF000000 || (int)(p->low >> 32) != 0) + { + uint8_t temp = p->cache; + do + { + uint8_t *buf = p->buf; + *buf++ = (uint8_t)(temp + (uint8_t)(p->low >> 32)); + p->buf = buf; + if (buf == p->bufLim) + RangeEnc_FlushStream(p); + temp = 0xFF; + } while (--p->cacheSize != 0); + p->cache = (uint8_t)((uint32_t)p->low >> 24); + } + p->cacheSize++; + p->low = (uint32_t)p->low << 8; +} + +static void RangeEnc_FlushData(CRangeEnc *p) +{ + int i; + for (i = 0; i < 5; i++) + RangeEnc_ShiftLow(p); +} + +static void RangeEnc_EncodeDirectBits(CRangeEnc *p, uint32_t value, int numBits) +{ + do + { + p->range >>= 1; + p->low += p->range & (0 - ((value >> --numBits) & 1)); + if (p->range < kTopValue) + { + p->range <<= 8; + RangeEnc_ShiftLow(p); + } + } while (numBits != 0); +} + +static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, uint32_t symbol) +{ + uint32_t ttt = *prob; + uint32_t newBound = (p->range >> kNumBitModelTotalBits) * ttt; + if (symbol == 0) + { + p->range = newBound; + ttt += (kBitModelTotal - ttt) >> kNumMoveBits; + } + else + { + p->low += newBound; + p->range -= newBound; + ttt -= ttt >> kNumMoveBits; + } + *prob = (CLzmaProb)ttt; + if (p->range < kTopValue) + { + p->range <<= 8; + RangeEnc_ShiftLow(p); + } +} + +static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, uint32_t symbol) +{ + symbol |= 0x100; + do + { + RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1); + symbol <<= 1; + } while (symbol < 0x10000); +} + +static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, uint32_t symbol, + uint32_t matchByte) +{ + uint32_t offs = 0x100; + symbol |= 0x100; + do + { + matchByte <<= 1; + RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), + (symbol >> 7) & 1); + symbol <<= 1; + offs &= ~(matchByte ^ symbol); + } while (symbol < 0x10000); +} + +void LzmaEnc_InitPriceTables(uint32_t *ProbPrices) +{ + uint32_t i; + for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; + i += (1 << kNumMoveReducingBits)) + { + const int kCyclesBits = kNumBitPriceShiftBits; + uint32_t w = i; + uint32_t bitCount = 0; + int j; + for (j = 0; j < kCyclesBits; j++) + { + w = w * w; + bitCount <<= 1; + while (w >= ((uint32_t)1 << 16)) + { + w >>= 1; + bitCount++; + } + } + ProbPrices[i >> kNumMoveReducingBits] = + ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount); + } +} + +#define GET_PRICE(prob, symbol) \ + p->ProbPrices \ + [((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]; + +#define GET_PRICEa(prob, symbol) \ + ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]; + +#define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits] +#define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits] + +#define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits] +#define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits] + +static uint32_t LitEnc_GetPrice(const CLzmaProb *probs, uint32_t symbol, uint32_t *ProbPrices) +{ + uint32_t price = 0; + symbol |= 0x100; + do + { + price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1); + symbol <<= 1; + } while (symbol < 0x10000); + return price; +} + +static uint32_t LitEnc_GetPriceMatched(const CLzmaProb *probs, uint32_t symbol, + uint32_t matchByte, uint32_t *ProbPrices) +{ + uint32_t price = 0; + uint32_t offs = 0x100; + symbol |= 0x100; + do + { + matchByte <<= 1; + price += + GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1); + symbol <<= 1; + offs &= ~(matchByte ^ symbol); + } while (symbol < 0x10000); + return price; +} + +static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, uint32_t symbol) +{ + uint32_t m = 1; + int i; + for (i = numBitLevels; i != 0;) + { + uint32_t bit; + i--; + bit = (symbol >> i) & 1; + RangeEnc_EncodeBit(rc, probs + m, bit); + m = (m << 1) | bit; + } +} + +static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, + uint32_t symbol) +{ + uint32_t m = 1; + int i; + for (i = 0; i < numBitLevels; i++) + { + uint32_t bit = symbol & 1; + RangeEnc_EncodeBit(rc, probs + m, bit); + m = (m << 1) | bit; + symbol >>= 1; + } +} + +static uint32_t RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, uint32_t symbol, + uint32_t *ProbPrices) +{ + uint32_t price = 0; + symbol |= (1 << numBitLevels); + while (symbol != 1) + { + price += GET_PRICEa(probs[symbol >> 1], symbol & 1); + symbol >>= 1; + } + return price; +} + +static uint32_t RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, + uint32_t symbol, uint32_t *ProbPrices) +{ + uint32_t price = 0; + uint32_t m = 1; + int i; + for (i = numBitLevels; i != 0; i--) + { + uint32_t bit = symbol & 1; + symbol >>= 1; + price += GET_PRICEa(probs[m], bit); + m = (m << 1) | bit; + } + return price; +} + +static void LenEnc_Init(CLenEnc *p) +{ + unsigned i; + p->choice = p->choice2 = kProbInitValue; + for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++) + p->low[i] = kProbInitValue; + for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++) + p->mid[i] = kProbInitValue; + for (i = 0; i < kLenNumHighSymbols; i++) + p->high[i] = kProbInitValue; +} + +static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, uint32_t symbol, uint32_t posState) +{ + if (symbol < kLenNumLowSymbols) + { + RangeEnc_EncodeBit(rc, &p->choice, 0); + RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol); + } + else + { + RangeEnc_EncodeBit(rc, &p->choice, 1); + if (symbol < kLenNumLowSymbols + kLenNumMidSymbols) + { + RangeEnc_EncodeBit(rc, &p->choice2, 0); + RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, + symbol - kLenNumLowSymbols); + } + else + { + RangeEnc_EncodeBit(rc, &p->choice2, 1); + RcTree_Encode(rc, p->high, kLenNumHighBits, + symbol - kLenNumLowSymbols - kLenNumMidSymbols); + } + } +} + +static void LenEnc_SetPrices(CLenEnc *p, uint32_t posState, uint32_t numSymbols, + uint32_t *prices, uint32_t *ProbPrices) +{ + uint32_t a0 = GET_PRICE_0a(p->choice); + uint32_t a1 = GET_PRICE_1a(p->choice); + uint32_t b0 = a1 + GET_PRICE_0a(p->choice2); + uint32_t b1 = a1 + GET_PRICE_1a(p->choice2); + uint32_t i = 0; + for (i = 0; i < kLenNumLowSymbols; i++) + { + if (i >= numSymbols) + return; + prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, + i, ProbPrices); + } + for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++) + { + if (i >= numSymbols) + return; + prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, + i - kLenNumLowSymbols, ProbPrices); + } + for (; i < numSymbols; i++) + prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, + i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices); +} + +static void MY_FAST_CALL +LenPriceEnc_UpdateTable(CLenPriceEnc *p, uint32_t posState, uint32_t *ProbPrices) +{ + LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices); + p->counters[posState] = p->tableSize; +} + +static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, uint32_t numPosStates, + uint32_t *ProbPrices) +{ + uint32_t posState; + for (posState = 0; posState < numPosStates; posState++) + LenPriceEnc_UpdateTable(p, posState, ProbPrices); +} + +static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, uint32_t symbol, uint32_t posState, + Bool updatePrice, uint32_t *ProbPrices) +{ + LenEnc_Encode(&p->p, rc, symbol, posState); + if (updatePrice) + if (--p->counters[posState] == 0) + LenPriceEnc_UpdateTable(p, posState, ProbPrices); +} + +static void MovePos(CLzmaEnc *p, uint32_t num) +{ +#ifdef SHOW_STAT + ttt += num; + printf("\n MovePos %d", num); +#endif + if (num != 0) + { + p->additionalOffset += num; + p->matchFinder.Skip(p->matchFinderObj, num); + } +} + +static uint32_t ReadMatchDistances(CLzmaEnc *p, uint32_t *numDistancePairsRes) +{ + uint32_t lenRes = 0, numPairs; + p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); + numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches); +#ifdef SHOW_STAT + printf("\n i = %d numPairs = %d ", ttt, numPairs / 2); + ttt++; + { + uint32_t i; + for (i = 0; i < numPairs; i += 2) + printf("%2d %6d | ", p->matches[i], p->matches[i + 1]); + } +#endif + if (numPairs > 0) + { + lenRes = p->matches[numPairs - 2]; + if (lenRes == p->numFastBytes) + { + const uint8_t *pby = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; + uint32_t distance = p->matches[numPairs - 1] + 1; + uint32_t numAvail = p->numAvail; + if (numAvail > LZMA_MATCH_LEN_MAX) + numAvail = LZMA_MATCH_LEN_MAX; + { + const uint8_t *pby2 = pby - distance; + for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++) + ; + } + } + } + p->additionalOffset++; + *numDistancePairsRes = numPairs; + return lenRes; +} + +#define MakeAsChar(p) \ + (p)->backPrev = (uint32_t)(-1); \ + (p)->prev1IsChar = False; +#define MakeAsShortRep(p) \ + (p)->backPrev = 0; \ + (p)->prev1IsChar = False; +#define IsShortRep(p) ((p)->backPrev == 0) + +static uint32_t GetRepLen1Price(CLzmaEnc *p, uint32_t state, uint32_t posState) +{ + return GET_PRICE_0(p->isRepG0[state]) + GET_PRICE_0(p->isRep0Long[state][posState]); +} + +static uint32_t GetPureRepPrice(CLzmaEnc *p, uint32_t repIndex, uint32_t state, + uint32_t posState) +{ + uint32_t price; + if (repIndex == 0) + { + price = GET_PRICE_0(p->isRepG0[state]); + price += GET_PRICE_1(p->isRep0Long[state][posState]); + } + else + { + price = GET_PRICE_1(p->isRepG0[state]); + if (repIndex == 1) + price += GET_PRICE_0(p->isRepG1[state]); + else + { + price += GET_PRICE_1(p->isRepG1[state]); + price += GET_PRICE(p->isRepG2[state], repIndex - 2); + } + } + return price; +} + +static uint32_t GetRepPrice(CLzmaEnc *p, uint32_t repIndex, uint32_t len, uint32_t state, + uint32_t posState) +{ + return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] + + GetPureRepPrice(p, repIndex, state, posState); +} + +static uint32_t Backward(CLzmaEnc *p, uint32_t *backRes, uint32_t cur) +{ + uint32_t posMem = p->opt[cur].posPrev; + uint32_t backMem = p->opt[cur].backPrev; + p->optimumEndIndex = cur; + do + { + if (p->opt[cur].prev1IsChar) + { + MakeAsChar(&p->opt[posMem]) + p->opt[posMem].posPrev = posMem - 1; + if (p->opt[cur].prev2) + { + p->opt[posMem - 1].prev1IsChar = False; + p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2; + p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2; + } + } + { + uint32_t posPrev = posMem; + uint32_t backCur = backMem; + + backMem = p->opt[posPrev].backPrev; + posMem = p->opt[posPrev].posPrev; + + p->opt[posPrev].backPrev = backCur; + p->opt[posPrev].posPrev = cur; + cur = posPrev; + } + } while (cur != 0); + *backRes = p->opt[0].backPrev; + p->optimumCurrentIndex = p->opt[0].posPrev; + return p->optimumCurrentIndex; +} + +#define LIT_PROBS(pos, prevByte) \ + (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300) + +static uint32_t GetOptimum(CLzmaEnc *p, uint32_t position, uint32_t *backRes) +{ + uint32_t numAvail, mainLen, numPairs, repMaxIndex, i, posState, lenEnd, len, cur; + uint32_t matchPrice, repMatchPrice, normalMatchPrice; + uint32_t reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS]; + uint32_t *matches; + const uint8_t *data; + uint8_t curByte, matchByte; + if (p->optimumEndIndex != p->optimumCurrentIndex) + { + const COptimal *opt = &p->opt[p->optimumCurrentIndex]; + uint32_t lenRes = opt->posPrev - p->optimumCurrentIndex; + *backRes = opt->backPrev; + p->optimumCurrentIndex = opt->posPrev; + return lenRes; + } + p->optimumCurrentIndex = p->optimumEndIndex = 0; + + if (p->additionalOffset == 0) + mainLen = ReadMatchDistances(p, &numPairs); + else + { + mainLen = p->longestMatchLength; + numPairs = p->numPairs; + } + + numAvail = p->numAvail; + if (numAvail < 2) + { + *backRes = (uint32_t)(-1); + return 1; + } + if (numAvail > LZMA_MATCH_LEN_MAX) + numAvail = LZMA_MATCH_LEN_MAX; + + data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; + repMaxIndex = 0; + for (i = 0; i < LZMA_NUM_REPS; i++) + { + uint32_t lenTest; + const uint8_t *data2; + reps[i] = p->reps[i]; + data2 = data - (reps[i] + 1); + if (data[0] != data2[0] || data[1] != data2[1]) + { + repLens[i] = 0; + continue; + } + for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++) + ; + repLens[i] = lenTest; + if (lenTest > repLens[repMaxIndex]) + repMaxIndex = i; + } + if (repLens[repMaxIndex] >= p->numFastBytes) + { + uint32_t lenRes; + *backRes = repMaxIndex; + lenRes = repLens[repMaxIndex]; + MovePos(p, lenRes - 1); + return lenRes; + } + + matches = p->matches; + if (mainLen >= p->numFastBytes) + { + *backRes = matches[numPairs - 1] + LZMA_NUM_REPS; + MovePos(p, mainLen - 1); + return mainLen; + } + curByte = *data; + matchByte = *(data - (reps[0] + 1)); + + if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2) + { + *backRes = (uint32_t) - 1; + return 1; + } + + p->opt[0].state = (CState)p->state; + + posState = (position & p->pbMask); + + { + const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); + p->opt[1].price = + GET_PRICE_0(p->isMatch[p->state][posState]) + + (!IsCharState(p->state) + ? LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) + : LitEnc_GetPrice(probs, curByte, p->ProbPrices)); + } + + MakeAsChar(&p->opt[1]); + + matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]); + repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]); + + if (matchByte == curByte) + { + uint32_t shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState); + if (shortRepPrice < p->opt[1].price) + { + p->opt[1].price = shortRepPrice; + MakeAsShortRep(&p->opt[1]); + } + } + lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]); + + if (lenEnd < 2) + { + *backRes = p->opt[1].backPrev; + return 1; + } + + p->opt[1].posPrev = 0; + for (i = 0; i < LZMA_NUM_REPS; i++) + p->opt[0].backs[i] = reps[i]; + + len = lenEnd; + do + p->opt[len--].price = kInfinityPrice; + while (len >= 2); + + for (i = 0; i < LZMA_NUM_REPS; i++) + { + uint32_t repLen = repLens[i]; + uint32_t price; + if (repLen < 2) + continue; + price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState); + do + { + uint32_t curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2]; + COptimal *opt = &p->opt[repLen]; + if (curAndLenPrice < opt->price) + { + opt->price = curAndLenPrice; + opt->posPrev = 0; + opt->backPrev = i; + opt->prev1IsChar = False; + } + } while (--repLen >= 2); + } + + normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]); + + len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2); + if (len <= mainLen) + { + uint32_t offs = 0; + while (len > matches[offs]) + offs += 2; + for (;; len++) + { + COptimal *opt; + uint32_t distance = matches[offs + 1]; + + uint32_t curAndLenPrice = + normalMatchPrice + p->lenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN]; + uint32_t lenToPosState = GetLenToPosState(len); + if (distance < kNumFullDistances) + curAndLenPrice += p->distancesPrices[lenToPosState][distance]; + else + { + uint32_t slot; + GetPosSlot2(distance, slot); + curAndLenPrice += p->alignPrices[distance & kAlignMask] + + p->posSlotPrices[lenToPosState][slot]; + } + opt = &p->opt[len]; + if (curAndLenPrice < opt->price) + { + opt->price = curAndLenPrice; + opt->posPrev = 0; + opt->backPrev = distance + LZMA_NUM_REPS; + opt->prev1IsChar = False; + } + if (len == matches[offs]) + { + offs += 2; + if (offs == numPairs) + break; + } + } + } + + cur = 0; + +#ifdef SHOW_STAT2 + if (position >= 0) + { + unsigned i; + printf("\n pos = %4X", position); + for (i = cur; i <= lenEnd; i++) + printf("\nprice[%4X] = %d", position - cur + i, p->opt[i].price); + } +#endif + + for (;;) + { + uint32_t numAvailFull, newLen, numPairs, posPrev, state, posState, startLen; + uint32_t curPrice, curAnd1Price, matchPrice, repMatchPrice; + Bool nextIsChar; + uint8_t curByte, matchByte; + const uint8_t *data; + COptimal *curOpt; + COptimal *nextOpt; + + cur++; + if (cur == lenEnd) + return Backward(p, backRes, cur); + + newLen = ReadMatchDistances(p, &numPairs); + if (newLen >= p->numFastBytes) + { + p->numPairs = numPairs; + p->longestMatchLength = newLen; + return Backward(p, backRes, cur); + } + position++; + curOpt = &p->opt[cur]; + posPrev = curOpt->posPrev; + if (curOpt->prev1IsChar) + { + posPrev--; + if (curOpt->prev2) + { + state = p->opt[curOpt->posPrev2].state; + if (curOpt->backPrev2 < LZMA_NUM_REPS) + state = kRepNextStates[state]; + else + state = kMatchNextStates[state]; + } + else + state = p->opt[posPrev].state; + state = kLiteralNextStates[state]; + } + else + state = p->opt[posPrev].state; + if (posPrev == cur - 1) + { + if (IsShortRep(curOpt)) + state = kShortRepNextStates[state]; + else + state = kLiteralNextStates[state]; + } + else + { + uint32_t pos; + const COptimal *prevOpt; + if (curOpt->prev1IsChar && curOpt->prev2) + { + posPrev = curOpt->posPrev2; + pos = curOpt->backPrev2; + state = kRepNextStates[state]; + } + else + { + pos = curOpt->backPrev; + if (pos < LZMA_NUM_REPS) + state = kRepNextStates[state]; + else + state = kMatchNextStates[state]; + } + prevOpt = &p->opt[posPrev]; + if (pos < LZMA_NUM_REPS) + { + uint32_t i; + reps[0] = prevOpt->backs[pos]; + for (i = 1; i <= pos; i++) + reps[i] = prevOpt->backs[i - 1]; + for (; i < LZMA_NUM_REPS; i++) + reps[i] = prevOpt->backs[i]; + } + else + { + uint32_t i; + reps[0] = (pos - LZMA_NUM_REPS); + for (i = 1; i < LZMA_NUM_REPS; i++) + reps[i] = prevOpt->backs[i - 1]; + } + } + curOpt->state = (CState)state; + + curOpt->backs[0] = reps[0]; + curOpt->backs[1] = reps[1]; + curOpt->backs[2] = reps[2]; + curOpt->backs[3] = reps[3]; + + curPrice = curOpt->price; + nextIsChar = False; + data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; + curByte = *data; + matchByte = *(data - (reps[0] + 1)); + + posState = (position & p->pbMask); + + curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]); + { + const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); + curAnd1Price += + (!IsCharState(state) + ? LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) + : LitEnc_GetPrice(probs, curByte, p->ProbPrices)); + } + + nextOpt = &p->opt[cur + 1]; + + if (curAnd1Price < nextOpt->price) + { + nextOpt->price = curAnd1Price; + nextOpt->posPrev = cur; + MakeAsChar(nextOpt); + nextIsChar = True; + } + + matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]); + repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]); + + if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev == 0)) + { + uint32_t shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState); + if (shortRepPrice <= nextOpt->price) + { + nextOpt->price = shortRepPrice; + nextOpt->posPrev = cur; + MakeAsShortRep(nextOpt); + nextIsChar = True; + } + } + numAvailFull = p->numAvail; + { + uint32_t temp = kNumOpts - 1 - cur; + if (temp < numAvailFull) + numAvailFull = temp; + } + + if (numAvailFull < 2) + continue; + numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes); + + if (!nextIsChar && matchByte != curByte) /* speed optimization */ + { + /* try Literal + rep0 */ + uint32_t temp; + uint32_t lenTest2; + const uint8_t *data2 = data - (reps[0] + 1); + uint32_t limit = p->numFastBytes + 1; + if (limit > numAvailFull) + limit = numAvailFull; + + for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++) + ; + lenTest2 = temp - 1; + if (lenTest2 >= 2) + { + uint32_t state2 = kLiteralNextStates[state]; + uint32_t posStateNext = (position + 1) & p->pbMask; + uint32_t nextRepMatchPrice = curAnd1Price + + GET_PRICE_1(p->isMatch[state2][posStateNext]) + + GET_PRICE_1(p->isRep[state2]); + /* for (; lenTest2 >= 2; lenTest2--) */ + { + uint32_t curAndLenPrice; + COptimal *opt; + uint32_t offset = cur + 1 + lenTest2; + while (lenEnd < offset) + p->opt[++lenEnd].price = kInfinityPrice; + curAndLenPrice = + nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext); + opt = &p->opt[offset]; + if (curAndLenPrice < opt->price) + { + opt->price = curAndLenPrice; + opt->posPrev = cur + 1; + opt->backPrev = 0; + opt->prev1IsChar = True; + opt->prev2 = False; + } + } + } + } + + startLen = 2; /* speed optimization */ + { + uint32_t repIndex; + for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++) + { + uint32_t lenTest; + uint32_t lenTestTemp; + uint32_t price; + const uint8_t *data2 = data - (reps[repIndex] + 1); + if (data[0] != data2[0] || data[1] != data2[1]) + continue; + for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; + lenTest++) + ; + while (lenEnd < cur + lenTest) + p->opt[++lenEnd].price = kInfinityPrice; + lenTestTemp = lenTest; + price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState); + do + { + uint32_t curAndLenPrice = + price + p->repLenEnc.prices[posState][lenTest - 2]; + COptimal *opt = &p->opt[cur + lenTest]; + if (curAndLenPrice < opt->price) + { + opt->price = curAndLenPrice; + opt->posPrev = cur; + opt->backPrev = repIndex; + opt->prev1IsChar = False; + } + } while (--lenTest >= 2); + lenTest = lenTestTemp; + + if (repIndex == 0) + startLen = lenTest + 1; + + /* if (_maxMode) */ + { + uint32_t lenTest2 = lenTest + 1; + uint32_t limit = lenTest2 + p->numFastBytes; + uint32_t nextRepMatchPrice; + if (limit > numAvailFull) + limit = numAvailFull; + for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++) + ; + lenTest2 -= lenTest + 1; + if (lenTest2 >= 2) + { + uint32_t state2 = kRepNextStates[state]; + uint32_t posStateNext = (position + lenTest) & p->pbMask; + uint32_t curAndLenCharPrice = + price + p->repLenEnc.prices[posState][lenTest - 2] + + GET_PRICE_0(p->isMatch[state2][posStateNext]) + + LitEnc_GetPriceMatched( + LIT_PROBS(position + lenTest, data[lenTest - 1]), data[lenTest], + data2[lenTest], p->ProbPrices); + state2 = kLiteralNextStates[state2]; + posStateNext = (position + lenTest + 1) & p->pbMask; + nextRepMatchPrice = curAndLenCharPrice + + GET_PRICE_1(p->isMatch[state2][posStateNext]) + + GET_PRICE_1(p->isRep[state2]); + + /* for (; lenTest2 >= 2; lenTest2--) */ + { + uint32_t curAndLenPrice; + COptimal *opt; + uint32_t offset = cur + lenTest + 1 + lenTest2; + while (lenEnd < offset) + p->opt[++lenEnd].price = kInfinityPrice; + curAndLenPrice = nextRepMatchPrice + + GetRepPrice(p, 0, lenTest2, state2, posStateNext); + opt = &p->opt[offset]; + if (curAndLenPrice < opt->price) + { + opt->price = curAndLenPrice; + opt->posPrev = cur + lenTest + 1; + opt->backPrev = 0; + opt->prev1IsChar = True; + opt->prev2 = True; + opt->posPrev2 = cur; + opt->backPrev2 = repIndex; + } + } + } + } + } + } + /* for (uint32_t lenTest = 2; lenTest <= newLen; lenTest++) */ + if (newLen > numAvail) + { + newLen = numAvail; + for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2) + ; + matches[numPairs] = newLen; + numPairs += 2; + } + if (newLen >= startLen) + { + uint32_t normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]); + uint32_t offs, curBack, posSlot; + uint32_t lenTest; + while (lenEnd < cur + newLen) + p->opt[++lenEnd].price = kInfinityPrice; + + offs = 0; + while (startLen > matches[offs]) + offs += 2; + curBack = matches[offs + 1]; + GetPosSlot2(curBack, posSlot); + for (lenTest = /*2*/ startLen;; lenTest++) + { + uint32_t curAndLenPrice = + normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN]; + uint32_t lenToPosState = GetLenToPosState(lenTest); + COptimal *opt; + if (curBack < kNumFullDistances) + curAndLenPrice += p->distancesPrices[lenToPosState][curBack]; + else + curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + + p->alignPrices[curBack & kAlignMask]; + + opt = &p->opt[cur + lenTest]; + if (curAndLenPrice < opt->price) + { + opt->price = curAndLenPrice; + opt->posPrev = cur; + opt->backPrev = curBack + LZMA_NUM_REPS; + opt->prev1IsChar = False; + } + + if (/*_maxMode && */ lenTest == matches[offs]) + { + /* Try Match + Literal + Rep0 */ + const uint8_t *data2 = data - (curBack + 1); + uint32_t lenTest2 = lenTest + 1; + uint32_t limit = lenTest2 + p->numFastBytes; + uint32_t nextRepMatchPrice; + if (limit > numAvailFull) + limit = numAvailFull; + for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++) + ; + lenTest2 -= lenTest + 1; + if (lenTest2 >= 2) + { + uint32_t state2 = kMatchNextStates[state]; + uint32_t posStateNext = (position + lenTest) & p->pbMask; + uint32_t curAndLenCharPrice = + curAndLenPrice + GET_PRICE_0(p->isMatch[state2][posStateNext]) + + LitEnc_GetPriceMatched( + LIT_PROBS(position + lenTest, data[lenTest - 1]), data[lenTest], + data2[lenTest], p->ProbPrices); + state2 = kLiteralNextStates[state2]; + posStateNext = (posStateNext + 1) & p->pbMask; + nextRepMatchPrice = curAndLenCharPrice + + GET_PRICE_1(p->isMatch[state2][posStateNext]) + + GET_PRICE_1(p->isRep[state2]); + + /* for (; lenTest2 >= 2; lenTest2--) */ + { + uint32_t offset = cur + lenTest + 1 + lenTest2; + uint32_t curAndLenPrice; + COptimal *opt; + while (lenEnd < offset) + p->opt[++lenEnd].price = kInfinityPrice; + curAndLenPrice = nextRepMatchPrice + + GetRepPrice(p, 0, lenTest2, state2, posStateNext); + opt = &p->opt[offset]; + if (curAndLenPrice < opt->price) + { + opt->price = curAndLenPrice; + opt->posPrev = cur + lenTest + 1; + opt->backPrev = 0; + opt->prev1IsChar = True; + opt->prev2 = True; + opt->posPrev2 = cur; + opt->backPrev2 = curBack + LZMA_NUM_REPS; + } + } + } + offs += 2; + if (offs == numPairs) + break; + curBack = matches[offs + 1]; + if (curBack >= kNumFullDistances) + GetPosSlot2(curBack, posSlot); + } + } + } + } +} + +#define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist)) + +static uint32_t GetOptimumFast(CLzmaEnc *p, uint32_t *backRes) +{ + uint32_t numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i; + const uint8_t *data; + const uint32_t *matches; + + if (p->additionalOffset == 0) + mainLen = ReadMatchDistances(p, &numPairs); + else + { + mainLen = p->longestMatchLength; + numPairs = p->numPairs; + } + + numAvail = p->numAvail; + *backRes = (uint32_t) - 1; + if (numAvail < 2) + return 1; + if (numAvail > LZMA_MATCH_LEN_MAX) + numAvail = LZMA_MATCH_LEN_MAX; + data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; + + repLen = repIndex = 0; + for (i = 0; i < LZMA_NUM_REPS; i++) + { + uint32_t len; + const uint8_t *data2 = data - (p->reps[i] + 1); + if (data[0] != data2[0] || data[1] != data2[1]) + continue; + for (len = 2; len < numAvail && data[len] == data2[len]; len++) + ; + if (len >= p->numFastBytes) + { + *backRes = i; + MovePos(p, len - 1); + return len; + } + if (len > repLen) + { + repIndex = i; + repLen = len; + } + } + + matches = p->matches; + if (mainLen >= p->numFastBytes) + { + *backRes = matches[numPairs - 1] + LZMA_NUM_REPS; + MovePos(p, mainLen - 1); + return mainLen; + } + + mainDist = 0; /* for GCC */ + if (mainLen >= 2) + { + mainDist = matches[numPairs - 1]; + while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1) + { + if (!ChangePair(matches[numPairs - 3], mainDist)) + break; + numPairs -= 2; + mainLen = matches[numPairs - 2]; + mainDist = matches[numPairs - 1]; + } + if (mainLen == 2 && mainDist >= 0x80) + mainLen = 1; + } + + if (repLen >= 2 && + ((repLen + 1 >= mainLen) || (repLen + 2 >= mainLen && mainDist >= (1 << 9)) || + (repLen + 3 >= mainLen && mainDist >= (1 << 15)))) + { + *backRes = repIndex; + MovePos(p, repLen - 1); + return repLen; + } + + if (mainLen < 2 || numAvail <= 2) + return 1; + + p->longestMatchLength = ReadMatchDistances(p, &p->numPairs); + if (p->longestMatchLength >= 2) + { + uint32_t newDistance = matches[p->numPairs - 1]; + if ((p->longestMatchLength >= mainLen && newDistance < mainDist) || + (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) || + (p->longestMatchLength > mainLen + 1) || + (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && + ChangePair(newDistance, mainDist))) + return 1; + } + + data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; + for (i = 0; i < LZMA_NUM_REPS; i++) + { + uint32_t len, limit; + const uint8_t *data2 = data - (p->reps[i] + 1); + if (data[0] != data2[0] || data[1] != data2[1]) + continue; + limit = mainLen - 1; + for (len = 2; len < limit && data[len] == data2[len]; len++) + ; + if (len >= limit) + return 1; + } + *backRes = mainDist + LZMA_NUM_REPS; + MovePos(p, mainLen - 2); + return mainLen; +} + +static void WriteEndMarker(CLzmaEnc *p, uint32_t posState) +{ + uint32_t len; + RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1); + RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0); + p->state = kMatchNextStates[p->state]; + len = LZMA_MATCH_LEN_MIN; + LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, + p->ProbPrices); + RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, + (1 << kNumPosSlotBits) - 1); + RangeEnc_EncodeDirectBits(&p->rc, (((uint32_t)1 << 30) - 1) >> kNumAlignBits, + 30 - kNumAlignBits); + RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask); +} + +static SRes CheckErrors(CLzmaEnc *p) +{ + if (p->result != SZ_OK) + return p->result; + if (p->rc.res != SZ_OK) + p->result = SZ_ERROR_WRITE; + if (p->matchFinderBase.result != SZ_OK) + p->result = SZ_ERROR_READ; + if (p->result != SZ_OK) + p->finished = True; + return p->result; +} + +static SRes Flush(CLzmaEnc *p, uint32_t nowPos) +{ + /* ReleaseMFStream(); */ + p->finished = True; + if (p->writeEndMark) + WriteEndMarker(p, nowPos & p->pbMask); + RangeEnc_FlushData(&p->rc); + RangeEnc_FlushStream(&p->rc); + return CheckErrors(p); +} + +static void FillAlignPrices(CLzmaEnc *p) +{ + uint32_t i; + for (i = 0; i < kAlignTableSize; i++) + p->alignPrices[i] = + RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices); + p->alignPriceCount = 0; +} + +static void FillDistancesPrices(CLzmaEnc *p) +{ + uint32_t tempPrices[kNumFullDistances]; + uint32_t i, lenToPosState; + for (i = kStartPosModelIndex; i < kNumFullDistances; i++) + { + uint32_t posSlot = GetPosSlot1(i); + uint32_t footerBits = ((posSlot >> 1) - 1); + uint32_t base = ((2 | (posSlot & 1)) << footerBits); + tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, + i - base, p->ProbPrices); + } + + for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++) + { + uint32_t posSlot; + const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState]; + uint32_t *posSlotPrices = p->posSlotPrices[lenToPosState]; + for (posSlot = 0; posSlot < p->distTableSize; posSlot++) + posSlotPrices[posSlot] = + RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices); + for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++) + posSlotPrices[posSlot] += + ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits); + + { + uint32_t *distancesPrices = p->distancesPrices[lenToPosState]; + uint32_t i; + for (i = 0; i < kStartPosModelIndex; i++) + distancesPrices[i] = posSlotPrices[i]; + for (; i < kNumFullDistances; i++) + distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i]; + } + } + p->matchPriceCount = 0; +} + +void LzmaEnc_Construct(CLzmaEnc *p) +{ + RangeEnc_Construct(&p->rc); + MatchFinder_Construct(&p->matchFinderBase); +#ifdef COMPRESS_MF_MT + MatchFinderMt_Construct(&p->matchFinderMt); + p->matchFinderMt.MatchFinder = &p->matchFinderBase; +#endif + + { + CLzmaEncProps props; + LzmaEncProps_Init(&props); + LzmaEnc_SetProps(p, &props); + } + +#ifndef LZMA_LOG_BSR + LzmaEnc_FastPosInit(p->g_FastPos); +#endif + + LzmaEnc_InitPriceTables(p->ProbPrices); + p->litProbs = 0; + p->saveState.litProbs = 0; +} + +CLzmaEncHandle LzmaEnc_Create() +{ + void *p; + p = malloc(sizeof(CLzmaEnc)); + if (p != 0) + LzmaEnc_Construct((CLzmaEnc *)p); + return p; +} + +void LzmaEnc_FreeLits(CLzmaEnc *p) +{ + free(p->litProbs); + free(p->saveState.litProbs); + p->litProbs = 0; + p->saveState.litProbs = 0; +} + +void LzmaEnc_Destruct(CLzmaEnc *p) +{ +#ifdef COMPRESS_MF_MT + MatchFinderMt_Destruct(&p->matchFinderMt, allocBig); +#endif + MatchFinder_Free(&p->matchFinderBase); + LzmaEnc_FreeLits(p); + RangeEnc_Free(&p->rc); +} + +void LzmaEnc_Destroy(CLzmaEncHandle p) +{ + LzmaEnc_Destruct((CLzmaEnc *)p); + free(p); +} + +static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, uint32_t maxPackSize, + uint32_t maxUnpackSize) +{ + uint32_t nowPos32, startPos32; + if (p->inStream != 0) + { + p->matchFinderBase.stream = p->inStream; + p->matchFinder.Init(p->matchFinderObj); + p->inStream = 0; + } + + if (p->finished) + return p->result; + RINOK(CheckErrors(p)); + + nowPos32 = (uint32_t)p->nowPos64; + startPos32 = nowPos32; + + if (p->nowPos64 == 0) + { + uint32_t numPairs; + uint8_t curByte; + if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) + return Flush(p, nowPos32); + ReadMatchDistances(p, &numPairs); + RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0); + p->state = kLiteralNextStates[p->state]; + curByte = p->matchFinder.GetIndexByte(p->matchFinderObj, 0 - p->additionalOffset); + LitEnc_Encode(&p->rc, p->litProbs, curByte); + p->additionalOffset--; + nowPos32++; + } + + if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0) + for (;;) + { + uint32_t pos, len, posState; + + if (p->fastMode) + len = GetOptimumFast(p, &pos); + else + len = GetOptimum(p, nowPos32, &pos); + +#ifdef SHOW_STAT2 + printf("\n pos = %4X, len = %d pos = %d", nowPos32, len, pos); +#endif + + posState = nowPos32 & p->pbMask; + if (len == 1 && pos == (uint32_t) - 1) + { + uint8_t curByte; + CLzmaProb *probs; + const uint8_t *data; + + RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0); + data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - + p->additionalOffset; + curByte = *data; + probs = LIT_PROBS(nowPos32, *(data - 1)); + if (IsCharState(p->state)) + LitEnc_Encode(&p->rc, probs, curByte); + else + LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1)); + p->state = kLiteralNextStates[p->state]; + } + else + { + RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1); + if (pos < LZMA_NUM_REPS) + { + RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1); + if (pos == 0) + { + RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0); + RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], + ((len == 1) ? 0 : 1)); + } + else + { + uint32_t distance = p->reps[pos]; + RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1); + if (pos == 1) + RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0); + else + { + RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1); + RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2); + if (pos == 3) + p->reps[3] = p->reps[2]; + p->reps[2] = p->reps[1]; + } + p->reps[1] = p->reps[0]; + p->reps[0] = distance; + } + if (len == 1) + p->state = kShortRepNextStates[p->state]; + else + { + LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, + posState, !p->fastMode, p->ProbPrices); + p->state = kRepNextStates[p->state]; + } + } + else + { + uint32_t posSlot; + RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0); + p->state = kMatchNextStates[p->state]; + LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, + !p->fastMode, p->ProbPrices); + pos -= LZMA_NUM_REPS; + GetPosSlot(pos, posSlot); + RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], + kNumPosSlotBits, posSlot); + + if (posSlot >= kStartPosModelIndex) + { + uint32_t footerBits = ((posSlot >> 1) - 1); + uint32_t base = ((2 | (posSlot & 1)) << footerBits); + uint32_t posReduced = pos - base; + + if (posSlot < kEndPosModelIndex) + RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, + footerBits, posReduced); + else + { + RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, + footerBits - kNumAlignBits); + RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, + posReduced & kAlignMask); + p->alignPriceCount++; + } + } + p->reps[3] = p->reps[2]; + p->reps[2] = p->reps[1]; + p->reps[1] = p->reps[0]; + p->reps[0] = pos; + p->matchPriceCount++; + } + } + p->additionalOffset -= len; + nowPos32 += len; + if (p->additionalOffset == 0) + { + uint32_t processed; + if (!p->fastMode) + { + if (p->matchPriceCount >= (1 << 7)) + FillDistancesPrices(p); + if (p->alignPriceCount >= kAlignTableSize) + FillAlignPrices(p); + } + if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) + break; + processed = nowPos32 - startPos32; + if (useLimits) + { + if (processed + kNumOpts + 300 >= maxUnpackSize || + RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize) + break; + } + else if (processed >= (1 << 15)) + { + p->nowPos64 += nowPos32 - startPos32; + return CheckErrors(p); + } + } + } + p->nowPos64 += nowPos32 - startPos32; + return Flush(p, nowPos32); +} + +#define kBigHashDicLimit ((uint32_t)1 << 24) + +static SRes LzmaEnc_Alloc(CLzmaEnc *p, uint32_t keepWindowSize) +{ + uint32_t beforeSize = kNumOpts; + Bool btMode; + if (!RangeEnc_Alloc(&p->rc)) + return SZ_ERROR_MEM; + btMode = (p->matchFinderBase.btMode != 0); +#ifdef COMPRESS_MF_MT + p->mtMode = (p->multiThread && !p->fastMode && btMode); +#endif + + { + unsigned lclp = p->lc + p->lp; + if (p->litProbs == 0 || p->saveState.litProbs == 0 || p->lclp != lclp) + { + LzmaEnc_FreeLits(p); + p->litProbs = (CLzmaProb *)malloc((0x300 << lclp) * sizeof(CLzmaProb)); + p->saveState.litProbs = (CLzmaProb *)malloc((0x300 << lclp) * sizeof(CLzmaProb)); + if (p->litProbs == 0 || p->saveState.litProbs == 0) + { + LzmaEnc_FreeLits(p); + return SZ_ERROR_MEM; + } + p->lclp = lclp; + } + } + + p->matchFinderBase.bigHash = (p->dictSize > kBigHashDicLimit); + + if (beforeSize + p->dictSize < keepWindowSize) + beforeSize = keepWindowSize - p->dictSize; + +#ifdef COMPRESS_MF_MT + if (p->mtMode) + { + RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, + LZMA_MATCH_LEN_MAX)); + p->matchFinderObj = &p->matchFinderMt; + MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder); + } + else +#endif + { + if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, + LZMA_MATCH_LEN_MAX)) + return SZ_ERROR_MEM; + p->matchFinderObj = &p->matchFinderBase; + MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder); + } + return SZ_OK; +} + +void LzmaEnc_Init(CLzmaEnc *p) +{ + uint32_t i; + p->state = 0; + for (i = 0; i < LZMA_NUM_REPS; i++) + p->reps[i] = 0; + + RangeEnc_Init(&p->rc); + + for (i = 0; i < kNumStates; i++) + { + uint32_t j; + for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++) + { + p->isMatch[i][j] = kProbInitValue; + p->isRep0Long[i][j] = kProbInitValue; + } + p->isRep[i] = kProbInitValue; + p->isRepG0[i] = kProbInitValue; + p->isRepG1[i] = kProbInitValue; + p->isRepG2[i] = kProbInitValue; + } + + { + uint32_t num = 0x300 << (p->lp + p->lc); + for (i = 0; i < num; i++) + p->litProbs[i] = kProbInitValue; + } + + { + for (i = 0; i < kNumLenToPosStates; i++) + { + CLzmaProb *probs = p->posSlotEncoder[i]; + uint32_t j; + for (j = 0; j < (1 << kNumPosSlotBits); j++) + probs[j] = kProbInitValue; + } + } + { + for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++) + p->posEncoders[i] = kProbInitValue; + } + + LenEnc_Init(&p->lenEnc.p); + LenEnc_Init(&p->repLenEnc.p); + + for (i = 0; i < (1 << kNumAlignBits); i++) + p->posAlignEncoder[i] = kProbInitValue; + + p->optimumEndIndex = 0; + p->optimumCurrentIndex = 0; + p->additionalOffset = 0; + + p->pbMask = (1 << p->pb) - 1; + p->lpMask = (1 << p->lp) - 1; +} + +void LzmaEnc_InitPrices(CLzmaEnc *p) +{ + if (!p->fastMode) + { + FillDistancesPrices(p); + FillAlignPrices(p); + } + + p->lenEnc.tableSize = p->repLenEnc.tableSize = p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN; + LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices); + LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices); +} + +static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, uint32_t keepWindowSize) +{ + uint32_t i; + for (i = 0; i < (uint32_t)kDicLogSizeMaxCompress; i++) + if (p->dictSize <= ((uint32_t)1 << i)) + break; + p->distTableSize = i * 2; + + p->finished = False; + p->result = SZ_OK; + RINOK(LzmaEnc_Alloc(p, keepWindowSize)); + LzmaEnc_Init(p); + LzmaEnc_InitPrices(p); + p->nowPos64 = 0; + return SZ_OK; +} + +static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqInStream *inStream, ISeqOutStream *outStream) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + p->inStream = inStream; + p->rc.outStream = outStream; + return LzmaEnc_AllocAndInit(p, 0); +} + +SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp, ISeqInStream *inStream, uint32_t keepWindowSize) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + p->inStream = inStream; + return LzmaEnc_AllocAndInit(p, keepWindowSize); +} + +static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const uint8_t *src, size_t srcLen) +{ + p->seqBufInStream.funcTable.Read = MyRead; + p->seqBufInStream.data = src; + p->seqBufInStream.rem = srcLen; +} + +SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const uint8_t *src, size_t srcLen, + uint32_t keepWindowSize) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + LzmaEnc_SetInputBuf(p, src, srcLen); + p->inStream = &p->seqBufInStream.funcTable; + return LzmaEnc_AllocAndInit(p, keepWindowSize); +} + +void LzmaEnc_Finish(CLzmaEncHandle pp) +{ +#ifdef COMPRESS_MF_MT + CLzmaEnc *p = (CLzmaEnc *)pp; + if (p->mtMode) + MatchFinderMt_ReleaseStream(&p->matchFinderMt); +#else + pp = pp; +#endif +} + +typedef struct _CSeqOutStreamBuf +{ + ISeqOutStream funcTable; + uint8_t *data; + size_t rem; + Bool overflow; +} CSeqOutStreamBuf; + +static size_t MyWrite(void *pp, const void *data, size_t size) +{ + CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp; + if (p->rem < size) + { + size = p->rem; + p->overflow = True; + } + memcpy(p->data, data, size); + p->rem -= size; + p->data += size; + return size; +} + +uint32_t LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp) +{ + const CLzmaEnc *p = (CLzmaEnc *)pp; + return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); +} + +const uint8_t *LzmaEnc_GetCurBuf(CLzmaEncHandle pp) +{ + const CLzmaEnc *p = (CLzmaEnc *)pp; + return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset; +} + +SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit, uint8_t *dest, size_t *destLen, + uint32_t desiredPackSize, uint32_t *unpackSize) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + uint64_t nowPos64; + SRes res; + CSeqOutStreamBuf outStream; + + outStream.funcTable.Write = MyWrite; + outStream.data = dest; + outStream.rem = *destLen; + outStream.overflow = False; + + p->writeEndMark = False; + p->finished = False; + p->result = SZ_OK; + + if (reInit) + LzmaEnc_Init(p); + LzmaEnc_InitPrices(p); + nowPos64 = p->nowPos64; + RangeEnc_Init(&p->rc); + p->rc.outStream = &outStream.funcTable; + + res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize); + + *unpackSize = (uint32_t)(p->nowPos64 - nowPos64); + *destLen -= outStream.rem; + if (outStream.overflow) + return SZ_ERROR_OUTPUT_EOF; + + return res; +} + +SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, + ICompressProgress *progress) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + SRes res = SZ_OK; + +#ifdef COMPRESS_MF_MT + Byte allocaDummy[0x300]; + int i = 0; + for (i = 0; i < 16; i++) + allocaDummy[i] = (Byte)i; +#endif + + RINOK(LzmaEnc_Prepare(pp, inStream, outStream)); + + for (;;) + { + res = LzmaEnc_CodeOneBlock(p, False, 0, 0); + if (res != SZ_OK || p->finished != 0) + break; + if (progress != 0) + { + res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc)); + if (res != SZ_OK) + { + res = SZ_ERROR_PROGRESS; + break; + } + } + } + LzmaEnc_Finish(pp); + return res; +} + +SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, uint8_t *props, size_t *size) +{ + CLzmaEnc *p = (CLzmaEnc *)pp; + int i; + uint32_t dictSize = p->dictSize; + if (*size < LZMA_PROPS_SIZE) + return SZ_ERROR_PARAM; + *size = LZMA_PROPS_SIZE; + props[0] = (uint8_t)((p->pb * 5 + p->lp) * 9 + p->lc); + + for (i = 11; i <= 30; i++) + { + if (dictSize <= ((uint32_t)2 << i)) + { + dictSize = (2 << i); + break; + } + if (dictSize <= ((uint32_t)3 << i)) + { + dictSize = (3 << i); + break; + } + } + + for (i = 0; i < 4; i++) + props[1 + i] = (uint8_t)(dictSize >> (8 * i)); + return SZ_OK; +} + +SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, uint8_t *dest, size_t *destLen, const uint8_t *src, + size_t srcLen, int writeEndMark, ICompressProgress *progress) +{ + SRes res; + CLzmaEnc *p = (CLzmaEnc *)pp; + + CSeqOutStreamBuf outStream; + + LzmaEnc_SetInputBuf(p, src, srcLen); + + outStream.funcTable.Write = MyWrite; + outStream.data = dest; + outStream.rem = *destLen; + outStream.overflow = False; + + p->writeEndMark = writeEndMark; + res = LzmaEnc_Encode(pp, &outStream.funcTable, &p->seqBufInStream.funcTable, progress); + + *destLen -= outStream.rem; + if (outStream.overflow) + return SZ_ERROR_OUTPUT_EOF; + return res; +} + +SRes LzmaEncode(uint8_t *dest, size_t *destLen, const uint8_t *src, size_t srcLen, + const CLzmaEncProps *props, uint8_t *propsEncoded, size_t *propsSize, + int writeEndMark, ICompressProgress *progress) +{ + CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(); + SRes res; + if (p == 0) + return SZ_ERROR_MEM; + + res = LzmaEnc_SetProps(p, props); + if (res == SZ_OK) + { + res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize); + if (res == SZ_OK) + res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen, writeEndMark, progress); + } + + LzmaEnc_Destroy(p); + return res; +} diff --git a/depends/lzma/pavlov/LzmaEnc.h b/depends/lzma/pavlov/LzmaEnc.h new file mode 100755 index 00000000..961436e4 --- /dev/null +++ b/depends/lzma/pavlov/LzmaEnc.h @@ -0,0 +1,71 @@ +/* LzmaEnc.h -- LZMA Encoder +2008-10-04 : Igor Pavlov : Public domain */ + +#ifndef __LZMAENC_H +#define __LZMAENC_H + +#include "Types.h" + +#define LZMA_PROPS_SIZE 5 + +typedef struct _CLzmaEncProps +{ + int level; /* 0 <= level <= 9 */ + uint32_t dictSize; /* (1 << 12) <= dictSize <= (1 << 27) for 32-bit version + (1 << 12) <= dictSize <= (1 << 30) for 64-bit version + default = (1 << 24) */ + int lc; /* 0 <= lc <= 8, default = 3 */ + int lp; /* 0 <= lp <= 4, default = 0 */ + int pb; /* 0 <= pb <= 4, default = 2 */ + int algo; /* 0 - fast, 1 - normal, default = 1 */ + int fb; /* 5 <= fb <= 273, default = 32 */ + int btMode; /* 0 - hashChain Mode, 1 - binTree mode - normal, default = 1 */ + int numHashBytes; /* 2, 3 or 4, default = 4 */ + uint32_t mc; /* 1 <= mc <= (1 << 30), default = 32 */ + unsigned writeEndMark; /* 0 - do not write EOPM, 1 - write EOPM, default = 0 */ + int numThreads; /* 1 or 2, default = 2 */ +} CLzmaEncProps; + +void LzmaEncProps_Init(CLzmaEncProps *p); +void LzmaEncProps_Normalize(CLzmaEncProps *p); +uint32_t LzmaEncProps_GetDictSize(const CLzmaEncProps *props2); + +/* ---------- CLzmaEncHandle Interface ---------- */ + +/* LzmaEnc_* functions can return the following exit codes: +Returns: + SZ_OK - OK + SZ_ERROR_MEM - Memory allocation error + SZ_ERROR_PARAM - Incorrect paramater in props + SZ_ERROR_WRITE - Write callback error. + SZ_ERROR_PROGRESS - some break from progress callback + SZ_ERROR_THREAD - errors in multithreading functions (only for Mt version) +*/ + +typedef void *CLzmaEncHandle; + +CLzmaEncHandle LzmaEnc_Create(); +void LzmaEnc_Destroy(CLzmaEncHandle p); +SRes LzmaEnc_SetProps(CLzmaEncHandle p, const CLzmaEncProps *props); +SRes LzmaEnc_WriteProperties(CLzmaEncHandle p, uint8_t *properties, size_t *size); +SRes LzmaEnc_Encode(CLzmaEncHandle p, ISeqOutStream *outStream, ISeqInStream *inStream, + ICompressProgress *progress); +SRes LzmaEnc_MemEncode(CLzmaEncHandle p, uint8_t *dest, size_t *destLen, const uint8_t *src, + size_t srcLen, int writeEndMark, ICompressProgress *progress); + +/* ---------- One Call Interface ---------- */ + +/* LzmaEncode +Return code: + SZ_OK - OK + SZ_ERROR_MEM - Memory allocation error + SZ_ERROR_PARAM - Incorrect paramater + SZ_ERROR_OUTPUT_EOF - output buffer overflow + SZ_ERROR_THREAD - errors in multithreading functions (only for Mt version) +*/ + +SRes LzmaEncode(uint8_t *dest, size_t *destLen, const uint8_t *src, size_t srcLen, + const CLzmaEncProps *props, uint8_t *propsEncoded, size_t *propsSize, + int writeEndMark, ICompressProgress *progress); + +#endif diff --git a/depends/lzma/pavlov/LzmaLib.c b/depends/lzma/pavlov/LzmaLib.c new file mode 100755 index 00000000..6759d69b --- /dev/null +++ b/depends/lzma/pavlov/LzmaLib.c @@ -0,0 +1,41 @@ +/* LzmaLib.c -- LZMA library wrapper +2008-08-05 +Igor Pavlov +Public domain */ + +#include "LzmaEnc.h" +#include "LzmaDec.h" +#include "LzmaLib.h" + +MY_STDAPI +LzmaCompress(unsigned char *dest, size_t *destLen, const unsigned char *src, size_t srcLen, + unsigned char *outProps, size_t *outPropsSize, + int level, /* 0 <= level <= 9, default = 5 */ + unsigned dictSize, /* use (1 << N) or (3 << N). 4 KB < dictSize <= 128 MB */ + int lc, /* 0 <= lc <= 8, default = 3 */ + int lp, /* 0 <= lp <= 4, default = 0 */ + int pb, /* 0 <= pb <= 4, default = 2 */ + int fb, /* 5 <= fb <= 273, default = 32 */ + int numThreads /* 1 or 2, default = 2 */ + ) +{ + CLzmaEncProps props; + LzmaEncProps_Init(&props); + props.level = level; + props.dictSize = dictSize; + props.lc = lc; + props.lp = lp; + props.pb = pb; + props.fb = fb; + props.numThreads = numThreads; + + return LzmaEncode(dest, destLen, src, srcLen, &props, outProps, outPropsSize, 0, NULL); +} + +MY_STDAPI LzmaUncompress(unsigned char *dest, size_t *destLen, const unsigned char *src, + size_t *srcLen, const unsigned char *props, size_t propsSize) +{ + ELzmaStatus status; + return LzmaDecode(dest, destLen, src, srcLen, props, (unsigned)propsSize, LZMA_FINISH_ANY, + &status); +} diff --git a/depends/lzma/pavlov/LzmaLib.h b/depends/lzma/pavlov/LzmaLib.h new file mode 100755 index 00000000..804329d1 --- /dev/null +++ b/depends/lzma/pavlov/LzmaLib.h @@ -0,0 +1,137 @@ +/* LzmaLib.h -- LZMA library interface +2008-08-05 +Igor Pavlov +Public domain */ + +#ifndef __LZMALIB_H +#define __LZMALIB_H + +#include "Types.h" + +#ifdef __cplusplus +#define MY_EXTERN_C extern "C" +#else +#define MY_EXTERN_C extern +#endif + +#define MY_STDAPI MY_EXTERN_C int MY_STD_CALL + +#define LZMA_PROPS_SIZE 5 + +/* +RAM requirements for LZMA: + for compression: (dictSize * 11.5 + 6 MB) + state_size + for decompression: dictSize + state_size + state_size = (4 + (1.5 << (lc + lp))) KB + by default (lc=3, lp=0), state_size = 16 KB. + +LZMA properties (5 bytes) format + Offset Size Description + 0 1 lc, lp and pb in encoded form. + 1 4 dictSize (little endian). +*/ + +/* +LzmaCompress +------------ + +outPropsSize - + In: the pointer to the size of outProps buffer; *outPropsSize = LZMA_PROPS_SIZE = 5. + Out: the pointer to the size of written properties in outProps buffer; *outPropsSize = +LZMA_PROPS_SIZE = 5. + + LZMA Encoder will use defult values for any parameter, if it is + -1 for any from: level, loc, lp, pb, fb, numThreads + 0 for dictSize + +level - compression level: 0 <= level <= 9; + + level dictSize algo fb + 0: 16 KB 0 32 + 1: 64 KB 0 32 + 2: 256 KB 0 32 + 3: 1 MB 0 32 + 4: 4 MB 0 32 + 5: 16 MB 1 32 + 6: 32 MB 1 32 + 7+: 64 MB 1 64 + + The default value for "level" is 5. + + algo = 0 means fast method + algo = 1 means normal method + +dictSize - The dictionary size in bytes. The maximum value is + 128 MB = (1 << 27) bytes for 32-bit version + 1 GB = (1 << 30) bytes for 64-bit version + The default value is 16 MB = (1 << 24) bytes. + It's recommended to use the dictionary that is larger than 4 KB and + that can be calculated as (1 << N) or (3 << N) sizes. + +lc - The number of literal context bits (high bits of previous literal). + It can be in the range from 0 to 8. The default value is 3. + Sometimes lc=4 gives the gain for big files. + +lp - The number of literal pos bits (low bits of current position for literals). + It can be in the range from 0 to 4. The default value is 0. + The lp switch is intended for periodical data when the period is equal to 2^lp. + For example, for 32-bit (4 bytes) periodical data you can use lp=2. Often it's + better to set lc=0, if you change lp switch. + +pb - The number of pos bits (low bits of current position). + It can be in the range from 0 to 4. The default value is 2. + The pb switch is intended for periodical data when the period is equal 2^pb. + +fb - Word size (the number of fast bytes). + It can be in the range from 5 to 273. The default value is 32. + Usually, a big number gives a little bit better compression ratio and + slower compression process. + +numThreads - The number of thereads. 1 or 2. The default value is 2. + Fast mode (algo = 0) can use only 1 thread. + +Out: + destLen - processed output size +Returns: + SZ_OK - OK + SZ_ERROR_MEM - Memory allocation error + SZ_ERROR_PARAM - Incorrect paramater + SZ_ERROR_OUTPUT_EOF - output buffer overflow + SZ_ERROR_THREAD - errors in multithreading functions (only for Mt version) +*/ + +MY_STDAPI LzmaCompress(unsigned char *dest, size_t *destLen, const unsigned char *src, + size_t srcLen, unsigned char *outProps, + size_t *outPropsSize, /* *outPropsSize must be = 5 */ + int level, /* 0 <= level <= 9, default = 5 */ + unsigned dictSize, /* default = (1 << 24) */ + int lc, /* 0 <= lc <= 8, default = 3 */ + int lp, /* 0 <= lp <= 4, default = 0 */ + int pb, /* 0 <= pb <= 4, default = 2 */ + int fb, /* 5 <= fb <= 273, default = 32 */ + int numThreads /* 1 or 2, default = 2 */ + ); + +/* +LzmaUncompress +-------------- +In: + dest - output data + destLen - output data size + src - input data + srcLen - input data size +Out: + destLen - processed output size + srcLen - processed input size +Returns: + SZ_OK - OK + SZ_ERROR_DATA - Data error + SZ_ERROR_MEM - Memory allocation arror + SZ_ERROR_UNSUPPORTED - Unsupported properties + SZ_ERROR_INPUT_EOF - it needs more bytes in input buffer (src) +*/ + +MY_STDAPI LzmaUncompress(unsigned char *dest, size_t *destLen, const unsigned char *src, + size_t *srcLen, const unsigned char *props, size_t propsSize); + +#endif diff --git a/depends/lzma/pavlov/Types.h b/depends/lzma/pavlov/Types.h new file mode 100755 index 00000000..e75bcb4a --- /dev/null +++ b/depends/lzma/pavlov/Types.h @@ -0,0 +1,87 @@ +/* Types.h -- Basic types +2008-11-23 : Igor Pavlov : Public domain */ + +#pragma once + +#include +#include + +#ifdef _WIN32 +#include +#endif + +#define SZ_OK 0 + +#define SZ_ERROR_DATA 1 +#define SZ_ERROR_MEM 2 +#define SZ_ERROR_CRC 3 +#define SZ_ERROR_UNSUPPORTED 4 +#define SZ_ERROR_PARAM 5 +#define SZ_ERROR_INPUT_EOF 6 +#define SZ_ERROR_OUTPUT_EOF 7 +#define SZ_ERROR_READ 8 +#define SZ_ERROR_WRITE 9 +#define SZ_ERROR_PROGRESS 10 +#define SZ_ERROR_FAIL 11 +#define SZ_ERROR_THREAD 12 + +#define SZ_ERROR_ARCHIVE 16 +#define SZ_ERROR_NO_ARCHIVE 17 + +typedef int SRes; + +#ifndef RINOK +#define RINOK(x) \ + { \ + int __result__ = (x); \ + if (__result__ != 0) \ + return __result__; \ + } +#endif + +typedef int Bool; +#define True 1 +#define False 0 + +#ifdef _MSC_VER + +#if _MSC_VER >= 1300 +#define MY_NO_INLINE __declspec(noinline) +#else +#define MY_NO_INLINE +#endif + +#define MY_CDECL __cdecl +#define MY_STD_CALL __stdcall +#define MY_FAST_CALL MY_NO_INLINE __fastcall + +#else + +#define MY_CDECL +#define MY_STD_CALL +#define MY_FAST_CALL + +#endif + +/* The following interfaces use first parameter as pointer to structure */ + +typedef struct +{ + SRes (*Read)(void *p, void *buf, size_t *size); + /* if (input(*size) != 0 && output(*size) == 0) means end_of_stream. + (output(*size) < input(*size)) is allowed */ +} ISeqInStream; + +typedef struct +{ + size_t (*Write)(void *p, const void *buf, size_t size); + /* Returns: result - the number of actually written bytes. + (result < size) means error */ +} ISeqOutStream; + +typedef struct +{ + SRes (*Progress)(void *p, uint64_t inSize, uint64_t outSize); + /* Returns: result. (result != SZ_OK) means break. + Value (uint64_t)(int64_t)-1 for size means unknown value. */ +} ICompressProgress; diff --git a/depends/lzma/wrapper/common_internal.c b/depends/lzma/wrapper/common_internal.c new file mode 100644 index 00000000..c9213ef4 --- /dev/null +++ b/depends/lzma/wrapper/common_internal.c @@ -0,0 +1,46 @@ +/* + * 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. + */ + +#include "common_internal.h" + +static void *elzmaAlloc(void *p, size_t size) +{ + struct elzma_alloc_struct *as = (struct elzma_alloc_struct *)p; + if (as->clientMallocFunc) + { + return as->clientMallocFunc(as->clientMallocContext, size); + } + return malloc(size); +} + +static void elzmaFree(void *p, void *address) +{ + struct elzma_alloc_struct *as = (struct elzma_alloc_struct *)p; + if (as->clientFreeFunc) + { + as->clientFreeFunc(as->clientMallocContext, address); + } + else + { + free(address); + } +} + +void init_alloc_struct(struct elzma_alloc_struct *as, elzma_malloc clientMallocFunc, + void *clientMallocContext, elzma_free clientFreeFunc, + void *clientFreeContext) +{ + as->Alloc = elzmaAlloc; + as->Free = elzmaFree; + as->clientMallocFunc = clientMallocFunc; + as->clientMallocContext = clientMallocContext; + as->clientFreeFunc = clientFreeFunc; + as->clientFreeContext = clientFreeContext; +} diff --git a/depends/lzma/wrapper/common_internal.h b/depends/lzma/wrapper/common_internal.h new file mode 100644 index 00000000..2c46fadf --- /dev/null +++ b/depends/lzma/wrapper/common_internal.h @@ -0,0 +1,60 @@ +#ifndef __ELZMA_COMMON_INTERNAL_H__ +#define __ELZMA_COMMON_INTERNAL_H__ + +#include "common.h" + +/** a structure which may be cast and passed into Igor's allocate + * routines */ +struct elzma_alloc_struct +{ + void *(*Alloc)(void *p, size_t size); + void (*Free)(void *p, void *address); /* address can be 0 */ + + elzma_malloc clientMallocFunc; + void *clientMallocContext; + + elzma_free clientFreeFunc; + void *clientFreeContext; +}; + +/* initialize an allocation structure, may be called safely multiple + * times */ +void init_alloc_struct(struct elzma_alloc_struct *allocStruct, elzma_malloc clientMallocFunc, + void *clientMallocContext, elzma_free clientFreeFunc, + void *clientFreeContext); + +/** superset representation of a compressed file header */ +struct elzma_file_header +{ + unsigned char pb; + unsigned char lp; + unsigned char lc; + unsigned char isStreamed; + long long unsigned int uncompressedSize; + unsigned int dictSize; +}; + +/** superset representation of a compressed file footer */ +struct elzma_file_footer +{ + unsigned int crc32; + long long unsigned int uncompressedSize; +}; + +/** a structure which encapsulates information about the particular + * file header and footer in use (lzip vs lzma vs (eventually) xz. + * The intention of this structure is to simplify compression and + * decompression logic by abstracting the file format details a bit. */ +struct elzma_format_handler +{ + unsigned int header_size; + void (*init_header)(struct elzma_file_header *hdr); + int (*parse_header)(const unsigned char *hdrBuf, struct elzma_file_header *hdr); + int (*serialize_header)(unsigned char *hdrBuf, const struct elzma_file_header *hdr); + + unsigned int footer_size; + int (*serialize_footer)(struct elzma_file_footer *ftr, unsigned char *ftrBuf); + int (*parse_footer)(const unsigned char *ftrBuf, struct elzma_file_footer *ftr); +}; + +#endif diff --git a/depends/lzma/wrapper/compress.c b/depends/lzma/wrapper/compress.c new file mode 100644 index 00000000..38ca0a68 --- /dev/null +++ b/depends/lzma/wrapper/compress.c @@ -0,0 +1,297 @@ +/* + * 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. + */ + +#include "compress.h" +#include "lzma_header.h" +#include "lzip_header.h" +#include "common_internal.h" + +#include "pavlov/Types.h" +#include "pavlov/LzmaEnc.h" +#include "pavlov/7zCrc.h" + +#include + +struct _elzma_compress_handle +{ + CLzmaEncProps props; + CLzmaEncHandle encHand; + unsigned long long uncompressedSize; + elzma_file_format format; + struct elzma_alloc_struct allocStruct; + struct elzma_format_handler formatHandler; +}; + +elzma_compress_handle elzma_compress_alloc() +{ + elzma_compress_handle hand = malloc(sizeof(struct _elzma_compress_handle)); + memset((void *)hand, 0, sizeof(struct _elzma_compress_handle)); + + /* "reasonable" defaults for props */ + LzmaEncProps_Init(&(hand->props)); + hand->props.lc = 3; + hand->props.lp = 0; + hand->props.pb = 2; + hand->props.level = 5; + hand->props.algo = 1; + hand->props.fb = 32; + hand->props.dictSize = 1 << 24; + hand->props.btMode = 1; + hand->props.numHashBytes = 4; + hand->props.mc = 32; + hand->props.numThreads = 1; + hand->props.writeEndMark = 1; + + init_alloc_struct(&(hand->allocStruct), NULL, NULL, NULL, NULL); + + /* default format is LZMA-Alone */ + initializeLZMAFormatHandler(&(hand->formatHandler)); + + return hand; +} + +void elzma_compress_free(elzma_compress_handle *hand) +{ + if (hand && *hand) + { + if ((*hand)->encHand) + { + LzmaEnc_Destroy((*hand)->encHand); + } + } + *hand = NULL; +} + +int 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) +{ + /* XXX: validate arguments are in valid ranges */ + + hand->props.lc = lc; + hand->props.lp = lp; + hand->props.pb = pb; + hand->props.level = level; + hand->props.dictSize = dictionarySize; + hand->uncompressedSize = uncompressedSize; + hand->format = format; + + /* default of LZMA-Alone is set at alloc time, and there are only + * two possible formats */ + if (format == ELZMA_lzip) + { + initializeLZIPFormatHandler(&(hand->formatHandler)); + } + + return ELZMA_E_OK; +} + +/* use Igor's stream hooks for compression. */ +struct elzmaInStream +{ + SRes (*ReadPtr)(void *p, void *buf, size_t *size); + elzma_read_callback inputStream; + void *inputContext; + unsigned int crc32; + unsigned int crc32a; + unsigned int crc32b; + unsigned int crc32c; + int calculateCRC; +}; + +static SRes elzmaReadFunc(void *p, void *buf, size_t *size) +{ + int rv; + struct elzmaInStream *is = (struct elzmaInStream *)p; + rv = is->inputStream(is->inputContext, buf, size); + if (rv == 0 && *size > 0 && is->calculateCRC) + { + is->crc32 = CrcUpdate(is->crc32, buf, *size); + } + return rv; +} + +struct elzmaOutStream +{ + size_t (*WritePtr)(void *p, const void *buf, size_t size); + elzma_write_callback outputStream; + void *outputContext; +}; + +static size_t elzmaWriteFunc(void *p, const void *buf, size_t size) +{ + struct elzmaOutStream *os = (struct elzmaOutStream *)p; + return os->outputStream(os->outputContext, buf, size); +} + +/* use Igor's stream hooks for compression. */ +struct elzmaProgressStruct +{ + SRes (*Progress)(void *p, uint64_t inSize, uint64_t outSize); + long long unsigned int uncompressedSize; + elzma_progress_callback progressCallback; + void *progressContext; +}; + +#include +static SRes elzmaProgress(void *p, uint64_t inSize, uint64_t outSize) +{ + struct elzmaProgressStruct *ps = (struct elzmaProgressStruct *)p; + if (ps->progressCallback) + { + ps->progressCallback(ps->progressContext, inSize, ps->uncompressedSize); + } + return SZ_OK; +} + +void elzma_compress_set_allocation_callbacks(elzma_compress_handle hand, + elzma_malloc mallocFunc, void *mallocFuncContext, + elzma_free freeFunc, void *freeFuncContext) +{ + if (hand) + { + init_alloc_struct(&(hand->allocStruct), mallocFunc, mallocFuncContext, freeFunc, + freeFuncContext); + } +} + +int 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) +{ + struct elzmaInStream inStreamStruct; + struct elzmaOutStream outStreamStruct; + struct elzmaProgressStruct progressStruct; + SRes r; + + CrcGenerateTable(); + + if (hand == NULL || inputStream == NULL) + return ELZMA_E_BAD_PARAMS; + + /* initialize stream structrures */ + inStreamStruct.ReadPtr = elzmaReadFunc; + inStreamStruct.inputStream = inputStream; + inStreamStruct.inputContext = inputContext; + inStreamStruct.crc32 = CRC_INIT_VAL; + inStreamStruct.calculateCRC = (hand->formatHandler.serialize_footer != NULL); + + outStreamStruct.WritePtr = elzmaWriteFunc; + outStreamStruct.outputStream = outputStream; + outStreamStruct.outputContext = outputContext; + + progressStruct.Progress = elzmaProgress; + progressStruct.uncompressedSize = hand->uncompressedSize; + progressStruct.progressCallback = progressCallback; + progressStruct.progressContext = progressContext; + + /* create an encoding object */ + hand->encHand = LzmaEnc_Create(); + + if (hand->encHand == NULL) + { + return ELZMA_E_COMPRESS_ERROR; + } + + /* inintialize with compression parameters */ + if (SZ_OK != LzmaEnc_SetProps(hand->encHand, &(hand->props))) + { + return ELZMA_E_BAD_PARAMS; + } + + /* verify format is sane */ + if (ELZMA_lzma != hand->format && ELZMA_lzip != hand->format) + { + return ELZMA_E_UNSUPPORTED_FORMAT; + } + + /* now write the compression header header */ + { + unsigned char *hdr = + hand->allocStruct.Alloc(&(hand->allocStruct), hand->formatHandler.header_size); + + struct elzma_file_header h; + size_t wt; + + hand->formatHandler.init_header(&h); + h.pb = (unsigned char)hand->props.pb; + h.lp = (unsigned char)hand->props.lp; + h.lc = (unsigned char)hand->props.lc; + h.dictSize = hand->props.dictSize; + h.isStreamed = (unsigned char)(hand->uncompressedSize == 0); + h.uncompressedSize = hand->uncompressedSize; + + hand->formatHandler.serialize_header(hdr, &h); + + wt = outputStream(outputContext, (void *)hdr, hand->formatHandler.header_size); + + hand->allocStruct.Free(&(hand->allocStruct), hdr); + + if (wt != hand->formatHandler.header_size) + { + return ELZMA_E_OUTPUT_ERROR; + } + } + + /* begin LZMA encoding */ + /* XXX: expose encoding progress */ + r = LzmaEnc_Encode(hand->encHand, (ISeqOutStream *)&outStreamStruct, + (ISeqInStream *)&inStreamStruct, (ICompressProgress *)&progressStruct); + + if (r != SZ_OK) + return ELZMA_E_COMPRESS_ERROR; + + /* support a footer! (lzip) */ + if (hand->formatHandler.serialize_footer != NULL && hand->formatHandler.footer_size > 0) + { + size_t wt; + unsigned char *ftrBuf = + hand->allocStruct.Alloc(&(hand->allocStruct), hand->formatHandler.footer_size); + struct elzma_file_footer ftr; + ftr.crc32 = inStreamStruct.crc32 ^ 0xFFFFFFFF; + ftr.uncompressedSize = hand->uncompressedSize; + + hand->formatHandler.serialize_footer(&ftr, ftrBuf); + + wt = outputStream(outputContext, (void *)ftrBuf, hand->formatHandler.footer_size); + + hand->allocStruct.Free(&(hand->allocStruct), ftrBuf); + + if (wt != hand->formatHandler.footer_size) + { + return ELZMA_E_OUTPUT_ERROR; + } + } + + return ELZMA_E_OK; +} + +unsigned int elzma_get_dict_size(unsigned long long size) +{ + int i = 13; /* 16k dict is minimum */ + + /* now we'll find the closes power of two with a max at 16< * + * if the size is greater than 8m, we'll divide by two, all of this + * is based on a quick set of emperical tests on hopefully + * representative sample data */ + if (size > (1 << 23)) + size >>= 1; + + while (size >> i) + i++; + + if (i > 23) + return 1 << 23; + + /* now 1 << i is greater than size, let's return either 1< (size - (1 << (i - 1)))) ? i - 1 : i); +} diff --git a/depends/lzma/wrapper/decompress.c b/depends/lzma/wrapper/decompress.c new file mode 100644 index 00000000..65ff9119 --- /dev/null +++ b/depends/lzma/wrapper/decompress.c @@ -0,0 +1,263 @@ +/* + * 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. + */ + +#include "include/decompress.h" +#include "pavlov/LzmaDec.h" +#include "pavlov/7zCrc.h" +#include "common_internal.h" +#include "lzma_header.h" +#include "lzip_header.h" + +#include +#include + +#define ELZMA_DECOMPRESS_INPUT_BUFSIZE (1024 * 64) +#define ELZMA_DECOMPRESS_OUTPUT_BUFSIZE (1024 * 256) + +/** an opaque handle to an lzma decompressor */ +struct _elzma_decompress_handle +{ + char inbuf[ELZMA_DECOMPRESS_INPUT_BUFSIZE]; + char outbuf[ELZMA_DECOMPRESS_OUTPUT_BUFSIZE]; + struct elzma_alloc_struct allocStruct; +}; + +elzma_decompress_handle elzma_decompress_alloc() +{ + elzma_decompress_handle hand = malloc(sizeof(struct _elzma_decompress_handle)); + memset((void *)hand, 0, sizeof(struct _elzma_decompress_handle)); + init_alloc_struct(&(hand->allocStruct), NULL, NULL, NULL, NULL); + return hand; +} + +void elzma_decompress_set_allocation_callbacks(elzma_decompress_handle hand, + elzma_malloc mallocFunc, void *mallocFuncContext, + elzma_free freeFunc, void *freeFuncContext) +{ + if (hand) + { + init_alloc_struct(&(hand->allocStruct), mallocFunc, mallocFuncContext, freeFunc, + freeFuncContext); + } +} + +void elzma_decompress_free(elzma_decompress_handle *hand) +{ + if (*hand) + free(*hand); + *hand = NULL; +} + +int elzma_decompress_run(elzma_decompress_handle hand, elzma_read_callback inputStream, + void *inputContext, elzma_write_callback outputStream, + void *outputContext, elzma_file_format format) +{ + unsigned long long int totalRead = 0; /* total amount read from stream */ + unsigned int crc32 = CRC_INIT_VAL; /* running crc32 (lzip case) */ + CLzmaDec dec; + unsigned int errorCode = ELZMA_E_OK; + struct elzma_format_handler formatHandler; + struct elzma_file_header h; + struct elzma_file_footer f; + + /* switch between supported formats */ + if (format == ELZMA_lzma) + { + initializeLZMAFormatHandler(&formatHandler); + } + else if (format == ELZMA_lzip) + { + CrcGenerateTable(); + initializeLZIPFormatHandler(&formatHandler); + } + else + { + return ELZMA_E_BAD_PARAMS; + } + + /* initialize footer */ + f.crc32 = 0; + f.uncompressedSize = 0; + + /* initialize decoder memory */ + memset((void *)&dec, 0, sizeof(dec)); + LzmaDec_Init(&dec); + + /* decode the header. */ + { + unsigned char *hdr = + hand->allocStruct.Alloc(&(hand->allocStruct), formatHandler.header_size); + + size_t sz = formatHandler.header_size; + + formatHandler.init_header(&h); + + if (inputStream(inputContext, hdr, &sz) != 0 || sz != formatHandler.header_size) + { + hand->allocStruct.Free(&(hand->allocStruct), hdr); + return ELZMA_E_INPUT_ERROR; + } + + if (0 != formatHandler.parse_header(hdr, &h)) + { + hand->allocStruct.Free(&(hand->allocStruct), hdr); + return ELZMA_E_CORRUPT_HEADER; + } + + /* the LzmaDec_Allocate call requires 5 bytes which have + * compression properties encoded in them. In the case of + * lzip, the header format does not already contain what + * LzmaDec_Allocate expects, so we must craft it, silly */ + { + unsigned char propsBuf[13]; + const unsigned char *propsPtr = hdr; + + if (format == ELZMA_lzip) + { + struct elzma_format_handler lzmaHand; + initializeLZMAFormatHandler(&lzmaHand); + lzmaHand.serialize_header(propsBuf, &h); + propsPtr = propsBuf; + } + + /* now we're ready to allocate the decoder */ + LzmaDec_Allocate(&dec, propsPtr, 5); + } + + hand->allocStruct.Free(&(hand->allocStruct), hdr); + } + + /* perform the decoding */ + for (;;) + { + size_t dstLen = ELZMA_DECOMPRESS_OUTPUT_BUFSIZE; + size_t srcLen = ELZMA_DECOMPRESS_INPUT_BUFSIZE; + size_t amt = 0; + size_t bufOff = 0; + ELzmaStatus stat; + + if (0 != inputStream(inputContext, hand->inbuf, &srcLen)) + { + errorCode = ELZMA_E_INPUT_ERROR; + goto decompressEnd; + } + + /* handle the case where the input prematurely finishes */ + if (srcLen == 0) + { + errorCode = ELZMA_E_INSUFFICIENT_INPUT; + goto decompressEnd; + } + + amt = srcLen; + + /* handle the case where a single read buffer of compressed bytes + * will translate into multiple buffers of uncompressed bytes, + * with this inner loop */ + stat = LZMA_STATUS_NOT_SPECIFIED; + + while (bufOff < srcLen) + { + SRes r = LzmaDec_DecodeToBuf(&dec, (uint8_t *)hand->outbuf, &dstLen, + ((uint8_t *)hand->inbuf + bufOff), &amt, + LZMA_FINISH_ANY, &stat); + + /* XXX deal with result code more granularly*/ + if (r != SZ_OK) + { + errorCode = ELZMA_E_DECOMPRESS_ERROR; + goto decompressEnd; + } + + /* write what we've read */ + { + size_t wt; + + /* if decoding lzip, update our crc32 value */ + if (format == ELZMA_lzip && dstLen > 0) + { + crc32 = CrcUpdate(crc32, hand->outbuf, dstLen); + } + totalRead += dstLen; + + wt = outputStream(outputContext, hand->outbuf, dstLen); + if (wt != dstLen) + { + errorCode = ELZMA_E_OUTPUT_ERROR; + goto decompressEnd; + } + } + + /* do we have more data on the input buffer? */ + bufOff += amt; + assert(bufOff <= srcLen); + if (bufOff >= srcLen) + break; + amt = srcLen - bufOff; + + /* with lzip, we will have the footer left on the buffer! */ + if (stat == LZMA_STATUS_FINISHED_WITH_MARK) + { + break; + } + } + + /* now check status */ + if (stat == LZMA_STATUS_FINISHED_WITH_MARK) + { + /* read a footer if one is expected and + * present */ + if (formatHandler.footer_size > 0 && amt >= formatHandler.footer_size && + formatHandler.parse_footer != NULL) + { + formatHandler.parse_footer((unsigned char *)hand->inbuf + bufOff, &f); + } + + break; + } + /* for LZMA utils, we don't always have a finished mark */ + if (!h.isStreamed && totalRead >= h.uncompressedSize) + { + break; + } + } + + /* finish the calculated crc32 */ + crc32 ^= 0xFFFFFFFF; + + /* if we have a footer, check that the calculated crc32 matches + * the encoded crc32, and that the sizes match */ + if (formatHandler.footer_size) + { + if (f.crc32 != crc32) + { + errorCode = ELZMA_E_CRC32_MISMATCH; + } + else if (f.uncompressedSize != totalRead) + { + errorCode = ELZMA_E_SIZE_MISMATCH; + } + } + else if (!h.isStreamed) + { + /* if the format does not support a footer and has an uncompressed + * size in the header, let's compare that with how much we actually + * read */ + if (h.uncompressedSize != totalRead) + { + errorCode = ELZMA_E_SIZE_MISMATCH; + } + } + +decompressEnd: + LzmaDec_Free(&dec); + + return errorCode; +} diff --git a/depends/lzma/wrapper/lzip_header.c b/depends/lzma/wrapper/lzip_header.c new file mode 100644 index 00000000..39872813 --- /dev/null +++ b/depends/lzma/wrapper/lzip_header.c @@ -0,0 +1,96 @@ +#include "lzip_header.h" + +#include + +#define ELZMA_LZIP_HEADER_SIZE 6 +#define ELZMA_LZIP_FOOTER_SIZE 12 + +static void initLzipHeader(struct elzma_file_header *hdr) +{ + memset((void *)hdr, 0, sizeof(struct elzma_file_header)); +} + +static int parseLzipHeader(const unsigned char *hdrBuf, struct elzma_file_header *hdr) +{ + if (0 != strncmp("LZIP", (char *)hdrBuf, 4)) + return 1; + /* XXX: ignore version for now */ + hdr->pb = 2; + hdr->lp = 0; + hdr->lc = 3; + /* unknown at this point */ + hdr->isStreamed = 1; + hdr->uncompressedSize = 0; + hdr->dictSize = 1 << (hdrBuf[5] & 0x1F); + return 0; +} + +static int serializeLzipHeader(unsigned char *hdrBuf, const struct elzma_file_header *hdr) +{ + hdrBuf[0] = 'L'; + hdrBuf[1] = 'Z'; + hdrBuf[2] = 'I'; + hdrBuf[3] = 'P'; + hdrBuf[4] = 0; + { + int r = 0; + while ((hdr->dictSize >> r) != 0) + r++; + hdrBuf[5] = (unsigned char)(r - 1) & 0x1F; + } + return 0; +} + +static int serializeLzipFooter(struct elzma_file_footer *ftr, unsigned char *ftrBuf) +{ + unsigned int i = 0; + + /* first crc32 */ + for (i = 0; i < 4; i++) + { + *(ftrBuf++) = (unsigned char)(ftr->crc32 >> (i * 8)); + } + + /* next data size */ + for (i = 0; i < 8; i++) + { + *(ftrBuf++) = (unsigned char)(ftr->uncompressedSize >> (i * 8)); + } + + /* write version 0 files, omit member length for now*/ + + return 0; +} + +static int parseLzipFooter(const unsigned char *ftrBuf, struct elzma_file_footer *ftr) +{ + unsigned int i = 0; + ftr->crc32 = 0; + ftr->uncompressedSize = 0; + + /* first crc32 */ + for (i = 0; i < 4; i++) + { + ftr->crc32 += ((unsigned int)*(ftrBuf++) << (i * 8)); + } + + /* next data size */ + for (i = 0; i < 8; i++) + { + ftr->uncompressedSize += (unsigned long long)*(ftrBuf++) << (i * 8); + } + /* read version 0 files, omit member length for now*/ + + return 0; +} + +void initializeLZIPFormatHandler(struct elzma_format_handler *hand) +{ + hand->header_size = ELZMA_LZIP_HEADER_SIZE; + hand->init_header = initLzipHeader; + hand->parse_header = parseLzipHeader; + hand->serialize_header = serializeLzipHeader; + hand->footer_size = ELZMA_LZIP_FOOTER_SIZE; + hand->serialize_footer = serializeLzipFooter; + hand->parse_footer = parseLzipFooter; +} diff --git a/depends/lzma/wrapper/lzip_header.h b/depends/lzma/wrapper/lzip_header.h new file mode 100644 index 00000000..138afa60 --- /dev/null +++ b/depends/lzma/wrapper/lzip_header.h @@ -0,0 +1,11 @@ +#ifndef __EASYLZMA_LZIP_HEADER__ +#define __EASYLZMA_LZIP_HEADER__ + +#include "common_internal.h" + +/* lzip file format documented here: + * http://download.savannah.gnu.org/releases-noredirect/lzip/manual/ */ + +void initializeLZIPFormatHandler(struct elzma_format_handler *hand); + +#endif diff --git a/depends/lzma/wrapper/lzma_header.c b/depends/lzma/wrapper/lzma_header.c new file mode 100644 index 00000000..ab32549f --- /dev/null +++ b/depends/lzma/wrapper/lzma_header.c @@ -0,0 +1,134 @@ +/* + * 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. + */ + +/* XXX: clean this up, it's mostly lifted from pavel */ + +#include "lzma_header.h" + +#include +#include + +#define ELZMA_LZMA_HEADER_SIZE 13 +#define ELZMA_LZMA_PROPSBUF_SIZE 5 + +/**************** + Header parsing + ****************/ + +#ifndef UINT64_MAX +#define UINT64_MAX ((unsigned long long)-1) +#endif + +/* Parse the properties byte */ +static char lzmadec_header_properties(unsigned char *pb, unsigned char *lp, unsigned char *lc, + const unsigned char c) +{ + /* pb, lp and lc are encoded into a single byte. */ + if (c > (9 * 5 * 5)) + return -1; + *pb = c / (9 * 5); /* 0 <= pb <= 4 */ + *lp = (c % (9 * 5)) / 9; /* 0 <= lp <= 4 */ + *lc = c % 9; /* 0 <= lc <= 8 */ + + assert(*pb < 5 && *lp < 5 && *lc < 9); + return 0; +} + +/* Parse the dictionary size (4 bytes, little endian) */ +static char lzmadec_header_dictionary(unsigned int *size, const unsigned char *buffer) +{ + unsigned int i; + *size = 0; + for (i = 0; i < 4; i++) + *size += (unsigned int)(*buffer++) << (i * 8); + /* The dictionary size is limited to 256 MiB (checked from + * LZMA SDK 4.30) */ + if (*size > (1 << 28)) + return -1; + return 0; +} + +/* Parse the uncompressed size field (8 bytes, little endian) */ +static void lzmadec_header_uncompressed(unsigned long long *size, unsigned char *is_streamed, + const unsigned char *buffer) +{ + unsigned int i; + + /* Streamed files have all 64 bits set in the size field. + * We don't know the uncompressed size beforehand. */ + *is_streamed = 1; /* Assume streamed. */ + *size = 0; + for (i = 0; i < 8; i++) + { + *size += (unsigned long long)buffer[i] << (i * 8); + if (buffer[i] != 255) + *is_streamed = 0; + } + assert((*is_streamed == 1 && *size == UINT64_MAX) || + (*is_streamed == 0 && *size < UINT64_MAX)); +} + +static void initLzmaHeader(struct elzma_file_header *hdr) +{ + memset((void *)hdr, 0, sizeof(struct elzma_file_header)); +} + +static int parseLzmaHeader(const unsigned char *hdrBuf, struct elzma_file_header *hdr) +{ + if (lzmadec_header_properties(&(hdr->pb), &(hdr->lp), &(hdr->lc), *hdrBuf) || + lzmadec_header_dictionary(&(hdr->dictSize), hdrBuf + 1)) + { + return 1; + } + lzmadec_header_uncompressed(&(hdr->uncompressedSize), &(hdr->isStreamed), hdrBuf + 5); + + return 0; +} + +static int serializeLzmaHeader(unsigned char *hdrBuf, const struct elzma_file_header *hdr) +{ + unsigned int i; + + memset((void *)hdrBuf, 0, ELZMA_LZMA_HEADER_SIZE); + + /* encode lc, pb, and lp */ + *hdrBuf++ = hdr->lc + (hdr->pb * 45) + (hdr->lp * 45 * 9); + + /* encode dictionary size */ + for (i = 0; i < 4; i++) + { + *(hdrBuf++) = (unsigned char)(hdr->dictSize >> (i * 8)); + } + + /* encode uncompressed size */ + for (i = 0; i < 8; i++) + { + if (hdr->isStreamed) + { + *(hdrBuf++) = 0xff; + } + else + { + *(hdrBuf++) = (unsigned char)(hdr->uncompressedSize >> (i * 8)); + } + } + + return 0; +} + +void initializeLZMAFormatHandler(struct elzma_format_handler *hand) +{ + hand->header_size = ELZMA_LZMA_HEADER_SIZE; + hand->init_header = initLzmaHeader; + hand->parse_header = parseLzmaHeader; + hand->serialize_header = serializeLzmaHeader; + hand->footer_size = 0; + hand->serialize_footer = NULL; +} diff --git a/depends/lzma/wrapper/lzma_header.h b/depends/lzma/wrapper/lzma_header.h new file mode 100644 index 00000000..6a5d7a9c --- /dev/null +++ b/depends/lzma/wrapper/lzma_header.h @@ -0,0 +1,10 @@ +#ifndef __EASYLZMA_LZMA_HEADER__ +#define __EASYLZMA_LZMA_HEADER__ + +#include "common_internal.h" + +/* LZMA-Alone header format gleaned from reading Igor's code */ + +void initializeLZMAFormatHandler(struct elzma_format_handler *hand); + +#endif diff --git a/depends/lzma/wrapper/simple.c b/depends/lzma/wrapper/simple.c new file mode 100644 index 00000000..98d3c285 --- /dev/null +++ b/depends/lzma/wrapper/simple.c @@ -0,0 +1,139 @@ +/* + * 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.c - a wrapper around easylzma to compress/decompress to memory + */ + +#include "simple.h" + +#include +#include + +struct dataStream +{ + const unsigned char *inData; + size_t inLen; + + unsigned char *outData; + size_t outLen; +}; + +static int inputCallback(void *ctx, void *buf, size_t *size) +{ + size_t rd = 0; + struct dataStream *ds = (struct dataStream *)ctx; + assert(ds != NULL); + + rd = (ds->inLen < *size) ? ds->inLen : *size; + + if (rd > 0) + { + memcpy(buf, (void *)ds->inData, rd); + ds->inData += rd; + ds->inLen -= rd; + } + + *size = rd; + + return 0; +} + +static size_t outputCallback(void *ctx, const void *buf, size_t size) +{ + struct dataStream *ds = (struct dataStream *)ctx; + assert(ds != NULL); + + if (size > 0) + { + ds->outData = realloc(ds->outData, ds->outLen + size); + memcpy((void *)(ds->outData + ds->outLen), buf, size); + ds->outLen += size; + } + + return size; +} + +int simpleCompress(elzma_file_format format, const unsigned char *inData, size_t inLen, + unsigned char **outData, size_t *outLen) +{ + int rc; + elzma_compress_handle hand; + + /* allocate compression handle */ + hand = elzma_compress_alloc(); + assert(hand != NULL); + + rc = elzma_compress_config(hand, ELZMA_LC_DEFAULT, ELZMA_LP_DEFAULT, ELZMA_PB_DEFAULT, 5, + (1 << 20) /* 1mb */, format, inLen); + + if (rc != ELZMA_E_OK) + { + elzma_compress_free(&hand); + return rc; + } + + /* now run the compression */ + { + struct dataStream ds; + ds.inData = inData; + ds.inLen = inLen; + ds.outData = NULL; + ds.outLen = 0; + + rc = elzma_compress_run(hand, inputCallback, (void *)&ds, outputCallback, (void *)&ds, + NULL, NULL); + + if (rc != ELZMA_E_OK) + { + if (ds.outData != NULL) + free(ds.outData); + elzma_compress_free(&hand); + return rc; + } + + *outData = ds.outData; + *outLen = ds.outLen; + } + + return rc; +} + +int simpleDecompress(elzma_file_format format, const unsigned char *inData, size_t inLen, + unsigned char **outData, size_t *outLen) +{ + int rc; + elzma_decompress_handle hand; + + hand = elzma_decompress_alloc(); + + /* now run the compression */ + { + struct dataStream ds; + ds.inData = inData; + ds.inLen = inLen; + ds.outData = NULL; + ds.outLen = 0; + + rc = elzma_decompress_run(hand, inputCallback, (void *)&ds, outputCallback, (void *)&ds, + format); + + if (rc != ELZMA_E_OK) + { + if (ds.outData != NULL) + free(ds.outData); + elzma_decompress_free(&hand); + return rc; + } + + *outData = ds.outData; + *outLen = ds.outLen; + } + + return rc; +} -- cgit v1.2.3