ReactOS  0.4.15-dev-5446-g3f3714b
huf_compress.c
Go to the documentation of this file.
1 /* ******************************************************************
2  * Huffman encoder, part of New Generation Entropy library
3  * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
4  *
5  * You can contact the author at :
6  * - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
7  * - Public forum : https://groups.google.com/forum/#!forum/lz4c
8  *
9  * This source code is licensed under both the BSD-style license (found in the
10  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
11  * in the COPYING file in the root directory of this source tree).
12  * You may select, at your option, one of the above-listed licenses.
13 ****************************************************************** */
14 
15 /* **************************************************************
16 * Compiler specifics
17 ****************************************************************/
18 #ifdef _MSC_VER /* Visual Studio */
19 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
20 #endif
21 
22 
23 /* **************************************************************
24 * Includes
25 ****************************************************************/
26 #include <string.h> /* memcpy, memset */
27 #include <stdio.h> /* printf (debug) */
28 #include "compiler.h"
29 #include "bitstream.h"
30 #include "hist.h"
31 #define FSE_STATIC_LINKING_ONLY /* FSE_optimalTableLog_internal */
32 #include "fse.h" /* header compression */
33 #define HUF_STATIC_LINKING_ONLY
34 #include "huf.h"
35 #include "error_private.h"
36 
37 
38 /* **************************************************************
39 * Error Management
40 ****************************************************************/
41 #define HUF_isError ERR_isError
42 #define HUF_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
43 
44 
45 /* **************************************************************
46 * Utils
47 ****************************************************************/
48 unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
49 {
50  return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 1);
51 }
52 
53 
54 /* *******************************************************
55 * HUF : Huffman block compression
56 *********************************************************/
57 /* HUF_compressWeights() :
58  * Same as FSE_compress(), but dedicated to huff0's weights compression.
59  * The use case needs much less stack memory.
60  * Note : all elements within weightTable are supposed to be <= HUF_TABLELOG_MAX.
61  */
62 #define MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6
63 static size_t HUF_compressWeights (void* dst, size_t dstSize, const void* weightTable, size_t wtSize)
64 {
65  BYTE* const ostart = (BYTE*) dst;
66  BYTE* op = ostart;
67  BYTE* const oend = ostart + dstSize;
68 
69  unsigned maxSymbolValue = HUF_TABLELOG_MAX;
71 
72  FSE_CTable CTable[FSE_CTABLE_SIZE_U32(MAX_FSE_TABLELOG_FOR_HUFF_HEADER, HUF_TABLELOG_MAX)];
73  BYTE scratchBuffer[1<<MAX_FSE_TABLELOG_FOR_HUFF_HEADER];
74 
75  unsigned count[HUF_TABLELOG_MAX+1];
76  S16 norm[HUF_TABLELOG_MAX+1];
77 
78  /* init conditions */
79  if (wtSize <= 1) return 0; /* Not compressible */
80 
81  /* Scan input and build symbol stats */
82  { unsigned const maxCount = HIST_count_simple(count, &maxSymbolValue, weightTable, wtSize); /* never fails */
83  if (maxCount == wtSize) return 1; /* only a single symbol in src : rle */
84  if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
85  }
86 
87  tableLog = FSE_optimalTableLog(tableLog, wtSize, maxSymbolValue);
88  CHECK_F( FSE_normalizeCount(norm, tableLog, count, wtSize, maxSymbolValue) );
89 
90  /* Write table description header */
91  { CHECK_V_F(hSize, FSE_writeNCount(op, (size_t)(oend-op), norm, maxSymbolValue, tableLog) );
92  op += hSize;
93  }
94 
95  /* Compress */
96  CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, sizeof(scratchBuffer)) );
97  { CHECK_V_F(cSize, FSE_compress_usingCTable(op, (size_t)(oend - op), weightTable, wtSize, CTable) );
98  if (cSize == 0) return 0; /* not enough space for compressed data */
99  op += cSize;
100  }
101 
102  return (size_t)(op-ostart);
103 }
104 
105 
106 struct HUF_CElt_s {
109 }; /* typedef'd to HUF_CElt within "huf.h" */
110 
114 size_t HUF_writeCTable (void* dst, size_t maxDstSize,
115  const HUF_CElt* CTable, unsigned maxSymbolValue, unsigned huffLog)
116 {
117  BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; /* precomputed conversion table */
118  BYTE huffWeight[HUF_SYMBOLVALUE_MAX];
119  BYTE* op = (BYTE*)dst;
120  U32 n;
121 
122  /* check conditions */
123  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
124 
125  /* convert to weight */
126  bitsToWeight[0] = 0;
127  for (n=1; n<huffLog+1; n++)
128  bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
129  for (n=0; n<maxSymbolValue; n++)
130  huffWeight[n] = bitsToWeight[CTable[n].nbBits];
131 
132  /* attempt weights compression by FSE */
133  { CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, huffWeight, maxSymbolValue) );
134  if ((hSize>1) & (hSize < maxSymbolValue/2)) { /* FSE compressed */
135  op[0] = (BYTE)hSize;
136  return hSize+1;
137  } }
138 
139  /* write raw values as 4-bits (max : 15) */
140  if (maxSymbolValue > (256-128)) return ERROR(GENERIC); /* should not happen : likely means source cannot be compressed */
141  if (((maxSymbolValue+1)/2) + 1 > maxDstSize) return ERROR(dstSize_tooSmall); /* not enough space within dst buffer */
142  op[0] = (BYTE)(128 /*special case*/ + (maxSymbolValue-1));
143  huffWeight[maxSymbolValue] = 0; /* to be sure it doesn't cause msan issue in final combination */
144  for (n=0; n<maxSymbolValue; n+=2)
145  op[(n/2)+1] = (BYTE)((huffWeight[n] << 4) + huffWeight[n+1]);
146  return ((maxSymbolValue+1)/2) + 1;
147 }
148 
149 
150 size_t HUF_readCTable (HUF_CElt* CTable, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize, unsigned* hasZeroWeights)
151 {
152  BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; /* init not required, even though some static analyzer may complain */
153  U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
154  U32 tableLog = 0;
155  U32 nbSymbols = 0;
156 
157  /* get symbol weights */
158  CHECK_V_F(readSize, HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize));
159 
160  /* check result */
161  if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
162  if (nbSymbols > *maxSymbolValuePtr+1) return ERROR(maxSymbolValue_tooSmall);
163 
164  /* Prepare base value per rank */
165  { U32 n, nextRankStart = 0;
166  for (n=1; n<=tableLog; n++) {
167  U32 current = nextRankStart;
168  nextRankStart += (rankVal[n] << (n-1));
169  rankVal[n] = current;
170  } }
171 
172  /* fill nbBits */
173  *hasZeroWeights = 0;
174  { U32 n; for (n=0; n<nbSymbols; n++) {
175  const U32 w = huffWeight[n];
176  *hasZeroWeights |= (w == 0);
177  CTable[n].nbBits = (BYTE)(tableLog + 1 - w) & -(w != 0);
178  } }
179 
180  /* fill val */
181  { U16 nbPerRank[HUF_TABLELOG_MAX+2] = {0}; /* support w=0=>n=tableLog+1 */
182  U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
183  { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[CTable[n].nbBits]++; }
184  /* determine stating value per rank */
185  valPerRank[tableLog+1] = 0; /* for w==0 */
186  { U16 min = 0;
187  U32 n; for (n=tableLog; n>0; n--) { /* start at n=tablelog <-> w=1 */
188  valPerRank[n] = min; /* get starting value within each rank */
189  min += nbPerRank[n];
190  min >>= 1;
191  } }
192  /* assign value within rank, symbol order */
193  { U32 n; for (n=0; n<nbSymbols; n++) CTable[n].val = valPerRank[CTable[n].nbBits]++; }
194  }
195 
196  *maxSymbolValuePtr = nbSymbols - 1;
197  return readSize;
198 }
199 
200 U32 HUF_getNbBits(const void* symbolTable, U32 symbolValue)
201 {
202  const HUF_CElt* table = (const HUF_CElt*)symbolTable;
203  assert(symbolValue <= HUF_SYMBOLVALUE_MAX);
204  return table[symbolValue].nbBits;
205 }
206 
207 
208 typedef struct nodeElt_s {
213 } nodeElt;
214 
215 static U32 HUF_setMaxHeight(nodeElt* huffNode, U32 lastNonNull, U32 maxNbBits)
216 {
217  const U32 largestBits = huffNode[lastNonNull].nbBits;
218  if (largestBits <= maxNbBits) return largestBits; /* early exit : no elt > maxNbBits */
219 
220  /* there are several too large elements (at least >= 2) */
221  { int totalCost = 0;
222  const U32 baseCost = 1 << (largestBits - maxNbBits);
223  int n = (int)lastNonNull;
224 
225  while (huffNode[n].nbBits > maxNbBits) {
226  totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits));
227  huffNode[n].nbBits = (BYTE)maxNbBits;
228  n --;
229  } /* n stops at huffNode[n].nbBits <= maxNbBits */
230  while (huffNode[n].nbBits == maxNbBits) n--; /* n end at index of smallest symbol using < maxNbBits */
231 
232  /* renorm totalCost */
233  totalCost >>= (largestBits - maxNbBits); /* note : totalCost is necessarily a multiple of baseCost */
234 
235  /* repay normalized cost */
236  { U32 const noSymbol = 0xF0F0F0F0;
237  U32 rankLast[HUF_TABLELOG_MAX+2];
238 
239  /* Get pos of last (smallest) symbol per rank */
240  memset(rankLast, 0xF0, sizeof(rankLast));
241  { U32 currentNbBits = maxNbBits;
242  int pos;
243  for (pos=n ; pos >= 0; pos--) {
244  if (huffNode[pos].nbBits >= currentNbBits) continue;
245  currentNbBits = huffNode[pos].nbBits; /* < maxNbBits */
246  rankLast[maxNbBits-currentNbBits] = (U32)pos;
247  } }
248 
249  while (totalCost > 0) {
250  U32 nBitsToDecrease = BIT_highbit32((U32)totalCost) + 1;
251  for ( ; nBitsToDecrease > 1; nBitsToDecrease--) {
252  U32 const highPos = rankLast[nBitsToDecrease];
253  U32 const lowPos = rankLast[nBitsToDecrease-1];
254  if (highPos == noSymbol) continue;
255  if (lowPos == noSymbol) break;
256  { U32 const highTotal = huffNode[highPos].count;
257  U32 const lowTotal = 2 * huffNode[lowPos].count;
258  if (highTotal <= lowTotal) break;
259  } }
260  /* only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !) */
261  /* HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary */
262  while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol))
263  nBitsToDecrease ++;
264  totalCost -= 1 << (nBitsToDecrease-1);
265  if (rankLast[nBitsToDecrease-1] == noSymbol)
266  rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease]; /* this rank is no longer empty */
267  huffNode[rankLast[nBitsToDecrease]].nbBits ++;
268  if (rankLast[nBitsToDecrease] == 0) /* special case, reached largest symbol */
269  rankLast[nBitsToDecrease] = noSymbol;
270  else {
271  rankLast[nBitsToDecrease]--;
272  if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
273  rankLast[nBitsToDecrease] = noSymbol; /* this rank is now empty */
274  } } /* while (totalCost > 0) */
275 
276  while (totalCost < 0) { /* Sometimes, cost correction overshoot */
277  if (rankLast[1] == noSymbol) { /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */
278  while (huffNode[n].nbBits == maxNbBits) n--;
279  huffNode[n+1].nbBits--;
280  assert(n >= 0);
281  rankLast[1] = (U32)(n+1);
282  totalCost++;
283  continue;
284  }
285  huffNode[ rankLast[1] + 1 ].nbBits--;
286  rankLast[1]++;
287  totalCost ++;
288  } } } /* there are several too large elements (at least >= 2) */
289 
290  return maxNbBits;
291 }
292 
293 typedef struct {
296 } rankPos;
297 
298 typedef nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32];
299 
300 #define RANK_POSITION_TABLE_SIZE 32
301 
302 typedef struct {
306 
307 static void HUF_sort(nodeElt* huffNode, const unsigned* count, U32 maxSymbolValue, rankPos* rankPosition)
308 {
309  U32 n;
310 
311  memset(rankPosition, 0, sizeof(*rankPosition) * RANK_POSITION_TABLE_SIZE);
312  for (n=0; n<=maxSymbolValue; n++) {
313  U32 r = BIT_highbit32(count[n] + 1);
314  rankPosition[r].base ++;
315  }
316  for (n=30; n>0; n--) rankPosition[n-1].base += rankPosition[n].base;
317  for (n=0; n<32; n++) rankPosition[n].current = rankPosition[n].base;
318  for (n=0; n<=maxSymbolValue; n++) {
319  U32 const c = count[n];
320  U32 const r = BIT_highbit32(c+1) + 1;
321  U32 pos = rankPosition[r].current++;
322  while ((pos > rankPosition[r].base) && (c > huffNode[pos-1].count)) {
323  huffNode[pos] = huffNode[pos-1];
324  pos--;
325  }
326  huffNode[pos].count = c;
327  huffNode[pos].byte = (BYTE)n;
328  }
329 }
330 
331 
336 #define STARTNODE (HUF_SYMBOLVALUE_MAX+1)
337 
338 size_t HUF_buildCTable_wksp (HUF_CElt* tree, const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
339 {
340  HUF_buildCTable_wksp_tables* const wksp_tables = (HUF_buildCTable_wksp_tables*)workSpace;
341  nodeElt* const huffNode0 = wksp_tables->huffNodeTbl;
342  nodeElt* const huffNode = huffNode0+1;
343  int nonNullRank;
344  int lowS, lowN;
345  int nodeNb = STARTNODE;
346  int n, nodeRoot;
347 
348  /* safety checks */
349  if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
350  if (wkspSize < sizeof(HUF_buildCTable_wksp_tables))
351  return ERROR(workSpace_tooSmall);
352  if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
353  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX)
354  return ERROR(maxSymbolValue_tooLarge);
355  memset(huffNode0, 0, sizeof(huffNodeTable));
356 
357  /* sort, decreasing order */
358  HUF_sort(huffNode, count, maxSymbolValue, wksp_tables->rankPosition);
359 
360  /* init for parents */
361  nonNullRank = (int)maxSymbolValue;
362  while(huffNode[nonNullRank].count == 0) nonNullRank--;
363  lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb;
364  huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count;
365  huffNode[lowS].parent = huffNode[lowS-1].parent = (U16)nodeNb;
366  nodeNb++; lowS-=2;
367  for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30);
368  huffNode0[0].count = (U32)(1U<<31); /* fake entry, strong barrier */
369 
370  /* create parents */
371  while (nodeNb <= nodeRoot) {
372  int const n1 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
373  int const n2 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
374  huffNode[nodeNb].count = huffNode[n1].count + huffNode[n2].count;
375  huffNode[n1].parent = huffNode[n2].parent = (U16)nodeNb;
376  nodeNb++;
377  }
378 
379  /* distribute weights (unlimited tree height) */
380  huffNode[nodeRoot].nbBits = 0;
381  for (n=nodeRoot-1; n>=STARTNODE; n--)
382  huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
383  for (n=0; n<=nonNullRank; n++)
384  huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
385 
386  /* enforce maxTableLog */
387  maxNbBits = HUF_setMaxHeight(huffNode, (U32)nonNullRank, maxNbBits);
388 
389  /* fill result into tree (val, nbBits) */
390  { U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
391  U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
392  int const alphabetSize = (int)(maxSymbolValue + 1);
393  if (maxNbBits > HUF_TABLELOG_MAX) return ERROR(GENERIC); /* check fit into table */
394  for (n=0; n<=nonNullRank; n++)
395  nbPerRank[huffNode[n].nbBits]++;
396  /* determine stating value per rank */
397  { U16 min = 0;
398  for (n=(int)maxNbBits; n>0; n--) {
399  valPerRank[n] = min; /* get starting value within each rank */
400  min += nbPerRank[n];
401  min >>= 1;
402  } }
403  for (n=0; n<alphabetSize; n++)
404  tree[huffNode[n].byte].nbBits = huffNode[n].nbBits; /* push nbBits per symbol, symbol order */
405  for (n=0; n<alphabetSize; n++)
406  tree[n].val = valPerRank[tree[n].nbBits]++; /* assign value within rank, symbol order */
407  }
408 
409  return maxNbBits;
410 }
411 
416 size_t HUF_buildCTable (HUF_CElt* tree, const unsigned* count, unsigned maxSymbolValue, unsigned maxNbBits)
417 {
418  HUF_buildCTable_wksp_tables workspace;
419  return HUF_buildCTable_wksp(tree, count, maxSymbolValue, maxNbBits, &workspace, sizeof(workspace));
420 }
421 
422 size_t HUF_estimateCompressedSize(const HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue)
423 {
424  size_t nbBits = 0;
425  int s;
426  for (s = 0; s <= (int)maxSymbolValue; ++s) {
427  nbBits += CTable[s].nbBits * count[s];
428  }
429  return nbBits >> 3;
430 }
431 
432 int HUF_validateCTable(const HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue) {
433  int bad = 0;
434  int s;
435  for (s = 0; s <= (int)maxSymbolValue; ++s) {
436  bad |= (count[s] != 0) & (CTable[s].nbBits == 0);
437  }
438  return !bad;
439 }
440 
441 size_t HUF_compressBound(size_t size) { return HUF_COMPRESSBOUND(size); }
442 
444 HUF_encodeSymbol(BIT_CStream_t* bitCPtr, U32 symbol, const HUF_CElt* CTable)
445 {
446  BIT_addBitsFast(bitCPtr, CTable[symbol].val, CTable[symbol].nbBits);
447 }
448 
449 #define HUF_FLUSHBITS(s) BIT_flushBits(s)
450 
451 #define HUF_FLUSHBITS_1(stream) \
452  if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*2+7) HUF_FLUSHBITS(stream)
453 
454 #define HUF_FLUSHBITS_2(stream) \
455  if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*4+7) HUF_FLUSHBITS(stream)
456 
459  const void* src, size_t srcSize,
460  const HUF_CElt* CTable)
461 {
462  const BYTE* ip = (const BYTE*) src;
463  BYTE* const ostart = (BYTE*)dst;
464  BYTE* const oend = ostart + dstSize;
465  BYTE* op = ostart;
466  size_t n;
467  BIT_CStream_t bitC;
468 
469  /* init */
470  if (dstSize < 8) return 0; /* not enough space to compress */
471  { size_t const initErr = BIT_initCStream(&bitC, op, (size_t)(oend-op));
472  if (HUF_isError(initErr)) return 0; }
473 
474  n = srcSize & ~3; /* join to mod 4 */
475  switch (srcSize & 3)
476  {
477  case 3 : HUF_encodeSymbol(&bitC, ip[n+ 2], CTable);
478  HUF_FLUSHBITS_2(&bitC);
479  /* fall-through */
480  case 2 : HUF_encodeSymbol(&bitC, ip[n+ 1], CTable);
481  HUF_FLUSHBITS_1(&bitC);
482  /* fall-through */
483  case 1 : HUF_encodeSymbol(&bitC, ip[n+ 0], CTable);
484  HUF_FLUSHBITS(&bitC);
485  /* fall-through */
486  case 0 : /* fall-through */
487  default: break;
488  }
489 
490  for (; n>0; n-=4) { /* note : n&3==0 at this stage */
491  HUF_encodeSymbol(&bitC, ip[n- 1], CTable);
492  HUF_FLUSHBITS_1(&bitC);
493  HUF_encodeSymbol(&bitC, ip[n- 2], CTable);
494  HUF_FLUSHBITS_2(&bitC);
495  HUF_encodeSymbol(&bitC, ip[n- 3], CTable);
496  HUF_FLUSHBITS_1(&bitC);
497  HUF_encodeSymbol(&bitC, ip[n- 4], CTable);
498  HUF_FLUSHBITS(&bitC);
499  }
500 
501  return BIT_closeCStream(&bitC);
502 }
503 
504 #if DYNAMIC_BMI2
505 
506 static TARGET_ATTRIBUTE("bmi2") size_t
507 HUF_compress1X_usingCTable_internal_bmi2(void* dst, size_t dstSize,
508  const void* src, size_t srcSize,
509  const HUF_CElt* CTable)
510 {
511  return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
512 }
513 
514 static size_t
515 HUF_compress1X_usingCTable_internal_default(void* dst, size_t dstSize,
516  const void* src, size_t srcSize,
517  const HUF_CElt* CTable)
518 {
519  return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
520 }
521 
522 static size_t
523 HUF_compress1X_usingCTable_internal(void* dst, size_t dstSize,
524  const void* src, size_t srcSize,
525  const HUF_CElt* CTable, const int bmi2)
526 {
527  if (bmi2) {
528  return HUF_compress1X_usingCTable_internal_bmi2(dst, dstSize, src, srcSize, CTable);
529  }
530  return HUF_compress1X_usingCTable_internal_default(dst, dstSize, src, srcSize, CTable);
531 }
532 
533 #else
534 
535 static size_t
537  const void* src, size_t srcSize,
538  const HUF_CElt* CTable, const int bmi2)
539 {
540  (void)bmi2;
541  return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
542 }
543 
544 #endif
545 
546 size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
547 {
548  return HUF_compress1X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
549 }
550 
551 
552 static size_t
554  const void* src, size_t srcSize,
555  const HUF_CElt* CTable, int bmi2)
556 {
557  size_t const segmentSize = (srcSize+3)/4; /* first 3 segments */
558  const BYTE* ip = (const BYTE*) src;
559  const BYTE* const iend = ip + srcSize;
560  BYTE* const ostart = (BYTE*) dst;
561  BYTE* const oend = ostart + dstSize;
562  BYTE* op = ostart;
563 
564  if (dstSize < 6 + 1 + 1 + 1 + 8) return 0; /* minimum space to compress successfully */
565  if (srcSize < 12) return 0; /* no saving possible : too small input */
566  op += 6; /* jumpTable */
567 
568  assert(op <= oend);
569  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) );
570  if (cSize==0) return 0;
571  assert(cSize <= 65535);
572  MEM_writeLE16(ostart, (U16)cSize);
573  op += cSize;
574  }
575 
576  ip += segmentSize;
577  assert(op <= oend);
578  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) );
579  if (cSize==0) return 0;
580  assert(cSize <= 65535);
581  MEM_writeLE16(ostart+2, (U16)cSize);
582  op += cSize;
583  }
584 
585  ip += segmentSize;
586  assert(op <= oend);
587  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) );
588  if (cSize==0) return 0;
589  assert(cSize <= 65535);
590  MEM_writeLE16(ostart+4, (U16)cSize);
591  op += cSize;
592  }
593 
594  ip += segmentSize;
595  assert(op <= oend);
596  assert(ip <= iend);
597  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, (size_t)(iend-ip), CTable, bmi2) );
598  if (cSize==0) return 0;
599  op += cSize;
600  }
601 
602  return (size_t)(op-ostart);
603 }
604 
605 size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
606 {
607  return HUF_compress4X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
608 }
609 
611 
613  BYTE* const ostart, BYTE* op, BYTE* const oend,
614  const void* src, size_t srcSize,
615  HUF_nbStreams_e nbStreams, const HUF_CElt* CTable, const int bmi2)
616 {
617  size_t const cSize = (nbStreams==HUF_singleStream) ?
618  HUF_compress1X_usingCTable_internal(op, (size_t)(oend - op), src, srcSize, CTable, bmi2) :
619  HUF_compress4X_usingCTable_internal(op, (size_t)(oend - op), src, srcSize, CTable, bmi2);
620  if (HUF_isError(cSize)) { return cSize; }
621  if (cSize==0) { return 0; } /* uncompressible */
622  op += cSize;
623  /* check compressibility */
624  assert(op >= ostart);
625  if ((size_t)(op-ostart) >= srcSize-1) { return 0; }
626  return (size_t)(op-ostart);
627 }
628 
629 typedef struct {
630  unsigned count[HUF_SYMBOLVALUE_MAX + 1];
631  HUF_CElt CTable[HUF_SYMBOLVALUE_MAX + 1];
634 
635 /* HUF_compress_internal() :
636  * `workSpace` must a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */
637 static size_t
638 HUF_compress_internal (void* dst, size_t dstSize,
639  const void* src, size_t srcSize,
640  unsigned maxSymbolValue, unsigned huffLog,
641  HUF_nbStreams_e nbStreams,
642  void* workSpace, size_t wkspSize,
643  HUF_CElt* oldHufTable, HUF_repeat* repeat, int preferRepeat,
644  const int bmi2)
645 {
647  BYTE* const ostart = (BYTE*)dst;
648  BYTE* const oend = ostart + dstSize;
649  BYTE* op = ostart;
650 
652 
653  /* checks & inits */
654  if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
655  if (wkspSize < HUF_WORKSPACE_SIZE) return ERROR(workSpace_tooSmall);
656  if (!srcSize) return 0; /* Uncompressed */
657  if (!dstSize) return 0; /* cannot fit anything within dst budget */
658  if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); /* current block size limit */
659  if (huffLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
660  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
661  if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX;
662  if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT;
663 
664  /* Heuristic : If old table is valid, use it for small inputs */
665  if (preferRepeat && repeat && *repeat == HUF_repeat_valid) {
666  return HUF_compressCTable_internal(ostart, op, oend,
667  src, srcSize,
668  nbStreams, oldHufTable, bmi2);
669  }
670 
671  /* Scan input and build symbol stats */
672  { CHECK_V_F(largest, HIST_count_wksp (table->count, &maxSymbolValue, (const BYTE*)src, srcSize, workSpace, wkspSize) );
673  if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 1; } /* single symbol, rle */
674  if (largest <= (srcSize >> 7)+4) return 0; /* heuristic : probably not compressible enough */
675  }
676 
677  /* Check validity of previous table */
678  if ( repeat
679  && *repeat == HUF_repeat_check
680  && !HUF_validateCTable(oldHufTable, table->count, maxSymbolValue)) {
681  *repeat = HUF_repeat_none;
682  }
683  /* Heuristic : use existing table for small inputs */
684  if (preferRepeat && repeat && *repeat != HUF_repeat_none) {
685  return HUF_compressCTable_internal(ostart, op, oend,
686  src, srcSize,
687  nbStreams, oldHufTable, bmi2);
688  }
689 
690  /* Build Huffman Tree */
691  huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue);
692  { size_t const maxBits = HUF_buildCTable_wksp(table->CTable, table->count,
693  maxSymbolValue, huffLog,
694  &table->buildCTable_wksp, sizeof(table->buildCTable_wksp));
695  CHECK_F(maxBits);
696  huffLog = (U32)maxBits;
697  /* Zero unused symbols in CTable, so we can check it for validity */
698  memset(table->CTable + (maxSymbolValue + 1), 0,
699  sizeof(table->CTable) - ((maxSymbolValue + 1) * sizeof(HUF_CElt)));
700  }
701 
702  /* Write table description header */
703  { CHECK_V_F(hSize, HUF_writeCTable (op, dstSize, table->CTable, maxSymbolValue, huffLog) );
704  /* Check if using previous huffman table is beneficial */
705  if (repeat && *repeat != HUF_repeat_none) {
706  size_t const oldSize = HUF_estimateCompressedSize(oldHufTable, table->count, maxSymbolValue);
707  size_t const newSize = HUF_estimateCompressedSize(table->CTable, table->count, maxSymbolValue);
708  if (oldSize <= hSize + newSize || hSize + 12 >= srcSize) {
709  return HUF_compressCTable_internal(ostart, op, oend,
710  src, srcSize,
711  nbStreams, oldHufTable, bmi2);
712  } }
713 
714  /* Use the new huffman table */
715  if (hSize + 12ul >= srcSize) { return 0; }
716  op += hSize;
717  if (repeat) { *repeat = HUF_repeat_none; }
718  if (oldHufTable)
719  memcpy(oldHufTable, table->CTable, sizeof(table->CTable)); /* Save new table */
720  }
721  return HUF_compressCTable_internal(ostart, op, oend,
722  src, srcSize,
723  nbStreams, table->CTable, bmi2);
724 }
725 
726 
727 size_t HUF_compress1X_wksp (void* dst, size_t dstSize,
728  const void* src, size_t srcSize,
729  unsigned maxSymbolValue, unsigned huffLog,
730  void* workSpace, size_t wkspSize)
731 {
732  return HUF_compress_internal(dst, dstSize, src, srcSize,
733  maxSymbolValue, huffLog, HUF_singleStream,
734  workSpace, wkspSize,
735  NULL, NULL, 0, 0 /*bmi2*/);
736 }
737 
738 size_t HUF_compress1X_repeat (void* dst, size_t dstSize,
739  const void* src, size_t srcSize,
740  unsigned maxSymbolValue, unsigned huffLog,
741  void* workSpace, size_t wkspSize,
742  HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2)
743 {
744  return HUF_compress_internal(dst, dstSize, src, srcSize,
745  maxSymbolValue, huffLog, HUF_singleStream,
746  workSpace, wkspSize, hufTable,
747  repeat, preferRepeat, bmi2);
748 }
749 
750 size_t HUF_compress1X (void* dst, size_t dstSize,
751  const void* src, size_t srcSize,
752  unsigned maxSymbolValue, unsigned huffLog)
753 {
754  unsigned workSpace[HUF_WORKSPACE_SIZE_U32];
755  return HUF_compress1X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace));
756 }
757 
758 /* HUF_compress4X_repeat():
759  * compress input using 4 streams.
760  * provide workspace to generate compression tables */
761 size_t HUF_compress4X_wksp (void* dst, size_t dstSize,
762  const void* src, size_t srcSize,
763  unsigned maxSymbolValue, unsigned huffLog,
764  void* workSpace, size_t wkspSize)
765 {
766  return HUF_compress_internal(dst, dstSize, src, srcSize,
767  maxSymbolValue, huffLog, HUF_fourStreams,
768  workSpace, wkspSize,
769  NULL, NULL, 0, 0 /*bmi2*/);
770 }
771 
772 /* HUF_compress4X_repeat():
773  * compress input using 4 streams.
774  * re-use an existing huffman compression table */
775 size_t HUF_compress4X_repeat (void* dst, size_t dstSize,
776  const void* src, size_t srcSize,
777  unsigned maxSymbolValue, unsigned huffLog,
778  void* workSpace, size_t wkspSize,
779  HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2)
780 {
781  return HUF_compress_internal(dst, dstSize, src, srcSize,
782  maxSymbolValue, huffLog, HUF_fourStreams,
783  workSpace, wkspSize,
784  hufTable, repeat, preferRepeat, bmi2);
785 }
786 
787 size_t HUF_compress2 (void* dst, size_t dstSize,
788  const void* src, size_t srcSize,
789  unsigned maxSymbolValue, unsigned huffLog)
790 {
791  unsigned workSpace[HUF_WORKSPACE_SIZE_U32];
792  return HUF_compress4X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace));
793 }
794 
795 size_t HUF_compress (void* dst, size_t maxDstSize, const void* src, size_t srcSize)
796 {
797  return HUF_compress2(dst, maxDstSize, src, srcSize, 255, HUF_TABLELOG_DEFAULT);
798 }
size_t HUF_buildCTable(HUF_CElt *tree, const unsigned *count, unsigned maxSymbolValue, unsigned maxNbBits)
Definition: huf_compress.c:416
FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:342
MEM_STATIC void MEM_writeLE16(void *memPtr, U16 val)
Definition: mem.h:324
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)
Definition: huf_compress.c:738
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
Definition: fse_compress.c:69
#define HUF_FLUSHBITS_2(stream)
Definition: huf_compress.c:454
FSE_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:438
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)
Definition: huf_compress.c:458
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
#define HUF_isError
Definition: huf_compress.c:41
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
#define CHECK_F(f)
Definition: error_private.h:62
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define HUF_WORKSPACE_SIZE_U32
Definition: huf.h:94
#define TARGET_ATTRIBUTE(target)
Definition: compiler.h:89
U32 current
Definition: huf_compress.c:295
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define ERROR(name)
Definition: error_private.h:53
#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER
Definition: huf_compress.c:62
GLuint GLuint GLsizei count
Definition: gl.h:1545
size_t HUF_buildCTable_wksp(HUF_CElt *tree, const unsigned *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:338
#define U(x)
Definition: wordpad.c:45
#define CHECK_V_F(e, f)
Definition: error_private.h:61
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)
Definition: huf_compress.c:536
GLdouble n
Definition: glext.h:7729
#define assert(x)
Definition: debug.h:53
unsigned FSE_CTable
Definition: fse.h:160
#define HUF_STATIC_ASSERT(c)
Definition: huf_compress.c:42
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
Definition: fse_compress.c:328
size_t HUF_writeCTable(void *dst, size_t maxDstSize, const HUF_CElt *CTable, unsigned maxSymbolValue, unsigned huffLog)
Definition: huf_compress.c:114
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)
Definition: huf_compress.c:761
static void HUF_sort(nodeElt *huffNode, const unsigned *count, U32 maxSymbolValue, rankPos *rankPosition)
Definition: huf_compress.c:307
HUF_nbStreams_e
Definition: huf_compress.c:610
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:183
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: huf_compress.c:48
FSE_PUBLIC_API size_t FSE_compress_usingCTable(void *dst, size_t dstCapacity, const void *src, size_t srcSize, const FSE_CTable *ct)
Definition: fse_compress.c:616
struct nodeElt_s nodeElt
#define HUF_BLOCKSIZE_MAX
Definition: huf.h:72
size_t HUF_readCTable(HUF_CElt *CTable, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize, unsigned *hasZeroWeights)
Definition: huf_compress.c:150
size_t HUF_compressBound(size_t size)
Definition: huf_compress.c:441
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)
Definition: huf_compress.c:775
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:166
FORCE_INLINE_TEMPLATE void HUF_encodeSymbol(BIT_CStream_t *bitCPtr, U32 symbol, const HUF_CElt *CTable)
Definition: huf_compress.c:444
GLuint GLfloat * val
Definition: glext.h:7180
__kernel_size_t size_t
Definition: linux.h:237
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, HUF_nbStreams_e nbStreams, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:638
GLsizeiptr size
Definition: glext.h:5919
Definition: dhcpd.h:61
r parent
Definition: btrfs.c:3010
const GLubyte * c
Definition: glext.h:8905
UINT op
Definition: effect.c:236
int n1
Definition: dwarfget.c:148
struct task_struct * current
Definition: linux.c:32
size_t HUF_compress1X(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
Definition: huf_compress.c:750
#define HUF_FLUSHBITS(s)
Definition: huf_compress.c:449
static size_t HUF_compress4X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int bmi2)
Definition: huf_compress.c:553
nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]
Definition: huf_compress.c:298
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLdouble s
Definition: gl.h:2039
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:29
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)
Definition: huf_compress.c:727
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
#define HUF_FLUSHBITS_1(stream)
Definition: huf_compress.c:451
static int repeat
Definition: xmllint.c:137
size_t HUF_compress1X_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
Definition: huf_compress.c:546
unsigned short U16
Definition: xxhash.c:194
static size_t HUF_compressWeights(void *dst, size_t dstSize, const void *weightTable, size_t wtSize)
Definition: huf_compress.c:63
rankPos rankPosition[RANK_POSITION_TABLE_SIZE]
Definition: huf_compress.c:304
int n2
Definition: dwarfget.c:148
GLenum GLenum dst
Definition: glext.h:6340
GLsizei maxCount
Definition: glext.h:6042
int HUF_validateCTable(const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
Definition: huf_compress.c:432
size_t HUF_compress(void *dst, size_t maxDstSize, const void *src, size_t srcSize)
Definition: huf_compress.c:795
size_t HUF_compress4X_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
Definition: huf_compress.c:605
#define min(a, b)
Definition: monoChain.cc:55
#define NULL
Definition: types.h:112
FSE_PUBLIC_API size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:291
HUF_buildCTable_wksp_tables buildCTable_wksp
Definition: huf_compress.c:632
signed short S16
Definition: mem.h:146
U32 HUF_getNbBits(const void *symbolTable, U32 symbolValue)
Definition: huf_compress.c:200
#define HUF_WORKSPACE_SIZE
Definition: huf.h:93
#define c
Definition: ke_i.h:80
#define const
Definition: zconf.h:230
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:211
static U32 HUF_setMaxHeight(nodeElt *huffNode, U32 lastNonNull, U32 maxNbBits)
Definition: huf_compress.c:215
static size_t HUF_compressCTable_internal(BYTE *const ostart, BYTE *op, BYTE *const oend, const void *src, size_t srcSize, HUF_nbStreams_e nbStreams, const HUF_CElt *CTable, const int bmi2)
Definition: huf_compress.c:612
#define memset(x, y, z)
Definition: compat.h:39
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:254
unsigned int U32
Definition: xxhash.c:195
#define RANK_POSITION_TABLE_SIZE
Definition: huf_compress.c:300
size_t HUF_compress2(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
Definition: huf_compress.c:787
size_t HUF_estimateCompressedSize(const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
Definition: huf_compress.c:422
#define STARTNODE
Definition: huf_compress.c:336
#define FORCE_INLINE_TEMPLATE
Definition: xxhash.c:172
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 *
Definition: typeof.h:31