Home | History | Annotate | Line # | Download | only in common 
      1 /*
      2  * Copyright (c) Meta Platforms, Inc. and affiliates.
      3  * All rights reserved.
      4  *
      5  * This source code is licensed under both the BSD-style license (found in the
      6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
      7  * in the COPYING file in the root directory of this source tree).
      8  * You may select, at your option, one of the above-listed licenses.
      9  */
     10 
     11 #ifndef ZSTD_BITS_H
     12 #define ZSTD_BITS_H
     13 
     14 #include "mem.h"
     15 
     16 MEM_STATIC unsigned ZSTD_countTrailingZeros32_fallback(U32 val)
     17 {
     18     assert(val != 0);
     19     {
     20         static const U32 DeBruijnBytePos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
     21                                                 30, 22, 20, 15, 25, 17, 4, 8,
     22                                                 31, 27, 13, 23, 21, 19, 16, 7,
     23                                                 26, 12, 18, 6, 11, 5, 10, 9};
     24         return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >> 27];
     25     }
     26 }
     27 
     28 MEM_STATIC unsigned ZSTD_countTrailingZeros32(U32 val)
     29 {
     30     assert(val != 0);
     31 #if defined(_MSC_VER)
     32 #  if STATIC_BMI2
     33     return (unsigned)_tzcnt_u32(val);
     34 #  else
     35     if (val != 0) {
     36         unsigned long r;
     37         _BitScanForward(&r, val);
     38         return (unsigned)r;
     39     } else {
     40         __assume(0); /* Should not reach this code path */
     41     }
     42 #  endif
     43 #elif defined(__GNUC__) && (__GNUC__ >= 4)
     44     return (unsigned)__builtin_ctz(val);
     45 #elif defined(__ICCARM__)
     46     return (unsigned)__builtin_ctz(val);
     47 #else
     48     return ZSTD_countTrailingZeros32_fallback(val);
     49 #endif
     50 }
     51 
     52 MEM_STATIC unsigned ZSTD_countLeadingZeros32_fallback(U32 val)
     53 {
     54     assert(val != 0);
     55     {
     56         static const U32 DeBruijnClz[32] = {0, 9, 1, 10, 13, 21, 2, 29,
     57                                             11, 14, 16, 18, 22, 25, 3, 30,
     58                                             8, 12, 20, 28, 15, 17, 24, 7,
     59                                             19, 27, 23, 6, 26, 5, 4, 31};
     60         val |= val >> 1;
     61         val |= val >> 2;
     62         val |= val >> 4;
     63         val |= val >> 8;
     64         val |= val >> 16;
     65         return 31 - DeBruijnClz[(val * 0x07C4ACDDU) >> 27];
     66     }
     67 }
     68 
     69 MEM_STATIC unsigned ZSTD_countLeadingZeros32(U32 val)
     70 {
     71     assert(val != 0);
     72 #if defined(_MSC_VER)
     73 #  if STATIC_BMI2
     74     return (unsigned)_lzcnt_u32(val);
     75 #  else
     76     if (val != 0) {
     77         unsigned long r;
     78         _BitScanReverse(&r, val);
     79         return (unsigned)(31 - r);
     80     } else {
     81         __assume(0); /* Should not reach this code path */
     82     }
     83 #  endif
     84 #elif defined(__GNUC__) && (__GNUC__ >= 4)
     85     return (unsigned)__builtin_clz(val);
     86 #elif defined(__ICCARM__)
     87     return (unsigned)__builtin_clz(val);
     88 #else
     89     return ZSTD_countLeadingZeros32_fallback(val);
     90 #endif
     91 }
     92 
     93 MEM_STATIC unsigned ZSTD_countTrailingZeros64(U64 val)
     94 {
     95     assert(val != 0);
     96 #if defined(_MSC_VER) && defined(_WIN64)
     97 #  if STATIC_BMI2
     98     return (unsigned)_tzcnt_u64(val);
     99 #  else
    100     if (val != 0) {
    101         unsigned long r;
    102         _BitScanForward64(&r, val);
    103         return (unsigned)r;
    104     } else {
    105         __assume(0); /* Should not reach this code path */
    106     }
    107 #  endif
    108 #elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(__LP64__)
    109     return (unsigned)__builtin_ctzll(val);
    110 #elif defined(__ICCARM__)
    111     return (unsigned)__builtin_ctzll(val);
    112 #else
    113     {
    114         U32 mostSignificantWord = (U32)(val >> 32);
    115         U32 leastSignificantWord = (U32)val;
    116         if (leastSignificantWord == 0) {
    117             return 32 + ZSTD_countTrailingZeros32(mostSignificantWord);
    118         } else {
    119             return ZSTD_countTrailingZeros32(leastSignificantWord);
    120         }
    121     }
    122 #endif
    123 }
    124 
    125 MEM_STATIC unsigned ZSTD_countLeadingZeros64(U64 val)
    126 {
    127     assert(val != 0);
    128 #if defined(_MSC_VER) && defined(_WIN64)
    129 #  if STATIC_BMI2
    130     return (unsigned)_lzcnt_u64(val);
    131 #  else
    132     if (val != 0) {
    133         unsigned long r;
    134         _BitScanReverse64(&r, val);
    135         return (unsigned)(63 - r);
    136     } else {
    137         __assume(0); /* Should not reach this code path */
    138     }
    139 #  endif
    140 #elif defined(__GNUC__) && (__GNUC__ >= 4)
    141     return (unsigned)(__builtin_clzll(val));
    142 #elif defined(__ICCARM__)
    143     return (unsigned)(__builtin_clzll(val));
    144 #else
    145     {
    146         U32 mostSignificantWord = (U32)(val >> 32);
    147         U32 leastSignificantWord = (U32)val;
    148         if (mostSignificantWord == 0) {
    149             return 32 + ZSTD_countLeadingZeros32(leastSignificantWord);
    150         } else {
    151             return ZSTD_countLeadingZeros32(mostSignificantWord);
    152         }
    153     }
    154 #endif
    155 }
    156 
    157 MEM_STATIC unsigned ZSTD_NbCommonBytes(size_t val)
    158 {
    159     if (MEM_isLittleEndian()) {
    160         if (MEM_64bits()) {
    161             return ZSTD_countTrailingZeros64((U64)val) >> 3;
    162         } else {
    163             return ZSTD_countTrailingZeros32((U32)val) >> 3;
    164         }
    165     } else {  /* Big Endian CPU */
    166         if (MEM_64bits()) {
    167             return ZSTD_countLeadingZeros64((U64)val) >> 3;
    168         } else {
    169             return ZSTD_countLeadingZeros32((U32)val) >> 3;
    170         }
    171     }
    172 }
    173 
    174 MEM_STATIC unsigned ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
    175 {
    176     assert(val != 0);
    177     return 31 - ZSTD_countLeadingZeros32(val);
    178 }
    179 
    180 /* ZSTD_rotateRight_*():
    181  * Rotates a bitfield to the right by "count" bits.
    182  * https://en.wikipedia.org/w/index.php?title=Circular_shift&oldid=991635599#Implementing_circular_shifts
    183  */
    184 MEM_STATIC
    185 U64 ZSTD_rotateRight_U64(U64 const value, U32 count) {
    186     assert(count < 64);
    187     count &= 0x3F; /* for fickle pattern recognition */
    188     return (value >> count) | (U64)(value << ((0U - count) & 0x3F));
    189 }
    190 
    191 MEM_STATIC
    192 U32 ZSTD_rotateRight_U32(U32 const value, U32 count) {
    193     assert(count < 32);
    194     count &= 0x1F; /* for fickle pattern recognition */
    195     return (value >> count) | (U32)(value << ((0U - count) & 0x1F));
    196 }
    197 
    198 MEM_STATIC
    199 U16 ZSTD_rotateRight_U16(U16 const value, U32 count) {
    200     assert(count < 16);
    201     count &= 0x0F; /* for fickle pattern recognition */
    202     return (value >> count) | (U16)(value << ((0U - count) & 0x0F));
    203 }
    204 
    205 #endif /* ZSTD_BITS_H */
    206