/*******************************************************************************
 * Copyright IBM Corp. and others 1996
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

/***************************************************************************/
/*                                                                         */
/*  File name:  bitmanip.h                                                 */
/*  Purpose:    Definition of various bitwise operations.                  */
/*                                                                         */
/***************************************************************************/

#ifndef CSBITMANIP_H
#define CSBITMANIP_H

#if (defined(__IBMCPP__) || defined(__open_xl__)) && defined(__PPC__)
// to __cntlz4 and related routines
#include "builtins.h"
#endif

namespace CS2 {

static const uint8_t kByteLeadingZeroes[256] = {
    /* 0x00 */ 8,
    /* 0x01 */ 7,
    /* 0x02 */ 6, 6,
    /* 0x04 */ 5, 5, 5, 5,
    /* 0x08 */ 4, 4, 4, 4, 4, 4, 4, 4,
    /* 0x10 */ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
    /* 0x20 */ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    /* 0x40 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
    /* the remainder of the array is filled with zeroes */
};

/// BitManipulator
///
/// \brief A class of functions to manipulate bit masks
/// \ingroup CompilerServices
namespace BitManipulator {

/// \brief count the number of 1-bits in the argument, and return the count
uint32_t PopulationCount(uint32_t);
uint32_t PopulationCount(uint64_t);

/// \brief Return a count 0..32 of leading zeroes in the given word
uint32_t LeadingZeroes(uint32_t);
uint32_t EmulateLeadingZeroes(uint32_t);

/// \brief Return a count 0..64 of leading zeroes in the given doubleword
uint32_t LeadingZeroes(uint64_t);
uint32_t EmulateLeadingZeroes(uint64_t);

/// \brief Return a count 0..32 of leading ones in the given word
uint32_t LeadingOnes(uint32_t);

/// \brief Return a count 0..64 of leading ones in the given doubleword
uint32_t LeadingOnes(uint64_t);

/// \brief Return a count 0..32 of trailing zeroes in the given word
uint32_t TrailingZeroes(uint32_t);

/// \brief Return a count 0..64 of trailing zeroes in the given doubleword
uint32_t TrailingZeroes(uint64_t);

/// \brief Return a count 0..32 of trailing ones in the given word
uint32_t TrailingOnes(uint32_t);

/// \brief Return a count 0..64 of trailing ones in the given doubleword
uint32_t TrailingOnes(uint64_t);

/// \brief Determine the ceiling power of two of the given number (ie. return
/// the next higher power of two unless the input is already a power of
/// two, in which case the input is returned).
uint32_t CeilingPowerOfTwo(uint32_t);
uint64_t CeilingPowerOfTwo(uint64_t);

/// \brief Determine the floor power of two of the given number (ie. return
/// the next lower power of two unless the input is already a power of
/// two, in which case the input is returned).
uint64_t FloorPowerOfTwo(uint64_t);

/// \brief Byte reverse a short
uint16_t ByteReverse(uint16_t);

/// \brief Byte reverse a word
uint32_t ByteReverse(uint32_t);

/// \brief Byte reverse a doubleword
uint64_t ByteReverse(uint64_t);

/// \brief Determine if a given numbers 1-bits are continugous in the form of:
/// 00...011...100...0 or 11...100...011...1, (or if == 0)
bool ContiguousOnes(int32_t);
bool ContiguousOnes(int64_t);

/// \brief Return a count 0..8 of leading zeroes in the given byte
uint32_t LeadingZeroes(uint8_t);

uint32_t High32Of64(uint64_t u64);
uint32_t Low32Of64(uint64_t u64);
}; // namespace BitManipulator

inline uint32_t BitManipulator::High32Of64(uint64_t u64) { return uint32_t(u64 >> 32); }

inline uint32_t BitManipulator::Low32Of64(uint64_t u64) { return uint32_t(u64); }

#if (defined(__IBMCPP__) || defined(__ibmxl__) || defined(__open_xl__)) && defined(__PPC__)
inline uint32_t BitManipulator::LeadingZeroes(uint32_t inputWord) { return __cntlz4(inputWord); }

#if defined(__64BIT__)
inline uint32_t BitManipulator::LeadingZeroes(uint64_t inputWord) { return __cntlz8(inputWord); }
#else
inline uint32_t BitManipulator::LeadingZeroes(uint64_t inputWord)
{
    return BitManipulator::EmulateLeadingZeroes(inputWord);
}
#endif
#else
inline uint32_t BitManipulator::LeadingZeroes(uint32_t inputWord)
{
    return BitManipulator::EmulateLeadingZeroes(inputWord);
}

inline uint32_t BitManipulator::LeadingZeroes(uint64_t inputWord)
{
    return BitManipulator::EmulateLeadingZeroes(inputWord);
}
#endif

inline uint32_t BitManipulator::LeadingOnes(uint32_t inputWord) { return BitManipulator::LeadingZeroes(~inputWord); }

inline uint32_t BitManipulator::LeadingOnes(uint64_t inputWord) { return BitManipulator::LeadingZeroes(~inputWord); }

inline uint32_t BitManipulator::TrailingZeroes(uint32_t inputWord)
{
    uint32_t work;

    work = inputWord;
    work = ~work & (work - 1);

    return 32 - LeadingZeroes(work);
}

inline uint32_t BitManipulator::TrailingZeroes(uint64_t inputDoubleWord)
{
    uint32_t lowerWord, upperWord;

    lowerWord = Low32Of64(inputDoubleWord);
    if (lowerWord == 0) {
        upperWord = High32Of64(inputDoubleWord);
        return 32 + TrailingZeroes(upperWord);
    } else
        return TrailingZeroes(lowerWord);
}

inline uint32_t BitManipulator::TrailingOnes(uint32_t inputWord) { return BitManipulator::TrailingZeroes(~inputWord); }

inline uint32_t BitManipulator::TrailingOnes(uint64_t inputWord) { return BitManipulator::TrailingZeroes(~inputWord); }

inline uint32_t BitManipulator::CeilingPowerOfTwo(uint32_t inputWord)
{
    return 1 << (32 - LeadingZeroes(inputWord - 1));
}

inline uint64_t BitManipulator::CeilingPowerOfTwo(uint64_t inputDoubleWord)
{
    return (uint64_t)1 << (64 - LeadingZeroes(inputDoubleWord - (uint64_t)1));
}

inline uint64_t BitManipulator::FloorPowerOfTwo(uint64_t inputDoubleWord)
{
    return (uint64_t)1 << (63 - LeadingZeroes(inputDoubleWord));
}

inline uint16_t BitManipulator::ByteReverse(uint16_t inputHalfWord)
{
    uint16_t reversedHalfWord;
    reversedHalfWord = (inputHalfWord << 8) | (inputHalfWord >> 8);
    return reversedHalfWord;
}

inline uint32_t BitManipulator::ByteReverse(uint32_t inputWord)
{
    uint32_t reversedWord;
    reversedWord
        = (inputWord << 24) | ((inputWord & 0xFF00ul) << 8) | ((inputWord >> 8) & 0xFF00ul) | (inputWord >> 24);
    return reversedWord;
}

// BitManipulator::PopulationCount
//
// count the number of 1-bits in the argument, and return the count

inline uint32_t BitManipulator::PopulationCount(uint32_t inputWord)
{
    uint32_t popCount;

    uint32_t work, temp;

    work = inputWord;
    if (0 == work)
        return 0;
    work = work - ((work >> 1) & 0x55555555ul);
    temp = ((work >> 2) & 0x33333333ul);
    work = (work & 0x33333333ul) + temp;
    work = (work + (work >> 4)) & 0x0F0F0F0Ful;
    work = work + (work << 8);
    work = work + (work << 16);
    popCount = work >> 24;

    return popCount;
}

#ifdef __64BIT__
inline uint32_t BitManipulator::PopulationCount(uint64_t inputDoubleWord)
{
    uint64_t work;
    uint32_t res;

    work = inputDoubleWord;
    if (inputDoubleWord == 0)
        return 0;

    work = work - ((work >> 1) & 0x5555555555555555ull);
    work = (work & 0x3333333333333333ull) + ((work >> 2) & 0x3333333333333333ull);

    res = ((uint32_t)work) + ((uint32_t)(work >> 32));
    res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
    res = (res & 0xFFFF) + (res >> 16);
    res = (res & 0xFF) + (res >> 8);
    return res;
}
#else
inline uint32_t BitManipulator::PopulationCount(uint64_t inputDoubleWord)
{
    return PopulationCount(High32Of64(inputDoubleWord)) + PopulationCount(Low32Of64(inputDoubleWord));
}
#endif

inline uint32_t BitManipulator::LeadingZeroes(uint8_t inputByte) { return kByteLeadingZeroes[inputByte]; }

// BitManipulator::EmulateLeadingZeroes (uint32_t)
//
// Return a count 0..32 of leading zeroes in the given word

inline uint32_t BitManipulator::EmulateLeadingZeroes(uint32_t inputWord)
{
    uint32_t byteMask, bitCount;

    byteMask = 0xFFul << 24; // a byte mask high order justified

    // find first non-zero byte
    for (bitCount = 0; bitCount < 32; bitCount += 8) {
        uint8_t byteValue;
        uint32_t testWord;

        testWord = inputWord & byteMask;
        if (testWord != 0) {
            byteValue = testWord >> (24 - bitCount);
            return bitCount + BitManipulator::LeadingZeroes(byteValue);
        }

        byteMask >>= 8;
    }

    return 32;
}

// BitManipulator::EmulateLeadingZeroes (uint64_t)
//
// Return a count 0..64 of leading zeroes in the given doubleword

inline uint32_t BitManipulator::EmulateLeadingZeroes(uint64_t inputDoubleWord)
{
    uint32_t testWord = uint32_t(inputDoubleWord >> 32);
    uint32_t adjust = 0;

    if (testWord == 0) {
        // upper word is zero
        testWord = uint32_t(inputDoubleWord);
        adjust = 32;
    }
    return adjust + BitManipulator::EmulateLeadingZeroes(testWord);
}

// BitManipulator::ByteReverse (uint64_t)
//
// Byte reverse a doubleword

inline uint64_t BitManipulator::ByteReverse(uint64_t inputDoubleWord)
{
    uint64_t reversedDoubleWord;
    uint32_t upperWord, reversedUpperWord, lowerWord, reversedLowerWord;

    upperWord = uint32_t(inputDoubleWord >> 32);
    reversedUpperWord = BitManipulator::ByteReverse(upperWord);

    lowerWord = uint32_t(inputDoubleWord);
    reversedLowerWord = BitManipulator::ByteReverse(lowerWord);

    reversedDoubleWord = ((uint64_t)reversedLowerWord << 32u) | ((uint64_t)reversedUpperWord);

    return reversedDoubleWord;
}

// BitManipulator::ContiguousOnes (int32_t)
//
// Return true if there is a set of contiguous ones/zeroes
inline bool BitManipulator::ContiguousOnes(int32_t mask)
{
    // 1's complement if negative
    mask ^= mask >> 31;
    mask = ((mask | (mask - 1)) + 1) & mask;
    if (mask == 0)
        return true;
    return false;
}

// BitManipulator::ContiguousOnes (int64_t)
//
// Return true if there is a set of contiguous ones/zeroes
inline bool BitManipulator::ContiguousOnes(int64_t mask)
{
    // 1's complement if negative
    mask ^= mask >> 63;
    uint64_t umask = mask;
    umask = ((umask | (umask - (uint64_t)1)) + (uint64_t)1) & umask;
    if (umask == (uint64_t)0)
        return true;
    return false;
}

} // namespace CS2
#endif // CSBITMANIP_H
