Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
kernel
os
linux
1/* SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause */
2/* ******************************************************************
3 * hist : Histogram functions
4 * part of Finite State Entropy project
5 * Copyright (c) Meta Platforms, Inc. and affiliates.
6 *
7 * You can contact the author at :
8 * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
9 * - Public forum : https://groups.google.com/forum/#!forum/lz4c
10 *
11 * This source code is licensed under both the BSD-style license (found in the
12 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
13 * in the COPYING file in the root directory of this source tree).
14 * You may select, at your option, one of the above-listed licenses.
15****************************************************************** */
16
17/* --- dependencies --- */
18#include "../common/zstd_deps.h" /* size_t */
19
20
21/* --- simple histogram functions --- */
22
23/*! HIST_count():
24 * Provides the precise count of each byte within a table 'count'.
25 * 'count' is a table of unsigned int, of minimum size (*maxSymbolValuePtr+1).
26 * Updates *maxSymbolValuePtr with actual largest symbol value detected.
27 * @return : count of the most frequent symbol (which isn't identified).
28 * or an error code, which can be tested using HIST_isError().
29 * note : if return == srcSize, there is only one symbol.
30 */
31size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr,
32 const void* src, size_t srcSize);
33
34unsigned HIST_isError(size_t code); /*< tells if a return value is an error code */
35
36
37/* --- advanced histogram functions --- */
38
39#define HIST_WKSP_SIZE_U32 1024
40#define HIST_WKSP_SIZE (HIST_WKSP_SIZE_U32 * sizeof(unsigned))
41/* HIST_count_wksp() :
42 * Same as HIST_count(), but using an externally provided scratch buffer.
43 * Benefit is this function will use very little stack space.
44 * `workSpace` is a writable buffer which must be 4-bytes aligned,
45 * `workSpaceSize` must be >= HIST_WKSP_SIZE
46 */
47size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
48 const void* src, size_t srcSize,
49 void* workSpace, size_t workSpaceSize);
50
51/* HIST_countFast() :
52 * same as HIST_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr.
53 * This function is unsafe, and will segfault if any value within `src` is `> *maxSymbolValuePtr`
54 */
55size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
56 const void* src, size_t srcSize);
57
58/* HIST_countFast_wksp() :
59 * Same as HIST_countFast(), but using an externally provided scratch buffer.
60 * `workSpace` is a writable buffer which must be 4-bytes aligned,
61 * `workSpaceSize` must be >= HIST_WKSP_SIZE
62 */
63size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
64 const void* src, size_t srcSize,
65 void* workSpace, size_t workSpaceSize);
66
67/*! HIST_count_simple() :
68 * Same as HIST_countFast(), this function is unsafe,
69 * and will segfault if any value within `src` is `> *maxSymbolValuePtr`.
70 * It is also a bit slower for large inputs.
71 * However, it does not need any additional memory (not even on stack).
72 * @return : count of the most frequent symbol.
73 * Note this function doesn't produce any error (i.e. it must succeed).
74 */
75unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
76 const void* src, size_t srcSize);
77
78/*! HIST_add() :
79 * Lowest level: just add nb of occurrences of characters from @src into @count.
80 * @count is not reset. @count array is presumed large enough (i.e. 1 KB).
81 @ This function does not need any additional stack memory.
82 */
83void HIST_add(unsigned* count, const void* src, size_t srcSize);