]>
Commit | Line | Data |
---|---|---|
9f95a23c | 1 | /* ****************************************************************** |
f67539c2 TL |
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. | |
9f95a23c TL |
14 | ****************************************************************** */ |
15 | ||
16 | /* --- dependencies --- */ | |
f67539c2 TL |
17 | #include "../common/mem.h" /* U32, BYTE, etc. */ |
18 | #include "../common/debug.h" /* assert, DEBUGLOG */ | |
19 | #include "../common/error_private.h" /* ERROR */ | |
9f95a23c TL |
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 | } |