diff options
author | Igor Pavlov <ipavlov@users.sourceforge.net> | 2007-01-20 03:00:00 +0300 |
---|---|---|
committer | Kornel LesiĆski <kornel@geekhood.net> | 2016-05-28 02:15:49 +0300 |
commit | d9666cf046a8453b33b3e2fbf4d82295a9f87df3 (patch) | |
tree | c722ed19b844b53042aec0c1d7d2f8381140a5ed /C/Compress | |
parent | 804edc5756fede54dbb1aefda6d39d306111938d (diff) |
4.44 beta
Diffstat (limited to 'C/Compress')
28 files changed, 4929 insertions, 0 deletions
diff --git a/C/Compress/Branch/BranchARM.c b/C/Compress/Branch/BranchARM.c new file mode 100755 index 00000000..6d4e3672 --- /dev/null +++ b/C/Compress/Branch/BranchARM.c @@ -0,0 +1,26 @@ +/* BranchARM.c */ + +#include "BranchARM.h" + +UInt32 ARM_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding) +{ + UInt32 i; + for (i = 0; i + 4 <= size; i += 4) + { + if (data[i + 3] == 0xEB) + { + UInt32 src = (data[i + 2] << 16) | (data[i + 1] << 8) | (data[i + 0]); + src <<= 2; + UInt32 dest; + if (encoding) + dest = nowPos + i + 8 + src; + else + dest = src - (nowPos + i + 8); + dest >>= 2; + data[i + 2] = (Byte)(dest >> 16); + data[i + 1] = (Byte)(dest >> 8); + data[i + 0] = (Byte)dest; + } + } + return i; +} diff --git a/C/Compress/Branch/BranchARM.h b/C/Compress/Branch/BranchARM.h new file mode 100755 index 00000000..02eb1b47 --- /dev/null +++ b/C/Compress/Branch/BranchARM.h @@ -0,0 +1,10 @@ +// BranchARM.h + +#ifndef __BRANCH_ARM_H +#define __BRANCH_ARM_H + +#include "BranchTypes.h" + +UInt32 ARM_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding); + +#endif diff --git a/C/Compress/Branch/BranchARMThumb.c b/C/Compress/Branch/BranchARMThumb.c new file mode 100755 index 00000000..aab9c7a1 --- /dev/null +++ b/C/Compress/Branch/BranchARMThumb.c @@ -0,0 +1,35 @@ +/* BranchARMThumb.c */ + +#include "BranchARMThumb.h" + +UInt32 ARMThumb_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding) +{ + UInt32 i; + for (i = 0; i + 4 <= size; i += 2) + { + if ((data[i + 1] & 0xF8) == 0xF0 && + (data[i + 3] & 0xF8) == 0xF8) + { + UInt32 src = + ((data[i + 1] & 0x7) << 19) | + (data[i + 0] << 11) | + ((data[i + 3] & 0x7) << 8) | + (data[i + 2]); + + src <<= 1; + UInt32 dest; + if (encoding) + dest = nowPos + i + 4 + src; + else + dest = src - (nowPos + i + 4); + dest >>= 1; + + data[i + 1] = (Byte)(0xF0 | ((dest >> 19) & 0x7)); + data[i + 0] = (Byte)(dest >> 11); + data[i + 3] = (Byte)(0xF8 | ((dest >> 8) & 0x7)); + data[i + 2] = (Byte)dest; + i += 2; + } + } + return i; +} diff --git a/C/Compress/Branch/BranchARMThumb.h b/C/Compress/Branch/BranchARMThumb.h new file mode 100755 index 00000000..d67e6e5a --- /dev/null +++ b/C/Compress/Branch/BranchARMThumb.h @@ -0,0 +1,10 @@ +// BranchARMThumb.h + +#ifndef __BRANCH_ARM_THUMB_H +#define __BRANCH_ARM_THUMB_H + +#include "BranchTypes.h" + +UInt32 ARMThumb_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding); + +#endif diff --git a/C/Compress/Branch/BranchIA64.c b/C/Compress/Branch/BranchIA64.c new file mode 100755 index 00000000..e7775564 --- /dev/null +++ b/C/Compress/Branch/BranchIA64.c @@ -0,0 +1,63 @@ +/* BranchIA64.c */ + +#include "BranchIA64.h" + +const Byte kBranchTable[32] = +{ + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 4, 4, 6, 6, 0, 0, 7, 7, + 4, 4, 0, 0, 4, 4, 0, 0 +}; + +UInt32 IA64_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding) +{ + UInt32 i; + for (i = 0; i + 16 <= size; i += 16) + { + UInt32 instrTemplate = data[i] & 0x1F; + UInt32 mask = kBranchTable[instrTemplate]; + UInt32 bitPos = 5; + for (int slot = 0; slot < 3; slot++, bitPos += 41) + { + if (((mask >> slot) & 1) == 0) + continue; + UInt32 bytePos = (bitPos >> 3); + UInt32 bitRes = bitPos & 0x7; + UInt64 instruction = 0; + int j; + for (j = 0; j < 6; j++) + instruction += (UInt64)(data[i + j + bytePos]) << (8 * j); + + UInt64 instNorm = instruction >> bitRes; + if (((instNorm >> 37) & 0xF) == 0x5 + && ((instNorm >> 9) & 0x7) == 0 + /* && (instNorm & 0x3F)== 0 */ + ) + { + UInt32 src = UInt32((instNorm >> 13) & 0xFFFFF); + src |= ((instNorm >> 36) & 1) << 20; + + src <<= 4; + + UInt32 dest; + if (encoding) + dest = nowPos + i + src; + else + dest = src - (nowPos + i); + + dest >>= 4; + + instNorm &= ~(UInt64(0x8FFFFF) << 13); + instNorm |= (UInt64(dest & 0xFFFFF) << 13); + instNorm |= (UInt64(dest & 0x100000) << (36 - 20)); + + instruction &= (1 << bitRes) - 1; + instruction |= (instNorm << bitRes); + for (j = 0; j < 6; j++) + data[i + j + bytePos] = Byte(instruction >> (8 * j)); + } + } + } + return i; +} diff --git a/C/Compress/Branch/BranchIA64.h b/C/Compress/Branch/BranchIA64.h new file mode 100755 index 00000000..b7757fe9 --- /dev/null +++ b/C/Compress/Branch/BranchIA64.h @@ -0,0 +1,10 @@ +// BranchIA64.h + +#ifndef __BRANCH_IA64_H +#define __BRANCH_IA64_H + +#include "BranchTypes.h" + +UInt32 IA64_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding); + +#endif diff --git a/C/Compress/Branch/BranchPPC.c b/C/Compress/Branch/BranchPPC.c new file mode 100755 index 00000000..b3e5703f --- /dev/null +++ b/C/Compress/Branch/BranchPPC.c @@ -0,0 +1,36 @@ +/* BranchPPC.c */ + +#include "BranchPPC.h" + +UInt32 PPC_B_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding) +{ + UInt32 i; + for (i = 0; i + 4 <= size; i += 4) + { + /* PowerPC branch 6(48) 24(Offset) 1(Abs) 1(Link) */ + if ((data[i] >> 2) == 0x12 && + ( + (data[i + 3] & 3) == 1 + /* || (data[i+3] & 3) == 3 */ + ) + ) + { + UInt32 src = ((data[i + 0] & 3) << 24) | + (data[i + 1] << 16) | + (data[i + 2] << 8) | + (data[i + 3] & (~3)); + + UInt32 dest; + if (encoding) + dest = nowPos + i + src; + else + dest = src - (nowPos + i); + data[i + 0] = (Byte)(0x48 | ((dest >> 24) & 0x3)); + data[i + 1] = (Byte)(dest >> 16); + data[i + 2] = (Byte)(dest >> 8); + data[i + 3] &= 0x3; + data[i + 3] |= dest; + } + } + return i; +} diff --git a/C/Compress/Branch/BranchPPC.h b/C/Compress/Branch/BranchPPC.h new file mode 100755 index 00000000..c02bba19 --- /dev/null +++ b/C/Compress/Branch/BranchPPC.h @@ -0,0 +1,10 @@ +// BranchPPC.h + +#ifndef __BRANCH_PPC_H +#define __BRANCH_PPC_H + +#include "BranchTypes.h" + +UInt32 PPC_B_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding); + +#endif diff --git a/C/Compress/Branch/BranchSPARC.c b/C/Compress/Branch/BranchSPARC.c new file mode 100755 index 00000000..c175875b --- /dev/null +++ b/C/Compress/Branch/BranchSPARC.c @@ -0,0 +1,36 @@ +/* BranchSPARC.c */ + +#include "BranchSPARC.h" + +UInt32 SPARC_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding) +{ + UInt32 i; + for (i = 0; i + 4 <= size; i += 4) + { + if (data[i] == 0x40 && (data[i + 1] & 0xC0) == 0x00 || + data[i] == 0x7F && (data[i + 1] & 0xC0) == 0xC0) + { + UInt32 src = + ((UInt32)data[i + 0] << 24) | + ((UInt32)data[i + 1] << 16) | + ((UInt32)data[i + 2] << 8) | + ((UInt32)data[i + 3]); + + src <<= 2; + UInt32 dest; + if (encoding) + dest = nowPos + i + src; + else + dest = src - (nowPos + i); + dest >>= 2; + + dest = (((0 - ((dest >> 22) & 1)) << 22) & 0x3FFFFFFF) | (dest & 0x3FFFFF) | 0x40000000; + + data[i + 0] = (Byte)(dest >> 24); + data[i + 1] = (Byte)(dest >> 16); + data[i + 2] = (Byte)(dest >> 8); + data[i + 3] = (Byte)dest; + } + } + return i; +} diff --git a/C/Compress/Branch/BranchSPARC.h b/C/Compress/Branch/BranchSPARC.h new file mode 100755 index 00000000..fbe9e673 --- /dev/null +++ b/C/Compress/Branch/BranchSPARC.h @@ -0,0 +1,10 @@ +// BranchSPARC.h + +#ifndef __BRANCH_SPARC_H +#define __BRANCH_SPARC_H + +#include "BranchTypes.h" + +UInt32 SPARC_B_Convert(Byte *data, UInt32 size, UInt32 nowPos, int encoding); + +#endif diff --git a/C/Compress/Branch/BranchTypes.h b/C/Compress/Branch/BranchTypes.h new file mode 100755 index 00000000..f7ad3abc --- /dev/null +++ b/C/Compress/Branch/BranchTypes.h @@ -0,0 +1,25 @@ +/* BranchTypes.h */ + +#ifndef __BRANCHTYPES_H +#define __BRANCHTYPES_H + +#ifndef _7ZIP_BYTE_DEFINED +#define _7ZIP_BYTE_DEFINED +typedef unsigned char Byte; +#endif + +#ifndef _7ZIP_UINT16_DEFINED +#define _7ZIP_UINT16_DEFINED +typedef unsigned short UInt16; +#endif + +#ifndef _7ZIP_UINT32_DEFINED +#define _7ZIP_UINT32_DEFINED +#ifdef _LZMA_UINT32_IS_ULONG +typedef unsigned long UInt32; +#else +typedef unsigned int UInt32; +#endif +#endif + +#endif diff --git a/C/Compress/Branch/BranchX86.c b/C/Compress/Branch/BranchX86.c new file mode 100755 index 00000000..c3f455b8 --- /dev/null +++ b/C/Compress/Branch/BranchX86.c @@ -0,0 +1,101 @@ +/* BranchX86.c */ + +#include "BranchX86.h" + +/* +static int inline Test86MSByte(Byte b) +{ + return (b == 0 || b == 0xFF); +} +*/ +#define Test86MSByte(b) ((b) == 0 || (b) == 0xFF) + +const int kMaskToAllowedStatus[8] = {1, 1, 1, 0, 1, 0, 0, 0}; +const Byte kMaskToBitNumber[8] = {0, 1, 2, 2, 3, 3, 3, 3}; + +/* +void x86_Convert_Init(UInt32 *prevMask, UInt32 *prevPos) +{ + *prevMask = 0; + *prevPos = (UInt32)(-5); +} +*/ + +UInt32 x86_Convert(Byte *buffer, UInt32 endPos, UInt32 nowPos, + UInt32 *prevMask, UInt32 *prevPos, int encoding) +{ + UInt32 bufferPos = 0; + UInt32 limit; + + if (endPos < 5) + return 0; + + if (nowPos - *prevPos > 5) + *prevPos = nowPos - 5; + + limit = endPos - 5; + while(bufferPos <= limit) + { + Byte b = buffer[bufferPos]; + UInt32 offset; + if (b != 0xE8 && b != 0xE9) + { + bufferPos++; + continue; + } + offset = (nowPos + bufferPos - *prevPos); + *prevPos = (nowPos + bufferPos); + if (offset > 5) + *prevMask = 0; + else + { + UInt32 i; + for (i = 0; i < offset; i++) + { + *prevMask &= 0x77; + *prevMask <<= 1; + } + } + b = buffer[bufferPos + 4]; + if (Test86MSByte(b) && kMaskToAllowedStatus[(*prevMask >> 1) & 0x7] && + (*prevMask >> 1) < 0x10) + { + UInt32 src = + ((UInt32)(b) << 24) | + ((UInt32)(buffer[bufferPos + 3]) << 16) | + ((UInt32)(buffer[bufferPos + 2]) << 8) | + (buffer[bufferPos + 1]); + + UInt32 dest; + for (;;) + { + UInt32 index; + if (encoding) + dest = (nowPos + bufferPos + 5) + src; + else + dest = src - (nowPos + bufferPos + 5); + if (*prevMask == 0) + break; + index = kMaskToBitNumber[*prevMask >> 1]; + b = (Byte)(dest >> (24 - index * 8)); + if (!Test86MSByte(b)) + break; + src = dest ^ ((1 << (32 - index * 8)) - 1); + } + buffer[bufferPos + 4] = (Byte)(~(((dest >> 24) & 1) - 1)); + buffer[bufferPos + 3] = (Byte)(dest >> 16); + buffer[bufferPos + 2] = (Byte)(dest >> 8); + buffer[bufferPos + 1] = (Byte)dest; + bufferPos += 5; + *prevMask = 0; + } + else + { + bufferPos++; + *prevMask |= 1; + if (Test86MSByte(b)) + *prevMask |= 0x10; + } + } + return bufferPos; +} diff --git a/C/Compress/Branch/BranchX86.h b/C/Compress/Branch/BranchX86.h new file mode 100755 index 00000000..25c1ae51 --- /dev/null +++ b/C/Compress/Branch/BranchX86.h @@ -0,0 +1,13 @@ +/* BranchX86.h */ + +#ifndef __BRANCHX86_H +#define __BRANCHX86_H + +#include "BranchTypes.h" + +#define x86_Convert_Init(prevMask, prevPos) { prevMask = 0; prevPos = (UInt32)(-5); } + +UInt32 x86_Convert(Byte *buffer, UInt32 endPos, UInt32 nowPos, + UInt32 *prevMask, UInt32 *prevPos, int encoding); + +#endif diff --git a/C/Compress/Huffman/HuffmanEncode.c b/C/Compress/Huffman/HuffmanEncode.c new file mode 100755 index 00000000..3168db2d --- /dev/null +++ b/C/Compress/Huffman/HuffmanEncode.c @@ -0,0 +1,146 @@ +// Compression/HuffmanEncode.c + +#include "HuffmanEncode.h" +#include "../../Sort.h" + +#define kMaxLen 16 +#define NUM_BITS 10 +#define MASK ((1 << NUM_BITS) - 1) + +#define NUM_COUNTERS 64 + +// use BLOCK_SORT_EXTERNAL_FLAGS if blockSize > 1M +#define HUFFMAN_SPEED_OPT + +void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen) +{ + UInt32 num = 0; + // if (maxLen > 10) maxLen = 10; + { + UInt32 i; + + #ifdef HUFFMAN_SPEED_OPT + + UInt32 counters[NUM_COUNTERS]; + for (i = 0; i < NUM_COUNTERS; i++) + counters[i] = 0; + for (i = 0; i < numSymbols; i++) + { + UInt32 freq = freqs[i]; + counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++; + } + + for (i = 1; i < NUM_COUNTERS; i++) + { + UInt32 temp = counters[i]; + counters[i] = num; + num += temp; + } + + for (i = 0; i < numSymbols; i++) + { + UInt32 freq = freqs[i]; + if (freq == 0) + lens[i] = 0; + else + p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS); + } + counters[0] = 0; + HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]); + + #else + + for (i = 0; i < numSymbols; i++) + { + UInt32 freq = freqs[i]; + if (freq == 0) + lens[i] = 0; + else + p[num++] = i | (freq << NUM_BITS); + } + HeapSort(p, num); + + #endif + } + + if (num < 2) + { + int minCode = 0; + int maxCode = 1; + if (num == 1) + { + maxCode = p[0] & MASK; + if (maxCode == 0) + maxCode++; + } + p[minCode] = 0; + p[maxCode] = 1; + lens[minCode] = lens[maxCode] = 1; + return; + } + + { + UInt32 b, e, i; + + i = b = e = 0; + do + { + UInt32 n, m, freq; + n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++; + freq = (p[n] & ~MASK); + p[n] = (p[n] & MASK) | (e << NUM_BITS); + m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++; + freq += (p[m] & ~MASK); + p[m] = (p[m] & MASK) | (e << NUM_BITS); + p[e] = (p[e] & MASK) | freq; + e++; + } + while (num - e > 1); + + { + UInt32 lenCounters[kMaxLen + 1]; + for (i = 0; i <= kMaxLen; i++) + lenCounters[i] = 0; + + p[--e] &= MASK; + lenCounters[1] = 2; + while (e > 0) + { + UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1; + p[e] = (p[e] & MASK) | (len << NUM_BITS); + if (len >= maxLen) + for (len = maxLen - 1; lenCounters[len] == 0; len--); + lenCounters[len]--; + lenCounters[len + 1] += 2; + } + + { + UInt32 len; + i = 0; + for (len = maxLen; len != 0; len--) + { + UInt32 num; + for (num = lenCounters[len]; num != 0; num--) + lens[p[i++] & MASK] = (Byte)len; + } + } + + { + UInt32 nextCodes[kMaxLen + 1]; + { + UInt32 code = 0; + UInt32 len; + for (len = 1; len <= kMaxLen; len++) + nextCodes[len] = code = (code + lenCounters[len - 1]) << 1; + } + // if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; + + { + UInt32 i; + for (i = 0; i < numSymbols; i++) + p[i] = nextCodes[lens[i]]++; + } + } + } + } +} diff --git a/C/Compress/Huffman/HuffmanEncode.h b/C/Compress/Huffman/HuffmanEncode.h new file mode 100755 index 00000000..dfd2f0ab --- /dev/null +++ b/C/Compress/Huffman/HuffmanEncode.h @@ -0,0 +1,20 @@ +// Compress/HuffmanEncode.h + +#ifndef __COMPRESS_HUFFMANENCODE_H +#define __COMPRESS_HUFFMANENCODE_H + +#include "../../Types.h" + +#define HUFFMAN_TEMP_SIZE(num) (num * 2) + +/* +Conditions: + num <= 1024 = 2 ^ NUM_BITS + Sum(freqs) < 4M = 2 ^ (32 - NUM_BITS) + maxLen <= 16 = kMaxLen + Num_Items(p) >= HUFFMAN_TEMP_SIZE(num) +*/ + +void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 num, UInt32 maxLen); + +#endif diff --git a/C/Compress/Lz/LzHash.h b/C/Compress/Lz/LzHash.h new file mode 100755 index 00000000..87c28365 --- /dev/null +++ b/C/Compress/Lz/LzHash.h @@ -0,0 +1,53 @@ +/* LzHash.h */ + +#ifndef __C_LZHASH_H +#define __C_LZHASH_H + +#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)cur[1] << 8); + +#define HASH3_CALC { \ + UInt32 temp = g_CrcTable[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hashValue = (temp ^ ((UInt32)cur[2] << 8)) & p->hashMask; } + +#define HASH4_CALC { \ + UInt32 temp = g_CrcTable[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \ + hashValue = (temp ^ ((UInt32)cur[2] << 8) ^ (g_CrcTable[cur[3]] << 5)) & p->hashMask; } + +#define HASH5_CALC { \ + UInt32 temp = g_CrcTable[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \ + hash4Value = (temp ^ ((UInt32)cur[2] << 8) ^ (g_CrcTable[cur[3]] << 5)); \ + hashValue = (hash4Value ^ (g_CrcTable[cur[4]] << 3)) & p->hashMask; \ + hash4Value &= (kHash4Size - 1); } + +/* #define HASH_ZIP_CALC hashValue = ((cur[0] | ((UInt32)cur[1] << 8)) ^ g_CrcTable[cur[2]]) & 0xFFFF; */ +#define HASH_ZIP_CALC hashValue = ((cur[2] | ((UInt32)cur[0] << 8)) ^ g_CrcTable[cur[1]]) & 0xFFFF; + + +#define MT_HASH2_CALC \ + hash2Value = (g_CrcTable[cur[0]] ^ cur[1]) & (kHash2Size - 1); + +#define MT_HASH3_CALC { \ + UInt32 temp = g_CrcTable[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); } + +#define MT_HASH4_CALC { \ + UInt32 temp = g_CrcTable[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \ + hash4Value = (temp ^ ((UInt32)cur[2] << 8) ^ (g_CrcTable[cur[3]] << 5)) & (kHash4Size - 1); } + +#endif diff --git a/C/Compress/Lz/MatchFinder.c b/C/Compress/Lz/MatchFinder.c new file mode 100755 index 00000000..4580c52b --- /dev/null +++ b/C/Compress/Lz/MatchFinder.c @@ -0,0 +1,725 @@ +/* MatchFinder.c */ +/* Please call InitCrcTable before */ + +#include <string.h> + +#include "MatchFinder.h" +#include "LzHash.h" + +#include "../../7zCrc.h" + +#define kEmptyHashValue 0 +#define kMaxValForNormalize ((UInt32)0xFFFFFFFF) +#define kNormalizeStepMin (1 << 10) /* it must be power of 2 */ +#define kNormalizeMask (~(kNormalizeStepMin - 1)) +#define kMaxHistorySize ((UInt32)3 << 30) + +#define kStartMaxLen 3 + +void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc) +{ + if (!p->directInput) + { + alloc->Free(p->bufferBase); + p->bufferBase = 0; + } +} + +/* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */ + +int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc) +{ + UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv; + if (p->directInput) + { + p->blockSize = blockSize; + return 1; + } + if (p->bufferBase == 0 || p->blockSize != blockSize) + { + LzInWindow_Free(p, alloc); + p->blockSize = blockSize; + p->bufferBase = (Byte *)alloc->Alloc(blockSize); + } + return (p->bufferBase != 0); +} + +Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer + p->pos; } +Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[(size_t)p->pos + index]; } + +UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; } + +void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue) +{ + p->buffer += subValue; + p->posLimit -= subValue; + p->pos -= subValue; + p->streamPos -= subValue; +} + +void MatchFinder_ReadBlock(CMatchFinder *p) +{ + if (p->streamEndWasReached || p->result != SZ_OK) + return; + for (;;) + { + Byte *dest = (p->buffer + p->pos + (p->streamPos - p->pos)); + UInt32 numReadBytes; + UInt32 size = (UInt32)(p->bufferBase + p->blockSize - dest); + if (size == 0) + return; + p->result = p->stream->Read(p->stream, dest, size, &numReadBytes); + if (p->result != SZ_OK) + return; + if (numReadBytes == 0) + { + p->streamEndWasReached = 1; + return; + } + p->streamPos += numReadBytes; + if (p->streamPos - p->pos > p->keepSizeAfter) + return; + } +} + +void MatchFinder_MoveBlock(CMatchFinder *p) +{ + memmove(p->bufferBase, + p->buffer + p->pos - p->keepSizeBefore, + p->streamPos - p->pos + p->keepSizeBefore); + p->buffer = p->bufferBase + p->keepSizeBefore - p->pos; +} + + +int MatchFinder_NeedMove(CMatchFinder *p) +{ + /* if (p->streamEndWasReached) return 0; */ + return ((size_t)(p->bufferBase + p->blockSize - (p->buffer + p->pos)) <= p->keepSizeAfter); +} + +void MatchFinder_ReadIfRequired(CMatchFinder *p) +{ + if (p->streamEndWasReached) + return; + if (p->keepSizeAfter >= p->streamPos - p->pos) + MatchFinder_ReadBlock(p); +} + +void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p) +{ + if (MatchFinder_NeedMove(p)) + MatchFinder_MoveBlock(p); + MatchFinder_ReadBlock(p); +} + +void MatchFinder_SetDefaultSettings(CMatchFinder *p) +{ + p->cutValue = 32; + p->btMode = 1; + p->numHashBytes = 4; + /* p->skipModeBits = 0; */ + p->directInput = 0; + p->bigHash = 0; +} + +void MatchFinder_Construct(CMatchFinder *p) +{ + p->bufferBase = 0; + p->directInput = 0; + p->hash = 0; + MatchFinder_SetDefaultSettings(p); +} + +void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc) +{ + alloc->Free(p->hash); + p->hash = 0; +} + +void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc) +{ + MatchFinder_FreeThisClassMemory(p, alloc); + LzInWindow_Free(p, alloc); +} + +CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc) +{ + size_t sizeInBytes = (size_t)num * sizeof(CLzRef); + if (sizeInBytes / sizeof(CLzRef) != num) + return 0; + return (CLzRef *)alloc->Alloc(sizeInBytes); +} + +int MatchFinder_Create(CMatchFinder *p, UInt32 historySize, + UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter, + ISzAlloc *alloc) +{ + UInt32 sizeReserv; + if (historySize > kMaxHistorySize) + { + MatchFinder_Free(p, alloc); + return 0; + } + sizeReserv = historySize >> 1; + if (historySize > ((UInt32)2 << 30)) + sizeReserv = historySize >> 2; + sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 12); + + 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, alloc)) + { + UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1; + UInt32 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 prevSize = p->hashSizeSum + p->numSons; + UInt32 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, alloc); + p->hash = AllocRefs(newSize, alloc); + if (p->hash != 0) + { + p->son = p->hash + p->hashSizeSum; + return 1; + } + } + } + MatchFinder_Free(p, alloc); + return 0; +} + +void MatchFinder_SetLimits(CMatchFinder *p) +{ + UInt32 limit = kMaxValForNormalize - p->pos; + UInt32 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 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 i; + for(i = 0; i < p->hashSizeSum; i++) + p->hash[i] = kEmptyHashValue; + p->cyclicBufferPos = 0; + p->buffer = p->bufferBase - p->cyclicBufferSize; + p->pos = p->streamPos = p->cyclicBufferSize; + p->result = SZ_OK; + p->streamEndWasReached = 0; + MatchFinder_ReadBlock(p); + MatchFinder_SetLimits(p); +} + +UInt32 MatchFinder_GetSubValue(CMatchFinder *p) +{ + return (p->pos - p->historySize - 1) & kNormalizeMask; +} + +void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems) +{ + UInt32 i; + for (i = 0; i < numItems; i++) + { + UInt32 value = items[i]; + if (value <= subValue) + value = kEmptyHashValue; + else + value -= subValue; + items[i] = value; + } +} + +void MatchFinder_Normalize(CMatchFinder *p) +{ + UInt32 subValue = MatchFinder_GetSubValue(p); + MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons); + MatchFinder_ReduceOffsets(p, subValue); +} + +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); +} + +UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son, + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue, + UInt32 *distances, UInt32 maxLen) +{ + son[_cyclicBufferPos] = curMatch; + for (;;) + { + UInt32 delta = pos - curMatch; + if (cutValue-- == 0 || delta >= _cyclicBufferSize) + return distances; + { + const Byte *pb = buffer + curMatch; + const Byte *cur = buffer + pos; + curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)]; + if (pb[maxLen] == cur[maxLen] && *pb == *cur) + { + UInt32 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 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son, + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue, + UInt32 *distances, UInt32 maxLen) +{ + CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1; + CLzRef *ptr1 = son + (_cyclicBufferPos << 1); + UInt32 len0 = 0, len1 = 0; + for (;;) + { + UInt32 delta = pos - curMatch; + if (cutValue-- == 0 || delta >= _cyclicBufferSize) + { + *ptr0 = *ptr1 = kEmptyHashValue; + return distances; + } + { + CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1); + const Byte *pb = buffer + curMatch; + const Byte *cur = buffer + pos; + UInt32 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; + } + } + } +} + +void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son, + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue) +{ + CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1; + CLzRef *ptr1 = son + (_cyclicBufferPos << 1); + UInt32 len0 = 0, len1 = 0; + for (;;) + { + UInt32 delta = pos - curMatch; + if (cutValue-- == 0 || delta >= _cyclicBufferSize) + { + *ptr0 = *ptr1 = kEmptyHashValue; + return; + } + { + CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1); + const Byte *pb = buffer + curMatch; + const Byte *cur = buffer + pos; + UInt32 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; \ + if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p); + +#define MOVE_POS_RET MOVE_POS return offset; + +void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; } + +#define GET_MATCHES_HEADER2(minLen, ret_op) \ + UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \ + lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \ + cur = p->buffer + p->pos; + +#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0) +#define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue) + +#define GET_MATCHES_FOOTER(offset, maxLen) \ + offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, p->pos, p->buffer, p->son, p->cyclicBufferPos, \ + p->cyclicBufferSize, p->cutValue, distances + offset, maxLen) - distances); MOVE_POS_RET; + +#define SKIP_FOOTER \ + SkipMatchesSpec(lenLimit, curMatch, p->pos, p->buffer, p->son, \ + p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue); MOVE_POS; + +UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) +{ + UInt32 offset; + GET_MATCHES_HEADER(2) + HASH2_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + offset = 0; + GET_MATCHES_FOOTER(offset, 1) +} + +UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) +{ + UInt32 offset; + GET_MATCHES_HEADER(3) + HASH_ZIP_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + offset = 0; + GET_MATCHES_FOOTER(offset, 2) +} + +UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) +{ + UInt32 hash2Value, matchMinPos, curMatch2, maxLen, offset; + GET_MATCHES_HEADER(3) + + HASH3_CALC; + + curMatch2 = p->hash[hash2Value]; + curMatch = p->hash[kFix3HashSize + hashValue]; + + p->hash[hash2Value] = + p->hash[kFix3HashSize + hashValue] = p->pos; + + matchMinPos = p->pos - p->cyclicBufferSize; + + maxLen = 2; + offset = 0; + if (curMatch2 > matchMinPos && p->buffer[curMatch2] == cur[0]) + { + for (; maxLen != lenLimit; maxLen++) + if (p->buffer[curMatch2 + maxLen] != cur[maxLen]) + break; + distances[0] = maxLen; + distances[1] = p->pos - curMatch2 - 1; + offset = 2; + if (maxLen == lenLimit) + { + SkipMatchesSpec(lenLimit, curMatch, p->pos, p->buffer, p->son, + p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue); + MOVE_POS_RET; + } + } + GET_MATCHES_FOOTER(offset, maxLen) +} + +UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) +{ + UInt32 hash2Value, hash3Value, matchMinPos, curMatch2, curMatch3, maxLen, offset; + GET_MATCHES_HEADER(4) + + HASH4_CALC; + + curMatch2 = p->hash[ hash2Value]; + curMatch3 = p->hash[kFix3HashSize + hash3Value]; + curMatch = p->hash[kFix4HashSize + hashValue]; + + p->hash[ hash2Value] = + p->hash[kFix3HashSize + hash3Value] = + p->hash[kFix4HashSize + hashValue] = p->pos; + + matchMinPos = p->pos - p->cyclicBufferSize; + maxLen = 1; + offset = 0; + if (curMatch2 > matchMinPos && p->buffer[curMatch2] == cur[0]) + { + distances[0] = maxLen = 2; + distances[1] = p->pos - curMatch2 - 1; + offset = 2; + } + if (curMatch2 != curMatch3 && curMatch3 > matchMinPos && p->buffer[curMatch3] == cur[0]) + { + maxLen = 3; + distances[offset + 1] = p->pos - curMatch3 - 1; + offset += 2; + curMatch2 = curMatch3; + } + if (offset != 0) + { + for (; maxLen != lenLimit; maxLen++) + if (p->buffer[curMatch2 + maxLen] != cur[maxLen]) + break; + distances[offset - 2] = maxLen; + if (maxLen == lenLimit) + { + SkipMatchesSpec(lenLimit, curMatch, p->pos, p->buffer, p->son, + p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue); + MOVE_POS_RET; + } + } + if (maxLen < 3) + maxLen = 3; + GET_MATCHES_FOOTER(offset, maxLen) +} + +UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) +{ + UInt32 hash2Value, hash3Value, matchMinPos, curMatch2, curMatch3, maxLen, offset; + GET_MATCHES_HEADER(4) + + HASH4_CALC; + + curMatch2 = p->hash[ hash2Value]; + curMatch3 = p->hash[kFix3HashSize + hash3Value]; + curMatch = p->hash[kFix4HashSize + hashValue]; + + p->hash[ hash2Value] = + p->hash[kFix3HashSize + hash3Value] = + p->hash[kFix4HashSize + hashValue] = p->pos; + + matchMinPos = p->pos - p->cyclicBufferSize; + maxLen = 1; + offset = 0; + if (curMatch2 > matchMinPos && p->buffer[curMatch2] == cur[0]) + { + distances[0] = maxLen = 2; + distances[1] = p->pos - curMatch2 - 1; + offset = 2; + } + if (curMatch2 != curMatch3 && curMatch3 > matchMinPos && p->buffer[curMatch3] == cur[0]) + { + maxLen = 3; + distances[offset + 1] = p->pos - curMatch3 - 1; + offset += 2; + curMatch2 = curMatch3; + } + if (offset != 0) + { + for (; maxLen != lenLimit; maxLen++) + if (p->buffer[curMatch2 + maxLen] != 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)(Hc_GetMatchesSpec(lenLimit, curMatch, p->pos, p->buffer, p->son, + p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue, + distances + offset, maxLen) - (distances)); + MOVE_POS_RET +} + +void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 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 num) +{ + do + { + SKIP_HEADER(3) + HASH_ZIP_CALC; + curMatch = p->hash[hashValue]; + p->hash[hashValue] = p->pos; + SKIP_FOOTER + } + while (--num != 0); +} + +void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num) +{ + do + { + UInt32 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); +} + +void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num) +{ + do + { + UInt32 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); +} + +void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num) +{ + do + { + UInt32 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 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/C/Compress/Lz/MatchFinder.h b/C/Compress/Lz/MatchFinder.h new file mode 100755 index 00000000..43906312 --- /dev/null +++ b/C/Compress/Lz/MatchFinder.h @@ -0,0 +1,103 @@ +/* MatchFinder.h */ + +#ifndef __MATCHFINDER_H +#define __MATCHFINDER_H + +#include "../../IStream.h" + +typedef UInt32 CLzRef; + +typedef struct _CMatchFinder +{ + Byte *buffer; + UInt32 pos; + UInt32 posLimit; + UInt32 streamPos; + UInt32 lenLimit; + + UInt32 cyclicBufferPos; + UInt32 cyclicBufferSize; /* it must be = (historySize + 1) */ + + UInt32 matchMaxLen; + CLzRef *hash; + CLzRef *son; + UInt32 hashMask; + UInt32 cutValue; + + Byte *bufferBase; + ISeqInStream *stream; + int streamEndWasReached; + + UInt32 blockSize; + UInt32 keepSizeBefore; + UInt32 keepSizeAfter; + + UInt32 numHashBytes; + int directInput; + int btMode; + /* int skipModeBits; */ + int bigHash; + UInt32 historySize; + UInt32 fixedHashSize; + UInt32 hashSizeSum; + UInt32 numSons; + + HRes result; +} CMatchFinder; + +#define Inline_MatchFinder_GetPointerToCurrentPos(p) ((p)->buffer + (p)->pos) +#define Inline_MatchFinder_GetIndexByte(p, index) ((p)->buffer[(size_t)(p)->pos + (Int32)(index)]) +#define Inline_MatchFinder_GetNumAvailableBytes(p) ((p)->streamPos - (p)->pos) + +int MatchFinder_NeedMove(CMatchFinder *p); +Byte *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 historySize, + UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter, + ISzAlloc *alloc); +void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc); +void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems); +void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue); + +UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son, + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue, + UInt32 *distances, UInt32 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 Byte (*Mf_GetIndexByte_Func)(void *object, Int32 index); +typedef UInt32 (*Mf_GetNumAvailableBytes_Func)(void *object); +typedef const Byte * (*Mf_GetPointerToCurrentPos_Func)(void *object); +typedef UInt32 (*Mf_GetMatches_Func)(void *object, UInt32 *distances); +typedef void (*Mf_Skip_Func)(void *object, UInt32); + +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 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances); +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num); + +#endif diff --git a/C/Compress/Lz/MatchFinderMt.c b/C/Compress/Lz/MatchFinderMt.c new file mode 100755 index 00000000..4ab90d9a --- /dev/null +++ b/C/Compress/Lz/MatchFinderMt.c @@ -0,0 +1,792 @@ +/* MatchFinderMt.c */ + +#include <stdio.h> +#include "../../7zCrc.h" +#include "LzHash.h" + +#include "MatchFinderMt.h" + +void MtSync_Construct(CMtSync *p) +{ + p->wasCreated = False; + p->csWasInitialized = False; + p->csWasEntered = False; + Thread_Construct(&p->thread); + Event_Construct(&p->canStart); + Event_Construct(&p->wasStarted); + Event_Construct(&p->wasStopped); + Semaphore_Construct(&p->freeSemaphore); + Semaphore_Construct(&p->filledSemaphore); +} + +void MtSync_GetNextBlock(CMtSync *p) +{ + if (p->needStart) + { + p->numProcessedBlocks = 1; + p->needStart = False; + p->stopWriting = False; + p->exit = False; + Event_Reset(&p->wasStarted); + Event_Reset(&p->wasStopped); + + Event_Set(&p->canStart); + Event_Wait(&p->wasStarted); + } + else + { + CriticalSection_Leave(&p->cs); + p->csWasEntered = False; + p->numProcessedBlocks++; + Semaphore_Release1(&p->freeSemaphore); + } + Semaphore_Wait(&p->filledSemaphore); + CriticalSection_Enter(&p->cs); + p->csWasEntered = True; +} + +/* MtSync_StopWriting must be called if Writing was started */ + +void MtSync_StopWriting(CMtSync *p) +{ + UInt32 myNumBlocks = p->numProcessedBlocks; + if (!Thread_WasCreated(&p->thread) || p->needStart) + return; + p->stopWriting = True; + if (p->csWasEntered) + { + CriticalSection_Leave(&p->cs); + p->csWasEntered = False; + } + Semaphore_Release1(&p->freeSemaphore); + + Event_Wait(&p->wasStopped); + + while (myNumBlocks++ != p->numProcessedBlocks) + { + Semaphore_Wait(&p->filledSemaphore); + Semaphore_Release1(&p->freeSemaphore); + } + p->needStart = True; +} + +void MtSync_Destruct(CMtSync *p) +{ + if (Thread_WasCreated(&p->thread)) + { + MtSync_StopWriting(p); + p->exit = True; + if (p->needStart) + Event_Set(&p->canStart); + Thread_Wait(&p->thread); + Thread_Close(&p->thread); + } + if (p->csWasInitialized) + { + CriticalSection_Delete(&p->cs); + p->csWasInitialized = False; + } + + Event_Close(&p->canStart); + Event_Close(&p->wasStarted); + Event_Close(&p->wasStopped); + Semaphore_Close(&p->freeSemaphore); + Semaphore_Close(&p->filledSemaphore); + + p->wasCreated = False; +} + +HRes MtSync_Create2(CMtSync *p, unsigned (StdCall *startAddress)(void *), void *obj, UInt32 numBlocks) +{ + if (p->wasCreated) + return SZ_OK; + + RINOK(CriticalSection_Init(&p->cs)); + p->csWasInitialized = True; + + RINOK(AutoResetEvent_CreateNotSignaled(&p->canStart)); + RINOK(AutoResetEvent_CreateNotSignaled(&p->wasStarted)); + RINOK(AutoResetEvent_CreateNotSignaled(&p->wasStopped)); + + RINOK(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks)); + RINOK(Semaphore_Create(&p->filledSemaphore, 0, numBlocks)); + + p->needStart = True; + + RINOK(Thread_Create(&p->thread, startAddress, obj)); + p->wasCreated = True; + return SZ_OK; +} + +HRes MtSync_Create(CMtSync *p, unsigned (StdCall *startAddress)(void *), void *obj, UInt32 numBlocks) +{ + HRes res = MtSync_Create2(p, startAddress, obj, numBlocks); + if (res != SZ_OK) + MtSync_Destruct(p); + return res; +} + + +void MtSync_Init(CMtSync *p) { p->needStart = True; } + +#define kMtMaxValForNormalize 0xFFFFFFFF + +/* +Notes: +instead of "size_t pos" we can use "UInt32 pos". +But MSVC++ compilers have BUG: +sometimes they use signed extending: (size_t)pos was compiled to "movsxd r10, edx" +*/ + +#define DEF_GetHeads(name, v) \ +static void GetHeads ## name(const Byte *buffer, size_t pos, \ +UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads) { \ +for (; numHeads != 0; numHeads--) { const Byte *p = buffer + (size_t)pos; \ +const UInt32 value = (v); *heads++ = (UInt32)pos - hash[value]; hash[value] = (UInt32)(pos++); } } + +DEF_GetHeads(2, (p[0] | ((UInt32)p[1] << 8)) & hashMask) +DEF_GetHeads(3, (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask) +DEF_GetHeads(4, (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (g_CrcTable[p[3]] << 5)) & hashMask) +DEF_GetHeads(4b, (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ ((UInt32)p[3] << 16)) & hashMask) +DEF_GetHeads(5, (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (g_CrcTable[p[3]] << 5) ^ (g_CrcTable[p[4]] << 3)) & hashMask) + +void HashThreadFunc(CMatchFinderMt *mt) +{ + CMtSync *p = &mt->hashSync; + for (;;) + { + UInt32 numProcessedBlocks = 0; + Event_Wait(&p->canStart); + Event_Set(&p->wasStarted); + for (;;) + { + if (p->exit) + return; + if (p->stopWriting) + { + p->numProcessedBlocks = numProcessedBlocks; + Event_Set(&p->wasStopped); + break; + } + + { + CMatchFinder *mf = mt->MatchFinder; + if (MatchFinder_NeedMove(mf)) + { + CriticalSection_Enter(&mt->btSync.cs); + CriticalSection_Enter(&mt->hashSync.cs); + { + const Byte *beforePtr = MatchFinder_GetPointerToCurrentPos(mf); + const Byte *afterPtr; + MatchFinder_MoveBlock(mf); + afterPtr = MatchFinder_GetPointerToCurrentPos(mf); + mt->pointerToCurPos -= beforePtr - afterPtr; + mt->buffer -= beforePtr - afterPtr; + } + CriticalSection_Leave(&mt->btSync.cs); + CriticalSection_Leave(&mt->hashSync.cs); + continue; + } + + Semaphore_Wait(&p->freeSemaphore); + + MatchFinder_ReadIfRequired(mf); + if (mf->pos > (kMtMaxValForNormalize - kMtHashBlockSize)) + { + UInt32 subValue = (mf->pos - mf->historySize - 1); + MatchFinder_ReduceOffsets(mf, subValue); + MatchFinder_Normalize3(subValue, mf->hash + mf->fixedHashSize, mf->hashMask + 1); + } + { + UInt32 *heads = mt->hashBuf + ((numProcessedBlocks++) & kMtHashNumBlocksMask) * kMtHashBlockSize; + UInt32 num = mf->streamPos - mf->pos; + heads[0] = 2; + heads[1] = num; + if (num >= mf->numHashBytes) + { + num = num - mf->numHashBytes + 1; + if (num > kMtHashBlockSize - 2) + num = kMtHashBlockSize - 2; + mt->GetHeadsFunc(mf->buffer, mf->pos, mf->hash + mf->fixedHashSize, mf->hashMask, heads + 2, num); + heads[0] += num; + } + mf->pos += num; + } + } + + Semaphore_Release1(&p->filledSemaphore); + } + } +} + +void MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt *p) +{ + MtSync_GetNextBlock(&p->hashSync); + p->hashBufPosLimit = p->hashBufPos = ((p->hashSync.numProcessedBlocks - 1) & kMtHashNumBlocksMask) * kMtHashBlockSize; + p->hashBufPosLimit += p->hashBuf[p->hashBufPos++]; + p->hashNumAvail = p->hashBuf[p->hashBufPos++]; +} + +#define kEmptyHashValue 0 + +/* #define MFMT_GM_INLINE */ + +#ifdef MFMT_GM_INLINE + +#if _MSC_VER >= 1300 +#define NO_INLINE __declspec(noinline) __fastcall +#else +#ifdef _MSC_VER +#define NO_INLINE __fastcall +#endif +#endif + +Int32 NO_INLINE GetMatchesSpecN(UInt32 lenLimit, UInt32 pos, const Byte *buffer, CLzRef *son, + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue, + UInt32 *_distances, UInt32 _maxLen, const UInt32 *hash, Int32 limit, UInt32 size, UInt32 *posRes) +{ + do + { + UInt32 *distances = _distances + 1; + UInt32 curMatch = pos - *hash++; + + CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1; + CLzRef *ptr1 = son + (_cyclicBufferPos << 1); + UInt32 len0 = 0, len1 = 0; + UInt32 cutValue = _cutValue; + UInt32 maxLen = _maxLen; + for (;;) + { + UInt32 delta = pos - curMatch; + if (cutValue-- == 0 || delta >= _cyclicBufferSize) + { + *ptr0 = *ptr1 = kEmptyHashValue; + break; + } + { + CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1); + const Byte *pb = buffer + curMatch; + const Byte *cur = buffer + pos; + UInt32 len = (len0 < len1 ? len0 : len1); + if (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]; + break; + } + } + } + if (pb[len] < cur[len]) + { + *ptr1 = curMatch; + ptr1 = pair + 1; + curMatch = *ptr1; + len1 = len; + } + else + { + *ptr0 = curMatch; + ptr0 = pair; + curMatch = *ptr0; + len0 = len; + } + } + } + pos++; + _cyclicBufferPos++; + { + UInt32 num = (UInt32)(distances - _distances); + *_distances = num - 1; + _distances += num; + limit -= num; + } + } + while (limit > 0 && --size != 0); + *posRes = pos; + return limit; +} + +#endif + +void BtGetMatches(CMatchFinderMt *p, UInt32 *distances) +{ + UInt32 numProcessed = 0; + UInt32 curPos = 2; + UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2); + distances[1] = p->hashNumAvail; + while (curPos < limit) + { + if (p->hashBufPos == p->hashBufPosLimit) + { + MatchFinderMt_GetNextBlock_Hash(p); + distances[1] = numProcessed + p->hashNumAvail; + if (p->hashNumAvail >= p->numHashBytes) + continue; + for (; p->hashNumAvail != 0; p->hashNumAvail--) + distances[curPos++] = 0; + break; + } + { + UInt32 size = p->hashBufPosLimit - p->hashBufPos; + UInt32 lenLimit = p->matchMaxLen; + UInt32 pos = p->pos; + UInt32 cyclicBufferPos = p->cyclicBufferPos; + if (lenLimit >= p->hashNumAvail) + lenLimit = p->hashNumAvail; + { + UInt32 size2 = p->hashNumAvail - lenLimit + 1; + if (size2 < size) + size = size2; + size2 = p->cyclicBufferSize - cyclicBufferPos; + if (size2 < size) + size = size2; + } + #ifndef MFMT_GM_INLINE + while (curPos < limit && size-- != 0) + { + UInt32 *startDistances = distances + curPos; + UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++], + pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue, + startDistances + 1, p->numHashBytes - 1) - startDistances); + *startDistances = num - 1; + curPos += num; + cyclicBufferPos++; + pos++; + } + #else + { + UInt32 posRes; + curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue, + distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos) , size, &posRes); + p->hashBufPos += posRes - pos; + cyclicBufferPos += posRes - pos; + pos = posRes; + } + #endif + + numProcessed += pos - p->pos; + p->hashNumAvail -= pos - p->pos; + p->pos = pos; + if (cyclicBufferPos == p->cyclicBufferSize) + cyclicBufferPos = 0; + p->cyclicBufferPos = cyclicBufferPos; + } + } + distances[0] = curPos; +} + +void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex) +{ + CMtSync *sync = &p->hashSync; + if (!sync->needStart) + { + CriticalSection_Enter(&sync->cs); + sync->csWasEntered = True; + } + + BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize); + + if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize) + { + UInt32 subValue = p->pos - p->cyclicBufferSize; + MatchFinder_Normalize3(subValue, p->son, p->cyclicBufferSize * 2); + p->pos -= subValue; + p->buffer += subValue; + } + + if (!sync->needStart) + { + CriticalSection_Leave(&sync->cs); + sync->csWasEntered = False; + } +} + +void BtThreadFunc(CMatchFinderMt *mt) +{ + CMtSync *p = &mt->btSync; + for (;;) + { + UInt32 blockIndex = 0; + Event_Wait(&p->canStart); + Event_Set(&p->wasStarted); + for (;;) + { + if (p->exit) + return; + if (p->stopWriting) + { + p->numProcessedBlocks = blockIndex; + MtSync_StopWriting(&mt->hashSync); + Event_Set(&p->wasStopped); + break; + } + Semaphore_Wait(&p->freeSemaphore); + BtFillBlock(mt, blockIndex++); + Semaphore_Release1(&p->filledSemaphore); + } + } +} + +void MatchFinderMt_Construct(CMatchFinderMt *p) +{ + p->hashBuf = 0; + MtSync_Construct(&p->hashSync); + MtSync_Construct(&p->btSync); +} + +void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc) +{ + alloc->Free(p->hashBuf); + p->hashBuf = 0; +} + +void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc) +{ + MtSync_Destruct(&p->hashSync); + MtSync_Destruct(&p->btSync); + MatchFinderMt_FreeMem(p, alloc); +} + +#define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks) +#define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks) + +static unsigned StdCall HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p); return 0; } +static unsigned StdCall BtThreadFunc2(void *p) { BtThreadFunc((CMatchFinderMt *)p); return 0; } + +HRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore, + UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc) +{ + CMatchFinder *mf = p->MatchFinder; + p->historySize = historySize; + if (kMtBtBlockSize <= matchMaxLen * 4) + return E_INVALIDARG; + if (p->hashBuf == 0) + { + p->hashBuf = (UInt32 *)alloc->Alloc((kHashBufferSize + kBtBufferSize) * sizeof(UInt32)); + if (p->hashBuf == 0) + return SZE_OUTOFMEMORY; + p->btBuf = p->hashBuf + kHashBufferSize; + } + keepAddBufferBefore += (kHashBufferSize + kBtBufferSize); + keepAddBufferAfter += kMtHashBlockSize; + if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc)) + return SZE_OUTOFMEMORY; + + RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks)); + RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks)); + return SZ_OK; +} + +/* Call it after ReleaseStream / SetStream */ +void MatchFinderMt_Init(CMatchFinderMt *p) +{ + CMatchFinder *mf = p->MatchFinder; + p->btBufPos = p->btBufPosLimit = 0; + p->hashBufPos = p->hashBufPosLimit = 0; + MatchFinder_Init(mf); + p->pointerToCurPos = MatchFinder_GetPointerToCurrentPos(mf); + p->btNumAvailBytes = 0; + p->lzPos = p->historySize + 1; + + p->hash = mf->hash; + p->fixedHashSize = mf->fixedHashSize; + + p->son = mf->son; + p->matchMaxLen = mf->matchMaxLen; + p->numHashBytes = mf->numHashBytes; + p->pos = mf->pos; + p->buffer = mf->buffer; + p->cyclicBufferPos = mf->cyclicBufferPos; + p->cyclicBufferSize = mf->cyclicBufferSize; + p->cutValue = mf->cutValue; +} + +/* ReleaseStream is required to finish multithreading */ +void MatchFinderMt_ReleaseStream(CMatchFinderMt *p) +{ + MtSync_StopWriting(&p->btSync); + /* p->MatchFinder->ReleaseStream(); */ +} + +void MatchFinderMt_Normalize(CMatchFinderMt *p) +{ + MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize); + p->lzPos = p->historySize + 1; +} + +void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p) +{ + UInt32 blockIndex; + MtSync_GetNextBlock(&p->btSync); + blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask); + p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize; + p->btBufPosLimit += p->btBuf[p->btBufPos++]; + p->btNumAvailBytes = p->btBuf[p->btBufPos++]; + if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize) + MatchFinderMt_Normalize(p); +} + +const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p) +{ + return p->pointerToCurPos; +} + +#define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p); + +UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p) +{ + GET_NEXT_BLOCK_IF_REQUIRED; + return p->btNumAvailBytes; +} + +Byte MatchFinderMt_GetIndexByte(CMatchFinderMt *p, Int32 index) +{ + return p->pointerToCurPos[index]; +} + +UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances) +{ + UInt32 hash2Value, curMatch2; + UInt32 *hash = p->hash; + const Byte *cur = p->pointerToCurPos; + UInt32 lzPos = p->lzPos; + MT_HASH2_CALC + + curMatch2 = hash[hash2Value]; + hash[hash2Value] = lzPos; + + if (curMatch2 >= matchMinPos) + if (cur[(size_t)curMatch2 - lzPos] == cur[0]) + { + *distances++ = 2; + *distances++ = lzPos - curMatch2 - 1; + } + return distances; +} + +UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances) +{ + UInt32 hash2Value, hash3Value, curMatch2, curMatch3; + UInt32 *hash = p->hash; + const Byte *cur = p->pointerToCurPos; + UInt32 lzPos = p->lzPos; + MT_HASH3_CALC + + curMatch2 = hash[ hash2Value]; + curMatch3 = hash[kFix3HashSize + hash3Value]; + + hash[ hash2Value] = + hash[kFix3HashSize + hash3Value] = + lzPos; + + if (curMatch2 >= matchMinPos && cur[(size_t)curMatch2 - lzPos] == cur[0]) + { + distances[1] = lzPos - curMatch2 - 1; + if (cur[(size_t)curMatch2 - lzPos + 2] == cur[2]) + { + distances[0] = 3; + return distances + 2; + } + distances[0] = 2; + distances += 2; + } + if (curMatch3 >= matchMinPos && cur[(size_t)curMatch3 - lzPos] == cur[0]) + { + *distances++ = 3; + *distances++ = lzPos - curMatch3 - 1; + } + return distances; +} + +/* +UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances) +{ + UInt32 hash2Value, hash3Value, hash4Value, curMatch2, curMatch3, curMatch4; + UInt32 *hash = p->hash; + const Byte *cur = p->pointerToCurPos; + UInt32 lzPos = p->lzPos; + MT_HASH4_CALC + + curMatch2 = hash[ hash2Value]; + curMatch3 = hash[kFix3HashSize + hash3Value]; + curMatch4 = hash[kFix4HashSize + hash4Value]; + + hash[ hash2Value] = + hash[kFix3HashSize + hash3Value] = + hash[kFix4HashSize + hash4Value] = + lzPos; + + if (curMatch2 >= matchMinPos && cur[(size_t)curMatch2 - lzPos] == cur[0]) + { + distances[1] = lzPos - curMatch2 - 1; + if (cur[(size_t)curMatch2 - lzPos + 2] == cur[2]) + { + distances[0] = (cur[(size_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3; + return distances + 2; + } + distances[0] = 2; + distances += 2; + } + if (curMatch3 >= matchMinPos && cur[(size_t)curMatch3 - lzPos] == cur[0]) + { + distances[1] = lzPos - curMatch3 - 1; + if (cur[(size_t)curMatch3 - lzPos + 3] == cur[3]) + { + distances[0] = 4; + return distances + 2; + } + distances[0] = 3; + distances += 2; + } + + if (curMatch4 >= matchMinPos) + if ( + cur[(size_t)curMatch4 - lzPos] == cur[0] && + cur[(size_t)curMatch4 - lzPos + 3] == cur[3] + ) + { + *distances++ = 4; + *distances++ = lzPos - curMatch4 - 1; + } + return distances; +} +*/ + +#define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++; + +UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances) +{ + const UInt32 *btBuf = p->btBuf + p->btBufPos; + UInt32 len = *btBuf++; + p->btBufPos += 1 + len; + p->btNumAvailBytes--; + { + UInt32 i; + for (i = 0; i < len; i += 2) + { + *distances++ = *btBuf++; + *distances++ = *btBuf++; + } + } + INCREASE_LZ_POS + return len; +} + +UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances) +{ + const UInt32 *btBuf = p->btBuf + p->btBufPos; + UInt32 len = *btBuf++; + p->btBufPos += 1 + len; + + if (len == 0) + { + if (p->btNumAvailBytes-- >= 4) + len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances)); + } + else + { + /* Condition: there are matches in btBuf with length < p->numHashBytes */ + UInt32 *distances2; + p->btNumAvailBytes--; + distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances); + do + { + *distances2++ = *btBuf++; + *distances2++ = *btBuf++; + } + while ((len -= 2) != 0); + len = (UInt32)(distances2 - (distances)); + } + INCREASE_LZ_POS + return len; +} + +#define SKIP_HEADER2 do { GET_NEXT_BLOCK_IF_REQUIRED +#define SKIP_HEADER(n) SKIP_HEADER2 if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash; +#define SKIP_FOOTER } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while(--num != 0); + +void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num) +{ + SKIP_HEADER2 { p->btNumAvailBytes--; + SKIP_FOOTER +} + +void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num) +{ + SKIP_HEADER(2) + UInt32 hash2Value; + MT_HASH2_CALC + hash[hash2Value] = p->lzPos; + SKIP_FOOTER +} + +void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num) +{ + SKIP_HEADER(3) + UInt32 hash2Value, hash3Value; + MT_HASH3_CALC + hash[kFix3HashSize + hash3Value] = + hash[ hash2Value] = + p->lzPos; + SKIP_FOOTER +} + +/* +void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num) +{ + SKIP_HEADER(4) + UInt32 hash2Value, hash3Value, hash4Value; + MT_HASH4_CALC + hash[kFix4HashSize + hash4Value] = + hash[kFix3HashSize + hash3Value] = + hash[ hash2Value] = + p->lzPos; + SKIP_FOOTER +} +*/ + +void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable) +{ + vTable->Init = (Mf_Init_Func)MatchFinderMt_Init; + vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinderMt_GetIndexByte; + vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes; + vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos; + vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches; + switch(p->MatchFinder->numHashBytes) + { + case 2: + p->GetHeadsFunc = GetHeads2; + p->MixMatchesFunc = (Mf_Mix_Matches)0; + vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip; + vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches; + break; + case 3: + p->GetHeadsFunc = GetHeads3; + p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2; + vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip; + break; + default: + /* case 4: */ + p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4; + /* p->GetHeadsFunc = GetHeads4; */ + p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3; + vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip; + break; + /* + default: + p->GetHeadsFunc = GetHeads5; + p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4; + vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip; + break; + */ + } +} diff --git a/C/Compress/Lz/MatchFinderMt.h b/C/Compress/Lz/MatchFinderMt.h new file mode 100755 index 00000000..a99cc45f --- /dev/null +++ b/C/Compress/Lz/MatchFinderMt.h @@ -0,0 +1,97 @@ +/* MatchFinderMt.h */ + +#ifndef __MATCHFINDERMT_H +#define __MATCHFINDERMT_H + +#include "../../Threads.h" +#include "MatchFinder.h" + +#define _LZ_MT + +#define kMtHashBlockSize (1 << 13) +#define kMtHashNumBlocks (1 << 3) +#define kMtHashNumBlocksMask (kMtHashNumBlocks - 1) + +#define kMtBtBlockSize (1 << 14) +#define kMtBtNumBlocks (1 << 6) +#define kMtBtNumBlocksMask (kMtBtNumBlocks - 1) + +typedef struct _CMtSync +{ + Bool wasCreated; + Bool needStart; + Bool exit; + Bool stopWriting; + + CThread thread; + CAutoResetEvent canStart; + CAutoResetEvent wasStarted; + CAutoResetEvent wasStopped; + CSemaphore freeSemaphore; + CSemaphore filledSemaphore; + Bool csWasInitialized; + Bool csWasEntered; + CCriticalSection cs; + UInt32 numProcessedBlocks; +} CMtSync; + +typedef UInt32 * (*Mf_Mix_Matches)(void *p, UInt32 matchMinPos, UInt32 *distances); + +/* kMtCacheLineDummy must be >= size_of_CPU_cache_line */ +#define kMtCacheLineDummy 128 + +typedef void (*Mf_GetHeads)(const Byte *buffer, size_t pos, + UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads); + +typedef struct _CMatchFinderMt +{ + /* LZ */ + const Byte *pointerToCurPos; + UInt32 *btBuf; + UInt32 btBufPos; + UInt32 btBufPosLimit; + UInt32 lzPos; + UInt32 btNumAvailBytes; + + UInt32 *hash; + UInt32 fixedHashSize; + UInt32 historySize; + + Mf_Mix_Matches MixMatchesFunc; + + /* LZ + BT */ + CMtSync btSync; + Byte btDummy[kMtCacheLineDummy]; + + /* BT */ + UInt32 *hashBuf; + UInt32 hashBufPos; + UInt32 hashBufPosLimit; + UInt32 hashNumAvail; + + CLzRef *son; + UInt32 matchMaxLen; + UInt32 numHashBytes; + UInt32 pos; + Byte *buffer; // Pointer to virtual Buffer begin + UInt32 cyclicBufferPos; + UInt32 cyclicBufferSize; // it must be historySize + 1 + UInt32 cutValue; + + /* BT + Hash */ + CMtSync hashSync; + /* Byte hashDummy[kMtCacheLineDummy]; */ + + /* Hash */ + Mf_GetHeads GetHeadsFunc; + CMatchFinder *MatchFinder; +} CMatchFinderMt; + +void MatchFinderMt_Construct(CMatchFinderMt *p); +void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc); +HRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore, + UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc); +void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable); +void MatchFinderMt_ReleaseStream(CMatchFinderMt *p); + +#endif diff --git a/C/Compress/Lzma/LzmaDecode.c b/C/Compress/Lzma/LzmaDecode.c new file mode 100755 index 00000000..cb834537 --- /dev/null +++ b/C/Compress/Lzma/LzmaDecode.c @@ -0,0 +1,584 @@ +/* + LzmaDecode.c + LZMA Decoder (optimized for Speed version) + + LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) + http://www.7-zip.org/ + + LZMA SDK is licensed under two licenses: + 1) GNU Lesser General Public License (GNU LGPL) + 2) Common Public License (CPL) + It means that you can select one of these two licenses and + follow rules of that license. + + SPECIAL EXCEPTION: + Igor Pavlov, as the author of this Code, expressly permits you to + statically or dynamically link your Code (or bind by name) to the + interfaces of this file without subjecting your linked Code to the + terms of the CPL or GNU LGPL. Any modifications or additions + to this file, however, are subject to the LGPL or CPL terms. +*/ + +#include "LzmaDecode.h" + +#define kNumTopBits 24 +#define kTopValue ((UInt32)1 << kNumTopBits) + +#define kNumBitModelTotalBits 11 +#define kBitModelTotal (1 << kNumBitModelTotalBits) +#define kNumMoveBits 5 + +#define RC_READ_BYTE (*Buffer++) + +#define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \ + { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }} + +#ifdef _LZMA_IN_CB + +#define RC_TEST { if (Buffer == BufferLim) \ + { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \ + BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }} + +#define RC_INIT Buffer = BufferLim = 0; RC_INIT2 + +#else + +#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; } + +#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2 + +#endif + +#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; } + +#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound) +#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits; +#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits; + +#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \ + { UpdateBit0(p); mi <<= 1; A0; } else \ + { UpdateBit1(p); mi = (mi + mi) + 1; A1; } + +#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;) + +#define RangeDecoderBitTreeDecode(probs, numLevels, res) \ + { int i = numLevels; res = 1; \ + do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \ + res -= (1 << numLevels); } + + +#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 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) + +#if Literal != LZMA_BASE_SIZE +StopCompilingDueBUG +#endif + +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size) +{ + unsigned char prop0; + if (size < LZMA_PROPERTIES_SIZE) + return LZMA_RESULT_DATA_ERROR; + prop0 = propsData[0]; + if (prop0 >= (9 * 5 * 5)) + return LZMA_RESULT_DATA_ERROR; + { + for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5)); + for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9); + propsRes->lc = prop0; + /* + unsigned char remainder = (unsigned char)(prop0 / 9); + propsRes->lc = prop0 % 9; + propsRes->pb = remainder / 5; + propsRes->lp = remainder % 5; + */ + } + + #ifdef _LZMA_OUT_READ + { + int i; + propsRes->DictionarySize = 0; + for (i = 0; i < 4; i++) + propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8); + if (propsRes->DictionarySize == 0) + propsRes->DictionarySize = 1; + } + #endif + return LZMA_RESULT_OK; +} + +#define kLzmaStreamWasFinishedId (-1) + +int LzmaDecode(CLzmaDecoderState *vs, + #ifdef _LZMA_IN_CB + ILzmaInCallback *InCallback, + #else + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, + #endif + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed) +{ + CProb *p = vs->Probs; + SizeT nowPos = 0; + Byte previousByte = 0; + UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; + UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; + int lc = vs->Properties.lc; + + #ifdef _LZMA_OUT_READ + + UInt32 Range = vs->Range; + UInt32 Code = vs->Code; + #ifdef _LZMA_IN_CB + const Byte *Buffer = vs->Buffer; + const Byte *BufferLim = vs->BufferLim; + #else + const Byte *Buffer = inStream; + const Byte *BufferLim = inStream + inSize; + #endif + int state = vs->State; + UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; + int len = vs->RemainLen; + UInt32 globalPos = vs->GlobalPos; + UInt32 distanceLimit = vs->DistanceLimit; + + Byte *dictionary = vs->Dictionary; + UInt32 dictionarySize = vs->Properties.DictionarySize; + UInt32 dictionaryPos = vs->DictionaryPos; + + Byte tempDictionary[4]; + + #ifndef _LZMA_IN_CB + *inSizeProcessed = 0; + #endif + *outSizeProcessed = 0; + if (len == kLzmaStreamWasFinishedId) + return LZMA_RESULT_OK; + + if (dictionarySize == 0) + { + dictionary = tempDictionary; + dictionarySize = 1; + tempDictionary[0] = vs->TempDictionary[0]; + } + + if (len == kLzmaNeedInitId) + { + { + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); + UInt32 i; + for (i = 0; i < numProbs; i++) + p[i] = kBitModelTotal >> 1; + rep0 = rep1 = rep2 = rep3 = 1; + state = 0; + globalPos = 0; + distanceLimit = 0; + dictionaryPos = 0; + dictionary[dictionarySize - 1] = 0; + #ifdef _LZMA_IN_CB + RC_INIT; + #else + RC_INIT(inStream, inSize); + #endif + } + len = 0; + } + while(len != 0 && nowPos < outSize) + { + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + len--; + } + if (dictionaryPos == 0) + previousByte = dictionary[dictionarySize - 1]; + else + previousByte = dictionary[dictionaryPos - 1]; + + #else /* if !_LZMA_OUT_READ */ + + int state = 0; + UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; + int len = 0; + const Byte *Buffer; + const Byte *BufferLim; + UInt32 Range; + UInt32 Code; + + #ifndef _LZMA_IN_CB + *inSizeProcessed = 0; + #endif + *outSizeProcessed = 0; + + { + UInt32 i; + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); + for (i = 0; i < numProbs; i++) + p[i] = kBitModelTotal >> 1; + } + + #ifdef _LZMA_IN_CB + RC_INIT; + #else + RC_INIT(inStream, inSize); + #endif + + #endif /* _LZMA_OUT_READ */ + + while(nowPos < outSize) + { + CProb *prob; + UInt32 bound; + int posState = (int)( + (nowPos + #ifdef _LZMA_OUT_READ + + globalPos + #endif + ) + & posStateMask); + + prob = p + IsMatch + (state << kNumPosBitsMax) + posState; + IfBit0(prob) + { + int symbol = 1; + UpdateBit0(prob) + prob = p + Literal + (LZMA_LIT_SIZE * + ((( + (nowPos + #ifdef _LZMA_OUT_READ + + globalPos + #endif + ) + & literalPosMask) << lc) + (previousByte >> (8 - lc)))); + + if (state >= kNumLitStates) + { + int matchByte; + #ifdef _LZMA_OUT_READ + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + matchByte = dictionary[pos]; + #else + matchByte = outStream[nowPos - rep0]; + #endif + do + { + int bit; + CProb *probLit; + matchByte <<= 1; + bit = (matchByte & 0x100); + probLit = prob + 0x100 + bit + symbol; + RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break) + } + while (symbol < 0x100); + } + while (symbol < 0x100) + { + CProb *probLit = prob + symbol; + RC_GET_BIT(probLit, symbol) + } + previousByte = (Byte)symbol; + + outStream[nowPos++] = previousByte; + #ifdef _LZMA_OUT_READ + if (distanceLimit < dictionarySize) + distanceLimit++; + + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #endif + if (state < 4) state = 0; + else if (state < 10) state -= 3; + else state -= 6; + } + else + { + UpdateBit1(prob); + prob = p + IsRep + state; + IfBit0(prob) + { + UpdateBit0(prob); + rep3 = rep2; + rep2 = rep1; + rep1 = rep0; + state = state < kNumLitStates ? 0 : 3; + prob = p + LenCoder; + } + else + { + UpdateBit1(prob); + prob = p + IsRepG0 + state; + IfBit0(prob) + { + UpdateBit0(prob); + prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; + IfBit0(prob) + { + #ifdef _LZMA_OUT_READ + UInt32 pos; + #endif + UpdateBit0(prob); + + #ifdef _LZMA_OUT_READ + if (distanceLimit == 0) + #else + if (nowPos == 0) + #endif + return LZMA_RESULT_DATA_ERROR; + + state = state < kNumLitStates ? 9 : 11; + #ifdef _LZMA_OUT_READ + pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #else + previousByte = outStream[nowPos - rep0]; + #endif + outStream[nowPos++] = previousByte; + #ifdef _LZMA_OUT_READ + if (distanceLimit < dictionarySize) + distanceLimit++; + #endif + + continue; + } + else + { + UpdateBit1(prob); + } + } + else + { + UInt32 distance; + UpdateBit1(prob); + prob = p + IsRepG1 + state; + IfBit0(prob) + { + UpdateBit0(prob); + distance = rep1; + } + else + { + UpdateBit1(prob); + prob = p + IsRepG2 + state; + IfBit0(prob) + { + UpdateBit0(prob); + distance = rep2; + } + else + { + UpdateBit1(prob); + distance = rep3; + rep3 = rep2; + } + rep2 = rep1; + } + rep1 = rep0; + rep0 = distance; + } + state = state < kNumLitStates ? 8 : 11; + prob = p + RepLenCoder; + } + { + int numBits, offset; + CProb *probLen = prob + LenChoice; + IfBit0(probLen) + { + UpdateBit0(probLen); + probLen = prob + LenLow + (posState << kLenNumLowBits); + offset = 0; + numBits = kLenNumLowBits; + } + else + { + UpdateBit1(probLen); + probLen = prob + LenChoice2; + IfBit0(probLen) + { + UpdateBit0(probLen); + probLen = prob + LenMid + (posState << kLenNumMidBits); + offset = kLenNumLowSymbols; + numBits = kLenNumMidBits; + } + else + { + UpdateBit1(probLen); + probLen = prob + LenHigh; + offset = kLenNumLowSymbols + kLenNumMidSymbols; + numBits = kLenNumHighBits; + } + } + RangeDecoderBitTreeDecode(probLen, numBits, len); + len += offset; + } + + if (state < 4) + { + int posSlot; + state += kNumLitStates; + prob = p + PosSlot + + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << + kNumPosSlotBits); + RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); + if (posSlot >= kStartPosModelIndex) + { + int numDirectBits = ((posSlot >> 1) - 1); + rep0 = (2 | ((UInt32)posSlot & 1)); + if (posSlot < kEndPosModelIndex) + { + rep0 <<= numDirectBits; + prob = p + SpecPos + rep0 - posSlot - 1; + } + else + { + numDirectBits -= kNumAlignBits; + do + { + RC_NORMALIZE + Range >>= 1; + rep0 <<= 1; + if (Code >= Range) + { + Code -= Range; + rep0 |= 1; + } + } + while (--numDirectBits != 0); + prob = p + Align; + rep0 <<= kNumAlignBits; + numDirectBits = kNumAlignBits; + } + { + int i = 1; + int mi = 1; + do + { + CProb *prob3 = prob + mi; + RC_GET_BIT2(prob3, mi, ; , rep0 |= i); + i <<= 1; + } + while(--numDirectBits != 0); + } + } + else + rep0 = posSlot; + if (++rep0 == (UInt32)(0)) + { + /* it's for stream version */ + len = kLzmaStreamWasFinishedId; + break; + } + } + + len += kMatchMinLen; + #ifdef _LZMA_OUT_READ + if (rep0 > distanceLimit) + #else + if (rep0 > nowPos) + #endif + return LZMA_RESULT_DATA_ERROR; + + #ifdef _LZMA_OUT_READ + if (dictionarySize - distanceLimit > (UInt32)len) + distanceLimit += len; + else + distanceLimit = dictionarySize; + #endif + + do + { + #ifdef _LZMA_OUT_READ + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #else + previousByte = outStream[nowPos - rep0]; + #endif + len--; + outStream[nowPos++] = previousByte; + } + while(len != 0 && nowPos < outSize); + } + } + RC_NORMALIZE; + + #ifdef _LZMA_OUT_READ + vs->Range = Range; + vs->Code = Code; + vs->DictionaryPos = dictionaryPos; + vs->GlobalPos = globalPos + (UInt32)nowPos; + vs->DistanceLimit = distanceLimit; + vs->Reps[0] = rep0; + vs->Reps[1] = rep1; + vs->Reps[2] = rep2; + vs->Reps[3] = rep3; + vs->State = state; + vs->RemainLen = len; + vs->TempDictionary[0] = tempDictionary[0]; + #endif + + #ifdef _LZMA_IN_CB + vs->Buffer = Buffer; + vs->BufferLim = BufferLim; + #else + *inSizeProcessed = (SizeT)(Buffer - inStream); + #endif + *outSizeProcessed = nowPos; + return LZMA_RESULT_OK; +} diff --git a/C/Compress/Lzma/LzmaDecode.h b/C/Compress/Lzma/LzmaDecode.h new file mode 100755 index 00000000..2870eeb9 --- /dev/null +++ b/C/Compress/Lzma/LzmaDecode.h @@ -0,0 +1,113 @@ +/* + LzmaDecode.h + LZMA Decoder interface + + LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) + http://www.7-zip.org/ + + LZMA SDK is licensed under two licenses: + 1) GNU Lesser General Public License (GNU LGPL) + 2) Common Public License (CPL) + It means that you can select one of these two licenses and + follow rules of that license. + + SPECIAL EXCEPTION: + Igor Pavlov, as the author of this code, expressly permits you to + statically or dynamically link your code (or bind by name) to the + interfaces of this file without subjecting your linked code to the + terms of the CPL or GNU LGPL. Any modifications or additions + to this file, however, are subject to the LGPL or CPL terms. +*/ + +#ifndef __LZMADECODE_H +#define __LZMADECODE_H + +#include "LzmaTypes.h" + +/* #define _LZMA_IN_CB */ +/* Use callback for input data */ + +/* #define _LZMA_OUT_READ */ +/* Use read function for output data */ + +/* #define _LZMA_PROB32 */ +/* It can increase speed on some 32-bit CPUs, + but memory usage will be doubled in that case */ + +/* #define _LZMA_LOC_OPT */ +/* Enable local speed optimizations inside code */ + +#ifdef _LZMA_PROB32 +#define CProb UInt32 +#else +#define CProb UInt16 +#endif + +#define LZMA_RESULT_OK 0 +#define LZMA_RESULT_DATA_ERROR 1 + +#ifdef _LZMA_IN_CB +typedef struct _ILzmaInCallback +{ + int (*Read)(void *object, const unsigned char **buffer, SizeT *bufferSize); +} ILzmaInCallback; +#endif + +#define LZMA_BASE_SIZE 1846 +#define LZMA_LIT_SIZE 768 + +#define LZMA_PROPERTIES_SIZE 5 + +typedef struct _CLzmaProperties +{ + int lc; + int lp; + int pb; + #ifdef _LZMA_OUT_READ + UInt32 DictionarySize; + #endif +}CLzmaProperties; + +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size); + +#define LzmaGetNumProbs(Properties) (LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((Properties)->lc + (Properties)->lp))) + +#define kLzmaNeedInitId (-2) + +typedef struct _CLzmaDecoderState +{ + CLzmaProperties Properties; + CProb *Probs; + + #ifdef _LZMA_IN_CB + const unsigned char *Buffer; + const unsigned char *BufferLim; + #endif + + #ifdef _LZMA_OUT_READ + unsigned char *Dictionary; + UInt32 Range; + UInt32 Code; + UInt32 DictionaryPos; + UInt32 GlobalPos; + UInt32 DistanceLimit; + UInt32 Reps[4]; + int State; + int RemainLen; + unsigned char TempDictionary[4]; + #endif +} CLzmaDecoderState; + +#ifdef _LZMA_OUT_READ +#define LzmaDecoderInit(vs) { (vs)->RemainLen = kLzmaNeedInitId; } +#endif + +int LzmaDecode(CLzmaDecoderState *vs, + #ifdef _LZMA_IN_CB + ILzmaInCallback *inCallback, + #else + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, + #endif + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed); + +#endif diff --git a/C/Compress/Lzma/LzmaDecodeSize.c b/C/Compress/Lzma/LzmaDecodeSize.c new file mode 100755 index 00000000..a3a5eb9d --- /dev/null +++ b/C/Compress/Lzma/LzmaDecodeSize.c @@ -0,0 +1,712 @@ +/* + LzmaDecodeSize.c + LZMA Decoder (optimized for Size version) + + LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) + http://www.7-zip.org/ + + LZMA SDK is licensed under two licenses: + 1) GNU Lesser General Public License (GNU LGPL) + 2) Common Public License (CPL) + It means that you can select one of these two licenses and + follow rules of that license. + + SPECIAL EXCEPTION: + Igor Pavlov, as the author of this code, expressly permits you to + statically or dynamically link your code (or bind by name) to the + interfaces of this file without subjecting your linked code to the + terms of the CPL or GNU LGPL. Any modifications or additions + to this file, however, are subject to the LGPL or CPL terms. +*/ + +#include "LzmaDecode.h" + +#define kNumTopBits 24 +#define kTopValue ((UInt32)1 << kNumTopBits) + +#define kNumBitModelTotalBits 11 +#define kBitModelTotal (1 << kNumBitModelTotalBits) +#define kNumMoveBits 5 + +typedef struct _CRangeDecoder +{ + const Byte *Buffer; + const Byte *BufferLim; + UInt32 Range; + UInt32 Code; + #ifdef _LZMA_IN_CB + ILzmaInCallback *InCallback; + int Result; + #endif + int ExtraBytes; +} CRangeDecoder; + +Byte RangeDecoderReadByte(CRangeDecoder *rd) +{ + if (rd->Buffer == rd->BufferLim) + { + #ifdef _LZMA_IN_CB + SizeT size; + rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size); + rd->BufferLim = rd->Buffer + size; + if (size == 0) + #endif + { + rd->ExtraBytes = 1; + return 0xFF; + } + } + return (*rd->Buffer++); +} + +/* #define ReadByte (*rd->Buffer++) */ +#define ReadByte (RangeDecoderReadByte(rd)) + +void RangeDecoderInit(CRangeDecoder *rd + #ifndef _LZMA_IN_CB + , const Byte *stream, SizeT bufferSize + #endif + ) +{ + int i; + #ifdef _LZMA_IN_CB + rd->Buffer = rd->BufferLim = 0; + #else + rd->Buffer = stream; + rd->BufferLim = stream + bufferSize; + #endif + rd->ExtraBytes = 0; + rd->Code = 0; + rd->Range = (0xFFFFFFFF); + for(i = 0; i < 5; i++) + rd->Code = (rd->Code << 8) | ReadByte; +} + +#define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code; +#define RC_FLUSH_VAR rd->Range = range; rd->Code = code; +#define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; } + +UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits) +{ + RC_INIT_VAR + UInt32 result = 0; + int i; + for (i = numTotalBits; i != 0; i--) + { + /* UInt32 t; */ + range >>= 1; + + result <<= 1; + if (code >= range) + { + code -= range; + result |= 1; + } + /* + t = (code - range) >> 31; + t &= 1; + code -= range & (t - 1); + result = (result + result) | (1 - t); + */ + RC_NORMALIZE + } + RC_FLUSH_VAR + return result; +} + +int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd) +{ + UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob; + if (rd->Code < bound) + { + rd->Range = bound; + *prob += (kBitModelTotal - *prob) >> kNumMoveBits; + if (rd->Range < kTopValue) + { + rd->Code = (rd->Code << 8) | ReadByte; + rd->Range <<= 8; + } + return 0; + } + else + { + rd->Range -= bound; + rd->Code -= bound; + *prob -= (*prob) >> kNumMoveBits; + if (rd->Range < kTopValue) + { + rd->Code = (rd->Code << 8) | ReadByte; + rd->Range <<= 8; + } + return 1; + } +} + +#define RC_GET_BIT2(prob, mi, A0, A1) \ + UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \ + if (code < bound) \ + { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \ + else \ + { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \ + RC_NORMALIZE + +#define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;) + +int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd) +{ + int mi = 1; + int i; + #ifdef _LZMA_LOC_OPT + RC_INIT_VAR + #endif + for(i = numLevels; i != 0; i--) + { + #ifdef _LZMA_LOC_OPT + CProb *prob = probs + mi; + RC_GET_BIT(prob, mi) + #else + mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd); + #endif + } + #ifdef _LZMA_LOC_OPT + RC_FLUSH_VAR + #endif + return mi - (1 << numLevels); +} + +int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd) +{ + int mi = 1; + int i; + int symbol = 0; + #ifdef _LZMA_LOC_OPT + RC_INIT_VAR + #endif + for(i = 0; i < numLevels; i++) + { + #ifdef _LZMA_LOC_OPT + CProb *prob = probs + mi; + RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i)) + #else + int bit = RangeDecoderBitDecode(probs + mi, rd); + mi = mi + mi + bit; + symbol |= (bit << i); + #endif + } + #ifdef _LZMA_LOC_OPT + RC_FLUSH_VAR + #endif + return symbol; +} + +Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd) +{ + int symbol = 1; + #ifdef _LZMA_LOC_OPT + RC_INIT_VAR + #endif + do + { + #ifdef _LZMA_LOC_OPT + CProb *prob = probs + symbol; + RC_GET_BIT(prob, symbol) + #else + symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd); + #endif + } + while (symbol < 0x100); + #ifdef _LZMA_LOC_OPT + RC_FLUSH_VAR + #endif + return symbol; +} + +Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte) +{ + int symbol = 1; + #ifdef _LZMA_LOC_OPT + RC_INIT_VAR + #endif + do + { + int bit; + int matchBit = (matchByte >> 7) & 1; + matchByte <<= 1; + #ifdef _LZMA_LOC_OPT + { + CProb *prob = probs + 0x100 + (matchBit << 8) + symbol; + RC_GET_BIT2(prob, symbol, bit = 0, bit = 1) + } + #else + bit = RangeDecoderBitDecode(probs + 0x100 + (matchBit << 8) + symbol, rd); + symbol = (symbol << 1) | bit; + #endif + if (matchBit != bit) + { + while (symbol < 0x100) + { + #ifdef _LZMA_LOC_OPT + CProb *prob = probs + symbol; + RC_GET_BIT(prob, symbol) + #else + symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd); + #endif + } + break; + } + } + while (symbol < 0x100); + #ifdef _LZMA_LOC_OPT + RC_FLUSH_VAR + #endif + return symbol; +} + +#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) + +int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState) +{ + if(RangeDecoderBitDecode(p + LenChoice, rd) == 0) + return RangeDecoderBitTreeDecode(p + LenLow + + (posState << kLenNumLowBits), kLenNumLowBits, rd); + if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0) + return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid + + (posState << kLenNumMidBits), kLenNumMidBits, rd); + return kLenNumLowSymbols + kLenNumMidSymbols + + RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd); +} + +#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 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) + +#if Literal != LZMA_BASE_SIZE +StopCompilingDueBUG +#endif + +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size) +{ + unsigned char prop0; + if (size < LZMA_PROPERTIES_SIZE) + return LZMA_RESULT_DATA_ERROR; + prop0 = propsData[0]; + if (prop0 >= (9 * 5 * 5)) + return LZMA_RESULT_DATA_ERROR; + { + for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5)); + for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9); + propsRes->lc = prop0; + /* + unsigned char remainder = (unsigned char)(prop0 / 9); + propsRes->lc = prop0 % 9; + propsRes->pb = remainder / 5; + propsRes->lp = remainder % 5; + */ + } + + #ifdef _LZMA_OUT_READ + { + int i; + propsRes->DictionarySize = 0; + for (i = 0; i < 4; i++) + propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8); + if (propsRes->DictionarySize == 0) + propsRes->DictionarySize = 1; + } + #endif + return LZMA_RESULT_OK; +} + +#define kLzmaStreamWasFinishedId (-1) + +int LzmaDecode(CLzmaDecoderState *vs, + #ifdef _LZMA_IN_CB + ILzmaInCallback *InCallback, + #else + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, + #endif + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed) +{ + CProb *p = vs->Probs; + SizeT nowPos = 0; + Byte previousByte = 0; + UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; + UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; + int lc = vs->Properties.lc; + CRangeDecoder rd; + + #ifdef _LZMA_OUT_READ + + int state = vs->State; + UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; + int len = vs->RemainLen; + UInt32 globalPos = vs->GlobalPos; + UInt32 distanceLimit = vs->DistanceLimit; + + Byte *dictionary = vs->Dictionary; + UInt32 dictionarySize = vs->Properties.DictionarySize; + UInt32 dictionaryPos = vs->DictionaryPos; + + Byte tempDictionary[4]; + + rd.Range = vs->Range; + rd.Code = vs->Code; + #ifdef _LZMA_IN_CB + rd.InCallback = InCallback; + rd.Buffer = vs->Buffer; + rd.BufferLim = vs->BufferLim; + #else + rd.Buffer = inStream; + rd.BufferLim = inStream + inSize; + #endif + + #ifndef _LZMA_IN_CB + *inSizeProcessed = 0; + #endif + *outSizeProcessed = 0; + if (len == kLzmaStreamWasFinishedId) + return LZMA_RESULT_OK; + + if (dictionarySize == 0) + { + dictionary = tempDictionary; + dictionarySize = 1; + tempDictionary[0] = vs->TempDictionary[0]; + } + + if (len == kLzmaNeedInitId) + { + { + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); + UInt32 i; + for (i = 0; i < numProbs; i++) + p[i] = kBitModelTotal >> 1; + rep0 = rep1 = rep2 = rep3 = 1; + state = 0; + globalPos = 0; + distanceLimit = 0; + dictionaryPos = 0; + dictionary[dictionarySize - 1] = 0; + RangeDecoderInit(&rd + #ifndef _LZMA_IN_CB + , inStream, inSize + #endif + ); + #ifdef _LZMA_IN_CB + if (rd.Result != LZMA_RESULT_OK) + return rd.Result; + #endif + if (rd.ExtraBytes != 0) + return LZMA_RESULT_DATA_ERROR; + } + len = 0; + } + while(len != 0 && nowPos < outSize) + { + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + len--; + } + if (dictionaryPos == 0) + previousByte = dictionary[dictionarySize - 1]; + else + previousByte = dictionary[dictionaryPos - 1]; + + #ifdef _LZMA_IN_CB + rd.Result = LZMA_RESULT_OK; + #endif + rd.ExtraBytes = 0; + + #else /* if !_LZMA_OUT_READ */ + + int state = 0; + UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; + int len = 0; + + #ifndef _LZMA_IN_CB + *inSizeProcessed = 0; + #endif + *outSizeProcessed = 0; + + { + UInt32 i; + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); + for (i = 0; i < numProbs; i++) + p[i] = kBitModelTotal >> 1; + } + + #ifdef _LZMA_IN_CB + rd.InCallback = InCallback; + #endif + RangeDecoderInit(&rd + #ifndef _LZMA_IN_CB + , inStream, inSize + #endif + ); + + #ifdef _LZMA_IN_CB + if (rd.Result != LZMA_RESULT_OK) + return rd.Result; + #endif + if (rd.ExtraBytes != 0) + return LZMA_RESULT_DATA_ERROR; + + #endif /* _LZMA_OUT_READ */ + + + while(nowPos < outSize) + { + int posState = (int)( + (nowPos + #ifdef _LZMA_OUT_READ + + globalPos + #endif + ) + & posStateMask); + #ifdef _LZMA_IN_CB + if (rd.Result != LZMA_RESULT_OK) + return rd.Result; + #endif + if (rd.ExtraBytes != 0) + return LZMA_RESULT_DATA_ERROR; + if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0) + { + CProb *probs = p + Literal + (LZMA_LIT_SIZE * + ((( + (nowPos + #ifdef _LZMA_OUT_READ + + globalPos + #endif + ) + & literalPosMask) << lc) + (previousByte >> (8 - lc)))); + + if (state >= kNumLitStates) + { + Byte matchByte; + #ifdef _LZMA_OUT_READ + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + matchByte = dictionary[pos]; + #else + matchByte = outStream[nowPos - rep0]; + #endif + previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte); + } + else + previousByte = LzmaLiteralDecode(probs, &rd); + outStream[nowPos++] = previousByte; + #ifdef _LZMA_OUT_READ + if (distanceLimit < dictionarySize) + distanceLimit++; + + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #endif + if (state < 4) state = 0; + else if (state < 10) state -= 3; + else state -= 6; + } + else + { + if (RangeDecoderBitDecode(p + IsRep + state, &rd) == 1) + { + if (RangeDecoderBitDecode(p + IsRepG0 + state, &rd) == 0) + { + if (RangeDecoderBitDecode(p + IsRep0Long + (state << kNumPosBitsMax) + posState, &rd) == 0) + { + #ifdef _LZMA_OUT_READ + UInt32 pos; + #endif + + #ifdef _LZMA_OUT_READ + if (distanceLimit == 0) + #else + if (nowPos == 0) + #endif + return LZMA_RESULT_DATA_ERROR; + + state = state < 7 ? 9 : 11; + #ifdef _LZMA_OUT_READ + pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #else + previousByte = outStream[nowPos - rep0]; + #endif + outStream[nowPos++] = previousByte; + + #ifdef _LZMA_OUT_READ + if (distanceLimit < dictionarySize) + distanceLimit++; + #endif + continue; + } + } + else + { + UInt32 distance; + if(RangeDecoderBitDecode(p + IsRepG1 + state, &rd) == 0) + distance = rep1; + else + { + if(RangeDecoderBitDecode(p + IsRepG2 + state, &rd) == 0) + distance = rep2; + else + { + distance = rep3; + rep3 = rep2; + } + rep2 = rep1; + } + rep1 = rep0; + rep0 = distance; + } + len = LzmaLenDecode(p + RepLenCoder, &rd, posState); + state = state < 7 ? 8 : 11; + } + else + { + int posSlot; + rep3 = rep2; + rep2 = rep1; + rep1 = rep0; + state = state < 7 ? 7 : 10; + len = LzmaLenDecode(p + LenCoder, &rd, posState); + posSlot = RangeDecoderBitTreeDecode(p + PosSlot + + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << + kNumPosSlotBits), kNumPosSlotBits, &rd); + if (posSlot >= kStartPosModelIndex) + { + int numDirectBits = ((posSlot >> 1) - 1); + rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits); + if (posSlot < kEndPosModelIndex) + { + rep0 += RangeDecoderReverseBitTreeDecode( + p + SpecPos + rep0 - posSlot - 1, numDirectBits, &rd); + } + else + { + rep0 += RangeDecoderDecodeDirectBits(&rd, + numDirectBits - kNumAlignBits) << kNumAlignBits; + rep0 += RangeDecoderReverseBitTreeDecode(p + Align, kNumAlignBits, &rd); + } + } + else + rep0 = posSlot; + if (++rep0 == (UInt32)(0)) + { + /* it's for stream version */ + len = kLzmaStreamWasFinishedId; + break; + } + } + + len += kMatchMinLen; + #ifdef _LZMA_OUT_READ + if (rep0 > distanceLimit) + #else + if (rep0 > nowPos) + #endif + return LZMA_RESULT_DATA_ERROR; + + #ifdef _LZMA_OUT_READ + if (dictionarySize - distanceLimit > (UInt32)len) + distanceLimit += len; + else + distanceLimit = dictionarySize; + #endif + + do + { + #ifdef _LZMA_OUT_READ + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #else + previousByte = outStream[nowPos - rep0]; + #endif + len--; + outStream[nowPos++] = previousByte; + } + while(len != 0 && nowPos < outSize); + } + } + + + #ifdef _LZMA_OUT_READ + vs->Range = rd.Range; + vs->Code = rd.Code; + vs->DictionaryPos = dictionaryPos; + vs->GlobalPos = globalPos + (UInt32)nowPos; + vs->DistanceLimit = distanceLimit; + vs->Reps[0] = rep0; + vs->Reps[1] = rep1; + vs->Reps[2] = rep2; + vs->Reps[3] = rep3; + vs->State = state; + vs->RemainLen = len; + vs->TempDictionary[0] = tempDictionary[0]; + #endif + + #ifdef _LZMA_IN_CB + vs->Buffer = rd.Buffer; + vs->BufferLim = rd.BufferLim; + #else + *inSizeProcessed = (SizeT)(rd.Buffer - inStream); + #endif + *outSizeProcessed = nowPos; + return LZMA_RESULT_OK; +} diff --git a/C/Compress/Lzma/LzmaStateDecode.c b/C/Compress/Lzma/LzmaStateDecode.c new file mode 100755 index 00000000..e50f88b5 --- /dev/null +++ b/C/Compress/Lzma/LzmaStateDecode.c @@ -0,0 +1,521 @@ +/* + LzmaStateDecode.c + LZMA Decoder (State version) + + LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) + http://www.7-zip.org/ + + LZMA SDK is licensed under two licenses: + 1) GNU Lesser General Public License (GNU LGPL) + 2) Common Public License (CPL) + It means that you can select one of these two licenses and + follow rules of that license. + + SPECIAL EXCEPTION: + Igor Pavlov, as the author of this Code, expressly permits you to + statically or dynamically link your Code (or bind by name) to the + interfaces of this file without subjecting your linked Code to the + terms of the CPL or GNU LGPL. Any modifications or additions + to this file, however, are subject to the LGPL or CPL terms. +*/ + +#include "LzmaStateDecode.h" + +#define kNumTopBits 24 +#define kTopValue ((UInt32)1 << kNumTopBits) + +#define kNumBitModelTotalBits 11 +#define kBitModelTotal (1 << kNumBitModelTotalBits) +#define kNumMoveBits 5 + +#define RC_READ_BYTE (*Buffer++) + +#define RC_INIT Code = 0; Range = 0xFFFFFFFF; \ + { int i; for(i = 0; i < 5; i++) { Code = (Code << 8) | RC_READ_BYTE; }} + +#define RC_NORMALIZE if (Range < kTopValue) { Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; } + +#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound) +#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits; +#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits; + +#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \ + { UpdateBit0(p); mi <<= 1; A0; } else \ + { UpdateBit1(p); mi = (mi + mi) + 1; A1; } + +#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;) + +#define RangeDecoderBitTreeDecode(probs, numLevels, res) \ + { int i = numLevels; res = 1; \ + do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \ + res -= (1 << numLevels); } + + +#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 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) + +#if Literal != LZMA_BASE_SIZE +StopCompilingDueBUG +#endif + +/* kRequiredInBufferSize = number of required input bytes for worst case: + longest match with longest distance. + kLzmaInBufferSize must be larger than kRequiredInBufferSize + 23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4(align) + 1 (RC_NORMALIZE) +*/ + +#define kRequiredInBufferSize ((23 * (kNumBitModelTotalBits - kNumMoveBits + 1) + 26 + 9) / 8) + +#define kLzmaStreamWasFinishedId (-1) + +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size) +{ + unsigned char prop0; + if (size < LZMA_PROPERTIES_SIZE) + return LZMA_RESULT_DATA_ERROR; + prop0 = propsData[0]; + if (prop0 >= (9 * 5 * 5)) + return LZMA_RESULT_DATA_ERROR; + { + for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5)); + for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9); + propsRes->lc = prop0; + /* + unsigned char remainder = (unsigned char)(prop0 / 9); + propsRes->lc = prop0 % 9; + propsRes->pb = remainder / 5; + propsRes->lp = remainder % 5; + */ + } + + { + int i; + propsRes->DictionarySize = 0; + for (i = 0; i < 4; i++) + propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8); + if (propsRes->DictionarySize == 0) + propsRes->DictionarySize = 1; + return LZMA_RESULT_OK; + } +} + +int LzmaDecode( + CLzmaDecoderState *vs, + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed, + int finishDecoding) +{ + UInt32 Range = vs->Range; + UInt32 Code = vs->Code; + + unsigned char *Buffer = vs->Buffer; + int BufferSize = vs->BufferSize; /* don't change it to unsigned int */ + CProb *p = vs->Probs; + + int state = vs->State; + unsigned char previousByte; + UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; + SizeT nowPos = 0; + UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; + UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; + int lc = vs->Properties.lc; + int len = vs->RemainLen; + UInt32 globalPos = vs->GlobalPos; + UInt32 distanceLimit = vs->DistanceLimit; + + unsigned char *dictionary = vs->Dictionary; + UInt32 dictionarySize = vs->Properties.DictionarySize; + UInt32 dictionaryPos = vs->DictionaryPos; + + unsigned char tempDictionary[4]; + + (*inSizeProcessed) = 0; + (*outSizeProcessed) = 0; + if (len == kLzmaStreamWasFinishedId) + return LZMA_RESULT_OK; + + if (dictionarySize == 0) + { + dictionary = tempDictionary; + dictionarySize = 1; + tempDictionary[0] = vs->TempDictionary[0]; + } + + if (len == kLzmaNeedInitId) + { + while (inSize > 0 && BufferSize < kLzmaInBufferSize) + { + Buffer[BufferSize++] = *inStream++; + (*inSizeProcessed)++; + inSize--; + } + if (BufferSize < 5) + { + vs->BufferSize = BufferSize; + return finishDecoding ? LZMA_RESULT_DATA_ERROR : LZMA_RESULT_OK; + } + { + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); + UInt32 i; + for (i = 0; i < numProbs; i++) + p[i] = kBitModelTotal >> 1; + rep0 = rep1 = rep2 = rep3 = 1; + state = 0; + globalPos = 0; + distanceLimit = 0; + dictionaryPos = 0; + dictionary[dictionarySize - 1] = 0; + RC_INIT; + } + len = 0; + } + while(len != 0 && nowPos < outSize) + { + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + len--; + } + if (dictionaryPos == 0) + previousByte = dictionary[dictionarySize - 1]; + else + previousByte = dictionary[dictionaryPos - 1]; + + while(1) + { + int bufferPos = (int)(Buffer - vs->Buffer); + if (BufferSize - bufferPos < kRequiredInBufferSize) + { + int i; + BufferSize -= bufferPos; + if (BufferSize < 0) + return LZMA_RESULT_DATA_ERROR; + for (i = 0; i < BufferSize; i++) + vs->Buffer[i] = Buffer[i]; + Buffer = vs->Buffer; + while (inSize > 0 && BufferSize < kLzmaInBufferSize) + { + Buffer[BufferSize++] = *inStream++; + (*inSizeProcessed)++; + inSize--; + } + if (BufferSize < kRequiredInBufferSize && !finishDecoding) + break; + } + if (nowPos >= outSize) + break; + { + CProb *prob; + UInt32 bound; + int posState = (int)((nowPos + globalPos) & posStateMask); + + prob = p + IsMatch + (state << kNumPosBitsMax) + posState; + IfBit0(prob) + { + int symbol = 1; + UpdateBit0(prob) + prob = p + Literal + (LZMA_LIT_SIZE * + ((((nowPos + globalPos)& literalPosMask) << lc) + (previousByte >> (8 - lc)))); + + if (state >= kNumLitStates) + { + int matchByte; + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + matchByte = dictionary[pos]; + do + { + int bit; + CProb *probLit; + matchByte <<= 1; + bit = (matchByte & 0x100); + probLit = prob + 0x100 + bit + symbol; + RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break) + } + while (symbol < 0x100); + } + while (symbol < 0x100) + { + CProb *probLit = prob + symbol; + RC_GET_BIT(probLit, symbol) + } + previousByte = (unsigned char)symbol; + + outStream[nowPos++] = previousByte; + if (distanceLimit < dictionarySize) + distanceLimit++; + + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + if (state < 4) state = 0; + else if (state < 10) state -= 3; + else state -= 6; + } + else + { + UpdateBit1(prob); + prob = p + IsRep + state; + IfBit0(prob) + { + UpdateBit0(prob); + rep3 = rep2; + rep2 = rep1; + rep1 = rep0; + state = state < kNumLitStates ? 0 : 3; + prob = p + LenCoder; + } + else + { + UpdateBit1(prob); + prob = p + IsRepG0 + state; + IfBit0(prob) + { + UpdateBit0(prob); + prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; + IfBit0(prob) + { + UInt32 pos; + UpdateBit0(prob); + if (distanceLimit == 0) + return LZMA_RESULT_DATA_ERROR; + if (distanceLimit < dictionarySize) + distanceLimit++; + state = state < kNumLitStates ? 9 : 11; + pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + outStream[nowPos++] = previousByte; + continue; + } + else + { + UpdateBit1(prob); + } + } + else + { + UInt32 distance; + UpdateBit1(prob); + prob = p + IsRepG1 + state; + IfBit0(prob) + { + UpdateBit0(prob); + distance = rep1; + } + else + { + UpdateBit1(prob); + prob = p + IsRepG2 + state; + IfBit0(prob) + { + UpdateBit0(prob); + distance = rep2; + } + else + { + UpdateBit1(prob); + distance = rep3; + rep3 = rep2; + } + rep2 = rep1; + } + rep1 = rep0; + rep0 = distance; + } + state = state < kNumLitStates ? 8 : 11; + prob = p + RepLenCoder; + } + { + int numBits, offset; + CProb *probLen = prob + LenChoice; + IfBit0(probLen) + { + UpdateBit0(probLen); + probLen = prob + LenLow + (posState << kLenNumLowBits); + offset = 0; + numBits = kLenNumLowBits; + } + else + { + UpdateBit1(probLen); + probLen = prob + LenChoice2; + IfBit0(probLen) + { + UpdateBit0(probLen); + probLen = prob + LenMid + (posState << kLenNumMidBits); + offset = kLenNumLowSymbols; + numBits = kLenNumMidBits; + } + else + { + UpdateBit1(probLen); + probLen = prob + LenHigh; + offset = kLenNumLowSymbols + kLenNumMidSymbols; + numBits = kLenNumHighBits; + } + } + RangeDecoderBitTreeDecode(probLen, numBits, len); + len += offset; + } + + if (state < 4) + { + int posSlot; + state += kNumLitStates; + prob = p + PosSlot + + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << + kNumPosSlotBits); + RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); + if (posSlot >= kStartPosModelIndex) + { + int numDirectBits = ((posSlot >> 1) - 1); + rep0 = (2 | ((UInt32)posSlot & 1)); + if (posSlot < kEndPosModelIndex) + { + rep0 <<= numDirectBits; + prob = p + SpecPos + rep0 - posSlot - 1; + } + else + { + numDirectBits -= kNumAlignBits; + do + { + RC_NORMALIZE + Range >>= 1; + rep0 <<= 1; + if (Code >= Range) + { + Code -= Range; + rep0 |= 1; + } + } + while (--numDirectBits != 0); + prob = p + Align; + rep0 <<= kNumAlignBits; + numDirectBits = kNumAlignBits; + } + { + int i = 1; + int mi = 1; + do + { + CProb *prob3 = prob + mi; + RC_GET_BIT2(prob3, mi, ; , rep0 |= i); + i <<= 1; + } + while(--numDirectBits != 0); + } + } + else + rep0 = posSlot; + if (++rep0 == (UInt32)(0)) + { + /* it's for stream version */ + len = kLzmaStreamWasFinishedId; + break; + } + } + + len += kMatchMinLen; + if (rep0 > distanceLimit) + return LZMA_RESULT_DATA_ERROR; + if (dictionarySize - distanceLimit > (UInt32)len) + distanceLimit += len; + else + distanceLimit = dictionarySize; + + do + { + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + len--; + outStream[nowPos++] = previousByte; + } + while(len != 0 && nowPos < outSize); + } + } + } + RC_NORMALIZE; + + BufferSize -= (int)(Buffer - vs->Buffer); + if (BufferSize < 0) + return LZMA_RESULT_DATA_ERROR; + { + int i; + for (i = 0; i < BufferSize; i++) + vs->Buffer[i] = Buffer[i]; + } + vs->BufferSize = BufferSize; + vs->Range = Range; + vs->Code = Code; + vs->DictionaryPos = dictionaryPos; + vs->GlobalPos = (UInt32)(globalPos + nowPos); + vs->DistanceLimit = distanceLimit; + vs->Reps[0] = rep0; + vs->Reps[1] = rep1; + vs->Reps[2] = rep2; + vs->Reps[3] = rep3; + vs->State = state; + vs->RemainLen = len; + vs->TempDictionary[0] = tempDictionary[0]; + + (*outSizeProcessed) = nowPos; + return LZMA_RESULT_OK; +} diff --git a/C/Compress/Lzma/LzmaStateDecode.h b/C/Compress/Lzma/LzmaStateDecode.h new file mode 100755 index 00000000..26490d61 --- /dev/null +++ b/C/Compress/Lzma/LzmaStateDecode.h @@ -0,0 +1,96 @@ +/* + LzmaStateDecode.h + LZMA Decoder interface (State version) + + LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) + http://www.7-zip.org/ + + LZMA SDK is licensed under two licenses: + 1) GNU Lesser General Public License (GNU LGPL) + 2) Common Public License (CPL) + It means that you can select one of these two licenses and + follow rules of that license. + + SPECIAL EXCEPTION: + Igor Pavlov, as the author of this code, expressly permits you to + statically or dynamically link your code (or bind by name) to the + interfaces of this file without subjecting your linked code to the + terms of the CPL or GNU LGPL. Any modifications or additions + to this file, however, are subject to the LGPL or CPL terms. +*/ + +#ifndef __LZMASTATEDECODE_H +#define __LZMASTATEDECODE_H + +#include "LzmaTypes.h" + +/* #define _LZMA_PROB32 */ +/* It can increase speed on some 32-bit CPUs, + but memory usage will be doubled in that case */ + +#ifdef _LZMA_PROB32 +#define CProb UInt32 +#else +#define CProb UInt16 +#endif + +#define LZMA_RESULT_OK 0 +#define LZMA_RESULT_DATA_ERROR 1 + +#define LZMA_BASE_SIZE 1846 +#define LZMA_LIT_SIZE 768 + +#define LZMA_PROPERTIES_SIZE 5 + +typedef struct _CLzmaProperties +{ + int lc; + int lp; + int pb; + UInt32 DictionarySize; +}CLzmaProperties; + +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size); + +#define LzmaGetNumProbs(lzmaProps) (LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((lzmaProps)->lc + (lzmaProps)->lp))) + +#define kLzmaInBufferSize 64 /* don't change it. it must be larger than kRequiredInBufferSize */ + +#define kLzmaNeedInitId (-2) + +typedef struct _CLzmaDecoderState +{ + CLzmaProperties Properties; + CProb *Probs; + unsigned char *Dictionary; + + unsigned char Buffer[kLzmaInBufferSize]; + int BufferSize; + + UInt32 Range; + UInt32 Code; + UInt32 DictionaryPos; + UInt32 GlobalPos; + UInt32 DistanceLimit; + UInt32 Reps[4]; + int State; + int RemainLen; /* -2: decoder needs internal initialization + -1: stream was finished, + 0: ok + > 0: need to write RemainLen bytes as match Reps[0], + */ + unsigned char TempDictionary[4]; /* it's required when DictionarySize = 0 */ +} CLzmaDecoderState; + +#define LzmaDecoderInit(vs) { (vs)->RemainLen = kLzmaNeedInitId; (vs)->BufferSize = 0; } + +/* LzmaDecode: decoding from input stream to output stream. + If finishDecoding != 0, then there are no more bytes in input stream + after inStream[inSize - 1]. */ + +int LzmaDecode(CLzmaDecoderState *vs, + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed, + int finishDecoding); + +#endif diff --git a/C/Compress/Lzma/LzmaStateTest.c b/C/Compress/Lzma/LzmaStateTest.c new file mode 100755 index 00000000..5df4e438 --- /dev/null +++ b/C/Compress/Lzma/LzmaStateTest.c @@ -0,0 +1,195 @@ +/* +LzmaStateTest.c +Test application for LZMA Decoder (State version) + +This file written and distributed to public domain by Igor Pavlov. +This file is part of LZMA SDK 4.26 (2005-08-02) +*/ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "LzmaStateDecode.h" + +const char *kCantReadMessage = "Can not read input file"; +const char *kCantWriteMessage = "Can not write output file"; +const char *kCantAllocateMessage = "Can not allocate memory"; + +#define kInBufferSize (1 << 15) +#define kOutBufferSize (1 << 15) + +unsigned char g_InBuffer[kInBufferSize]; +unsigned char g_OutBuffer[kOutBufferSize]; + +size_t MyReadFile(FILE *file, void *data, size_t size) + { return fread(data, 1, size, file); } + +int MyReadFileAndCheck(FILE *file, void *data, size_t size) + { return (MyReadFile(file, data, size) == size); } + +int PrintError(char *buffer, const char *message) +{ + sprintf(buffer + strlen(buffer), "\nError: "); + sprintf(buffer + strlen(buffer), message); + return 1; +} + +int main3(FILE *inFile, FILE *outFile, char *rs) +{ + /* We use two 32-bit integers to construct 64-bit integer for file size. + You can remove outSizeHigh, if you don't need >= 4GB supporting, + or you can use UInt64 outSize, if your compiler supports 64-bit integers*/ + UInt32 outSize = 0; + UInt32 outSizeHigh = 0; + + int waitEOS = 1; + /* waitEOS = 1, if there is no uncompressed size in headers, + so decoder will wait EOS (End of Stream Marker) in compressed stream */ + + int i; + int res = 0; + CLzmaDecoderState state; /* it's about 140 bytes structure, if int is 32-bit */ + unsigned char properties[LZMA_PROPERTIES_SIZE]; + SizeT inAvail = 0; + unsigned char *inBuffer = 0; + + if (sizeof(UInt32) < 4) + return PrintError(rs, "LZMA decoder needs correct UInt32"); + + /* Read LZMA properties for compressed stream */ + + if (!MyReadFileAndCheck(inFile, properties, sizeof(properties))) + return PrintError(rs, kCantReadMessage); + + /* Read uncompressed size */ + + for (i = 0; i < 8; i++) + { + unsigned char b; + if (!MyReadFileAndCheck(inFile, &b, 1)) + return PrintError(rs, kCantReadMessage); + if (b != 0xFF) + waitEOS = 0; + if (i < 4) + outSize += (UInt32)(b) << (i * 8); + else + outSizeHigh += (UInt32)(b) << ((i - 4) * 8); + } + + /* Decode LZMA properties and allocate memory */ + + if (LzmaDecodeProperties(&state.Properties, properties, LZMA_PROPERTIES_SIZE) != LZMA_RESULT_OK) + return PrintError(rs, "Incorrect stream properties"); + state.Probs = (CProb *)malloc(LzmaGetNumProbs(&state.Properties) * sizeof(CProb)); + if (state.Probs == 0) + return PrintError(rs, kCantAllocateMessage); + + if (state.Properties.DictionarySize == 0) + state.Dictionary = 0; + else + { + state.Dictionary = (unsigned char *)malloc(state.Properties.DictionarySize); + if (state.Dictionary == 0) + { + free(state.Probs); + return PrintError(rs, kCantAllocateMessage); + } + } + + /* Decompress */ + + LzmaDecoderInit(&state); + + do + { + SizeT inProcessed, outProcessed; + int finishDecoding; + UInt32 outAvail = kOutBufferSize; + if (!waitEOS && outSizeHigh == 0 && outAvail > outSize) + outAvail = outSize; + if (inAvail == 0) + { + inAvail = (SizeT)MyReadFile(inFile, g_InBuffer, kInBufferSize); + inBuffer = g_InBuffer; + } + finishDecoding = (inAvail == 0); + res = LzmaDecode(&state, + inBuffer, inAvail, &inProcessed, + g_OutBuffer, outAvail, &outProcessed, + finishDecoding); + if (res != 0) + { + sprintf(rs + strlen(rs), "\nDecoding error = %d\n", res); + res = 1; + break; + } + inAvail -= inProcessed; + inBuffer += inProcessed; + + if (outFile != 0) + if (fwrite(g_OutBuffer, 1, outProcessed, outFile) != outProcessed) + { + PrintError(rs, kCantWriteMessage); + res = 1; + break; + } + + if (outSize < outProcessed) + outSizeHigh--; + outSize -= (UInt32)outProcessed; + outSize &= 0xFFFFFFFF; + + if (outProcessed == 0 && finishDecoding) + { + if (!waitEOS && (outSize != 0 || outSizeHigh != 0)) + res = 1; + break; + } + } + while ((outSize != 0 && outSizeHigh == 0) || outSizeHigh != 0 || waitEOS); + + free(state.Dictionary); + free(state.Probs); + return res; +} + +int main2(int numArgs, const char *args[], char *rs) +{ + FILE *inFile = 0; + FILE *outFile = 0; + int res; + + sprintf(rs + strlen(rs), "\nLZMA Decoder 4.26 Copyright (c) 1999-2005 Igor Pavlov 2005-08-02\n"); + if (numArgs < 2 || numArgs > 3) + { + sprintf(rs + strlen(rs), "\nUsage: lzmadec file.lzma [outFile]\n"); + return 1; + } + + inFile = fopen(args[1], "rb"); + if (inFile == 0) + return PrintError(rs, "Can not open input file"); + + if (numArgs > 2) + { + outFile = fopen(args[2], "wb+"); + if (outFile == 0) + return PrintError(rs, "Can not open output file"); + } + + res = main3(inFile, outFile, rs); + + if (outFile != 0) + fclose(outFile); + fclose(inFile); + return res; +} + +int main(int numArgs, const char *args[]) +{ + char rs[800] = { 0 }; + int res = main2(numArgs, args, rs); + printf(rs); + return res; +} diff --git a/C/Compress/Lzma/LzmaTest.c b/C/Compress/Lzma/LzmaTest.c new file mode 100755 index 00000000..f95a753b --- /dev/null +++ b/C/Compress/Lzma/LzmaTest.c @@ -0,0 +1,342 @@ +/* +LzmaTest.c +Test application for LZMA Decoder + +This file written and distributed to public domain by Igor Pavlov. +This file is part of LZMA SDK 4.26 (2005-08-05) +*/ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "LzmaDecode.h" + +const char *kCantReadMessage = "Can not read input file"; +const char *kCantWriteMessage = "Can not write output file"; +const char *kCantAllocateMessage = "Can not allocate memory"; + +size_t MyReadFile(FILE *file, void *data, size_t size) +{ + if (size == 0) + return 0; + return fread(data, 1, size, file); +} + +int MyReadFileAndCheck(FILE *file, void *data, size_t size) + { return (MyReadFile(file, data, size) == size);} + +size_t MyWriteFile(FILE *file, const void *data, size_t size) +{ + if (size == 0) + return 0; + return fwrite(data, 1, size, file); +} + +int MyWriteFileAndCheck(FILE *file, const void *data, size_t size) + { return (MyWriteFile(file, data, size) == size); } + +#ifdef _LZMA_IN_CB +#define kInBufferSize (1 << 15) +typedef struct _CBuffer +{ + ILzmaInCallback InCallback; + FILE *File; + unsigned char Buffer[kInBufferSize]; +} CBuffer; + +int LzmaReadCompressed(void *object, const unsigned char **buffer, SizeT *size) +{ + CBuffer *b = (CBuffer *)object; + *buffer = b->Buffer; + *size = (SizeT)MyReadFile(b->File, b->Buffer, kInBufferSize); + return LZMA_RESULT_OK; +} +CBuffer g_InBuffer; + +#endif + +#ifdef _LZMA_OUT_READ +#define kOutBufferSize (1 << 15) +unsigned char g_OutBuffer[kOutBufferSize]; +#endif + +int PrintError(char *buffer, const char *message) +{ + sprintf(buffer + strlen(buffer), "\nError: "); + sprintf(buffer + strlen(buffer), message); + return 1; +} + +int main3(FILE *inFile, FILE *outFile, char *rs) +{ + /* We use two 32-bit integers to construct 64-bit integer for file size. + You can remove outSizeHigh, if you don't need >= 4GB supporting, + or you can use UInt64 outSize, if your compiler supports 64-bit integers*/ + UInt32 outSize = 0; + UInt32 outSizeHigh = 0; + #ifndef _LZMA_OUT_READ + SizeT outSizeFull; + unsigned char *outStream; + #endif + + int waitEOS = 1; + /* waitEOS = 1, if there is no uncompressed size in headers, + so decoder will wait EOS (End of Stream Marker) in compressed stream */ + + #ifndef _LZMA_IN_CB + SizeT compressedSize; + unsigned char *inStream; + #endif + + CLzmaDecoderState state; /* it's about 24-80 bytes structure, if int is 32-bit */ + unsigned char properties[LZMA_PROPERTIES_SIZE]; + + int res; + + #ifdef _LZMA_IN_CB + g_InBuffer.File = inFile; + #endif + + if (sizeof(UInt32) < 4) + return PrintError(rs, "LZMA decoder needs correct UInt32"); + + #ifndef _LZMA_IN_CB + { + long length; + fseek(inFile, 0, SEEK_END); + length = ftell(inFile); + fseek(inFile, 0, SEEK_SET); + if ((long)(SizeT)length != length) + return PrintError(rs, "Too big compressed stream"); + compressedSize = (SizeT)(length - (LZMA_PROPERTIES_SIZE + 8)); + } + #endif + + /* Read LZMA properties for compressed stream */ + + if (!MyReadFileAndCheck(inFile, properties, sizeof(properties))) + return PrintError(rs, kCantReadMessage); + + /* Read uncompressed size */ + + { + int i; + for (i = 0; i < 8; i++) + { + unsigned char b; + if (!MyReadFileAndCheck(inFile, &b, 1)) + return PrintError(rs, kCantReadMessage); + if (b != 0xFF) + waitEOS = 0; + if (i < 4) + outSize += (UInt32)(b) << (i * 8); + else + outSizeHigh += (UInt32)(b) << ((i - 4) * 8); + } + + #ifndef _LZMA_OUT_READ + if (waitEOS) + return PrintError(rs, "Stream with EOS marker is not supported"); + outSizeFull = (SizeT)outSize; + if (sizeof(SizeT) >= 8) + outSizeFull |= (((SizeT)outSizeHigh << 16) << 16); + else if (outSizeHigh != 0 || (UInt32)(SizeT)outSize != outSize) + return PrintError(rs, "Too big uncompressed stream"); + #endif + } + + /* Decode LZMA properties and allocate memory */ + + if (LzmaDecodeProperties(&state.Properties, properties, LZMA_PROPERTIES_SIZE) != LZMA_RESULT_OK) + return PrintError(rs, "Incorrect stream properties"); + state.Probs = (CProb *)malloc(LzmaGetNumProbs(&state.Properties) * sizeof(CProb)); + + #ifdef _LZMA_OUT_READ + if (state.Properties.DictionarySize == 0) + state.Dictionary = 0; + else + state.Dictionary = (unsigned char *)malloc(state.Properties.DictionarySize); + #else + if (outSizeFull == 0) + outStream = 0; + else + outStream = (unsigned char *)malloc(outSizeFull); + #endif + + #ifndef _LZMA_IN_CB + if (compressedSize == 0) + inStream = 0; + else + inStream = (unsigned char *)malloc(compressedSize); + #endif + + if (state.Probs == 0 + #ifdef _LZMA_OUT_READ + || (state.Dictionary == 0 && state.Properties.DictionarySize != 0) + #else + || (outStream == 0 && outSizeFull != 0) + #endif + #ifndef _LZMA_IN_CB + || (inStream == 0 && compressedSize != 0) + #endif + ) + { + free(state.Probs); + #ifdef _LZMA_OUT_READ + free(state.Dictionary); + #else + free(outStream); + #endif + #ifndef _LZMA_IN_CB + free(inStream); + #endif + return PrintError(rs, kCantAllocateMessage); + } + + /* Decompress */ + + #ifdef _LZMA_IN_CB + g_InBuffer.InCallback.Read = LzmaReadCompressed; + #else + if (!MyReadFileAndCheck(inFile, inStream, compressedSize)) + return PrintError(rs, kCantReadMessage); + #endif + + #ifdef _LZMA_OUT_READ + { + #ifndef _LZMA_IN_CB + SizeT inAvail = compressedSize; + const unsigned char *inBuffer = inStream; + #endif + LzmaDecoderInit(&state); + do + { + #ifndef _LZMA_IN_CB + SizeT inProcessed; + #endif + SizeT outProcessed; + SizeT outAvail = kOutBufferSize; + if (!waitEOS && outSizeHigh == 0 && outAvail > outSize) + outAvail = (SizeT)outSize; + res = LzmaDecode(&state, + #ifdef _LZMA_IN_CB + &g_InBuffer.InCallback, + #else + inBuffer, inAvail, &inProcessed, + #endif + g_OutBuffer, outAvail, &outProcessed); + if (res != 0) + { + sprintf(rs + strlen(rs), "\nDecoding error = %d\n", res); + res = 1; + break; + } + #ifndef _LZMA_IN_CB + inAvail -= inProcessed; + inBuffer += inProcessed; + #endif + + if (outFile != 0) + if (!MyWriteFileAndCheck(outFile, g_OutBuffer, (size_t)outProcessed)) + { + PrintError(rs, kCantWriteMessage); + res = 1; + break; + } + + if (outSize < outProcessed) + outSizeHigh--; + outSize -= (UInt32)outProcessed; + outSize &= 0xFFFFFFFF; + + if (outProcessed == 0) + { + if (!waitEOS && (outSize != 0 || outSizeHigh != 0)) + res = 1; + break; + } + } + while ((outSize != 0 && outSizeHigh == 0) || outSizeHigh != 0 || waitEOS); + } + + #else + { + #ifndef _LZMA_IN_CB + SizeT inProcessed; + #endif + SizeT outProcessed; + res = LzmaDecode(&state, + #ifdef _LZMA_IN_CB + &g_InBuffer.InCallback, + #else + inStream, compressedSize, &inProcessed, + #endif + outStream, outSizeFull, &outProcessed); + if (res != 0) + { + sprintf(rs + strlen(rs), "\nDecoding error = %d\n", res); + res = 1; + } + else if (outFile != 0) + { + if (!MyWriteFileAndCheck(outFile, outStream, (size_t)outProcessed)) + { + PrintError(rs, kCantWriteMessage); + res = 1; + } + } + } + #endif + + free(state.Probs); + #ifdef _LZMA_OUT_READ + free(state.Dictionary); + #else + free(outStream); + #endif + #ifndef _LZMA_IN_CB + free(inStream); + #endif + return res; +} + +int main2(int numArgs, const char *args[], char *rs) +{ + FILE *inFile = 0; + FILE *outFile = 0; + int res; + + sprintf(rs + strlen(rs), "\nLZMA Decoder 4.26 Copyright (c) 1999-2005 Igor Pavlov 2005-08-05\n"); + if (numArgs < 2 || numArgs > 3) + { + sprintf(rs + strlen(rs), "\nUsage: lzmadec file.lzma [outFile]\n"); + return 1; + } + + inFile = fopen(args[1], "rb"); + if (inFile == 0) + return PrintError(rs, "Can not open input file"); + + if (numArgs > 2) + { + outFile = fopen(args[2], "wb+"); + if (outFile == 0) + return PrintError(rs, "Can not open output file"); + } + + res = main3(inFile, outFile, rs); + + if (outFile != 0) + fclose(outFile); + fclose(inFile); + return res; +} + +int main(int numArgs, const char *args[]) +{ + char rs[800] = { 0 }; + int res = main2(numArgs, args, rs); + printf(rs); + return res; +} diff --git a/C/Compress/Lzma/LzmaTypes.h b/C/Compress/Lzma/LzmaTypes.h new file mode 100755 index 00000000..288c5e45 --- /dev/null +++ b/C/Compress/Lzma/LzmaTypes.h @@ -0,0 +1,45 @@ +/* +LzmaTypes.h + +Types for LZMA Decoder + +This file written and distributed to public domain by Igor Pavlov. +This file is part of LZMA SDK 4.40 (2006-05-01) +*/ + +#ifndef __LZMATYPES_H +#define __LZMATYPES_H + +#ifndef _7ZIP_BYTE_DEFINED +#define _7ZIP_BYTE_DEFINED +typedef unsigned char Byte; +#endif + +#ifndef _7ZIP_UINT16_DEFINED +#define _7ZIP_UINT16_DEFINED +typedef unsigned short UInt16; +#endif + +#ifndef _7ZIP_UINT32_DEFINED +#define _7ZIP_UINT32_DEFINED +#ifdef _LZMA_UINT32_IS_ULONG +typedef unsigned long UInt32; +#else +typedef unsigned int UInt32; +#endif +#endif + +/* #define _LZMA_SYSTEM_SIZE_T */ +/* Use system's size_t. You can use it to enable 64-bit sizes supporting */ + +#ifndef _7ZIP_SIZET_DEFINED +#define _7ZIP_SIZET_DEFINED +#ifdef _LZMA_SYSTEM_SIZE_T +#include <stddef.h> +typedef size_t SizeT; +#else +typedef UInt32 SizeT; +#endif +#endif + +#endif |