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 */ 31 size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr, 32 const void* src, size_t srcSize); 33 34 unsigned 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 */ 47 size_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 */ 55 size_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 */ 63 size_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 */ 75 unsigned 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 */ 83 void HIST_add(unsigned* count, const void* src, size_t srcSize); 84