mercurial-scm/hg: contrib/python-zstandard/zstd/common/fse

annotate contrib/python-zstandard/zstd/common/fse_decompress.c @ 30434:2e484bdea8c4

zstd: vendor zstd 1.1.1 zstd is a new compression format and it is awesome, yielding higher compression ratios and significantly faster compression and decompression operations compared to zlib (our current compression engine of choice) across the board. We want zstd to be a 1st class citizen in Mercurial and to eventually be the preferred compression format for various operations. This patch starts the formal process of supporting zstd by vendoring a copy of zstd. Why do we need to vendor zstd? Good question. First, zstd is relatively new and not widely available yet. If we didn't vendor zstd or distribute it with Mercurial, most users likely wouldn't have zstd installed or even available to install. What good is a feature if you can't use it? Vendoring and distributing the zstd sources gives us the highest liklihood that zstd will be available to Mercurial installs. Second, the Python bindings to zstd (which will be vendored in a separate changeset) make use of zstd APIs that are only available via static linking. One reason they are only available via static linking is that they are unstable and could change at any time. While it might be possible for the Python bindings to attempt to talk to different versions of the zstd C library, the safest thing to do is link against a specific, known-working version of zstd. This is why the Python zstd bindings themselves vendor zstd and why we must as well. This also explains why the added files are in a "python-zstandard" directory. The added files are from the 1.1.1 release of zstd (Git commit 4c0b44f8ced84c4c8edfa07b564d31e4fa3e8885 from https://github.com/facebook/zstd) and are added without modifications. Not all files from the zstd "distribution" have been added. Notably missing are files to support interacting with "legacy," pre-1.0 versions of zstd. The decision of which files to include is made by the upstream python-zstandard project (which I'm the author of). The files in this commit are a snapshot of the files from the 0.5.0 release of that project, Git commit e637c1b214d5f869cf8116c550dcae23ec13b677 from https://github.com/indygreg/python-zstandard.

author	Gregory Szorc <gregory.szorc@gmail.com>
date	Thu, 10 Nov 2016 21:45:29 -0800
parents
children	b54a2984cdd4

rev	line source
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1 /* ******************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	2 FSE : Finite State Entropy decoder
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	3 Copyright (C) 2013-2015, Yann Collet.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	4
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	6
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	7 Redistribution and use in source and binary forms, with or without
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	8 modification, are permitted provided that the following conditions are
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	9 met:
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	10
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	11 * Redistributions of source code must retain the above copyright
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	12 notice, this list of conditions and the following disclaimer.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	13 * Redistributions in binary form must reproduce the above
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	14 copyright notice, this list of conditions and the following disclaimer
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	15 in the documentation and/or other materials provided with the
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	16 distribution.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	17
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	29
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	30 You can contact the author at :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	31 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	32 - Public forum : https://groups.google.com/forum/#!forum/lz4c
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	33 ****************************************************************** */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	34
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	35
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	36 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	37 * Compiler specifics
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	38 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	39 #ifdef _MSC_VER /* Visual Studio */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	40 # define FORCE_INLINE static __forceinline
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	41 # include <intrin.h> /* For Visual 2005 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	42 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	43 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44 #else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	45 # if defined (__cplusplus) \|\| defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46 # ifdef __GNUC__
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	47 # define FORCE_INLINE static inline __attribute__((always_inline))
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48 # else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49 # define FORCE_INLINE static inline
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50 # endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 # else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 # define FORCE_INLINE static
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53 # endif /* __STDC_VERSION__ */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	55
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	56
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	57 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	58 * Includes
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	59 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	60 #include <stdlib.h> /* malloc, free, qsort */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	61 #include <string.h> /* memcpy, memset */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	62 #include <stdio.h> /* printf (debug) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	63 #include "bitstream.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	64 #define FSE_STATIC_LINKING_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	65 #include "fse.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	66
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	67
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	68 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	69 * Error Management
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	70 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	71 #define FSE_isError ERR_isError
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	72 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only after variable declarations */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	73
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74 /* check and forward error code */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75 #define CHECK_F(f) { size_t const e = f; if (FSE_isError(e)) return e; }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	76
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	77
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	78 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	79 * Complex types
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	80 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	81 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	82
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	83
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	84 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	85 * Templates
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	86 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	87 /*
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	88 designed to be included
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	89 for type-specific functions (template emulation in C)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	90 Objective is to write these functions only once, for improved maintenance
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	93 /* safety checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	94 #ifndef FSE_FUNCTION_EXTENSION
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	95 # error "FSE_FUNCTION_EXTENSION must be defined"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	96 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	97 #ifndef FSE_FUNCTION_TYPE
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	98 # error "FSE_FUNCTION_TYPE must be defined"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	99 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	100
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	101 /* Function names */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	102 #define FSE_CAT(X,Y) X##Y
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	103 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	104 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	105
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	106
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	107 /* Function templates */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	108 FSE_DTable* FSE_createDTable (unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	109 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	110 if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	111 return (FSE_DTable)malloc( FSE_DTABLE_SIZE_U32(tableLog) sizeof (U32) );
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	112 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	113
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	114 void FSE_freeDTable (FSE_DTable* dt)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	115 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	116 free(dt);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	117 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	118
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	119 size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	120 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	121 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits /
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	122 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	123 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125 U32 const maxSV1 = maxSymbolValue + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 U32 const tableSize = 1 << tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127 U32 highThreshold = tableSize-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 /* Sanity Checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	133 /* Init, lay down lowprob symbols */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	134 { FSE_DTableHeader DTableH;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	135 DTableH.tableLog = (U16)tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 DTableH.fastMode = 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137 { S16 const largeLimit= (S16)(1 << (tableLog-1));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 U32 s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	139 for (s=0; s<maxSV1; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140 if (normalizedCounter[s]==-1) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	141 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 symbolNext[s] = 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 symbolNext[s] = normalizedCounter[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146 } } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147 memcpy(dt, &DTableH, sizeof(DTableH));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	148 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	150 /* Spread symbols */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	151 { U32 const tableMask = tableSize-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	152 U32 const step = FSE_TABLESTEP(tableSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	153 U32 s, position = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	154 for (s=0; s<maxSV1; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	155 int i;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	156 for (i=0; i<normalizedCounter[s]; i++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	157 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	158 position = (position + step) & tableMask;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	159 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	160 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	161 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	162 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	163
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	164 /* Build Decoding table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	165 { U32 u;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	166 for (u=0; u<tableSize; u++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167 FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 U16 nextState = symbolNext[symbol]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	170 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	172
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	174 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	176
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	177 #ifndef FSE_COMMONDEFS_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	178
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	179 /-******************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	180 * Decompression (Byte symbols)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	181 *********************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	182 size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	183 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	184 void* ptr = dt;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	185 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	186 void* dPtr = dt + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	187 FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	188
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	189 DTableH->tableLog = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	190 DTableH->fastMode = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	191
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	192 cell->newState = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	193 cell->symbol = symbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	194 cell->nbBits = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	195
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	196 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	197 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	198
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	200 size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	202 void* ptr = dt;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	203 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	204 void* dPtr = dt + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	205 FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	206 const unsigned tableSize = 1 << nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	207 const unsigned tableMask = tableSize - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	208 const unsigned maxSV1 = tableMask+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	209 unsigned s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	210
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	211 /* Sanity checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	212 if (nbBits < 1) return ERROR(GENERIC); /* min size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	213
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	214 /* Build Decoding Table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	215 DTableH->tableLog = (U16)nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	216 DTableH->fastMode = 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	217 for (s=0; s<maxSV1; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	218 dinfo[s].newState = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	219 dinfo[s].symbol = (BYTE)s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	220 dinfo[s].nbBits = (BYTE)nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	221 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	222
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	223 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	224 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	225
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	226 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	227 void* dst, size_t maxDstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	228 const void* cSrc, size_t cSrcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	229 const FSE_DTable* dt, const unsigned fast)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	230 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	231 BYTE* const ostart = (BYTE*) dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	232 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	233 BYTE* const omax = op + maxDstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	234 BYTE* const olimit = omax-3;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 BIT_DStream_t bitD;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 FSE_DState_t state1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 FSE_DState_t state2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 /* Init */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243 FSE_initDState(&state1, &bitD, dt);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244 FSE_initDState(&state2, &bitD, dt);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 /* 4 symbols per loop */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) & (op<olimit) ; op+=4) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 op[0] = FSE_GETSYMBOL(&state1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 if (FSE_MAX_TABLELOG2+7 > sizeof(bitD.bitContainer)8) /* This test must be static */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 BIT_reloadDStream(&bitD);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 op[1] = FSE_GETSYMBOL(&state2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 if (FSE_MAX_TABLELOG4+7 > sizeof(bitD.bitContainer)8) /* This test must be static */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 op[2] = FSE_GETSYMBOL(&state1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 if (FSE_MAX_TABLELOG2+7 > sizeof(bitD.bitContainer)8) /* This test must be static */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 BIT_reloadDStream(&bitD);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 op[3] = FSE_GETSYMBOL(&state2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268 /* tail */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 while (1) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 *op++ = FSE_GETSYMBOL(&state1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	274 *op++ = FSE_GETSYMBOL(&state2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	275 break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	276 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 *op++ = FSE_GETSYMBOL(&state2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	281 *op++ = FSE_GETSYMBOL(&state1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	282 break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285 return op-ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290 const void* cSrc, size_t cSrcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 const FSE_DTable* dt)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	293 const void* ptr = dt;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294 const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295 const U32 fastMode = DTableH->fastMode;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 /* select fast mode (static) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298 if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	303 size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	304 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 const BYTE* const istart = (const BYTE*)cSrc;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306 const BYTE* ip = istart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307 short counting[FSE_MAX_SYMBOL_VALUE+1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 unsigned tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	311
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	313
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 /* normal FSE decoding mode */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315 { size_t const NCountLength = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	316 if (FSE_isError(NCountLength)) return NCountLength;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	317 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 ip += NCountLength;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	319 cSrcSize -= NCountLength;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	320 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322 CHECK_F( FSE_buildDTable (dt, counting, maxSymbolValue, tableLog) );
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	327
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	328
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	329 #endif /* FSE_COMMONDEFS_ONLY */

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/common/fse_decompress.c @ 30434:2e484bdea8c4