module tools.bitinfogen;

struct BitRange
{
    ubyte start;
    ubyte count;
}

enum BitInfoFlags
{
    none,
    hasPrefixZero = 1 << 0,
    hasSuffixZero = 1 << 1
}

struct BitInfo
{
    ubyte unsetCount;
    ubyte largestBitRangeCount;
    BitRange[8] bitRangeForSize; // BitRange.init stands for "no range". Bigger bit ranges will stand in for smaller ones if there's no dedicated smaller one.
    BitRange bitRangeForPrefix; // Only set for hasPrefixZero
    BitRange bitRangeForSuffix; // Only set for hasSuffixZero
    BitInfoFlags flags;
}

void main()
{
    import std;

    BitInfo[256] bitInfo;
    findBitInfo(bitInfo);
    ensureInProjectRoot();
    const masks = findBitMasks(bitInfo);
    const code  = formatBitInfoIntoCode(bitInfo, masks);
    std.file.write("source/libd/datastructures/_bitinfo.d", code);
}

void ensureInProjectRoot()
{
    import std : exists, chdir;
    while(!exists("dub.sdl"))
        chdir("..");
}

string formatBitInfoIntoCode(BitInfo[256] bitInfo, const ubyte[] masks)
{
    import std : Appender, assumeUnique, format;

    Appender!(char[]) output;

    output.put(`// This file is generated by tools/bitinfogen.d
module libd.datastructures._bitinfo;

package:

struct BitRange
{
    ubyte start;
    ubyte count;
}

enum BitInfoFlags
{
    none,
    hasPrefixZero = 1 << 0,
    hasSuffixZero = 1 << 1
}

struct BitInfo
{
    ubyte unsetCount;
    ubyte largestBitRangeCount;
    BitRange bitRangeForPrefix; // Only set for hasPrefixZero
    BitRange bitRangeForSuffix; // Only set for hasSuffixZero
    BitInfoFlags flags;
    BitRange[8] bitRangeForSize; // BitRange.init stands for "no range". Bigger bit ranges will stand in for smaller ones if there's no dedicated smaller one.
}

immutable BitInfo[256] BIT_INFO = 
[  
`);
    foreach(info; bitInfo)
    {
        output.put(format!"    BitInfo(%s, %s, BitRange(%s, %s), BitRange(%s, %s), cast(BitInfoFlags)%s, ["(
            info.unsetCount, info.largestBitRangeCount,
            info.bitRangeForPrefix.start, info.bitRangeForPrefix.count,
            info.bitRangeForSuffix.start, info.bitRangeForSuffix.count,
            cast(int)info.flags
        ));
        foreach(range; info.bitRangeForSize)
        {
            output.put(format!"BitRange(%s, %s), "(
                range.start, range.count
            ));
        }
        output.put("]),\n");
    }
    output.put("];");

    output.put(`
immutable ubyte[%s] BIT_MASKS =
[
    `.format(masks.length));
    foreach(mask; masks)
        output.put(format!"0x%X, "(mask));
    output.put("\n];");

    return output.data.assumeUnique;
}

ubyte[] findBitMasks(ref BitInfo[256] bitInfo)
{
    import std : map;

    ubyte[] data;
    foreach(start; 0..8)
    {
        foreach(count; 1..9)
        {
            const index   = (start * 10) + count;
            const maskBit = 1 << start;
            ubyte mask    = cast(ubyte)maskBit;
            foreach(_; 0..count-1)
            {
                mask <<= 1;
                mask |= cast(ubyte)maskBit;
            }

            if(data.length <= index)
                data.length = index+1;
            data[index] = mask;
        }
    }
    return data;
}

void findBitInfo(ref BitInfo[256] bitInfo)
{
    foreach(i; 0..ubyte.max+1)
    {
        const b = cast(ubyte)i;
        bitInfo[i].unsetCount = findUnsetCount(b);

        ubyte bitIndex;
        while(bitIndex < 8)
        {
            auto range = nextBitRange(b, bitIndex);
            if(range.count == 0)
                continue;

            if(range.count > bitInfo[i].largestBitRangeCount)
                bitInfo[i].largestBitRangeCount = range.count;
            if(range.start == 0)
            {
                bitInfo[i].flags |= BitInfoFlags.hasPrefixZero;
                bitInfo[i].bitRangeForPrefix = range;
            }
            if(range.start + range.count == 8)
            {
                bitInfo[i].flags |= BitInfoFlags.hasSuffixZero;
                bitInfo[i].bitRangeForSuffix = range;
            }

            foreach(ref r; bitInfo[i].bitRangeForSize[0..range.count])
            {
                if(r.count == 0 || range.count < r.count)
                    r = range;
            }
        }
    }
}

ubyte findUnsetCount(ubyte b)
{
    ubyte count;    
    foreach(i; 0..8)
        count += (b & (1 << i)) == 0;
    return count;
}

BitRange nextBitRange(ubyte b, ref ubyte bitIndex)
{
    BitRange range;
    range.start = bitIndex;

    while(bitIndex < 8)
    {
        const isUnset = (b & (1 << bitIndex++)) == 0;
        if(!isUnset)
        {
            if(range.count == 0)
            {
                range.start = bitIndex;
                continue;
            }
            break;
        }
        range.count++;
    }

    return range;
}