39 # pragma warning(disable : 4127) 51 #define FSE_STATIC_LINKING_ONLY 53 #define HUF_STATIC_LINKING_ONLY 59 #define HUFC_ALLOC_TAG 0x63465548 // "HUFc" 65 #define HUF_isError ERR_isError 66 #define HUF_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) 67 #define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return e 68 #define CHECK_F(f) { CHECK_V_F(_var_err__, f); } 88 #define MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6 93 BYTE*
const oend = ostart + dstSize;
95 U32 maxSymbolValue = HUF_TABLELOG_MAX;
105 if (wtSize <= 1)
return 0;
124 if (cSize == 0)
return 0;
141 const HUF_CElt* CTable,
U32 maxSymbolValue,
U32 huffLog)
143 BYTE bitsToWeight[HUF_TABLELOG_MAX + 1];
144 BYTE huffWeight[HUF_SYMBOLVALUE_MAX];
149 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX)
return ERROR(maxSymbolValue_tooLarge);
153 for (
n=1;
n<huffLog+1;
n++)
154 bitsToWeight[
n] = (
BYTE)(huffLog + 1 -
n);
155 for (
n=0;
n<maxSymbolValue;
n++)
156 huffWeight[
n] = bitsToWeight[CTable[
n].nbBits];
160 if ((hSize>1) & (hSize < maxSymbolValue/2)) {
166 if (maxSymbolValue > (256-128))
return ERROR(GENERIC);
167 if (((maxSymbolValue+1)/2) + 1 > maxDstSize)
return ERROR(dstSize_tooSmall);
168 op[0] = (
BYTE)(128 + (maxSymbolValue-1));
169 huffWeight[maxSymbolValue] = 0;
170 for (
n=0;
n<maxSymbolValue;
n+=2)
171 op[(
n/2)+1] = (
BYTE)((huffWeight[
n] << 4) + huffWeight[
n+1]);
172 return ((maxSymbolValue+1)/2) + 1;
178 BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1];
179 U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1];
187 if (tableLog > HUF_TABLELOG_MAX)
return ERROR(tableLog_tooLarge);
188 if (nbSymbols > *maxSymbolValuePtr+1)
return ERROR(maxSymbolValue_tooSmall);
191 {
U32 n, nextRankStart = 0;
192 for (
n=1;
n<=tableLog;
n++) {
194 nextRankStart += (rankVal[
n] << (
n-1));
199 {
U32 n;
for (
n=0;
n<nbSymbols;
n++) {
200 const U32 w = huffWeight[
n];
201 CTable[
n].nbBits = (
BYTE)(tableLog + 1 -
w);
205 {
U16 nbPerRank[HUF_TABLELOG_MAX+2] = {0};
206 U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
207 {
U32 n;
for (
n=0;
n<nbSymbols;
n++) nbPerRank[CTable[
n].nbBits]++; }
209 valPerRank[tableLog+1] = 0;
211 U32 n;
for (
n=tableLog;
n>0;
n--) {
217 {
U32 n;
for (
n=0;
n<nbSymbols;
n++) CTable[
n].
val = valPerRank[CTable[
n].nbBits]++; }
220 *maxSymbolValuePtr = nbSymbols - 1;
226 const HUF_CElt*
table = (
const HUF_CElt*)symbolTable;
227 assert(symbolValue <= HUF_SYMBOLVALUE_MAX);
228 return table[symbolValue].nbBits;
241 const U32 largestBits = huffNode[lastNonNull].
nbBits;
242 if (largestBits <= maxNbBits)
return largestBits;
246 const U32 baseCost = 1 << (largestBits - maxNbBits);
249 while (huffNode[
n].nbBits > maxNbBits) {
250 totalCost += baseCost - (1 << (largestBits - huffNode[
n].
nbBits));
254 while (huffNode[
n].nbBits == maxNbBits)
n--;
257 totalCost >>= (largestBits - maxNbBits);
260 {
U32 const noSymbol = 0xF0F0F0F0;
261 U32 rankLast[HUF_TABLELOG_MAX+2];
265 memset(rankLast, 0xF0,
sizeof(rankLast));
266 {
U32 currentNbBits = maxNbBits;
268 if (huffNode[
pos].nbBits >= currentNbBits)
continue;
270 rankLast[maxNbBits-currentNbBits] =
pos;
273 while (totalCost > 0) {
275 for ( ; nBitsToDecrease > 1; nBitsToDecrease--) {
276 U32 highPos = rankLast[nBitsToDecrease];
277 U32 lowPos = rankLast[nBitsToDecrease-1];
278 if (highPos == noSymbol)
continue;
279 if (lowPos == noSymbol)
break;
280 {
U32 const highTotal = huffNode[highPos].
count;
281 U32 const lowTotal = 2 * huffNode[lowPos].
count;
282 if (highTotal <= lowTotal)
break;
286 while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol))
288 totalCost -= 1 << (nBitsToDecrease-1);
289 if (rankLast[nBitsToDecrease-1] == noSymbol)
290 rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease];
291 huffNode[rankLast[nBitsToDecrease]].
nbBits ++;
292 if (rankLast[nBitsToDecrease] == 0)
293 rankLast[nBitsToDecrease] = noSymbol;
295 rankLast[nBitsToDecrease]--;
296 if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
297 rankLast[nBitsToDecrease] = noSymbol;
300 while (totalCost < 0) {
301 if (rankLast[1] == noSymbol) {
302 while (huffNode[
n].nbBits == maxNbBits)
n--;
308 huffNode[ rankLast[1] + 1 ].
nbBits--;
327 memset(rank, 0,
sizeof(rank));
328 for (
n=0;
n<=maxSymbolValue;
n++) {
334 for (
n=0;
n<=maxSymbolValue;
n++) {
339 huffNode[
pos] = huffNode[
pos-1];
352 #define STARTNODE (HUF_SYMBOLVALUE_MAX+1) 357 nodeElt*
const huffNode = huffNode0+1;
364 if (((
size_t)workSpace & 3) != 0)
return ERROR(GENERIC);
366 if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
367 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX)
return ERROR(maxSymbolValue_tooLarge);
374 nonNullRank = maxSymbolValue;
375 while(huffNode[nonNullRank].
count == 0) nonNullRank--;
376 lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb;
377 huffNode[nodeNb].
count = huffNode[lowS].
count + huffNode[lowS-1].
count;
378 huffNode[lowS].
parent = huffNode[lowS-1].
parent = nodeNb;
380 for (
n=nodeNb;
n<=nodeRoot;
n++) huffNode[
n].
count = (
U32)(1
U<<30);
384 while (nodeNb <= nodeRoot) {
385 U32 n1 = (huffNode[lowS].
count < huffNode[lowN].
count) ? lowS-- : lowN++;
386 U32 n2 = (huffNode[lowS].
count < huffNode[lowN].
count) ? lowS-- : lowN++;
393 huffNode[nodeRoot].
nbBits = 0;
395 huffNode[
n].nbBits = huffNode[ huffNode[
n].
parent ].nbBits + 1;
396 for (
n=0;
n<=nonNullRank;
n++)
397 huffNode[
n].nbBits = huffNode[ huffNode[
n].
parent ].nbBits + 1;
403 {
U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
404 U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
405 if (maxNbBits > HUF_TABLELOG_MAX)
return ERROR(GENERIC);
406 for (
n=0;
n<=nonNullRank;
n++)
407 nbPerRank[huffNode[
n].nbBits]++;
410 for (
n=maxNbBits;
n>0;
n--) {
415 for (
n=0;
n<=maxSymbolValue;
n++)
416 tree[huffNode[
n].
byte].nbBits = huffNode[
n].nbBits;
417 for (
n=0;
n<=maxSymbolValue;
n++)
447 for (
s = 0;
s <= (
int)maxSymbolValue; ++
s) {
448 nbBits += CTable[
s].nbBits *
count[
s];
456 for (
s = 0;
s <= (
int)maxSymbolValue; ++
s) {
457 bad |= (
count[
s] != 0) & (CTable[
s].nbBits == 0);
470 #define HUF_FLUSHBITS(s) BIT_flushBits(s) 472 #define HUF_FLUSHBITS_1(stream) \ 473 if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*2+7) HUF_FLUSHBITS(stream) 475 #define HUF_FLUSHBITS_2(stream) \ 476 if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*4+7) HUF_FLUSHBITS(stream) 480 const void*
src,
size_t srcSize,
481 const HUF_CElt* CTable)
485 BYTE*
const oend = ostart + dstSize;
491 if (dstSize < 8)
return 0;
528 HUF_compress1X_usingCTable_internal_bmi2(
void*
dst,
size_t dstSize,
530 const HUF_CElt* CTable)
536 HUF_compress1X_usingCTable_internal_default(
void*
dst,
size_t dstSize,
537 const void*
src,
size_t srcSize,
538 const HUF_CElt* CTable)
545 const void*
src,
size_t srcSize,
546 const HUF_CElt* CTable,
const int bmi2)
549 return HUF_compress1X_usingCTable_internal_bmi2(
dst, dstSize,
src, srcSize, CTable);
551 return HUF_compress1X_usingCTable_internal_default(
dst, dstSize,
src, srcSize, CTable);
558 const void*
src,
size_t srcSize,
559 const HUF_CElt* CTable,
const int bmi2)
575 const void*
src,
size_t srcSize,
576 const HUF_CElt* CTable,
int bmi2)
578 size_t const segmentSize = (srcSize+3)/4;
580 const BYTE*
const iend =
ip + srcSize;
582 BYTE*
const oend = ostart + dstSize;
585 if (dstSize < 6 + 1 + 1 + 1 + 8)
return 0;
586 if (srcSize < 12)
return 0;
590 if (cSize==0)
return 0;
598 if (cSize==0)
return 0;
606 if (cSize==0)
return 0;
614 if (cSize==0)
return 0;
629 const void*
src,
size_t srcSize,
630 unsigned singleStream,
const HUF_CElt* CTable,
const int bmi2)
632 size_t const cSize = singleStream ?
636 if (cSize==0) {
return 0; }
639 if ((
size_t)(
op-ostart) >= srcSize-1) {
return 0; }
645 HUF_CElt CTable[HUF_SYMBOLVALUE_MAX + 1];
652 void*
dst,
size_t dstSize,
653 const void*
src,
size_t srcSize,
654 unsigned maxSymbolValue,
unsigned huffLog,
655 unsigned singleStream,
656 void* workSpace,
size_t wkspSize,
657 HUF_CElt* oldHufTable, HUF_repeat*
repeat,
int preferRepeat,
662 BYTE*
const oend = ostart + dstSize;
666 if (((
size_t)workSpace & 3) != 0)
return ERROR(GENERIC);
667 if (wkspSize <
sizeof(*
table))
return ERROR(workSpace_tooSmall);
668 if (!srcSize)
return 0;
669 if (!dstSize)
return 0;
671 if (huffLog > HUF_TABLELOG_MAX)
return ERROR(tableLog_tooLarge);
672 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX)
return ERROR(maxSymbolValue_tooLarge);
673 if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX;
674 if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT;
677 if (preferRepeat &&
repeat && *
repeat == HUF_repeat_valid) {
680 singleStream, oldHufTable, bmi2);
685 if (largest == srcSize) { *ostart = ((
const BYTE*)
src)[0];
return 1; }
686 if (largest <= (srcSize >> 7)+4)
return 0;
691 && *
repeat == HUF_repeat_check
693 *
repeat = HUF_repeat_none;
696 if (preferRepeat &&
repeat && *
repeat != HUF_repeat_none) {
699 singleStream, oldHufTable, bmi2);
705 maxSymbolValue, huffLog,
706 table->nodeTable,
sizeof(
table->nodeTable)) );
707 huffLog = (
U32)maxBits;
710 sizeof(
table->CTable) - ((maxSymbolValue + 1) *
sizeof(HUF_CElt)));
719 if (oldSize <= hSize + newSize || hSize + 12 >= srcSize) {
722 singleStream, oldHufTable, bmi2);
726 if (hSize + 12ul >= srcSize) {
return 0; }
734 singleStream,
table->CTable, bmi2);
739 const void*
src,
size_t srcSize,
740 unsigned maxSymbolValue,
unsigned huffLog,
741 void* workSpace,
size_t wkspSize)
744 maxSymbolValue, huffLog, 1 ,
750 const void*
src,
size_t srcSize,
751 unsigned maxSymbolValue,
unsigned huffLog,
752 void* workSpace,
size_t wkspSize,
753 HUF_CElt* hufTable, HUF_repeat*
repeat,
int preferRepeat,
int bmi2)
756 maxSymbolValue, huffLog, 1 ,
757 workSpace, wkspSize, hufTable,
758 repeat, preferRepeat, bmi2);
762 const void*
src,
size_t srcSize,
763 unsigned maxSymbolValue,
unsigned huffLog)
782 const void*
src,
size_t srcSize,
783 unsigned maxSymbolValue,
unsigned huffLog,
784 void* workSpace,
size_t wkspSize)
787 maxSymbolValue, huffLog, 0 ,
796 const void*
src,
size_t srcSize,
797 unsigned maxSymbolValue,
unsigned huffLog,
798 void* workSpace,
size_t wkspSize,
799 HUF_CElt* hufTable, HUF_repeat*
repeat,
int preferRepeat,
int bmi2)
802 maxSymbolValue, huffLog, 0 ,
804 hufTable,
repeat, preferRepeat, bmi2);
808 const void*
src,
size_t srcSize,
809 unsigned maxSymbolValue,
unsigned huffLog)
FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
MEM_STATIC void MEM_writeLE16(void *memPtr, U16 val)
size_t HUF_compress1X_repeat(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize, HUF_CElt *hufTable, HUF_repeat *repeat, int preferRepeat, int bmi2)
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
#define HUF_FLUSHBITS_2(stream)
FSE_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue)
FORCE_INLINE_TEMPLATE size_t HUF_compress1X_usingCTable_internal_body(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
GLubyte GLubyte GLubyte GLubyte w
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
size_t HUF_writeCTable(void *dst, size_t maxDstSize, const HUF_CElt *CTable, U32 maxSymbolValue, U32 huffLog)
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
#define HUF_WORKSPACE_SIZE_U32
#define TARGET_ATTRIBUTE(target)
GLdouble GLdouble GLdouble r
#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER
GLuint GLuint GLsizei count
static size_t HUF_compress1X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, const int bmi2)
static void HUF_sort(nodeElt *huffNode, const U32 *count, U32 maxSymbolValue)
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
size_t HUF_compress4X_wksp(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
size_t HUF_buildCTable_wksp(HUF_CElt *tree, const U32 *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
size_t HUF_buildCTable(HUF_CElt *tree, const U32 *count, U32 maxSymbolValue, U32 maxNbBits)
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, unsigned singleStream, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
MEM_STATIC unsigned BIT_highbit32(U32 val)
unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
FSE_PUBLIC_API size_t FSE_compress_usingCTable(void *dst, size_t dstCapacity, const void *src, size_t srcSize, const FSE_CTable *ct)
#define HUF_BLOCKSIZE_MAX
size_t HUF_compressBound(size_t size)
size_t HUF_compress4X_repeat(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize, HUF_CElt *hufTable, HUF_repeat *repeat, int preferRepeat, int bmi2)
static size_t HUF_estimateCompressedSize(HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
FORCE_INLINE_TEMPLATE void HUF_encodeSymbol(BIT_CStream_t *bitCPtr, U32 symbol, const HUF_CElt *CTable)
size_t HUF_compress1X(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
#define ExAllocatePoolWithTag(hernya, size, tag)
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
static size_t HUF_compress4X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int bmi2)
nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]
size_t HUF_readCTable(HUF_CElt *CTable, U32 *maxSymbolValuePtr, const void *src, size_t srcSize)
#define memcpy(s1, s2, n)
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
size_t HUF_compress1X_wksp(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
#define HUF_FLUSHBITS_1(stream)
size_t HUF_compress1X_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
static size_t HUF_compressWeights(void *dst, size_t dstSize, const void *weightTable, size_t wtSize)
static int HUF_validateCTable(const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
size_t HUF_compress(void *dst, size_t maxDstSize, const void *src, size_t srcSize)
size_t HUF_compress4X_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
FSE_PUBLIC_API size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
U32 HUF_getNbBits(const void *symbolTable, U32 symbolValue)
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
static U32 HUF_setMaxHeight(nodeElt *huffNode, U32 lastNonNull, U32 maxNbBits)
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
size_t HUF_compress2(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
struct task_struct * current
#define FORCE_INLINE_TEMPLATE
size_t HUF_readStats(BYTE *huffWeight, size_t hwSize, U32 *rankStats, U32 *nbSymbolsPtr, U32 *tableLogPtr, const void *src, size_t srcSize)
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
static size_t HUF_compressCTable_internal(BYTE *const ostart, BYTE *op, BYTE *const oend, const void *src, size_t srcSize, unsigned singleStream, const HUF_CElt *CTable, const int bmi2)