ReactOS  0.4.14-dev-115-g4576127
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 = ExAllocatePoolWithTag(NonPagedPool, sizeof(FSE_FUNCTION_TYPE) * FSE_MAX_TABLESIZE, FSEC_ALLOC_TAG);
198  size_t ret;
199 
200  if (!tableSymbol)
201  return 0;
202 
203  ret = FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(FSE_FUNCTION_TYPE) * FSE_MAX_TABLESIZE);
204 
205  ExFreePool(tableSymbol);
206 
207  return ret;
208 }
209 
210 
211 
212 #ifndef FSE_COMMONDEFS_ONLY
213 
214 
215 /*-**************************************************************
216 * FSE NCount encoding
217 ****************************************************************/
218 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
219 {
220  size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
221  return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
222 }
223 
224 static size_t
225 FSE_writeNCount_generic (void* header, size_t headerBufferSize,
226  const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
227  unsigned writeIsSafe)
228 {
229  BYTE* const ostart = (BYTE*) header;
230  BYTE* out = ostart;
231  BYTE* const oend = ostart + headerBufferSize;
232  int nbBits;
233  const int tableSize = 1 << tableLog;
234  int remaining;
235  int threshold;
236  U32 bitStream = 0;
237  int bitCount = 0;
238  unsigned symbol = 0;
239  unsigned const alphabetSize = maxSymbolValue + 1;
240  int previousIs0 = 0;
241 
242  /* Table Size */
243  bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
244  bitCount += 4;
245 
246  /* Init */
247  remaining = tableSize+1; /* +1 for extra accuracy */
248  threshold = tableSize;
249  nbBits = tableLog+1;
250 
251  while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */
252  if (previousIs0) {
253  unsigned start = symbol;
254  while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
255  if (symbol == alphabetSize) break; /* incorrect distribution */
256  while (symbol >= start+24) {
257  start+=24;
258  bitStream += 0xFFFFU << bitCount;
259  if ((!writeIsSafe) && (out > oend-2))
260  return ERROR(dstSize_tooSmall); /* Buffer overflow */
261  out[0] = (BYTE) bitStream;
262  out[1] = (BYTE)(bitStream>>8);
263  out+=2;
264  bitStream>>=16;
265  }
266  while (symbol >= start+3) {
267  start+=3;
268  bitStream += 3 << bitCount;
269  bitCount += 2;
270  }
271  bitStream += (symbol-start) << bitCount;
272  bitCount += 2;
273  if (bitCount>16) {
274  if ((!writeIsSafe) && (out > oend - 2))
275  return ERROR(dstSize_tooSmall); /* Buffer overflow */
276  out[0] = (BYTE)bitStream;
277  out[1] = (BYTE)(bitStream>>8);
278  out += 2;
279  bitStream >>= 16;
280  bitCount -= 16;
281  } }
282  { int count = normalizedCounter[symbol++];
283  int const max = (2*threshold-1) - remaining;
284  remaining -= count < 0 ? -count : count;
285  count++; /* +1 for extra accuracy */
286  if (count>=threshold)
287  count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
288  bitStream += count << bitCount;
289  bitCount += nbBits;
290  bitCount -= (count<max);
291  previousIs0 = (count==1);
292  if (remaining<1) return ERROR(GENERIC);
293  while (remaining<threshold) { nbBits--; threshold>>=1; }
294  }
295  if (bitCount>16) {
296  if ((!writeIsSafe) && (out > oend - 2))
297  return ERROR(dstSize_tooSmall); /* Buffer overflow */
298  out[0] = (BYTE)bitStream;
299  out[1] = (BYTE)(bitStream>>8);
300  out += 2;
301  bitStream >>= 16;
302  bitCount -= 16;
303  } }
304 
305  if (remaining != 1)
306  return ERROR(GENERIC); /* incorrect normalized distribution */
307  assert(symbol <= alphabetSize);
308 
309  /* flush remaining bitStream */
310  if ((!writeIsSafe) && (out > oend - 2))
311  return ERROR(dstSize_tooSmall); /* Buffer overflow */
312  out[0] = (BYTE)bitStream;
313  out[1] = (BYTE)(bitStream>>8);
314  out+= (bitCount+7) /8;
315 
316  return (out-ostart);
317 }
318 
319 
320 size_t FSE_writeNCount (void* buffer, size_t bufferSize,
321  const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
322 {
323  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */
324  if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */
325 
326  if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
327  return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
328 
329  return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
330 }
331 
332 
333 /*-**************************************************************
334 * FSE Compression Code
335 ****************************************************************/
336 
337 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
338 {
339  size_t size;
340  if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
341  size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
343 }
344 
346 
347 /* provides the minimum logSize to safely represent a distribution */
348 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
349 {
350  U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1;
351  U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
352  U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
353  assert(srcSize > 1); /* Not supported, RLE should be used instead */
354  return minBits;
355 }
356 
357 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
358 {
359  U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
360  U32 tableLog = maxTableLog;
361  U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
362  assert(srcSize > 1); /* Not supported, RLE should be used instead */
363  if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
364  if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */
365  if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
366  if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
367  if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
368  return tableLog;
369 }
370 
371 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
372 {
373  return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
374 }
375 
376 
377 /* Secondary normalization method.
378  To be used when primary method fails. */
379 
380 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue)
381 {
382  short const NOT_YET_ASSIGNED = -2;
383  U32 s;
384  U32 distributed = 0;
385  U32 ToDistribute;
386 
387  /* Init */
388  U32 const lowThreshold = (U32)(total >> tableLog);
389  U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
390 
391  for (s=0; s<=maxSymbolValue; s++) {
392  if (count[s] == 0) {
393  norm[s]=0;
394  continue;
395  }
396  if (count[s] <= lowThreshold) {
397  norm[s] = -1;
398  distributed++;
399  total -= count[s];
400  continue;
401  }
402  if (count[s] <= lowOne) {
403  norm[s] = 1;
404  distributed++;
405  total -= count[s];
406  continue;
407  }
408 
409  norm[s]=NOT_YET_ASSIGNED;
410  }
411  ToDistribute = (1 << tableLog) - distributed;
412 
413  if (ToDistribute == 0)
414  return 0;
415 
416  if ((total / ToDistribute) > lowOne) {
417  /* risk of rounding to zero */
418  lowOne = (U32)((total * 3) / (ToDistribute * 2));
419  for (s=0; s<=maxSymbolValue; s++) {
420  if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
421  norm[s] = 1;
422  distributed++;
423  total -= count[s];
424  continue;
425  } }
426  ToDistribute = (1 << tableLog) - distributed;
427  }
428 
429  if (distributed == maxSymbolValue+1) {
430  /* all values are pretty poor;
431  probably incompressible data (should have already been detected);
432  find max, then give all remaining points to max */
433  U32 maxV = 0, maxC = 0;
434  for (s=0; s<=maxSymbolValue; s++)
435  if (count[s] > maxC) { maxV=s; maxC=count[s]; }
436  norm[maxV] += (short)ToDistribute;
437  return 0;
438  }
439 
440  if (total == 0) {
441  /* all of the symbols were low enough for the lowOne or lowThreshold */
442  for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
443  if (norm[s] > 0) { ToDistribute--; norm[s]++; }
444  return 0;
445  }
446 
447  { U64 const vStepLog = 62 - tableLog;
448  U64 const mid = (1ULL << (vStepLog-1)) - 1;
449  U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */
450  U64 tmpTotal = mid;
451  for (s=0; s<=maxSymbolValue; s++) {
452  if (norm[s]==NOT_YET_ASSIGNED) {
453  U64 const end = tmpTotal + (count[s] * rStep);
454  U32 const sStart = (U32)(tmpTotal >> vStepLog);
455  U32 const sEnd = (U32)(end >> vStepLog);
456  U32 const weight = sEnd - sStart;
457  if (weight < 1)
458  return ERROR(GENERIC);
459  norm[s] = (short)weight;
460  tmpTotal = end;
461  } } }
462 
463  return 0;
464 }
465 
466 
467 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
468  const unsigned* count, size_t total,
469  unsigned maxSymbolValue)
470 {
471  /* Sanity checks */
472  if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
473  if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */
474  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */
475  if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
476 
477  { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
478  U64 const scale = 62 - tableLog;
479  U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */
480  U64 const vStep = 1ULL<<(scale-20);
481  int stillToDistribute = 1<<tableLog;
482  unsigned s;
483  unsigned largest=0;
484  short largestP=0;
485  U32 lowThreshold = (U32)(total >> tableLog);
486 
487  for (s=0; s<=maxSymbolValue; s++) {
488  if (count[s] == total) return 0; /* rle special case */
489  if (count[s] == 0) { normalizedCounter[s]=0; continue; }
490  if (count[s] <= lowThreshold) {
491  normalizedCounter[s] = -1;
492  stillToDistribute--;
493  } else {
494  short proba = (short)((count[s]*step) >> scale);
495  if (proba<8) {
496  U64 restToBeat = vStep * rtbTable[proba];
497  proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
498  }
499  if (proba > largestP) { largestP=proba; largest=s; }
500  normalizedCounter[s] = proba;
501  stillToDistribute -= proba;
502  } }
503  if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
504  /* corner case, need another normalization method */
505  size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
506  if (FSE_isError(errorCode)) return errorCode;
507  }
508  else normalizedCounter[largest] += (short)stillToDistribute;
509  }
510 
511 #if 0
512  { /* Print Table (debug) */
513  U32 s;
514  U32 nTotal = 0;
515  for (s=0; s<=maxSymbolValue; s++)
516  RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
517  for (s=0; s<=maxSymbolValue; s++)
518  nTotal += abs(normalizedCounter[s]);
519  if (nTotal != (1U<<tableLog))
520  RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
521  getchar();
522  }
523 #endif
524 
525  return tableLog;
526 }
527 
528 
529 /* fake FSE_CTable, for raw (uncompressed) input */
530 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits)
531 {
532  const unsigned tableSize = 1 << nbBits;
533  const unsigned tableMask = tableSize - 1;
534  const unsigned maxSymbolValue = tableMask;
535  void* const ptr = ct;
536  U16* const tableU16 = ( (U16*) ptr) + 2;
537  void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1); /* assumption : tableLog >= 1 */
538  FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
539  unsigned s;
540 
541  /* Sanity checks */
542  if (nbBits < 1) return ERROR(GENERIC); /* min size */
543 
544  /* header */
545  tableU16[-2] = (U16) nbBits;
546  tableU16[-1] = (U16) maxSymbolValue;
547 
548  /* Build table */
549  for (s=0; s<tableSize; s++)
550  tableU16[s] = (U16)(tableSize + s);
551 
552  /* Build Symbol Transformation Table */
553  { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
554  for (s=0; s<=maxSymbolValue; s++) {
555  symbolTT[s].deltaNbBits = deltaNbBits;
556  symbolTT[s].deltaFindState = s-1;
557  } }
558 
559  return 0;
560 }
561 
562 /* fake FSE_CTable, for rle input (always same symbol) */
563 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
564 {
565  void* ptr = ct;
566  U16* tableU16 = ( (U16*) ptr) + 2;
567  void* FSCTptr = (U32*)ptr + 2;
568  FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
569 
570  /* header */
571  tableU16[-2] = (U16) 0;
572  tableU16[-1] = (U16) symbolValue;
573 
574  /* Build table */
575  tableU16[0] = 0;
576  tableU16[1] = 0; /* just in case */
577 
578  /* Build Symbol Transformation Table */
579  symbolTT[symbolValue].deltaNbBits = 0;
580  symbolTT[symbolValue].deltaFindState = 0;
581 
582  return 0;
583 }
584 
585 
586 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
587  const void* src, size_t srcSize,
588  const FSE_CTable* ct, const unsigned fast)
589 {
590  const BYTE* const istart = (const BYTE*) src;
591  const BYTE* const iend = istart + srcSize;
592  const BYTE* ip=iend;
593 
594  BIT_CStream_t bitC;
595  FSE_CState_t CState1, CState2;
596 
597  /* init */
598  if (srcSize <= 2) return 0;
599  { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
600  if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
601 
602 #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
603 
604  if (srcSize & 1) {
605  FSE_initCState2(&CState1, ct, *--ip);
606  FSE_initCState2(&CState2, ct, *--ip);
607  FSE_encodeSymbol(&bitC, &CState1, *--ip);
608  FSE_FLUSHBITS(&bitC);
609  } else {
610  FSE_initCState2(&CState2, ct, *--ip);
611  FSE_initCState2(&CState1, ct, *--ip);
612  }
613 
614  /* join to mod 4 */
615  srcSize -= 2;
616  if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */
617  FSE_encodeSymbol(&bitC, &CState2, *--ip);
618  FSE_encodeSymbol(&bitC, &CState1, *--ip);
619  FSE_FLUSHBITS(&bitC);
620  }
621 
622  /* 2 or 4 encoding per loop */
623  while ( ip>istart ) {
624 
625  FSE_encodeSymbol(&bitC, &CState2, *--ip);
626 
627  if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */
628  FSE_FLUSHBITS(&bitC);
629 
630  FSE_encodeSymbol(&bitC, &CState1, *--ip);
631 
632  if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */
633  FSE_encodeSymbol(&bitC, &CState2, *--ip);
634  FSE_encodeSymbol(&bitC, &CState1, *--ip);
635  }
636 
637  FSE_FLUSHBITS(&bitC);
638  }
639 
640  FSE_flushCState(&bitC, &CState2);
641  FSE_flushCState(&bitC, &CState1);
642  return BIT_closeCStream(&bitC);
643 }
644 
645 size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
646  const void* src, size_t srcSize,
647  const FSE_CTable* ct)
648 {
649  unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
650 
651  if (fast)
652  return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
653  else
654  return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
655 }
656 
657 
658 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
659 
660 #define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return e
661 #define CHECK_F(f) { CHECK_V_F(_var_err__, f); }
662 
663 /* FSE_compress_wksp() :
664  * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`).
665  * `wkspSize` size must be `(1<<tableLog)`.
666  */
667 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)
668 {
669  BYTE* const ostart = (BYTE*) dst;
670  BYTE* op = ostart;
671  BYTE* const oend = ostart + dstSize;
672 
673  U32 count[FSE_MAX_SYMBOL_VALUE+1];
674  S16 norm[FSE_MAX_SYMBOL_VALUE+1];
675  FSE_CTable* CTable = (FSE_CTable*)workSpace;
676  size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue);
677  void* scratchBuffer = (void*)(CTable + CTableSize);
678  size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable));
679 
680  /* init conditions */
681  if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge);
682  if (srcSize <= 1) return 0; /* Not compressible */
683  if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
684  if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
685 
686  /* Scan input and build symbol stats */
687  { CHECK_V_F(maxCount, HIST_count_wksp(count, &maxSymbolValue, src, srcSize, (unsigned*)scratchBuffer) );
688  if (maxCount == srcSize) return 1; /* only a single symbol in src : rle */
689  if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
690  if (maxCount < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */
691  }
692 
693  tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue);
694  CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) );
695 
696  /* Write table description header */
697  { CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) );
698  op += nc_err;
699  }
700 
701  /* Compress */
702  CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) );
703  { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) );
704  if (cSize == 0) return 0; /* not enough space for compressed data */
705  op += cSize;
706  }
707 
708  /* check compressibility */
709  if ( (size_t)(op-ostart) >= srcSize-1 ) return 0;
710 
711  return op-ostart;
712 }
713 
714 typedef struct {
715  FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)];
716  BYTE scratchBuffer[1 << FSE_MAX_TABLELOG];
717 } fseWkspMax_t;
718 
719 size_t FSE_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
720 {
721  fseWkspMax_t* scratchBuffer;
722  size_t ret;
723 
724  DEBUG_STATIC_ASSERT(sizeof(fseWkspMax_t) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */
725 
726  if (tableLog > FSE_MAX_TABLELOG)
727  return ERROR(tableLog_tooLarge);
728 
730 
731  if (!scratchBuffer)
732  return 0;
733 
734  ret = FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, scratchBuffer, sizeof(fseWkspMax_t));
735 
736  ExFreePool(scratchBuffer);
737 
738  return ret;
739 }
740 
741 size_t FSE_compress (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
742 {
743  return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
744 }
745 
746 
747 #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:337
_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:658
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:345
#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:357
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:530
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:645
static size_t FSE_normalizeM2(short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
Definition: fse_compress.c:380
#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:586
#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:660
#define DEBUG_STATIC_ASSERT(c)
Definition: debug.h:63
#define CHECK_F(f)
Definition: fse_compress.c:661
#define ULL(a, b)
Definition: format_msg.c:27
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:348
size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
Definition: fse_compress.c:563
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:719
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:667
size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:320
#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:371
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
Definition: hist.c:193
int ret
static size_t FSE_writeNCount_generic(void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, unsigned writeIsSafe)
Definition: fse_compress.c:225
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:467
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:741
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:218