//! Bitset utilities for register tracking.

//!

//! Provides efficient bit-level set operations for tracking live registers

//! during liveness analysis and register allocation.

@test mod tests;

use std::lang::alloc;

/// Return the minimum of two 32-bit values.

fn min(a: u32, b: u32) -> u32 {

    if a < b {

        return a;

    }

    return b;

}

/// Return the maximum of two 32-bit values.

fn max(a: u32, b: u32) -> u32 {

    if a > b {

        return a;

    }

    return b;

}

/// Calculate the number of 32-bit words needed to store `n` bits.

pub fn wordsFor(n: u32) -> u32 {

    return (n + 31) / 32;

}

/// A fixed-size bitset backed by an array of 32-bit words.

pub record Bitset {

    /// Backing storage for bits, organized as 32-bit words.

    bits: *mut [u32],

    /// Number of bits this bitset can hold.

    len: u32,

}

/// Create a new bitset backed by the given zero-initialized storage.

pub fn new(bits: *mut [u32]) -> Bitset {

    return Bitset { bits, len: bits.len * 32 };

}

/// Create a new bitset backed by the given storage, zeroing it first.

pub fn init(bits: *mut [u32]) -> Bitset {

    for i in 0..bits.len {

        bits[i] = 0;

    }

    return new(bits);

}

/// Create a bitset from arena allocation.

pub fn allocate(arena: *mut alloc::Arena, len: u32) -> Bitset throws (alloc::AllocError) {

    let numWords = wordsFor(len);

    let bits = try alloc::allocSlice(arena, @sizeOf(u32), @alignOf(u32), numWords) as *mut [u32];

    return init(bits);

}

/// Set bit `n` in the bitset.

pub fn set(bs: *mut Bitset, n: u32) {

    if n >= bs.len {

        return;

    }

    let word = n / 32;

    let b = n % 32;

    bs.bits[word] |= (1 << b);

}

/// Clear bit `n` in the bitset.

pub fn clear(bs: *mut Bitset, n: u32) {

    if n >= bs.len {

        return;

    }

    let word = n / 32;

    let b = n % 32;

    bs.bits[word] &= ~(1 << b);

}

/// Check if bit `n` is set.

pub fn contains(bs: *Bitset, n: u32) -> bool {

    if n >= bs.len {

        return false;

    }

    let word = n / 32;

    let b = n % 32;

    return (bs.bits[word] & (1 << b)) != 0;

}

/// Count the number of set bits.

pub fn count(bs: *Bitset) -> u32 {

    let mut total: u32 = 0;

    let numWords = wordsFor(bs.len);

    for i in 0..numWords {

        total += popCount(bs.bits[i]);

    }

    return total;

}

/// Population count for a 32-bit word.

fn popCount(x: u32) -> u32 {

    let mut n = x;

    n -= ((n >> 1) & 0x55555555);

    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);

    n = (n + (n >> 4)) & 0x0F0F0F0F;

    n += (n >> 8);

    n += (n >> 16);

    return n & 0x3F;

}

/// Union: `dst = dst | src`.

pub fn union_(dst: *mut Bitset, src: *Bitset) {

    let numWords = wordsFor(dst.len);

    let srcWords = wordsFor(src.len);

    let minWords = min(numWords, srcWords);

    for i in 0..minWords {

        dst.bits[i] |= src.bits[i];

    }

}

/// Subtract: `dst = dst - src`.

pub fn subtract(dst: *mut Bitset, src: *Bitset) {

    let numWords = wordsFor(dst.len);

    let srcWords = wordsFor(src.len);

    let minWords = min(numWords, srcWords);

    for i in 0..minWords {

        dst.bits[i] &= ~src.bits[i];

    }

}

/// Check if two bitsets are equal.

pub fn eq(a: *Bitset, b: *Bitset) -> bool {

    let numWordsA = wordsFor(a.len);

    let numWordsB = wordsFor(b.len);

    let maxWords = max(numWordsA, numWordsB);

    for i in 0..maxWords {

        let wordA = a.bits[i] if i < numWordsA else 0;

        let wordB = b.bits[i] if i < numWordsB else 0;

        if wordA != wordB {

            return false;

        }

    }

    return true;

}

/// Copy bits from source to destination.

pub fn copy(dst: *mut Bitset, src: *Bitset) {

    let numWords = wordsFor(dst.len);

    let srcWords = wordsFor(src.len);

    let minWords = min(numWords, srcWords);

    for i in 0..minWords {

        dst.bits[i] = src.bits[i];

    }

    // Clear remaining words if destination is larger.

    for i in minWords..numWords {

        dst.bits[i] = 0;

    }

}

/// Clear all bits.

pub fn clearAll(bs: *mut Bitset) {

    let numWords = wordsFor(bs.len);

    for i in 0..numWords {

        bs.bits[i] = 0;

    }

}

/// Iterator state for iterating set bits.

pub record BitIter {

    bs: *Bitset,

    wordIdx: u32,

    bitIdx: u32,

}

/// Create an iterator over set bits.

pub fn iter(bs: *Bitset) -> BitIter {

    return BitIter { bs, wordIdx: 0, bitIdx: 0 };

}

/// Get the next set bit, or nil if none remain.

pub fn iterNext(it: *mut BitIter) -> ?u32 {

    let numWords = wordsFor(it.bs.len);

    while it.wordIdx < numWords {

        let word = it.bs.bits[it.wordIdx];

        // Skip empty words entirely.

        if word == 0 and it.bitIdx == 0 {

            it.wordIdx += 1;

        } else {

            while it.bitIdx < 32 {

                let n = it.wordIdx * 32 + it.bitIdx;

                if n >= it.bs.len {

                    return nil;

                }

                it.bitIdx += 1;

                if (word & (1 << (it.bitIdx - 1))) != 0 {

                    return n;

                }

            }

            it.wordIdx += 1;

            it.bitIdx = 0;

        }

    }

    return nil;

}