/*
  Copyright (C) 2018 David Robillard <d@drobilla.net>
  Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca>

  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 2 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 CHILBERT_BIGBITVEC_HPP
#define CHILBERT_BIGBITVEC_HPP

#include "chilbert/FixBitVec.hpp"

#include <algorithm>
#include <cassert>
#include <cstring>
#include <memory>

#define FBVS_NEEDED(b) ((std::max(b, 1) + FBV_BITS - 1) / FBV_BITS)
#define BBV_MODSPLIT(r, b, k) \
	{                         \
		b = (k);              \
		r = b / FBV_BITS;     \
		b -= r * FBV_BITS;    \
	}

namespace chilbert {

class CBigBitVec
{
public:
	CBigBitVec(const int bits = 0)
	  : m_pcRacks{new FBV_UINT[bits == 0 ? 0 : FBVS_NEEDED(bits)]}
	  , m_iRacks{bits == 0 ? 0 : FBVS_NEEDED(bits)}
	{
	}

	CBigBitVec(const CBigBitVec& vec)
	  : m_pcRacks{new FBV_UINT[vec.m_iRacks]}
	  , m_iRacks{vec.m_iRacks}
	{
		if (vec.m_pcRacks) {
			memcpy(m_pcRacks.get(),
			       vec.m_pcRacks.get(),
			       sizeof(FBV_UINT) * m_iRacks);
		}
	}

	CBigBitVec(CBigBitVec&& vec) = default;

	CBigBitVec(const CFixBitVec& vec)
	  : m_pcRacks{new FBV_UINT[1]}
	  , m_iRacks{1}
	{
		m_pcRacks[0] = vec.rack();
	}

	/// Return the size in bits
	int size() const { return m_iRacks * FBV_BITS; }

	/// Set all bits to zero
	CBigBitVec& reset()
	{
		memset(m_pcRacks.get(), 0, sizeof(CFixBitVec) * m_iRacks);
		return *this;
	}

	/// Truncate to a given precision in bits (zero MSBs)
	CBigBitVec& truncate(const int bits)
	{
		assert(bits >= 0 && bits <= size());
		int r, b;

		BBV_MODSPLIT(r, b, bits);

		if (r >= m_iRacks) {
			return *this;
		}

		// Truncate rack that contains the split point
		m_pcRacks[r] &= FBVN1S(bits);

		for (int i = r + 1; i < m_iRacks; ++i) {
			m_pcRacks[i] = 0;
		}

		return *this;
	}

	/// Non-resizing assignment
	CBigBitVec& operator=(const CBigBitVec& vec)
	{
		if (m_iRacks < vec.m_iRacks) {
			m_iRacks  = vec.m_iRacks;
			m_pcRacks = std::unique_ptr<FBV_UINT[]>{new FBV_UINT[m_iRacks]};
			memcpy(m_pcRacks.get(),
			       vec.m_pcRacks.get(),
			       sizeof(CFixBitVec) * m_iRacks);
		} else if (vec.m_iRacks > 0) {
			m_iRacks = vec.m_iRacks;
			memcpy(m_pcRacks.get(),
			       vec.m_pcRacks.get(),
			       sizeof(CFixBitVec) * m_iRacks);
		} else {
			m_iRacks = 0;
			m_pcRacks.reset();
		}

		return *this;
	}

	CBigBitVec& operator=(CBigBitVec&& vec) = default;

	CBigBitVec& operator=(const CFixBitVec& vec)
	{
		if (!m_pcRacks) {
			m_pcRacks = std::unique_ptr<FBV_UINT[]>{new FBV_UINT[1]};
		}

		m_iRacks     = 1;
		m_pcRacks[0] = vec.rack();
		return *this;
	}

	CBigBitVec& operator=(const FBV_UINT j)
	{
		if (!m_pcRacks) {
			m_pcRacks = std::unique_ptr<FBV_UINT[]>{new FBV_UINT[1]};
		}

		m_iRacks     = 1;
		m_pcRacks[0] = j;
		return *this;
	}

	/// Return the value of the `index`th bit
	bool test(const int index) const
	{
		assert(index >= 0 && index < size());
		int r, b;
		BBV_MODSPLIT(r, b, index);
		return testBit(m_pcRacks[r], b);
	}

	/// Set the `index`th bit to 1
	CBigBitVec& set(const int index)
	{
		assert(index >= 0 && index < size());
		int r, b;
		BBV_MODSPLIT(r, b, index);
		setBit(m_pcRacks[r], b);
		return *this;
	}

	/// Reset the `index`th bit to 0
	CBigBitVec& reset(const int index)
	{
		assert(index >= 0 && index < size());
		int r, b;
		BBV_MODSPLIT(r, b, index);
		m_pcRacks[r] &= ~((FBV_UINT)1 << b);
		return *this;
	}

	/// Set the `index`th bit to `value`
	CBigBitVec& set(const int index, const bool value)
	{
		assert(index >= 0 && index < size());
		int r, b;
		BBV_MODSPLIT(r, b, index);
		setBit(m_pcRacks[r], b, value);
		return *this;
	}

	/// Toggle the value of the `index`th bit
	CBigBitVec& toggle(const int index)
	{
		assert(index >= 0 && index < size());
		int r, b;
		BBV_MODSPLIT(r, b, index);
		m_pcRacks[r] ^= (FBV1 << index);
		return *this;
	}

	CBigBitVec& operator&=(const CBigBitVec& vec)
	{
		for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
			m_pcRacks[i] &= vec.m_pcRacks[i];
		}

		return *this;
	}

	CBigBitVec operator&(const CBigBitVec& vec) const
	{
		CBigBitVec t(*this);
		t &= vec;

		return t;
	}

	CBigBitVec& operator|=(const CBigBitVec& vec)
	{
		for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
			m_pcRacks[i] |= vec.m_pcRacks[i];
		}

		return *this;
	}

	CBigBitVec operator|(const CBigBitVec& vec) const
	{
		CBigBitVec t(*this);
		t |= vec;

		return t;
	}

	CBigBitVec& operator^=(const CBigBitVec& vec)
	{
		for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
			m_pcRacks[i] ^= vec.m_pcRacks[i];
		}

		return *this;
	}

	CBigBitVec operator^(const CBigBitVec& vec) const
	{
		CBigBitVec t(*this);
		t ^= vec;

		return t;
	}

	CBigBitVec& operator<<=(const int bits)
	{
		assert(bits >= 0);
		int r, b, i;

		// No shift?
		if (bits == 0) {
			return *this;
		}

		BBV_MODSPLIT(r, b, bits);

		// All racks?
		if (r >= m_iRacks) {
			reset();
			return *this;
		}

		// Do rack shifts.
		if (r > 0) {
			for (i = m_iRacks - 1; i >= r; --i) {
				m_pcRacks[i] = m_pcRacks[i - r];
			}
			for (; i >= 0; --i) {
				m_pcRacks[i] = 0;
			}
		}

		// Do bit shifts.
		if (b > 0) {
			int bi = FBV_BITS - b;
			for (i = m_iRacks - 1; i >= r + 1; --i) {
				m_pcRacks[i] <<= b;
				m_pcRacks[i] |= m_pcRacks[i - 1] >> bi;
			}
			m_pcRacks[i] <<= b;
		}

		return *this;
	}

	CBigBitVec operator<<(const int bits) const
	{
		CBigBitVec t(*this);
		t <<= bits;
		return t;
	}

	CBigBitVec& operator>>=(const int bits)
	{
		assert(bits >= 0);
		int r, b, i;

		// No shift?
		if (bits == 0) {
			return *this;
		}

		BBV_MODSPLIT(r, b, bits);

		// All racks?
		if (r >= m_iRacks) {
			reset();
			return *this;
		}

		// Do rack shifts.
		if (r > 0) {
			for (i = 0; i < m_iRacks - r; ++i) {
				m_pcRacks[i] = m_pcRacks[i + r];
			}
			for (; i < m_iRacks; ++i) {
				m_pcRacks[i] = 0;
			}
		}

		// Do bit shifts.
		if (b > 0) {
			int bi = FBV_BITS - b;
			for (i = 0; i < m_iRacks - r - 1; ++i) {
				m_pcRacks[i] >>= b;
				m_pcRacks[i] |= m_pcRacks[i + 1] << bi;
			}
			m_pcRacks[i] >>= b;
		}

		return *this;
	}

	CBigBitVec operator>>(const int bits) const
	{
		CBigBitVec t(*this);
		t >>= bits;
		return t;
	}

	/// Right-rotate the least significant `width` bits by `bits` positions
	CBigBitVec& rotr(const int bits, int width)
	{
		assert(bits >= 0);

		// Fill in the width, if necessary.
		if (width <= 0) {
			width = size();
		}

		// Modulo the number of bits.
		assert(bits < width);
		if (bits == 0) {
			return *this;
		}

		// Ensure we are truncated appropriately.
		truncate(width);

		CBigBitVec t1(*this);
		(*this) >>= bits;
		t1 <<= (width - bits);
		(*this) |= t1;

		truncate(width);

		return *this;
	}

	/// Left-rotate the least significant `width` bits by `bits` positions
	CBigBitVec& rotl(const int bits, int width)
	{
		assert(bits >= 0);

		// Fill in the width, if necessary.
		if (width <= 0) {
			width = size();
		}

		// Modulo the number of bits.
		assert(bits < width);
		if (bits == 0) {
			return *this;
		}

		// Ensure we are truncated appropriately.
		truncate(width);

		CBigBitVec t1(*this);
		(*this) <<= bits;
		t1 >>= (width - bits);
		(*this) |= t1;

		truncate(width);

		return *this;
	}

	/// Return true iff all bits are zero
	bool none() const
	{
		for (int i = 0; i < m_iRacks; ++i) {
			if (m_pcRacks[i]) {
				return false;
			}
		}
		return true;
	}

	/// Return 1 + the index of the first set bit, or 0 if there are none
	int fsb() const
	{
		for (int i = 0; i < m_iRacks; ++i) {
			const int j = ffs(m_pcRacks[i]);
			if (j) {
				return (i * FBV_BITS) + j;
			}
		}
		return 0;
	}

	/// Flip all bits (one's complement)
	CBigBitVec& flip()
	{
		for (int i = 0; i < m_iRacks; ++i) {
			m_pcRacks[i] = ~m_pcRacks[i];
		}
		return *this;
	}

	/// Return the first rack
	FBV_UINT& rack() { return m_pcRacks[0]; }
	FBV_UINT  rack() const { return m_pcRacks[0]; }

	/// Return a pointer to the racks
	FBV_UINT*       racks() { return m_pcRacks.get(); }
	const FBV_UINT* racks() const { return m_pcRacks.get(); }

	/// Return the number of racks
	int rackCount() const { return m_iRacks; }

private:
	// Right rotates entire racks (in place).
	void rackRotr(int k)
	{
		assert(0 <= k && k < m_iRacks);

		if (k == 0) {
			return;
		}

		int c = 0;
		for (int v = 0; c < m_iRacks; ++v) {
			int       t = v, tp = v + k;
			const int tmp = m_pcRacks[v];
			c++;
			while (tp != v) {
				m_pcRacks[t] = m_pcRacks[tp];
				t            = tp;
				tp += k;
				if (tp >= m_iRacks) {
					tp -= m_iRacks;
				}
				c++;
			}
			m_pcRacks[t] = tmp;
		}
	}

	std::unique_ptr<FBV_UINT[]> m_pcRacks;
	int                         m_iRacks;
};

template <>
void
grayCode(CBigBitVec& value)
{
	FBV_UINT s = 0;

	for (int i = value.rackCount() - 1; i >= 0; --i) {
		const FBV_UINT t = value.racks()[i] & 1;
		grayCode(value.racks()[i]);
		value.racks()[i] ^= (s << (FBV_BITS - 1));
		s = t;
	}
}

template <>
void
grayCodeInv(CBigBitVec& value)
{
	FBV_UINT s = 0;

	for (int i = value.rackCount() - 1; i >= 0; --i) {
		FBV_UINT& rack = value.racks()[i];
		grayCodeInv(rack);
		if (s) {
			rack = ~rack;
		}
		s = rack & 1;
	}
}

} // namespace chilbert

#endif