lib/compress/hist.c - third_party/zstd - Git at Google

 /* ******************************************************************
  * hist : Histogram functions
  * part of Finite State Entropy project
  * Copyright (c) Meta Platforms, Inc. and affiliates.
  *
  *  You can contact the author at :
  *  - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
  *  - Public forum : https://groups.google.com/forum/#!forum/lz4c
  *
  * This source code is licensed under both the BSD-style license (found in the
  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
  * in the COPYING file in the root directory of this source tree).
  * You may select, at your option, one of the above-listed licenses.
 ****************************************************************** */

 /* --- dependencies --- */
 #include "../common/mem.h"             /* U32, BYTE, etc. */
 #include "../common/debug.h"           /* assert, DEBUGLOG */
 #include "../common/error_private.h"   /* ERROR */
 #include "hist.h"

 #if defined(ZSTD_ARCH_ARM_SVE2)
 #define HIST_FAST_THRESHOLD 500
 #else
 #define HIST_FAST_THRESHOLD 1500
 #endif


 /* --- Error management --- */
 unsigned HIST_isError(size_t code) { return ERR_isError(code); }

 /*-**************************************************************
  *  Histogram functions
  ****************************************************************/
 void HIST_add(unsigned* count, const void* src, size_t srcSize)
 {
     const BYTE* ip = (const BYTE*)src;
     const BYTE* const end = ip + srcSize;

     while (ip<end) {
         count[*ip++]++;
     }
 }

 unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
                            const void* src, size_t srcSize)
 {
     const BYTE* ip = (const BYTE*)src;
     const BYTE* const end = ip + srcSize;
     unsigned maxSymbolValue = *maxSymbolValuePtr;
     unsigned largestCount=0;

     ZSTD_memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
     if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }

     while (ip<end) {
         assert(*ip <= maxSymbolValue);
         count[*ip++]++;
     }

     while (!count[maxSymbolValue]) maxSymbolValue--;
     *maxSymbolValuePtr = maxSymbolValue;

     {   U32 s;
         for (s=0; s<=maxSymbolValue; s++)
             if (count[s] > largestCount) largestCount = count[s];
     }

     return largestCount;
 }

 typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e;

 #if defined(ZSTD_ARCH_ARM_SVE2)
 FORCE_INLINE_TEMPLATE size_t min_size(size_t a, size_t b) { return a < b ? a : b; }

 static
 svuint16_t HIST_count_6_sve2(const BYTE* const src, size_t size, U32* const dst,
                              const svuint8_t c0, const svuint8_t c1,
                              const svuint8_t c2, const svuint8_t c3,
                              const svuint8_t c4, const svuint8_t c5,
                              const svuint16_t histmax, size_t maxCount)
 {
     const svbool_t vl128 = svptrue_pat_b8(SV_VL16);
     svuint16_t hh0 = svdup_n_u16(0);
     svuint16_t hh1 = svdup_n_u16(0);
     svuint16_t hh2 = svdup_n_u16(0);
     svuint16_t hh3 = svdup_n_u16(0);
     svuint16_t hh4 = svdup_n_u16(0);
     svuint16_t hh5 = svdup_n_u16(0);
     svuint16_t hh6 = svdup_n_u16(0);
     svuint16_t hh7 = svdup_n_u16(0);
     svuint16_t hh8 = svdup_n_u16(0);
     svuint16_t hh9 = svdup_n_u16(0);
     svuint16_t hha = svdup_n_u16(0);
     svuint16_t hhb = svdup_n_u16(0);

     size_t i = 0;
     while (i < size) {
         /* We can only accumulate 15 (15 * 16 <= 255) iterations of histogram
          * in 8-bit accumulators! */
         const size_t size240 = min_size(i + 240, size);

         svbool_t pred = svwhilelt_b8_u64(i, size);
         svuint8_t c = svld1rq_u8(pred, src + i);
         svuint8_t h0 = svhistseg_u8(c0, c);
         svuint8_t h1 = svhistseg_u8(c1, c);
         svuint8_t h2 = svhistseg_u8(c2, c);
         svuint8_t h3 = svhistseg_u8(c3, c);
         svuint8_t h4 = svhistseg_u8(c4, c);
         svuint8_t h5 = svhistseg_u8(c5, c);

         for (i += 16; i < size240; i += 16) {
             pred = svwhilelt_b8_u64(i, size);
             c = svld1rq_u8(pred, src + i);
             h0 = svadd_u8_x(vl128, h0, svhistseg_u8(c0, c));
             h1 = svadd_u8_x(vl128, h1, svhistseg_u8(c1, c));
             h2 = svadd_u8_x(vl128, h2, svhistseg_u8(c2, c));
             h3 = svadd_u8_x(vl128, h3, svhistseg_u8(c3, c));
             h4 = svadd_u8_x(vl128, h4, svhistseg_u8(c4, c));
             h5 = svadd_u8_x(vl128, h5, svhistseg_u8(c5, c));
         }

         hh0 = svaddwb_u16(hh0, h0);
         hh1 = svaddwt_u16(hh1, h0);
         hh2 = svaddwb_u16(hh2, h1);
         hh3 = svaddwt_u16(hh3, h1);
         hh4 = svaddwb_u16(hh4, h2);
         hh5 = svaddwt_u16(hh5, h2);
         hh6 = svaddwb_u16(hh6, h3);
         hh7 = svaddwt_u16(hh7, h3);
         hh8 = svaddwb_u16(hh8, h4);
         hh9 = svaddwt_u16(hh9, h4);
         hha = svaddwb_u16(hha, h5);
         hhb = svaddwt_u16(hhb, h5);
     }

     svst1_u32(svwhilelt_b32_u64( 0, maxCount), dst +  0, svshllb_n_u32(hh0, 0));
     svst1_u32(svwhilelt_b32_u64( 4, maxCount), dst +  4, svshllt_n_u32(hh0, 0));
     svst1_u32(svwhilelt_b32_u64( 8, maxCount), dst +  8, svshllb_n_u32(hh1, 0));
     svst1_u32(svwhilelt_b32_u64(12, maxCount), dst + 12, svshllt_n_u32(hh1, 0));
     svst1_u32(svwhilelt_b32_u64(16, maxCount), dst + 16, svshllb_n_u32(hh2, 0));
     svst1_u32(svwhilelt_b32_u64(20, maxCount), dst + 20, svshllt_n_u32(hh2, 0));
     svst1_u32(svwhilelt_b32_u64(24, maxCount), dst + 24, svshllb_n_u32(hh3, 0));
     svst1_u32(svwhilelt_b32_u64(28, maxCount), dst + 28, svshllt_n_u32(hh3, 0));
     svst1_u32(svwhilelt_b32_u64(32, maxCount), dst + 32, svshllb_n_u32(hh4, 0));
     svst1_u32(svwhilelt_b32_u64(36, maxCount), dst + 36, svshllt_n_u32(hh4, 0));
     svst1_u32(svwhilelt_b32_u64(40, maxCount), dst + 40, svshllb_n_u32(hh5, 0));
     svst1_u32(svwhilelt_b32_u64(44, maxCount), dst + 44, svshllt_n_u32(hh5, 0));
     svst1_u32(svwhilelt_b32_u64(48, maxCount), dst + 48, svshllb_n_u32(hh6, 0));
     svst1_u32(svwhilelt_b32_u64(52, maxCount), dst + 52, svshllt_n_u32(hh6, 0));
     svst1_u32(svwhilelt_b32_u64(56, maxCount), dst + 56, svshllb_n_u32(hh7, 0));
     svst1_u32(svwhilelt_b32_u64(60, maxCount), dst + 60, svshllt_n_u32(hh7, 0));
     svst1_u32(svwhilelt_b32_u64(64, maxCount), dst + 64, svshllb_n_u32(hh8, 0));
     svst1_u32(svwhilelt_b32_u64(68, maxCount), dst + 68, svshllt_n_u32(hh8, 0));
     svst1_u32(svwhilelt_b32_u64(72, maxCount), dst + 72, svshllb_n_u32(hh9, 0));
     svst1_u32(svwhilelt_b32_u64(76, maxCount), dst + 76, svshllt_n_u32(hh9, 0));
     svst1_u32(svwhilelt_b32_u64(80, maxCount), dst + 80, svshllb_n_u32(hha, 0));
     svst1_u32(svwhilelt_b32_u64(84, maxCount), dst + 84, svshllt_n_u32(hha, 0));
     svst1_u32(svwhilelt_b32_u64(88, maxCount), dst + 88, svshllb_n_u32(hhb, 0));
     svst1_u32(svwhilelt_b32_u64(92, maxCount), dst + 92, svshllt_n_u32(hhb, 0));

     hh0 = svmax_u16_x(vl128, hh0, hh1);
     hh2 = svmax_u16_x(vl128, hh2, hh3);
     hh4 = svmax_u16_x(vl128, hh4, hh5);
     hh6 = svmax_u16_x(vl128, hh6, hh7);
     hh8 = svmax_u16_x(vl128, hh8, hh9);
     hha = svmax_u16_x(vl128, hha, hhb);
     hh0 = svmax_u16_x(vl128, hh0, hh2);
     hh4 = svmax_u16_x(vl128, hh4, hh6);
     hh8 = svmax_u16_x(vl128, hh8, hha);
     hh0 = svmax_u16_x(vl128, hh0, hh4);
     hh8 = svmax_u16_x(vl128, hh8, histmax);
     return svmax_u16_x(vl128, hh0, hh8);
 }

 static size_t HIST_count_sve2(unsigned* count, unsigned* maxSymbolValuePtr,
                               const void* source, size_t sourceSize,
                               HIST_checkInput_e check)
 {
     const BYTE* ip = (const BYTE*)source;
     const size_t maxCount = *maxSymbolValuePtr + 1;

     assert(*maxSymbolValuePtr <= 255);
     if (!sourceSize) {
         ZSTD_memset(count, 0, maxCount * sizeof(*count));
         *maxSymbolValuePtr = 0;
         return 0;
     }

     {   const svbool_t vl128 = svptrue_pat_b8(SV_VL16);
         const svuint8_t c0 = svreinterpret_u8(svindex_u32(0x0C040800, 0x01010101));
         const svuint8_t c1 = svadd_n_u8_x(vl128, c0, 16);
         const svuint8_t c2 = svadd_n_u8_x(vl128, c0, 32);
         const svuint8_t c3 = svadd_n_u8_x(vl128, c1, 32);

         svuint8_t symbolMax = svdup_n_u8(0);
         svuint16_t hh0 = svdup_n_u16(0);
         svuint16_t hh1 = svdup_n_u16(0);
         svuint16_t hh2 = svdup_n_u16(0);
         svuint16_t hh3 = svdup_n_u16(0);
         svuint16_t hh4 = svdup_n_u16(0);
         svuint16_t hh5 = svdup_n_u16(0);
         svuint16_t hh6 = svdup_n_u16(0);
         svuint16_t hh7 = svdup_n_u16(0);
         svuint16_t max;
         size_t maxSymbolValue;

         size_t i = 0;
         while (i < sourceSize) {
             /* We can only accumulate 15 (15 * 16 <= 255) iterations of
              * histogram in 8-bit accumulators! */
             const size_t size240 = min_size(i + 240, sourceSize);

             svbool_t pred = svwhilelt_b8_u64(i, sourceSize);
             svuint8_t c = svld1rq_u8(pred, ip + i);
             svuint8_t h0 = svhistseg_u8(c0, c);
             svuint8_t h1 = svhistseg_u8(c1, c);
             svuint8_t h2 = svhistseg_u8(c2, c);
             svuint8_t h3 = svhistseg_u8(c3, c);
             symbolMax = svmax_u8_x(vl128, symbolMax, c);

             for (i += 16; i < size240; i += 16) {
                 pred = svwhilelt_b8_u64(i, sourceSize);
                 c = svld1rq_u8(pred, ip + i);
                 h0 = svadd_u8_x(vl128, h0, svhistseg_u8(c0, c));
                 h1 = svadd_u8_x(vl128, h1, svhistseg_u8(c1, c));
                 h2 = svadd_u8_x(vl128, h2, svhistseg_u8(c2, c));
                 h3 = svadd_u8_x(vl128, h3, svhistseg_u8(c3, c));
                 symbolMax = svmax_u8_x(vl128, symbolMax, c);
             }

             hh0 = svaddwb_u16(hh0, h0);
             hh1 = svaddwt_u16(hh1, h0);
             hh2 = svaddwb_u16(hh2, h1);
             hh3 = svaddwt_u16(hh3, h1);
             hh4 = svaddwb_u16(hh4, h2);
             hh5 = svaddwt_u16(hh5, h2);
             hh6 = svaddwb_u16(hh6, h3);
             hh7 = svaddwt_u16(hh7, h3);
         }
         maxSymbolValue = svmaxv_u8(vl128, symbolMax);

         if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall);
         *maxSymbolValuePtr = maxSymbolValue;

         /* If the buffer size is not divisible by 16, the last elements of the final
          * vector register read will be zeros, and these elements must be subtracted
          * from the histogram.
          */
         hh0 = svsub_n_u16_m(svptrue_pat_b32(SV_VL1), hh0, -sourceSize & 15);

         svst1_u32(svwhilelt_b32_u64( 0, maxCount), count +  0, svshllb_n_u32(hh0, 0));
         svst1_u32(svwhilelt_b32_u64( 4, maxCount), count +  4, svshllt_n_u32(hh0, 0));
         svst1_u32(svwhilelt_b32_u64( 8, maxCount), count +  8, svshllb_n_u32(hh1, 0));
         svst1_u32(svwhilelt_b32_u64(12, maxCount), count + 12, svshllt_n_u32(hh1, 0));
         svst1_u32(svwhilelt_b32_u64(16, maxCount), count + 16, svshllb_n_u32(hh2, 0));
         svst1_u32(svwhilelt_b32_u64(20, maxCount), count + 20, svshllt_n_u32(hh2, 0));
         svst1_u32(svwhilelt_b32_u64(24, maxCount), count + 24, svshllb_n_u32(hh3, 0));
         svst1_u32(svwhilelt_b32_u64(28, maxCount), count + 28, svshllt_n_u32(hh3, 0));
         svst1_u32(svwhilelt_b32_u64(32, maxCount), count + 32, svshllb_n_u32(hh4, 0));
         svst1_u32(svwhilelt_b32_u64(36, maxCount), count + 36, svshllt_n_u32(hh4, 0));
         svst1_u32(svwhilelt_b32_u64(40, maxCount), count + 40, svshllb_n_u32(hh5, 0));
         svst1_u32(svwhilelt_b32_u64(44, maxCount), count + 44, svshllt_n_u32(hh5, 0));
         svst1_u32(svwhilelt_b32_u64(48, maxCount), count + 48, svshllb_n_u32(hh6, 0));
         svst1_u32(svwhilelt_b32_u64(52, maxCount), count + 52, svshllt_n_u32(hh6, 0));
         svst1_u32(svwhilelt_b32_u64(56, maxCount), count + 56, svshllb_n_u32(hh7, 0));
         svst1_u32(svwhilelt_b32_u64(60, maxCount), count + 60, svshllt_n_u32(hh7, 0));

         hh0 = svmax_u16_x(vl128, hh0, hh1);
         hh2 = svmax_u16_x(vl128, hh2, hh3);
         hh4 = svmax_u16_x(vl128, hh4, hh5);
         hh6 = svmax_u16_x(vl128, hh6, hh7);
         hh0 = svmax_u16_x(vl128, hh0, hh2);
         hh4 = svmax_u16_x(vl128, hh4, hh6);
         max = svmax_u16_x(vl128, hh0, hh4);

         maxSymbolValue = min_size(maxSymbolValue, maxCount);
         if (maxSymbolValue >= 64) {
             const svuint8_t c4 = svadd_n_u8_x(vl128, c0,  64);
             const svuint8_t c5 = svadd_n_u8_x(vl128, c1,  64);
             const svuint8_t c6 = svadd_n_u8_x(vl128, c2,  64);
             const svuint8_t c7 = svadd_n_u8_x(vl128, c3,  64);
             const svuint8_t c8 = svadd_n_u8_x(vl128, c0, 128);
             const svuint8_t c9 = svadd_n_u8_x(vl128, c1, 128);

             max = HIST_count_6_sve2(ip, sourceSize, count + 64, c4, c5, c6, c7,
                                     c8, c9, max, maxCount - 64);

             if (maxSymbolValue >= 160) {
                 const svuint8_t ca = svadd_n_u8_x(vl128, c2, 128);
                 const svuint8_t cb = svadd_n_u8_x(vl128, c3, 128);
                 const svuint8_t cc = svadd_n_u8_x(vl128, c4, 128);
                 const svuint8_t cd = svadd_n_u8_x(vl128, c5, 128);
                 const svuint8_t ce = svadd_n_u8_x(vl128, c6, 128);
                 const svuint8_t cf = svadd_n_u8_x(vl128, c7, 128);

                 max = HIST_count_6_sve2(ip, sourceSize, count + 160, ca, cb, cc,
                                         cd, ce, cf, max, maxCount - 160);
             } else if (maxCount > 160) {
                 ZSTD_memset(count + 160, 0, (maxCount - 160) * sizeof(*count));
             }
         } else if (maxCount > 64) {
             ZSTD_memset(count + 64, 0, (maxCount - 64) * sizeof(*count));
         }

         return svmaxv_u16(vl128, max);
     }
 }
 #endif

 /* HIST_count_parallel_wksp() :
  * store histogram into 4 intermediate tables, recombined at the end.
  * this design makes better use of OoO cpus,
  * and is noticeably faster when some values are heavily repeated.
  * But it needs some additional workspace for intermediate tables.
  * `workSpace` must be a U32 table of size >= HIST_WKSP_SIZE_U32.
  * @return : largest histogram frequency,
  *           or an error code (notably when histogram's alphabet is larger than *maxSymbolValuePtr) */
 static UNUSED_ATTR
 size_t HIST_count_parallel_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
                                 const void* source, size_t sourceSize,
                                 HIST_checkInput_e check,
                                 U32* const workSpace)
 {
     const BYTE* ip = (const BYTE*)source;
     const BYTE* const iend = ip+sourceSize;
     size_t const countSize = (*maxSymbolValuePtr + 1) * sizeof(*count);
     unsigned max=0;
     U32* const Counting1 = workSpace;
     U32* const Counting2 = Counting1 + 256;
     U32* const Counting3 = Counting2 + 256;
     U32* const Counting4 = Counting3 + 256;

     /* safety checks */
     assert(*maxSymbolValuePtr <= 255);
     if (!sourceSize) {
         ZSTD_memset(count, 0, countSize);
         *maxSymbolValuePtr = 0;
         return 0;
     }
     ZSTD_memset(workSpace, 0, 4*256*sizeof(unsigned));

     /* by stripes of 16 bytes */
     {   U32 cached = MEM_read32(ip); ip += 4;
         while (ip < iend-15) {
             U32 c = cached; cached = MEM_read32(ip); ip += 4;
             Counting1[(BYTE) c     ]++;
             Counting2[(BYTE)(c>>8) ]++;
             Counting3[(BYTE)(c>>16)]++;
             Counting4[       c>>24 ]++;
             c = cached; cached = MEM_read32(ip); ip += 4;
             Counting1[(BYTE) c     ]++;
             Counting2[(BYTE)(c>>8) ]++;
             Counting3[(BYTE)(c>>16)]++;
             Counting4[       c>>24 ]++;
             c = cached; cached = MEM_read32(ip); ip += 4;
             Counting1[(BYTE) c     ]++;
             Counting2[(BYTE)(c>>8) ]++;
             Counting3[(BYTE)(c>>16)]++;
             Counting4[       c>>24 ]++;
             c = cached; cached = MEM_read32(ip); ip += 4;
             Counting1[(BYTE) c     ]++;
             Counting2[(BYTE)(c>>8) ]++;
             Counting3[(BYTE)(c>>16)]++;
             Counting4[       c>>24 ]++;
         }
         ip-=4;
     }

     /* finish last symbols */
     while (ip<iend) Counting1[*ip++]++;

     {   U32 s;
         for (s=0; s<256; s++) {
             Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
             if (Counting1[s] > max) max = Counting1[s];
     }   }

     {   unsigned maxSymbolValue = 255;
         while (!Counting1[maxSymbolValue]) maxSymbolValue--;
         if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall);
         *maxSymbolValuePtr = maxSymbolValue;
         ZSTD_memmove(count, Counting1, countSize);   /* in case count & Counting1 are overlapping */
     }
     return (size_t)max;
 }

 /* HIST_countFast_wksp() :
  * Same as HIST_countFast(), but using an externally provided scratch buffer.
  * `workSpace` is a writable buffer which must be 4-bytes aligned,
  * `workSpaceSize` must be >= HIST_WKSP_SIZE
  */
 size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
                           const void* source, size_t sourceSize,
                           void* workSpace, size_t workSpaceSize)
 {
     if (sourceSize < HIST_FAST_THRESHOLD) /* heuristic threshold */
         return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
 #if defined(ZSTD_ARCH_ARM_SVE2)
     (void)workSpace;
     (void)workSpaceSize;
     return HIST_count_sve2(count, maxSymbolValuePtr, source, sourceSize, trustInput);
 #else
     if ((size_t)workSpace & 3) return ERROR(GENERIC);  /* must be aligned on 4-bytes boundaries */
     if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
     return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
 #endif
 }

 /* HIST_count_wksp() :
  * Same as HIST_count(), but using an externally provided scratch buffer.
  * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */
 size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
                        const void* source, size_t sourceSize,
                        void* workSpace, size_t workSpaceSize)
 {
 #if defined(ZSTD_ARCH_ARM_SVE2)
     if (*maxSymbolValuePtr < 255)
         return HIST_count_sve2(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue);
 #else
     if ((size_t)workSpace & 3) return ERROR(GENERIC);  /* must be aligned on 4-bytes boundaries */
     if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
     if (*maxSymbolValuePtr < 255)
         return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
 #endif
     *maxSymbolValuePtr = 255;
     return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
 }

 #ifndef ZSTD_NO_UNUSED_FUNCTIONS
 /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
 size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
                      const void* source, size_t sourceSize)
 {
     unsigned tmpCounters[HIST_WKSP_SIZE_U32];
     return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters));
 }

 size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr,
                  const void* src, size_t srcSize)
 {
     unsigned tmpCounters[HIST_WKSP_SIZE_U32];
     return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters));
 }
 #endif
	/* ******************************************************************
	* hist : Histogram functions
	* part of Finite State Entropy project
	* Copyright (c) Meta Platforms, Inc. and affiliates.
	*
	* You can contact the author at :
	* - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
	* - Public forum : https://groups.google.com/forum/#!forum/lz4c
	*
	* This source code is licensed under both the BSD-style license (found in the
	* LICENSE file in the root directory of this source tree) and the GPLv2 (found
	* in the COPYING file in the root directory of this source tree).
	* You may select, at your option, one of the above-listed licenses.
	****************************************************************** */

	/* --- dependencies --- */
	#include "../common/mem.h" /* U32, BYTE, etc. */
	#include "../common/debug.h" /* assert, DEBUGLOG */
	#include "../common/error_private.h" /* ERROR */
	#include "hist.h"

	#if defined(ZSTD_ARCH_ARM_SVE2)
	#define HIST_FAST_THRESHOLD 500
	#else
	#define HIST_FAST_THRESHOLD 1500
	#endif


	/* --- Error management --- */
	unsigned HIST_isError(size_t code) { return ERR_isError(code); }

	/-*************************************************************
	* Histogram functions
	****************************************************************/
	void HIST_add(unsigned* count, const void* src, size_t srcSize)
	{
	const BYTE* ip = (const BYTE*)src;
	const BYTE* const end = ip + srcSize;

	while (ip<end) {
	count[*ip++]++;
	}
	}

	unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
	const void* src, size_t srcSize)
	{
	const BYTE* ip = (const BYTE*)src;
	const BYTE* const end = ip + srcSize;
	unsigned maxSymbolValue = *maxSymbolValuePtr;
	unsigned largestCount=0;

	ZSTD_memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
	if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }

	while (ip<end) {
	assert(*ip <= maxSymbolValue);
	count[*ip++]++;
	}

	while (!count[maxSymbolValue]) maxSymbolValue--;
	*maxSymbolValuePtr = maxSymbolValue;

	{ U32 s;
	for (s=0; s<=maxSymbolValue; s++)
	if (count[s] > largestCount) largestCount = count[s];
	}

	return largestCount;
	}

	typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e;

	#if defined(ZSTD_ARCH_ARM_SVE2)
	FORCE_INLINE_TEMPLATE size_t min_size(size_t a, size_t b) { return a < b ? a : b; }

	static
	svuint16_t HIST_count_6_sve2(const BYTE* const src, size_t size, U32* const dst,
	const svuint8_t c0, const svuint8_t c1,
	const svuint8_t c2, const svuint8_t c3,
	const svuint8_t c4, const svuint8_t c5,
	const svuint16_t histmax, size_t maxCount)
	{
	const svbool_t vl128 = svptrue_pat_b8(SV_VL16);
	svuint16_t hh0 = svdup_n_u16(0);
	svuint16_t hh1 = svdup_n_u16(0);
	svuint16_t hh2 = svdup_n_u16(0);
	svuint16_t hh3 = svdup_n_u16(0);
	svuint16_t hh4 = svdup_n_u16(0);
	svuint16_t hh5 = svdup_n_u16(0);
	svuint16_t hh6 = svdup_n_u16(0);
	svuint16_t hh7 = svdup_n_u16(0);
	svuint16_t hh8 = svdup_n_u16(0);
	svuint16_t hh9 = svdup_n_u16(0);
	svuint16_t hha = svdup_n_u16(0);
	svuint16_t hhb = svdup_n_u16(0);

	size_t i = 0;
	while (i < size) {
	/* We can only accumulate 15 (15 * 16 <= 255) iterations of histogram
	* in 8-bit accumulators! */
	const size_t size240 = min_size(i + 240, size);

	svbool_t pred = svwhilelt_b8_u64(i, size);
	svuint8_t c = svld1rq_u8(pred, src + i);
	svuint8_t h0 = svhistseg_u8(c0, c);
	svuint8_t h1 = svhistseg_u8(c1, c);
	svuint8_t h2 = svhistseg_u8(c2, c);
	svuint8_t h3 = svhistseg_u8(c3, c);
	svuint8_t h4 = svhistseg_u8(c4, c);
	svuint8_t h5 = svhistseg_u8(c5, c);

	for (i += 16; i < size240; i += 16) {
	pred = svwhilelt_b8_u64(i, size);
	c = svld1rq_u8(pred, src + i);
	h0 = svadd_u8_x(vl128, h0, svhistseg_u8(c0, c));
	h1 = svadd_u8_x(vl128, h1, svhistseg_u8(c1, c));
	h2 = svadd_u8_x(vl128, h2, svhistseg_u8(c2, c));
	h3 = svadd_u8_x(vl128, h3, svhistseg_u8(c3, c));
	h4 = svadd_u8_x(vl128, h4, svhistseg_u8(c4, c));
	h5 = svadd_u8_x(vl128, h5, svhistseg_u8(c5, c));
	}

	hh0 = svaddwb_u16(hh0, h0);
	hh1 = svaddwt_u16(hh1, h0);
	hh2 = svaddwb_u16(hh2, h1);
	hh3 = svaddwt_u16(hh3, h1);
	hh4 = svaddwb_u16(hh4, h2);
	hh5 = svaddwt_u16(hh5, h2);
	hh6 = svaddwb_u16(hh6, h3);
	hh7 = svaddwt_u16(hh7, h3);
	hh8 = svaddwb_u16(hh8, h4);
	hh9 = svaddwt_u16(hh9, h4);
	hha = svaddwb_u16(hha, h5);
	hhb = svaddwt_u16(hhb, h5);
	}

	svst1_u32(svwhilelt_b32_u64( 0, maxCount), dst + 0, svshllb_n_u32(hh0, 0));
	svst1_u32(svwhilelt_b32_u64( 4, maxCount), dst + 4, svshllt_n_u32(hh0, 0));
	svst1_u32(svwhilelt_b32_u64( 8, maxCount), dst + 8, svshllb_n_u32(hh1, 0));
	svst1_u32(svwhilelt_b32_u64(12, maxCount), dst + 12, svshllt_n_u32(hh1, 0));
	svst1_u32(svwhilelt_b32_u64(16, maxCount), dst + 16, svshllb_n_u32(hh2, 0));
	svst1_u32(svwhilelt_b32_u64(20, maxCount), dst + 20, svshllt_n_u32(hh2, 0));
	svst1_u32(svwhilelt_b32_u64(24, maxCount), dst + 24, svshllb_n_u32(hh3, 0));
	svst1_u32(svwhilelt_b32_u64(28, maxCount), dst + 28, svshllt_n_u32(hh3, 0));
	svst1_u32(svwhilelt_b32_u64(32, maxCount), dst + 32, svshllb_n_u32(hh4, 0));
	svst1_u32(svwhilelt_b32_u64(36, maxCount), dst + 36, svshllt_n_u32(hh4, 0));
	svst1_u32(svwhilelt_b32_u64(40, maxCount), dst + 40, svshllb_n_u32(hh5, 0));
	svst1_u32(svwhilelt_b32_u64(44, maxCount), dst + 44, svshllt_n_u32(hh5, 0));
	svst1_u32(svwhilelt_b32_u64(48, maxCount), dst + 48, svshllb_n_u32(hh6, 0));
	svst1_u32(svwhilelt_b32_u64(52, maxCount), dst + 52, svshllt_n_u32(hh6, 0));
	svst1_u32(svwhilelt_b32_u64(56, maxCount), dst + 56, svshllb_n_u32(hh7, 0));
	svst1_u32(svwhilelt_b32_u64(60, maxCount), dst + 60, svshllt_n_u32(hh7, 0));
	svst1_u32(svwhilelt_b32_u64(64, maxCount), dst + 64, svshllb_n_u32(hh8, 0));
	svst1_u32(svwhilelt_b32_u64(68, maxCount), dst + 68, svshllt_n_u32(hh8, 0));
	svst1_u32(svwhilelt_b32_u64(72, maxCount), dst + 72, svshllb_n_u32(hh9, 0));
	svst1_u32(svwhilelt_b32_u64(76, maxCount), dst + 76, svshllt_n_u32(hh9, 0));
	svst1_u32(svwhilelt_b32_u64(80, maxCount), dst + 80, svshllb_n_u32(hha, 0));
	svst1_u32(svwhilelt_b32_u64(84, maxCount), dst + 84, svshllt_n_u32(hha, 0));
	svst1_u32(svwhilelt_b32_u64(88, maxCount), dst + 88, svshllb_n_u32(hhb, 0));
	svst1_u32(svwhilelt_b32_u64(92, maxCount), dst + 92, svshllt_n_u32(hhb, 0));

	hh0 = svmax_u16_x(vl128, hh0, hh1);
	hh2 = svmax_u16_x(vl128, hh2, hh3);
	hh4 = svmax_u16_x(vl128, hh4, hh5);
	hh6 = svmax_u16_x(vl128, hh6, hh7);
	hh8 = svmax_u16_x(vl128, hh8, hh9);
	hha = svmax_u16_x(vl128, hha, hhb);
	hh0 = svmax_u16_x(vl128, hh0, hh2);
	hh4 = svmax_u16_x(vl128, hh4, hh6);
	hh8 = svmax_u16_x(vl128, hh8, hha);
	hh0 = svmax_u16_x(vl128, hh0, hh4);
	hh8 = svmax_u16_x(vl128, hh8, histmax);
	return svmax_u16_x(vl128, hh0, hh8);
	}

	static size_t HIST_count_sve2(unsigned* count, unsigned* maxSymbolValuePtr,
	const void* source, size_t sourceSize,
	HIST_checkInput_e check)
	{
	const BYTE* ip = (const BYTE*)source;
	const size_t maxCount = *maxSymbolValuePtr + 1;

	assert(*maxSymbolValuePtr <= 255);
	if (!sourceSize) {
	ZSTD_memset(count, 0, maxCount * sizeof(*count));
	*maxSymbolValuePtr = 0;
	return 0;
	}

	{ const svbool_t vl128 = svptrue_pat_b8(SV_VL16);
	const svuint8_t c0 = svreinterpret_u8(svindex_u32(0x0C040800, 0x01010101));
	const svuint8_t c1 = svadd_n_u8_x(vl128, c0, 16);
	const svuint8_t c2 = svadd_n_u8_x(vl128, c0, 32);
	const svuint8_t c3 = svadd_n_u8_x(vl128, c1, 32);

	svuint8_t symbolMax = svdup_n_u8(0);
	svuint16_t hh0 = svdup_n_u16(0);
	svuint16_t hh1 = svdup_n_u16(0);
	svuint16_t hh2 = svdup_n_u16(0);
	svuint16_t hh3 = svdup_n_u16(0);
	svuint16_t hh4 = svdup_n_u16(0);
	svuint16_t hh5 = svdup_n_u16(0);
	svuint16_t hh6 = svdup_n_u16(0);
	svuint16_t hh7 = svdup_n_u16(0);
	svuint16_t max;
	size_t maxSymbolValue;

	size_t i = 0;
	while (i < sourceSize) {
	/* We can only accumulate 15 (15 * 16 <= 255) iterations of
	* histogram in 8-bit accumulators! */
	const size_t size240 = min_size(i + 240, sourceSize);

	svbool_t pred = svwhilelt_b8_u64(i, sourceSize);
	svuint8_t c = svld1rq_u8(pred, ip + i);
	svuint8_t h0 = svhistseg_u8(c0, c);
	svuint8_t h1 = svhistseg_u8(c1, c);
	svuint8_t h2 = svhistseg_u8(c2, c);
	svuint8_t h3 = svhistseg_u8(c3, c);
	symbolMax = svmax_u8_x(vl128, symbolMax, c);

	for (i += 16; i < size240; i += 16) {
	pred = svwhilelt_b8_u64(i, sourceSize);
	c = svld1rq_u8(pred, ip + i);
	h0 = svadd_u8_x(vl128, h0, svhistseg_u8(c0, c));
	h1 = svadd_u8_x(vl128, h1, svhistseg_u8(c1, c));
	h2 = svadd_u8_x(vl128, h2, svhistseg_u8(c2, c));
	h3 = svadd_u8_x(vl128, h3, svhistseg_u8(c3, c));
	symbolMax = svmax_u8_x(vl128, symbolMax, c);
	}

	hh0 = svaddwb_u16(hh0, h0);
	hh1 = svaddwt_u16(hh1, h0);
	hh2 = svaddwb_u16(hh2, h1);
	hh3 = svaddwt_u16(hh3, h1);
	hh4 = svaddwb_u16(hh4, h2);
	hh5 = svaddwt_u16(hh5, h2);
	hh6 = svaddwb_u16(hh6, h3);
	hh7 = svaddwt_u16(hh7, h3);
	}
	maxSymbolValue = svmaxv_u8(vl128, symbolMax);

	if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall);
	*maxSymbolValuePtr = maxSymbolValue;

	/* If the buffer size is not divisible by 16, the last elements of the final
	* vector register read will be zeros, and these elements must be subtracted
	* from the histogram.
	*/
	hh0 = svsub_n_u16_m(svptrue_pat_b32(SV_VL1), hh0, -sourceSize & 15);

	svst1_u32(svwhilelt_b32_u64( 0, maxCount), count + 0, svshllb_n_u32(hh0, 0));
	svst1_u32(svwhilelt_b32_u64( 4, maxCount), count + 4, svshllt_n_u32(hh0, 0));
	svst1_u32(svwhilelt_b32_u64( 8, maxCount), count + 8, svshllb_n_u32(hh1, 0));
	svst1_u32(svwhilelt_b32_u64(12, maxCount), count + 12, svshllt_n_u32(hh1, 0));
	svst1_u32(svwhilelt_b32_u64(16, maxCount), count + 16, svshllb_n_u32(hh2, 0));
	svst1_u32(svwhilelt_b32_u64(20, maxCount), count + 20, svshllt_n_u32(hh2, 0));
	svst1_u32(svwhilelt_b32_u64(24, maxCount), count + 24, svshllb_n_u32(hh3, 0));
	svst1_u32(svwhilelt_b32_u64(28, maxCount), count + 28, svshllt_n_u32(hh3, 0));
	svst1_u32(svwhilelt_b32_u64(32, maxCount), count + 32, svshllb_n_u32(hh4, 0));
	svst1_u32(svwhilelt_b32_u64(36, maxCount), count + 36, svshllt_n_u32(hh4, 0));
	svst1_u32(svwhilelt_b32_u64(40, maxCount), count + 40, svshllb_n_u32(hh5, 0));
	svst1_u32(svwhilelt_b32_u64(44, maxCount), count + 44, svshllt_n_u32(hh5, 0));
	svst1_u32(svwhilelt_b32_u64(48, maxCount), count + 48, svshllb_n_u32(hh6, 0));
	svst1_u32(svwhilelt_b32_u64(52, maxCount), count + 52, svshllt_n_u32(hh6, 0));
	svst1_u32(svwhilelt_b32_u64(56, maxCount), count + 56, svshllb_n_u32(hh7, 0));
	svst1_u32(svwhilelt_b32_u64(60, maxCount), count + 60, svshllt_n_u32(hh7, 0));

	hh0 = svmax_u16_x(vl128, hh0, hh1);
	hh2 = svmax_u16_x(vl128, hh2, hh3);
	hh4 = svmax_u16_x(vl128, hh4, hh5);
	hh6 = svmax_u16_x(vl128, hh6, hh7);
	hh0 = svmax_u16_x(vl128, hh0, hh2);
	hh4 = svmax_u16_x(vl128, hh4, hh6);
	max = svmax_u16_x(vl128, hh0, hh4);

	maxSymbolValue = min_size(maxSymbolValue, maxCount);
	if (maxSymbolValue >= 64) {
	const svuint8_t c4 = svadd_n_u8_x(vl128, c0, 64);
	const svuint8_t c5 = svadd_n_u8_x(vl128, c1, 64);
	const svuint8_t c6 = svadd_n_u8_x(vl128, c2, 64);
	const svuint8_t c7 = svadd_n_u8_x(vl128, c3, 64);
	const svuint8_t c8 = svadd_n_u8_x(vl128, c0, 128);
	const svuint8_t c9 = svadd_n_u8_x(vl128, c1, 128);

	max = HIST_count_6_sve2(ip, sourceSize, count + 64, c4, c5, c6, c7,
	c8, c9, max, maxCount - 64);

	if (maxSymbolValue >= 160) {
	const svuint8_t ca = svadd_n_u8_x(vl128, c2, 128);
	const svuint8_t cb = svadd_n_u8_x(vl128, c3, 128);
	const svuint8_t cc = svadd_n_u8_x(vl128, c4, 128);
	const svuint8_t cd = svadd_n_u8_x(vl128, c5, 128);
	const svuint8_t ce = svadd_n_u8_x(vl128, c6, 128);
	const svuint8_t cf = svadd_n_u8_x(vl128, c7, 128);

	max = HIST_count_6_sve2(ip, sourceSize, count + 160, ca, cb, cc,
	cd, ce, cf, max, maxCount - 160);
	} else if (maxCount > 160) {
	ZSTD_memset(count + 160, 0, (maxCount - 160) * sizeof(*count));
	}
	} else if (maxCount > 64) {
	ZSTD_memset(count + 64, 0, (maxCount - 64) * sizeof(*count));
	}

	return svmaxv_u16(vl128, max);
	}
	}
	#endif

	/* HIST_count_parallel_wksp() :
	* store histogram into 4 intermediate tables, recombined at the end.
	* this design makes better use of OoO cpus,
	* and is noticeably faster when some values are heavily repeated.
	* But it needs some additional workspace for intermediate tables.
	* `workSpace` must be a U32 table of size >= HIST_WKSP_SIZE_U32.
	* @return : largest histogram frequency,
	* or an error code (notably when histogram's alphabet is larger than maxSymbolValuePtr) /
	static UNUSED_ATTR
	size_t HIST_count_parallel_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
	const void* source, size_t sourceSize,
	HIST_checkInput_e check,
	U32* const workSpace)
	{
	const BYTE* ip = (const BYTE*)source;
	const BYTE* const iend = ip+sourceSize;
	size_t const countSize = (maxSymbolValuePtr + 1) sizeof(*count);
	unsigned max=0;
	U32* const Counting1 = workSpace;
	U32* const Counting2 = Counting1 + 256;
	U32* const Counting3 = Counting2 + 256;
	U32* const Counting4 = Counting3 + 256;

	/* safety checks */
	assert(*maxSymbolValuePtr <= 255);
	if (!sourceSize) {
	ZSTD_memset(count, 0, countSize);
	*maxSymbolValuePtr = 0;
	return 0;
	}
	ZSTD_memset(workSpace, 0, 4256sizeof(unsigned));

	/* by stripes of 16 bytes */
	{ U32 cached = MEM_read32(ip); ip += 4;
	while (ip < iend-15) {
	U32 c = cached; cached = MEM_read32(ip); ip += 4;
	Counting1[(BYTE) c ]++;
	Counting2[(BYTE)(c>>8) ]++;
	Counting3[(BYTE)(c>>16)]++;
	Counting4[ c>>24 ]++;
	c = cached; cached = MEM_read32(ip); ip += 4;
	Counting1[(BYTE) c ]++;
	Counting2[(BYTE)(c>>8) ]++;
	Counting3[(BYTE)(c>>16)]++;
	Counting4[ c>>24 ]++;
	c = cached; cached = MEM_read32(ip); ip += 4;
	Counting1[(BYTE) c ]++;
	Counting2[(BYTE)(c>>8) ]++;
	Counting3[(BYTE)(c>>16)]++;
	Counting4[ c>>24 ]++;
	c = cached; cached = MEM_read32(ip); ip += 4;
	Counting1[(BYTE) c ]++;
	Counting2[(BYTE)(c>>8) ]++;
	Counting3[(BYTE)(c>>16)]++;
	Counting4[ c>>24 ]++;
	}
	ip-=4;
	}

	/* finish last symbols */
	while (ip<iend) Counting1[*ip++]++;

	{ U32 s;
	for (s=0; s<256; s++) {
	Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
	if (Counting1[s] > max) max = Counting1[s];
	} }

	{ unsigned maxSymbolValue = 255;
	while (!Counting1[maxSymbolValue]) maxSymbolValue--;
	if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall);
	*maxSymbolValuePtr = maxSymbolValue;
	ZSTD_memmove(count, Counting1, countSize); /* in case count & Counting1 are overlapping */
	}
	return (size_t)max;
	}

	/* HIST_countFast_wksp() :
	* Same as HIST_countFast(), but using an externally provided scratch buffer.
	* `workSpace` is a writable buffer which must be 4-bytes aligned,
	* `workSpaceSize` must be >= HIST_WKSP_SIZE
	*/
	size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
	const void* source, size_t sourceSize,
	void* workSpace, size_t workSpaceSize)
	{
	if (sourceSize < HIST_FAST_THRESHOLD) /* heuristic threshold */
	return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
	#if defined(ZSTD_ARCH_ARM_SVE2)
	(void)workSpace;
	(void)workSpaceSize;
	return HIST_count_sve2(count, maxSymbolValuePtr, source, sourceSize, trustInput);
	#else
	if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
	if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
	return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
	#endif
	}

	/* HIST_count_wksp() :
	* Same as HIST_count(), but using an externally provided scratch buffer.
	* `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */
	size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
	const void* source, size_t sourceSize,
	void* workSpace, size_t workSpaceSize)
	{
	#if defined(ZSTD_ARCH_ARM_SVE2)
	if (*maxSymbolValuePtr < 255)
	return HIST_count_sve2(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue);
	#else
	if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
	if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
	if (*maxSymbolValuePtr < 255)
	return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
	#endif
	*maxSymbolValuePtr = 255;
	return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
	}

	#ifndef ZSTD_NO_UNUSED_FUNCTIONS
	/* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
	size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
	const void* source, size_t sourceSize)
	{
	unsigned tmpCounters[HIST_WKSP_SIZE_U32];
	return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters));
	}

	size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr,
	const void* src, size_t srcSize)
	{
	unsigned tmpCounters[HIST_WKSP_SIZE_U32];
	return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters));
	}
	#endif