//! 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;

}

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

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

    return n / 32 + (1 if n % 32 > 0 else 0);

}

/// Allocate zeroed words for at least `len` bits in a session.

export fn allocate 'bits (storage: &Session 'bits, len: u32) -> &'bits mut [u32] throws (alloc::AllocError) {

    return try storage.fill(0 as u32, wordsFor(len));

}

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

export fn put(bs: &mut [u32], n: u32) {

    let word = n / 32;

    if word >= bs.len {

        return;

    }

    let b = n % 32;

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

}

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

export fn clear(bs: &mut [u32], n: u32) {

    let word = n / 32;

    if word >= bs.len {

        return;

    }

    let b = n % 32;

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

}

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

export fn contains(bs: &[u32], n: u32) -> bool {

    let word = n / 32;

    if word >= bs.len {

        return false;

    }

    let b = n % 32;

    return (bs[word] & (1 << b)) <> 0;

}

/// Count the number of set bits.

export fn count(bs: &[u32]) -> u32 {

    let mut total: u32 = 0;

    for word in bs {

        if word <> 0 {

            set total += popCount(word);

        }

    }

    return total;

}

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

fn popCount(x: u32) -> u32 {

    let mut n = x;

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

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

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

    set n += (n >> 8);

    set n += (n >> 16);

    return n & 0x3F;

}

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

export fn union_(dst: &mut [u32], src: &[u32]) {

    for i in 0..min(dst.len, src.len) {

        set dst[i] |= src[i];

    }

}

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

export fn subtract(dst: &mut [u32], src: &[u32]) {

    for i in 0..min(dst.len, src.len) {

        set dst[i] &= ~src[i];

    }

}

/// Check if two bitsets are equal.

export fn eq(a: &[u32], b: &[u32]) -> bool {

    let minWords = min(a.len, b.len);

    for i in 0..minWords {

        if a[i] <> b[i] {

            return false;

        }

    }

    for i in minWords..a.len {

        if a[i] <> 0 {

            return false;

        }

    }

    for i in minWords..b.len {

        if b[i] <> 0 {

            return false;

        }

    }

    return true;

}

/// Copy bits from source to destination.

export fn copy(dst: &mut [u32], src: &[u32]) {

    let minWords = min(dst.len, src.len);

    for i in 0..minWords {

        set dst[i] = src[i];

    }

    // Clear remaining words if destination is larger.

    for i in minWords..dst.len {

        set dst[i] = 0;

    }

}

/// Clear all bits.

export fn clearAll(bs: &mut [u32]) {

    for i in 0..bs.len {

        set bs[i] = 0;

    }

}

/// Iterator state for iterating set bits.

export record BitIter: Copy {

    /// Current word index.

    wordIdx: u32,

    /// Remaining bits in the current word (visited bits cleared).

    remaining: u32,

}

/// Create an iterator over set bits.

/// The cursor retains the first word mask and its position.

export fn iter(bs: &[u32]) -> BitIter {

    let remaining = bs[0] if bs.len > 0 else 0;

    return BitIter { wordIdx: 0, remaining };

}

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

/// The current word mask is a value snapshot; later words are read on demand.

export fn iterNext(it: &mut BitIter, bs: &[u32]) -> ?u32 {

    // Skip to next non-zero word.

    while it.remaining == 0 {

        set it.wordIdx += 1;

        if it.wordIdx >= bs.len {

            return nil;

        }

        set it.remaining = bs[it.wordIdx];

    }

    // Find lowest set bit position using de Bruijn sequence.

    let b = ctz(it.remaining);

    let n = it.wordIdx * 32 + b;

    // Clear the lowest set bit.

    set it.remaining &= it.remaining - 1;

    return n;

}

/// Count trailing zeros in a 32-bit value.

/// Returns the bit position of the lowest set bit (0-31).

/// Behavior is undefined if `x` is 0.

fn ctz(x: u32) -> u32 {

    // De Bruijn sequence for 32-bit CTZ.

    constant DEBRUIJN: u32 = 0x077CB531;

    constant TABLE: [u8; 32] = [

         0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8,

        31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9,

    ];

    // Isolate lowest set bit, multiply by de Bruijn constant, look up.

    let isolated = x & (~x + 1);

    return TABLE[(isolated * DEBRUIJN) >> 27] as u32;

}