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