/*
 * Copyright 2001-2010, Haiku Inc. All rights reserved.
 * This file may be used under the terms of the MIT License.
 *
 * Authors:
 *              Janito V. Ferreira Filho
 *              Jérôme Duval
 */


#include "BitmapBlock.h"

#include "CRCTable.h"


//#define TRACE_EXT2
#ifdef TRACE_EXT2
#       define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
#else
#       define TRACE(x...) ;
#endif
#define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)


BitmapBlock::BitmapBlock(Volume* volume, uint32 numBits)
        :
        CachedBlock(volume),
        fVolume(volume),
        fData(NULL),
        fReadOnlyData(NULL),
        fNumBits(numBits),
        fMaxIndex(fNumBits >> 5)
{
        TRACE("BitmapBlock::BitmapBlock(): num bits: %" B_PRIu32 "\n", fNumBits);
}


BitmapBlock::~BitmapBlock()
{
}


bool
BitmapBlock::SetTo(off_t block)
{
        fData = NULL;
        fReadOnlyData = (uint32*)CachedBlock::SetTo(block);

        return fReadOnlyData != NULL;
}


bool
BitmapBlock::SetToWritable(Transaction& transaction, off_t block, bool empty)
{
        fReadOnlyData = NULL;
        fData = (uint32*)CachedBlock::SetToWritable(transaction, block, empty);

        return fData != NULL;
}


bool
BitmapBlock::_Check(uint32 start, uint32 length, bool marked)
{
        const uint32* data = fData == NULL ? fReadOnlyData : fData;
        if (data == NULL)
                return false;

        if (start + length > fNumBits)
                return false;
        if (length == 0)
                return true;

        uint32 startIndex = start >> 5;
        uint32 startBit = start & 0x1F;
        uint32 remainingBits = (length + startBit) & 0x1F;

        uint32 iterations;
       
        if (length < 32) {
                if (startBit + length < 32) {
                        uint32 bits = B_LENDIAN_TO_HOST_INT32(data[startIndex]);

                        uint32 mask = (1 << (startBit + length)) - 1;
                        mask &= ~((1 << startBit) - 1);
                       
                        return (bits & mask) == (marked ? mask : 0);
                } else
                        iterations = 0;
        } else
                iterations = (length - 32 + startBit) >> 5;

        uint32 index = startIndex;
        
        if (startBit != 0) {
                uint32 mask = ~((1 << startBit) - 1);
                uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);

                if ((bits & mask) != (marked ? mask : 0)) {
                        TRACE("BitmapBlock::_Check(): start %" B_PRIx32 " mask %" B_PRIx32
                                "\n", bits, mask);
                        return false;
                }

                index += 1;
        } else
                iterations++;

        for (; iterations > 0; --iterations) {
                if (data[index++] != (marked ? 0xFFFFFFFF : 0)) {
                        TRACE("BitmapBlock::_Check(): iterations %" B_PRIu32 " bits: %"
                                B_PRIx32 "\n", iterations, data[index - 1]);
                        return false;
                }
        }

        if (remainingBits != 0) {
                uint32 mask = (1 << remainingBits) - 1;

                uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
                if ((bits & mask) != (marked ? mask : 0)) {
                        TRACE("BitmapBlock::_Check(): remainingBits %" B_PRIu32
                                " remaining %" B_PRIx32 " mask %" B_PRIx32 "\n", remainingBits,
                                bits, mask);
                        return false;
                }
        }

        return true;
}


bool
BitmapBlock::_Update(uint32 start, uint32 length, bool mark, bool force)
{
        TRACE("BitmapBlock::_Update(%" B_PRIu32 ", %" B_PRIu32 ", %c, %c)\n",
                start, length, mark ? 't' : 'f', force ? 't' : 'f');

        if (fData == NULL || start + length > fNumBits)
                return false;

        uint32 startIndex = start >> 5;
        uint32 startBit = start & 0x1F;
        uint32 remainingBits = (length + startBit) & 0x1F;

        TRACE("BitmapBlock::_Update(): start index: %" B_PRIu32 ", start bit: %"
                B_PRIu32 ", remaining bits: %" B_PRIu32 ")\n", startIndex, startBit,
                remainingBits);
        uint32 iterations;
       
        if (length < 32) {
                if (startBit + length < 32) {
                        uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
                        TRACE("BitmapBlock::_Update(): bits: %" B_PRIx32 "\n", bits);

                        uint32 mask = (1 << (startBit + length)) - 1;
                        mask &= ~((1 << startBit) - 1);
                       
                        TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 "\n", mask);

                        if ((bits & mask) != (mark ? 0 : mask)) {
                                ERROR("BitmapBlock::_Update() Marking failed bits %" B_PRIx32
                                        " startBit %" B_PRIu32 "\n", bits, startBit);
                                return false;
                        }
                       
                        if (mark)
                            bits |= mask;
                        else
                            bits &= ~mask;
                       
                        TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n",
                                bits);
                        fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits);
                       
                        return true;
                } else
                        iterations = 0;
        } else
                iterations = (length - 32 + startBit) >> 5;

        TRACE("BitmapBlock::_Update(): iterations: %" B_PRIu32 "\n", iterations);
        uint32 index = startIndex;
        
        if (startBit != 0) {
                uint32 mask = ~((1 << startBit) - 1);
                uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);

                TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 ", bits: %" B_PRIx32
                        "\n", mask, bits);

                if (!force && (bits & mask) != (mark ? 0 : mask))
                        return false;

                if (mark)
                        bits |= mask;
                else
                        bits &= ~mask;
                fData[index] = B_HOST_TO_LENDIAN_INT32(bits);

                TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n", bits);
                index += 1;
        } else
                iterations++;

        for (; iterations > 0; --iterations) {
                if (!force && fData[index] != (mark ? 0 : 0xFFFFFFFF)) {
                        ERROR("BitmapBlock::_Update() Marking failed "
                                "index %" B_PRIu32 ", iterations %" B_PRId32 "\n", index,
                                iterations);
                        return false;
                }
                fData[index++] = (mark ? 0xFFFFFFFF : 0);
        }

        TRACE("BitmapBlock::_Update(): Finished iterations\n");

        if (remainingBits != 0) {
                uint32 mask = (1 << remainingBits) - 1;
                uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);

                TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 ", bits: %" B_PRIx32
                        "\n", mask, bits);

                if (!force && (bits & mask) != (mark ? 0 : mask)) {
                        ERROR("BitmapBlock::_Update() Marking failed remaining\n");
                        return false;
                }

                if (mark)
                        bits |= mask;
                else
                        bits &= ~mask;
                fData[index] = B_HOST_TO_LENDIAN_INT32(bits);

                TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n", bits);
        }

        return true;
}


void
BitmapBlock::_FindNext(uint32& pos, bool marked)
{
        TRACE("BitmapBlock::_FindNext(): pos: %" B_PRIu32 "\n", pos);

        const uint32* data = fData == NULL ? fReadOnlyData : fData;
        if (data == NULL)
                return;

        if (pos >= fNumBits) {
                pos = fNumBits;
                return;
        }

        uint32 index = pos >> 5;
        uint32 bit = pos & 0x1F;
        uint32 maxBit = 32;

        uint32 mask = ~((1 << bit) - 1);
        uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);

        TRACE("BitmapBlock::_FindNext(): index: %" B_PRIu32 ", bit: %" B_PRIu32
                ", mask: %" B_PRIx32 ", bits: %" B_PRIx32 "\n", index, bit, mask,
                bits);

        bits &= mask;
        if (bits == (marked ? 0 : mask) && index < fMaxIndex) {
                // Find a 32 bits block that has a marked bit
                do {
                        index++;
                } while (index < fMaxIndex && data[index] == (marked ? 0 : 0xFFFFFFFF));
                bit = 0;
                mask = 0xffffffff;
        }

        if (index >= fMaxIndex) {
                maxBit = fNumBits & 0x1F;

                if (maxBit == 0) {
                        // Not found
                        TRACE("BitmapBlock::_FindNext(): reached end of block, "
                                "num bits: %" B_PRIu32 "\n", fNumBits);
                        pos = fNumBits;
                        return;
                }
                bits = B_LENDIAN_TO_HOST_INT32(data[fMaxIndex]);
                mask &= (1 << maxBit) - 1;
                if ((bits & mask) == (marked ? 0 : mask)) {
                        TRACE("BitmapBlock::_FindNext(): reached end of block, "
                                "num bits: %" B_PRIu32 "\n", fNumBits);
                        pos = fNumBits;
                        return;
                }
                maxBit++;
        } else
                bits = B_LENDIAN_TO_HOST_INT32(data[index]);

        for (; bit < maxBit; ++bit) {
                // Find the marked bit
                if ((bits >> bit & 1) != (marked ? 0U : 1U)) {
                        pos = index << 5 | bit;
                        TRACE("BitmapBlock::_FindNext(): found bit: %" B_PRIu32 "\n", pos);
                        return;
                }
        }

        panic("Couldn't find bit inside an uint32 (%" B_PRIx32 ")\n", bits);
}


void
BitmapBlock::FindPreviousMarked(uint32& pos)
{
        TRACE("BitmapBlock::FindPreviousMarked(%" B_PRIu32 ")\n", pos);
        const uint32* data = fData == NULL ? fReadOnlyData : fData;
        if (data == NULL)
                return;

        if (pos >= fNumBits)
                pos = fNumBits;

        if (pos == 0)
                return;

        uint32 index = pos >> 5;
        int32 bit = pos & 0x1F;

        uint32 mask = (1 << bit) - 1;
        uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
        bits = bits & mask;

        TRACE("BitmapBlock::FindPreviousMarked(): index: %" B_PRIu32 " bit: %"
                B_PRIu32 " bits: %" B_PRIx32 "\n", index, bit, bits);

        if (bits == 0) {
                // Find a block of 32 bits that has a marked bit
                if (index > 0) {
                        do {
                                index--;
                        } while (data[index] == 0 && index > 0);

                        bits = B_LENDIAN_TO_HOST_INT32(data[index]);
                }
                if (bits == 0) {
                        // Not found
                        pos = 0;
                        return;
                }

                bit = 31;
        }

        TRACE("BitmapBlock::FindPreviousMarked(): index: %" B_PRIu32 " bit: %"
                B_PRIu32 " bits: %" B_PRIx32 "\n", index, bit, bits);

        for (; bit >= 0; --bit) {
                // Find the marked bit
                if ((bits >> bit & 1) != 0) {
                        pos = index << 5 | bit;
                        return;
                }
        }

        panic("Couldn't find marked bit inside an int32 with value different than "
                "zero!?\n");
}


void
BitmapBlock::FindLargestUnmarkedRange(uint32& start, uint32& length)
{
        const uint32* data = fData == NULL ? fReadOnlyData : fData;
        if (data == NULL)
                return;

        uint32 wordSpan = length >> 5;
        uint32 startIndex = 0;
        uint32 index = 0;
        uint32 bits = B_LENDIAN_TO_HOST_INT32(data[0]);

        TRACE("BitmapBlock::FindLargestUnmarkedRange(): word span: %" B_PRIu32
                ", last index: %" B_PRIu32 ", start index: %" B_PRIu32 ", index: %"
                B_PRIu32 ", bits: %" B_PRIx32 ", start: %" B_PRIu32 ", length: %"
                B_PRIu32 "\n", wordSpan, fMaxIndex, startIndex, index, bits, start,
                length);

        if (wordSpan == 0) {
                uint32 startPos = 0;
                uint32 endPos = 0;

                while (endPos < fNumBits) {
                        FindNextUnmarked(startPos);
                        endPos = startPos;

                        if (startPos != fNumBits) {
                                FindNextMarked(endPos);

                                uint32 newLength = endPos - startPos;

                                if (newLength > length) {
                                        start = startPos;
                                        length = newLength;
                                        TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
                                                "larger length %" B_PRIu32 " starting at %" B_PRIu32
                                                "\n", length, start);
                                } 

                                startPos = endPos;

                                if (newLength >= 32)
                                        break;
                        }
                }
                
                if (endPos >= fNumBits)
                        return;

                wordSpan = length >> 5;
                startIndex = startPos >> 5;
                index = (endPos >> 5) + 1;
                bits = B_LENDIAN_TO_HOST_INT32(data[index]);
        }

        for (; index < fMaxIndex; ++index) {
                bits = B_LENDIAN_TO_HOST_INT32(data[index]);

                if (bits != 0) {
                        // Contains marked bits
                        if (index - startIndex >= wordSpan) {
                                uint32 newLength = (index - startIndex - 1) << 5;
                                uint32 newStart = (startIndex + 1) << 5;

                                uint32 startBits =
                                        B_LENDIAN_TO_HOST_INT32(data[startIndex]);

                                for (int32 bit = 31; bit >= 0; --bit) {
                                        if ((startBits >> bit & 1) != 0)
                                                break;

                                        ++newLength;
                                        --newStart;
                                }

                                for (int32 bit = 0; bit < 32; ++bit) {
                                        if ((bits >> bit & 1) != 0)
                                                break;

                                        ++newLength;
                                }

                                if (newLength > length) {
                                        start = newStart;
                                        length = newLength;
                                        wordSpan = length >> 5;
                                        
                                        TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
                                                "larger length %" B_PRIu32 " starting at %" B_PRIu32
                                                "; word span: %" B_PRIu32 "\n", length, start,
                                                wordSpan);
                                }
                        }

                        startIndex = index;
                }
        }
        
        --index;

        if (index - startIndex >= wordSpan) {
                uint32 newLength = (index - startIndex) << 5;
                uint32 newStart = (startIndex + 1) << 5;
                
                TRACE("BitmapBlock::FindLargestUnmarkedRange(): Possibly found a "
                        "larger range. index: %" B_PRIu32 ", start index: %" B_PRIu32
                        ", word span: %" B_PRIu32 ", new length: %" B_PRIu32
                        ", new start: %" B_PRIu32 "\n", index, startIndex, wordSpan,
                        newLength, newStart);

                if (newStart != 0) {
                        uint32 startBits = B_LENDIAN_TO_HOST_INT32(data[startIndex]);
                        
                        TRACE("BitmapBlock::FindLargestUnmarkedRange(): start bits: %"
                                B_PRIu32 "\n", startBits);

                        for (int32 bit = 31; bit >= 0; --bit) {
                                if ((startBits >> bit & 1) != 0)
                                        break;

                                ++newLength;
                                --newStart;
                        }
                        
                        TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new start "
                                "to %" B_PRIu32 " and new length to %" B_PRIu32 "\n", newStart,
                                newLength);
                }

                for (int32 bit = 0; bit < 32; ++bit) {
                        if ((bits >> bit & 1) == 0)
                                break;

                        ++newLength;
                }
                
                TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new length to "
                        "%" B_PRIu32 "\n", newLength);

                if (newLength > length) {
                        start = newStart;
                        length = newLength;
                        TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
                                "largest length %" B_PRIu32 " starting at %" B_PRIu32 "\n",
                                length, start);
                }
        }
}


uint32
BitmapBlock::Checksum(uint32 unitsPerGroup) const
{
        const uint32* data = fData == NULL ? fReadOnlyData : fData;
        if (data == NULL)
                panic("BitmapBlock::Checksum() data is NULL\n");
        return calculate_crc32c(fVolume->ChecksumSeed(),
                (uint8*)data, unitsPerGroup / 8);
}