source: thirdparty/blosc/internal-complibs/zstd-0.7.4/common/huf.h @ 8ebc79b

Revision 8ebc79b, 10.8 KB checked in by Hal Finkel <hfinkel@…>, 8 years ago (diff)

Add the other internal compression libraries from blocs

  • Property mode set to 100644
RevLine 
[8ebc79b]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)
38extern "C" {
39#endif
40
41
42/* *** Dependencies *** */
43#include <stddef.h>    /* size_t */
44
45
46/* *** simple functions *** */
47/**
48HUF_compress() :
49    Compress content from buffer 'src', of size 'srcSize', into buffer 'dst'.
50    'dst' buffer must be already allocated.
51    Compression runs faster if `dstCapacity` >= HUF_compressBound(srcSize).
52    `srcSize` must be <= `HUF_BLOCKSIZE_MAX` == 128 KB.
53    @return : size of compressed data (<= `dstCapacity`).
54    Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!!
55                     if return == 1, srcData is a single repeated byte symbol (RLE compression).
56                     if HUF_isError(return), compression failed (more details using HUF_getErrorName())
57*/
58size_t HUF_compress(void* dst, size_t dstCapacity,
59              const void* src, size_t srcSize);
60
61/**
62HUF_decompress() :
63    Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
64    into already allocated buffer 'dst', of minimum size 'dstSize'.
65    `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
66    Note : in contrast with FSE, HUF_decompress can regenerate
67           RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
68           because it knows size to regenerate.
69    @return : size of regenerated data (== dstSize),
70              or an error code, which can be tested using HUF_isError()
71*/
72size_t HUF_decompress(void* dst,  size_t dstSize,
73                const void* cSrc, size_t cSrcSize);
74
75
76/* ****************************************
77*  Tool functions
78******************************************/
79#define HUF_BLOCKSIZE_MAX (128 * 1024)
80size_t HUF_compressBound(size_t size);       /**< maximum compressed size (worst case) */
81
82/* Error Management */
83unsigned    HUF_isError(size_t code);        /**< tells if a return value is an error code */
84const char* HUF_getErrorName(size_t code);   /**< provides error code string (useful for debugging) */
85
86
87/* *** Advanced function *** */
88
89/** HUF_compress2() :
90*   Same as HUF_compress(), but offers direct control over `maxSymbolValue` and `tableLog` */
91size_t HUF_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog);
92
93
94#ifdef HUF_STATIC_LINKING_ONLY
95
96/* *** Dependencies *** */
97#include "mem.h"   /* U32 */
98
99
100/* *** Constants *** */
101#define HUF_TABLELOG_ABSOLUTEMAX  16   /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
102#define HUF_TABLELOG_MAX  12           /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
103#define HUF_TABLELOG_DEFAULT  HUF_TABLELOG_MAX   /* tableLog by default, when not specified */
104#define HUF_SYMBOLVALUE_MAX 255
105#if (HUF_TABLELOG_MAX > HUF_TABLELOG_ABSOLUTEMAX)
106#  error "HUF_TABLELOG_MAX is too large !"
107#endif
108
109
110/* ****************************************
111*  Static allocation
112******************************************/
113/* HUF buffer bounds */
114#define HUF_CTABLEBOUND 129
115#define HUF_BLOCKBOUND(size) (size + (size>>8) + 8)   /* only true if incompressible pre-filtered with fast heuristic */
116#define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
117
118/* static allocation of HUF's Compression Table */
119#define HUF_CREATE_STATIC_CTABLE(name, maxSymbolValue) \
120    U32 name##hb[maxSymbolValue+1]; \
121    void* name##hv = &(name##hb); \
122    HUF_CElt* name = (HUF_CElt*)(name##hv)   /* no final ; */
123
124/* static allocation of HUF's DTable */
125typedef U32 HUF_DTable;
126#define HUF_DTABLE_SIZE(maxTableLog)   (1 + (1<<(maxTableLog)))
127#define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
128        HUF_DTable DTable[HUF_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
129#define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
130        HUF_DTable DTable[HUF_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
131
132
133/* ****************************************
134*  Advanced decompression functions
135******************************************/
136size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
137size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
138
139size_t HUF_decompress4X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< decodes RLE and uncompressed */
140size_t HUF_decompress4X_hufOnly(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< considers RLE and uncompressed as errors */
141size_t HUF_decompress4X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
142size_t HUF_decompress4X4_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
143
144size_t HUF_decompress1X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
145size_t HUF_decompress1X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
146size_t HUF_decompress1X4_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
147
148
149/* ****************************************
150*  HUF detailed API
151******************************************/
152/*!
153HUF_compress() does the following:
1541. count symbol occurrence from source[] into table count[] using FSE_count()
1552. (optional) refine tableLog using HUF_optimalTableLog()
1563. build Huffman table from count using HUF_buildCTable()
1574. save Huffman table to memory buffer using HUF_writeCTable()
1585. encode the data stream using HUF_compress4X_usingCTable()
159
160The following API allows targeting specific sub-functions for advanced tasks.
161For example, it's possible to compress several blocks using the same 'CTable',
162or to save and regenerate 'CTable' using external methods.
163*/
164/* FSE_count() : find it within "fse.h" */
165unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue);
166typedef struct HUF_CElt_s HUF_CElt;   /* incomplete type */
167size_t HUF_buildCTable (HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue, unsigned maxNbBits);
168size_t HUF_writeCTable (void* dst, size_t maxDstSize, const HUF_CElt* CTable, unsigned maxSymbolValue, unsigned huffLog);
169size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable);
170
171
172/*! HUF_readStats() :
173    Read compact Huffman tree, saved by HUF_writeCTable().
174    `huffWeight` is destination buffer.
175    @return : size read from `src` , or an error Code .
176    Note : Needed by HUF_readCTable() and HUF_readDTableXn() . */
177size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
178                     U32* nbSymbolsPtr, U32* tableLogPtr,
179                     const void* src, size_t srcSize);
180
181/** HUF_readCTable() :
182*   Loading a CTable saved with HUF_writeCTable() */
183size_t HUF_readCTable (HUF_CElt* CTable, unsigned maxSymbolValue, const void* src, size_t srcSize);
184
185
186/*
187HUF_decompress() does the following:
1881. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1892. build Huffman table from save, using HUF_readDTableXn()
1903. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable
191*/
192
193/** HUF_selectDecoder() :
194*   Tells which decoder is likely to decode faster,
195*   based on a set of pre-determined metrics.
196*   @return : 0==HUF_decompress4X2, 1==HUF_decompress4X4 .
197*   Assumption : 0 < cSrcSize < dstSize <= 128 KB */
198U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize);
199
200size_t HUF_readDTableX2 (HUF_DTable* DTable, const void* src, size_t srcSize);
201size_t HUF_readDTableX4 (HUF_DTable* DTable, const void* src, size_t srcSize);
202
203size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
204size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
205size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
206
207
208/* single stream variants */
209
210size_t HUF_compress1X (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog);
211size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable);
212
213size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
214size_t HUF_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-symbol decoder */
215
216size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
217size_t HUF_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
218size_t HUF_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable);
219
220
221#endif /* HUF_STATIC_LINKING_ONLY */
222
223
224#if defined (__cplusplus)
225}
226#endif
227
228#endif   /* HUF_H_298734234 */
Note: See TracBrowser for help on using the repository browser.