mercurial: comparison contrib/python-zstandard/zstd/compress/fse

equal deleted inserted replaced

-:1ce7a55b09d1
+:b1fb341d8a61
 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
 - Public forum : https://groups.google.com/forum/#!forum/lz4c
 ****************************************************************** */
 /* **************************************************************
-*  Compiler specifics
-****************************************************************/
-#ifdef _MSC_VER    /* Visual Studio */
-#  define FORCE_INLINE static __forceinline
-#  include <intrin.h>                    /* For Visual 2005 */
-#  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
-#  pragma warning(disable : 4214)        /* disable: C4214: non-int bitfields */
-#else
-#  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
-#    ifdef __GNUC__
-#      define FORCE_INLINE static inline __attribute__((always_inline))
-#    else
-#      define FORCE_INLINE static inline
-#    endif
-#  else
-#    define FORCE_INLINE static
-#  endif /* __STDC_VERSION__ */
-#endif
-/* **************************************************************
 *  Includes
 ****************************************************************/
 #include <stdlib.h>     /* malloc, free, qsort */
 #include <string.h>     /* memcpy, memset */
 #include <stdio.h>      /* printf (debug) */
 #include "bitstream.h"
+#include "compiler.h"
 #define FSE_STATIC_LINKING_ONLY
 #include "fse.h"
+#include "error_private.h"
 /* **************************************************************
 *  Error Management
 ****************************************************************/
+#define FSE_isError ERR_isError
 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
 /* **************************************************************
 *  Templates
 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
 {
 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND;  /* maxSymbolValue==0 ? use default */
 }
-static short FSE_abs(short a) { return (short)(a<0 ? -a : a); }
 static size_t FSE_writeNCount_generic (void* header, size_t headerBufferSize,
 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
 unsigned writeIsSafe)
 {
 out[1] = (BYTE)(bitStream>>8);
 out += 2;
 bitStream >>= 16;
 bitCount -= 16;
 }   }
-{   short count = normalizedCounter[charnum++];
+{   int count = normalizedCounter[charnum++];
-const short max = (short)((2*threshold-1)-remaining);
+int const max = (2*threshold-1)-remaining;
-remaining -= FSE_abs(count);
+remaining -= count < 0 ? -count : count;
-if (remaining<1) return ERROR(GENERIC);
 count++;   /* +1 for extra accuracy */
 if (count>=threshold) count += max;   /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
 bitStream += count << bitCount;
 bitCount  += nbBits;
 bitCount  -= (count<max);
 previous0  = (count==1);
-while (remaining<threshold) nbBits--, threshold>>=1;
+if (remaining<1) return ERROR(GENERIC);
+while (remaining<threshold) { nbBits--; threshold>>=1; }
 }
 if (bitCount>16) {
 if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall);   /* Buffer overflow */
 out[0] = (BYTE)bitStream;
 out[1] = (BYTE)(bitStream>>8);
 }
 size_t FSE_writeNCount (void* buffer, size_t bufferSize, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 {
-if (tableLog > FSE_MAX_TABLELOG) return ERROR(GENERIC);   /* Unsupported */
+if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported */
 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported */
 if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
 /*! FSE_count_simple
 This function counts byte values within `src`, and store the histogram into table `count`.
 It doesn't use any additional memory.
 But this function is unsafe : it doesn't check that all values within `src` can fit into `count`.
 For this reason, prefer using a table `count` with 256 elements.
-@return : count of most numerous element
+@return : count of most numerous element.
 */
 size_t FSE_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
 const void* src, size_t srcSize)
 {
 const BYTE* ip = (const BYTE*)src;
 unsigned max=0;
 memset(count, 0, (maxSymbolValue+1)*sizeof(*count));
 if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
-while (ip<end) count[*ip++]++;
+while (ip<end) {
+assert(*ip <= maxSymbolValue);
+count[*ip++]++;
+}
 while (!count[maxSymbolValue]) maxSymbolValue--;
 *maxSymbolValuePtr = maxSymbolValue;
 { U32 s; for (s=0; s<=maxSymbolValue; s++) if (count[s] > max) max = count[s]; }
 }
 /* FSE_count_parallel_wksp() :
 * Same as FSE_count_parallel(), but using an externally provided scratch buffer.
-* `workSpace` size must be a minimum of `1024 * sizeof(unsigned)`` */
+* `workSpace` size must be a minimum of `1024 * sizeof(unsigned)`.
+* @return : largest histogram frequency, or an error code (notably when histogram would be larger than *maxSymbolValuePtr). */
 static size_t FSE_count_parallel_wksp(
 unsigned* count, unsigned* maxSymbolValuePtr,
 const void* source, size_t sourceSize,
 unsigned checkMax, unsigned* const workSpace)
 {
 U32* const Counting1 = workSpace;
 U32* const Counting2 = Counting1 + 256;
 U32* const Counting3 = Counting2 + 256;
 U32* const Counting4 = Counting3 + 256;
-memset(Counting1, 0, 4*256*sizeof(unsigned));
+memset(workSpace, 0, 4*256*sizeof(unsigned));
 /* safety checks */
 if (!sourceSize) {
 memset(count, 0, maxSymbolValue + 1);
 *maxSymbolValuePtr = 0;
 U32 s; for (s=255; s>maxSymbolValue; s--) {
 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
 if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
 }   }
-{   U32 s; for (s=0; s<=maxSymbolValue; s++) {
+{   U32 s;
+if (maxSymbolValue > 255) maxSymbolValue = 255;
+for (s=0; s<=maxSymbolValue; s++) {
 count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
 if (count[s] > max) max = count[s];
 }   }
 while (!count[maxSymbolValue]) maxSymbolValue--;
 /* FSE_countFast_wksp() :
 * Same as FSE_countFast(), but using an externally provided scratch buffer.
 * `workSpace` size must be table of >= `1024` unsigned */
 size_t FSE_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
-const void* source, size_t sourceSize, unsigned* workSpace)
+const void* source, size_t sourceSize,
-{
+unsigned* workSpace)
-if (sourceSize < 1500) return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize);
+{
+if (sourceSize < 1500) /* heuristic threshold */
+return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize);
 return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 0, workSpace);
 }
 /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
 size_t FSE_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
 void FSE_freeCTable (FSE_CTable* ct) { free(ct); }
 /* provides the minimum logSize to safely represent a distribution */
 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
 {
-	U32 minBitsSrc = BIT_highbit32((U32)(srcSize - 1)) + 1;
+U32 minBitsSrc = BIT_highbit32((U32)(srcSize - 1)) + 1;
-	U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
+U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
-	U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
+U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
-	return minBits;
+assert(srcSize > 1); /* Not supported, RLE should be used instead */
+return minBits;
 }
 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
 {
-	U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
+U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
 U32 tableLog = maxTableLog;
-	U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
+U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
+assert(srcSize > 1); /* Not supported, RLE should be used instead */
 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
-	if (maxBitsSrc < tableLog) tableLog = maxBitsSrc;   /* Accuracy can be reduced */
+if (maxBitsSrc < tableLog) tableLog = maxBitsSrc;   /* Accuracy can be reduced */
-	if (minBits > tableLog) tableLog = minBits;   /* Need a minimum to safely represent all symbol values */
+if (minBits > tableLog) tableLog = minBits;   /* Need a minimum to safely represent all symbol values */
 if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
 if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
 return tableLog;
 }
 /* Secondary normalization method.
 To be used when primary method fails. */
 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue)
 {
+short const NOT_YET_ASSIGNED = -2;
 U32 s;
 U32 distributed = 0;
 U32 ToDistribute;
 /* Init */
 norm[s] = 1;
 distributed++;
 total -= count[s];
 continue;
 }
-norm[s]=-2;
+norm[s]=NOT_YET_ASSIGNED;
 }
 ToDistribute = (1 << tableLog) - distributed;
 if ((total / ToDistribute) > lowOne) {
 /* risk of rounding to zero */
 lowOne = (U32)((total * 3) / (ToDistribute * 2));
 for (s=0; s<=maxSymbolValue; s++) {
-if ((norm[s] == -2) && (count[s] <= lowOne)) {
+if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
 norm[s] = 1;
 distributed++;
 total -= count[s];
 continue;
 }   }
 /* all values are pretty poor;
 probably incompressible data (should have already been detected);
 find max, then give all remaining points to max */
 U32 maxV = 0, maxC = 0;
 for (s=0; s<=maxSymbolValue; s++)
-if (count[s] > maxC) maxV=s, maxC=count[s];
+if (count[s] > maxC) { maxV=s; maxC=count[s]; }
 norm[maxV] += (short)ToDistribute;
+return 0;
+}
+if (total == 0) {
+/* all of the symbols were low enough for the lowOne or lowThreshold */
+for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
+if (norm[s] > 0) { ToDistribute--; norm[s]++; }
 return 0;
 }
 {   U64 const vStepLog = 62 - tableLog;
 U64 const mid = (1ULL << (vStepLog-1)) - 1;
 U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total;   /* scale on remaining */
 U64 tmpTotal = mid;
 for (s=0; s<=maxSymbolValue; s++) {
-if (norm[s]==-2) {
+if (norm[s]==NOT_YET_ASSIGNED) {
 U64 const end = tmpTotal + (count[s] * rStep);
 U32 const sStart = (U32)(tmpTotal >> vStepLog);
 U32 const sEnd = (U32)(end >> vStepLog);
 U32 const weight = sEnd - sStart;
 if (weight < 1)
 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported size */
 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported size */
 if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC);   /* Too small tableLog, compression potentially impossible */
-{   U32 const rtbTable[] = {     0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
+{   static U32 const rtbTable[] = {     0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
 U64 const scale = 62 - tableLog;
 U64 const step = ((U64)1<<62) / total;   /* <== here, one division ! */
 U64 const vStep = 1ULL<<(scale-20);
 int stillToDistribute = 1<<tableLog;
 unsigned s;
 short proba = (short)((count[s]*step) >> scale);
 if (proba<8) {
 U64 restToBeat = vStep * rtbTable[proba];
 proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
 }
-if (proba > largestP) largestP=proba, largest=s;
+if (proba > largestP) { largestP=proba; largest=s; }
 normalizedCounter[s] = proba;
 stillToDistribute -= proba;
 }   }
 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
 /* corner case, need another normalization method */
 }
 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
-#define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return f
+#define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return e
 #define CHECK_F(f)   { CHECK_V_F(_var_err__, f); }
 /* FSE_compress_wksp() :
 * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`).
 * `wkspSize` size must be `(1<<tableLog)`.
 if (srcSize <= 1) return 0;  /* Not compressible */
 if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
 if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
 /* Scan input and build symbol stats */
-{   CHECK_V_F(maxCount, FSE_count(count, &maxSymbolValue, src, srcSize) );
+{   CHECK_V_F(maxCount, FSE_count_wksp(count, &maxSymbolValue, src, srcSize, (unsigned*)scratchBuffer) );
 if (maxCount == srcSize) return 1;   /* only a single symbol in src : rle */
 if (maxCount == 1) return 0;         /* each symbol present maximum once => not compressible */
 if (maxCount < (srcSize >> 7)) return 0;   /* Heuristic : not compressible enough */
 }

changeset 37495	b1fb341d8a61
parent 30822	b54a2984cdd4
child 40121	73fef626dae3