1 /* ****************************************************************** 2 * hist : Histogram functions 3 * part of Finite State Entropy project 4 * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc. 5 * 6 * You can contact the author at : 7 * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 8 * - Public forum : https://groups.google.com/forum/#!forum/lz4c 9 * 10 * This source code is licensed under both the BSD-style license (found in the 11 * LICENSE file in the root directory of this source tree) and the GPLv2 (found 12 * in the COPYING file in the root directory of this source tree). 13 * You may select, at your option, one of the above-listed licenses. 14 ****************************************************************** */ 15 16 /* --- dependencies --- */ 17 #include "../common/mem.h" /* U32, BYTE, etc. */ 18 #include "../common/debug.h" /* assert, DEBUGLOG */ 19 #include "../common/error_private.h" /* ERROR */ 20 #include "hist.h" 21 22 23 /* --- Error management --- */ 24 unsigned HIST_isError(size_t code) { return ERR_isError(code); } 25 26 /*-************************************************************** 27 * Histogram functions 28 ****************************************************************/ 29 unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr, 30 const void* src, size_t srcSize) 31 { 32 const BYTE* ip = (const BYTE*)src; 33 const BYTE* const end = ip + srcSize; 34 unsigned maxSymbolValue = *maxSymbolValuePtr; 35 unsigned largestCount=0; 36 37 memset(count, 0, (maxSymbolValue+1) * sizeof(*count)); 38 if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; } 39 40 while (ip<end) { 41 assert(*ip <= maxSymbolValue); 42 count[*ip++]++; 43 } 44 45 while (!count[maxSymbolValue]) maxSymbolValue--; 46 *maxSymbolValuePtr = maxSymbolValue; 47 48 { U32 s; 49 for (s=0; s<=maxSymbolValue; s++) 50 if (count[s] > largestCount) largestCount = count[s]; 51 } 52 53 return largestCount; 54 } 55 56 typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e; 57 58 /* HIST_count_parallel_wksp() : 59 * store histogram into 4 intermediate tables, recombined at the end. 60 * this design makes better use of OoO cpus, 61 * and is noticeably faster when some values are heavily repeated. 62 * But it needs some additional workspace for intermediate tables. 63 * `workSpace` size must be a table of size >= HIST_WKSP_SIZE_U32. 64 * @return : largest histogram frequency, 65 * or an error code (notably when histogram would be larger than *maxSymbolValuePtr). */ 66 static size_t HIST_count_parallel_wksp( 67 unsigned* count, unsigned* maxSymbolValuePtr, 68 const void* source, size_t sourceSize, 69 HIST_checkInput_e check, 70 U32* const workSpace) 71 { 72 const BYTE* ip = (const BYTE*)source; 73 const BYTE* const iend = ip+sourceSize; 74 unsigned maxSymbolValue = *maxSymbolValuePtr; 75 unsigned max=0; 76 U32* const Counting1 = workSpace; 77 U32* const Counting2 = Counting1 + 256; 78 U32* const Counting3 = Counting2 + 256; 79 U32* const Counting4 = Counting3 + 256; 80 81 memset(workSpace, 0, 4*256*sizeof(unsigned)); 82 83 /* safety checks */ 84 if (!sourceSize) { 85 memset(count, 0, maxSymbolValue + 1); 86 *maxSymbolValuePtr = 0; 87 return 0; 88 } 89 if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */ 90 91 /* by stripes of 16 bytes */ 92 { U32 cached = MEM_read32(ip); ip += 4; 93 while (ip < iend-15) { 94 U32 c = cached; cached = MEM_read32(ip); ip += 4; 95 Counting1[(BYTE) c ]++; 96 Counting2[(BYTE)(c>>8) ]++; 97 Counting3[(BYTE)(c>>16)]++; 98 Counting4[ c>>24 ]++; 99 c = cached; cached = MEM_read32(ip); ip += 4; 100 Counting1[(BYTE) c ]++; 101 Counting2[(BYTE)(c>>8) ]++; 102 Counting3[(BYTE)(c>>16)]++; 103 Counting4[ c>>24 ]++; 104 c = cached; cached = MEM_read32(ip); ip += 4; 105 Counting1[(BYTE) c ]++; 106 Counting2[(BYTE)(c>>8) ]++; 107 Counting3[(BYTE)(c>>16)]++; 108 Counting4[ c>>24 ]++; 109 c = cached; cached = MEM_read32(ip); ip += 4; 110 Counting1[(BYTE) c ]++; 111 Counting2[(BYTE)(c>>8) ]++; 112 Counting3[(BYTE)(c>>16)]++; 113 Counting4[ c>>24 ]++; 114 } 115 ip-=4; 116 } 117 118 /* finish last symbols */ 119 while (ip<iend) Counting1[*ip++]++; 120 121 if (check) { /* verify stats will fit into destination table */ 122 U32 s; for (s=255; s>maxSymbolValue; s--) { 123 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s]; 124 if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall); 125 } } 126 127 { U32 s; 128 if (maxSymbolValue > 255) maxSymbolValue = 255; 129 for (s=0; s<=maxSymbolValue; s++) { 130 count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s]; 131 if (count[s] > max) max = count[s]; 132 } } 133 134 while (!count[maxSymbolValue]) maxSymbolValue--; 135 *maxSymbolValuePtr = maxSymbolValue; 136 return (size_t)max; 137 } 138 139 /* HIST_countFast_wksp() : 140 * Same as HIST_countFast(), but using an externally provided scratch buffer. 141 * `workSpace` is a writable buffer which must be 4-bytes aligned, 142 * `workSpaceSize` must be >= HIST_WKSP_SIZE 143 */ 144 size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr, 145 const void* source, size_t sourceSize, 146 void* workSpace, size_t workSpaceSize) 147 { 148 if (sourceSize < 1500) /* heuristic threshold */ 149 return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize); 150 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */ 151 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall); 152 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace); 153 } 154 155 /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */ 156 size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr, 157 const void* source, size_t sourceSize) 158 { 159 unsigned tmpCounters[HIST_WKSP_SIZE_U32]; 160 return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters)); 161 } 162 163 /* HIST_count_wksp() : 164 * Same as HIST_count(), but using an externally provided scratch buffer. 165 * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */ 166 size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr, 167 const void* source, size_t sourceSize, 168 void* workSpace, size_t workSpaceSize) 169 { 170 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */ 171 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall); 172 if (*maxSymbolValuePtr < 255) 173 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace); 174 *maxSymbolValuePtr = 255; 175 return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize); 176 } 177 178 size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr, 179 const void* src, size_t srcSize) 180 { 181 unsigned tmpCounters[HIST_WKSP_SIZE_U32]; 182 return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters)); 183 } 184