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

annotate contrib/python-zstandard/zstd/compress/fse_compress.c @ 30822:b54a2984cdd4

zstd: vendor python-zstandard 0.6.0 Commit 63c68d6f5fc8de4afd9bde81b13b537beb4e47e8 from https://github.com/indygreg/python-zstandard is imported without modifications (other than removing unwanted files). This includes minor performance and feature improvements. It also changes the vendored zstd library from 1.1.1 to 1.1.2. # no-check-commit

author	Gregory Szorc <gregory.szorc@gmail.com>
date	Sat, 14 Jan 2017 19:41:43 -0800
parents	2e484bdea8c4
children	b1fb341d8a61

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 encoder
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 * Compiler specifics
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	37 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	38 #ifdef _MSC_VER /* Visual Studio */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	39 # define FORCE_INLINE static __forceinline
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	40 # include <intrin.h> /* For Visual 2005 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	41 # 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	42 # 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	43 #else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44 # 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	45 # ifdef __GNUC__
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46 # define FORCE_INLINE static inline __attribute__((always_inline))
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	47 # else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48 # define FORCE_INLINE static inline
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49 # endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50 # else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 # define FORCE_INLINE static
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 # endif /* __STDC_VERSION__ */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54
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 * Includes
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	58 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	59 #include <stdlib.h> /* malloc, free, qsort */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	60 #include <string.h> /* memcpy, memset */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	61 #include <stdio.h> /* printf (debug) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	62 #include "bitstream.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	63 #define FSE_STATIC_LINKING_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	64 #include "fse.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	65
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 * Error Management
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	69 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	70 #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	71
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	72
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 * Templates
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75 ****************************************************************/
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 designed to be included
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	78 for type-specific functions (template emulation in C)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	79 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	80 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	81
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	82 /* safety checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	83 #ifndef FSE_FUNCTION_EXTENSION
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	84 # error "FSE_FUNCTION_EXTENSION must be defined"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	85 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	86 #ifndef FSE_FUNCTION_TYPE
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	87 # error "FSE_FUNCTION_TYPE must be defined"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	88 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	89
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	90 /* Function names */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 #define FSE_CAT(X,Y) X##Y
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92 #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	93 #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	94
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	95
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	96 /* Function templates */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	97
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	98 /* FSE_buildCTable_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	99 * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	100 * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)`
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	101 * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	102 */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	103 size_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	104 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	105 U32 const tableSize = 1 << tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	106 U32 const tableMask = tableSize - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	107 void* const ptr = ct;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	108 U16* const tableU16 = ( (U16*) ptr) + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	109 void* const FSCT = ((U32)ptr) + 1 / header */ + (tableLog ? tableSize>>1 : 1) ;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	110 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	111 U32 const step = FSE_TABLESTEP(tableSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	112 U32 cumul[FSE_MAX_SYMBOL_VALUE+2];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	113
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	114 FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	115 U32 highThreshold = tableSize-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	116
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	117 /* CTable header */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	118 if (((size_t)1 << tableLog) * sizeof(FSE_FUNCTION_TYPE) > wkspSize) return ERROR(tableLog_tooLarge);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	119 tableU16[-2] = (U16) tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	120 tableU16[-1] = (U16) maxSymbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	121
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	122 /* For explanations on how to distribute symbol values over the table :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	123 * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
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 /* symbol start positions */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 { U32 u;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127 cumul[0] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 for (u=1; u<=maxSymbolValue+1; u++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 if (normalizedCounter[u-1]==-1) { /* Low proba symbol */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 cumul[u] = cumul[u-1] + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	133 cumul[u] = cumul[u-1] + normalizedCounter[u-1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	134 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	135 cumul[maxSymbolValue+1] = tableSize+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 /* Spread symbols */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	139 { U32 position = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140 U32 symbol;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	141 for (symbol=0; symbol<=maxSymbolValue; symbol++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 int nbOccurences;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143 for (nbOccurences=0; nbOccurences<normalizedCounter[symbol]; nbOccurences++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144 tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 position = (position + step) & tableMask;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146 while (position > highThreshold) position = (position + step) & tableMask; /* Low proba area */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147 } }
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 if (position!=0) return ERROR(GENERIC); /* Must have gone through all positions */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	150 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	151
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	152 /* Build table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	153 { U32 u; for (u=0; u<tableSize; u++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	154 FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	155 tableU16[cumul[s]++] = (U16) (tableSize+u); /* TableU16 : sorted by symbol order; gives next state value */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	156 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	157
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	158 /* Build Symbol Transformation Table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	159 { unsigned total = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	160 unsigned s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	161 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	162 switch (normalizedCounter[s])
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 case 0: break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	165
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	166 case -1:
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167 case 1:
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 symbolTT[s].deltaFindState = total - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	170 total ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171 break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	172 default :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	174 U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175 U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	176 symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	177 symbolTT[s].deltaFindState = total - normalizedCounter[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	178 total += normalizedCounter[s];
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	181 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	182 }
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
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	185 size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	186 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	187 FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	188 return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(tableSymbol));
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	189 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	190
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	191
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	192
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	193 #ifndef FSE_COMMONDEFS_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	194
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 * FSE NCount encoding-decoding
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 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	200 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	202 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	203
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	204 static short FSE_abs(short a) { return (short)(a<0 ? -a : a); }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	205
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	206 static size_t FSE_writeNCount_generic (void* header, size_t headerBufferSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	207 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	208 unsigned writeIsSafe)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	209 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	210 BYTE* const ostart = (BYTE*) header;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	211 BYTE* out = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	212 BYTE* const oend = ostart + headerBufferSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	213 int nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	214 const int tableSize = 1 << tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	215 int remaining;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	216 int threshold;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	217 U32 bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	218 int bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	219 unsigned charnum = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	220 int previous0 = 0;
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 bitStream = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	223 bitCount = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	224 /* Table Size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	225 bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	226 bitCount += 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	227
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	228 /* Init */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	229 remaining = tableSize+1; /* +1 for extra accuracy */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	230 threshold = tableSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	231 nbBits = tableLog+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	232
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	233 while (remaining>1) { /* stops at 1 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	234 if (previous0) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235 unsigned start = charnum;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 while (!normalizedCounter[charnum]) charnum++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 while (charnum >= start+24) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 start+=24;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239 bitStream += 0xFFFFU << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 if ((!writeIsSafe) && (out > oend-2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 out[0] = (BYTE) bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243 out+=2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244 bitStream>>=16;
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 while (charnum >= start+3) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247 start+=3;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 bitStream += 3 << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 bitStream += (charnum-start) << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 if (bitCount>16) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254 if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 out[0] = (BYTE)bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 out += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 bitStream >>= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259 bitCount -= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 { short count = normalizedCounter[charnum++];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 const short max = (short)((2*threshold-1)-remaining);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 remaining -= FSE_abs(count);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264 if (remaining<1) return ERROR(GENERIC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 count++; /* +1 for extra accuracy */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 if (count>=threshold) count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2threshold[ /
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267 bitStream += count << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268 bitCount += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 bitCount -= (count<max);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 previous0 = (count==1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 while (remaining<threshold) nbBits--, threshold>>=1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 if (bitCount>16) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	274 if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	275 out[0] = (BYTE)bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	276 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277 out += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 bitStream >>= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 bitCount -= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	281
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	282 /* flush remaining bitStream */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284 out[0] = (BYTE)bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 out+= (bitCount+7) /8;
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 if (charnum > maxSymbolValue + 1) return ERROR(GENERIC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290 return (out-ostart);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 }
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294 size_t FSE_writeNCount (void* buffer, size_t bufferSize, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 if (tableLog > FSE_MAX_TABLELOG) return ERROR(GENERIC); /* Unsupported */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
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 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	303 }
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307 /-*************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308 * Counting histogram
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 /*! FSE_count_simple
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	311 This function counts byte values within `src`, and store the histogram into table `count`.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	312 It doesn't use any additional memory.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	313 But this function is unsafe : it doesn't check that all values within `src` can fit into `count`.
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 For this reason, prefer using a table `count` with 256 elements.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315 @return : count of most numerous element
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	316 */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	317 size_t FSE_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	318 const void* src, size_t srcSize)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	319 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	320 const BYTE* ip = (const BYTE*)src;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321 const BYTE* const end = ip + srcSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322 unsigned maxSymbolValue = *maxSymbolValuePtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 unsigned max=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325 memset(count, 0, (maxSymbolValue+1)sizeof(count));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326 if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
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 while (ip<end) count[*ip++]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	329
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	330 while (!count[maxSymbolValue]) maxSymbolValue--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	331 *maxSymbolValuePtr = maxSymbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	332
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	333 { U32 s; for (s=0; s<=maxSymbolValue; s++) if (count[s] > max) max = count[s]; }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	334
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	335 return (size_t)max;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	336 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	337
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	338
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	339 /* FSE_count_parallel_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	340 * Same as FSE_count_parallel(), but using an externally provided scratch buffer.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	341 * `workSpace` size must be a minimum of `1024 * sizeof(unsigned)`` */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	342 static size_t FSE_count_parallel_wksp(
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	343 unsigned* count, unsigned* maxSymbolValuePtr,
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	344 const void* source, size_t sourceSize,
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	345 unsigned checkMax, unsigned* const workSpace)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	346 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	347 const BYTE* ip = (const BYTE*)source;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348 const BYTE* const iend = ip+sourceSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	349 unsigned maxSymbolValue = *maxSymbolValuePtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	350 unsigned max=0;
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	351 U32* const Counting1 = workSpace;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	352 U32* const Counting2 = Counting1 + 256;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	353 U32* const Counting3 = Counting2 + 256;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	354 U32* const Counting4 = Counting3 + 256;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	355
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	356 memset(Counting1, 0, 4256sizeof(unsigned));
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	357
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	358 /* safety checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	359 if (!sourceSize) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	360 memset(count, 0, maxSymbolValue + 1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	361 *maxSymbolValuePtr = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	362 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	363 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	364 if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	365
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 /* by stripes of 16 bytes */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	367 { U32 cached = MEM_read32(ip); ip += 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368 while (ip < iend-15) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369 U32 c = cached; cached = MEM_read32(ip); ip += 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370 Counting1[(BYTE) c ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 Counting2[(BYTE)(c>>8) ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372 Counting3[(BYTE)(c>>16)]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	373 Counting4[ c>>24 ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374 c = cached; cached = MEM_read32(ip); ip += 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	375 Counting1[(BYTE) c ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	376 Counting2[(BYTE)(c>>8) ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	377 Counting3[(BYTE)(c>>16)]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	378 Counting4[ c>>24 ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	379 c = cached; cached = MEM_read32(ip); ip += 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	380 Counting1[(BYTE) c ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	381 Counting2[(BYTE)(c>>8) ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 Counting3[(BYTE)(c>>16)]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383 Counting4[ c>>24 ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384 c = cached; cached = MEM_read32(ip); ip += 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	385 Counting1[(BYTE) c ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 Counting2[(BYTE)(c>>8) ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387 Counting3[(BYTE)(c>>16)]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388 Counting4[ c>>24 ]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	389 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	390 ip-=4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	391 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	392
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	393 /* finish last symbols */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394 while (ip<iend) Counting1[*ip++]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	395
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	396 if (checkMax) { /* verify stats will fit into destination table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397 U32 s; for (s=255; s>maxSymbolValue; s--) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	398 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399 if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	400 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	401
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	402 { U32 s; for (s=0; s<=maxSymbolValue; s++) {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	403 count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	404 if (count[s] > max) max = count[s];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	405 } }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	406
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	407 while (!count[maxSymbolValue]) maxSymbolValue--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	408 *maxSymbolValuePtr = maxSymbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	409 return (size_t)max;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	410 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	411
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	412 /* FSE_countFast_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	413 * Same as FSE_countFast(), but using an externally provided scratch buffer.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	414 * `workSpace` size must be table of >= `1024` unsigned */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	415 size_t FSE_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	416 const void* source, size_t sourceSize, unsigned* workSpace)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	417 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	418 if (sourceSize < 1500) return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	419 return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 0, workSpace);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	420 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	421
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	422 /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	423 size_t FSE_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424 const void* source, size_t sourceSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	425 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	426 unsigned tmpCounters[1024];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	427 return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	428 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	429
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	430 /* FSE_count_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	431 * Same as FSE_count(), but using an externally provided scratch buffer.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	432 * `workSpace` size must be table of >= `1024` unsigned */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	433 size_t FSE_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	434 const void* source, size_t sourceSize, unsigned* workSpace)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	435 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	436 if (*maxSymbolValuePtr < 255)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	437 return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 1, workSpace);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	438 *maxSymbolValuePtr = 255;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	439 return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	440 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	441
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	442 size_t FSE_count(unsigned* count, unsigned* maxSymbolValuePtr,
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	443 const void* src, size_t srcSize)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	444 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	445 unsigned tmpCounters[1024];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	446 return FSE_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	447 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	448
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	449
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	450
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	451 /-*************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 * FSE Compression Code
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	453 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	454 /*! FSE_sizeof_CTable() :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 FSE_CTable is a variable size structure which contains :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456 `U16 tableLog;`
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 `U16 maxSymbolValue;`
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458 `U16 nextStateNumber[1 << tableLog];` // This size is variable
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 `FSE_symbolCompressionTransform symbolTT[maxSymbolValue+1];` // This size is variable
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 Allocation is manual (C standard does not support variable-size structures).
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462 size_t FSE_sizeof_CTable (unsigned maxSymbolValue, unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	464 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	465 return FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	466 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	468 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 size_t size;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 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	472 size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	473 return (FSE_CTable*)malloc(size);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	474 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	475
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476 void FSE_freeCTable (FSE_CTable* ct) { free(ct); }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	477
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478 /* provides the minimum logSize to safely represent a distribution */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	479 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	480 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	481 U32 minBitsSrc = BIT_highbit32((U32)(srcSize - 1)) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	482 U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	483 U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	484 return minBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	485 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	487 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	489 U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	490 U32 tableLog = maxTableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	493 if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	494 if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495 if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496 if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	497 return tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	498 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	499
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	501 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	504
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 /* Secondary normalization method.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	507 To be used when primary method fails. */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	508
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	510 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	511 U32 s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512 U32 distributed = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	513 U32 ToDistribute;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	514
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	515 /* Init */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	516 U32 const lowThreshold = (U32)(total >> tableLog);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	518
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	519 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520 if (count[s] == 0) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	521 norm[s]=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	522 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	523 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524 if (count[s] <= lowThreshold) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	525 norm[s] = -1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	526 distributed++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	527 total -= count[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	528 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	529 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	530 if (count[s] <= lowOne) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	531 norm[s] = 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	532 distributed++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	533 total -= count[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	534 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	535 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	536 norm[s]=-2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	537 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	538 ToDistribute = (1 << tableLog) - distributed;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	539
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	540 if ((total / ToDistribute) > lowOne) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	541 /* risk of rounding to zero */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	542 lowOne = (U32)((total * 3) / (ToDistribute * 2));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	543 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	544 if ((norm[s] == -2) && (count[s] <= lowOne)) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	545 norm[s] = 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	546 distributed++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	547 total -= count[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	548 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	549 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	550 ToDistribute = (1 << tableLog) - distributed;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	551 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	552
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	553 if (distributed == maxSymbolValue+1) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	554 /* all values are pretty poor;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	555 probably incompressible data (should have already been detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	556 find max, then give all remaining points to max */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	557 U32 maxV = 0, maxC = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	558 for (s=0; s<=maxSymbolValue; s++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	559 if (count[s] > maxC) maxV=s, maxC=count[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	560 norm[maxV] += (short)ToDistribute;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	561 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	562 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	563
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	564 { U64 const vStepLog = 62 - tableLog;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	565 U64 const mid = (1ULL << (vStepLog-1)) - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	566 U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	567 U64 tmpTotal = mid;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	569 if (norm[s]==-2) {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	570 U64 const end = tmpTotal + (count[s] * rStep);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	571 U32 const sStart = (U32)(tmpTotal >> vStepLog);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	572 U32 const sEnd = (U32)(end >> vStepLog);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	573 U32 const weight = sEnd - sStart;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	574 if (weight < 1)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	575 return ERROR(GENERIC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	576 norm[s] = (short)weight;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	577 tmpTotal = end;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	578 } } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	579
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	580 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	581 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	582
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	583
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	584 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	585 const unsigned* count, size_t total,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	586 unsigned maxSymbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	587 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	588 /* Sanity checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	589 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	590 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	591 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	592 if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	593
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	594 { U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	595 U64 const scale = 62 - tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596 U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	597 U64 const vStep = 1ULL<<(scale-20);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	598 int stillToDistribute = 1<<tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	599 unsigned s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	600 unsigned largest=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	601 short largestP=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	602 U32 lowThreshold = (U32)(total >> tableLog);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	603
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	604 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	605 if (count[s] == total) return 0; /* rle special case */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	606 if (count[s] == 0) { normalizedCounter[s]=0; continue; }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	607 if (count[s] <= lowThreshold) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	608 normalizedCounter[s] = -1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	609 stillToDistribute--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	610 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	611 short proba = (short)((count[s]*step) >> scale);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	612 if (proba<8) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	613 U64 restToBeat = vStep * rtbTable[proba];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	614 proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	615 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	616 if (proba > largestP) largestP=proba, largest=s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	617 normalizedCounter[s] = proba;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	618 stillToDistribute -= proba;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	619 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	620 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	621 /* corner case, need another normalization method */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	622 size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	623 if (FSE_isError(errorCode)) return errorCode;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	624 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	625 else normalizedCounter[largest] += (short)stillToDistribute;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	626 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	627
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	628 #if 0
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	629 { /* Print Table (debug) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	630 U32 s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	631 U32 nTotal = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	632 for (s=0; s<=maxSymbolValue; s++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	633 printf("%3i: %4i \n", s, normalizedCounter[s]);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	634 for (s=0; s<=maxSymbolValue; s++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	635 nTotal += abs(normalizedCounter[s]);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	636 if (nTotal != (1U<<tableLog))
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	637 printf("Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	638 getchar();
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	639 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	640 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	641
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	642 return tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	643 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	644
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	645
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	646 /* fake FSE_CTable, for raw (uncompressed) input */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	647 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	648 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	649 const unsigned tableSize = 1 << nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	650 const unsigned tableMask = tableSize - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	651 const unsigned maxSymbolValue = tableMask;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	652 void* const ptr = ct;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	653 U16* const tableU16 = ( (U16*) ptr) + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	654 void* const FSCT = ((U32)ptr) + 1 / header / + (tableSize>>1); / assumption : tableLog >= 1 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	655 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	656 unsigned s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	657
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	658 /* Sanity checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	659 if (nbBits < 1) return ERROR(GENERIC); /* min size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	660
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	661 /* header */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	662 tableU16[-2] = (U16) nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	663 tableU16[-1] = (U16) maxSymbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	664
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	665 /* Build table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	666 for (s=0; s<tableSize; s++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	667 tableU16[s] = (U16)(tableSize + s);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	668
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	669 /* Build Symbol Transformation Table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	670 { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	671 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	672 symbolTT[s].deltaNbBits = deltaNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	673 symbolTT[s].deltaFindState = s-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	674 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	675
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	676 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	677 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	678
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	679 /* fake FSE_CTable, for rle input (always same symbol) */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	680 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	681 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	682 void* ptr = ct;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	683 U16* tableU16 = ( (U16*) ptr) + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	684 void* FSCTptr = (U32*)ptr + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	685 FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	686
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	687 /* header */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	688 tableU16[-2] = (U16) 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	689 tableU16[-1] = (U16) symbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	690
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	691 /* Build table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	692 tableU16[0] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	693 tableU16[1] = 0; /* just in case */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	694
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	695 /* Build Symbol Transformation Table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	696 symbolTT[symbolValue].deltaNbBits = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	697 symbolTT[symbolValue].deltaFindState = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	698
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	699 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	700 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	701
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	702
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	703 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	704 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	705 const FSE_CTable* ct, const unsigned fast)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	706 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	707 const BYTE* const istart = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	708 const BYTE* const iend = istart + srcSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	709 const BYTE* ip=iend;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	710
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	711 BIT_CStream_t bitC;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	712 FSE_CState_t CState1, CState2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	713
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	714 /* init */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	715 if (srcSize <= 2) return 0;
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	716 { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	717 if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	718
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	719 #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	720
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	721 if (srcSize & 1) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	722 FSE_initCState2(&CState1, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	723 FSE_initCState2(&CState2, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	724 FSE_encodeSymbol(&bitC, &CState1, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	725 FSE_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	726 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	727 FSE_initCState2(&CState2, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	728 FSE_initCState2(&CState1, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	729 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	730
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	731 /* join to mod 4 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	732 srcSize -= 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	733 if ((sizeof(bitC.bitContainer)8 > FSE_MAX_TABLELOG4+7 ) && (srcSize & 2)) { /* test bit 2 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	734 FSE_encodeSymbol(&bitC, &CState2, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	735 FSE_encodeSymbol(&bitC, &CState1, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	736 FSE_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	737 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	738
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	739 /* 2 or 4 encoding per loop */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	740 while ( ip>istart ) {
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	741
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	742 FSE_encodeSymbol(&bitC, &CState2, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	743
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	744 if (sizeof(bitC.bitContainer)8 < FSE_MAX_TABLELOG2+7 ) /* this test must be static */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	745 FSE_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	746
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	747 FSE_encodeSymbol(&bitC, &CState1, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	748
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	749 if (sizeof(bitC.bitContainer)8 > FSE_MAX_TABLELOG4+7 ) { /* this test must be static */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	750 FSE_encodeSymbol(&bitC, &CState2, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	751 FSE_encodeSymbol(&bitC, &CState1, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	752 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	753
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	754 FSE_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	755 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	756
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	757 FSE_flushCState(&bitC, &CState2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	758 FSE_flushCState(&bitC, &CState1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	759 return BIT_closeCStream(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	760 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	761
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	762 size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	763 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	764 const FSE_CTable* ct)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	765 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	766 unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	767
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	768 if (fast)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	769 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	770 else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	771 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	772 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	773
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	774
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	775 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	776
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	777 #define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return f
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	778 #define CHECK_F(f) { CHECK_V_F(_var_err__, f); }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	779
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	780 /* FSE_compress_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	781 * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`).
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	782 * `wkspSize` size must be `(1<<tableLog)`.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	783 */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	784 size_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	785 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	786 BYTE* const ostart = (BYTE*) dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	787 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	788 BYTE* const oend = ostart + dstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	789
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	790 U32 count[FSE_MAX_SYMBOL_VALUE+1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	791 S16 norm[FSE_MAX_SYMBOL_VALUE+1];
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	792 FSE_CTable* CTable = (FSE_CTable*)workSpace;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	793 size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	794 void* scratchBuffer = (void*)(CTable + CTableSize);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	795 size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable));
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	796
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	797 /* init conditions */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	798 if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	799 if (srcSize <= 1) return 0; /* Not compressible */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	800 if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	801 if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	802
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	803 /* Scan input and build symbol stats */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	804 { CHECK_V_F(maxCount, FSE_count(count, &maxSymbolValue, src, srcSize) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	805 if (maxCount == srcSize) return 1; /* only a single symbol in src : rle */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	806 if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	807 if (maxCount < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	808 }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	809
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	810 tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue);
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	811 CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	812
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	813 /* Write table description header */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	814 { CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	815 op += nc_err;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	816 }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	817
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	818 /* Compress */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	819 CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	820 { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	821 if (cSize == 0) return 0; /* not enough space for compressed data */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	822 op += cSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	823 }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	824
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	825 /* check compressibility */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	826 if ( (size_t)(op-ostart) >= srcSize-1 ) return 0;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	827
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	828 return op-ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	829 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	830
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	831 typedef struct {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	832 FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	833 BYTE scratchBuffer[1 << FSE_MAX_TABLELOG];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	834 } fseWkspMax_t;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	835
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	836 size_t FSE_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	837 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	838 fseWkspMax_t scratchBuffer;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	839 FSE_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	840 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	841 return FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, &scratchBuffer, sizeof(scratchBuffer));
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	842 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	843
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	844 size_t FSE_compress (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	845 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	846 return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	847 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	848
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	849
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	850 #endif /* FSE_COMMONDEFS_ONLY */

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/compress/fse_compress.c @ 30822:b54a2984cdd4