[pcsx_rearmed.git] / deps / libchdr / deps / zstd-1.5.5 / lib / common / bits.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 * All rights reserved.
 *
 * 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.
 */

#ifndef ZSTD_BITS_H
#define ZSTD_BITS_H

#include "mem.h"

MEM_STATIC unsigned ZSTD_countTrailingZeros32_fallback(U32 val)
{
    assert(val != 0);
    {
        static const U32 DeBruijnBytePos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
                                                30, 22, 20, 15, 25, 17, 4, 8,
                                                31, 27, 13, 23, 21, 19, 16, 7,
                                                26, 12, 18, 6, 11, 5, 10, 9};
        return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >> 27];
    }
}

MEM_STATIC unsigned ZSTD_countTrailingZeros32(U32 val)
{
    assert(val != 0);
#   if defined(_MSC_VER)
#       if STATIC_BMI2 == 1
            return (unsigned)_tzcnt_u32(val);
#       else
            if (val != 0) {
                unsigned long r;
                _BitScanForward(&r, val);
                return (unsigned)r;
            } else {
                /* Should not reach this code path */
                __assume(0);
            }
#       endif
#   elif defined(__GNUC__) && (__GNUC__ >= 4)
        return (unsigned)__builtin_ctz(val);
#   else
        return ZSTD_countTrailingZeros32_fallback(val);
#   endif
}

MEM_STATIC unsigned ZSTD_countLeadingZeros32_fallback(U32 val) {
    assert(val != 0);
    {
        static const U32 DeBruijnClz[32] = {0, 9, 1, 10, 13, 21, 2, 29,
                                            11, 14, 16, 18, 22, 25, 3, 30,
                                            8, 12, 20, 28, 15, 17, 24, 7,
                                            19, 27, 23, 6, 26, 5, 4, 31};
        val |= val >> 1;
        val |= val >> 2;
        val |= val >> 4;
        val |= val >> 8;
        val |= val >> 16;
        return 31 - DeBruijnClz[(val * 0x07C4ACDDU) >> 27];
    }
}

MEM_STATIC unsigned ZSTD_countLeadingZeros32(U32 val)
{
    assert(val != 0);
#   if defined(_MSC_VER)
#       if STATIC_BMI2 == 1
            return (unsigned)_lzcnt_u32(val);
#       else
            if (val != 0) {
                unsigned long r;
                _BitScanReverse(&r, val);
                return (unsigned)(31 - r);
            } else {
                /* Should not reach this code path */
                __assume(0);
            }
#       endif
#   elif defined(__GNUC__) && (__GNUC__ >= 4)
        return (unsigned)__builtin_clz(val);
#   else
        return ZSTD_countLeadingZeros32_fallback(val);
#   endif
}

MEM_STATIC unsigned ZSTD_countTrailingZeros64(U64 val)
{
    assert(val != 0);
#   if defined(_MSC_VER) && defined(_WIN64)
#       if STATIC_BMI2 == 1
            return (unsigned)_tzcnt_u64(val);
#       else
            if (val != 0) {
                unsigned long r;
                _BitScanForward64(&r, val);
                return (unsigned)r;
            } else {
                /* Should not reach this code path */
                __assume(0);
            }
#       endif
#   elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(__LP64__)
        return (unsigned)__builtin_ctzll(val);
#   else
        {
            U32 mostSignificantWord = (U32)(val >> 32);
            U32 leastSignificantWord = (U32)val;
            if (leastSignificantWord == 0) {
                return 32 + ZSTD_countTrailingZeros32(mostSignificantWord);
            } else {
                return ZSTD_countTrailingZeros32(leastSignificantWord);
            }
        }
#   endif
}

MEM_STATIC unsigned ZSTD_countLeadingZeros64(U64 val)
{
    assert(val != 0);
#   if defined(_MSC_VER) && defined(_WIN64)
#       if STATIC_BMI2 == 1
            return (unsigned)_lzcnt_u64(val);
#       else
            if (val != 0) {
                unsigned long r;
                _BitScanReverse64(&r, val);
                return (unsigned)(63 - r);
            } else {
                /* Should not reach this code path */
                __assume(0);
            }
#       endif
#   elif defined(__GNUC__) && (__GNUC__ >= 4)
        return (unsigned)(__builtin_clzll(val));
#   else
        {
            U32 mostSignificantWord = (U32)(val >> 32);
            U32 leastSignificantWord = (U32)val;
            if (mostSignificantWord == 0) {
                return 32 + ZSTD_countLeadingZeros32(leastSignificantWord);
            } else {
                return ZSTD_countLeadingZeros32(mostSignificantWord);
            }
        }
#   endif
}

MEM_STATIC unsigned ZSTD_NbCommonBytes(size_t val)
{
    if (MEM_isLittleEndian()) {
        if (MEM_64bits()) {
            return ZSTD_countTrailingZeros64((U64)val) >> 3;
        } else {
            return ZSTD_countTrailingZeros32((U32)val) >> 3;
        }
    } else {  /* Big Endian CPU */
        if (MEM_64bits()) {
            return ZSTD_countLeadingZeros64((U64)val) >> 3;
        } else {
            return ZSTD_countLeadingZeros32((U32)val) >> 3;
        }
    }
}

MEM_STATIC unsigned ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
{
    assert(val != 0);
    return 31 - ZSTD_countLeadingZeros32(val);
}

/* ZSTD_rotateRight_*():
 * Rotates a bitfield to the right by "count" bits.
 * https://en.wikipedia.org/w/index.php?title=Circular_shift&oldid=991635599#Implementing_circular_shifts
 */
MEM_STATIC
U64 ZSTD_rotateRight_U64(U64 const value, U32 count) {
    assert(count < 64);
    count &= 0x3F; /* for fickle pattern recognition */
    return (value >> count) | (U64)(value << ((0U - count) & 0x3F));
}

MEM_STATIC
U32 ZSTD_rotateRight_U32(U32 const value, U32 count) {
    assert(count < 32);
    count &= 0x1F; /* for fickle pattern recognition */
    return (value >> count) | (U32)(value << ((0U - count) & 0x1F));
}

MEM_STATIC
U16 ZSTD_rotateRight_U16(U16 const value, U32 count) {
    assert(count < 16);
    count &= 0x0F; /* for fickle pattern recognition */
    return (value >> count) | (U16)(value << ((0U - count) & 0x0F));
}

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