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

annotate contrib/python-zstandard/zstd/compress/huf_compress.c @ 30895:c32454d69b85

zstd: vendor python-zstandard 0.7.0 Commit 3054ae3a66112970a091d3939fee32c2d0c1a23e from https://github.com/indygreg/python-zstandard is imported without modifications (other than removing unwanted files). The vendored zstd library within has been upgraded from 1.1.2 to 1.1.3. This version introduced new APIs for threads, thread pools, multi-threaded compression, and a new dictionary builder (COVER). These features are not yet used by python-zstandard (or Mercurial for that matter). However, that will likely change in the next python-zstandard release (and I think there are opportunities for Mercurial to take advantage of the multi-threaded APIs). Relevant to Mercurial, the CFFI bindings are now fully implemented. This means zstd should "just work" with PyPy (although I haven't tried). The python-zstandard test suite also runs all tests against both the C extension and CFFI bindings to ensure feature parity. There is also a "decompress_content_dict_chain()" API. This was derived from discussions with Yann Collet on list about alternate ways of encoding delta chains. The change most relevant to Mercurial is a performance enhancement in the simple decompression API to reuse a data structure across operations. This makes decompression of multiple inputs significantly faster. (This scenario occurs when reading revlog delta chains, for example.) Using python-zstandard's bench.py to measure the performance difference... On changelog chunks in the mozilla-unified repo: decompress discrete decompress() reuse zctx 1.262243 wall; 1.260000 CPU; 1.260000 user; 0.000000 sys 170.43 MB/s (best of 3) 0.949106 wall; 0.950000 CPU; 0.950000 user; 0.000000 sys 226.66 MB/s (best of 4) decompress discrete dict decompress() reuse zctx 0.692170 wall; 0.690000 CPU; 0.690000 user; 0.000000 sys 310.80 MB/s (best of 5) 0.437088 wall; 0.440000 CPU; 0.440000 user; 0.000000 sys 492.17 MB/s (best of 7) On manifest chunks in the mozilla-unified repo: decompress discrete decompress() reuse zctx 1.367284 wall; 1.370000 CPU; 1.370000 user; 0.000000 sys 274.01 MB/s (best of 3) 1.086831 wall; 1.080000 CPU; 1.080000 user; 0.000000 sys 344.72 MB/s (best of 3) decompress discrete dict decompress() reuse zctx 0.993272 wall; 0.990000 CPU; 0.990000 user; 0.000000 sys 377.19 MB/s (best of 3) 0.678651 wall; 0.680000 CPU; 0.680000 user; 0.000000 sys 552.06 MB/s (best of 5) That should make reads on zstd revlogs a bit faster ;) # no-check-commit

author	Gregory Szorc <gregory.szorc@gmail.com>
date	Tue, 07 Feb 2017 23:24:47 -0800
parents	b54a2984cdd4
children	b1fb341d8a61

rev	line source
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1 /* ******************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	2 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) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48 #include "bitstream.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49 #define FSE_STATIC_LINKING_ONLY /* FSE_optimalTableLog_internal */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50 #include "fse.h" /* header compression */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 #define HUF_STATIC_LINKING_ONLY
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 #include "huf.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	55 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	56 * Error Management
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 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only after variable declarations */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	59 #define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return f
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	60 #define CHECK_F(f) { CHECK_V_F(_var_err__, f); }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	61
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	62
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	63 /* **************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	64 * Utils
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 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	67 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	68 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 1);
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	71
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	72 /* *******************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	73 * HUF : Huffman block compression
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74 *********************************************************/
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	75 /* HUF_compressWeights() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	76 * 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: 30434 diff changeset	77 * The use case needs much less stack memory.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	78 * 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: 30434 diff changeset	79 */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	80 #define MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	81 size_t HUF_compressWeights (void* dst, size_t dstSize, const void* weightTable, size_t wtSize)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	82 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	83 BYTE* const ostart = (BYTE*) dst;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	84 BYTE* op = ostart;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	85 BYTE* const oend = ostart + dstSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	86
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	87 U32 maxSymbolValue = HUF_TABLELOG_MAX;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	88 U32 tableLog = MAX_FSE_TABLELOG_FOR_HUFF_HEADER;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	89
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	90 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: 30434 diff changeset	91 BYTE scratchBuffer[1<<MAX_FSE_TABLELOG_FOR_HUFF_HEADER];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	92
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	93 U32 count[HUF_TABLELOG_MAX+1];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	94 S16 norm[HUF_TABLELOG_MAX+1];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	95
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	96 /* init conditions */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	97 if (wtSize <= 1) return 0; /* Not compressible */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	98
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	99 /* Scan input and build symbol stats */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	100 { CHECK_V_F(maxCount, FSE_count_simple(count, &maxSymbolValue, weightTable, wtSize) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	101 if (maxCount == wtSize) return 1; /* only a single symbol in src : rle */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	102 if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	103 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	104
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	105 tableLog = FSE_optimalTableLog(tableLog, wtSize, maxSymbolValue);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	106 CHECK_F( FSE_normalizeCount(norm, tableLog, count, wtSize, maxSymbolValue) );
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	107
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	108 /* Write table description header */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	109 { 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: 30434 diff changeset	110 op += hSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	111 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	112
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	113 /* Compress */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	114 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: 30434 diff changeset	115 { 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: 30434 diff changeset	116 if (cSize == 0) return 0; /* not enough space for compressed data */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	117 op += cSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	118 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	119
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	120 return op-ostart;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	121 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	122
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	123
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124 struct HUF_CElt_s {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125 U16 val;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 BYTE nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127 }; /* typedef'd to HUF_CElt within "huf.h" */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 /*! HUF_writeCTable() :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 `CTable` : huffman tree to save, using huf representation.
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 @return : size of saved CTable */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 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	133 const HUF_CElt* CTable, U32 maxSymbolValue, U32 huffLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	134 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	135 BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; /* precomputed conversion table */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 BYTE huffWeight[HUF_SYMBOLVALUE_MAX];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137 BYTE* op = (BYTE*)dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 U32 n;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	139
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140 /* check conditions */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	141 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143 /* convert to weight */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144 bitsToWeight[0] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 for (n=1; n<huffLog+1; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146 bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147 for (n=0; n<maxSymbolValue; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	148 huffWeight[n] = bitsToWeight[CTable[n].nbBits];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	150 /* attempt weights compression by FSE */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	151 { 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: 30434 diff changeset	152 if ((hSize>1) & (hSize < maxSymbolValue/2)) { /* FSE compressed */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	153 op[0] = (BYTE)hSize;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	154 return hSize+1;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	155 } }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	156
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	157 /* write raw values as 4-bits (max : 15) */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	158 if (maxSymbolValue > (256-128)) return ERROR(GENERIC); /* should not happen : likely means source cannot be compressed */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	159 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	160 op[0] = (BYTE)(128 /special case/ + (maxSymbolValue-1));
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	161 huffWeight[maxSymbolValue] = 0; /* to be sure it doesn't cause msan issue in final combination */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	162 for (n=0; n<maxSymbolValue; n+=2)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	163 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	164 return ((maxSymbolValue+1)/2) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	165 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	166
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 size_t HUF_readCTable (HUF_CElt* CTable, U32 maxSymbolValue, const void* src, size_t srcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	170 BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; /* init not required, even though some static analyzer may complain */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171 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	172 U32 tableLog = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 U32 nbSymbols = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	174
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175 /* get symbol weights */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	176 CHECK_V_F(readSize, HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize));
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	177
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	178 /* check result */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	179 if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	180 if (nbSymbols > maxSymbolValue+1) return ERROR(maxSymbolValue_tooSmall);
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 /* Prepare base value per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	183 { U32 n, nextRankStart = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	184 for (n=1; n<=tableLog; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	185 U32 current = nextRankStart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	186 nextRankStart += (rankVal[n] << (n-1));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	187 rankVal[n] = current;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	188 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	189
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	190 /* fill nbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	191 { U32 n; for (n=0; n<nbSymbols; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	192 const U32 w = huffWeight[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	193 CTable[n].nbBits = (BYTE)(tableLog + 1 - w);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	194 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	195
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	196 /* fill val */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	197 { 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	198 U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199 { 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	200 /* determine stating value per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201 valPerRank[tableLog+1] = 0; /* for w==0 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	202 { U16 min = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	203 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	204 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	205 min += nbPerRank[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	206 min >>= 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	207 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	208 /* assign value within rank, symbol order */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	209 { U32 n; for (n=0; n<=maxSymbolValue; n++) CTable[n].val = valPerRank[CTable[n].nbBits]++; }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	210 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	211
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	212 return readSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	213 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	214
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	215
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	216 typedef struct nodeElt_s {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	217 U32 count;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	218 U16 parent;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	219 BYTE byte;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	220 BYTE nbBits;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	221 } nodeElt;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	222
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	223 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	224 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	225 const U32 largestBits = huffNode[lastNonNull].nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	226 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	227
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	228 /* 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	229 { int totalCost = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	230 const U32 baseCost = 1 << (largestBits - maxNbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	231 U32 n = lastNonNull;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	232
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	233 while (huffNode[n].nbBits > maxNbBits) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	234 totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235 huffNode[n].nbBits = (BYTE)maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 n --;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 } /* n stops at huffNode[n].nbBits <= maxNbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 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	239
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 /* renorm totalCost */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 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	242
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243 /* repay normalized cost */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244 { U32 const noSymbol = 0xF0F0F0F0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245 U32 rankLast[HUF_TABLELOG_MAX+2];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246 int pos;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 /* Get pos of last (smallest) symbol per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 memset(rankLast, 0xF0, sizeof(rankLast));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 { U32 currentNbBits = maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 for (pos=n ; pos >= 0; pos--) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 if (huffNode[pos].nbBits >= currentNbBits) continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 currentNbBits = huffNode[pos].nbBits; /* < maxNbBits */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254 rankLast[maxNbBits-currentNbBits] = pos;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 while (totalCost > 0) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 U32 nBitsToDecrease = BIT_highbit32(totalCost) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259 for ( ; nBitsToDecrease > 1; nBitsToDecrease--) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 U32 highPos = rankLast[nBitsToDecrease];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 U32 lowPos = rankLast[nBitsToDecrease-1];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 if (highPos == noSymbol) continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 if (lowPos == noSymbol) break;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264 { U32 const highTotal = huffNode[highPos].count;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 U32 const lowTotal = 2 * huffNode[lowPos].count;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 if (highTotal <= lowTotal) break;
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 /* only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol)) /* HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 nBitsToDecrease ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 totalCost -= 1 << (nBitsToDecrease-1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 if (rankLast[nBitsToDecrease-1] == noSymbol)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 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	274 huffNode[rankLast[nBitsToDecrease]].nbBits ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	275 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	276 rankLast[nBitsToDecrease] = noSymbol;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277 else {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 rankLast[nBitsToDecrease]--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 rankLast[nBitsToDecrease] = noSymbol; /* this rank is now empty */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	281 } } /* while (totalCost > 0) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	282
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 while (totalCost < 0) { /* Sometimes, cost correction overshoot */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284 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	285 while (huffNode[n].nbBits == maxNbBits) n--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 huffNode[n+1].nbBits--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287 rankLast[1] = n+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288 totalCost++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 continue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 huffNode[ rankLast[1] + 1 ].nbBits--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292 rankLast[1]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	293 totalCost ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294 } } } /* 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	295
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 return maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 typedef struct {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301 U32 base;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 U32 current;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	303 } rankPos;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	304
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 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	306 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307 rankPos rank[32];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308 U32 n;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 memset(rank, 0, sizeof(rank));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	311 for (n=0; n<=maxSymbolValue; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312 U32 r = BIT_highbit32(count[n] + 1);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	313 rank[r].base ++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315 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	316 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	317 for (n=0; n<=maxSymbolValue; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 U32 const c = count[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	319 U32 const r = BIT_highbit32(c+1) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	320 U32 pos = rank[r].current++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321 while ((pos > rank[r].base) && (c > huffNode[pos-1].count)) huffNode[pos]=huffNode[pos-1], pos--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322 huffNode[pos].count = c;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 huffNode[pos].byte = (BYTE)n;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	327
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	328 /** HUF_buildCTable_wksp() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	329 * Same as HUF_buildCTable(), but using externally allocated scratch buffer.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	330 * `workSpace` must be aligned on 4-bytes boundaries, and be at least as large as a table of 1024 unsigned.
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	331 */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	332 #define STARTNODE (HUF_SYMBOLVALUE_MAX+1)
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	333 typedef nodeElt huffNodeTable[2*HUF_SYMBOLVALUE_MAX+1 +1];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	334 size_t HUF_buildCTable_wksp (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	335 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	336 nodeElt* const huffNode0 = (nodeElt*)workSpace;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	337 nodeElt* const huffNode = huffNode0+1;
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	338 U32 n, nonNullRank;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	339 int lowS, lowN;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	340 U16 nodeNb = STARTNODE;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	341 U32 nodeRoot;
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 /* safety checks */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	344 if (wkspSize < sizeof(huffNodeTable)) return ERROR(GENERIC); /* workSpace is not large enough */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	345 if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	346 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(GENERIC);
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	347 memset(huffNode0, 0, sizeof(huffNodeTable));
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	349 /* sort, decreasing order */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	350 HUF_sort(huffNode, count, maxSymbolValue);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	351
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	352 /* init for parents */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	353 nonNullRank = maxSymbolValue;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 while(huffNode[nonNullRank].count == 0) nonNullRank--;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	355 lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	356 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	357 huffNode[lowS].parent = huffNode[lowS-1].parent = nodeNb;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	358 nodeNb++; lowS-=2;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	359 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: 30434 diff changeset	360 huffNode0[0].count = (U32)(1U<<31); /* fake entry, strong barrier */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	361
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	362 /* create parents */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	363 while (nodeNb <= nodeRoot) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	364 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	365 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	366 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	367 huffNode[n1].parent = huffNode[n2].parent = nodeNb;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368 nodeNb++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 /* distribute weights (unlimited tree height) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372 huffNode[nodeRoot].nbBits = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	373 for (n=nodeRoot-1; n>=STARTNODE; n--)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374 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	375 for (n=0; n<=nonNullRank; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	376 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	377
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	378 /* enforce maxTableLog */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	379 maxNbBits = HUF_setMaxHeight(huffNode, nonNullRank, maxNbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	380
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	381 /* fill result into tree (val, nbBits) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 { U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383 U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384 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	385 for (n=0; n<=nonNullRank; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 nbPerRank[huffNode[n].nbBits]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387 /* determine stating value per rank */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388 { U16 min = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	389 for (n=maxNbBits; n>0; n--) {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	390 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	391 min += nbPerRank[n];
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	392 min >>= 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	393 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394 for (n=0; n<=maxSymbolValue; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	395 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	396 for (n=0; n<=maxSymbolValue; n++)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397 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	398 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	400 return maxNbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	401 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	402
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	403 /** HUF_buildCTable() :
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	404 * 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: 30434 diff changeset	405 */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	406 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: 30434 diff changeset	407 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	408 huffNodeTable nodeTable;
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	409 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: 30434 diff changeset	410 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	411
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	412 static void HUF_encodeSymbol(BIT_CStream_t* bitCPtr, U32 symbol, const HUF_CElt* CTable)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	413 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	414 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	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 size_t HUF_compressBound(size_t size) { return HUF_COMPRESSBOUND(size); }
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 #define HUF_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	420
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	421 #define HUF_FLUSHBITS_1(stream) \
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	422 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	423
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424 #define HUF_FLUSHBITS_2(stream) \
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	425 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	426
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	427 size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	428 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	429 const BYTE* ip = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	430 BYTE* const ostart = (BYTE*)dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	431 BYTE* const oend = ostart + dstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	432 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	433 size_t n;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	434 const unsigned fast = (dstSize >= HUF_BLOCKBOUND(srcSize));
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	435 BIT_CStream_t bitC;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	436
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	437 /* init */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	438 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: 30434 diff changeset	439 { 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: 30434 diff changeset	440 if (HUF_isError(initErr)) return 0; }
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	441
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	442 n = srcSize & ~3; /* join to mod 4 */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	443 switch (srcSize & 3)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	444 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	445 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	446 HUF_FLUSHBITS_2(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	447 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	448 HUF_FLUSHBITS_1(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	449 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	450 HUF_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	451 case 0 :
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 default: ;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	453 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	454
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 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	456 HUF_encodeSymbol(&bitC, ip[n- 1], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 HUF_FLUSHBITS_1(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458 HUF_encodeSymbol(&bitC, ip[n- 2], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 HUF_FLUSHBITS_2(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 HUF_encodeSymbol(&bitC, ip[n- 3], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461 HUF_FLUSHBITS_1(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462 HUF_encodeSymbol(&bitC, ip[n- 4], CTable);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 HUF_FLUSHBITS(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	464 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	465
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	466 return BIT_closeCStream(&bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	468
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	472 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	473 const BYTE* ip = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	474 const BYTE* const iend = ip + srcSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	475 BYTE* const ostart = (BYTE*) dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476 BYTE* const oend = ostart + dstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	477 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	479 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	480 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	481 op += 6; /* jumpTable */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	482
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	483 { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	484 if (cSize==0) return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	485 MEM_writeLE16(ostart, (U16)cSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 op += cSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	487 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	489 ip += segmentSize;
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	490 { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 if (cSize==0) return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 MEM_writeLE16(ostart+2, (U16)cSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	493 op += cSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	494 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496 ip += segmentSize;
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	497 { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	498 if (cSize==0) return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	499 MEM_writeLE16(ostart+4, (U16)cSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 op += cSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	501 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 ip += segmentSize;
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	504 { CHECK_V_F(cSize, HUF_compress1X_usingCTable(op, oend-op, ip, iend-ip, CTable) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505 if (cSize==0) return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 op += cSize;
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 op-ostart;
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	513 /* `workSpace` must a table of at least 1024 unsigned */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	514 static size_t HUF_compress_internal (
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	515 void* dst, size_t dstSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	516 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 unsigned maxSymbolValue, unsigned huffLog,
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	518 unsigned singleStream,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	519 void* workSpace, size_t wkspSize)
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	521 BYTE* const ostart = (BYTE*)dst;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	522 BYTE* const oend = ostart + dstSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	523 BYTE* op = ostart;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	525 union {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	526 U32 count[HUF_SYMBOLVALUE_MAX+1];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	527 HUF_CElt CTable[HUF_SYMBOLVALUE_MAX+1];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	528 } table; /* `count` can overlap with `CTable`; saves 1 KB */
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	529
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	530 /* checks & inits */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	531 if (wkspSize < sizeof(huffNodeTable)) return ERROR(GENERIC);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	532 if (!srcSize) return 0; /* Uncompressed (note : 1 means rle, so first byte must be correct) */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	533 if (!dstSize) return 0; /* cannot fit within dst budget */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	534 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	535 if (huffLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	536 if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	537 if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	538
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	539 /* Scan input and build symbol stats */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	540 { CHECK_V_F(largest, FSE_count_wksp (table.count, &maxSymbolValue, (const BYTE)src, srcSize, (U32)workSpace) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	541 if (largest == srcSize) { ostart = ((const BYTE)src)[0]; return 1; } /* single symbol, rle */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	542 if (largest <= (srcSize >> 7)+1) return 0; /* Fast heuristic : not compressible enough */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	543 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	544
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	545 /* Build Huffman Tree */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	546 huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue);
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	547 { CHECK_V_F(maxBits, HUF_buildCTable_wksp (table.CTable, table.count, maxSymbolValue, huffLog, workSpace, wkspSize) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	548 huffLog = (U32)maxBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	549 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	550
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	551 /* Write table description header */
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	552 { CHECK_V_F(hSize, HUF_writeCTable (op, dstSize, table.CTable, maxSymbolValue, huffLog) );
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	553 if (hSize + 12 >= srcSize) return 0; /* not useful to try compression */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	554 op += hSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	555 }
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	556
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	557 /* Compress */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	558 { size_t const cSize = (singleStream) ?
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	559 HUF_compress1X_usingCTable(op, oend - op, src, srcSize, table.CTable) : /* single segment */
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	560 HUF_compress4X_usingCTable(op, oend - op, src, srcSize, table.CTable);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	561 if (HUF_isError(cSize)) return cSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	562 if (cSize==0) return 0; /* uncompressible */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	563 op += cSize;
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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	566 /* check compressibility */
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	567 if ((size_t)(op-ostart) >= srcSize-1)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	569
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	570 return 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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	573
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	574 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: 30434 diff changeset	575 const void* src, size_t srcSize,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	576 unsigned maxSymbolValue, unsigned huffLog,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	577 void* workSpace, size_t wkspSize)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	578 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	579 return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 1 /* single stream */, workSpace, wkspSize);
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	580 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	581
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	582 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	583 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	584 unsigned maxSymbolValue, unsigned huffLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	585 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	586 unsigned workSpace[1024];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	587 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: 30434 diff changeset	588 }
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	589
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	590 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: 30434 diff changeset	591 const void* src, size_t srcSize,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	592 unsigned maxSymbolValue, unsigned huffLog,
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	593 void* workSpace, size_t wkspSize)
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	594 {
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	595 return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 0 /* 4 streams */, workSpace, wkspSize);
30434 2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596 }
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 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	599 const void* src, size_t srcSize,
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	600 unsigned maxSymbolValue, unsigned huffLog)
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	601 {
30822 b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	602 unsigned workSpace[1024];
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 30434 diff changeset	603 return HUF_compress4X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace));
30434 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
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	606 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	607 {
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	608 return HUF_compress2(dst, maxDstSize, src, (U32)srcSize, 255, HUF_TABLELOG_DEFAULT);
2e484bdea8c4 zstd: vendor zstd 1.1.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	609 }

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/compress/huf_compress.c @ 30895:c32454d69b85