Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / bitmap_view.lucb

#==============================================================================================
#
#   bitmap_view - BitmapView: a non-owning view of a bit array
#
#   DESCRIPTION:
#       Port of AK/BitmapView.h (lines 1-385) and of the bit-counting helpers of
#       AK/BuiltinWrappers.h it uses (popcount, bit_scan_forward, count_trailing_zeroes).
#       The donor scans whole size_t words where it can; so does this port, reading words
#       through aligned pointers exactly where the donor does.
#
#==============================================================================================

# mark: BuiltinWrappers.h helpers ===============================================================

# popcount(u8).
func bitmap_popcount_u8(value: u8) -> usize:
    var v = value
    var count: usize = 0
    while v != 0:
        count += (usize)(v & 1)
        v = v >> 1
    return count

# popcount(size_t).
func bitmap_popcount_usize(value: usize) -> usize:
    var v = value
    var count: usize = 0
    while v != 0:
        v = v & (v - 1)
        count += 1
    return count

# bit_scan_forward: one plus the index of the lowest set bit, 0 for zero.
func bitmap_bit_scan_forward(value: usize) -> usize:
    if value == 0:
        return 0
    return (usize)bitmap_count_trailing_zeroes(value) + 1

# count_trailing_zeroes (__builtin_ctzl: undefined for zero).
func bitmap_count_trailing_zeroes(value: usize) -> u32:
    assert(value != 0)
    var count: u32 = 0
    var v = value
    while (v & 1) == 0:
        count += 1
        v = v >> 1
    return count

# mark: BitmapView ==============================================================================

## Ported from AK/BitmapView.h:24 AK::BitmapView::BitmapView.
pub func bitmap_view_construct(this: BitmapView*, data: u8*?, size: usize):
    this.m_data = data
    this.m_size = size

## Ported from AK/BitmapView.h:30 AK::BitmapView::size.
pub func bitmap_view_size(this: const BitmapView*) -> usize:
    return this.m_size

## Ported from AK/BitmapView.h:31 AK::BitmapView::size_in_bytes.
pub func bitmap_view_size_in_bytes(this: const BitmapView*) -> usize:
    return ceil_div_usize(this.m_size, 8)

# m_data, which every non-empty view has.
func bitmap_view_bytes(this: const BitmapView*) -> u8*:
    return this.m_data else trap("VERIFY: BitmapView has no data")

## Ported from AK/BitmapView.h:32 AK::BitmapView::get.
pub func bitmap_view_get(this: const BitmapView*, index: usize) -> bool:
    assert(index < this.m_size)
    return 0 != (bitmap_view_bytes(this)[index // 8] & ((u8)1 << (u8)(index % 8)))

## Ported from AK/BitmapView.h:38 AK::BitmapView::count_slow.
pub func bitmap_view_count_slow(this: const BitmapView*, value: bool) -> usize:
    return bitmap_view_count_in_range(this, 0, this.m_size, value)

## Ported from AK/BitmapView.h:43 AK::BitmapView::count_in_range.
pub func bitmap_view_count_in_range(this: const BitmapView*, start: usize, len: usize, value: bool) -> usize:
    assert(start < this.m_size)
    assert(start + len <= this.m_size)
    if len == 0:
        return 0

    let data = bitmap_view_bytes(this)
    var count: usize
    var first = data + start // 8
    let last = data + (start + len) // 8
    var byte = *first
    byte = byte & bitmask_first_byte[start % 8]
    if first == last:
        byte = byte & bitmask_last_byte[(start + len) % 8]
        count = bitmap_popcount_u8(byte)
    else:
        count = bitmap_popcount_u8(byte)
        # Don't access *last if it's out of bounds
        if last < data + bitmap_view_size_in_bytes(this):
            byte = *last
            byte = byte & bitmask_last_byte[(start + len) % 8]
            count += bitmap_popcount_u8(byte)
        first = first + 1
        if first < last:
            var ptr_large = (usize*)(void*)(u8*)(((usize)first + memory.size_of(usize) - 1) & ~(memory.size_of(usize) - 1))
            if (u8*)(void*)ptr_large > last:
                ptr_large = (usize*)(void*)last
            while first < (u8*)(void*)ptr_large:
                count += bitmap_popcount_u8(*first)
                first = first + 1
            let last_large = (usize*)(void*)(u8*)((usize)last & ~(memory.size_of(usize) - 1))
            while ptr_large < last_large:
                count += bitmap_popcount_usize(*ptr_large)
                ptr_large = ptr_large + 1
            first = (u8*)(void*)ptr_large
            while first < last:
                count += bitmap_popcount_u8(*first)
                first = first + 1

    if not value:
        count = len - count
    return count

## Ported from AK/BitmapView.h:89 AK::BitmapView::is_null.
pub func bitmap_view_is_null(this: const BitmapView*) -> bool:
    return this.m_data == none

## Ported from AK/BitmapView.h:91 AK::BitmapView::data.
pub func bitmap_view_data(this: const BitmapView*) -> const u8*?:
    return this.m_data

# AK/BitmapView.h:94 AK::BitmapView::find_one_anywhere<VALUE>.
func bitmap_view_find_one_anywhere(this: const BitmapView*, value: bool, start_hint: usize) -> usize?:
    var hint = start_hint
    assert(hint < this.m_size)
    let data = bitmap_view_bytes(this)
    var end = data + bitmap_view_size_in_bytes(this)

    while true:
        # We will use hint as what it is: a hint. Because we try to
        # scan over entire 32 bit words, we may start searching before
        # the hint!
        var ptr_large = (usize*)(void*)(u8*)((usize)(data + hint // 8) & ~(memory.size_of(usize) - 1))
        if (u8*)(void*)ptr_large < data:
            ptr_large = ptr_large + 1

            # m_data isn't aligned, check first bytes
            let start_ptr_large = (usize)((u8*)(void*)ptr_large - data)
            var i: usize = 0
            var byte: u8 = 0x00 if value else 0xff
            while i < start_ptr_large and data[i] == byte:
                i += 1
            if i < start_ptr_large:
                byte = data[i]
                if not value:
                    byte = ~byte
                assert(byte != 0)
                return i * 8 + bitmap_bit_scan_forward(byte) - 1

        var val_large: usize = 0x0 if value else usize_max
        let end_large = (usize*)(void*)(u8*)((usize)end & ~(memory.size_of(usize) - 1))
        while ptr_large < end_large and *ptr_large == val_large:
            ptr_large = ptr_large + 1

        if ptr_large == end_large:
            # We didn't find anything, check the remaining few bytes (if any)
            var byte: u8 = 0x00 if value else 0xff
            var i = (usize)((u8*)(void*)ptr_large - data)
            let byte_count = bitmap_view_size_in_bytes(this)
            assert(i <= byte_count)
            while i < byte_count and data[i] == byte:
                i += 1
            if i == byte_count:
                if hint <= 8:
                    return none  # We already checked from the beginning

                # Try scanning before the hint
                end = (u8*)((usize)(data + hint // 8) & ~(memory.size_of(usize) - 1))
                hint = 0
                continue
            byte = data[i]
            if not value:
                byte = ~byte
            assert(byte != 0)
            return i * 8 + bitmap_bit_scan_forward(byte) - 1

        # NOTE: We don't really care about byte ordering. We found *one*
        # free bit, just calculate the position and return it
        val_large = *ptr_large
        if not value:
            val_large = ~val_large
        assert(val_large != 0)
        return (usize)((u8*)(void*)ptr_large - data) * 8 + bitmap_bit_scan_forward(val_large) - 1

## Ported from AK/BitmapView.h:161 AK::BitmapView::find_one_anywhere_set.
pub func bitmap_view_find_one_anywhere_set(this: const BitmapView*, hint: usize = 0) -> usize?:
    return bitmap_view_find_one_anywhere(this, true, hint)

## Ported from AK/BitmapView.h:166 AK::BitmapView::find_one_anywhere_unset.
pub func bitmap_view_find_one_anywhere_unset(this: const BitmapView*, hint: usize = 0) -> usize?:
    return bitmap_view_find_one_anywhere(this, false, hint)

# AK/BitmapView.h:171 AK::BitmapView::find_first<VALUE>.
func bitmap_view_find_first(this: const BitmapView*, value: bool) -> usize?:
    let byte_count = bitmap_view_size_in_bytes(this)
    var i: usize = 0

    let data = bitmap_view_bytes(this)
    var byte: u8 = 0x00 if value else 0xff
    while i < byte_count and data[i] == byte:
        i += 1
    if i == byte_count:
        return none

    byte = data[i]
    if not value:
        byte = ~byte
    assert(byte != 0)
    return i * 8 + bitmap_bit_scan_forward(byte) - 1

## Ported from AK/BitmapView.h:190 AK::BitmapView::find_first_set.
pub func bitmap_view_find_first_set(this: const BitmapView*) -> usize?:
    return bitmap_view_find_first(this, true)

## Ported from AK/BitmapView.h:191 AK::BitmapView::find_first_unset.
pub func bitmap_view_find_first_unset(this: const BitmapView*) -> usize?:
    return bitmap_view_find_first(this, false)

## Ported from AK/BitmapView.h:202 AK::BitmapView::find_next_range_of_unset_bits.
# The function will return the next range of unset bits starting from the
# @from value.
# @from: the position from which the search starts. The var will be
#        changed and new value is the offset of the found block.
# @min_length: minimum size of the range which will be returned.
# @max_length: maximum size of the range which will be returned.
#              This is used to increase performance, since the range of
#              unset bits can be long, and we don't need the while range,
#              so we can stop when we've reached @max_length.
pub func bitmap_view_find_next_range_of_unset_bits(this: const BitmapView*, from_: usize*, min_length: usize = 1, max_length: usize = bitmap_view_max_size) -> usize?:
    if min_length > max_length:
        return none

    let bit_size = 8 * memory.size_of(usize)

    let bitmap = (usize*)(void*)bitmap_view_bytes(this)

    # Calculating the start offset.
    let start_bucket_index = *from_ // bit_size
    var start_bucket_bit = *from_ % bit_size

    let start_of_free_chunks = from_
    var free_chunks: usize = 0

    for bucket_index in start_bucket_index..<this.m_size // bit_size:
        if bitmap[bucket_index] == usize_max:
            # Skip over completely full bucket of size bit_size.
            if free_chunks >= min_length:
                return min_usize(free_chunks, max_length)
            free_chunks = 0
            start_bucket_bit = 0
            continue
        if bitmap[bucket_index] == 0x0:
            # Skip over completely empty bucket of size bit_size.
            if free_chunks == 0:
                *start_of_free_chunks = bucket_index * bit_size
            free_chunks += bit_size
            if free_chunks >= max_length:
                return max_length
            start_bucket_bit = 0
            continue

        var bucket = bitmap[bucket_index]
        var viewed_bits = (u8)start_bucket_bit
        var trailing_zeroes: u32 = 0

        bucket = bucket >> (usize)viewed_bits
        start_bucket_bit = 0

        while (usize)viewed_bits < bit_size:
            if bucket == 0:
                if free_chunks == 0:
                    *start_of_free_chunks = bucket_index * bit_size + (usize)viewed_bits
                free_chunks += bit_size - (usize)viewed_bits
                viewed_bits = (u8)bit_size
            else:
                trailing_zeroes = bitmap_count_trailing_zeroes(bucket)
                bucket = bucket >> (usize)trailing_zeroes

                if free_chunks == 0:
                    *start_of_free_chunks = bucket_index * bit_size + (usize)viewed_bits
                free_chunks += (usize)trailing_zeroes
                viewed_bits += (u8)trailing_zeroes

                if free_chunks >= min_length:
                    return min_usize(free_chunks, max_length)

                # Deleting trailing ones.
                let trailing_ones = bitmap_count_trailing_zeroes(~bucket)
                bucket = bucket >> (usize)trailing_ones
                viewed_bits += (u8)trailing_ones
                free_chunks = 0

    if free_chunks < min_length:
        let first_trailing_bit = (this.m_size // bit_size) * bit_size
        let trailing_bits = bitmap_view_size(this) % bit_size
        for i in 0..<trailing_bits:
            if not bitmap_view_get(this, first_trailing_bit + i):
                if free_chunks == 0:
                    *start_of_free_chunks = first_trailing_bit + i
                free_chunks += 1
                if free_chunks >= min_length:
                    return min_usize(free_chunks, max_length)
            else:
                free_chunks = 0
        return none

    return min_usize(free_chunks, max_length)

# min<size_t>.
func min_usize(a: usize, b: usize) -> usize:
    return b if b < a else a

## Ported from AK/BitmapView.h:298 AK::BitmapView::find_longest_range_of_unset_bits.
pub func bitmap_view_find_longest_range_of_unset_bits(this: const BitmapView*, max_length: usize, found_range_size: usize*) -> usize?:
    var start: usize = 0
    var max_region_start: usize = 0
    var max_region_size: usize = 0

    while true:
        # Look for the next block which is bigger than currunt.
        if let length_of_found_range = bitmap_view_find_next_range_of_unset_bits(this, &start, max_region_size + 1, max_length):
            max_region_start = start
            max_region_size = length_of_found_range
            start += max_region_size
        else:
            # No ranges which are bigger than current were found.
            break

    *found_range_size = max_region_size
    if max_region_size != 0:
        return max_region_start
    return none

## Ported from AK/BitmapView.h:324 AK::BitmapView::find_first_fit.
pub func bitmap_view_find_first_fit(this: const BitmapView*, minimum_length: usize) -> usize?:
    var start: usize = 0
    if bitmap_view_find_next_range_of_unset_bits(this, &start, minimum_length, minimum_length) != none:
        return start
    return none

## Ported from AK/BitmapView.h:334 AK::BitmapView::find_best_fit.
pub func bitmap_view_find_best_fit(this: const BitmapView*, minimum_length: usize) -> usize?:
    var start: usize = 0
    var best_region_start: usize = 0
    var best_region_size = bitmap_view_max_size
    var found = false

    while true:
        # Look for the next block which is bigger than requested length.
        if let length_of_found_range = bitmap_view_find_next_range_of_unset_bits(this, &start, minimum_length, best_region_size):
            if best_region_size > length_of_found_range or not found:
                best_region_start = start
                best_region_size = length_of_found_range
                found = true
            start += length_of_found_range
        else:
            # There are no ranges which can fit requested length.
            break

    if found:
        return best_region_start
    return none

## Ported from AK/BitmapView.h:365 AK::BitmapView::operator==.
pub func bitmap_view_eq(this: const BitmapView*, other: BitmapView) -> bool:
    if bitmap_view_size(this) != bitmap_view_size(&other):
        return false
    for i in 0..<bitmap_view_size_in_bytes(this):
        if bitmap_view_bytes(this)[i] != bitmap_view_bytes(&other)[i]:
            return false
    return true