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

annotate contrib/python-zstandard/zstd/compress/fse_compress.c @ 40121:73fef626dae3

zstandard: vendor python-zstandard 0.10.1 This was just released. The upstream source distribution from PyPI was extracted. Unwanted files were removed. The clang-format ignore list was updated to reflect the new source of files. setup.py was updated to pass a new argument to python-zstandard's function for returning an Extension instance. Upstream had to change to use relative paths because Python 3.7's packaging doesn't seem to like absolute paths when defining sources, includes, etc. The default relative path calculation is relative to setup_zstd.py which is different from the directory of Mercurial's setup.py. The project contains a vendored copy of zstandard 1.3.6. The old version was 1.3.4. The API should be backwards compatible and nothing in core should need adjusted. However, there is a new "chunker" API that we may find useful in places where we want to emit compressed chunks of a fixed size. There are a pair of bug fixes in 0.10.0 with regards to compressobj() and decompressobj() when block flushing is used. I actually found these bugs when introducing these APIs in Mercurial! But existing Mercurial code is not affected because we don't perform block flushing. # no-check-commit because 3rd party code has different style guidelines Differential Revision: https://phab.mercurial-scm.org/D4911

author	Gregory Szorc <gregory.szorc@gmail.com>
date	Mon, 08 Oct 2018 16:27:40 -0700
parents	b1fb341d8a61
children	675775c33ab6

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
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	3 Copyright (C) 2013-present, Yann Collet.
30434 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 * Includes
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 #include <stdlib.h> /* malloc, free, qsort */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	39 #include <string.h> /* memcpy, memset */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	40 #include "compiler.h"
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	41 #include "mem.h" /* U32, U16, etc. */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	42 #include "debug.h" /* assert, DEBUGLOG */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	43 #include "hist.h" /* HIST_count_wksp */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44 #include "bitstream.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	45 #define FSE_STATIC_LINKING_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46 #include "fse.h"
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	47 #include "error_private.h"
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 * Error Management
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 ****************************************************************/
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	53 #define FSE_isError ERR_isError
30434 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 * Templates
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 /*
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	60 designed to be included
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	61 for type-specific functions (template emulation in C)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	62 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	63 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	64
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	65 /* safety checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	66 #ifndef FSE_FUNCTION_EXTENSION
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	67 # error "FSE_FUNCTION_EXTENSION must be defined"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	68 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	69 #ifndef FSE_FUNCTION_TYPE
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	70 # error "FSE_FUNCTION_TYPE must be defined"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	71 #endif
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 /* Function names */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74 #define FSE_CAT(X,Y) X##Y
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75 #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	76 #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	77
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	78
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	79 /* Function templates */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	80
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	81 /* FSE_buildCTable_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	82 * 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	83 * 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	84 * 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	85 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	86 size_t FSE_buildCTable_wksp(FSE_CTable* ct,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	87 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	88 void* workSpace, size_t wkspSize)
30434 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 U32 const tableSize = 1 << tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 U32 const tableMask = tableSize - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92 void* const ptr = ct;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	93 U16* const tableU16 = ( (U16*) ptr) + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	94 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	95 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	96 U32 const step = FSE_TABLESTEP(tableSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	97 U32 cumul[FSE_MAX_SYMBOL_VALUE+2];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	98
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	99 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	100 U32 highThreshold = tableSize-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	101
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	102 /* CTable header */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	103 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	104 tableU16[-2] = (U16) tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	105 tableU16[-1] = (U16) maxSymbolValue;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	106 assert(tableLog < 16); /* required for threshold strategy to work */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	107
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	108 /* For explanations on how to distribute symbol values over the table :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	109 * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	110
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	111 #ifdef __clang_analyzer__
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	112 memset(tableSymbol, 0, sizeof(tableSymbol) tableSize); /* useless initialization, just to keep scan-build happy */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	113 #endif
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	114
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	115 /* symbol start positions */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	116 { U32 u;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	117 cumul[0] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	118 for (u=1; u<=maxSymbolValue+1; u++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	119 if (normalizedCounter[u-1]==-1) { /* Low proba symbol */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	120 cumul[u] = cumul[u-1] + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	121 tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	122 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	123 cumul[u] = cumul[u-1] + normalizedCounter[u-1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125 cumul[maxSymbolValue+1] = tableSize+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 /* Spread symbols */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 { U32 position = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 U32 symbol;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 for (symbol=0; symbol<=maxSymbolValue; symbol++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 int nbOccurences;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	133 int const freq = normalizedCounter[symbol];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	134 for (nbOccurences=0; nbOccurences<freq; nbOccurences++) {
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	135 tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 position = (position + step) & tableMask;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	137 while (position > highThreshold)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	138 position = (position + step) & tableMask; /* Low proba area */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	139 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	141 assert(position==0); /* Must have initialized all positions */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144 /* Build table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 { U32 u; for (u=0; u<tableSize; u++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146 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	147 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	148 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	150 /* Build Symbol Transformation Table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	151 { unsigned total = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	152 unsigned s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	153 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	154 switch (normalizedCounter[s])
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	155 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	156 case 0:
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	157 /* filling nonetheless, for compatibility with FSE_getMaxNbBits() */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	158 symbolTT[s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	159 break;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	160
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	161 case -1:
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	162 case 1:
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	163 symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	164 symbolTT[s].deltaFindState = total - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	165 total ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	166 break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167 default :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 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	170 U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171 symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	172 symbolTT[s].deltaFindState = total - normalizedCounter[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 total += normalizedCounter[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	174 } } } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	176 #if 0 /* debug : symbol costs */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	177 DEBUGLOG(5, "\n --- table statistics : ");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	178 { U32 symbol;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	179 for (symbol=0; symbol<=maxSymbolValue; symbol++) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	180 DEBUGLOG(5, "%3u: w=%3i, maxBits=%u, fracBits=%.2f",
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	181 symbol, normalizedCounter[symbol],
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	182 FSE_getMaxNbBits(symbolTT, symbol),
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	183 (double)FSE_bitCost(symbolTT, tableLog, symbol, 8) / 256);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	184 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	185 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	186 #endif
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	187
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	188 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	189 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	190
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	191
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	192 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	193 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	194 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	195 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	196 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	197
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	198
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	200 #ifndef FSE_COMMONDEFS_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	202
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	203 /-*************************************************************
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	204 * FSE NCount encoding
30434 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 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	207 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	208 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	209 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	210 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	211
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	212 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	213 FSE_writeNCount_generic (void* header, size_t headerBufferSize,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	214 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	215 unsigned writeIsSafe)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	216 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	217 BYTE* const ostart = (BYTE*) header;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	218 BYTE* out = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	219 BYTE* const oend = ostart + headerBufferSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	220 int nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	221 const int tableSize = 1 << tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	222 int remaining;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	223 int threshold;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	224 U32 bitStream = 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	225 int bitCount = 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	226 unsigned symbol = 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	227 unsigned const alphabetSize = maxSymbolValue + 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	228 int previousIs0 = 0;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	229
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	230 /* Table Size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	231 bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	232 bitCount += 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	233
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	234 /* Init */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235 remaining = tableSize+1; /* +1 for extra accuracy */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 threshold = tableSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 nbBits = tableLog+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	239 while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	240 if (previousIs0) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	241 unsigned start = symbol;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	242 while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	243 if (symbol == alphabetSize) break; /* incorrect distribution */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	244 while (symbol >= start+24) {
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245 start+=24;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246 bitStream += 0xFFFFU << bitCount;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	247 if ((!writeIsSafe) && (out > oend-2))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	248 return ERROR(dstSize_tooSmall); /* Buffer overflow */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 out[0] = (BYTE) bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 out+=2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 bitStream>>=16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	254 while (symbol >= start+3) {
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 start+=3;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 bitStream += 3 << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	259 bitStream += (symbol-start) << bitCount;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 if (bitCount>16) {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	262 if ((!writeIsSafe) && (out > oend - 2))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	263 return ERROR(dstSize_tooSmall); /* Buffer overflow */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264 out[0] = (BYTE)bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 out += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267 bitStream >>= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268 bitCount -= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 } }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	270 { int count = normalizedCounter[symbol++];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	271 int const max = (2*threshold-1) - remaining;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	272 remaining -= count < 0 ? -count : count;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 count++; /* +1 for extra accuracy */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	274 if (count>=threshold)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	275 count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2threshold[ /
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	276 bitStream += count << bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277 bitCount += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 bitCount -= (count<max);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	279 previousIs0 = (count==1);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	280 if (remaining<1) return ERROR(GENERIC);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	281 while (remaining<threshold) { nbBits--; threshold>>=1; }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	282 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 if (bitCount>16) {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	284 if ((!writeIsSafe) && (out > oend - 2))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	285 return ERROR(dstSize_tooSmall); /* Buffer overflow */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 out[0] = (BYTE)bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288 out += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 bitStream >>= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290 bitCount -= 16;
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
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	293 if (remaining != 1)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	294 return ERROR(GENERIC); /* incorrect normalized distribution */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	295 assert(symbol <= alphabetSize);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	296
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 /* flush remaining bitStream */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	298 if ((!writeIsSafe) && (out > oend - 2))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	299 return ERROR(dstSize_tooSmall); /* Buffer overflow */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 out[0] = (BYTE)bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301 out[1] = (BYTE)(bitStream>>8);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 out+= (bitCount+7) /8;
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 return (out-ostart);
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
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	308 size_t FSE_writeNCount (void* buffer, size_t bufferSize,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	309 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	311 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312 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	313
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315 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	316
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	317 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 }
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321 /-*************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322 * FSE Compression Code
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	327 size_t size;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	328 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	329 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	330 return (FSE_CTable*)malloc(size);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	331 }
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 void FSE_freeCTable (FSE_CTable* ct) { free(ct); }
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 /* 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	336 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	337 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	338 U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	339 U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	340 U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	341 assert(srcSize > 1); /* Not supported, RLE should be used instead */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	342 return minBits;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	343 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	344
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	345 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	346 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	347 U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348 U32 tableLog = maxTableLog;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	349 U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	350 assert(srcSize > 1); /* Not supported, RLE should be used instead */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	351 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	352 if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	353 if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 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	355 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	356 return tableLog;
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	359 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	360 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	361 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	362 }
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	365 /* Secondary normalization method.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 To be used when primary method fails. */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	367
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368 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	369 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	370 short const NOT_YET_ASSIGNED = -2;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 U32 s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372 U32 distributed = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	373 U32 ToDistribute;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	375 /* Init */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	376 U32 const lowThreshold = (U32)(total >> tableLog);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	377 U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	378
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	379 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	380 if (count[s] == 0) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	381 norm[s]=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384 if (count[s] <= lowThreshold) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	385 norm[s] = -1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 distributed++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387 total -= count[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388 continue;
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 if (count[s] <= lowOne) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	391 norm[s] = 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	392 distributed++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	393 total -= count[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	395 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	396
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	397 norm[s]=NOT_YET_ASSIGNED;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	398 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399 ToDistribute = (1 << tableLog) - distributed;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	400
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	401 if (ToDistribute == 0)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	402 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	403
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	404 if ((total / ToDistribute) > lowOne) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	405 /* risk of rounding to zero */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	406 lowOne = (U32)((total * 3) / (ToDistribute * 2));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	407 for (s=0; s<=maxSymbolValue; s++) {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	408 if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	409 norm[s] = 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	410 distributed++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	411 total -= count[s];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	412 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	413 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	414 ToDistribute = (1 << tableLog) - distributed;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	415 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	416
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	417 if (distributed == maxSymbolValue+1) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	418 /* all values are pretty poor;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	419 probably incompressible data (should have already been detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	420 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	421 U32 maxV = 0, maxC = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	422 for (s=0; s<=maxSymbolValue; s++)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	423 if (count[s] > maxC) { maxV=s; maxC=count[s]; }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424 norm[maxV] += (short)ToDistribute;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	425 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	426 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	427
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	428 if (total == 0) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	429 /* all of the symbols were low enough for the lowOne or lowThreshold */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	430 for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	431 if (norm[s] > 0) { ToDistribute--; norm[s]++; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	432 return 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	433 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	434
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	435 { U64 const vStepLog = 62 - tableLog;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	436 U64 const mid = (1ULL << (vStepLog-1)) - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	437 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	438 U64 tmpTotal = mid;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	439 for (s=0; s<=maxSymbolValue; s++) {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	440 if (norm[s]==NOT_YET_ASSIGNED) {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	441 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	442 U32 const sStart = (U32)(tmpTotal >> vStepLog);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	443 U32 const sEnd = (U32)(end >> vStepLog);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	444 U32 const weight = sEnd - sStart;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	445 if (weight < 1)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	446 return ERROR(GENERIC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	447 norm[s] = (short)weight;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	448 tmpTotal = end;
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 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 }
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456 const unsigned* count, size_t total,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 unsigned maxSymbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 /* Sanity checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461 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	462 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	463 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	464
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	465 { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	466 U64 const scale = 62 - tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467 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	468 U64 const vStep = 1ULL<<(scale-20);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469 int stillToDistribute = 1<<tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 unsigned s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 unsigned largest=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	472 short largestP=0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	473 U32 lowThreshold = (U32)(total >> tableLog);
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 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476 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	477 if (count[s] == 0) { normalizedCounter[s]=0; continue; }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478 if (count[s] <= lowThreshold) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	479 normalizedCounter[s] = -1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	480 stillToDistribute--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	481 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	482 short proba = (short)((count[s]*step) >> scale);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	483 if (proba<8) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	484 U64 restToBeat = vStep * rtbTable[proba];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	485 proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	487 if (proba > largestP) { largestP=proba; largest=s; }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 normalizedCounter[s] = proba;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	489 stillToDistribute -= proba;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	490 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 /* 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	493 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	494 if (FSE_isError(errorCode)) return errorCode;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496 else normalizedCounter[largest] += (short)stillToDistribute;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	497 }
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 #if 0
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 { /* Print Table (debug) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	501 U32 s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 U32 nTotal = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 for (s=0; s<=maxSymbolValue; s++)
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	504 RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505 for (s=0; s<=maxSymbolValue; s++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 nTotal += abs(normalizedCounter[s]);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	507 if (nTotal != (1U<<tableLog))
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	508 RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 getchar();
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 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	513 return tableLog;
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	516
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 /* fake FSE_CTable, for raw (uncompressed) input */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	518 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	519 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520 const unsigned tableSize = 1 << nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	521 const unsigned tableMask = tableSize - 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	522 const unsigned maxSymbolValue = tableMask;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	523 void* const ptr = ct;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524 U16* const tableU16 = ( (U16*) ptr) + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	525 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	526 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	527 unsigned s;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	528
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	529 /* Sanity checks */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	530 if (nbBits < 1) return ERROR(GENERIC); /* min size */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	531
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	532 /* header */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	533 tableU16[-2] = (U16) nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	534 tableU16[-1] = (U16) maxSymbolValue;
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 /* Build table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	537 for (s=0; s<tableSize; s++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	538 tableU16[s] = (U16)(tableSize + s);
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 /* Build Symbol Transformation Table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	541 { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	542 for (s=0; s<=maxSymbolValue; s++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	543 symbolTT[s].deltaNbBits = deltaNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	544 symbolTT[s].deltaFindState = s-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	545 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	546
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	547 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	548 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	549
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	550 /* 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	551 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	552 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	553 void* ptr = ct;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	554 U16* tableU16 = ( (U16*) ptr) + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	555 void* FSCTptr = (U32*)ptr + 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	556 FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	557
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	558 /* header */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	559 tableU16[-2] = (U16) 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	560 tableU16[-1] = (U16) symbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	561
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	562 /* Build table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	563 tableU16[0] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	564 tableU16[1] = 0; /* just in case */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	565
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	566 /* Build Symbol Transformation Table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	567 symbolTT[symbolValue].deltaNbBits = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 symbolTT[symbolValue].deltaFindState = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	569
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	570 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	571 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	572
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	573
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	574 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	575 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	576 const FSE_CTable* ct, const unsigned fast)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	577 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	578 const BYTE* const istart = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	579 const BYTE* const iend = istart + srcSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	580 const BYTE* ip=iend;
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 BIT_CStream_t bitC;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	583 FSE_CState_t CState1, CState2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	584
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	585 /* init */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	586 if (srcSize <= 2) return 0;
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	587 { 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	588 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	589
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	590 #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	591
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	592 if (srcSize & 1) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	593 FSE_initCState2(&CState1, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	594 FSE_initCState2(&CState2, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	595 FSE_encodeSymbol(&bitC, &CState1, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596 FSE_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	597 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	598 FSE_initCState2(&CState2, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	599 FSE_initCState2(&CState1, ct, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	600 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	601
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	602 /* join to mod 4 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	603 srcSize -= 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	604 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	605 FSE_encodeSymbol(&bitC, &CState2, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	606 FSE_encodeSymbol(&bitC, &CState1, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	607 FSE_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	608 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	609
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	610 /* 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	611 while ( ip>istart ) {
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	612
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	613 FSE_encodeSymbol(&bitC, &CState2, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	614
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	615 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	616 FSE_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	617
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	618 FSE_encodeSymbol(&bitC, &CState1, *--ip);
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 (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	621 FSE_encodeSymbol(&bitC, &CState2, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	622 FSE_encodeSymbol(&bitC, &CState1, *--ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	623 }
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 FSE_FLUSHBITS(&bitC);
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 FSE_flushCState(&bitC, &CState2);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	629 FSE_flushCState(&bitC, &CState1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	630 return BIT_closeCStream(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	631 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	632
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	633 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	634 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	635 const FSE_CTable* ct)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	636 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	637 unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	638
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	639 if (fast)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	640 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	641 else
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	642 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	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 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	647
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	648 #define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return e
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	649 #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	650
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	651 /* FSE_compress_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	652 * 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	653 * `wkspSize` size must be `(1<<tableLog)`.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	654 */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	655 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	656 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	657 BYTE* const ostart = (BYTE*) dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	658 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	659 BYTE* const oend = ostart + dstSize;
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 U32 count[FSE_MAX_SYMBOL_VALUE+1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	662 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	663 FSE_CTable* CTable = (FSE_CTable*)workSpace;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	664 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	665 void* scratchBuffer = (void*)(CTable + CTableSize);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	666 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	667
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	668 /* init conditions */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	669 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	670 if (srcSize <= 1) return 0; /* Not compressible */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	671 if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	672 if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	673
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	674 /* Scan input and build symbol stats */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	675 { CHECK_V_F(maxCount, HIST_count_wksp(count, &maxSymbolValue, src, srcSize, (unsigned*)scratchBuffer) );
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	676 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	677 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	678 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	679 }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	680
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	681 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	682 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	683
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	684 /* Write table description header */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	685 { 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	686 op += nc_err;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	687 }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	688
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	689 /* Compress */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	690 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	691 { 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	692 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	693 op += cSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	694 }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	695
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	696 /* check compressibility */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	697 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	698
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	699 return op-ostart;
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
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	702 typedef struct {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	703 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	704 BYTE scratchBuffer[1 << FSE_MAX_TABLELOG];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	705 } fseWkspMax_t;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	706
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	707 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	708 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	709 fseWkspMax_t scratchBuffer;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	710 DEBUG_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	711 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	712 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	713 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	714
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	715 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	716 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	717 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	718 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	719
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 #endif /* FSE_COMMONDEFS_ONLY */

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/compress/fse_compress.c @ 40121:73fef626dae3