view release on metacpan or search on metacpan
ext/zstd/doc/educational_decoder/zstd_decompress.c view on Meta::CPAN
224122422243224422452246224722482249225022512252225322542255225622572258225922602261const u16 lower_mask = ((u16)1 << (bits - 1)) - 1;
const u16 threshold = ((u16)1 << bits) - 1 - (remaining + 1);
if
((val & lower_mask) < threshold) {
IO_rewind_bits(in, 1);
val = val & lower_mask;
}
else
if
(val > lower_mask) {
val = val - threshold;
}
// "Probability is obtained from Value decoded by following formula :
// Proba = value - 1"
const i16 proba = (i16)val - 1;
// "It means value 0 becomes negative probability -1. -1 is a special
// probability, which means
"less than 1"
. Its effect on distribution
// table is described in
next
paragraph. For the purpose of calculating
// cumulated distribution, it counts as one."
remaining -= proba < 0 ? -proba : proba;
frequencies[symb] = proba;
ext/zstd/doc/zstd_compression_format.md view on Meta::CPAN
240241242243244245246247248249250251252253254255256257258259260The `Window_Descriptor` byte is optional.
When `Single_Segment_flag` is set, `Window_Descriptor` is not present.
In this case, `Window_Size` is `Frame_Content_Size`,
which can be any value from 0 to 2^64-1 bytes (16 ExaBytes).
| Bit numbers | 7-3 | 2-0 |
| ----------- | ---------- | ---------- |
| Field name | `Exponent` | `Mantissa` |
The minimum memory buffer size is called `Window_Size`.
It is described by the following formulas :
```
windowLog = 10 + Exponent;
windowBase = 1 << windowLog;
windowAdd = (windowBase / 8) * Mantissa;
Window_Size = windowBase + windowAdd;
```
The minimum `Window_Size` is 1 KB.
The maximum `Window_Size` is `(1<<41) + 7*(1<<38)` bytes, which is 3.75 TB.
In general, larger `Window_Size` tend to improve compression ratio,
ext/zstd/doc/zstd_compression_format.md view on Meta::CPAN
764765766767768769770771772773774775776777778779780781782783784##### Offset codes
Offset codes are
values
ranging from `0` to `N`.
A decoder is free to limit its maximum `N` supported.
Recommendation is to support at least up to `22`.
For information, at the
time
of this writing.
the reference decoder supports a maximum `N` value of `31`.
An offset code is also the number of additional bits to
read
in __little-endian__ fashion,
and can be translated into an `Offset_Value` using the following formulas :
```
Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if
(Offset_Value > 3) offset = Offset_Value - 3;
```
It means that maximum `Offset_Value` is `(2^(N+1))-1`
supporting back-reference distances up to `(2^(N+1))-4`,
but is limited by [maximum back-reference distance](
#window_descriptor).
`Offset_Value` from 1 to 3 are special : they define
"repeat codes"
.
ext/zstd/doc/zstd_compression_format.md view on Meta::CPAN
109410951096109710981099110011011102110311041105110611071108110911101111111211131114
| Value
read
| Value decoded | Number of bits used |
| ---------- | ------------- | ------------------- |
| 0 - 97 | 0 - 97 | 7 |
| 98 - 127 | 98 - 127 | 8 |
| 128 - 225 | 0 - 97 | 7 |
| 226 - 255 | 128 - 157 | 8 |
Symbols probabilities are
read
one by one, in order.
Probability is obtained from Value decoded by following formula :
`Proba = value - 1`
It means value `0` becomes negative probability `-1`.
`-1` is a special probability, which means
"less than 1"
.
Its effect on distribution table is described in the [
next
section].
For the purpose of calculating total allocated probability points, it counts as one.
[
next
section]:
#from-normalized-distribution-to-decoding-tables
When a symbol
has
a __probability__ of `zero`,
ext/zstd/doc/zstd_compression_format.md view on Meta::CPAN
123612371238123912401241124212431244124512461247124812491250125112521253125412551256Prefix code must not exceed a maximum code
length
.
More bits improve accuracy but cost more header size,
This specification limits maximum code
length
to 11 bits.
#### Representation
All literal
values
from zero (included) to
last
present one (excluded)
are represented by `Weight`
with
values
from `0` to `Max_Number_of_Bits`.
Transformation from `Weight` to `Number_of_Bits` follows this formula :
```
Number_of_Bits = Weight ? (Max_Number_of_Bits + 1 - Weight) : 0
```
When a literal value is not present, it receives a `Weight` of 0.
The least frequent symbol receives a `Weight` of 1.
Consequently, the `Weight` 1 is necessarily present.
The most frequent symbol receives a `Weight` anywhere between 1 and 11 (max).
The
last
symbol's `Weight` is deduced from previously retrieved Weights,
by completing to the nearest power of 2. It's necessarily non 0.
If it's not possible to reach a clean power of 2
with
a single `Weight` value,
ext/zstd/doc/zstd_compression_format.md view on Meta::CPAN
126412651266126712681269127012711272127312741275127612771278127912801281128212831284| literal value | 0 | 1 | 2 | 3 | 4 | 5 |
| ---------------- | --- | --- | --- | --- | --- | --- |
| `Number_of_Bits` | 1 | 2 | 3 | 0 | 4 | 4 |
The tree depth is 4, since its longest elements uses 4 bits
(longest elements are the one
with
smallest frequency).
Literal value `5` will not be listed, as it can be determined from previous
values
0-4,
nor will
values
above `5` as they are all 0.
Values from `0` to `4` will be listed using `Weight` instead of `Number_of_Bits`.
Weight formula is :
```
Weight = Number_of_Bits ? (Max_Number_of_Bits + 1 - Number_of_Bits) : 0
```
It gives the following series of weights :
| literal value | 0 | 1 | 2 | 3 | 4 |
| ------------- | --- | --- | --- | --- | --- |
| `Weight` | 4 | 3 | 2 | 0 | 1 |
The decoder will
do
the inverse operation :
ext/zstd/doc/zstd_compression_format.md view on Meta::CPAN
134613471348134913501351135213531354135513561357135813591360136113621363136413651366The number of symbols to decode is determined
by tracking bitStream overflow condition:
remain in the stream, it is assumed that extra bits are 0. Then,
symbols
for
each
of the final states are decoded and the process is complete.
#### Conversion from weights to Huffman prefix codes
All present symbols shall now have a `Weight` value.
It is possible to transform weights into `Number_of_Bits`, using this formula:
```
Number_of_Bits = (Weight>0) ? Max_Number_of_Bits + 1 - Weight : 0
```
Symbols are sorted by `Weight`.
Within same `Weight`, symbols keep natural sequential order.
Symbols
with
a `Weight` of zero are removed.
Then, starting from lowest `Weight`, prefix codes are distributed in sequential order.
__Example__ :
Let's presume the following list of weights
has
been decoded :
ext/zstd/doc/zstd_manual.html view on Meta::CPAN
150151152153154155156157158159160161162163164165166167168169170* In which case, ZSTD_compressBound() will
return
an error code
* which can be tested using ZSTD_isError().
*
* ZSTD_COMPRESSBOUND() :
* same as ZSTD_compressBound(), but as a macro.
* It can be used to produce constants, which can be useful
for
static allocation,
*
for
example to size a static array on stack.
* Will produce constant value 0
if
srcSize too large.
*/
#define ZSTD_MAX_INPUT_SIZE ((sizeof(size_t)==8) ? 0xFF00FF00FF00FF00LLU : 0xFF00FF00U)
#define ZSTD_COMPRESSBOUND(srcSize) (((size_t)(srcSize) >= ZSTD_MAX_INPUT_SIZE) ? 0 : (srcSize) + ((srcSize)>>8) + (((srcSize) < (128<<10)) ? (((128<<10) - (srcSize)) >> 11) </b>/* margin, from 64 to 0 */ : 0)) /* this formula ensures that bound(A...
size_t ZSTD_compressBound(size_t srcSize); </b>/*!< maximum compressed size in worst case single-pass scenario */<b>
</b>/* ZSTD_isError() :<b>
* Most ZSTD_* functions returning a size_t value can be tested
for
error,
* using ZSTD_isError().
*
@return
1
if
error, 0 otherwise
*/
unsigned ZSTD_isError(size_t code); </b>/*!< tells
if
a `size_t` function result is an error code */<b>
const char* ZSTD_getErrorName(size_t code); </b>/*!< provides readable string from an error code */<b>
int
ZSTD_minCLevel(void); </b>/*!< minimum negative compression level allowed, requires v1.4.0+ */<b>
int
ZSTD_maxCLevel(void); </b>/*!< maximum compression level available */<b>
ext/zstd/lib/common/fse.h view on Meta::CPAN
575576577578579580581582583584585586587588589590591592593594595}
#ifndef FSE_COMMONDEFS_ONLY
/* **************************************************************
* Tuning parameters
****************************************************************/
/*!MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#ifndef FSE_MAX_MEMORY_USAGE
# define FSE_MAX_MEMORY_USAGE 14
#endif
#ifndef FSE_DEFAULT_MEMORY_USAGE
# define FSE_DEFAULT_MEMORY_USAGE 13
#endif
#if (FSE_DEFAULT_MEMORY_USAGE > FSE_MAX_MEMORY_USAGE)
ext/zstd/lib/common/xxhash.h view on Meta::CPAN
742743744745746747748749750751752753754755756757758759760761762* XXH3's speed benefits greatly from SIMD and 64-bit arithmetic,
* Any 32-bit and 64-bit targets that can run XXH32 smoothly
* can run XXH3 at competitive speeds, even without vector support.
* Further details are explained in the implementation.
*
* Optimized implementations are provided
for
AVX512, AVX2, SSE2, NEON, POWER8,
* ZVector and
scalar
targets. This can be controlled via the XXH_VECTOR macro.
*
* XXH3 implementation is portable:
* it
has
a generic C90 formulation that can be compiled on any platform,
* all implementations generage exactly the same hash value on all platforms.
* Starting from v0.8.0, it's also labelled
"stable"
, meaning that
* any future version will also generate the same hash value.
*
* XXH3 offers 2 variants, _64bits and _128bits.
*
* When only 64 bits are needed, prefer invoking the _64bits variant, as it
* reduces the amount of mixing, resulting in faster speed on small inputs.
* It's also generally simpler to manipulate a
scalar
return
type than a struct.
*
ext/zstd/lib/compress/zstd_compress_internal.h view on Meta::CPAN
585586587588589590591592593594595596597598599600601602603604605
RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall,
""
);
MEM_writeLE24(op, cBlockHeader);
op[3] = src;
return
4;
}
/* ZSTD_minGain() :
* minimum compression required
* to generate a compress block or a compressed literals section.
MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
{
U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6;
ZSTD_STATIC_ASSERT(ZSTD_btultra == 8);
assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, (
int
)strat));
return
(srcSize >> minlog) + 2;
}
MEM_STATIC
int
ZSTD_literalsCompressionIsDisabled(const ZSTD_CCtx_params* cctxParams)
{
ext/zstd/lib/legacy/zstd_v01.c view on Meta::CPAN
9293949596979899100101102103104105106107108109110111112
FSE_DStream_endOfBuffer = 1,
FSE_DStream_completed = 2,
FSE_DStream_tooFar = 3 } FSE_DStream_status; /* result of FSE_reloadDStream() */
/* 1,2,4,8 would be better
for
bitmap combinations, but slows down performance a bit ... ?! */
/****************************************************************
* Tuning parameters
****************************************************************/
/* MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#define FSE_MAX_MEMORY_USAGE 14
#define FSE_DEFAULT_MEMORY_USAGE 13
/* FSE_MAX_SYMBOL_VALUE :
* Maximum symbol value authorized.
* Required
for
proper stack allocation */
#define FSE_MAX_SYMBOL_VALUE 255
ext/zstd/lib/legacy/zstd_v01.c view on Meta::CPAN
117611771178117911801181118211831184118511861187118811891190119111921193119411951196
You can contact the author at :
- zstd source repository : https://github.com/Cyan4973/zstd
*/
/****************************************************************
* Tuning parameters
*****************************************************************/
/* MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect */
#define ZSTD_MEMORY_USAGE 17
/**************************************
CPU Feature Detection
**************************************/
/*
* Automated efficient unaligned memory access detection
ext/zstd/lib/legacy/zstd_v02.c view on Meta::CPAN
927928929930931932933934935936937938939940941942943944945946947
- FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
****************************************************************** */
#ifndef FSE_COMMONDEFS_ONLY
/****************************************************************
* Tuning parameters
****************************************************************/
/* MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#define FSE_MAX_MEMORY_USAGE 14
#define FSE_DEFAULT_MEMORY_USAGE 13
/* FSE_MAX_SYMBOL_VALUE :
* Maximum symbol value authorized.
* Required
for
proper stack allocation */
#define FSE_MAX_SYMBOL_VALUE 255
ext/zstd/lib/legacy/zstd_v02.c view on Meta::CPAN
258725882589259025912592259325942595259625972598259926002601260226032604260526062607
You can contact the author at :
- zstd source repository : https://github.com/Cyan4973/zstd
*/
/* ***************************************************************
* Tuning parameters
*****************************************************************/
/*!
* MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
*/
#define ZSTD_MEMORY_USAGE 17
/*!
* HEAPMODE :
* Select how
default
compression functions will allocate memory
for
their hash table,
* in memory stack (0, fastest), or in memory heap (1, requires malloc())
* Note that compression context is fairly large, as a consequence heap memory is recommended.
ext/zstd/lib/legacy/zstd_v03.c view on Meta::CPAN
927928929930931932933934935936937938939940941942943944945946947
- FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
****************************************************************** */
#ifndef FSE_COMMONDEFS_ONLY
/****************************************************************
* Tuning parameters
****************************************************************/
/* MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#define FSE_MAX_MEMORY_USAGE 14
#define FSE_DEFAULT_MEMORY_USAGE 13
/* FSE_MAX_SYMBOL_VALUE :
* Maximum symbol value authorized.
* Required
for
proper stack allocation */
#define FSE_MAX_SYMBOL_VALUE 255
ext/zstd/lib/legacy/zstd_v03.c view on Meta::CPAN
222522262227222822292230223122322233223422352236223722382239224022412242224322442245
You can contact the author at :
- zstd source repository : https://github.com/Cyan4973/zstd
*/
/* ***************************************************************
* Tuning parameters
*****************************************************************/
/*!
* MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
*/
#define ZSTD_MEMORY_USAGE 17
/*!
* HEAPMODE :
* Select how
default
compression functions will allocate memory
for
their hash table,
* in memory stack (0, fastest), or in memory heap (1, requires malloc())
* Note that compression context is fairly large, as a consequence heap memory is recommended.
ext/zstd/lib/legacy/zstd_v04.c view on Meta::CPAN
911912913914915916917918919920921922923924925926927928929930931
- FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
****************************************************************** */
#ifndef FSE_COMMONDEFS_ONLY
/* **************************************************************
* Tuning parameters
****************************************************************/
/*!MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#define FSE_MAX_MEMORY_USAGE 14
#define FSE_DEFAULT_MEMORY_USAGE 13
/*!FSE_MAX_SYMBOL_VALUE :
* Maximum symbol value authorized.
* Required
for
proper stack allocation */
#define FSE_MAX_SYMBOL_VALUE 255
ext/zstd/lib/legacy/zstd_v05.c view on Meta::CPAN
102810291030103110321033103410351036103710381039104010411042104310441045104610471048
- FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
****************************************************************** */
#ifndef FSEv05_COMMONDEFS_ONLY
/* **************************************************************
* Tuning parameters
****************************************************************/
/*!MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#define FSEv05_MAX_MEMORY_USAGE 14
#define FSEv05_DEFAULT_MEMORY_USAGE 13
/*!FSEv05_MAX_SYMBOL_VALUE :
* Maximum symbol value authorized.
* Required
for
proper stack allocation */
#define FSEv05_MAX_SYMBOL_VALUE 255
ext/zstd/lib/legacy/zstd_v06.c view on Meta::CPAN
110511061107110811091110111111121113111411151116111711181119112011211122112311241125}
#ifndef FSEv06_COMMONDEFS_ONLY
/* **************************************************************
* Tuning parameters
****************************************************************/
/*!MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#define FSEv06_MAX_MEMORY_USAGE 14
#define FSEv06_DEFAULT_MEMORY_USAGE 13
/*!FSEv06_MAX_SYMBOL_VALUE :
* Maximum symbol value authorized.
* Required
for
proper stack allocation */
#define FSEv06_MAX_SYMBOL_VALUE 255
ext/zstd/lib/legacy/zstd_v07.c view on Meta::CPAN
870871872873874875876877878879880881882883884885886887888889890}
#ifndef FSEv07_COMMONDEFS_ONLY
/* **************************************************************
* Tuning parameters
****************************************************************/
/*!MEMORY_USAGE :
* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
* Increasing memory usage improves compression ratio
* Reduced memory usage can improve speed, due to cache effect
* Recommended max value is 14,
for
16KB, which nicely fits into Intel x86 L1 cache */
#define FSEv07_MAX_MEMORY_USAGE 14
#define FSEv07_DEFAULT_MEMORY_USAGE 13
/*!FSEv07_MAX_SYMBOL_VALUE :
* Maximum symbol value authorized.
* Required
for
proper stack allocation */
#define FSEv07_MAX_SYMBOL_VALUE 255
ext/zstd/lib/zstd.h view on Meta::CPAN
222223224225226227228229230231232233234235236237238239240241242* In which case, ZSTD_compressBound() will
return
an error code
* which can be tested using ZSTD_isError().
*
* ZSTD_COMPRESSBOUND() :
* same as ZSTD_compressBound(), but as a macro.
* It can be used to produce constants, which can be useful
for
static allocation,
*
for
example to size a static array on stack.
* Will produce constant value 0
if
srcSize too large.
*/
#define ZSTD_MAX_INPUT_SIZE ((sizeof(size_t)==8) ? 0xFF00FF00FF00FF00LLU : 0xFF00FF00U)
#define ZSTD_COMPRESSBOUND(srcSize) (((size_t)(srcSize) >= ZSTD_MAX_INPUT_SIZE) ? 0 : (srcSize) + ((srcSize)>>8) + (((srcSize) < (128<<10)) ? (((128<<10) - (srcSize)) >> 11) /* margin, from 64 to 0 */ : 0)) /* this formula ensures that bound(A) + ...
ZSTDLIB_API size_t ZSTD_compressBound(size_t srcSize); /*!< maximum compressed size in worst case single-pass scenario */
/* ZSTD_isError() :
* Most ZSTD_* functions returning a size_t value can be tested
for
error,
* using ZSTD_isError().
*
@return
1
if
error, 0 otherwise
*/
ZSTDLIB_API unsigned ZSTD_isError(size_t code); /*!< tells
if
a `size_t` function result is an error code */
ZSTDLIB_API const char* ZSTD_getErrorName(size_t code); /*!< provides readable string from an error code */
ZSTDLIB_API
int
ZSTD_minCLevel(void); /*!< minimum negative compression level allowed, requires v1.4.0+ */
ZSTDLIB_API
int
ZSTD_maxCLevel(void); /*!< maximum compression level available */