From 63ecd747dee413f785d9a30d8b859335da2df049 Mon Sep 17 00:00:00 2001 From: inikep Date: Fri, 13 May 2016 11:27:56 +0200 Subject: [PATCH] added common/entropy_common.c --- contrib/cmake/lib/CMakeLists.txt | 1 + lib/Makefile | 2 +- lib/common/entropy_common.c | 158 ++++++++++++++++++ lib/common/zstd_common.c | 123 +------------- programs/Makefile | 4 +- visual/2013/fullbench/fullbench.vcxproj | 1 + .../2013/fullbench/fullbench.vcxproj.filters | 3 + visual/2013/fuzzer/fuzzer.vcxproj | 1 + visual/2013/fuzzer/fuzzer.vcxproj.filters | 3 + visual/2013/zstd/zstd.vcxproj | 1 + visual/2013/zstd/zstd.vcxproj.filters | 3 + visual/2013/zstdlib/zstdlib.vcxproj | 1 + visual/2013/zstdlib/zstdlib.vcxproj.filters | 3 + 13 files changed, 180 insertions(+), 124 deletions(-) create mode 100644 lib/common/entropy_common.c diff --git a/contrib/cmake/lib/CMakeLists.txt b/contrib/cmake/lib/CMakeLists.txt index dff147670..dae706cbe 100644 --- a/contrib/cmake/lib/CMakeLists.txt +++ b/contrib/cmake/lib/CMakeLists.txt @@ -57,6 +57,7 @@ GetLibraryVersion("${HEADER_CONTENT}" LIBVER_MAJOR LIBVER_MINOR LIBVER_RELEASE) MESSAGE("ZSTD VERSION ${LIBVER_MAJOR}.${LIBVER_MINOR}.${LIBVER_RELEASE}") SET(Sources + ${LIBRARY_DIR}/common/entropy_common.c ${LIBRARY_DIR}/common/zstd_common.c ${LIBRARY_DIR}/common/fse_decompress.c ${LIBRARY_DIR}/compress/fse_compress.c diff --git a/lib/Makefile b/lib/Makefile index 5969437de..5ea014dd1 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -54,7 +54,7 @@ INCLUDEDIR=$(PREFIX)/include ZSTDCOMP_FILES := compress/zstd_compress.c compress/fse_compress.c compress/huf_compress.c compress/zbuff_compress.c ZSTDDECOMP_FILES := decompress/zstd_decompress.c common/fse_decompress.c decompress/huf_decompress.c decompress/zbuff_decompress.c ZSTDDICT_FILES := dictBuilder/zdict.c dictBuilder/divsufsort.c -ZSTD_FILES := $(ZSTDDECOMP_FILES) common/zstd_common.c $(ZSTDCOMP_FILES) $(ZSTDDICT_FILES) +ZSTD_FILES := $(ZSTDDECOMP_FILES) common/entropy_common.c common/zstd_common.c $(ZSTDCOMP_FILES) $(ZSTDDICT_FILES) ZSTD_LEGACY:= legacy/zstd_v01.c legacy/zstd_v02.c legacy/zstd_v03.c legacy/zstd_v04.c legacy/zstd_v05.c ifeq ($(ZSTD_LEGACY_SUPPORT), 0) diff --git a/lib/common/entropy_common.c b/lib/common/entropy_common.c new file mode 100644 index 000000000..b4c366e61 --- /dev/null +++ b/lib/common/entropy_common.c @@ -0,0 +1,158 @@ +/* + Common functions of New Generation Entropy library + Copyright (C) 2016, Yann Collet. + + BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are + met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following disclaimer + in the documentation and/or other materials provided with the + distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + You can contact the author at : + - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy + - Public forum : https://groups.google.com/forum/#!forum/lz4c +*************************************************************************** */ + +/* ************************************* +* Dependencies +***************************************/ +#include +#include "mem.h" +#include "fse_static.h" /* FSE_MIN_TABLELOG */ +#include "error_private.h" +#include "fse.h" /* declaration of FSE_isError, FSE_getErrorName */ +#include "huf.h" /* declaration of HUF_isError, HUF_getErrorName */ + + + +/*-**************************************** +* FSE Error Management +******************************************/ +unsigned FSE_isError(size_t code) { return ERR_isError(code); } + +const char* FSE_getErrorName(size_t code) { return ERR_getErrorName(code); } + + +/* ************************************************************** +* HUF Error Management +****************************************************************/ +unsigned HUF_isError(size_t code) { return ERR_isError(code); } + +const char* HUF_getErrorName(size_t code) { return ERR_getErrorName(code); } + + +/*-************************************************************** +* FSE NCount encoding-decoding +****************************************************************/ +static short FSE_abs(short a) { return a<0 ? -a : a; } + +size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, + const void* headerBuffer, size_t hbSize) +{ + const BYTE* const istart = (const BYTE*) headerBuffer; + const BYTE* const iend = istart + hbSize; + const BYTE* ip = istart; + int nbBits; + int remaining; + int threshold; + U32 bitStream; + int bitCount; + unsigned charnum = 0; + int previous0 = 0; + + if (hbSize < 4) return ERROR(srcSize_wrong); + bitStream = MEM_readLE32(ip); + nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ + if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); + bitStream >>= 4; + bitCount = 4; + *tableLogPtr = nbBits; + remaining = (1<1) && (charnum<=*maxSVPtr)) { + if (previous0) { + unsigned n0 = charnum; + while ((bitStream & 0xFFFF) == 0xFFFF) { + n0+=24; + if (ip < iend-5) { + ip+=2; + bitStream = MEM_readLE32(ip) >> bitCount; + } else { + bitStream >>= 16; + bitCount+=16; + } } + while ((bitStream & 3) == 3) { + n0+=3; + bitStream>>=2; + bitCount+=2; + } + n0 += bitStream & 3; + bitCount += 2; + if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); + while (charnum < n0) normalizedCounter[charnum++] = 0; + if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { + ip += bitCount>>3; + bitCount &= 7; + bitStream = MEM_readLE32(ip) >> bitCount; + } + else + bitStream >>= 2; + } + { short const max = (short)((2*threshold-1)-remaining); + short count; + + if ((bitStream & (threshold-1)) < (U32)max) { + count = (short)(bitStream & (threshold-1)); + bitCount += nbBits-1; + } else { + count = (short)(bitStream & (2*threshold-1)); + if (count >= threshold) count -= max; + bitCount += nbBits; + } + + count--; /* extra accuracy */ + remaining -= FSE_abs(count); + normalizedCounter[charnum++] = count; + previous0 = !count; + while (remaining < threshold) { + nbBits--; + threshold >>= 1; + } + + if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { + ip += bitCount>>3; + bitCount &= 7; + } else { + bitCount -= (int)(8 * (iend - 4 - ip)); + ip = iend - 4; + } + bitStream = MEM_readLE32(ip) >> (bitCount & 31); + } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */ + if (remaining != 1) return ERROR(GENERIC); + *maxSVPtr = charnum-1; + + ip += (bitCount+7)>>3; + if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); + return ip-istart; +} diff --git a/lib/common/zstd_common.c b/lib/common/zstd_common.c index 1b3340889..8812c0388 100644 --- a/lib/common/zstd_common.c +++ b/lib/common/zstd_common.c @@ -33,14 +33,9 @@ /*-************************************* * Dependencies ***************************************/ -#include -#include "mem.h" -#include "fse_static.h" /* FSE_MIN_TABLELOG */ #include "error_private.h" -#include "zstd.h" /* declaration of ZSTD_isError, ZSTD_getErrorName */ -#include "zbuff.h" /* declaration of ZBUFF_isError, ZBUFF_getErrorName */ -#include "fse.h" /* declaration of FSE_isError, FSE_getErrorName */ -#include "huf.h" /* declaration of HUF_isError, HUF_getErrorName */ +#include "zstd.h" /* declaration of ZSTD_isError, ZSTD_getErrorName */ +#include "zbuff.h" /* declaration of ZBUFF_isError, ZBUFF_getErrorName */ /*-**************************************** @@ -69,123 +64,9 @@ ZSTD_ErrorCode ZSTD_getErrorCode(size_t code) { return ERR_getErrorCode(code); } const char* ZSTD_getErrorString(ZSTD_ErrorCode code) { return ERR_getErrorName(code); } -/*-**************************************** -* FSE Error Management -******************************************/ -unsigned FSE_isError(size_t code) { return ERR_isError(code); } - -const char* FSE_getErrorName(size_t code) { return ERR_getErrorName(code); } - - -/* ************************************************************** -* HUF Error Management -****************************************************************/ -unsigned HUF_isError(size_t code) { return ERR_isError(code); } - -const char* HUF_getErrorName(size_t code) { return ERR_getErrorName(code); } - - /* ************************************************************** * ZBUFF Error Management ****************************************************************/ unsigned ZBUFF_isError(size_t errorCode) { return ERR_isError(errorCode); } const char* ZBUFF_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } - - -/*-************************************************************** -* FSE NCount decoding -****************************************************************/ -static short FSE_abs(short a) { return a<0 ? -a : a; } - -size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, - const void* headerBuffer, size_t hbSize) -{ - const BYTE* const istart = (const BYTE*) headerBuffer; - const BYTE* const iend = istart + hbSize; - const BYTE* ip = istart; - int nbBits; - int remaining; - int threshold; - U32 bitStream; - int bitCount; - unsigned charnum = 0; - int previous0 = 0; - - if (hbSize < 4) return ERROR(srcSize_wrong); - bitStream = MEM_readLE32(ip); - nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ - if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); - bitStream >>= 4; - bitCount = 4; - *tableLogPtr = nbBits; - remaining = (1<1) && (charnum<=*maxSVPtr)) { - if (previous0) { - unsigned n0 = charnum; - while ((bitStream & 0xFFFF) == 0xFFFF) { - n0+=24; - if (ip < iend-5) { - ip+=2; - bitStream = MEM_readLE32(ip) >> bitCount; - } else { - bitStream >>= 16; - bitCount+=16; - } } - while ((bitStream & 3) == 3) { - n0+=3; - bitStream>>=2; - bitCount+=2; - } - n0 += bitStream & 3; - bitCount += 2; - if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); - while (charnum < n0) normalizedCounter[charnum++] = 0; - if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { - ip += bitCount>>3; - bitCount &= 7; - bitStream = MEM_readLE32(ip) >> bitCount; - } - else - bitStream >>= 2; - } - { short const max = (short)((2*threshold-1)-remaining); - short count; - - if ((bitStream & (threshold-1)) < (U32)max) { - count = (short)(bitStream & (threshold-1)); - bitCount += nbBits-1; - } else { - count = (short)(bitStream & (2*threshold-1)); - if (count >= threshold) count -= max; - bitCount += nbBits; - } - - count--; /* extra accuracy */ - remaining -= FSE_abs(count); - normalizedCounter[charnum++] = count; - previous0 = !count; - while (remaining < threshold) { - nbBits--; - threshold >>= 1; - } - - if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { - ip += bitCount>>3; - bitCount &= 7; - } else { - bitCount -= (int)(8 * (iend - 4 - ip)); - ip = iend - 4; - } - bitStream = MEM_readLE32(ip) >> (bitCount & 31); - } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */ - if (remaining != 1) return ERROR(GENERIC); - *maxSVPtr = charnum-1; - - ip += (bitCount+7)>>3; - if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); - return ip-istart; -} diff --git a/programs/Makefile b/programs/Makefile index efbbaabcd..70434cedc 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -53,8 +53,8 @@ BINDIR = $(PREFIX)/bin MANDIR = $(PREFIX)/share/man/man1 ZSTDDIR = ../lib -ZSTDCOMP_FILES := $(ZSTDDIR)/common/fse_decompress.c $(ZSTDDIR)/compress/zstd_compress.c $(ZSTDDIR)/compress/fse_compress.c $(ZSTDDIR)/compress/huf_compress.c $(ZSTDDIR)/common/zstd_common.c -ZSTDDECOMP_FILES := $(ZSTDDIR)/decompress/zstd_decompress.c $(ZSTDDIR)/common/fse_decompress.c $(ZSTDDIR)/decompress/huf_decompress.c $(ZSTDDIR)/common/zstd_common.c +ZSTDCOMP_FILES := $(ZSTDDIR)/common/fse_decompress.c $(ZSTDDIR)/compress/zstd_compress.c $(ZSTDDIR)/compress/fse_compress.c $(ZSTDDIR)/compress/huf_compress.c $(ZSTDDIR)/common/zstd_common.c $(ZSTDDIR)/common/entropy_common.c +ZSTDDECOMP_FILES := $(ZSTDDIR)/decompress/zstd_decompress.c $(ZSTDDIR)/common/fse_decompress.c $(ZSTDDIR)/decompress/huf_decompress.c $(ZSTDDIR)/common/zstd_common.c $(ZSTDDIR)/common/entropy_common.c ZDICT_FILES := $(ZSTDDIR)/dictBuilder/zdict.c $(ZSTDDIR)/dictBuilder/divsufsort.c ZBUFF_FILES := $(ZSTDDIR)/compress/zbuff_compress.c $(ZSTDDIR)/decompress/zbuff_decompress.c ZSTD_FILES := $(ZSTDDECOMP_FILES) $(ZSTDCOMP_FILES) diff --git a/visual/2013/fullbench/fullbench.vcxproj b/visual/2013/fullbench/fullbench.vcxproj index 95f98d6bb..c24105ee3 100644 --- a/visual/2013/fullbench/fullbench.vcxproj +++ b/visual/2013/fullbench/fullbench.vcxproj @@ -156,6 +156,7 @@ + diff --git a/visual/2013/fullbench/fullbench.vcxproj.filters b/visual/2013/fullbench/fullbench.vcxproj.filters index 168094772..75d738c91 100644 --- a/visual/2013/fullbench/fullbench.vcxproj.filters +++ b/visual/2013/fullbench/fullbench.vcxproj.filters @@ -44,6 +44,9 @@ Source Files + + Source Files + diff --git a/visual/2013/fuzzer/fuzzer.vcxproj b/visual/2013/fuzzer/fuzzer.vcxproj index 635c3c846..5fd5f5b48 100644 --- a/visual/2013/fuzzer/fuzzer.vcxproj +++ b/visual/2013/fuzzer/fuzzer.vcxproj @@ -156,6 +156,7 @@ + diff --git a/visual/2013/fuzzer/fuzzer.vcxproj.filters b/visual/2013/fuzzer/fuzzer.vcxproj.filters index b2abefbc0..fbbc183ae 100644 --- a/visual/2013/fuzzer/fuzzer.vcxproj.filters +++ b/visual/2013/fuzzer/fuzzer.vcxproj.filters @@ -41,6 +41,9 @@ Source Files + + Source Files + diff --git a/visual/2013/zstd/zstd.vcxproj b/visual/2013/zstd/zstd.vcxproj index 5ada0e199..d6f7edd66 100755 --- a/visual/2013/zstd/zstd.vcxproj +++ b/visual/2013/zstd/zstd.vcxproj @@ -19,6 +19,7 @@ + diff --git a/visual/2013/zstd/zstd.vcxproj.filters b/visual/2013/zstd/zstd.vcxproj.filters index 87666627f..4c1a64a69 100755 --- a/visual/2013/zstd/zstd.vcxproj.filters +++ b/visual/2013/zstd/zstd.vcxproj.filters @@ -80,6 +80,9 @@ Source Files + + Source Files + diff --git a/visual/2013/zstdlib/zstdlib.vcxproj b/visual/2013/zstdlib/zstdlib.vcxproj index bcfac4995..94da3e5d3 100644 --- a/visual/2013/zstdlib/zstdlib.vcxproj +++ b/visual/2013/zstdlib/zstdlib.vcxproj @@ -19,6 +19,7 @@ + diff --git a/visual/2013/zstdlib/zstdlib.vcxproj.filters b/visual/2013/zstdlib/zstdlib.vcxproj.filters index 367a26c09..327f3a26e 100644 --- a/visual/2013/zstdlib/zstdlib.vcxproj.filters +++ b/visual/2013/zstdlib/zstdlib.vcxproj.filters @@ -48,6 +48,9 @@ Source Files + + Source Files + -- 2.47.2