bittricks.h

Go to the documentation of this file.

// Hoover Chess Utilities / PGN reader
// Copyright (C) 2025-2026  Sami Kiminki
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
#ifndef HOOVER_CHESS_UTILS__PGN_READER__BITTRICKS_H_INCLUDED
#define HOOVER_CHESS_UTILS__PGN_READER__BITTRICKS_H_INCLUDED
 
#include "pgnreader-config.h"
 
#include <bit>
#include <cassert>
#include <cinttypes>
 
#if (HAVE_X86_BMI2)
#include <immintrin.h>
#endif
 
#if (HAVE_AARCH64_SVE2_BITPERM)
#include <arm_sve.h>
#endif
 
namespace hoover_chess_utils::pgn_reader
{
 
struct BitTricks
{
 
    static constexpr inline std::uint64_t bits0ToN(std::uint8_t n) noexcept
    {
        assert(n <= 63U);
 
        return (std::uint64_t { 2 } << n) - 1U;
    }
 
    static constexpr inline std::uint64_t rangeHalfOpen(std::uint8_t a, std::uint8_t b) noexcept
    {
        assert(a <= 63U);
        assert(b <= 63U);
 
        return bits0ToN(a) ^ bits0ToN(b);
    }
 
    static constexpr inline std::uint64_t isolateLowestSetBit(std::uint64_t mask) noexcept
    {
        return mask & (-mask);
    }
 
    static constexpr inline std::uint64_t isolateHighestSetBit(std::uint64_t mask) noexcept
    {
        // Note: we need to 'and' to ensure that the isolated bit actually exists (when n == 0)
        if (mask != 0U) [[likely]]
        {
            std::uint64_t topBit { UINT64_C(0x80'00'00'00'00'00'00'00) };
            return (topBit >> std::countl_zero(mask));
        }
        else [[unlikely]]
        {
            return 0U;
        }
    }
 
private:
    static std::uint64_t parallelExtractPortable(std::uint64_t data, std::uint64_t mask) noexcept;
    static std::uint64_t parallelDepositPortable(std::uint64_t data, std::uint64_t mask) noexcept;
 
public:
 
    static inline std::uint64_t parallelExtract(std::uint64_t data, std::uint64_t mask) noexcept
    {
#if (HAVE_X86_BMI2)
        return _pext_u64(data, mask);
#elif (HAVE_AARCH64_SVE2_BITPERM)
        return svbext_n_u64(svdup_u64(data), mask)[0U];
#elif 1
        return parallelExtractPortable(data, mask);
#else
        std::uint64_t mk { (~mask) << 1U };
        data = data & mask;
 
        for (unsigned i { }; i < 6U; ++i)
        {
            std::uint64_t mp { mk ^ (mk << 1U) };
            mp = mp ^ (mp << 2U);
            mp = mp ^ (mp << 4U);
            mp = mp ^ (mp << 8U);
            mp = mp ^ (mp << 16U);
            mp = mp ^ (mp << 32U);
 
            const std::uint64_t mv { mp & mask };
            mask = (mask ^ mv) | (mv >> (UINT64_C(1) << i));
            const std::uint64_t t { data & mv };
            data = (data ^ t) | (t >> (UINT64_C(1) << i));
            mk = mk & ~mp;
        }
 
        return data;
#endif
    }
 
    static inline std::uint64_t parallelDeposit(std::uint64_t data, std::uint64_t mask) noexcept
    {
#if (HAVE_X86_BMI2)
        return _pdep_u64(data, mask);
#elif (HAVE_AARCH64_SVE2_BITPERM)
        return svbdep_n_u64(svdup_u64(data), mask)[0U];
#elif 1
        return parallelDepositPortable(data, mask);
#else
        std::uint64_t mk { (~mask) << 1U };
        const std::uint64_t m0 { mask };
 
        std::uint64_t arr[6];
 
        for (unsigned i { }; i < 6U; ++i)
        {
            std::uint64_t mp { mk ^ (mk << 1U) };
            mp = mp ^ (mp << 2U);
            mp = mp ^ (mp << 4U);
            mp = mp ^ (mp << 8U);
            mp = mp ^ (mp << 16U);
            mp = mp ^ (mp << 32U);
 
            const std::uint64_t mv { mp & mask };
            arr[i] = mv;
            mask = (mask ^ mv) | (mv >> (UINT64_C(1) << i));
            mk = mk & ~mp;
        }
 
        for (unsigned i { 5U }; i <= 5U; --i)
        {
            std::uint64_t mv { arr[i] };
            const std::uint64_t t { data << (1U << i) };
            data = (data & ~mv) | (t & mv);
        }
 
        return data & m0;
#endif
    }
 
};
 
}
 
#endif