ReactOS  0.4.15-dev-4927-gfe8f806
fse_compress.c
Go to the documentation of this file.
1 /* ******************************************************************
2  * FSE : Finite State Entropy encoder
3  * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
4  *
5  * You can contact the author at :
6  * - FSE 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 * Includes
17 ****************************************************************/
18 #include <stdlib.h> /* malloc, free, qsort */
19 #include <string.h> /* memcpy, memset */
20 #include "compiler.h"
21 #include "mem.h" /* U32, U16, etc. */
22 #include "debug.h" /* assert, DEBUGLOG */
23 #include "hist.h" /* HIST_count_wksp */
24 #include "bitstream.h"
25 #define FSE_STATIC_LINKING_ONLY
26 #include "fse.h"
27 #include "error_private.h"
28 #include <ntifs.h>
29 #include <ntddk.h>
30 
31 
32 /* **************************************************************
33 * Error Management
34 ****************************************************************/
35 #define FSE_isError ERR_isError
36 
37 
38 /* **************************************************************
39 * Templates
40 ****************************************************************/
41 /*
42  designed to be included
43  for type-specific functions (template emulation in C)
44  Objective is to write these functions only once, for improved maintenance
45 */
46 
47 /* safety checks */
48 #ifndef FSE_FUNCTION_EXTENSION
49 # error "FSE_FUNCTION_EXTENSION must be defined"
50 #endif
51 #ifndef FSE_FUNCTION_TYPE
52 # error "FSE_FUNCTION_TYPE must be defined"
53 #endif
54 
55 /* Function names */
56 #define FSE_CAT(X,Y) X##Y
57 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
58 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
59 
60 #define FSEC_ALLOC_TAG 0x64455346 // "FSEc"
61 
62 /* Function templates */
63 
64 /* FSE_buildCTable_wksp() :
65  * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
66  * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)`
67  * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements
68  */
70  const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
71  void* workSpace, size_t wkspSize)
72 {
73  U32 const tableSize = 1 << tableLog;
74  U32 const tableMask = tableSize - 1;
75  void* const ptr = ct;
76  U16* const tableU16 = ( (U16*) ptr) + 2;
77  void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ;
78  FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
79  U32 const step = FSE_TABLESTEP(tableSize);
80  U32 cumul[FSE_MAX_SYMBOL_VALUE+2];
81 
82  FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace;
83  U32 highThreshold = tableSize-1;
84 
85  /* CTable header */
86  if (((size_t)1 << tableLog) * sizeof(FSE_FUNCTION_TYPE) > wkspSize) return ERROR(tableLog_tooLarge);
87  tableU16[-2] = (U16) tableLog;
88  tableU16[-1] = (U16) maxSymbolValue;
89  assert(tableLog < 16); /* required for threshold strategy to work */
90 
91  /* For explanations on how to distribute symbol values over the table :
92  * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
93 
94  #ifdef __clang_analyzer__
95  memset(tableSymbol, 0, sizeof(*tableSymbol) * tableSize); /* useless initialization, just to keep scan-build happy */
96  #endif
97 
98  /* symbol start positions */
99  { U32 u;
100  cumul[0] = 0;
101  for (u=1; u <= maxSymbolValue+1; u++) {
102  if (normalizedCounter[u-1]==-1) { /* Low proba symbol */
103  cumul[u] = cumul[u-1] + 1;
104  tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
105  } else {
106  cumul[u] = cumul[u-1] + normalizedCounter[u-1];
107  } }
108  cumul[maxSymbolValue+1] = tableSize+1;
109  }
110 
111  /* Spread symbols */
112  { U32 position = 0;
113  U32 symbol;
114  for (symbol=0; symbol<=maxSymbolValue; symbol++) {
115  int nbOccurrences;
116  int const freq = normalizedCounter[symbol];
117  for (nbOccurrences=0; nbOccurrences<freq; nbOccurrences++) {
118  tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
119  position = (position + step) & tableMask;
120  while (position > highThreshold)
121  position = (position + step) & tableMask; /* Low proba area */
122  } }
123 
124  assert(position==0); /* Must have initialized all positions */
125  }
126 
127  /* Build table */
128  { U32 u; for (u=0; u<tableSize; u++) {
129  FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */
130  tableU16[cumul[s]++] = (U16) (tableSize+u); /* TableU16 : sorted by symbol order; gives next state value */
131  } }
132 
133  /* Build Symbol Transformation Table */
134  { unsigned total = 0;
135  unsigned s;
136  for (s=0; s<=maxSymbolValue; s++) {
137  switch (normalizedCounter[s])
138  {
139  case 0:
140  /* filling nonetheless, for compatibility with FSE_getMaxNbBits() */
141  symbolTT[s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog);
142  break;
143 
144  case -1:
145  case 1:
146  symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
147  symbolTT[s].deltaFindState = total - 1;
148  total ++;
149  break;
150  default :
151  {
152  U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1);
153  U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
154  symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
155  symbolTT[s].deltaFindState = total - normalizedCounter[s];
156  total += normalizedCounter[s];
157  } } } }
158 
159 #if 0 /* debug : symbol costs */
160  DEBUGLOG(5, "\n --- table statistics : ");
161  { U32 symbol;
162  for (symbol=0; symbol<=maxSymbolValue; symbol++) {
163  DEBUGLOG(5, "%3u: w=%3i, maxBits=%u, fracBits=%.2f",
164  symbol, normalizedCounter[symbol],
165  FSE_getMaxNbBits(symbolTT, symbol),
166  (double)FSE_bitCost(symbolTT, tableLog, symbol, 8) / 256);
167  }
168  }
169 #endif
170 
171  return 0;
172 }
173 
174 
175 size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
176 {
177  FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */
178  return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(tableSymbol));
179 }
180 
181 
182 
183 #ifndef FSE_COMMONDEFS_ONLY
184 
185 
186 /*-**************************************************************
187 * FSE NCount encoding
188 ****************************************************************/
189 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
190 {
191  size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
192  return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
193 }
194 
195 static size_t
196 FSE_writeNCount_generic (void* header, size_t headerBufferSize,
197  const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
198  unsigned writeIsSafe)
199 {
200  BYTE* const ostart = (BYTE*) header;
201  BYTE* out = ostart;
202  BYTE* const oend = ostart + headerBufferSize;
203  int nbBits;
204  const int tableSize = 1 << tableLog;
205  int remaining;
206  int threshold;
207  U32 bitStream = 0;
208  int bitCount = 0;
209  unsigned symbol = 0;
210  unsigned const alphabetSize = maxSymbolValue + 1;
211  int previousIs0 = 0;
212 
213  /* Table Size */
214  bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
215  bitCount += 4;
216 
217  /* Init */
218  remaining = tableSize+1; /* +1 for extra accuracy */
219  threshold = tableSize;
220  nbBits = tableLog+1;
221 
222  while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */
223  if (previousIs0) {
224  unsigned start = symbol;
225  while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
226  if (symbol == alphabetSize) break; /* incorrect distribution */
227  while (symbol >= start+24) {
228  start+=24;
229  bitStream += 0xFFFFU << bitCount;
230  if ((!writeIsSafe) && (out > oend-2))
231  return ERROR(dstSize_tooSmall); /* Buffer overflow */
232  out[0] = (BYTE) bitStream;
233  out[1] = (BYTE)(bitStream>>8);
234  out+=2;
235  bitStream>>=16;
236  }
237  while (symbol >= start+3) {
238  start+=3;
239  bitStream += 3 << bitCount;
240  bitCount += 2;
241  }
242  bitStream += (symbol-start) << bitCount;
243  bitCount += 2;
244  if (bitCount>16) {
245  if ((!writeIsSafe) && (out > oend - 2))
246  return ERROR(dstSize_tooSmall); /* Buffer overflow */
247  out[0] = (BYTE)bitStream;
248  out[1] = (BYTE)(bitStream>>8);
249  out += 2;
250  bitStream >>= 16;
251  bitCount -= 16;
252  } }
253  { int count = normalizedCounter[symbol++];
254  int const max = (2*threshold-1) - remaining;
255  remaining -= count < 0 ? -count : count;
256  count++; /* +1 for extra accuracy */
257  if (count>=threshold)
258  count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
259  bitStream += count << bitCount;
260  bitCount += nbBits;
261  bitCount -= (count<max);
262  previousIs0 = (count==1);
263  if (remaining<1) return ERROR(GENERIC);
264  while (remaining<threshold) { nbBits--; threshold>>=1; }
265  }
266  if (bitCount>16) {
267  if ((!writeIsSafe) && (out > oend - 2))
268  return ERROR(dstSize_tooSmall); /* Buffer overflow */
269  out[0] = (BYTE)bitStream;
270  out[1] = (BYTE)(bitStream>>8);
271  out += 2;
272  bitStream >>= 16;
273  bitCount -= 16;
274  } }
275 
276  if (remaining != 1)
277  return ERROR(GENERIC); /* incorrect normalized distribution */
278  assert(symbol <= alphabetSize);
279 
280  /* flush remaining bitStream */
281  if ((!writeIsSafe) && (out > oend - 2))
282  return ERROR(dstSize_tooSmall); /* Buffer overflow */
283  out[0] = (BYTE)bitStream;
284  out[1] = (BYTE)(bitStream>>8);
285  out+= (bitCount+7) /8;
286 
287  return (out-ostart);
288 }
289 
290 
291 size_t FSE_writeNCount (void* buffer, size_t bufferSize,
292  const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
293 {
294  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */
295  if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */
296 
297  if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
298  return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
299 
300  return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
301 }
302 
303 
304 /*-**************************************************************
305 * FSE Compression Code
306 ****************************************************************/
307 
308 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
309 {
310  size_t size;
311  if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
312  size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
314 }
315 
317 
318 /* provides the minimum logSize to safely represent a distribution */
319 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
320 {
321  U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1;
322  U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
323  U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
324  assert(srcSize > 1); /* Not supported, RLE should be used instead */
325  return minBits;
326 }
327 
328 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
329 {
330  U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
331  U32 tableLog = maxTableLog;
332  U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
333  assert(srcSize > 1); /* Not supported, RLE should be used instead */
334  if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
335  if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */
336  if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
337  if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
338  if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
339  return tableLog;
340 }
341 
342 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
343 {
344  return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
345 }
346 
347 
348 /* Secondary normalization method.
349  To be used when primary method fails. */
350 
351 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue)
352 {
353  short const NOT_YET_ASSIGNED = -2;
354  U32 s;
355  U32 distributed = 0;
356  U32 ToDistribute;
357 
358  /* Init */
359  U32 const lowThreshold = (U32)(total >> tableLog);
360  U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
361 
362  for (s=0; s<=maxSymbolValue; s++) {
363  if (count[s] == 0) {
364  norm[s]=0;
365  continue;
366  }
367  if (count[s] <= lowThreshold) {
368  norm[s] = -1;
369  distributed++;
370  total -= count[s];
371  continue;
372  }
373  if (count[s] <= lowOne) {
374  norm[s] = 1;
375  distributed++;
376  total -= count[s];
377  continue;
378  }
379 
380  norm[s]=NOT_YET_ASSIGNED;
381  }
382  ToDistribute = (1 << tableLog) - distributed;
383 
384  if (ToDistribute == 0)
385  return 0;
386 
387  if ((total / ToDistribute) > lowOne) {
388  /* risk of rounding to zero */
389  lowOne = (U32)((total * 3) / (ToDistribute * 2));
390  for (s=0; s<=maxSymbolValue; s++) {
391  if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
392  norm[s] = 1;
393  distributed++;
394  total -= count[s];
395  continue;
396  } }
397  ToDistribute = (1 << tableLog) - distributed;
398  }
399 
400  if (distributed == maxSymbolValue+1) {
401  /* all values are pretty poor;
402  probably incompressible data (should have already been detected);
403  find max, then give all remaining points to max */
404  U32 maxV = 0, maxC = 0;
405  for (s=0; s<=maxSymbolValue; s++)
406  if (count[s] > maxC) { maxV=s; maxC=count[s]; }
407  norm[maxV] += (short)ToDistribute;
408  return 0;
409  }
410 
411  if (total == 0) {
412  /* all of the symbols were low enough for the lowOne or lowThreshold */
413  for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
414  if (norm[s] > 0) { ToDistribute--; norm[s]++; }
415  return 0;
416  }
417 
418  { U64 const vStepLog = 62 - tableLog;
419  U64 const mid = (1ULL << (vStepLog-1)) - 1;
420  U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */
421  U64 tmpTotal = mid;
422  for (s=0; s<=maxSymbolValue; s++) {
423  if (norm[s]==NOT_YET_ASSIGNED) {
424  U64 const end = tmpTotal + (count[s] * rStep);
425  U32 const sStart = (U32)(tmpTotal >> vStepLog);
426  U32 const sEnd = (U32)(end >> vStepLog);
427  U32 const weight = sEnd - sStart;
428  if (weight < 1)
429  return ERROR(GENERIC);
430  norm[s] = (short)weight;
431  tmpTotal = end;
432  } } }
433 
434  return 0;
435 }
436 
437 
438 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
439  const unsigned* count, size_t total,
440  unsigned maxSymbolValue)
441 {
442  /* Sanity checks */
443  if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
444  if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */
445  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */
446  if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
447 
448  { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
449  U64 const scale = 62 - tableLog;
450  U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */
451  U64 const vStep = 1ULL<<(scale-20);
452  int stillToDistribute = 1<<tableLog;
453  unsigned s;
454  unsigned largest=0;
455  short largestP=0;
456  U32 lowThreshold = (U32)(total >> tableLog);
457 
458  for (s=0; s<=maxSymbolValue; s++) {
459  if (count[s] == total) return 0; /* rle special case */
460  if (count[s] == 0) { normalizedCounter[s]=0; continue; }
461  if (count[s] <= lowThreshold) {
462  normalizedCounter[s] = -1;
463  stillToDistribute--;
464  } else {
465  short proba = (short)((count[s]*step) >> scale);
466  if (proba<8) {
467  U64 restToBeat = vStep * rtbTable[proba];
468  proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
469  }
470  if (proba > largestP) { largestP=proba; largest=s; }
471  normalizedCounter[s] = proba;
472  stillToDistribute -= proba;
473  } }
474  if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
475  /* corner case, need another normalization method */
476  size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
477  if (FSE_isError(errorCode)) return errorCode;
478  }
479  else normalizedCounter[largest] += (short)stillToDistribute;
480  }
481 
482 #if 0
483  { /* Print Table (debug) */
484  U32 s;
485  U32 nTotal = 0;
486  for (s=0; s<=maxSymbolValue; s++)
487  RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
488  for (s=0; s<=maxSymbolValue; s++)
489  nTotal += abs(normalizedCounter[s]);
490  if (nTotal != (1U<<tableLog))
491  RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
492  getchar();
493  }
494 #endif
495 
496  return tableLog;
497 }
498 
499 
500 /* fake FSE_CTable, for raw (uncompressed) input */
501 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits)
502 {
503  const unsigned tableSize = 1 << nbBits;
504  const unsigned tableMask = tableSize - 1;
505  const unsigned maxSymbolValue = tableMask;
506  void* const ptr = ct;
507  U16* const tableU16 = ( (U16*) ptr) + 2;
508  void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1); /* assumption : tableLog >= 1 */
509  FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
510  unsigned s;
511 
512  /* Sanity checks */
513  if (nbBits < 1) return ERROR(GENERIC); /* min size */
514 
515  /* header */
516  tableU16[-2] = (U16) nbBits;
517  tableU16[-1] = (U16) maxSymbolValue;
518 
519  /* Build table */
520  for (s=0; s<tableSize; s++)
521  tableU16[s] = (U16)(tableSize + s);
522 
523  /* Build Symbol Transformation Table */
524  { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
525  for (s=0; s<=maxSymbolValue; s++) {
526  symbolTT[s].deltaNbBits = deltaNbBits;
527  symbolTT[s].deltaFindState = s-1;
528  } }
529 
530  return 0;
531 }
532 
533 /* fake FSE_CTable, for rle input (always same symbol) */
534 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
535 {
536  void* ptr = ct;
537  U16* tableU16 = ( (U16*) ptr) + 2;
538  void* FSCTptr = (U32*)ptr + 2;
539  FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
540 
541  /* header */
542  tableU16[-2] = (U16) 0;
543  tableU16[-1] = (U16) symbolValue;
544 
545  /* Build table */
546  tableU16[0] = 0;
547  tableU16[1] = 0; /* just in case */
548 
549  /* Build Symbol Transformation Table */
550  symbolTT[symbolValue].deltaNbBits = 0;
551  symbolTT[symbolValue].deltaFindState = 0;
552 
553  return 0;
554 }
555 
556 
557 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
558  const void* src, size_t srcSize,
559  const FSE_CTable* ct, const unsigned fast)
560 {
561  const BYTE* const istart = (const BYTE*) src;
562  const BYTE* const iend = istart + srcSize;
563  const BYTE* ip=iend;
564 
565  BIT_CStream_t bitC;
566  FSE_CState_t CState1, CState2;
567 
568  /* init */
569  if (srcSize <= 2) return 0;
570  { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
571  if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
572 
573 #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
574 
575  if (srcSize & 1) {
576  FSE_initCState2(&CState1, ct, *--ip);
577  FSE_initCState2(&CState2, ct, *--ip);
578  FSE_encodeSymbol(&bitC, &CState1, *--ip);
579  FSE_FLUSHBITS(&bitC);
580  } else {
581  FSE_initCState2(&CState2, ct, *--ip);
582  FSE_initCState2(&CState1, ct, *--ip);
583  }
584 
585  /* join to mod 4 */
586  srcSize -= 2;
587  if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */
588  FSE_encodeSymbol(&bitC, &CState2, *--ip);
589  FSE_encodeSymbol(&bitC, &CState1, *--ip);
590  FSE_FLUSHBITS(&bitC);
591  }
592 
593  /* 2 or 4 encoding per loop */
594  while ( ip>istart ) {
595 
596  FSE_encodeSymbol(&bitC, &CState2, *--ip);
597 
598  if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */
599  FSE_FLUSHBITS(&bitC);
600 
601  FSE_encodeSymbol(&bitC, &CState1, *--ip);
602 
603  if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */
604  FSE_encodeSymbol(&bitC, &CState2, *--ip);
605  FSE_encodeSymbol(&bitC, &CState1, *--ip);
606  }
607 
608  FSE_FLUSHBITS(&bitC);
609  }
610 
611  FSE_flushCState(&bitC, &CState2);
612  FSE_flushCState(&bitC, &CState1);
613  return BIT_closeCStream(&bitC);
614 }
615 
616 size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
617  const void* src, size_t srcSize,
618  const FSE_CTable* ct)
619 {
620  unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
621 
622  if (fast)
623  return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
624  else
625  return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
626 }
627 
628 
629 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
630 
631 /* FSE_compress_wksp() :
632  * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`).
633  * `wkspSize` size must be `(1<<tableLog)`.
634  */
635 size_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize)
636 {
637  BYTE* const ostart = (BYTE*) dst;
638  BYTE* op = ostart;
639  BYTE* const oend = ostart + dstSize;
640 
641  unsigned count[FSE_MAX_SYMBOL_VALUE+1];
642  S16 norm[FSE_MAX_SYMBOL_VALUE+1];
643  FSE_CTable* CTable = (FSE_CTable*)workSpace;
644  size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue);
645  void* scratchBuffer = (void*)(CTable + CTableSize);
646  size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable));
647 
648  /* init conditions */
649  if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge);
650  if (srcSize <= 1) return 0; /* Not compressible */
651  if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
652  if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
653 
654  /* Scan input and build symbol stats */
655  { CHECK_V_F(maxCount, HIST_count_wksp(count, &maxSymbolValue, src, srcSize, scratchBuffer, scratchBufferSize) );
656  if (maxCount == srcSize) return 1; /* only a single symbol in src : rle */
657  if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
658  if (maxCount < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */
659  }
660 
661  tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue);
662  CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) );
663 
664  /* Write table description header */
665  { CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) );
666  op += nc_err;
667  }
668 
669  /* Compress */
670  CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) );
671  { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) );
672  if (cSize == 0) return 0; /* not enough space for compressed data */
673  op += cSize;
674  }
675 
676  /* check compressibility */
677  if ( (size_t)(op-ostart) >= srcSize-1 ) return 0;
678 
679  return op-ostart;
680 }
681 
682 typedef struct {
683  FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)];
684  BYTE scratchBuffer[1 << FSE_MAX_TABLELOG];
685 } fseWkspMax_t;
686 
687 size_t FSE_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
688 {
689  fseWkspMax_t scratchBuffer;
690  DEBUG_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */
691  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
692  return FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, &scratchBuffer, sizeof(scratchBuffer));
693 }
694 
695 size_t FSE_compress (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
696 {
697  return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
698 }
699 
700 
701 #endif /* FSE_COMMONDEFS_ONLY */
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
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 abs(i)
Definition: fconv.c:206
#define max(a, b)
Definition: svc.c:63
FSE_CTable * FSE_createCTable(unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:308
#define CHECK_F(f)
Definition: error_private.h:62
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define ERROR(name)
Definition: error_private.h:53
size_t FSE_compressBound(size_t size)
Definition: fse_compress.c:629
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLenum GLenum GLenum GLenum GLenum scale
Definition: glext.h:9032
#define U(x)
Definition: wordpad.c:45
#define CHECK_V_F(e, f)
Definition: error_private.h:61
void FSE_freeCTable(FSE_CTable *ct)
Definition: fse_compress.c:316
#define assert(x)
Definition: debug.h:53
GLuint buffer
Definition: glext.h:5915
unsigned FSE_CTable
Definition: fse.h:160
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
Definition: fse_compress.c:328
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:183
#define DEBUGLOG(l,...)
Definition: debug.h:106
size_t FSE_buildCTable_raw(FSE_CTable *ct, unsigned nbBits)
Definition: fse_compress.c:501
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
#define FSEC_ALLOC_TAG
Definition: fse_compress.c:60
unsigned short(__cdecl typeof(TIFFCurrentDirectory))(struct tiff *)
Definition: typeof.h:94
size_t FSE_compress_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
Definition: fse_compress.c:616
static size_t FSE_normalizeM2(short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
Definition: fse_compress.c:351
#define RAWLOG(l,...)
Definition: debug.h:105
static PVOID ptr
Definition: dispmode.c:27
static size_t FSE_compress_usingCTable_generic(void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct, const unsigned fast)
Definition: fse_compress.c:557
#define FSE_isError
Definition: fse_compress.c:35
size_t bitContainer
Definition: bitstream.h:58
#define DEBUG_STATIC_ASSERT(c)
Definition: debug.h:43
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:166
#define ULL(a, b)
Definition: format_msg.c:27
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:319
size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
Definition: fse_compress.c:534
GLsizeiptr size
Definition: glext.h:5919
Definition: dhcpd.h:61
size_t FSE_buildCTable(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:175
static FILE * out
Definition: regtests2xml.c:44
UINT op
Definition: effect.c:236
size_t FSE_compress2(void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:687
size_t FSE_compress_wksp(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
Definition: fse_compress.c:635
size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:291
GLuint GLuint end
Definition: gl.h:1545
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:342
size_t bufferSize
static size_t FSE_writeNCount_generic(void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, unsigned writeIsSafe)
Definition: fse_compress.c:196
GLdouble s
Definition: gl.h:2039
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194
_Check_return_ _CRTIMP int __cdecl getchar(void)
Definition: file.c:3627
weight
Definition: sortkey.c:156
unsigned long long U64
Definition: xxhash.c:197
GLuint start
Definition: gl.h:1545
GLenum GLenum dst
Definition: glext.h:6340
GLsizei maxCount
Definition: glext.h:6042
#define FSE_FLUSHBITS(s)
size_t total
size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
Definition: fse_compress.c:438
signed short S16
Definition: mem.h:146
#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
size_t FSE_compress(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
Definition: fse_compress.c:695
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:189