contrib/zstd/lib/common/huf.h

   1 /* ******************************************************************
   2    Huffman coder, part of New Generation Entropy library
   3    header file
   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 #ifndef HUF_H_298734234
  35 #define HUF_H_298734234
  36
  37 #if defined (__cplusplus)
  38 extern "C" {
  39 #endif
  40
  41
  42 /* *** Dependencies *** */
  43 #include <stddef.h>    /* size_t */
  44
  45
  46 /* *** library symbols visibility *** */
  47 /* Note : when linking with -fvisibility=hidden on gcc, or by default on Visual,
  48  *        HUF symbols remain "private" (internal symbols for library only).
  49  *        Set macro FSE_DLL_EXPORT to 1 if you want HUF symbols visible on DLL interface */
  50 #if defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) && defined(__GNUC__) && (__GNUC__ >= 4)
  51 #  define HUF_PUBLIC_API __attribute__ ((visibility ("default")))
  52 #elif defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1)   /* Visual expected */
  53 #  define HUF_PUBLIC_API __declspec(dllexport)
  54 #elif defined(FSE_DLL_IMPORT) && (FSE_DLL_IMPORT==1)
  55 #  define HUF_PUBLIC_API __declspec(dllimport)  /* not required, just to generate faster code (saves a function pointer load from IAT and an indirect jump) */
  56 #else
  57 #  define HUF_PUBLIC_API
  58 #endif
  59
  60
  61 /* *** simple functions *** */
  62 /**
  63 HUF_compress() :
  64     Compress content from buffer 'src', of size 'srcSize', into buffer 'dst'.
  65     'dst' buffer must be already allocated.
  66     Compression runs faster if `dstCapacity` >= HUF_compressBound(srcSize).
  67     `srcSize` must be <= `HUF_BLOCKSIZE_MAX` == 128 KB.
  68     @return : size of compressed data (<= `dstCapacity`).
  69     Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!!
  70                      if return == 1, srcData is a single repeated byte symbol (RLE compression).
  71                      if HUF_isError(return), compression failed (more details using HUF_getErrorName())
  72 */
  73 HUF_PUBLIC_API size_t HUF_compress(void* dst, size_t dstCapacity,
  74                              const void* src, size_t srcSize);
  75
  76 /**
  77 HUF_decompress() :
  78     Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
  79     into already allocated buffer 'dst', of minimum size 'dstSize'.
  80     `originalSize` : **must** be the ***exact*** size of original (uncompressed) data.
  81     Note : in contrast with FSE, HUF_decompress can regenerate
  82            RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
  83            because it knows size to regenerate.
  84     @return : size of regenerated data (== originalSize),
  85               or an error code, which can be tested using HUF_isError()
  86 */
  87 HUF_PUBLIC_API size_t HUF_decompress(void* dst,  size_t originalSize,
  88                                const void* cSrc, size_t cSrcSize);
  89
  90
  91 /* ***   Tool functions *** */
  92 #define HUF_BLOCKSIZE_MAX (128 * 1024)                  /**< maximum input size for a single block compressed with HUF_compress */
  93 HUF_PUBLIC_API size_t HUF_compressBound(size_t size);   /**< maximum compressed size (worst case) */
  94
  95 /* Error Management */
  96 HUF_PUBLIC_API unsigned    HUF_isError(size_t code);       /**< tells if a return value is an error code */
  97 HUF_PUBLIC_API const char* HUF_getErrorName(size_t code);  /**< provides error code string (useful for debugging) */
  98
  99
 100 /* ***   Advanced function   *** */
 101
 102 /** HUF_compress2() :
 103  *  Same as HUF_compress(), but offers direct control over `maxSymbolValue` and `tableLog`.
 104  *  `tableLog` must be `<= HUF_TABLELOG_MAX` . */
 105 HUF_PUBLIC_API size_t HUF_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog);
 106
 107 /** HUF_compress4X_wksp() :
 108  *  Same as HUF_compress2(), but uses externally allocated `workSpace`.
 109  *  `workspace` must have minimum alignment of 4, and be at least as large as following macro */
 110 #define HUF_WORKSPACE_SIZE (6 << 10)
 111 #define HUF_WORKSPACE_SIZE_U32 (HUF_WORKSPACE_SIZE / sizeof(U32))
 112 HUF_PUBLIC_API size_t HUF_compress4X_wksp (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize);
 113
 114 /**
 115  *  The minimum workspace size for the `workSpace` used in
 116  *  HUF_readDTableX2_wksp() and HUF_readDTableX4_wksp().
 117  *
 118  *  The space used depends on HUF_TABLELOG_MAX, ranging from ~1500 bytes when
 119  *  HUF_TABLE_LOG_MAX=12 to ~1850 bytes when HUF_TABLE_LOG_MAX=15.
 120  *  Buffer overflow errors may potentially occur if code modifications result in
 121  *  a required workspace size greater than that specified in the following
 122  *  macro.
 123  */
 124 #define HUF_DECOMPRESS_WORKSPACE_SIZE (2 << 10)
 125 #define HUF_DECOMPRESS_WORKSPACE_SIZE_U32 (HUF_DECOMPRESS_WORKSPACE_SIZE / sizeof(U32))
 126
 127
 128 /* ******************************************************************
 129  *  WARNING !!
 130  *  The following section contains advanced and experimental definitions
 131  *  which shall never be used in the context of dll
 132  *  because they are not guaranteed to remain stable in the future.
 133  *  Only consider them in association with static linking.
 134  *******************************************************************/
 135 #ifdef HUF_STATIC_LINKING_ONLY
 136
 137 /* *** Dependencies *** */
 138 #include "mem.h"   /* U32 */
 139
 140
 141 /* *** Constants *** */
 142 #define HUF_TABLELOG_MAX      12       /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
 143 #define HUF_TABLELOG_DEFAULT  11       /* tableLog by default, when not specified */
 144 #define HUF_SYMBOLVALUE_MAX  255
 145
 146 #define HUF_TABLELOG_ABSOLUTEMAX  15   /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
 147 #if (HUF_TABLELOG_MAX > HUF_TABLELOG_ABSOLUTEMAX)
 148 #  error "HUF_TABLELOG_MAX is too large !"
 149 #endif
 150
 151
 152 /* ****************************************
 153 *  Static allocation
 154 ******************************************/
 155 /* HUF buffer bounds */
 156 #define HUF_CTABLEBOUND 129
 157 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8)   /* only true when incompressible is pre-filtered with fast heuristic */
 158 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
 159
 160 /* static allocation of HUF's Compression Table */
 161 #define HUF_CTABLE_SIZE_U32(maxSymbolValue)   ((maxSymbolValue)+1)   /* Use tables of U32, for proper alignment */
 162 #define HUF_CTABLE_SIZE(maxSymbolValue)       (HUF_CTABLE_SIZE_U32(maxSymbolValue) * sizeof(U32))
 163 #define HUF_CREATE_STATIC_CTABLE(name, maxSymbolValue) \
 164     U32 name##hb[HUF_CTABLE_SIZE_U32(maxSymbolValue)]; \
 165     void* name##hv = &(name##hb); \
 166     HUF_CElt* name = (HUF_CElt*)(name##hv)   /* no final ; */
 167
 168 /* static allocation of HUF's DTable */
 169 typedef U32 HUF_DTable;
 170 #define HUF_DTABLE_SIZE(maxTableLog)   (1 + (1<<(maxTableLog)))
 171 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
 172         HUF_DTable DTable[HUF_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1) * 0x01000001) }
 173 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
 174         HUF_DTable DTable[HUF_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog) * 0x01000001) }
 175
 176
 177 /* ****************************************
 178 *  Advanced decompression functions
 179 ******************************************/
 180 size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
 181 size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
 182
 183 size_t HUF_decompress4X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< decodes RLE and uncompressed */
 184 size_t HUF_decompress4X_hufOnly(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< considers RLE and uncompressed as errors */
 185 size_t HUF_decompress4X_hufOnly_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize); /**< considers RLE and uncompressed as errors */
 186 size_t HUF_decompress4X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
 187 size_t HUF_decompress4X2_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize);   /**< single-symbol decoder */
 188 size_t HUF_decompress4X4_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
 189 size_t HUF_decompress4X4_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize);   /**< double-symbols decoder */
 190
 191
 192 /* ****************************************
 193 *  HUF detailed API
 194 ******************************************/
 195 /*!
 196 HUF_compress() does the following:
 197 1. count symbol occurrence from source[] into table count[] using FSE_count()
 198 2. (optional) refine tableLog using HUF_optimalTableLog()
 199 3. build Huffman table from count using HUF_buildCTable()
 200 4. save Huffman table to memory buffer using HUF_writeCTable()
 201 5. encode the data stream using HUF_compress4X_usingCTable()
 202
 203 The following API allows targeting specific sub-functions for advanced tasks.
 204 For example, it's possible to compress several blocks using the same 'CTable',
 205 or to save and regenerate 'CTable' using external methods.
 206 */
 207 /* FSE_count() : find it within "fse.h" */
 208 unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue);
 209 typedef struct HUF_CElt_s HUF_CElt;   /* incomplete type */
 210 size_t HUF_buildCTable (HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue, unsigned maxNbBits);
 211 size_t HUF_writeCTable (void* dst, size_t maxDstSize, const HUF_CElt* CTable, unsigned maxSymbolValue, unsigned huffLog);
 212 size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable);
 213
 214 typedef enum {
 215    HUF_repeat_none,  /**< Cannot use the previous table */
 216    HUF_repeat_check, /**< Can use the previous table but it must be checked. Note : The previous table must have been constructed by HUF_compress{1, 4}X_repeat */
 217    HUF_repeat_valid  /**< Can use the previous table and it is asumed to be valid */
 218  } HUF_repeat;
 219 /** HUF_compress4X_repeat() :
 220 *   Same as HUF_compress4X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none.
 221 *   If it uses hufTable it does not modify hufTable or repeat.
 222 *   If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used.
 223 *   If preferRepeat then the old table will always be used if valid. */
 224 size_t HUF_compress4X_repeat(void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize, HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat);  /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */
 225
 226 /** HUF_buildCTable_wksp() :
 227  *  Same as HUF_buildCTable(), but using externally allocated scratch buffer.
 228  *  `workSpace` must be aligned on 4-bytes boundaries, and be at least as large as a table of 1024 unsigned.
 229  */
 230 size_t HUF_buildCTable_wksp (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize);
 231
 232 /*! HUF_readStats() :
 233     Read compact Huffman tree, saved by HUF_writeCTable().
 234     `huffWeight` is destination buffer.
 235     @return : size read from `src` , or an error Code .
 236     Note : Needed by HUF_readCTable() and HUF_readDTableXn() . */
 237 size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
 238                      U32* nbSymbolsPtr, U32* tableLogPtr,
 239                      const void* src, size_t srcSize);
 240
 241 /** HUF_readCTable() :
 242 *   Loading a CTable saved with HUF_writeCTable() */
 243 size_t HUF_readCTable (HUF_CElt* CTable, unsigned maxSymbolValue, const void* src, size_t srcSize);
 244
 245
 246 /*
 247 HUF_decompress() does the following:
 248 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
 249 2. build Huffman table from save, using HUF_readDTableXn()
 250 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable
 251 */
 252
 253 /** HUF_selectDecoder() :
 254 *   Tells which decoder is likely to decode faster,
 255 *   based on a set of pre-determined metrics.
 256 *   @return : 0==HUF_decompress4X2, 1==HUF_decompress4X4 .
 257 *   Assumption : 0 < cSrcSize < dstSize <= 128 KB */
 258 U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize);
 259
 260 size_t HUF_readDTableX2 (HUF_DTable* DTable, const void* src, size_t srcSize);
 261 size_t HUF_readDTableX2_wksp (HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize);
 262 size_t HUF_readDTableX4 (HUF_DTable* DTable, const void* src, size_t srcSize);
 263 size_t HUF_readDTableX4_wksp (HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize);
 264
 265 size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
 266 size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
 267 size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
 268
 269
 270 /* single stream variants */
 271
 272 size_t HUF_compress1X (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog);
 273 size_t HUF_compress1X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize);  /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */
 274 size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable);
 275 /** HUF_compress1X_repeat() :
 276 *   Same as HUF_compress1X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none.
 277 *   If it uses hufTable it does not modify hufTable or repeat.
 278 *   If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used.
 279 *   If preferRepeat then the old table will always be used if valid. */
 280 size_t HUF_compress1X_repeat(void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize, HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat);  /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */
 281
 282 size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
 283 size_t HUF_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-symbol decoder */
 284
 285 size_t HUF_decompress1X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
 286 size_t HUF_decompress1X_DCtx_wksp (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize);
 287 size_t HUF_decompress1X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
 288 size_t HUF_decompress1X2_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize);   /**< single-symbol decoder */
 289 size_t HUF_decompress1X4_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
 290 size_t HUF_decompress1X4_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize);   /**< double-symbols decoder */
 291
 292 size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);   /**< automatic selection of sing or double symbol decoder, based on DTable */
 293 size_t HUF_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
 294 size_t HUF_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
 295
 296 #endif /* HUF_STATIC_LINKING_ONLY */
 297
 298
 299 #if defined (__cplusplus)
 300 }
 301 #endif
 302
 303 #endif   /* HUF_H_298734234 */