mercurial-scm/hg-stable: contrib/python-zstandard/zstd/compress/huf

annotate contrib/python-zstandard/zstd/compress/huf_compress.c @ 40450:41f0529b5112 stable

commandserver: get around ETIMEDOUT raised by selectors2 selector.select() should exits with an empty event list on timed out, but selectors2 raises OSError if timeout expires while recovering from EINTR. Spotted while debugging new chg feature.

author	Yuya Nishihara <yuya@tcha.org>
date	Mon, 03 Dec 2018 21:45:15 +0900
parents	73fef626dae3
children	675775c33ab6

rev	line source
30443 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 Huffman encoder, part of New Generation Entropy library
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	3 Copyright (C) 2013-2016, Yann Collet.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	4
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	6
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	7 Redistribution and use in source and binary forms, with or without
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	8 modification, are permitted provided that the following conditions are
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	9 met:
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	10
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	11 * Redistributions of source code must retain the above copyright
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	12 notice, this list of conditions and the following disclaimer.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	13 * Redistributions in binary form must reproduce the above
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	14 copyright notice, this list of conditions and the following disclaimer
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	15 in the documentation and/or other materials provided with the
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	16 distribution.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	17
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	29
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	30 You can contact the author at :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	31 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	32 - Public forum : https://groups.google.com/forum/#!forum/lz4c
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	33 ****************************************************************** */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	34
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	35 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	36 * Compiler specifics
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	37 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	38 #ifdef _MSC_VER /* Visual Studio */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	39 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	40 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	41
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	42
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	43 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44 * Includes
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	45 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46 #include <string.h> /* memcpy, memset */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	47 #include <stdio.h> /* printf (debug) */
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	48 #include "compiler.h"
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49 #include "bitstream.h"
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	50 #include "hist.h"
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 #define FSE_STATIC_LINKING_ONLY /* FSE_optimalTableLog_internal */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 #include "fse.h" /* header compression */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53 #define HUF_STATIC_LINKING_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54 #include "huf.h"
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	55 #include "error_private.h"
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	56
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	57
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	58 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	59 * Error Management
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	60 ****************************************************************/
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	61 #define HUF_isError ERR_isError
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	62 #define HUF_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only after variable declarations */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	63 #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: 30443 diff changeset	64 #define CHECK_F(f) { CHECK_V_F(_var_err__, f); }
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	65
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	66
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	67 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	68 * Utils
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	69 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	70 unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	71 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	72 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	73 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	76 /* *******************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	77 * HUF : Huffman block compression
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	78 *********************************************************/
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	79 /* HUF_compressWeights() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	80 * Same as FSE_compress(), but dedicated to huff0's weights compression.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	81 * The use case needs much less stack memory.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	82 * Note : all elements within weightTable are supposed to be <= HUF_TABLELOG_MAX.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	83 */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	84 #define MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	85 static size_t HUF_compressWeights (void* dst, size_t dstSize, const void* weightTable, size_t wtSize)
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	86 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	87 BYTE* const ostart = (BYTE*) dst;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	88 BYTE* op = ostart;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	89 BYTE* const oend = ostart + dstSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	90
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	91 U32 maxSymbolValue = HUF_TABLELOG_MAX;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	92 U32 tableLog = MAX_FSE_TABLELOG_FOR_HUFF_HEADER;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	93
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	94 FSE_CTable CTable[FSE_CTABLE_SIZE_U32(MAX_FSE_TABLELOG_FOR_HUFF_HEADER, HUF_TABLELOG_MAX)];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	95 BYTE scratchBuffer[1<<MAX_FSE_TABLELOG_FOR_HUFF_HEADER];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	96
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	97 U32 count[HUF_TABLELOG_MAX+1];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	98 S16 norm[HUF_TABLELOG_MAX+1];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	99
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	100 /* init conditions */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	101 if (wtSize <= 1) return 0; /* Not compressible */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	102
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	103 /* Scan input and build symbol stats */
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	104 { unsigned const maxCount = HIST_count_simple(count, &maxSymbolValue, weightTable, wtSize); /* never fails */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	105 if (maxCount == wtSize) return 1; /* only a single symbol in src : rle */
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	106 if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	107 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	108
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	109 tableLog = FSE_optimalTableLog(tableLog, wtSize, maxSymbolValue);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	110 CHECK_F( FSE_normalizeCount(norm, tableLog, count, wtSize, maxSymbolValue) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	111
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	112 /* Write table description header */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	113 { CHECK_V_F(hSize, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	114 op += hSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	115 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	116
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	117 /* Compress */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	118 CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, sizeof(scratchBuffer)) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	119 { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, weightTable, wtSize, CTable) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	120 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: 30443 diff changeset	121 op += cSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	122 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	123
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	124 return op-ostart;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	125 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	126
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	127
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 struct HUF_CElt_s {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 U16 val;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 BYTE nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 }; /* typedef'd to HUF_CElt within "huf.h" */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	133 /*! HUF_writeCTable() :
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	134 `CTable` : Huffman tree to save, using huf representation.
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	135 @return : size of saved CTable */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 size_t HUF_writeCTable (void* dst, size_t maxDstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137 const HUF_CElt* CTable, U32 maxSymbolValue, U32 huffLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	139 BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; /* precomputed conversion table */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140 BYTE huffWeight[HUF_SYMBOLVALUE_MAX];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	141 BYTE* op = (BYTE*)dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 U32 n;
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 /* check conditions */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	145 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147 /* convert to weight */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	148 bitsToWeight[0] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149 for (n=1; n<huffLog+1; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	150 bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	151 for (n=0; n<maxSymbolValue; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	152 huffWeight[n] = bitsToWeight[CTable[n].nbBits];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	153
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	154 /* attempt weights compression by FSE */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	155 { CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, huffWeight, maxSymbolValue) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	156 if ((hSize>1) & (hSize < maxSymbolValue/2)) { /* FSE compressed */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	157 op[0] = (BYTE)hSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	158 return hSize+1;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	159 } }
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	160
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	161 /* write raw values as 4-bits (max : 15) */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	162 if (maxSymbolValue > (256-128)) return ERROR(GENERIC); /* should not happen : likely means source cannot be compressed */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	163 if (((maxSymbolValue+1)/2) + 1 > maxDstSize) return ERROR(dstSize_tooSmall); /* not enough space within dst buffer */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	164 op[0] = (BYTE)(128 /special case/ + (maxSymbolValue-1));
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	165 huffWeight[maxSymbolValue] = 0; /* to be sure it doesn't cause msan issue in final combination */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	166 for (n=0; n<maxSymbolValue; n+=2)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167 op[(n/2)+1] = (BYTE)((huffWeight[n] << 4) + huffWeight[n+1]);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 return ((maxSymbolValue+1)/2) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	170
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	172 size_t HUF_readCTable (HUF_CElt* CTable, U32* maxSymbolValuePtr, const void* src, size_t srcSize)
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	174 BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; /* init not required, even though some static analyzer may complain */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175 U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	176 U32 tableLog = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	177 U32 nbSymbols = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	178
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	179 /* get symbol weights */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	180 CHECK_V_F(readSize, HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize));
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	181
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	182 /* check result */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	183 if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	184 if (nbSymbols > *maxSymbolValuePtr+1) return ERROR(maxSymbolValue_tooSmall);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	185
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	186 /* Prepare base value per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	187 { U32 n, nextRankStart = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	188 for (n=1; n<=tableLog; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	189 U32 current = nextRankStart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	190 nextRankStart += (rankVal[n] << (n-1));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	191 rankVal[n] = current;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	192 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	193
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	194 /* fill nbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	195 { U32 n; for (n=0; n<nbSymbols; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	196 const U32 w = huffWeight[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	197 CTable[n].nbBits = (BYTE)(tableLog + 1 - w);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	198 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	200 /* fill val */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201 { U16 nbPerRank[HUF_TABLELOG_MAX+2] = {0}; /* support w=0=>n=tableLog+1 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	202 U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	203 { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[CTable[n].nbBits]++; }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	204 /* determine stating value per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	205 valPerRank[tableLog+1] = 0; /* for w==0 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	206 { U16 min = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	207 U32 n; for (n=tableLog; n>0; n--) { /* start at n=tablelog <-> w=1 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	208 valPerRank[n] = min; /* get starting value within each rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	209 min += nbPerRank[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	210 min >>= 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	211 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	212 /* assign value within rank, symbol order */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	213 { U32 n; for (n=0; n<nbSymbols; n++) CTable[n].val = valPerRank[CTable[n].nbBits]++; }
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	214 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	215
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	216 *maxSymbolValuePtr = nbSymbols - 1;
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	217 return readSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	218 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	219
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	220 U32 HUF_getNbBits(const void* symbolTable, U32 symbolValue)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	221 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	222 const HUF_CElt* table = (const HUF_CElt*)symbolTable;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	223 assert(symbolValue <= HUF_SYMBOLVALUE_MAX);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	224 return table[symbolValue].nbBits;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	225 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	226
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	227
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	228 typedef struct nodeElt_s {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	229 U32 count;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	230 U16 parent;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	231 BYTE byte;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	232 BYTE nbBits;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	233 } nodeElt;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	234
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235 static U32 HUF_setMaxHeight(nodeElt* huffNode, U32 lastNonNull, U32 maxNbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 const U32 largestBits = huffNode[lastNonNull].nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 if (largestBits <= maxNbBits) return largestBits; /* early exit : no elt > maxNbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 /* there are several too large elements (at least >= 2) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 { int totalCost = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242 const U32 baseCost = 1 << (largestBits - maxNbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243 U32 n = lastNonNull;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245 while (huffNode[n].nbBits > maxNbBits) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246 totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247 huffNode[n].nbBits = (BYTE)maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 n --;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 } /* n stops at huffNode[n].nbBits <= maxNbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 while (huffNode[n].nbBits == maxNbBits) n--; /* n end at index of smallest symbol using < maxNbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 /* renorm totalCost */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 totalCost >>= (largestBits - maxNbBits); /* note : totalCost is necessarily a multiple of baseCost */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 /* repay normalized cost */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 { U32 const noSymbol = 0xF0F0F0F0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 U32 rankLast[HUF_TABLELOG_MAX+2];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 int pos;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 /* Get pos of last (smallest) symbol per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 memset(rankLast, 0xF0, sizeof(rankLast));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 { U32 currentNbBits = maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 for (pos=n ; pos >= 0; pos--) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264 if (huffNode[pos].nbBits >= currentNbBits) continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 currentNbBits = huffNode[pos].nbBits; /* < maxNbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 rankLast[maxNbBits-currentNbBits] = pos;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 while (totalCost > 0) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 U32 nBitsToDecrease = BIT_highbit32(totalCost) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 for ( ; nBitsToDecrease > 1; nBitsToDecrease--) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 U32 highPos = rankLast[nBitsToDecrease];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 U32 lowPos = rankLast[nBitsToDecrease-1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	274 if (highPos == noSymbol) continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	275 if (lowPos == noSymbol) break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	276 { U32 const highTotal = huffNode[highPos].count;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277 U32 const lowTotal = 2 * huffNode[lowPos].count;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 if (highTotal <= lowTotal) break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 /* only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !) */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	281 /* HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	282 while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol))
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 nBitsToDecrease ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284 totalCost -= 1 << (nBitsToDecrease-1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285 if (rankLast[nBitsToDecrease-1] == noSymbol)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease]; /* this rank is no longer empty */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287 huffNode[rankLast[nBitsToDecrease]].nbBits ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288 if (rankLast[nBitsToDecrease] == 0) /* special case, reached largest symbol */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 rankLast[nBitsToDecrease] = noSymbol;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290 else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 rankLast[nBitsToDecrease]--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292 if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	293 rankLast[nBitsToDecrease] = noSymbol; /* this rank is now empty */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294 } } /* while (totalCost > 0) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 while (totalCost < 0) { /* Sometimes, cost correction overshoot */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 if (rankLast[1] == noSymbol) { /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298 while (huffNode[n].nbBits == maxNbBits) n--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 huffNode[n+1].nbBits--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 rankLast[1] = n+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301 totalCost++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 continue;
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 huffNode[ rankLast[1] + 1 ].nbBits--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 rankLast[1]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306 totalCost ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307 } } } /* there are several too large elements (at least >= 2) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 return maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	311
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	313 typedef struct {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 U32 base;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315 U32 current;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	316 } rankPos;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	317
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 static void HUF_sort(nodeElt* huffNode, const U32* count, U32 maxSymbolValue)
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 rankPos rank[32];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321 U32 n;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 memset(rank, 0, sizeof(rank));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324 for (n=0; n<=maxSymbolValue; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325 U32 r = BIT_highbit32(count[n] + 1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326 rank[r].base ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	327 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	328 for (n=30; n>0; n--) rank[n-1].base += rank[n].base;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	329 for (n=0; n<32; n++) rank[n].current = rank[n].base;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	330 for (n=0; n<=maxSymbolValue; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	331 U32 const c = count[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	332 U32 const r = BIT_highbit32(c+1) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	333 U32 pos = rank[r].current++;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	334 while ((pos > rank[r].base) && (c > huffNode[pos-1].count)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	335 huffNode[pos] = huffNode[pos-1];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	336 pos--;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	337 }
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	338 huffNode[pos].count = c;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	339 huffNode[pos].byte = (BYTE)n;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	340 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	341 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	342
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	343
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	344 /** HUF_buildCTable_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	345 * Same as HUF_buildCTable(), but using externally allocated scratch buffer.
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	346 * `workSpace` must be aligned on 4-bytes boundaries, and be at least as large as a table of HUF_CTABLE_WORKSPACE_SIZE_U32 unsigned.
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	347 */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348 #define STARTNODE (HUF_SYMBOLVALUE_MAX+1)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	349 typedef nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32];
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	350 size_t HUF_buildCTable_wksp (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	351 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	352 nodeElt* const huffNode0 = (nodeElt*)workSpace;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	353 nodeElt* const huffNode = huffNode0+1;
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 U32 n, nonNullRank;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	355 int lowS, lowN;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	356 U16 nodeNb = STARTNODE;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	357 U32 nodeRoot;
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 /* safety checks */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	360 if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	361 if (wkspSize < sizeof(huffNodeTable)) return ERROR(workSpace_tooSmall);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	362 if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	363 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	364 memset(huffNode0, 0, sizeof(huffNodeTable));
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	365
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 /* sort, decreasing order */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	367 HUF_sort(huffNode, count, maxSymbolValue);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369 /* init for parents */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370 nonNullRank = maxSymbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 while(huffNode[nonNullRank].count == 0) nonNullRank--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372 lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	373 huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374 huffNode[lowS].parent = huffNode[lowS-1].parent = nodeNb;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	375 nodeNb++; lowS-=2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	376 for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30);
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	377 huffNode0[0].count = (U32)(1U<<31); /* fake entry, strong barrier */
30443 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 /* create parents */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	380 while (nodeNb <= nodeRoot) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	381 U32 n1 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 U32 n2 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383 huffNode[nodeNb].count = huffNode[n1].count + huffNode[n2].count;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384 huffNode[n1].parent = huffNode[n2].parent = nodeNb;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	385 nodeNb++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388 /* distribute weights (unlimited tree height) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	389 huffNode[nodeRoot].nbBits = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	390 for (n=nodeRoot-1; n>=STARTNODE; n--)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	391 huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	392 for (n=0; n<=nonNullRank; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	393 huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	395 /* enforce maxTableLog */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	396 maxNbBits = HUF_setMaxHeight(huffNode, nonNullRank, maxNbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	398 /* fill result into tree (val, nbBits) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399 { U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	400 U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	401 if (maxNbBits > HUF_TABLELOG_MAX) return ERROR(GENERIC); /* check fit into table */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	402 for (n=0; n<=nonNullRank; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	403 nbPerRank[huffNode[n].nbBits]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	404 /* determine stating value per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	405 { U16 min = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	406 for (n=maxNbBits; n>0; n--) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	407 valPerRank[n] = min; /* get starting value within each rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	408 min += nbPerRank[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	409 min >>= 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	410 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	411 for (n=0; n<=maxSymbolValue; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	412 tree[huffNode[n].byte].nbBits = huffNode[n].nbBits; /* push nbBits per symbol, symbol order */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	413 for (n=0; n<=maxSymbolValue; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	414 tree[n].val = valPerRank[tree[n].nbBits]++; /* assign value within rank, symbol order */
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 return maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	418 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	419
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	420 /** HUF_buildCTable() :
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	421 * @return : maxNbBits
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	422 * Note : count is used before tree is written, so they can safely overlap
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	423 */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	424 size_t HUF_buildCTable (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	425 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	426 huffNodeTable nodeTable;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	427 return HUF_buildCTable_wksp(tree, count, maxSymbolValue, maxNbBits, nodeTable, sizeof(nodeTable));
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	428 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	429
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	430 static size_t HUF_estimateCompressedSize(HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	431 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	432 size_t nbBits = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	433 int s;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	434 for (s = 0; s <= (int)maxSymbolValue; ++s) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	435 nbBits += CTable[s].nbBits * count[s];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	436 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	437 return nbBits >> 3;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	438 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	439
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	440 static int HUF_validateCTable(const HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	441 int bad = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	442 int s;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	443 for (s = 0; s <= (int)maxSymbolValue; ++s) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	444 bad \|= (count[s] != 0) & (CTable[s].nbBits == 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	445 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	446 return !bad;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	447 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	448
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	449 size_t HUF_compressBound(size_t size) { return HUF_COMPRESSBOUND(size); }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	450
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	451 FORCE_INLINE_TEMPLATE void
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	452 HUF_encodeSymbol(BIT_CStream_t* bitCPtr, U32 symbol, const HUF_CElt* CTable)
30443 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 BIT_addBitsFast(bitCPtr, CTable[symbol].val, CTable[symbol].nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	457 #define HUF_FLUSHBITS(s) BIT_flushBits(s)
30443 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 #define HUF_FLUSHBITS_1(stream) \
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 if (sizeof((stream)->bitContainer)8 < HUF_TABLELOG_MAX2+7) HUF_FLUSHBITS(stream)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462 #define HUF_FLUSHBITS_2(stream) \
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 if (sizeof((stream)->bitContainer)8 < HUF_TABLELOG_MAX4+7) HUF_FLUSHBITS(stream)
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 FORCE_INLINE_TEMPLATE size_t
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	466 HUF_compress1X_usingCTable_internal_body(void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	467 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	468 const HUF_CElt* CTable)
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 const BYTE* ip = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 BYTE* const ostart = (BYTE*)dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	472 BYTE* const oend = ostart + dstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	473 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	474 size_t n;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	475 BIT_CStream_t bitC;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	477 /* init */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478 if (dstSize < 8) return 0; /* not enough space to compress */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	479 { size_t const initErr = BIT_initCStream(&bitC, op, oend-op);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	480 if (HUF_isError(initErr)) return 0; }
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	481
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	482 n = srcSize & ~3; /* join to mod 4 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	483 switch (srcSize & 3)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	484 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	485 case 3 : HUF_encodeSymbol(&bitC, ip[n+ 2], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 HUF_FLUSHBITS_2(&bitC);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	487 /* fall-through */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 case 2 : HUF_encodeSymbol(&bitC, ip[n+ 1], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	489 HUF_FLUSHBITS_1(&bitC);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	490 /* fall-through */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 case 1 : HUF_encodeSymbol(&bitC, ip[n+ 0], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 HUF_FLUSHBITS(&bitC);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	493 /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	494 case 0 : /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	495 default: break;
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496 }
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 for (; n>0; n-=4) { /* note : n&3==0 at this stage */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	499 HUF_encodeSymbol(&bitC, ip[n- 1], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 HUF_FLUSHBITS_1(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	501 HUF_encodeSymbol(&bitC, ip[n- 2], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 HUF_FLUSHBITS_2(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 HUF_encodeSymbol(&bitC, ip[n- 3], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	504 HUF_FLUSHBITS_1(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505 HUF_encodeSymbol(&bitC, ip[n- 4], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 HUF_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	507 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	508
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 return BIT_closeCStream(&bitC);
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
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	512 #if DYNAMIC_BMI2
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	513
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	514 static TARGET_ATTRIBUTE("bmi2") size_t
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	515 HUF_compress1X_usingCTable_internal_bmi2(void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	516 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	517 const HUF_CElt* CTable)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	518 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	519 return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	520 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	521
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	522 static size_t
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	523 HUF_compress1X_usingCTable_internal_default(void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	524 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	525 const HUF_CElt* CTable)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	526 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	527 return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	528 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	529
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	530 static size_t
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	531 HUF_compress1X_usingCTable_internal(void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	532 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	533 const HUF_CElt* CTable, const int bmi2)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	534 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	535 if (bmi2) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	536 return HUF_compress1X_usingCTable_internal_bmi2(dst, dstSize, src, srcSize, CTable);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	537 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	538 return HUF_compress1X_usingCTable_internal_default(dst, dstSize, src, srcSize, CTable);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	539 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	540
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	541 #else
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	542
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	543 static size_t
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	544 HUF_compress1X_usingCTable_internal(void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	545 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	546 const HUF_CElt* CTable, const int bmi2)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	547 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	548 (void)bmi2;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	549 return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	550 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	551
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	552 #endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	553
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	554 size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	555 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	556 return HUF_compress1X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	557 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	558
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	559
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	560 static size_t
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	561 HUF_compress4X_usingCTable_internal(void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	562 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	563 const HUF_CElt* CTable, int bmi2)
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	564 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	565 size_t const segmentSize = (srcSize+3)/4; /* first 3 segments */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	566 const BYTE* ip = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	567 const BYTE* const iend = ip + srcSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 BYTE* const ostart = (BYTE*) dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	569 BYTE* const oend = ostart + dstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	570 BYTE* op = ostart;
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 if (dstSize < 6 + 1 + 1 + 1 + 8) return 0; /* minimum space to compress successfully */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	573 if (srcSize < 12) return 0; /* no saving possible : too small input */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	574 op += 6; /* jumpTable */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	575
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	576 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, segmentSize, CTable, bmi2) );
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	577 if (cSize==0) return 0;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	578 assert(cSize <= 65535);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	579 MEM_writeLE16(ostart, (U16)cSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	580 op += cSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	581 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	582
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	583 ip += segmentSize;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	584 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, segmentSize, CTable, bmi2) );
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	585 if (cSize==0) return 0;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	586 assert(cSize <= 65535);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	587 MEM_writeLE16(ostart+2, (U16)cSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	588 op += cSize;
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	591 ip += segmentSize;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	592 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, segmentSize, CTable, bmi2) );
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	593 if (cSize==0) return 0;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	594 assert(cSize <= 65535);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	595 MEM_writeLE16(ostart+4, (U16)cSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596 op += cSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	597 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	598
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	599 ip += segmentSize;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	600 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, iend-ip, CTable, bmi2) );
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	601 if (cSize==0) return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	602 op += cSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	603 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	604
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	605 return op-ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	606 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	607
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	608 size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	609 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	610 return HUF_compress4X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	611 }
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	612
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	613
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	614 static size_t HUF_compressCTable_internal(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	615 BYTE* const ostart, BYTE* op, BYTE* const oend,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	616 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	617 unsigned singleStream, const HUF_CElt* CTable, const int bmi2)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	618 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	619 size_t const cSize = singleStream ?
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	620 HUF_compress1X_usingCTable_internal(op, oend - op, src, srcSize, CTable, bmi2) :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	621 HUF_compress4X_usingCTable_internal(op, oend - op, src, srcSize, CTable, bmi2);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	622 if (HUF_isError(cSize)) { return cSize; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	623 if (cSize==0) { return 0; } /* uncompressible */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	624 op += cSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	625 /* check compressibility */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	626 if ((size_t)(op-ostart) >= srcSize-1) { return 0; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	627 return op-ostart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	628 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	629
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	630 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	631 U32 count[HUF_SYMBOLVALUE_MAX + 1];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	632 HUF_CElt CTable[HUF_SYMBOLVALUE_MAX + 1];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	633 huffNodeTable nodeTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	634 } HUF_compress_tables_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	635
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	636 /* HUF_compress_internal() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	637 * `workSpace` must a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	638 static size_t HUF_compress_internal (
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	639 void* dst, size_t dstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	640 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	641 unsigned maxSymbolValue, unsigned huffLog,
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	642 unsigned singleStream,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	643 void* workSpace, size_t wkspSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	644 HUF_CElt* oldHufTable, HUF_repeat* repeat, int preferRepeat,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	645 const int bmi2)
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	646 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	647 HUF_compress_tables_t* const table = (HUF_compress_tables_t*)workSpace;
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	648 BYTE* const ostart = (BYTE*)dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	649 BYTE* const oend = ostart + dstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	650 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	651
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	652 /* checks & inits */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	653 if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	654 if (wkspSize < sizeof(*table)) return ERROR(workSpace_tooSmall);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	655 if (!srcSize) return 0; /* Uncompressed */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	656 if (!dstSize) return 0; /* cannot fit anything within dst budget */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	657 if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); /* current block size limit */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	658 if (huffLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	659 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	660 if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	661 if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	662
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	663 /* Heuristic : If old table is valid, use it for small inputs */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	664 if (preferRepeat && repeat && *repeat == HUF_repeat_valid) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	665 return HUF_compressCTable_internal(ostart, op, oend,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	666 src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	667 singleStream, oldHufTable, bmi2);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	668 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	669
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	670 /* Scan input and build symbol stats */
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	671 { CHECK_V_F(largest, HIST_count_wksp (table->count, &maxSymbolValue, (const BYTE*)src, srcSize, table->count) );
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	672 if (largest == srcSize) { ostart = ((const BYTE)src)[0]; return 1; } /* single symbol, rle */
40122 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	673 if (largest <= (srcSize >> 7)+4) return 0; /* heuristic : probably not compressible enough */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	674 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	675
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	676 /* Check validity of previous table */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	677 if ( repeat
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	678 && *repeat == HUF_repeat_check
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	679 && !HUF_validateCTable(oldHufTable, table->count, maxSymbolValue)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	680 *repeat = HUF_repeat_none;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	681 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	682 /* Heuristic : use existing table for small inputs */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	683 if (preferRepeat && repeat && *repeat != HUF_repeat_none) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	684 return HUF_compressCTable_internal(ostart, op, oend,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	685 src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	686 singleStream, oldHufTable, bmi2);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	687 }
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 /* Build Huffman Tree */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	690 huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	691 { CHECK_V_F(maxBits, HUF_buildCTable_wksp(table->CTable, table->count,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	692 maxSymbolValue, huffLog,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	693 table->nodeTable, sizeof(table->nodeTable)) );
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	694 huffLog = (U32)maxBits;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	695 /* Zero unused symbols in CTable, so we can check it for validity */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	696 memset(table->CTable + (maxSymbolValue + 1), 0,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	697 sizeof(table->CTable) - ((maxSymbolValue + 1) * sizeof(HUF_CElt)));
30443 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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	700 /* Write table description header */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	701 { CHECK_V_F(hSize, HUF_writeCTable (op, dstSize, table->CTable, maxSymbolValue, huffLog) );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	702 /* Check if using previous huffman table is beneficial */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	703 if (repeat && *repeat != HUF_repeat_none) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	704 size_t const oldSize = HUF_estimateCompressedSize(oldHufTable, table->count, maxSymbolValue);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	705 size_t const newSize = HUF_estimateCompressedSize(table->CTable, table->count, maxSymbolValue);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	706 if (oldSize <= hSize + newSize \|\| hSize + 12 >= srcSize) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	707 return HUF_compressCTable_internal(ostart, op, oend,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	708 src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	709 singleStream, oldHufTable, bmi2);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	710 } }
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	711
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	712 /* Use the new huffman table */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	713 if (hSize + 12ul >= srcSize) { return 0; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	714 op += hSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	715 if (repeat) { *repeat = HUF_repeat_none; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	716 if (oldHufTable)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	717 memcpy(oldHufTable, table->CTable, sizeof(table->CTable)); /* Save new table */
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	718 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	719 return HUF_compressCTable_internal(ostart, op, oend,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	720 src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	721 singleStream, table->CTable, bmi2);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	722 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	723
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	724
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	725 size_t HUF_compress1X_wksp (void* dst, size_t dstSize,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	726 const void* src, size_t srcSize,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	727 unsigned maxSymbolValue, unsigned huffLog,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	728 void* workSpace, size_t wkspSize)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	729 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	730 return HUF_compress_internal(dst, dstSize, src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	731 maxSymbolValue, huffLog, 1 /single stream/,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	732 workSpace, wkspSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	733 NULL, NULL, 0, 0 /bmi2/);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	734 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	735
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	736 size_t HUF_compress1X_repeat (void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	737 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	738 unsigned maxSymbolValue, unsigned huffLog,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	739 void* workSpace, size_t wkspSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	740 HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	741 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	742 return HUF_compress_internal(dst, dstSize, src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	743 maxSymbolValue, huffLog, 1 /single stream/,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	744 workSpace, wkspSize, hufTable,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	745 repeat, preferRepeat, bmi2);
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	746 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	747
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	748 size_t HUF_compress1X (void* dst, size_t dstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	749 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	750 unsigned maxSymbolValue, unsigned huffLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	751 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	752 unsigned workSpace[HUF_WORKSPACE_SIZE_U32];
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	753 return HUF_compress1X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace));
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	754 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	755
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	756 /* HUF_compress4X_repeat():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	757 * compress input using 4 streams.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	758 * provide workspace to generate compression tables */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	759 size_t HUF_compress4X_wksp (void* dst, size_t dstSize,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	760 const void* src, size_t srcSize,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	761 unsigned maxSymbolValue, unsigned huffLog,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	762 void* workSpace, size_t wkspSize)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	763 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	764 return HUF_compress_internal(dst, dstSize, src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	765 maxSymbolValue, huffLog, 0 /4 streams/,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	766 workSpace, wkspSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	767 NULL, NULL, 0, 0 /bmi2/);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	768 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	769
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	770 /* HUF_compress4X_repeat():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	771 * compress input using 4 streams.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	772 * re-use an existing huffman compression table */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	773 size_t HUF_compress4X_repeat (void* dst, size_t dstSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	774 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	775 unsigned maxSymbolValue, unsigned huffLog,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	776 void* workSpace, size_t wkspSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	777 HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	778 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	779 return HUF_compress_internal(dst, dstSize, src, srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	780 maxSymbolValue, huffLog, 0 /* 4 streams */,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	781 workSpace, wkspSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	782 hufTable, repeat, preferRepeat, bmi2);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	783 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	784
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	785 size_t HUF_compress2 (void* dst, size_t dstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	786 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	787 unsigned maxSymbolValue, unsigned huffLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	788 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	789 unsigned workSpace[HUF_WORKSPACE_SIZE_U32];
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30443 diff changeset	790 return HUF_compress4X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace));
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	791 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	792
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	793 size_t HUF_compress (void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	794 {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30822 diff changeset	795 return HUF_compress2(dst, maxDstSize, src, srcSize, 255, HUF_TABLELOG_DEFAULT);
30443 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	796 }

Mercurial > public > mercurial-scm > hg-stable

annotate contrib/python-zstandard/zstd/compress/huf_compress.c @ 40450:41f0529b5112 stable