dymokomi/luce-browser-foundation
Source of release 0.6.0
0.6.0 / 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