/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * 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
 *******************************************************************************/

#include "infra/BitVector.hpp"

#include <stdint.h>
#include <stdio.h>
#include "compile/Compilation.hpp"
#include "ras/Debug.hpp"

// Number of bits set in a byte containing the index value
//
static int8_t bitsInByte[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4,
    4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2,
    3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,
    4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
    4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5,
    5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
    4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };

int32_t TR_BitVector::elementCount()
{
    int32_t count = 0;
    for (int32_t i = _firstChunkWithNonZero; i <= _lastChunkWithNonZero; i++) {
        if (_chunks[i]) {
            uint8_t *p = (uint8_t *)&_chunks[i];
            count += bitsInByte[p[0]];
            count += bitsInByte[p[1]];
            count += bitsInByte[p[2]];
            count += bitsInByte[p[3]];
#if BITS_IN_CHUNK == 64
            count += bitsInByte[p[4]];
            count += bitsInByte[p[5]];
            count += bitsInByte[p[6]];
            count += bitsInByte[p[7]];
#endif
        }
    }
    return count;
}

int32_t TR_BitVector::commonElementCount(TR_BitVector &v2)
{
    if (v2._lastChunkWithNonZero < _firstChunkWithNonZero || v2._firstChunkWithNonZero > _lastChunkWithNonZero)
        return false; // No intersection
    int32_t low
        = _firstChunkWithNonZero >= v2._firstChunkWithNonZero ? _firstChunkWithNonZero : v2._firstChunkWithNonZero;
    int32_t high = _lastChunkWithNonZero <= v2._lastChunkWithNonZero ? _lastChunkWithNonZero : v2._lastChunkWithNonZero;
    int32_t count = 0;
    for (int32_t i = low; i <= high; i++) {
        chunk_t tmp = _chunks[i] & v2._chunks[i];
        if (tmp) {
            uint8_t *p = (uint8_t *)&tmp;
            count += bitsInByte[p[0]];
            count += bitsInByte[p[1]];
            count += bitsInByte[p[2]];
            count += bitsInByte[p[3]];
#if BITS_IN_CHUNK == 64
            count += bitsInByte[p[4]];
            count += bitsInByte[p[5]];
            count += bitsInByte[p[6]];
            count += bitsInByte[p[7]];
#endif
        }
    }
    return count;
}

bool TR_BitVector::hasMoreThanOneElement()
{
    if (_firstChunkWithNonZero < _lastChunkWithNonZero)
        return true;
    if (_lastChunkWithNonZero < 0)
        return false;
    int32_t count = 0;
    uint8_t *p = (uint8_t *)&_chunks[_firstChunkWithNonZero];
    count += bitsInByte[p[0]];
    count += bitsInByte[p[1]];
    count += bitsInByte[p[2]];
    count += bitsInByte[p[3]];
#if BITS_IN_CHUNK == 64
    count += bitsInByte[p[4]];
    count += bitsInByte[p[5]];
    count += bitsInByte[p[6]];
    count += bitsInByte[p[7]];
#endif

    return (count > 1);
}

void TR_BitVector::setChunkSize(int32_t chunkSize)
{
    if (chunkSize == _numChunks)
        return;
    if (chunkSize == 0) {
        if (_chunks && _region == NULL)
            jitPersistentFree(_chunks);
        _chunks = NULL;
        _numChunks = 0;
        _firstChunkWithNonZero = 0;
        _lastChunkWithNonZero = -1;
#if BV_SANITY_CHECK
        sanityCheck("setChunkSize");
#endif
        return;
    }

    if (_numChunks > chunkSize) {
        // Shrinking the bit vector ... may have lost some bits
        if (_lastChunkWithNonZero < 0)
            _firstChunkWithNonZero = chunkSize;
        else if (_firstChunkWithNonZero >= chunkSize) {
            _firstChunkWithNonZero = chunkSize;
            _lastChunkWithNonZero = -1;
        } else if (_lastChunkWithNonZero >= chunkSize) {
            // Lost some bits at the end
            for (_lastChunkWithNonZero = chunkSize - 1; _chunks[_lastChunkWithNonZero] == 0; _lastChunkWithNonZero--)
                ;
        }
    } else {
        // Growing the bit vector
        if (_lastChunkWithNonZero < 0)
            _firstChunkWithNonZero = chunkSize;
    }

    TR_ASSERT(_growable == growable, "Bit vector is not growable");

    chunk_t *newChunks = _region != NULL
        ? (chunk_t *)_region->allocate(chunkSize * sizeof(chunk_t))
        : (chunk_t *)TR_Memory::jitPersistentAlloc(chunkSize * sizeof(chunk_t), TR_Memory::BitVector);
    memset(newChunks, 0, chunkSize * sizeof(chunk_t));
#ifdef TRACK_TRBITVECTOR_MEMORY
    _memoryUsed += chunkSize * sizeof(chunk_t);
#endif
    if (_chunks) {
        uint32_t chunksToCopy = (chunkSize < _numChunks) ? chunkSize : _numChunks;
        memcpy(newChunks, _chunks, chunksToCopy * sizeof(chunk_t));
        if (_region == NULL)
            jitPersistentFree(_chunks);
    }

    _chunks = newChunks;
    _numChunks = chunkSize;
#if BV_SANITY_CHECK
    sanityCheck("setChunkSize");
#endif
}

void TR_BitVector::print(TR::Compilation *comp, TR::FILE *file)
{
    if (comp->getDebug()) {
        if (file == NULL)
            file = comp->getOutFile();
        comp->getDebug()->print(file, this);
    }
}

void TR_SingleBitContainer::print(TR::Compilation *comp, TR::FILE *file)
{
    if (comp->getDebug()) {
        if (file == NULL)
            file = comp->getOutFile();
        comp->getDebug()->print(file, this);
    }
}

// Compare this with a bit vector
//
inline bool TR_BitContainer::operator==(TR_BitVector &v2)
{
    if (_type == bitvector)
        return _bitVector && ((*_bitVector) == v2);
    else
        return (v2.get(_singleBit) && !v2.hasMoreThanOneElement());
}

bool TR_BitContainer::hasMoreThanOneElement()
{
    if (_type == bitvector && _bitVector && _bitVector->hasMoreThanOneElement())
        return true;
    return false;
}

int32_t TR_BitContainer::get(int32_t n)
{
    if (_type == bitvector && _bitVector)
        return _bitVector->get(n);
    else if (_type == bitvector)
        return 0;
    else
        return (_singleBit == n ? _singleBit : 0);
}

bool TR_BitContainer::intersects(TR_BitVector &v2)
{
    if (_type == bitvector && _bitVector)
        return _bitVector->intersects(v2);
    else if (_type == bitvector)
        return false;
    else
        return v2.get(_singleBit) != 0;
}

bool TR_BitContainer::intersects(TR_BitContainer &v2)
{
    if (v2._type == bitvector && v2._bitVector)
        return intersects(*(v2._bitVector));
    else if (v2._type == bitvector)
        return false;
    else {
        // v2 is singleton
        if (_type == bitvector && _bitVector)
            return get(v2._singleBit) != 0;
        else if (_type == bitvector)
            return false;
        else
            // both are singletons
            return v2._singleBit == _singleBit;
    }
}
