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