.NET-Community-Toolkit/CommunityToolkit.HighPerformance/Helpers/BitHelper.cs

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System.Runtime.CompilerServices;
#if NETCOREAPP3_1_OR_GREATER
using System.Runtime.Intrinsics.X86;
#endif

namespace CommunityToolkit.HighPerformance.Helpers;

/// <summary>
/// Helpers to perform bit operations on numeric types.
/// </summary>
public static class BitHelper
{
    /// <summary>
    /// Checks whether or not a given bit is set.
    /// </summary>
    /// <param name="value">The input <see cref="uint"/> value.</param>
    /// <param name="n">The position of the bit to check (in [0, 31] range).</param>
    /// <returns>Whether or not the n-th bit is set.</returns>
    /// <remarks>
    /// This method doesn't validate <paramref name="n"/> against the valid range.
    /// If the parameter is not valid, the result will just be inconsistent.
    /// Additionally, no conditional branches are used to retrieve the flag.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe bool HasFlag(uint value, int n)
    {
        // Read the n-th bit, downcast to byte
        byte flag = (byte)((value >> n) & 1);

        // Reinterpret the byte to avoid the test, setnz and
        // movzx instructions (asm x64). This is because the JIT
        // compiler is able to optimize this reinterpret-cast as
        // a single "and eax, 0x1" instruction, whereas if we had
        // compared the previous computed flag against 0, the assembly
        // would have had to perform the test, set the non-zero
        // flag and then extend the (byte) result to eax.
        return *(bool*)&flag;
    }

    /// <summary>
    /// Checks whether or not a given bit is set in a given bitwise lookup table.
    /// This method provides a branchless, register-based (with no memory accesses) way to
    /// check whether a given value is valid, according to a precomputed lookup table.
    /// It is similar in behavior to <see cref="HasFlag(uint,int)"/>, with the main difference
    /// being that this method will also validate the input <paramref name="x"/> parameter, and
    /// will always return <see langword="false"/> if it falls outside of the expected interval.
    /// Additionally, this method accepts a <paramref name="min"/> parameter, which is used to
    /// decrement the input parameter <paramref name="x"/> to ensure that the range of accepted
    /// values fits within the available 32 bits of the lookup table in use.
    /// For more info on this optimization technique, see <see href="https://egorbo.com/llvm-range-checks.html"/>.
    /// Here is how the code from the link above would be implemented using this method:
    /// <code>
    /// bool IsReservedCharacter(char c)
    /// {
    ///     return BitHelper.HasLookupFlag(314575237u, c, 36);
    /// }
    /// </code>
    /// The resulted assembly is virtually identical, with the added optimization that the one
    /// produced by <see cref="HasLookupFlag(uint,int,int)"/> has no conditional branches at all.
    /// </summary>
    /// <param name="table">The input lookup table to use.</param>
    /// <param name="x">The input value to check.</param>
    /// <param name="min">The minimum accepted value for <paramref name="x"/> (defaults to 0).</param>
    /// <returns>Whether or not the corresponding flag for <paramref name="x"/> is set in <paramref name="table"/>.</returns>
    /// <remarks>
    /// For best results, as shown in the sample code, both <paramref name="table"/> and <paramref name="min"/>
    /// should be compile-time constants, so that the JIT compiler will be able to produce more efficient code.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe bool HasLookupFlag(uint table, int x, int min = 0)
    {
        // First, the input value is scaled down by the given minimum.
        // This step will be skipped entirely if min is just the default of 0.
        // The valid range is given by 32, which is the number of bits in the
        // lookup table. The input value is first cast to uint so that if it was
        // negative, the check will fail as well. Then, the result of this
        // operation is used to compute a bitwise flag of either 0xFFFFFFFF if the
        // input is accepted, or all 0 otherwise. The target bit is then extracted,
        // and this value is combined with the previous mask. This is done so that
        // if the shift was performed with a value that was too high, which has an
        // undefined behavior and could produce a non-0 value, the mask will reset
        // the final value anyway. This result is then unchecked-cast to a byte (as
        // it is guaranteed to always be either 1 or 0), and then reinterpreted
        // as a bool just like in the HasFlag method above, and then returned.
        int i = x - min;
        bool isInRange = (uint)i < 32u;
        byte byteFlag = *(byte*)&isInRange;
        int negativeFlag = byteFlag - 1;
        int mask = ~negativeFlag;
        int shift = unchecked((int)((table >> i) & 1));
        int and = shift & mask;
        byte result = unchecked((byte)and);
        bool valid = *(bool*)&result;

        return valid;
    }

    /// <summary>
    /// Checks whether the given value has any bytes that are set to 0.
    /// That is, given a <see cref="uint"/> value, which has a total of 4 bytes,
    /// it checks whether any of those have all the bits set to 0.
    /// </summary>
    /// <param name="value">The input value to check.</param>
    /// <returns>Whether <paramref name="value"/> has any bytes set to 0.</returns>
    /// <remarks>
    /// This method contains no branches.
    /// For more background on this subject, see <see href="https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord"/>.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool HasZeroByte(uint value)
    {
        return ((value - 0x0101_0101u) & ~value & 0x8080_8080u) != 0;
    }

    /// <summary>
    /// Checks whether the given value has any bytes that are set to 0.
    /// This method mirrors <see cref="HasZeroByte(uint)"/>, but with <see cref="ulong"/> values.
    /// </summary>
    /// <param name="value">The input value to check.</param>
    /// <returns>Whether <paramref name="value"/> has any bytes set to 0.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool HasZeroByte(ulong value)
    {
        return ((value - 0x0101_0101_0101_0101ul) & ~value & 0x8080_8080_8080_8080ul) != 0;
    }

    /// <summary>
    /// Checks whether a byte in the input <see cref="uint"/> value matches a target value.
    /// </summary>
    /// <param name="value">The input value to check.</param>
    /// <param name="target">The target byte to look for.</param>
    /// <returns>Whether <paramref name="value"/> has any bytes set to <paramref name="target"/>.</returns>
    /// <remarks>
    /// This method contains no branches.
    /// For more info, see <see href="https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord"/>.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool HasByteEqualTo(uint value, byte target)
    {
        return HasZeroByte(value ^ (0x0101_0101u * target));
    }

    /// <summary>
    /// Checks whether a byte in the input <see cref="uint"/> value matches a target value.
    /// This method mirrors <see cref="HasByteEqualTo(uint,byte)"/>, but with <see cref="ulong"/> values.
    /// </summary>
    /// <param name="value">The input value to check.</param>
    /// <param name="target">The target byte to look for.</param>
    /// <returns>Whether <paramref name="value"/> has any bytes set to <paramref name="target"/>.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool HasByteEqualTo(ulong value, byte target)
    {
        return HasZeroByte(value ^ (0x0101_0101_0101_0101u * target));
    }

    /// <summary>
    /// Sets a bit to a specified value.
    /// </summary>
    /// <param name="value">The target <see cref="uint"/> value.</param>
    /// <param name="n">The position of the bit to set or clear (in [0, 31] range).</param>
    /// <param name="flag">The value to assign to the target bit.</param>
    /// <remarks>
    /// Just like <see cref="HasFlag(uint,int)"/>, this method doesn't validate <paramref name="n"/>
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void SetFlag(ref uint value, int n, bool flag)
    {
        value = SetFlag(value, n, flag);
    }

    /// <summary>
    /// Sets a bit to a specified value.
    /// </summary>
    /// <param name="value">The input <see cref="uint"/> value.</param>
    /// <param name="n">The position of the bit to set or clear (in [0, 31] range).</param>
    /// <param name="flag">The value to assign to the target bit.</param>
    /// <returns>An <see cref="uint"/> value equal to <paramref name="value"/> except for the <paramref name="n"/>-th bit.</returns>
    /// <remarks>
    /// Just like <see cref="HasFlag(uint,int)"/>, this method doesn't validate <paramref name="n"/>
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe uint SetFlag(uint value, int n, bool flag)
    {
        // Shift a bit left to the n-th position, negate the
        // resulting value and perform an AND with the input value.
        // This effectively clears the n-th bit of our input.
        uint bit = 1u << n;
        uint not = ~bit;
        uint and = value & not;

        // Reinterpret the flag as 1 or 0, and cast to uint,
        // then we left shift the uint flag to the right position
        // and perform an OR with the resulting value of the previous
        // operation. This will always guaranteed to work, thanks to the
        // initial code clearing that bit before setting it again.
        bool copy = flag;
        uint flag32 = *(byte*)&copy;
        uint shift = flag32 << n;
        uint or = and | shift;

        return or;
    }

    /// <summary>
    /// Extracts a bit field range from a given value.
    /// </summary>
    /// <param name="value">The input <see cref="uint"/> value.</param>
    /// <param name="start">The initial index of the range to extract (in [0, 31] range).</param>
    /// <param name="length">The length of the range to extract (depends on <paramref name="start"/>).</param>
    /// <returns>The value of the extracted range within <paramref name="value"/>.</returns>
    /// <remarks>
    /// This method doesn't validate <paramref name="start"/> and <paramref name="length"/>.
    /// If either parameter is not valid, the result will just be inconsistent. The method
    /// should not be used to set all the bits at once, and it is not guaranteed to work in
    /// that case, which would just be equivalent to assigning the <see cref="uint"/> value.
    /// Additionally, no conditional branches are used to retrieve the range.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static uint ExtractRange(uint value, byte start, byte length)
    {
#if NETCOREAPP3_1_OR_GREATER
        if (Bmi1.IsSupported)
        {
            return Bmi1.BitFieldExtract(value, start, length);
        }
#endif

        return (value >> start) & ((1u << length) - 1u);
    }

    /// <summary>
    /// Sets a bit field range within a target value.
    /// </summary>
    /// <param name="value">The target <see cref="uint"/> value.</param>
    /// <param name="start">The initial index of the range to extract (in [0, 31] range).</param>
    /// <param name="length">The length of the range to extract (depends on <paramref name="start"/>).</param>
    /// <param name="flags">The input flags to insert in the target range.</param>
    /// <remarks>
    /// Just like <see cref="ExtractRange(uint,byte,byte)"/>, this method doesn't validate the parameters
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void SetRange(ref uint value, byte start, byte length, uint flags)
    {
        value = SetRange(value, start, length, flags);
    }

    /// <summary>
    /// Sets a bit field range within a target value.
    /// </summary>
    /// <param name="value">The initial <see cref="uint"/> value.</param>
    /// <param name="start">The initial index of the range to extract (in [0, 31] range).</param>
    /// <param name="length">The length of the range to extract (depends on <paramref name="start"/>).</param>
    /// <param name="flags">The input flags to insert in the target range.</param>
    /// <returns>The updated bit field value after setting the specified range.</returns>
    /// <remarks>
    /// Just like <see cref="ExtractRange(uint,byte,byte)"/>, this method doesn't validate the parameters
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static uint SetRange(uint value, byte start, byte length, uint flags)
    {
        uint highBits = (1u << length) - 1u;
        uint loadMask = highBits << start;
        uint storeMask = (flags & highBits) << start;

#if NETCOREAPP3_1_OR_GREATER
        if (Bmi1.IsSupported)
        {
            return Bmi1.AndNot(loadMask, value) | storeMask;
        }
#endif

        return (~loadMask & value) | storeMask;
    }

    /// <summary>
    /// Checks whether or not a given bit is set.
    /// </summary>
    /// <param name="value">The input <see cref="ulong"/> value.</param>
    /// <param name="n">The position of the bit to check (in [0, 63] range).</param>
    /// <returns>Whether or not the n-th bit is set.</returns>
    /// <remarks>
    /// This method doesn't validate <paramref name="n"/> against the valid range.
    /// If the parameter is not valid, the result will just be inconsistent.
    /// Additionally, no conditional branches are used to retrieve the flag.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe bool HasFlag(ulong value, int n)
    {
        // Same logic as the uint version, see that for more info
        byte flag = (byte)((value >> n) & 1);

        return *(bool*)&flag;
    }

    /// <summary>
    /// Checks whether or not a given bit is set in a given bitwise lookup table.
    /// For more info, check the XML docs of the <see cref="HasLookupFlag(uint,int,int)"/> overload.
    /// </summary>
    /// <param name="table">The input lookup table to use.</param>
    /// <param name="x">The input value to check.</param>
    /// <param name="min">The minimum accepted value for <paramref name="x"/> (defaults to 0).</param>
    /// <returns>Whether or not the corresponding flag for <paramref name="x"/> is set in <paramref name="table"/>.</returns>
    /// <remarks>
    /// For best results, as shown in the sample code, both <paramref name="table"/> and <paramref name="min"/>
    /// should be compile-time constants, so that the JIT compiler will be able to produce more efficient code.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe bool HasLookupFlag(ulong table, int x, int min = 0)
    {
        int i = x - min;
        bool isInRange = (uint)i < 64u;
        byte byteFlag = *(byte*)&isInRange;
        int negativeFlag = byteFlag - 1;
        int mask = ~negativeFlag;
        int shift = unchecked((int)((table >> i) & 1));
        int and = shift & mask;
        byte result = unchecked((byte)and);
        bool valid = *(bool*)&result;

        return valid;
    }

    /// <summary>
    /// Sets a bit to a specified value.
    /// </summary>
    /// <param name="value">The target <see cref="ulong"/> value.</param>
    /// <param name="n">The position of the bit to set or clear (in [0, 63] range).</param>
    /// <param name="flag">The value to assign to the target bit.</param>
    /// <remarks>
    /// Just like <see cref="HasFlag(ulong,int)"/>, this method doesn't validate <paramref name="n"/>
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void SetFlag(ref ulong value, int n, bool flag)
    {
        value = SetFlag(value, n, flag);
    }

    /// <summary>
    /// Sets a bit to a specified value.
    /// </summary>
    /// <param name="value">The input <see cref="ulong"/> value.</param>
    /// <param name="n">The position of the bit to set or clear (in [0, 63] range).</param>
    /// <param name="flag">The value to assign to the target bit.</param>
    /// <returns>An <see cref="ulong"/> value equal to <paramref name="value"/> except for the <paramref name="n"/>-th bit.</returns>
    /// <remarks>
    /// Just like <see cref="HasFlag(ulong,int)"/>, this method doesn't validate <paramref name="n"/>
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static unsafe ulong SetFlag(ulong value, int n, bool flag)
    {
        ulong bit = 1ul << n;
        ulong not = ~bit;
        ulong and = value & not;
        bool copy = flag;
        ulong flag64 = *(byte*)&copy;
        ulong shift = flag64 << n;
        ulong or = and | shift;

        return or;
    }

    /// <summary>
    /// Extracts a bit field range from a given value.
    /// </summary>
    /// <param name="value">The input <see cref="ulong"/> value.</param>
    /// <param name="start">The initial index of the range to extract (in [0, 63] range).</param>
    /// <param name="length">The length of the range to extract (depends on <paramref name="start"/>).</param>
    /// <returns>The value of the extracted range within <paramref name="value"/>.</returns>
    /// <remarks>
    /// This method doesn't validate <paramref name="start"/> and <paramref name="length"/>.
    /// If either parameter is not valid, the result will just be inconsistent. The method
    /// should not be used to set all the bits at once, and it is not guaranteed to work in
    /// that case, which would just be equivalent to assigning the <see cref="ulong"/> value.
    /// Additionally, no conditional branches are used to retrieve the range.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ulong ExtractRange(ulong value, byte start, byte length)
    {
#if NETCOREAPP3_1_OR_GREATER
        if (Bmi1.X64.IsSupported)
        {
            return Bmi1.X64.BitFieldExtract(value, start, length);
        }
#endif

        return (value >> start) & ((1ul << length) - 1ul);
    }

    /// <summary>
    /// Sets a bit field range within a target value.
    /// </summary>
    /// <param name="value">The target <see cref="ulong"/> value.</param>
    /// <param name="start">The initial index of the range to extract (in [0, 63] range).</param>
    /// <param name="length">The length of the range to extract (depends on <paramref name="start"/>).</param>
    /// <param name="flags">The input flags to insert in the target range.</param>
    /// <remarks>
    /// Just like <see cref="ExtractRange(ulong,byte,byte)"/>, this method doesn't validate the parameters
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void SetRange(ref ulong value, byte start, byte length, ulong flags)
    {
        value = SetRange(value, start, length, flags);
    }

    /// <summary>
    /// Sets a bit field range within a target value.
    /// </summary>
    /// <param name="value">The initial <see cref="ulong"/> value.</param>
    /// <param name="start">The initial index of the range to extract (in [0, 63] range).</param>
    /// <param name="length">The length of the range to extract (depends on <paramref name="start"/>).</param>
    /// <param name="flags">The input flags to insert in the target range.</param>
    /// <returns>The updated bit field value after setting the specified range.</returns>
    /// <remarks>
    /// Just like <see cref="ExtractRange(ulong,byte,byte)"/>, this method doesn't validate the parameters
    /// and does not contain branching instructions, so it's well suited for use in tight loops as well.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ulong SetRange(ulong value, byte start, byte length, ulong flags)
    {
        ulong highBits = (1ul << length) - 1ul;
        ulong loadMask = highBits << start;
        ulong storeMask = (flags & highBits) << start;

#if NETCOREAPP3_1_OR_GREATER
        if (Bmi1.X64.IsSupported)
        {
            return Bmi1.X64.AndNot(loadMask, value) | storeMask;
        }
#endif

        return (~loadMask & value) | storeMask;
    }
}