[evince/wip/hadess/lzma-sdk-2102] unarr: Update LZMA SDK
- From: Bastien Nocera <hadess src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [evince/wip/hadess/lzma-sdk-2102] unarr: Update LZMA SDK
- Date: Thu, 1 Jul 2021 14:00:52 +0000 (UTC)
commit 2993e9818c17987ebb9ee80e5e4765a5d0fb0d10
Author: Bastien Nocera <hadess hadess net>
Date: Thu Jul 1 15:57:34 2021 +0200
unarr: Update LZMA SDK
Using lzma2102.7z from:
https://sourceforge.net/projects/sevenzip/files/LZMA%20SDK/
And adapt RAR decoder for changes in C API.
cut-n-paste/unarr/lzmasdk/7zTypes.h | 182 ++++++-
cut-n-paste/unarr/lzmasdk/CpuArch.c | 248 ++++++++-
cut-n-paste/unarr/lzmasdk/CpuArch.h | 125 ++++-
cut-n-paste/unarr/lzmasdk/Ppmd.h | 144 ++++--
cut-n-paste/unarr/lzmasdk/Ppmd7.c | 890 ++++++++++++++++++++++++---------
cut-n-paste/unarr/lzmasdk/Ppmd7.h | 175 ++++---
cut-n-paste/unarr/lzmasdk/Ppmd7Dec.c | 330 +++++++-----
cut-n-paste/unarr/rar/rar.h | 2 +-
cut-n-paste/unarr/rar/uncompress-rar.c | 40 +-
9 files changed, 1585 insertions(+), 551 deletions(-)
---
diff --git a/cut-n-paste/unarr/lzmasdk/7zTypes.h b/cut-n-paste/unarr/lzmasdk/7zTypes.h
index 65b3af63..f817b7f5 100644
--- a/cut-n-paste/unarr/lzmasdk/7zTypes.h
+++ b/cut-n-paste/unarr/lzmasdk/7zTypes.h
@@ -1,11 +1,13 @@
/* 7zTypes.h -- Basic types
-2018-08-04 : Igor Pavlov : Public domain */
+2021-04-25 : Igor Pavlov : Public domain */
#ifndef __7Z_TYPES_H
#define __7Z_TYPES_H
#ifdef _WIN32
/* #include <windows.h> */
+#else
+#include <errno.h>
#endif
#include <stddef.h>
@@ -43,18 +45,112 @@ EXTERN_C_BEGIN
typedef int SRes;
+#ifdef _MSC_VER
+ #if _MSC_VER > 1200
+ #define MY_ALIGN(n) __declspec(align(n))
+ #else
+ #define MY_ALIGN(n)
+ #endif
+#else
+ #define MY_ALIGN(n) __attribute__ ((aligned(n)))
+#endif
+
+
#ifdef _WIN32
/* typedef DWORD WRes; */
typedef unsigned WRes;
#define MY_SRes_HRESULT_FROM_WRes(x) HRESULT_FROM_WIN32(x)
-#else
+#else // _WIN32
+// #define ENV_HAVE_LSTAT
typedef int WRes;
-#define MY__FACILITY_WIN32 7
-#define MY__FACILITY__WRes MY__FACILITY_WIN32
-#define MY_SRes_HRESULT_FROM_WRes(x) ((HRESULT)(x) <= 0 ? ((HRESULT)(x)) : ((HRESULT) (((x) & 0x0000FFFF) |
(MY__FACILITY__WRes << 16) | 0x80000000)))
+
+// (FACILITY_ERRNO = 0x800) is 7zip's FACILITY constant to represent (errno) errors in HRESULT
+#define MY__FACILITY_ERRNO 0x800
+#define MY__FACILITY_WIN32 7
+#define MY__FACILITY__WRes MY__FACILITY_ERRNO
+
+#define MY_HRESULT_FROM_errno_CONST_ERROR(x) ((HRESULT)( \
+ ( (HRESULT)(x) & 0x0000FFFF) \
+ | (MY__FACILITY__WRes << 16) \
+ | (HRESULT)0x80000000 ))
+
+#define MY_SRes_HRESULT_FROM_WRes(x) \
+ ((HRESULT)(x) <= 0 ? ((HRESULT)(x)) : MY_HRESULT_FROM_errno_CONST_ERROR(x))
+
+// we call macro HRESULT_FROM_WIN32 for system errors (WRes) that are (errno)
+#define HRESULT_FROM_WIN32(x) MY_SRes_HRESULT_FROM_WRes(x)
+
+/*
+#define ERROR_FILE_NOT_FOUND 2L
+#define ERROR_ACCESS_DENIED 5L
+#define ERROR_NO_MORE_FILES 18L
+#define ERROR_LOCK_VIOLATION 33L
+#define ERROR_FILE_EXISTS 80L
+#define ERROR_DISK_FULL 112L
+#define ERROR_NEGATIVE_SEEK 131L
+#define ERROR_ALREADY_EXISTS 183L
+#define ERROR_DIRECTORY 267L
+#define ERROR_TOO_MANY_POSTS 298L
+
+#define ERROR_INVALID_REPARSE_DATA 4392L
+#define ERROR_REPARSE_TAG_INVALID 4393L
+#define ERROR_REPARSE_TAG_MISMATCH 4394L
+*/
+
+// we use errno equivalents for some WIN32 errors:
+
+#define ERROR_INVALID_FUNCTION EINVAL
+#define ERROR_ALREADY_EXISTS EEXIST
+#define ERROR_FILE_EXISTS EEXIST
+#define ERROR_PATH_NOT_FOUND ENOENT
+#define ERROR_FILE_NOT_FOUND ENOENT
+#define ERROR_DISK_FULL ENOSPC
+// #define ERROR_INVALID_HANDLE EBADF
+
+// we use FACILITY_WIN32 for errors that has no errno equivalent
+// Too many posts were made to a semaphore.
+#define ERROR_TOO_MANY_POSTS ((HRESULT)0x8007012AL)
+#define ERROR_INVALID_REPARSE_DATA ((HRESULT)0x80071128L)
+#define ERROR_REPARSE_TAG_INVALID ((HRESULT)0x80071129L)
+
+// if (MY__FACILITY__WRes != FACILITY_WIN32),
+// we use FACILITY_WIN32 for COM errors:
+#define E_OUTOFMEMORY ((HRESULT)0x8007000EL)
+#define E_INVALIDARG ((HRESULT)0x80070057L)
+#define MY__E_ERROR_NEGATIVE_SEEK ((HRESULT)0x80070083L)
+
+/*
+// we can use FACILITY_ERRNO for some COM errors, that have errno equivalents:
+#define E_OUTOFMEMORY MY_HRESULT_FROM_errno_CONST_ERROR(ENOMEM)
+#define E_INVALIDARG MY_HRESULT_FROM_errno_CONST_ERROR(EINVAL)
+#define MY__E_ERROR_NEGATIVE_SEEK MY_HRESULT_FROM_errno_CONST_ERROR(EINVAL)
+*/
+
+// gcc / clang : (sizeof(long) == sizeof(void*)) in 32/64 bits
+typedef long INT_PTR;
+typedef unsigned long UINT_PTR;
+
+#define TEXT(quote) quote
+
+#define FILE_ATTRIBUTE_READONLY 0x0001
+#define FILE_ATTRIBUTE_HIDDEN 0x0002
+#define FILE_ATTRIBUTE_SYSTEM 0x0004
+#define FILE_ATTRIBUTE_DIRECTORY 0x0010
+#define FILE_ATTRIBUTE_ARCHIVE 0x0020
+#define FILE_ATTRIBUTE_DEVICE 0x0040
+#define FILE_ATTRIBUTE_NORMAL 0x0080
+#define FILE_ATTRIBUTE_TEMPORARY 0x0100
+#define FILE_ATTRIBUTE_SPARSE_FILE 0x0200
+#define FILE_ATTRIBUTE_REPARSE_POINT 0x0400
+#define FILE_ATTRIBUTE_COMPRESSED 0x0800
+#define FILE_ATTRIBUTE_OFFLINE 0x1000
+#define FILE_ATTRIBUTE_NOT_CONTENT_INDEXED 0x2000
+#define FILE_ATTRIBUTE_ENCRYPTED 0x4000
+
+#define FILE_ATTRIBUTE_UNIX_EXTENSION 0x8000 /* trick for Unix */
#endif
@@ -63,6 +159,10 @@ typedef int WRes;
#define RINOK(x) { int __result__ = (x); if (__result__ != 0) return __result__; }
#endif
+#ifndef RINOK_WRes
+#define RINOK_WRes(x) { WRes __result__ = (x); if (__result__ != 0) return __result__; }
+#endif
+
typedef unsigned char Byte;
typedef short Int16;
typedef unsigned short UInt16;
@@ -75,6 +175,38 @@ typedef int Int32;
typedef unsigned int UInt32;
#endif
+
+#ifndef _WIN32
+
+typedef int INT;
+typedef Int32 INT32;
+typedef unsigned int UINT;
+typedef UInt32 UINT32;
+typedef INT32 LONG; // LONG, ULONG and DWORD must be 32-bit for _WIN32 compatibility
+typedef UINT32 ULONG;
+
+#undef DWORD
+typedef UINT32 DWORD;
+
+#define VOID void
+
+#define HRESULT LONG
+
+typedef void *LPVOID;
+// typedef void VOID;
+// typedef ULONG_PTR DWORD_PTR, *PDWORD_PTR;
+// gcc / clang on Unix : sizeof(long==sizeof(void*) in 32 or 64 bits)
+typedef long INT_PTR;
+typedef unsigned long UINT_PTR;
+typedef long LONG_PTR;
+typedef unsigned long DWORD_PTR;
+
+typedef size_t SIZE_T;
+
+#endif // _WIN32
+
+
+
#ifdef _SZ_NO_INT_64
/* define _SZ_NO_INT_64, if your compiler doesn't support 64-bit integers.
@@ -128,25 +260,37 @@ typedef int BoolInt;
#define MY_CDECL __cdecl
#define MY_FAST_CALL __fastcall
-#else
+#else // _MSC_VER
+#if (defined(__GNUC__) && (__GNUC__ >= 4)) \
+ || (defined(__clang__) && (__clang_major__ >= 4)) \
+ || defined(__INTEL_COMPILER) \
+ || defined(__xlC__)
+#define MY_NO_INLINE __attribute__((noinline))
+// #define MY_FORCE_INLINE __attribute__((always_inline)) inline
+#else
#define MY_NO_INLINE
+#endif
+
#define MY_FORCE_INLINE
-#define MY_CDECL
-#define MY_FAST_CALL
-/* inline keyword : for C++ / C99 */
-/* GCC, clang: */
-/*
-#if defined (__GNUC__) && (__GNUC__ >= 4)
-#define MY_FORCE_INLINE __attribute__((always_inline))
-#define MY_NO_INLINE __attribute__((noinline))
-#endif
-*/
+#define MY_CDECL
+#if defined(_M_IX86) \
+ || defined(__i386__)
+// #define MY_FAST_CALL __attribute__((fastcall))
+// #define MY_FAST_CALL __attribute__((cdecl))
+#define MY_FAST_CALL
+#elif defined(MY_CPU_AMD64)
+// #define MY_FAST_CALL __attribute__((ms_abi))
+#define MY_FAST_CALL
+#else
+#define MY_FAST_CALL
#endif
+#endif // _MSC_VER
+
/* The following interfaces use first parameter as pointer to structure */
@@ -335,12 +479,11 @@ struct ISzAlloc
GCC 4.8.1 : classes with non-public variable members"
*/
-#define MY_container_of(ptr, type, m) ((type *)((char *)(1 ? (ptr) : &((type *)0)->m) - MY_offsetof(type,
m)))
-
+#define MY_container_of(ptr, type, m) ((type *)(void *)((char *)(void *)(1 ? (ptr) : &((type *)0)->m) -
MY_offsetof(type, m)))
#endif
-#define CONTAINER_FROM_VTBL_SIMPLE(ptr, type, m) ((type *)(ptr))
+#define CONTAINER_FROM_VTBL_SIMPLE(ptr, type, m) ((type *)(void *)(ptr))
/*
#define CONTAINER_FROM_VTBL(ptr, type, m) CONTAINER_FROM_VTBL_SIMPLE(ptr, type, m)
@@ -353,6 +496,7 @@ struct ISzAlloc
*/
+#define MY_memset_0_ARRAY(a) memset((a), 0, sizeof(a))
#ifdef _WIN32
diff --git a/cut-n-paste/unarr/lzmasdk/CpuArch.c b/cut-n-paste/unarr/lzmasdk/CpuArch.c
index b82785cf..99774346 100644
--- a/cut-n-paste/unarr/lzmasdk/CpuArch.c
+++ b/cut-n-paste/unarr/lzmasdk/CpuArch.c
@@ -1,5 +1,5 @@
/* CpuArch.c -- CPU specific code
-2018-02-18: Igor Pavlov : Public domain */
+2021-04-28 : Igor Pavlov : Public domain */
#include "Precomp.h"
@@ -55,6 +55,47 @@ static UInt32 CheckFlag(UInt32 flag)
#define CHECK_CPUID_IS_SUPPORTED
#endif
+#ifndef USE_ASM
+ #ifdef _MSC_VER
+ #if _MSC_VER >= 1600
+ #define MY__cpuidex __cpuidex
+ #else
+
+/*
+ __cpuid (function == 4) requires subfunction number in ECX.
+ MSDN: The __cpuid intrinsic clears the ECX register before calling the cpuid instruction.
+ __cpuid() in new MSVC clears ECX.
+ __cpuid() in old MSVC (14.00) doesn't clear ECX
+ We still can use __cpuid for low (function) values that don't require ECX,
+ but __cpuid() in old MSVC will be incorrect for some function values: (function == 4).
+ So here we use the hack for old MSVC to send (subFunction) in ECX register to cpuid instruction,
+ where ECX value is first parameter for FAST_CALL / NO_INLINE function,
+ So the caller of MY__cpuidex_HACK() sets ECX as subFunction, and
+ old MSVC for __cpuid() doesn't change ECX and cpuid instruction gets (subFunction) value.
+
+ DON'T remove MY_NO_INLINE and MY_FAST_CALL for MY__cpuidex_HACK() !!!
+*/
+
+static
+MY_NO_INLINE
+void MY_FAST_CALL MY__cpuidex_HACK(UInt32 subFunction, int *CPUInfo, UInt32 function)
+{
+ UNUSED_VAR(subFunction);
+ __cpuid(CPUInfo, function);
+}
+
+ #define MY__cpuidex(info, func, func2) MY__cpuidex_HACK(func2, info, func)
+ #pragma message("======== MY__cpuidex_HACK WAS USED ========")
+ #endif
+ #else
+ #define MY__cpuidex(info, func, func2) __cpuid(info, func)
+ #pragma message("======== (INCORRECT ?) cpuid WAS USED ========")
+ #endif
+#endif
+
+
+
+
void MyCPUID(UInt32 function, UInt32 *a, UInt32 *b, UInt32 *c, UInt32 *d)
{
#ifdef USE_ASM
@@ -99,18 +140,20 @@ void MyCPUID(UInt32 function, UInt32 *a, UInt32 *b, UInt32 *c, UInt32 *d)
#endif
"=c" (*c) ,
"=d" (*d)
- : "0" (function)) ;
+ : "0" (function), "c"(0) ) ;
#endif
-
+
#else
int CPUInfo[4];
- __cpuid(CPUInfo, function);
- *a = CPUInfo[0];
- *b = CPUInfo[1];
- *c = CPUInfo[2];
- *d = CPUInfo[3];
+
+ MY__cpuidex(CPUInfo, (int)function, 0);
+
+ *a = (UInt32)CPUInfo[0];
+ *b = (UInt32)CPUInfo[1];
+ *c = (UInt32)CPUInfo[2];
+ *d = (UInt32)CPUInfo[3];
#endif
}
@@ -154,7 +197,7 @@ BoolInt CPU_Is_InOrder(void)
family = x86cpuid_GetFamily(p.ver);
model = x86cpuid_GetModel(p.ver);
-
+
firm = x86cpuid_GetFirm(&p);
switch (firm)
@@ -174,8 +217,8 @@ BoolInt CPU_Is_InOrder(void)
}
#if !defined(MY_CPU_AMD64) && defined(_WIN32)
-#include <windows.h>
-static BoolInt CPU_Sys_Is_SSE_Supported()
+#include <Windows.h>
+static BoolInt CPU_Sys_Is_SSE_Supported(void)
{
OSVERSIONINFO vi;
vi.dwOSVersionInfoSize = sizeof(vi);
@@ -188,16 +231,80 @@ static BoolInt CPU_Sys_Is_SSE_Supported()
#define CHECK_SYS_SSE_SUPPORT
#endif
-BoolInt CPU_Is_Aes_Supported(void)
+
+static UInt32 X86_CPUID_ECX_Get_Flags(void)
{
Cx86cpuid p;
CHECK_SYS_SSE_SUPPORT
if (!x86cpuid_CheckAndRead(&p))
+ return 0;
+ return p.c;
+}
+
+BoolInt CPU_IsSupported_AES(void)
+{
+ return (X86_CPUID_ECX_Get_Flags() >> 25) & 1;
+}
+
+BoolInt CPU_IsSupported_SSSE3(void)
+{
+ return (X86_CPUID_ECX_Get_Flags() >> 9) & 1;
+}
+
+BoolInt CPU_IsSupported_SSE41(void)
+{
+ return (X86_CPUID_ECX_Get_Flags() >> 19) & 1;
+}
+
+BoolInt CPU_IsSupported_SHA(void)
+{
+ Cx86cpuid p;
+ CHECK_SYS_SSE_SUPPORT
+ if (!x86cpuid_CheckAndRead(&p))
+ return False;
+
+ if (p.maxFunc < 7)
return False;
- return (p.c >> 25) & 1;
+ {
+ UInt32 d[4] = { 0 };
+ MyCPUID(7, &d[0], &d[1], &d[2], &d[3]);
+ return (d[1] >> 29) & 1;
+ }
}
-BoolInt CPU_IsSupported_PageGB()
+// #include <stdio.h>
+
+#ifdef _WIN32
+#include <Windows.h>
+#endif
+
+BoolInt CPU_IsSupported_VAES_AVX2(void)
+{
+ Cx86cpuid p;
+ CHECK_SYS_SSE_SUPPORT
+
+ #ifdef _WIN32
+ #define MY__PF_XSAVE_ENABLED 17
+ if (!IsProcessorFeaturePresent(MY__PF_XSAVE_ENABLED))
+ return False;
+ #endif
+
+ if (!x86cpuid_CheckAndRead(&p))
+ return False;
+ if (p.maxFunc < 7)
+ return False;
+ {
+ UInt32 d[4] = { 0 };
+ MyCPUID(7, &d[0], &d[1], &d[2], &d[3]);
+ // printf("\ncpuid(7): ebx=%8x ecx=%8x\n", d[1], d[2]);
+ return 1
+ & (d[1] >> 5) // avx2
+ // & (d[1] >> 31) // avx512vl
+ & (d[2] >> 9); // vaes // VEX-256/EVEX
+ }
+}
+
+BoolInt CPU_IsSupported_PageGB(void)
{
Cx86cpuid cpuid;
if (!x86cpuid_CheckAndRead(&cpuid))
@@ -215,4 +322,117 @@ BoolInt CPU_IsSupported_PageGB()
}
}
+
+#elif defined(MY_CPU_ARM_OR_ARM64)
+
+#ifdef _WIN32
+
+#include <Windows.h>
+
+BoolInt CPU_IsSupported_CRC32(void)
+ { return IsProcessorFeaturePresent(PF_ARM_V8_CRC32_INSTRUCTIONS_AVAILABLE) ? 1 : 0; }
+BoolInt CPU_IsSupported_CRYPTO(void)
+ { return IsProcessorFeaturePresent(PF_ARM_V8_CRYPTO_INSTRUCTIONS_AVAILABLE) ? 1 : 0; }
+
+#else
+
+#if defined(__APPLE__)
+
+/*
+#include <stdio.h>
+#include <string.h>
+static void Print_sysctlbyname(const char *name)
+{
+ size_t bufSize = 256;
+ char buf[256];
+ int res = sysctlbyname(name, &buf, &bufSize, NULL, 0);
+ {
+ int i;
+ printf("\nres = %d : %s : '%s' : bufSize = %d, numeric", res, name, buf, (unsigned)bufSize);
+ for (i = 0; i < 20; i++)
+ printf(" %2x", (unsigned)(Byte)buf[i]);
+
+ }
+}
+*/
+
+BoolInt CPU_IsSupported_CRC32(void)
+{
+ /*
+ Print_sysctlbyname("hw.pagesize");
+ Print_sysctlbyname("machdep.cpu.brand_string");
+ */
+
+ UInt32 val = 0;
+ if (My_sysctlbyname_Get_UInt32("hw.optional.armv8_crc32", &val) == 0 && val == 1)
+ return 1;
+ return 0;
+}
+
+#ifdef MY_CPU_ARM64
+#define APPLE_CRYPTO_SUPPORT_VAL 1
+#else
+#define APPLE_CRYPTO_SUPPORT_VAL 0
+#endif
+
+BoolInt CPU_IsSupported_SHA1(void) { return APPLE_CRYPTO_SUPPORT_VAL; }
+BoolInt CPU_IsSupported_SHA2(void) { return APPLE_CRYPTO_SUPPORT_VAL; }
+BoolInt CPU_IsSupported_AES (void) { return APPLE_CRYPTO_SUPPORT_VAL; }
+
+
+#else // __APPLE__
+
+#include <sys/auxv.h>
+
+#define USE_HWCAP
+
+#ifdef USE_HWCAP
+
+#include <asm/hwcap.h>
+
+#ifdef MY_CPU_ARM64
+ #define MY_HWCAP_CHECK_FUNC(name) \
+ BoolInt CPU_IsSupported_ ## name() { return (getauxval(AT_HWCAP) & (HWCAP_ ## name)) ? 1 : 0; }
+#elif defined(MY_CPU_ARM)
+ #define MY_HWCAP_CHECK_FUNC(name) \
+ BoolInt CPU_IsSupported_ ## name() { return (getauxval(AT_HWCAP2) & (HWCAP2_ ## name)) ? 1 : 0; }
+#endif
+
+#else // USE_HWCAP
+
+ #define MY_HWCAP_CHECK_FUNC(name) \
+ BoolInt CPU_IsSupported_ ## name() { return 0; }
+
+#endif // USE_HWCAP
+
+MY_HWCAP_CHECK_FUNC (CRC32)
+MY_HWCAP_CHECK_FUNC (SHA1)
+MY_HWCAP_CHECK_FUNC (SHA2)
+MY_HWCAP_CHECK_FUNC (AES)
+
+#endif // __APPLE__
+#endif // _WIN32
+
+#endif // MY_CPU_ARM_OR_ARM64
+
+
+
+#ifdef __APPLE__
+
+#include <sys/sysctl.h>
+
+int My_sysctlbyname_Get(const char *name, void *buf, size_t *bufSize)
+{
+ return sysctlbyname(name, buf, bufSize, NULL, 0);
+}
+
+int My_sysctlbyname_Get_UInt32(const char *name, UInt32 *val)
+{
+ size_t bufSize = sizeof(*val);
+ int res = My_sysctlbyname_Get(name, val, &bufSize);
+ if (res == 0 && bufSize != sizeof(*val))
+ return EFAULT;
+ return res;
+}
+
#endif
diff --git a/cut-n-paste/unarr/lzmasdk/CpuArch.h b/cut-n-paste/unarr/lzmasdk/CpuArch.h
index f1edae38..6c4ab404 100644
--- a/cut-n-paste/unarr/lzmasdk/CpuArch.h
+++ b/cut-n-paste/unarr/lzmasdk/CpuArch.h
@@ -1,5 +1,5 @@
/* CpuArch.h -- CPU specific code
-2018-02-18 : Igor Pavlov : Public domain */
+2021-04-25 : Igor Pavlov : Public domain */
#ifndef __CPU_ARCH_H
#define __CPU_ARCH_H
@@ -14,6 +14,10 @@ MY_CPU_BE means that CPU is BIG ENDIAN.
If MY_CPU_LE and MY_CPU_BE are not defined, we don't know about ENDIANNESS of platform.
MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned memory accesses.
+
+MY_CPU_64BIT means that processor can work with 64-bit registers.
+ MY_CPU_64BIT can be used to select fast code branch
+ MY_CPU_64BIT doesn't mean that (sizeof(void *) == 8)
*/
#if defined(_M_X64) \
@@ -24,8 +28,10 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
#define MY_CPU_AMD64
#ifdef __ILP32__
#define MY_CPU_NAME "x32"
+ #define MY_CPU_SIZEOF_POINTER 4
#else
#define MY_CPU_NAME "x64"
+ #define MY_CPU_SIZEOF_POINTER 8
#endif
#define MY_CPU_64BIT
#endif
@@ -35,7 +41,8 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
|| defined(__i386__)
#define MY_CPU_X86
#define MY_CPU_NAME "x86"
- #define MY_CPU_32BIT
+ /* #define MY_CPU_32BIT */
+ #define MY_CPU_SIZEOF_POINTER 4
#endif
@@ -59,8 +66,14 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
|| defined(__THUMBEL__) \
|| defined(__THUMBEB__)
#define MY_CPU_ARM
- #define MY_CPU_NAME "arm"
- #define MY_CPU_32BIT
+
+ #if defined(__thumb__) || defined(__THUMBEL__) || defined(_M_ARMT)
+ #define MY_CPU_NAME "armt"
+ #else
+ #define MY_CPU_NAME "arm"
+ #endif
+ /* #define MY_CPU_32BIT */
+ #define MY_CPU_SIZEOF_POINTER 4
#endif
@@ -84,17 +97,29 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
#if defined(__ppc64__) \
- || defined(__powerpc64__)
+ || defined(__powerpc64__) \
+ || defined(__ppc__) \
+ || defined(__powerpc__) \
+ || defined(__PPC__) \
+ || defined(_POWER)
+
+#if defined(__ppc64__) \
+ || defined(__powerpc64__) \
+ || defined(_LP64) \
+ || defined(__64BIT__)
#ifdef __ILP32__
#define MY_CPU_NAME "ppc64-32"
+ #define MY_CPU_SIZEOF_POINTER 4
#else
#define MY_CPU_NAME "ppc64"
+ #define MY_CPU_SIZEOF_POINTER 8
#endif
#define MY_CPU_64BIT
-#elif defined(__ppc__) \
- || defined(__powerpc__)
+#else
#define MY_CPU_NAME "ppc"
- #define MY_CPU_32BIT
+ #define MY_CPU_SIZEOF_POINTER 4
+ /* #define MY_CPU_32BIT */
+#endif
#endif
@@ -111,6 +136,10 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
#define MY_CPU_X86_OR_AMD64
#endif
+#if defined(MY_CPU_ARM) || defined(MY_CPU_ARM64)
+#define MY_CPU_ARM_OR_ARM64
+#endif
+
#ifdef _WIN32
@@ -170,6 +199,41 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
#error Stop_Compiling_Bad_32_64_BIT
#endif
+#ifdef __SIZEOF_POINTER__
+ #ifdef MY_CPU_SIZEOF_POINTER
+ #if MY_CPU_SIZEOF_POINTER != __SIZEOF_POINTER__
+ #error Stop_Compiling_Bad_MY_CPU_PTR_SIZE
+ #endif
+ #else
+ #define MY_CPU_SIZEOF_POINTER __SIZEOF_POINTER__
+ #endif
+#endif
+
+#if defined(MY_CPU_SIZEOF_POINTER) && (MY_CPU_SIZEOF_POINTER == 4)
+#if defined (_LP64)
+ #error Stop_Compiling_Bad_MY_CPU_PTR_SIZE
+#endif
+#endif
+
+#ifdef _MSC_VER
+ #if _MSC_VER >= 1300
+ #define MY_CPU_pragma_pack_push_1 __pragma(pack(push, 1))
+ #define MY_CPU_pragma_pop __pragma(pack(pop))
+ #else
+ #define MY_CPU_pragma_pack_push_1
+ #define MY_CPU_pragma_pop
+ #endif
+#else
+ #ifdef __xlC__
+ // for XLC compiler:
+ #define MY_CPU_pragma_pack_push_1 _Pragma("pack(1)")
+ #define MY_CPU_pragma_pop _Pragma("pack()")
+ #else
+ #define MY_CPU_pragma_pack_push_1 _Pragma("pack(push, 1)")
+ #define MY_CPU_pragma_pop _Pragma("pack(pop)")
+ #endif
+#endif
+
#ifndef MY_CPU_NAME
#ifdef MY_CPU_LE
@@ -202,9 +266,9 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
#define GetUi32(p) (*(const UInt32 *)(const void *)(p))
#define GetUi64(p) (*(const UInt64 *)(const void *)(p))
-#define SetUi16(p, v) { *(UInt16 *)(p) = (v); }
-#define SetUi32(p, v) { *(UInt32 *)(p) = (v); }
-#define SetUi64(p, v) { *(UInt64 *)(p) = (v); }
+#define SetUi16(p, v) { *(UInt16 *)(void *)(p) = (v); }
+#define SetUi32(p, v) { *(UInt32 *)(void *)(p) = (v); }
+#define SetUi64(p, v) { *(UInt64 *)(void *)(p) = (v); }
#else
@@ -242,7 +306,7 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
#define MY__has_builtin(x) 0
#endif
-#if defined(MY_CPU_LE_UNALIGN) && /* defined(_WIN64) && */ (_MSC_VER >= 1300)
+#if defined(MY_CPU_LE_UNALIGN) && /* defined(_WIN64) && */ defined(_MSC_VER) && (_MSC_VER >= 1300)
/* Note: we use bswap instruction, that is unsupported in 386 cpu */
@@ -253,8 +317,8 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
#pragma intrinsic(_byteswap_uint64)
/* #define GetBe16(p) _byteswap_ushort(*(const UInt16 *)(const Byte *)(p)) */
-#define GetBe32(p) _byteswap_ulong(*(const UInt32 *)(const Byte *)(p))
-#define GetBe64(p) _byteswap_uint64(*(const UInt64 *)(const Byte *)(p))
+#define GetBe32(p) _byteswap_ulong (*(const UInt32 *)(const void *)(p))
+#define GetBe64(p) _byteswap_uint64(*(const UInt64 *)(const void *)(p))
#define SetBe32(p, v) (*(UInt32 *)(void *)(p)) = _byteswap_ulong(v)
@@ -262,9 +326,9 @@ MY_CPU_LE_UNALIGN means that CPU is LITTLE ENDIAN and CPU supports unaligned mem
(defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3))) \
|| (defined(__clang__) && MY__has_builtin(__builtin_bswap16)) )
-/* #define GetBe16(p) __builtin_bswap16(*(const UInt16 *)(const Byte *)(p)) */
-#define GetBe32(p) __builtin_bswap32(*(const UInt32 *)(const Byte *)(p))
-#define GetBe64(p) __builtin_bswap64(*(const UInt64 *)(const Byte *)(p))
+/* #define GetBe16(p) __builtin_bswap16(*(const UInt16 *)(const void *)(p)) */
+#define GetBe32(p) __builtin_bswap32(*(const UInt32 *)(const void *)(p))
+#define GetBe64(p) __builtin_bswap64(*(const UInt64 *)(const void *)(p))
#define SetBe32(p, v) (*(UInt32 *)(void *)(p)) = __builtin_bswap32(v)
@@ -326,9 +390,34 @@ int x86cpuid_GetFirm(const Cx86cpuid *p);
#define x86cpuid_GetStepping(ver) (ver & 0xF)
BoolInt CPU_Is_InOrder(void);
-BoolInt CPU_Is_Aes_Supported(void);
+
+BoolInt CPU_IsSupported_AES(void);
+BoolInt CPU_IsSupported_VAES_AVX2(void);
+BoolInt CPU_IsSupported_SSSE3(void);
+BoolInt CPU_IsSupported_SSE41(void);
+BoolInt CPU_IsSupported_SHA(void);
BoolInt CPU_IsSupported_PageGB(void);
+#elif defined(MY_CPU_ARM_OR_ARM64)
+
+BoolInt CPU_IsSupported_CRC32(void);
+
+#if defined(_WIN32)
+BoolInt CPU_IsSupported_CRYPTO(void);
+#define CPU_IsSupported_SHA1 CPU_IsSupported_CRYPTO
+#define CPU_IsSupported_SHA2 CPU_IsSupported_CRYPTO
+#define CPU_IsSupported_AES CPU_IsSupported_CRYPTO
+#else
+BoolInt CPU_IsSupported_SHA1(void);
+BoolInt CPU_IsSupported_SHA2(void);
+BoolInt CPU_IsSupported_AES(void);
+#endif
+
+#endif
+
+#if defined(__APPLE__)
+int My_sysctlbyname_Get(const char *name, void *buf, size_t *bufSize);
+int My_sysctlbyname_Get_UInt32(const char *name, UInt32 *val);
#endif
EXTERN_C_END
diff --git a/cut-n-paste/unarr/lzmasdk/Ppmd.h b/cut-n-paste/unarr/lzmasdk/Ppmd.h
index a5c1e3ef..b1987920 100644
--- a/cut-n-paste/unarr/lzmasdk/Ppmd.h
+++ b/cut-n-paste/unarr/lzmasdk/Ppmd.h
@@ -1,5 +1,5 @@
/* Ppmd.h -- PPMD codec common code
-2017-04-03 : Igor Pavlov : Public domain
+2021-04-13 : Igor Pavlov : Public domain
This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
#ifndef __PPMD_H
@@ -9,7 +9,16 @@ This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
EXTERN_C_BEGIN
-#ifdef MY_CPU_32BIT
+#if defined(MY_CPU_SIZEOF_POINTER) && (MY_CPU_SIZEOF_POINTER == 4)
+/*
+ PPMD code always uses 32-bit internal fields in PPMD structures to store internal references in main
block.
+ if (PPMD_32BIT is defined), the PPMD code stores internal pointers to 32-bit reference fields.
+ if (PPMD_32BIT is NOT defined), the PPMD code stores internal UInt32 offsets to reference fields.
+ if (pointer size is 64-bit), then (PPMD_32BIT) mode is not allowed,
+ if (pointer size is 32-bit), then (PPMD_32BIT) mode is optional,
+ and it's allowed to disable PPMD_32BIT mode even if pointer is 32-bit.
+ PPMD code works slightly faster in (PPMD_32BIT) mode.
+*/
#define PPMD_32BIT
#endif
@@ -28,7 +37,7 @@ EXTERN_C_BEGIN
#define PPMD_N4 ((128 + 3 - 1 * PPMD_N1 - 2 * PPMD_N2 - 3 * PPMD_N3) / 4)
#define PPMD_NUM_INDEXES (PPMD_N1 + PPMD_N2 + PPMD_N3 + PPMD_N4)
-#pragma pack(push, 1)
+MY_CPU_pragma_pack_push_1
/* Most compilers works OK here even without #pragma pack(push, 1), but some GCC compilers need it. */
/* SEE-contexts for PPM-contexts with masked symbols */
@@ -40,41 +49,114 @@ typedef struct
} CPpmd_See;
#define Ppmd_See_Update(p) if ((p)->Shift < PPMD_PERIOD_BITS && --(p)->Count == 0) \
- { (p)->Summ <<= 1; (p)->Count = (Byte)(3 << (p)->Shift++); }
+ { (p)->Summ = (UInt16)((p)->Summ << 1); (p)->Count = (Byte)(3 << (p)->Shift++); }
+
typedef struct
{
Byte Symbol;
Byte Freq;
- UInt16 SuccessorLow;
- UInt16 SuccessorHigh;
+ UInt16 Successor_0;
+ UInt16 Successor_1;
} CPpmd_State;
-#pragma pack(pop)
-
-typedef
- #ifdef PPMD_32BIT
- CPpmd_State *
- #else
- UInt32
- #endif
- CPpmd_State_Ref;
-
-typedef
- #ifdef PPMD_32BIT
- void *
- #else
- UInt32
- #endif
- CPpmd_Void_Ref;
-
-typedef
- #ifdef PPMD_32BIT
- Byte *
- #else
- UInt32
- #endif
- CPpmd_Byte_Ref;
+typedef struct CPpmd_State2_
+{
+ Byte Symbol;
+ Byte Freq;
+} CPpmd_State2;
+
+typedef struct CPpmd_State4_
+{
+ UInt16 Successor_0;
+ UInt16 Successor_1;
+} CPpmd_State4;
+
+MY_CPU_pragma_pop
+
+/*
+ PPMD code can write full CPpmd_State structure data to CPpmd*_Context
+ at (byte offset = 2) instead of some fields of original CPpmd*_Context structure.
+
+ If we use pointers to different types, but that point to shared
+ memory space, we can have aliasing problem (strict aliasing).
+
+ XLC compiler in -O2 mode can change the order of memory write instructions
+ in relation to read instructions, if we have use pointers to different types.
+
+ To solve that aliasing problem we use combined CPpmd*_Context structure
+ with unions that contain the fields from both structures:
+ the original CPpmd*_Context and CPpmd_State.
+ So we can access the fields from both structures via one pointer,
+ and the compiler doesn't change the order of write instructions
+ in relation to read instructions.
+
+ If we don't use memory write instructions to shared memory in
+ some local code, and we use only reading instructions (read only),
+ then probably it's safe to use pointers to different types for reading.
+*/
+
+
+
+#ifdef PPMD_32BIT
+
+ #define Ppmd_Ref_Type(type) type *
+ #define Ppmd_GetRef(p, ptr) (ptr)
+ #define Ppmd_GetPtr(p, ptr) (ptr)
+ #define Ppmd_GetPtr_Type(p, ptr, note_type) (ptr)
+
+#else
+
+ #define Ppmd_Ref_Type(type) UInt32
+ #define Ppmd_GetRef(p, ptr) ((UInt32)((Byte *)(ptr) - (p)->Base))
+ #define Ppmd_GetPtr(p, offs) ((void *)((p)->Base + (offs)))
+ #define Ppmd_GetPtr_Type(p, offs, type) ((type *)Ppmd_GetPtr(p, offs))
+
+#endif // PPMD_32BIT
+
+
+typedef Ppmd_Ref_Type(CPpmd_State) CPpmd_State_Ref;
+typedef Ppmd_Ref_Type(void) CPpmd_Void_Ref;
+typedef Ppmd_Ref_Type(Byte) CPpmd_Byte_Ref;
+
+
+/*
+#ifdef MY_CPU_LE_UNALIGN
+// the unaligned 32-bit access latency can be too large, if the data is not in L1 cache.
+#define Ppmd_GET_SUCCESSOR(p) ((CPpmd_Void_Ref)*(const UInt32 *)(const void *)&(p)->Successor_0)
+#define Ppmd_SET_SUCCESSOR(p, v) *(UInt32 *)(void *)(void *)&(p)->Successor_0 = (UInt32)(v)
+
+#else
+*/
+
+/*
+ We can write 16-bit halves to 32-bit (Successor) field in any selected order.
+ But the native order is more consistent way.
+ So we use the native order, if LE/BE order can be detected here at compile time.
+*/
+
+#ifdef MY_CPU_BE
+
+ #define Ppmd_GET_SUCCESSOR(p) \
+ ( (CPpmd_Void_Ref) (((UInt32)(p)->Successor_0 << 16) | (p)->Successor_1) )
+
+ #define Ppmd_SET_SUCCESSOR(p, v) { \
+ (p)->Successor_0 = (UInt16)(((UInt32)(v) >> 16) /* & 0xFFFF */); \
+ (p)->Successor_1 = (UInt16)((UInt32)(v) /* & 0xFFFF */); }
+
+#else
+
+ #define Ppmd_GET_SUCCESSOR(p) \
+ ( (CPpmd_Void_Ref) ((p)->Successor_0 | ((UInt32)(p)->Successor_1 << 16)) )
+
+ #define Ppmd_SET_SUCCESSOR(p, v) { \
+ (p)->Successor_0 = (UInt16)((UInt32)(v) /* & 0xFFFF */); \
+ (p)->Successor_1 = (UInt16)(((UInt32)(v) >> 16) /* & 0xFFFF */); }
+
+#endif
+
+// #endif
+
#define PPMD_SetAllBitsIn256Bytes(p) \
{ size_t z; for (z = 0; z < 256 / sizeof(p[0]); z += 8) { \
diff --git a/cut-n-paste/unarr/lzmasdk/Ppmd7.c b/cut-n-paste/unarr/lzmasdk/Ppmd7.c
index 470aadcc..cf401cb3 100644
--- a/cut-n-paste/unarr/lzmasdk/Ppmd7.c
+++ b/cut-n-paste/unarr/lzmasdk/Ppmd7.c
@@ -1,5 +1,5 @@
/* Ppmd7.c -- PPMdH codec
-2018-07-04 : Igor Pavlov : Public domain
+2021-04-13 : Igor Pavlov : Public domain
This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
#include "Precomp.h"
@@ -8,7 +8,12 @@ This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
#include "Ppmd7.h"
-const Byte PPMD7_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
+/* define PPMD7_ORDER_0_SUPPPORT to suport order-0 mode, unsupported by orignal PPMd var.H. code */
+// #define PPMD7_ORDER_0_SUPPPORT
+
+MY_ALIGN(16)
+static const Byte PPMD7_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
+MY_ALIGN(16)
static const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
#define MAX_FREQ 124
@@ -16,13 +21,10 @@ static const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x
#define U2B(nu) ((UInt32)(nu) * UNIT_SIZE)
#define U2I(nu) (p->Units2Indx[(size_t)(nu) - 1])
-#define I2U(indx) (p->Indx2Units[indx])
+#define I2U(indx) ((unsigned)p->Indx2Units[indx])
+#define I2U_UInt16(indx) ((UInt16)p->Indx2Units[indx])
-#ifdef PPMD_32BIT
- #define REF(ptr) (ptr)
-#else
- #define REF(ptr) ((UInt32)((Byte *)(ptr) - (p)->Base))
-#endif
+#define REF(ptr) Ppmd_GetRef(p, ptr)
#define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr))
@@ -35,13 +37,7 @@ typedef CPpmd7_Context * CTX_PTR;
struct CPpmd7_Node_;
-typedef
- #ifdef PPMD_32BIT
- struct CPpmd7_Node_ *
- #else
- UInt32
- #endif
- CPpmd7_Node_Ref;
+typedef Ppmd_Ref_Type(struct CPpmd7_Node_) CPpmd7_Node_Ref;
typedef struct CPpmd7_Node_
{
@@ -51,17 +47,13 @@ typedef struct CPpmd7_Node_
CPpmd7_Node_Ref Prev;
} CPpmd7_Node;
-#ifdef PPMD_32BIT
- #define NODE(ptr) (ptr)
-#else
- #define NODE(offs) ((CPpmd7_Node *)(p->Base + (offs)))
-#endif
+#define NODE(r) Ppmd_GetPtr_Type(p, r, CPpmd7_Node)
void Ppmd7_Construct(CPpmd7 *p)
{
unsigned i, k, m;
- p->Base = 0;
+ p->Base = NULL;
for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++)
{
@@ -77,6 +69,7 @@ void Ppmd7_Construct(CPpmd7 *p)
for (i = 0; i < 3; i++)
p->NS2Indx[i] = (Byte)i;
+
for (m = i, k = 1; i < 256; i++)
{
p->NS2Indx[i] = (Byte)m;
@@ -84,54 +77,63 @@ void Ppmd7_Construct(CPpmd7 *p)
k = (++m) - 2;
}
- memset(p->HB2Flag, 0, 0x40);
- memset(p->HB2Flag + 0x40, 8, 0x100 - 0x40);
+ memcpy(p->ExpEscape, PPMD7_kExpEscape, 16);
}
+
void Ppmd7_Free(CPpmd7 *p, ISzAllocPtr alloc)
{
ISzAlloc_Free(alloc, p->Base);
p->Size = 0;
- p->Base = 0;
+ p->Base = NULL;
}
+
BoolInt Ppmd7_Alloc(CPpmd7 *p, UInt32 size, ISzAllocPtr alloc)
{
if (!p->Base || p->Size != size)
{
- size_t size2;
Ppmd7_Free(p, alloc);
- size2 = 0
- #ifndef PPMD_32BIT
- + UNIT_SIZE
- #endif
- ;
- p->AlignOffset =
- #ifdef PPMD_32BIT
- (4 - size) & 3;
- #else
- 4 - (size & 3);
- #endif
- if ((p->Base = (Byte *)ISzAlloc_Alloc(alloc, p->AlignOffset + size + size2)) == 0)
+ p->AlignOffset = (4 - size) & 3;
+ if ((p->Base = (Byte *)ISzAlloc_Alloc(alloc, p->AlignOffset + size)) == NULL)
return False;
p->Size = size;
}
return True;
}
+
+
+// ---------- Internal Memory Allocator ----------
+
+/* We can use CPpmd7_Node in list of free units (as in Ppmd8)
+ But we still need one additional list walk pass in GlueFreeBlocks().
+ So we use simple CPpmd_Void_Ref instead of CPpmd7_Node in InsertNode() / RemoveNode()
+*/
+
+#define EMPTY_NODE 0
+
+
static void InsertNode(CPpmd7 *p, void *node, unsigned indx)
{
*((CPpmd_Void_Ref *)node) = p->FreeList[indx];
+ // ((CPpmd7_Node *)node)->Next = (CPpmd7_Node_Ref)p->FreeList[indx];
+
p->FreeList[indx] = REF(node);
+
}
+
static void *RemoveNode(CPpmd7 *p, unsigned indx)
{
CPpmd_Void_Ref *node = (CPpmd_Void_Ref *)Ppmd7_GetPtr(p, p->FreeList[indx]);
p->FreeList[indx] = *node;
+ // CPpmd7_Node *node = NODE((CPpmd7_Node_Ref)p->FreeList[indx]);
+ // p->FreeList[indx] = node->Next;
return node;
}
+
static void SplitBlock(CPpmd7 *p, void *ptr, unsigned oldIndx, unsigned newIndx)
{
unsigned i, nu = I2U(oldIndx) - I2U(newIndx);
@@ -144,123 +146,167 @@ static void SplitBlock(CPpmd7 *p, void *ptr, unsigned oldIndx, unsigned newIndx)
InsertNode(p, ptr, i);
}
-static void GlueFreeBlocks(CPpmd7 *p)
+
+/* we use CPpmd7_Node_Union union to solve XLC -O2 strict pointer aliasing problem */
+
+typedef union _CPpmd7_Node_Union
{
- #ifdef PPMD_32BIT
- CPpmd7_Node headItem;
- CPpmd7_Node_Ref head = &headItem;
- #else
- CPpmd7_Node_Ref head = p->AlignOffset + p->Size;
- #endif
-
- CPpmd7_Node_Ref n = head;
- unsigned i;
+ CPpmd7_Node Node;
+ CPpmd7_Node_Ref NextRef;
+} CPpmd7_Node_Union;
+
+/* Original PPmdH (Ppmd7) code uses doubly linked list in GlueFreeBlocks()
+ we use single linked list similar to Ppmd8 code */
+
+static void GlueFreeBlocks(CPpmd7 *p)
+{
+ /*
+ we use first UInt16 field of 12-bytes UNITs as record type stamp
+ CPpmd_State { Byte Symbol; Byte Freq; : Freq != 0
+ CPpmd7_Context { UInt16 NumStats; : NumStats != 0
+ CPpmd7_Node { UInt16 Stamp : Stamp == 0 for free record
+ : Stamp == 1 for head record and guard
+ Last 12-bytes UNIT in array is always contains 12-bytes order-0 CPpmd7_Context record.
+ */
+ CPpmd7_Node_Ref head, n = 0;
+
p->GlueCount = 255;
- /* create doubly-linked list of free blocks */
- for (i = 0; i < PPMD_NUM_INDEXES; i++)
+
+ /* we set guard NODE at LoUnit */
+ if (p->LoUnit != p->HiUnit)
+ ((CPpmd7_Node *)(void *)p->LoUnit)->Stamp = 1;
+
{
- UInt16 nu = I2U(i);
- CPpmd7_Node_Ref next = (CPpmd7_Node_Ref)p->FreeList[i];
- p->FreeList[i] = 0;
- while (next != 0)
+ /* Create list of free blocks.
+ We still need one additional list walk pass before Glue. */
+ unsigned i;
+ for (i = 0; i < PPMD_NUM_INDEXES; i++)
{
- CPpmd7_Node *node = NODE(next);
- node->Next = n;
- n = NODE(n)->Prev = next;
- next = *(const CPpmd7_Node_Ref *)node;
- node->Stamp = 0;
- node->NU = (UInt16)nu;
+ const UInt16 nu = I2U_UInt16(i);
+ CPpmd7_Node_Ref next = (CPpmd7_Node_Ref)p->FreeList[i];
+ p->FreeList[i] = 0;
+ while (next != 0)
+ {
+ /* Don't change the order of the following commands: */
+ CPpmd7_Node_Union *un = (CPpmd7_Node_Union *)NODE(next);
+ const CPpmd7_Node_Ref tmp = next;
+ next = un->NextRef;
+ un->Node.Stamp = EMPTY_NODE;
+ un->Node.NU = nu;
+ un->Node.Next = n;
+ n = tmp;
+ }
}
}
- NODE(head)->Stamp = 1;
- NODE(head)->Next = n;
- NODE(n)->Prev = head;
- if (p->LoUnit != p->HiUnit)
- ((CPpmd7_Node *)p->LoUnit)->Stamp = 1;
-
- /* Glue free blocks */
- while (n != head)
+
+ head = n;
+ /* Glue and Fill must walk the list in same direction */
{
- CPpmd7_Node *node = NODE(n);
- UInt32 nu = (UInt32)node->NU;
- for (;;)
+ /* Glue free blocks */
+ CPpmd7_Node_Ref *prev = &head;
+ while (n)
{
- CPpmd7_Node *node2 = NODE(n) + nu;
- nu += node2->NU;
- if (node2->Stamp != 0 || nu >= 0x10000)
- break;
- NODE(node2->Prev)->Next = node2->Next;
- NODE(node2->Next)->Prev = node2->Prev;
- node->NU = (UInt16)nu;
+ CPpmd7_Node *node = NODE(n);
+ UInt32 nu = node->NU;
+ n = node->Next;
+ if (nu == 0)
+ {
+ *prev = n;
+ continue;
+ }
+ prev = &node->Next;
+ for (;;)
+ {
+ CPpmd7_Node *node2 = node + nu;
+ nu += node2->NU;
+ if (node2->Stamp != EMPTY_NODE || nu >= 0x10000)
+ break;
+ node->NU = (UInt16)nu;
+ node2->NU = 0;
+ }
}
- n = node->Next;
}
-
+
/* Fill lists of free blocks */
- for (n = NODE(head)->Next; n != head;)
+ for (n = head; n != 0;)
{
CPpmd7_Node *node = NODE(n);
- unsigned nu;
- CPpmd7_Node_Ref next = node->Next;
- for (nu = node->NU; nu > 128; nu -= 128, node += 128)
+ UInt32 nu = node->NU;
+ unsigned i;
+ n = node->Next;
+ if (nu == 0)
+ continue;
+ for (; nu > 128; nu -= 128, node += 128)
InsertNode(p, node, PPMD_NUM_INDEXES - 1);
if (I2U(i = U2I(nu)) != nu)
{
unsigned k = I2U(--i);
- InsertNode(p, node + k, nu - k - 1);
+ InsertNode(p, node + k, (unsigned)nu - k - 1);
}
InsertNode(p, node, i);
- n = next;
}
}
+
+MY_NO_INLINE
static void *AllocUnitsRare(CPpmd7 *p, unsigned indx)
{
unsigned i;
- void *retVal;
+
if (p->GlueCount == 0)
{
GlueFreeBlocks(p);
if (p->FreeList[indx] != 0)
return RemoveNode(p, indx);
}
+
i = indx;
+
do
{
if (++i == PPMD_NUM_INDEXES)
{
UInt32 numBytes = U2B(I2U(indx));
+ Byte *us = p->UnitsStart;
p->GlueCount--;
- return ((UInt32)(p->UnitsStart - p->Text) > numBytes) ? (p->UnitsStart -= numBytes) : (NULL);
+ return ((UInt32)(us - p->Text) > numBytes) ? (p->UnitsStart = us - numBytes) : NULL;
}
}
while (p->FreeList[i] == 0);
- retVal = RemoveNode(p, i);
- SplitBlock(p, retVal, i, indx);
- return retVal;
+
+ {
+ void *block = RemoveNode(p, i);
+ SplitBlock(p, block, i, indx);
+ return block;
+ }
}
+
static void *AllocUnits(CPpmd7 *p, unsigned indx)
{
- UInt32 numBytes;
if (p->FreeList[indx] != 0)
return RemoveNode(p, indx);
- numBytes = U2B(I2U(indx));
- if (numBytes <= (UInt32)(p->HiUnit - p->LoUnit))
{
- void *retVal = p->LoUnit;
- p->LoUnit += numBytes;
- return retVal;
+ UInt32 numBytes = U2B(I2U(indx));
+ Byte *lo = p->LoUnit;
+ if ((UInt32)(p->HiUnit - lo) >= numBytes)
+ {
+ p->LoUnit = lo + numBytes;
+ return lo;
+ }
}
return AllocUnitsRare(p, indx);
}
+
#define MyMem12Cpy(dest, src, num) \
- { UInt32 *d = (UInt32 *)dest; const UInt32 *s = (const UInt32 *)src; UInt32 n = num; \
- do { d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; s += 3; d += 3; } while (--n); }
+ { UInt32 *d = (UInt32 *)dest; const UInt32 *z = (const UInt32 *)src; UInt32 n = num; \
+ do { d[0] = z[0]; d[1] = z[1]; d[2] = z[2]; z += 3; d += 3; } while (--n); }
+
+/*
static void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU)
{
unsigned i0 = U2I(oldNU);
@@ -277,20 +323,25 @@ static void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU
SplitBlock(p, oldPtr, i0, i1);
return oldPtr;
}
+*/
-#define SUCCESSOR(p) ((CPpmd_Void_Ref)((p)->SuccessorLow | ((UInt32)(p)->SuccessorHigh << 16)))
+#define SUCCESSOR(p) Ppmd_GET_SUCCESSOR(p)
static void SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v)
{
- (p)->SuccessorLow = (UInt16)((UInt32)(v) & 0xFFFF);
- (p)->SuccessorHigh = (UInt16)(((UInt32)(v) >> 16) & 0xFFFF);
+ Ppmd_SET_SUCCESSOR(p, v);
}
-static void RestartModel(CPpmd7 *p)
+
+
+MY_NO_INLINE
+static
+void RestartModel(CPpmd7 *p)
{
- unsigned i, k, m;
+ unsigned i, k;
memset(p->FreeList, 0, sizeof(p->FreeList));
+
p->Text = p->Base + p->AlignOffset;
p->HiUnit = p->Text + p->Size;
p->LoUnit = p->UnitsStart = p->HiUnit - p->Size / 8 / UNIT_SIZE * 7 * UNIT_SIZE;
@@ -300,57 +351,110 @@ static void RestartModel(CPpmd7 *p)
p->RunLength = p->InitRL = -(Int32)((p->MaxOrder < 12) ? p->MaxOrder : 12) - 1;
p->PrevSuccess = 0;
- p->MinContext = p->MaxContext = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */
- p->MinContext->Suffix = 0;
- p->MinContext->NumStats = 256;
- p->MinContext->SummFreq = 256 + 1;
- p->FoundState = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */
- p->LoUnit += U2B(256 / 2);
- p->MinContext->Stats = REF(p->FoundState);
- for (i = 0; i < 256; i++)
{
- CPpmd_State *s = &p->FoundState[i];
- s->Symbol = (Byte)i;
- s->Freq = 1;
- SetSuccessor(s, 0);
+ CPpmd7_Context *mc = (CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */
+ CPpmd_State *s = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */
+
+ p->LoUnit += U2B(256 / 2);
+ p->MaxContext = p->MinContext = mc;
+ p->FoundState = s;
+
+ mc->NumStats = 256;
+ mc->Union2.SummFreq = 256 + 1;
+ mc->Union4.Stats = REF(s);
+ mc->Suffix = 0;
+
+ for (i = 0; i < 256; i++, s++)
+ {
+ s->Symbol = (Byte)i;
+ s->Freq = 1;
+ SetSuccessor(s, 0);
+ }
+
+ #ifdef PPMD7_ORDER_0_SUPPPORT
+ if (p->MaxOrder == 0)
+ {
+ CPpmd_Void_Ref r = REF(mc);
+ s = p->FoundState;
+ for (i = 0; i < 256; i++, s++)
+ SetSuccessor(s, r);
+ return;
+ }
+ #endif
}
for (i = 0; i < 128; i++)
+
+
+
for (k = 0; k < 8; k++)
{
+ unsigned m;
UInt16 *dest = p->BinSumm[i] + k;
UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 2));
for (m = 0; m < 64; m += 8)
dest[m] = val;
}
-
+
+
for (i = 0; i < 25; i++)
- for (k = 0; k < 16; k++)
+ {
+
+ CPpmd_See *s = p->See[i];
+
+
+
+ unsigned summ = ((5 * i + 10) << (PPMD_PERIOD_BITS - 4));
+ for (k = 0; k < 16; k++, s++)
{
- CPpmd_See *s = &p->See[i][k];
- s->Summ = (UInt16)((5 * i + 10) << (s->Shift = PPMD_PERIOD_BITS - 4));
+ s->Summ = (UInt16)summ;
+ s->Shift = (PPMD_PERIOD_BITS - 4);
s->Count = 4;
}
+ }
+
+ p->DummySee.Summ = 0; /* unused */
+ p->DummySee.Shift = PPMD_PERIOD_BITS;
+ p->DummySee.Count = 64; /* unused */
}
+
void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder)
{
p->MaxOrder = maxOrder;
+
RestartModel(p);
- p->DummySee.Shift = PPMD_PERIOD_BITS;
- p->DummySee.Summ = 0; /* unused */
- p->DummySee.Count = 64; /* unused */
}
-static CTX_PTR CreateSuccessors(CPpmd7 *p, BoolInt skip)
+
+
+/*
+ CreateSuccessors()
+ It's called when (FoundState->Successor) is RAW-Successor,
+ that is the link to position in Raw text.
+ So we create Context records and write the links to
+ FoundState->Successor and to identical RAW-Successors in suffix
+ contexts of MinContex.
+
+ The function returns:
+ if (OrderFall == 0) then MinContext is already at MAX order,
+ { return pointer to new or existing context of same MAX order }
+ else
+ { return pointer to new real context that will be (Order+1) in comparison with MinContext
+
+ also it can return pointer to real context of same order,
+*/
+
+MY_NO_INLINE
+static CTX_PTR CreateSuccessors(CPpmd7 *p)
{
- CPpmd_State upState;
CTX_PTR c = p->MinContext;
CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState);
- CPpmd_State *ps[PPMD7_MAX_ORDER];
+ Byte newSym, newFreq;
unsigned numPs = 0;
-
- if (!skip)
+ CPpmd_State *ps[PPMD7_MAX_ORDER];
+
+ if (p->OrderFall != 0)
ps[numPs++] = p->FoundState;
while (c->Suffix)
@@ -358,44 +462,70 @@ static CTX_PTR CreateSuccessors(CPpmd7 *p, BoolInt skip)
CPpmd_Void_Ref successor;
CPpmd_State *s;
c = SUFFIX(c);
+
+
if (c->NumStats != 1)
{
- for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++);
+ Byte sym = p->FoundState->Symbol;
+ for (s = STATS(c); s->Symbol != sym; s++);
+
}
else
+ {
s = ONE_STATE(c);
+
+ }
successor = SUCCESSOR(s);
if (successor != upBranch)
{
+ // (c) is real record Context here,
c = CTX(successor);
if (numPs == 0)
+ {
+ // (c) is real record MAX Order Context here,
+ // So we don't need to create any new contexts.
return c;
+ }
break;
}
ps[numPs++] = s;
}
- upState.Symbol = *(const Byte *)Ppmd7_GetPtr(p, upBranch);
- SetSuccessor(&upState, upBranch + 1);
+ // All created contexts will have single-symbol with new RAW-Successor
+ // All new RAW-Successors will point to next position in RAW text
+ // after FoundState->Successor
+
+ newSym = *(const Byte *)Ppmd7_GetPtr(p, upBranch);
+ upBranch++;
+
if (c->NumStats == 1)
- upState.Freq = ONE_STATE(c)->Freq;
+ newFreq = ONE_STATE(c)->Freq;
else
{
UInt32 cf, s0;
CPpmd_State *s;
- for (s = STATS(c); s->Symbol != upState.Symbol; s++);
- cf = s->Freq - 1;
- s0 = c->SummFreq - c->NumStats - cf;
- upState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((2 * cf + 3 * s0 - 1) / (2 * s0))));
+ for (s = STATS(c); s->Symbol != newSym; s++);
+ cf = (UInt32)s->Freq - 1;
+ s0 = (UInt32)c->Union2.SummFreq - c->NumStats - cf;
+ /*
+ cf - is frequency of symbol that will be Successor in new context records.
+ s0 - is commulative frequency sum of another symbols from parent context.
+ max(newFreq)= (s->Freq + 1), when (s0 == 1)
+ we have requirement (Ppmd7Context_OneState()->Freq <= 128) in BinSumm[]
+ so (s->Freq < 128) - is requirement for multi-symbol contexts
+ */
+ newFreq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : (2 * cf + s0 - 1) / (2 * s0) + 1));
}
+ // Create new single-symbol contexts from low order to high order in loop
+
do
{
- /* Create Child */
- CTX_PTR c1; /* = AllocContext(p); */
+ CTX_PTR c1;
+ /* = AllocContext(p); */
if (p->HiUnit != p->LoUnit)
- c1 = (CTX_PTR)(p->HiUnit -= UNIT_SIZE);
+ c1 = (CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE);
else if (p->FreeList[0] != 0)
c1 = (CTX_PTR)RemoveNode(p, 0);
else
@@ -404,8 +534,11 @@ static CTX_PTR CreateSuccessors(CPpmd7 *p, BoolInt skip)
if (!c1)
return NULL;
}
+
c1->NumStats = 1;
- *ONE_STATE(c1) = upState;
+ ONE_STATE(c1)->Symbol = newSym;
+ ONE_STATE(c1)->Freq = newFreq;
+ SetSuccessor(ONE_STATE(c1), upBranch);
c1->Suffix = REF(c);
SetSuccessor(ps[--numPs], REF(c1));
c = c1;
@@ -415,21 +548,26 @@ static CTX_PTR CreateSuccessors(CPpmd7 *p, BoolInt skip)
return c;
}
-static void SwapStates(CPpmd_State *t1, CPpmd_State *t2)
-{
- CPpmd_State tmp = *t1;
- *t1 = *t2;
- *t2 = tmp;
-}
-static void UpdateModel(CPpmd7 *p)
+
+#define SwapStates(s) \
+ { CPpmd_State tmp = s[0]; s[0] = s[-1]; s[-1] = tmp; }
+
+
+void Ppmd7_UpdateModel(CPpmd7 *p);
+MY_NO_INLINE
+void Ppmd7_UpdateModel(CPpmd7 *p)
{
- CPpmd_Void_Ref successor, fSuccessor = SUCCESSOR(p->FoundState);
- CTX_PTR c;
+ CPpmd_Void_Ref maxSuccessor, minSuccessor;
+ CTX_PTR c, mc;
unsigned s0, ns;
-
+
+
+
if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0)
{
+ /* Update Freqs in Suffix Context */
+
c = SUFFIX(p->MinContext);
if (c->NumStats == 1)
@@ -441,27 +579,39 @@ static void UpdateModel(CPpmd7 *p)
else
{
CPpmd_State *s = STATS(c);
- if (s->Symbol != p->FoundState->Symbol)
+ Byte sym = p->FoundState->Symbol;
+
+ if (s->Symbol != sym)
{
- do { s++; } while (s->Symbol != p->FoundState->Symbol);
+ do
+ {
+ // s++; if (s->Symbol == sym) break;
+ s++;
+ }
+ while (s->Symbol != sym);
+
if (s[0].Freq >= s[-1].Freq)
{
- SwapStates(&s[0], &s[-1]);
+ SwapStates(s);
s--;
}
}
+
if (s->Freq < MAX_FREQ - 9)
{
- s->Freq += 2;
- c->SummFreq += 2;
+ s->Freq = (Byte)(s->Freq + 2);
+ c->Union2.SummFreq = (UInt16)(c->Union2.SummFreq + 2);
}
}
}
+
if (p->OrderFall == 0)
{
- p->MinContext = p->MaxContext = CreateSuccessors(p, True);
- if (p->MinContext == 0)
+ /* MAX ORDER context */
+ /* (FoundState->Successor) is RAW-Successor. */
+ p->MaxContext = p->MinContext = CreateSuccessors(p);
+ if (!p->MinContext)
{
RestartModel(p);
return;
@@ -469,45 +619,93 @@ static void UpdateModel(CPpmd7 *p)
SetSuccessor(p->FoundState, REF(p->MinContext));
return;
}
+
+
+ /* NON-MAX ORDER context */
- *p->Text++ = p->FoundState->Symbol;
- successor = REF(p->Text);
- if (p->Text >= p->UnitsStart)
{
- RestartModel(p);
- return;
+ Byte *text = p->Text;
+ *text++ = p->FoundState->Symbol;
+ p->Text = text;
+ if (text >= p->UnitsStart)
+ {
+ RestartModel(p);
+ return;
+ }
+ maxSuccessor = REF(text);
}
- if (fSuccessor)
+ minSuccessor = SUCCESSOR(p->FoundState);
+
+ if (minSuccessor)
{
- if (fSuccessor <= successor)
+ // there is Successor for FoundState in MinContext.
+ // So the next context will be one order higher than MinContext.
+
+ if (minSuccessor <= maxSuccessor)
{
- CTX_PTR cs = CreateSuccessors(p, False);
- if (cs == NULL)
+ // minSuccessor is RAW-Successor. So we will create real contexts records:
+ CTX_PTR cs = CreateSuccessors(p);
+ if (!cs)
{
RestartModel(p);
return;
}
- fSuccessor = REF(cs);
+ minSuccessor = REF(cs);
}
+
+ // minSuccessor now is real Context pointer that points to existing (Order+1) context
+
if (--p->OrderFall == 0)
{
- successor = fSuccessor;
+ /*
+ if we move to MaxOrder context, then minSuccessor will be common Succesor for both:
+ MinContext that is (MaxOrder - 1)
+ MaxContext that is (MaxOrder)
+ so we don't need new RAW-Successor, and we can use real minSuccessor
+ as succssors for both MinContext and MaxContext.
+ */
+ maxSuccessor = minSuccessor;
+
+ /*
+ if (MaxContext != MinContext)
+ {
+ there was order fall from MaxOrder and we don't need current symbol
+ to transfer some RAW-Succesors to real contexts.
+ So we roll back pointer in raw data for one position.
+ }
+ */
p->Text -= (p->MaxContext != p->MinContext);
}
}
else
{
- SetSuccessor(p->FoundState, successor);
- fSuccessor = REF(p->MinContext);
+ /*
+ FoundState has NULL-Successor here.
+ And only root 0-order context can contain NULL-Successors.
+ We change Successor in FoundState to RAW-Successor,
+ And next context will be same 0-order root Context.
+ */
+ SetSuccessor(p->FoundState, maxSuccessor);
+ minSuccessor = REF(p->MinContext);
}
-
- s0 = p->MinContext->SummFreq - (ns = p->MinContext->NumStats) - (p->FoundState->Freq - 1);
-
- for (c = p->MaxContext; c != p->MinContext; c = SUFFIX(c))
+
+ mc = p->MinContext;
+ c = p->MaxContext;
+
+ p->MaxContext = p->MinContext = CTX(minSuccessor);
+
+ if (c == mc)
+ return;
+
+ // s0 : is pure Escape Freq
+ s0 = mc->Union2.SummFreq - (ns = mc->NumStats) - ((unsigned)p->FoundState->Freq - 1);
+
+ do
{
unsigned ns1;
- UInt32 cf, sf;
+ UInt32 sum;
+
if ((ns1 = c->NumStats) != 1)
{
if ((ns1 & 1) == 0)
@@ -527,80 +725,127 @@ static void UpdateModel(CPpmd7 *p)
oldPtr = STATS(c);
MyMem12Cpy(ptr, oldPtr, oldNU);
InsertNode(p, oldPtr, i);
- c->Stats = STATS_REF(ptr);
+ c->Union4.Stats = STATS_REF(ptr);
}
}
- c->SummFreq = (UInt16)(c->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) & (c->SummFreq <= 8 *
ns1)));
+ sum = c->Union2.SummFreq;
+ /* max increase of Escape_Freq is 3 here.
+ total increase of Union2.SummFreq for all symbols is less than 256 here */
+ sum += (UInt32)(2 * ns1 < ns) + 2 * ((unsigned)(4 * ns1 <= ns) & (sum <= 8 * ns1));
+ /* original PPMdH uses 16-bit variable for (sum) here.
+ But (sum < 0x9000). So we don't truncate (sum) to 16-bit */
+ // sum = (UInt16)sum;
}
else
{
+ // instead of One-symbol context we create 2-symbol context
CPpmd_State *s = (CPpmd_State*)AllocUnits(p, 0);
if (!s)
{
RestartModel(p);
return;
}
- *s = *ONE_STATE(c);
- c->Stats = REF(s);
- if (s->Freq < MAX_FREQ / 4 - 1)
- s->Freq <<= 1;
- else
- s->Freq = MAX_FREQ - 4;
- c->SummFreq = (UInt16)(s->Freq + p->InitEsc + (ns > 3));
- }
- cf = 2 * (UInt32)p->FoundState->Freq * (c->SummFreq + 6);
- sf = (UInt32)s0 + c->SummFreq;
- if (cf < 6 * sf)
- {
- cf = 1 + (cf > sf) + (cf >= 4 * sf);
- c->SummFreq += 3;
- }
- else
- {
- cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);
- c->SummFreq = (UInt16)(c->SummFreq + cf);
+ {
+ unsigned freq = c->Union2.State2.Freq;
+ // s = *ONE_STATE(c);
+ s->Symbol = c->Union2.State2.Symbol;
+ s->Successor_0 = c->Union4.State4.Successor_0;
+ s->Successor_1 = c->Union4.State4.Successor_1;
+ // SetSuccessor(s, c->Union4.Stats); // call it only for debug purposes to check the order of
+ // (Successor_0 and Successor_1) in LE/BE.
+ c->Union4.Stats = REF(s);
+ if (freq < MAX_FREQ / 4 - 1)
+ freq <<= 1;
+ else
+ freq = MAX_FREQ - 4;
+ // (max(s->freq) == 120), when we convert from 1-symbol into 2-symbol context
+ s->Freq = (Byte)freq;
+ // max(InitEsc = PPMD7_kExpEscape[*]) is 25. So the max(escapeFreq) is 26 here
+ sum = freq + p->InitEsc + (ns > 3);
+ }
}
+
{
CPpmd_State *s = STATS(c) + ns1;
- SetSuccessor(s, successor);
+ UInt32 cf = 2 * (sum + 6) * (UInt32)p->FoundState->Freq;
+ UInt32 sf = (UInt32)s0 + sum;
s->Symbol = p->FoundState->Symbol;
- s->Freq = (Byte)cf;
c->NumStats = (UInt16)(ns1 + 1);
+ SetSuccessor(s, maxSuccessor);
+
+ if (cf < 6 * sf)
+ {
+ cf = (UInt32)1 + (cf > sf) + (cf >= 4 * sf);
+ sum += 3;
+ /* It can add (0, 1, 2) to Escape_Freq */
+ }
+ else
+ {
+ cf = (UInt32)4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);
+ sum += cf;
+ }
+
+ c->Union2.SummFreq = (UInt16)sum;
+ s->Freq = (Byte)cf;
}
+ c = SUFFIX(c);
}
- p->MaxContext = p->MinContext = CTX(fSuccessor);
+ while (c != mc);
}
+
+
+MY_NO_INLINE
static void Rescale(CPpmd7 *p)
{
unsigned i, adder, sumFreq, escFreq;
CPpmd_State *stats = STATS(p->MinContext);
CPpmd_State *s = p->FoundState;
+
+ /* Sort the list by Freq */
+ if (s != stats)
{
CPpmd_State tmp = *s;
- for (; s != stats; s--)
+ do
s[0] = s[-1];
+ while (--s != stats);
*s = tmp;
}
- escFreq = p->MinContext->SummFreq - s->Freq;
- s->Freq += 4;
- adder = (p->OrderFall != 0);
- s->Freq = (Byte)((s->Freq + adder) >> 1);
+
sumFreq = s->Freq;
+ escFreq = p->MinContext->Union2.SummFreq - sumFreq;
+
+ /*
+ if (p->OrderFall == 0), adder = 0 : it's allowed to remove symbol from MAX Order context
+ if (p->OrderFall != 0), adder = 1 : it's NOT allowed to remove symbol from NON-MAX Order context
+ */
+
+ adder = (p->OrderFall != 0);
+
+ #ifdef PPMD7_ORDER_0_SUPPPORT
+ adder |= (p->MaxOrder == 0); // we don't remove symbols from order-0 context
+ #endif
+
+ sumFreq = (sumFreq + 4 + adder) >> 1;
+ i = (unsigned)p->MinContext->NumStats - 1;
+ s->Freq = (Byte)sumFreq;
- i = p->MinContext->NumStats - 1;
do
{
- escFreq -= (++s)->Freq;
- s->Freq = (Byte)((s->Freq + adder) >> 1);
- sumFreq += s->Freq;
- if (s[0].Freq > s[-1].Freq)
+ unsigned freq = (++s)->Freq;
+ escFreq -= freq;
+ freq = (freq + adder) >> 1;
+ sumFreq += freq;
+ s->Freq = (Byte)freq;
+ if (freq > s[-1].Freq)
{
+ CPpmd_State tmp = *s;
CPpmd_State *s1 = s;
- CPpmd_State tmp = *s1;
do
+ {
s1[0] = s1[-1];
- while (--s1 != stats && tmp.Freq > s1[-1].Freq);
+ }
+ while (--s1 != stats && freq > s1[-1].Freq);
*s1 = tmp;
}
}
@@ -608,47 +853,89 @@ static void Rescale(CPpmd7 *p)
if (s->Freq == 0)
{
- unsigned numStats = p->MinContext->NumStats;
- unsigned n0, n1;
- do { i++; } while ((--s)->Freq == 0);
+ /* Remove all items with Freq == 0 */
+ CPpmd7_Context *mc;
+ unsigned numStats, numStatsNew, n0, n1;
+
+ i = 0; do { i++; } while ((--s)->Freq == 0);
+
+ /* We increase (escFreq) for the number of removed symbols.
+ So we will have (0.5) increase for Escape_Freq in avarage per
+ removed symbol after Escape_Freq halving */
escFreq += i;
- p->MinContext->NumStats = (UInt16)(p->MinContext->NumStats - i);
- if (p->MinContext->NumStats == 1)
+ mc = p->MinContext;
+ numStats = mc->NumStats;
+ numStatsNew = numStats - i;
+ mc->NumStats = (UInt16)(numStatsNew);
+ n0 = (numStats + 1) >> 1;
+
+ if (numStatsNew == 1)
{
- CPpmd_State tmp = *stats;
+ /* Create Single-Symbol context */
+ unsigned freq = stats->Freq;
+
do
{
- tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1));
escFreq >>= 1;
+ freq = (freq + 1) >> 1;
}
while (escFreq > 1);
- InsertNode(p, stats, U2I(((numStats + 1) >> 1)));
- *(p->FoundState = ONE_STATE(p->MinContext)) = tmp;
+
+ s = ONE_STATE(mc);
+ *s = *stats;
+ s->Freq = (Byte)freq; // (freq <= 260 / 4)
+ p->FoundState = s;
+ InsertNode(p, stats, U2I(n0));
return;
}
- n0 = (numStats + 1) >> 1;
- n1 = (p->MinContext->NumStats + 1) >> 1;
+
+ n1 = (numStatsNew + 1) >> 1;
if (n0 != n1)
- p->MinContext->Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1));
+ {
+ // p->MinContext->Union4.Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1));
+ unsigned i0 = U2I(n0);
+ unsigned i1 = U2I(n1);
+ if (i0 != i1)
+ {
+ if (p->FreeList[i1] != 0)
+ {
+ void *ptr = RemoveNode(p, i1);
+ p->MinContext->Union4.Stats = STATS_REF(ptr);
+ MyMem12Cpy(ptr, (const void *)stats, n1);
+ InsertNode(p, stats, i0);
+ }
+ else
+ SplitBlock(p, stats, i0, i1);
+ }
+ }
+ }
+ {
+ CPpmd7_Context *mc = p->MinContext;
+ mc->Union2.SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1));
+ // Escape_Freq halving here
+ p->FoundState = STATS(mc);
}
- p->MinContext->SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1));
- p->FoundState = STATS(p->MinContext);
}
+
CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq)
{
CPpmd_See *see;
- unsigned nonMasked = p->MinContext->NumStats - numMasked;
- if (p->MinContext->NumStats != 256)
+ const CPpmd7_Context *mc = p->MinContext;
+ unsigned numStats = mc->NumStats;
+ if (numStats != 256)
{
- see = p->See[(unsigned)p->NS2Indx[(size_t)nonMasked - 1]] +
- (nonMasked < (unsigned)SUFFIX(p->MinContext)->NumStats - p->MinContext->NumStats) +
- 2 * (unsigned)(p->MinContext->SummFreq < 11 * p->MinContext->NumStats) +
- 4 * (unsigned)(numMasked > nonMasked) +
+ unsigned nonMasked = numStats - numMasked;
+ see = p->See[(unsigned)p->NS2Indx[(size_t)nonMasked - 1]]
+ + (nonMasked < (unsigned)SUFFIX(mc)->NumStats - numStats)
+ + 2 * (unsigned)(mc->Union2.SummFreq < 11 * numStats)
+ + 4 * (unsigned)(numMasked > nonMasked) +
p->HiBitsFlag;
{
- unsigned r = (see->Summ >> see->Shift);
- see->Summ = (UInt16)(see->Summ - r);
+ // if (see->Summ) field is larger than 16-bit, we need only low 16 bits of Summ
+ unsigned summ = (UInt16)see->Summ; // & 0xFFFF
+ unsigned r = (summ >> see->Shift);
+ see->Summ = (UInt16)(summ - r);
*escFreq = r + (r == 0);
}
}
@@ -660,53 +947,158 @@ CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq)
return see;
}
+
static void NextContext(CPpmd7 *p)
{
CTX_PTR c = CTX(SUCCESSOR(p->FoundState));
- if (p->OrderFall == 0 && (Byte *)c > p->Text)
- p->MinContext = p->MaxContext = c;
+ if (p->OrderFall == 0 && (const Byte *)c > p->Text)
+ p->MaxContext = p->MinContext = c;
else
- UpdateModel(p);
+ Ppmd7_UpdateModel(p);
}
+
void Ppmd7_Update1(CPpmd7 *p)
{
CPpmd_State *s = p->FoundState;
- s->Freq += 4;
- p->MinContext->SummFreq += 4;
- if (s[0].Freq > s[-1].Freq)
+ unsigned freq = s->Freq;
+ freq += 4;
+ p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4);
+ s->Freq = (Byte)freq;
+ if (freq > s[-1].Freq)
{
- SwapStates(&s[0], &s[-1]);
+ SwapStates(s);
p->FoundState = --s;
- if (s->Freq > MAX_FREQ)
+ if (freq > MAX_FREQ)
Rescale(p);
}
NextContext(p);
}
+
void Ppmd7_Update1_0(CPpmd7 *p)
{
- p->PrevSuccess = (2 * p->FoundState->Freq > p->MinContext->SummFreq);
- p->RunLength += p->PrevSuccess;
- p->MinContext->SummFreq += 4;
- if ((p->FoundState->Freq += 4) > MAX_FREQ)
+ CPpmd_State *s = p->FoundState;
+ CPpmd7_Context *mc = p->MinContext;
+ unsigned freq = s->Freq;
+ unsigned summFreq = mc->Union2.SummFreq;
+ p->PrevSuccess = (2 * freq > summFreq);
+ p->RunLength += (int)p->PrevSuccess;
+ mc->Union2.SummFreq = (UInt16)(summFreq + 4);
+ freq += 4;
+ s->Freq = (Byte)freq;
+ if (freq > MAX_FREQ)
Rescale(p);
NextContext(p);
}
+
+/*
void Ppmd7_UpdateBin(CPpmd7 *p)
{
- p->FoundState->Freq = (Byte)(p->FoundState->Freq + (p->FoundState->Freq < 128 ? 1: 0));
+ unsigned freq = p->FoundState->Freq;
+ p->FoundState->Freq = (Byte)(freq + (freq < 128));
p->PrevSuccess = 1;
p->RunLength++;
NextContext(p);
}
+*/
void Ppmd7_Update2(CPpmd7 *p)
{
- p->MinContext->SummFreq += 4;
- if ((p->FoundState->Freq += 4) > MAX_FREQ)
- Rescale(p);
+ CPpmd_State *s = p->FoundState;
+ unsigned freq = s->Freq;
+ freq += 4;
p->RunLength = p->InitRL;
- UpdateModel(p);
+ p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4);
+ s->Freq = (Byte)freq;
+ if (freq > MAX_FREQ)
+ Rescale(p);
+ Ppmd7_UpdateModel(p);
+}
+
+
+
+/*
+PPMd Memory Map:
+{
+ [ 0 ] contains subset of original raw text, that is required to create context
+ records, Some symbols are not written, when max order context was reached
+ [ Text ] free area
+ [ UnitsStart ] CPpmd_State vectors and CPpmd7_Context records
+ [ LoUnit ] free area for CPpmd_State and CPpmd7_Context items
+[ HiUnit ] CPpmd7_Context records
+ [ Size ] end of array
}
+
+These addresses don't cross at any time.
+And the following condtions is true for addresses:
+ (0 <= Text < UnitsStart <= LoUnit <= HiUnit <= Size)
+
+Raw text is BYTE--aligned.
+the data in block [ UnitsStart ... Size ] contains 12-bytes aligned UNITs.
+
+Last UNIT of array at offset (Size - 12) is root order-0 CPpmd7_Context record.
+The code can free UNITs memory blocks that were allocated to store CPpmd_State vectors.
+The code doesn't free UNITs allocated for CPpmd7_Context records.
+
+The code calls RestartModel(), when there is no free memory for allocation.
+And RestartModel() changes the state to orignal start state, with full free block.
+
+
+The code allocates UNITs with the following order:
+
+Allocation of 1 UNIT for Context record
+ - from free space (HiUnit) down to (LoUnit)
+ - from FreeList[0]
+ - AllocUnitsRare()
+
+AllocUnits() for CPpmd_State vectors:
+ - from FreeList[i]
+ - from free space (LoUnit) up to (HiUnit)
+ - AllocUnitsRare()
+
+AllocUnitsRare()
+ - if (GlueCount == 0)
+ { Glue lists, GlueCount = 255, allocate from FreeList[i]] }
+ - loop for all higher sized FreeList[...] lists
+ - from (UnitsStart - Text), GlueCount--
+ - ERROR
+
+
+Each Record with Context contains the CPpmd_State vector, where each
+CPpmd_State contains the link to Successor.
+There are 3 types of Successor:
+ 1) NULL-Successor - NULL pointer. NULL-Successor links can be stored
+ only in 0-order Root Context Record.
+ We use 0 value as NULL-Successor
+ 2) RAW-Successor - the link to position in raw text,
+ that "RAW-Successor" is being created after first
+ occurrence of new symbol for some existing context record.
+ (RAW-Successor > 0).
+ 3) RECORD-Successor - the link to CPpmd7_Context record of (Order+1),
+ that record is being created when we go via RAW-Successor again.
+
+For any successors at any time: the following condtions are true for Successor links:
+(NULL-Successor < RAW-Successor < UnitsStart <= RECORD-Successor)
+
+
+---------- Symbol Frequency, SummFreq and Range in Range_Coder ----------
+
+CPpmd7_Context::SummFreq = Sum(Stats[].Freq) + Escape_Freq
+
+The PPMd code tries to fulfill the condition:
+ (SummFreq <= (256 * 128 = RC::kBot))
+
+We have (Sum(Stats[].Freq) <= 256 * 124), because of (MAX_FREQ = 124)
+So (4 = 128 - 124) is average reserve for Escape_Freq for each symbol.
+If (CPpmd_State::Freq) is not aligned for 4, the reserve can be 5, 6 or 7.
+SummFreq and Escape_Freq can be changed in Rescale() and *Update*() functions.
+Rescale() can remove symbols only from max-order contexts. So Escape_Freq can increase after multiple calls
of Rescale() for
+max-order context.
+
+When the PPMd code still break (Total <= RC::Range) condition in range coder,
+we have two ways to resolve that problem:
+ 1) we can report error, if we want to keep compatibility with original PPMd code that has no fix for such
cases.
+ 2) we can reduce (Total) value to (RC::Range) by reducing (Escape_Freq) part of (Total) value.
+*/
diff --git a/cut-n-paste/unarr/lzmasdk/Ppmd7.h b/cut-n-paste/unarr/lzmasdk/Ppmd7.h
index 610539a0..d31809ae 100644
--- a/cut-n-paste/unarr/lzmasdk/Ppmd7.h
+++ b/cut-n-paste/unarr/lzmasdk/Ppmd7.h
@@ -1,10 +1,8 @@
-/* Ppmd7.h -- PPMdH compression codec
-2018-07-04 : Igor Pavlov : Public domain
-This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
-
-/* This code supports virtual RangeDecoder and includes the implementation
-of RangeCoder from 7z, instead of RangeCoder from original PPMd var.H.
-If you need the compatibility with original PPMd var.H, you can use external RangeDecoder */
+/* Ppmd7.h -- Ppmd7 (PPMdH) compression codec
+2021-04-13 : Igor Pavlov : Public domain
+This code is based on:
+ PPMd var.H (2001): Dmitry Shkarin : Public domain */
+
#ifndef __PPMD7_H
#define __PPMD7_H
@@ -21,23 +19,56 @@ EXTERN_C_BEGIN
struct CPpmd7_Context_;
-typedef
- #ifdef PPMD_32BIT
- struct CPpmd7_Context_ *
- #else
- UInt32
- #endif
- CPpmd7_Context_Ref;
+typedef Ppmd_Ref_Type(struct CPpmd7_Context_) CPpmd7_Context_Ref;
+
+// MY_CPU_pragma_pack_push_1
typedef struct CPpmd7_Context_
{
UInt16 NumStats;
- UInt16 SummFreq;
- CPpmd_State_Ref Stats;
+
+
+ union
+ {
+ UInt16 SummFreq;
+ CPpmd_State2 State2;
+ } Union2;
+
+ union
+ {
+ CPpmd_State_Ref Stats;
+ CPpmd_State4 State4;
+ } Union4;
+
CPpmd7_Context_Ref Suffix;
} CPpmd7_Context;
-#define Ppmd7Context_OneState(p) ((CPpmd_State *)&(p)->SummFreq)
+// MY_CPU_pragma_pop
+
+#define Ppmd7Context_OneState(p) ((CPpmd_State *)&(p)->Union2)
+
+
+
+
+typedef struct
+{
+ UInt32 Range;
+ UInt32 Code;
+ UInt32 Low;
+ IByteIn *Stream;
+} CPpmd7_RangeDec;
+
+
+typedef struct
+{
+ UInt32 Range;
+ Byte Cache;
+ // Byte _dummy_[3];
+ UInt64 Low;
+ UInt64 CacheSize;
+ IByteOut *Stream;
+} CPpmd7z_RangeEnc;
+
typedef struct
{
@@ -48,17 +79,30 @@ typedef struct
UInt32 Size;
UInt32 GlueCount;
- Byte *Base, *LoUnit, *HiUnit, *Text, *UnitsStart;
UInt32 AlignOffset;
+ Byte *Base, *LoUnit, *HiUnit, *Text, *UnitsStart;
- Byte Indx2Units[PPMD_NUM_INDEXES];
+
+
+
+ union
+ {
+ CPpmd7_RangeDec dec;
+ CPpmd7z_RangeEnc enc;
+ } rc;
+
+ Byte Indx2Units[PPMD_NUM_INDEXES + 2]; // +2 for alignment
Byte Units2Indx[128];
CPpmd_Void_Ref FreeList[PPMD_NUM_INDEXES];
- Byte NS2Indx[256], NS2BSIndx[256], HB2Flag[256];
+
+ Byte NS2BSIndx[256], NS2Indx[256];
+ Byte ExpEscape[16];
CPpmd_See DummySee, See[25][16];
UInt16 BinSumm[128][64];
+ // int LastSymbol;
} CPpmd7;
+
void Ppmd7_Construct(CPpmd7 *p);
BoolInt Ppmd7_Alloc(CPpmd7 *p, UInt32 size, ISzAllocPtr alloc);
void Ppmd7_Free(CPpmd7 *p, ISzAllocPtr alloc);
@@ -68,74 +112,69 @@ void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder);
/* ---------- Internal Functions ---------- */
-extern const Byte PPMD7_kExpEscape[16];
-
-#ifdef PPMD_32BIT
- #define Ppmd7_GetPtr(p, ptr) (ptr)
- #define Ppmd7_GetContext(p, ptr) (ptr)
- #define Ppmd7_GetStats(p, ctx) ((ctx)->Stats)
-#else
- #define Ppmd7_GetPtr(p, offs) ((void *)((p)->Base + (offs)))
- #define Ppmd7_GetContext(p, offs) ((CPpmd7_Context *)Ppmd7_GetPtr((p), (offs)))
- #define Ppmd7_GetStats(p, ctx) ((CPpmd_State *)Ppmd7_GetPtr((p), ((ctx)->Stats)))
-#endif
+#define Ppmd7_GetPtr(p, ptr) Ppmd_GetPtr(p, ptr)
+#define Ppmd7_GetContext(p, ptr) Ppmd_GetPtr_Type(p, ptr, CPpmd7_Context)
+#define Ppmd7_GetStats(p, ctx) Ppmd_GetPtr_Type(p, (ctx)->Union4.Stats, CPpmd_State)
void Ppmd7_Update1(CPpmd7 *p);
void Ppmd7_Update1_0(CPpmd7 *p);
void Ppmd7_Update2(CPpmd7 *p);
-void Ppmd7_UpdateBin(CPpmd7 *p);
+
+#define PPMD7_HiBitsFlag_3(sym) ((((unsigned)sym + 0xC0) >> (8 - 3)) & (1 << 3))
+#define PPMD7_HiBitsFlag_4(sym) ((((unsigned)sym + 0xC0) >> (8 - 4)) & (1 << 4))
+// #define PPMD7_HiBitsFlag_3(sym) ((sym) < 0x40 ? 0 : (1 << 3))
+// #define PPMD7_HiBitsFlag_4(sym) ((sym) < 0x40 ? 0 : (1 << 4))
#define Ppmd7_GetBinSumm(p) \
- &p->BinSumm[(size_t)(unsigned)Ppmd7Context_OneState(p->MinContext)->Freq - 1][p->PrevSuccess + \
- p->NS2BSIndx[(size_t)Ppmd7_GetContext(p, p->MinContext->Suffix)->NumStats - 1] + \
- (p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol]) + \
- 2 * p->HB2Flag[(unsigned)Ppmd7Context_OneState(p->MinContext)->Symbol] + \
- ((p->RunLength >> 26) & 0x20)]
+ &p->BinSumm[(size_t)(unsigned)Ppmd7Context_OneState(p->MinContext)->Freq - 1] \
+ [ p->PrevSuccess + ((p->RunLength >> 26) & 0x20) \
+ + p->NS2BSIndx[(size_t)Ppmd7_GetContext(p, p->MinContext->Suffix)->NumStats - 1] \
+ + PPMD7_HiBitsFlag_4(Ppmd7Context_OneState(p->MinContext)->Symbol) \
+ + (p->HiBitsFlag = PPMD7_HiBitsFlag_3(p->FoundState->Symbol)) ]
CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *scale);
+/*
+We support two versions of Ppmd7 (PPMdH) methods that use same CPpmd7 structure:
+ 1) Ppmd7a_*: original PPMdH
+ 2) Ppmd7z_*: modified PPMdH with 7z Range Coder
+Ppmd7_*: the structures and functions that are common for both versions of PPMd7 (PPMdH)
+*/
+
/* ---------- Decode ---------- */
-typedef struct IPpmd7_RangeDec IPpmd7_RangeDec;
+#define PPMD7_SYM_END (-1)
+#define PPMD7_SYM_ERROR (-2)
-struct IPpmd7_RangeDec
-{
- UInt32 (*GetThreshold)(const IPpmd7_RangeDec *p, UInt32 total);
- void (*Decode)(const IPpmd7_RangeDec *p, UInt32 start, UInt32 size);
- UInt32 (*DecodeBit)(const IPpmd7_RangeDec *p, UInt32 size0);
-};
+/*
+You must set (CPpmd7::rc.dec.Stream) before Ppmd7*_RangeDec_Init()
-typedef struct
-{
- IPpmd7_RangeDec vt;
- UInt32 Range;
- UInt32 Code;
- IByteIn *Stream;
-} CPpmd7z_RangeDec;
+Ppmd7*_DecodeSymbol()
+out:
+ >= 0 : decoded byte
+ -1 : PPMD7_SYM_END : End of payload marker
+ -2 : PPMD7_SYM_ERROR : Data error
+*/
-void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p);
-BoolInt Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p);
-#define Ppmd7z_RangeDec_IsFinishedOK(p) ((p)->Code == 0)
+/* Ppmd7a_* : original PPMdH */
+BoolInt Ppmd7a_RangeDec_Init(CPpmd7_RangeDec *p);
+#define Ppmd7a_RangeDec_IsFinishedOK(p) ((p)->Code == 0)
+int Ppmd7a_DecodeSymbol(CPpmd7 *p);
-int Ppmd7_DecodeSymbol(CPpmd7 *p, const IPpmd7_RangeDec *rc);
+/* Ppmd7z_* : modified PPMdH with 7z Range Coder */
+BoolInt Ppmd7z_RangeDec_Init(CPpmd7_RangeDec *p);
+#define Ppmd7z_RangeDec_IsFinishedOK(p) ((p)->Code == 0)
+int Ppmd7z_DecodeSymbol(CPpmd7 *p);
+// Byte *Ppmd7z_DecodeSymbols(CPpmd7 *p, Byte *buf, const Byte *lim);
/* ---------- Encode ---------- */
-typedef struct
-{
- UInt64 Low;
- UInt32 Range;
- Byte Cache;
- UInt64 CacheSize;
- IByteOut *Stream;
-} CPpmd7z_RangeEnc;
-
-void Ppmd7z_RangeEnc_Init(CPpmd7z_RangeEnc *p);
-void Ppmd7z_RangeEnc_FlushData(CPpmd7z_RangeEnc *p);
-
-void Ppmd7_EncodeSymbol(CPpmd7 *p, CPpmd7z_RangeEnc *rc, int symbol);
+void Ppmd7z_Init_RangeEnc(CPpmd7 *p);
+void Ppmd7z_Flush_RangeEnc(CPpmd7 *p);
+// void Ppmd7z_EncodeSymbol(CPpmd7 *p, int symbol);
+void Ppmd7z_EncodeSymbols(CPpmd7 *p, const Byte *buf, const Byte *lim);
EXTERN_C_END
diff --git a/cut-n-paste/unarr/lzmasdk/Ppmd7Dec.c b/cut-n-paste/unarr/lzmasdk/Ppmd7Dec.c
index 311e9f9d..55d74ff9 100644
--- a/cut-n-paste/unarr/lzmasdk/Ppmd7Dec.c
+++ b/cut-n-paste/unarr/lzmasdk/Ppmd7Dec.c
@@ -1,6 +1,8 @@
-/* Ppmd7Dec.c -- PPMdH Decoder
-2018-07-04 : Igor Pavlov : Public domain
-This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
+/* Ppmd7Dec.c -- Ppmd7z (PPMdH with 7z Range Coder) Decoder
+2021-04-13 : Igor Pavlov : Public domain
+This code is based on:
+ PPMd var.H (2001): Dmitry Shkarin : Public domain */
+
#include "Precomp.h"
@@ -8,184 +10,288 @@ This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
#define kTopValue (1 << 24)
-BoolInt Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p)
+
+#define READ_BYTE(p) IByteIn_Read((p)->Stream)
+
+BoolInt Ppmd7z_RangeDec_Init(CPpmd7_RangeDec *p)
{
unsigned i;
p->Code = 0;
p->Range = 0xFFFFFFFF;
- if (IByteIn_Read(p->Stream) != 0)
+ if (READ_BYTE(p) != 0)
return False;
for (i = 0; i < 4; i++)
- p->Code = (p->Code << 8) | IByteIn_Read(p->Stream);
+ p->Code = (p->Code << 8) | READ_BYTE(p);
return (p->Code < 0xFFFFFFFF);
}
-#define GET_Ppmd7z_RangeDec CPpmd7z_RangeDec *p = CONTAINER_FROM_VTBL(pp, CPpmd7z_RangeDec, vt);
-
-static UInt32 Range_GetThreshold(const IPpmd7_RangeDec *pp, UInt32 total)
-{
- GET_Ppmd7z_RangeDec
- return p->Code / (p->Range /= total);
-}
+#define RC_NORM_BASE(p) if ((p)->Range < kTopValue) \
+ { (p)->Code = ((p)->Code << 8) | READ_BYTE(p); (p)->Range <<= 8;
-static void Range_Normalize(CPpmd7z_RangeDec *p)
-{
- if (p->Range < kTopValue)
- {
- p->Code = (p->Code << 8) | IByteIn_Read(p->Stream);
- p->Range <<= 8;
- if (p->Range < kTopValue)
- {
- p->Code = (p->Code << 8) | IByteIn_Read(p->Stream);
- p->Range <<= 8;
- }
- }
-}
+#define RC_NORM_1(p) RC_NORM_BASE(p) }
+#define RC_NORM(p) RC_NORM_BASE(p) RC_NORM_BASE(p) }}
-static void Range_Decode(const IPpmd7_RangeDec *pp, UInt32 start, UInt32 size)
-{
- GET_Ppmd7z_RangeDec
- p->Code -= start * p->Range;
- p->Range *= size;
- Range_Normalize(p);
-}
+// we must use only one type of Normalization from two: LOCAL or REMOTE
+#define RC_NORM_LOCAL(p) // RC_NORM(p)
+#define RC_NORM_REMOTE(p) RC_NORM(p)
-static UInt32 Range_DecodeBit(const IPpmd7_RangeDec *pp, UInt32 size0)
-{
- GET_Ppmd7z_RangeDec
- UInt32 newBound = (p->Range >> 14) * size0;
- UInt32 symbol;
- if (p->Code < newBound)
- {
- symbol = 0;
- p->Range = newBound;
- }
- else
- {
- symbol = 1;
- p->Code -= newBound;
- p->Range -= newBound;
- }
- Range_Normalize(p);
- return symbol;
-}
+#define R (&p->rc.dec)
-void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p)
+MY_FORCE_INLINE
+// MY_NO_INLINE
+static void RangeDec_Decode(CPpmd7 *p, UInt32 start, UInt32 size)
{
- p->vt.GetThreshold = Range_GetThreshold;
- p->vt.Decode = Range_Decode;
- p->vt.DecodeBit = Range_DecodeBit;
+
+
+ R->Code -= start * R->Range;
+ R->Range *= size;
+ RC_NORM_LOCAL(R)
}
+#define RC_Decode(start, size) RangeDec_Decode(p, start, size);
+#define RC_DecodeFinal(start, size) RC_Decode(start, size) RC_NORM_REMOTE(R)
+#define RC_GetThreshold(total) (R->Code / (R->Range /= (total)))
+
-#define MASK(sym) ((signed char *)charMask)[sym]
+#define CTX(ref) ((CPpmd7_Context *)Ppmd7_GetContext(p, ref))
+typedef CPpmd7_Context * CTX_PTR;
+#define SUCCESSOR(p) Ppmd_GET_SUCCESSOR(p)
+void Ppmd7_UpdateModel(CPpmd7 *p);
-int Ppmd7_DecodeSymbol(CPpmd7 *p, const IPpmd7_RangeDec *rc)
+#define MASK(sym) ((unsigned char *)charMask)[sym]
+// MY_FORCE_INLINE
+// static
+int Ppmd7z_DecodeSymbol(CPpmd7 *p)
{
size_t charMask[256 / sizeof(size_t)];
+
if (p->MinContext->NumStats != 1)
{
CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext);
unsigned i;
UInt32 count, hiCnt;
- if ((count = rc->GetThreshold(rc, p->MinContext->SummFreq)) < (hiCnt = s->Freq))
+ UInt32 summFreq = p->MinContext->Union2.SummFreq;
+
+
+
+
+ count = RC_GetThreshold(summFreq);
+ hiCnt = count;
+
+ if ((Int32)(count -= s->Freq) < 0)
{
- Byte symbol;
- rc->Decode(rc, 0, s->Freq);
+ Byte sym;
+ RC_DecodeFinal(0, s->Freq);
p->FoundState = s;
- symbol = s->Symbol;
+ sym = s->Symbol;
Ppmd7_Update1_0(p);
- return symbol;
+ return sym;
}
+
p->PrevSuccess = 0;
- i = p->MinContext->NumStats - 1;
+ i = (unsigned)p->MinContext->NumStats - 1;
+
do
{
- if ((hiCnt += (++s)->Freq) > count)
+ if ((Int32)(count -= (++s)->Freq) < 0)
{
- Byte symbol;
- rc->Decode(rc, hiCnt - s->Freq, s->Freq);
+ Byte sym;
+ RC_DecodeFinal((hiCnt - count) - s->Freq, s->Freq);
p->FoundState = s;
- symbol = s->Symbol;
+ sym = s->Symbol;
Ppmd7_Update1(p);
- return symbol;
+ return sym;
}
}
while (--i);
- if (count >= p->MinContext->SummFreq)
- return -2;
- p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];
- rc->Decode(rc, hiCnt, p->MinContext->SummFreq - hiCnt);
+
+ if (hiCnt >= summFreq)
+ return PPMD7_SYM_ERROR;
+
+ hiCnt -= count;
+ RC_Decode(hiCnt, summFreq - hiCnt);
+
+ p->HiBitsFlag = PPMD7_HiBitsFlag_3(p->FoundState->Symbol);
PPMD_SetAllBitsIn256Bytes(charMask);
- MASK(s->Symbol) = 0;
- i = p->MinContext->NumStats - 1;
- do { MASK((--s)->Symbol) = 0; } while (--i);
+ // i = p->MinContext->NumStats - 1;
+ // do { MASK((--s)->Symbol) = 0; } while (--i);
+ {
+ CPpmd_State *s2 = Ppmd7_GetStats(p, p->MinContext);
+ MASK(s->Symbol) = 0;
+ do
+ {
+ unsigned sym0 = s2[0].Symbol;
+ unsigned sym1 = s2[1].Symbol;
+ s2 += 2;
+ MASK(sym0) = 0;
+ MASK(sym1) = 0;
+ }
+ while (s2 < s);
+ }
}
else
{
+ CPpmd_State *s = Ppmd7Context_OneState(p->MinContext);
UInt16 *prob = Ppmd7_GetBinSumm(p);
- if (rc->DecodeBit(rc, *prob) == 0)
+ UInt32 pr = *prob;
+ UInt32 size0 = (R->Range >> 14) * pr;
+ pr = PPMD_UPDATE_PROB_1(pr);
+
+ if (R->Code < size0)
{
- Byte symbol;
- *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);
- symbol = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol;
- Ppmd7_UpdateBin(p);
- return symbol;
+ Byte sym;
+ *prob = (UInt16)(pr + (1 << PPMD_INT_BITS));
+
+ // RangeDec_DecodeBit0(size0);
+ R->Range = size0;
+ RC_NORM_1(R)
+ /* we can use single byte normalization here because of
+ (min(BinSumm[][]) = 95) > (1 << (14 - 8)) */
+
+ // sym = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol;
+ // Ppmd7_UpdateBin(p);
+ {
+ unsigned freq = s->Freq;
+ CTX_PTR c = CTX(SUCCESSOR(s));
+ sym = s->Symbol;
+ p->FoundState = s;
+ p->PrevSuccess = 1;
+ p->RunLength++;
+ s->Freq = (Byte)(freq + (freq < 128));
+ // NextContext(p);
+ if (p->OrderFall == 0 && (const Byte *)c > p->Text)
+ p->MaxContext = p->MinContext = c;
+ else
+ Ppmd7_UpdateModel(p);
+ }
+ return sym;
}
- *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);
- p->InitEsc = PPMD7_kExpEscape[*prob >> 10];
+
+ *prob = (UInt16)pr;
+ p->InitEsc = p->ExpEscape[pr >> 10];
+
+ // RangeDec_DecodeBit1(size0);
+
+ R->Code -= size0;
+ R->Range -= size0;
+ RC_NORM_LOCAL(R)
+
PPMD_SetAllBitsIn256Bytes(charMask);
MASK(Ppmd7Context_OneState(p->MinContext)->Symbol) = 0;
p->PrevSuccess = 0;
}
+
for (;;)
{
- CPpmd_State *ps[256], *s;
+ CPpmd_State *s, *s2;
UInt32 freqSum, count, hiCnt;
+
CPpmd_See *see;
- unsigned i, num, numMasked = p->MinContext->NumStats;
+ CPpmd7_Context *mc;
+ unsigned numMasked;
+ RC_NORM_REMOTE(R)
+ mc = p->MinContext;
+ numMasked = mc->NumStats;
+
do
{
p->OrderFall++;
- if (!p->MinContext->Suffix)
- return -1;
- p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);
+ if (!mc->Suffix)
+ return PPMD7_SYM_END;
+ mc = Ppmd7_GetContext(p, mc->Suffix);
}
- while (p->MinContext->NumStats == numMasked);
- hiCnt = 0;
- s = Ppmd7_GetStats(p, p->MinContext);
- i = 0;
- num = p->MinContext->NumStats - numMasked;
- do
+ while (mc->NumStats == numMasked);
+
+ s = Ppmd7_GetStats(p, mc);
+
{
- int k = (int)(MASK(s->Symbol));
- hiCnt += (s->Freq & k);
- ps[i] = s++;
- i -= k;
+ unsigned num = mc->NumStats;
+ unsigned num2 = num / 2;
+
+ num &= 1;
+ hiCnt = (s->Freq & (unsigned)(MASK(s->Symbol))) & (0 - (UInt32)num);
+ s += num;
+ p->MinContext = mc;
+
+ do
+ {
+ unsigned sym0 = s[0].Symbol;
+ unsigned sym1 = s[1].Symbol;
+ s += 2;
+ hiCnt += (s[-2].Freq & (unsigned)(MASK(sym0)));
+ hiCnt += (s[-1].Freq & (unsigned)(MASK(sym1)));
+ }
+ while (--num2);
}
- while (i != num);
-
+
see = Ppmd7_MakeEscFreq(p, numMasked, &freqSum);
freqSum += hiCnt;
- count = rc->GetThreshold(rc, freqSum);
+
+
+
+
+ count = RC_GetThreshold(freqSum);
if (count < hiCnt)
{
- Byte symbol;
- CPpmd_State **pps = ps;
- for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++);
- s = *pps;
- rc->Decode(rc, hiCnt - s->Freq, s->Freq);
+ Byte sym;
+
+ s = Ppmd7_GetStats(p, p->MinContext);
+ hiCnt = count;
+ // count -= s->Freq & (unsigned)(MASK(s->Symbol));
+ // if ((Int32)count >= 0)
+ {
+ for (;;)
+ {
+ count -= s->Freq & (unsigned)(MASK((s)->Symbol)); s++; if ((Int32)count < 0) break;
+ // count -= s->Freq & (unsigned)(MASK((s)->Symbol)); s++; if ((Int32)count < 0) break;
+ };
+ }
+ s--;
+ RC_DecodeFinal((hiCnt - count) - s->Freq, s->Freq);
+
+ // new (see->Summ) value can overflow over 16-bits in some rare cases
Ppmd_See_Update(see);
p->FoundState = s;
- symbol = s->Symbol;
+ sym = s->Symbol;
Ppmd7_Update2(p);
- return symbol;
+ return sym;
}
+
if (count >= freqSum)
- return -2;
- rc->Decode(rc, hiCnt, freqSum - hiCnt);
+ return PPMD7_SYM_ERROR;
+
+ RC_Decode(hiCnt, freqSum - hiCnt);
+
+ // We increase (see->Summ) for sum of Freqs of all non_Masked symbols.
+ // new (see->Summ) value can overflow over 16-bits in some rare cases
see->Summ = (UInt16)(see->Summ + freqSum);
- do { MASK(ps[--i]->Symbol) = 0; } while (i != 0);
+
+ s = Ppmd7_GetStats(p, p->MinContext);
+ s2 = s + p->MinContext->NumStats;
+ do
+ {
+ MASK(s->Symbol) = 0;
+ s++;
+ }
+ while (s != s2);
+ }
+}
+
+/*
+Byte *Ppmd7z_DecodeSymbols(CPpmd7 *p, Byte *buf, const Byte *lim)
+{
+ int sym = 0;
+ if (buf != lim)
+ do
+ {
+ sym = Ppmd7z_DecodeSymbol(p);
+ if (sym < 0)
+ break;
+ *buf = (Byte)sym;
}
+ while (++buf < lim);
+ p->LastSymbol = sym;
+ return buf;
}
+*/
diff --git a/cut-n-paste/unarr/rar/rar.h b/cut-n-paste/unarr/rar/rar.h
index 0e112224..783f9f75 100644
--- a/cut-n-paste/unarr/rar/rar.h
+++ b/cut-n-paste/unarr/rar/rar.h
@@ -142,7 +142,7 @@ struct ByteReader {
};
struct CPpmdRAR_RangeDec {
- IPpmd7_RangeDec super;
+ CPpmd7_RangeDec super;
UInt32 Range;
UInt32 Code;
UInt32 Low;
diff --git a/cut-n-paste/unarr/rar/uncompress-rar.c b/cut-n-paste/unarr/rar/uncompress-rar.c
index 45a9d86c..53449ba3 100644
--- a/cut-n-paste/unarr/rar/uncompress-rar.c
+++ b/cut-n-paste/unarr/rar/uncompress-rar.c
@@ -68,46 +68,8 @@ static void PpmdRAR_RangeDec_Init(struct CPpmdRAR_RangeDec *p)
}
}
-static UInt32 Range_GetThreshold(const IPpmd7_RangeDec *p, UInt32 total)
-{
- struct CPpmdRAR_RangeDec *self = (struct CPpmdRAR_RangeDec *) p;
- return self->Code / (self->Range /= total);
-}
-
-static void Range_Decode_RAR(const IPpmd7_RangeDec *p, UInt32 start, UInt32 size)
-{
- struct CPpmdRAR_RangeDec *self = (struct CPpmdRAR_RangeDec *) p;
- self->Low += start * self->Range;
- self->Code -= start * self->Range;
- self->Range *= size;
- for (;;) {
- if ((self->Low ^ (self->Low + self->Range)) >= (1 << 24)) {
- if (self->Range >= (1 << 15))
- break;
- self->Range = ((uint32_t)(-(int32_t)self->Low)) & ((1 << 15) - 1);
- }
- self->Code = (self->Code << 8) | self->Stream->Read(self->Stream);
- self->Range <<= 8;
- self->Low <<= 8;
- }
-}
-
-static UInt32 Range_DecodeBit_RAR(const IPpmd7_RangeDec *p, UInt32 size0)
-{
- UInt32 value = Range_GetThreshold(p, PPMD_BIN_SCALE);
- UInt32 bit = value < size0 ? 0 : 1;
- if (!bit)
- Range_Decode_RAR(p, 0, size0);
- else
- Range_Decode_RAR(p, size0, PPMD_BIN_SCALE - size0);
- return bit;
-}
-
static void PpmdRAR_RangeDec_CreateVTable(struct CPpmdRAR_RangeDec *p, IByteIn *stream)
{
- p->super.GetThreshold = Range_GetThreshold;
- p->super.Decode = Range_Decode_RAR;
- p->super.DecodeBit = Range_DecodeBit_RAR;
p->Stream = stream;
}
@@ -716,7 +678,7 @@ static bool rar_read_filter(ar_archive_rar *rar, bool (* decode_byte)(ar_archive
static inline bool rar_decode_ppmd7_symbol(struct ar_archive_rar_uncomp_v3 *uncomp_v3, Byte *symbol)
{
- int value = Ppmd7_DecodeSymbol(&uncomp_v3->ppmd7_context, &uncomp_v3->range_dec.super);
+ int value = Ppmd7z_DecodeSymbol(&uncomp_v3->ppmd7_context);
if (value < 0) {
warn("Invalid data in bitstream"); /* invalid PPMd symbol */
return false;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
