Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 1 | /* ****************************************************************** |
| 2 | FSE : Finite State Entropy codec |
| 3 | Public Prototypes declaration |
| 4 | Copyright (C) 2013-2016, Yann Collet. |
| 5 | |
| 6 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) |
| 7 | |
| 8 | Redistribution and use in source and binary forms, with or without |
| 9 | modification, are permitted provided that the following conditions are |
| 10 | met: |
| 11 | |
| 12 | * Redistributions of source code must retain the above copyright |
| 13 | notice, this list of conditions and the following disclaimer. |
| 14 | * Redistributions in binary form must reproduce the above |
| 15 | copyright notice, this list of conditions and the following disclaimer |
| 16 | in the documentation and/or other materials provided with the |
| 17 | distribution. |
| 18 | |
| 19 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 20 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 21 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 22 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 23 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 24 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 25 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 26 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 27 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 28 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 29 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 30 | |
| 31 | You can contact the author at : |
| 32 | - Source repository : https://github.com/Cyan4973/FiniteStateEntropy |
| 33 | ****************************************************************** */ |
| 34 | |
| 35 | #if defined (__cplusplus) |
| 36 | extern "C" { |
| 37 | #endif |
| 38 | |
| 39 | #ifndef FSE_H |
| 40 | #define FSE_H |
| 41 | |
| 42 | |
| 43 | /*-***************************************** |
| 44 | * Dependencies |
| 45 | ******************************************/ |
| 46 | #include <stddef.h> /* size_t, ptrdiff_t */ |
| 47 | |
| 48 | |
| 49 | /*-***************************************** |
| 50 | * FSE_PUBLIC_API : control library symbols visibility |
| 51 | ******************************************/ |
| 52 | #if defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) && defined(__GNUC__) && (__GNUC__ >= 4) |
| 53 | # define FSE_PUBLIC_API __attribute__ ((visibility ("default"))) |
| 54 | #elif defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) /* Visual expected */ |
| 55 | # define FSE_PUBLIC_API __declspec(dllexport) |
| 56 | #elif defined(FSE_DLL_IMPORT) && (FSE_DLL_IMPORT==1) |
| 57 | # define FSE_PUBLIC_API __declspec(dllimport) /* It isn't required but allows to generate better code, saving a function pointer load from the IAT and an indirect jump.*/ |
| 58 | #else |
| 59 | # define FSE_PUBLIC_API |
| 60 | #endif |
| 61 | |
| 62 | /*------ Version ------*/ |
| 63 | #define FSE_VERSION_MAJOR 0 |
| 64 | #define FSE_VERSION_MINOR 9 |
| 65 | #define FSE_VERSION_RELEASE 0 |
| 66 | |
| 67 | #define FSE_LIB_VERSION FSE_VERSION_MAJOR.FSE_VERSION_MINOR.FSE_VERSION_RELEASE |
| 68 | #define FSE_QUOTE(str) #str |
| 69 | #define FSE_EXPAND_AND_QUOTE(str) FSE_QUOTE(str) |
| 70 | #define FSE_VERSION_STRING FSE_EXPAND_AND_QUOTE(FSE_LIB_VERSION) |
| 71 | |
| 72 | #define FSE_VERSION_NUMBER (FSE_VERSION_MAJOR *100*100 + FSE_VERSION_MINOR *100 + FSE_VERSION_RELEASE) |
| 73 | FSE_PUBLIC_API unsigned FSE_versionNumber(void); /**< library version number; to be used when checking dll version */ |
| 74 | |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 75 | |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 76 | /*-**************************************** |
| 77 | * FSE simple functions |
| 78 | ******************************************/ |
| 79 | /*! FSE_compress() : |
| 80 | Compress content of buffer 'src', of size 'srcSize', into destination buffer 'dst'. |
| 81 | 'dst' buffer must be already allocated. Compression runs faster is dstCapacity >= FSE_compressBound(srcSize). |
| 82 | @return : size of compressed data (<= dstCapacity). |
| 83 | Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! |
| 84 | if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression instead. |
| 85 | if FSE_isError(return), compression failed (more details using FSE_getErrorName()) |
| 86 | */ |
| 87 | FSE_PUBLIC_API size_t FSE_compress(void* dst, size_t dstCapacity, |
| 88 | const void* src, size_t srcSize); |
| 89 | |
| 90 | /*! FSE_decompress(): |
| 91 | Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', |
| 92 | into already allocated destination buffer 'dst', of size 'dstCapacity'. |
| 93 | @return : size of regenerated data (<= maxDstSize), |
| 94 | or an error code, which can be tested using FSE_isError() . |
| 95 | |
| 96 | ** Important ** : FSE_decompress() does not decompress non-compressible nor RLE data !!! |
| 97 | Why ? : making this distinction requires a header. |
| 98 | Header management is intentionally delegated to the user layer, which can better manage special cases. |
| 99 | */ |
| 100 | FSE_PUBLIC_API size_t FSE_decompress(void* dst, size_t dstCapacity, |
| 101 | const void* cSrc, size_t cSrcSize); |
| 102 | |
| 103 | |
| 104 | /*-***************************************** |
| 105 | * Tool functions |
| 106 | ******************************************/ |
| 107 | FSE_PUBLIC_API size_t FSE_compressBound(size_t size); /* maximum compressed size */ |
| 108 | |
| 109 | /* Error Management */ |
| 110 | FSE_PUBLIC_API unsigned FSE_isError(size_t code); /* tells if a return value is an error code */ |
| 111 | FSE_PUBLIC_API const char* FSE_getErrorName(size_t code); /* provides error code string (useful for debugging) */ |
| 112 | |
| 113 | |
| 114 | /*-***************************************** |
| 115 | * FSE advanced functions |
| 116 | ******************************************/ |
| 117 | /*! FSE_compress2() : |
| 118 | Same as FSE_compress(), but allows the selection of 'maxSymbolValue' and 'tableLog' |
| 119 | Both parameters can be defined as '0' to mean : use default value |
| 120 | @return : size of compressed data |
| 121 | Special values : if return == 0, srcData is not compressible => Nothing is stored within cSrc !!! |
| 122 | if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression. |
| 123 | if FSE_isError(return), it's an error code. |
| 124 | */ |
| 125 | FSE_PUBLIC_API size_t FSE_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog); |
| 126 | |
| 127 | |
| 128 | /*-***************************************** |
| 129 | * FSE detailed API |
| 130 | ******************************************/ |
| 131 | /*! |
| 132 | FSE_compress() does the following: |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 133 | 1. count symbol occurrence from source[] into table count[] (see hist.h) |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 134 | 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog) |
| 135 | 3. save normalized counters to memory buffer using writeNCount() |
| 136 | 4. build encoding table 'CTable' from normalized counters |
| 137 | 5. encode the data stream using encoding table 'CTable' |
| 138 | |
| 139 | FSE_decompress() does the following: |
| 140 | 1. read normalized counters with readNCount() |
| 141 | 2. build decoding table 'DTable' from normalized counters |
| 142 | 3. decode the data stream using decoding table 'DTable' |
| 143 | |
| 144 | The following API allows targeting specific sub-functions for advanced tasks. |
| 145 | For example, it's possible to compress several blocks using the same 'CTable', |
| 146 | or to save and provide normalized distribution using external method. |
| 147 | */ |
| 148 | |
| 149 | /* *** COMPRESSION *** */ |
| 150 | |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 151 | /*! FSE_optimalTableLog(): |
| 152 | dynamically downsize 'tableLog' when conditions are met. |
| 153 | It saves CPU time, by using smaller tables, while preserving or even improving compression ratio. |
| 154 | @return : recommended tableLog (necessarily <= 'maxTableLog') */ |
| 155 | FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue); |
| 156 | |
| 157 | /*! FSE_normalizeCount(): |
| 158 | normalize counts so that sum(count[]) == Power_of_2 (2^tableLog) |
| 159 | 'normalizedCounter' is a table of short, of minimum size (maxSymbolValue+1). |
| 160 | @return : tableLog, |
| 161 | or an errorCode, which can be tested using FSE_isError() */ |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 162 | FSE_PUBLIC_API size_t FSE_normalizeCount(short* normalizedCounter, unsigned tableLog, |
| 163 | const unsigned* count, size_t srcSize, unsigned maxSymbolValue); |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 164 | |
| 165 | /*! FSE_NCountWriteBound(): |
| 166 | Provides the maximum possible size of an FSE normalized table, given 'maxSymbolValue' and 'tableLog'. |
| 167 | Typically useful for allocation purpose. */ |
| 168 | FSE_PUBLIC_API size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog); |
| 169 | |
| 170 | /*! FSE_writeNCount(): |
| 171 | Compactly save 'normalizedCounter' into 'buffer'. |
| 172 | @return : size of the compressed table, |
| 173 | or an errorCode, which can be tested using FSE_isError(). */ |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 174 | FSE_PUBLIC_API size_t FSE_writeNCount (void* buffer, size_t bufferSize, |
| 175 | const short* normalizedCounter, |
| 176 | unsigned maxSymbolValue, unsigned tableLog); |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 177 | |
| 178 | /*! Constructor and Destructor of FSE_CTable. |
| 179 | Note that FSE_CTable size depends on 'tableLog' and 'maxSymbolValue' */ |
| 180 | typedef unsigned FSE_CTable; /* don't allocate that. It's only meant to be more restrictive than void* */ |
| 181 | FSE_PUBLIC_API FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog); |
| 182 | FSE_PUBLIC_API void FSE_freeCTable (FSE_CTable* ct); |
| 183 | |
| 184 | /*! FSE_buildCTable(): |
| 185 | Builds `ct`, which must be already allocated, using FSE_createCTable(). |
| 186 | @return : 0, or an errorCode, which can be tested using FSE_isError() */ |
| 187 | FSE_PUBLIC_API size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); |
| 188 | |
| 189 | /*! FSE_compress_usingCTable(): |
| 190 | Compress `src` using `ct` into `dst` which must be already allocated. |
| 191 | @return : size of compressed data (<= `dstCapacity`), |
| 192 | or 0 if compressed data could not fit into `dst`, |
| 193 | or an errorCode, which can be tested using FSE_isError() */ |
| 194 | FSE_PUBLIC_API size_t FSE_compress_usingCTable (void* dst, size_t dstCapacity, const void* src, size_t srcSize, const FSE_CTable* ct); |
| 195 | |
| 196 | /*! |
| 197 | Tutorial : |
| 198 | ---------- |
| 199 | The first step is to count all symbols. FSE_count() does this job very fast. |
| 200 | Result will be saved into 'count', a table of unsigned int, which must be already allocated, and have 'maxSymbolValuePtr[0]+1' cells. |
| 201 | 'src' is a table of bytes of size 'srcSize'. All values within 'src' MUST be <= maxSymbolValuePtr[0] |
| 202 | maxSymbolValuePtr[0] will be updated, with its real value (necessarily <= original value) |
| 203 | FSE_count() will return the number of occurrence of the most frequent symbol. |
| 204 | This can be used to know if there is a single symbol within 'src', and to quickly evaluate its compressibility. |
| 205 | If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()). |
| 206 | |
| 207 | The next step is to normalize the frequencies. |
| 208 | FSE_normalizeCount() will ensure that sum of frequencies is == 2 ^'tableLog'. |
| 209 | It also guarantees a minimum of 1 to any Symbol with frequency >= 1. |
| 210 | You can use 'tableLog'==0 to mean "use default tableLog value". |
| 211 | If you are unsure of which tableLog value to use, you can ask FSE_optimalTableLog(), |
| 212 | which will provide the optimal valid tableLog given sourceSize, maxSymbolValue, and a user-defined maximum (0 means "default"). |
| 213 | |
| 214 | The result of FSE_normalizeCount() will be saved into a table, |
| 215 | called 'normalizedCounter', which is a table of signed short. |
| 216 | 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValue+1' cells. |
| 217 | The return value is tableLog if everything proceeded as expected. |
| 218 | It is 0 if there is a single symbol within distribution. |
| 219 | If there is an error (ex: invalid tableLog value), the function will return an ErrorCode (which can be tested using FSE_isError()). |
| 220 | |
| 221 | 'normalizedCounter' can be saved in a compact manner to a memory area using FSE_writeNCount(). |
| 222 | 'buffer' must be already allocated. |
| 223 | For guaranteed success, buffer size must be at least FSE_headerBound(). |
| 224 | The result of the function is the number of bytes written into 'buffer'. |
| 225 | If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError(); ex : buffer size too small). |
| 226 | |
| 227 | 'normalizedCounter' can then be used to create the compression table 'CTable'. |
| 228 | The space required by 'CTable' must be already allocated, using FSE_createCTable(). |
| 229 | You can then use FSE_buildCTable() to fill 'CTable'. |
| 230 | If there is an error, both functions will return an ErrorCode (which can be tested using FSE_isError()). |
| 231 | |
| 232 | 'CTable' can then be used to compress 'src', with FSE_compress_usingCTable(). |
| 233 | Similar to FSE_count(), the convention is that 'src' is assumed to be a table of char of size 'srcSize' |
| 234 | The function returns the size of compressed data (without header), necessarily <= `dstCapacity`. |
| 235 | If it returns '0', compressed data could not fit into 'dst'. |
| 236 | If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()). |
| 237 | */ |
| 238 | |
| 239 | |
| 240 | /* *** DECOMPRESSION *** */ |
| 241 | |
| 242 | /*! FSE_readNCount(): |
| 243 | Read compactly saved 'normalizedCounter' from 'rBuffer'. |
| 244 | @return : size read from 'rBuffer', |
| 245 | or an errorCode, which can be tested using FSE_isError(). |
| 246 | maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 247 | FSE_PUBLIC_API size_t FSE_readNCount (short* normalizedCounter, |
| 248 | unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, |
| 249 | const void* rBuffer, size_t rBuffSize); |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 250 | |
| 251 | /*! Constructor and Destructor of FSE_DTable. |
| 252 | Note that its size depends on 'tableLog' */ |
| 253 | typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ |
| 254 | FSE_PUBLIC_API FSE_DTable* FSE_createDTable(unsigned tableLog); |
| 255 | FSE_PUBLIC_API void FSE_freeDTable(FSE_DTable* dt); |
| 256 | |
| 257 | /*! FSE_buildDTable(): |
| 258 | Builds 'dt', which must be already allocated, using FSE_createDTable(). |
| 259 | return : 0, or an errorCode, which can be tested using FSE_isError() */ |
| 260 | FSE_PUBLIC_API size_t FSE_buildDTable (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); |
| 261 | |
| 262 | /*! FSE_decompress_usingDTable(): |
| 263 | Decompress compressed source `cSrc` of size `cSrcSize` using `dt` |
| 264 | into `dst` which must be already allocated. |
| 265 | @return : size of regenerated data (necessarily <= `dstCapacity`), |
| 266 | or an errorCode, which can be tested using FSE_isError() */ |
| 267 | FSE_PUBLIC_API size_t FSE_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt); |
| 268 | |
| 269 | /*! |
| 270 | Tutorial : |
| 271 | ---------- |
| 272 | (Note : these functions only decompress FSE-compressed blocks. |
| 273 | If block is uncompressed, use memcpy() instead |
| 274 | If block is a single repeated byte, use memset() instead ) |
| 275 | |
| 276 | The first step is to obtain the normalized frequencies of symbols. |
| 277 | This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount(). |
| 278 | 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. |
| 279 | In practice, that means it's necessary to know 'maxSymbolValue' beforehand, |
| 280 | or size the table to handle worst case situations (typically 256). |
| 281 | FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'. |
| 282 | The result of FSE_readNCount() is the number of bytes read from 'rBuffer'. |
| 283 | Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. |
| 284 | If there is an error, the function will return an error code, which can be tested using FSE_isError(). |
| 285 | |
| 286 | The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'. |
| 287 | This is performed by the function FSE_buildDTable(). |
| 288 | The space required by 'FSE_DTable' must be already allocated using FSE_createDTable(). |
| 289 | If there is an error, the function will return an error code, which can be tested using FSE_isError(). |
| 290 | |
| 291 | `FSE_DTable` can then be used to decompress `cSrc`, with FSE_decompress_usingDTable(). |
| 292 | `cSrcSize` must be strictly correct, otherwise decompression will fail. |
| 293 | FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`). |
| 294 | If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small) |
| 295 | */ |
| 296 | |
| 297 | #endif /* FSE_H */ |
| 298 | |
| 299 | #if defined(FSE_STATIC_LINKING_ONLY) && !defined(FSE_H_FSE_STATIC_LINKING_ONLY) |
| 300 | #define FSE_H_FSE_STATIC_LINKING_ONLY |
| 301 | |
| 302 | /* *** Dependency *** */ |
| 303 | #include "bitstream.h" |
| 304 | |
| 305 | |
| 306 | /* ***************************************** |
| 307 | * Static allocation |
| 308 | *******************************************/ |
| 309 | /* FSE buffer bounds */ |
| 310 | #define FSE_NCOUNTBOUND 512 |
| 311 | #define FSE_BLOCKBOUND(size) (size + (size>>7)) |
| 312 | #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ |
| 313 | |
| 314 | /* It is possible to statically allocate FSE CTable/DTable as a table of FSE_CTable/FSE_DTable using below macros */ |
| 315 | #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2)) |
| 316 | #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) |
| 317 | |
| 318 | /* or use the size to malloc() space directly. Pay attention to alignment restrictions though */ |
| 319 | #define FSE_CTABLE_SIZE(maxTableLog, maxSymbolValue) (FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) * sizeof(FSE_CTable)) |
| 320 | #define FSE_DTABLE_SIZE(maxTableLog) (FSE_DTABLE_SIZE_U32(maxTableLog) * sizeof(FSE_DTable)) |
| 321 | |
| 322 | |
| 323 | /* ***************************************** |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 324 | * FSE advanced API |
| 325 | ***************************************** */ |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 326 | |
| 327 | unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus); |
| 328 | /**< same as FSE_optimalTableLog(), which used `minus==2` */ |
| 329 | |
| 330 | /* FSE_compress_wksp() : |
| 331 | * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`). |
| 332 | * FSE_WKSP_SIZE_U32() provides the minimum size required for `workSpace` as a table of FSE_CTable. |
| 333 | */ |
| 334 | #define FSE_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) ( FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) + ((maxTableLog > 12) ? (1 << (maxTableLog - 2)) : 1024) ) |
| 335 | size_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); |
| 336 | |
| 337 | size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits); |
| 338 | /**< build a fake FSE_CTable, designed for a flat distribution, where each symbol uses nbBits */ |
| 339 | |
| 340 | size_t FSE_buildCTable_rle (FSE_CTable* ct, unsigned char symbolValue); |
| 341 | /**< build a fake FSE_CTable, designed to compress always the same symbolValue */ |
| 342 | |
| 343 | /* FSE_buildCTable_wksp() : |
| 344 | * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). |
| 345 | * `wkspSize` must be >= `(1<<tableLog)`. |
| 346 | */ |
| 347 | size_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); |
| 348 | |
| 349 | size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits); |
| 350 | /**< build a fake FSE_DTable, designed to read a flat distribution where each symbol uses nbBits */ |
| 351 | |
| 352 | size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue); |
| 353 | /**< build a fake FSE_DTable, designed to always generate the same symbolValue */ |
| 354 | |
| 355 | size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, FSE_DTable* workSpace, unsigned maxLog); |
| 356 | /**< same as FSE_decompress(), using an externally allocated `workSpace` produced with `FSE_DTABLE_SIZE_U32(maxLog)` */ |
| 357 | |
| 358 | typedef enum { |
| 359 | FSE_repeat_none, /**< Cannot use the previous table */ |
| 360 | FSE_repeat_check, /**< Can use the previous table but it must be checked */ |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 361 | FSE_repeat_valid /**< Can use the previous table and it is assumed to be valid */ |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 362 | } FSE_repeat; |
| 363 | |
| 364 | /* ***************************************** |
| 365 | * FSE symbol compression API |
| 366 | *******************************************/ |
| 367 | /*! |
| 368 | This API consists of small unitary functions, which highly benefit from being inlined. |
| 369 | Hence their body are included in next section. |
| 370 | */ |
| 371 | typedef struct { |
| 372 | ptrdiff_t value; |
| 373 | const void* stateTable; |
| 374 | const void* symbolTT; |
| 375 | unsigned stateLog; |
| 376 | } FSE_CState_t; |
| 377 | |
| 378 | static void FSE_initCState(FSE_CState_t* CStatePtr, const FSE_CTable* ct); |
| 379 | |
| 380 | static void FSE_encodeSymbol(BIT_CStream_t* bitC, FSE_CState_t* CStatePtr, unsigned symbol); |
| 381 | |
| 382 | static void FSE_flushCState(BIT_CStream_t* bitC, const FSE_CState_t* CStatePtr); |
| 383 | |
| 384 | /**< |
| 385 | These functions are inner components of FSE_compress_usingCTable(). |
| 386 | They allow the creation of custom streams, mixing multiple tables and bit sources. |
| 387 | |
| 388 | A key property to keep in mind is that encoding and decoding are done **in reverse direction**. |
| 389 | So the first symbol you will encode is the last you will decode, like a LIFO stack. |
| 390 | |
| 391 | You will need a few variables to track your CStream. They are : |
| 392 | |
| 393 | FSE_CTable ct; // Provided by FSE_buildCTable() |
| 394 | BIT_CStream_t bitStream; // bitStream tracking structure |
| 395 | FSE_CState_t state; // State tracking structure (can have several) |
| 396 | |
| 397 | |
| 398 | The first thing to do is to init bitStream and state. |
| 399 | size_t errorCode = BIT_initCStream(&bitStream, dstBuffer, maxDstSize); |
| 400 | FSE_initCState(&state, ct); |
| 401 | |
| 402 | Note that BIT_initCStream() can produce an error code, so its result should be tested, using FSE_isError(); |
| 403 | You can then encode your input data, byte after byte. |
| 404 | FSE_encodeSymbol() outputs a maximum of 'tableLog' bits at a time. |
| 405 | Remember decoding will be done in reverse direction. |
| 406 | FSE_encodeByte(&bitStream, &state, symbol); |
| 407 | |
| 408 | At any time, you can also add any bit sequence. |
| 409 | Note : maximum allowed nbBits is 25, for compatibility with 32-bits decoders |
| 410 | BIT_addBits(&bitStream, bitField, nbBits); |
| 411 | |
| 412 | The above methods don't commit data to memory, they just store it into local register, for speed. |
| 413 | Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t). |
| 414 | Writing data to memory is a manual operation, performed by the flushBits function. |
| 415 | BIT_flushBits(&bitStream); |
| 416 | |
| 417 | Your last FSE encoding operation shall be to flush your last state value(s). |
| 418 | FSE_flushState(&bitStream, &state); |
| 419 | |
| 420 | Finally, you must close the bitStream. |
| 421 | The function returns the size of CStream in bytes. |
| 422 | If data couldn't fit into dstBuffer, it will return a 0 ( == not compressible) |
| 423 | If there is an error, it returns an errorCode (which can be tested using FSE_isError()). |
| 424 | size_t size = BIT_closeCStream(&bitStream); |
| 425 | */ |
| 426 | |
| 427 | |
| 428 | /* ***************************************** |
| 429 | * FSE symbol decompression API |
| 430 | *******************************************/ |
| 431 | typedef struct { |
| 432 | size_t state; |
| 433 | const void* table; /* precise table may vary, depending on U16 */ |
| 434 | } FSE_DState_t; |
| 435 | |
| 436 | |
| 437 | static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt); |
| 438 | |
| 439 | static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); |
| 440 | |
| 441 | static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr); |
| 442 | |
| 443 | /**< |
| 444 | Let's now decompose FSE_decompress_usingDTable() into its unitary components. |
| 445 | You will decode FSE-encoded symbols from the bitStream, |
| 446 | and also any other bitFields you put in, **in reverse order**. |
| 447 | |
| 448 | You will need a few variables to track your bitStream. They are : |
| 449 | |
| 450 | BIT_DStream_t DStream; // Stream context |
| 451 | FSE_DState_t DState; // State context. Multiple ones are possible |
| 452 | FSE_DTable* DTablePtr; // Decoding table, provided by FSE_buildDTable() |
| 453 | |
| 454 | The first thing to do is to init the bitStream. |
| 455 | errorCode = BIT_initDStream(&DStream, srcBuffer, srcSize); |
| 456 | |
| 457 | You should then retrieve your initial state(s) |
| 458 | (in reverse flushing order if you have several ones) : |
| 459 | errorCode = FSE_initDState(&DState, &DStream, DTablePtr); |
| 460 | |
| 461 | You can then decode your data, symbol after symbol. |
| 462 | For information the maximum number of bits read by FSE_decodeSymbol() is 'tableLog'. |
| 463 | Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out). |
| 464 | unsigned char symbol = FSE_decodeSymbol(&DState, &DStream); |
| 465 | |
| 466 | You can retrieve any bitfield you eventually stored into the bitStream (in reverse order) |
| 467 | Note : maximum allowed nbBits is 25, for 32-bits compatibility |
| 468 | size_t bitField = BIT_readBits(&DStream, nbBits); |
| 469 | |
| 470 | All above operations only read from local register (which size depends on size_t). |
| 471 | Refueling the register from memory is manually performed by the reload method. |
| 472 | endSignal = FSE_reloadDStream(&DStream); |
| 473 | |
| 474 | BIT_reloadDStream() result tells if there is still some more data to read from DStream. |
| 475 | BIT_DStream_unfinished : there is still some data left into the DStream. |
| 476 | BIT_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled. |
| 477 | BIT_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed. |
| 478 | BIT_DStream_tooFar : Dstream went too far. Decompression result is corrupted. |
| 479 | |
| 480 | When reaching end of buffer (BIT_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop, |
| 481 | to properly detect the exact end of stream. |
| 482 | After each decoded symbol, check if DStream is fully consumed using this simple test : |
| 483 | BIT_reloadDStream(&DStream) >= BIT_DStream_completed |
| 484 | |
| 485 | When it's done, verify decompression is fully completed, by checking both DStream and the relevant states. |
| 486 | Checking if DStream has reached its end is performed by : |
| 487 | BIT_endOfDStream(&DStream); |
| 488 | Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible. |
| 489 | FSE_endOfDState(&DState); |
| 490 | */ |
| 491 | |
| 492 | |
| 493 | /* ***************************************** |
| 494 | * FSE unsafe API |
| 495 | *******************************************/ |
| 496 | static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); |
| 497 | /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ |
| 498 | |
| 499 | |
| 500 | /* ***************************************** |
| 501 | * Implementation of inlined functions |
| 502 | *******************************************/ |
| 503 | typedef struct { |
| 504 | int deltaFindState; |
| 505 | U32 deltaNbBits; |
| 506 | } FSE_symbolCompressionTransform; /* total 8 bytes */ |
| 507 | |
| 508 | MEM_STATIC void FSE_initCState(FSE_CState_t* statePtr, const FSE_CTable* ct) |
| 509 | { |
| 510 | const void* ptr = ct; |
| 511 | const U16* u16ptr = (const U16*) ptr; |
| 512 | const U32 tableLog = MEM_read16(ptr); |
| 513 | statePtr->value = (ptrdiff_t)1<<tableLog; |
| 514 | statePtr->stateTable = u16ptr+2; |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 515 | statePtr->symbolTT = ct + 1 + (tableLog ? (1<<(tableLog-1)) : 1); |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 516 | statePtr->stateLog = tableLog; |
| 517 | } |
| 518 | |
| 519 | |
| 520 | /*! FSE_initCState2() : |
| 521 | * Same as FSE_initCState(), but the first symbol to include (which will be the last to be read) |
| 522 | * uses the smallest state value possible, saving the cost of this symbol */ |
| 523 | MEM_STATIC void FSE_initCState2(FSE_CState_t* statePtr, const FSE_CTable* ct, U32 symbol) |
| 524 | { |
| 525 | FSE_initCState(statePtr, ct); |
| 526 | { const FSE_symbolCompressionTransform symbolTT = ((const FSE_symbolCompressionTransform*)(statePtr->symbolTT))[symbol]; |
| 527 | const U16* stateTable = (const U16*)(statePtr->stateTable); |
| 528 | U32 nbBitsOut = (U32)((symbolTT.deltaNbBits + (1<<15)) >> 16); |
| 529 | statePtr->value = (nbBitsOut << 16) - symbolTT.deltaNbBits; |
| 530 | statePtr->value = stateTable[(statePtr->value >> nbBitsOut) + symbolTT.deltaFindState]; |
| 531 | } |
| 532 | } |
| 533 | |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 534 | MEM_STATIC void FSE_encodeSymbol(BIT_CStream_t* bitC, FSE_CState_t* statePtr, unsigned symbol) |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 535 | { |
| 536 | FSE_symbolCompressionTransform const symbolTT = ((const FSE_symbolCompressionTransform*)(statePtr->symbolTT))[symbol]; |
| 537 | const U16* const stateTable = (const U16*)(statePtr->stateTable); |
| 538 | U32 const nbBitsOut = (U32)((statePtr->value + symbolTT.deltaNbBits) >> 16); |
| 539 | BIT_addBits(bitC, statePtr->value, nbBitsOut); |
| 540 | statePtr->value = stateTable[ (statePtr->value >> nbBitsOut) + symbolTT.deltaFindState]; |
| 541 | } |
| 542 | |
| 543 | MEM_STATIC void FSE_flushCState(BIT_CStream_t* bitC, const FSE_CState_t* statePtr) |
| 544 | { |
| 545 | BIT_addBits(bitC, statePtr->value, statePtr->stateLog); |
| 546 | BIT_flushBits(bitC); |
| 547 | } |
| 548 | |
| 549 | |
Scott Baker | 8487c5d | 2019-10-18 12:49:46 -0700 | [diff] [blame^] | 550 | /* FSE_getMaxNbBits() : |
| 551 | * Approximate maximum cost of a symbol, in bits. |
| 552 | * Fractional get rounded up (i.e : a symbol with a normalized frequency of 3 gives the same result as a frequency of 2) |
| 553 | * note 1 : assume symbolValue is valid (<= maxSymbolValue) |
| 554 | * note 2 : if freq[symbolValue]==0, @return a fake cost of tableLog+1 bits */ |
| 555 | MEM_STATIC U32 FSE_getMaxNbBits(const void* symbolTTPtr, U32 symbolValue) |
| 556 | { |
| 557 | const FSE_symbolCompressionTransform* symbolTT = (const FSE_symbolCompressionTransform*) symbolTTPtr; |
| 558 | return (symbolTT[symbolValue].deltaNbBits + ((1<<16)-1)) >> 16; |
| 559 | } |
| 560 | |
| 561 | /* FSE_bitCost() : |
| 562 | * Approximate symbol cost, as fractional value, using fixed-point format (accuracyLog fractional bits) |
| 563 | * note 1 : assume symbolValue is valid (<= maxSymbolValue) |
| 564 | * note 2 : if freq[symbolValue]==0, @return a fake cost of tableLog+1 bits */ |
| 565 | MEM_STATIC U32 FSE_bitCost(const void* symbolTTPtr, U32 tableLog, U32 symbolValue, U32 accuracyLog) |
| 566 | { |
| 567 | const FSE_symbolCompressionTransform* symbolTT = (const FSE_symbolCompressionTransform*) symbolTTPtr; |
| 568 | U32 const minNbBits = symbolTT[symbolValue].deltaNbBits >> 16; |
| 569 | U32 const threshold = (minNbBits+1) << 16; |
| 570 | assert(tableLog < 16); |
| 571 | assert(accuracyLog < 31-tableLog); /* ensure enough room for renormalization double shift */ |
| 572 | { U32 const tableSize = 1 << tableLog; |
| 573 | U32 const deltaFromThreshold = threshold - (symbolTT[symbolValue].deltaNbBits + tableSize); |
| 574 | U32 const normalizedDeltaFromThreshold = (deltaFromThreshold << accuracyLog) >> tableLog; /* linear interpolation (very approximate) */ |
| 575 | U32 const bitMultiplier = 1 << accuracyLog; |
| 576 | assert(symbolTT[symbolValue].deltaNbBits + tableSize <= threshold); |
| 577 | assert(normalizedDeltaFromThreshold <= bitMultiplier); |
| 578 | return (minNbBits+1)*bitMultiplier - normalizedDeltaFromThreshold; |
| 579 | } |
| 580 | } |
| 581 | |
| 582 | |
Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 583 | /* ====== Decompression ====== */ |
| 584 | |
| 585 | typedef struct { |
| 586 | U16 tableLog; |
| 587 | U16 fastMode; |
| 588 | } FSE_DTableHeader; /* sizeof U32 */ |
| 589 | |
| 590 | typedef struct |
| 591 | { |
| 592 | unsigned short newState; |
| 593 | unsigned char symbol; |
| 594 | unsigned char nbBits; |
| 595 | } FSE_decode_t; /* size == U32 */ |
| 596 | |
| 597 | MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt) |
| 598 | { |
| 599 | const void* ptr = dt; |
| 600 | const FSE_DTableHeader* const DTableH = (const FSE_DTableHeader*)ptr; |
| 601 | DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog); |
| 602 | BIT_reloadDStream(bitD); |
| 603 | DStatePtr->table = dt + 1; |
| 604 | } |
| 605 | |
| 606 | MEM_STATIC BYTE FSE_peekSymbol(const FSE_DState_t* DStatePtr) |
| 607 | { |
| 608 | FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; |
| 609 | return DInfo.symbol; |
| 610 | } |
| 611 | |
| 612 | MEM_STATIC void FSE_updateState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) |
| 613 | { |
| 614 | FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; |
| 615 | U32 const nbBits = DInfo.nbBits; |
| 616 | size_t const lowBits = BIT_readBits(bitD, nbBits); |
| 617 | DStatePtr->state = DInfo.newState + lowBits; |
| 618 | } |
| 619 | |
| 620 | MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) |
| 621 | { |
| 622 | FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; |
| 623 | U32 const nbBits = DInfo.nbBits; |
| 624 | BYTE const symbol = DInfo.symbol; |
| 625 | size_t const lowBits = BIT_readBits(bitD, nbBits); |
| 626 | |
| 627 | DStatePtr->state = DInfo.newState + lowBits; |
| 628 | return symbol; |
| 629 | } |
| 630 | |
| 631 | /*! FSE_decodeSymbolFast() : |
| 632 | unsafe, only works if no symbol has a probability > 50% */ |
| 633 | MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) |
| 634 | { |
| 635 | FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; |
| 636 | U32 const nbBits = DInfo.nbBits; |
| 637 | BYTE const symbol = DInfo.symbol; |
| 638 | size_t const lowBits = BIT_readBitsFast(bitD, nbBits); |
| 639 | |
| 640 | DStatePtr->state = DInfo.newState + lowBits; |
| 641 | return symbol; |
| 642 | } |
| 643 | |
| 644 | MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr) |
| 645 | { |
| 646 | return DStatePtr->state == 0; |
| 647 | } |
| 648 | |
| 649 | |
| 650 | |
| 651 | #ifndef FSE_COMMONDEFS_ONLY |
| 652 | |
| 653 | /* ************************************************************** |
| 654 | * Tuning parameters |
| 655 | ****************************************************************/ |
| 656 | /*!MEMORY_USAGE : |
| 657 | * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) |
| 658 | * Increasing memory usage improves compression ratio |
| 659 | * Reduced memory usage can improve speed, due to cache effect |
| 660 | * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ |
| 661 | #ifndef FSE_MAX_MEMORY_USAGE |
| 662 | # define FSE_MAX_MEMORY_USAGE 14 |
| 663 | #endif |
| 664 | #ifndef FSE_DEFAULT_MEMORY_USAGE |
| 665 | # define FSE_DEFAULT_MEMORY_USAGE 13 |
| 666 | #endif |
| 667 | |
| 668 | /*!FSE_MAX_SYMBOL_VALUE : |
| 669 | * Maximum symbol value authorized. |
| 670 | * Required for proper stack allocation */ |
| 671 | #ifndef FSE_MAX_SYMBOL_VALUE |
| 672 | # define FSE_MAX_SYMBOL_VALUE 255 |
| 673 | #endif |
| 674 | |
| 675 | /* ************************************************************** |
| 676 | * template functions type & suffix |
| 677 | ****************************************************************/ |
| 678 | #define FSE_FUNCTION_TYPE BYTE |
| 679 | #define FSE_FUNCTION_EXTENSION |
| 680 | #define FSE_DECODE_TYPE FSE_decode_t |
| 681 | |
| 682 | |
| 683 | #endif /* !FSE_COMMONDEFS_ONLY */ |
| 684 | |
| 685 | |
| 686 | /* *************************************************************** |
| 687 | * Constants |
| 688 | *****************************************************************/ |
| 689 | #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) |
| 690 | #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG) |
| 691 | #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1) |
| 692 | #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2) |
| 693 | #define FSE_MIN_TABLELOG 5 |
| 694 | |
| 695 | #define FSE_TABLELOG_ABSOLUTE_MAX 15 |
| 696 | #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX |
| 697 | # error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" |
| 698 | #endif |
| 699 | |
| 700 | #define FSE_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3) |
| 701 | |
| 702 | |
| 703 | #endif /* FSE_STATIC_LINKING_ONLY */ |
| 704 | |
| 705 | |
| 706 | #if defined (__cplusplus) |
| 707 | } |
| 708 | #endif |