bits.h

  1/* SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause */
  2/*
  3 * Copyright (c) Meta Platforms, Inc. and affiliates.
  4 * All rights reserved.
  5 *
  6 * This source code is licensed under both the BSD-style license (found in the
  7 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
  8 * in the COPYING file in the root directory of this source tree).
  9 * You may select, at your option, one of the above-listed licenses.
 10 */
 11
 12#ifndef ZSTD_BITS_H
 13#define ZSTD_BITS_H
 14
 15#include "mem.h"
 16
 17MEM_STATIC unsigned ZSTD_countTrailingZeros32_fallback(U32 val)
 18{
 19    assert(val != 0);
 20    {
 21        static const U32 DeBruijnBytePos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
 22                                                30, 22, 20, 15, 25, 17, 4, 8,
 23                                                31, 27, 13, 23, 21, 19, 16, 7,
 24                                                26, 12, 18, 6, 11, 5, 10, 9};
 25        return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >> 27];
 26    }
 27}
 28
 29MEM_STATIC unsigned ZSTD_countTrailingZeros32(U32 val)
 30{
 31    assert(val != 0);
 32#if (__GNUC__ >= 4)
 33    return (unsigned)__builtin_ctz(val);
 34#else
 35    return ZSTD_countTrailingZeros32_fallback(val);
 36#endif
 37}
 38
 39MEM_STATIC unsigned ZSTD_countLeadingZeros32_fallback(U32 val)
 40{
 41    assert(val != 0);
 42    {
 43        static const U32 DeBruijnClz[32] = {0, 9, 1, 10, 13, 21, 2, 29,
 44                                            11, 14, 16, 18, 22, 25, 3, 30,
 45                                            8, 12, 20, 28, 15, 17, 24, 7,
 46                                            19, 27, 23, 6, 26, 5, 4, 31};
 47        val |= val >> 1;
 48        val |= val >> 2;
 49        val |= val >> 4;
 50        val |= val >> 8;
 51        val |= val >> 16;
 52        return 31 - DeBruijnClz[(val * 0x07C4ACDDU) >> 27];
 53    }
 54}
 55
 56MEM_STATIC unsigned ZSTD_countLeadingZeros32(U32 val)
 57{
 58    assert(val != 0);
 59#if (__GNUC__ >= 4)
 60    return (unsigned)__builtin_clz(val);
 61#else
 62    return ZSTD_countLeadingZeros32_fallback(val);
 63#endif
 64}
 65
 66MEM_STATIC unsigned ZSTD_countTrailingZeros64(U64 val)
 67{
 68    assert(val != 0);
 69#if (__GNUC__ >= 4) && defined(__LP64__)
 70    return (unsigned)__builtin_ctzll(val);
 71#else
 72    {
 73        U32 mostSignificantWord = (U32)(val >> 32);
 74        U32 leastSignificantWord = (U32)val;
 75        if (leastSignificantWord == 0) {
 76            return 32 + ZSTD_countTrailingZeros32(mostSignificantWord);
 77        } else {
 78            return ZSTD_countTrailingZeros32(leastSignificantWord);
 79        }
 80    }
 81#endif
 82}
 83
 84MEM_STATIC unsigned ZSTD_countLeadingZeros64(U64 val)
 85{
 86    assert(val != 0);
 87#if (__GNUC__ >= 4)
 88    return (unsigned)(__builtin_clzll(val));
 89#else
 90    {
 91        U32 mostSignificantWord = (U32)(val >> 32);
 92        U32 leastSignificantWord = (U32)val;
 93        if (mostSignificantWord == 0) {
 94            return 32 + ZSTD_countLeadingZeros32(leastSignificantWord);
 95        } else {
 96            return ZSTD_countLeadingZeros32(mostSignificantWord);
 97        }
 98    }
 99#endif
100}
101
102MEM_STATIC unsigned ZSTD_NbCommonBytes(size_t val)
103{
104    if (MEM_isLittleEndian()) {
105        if (MEM_64bits()) {
106            return ZSTD_countTrailingZeros64((U64)val) >> 3;
107        } else {
108            return ZSTD_countTrailingZeros32((U32)val) >> 3;
109        }
110    } else {  /* Big Endian CPU */
111        if (MEM_64bits()) {
112            return ZSTD_countLeadingZeros64((U64)val) >> 3;
113        } else {
114            return ZSTD_countLeadingZeros32((U32)val) >> 3;
115        }
116    }
117}
118
119MEM_STATIC unsigned ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
120{
121    assert(val != 0);
122    return 31 - ZSTD_countLeadingZeros32(val);
123}
124
125/* ZSTD_rotateRight_*():
126 * Rotates a bitfield to the right by "count" bits.
127 * https://en.wikipedia.org/w/index.php?title=Circular_shift&oldid=991635599#Implementing_circular_shifts
128 */
129MEM_STATIC
130U64 ZSTD_rotateRight_U64(U64 const value, U32 count) {
131    assert(count < 64);
132    count &= 0x3F; /* for fickle pattern recognition */
133    return (value >> count) | (U64)(value << ((0U - count) & 0x3F));
134}
135
136MEM_STATIC
137U32 ZSTD_rotateRight_U32(U32 const value, U32 count) {
138    assert(count < 32);
139    count &= 0x1F; /* for fickle pattern recognition */
140    return (value >> count) | (U32)(value << ((0U - count) & 0x1F));
141}
142
143MEM_STATIC
144U16 ZSTD_rotateRight_U16(U16 const value, U32 count) {
145    assert(count < 16);
146    count &= 0x0F; /* for fickle pattern recognition */
147    return (value >> count) | (U16)(value << ((0U - count) & 0x0F));
148}
149
150#endif /* ZSTD_BITS_H */