/* ****************************************************************** * FSE : Finite State Entropy encoder * Copyright (c) Meta Platforms, Inc. and affiliates. * * You can contact the author at : * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy * - Public forum : https://groups.google.com/forum/#!forum/lz4c * * This source code is licensed under both the BSD-style license (found in the * LICENSE file in the root directory of this source tree) and the GPLv2 (found * in the COPYING file in the root directory of this source tree). * You may select, at your option, one of the above-listed licenses. ****************************************************************** */ /* ************************************************************** * Includes ****************************************************************/ #include "../common/compiler.h" #include "../common/mem.h" /* U32, U16, etc. */ #include "../common/debug.h" /* assert, DEBUGLOG */ #include "hist.h" /* HIST_count_wksp */ #include "../common/bitstream.h" #define FSE_STATIC_LINKING_ONLY #include "../common/fse.h" #include "../common/error_private.h" #define ZSTD_DEPS_NEED_MALLOC #define ZSTD_DEPS_NEED_MATH64 #include "../common/zstd_deps.h" /* ZSTD_memset */ #include "../common/bits.h" /* ZSTD_highbit32 */ /* ************************************************************** * Error Management ****************************************************************/ #define FSE_isError … /* ************************************************************** * Templates ****************************************************************/ /* designed to be included for type-specific functions (template emulation in C) Objective is to write these functions only once, for improved maintenance */ /* safety checks */ #ifndef FSE_FUNCTION_EXTENSION # error "FSE_FUNCTION_EXTENSION must be defined" #endif #ifndef FSE_FUNCTION_TYPE # error "FSE_FUNCTION_TYPE must be defined" #endif /* Function names */ #define FSE_CAT(X,Y) … #define FSE_FUNCTION_NAME(X,Y) … #define FSE_TYPE_NAME(X,Y) … /* Function templates */ /* FSE_buildCTable_wksp() : * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)` * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements */ size_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize) { … } #ifndef FSE_COMMONDEFS_ONLY /*-************************************************************** * FSE NCount encoding ****************************************************************/ size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog) { … } static size_t FSE_writeNCount_generic (void* header, size_t headerBufferSize, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, unsigned writeIsSafe) { … } size_t FSE_writeNCount (void* buffer, size_t bufferSize, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) { … } /*-************************************************************** * FSE Compression Code ****************************************************************/ /* provides the minimum logSize to safely represent a distribution */ static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue) { … } unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus) { … } unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue) { … } /* Secondary normalization method. To be used when primary method fails. */ static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue, short lowProbCount) { … } size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog, const unsigned* count, size_t total, unsigned maxSymbolValue, unsigned useLowProbCount) { … } /* fake FSE_CTable, for rle input (always same symbol) */ size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue) { … } static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize, const void* src, size_t srcSize, const FSE_CTable* ct, const unsigned fast) { … } size_t FSE_compress_usingCTable (void* dst, size_t dstSize, const void* src, size_t srcSize, const FSE_CTable* ct) { … } size_t FSE_compressBound(size_t size) { … } #endif /* FSE_COMMONDEFS_ONLY */