/src/zstd/lib/compress/hist.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* ****************************************************************** |
2 | | * hist : Histogram functions |
3 | | * part of Finite State Entropy project |
4 | | * Copyright (c) Meta Platforms, Inc. and affiliates. |
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 | 0 | 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 | 186M | { |
32 | 186M | const BYTE* ip = (const BYTE*)src; |
33 | 186M | const BYTE* const end = ip + srcSize; |
34 | 186M | unsigned maxSymbolValue = *maxSymbolValuePtr; |
35 | 186M | unsigned largestCount=0; |
36 | | |
37 | 186M | ZSTD_memset(count, 0, (maxSymbolValue+1) * sizeof(*count)); |
38 | 186M | if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; } |
39 | | |
40 | 14.8G | while (ip<end) { |
41 | 14.6G | assert(*ip <= maxSymbolValue); |
42 | 14.6G | count[*ip++]++; |
43 | 14.6G | } |
44 | | |
45 | 7.08G | while (!count[maxSymbolValue]) maxSymbolValue--; |
46 | 184M | *maxSymbolValuePtr = maxSymbolValue; |
47 | | |
48 | 184M | { U32 s; |
49 | 7.16G | for (s=0; s<=maxSymbolValue; s++) |
50 | 6.97G | if (count[s] > largestCount) largestCount = count[s]; |
51 | 184M | } |
52 | | |
53 | 184M | return largestCount; |
54 | 184M | } |
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` must be a U32 table of size >= HIST_WKSP_SIZE_U32. |
64 | | * @return : largest histogram frequency, |
65 | | * or an error code (notably when histogram's alphabet is 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 | 2.29M | { |
72 | 2.29M | const BYTE* ip = (const BYTE*)source; |
73 | 2.29M | const BYTE* const iend = ip+sourceSize; |
74 | 2.29M | size_t const countSize = (*maxSymbolValuePtr + 1) * sizeof(*count); |
75 | 2.29M | unsigned max=0; |
76 | 2.29M | U32* const Counting1 = workSpace; |
77 | 2.29M | U32* const Counting2 = Counting1 + 256; |
78 | 2.29M | U32* const Counting3 = Counting2 + 256; |
79 | 2.29M | U32* const Counting4 = Counting3 + 256; |
80 | | |
81 | | /* safety checks */ |
82 | 2.29M | assert(*maxSymbolValuePtr <= 255); |
83 | 2.29M | if (!sourceSize) { |
84 | 0 | ZSTD_memset(count, 0, countSize); |
85 | 0 | *maxSymbolValuePtr = 0; |
86 | 0 | return 0; |
87 | 0 | } |
88 | 2.29M | ZSTD_memset(workSpace, 0, 4*256*sizeof(unsigned)); |
89 | | |
90 | | /* by stripes of 16 bytes */ |
91 | 2.29M | { U32 cached = MEM_read32(ip); ip += 4; |
92 | 573M | while (ip < iend-15) { |
93 | 571M | U32 c = cached; cached = MEM_read32(ip); ip += 4; |
94 | 571M | Counting1[(BYTE) c ]++; |
95 | 571M | Counting2[(BYTE)(c>>8) ]++; |
96 | 571M | Counting3[(BYTE)(c>>16)]++; |
97 | 571M | Counting4[ c>>24 ]++; |
98 | 571M | c = cached; cached = MEM_read32(ip); ip += 4; |
99 | 571M | Counting1[(BYTE) c ]++; |
100 | 571M | Counting2[(BYTE)(c>>8) ]++; |
101 | 571M | Counting3[(BYTE)(c>>16)]++; |
102 | 571M | Counting4[ c>>24 ]++; |
103 | 571M | c = cached; cached = MEM_read32(ip); ip += 4; |
104 | 571M | Counting1[(BYTE) c ]++; |
105 | 571M | Counting2[(BYTE)(c>>8) ]++; |
106 | 571M | Counting3[(BYTE)(c>>16)]++; |
107 | 571M | Counting4[ c>>24 ]++; |
108 | 571M | c = cached; cached = MEM_read32(ip); ip += 4; |
109 | 571M | Counting1[(BYTE) c ]++; |
110 | 571M | Counting2[(BYTE)(c>>8) ]++; |
111 | 571M | Counting3[(BYTE)(c>>16)]++; |
112 | 571M | Counting4[ c>>24 ]++; |
113 | 571M | } |
114 | 2.29M | ip-=4; |
115 | 2.29M | } |
116 | | |
117 | | /* finish last symbols */ |
118 | 28.7M | while (ip<iend) Counting1[*ip++]++; |
119 | | |
120 | 2.29M | { U32 s; |
121 | 586M | for (s=0; s<256; s++) { |
122 | 584M | Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s]; |
123 | 584M | if (Counting1[s] > max) max = Counting1[s]; |
124 | 584M | } } |
125 | | |
126 | 2.29M | { unsigned maxSymbolValue = 255; |
127 | 233M | while (!Counting1[maxSymbolValue]) maxSymbolValue--; |
128 | 2.29M | if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall); |
129 | 2.29M | *maxSymbolValuePtr = maxSymbolValue; |
130 | 2.29M | ZSTD_memmove(count, Counting1, countSize); /* in case count & Counting1 are overlapping */ |
131 | 2.29M | } |
132 | 0 | return (size_t)max; |
133 | 2.29M | } |
134 | | |
135 | | /* HIST_countFast_wksp() : |
136 | | * Same as HIST_countFast(), but using an externally provided scratch buffer. |
137 | | * `workSpace` is a writable buffer which must be 4-bytes aligned, |
138 | | * `workSpaceSize` must be >= HIST_WKSP_SIZE |
139 | | */ |
140 | | size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr, |
141 | | const void* source, size_t sourceSize, |
142 | | void* workSpace, size_t workSpaceSize) |
143 | 187M | { |
144 | 187M | if (sourceSize < 1500) /* heuristic threshold */ |
145 | 185M | return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize); |
146 | 2.27M | if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */ |
147 | 2.27M | if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall); |
148 | 2.27M | return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace); |
149 | 2.27M | } |
150 | | |
151 | | /* HIST_count_wksp() : |
152 | | * Same as HIST_count(), but using an externally provided scratch buffer. |
153 | | * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */ |
154 | | size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr, |
155 | | const void* source, size_t sourceSize, |
156 | | void* workSpace, size_t workSpaceSize) |
157 | 33.2M | { |
158 | 33.2M | if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */ |
159 | 33.2M | if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall); |
160 | 33.2M | if (*maxSymbolValuePtr < 255) |
161 | 0 | return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace); |
162 | 33.2M | *maxSymbolValuePtr = 255; |
163 | 33.2M | return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize); |
164 | 33.2M | } |
165 | | |
166 | | #ifndef ZSTD_NO_UNUSED_FUNCTIONS |
167 | | /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */ |
168 | | size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr, |
169 | | const void* source, size_t sourceSize) |
170 | 0 | { |
171 | 0 | unsigned tmpCounters[HIST_WKSP_SIZE_U32]; |
172 | 0 | return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters)); |
173 | 0 | } |
174 | | |
175 | | size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr, |
176 | | const void* src, size_t srcSize) |
177 | 0 | { |
178 | 0 | unsigned tmpCounters[HIST_WKSP_SIZE_U32]; |
179 | 0 | return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters)); |
180 | 0 | } |
181 | | #endif |