zstd/compress/hist.c

0001 /* ******************************************************************
0002  * hist : Histogram functions
0003  * part of Finite State Entropy project
0004  * Copyright (c) Yann Collet, Facebook, Inc.
0005  *
0006  *  You can contact the author at :
0007  *  - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
0008  *  - Public forum : https://groups.google.com/forum/#!forum/lz4c
0009  *
0010  * This source code is licensed under both the BSD-style license (found in the
0011  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0012  * in the COPYING file in the root directory of this source tree).
0013  * You may select, at your option, one of the above-listed licenses.
0014 ****************************************************************** */
0015
0016 /* --- dependencies --- */
0017 #include "../common/mem.h"             /* U32, BYTE, etc. */
0018 #include "../common/debug.h"           /* assert, DEBUGLOG */
0019 #include "../common/error_private.h"   /* ERROR */
0020 #include "hist.h"
0021
0022
0023 /* --- Error management --- */
0024 unsigned HIST_isError(size_t code) { return ERR_isError(code); }
0025
0026 /*-**************************************************************
0027  *  Histogram functions
0028  ****************************************************************/
0029 unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
0030                            const void* src, size_t srcSize)
0031 {
0032     const BYTE* ip = (const BYTE*)src;
0033     const BYTE* const end = ip + srcSize;
0034     unsigned maxSymbolValue = *maxSymbolValuePtr;
0035     unsigned largestCount=0;
0036
0037     ZSTD_memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
0038     if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
0039
0040     while (ip<end) {
0041         assert(*ip <= maxSymbolValue);
0042         count[*ip++]++;
0043     }
0044
0045     while (!count[maxSymbolValue]) maxSymbolValue--;
0046     *maxSymbolValuePtr = maxSymbolValue;
0047
0048     {   U32 s;
0049         for (s=0; s<=maxSymbolValue; s++)
0050             if (count[s] > largestCount) largestCount = count[s];
0051     }
0052
0053     return largestCount;
0054 }
0055
0056 typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e;
0057
0058 /* HIST_count_parallel_wksp() :
0059  * store histogram into 4 intermediate tables, recombined at the end.
0060  * this design makes better use of OoO cpus,
0061  * and is noticeably faster when some values are heavily repeated.
0062  * But it needs some additional workspace for intermediate tables.
0063  * `workSpace` must be a U32 table of size >= HIST_WKSP_SIZE_U32.
0064  * @return : largest histogram frequency,
0065  *           or an error code (notably when histogram's alphabet is larger than *maxSymbolValuePtr) */
0066 static size_t HIST_count_parallel_wksp(
0067                                 unsigned* count, unsigned* maxSymbolValuePtr,
0068                                 const void* source, size_t sourceSize,
0069                                 HIST_checkInput_e check,
0070                                 U32* const workSpace)
0071 {
0072     const BYTE* ip = (const BYTE*)source;
0073     const BYTE* const iend = ip+sourceSize;
0074     size_t const countSize = (*maxSymbolValuePtr + 1) * sizeof(*count);
0075     unsigned max=0;
0076     U32* const Counting1 = workSpace;
0077     U32* const Counting2 = Counting1 + 256;
0078     U32* const Counting3 = Counting2 + 256;
0079     U32* const Counting4 = Counting3 + 256;
0080
0081     /* safety checks */
0082     assert(*maxSymbolValuePtr <= 255);
0083     if (!sourceSize) {
0084         ZSTD_memset(count, 0, countSize);
0085         *maxSymbolValuePtr = 0;
0086         return 0;
0087     }
0088     ZSTD_memset(workSpace, 0, 4*256*sizeof(unsigned));
0089
0090     /* by stripes of 16 bytes */
0091     {   U32 cached = MEM_read32(ip); ip += 4;
0092         while (ip < iend-15) {
0093             U32 c = cached; cached = MEM_read32(ip); ip += 4;
0094             Counting1[(BYTE) c     ]++;
0095             Counting2[(BYTE)(c>>8) ]++;
0096             Counting3[(BYTE)(c>>16)]++;
0097             Counting4[       c>>24 ]++;
0098             c = cached; cached = MEM_read32(ip); ip += 4;
0099             Counting1[(BYTE) c     ]++;
0100             Counting2[(BYTE)(c>>8) ]++;
0101             Counting3[(BYTE)(c>>16)]++;
0102             Counting4[       c>>24 ]++;
0103             c = cached; cached = MEM_read32(ip); ip += 4;
0104             Counting1[(BYTE) c     ]++;
0105             Counting2[(BYTE)(c>>8) ]++;
0106             Counting3[(BYTE)(c>>16)]++;
0107             Counting4[       c>>24 ]++;
0108             c = cached; cached = MEM_read32(ip); ip += 4;
0109             Counting1[(BYTE) c     ]++;
0110             Counting2[(BYTE)(c>>8) ]++;
0111             Counting3[(BYTE)(c>>16)]++;
0112             Counting4[       c>>24 ]++;
0113         }
0114         ip-=4;
0115     }
0116
0117     /* finish last symbols */
0118     while (ip<iend) Counting1[*ip++]++;
0119
0120     {   U32 s;
0121         for (s=0; s<256; s++) {
0122             Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
0123             if (Counting1[s] > max) max = Counting1[s];
0124     }   }
0125
0126     {   unsigned maxSymbolValue = 255;
0127         while (!Counting1[maxSymbolValue]) maxSymbolValue--;
0128         if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall);
0129         *maxSymbolValuePtr = maxSymbolValue;
0130         ZSTD_memmove(count, Counting1, countSize);   /* in case count & Counting1 are overlapping */
0131     }
0132     return (size_t)max;
0133 }
0134
0135 /* HIST_countFast_wksp() :
0136  * Same as HIST_countFast(), but using an externally provided scratch buffer.
0137  * `workSpace` is a writable buffer which must be 4-bytes aligned,
0138  * `workSpaceSize` must be >= HIST_WKSP_SIZE
0139  */
0140 size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
0141                           const void* source, size_t sourceSize,
0142                           void* workSpace, size_t workSpaceSize)
0143 {
0144     if (sourceSize < 1500) /* heuristic threshold */
0145         return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
0146     if ((size_t)workSpace & 3) return ERROR(GENERIC);  /* must be aligned on 4-bytes boundaries */
0147     if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
0148     return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
0149 }
0150
0151 /* HIST_count_wksp() :
0152  * Same as HIST_count(), but using an externally provided scratch buffer.
0153  * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */
0154 size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
0155                        const void* source, size_t sourceSize,
0156                        void* workSpace, size_t workSpaceSize)
0157 {
0158     if ((size_t)workSpace & 3) return ERROR(GENERIC);  /* must be aligned on 4-bytes boundaries */
0159     if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
0160     if (*maxSymbolValuePtr < 255)
0161         return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
0162     *maxSymbolValuePtr = 255;
0163     return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
0164 }
0165