Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / tests_bitmap.lucb

#==============================================================================================
#
#   tests_bitmap - Bitmap and BitmapView
#
#   DESCRIPTION:
#       Port of Tests/AK/TestBitmap.cpp. The randomized cases run over a fixed set of
#       seeds from testing.random().
#
#==============================================================================================

# MUST(Bitmap::create(size, value)).
func test_bitmap(size: usize, value: bool) -> Bitmap:
    return bitmap_create(size, value) else trap("MUST: Bitmap::create")

# Releases a test bitmap's storage (the donor's ~Bitmap).
func test_bitmap_free(bitmap: Bitmap*):
    kfree(bitmap.bitmap_view.m_data)

test "bitmap: construct_empty":
    var bitmap: Bitmap
    bitmap_init_fields(&bitmap)
    assert(bitmap_view_size(&bitmap.bitmap_view) == 0)

test "bitmap: find_first_set and find_first_unset":
    var bitmap = test_bitmap(128, false)
    bitmap_set(&bitmap, 69, true)
    assert((bitmap_view_find_first_set(&bitmap.bitmap_view) else trap("none")) == 69)
    var other = test_bitmap(128, true)
    bitmap_set(&other, 51, false)
    assert((bitmap_view_find_first_unset(&other.bitmap_view) else trap("none")) == 51)

# find_one_anywhere(hint).value() for one value of the bit.
func test_find_anywhere(bitmap: const Bitmap*, set: bool, hint: usize) -> usize:
    if set:
        return bitmap_view_find_one_anywhere_set(&bitmap.bitmap_view, hint) else trap("none")
    return bitmap_view_find_one_anywhere_unset(&bitmap.bitmap_view, hint) else trap("none")

test "bitmap: find_one_anywhere_set and find_one_anywhere_unset":
    for set in [true, false]:
        var bitmap = test_bitmap(168, not set)
        bitmap_set(&bitmap, 34, set)
        bitmap_set(&bitmap, 97, set)
        assert(test_find_anywhere(&bitmap, set, 0) == 34)
        assert(test_find_anywhere(&bitmap, set, 31) == 34)
        assert(test_find_anywhere(&bitmap, set, 32) == 34)
        assert(test_find_anywhere(&bitmap, set, 34) == 34)
        assert(test_find_anywhere(&bitmap, set, 36) == 34)
        assert(test_find_anywhere(&bitmap, set, 63) == 34)
        assert(test_find_anywhere(&bitmap, set, 64) == 97)
        assert(test_find_anywhere(&bitmap, set, 96) == 97)
        assert(test_find_anywhere(&bitmap, set, 97) == 97)
        assert(test_find_anywhere(&bitmap, set, 127) == 97)
        assert(test_find_anywhere(&bitmap, set, 128) == 34)

        var second = test_bitmap(128 + 24, not set)
        bitmap_set(&second, 34, set)
        bitmap_set(&second, 126, set)
        assert(test_find_anywhere(&second, set, 0) == 34)
        assert(test_find_anywhere(&second, set, 63) == 34)
        assert(test_find_anywhere(&second, set, 64) == 126)

        var third = test_bitmap(32, not set)
        bitmap_set(&third, 12, set)
        bitmap_set(&third, 24, set)
        let got = test_find_anywhere(&third, set, 0)
        assert(got == 12 or got == 24)

test "bitmap: find_first_range":
    var bitmap = test_bitmap(128, true)
    for i in 47..<52usize:
        bitmap_set(&bitmap, i, false)
    var found_range_size: usize = 0
    let result = bitmap_view_find_longest_range_of_unset_bits(&bitmap.bitmap_view, 5, &found_range_size)
    assert(result != none)
    assert(found_range_size == 5)
    assert((result else 0) == 47)

test "bitmap: set_range":
    var bitmap = test_bitmap(128, false)
    bitmap_set_range(&bitmap, 41, 10, true)
    assert(not bitmap_view_get(&bitmap.bitmap_view, 40))
    for i in 41..<51usize:
        assert(bitmap_view_get(&bitmap.bitmap_view, i))
    assert(not bitmap_view_get(&bitmap.bitmap_view, 51))

    var big = test_bitmap(288, false)
    bitmap_set_range(&big, 48, 32, true)
    bitmap_set_range(&big, 94, 39, true)
    bitmap_set_range(&big, 190, 71, true)
    bitmap_set_range(&big, 190 + 71 - 7, 21, false)  # slightly overlapping clear
    for i in 0..<bitmap_view_size(&big.bitmap_view):
        let should_be_set = (i >= 48 and i < 48 + 32) or (i >= 94 and i < 94 + 39) or ((i >= 190 and i < 190 + 71) and not (i >= 190 + 71 - 7 and i < 190 + 71 - 7 + 21))
        assert(bitmap_view_get(&big.bitmap_view, i) == should_be_set)
    assert(bitmap_view_count_slow(&big.bitmap_view, true) == 32 + 39 + 71 - 7)

test "bitmap: find_first_fit":
    var full = test_bitmap(32, true)
    assert(bitmap_view_find_first_fit(&full.bitmap_view, 1) == none)
    bitmap_set(&full, 31, false)
    assert((bitmap_view_find_first_fit(&full.bitmap_view, 1) else trap("none")) == 31)

    for i in 0..<128usize:
        var bitmap = test_bitmap(128, true)
        bitmap_set(&bitmap, i, false)
        assert((bitmap_view_find_first_fit(&bitmap.bitmap_view, 1) else trap("none")) == i)
        test_bitmap_free(&bitmap)

    for i in 0..<127usize:
        var bitmap = test_bitmap(128, true)
        bitmap_set(&bitmap, i, false)
        bitmap_set(&bitmap, i + 1, false)
        assert((bitmap_view_find_first_fit(&bitmap.bitmap_view, 2) else trap("none")) == i)
        test_bitmap_free(&bitmap)

    let bitmap_size: usize = 1024
    for chunk_size in 1..<64usize:
        for i in 0..<bitmap_size - chunk_size:
            var bitmap = test_bitmap(bitmap_size, true)
            for c in 0..<chunk_size:
                bitmap_set(&bitmap, i + c, false)
            assert((bitmap_view_find_first_fit(&bitmap.bitmap_view, chunk_size) else trap("none")) == i)
            test_bitmap_free(&bitmap)

test "bitmap: find_longest_range_of_unset_bits_edge":
    var bitmap = test_bitmap(36, true)
    bitmap_set_range(&bitmap, 32, 4, false)
    var found_range_size: usize = 0
    let result = bitmap_view_find_longest_range_of_unset_bits(&bitmap.bitmap_view, 1, &found_range_size)
    assert((result else trap("none")) == 32)

# count_bits_slow of TestBitmap.cpp.
func test_count_bits_slow(b: const Bitmap*, start: usize, len: usize, value: bool) -> usize:
    var count: usize = 0
    for i in start..<start + len:
        if bitmap_view_get(&b.bitmap_view, i) == value:
            count += 1
    return count

test "bitmap: count_in_range":
    var bitmap = test_bitmap(256, false)
    bitmap_set(&bitmap, 14, true)
    bitmap_set(&bitmap, 17, true)
    bitmap_set(&bitmap, 19, true)
    bitmap_set(&bitmap, 20, true)
    for i in 34..<250usize:
        if i < 130 or i > 183:
            bitmap_set(&bitmap, i, true)
    for value in [true, false]:
        for (start, len) in [(16usize, 2usize), (16, 3), (16, 4)]:
            assert(bitmap_view_count_in_range(&bitmap.bitmap_view, start, len, value) == test_count_bits_slow(&bitmap, start, len, value))
        for start in 8..<24usize:
            for end in 9..<25usize:
                if start >= end:
                    continue
                assert(bitmap_view_count_in_range(&bitmap.bitmap_view, start, end - start, value) == test_count_bits_slow(&bitmap, start, end - start, value))
        for start in 1..=9usize:
            for i in start + 1..<bitmap_view_size(&bitmap.bitmap_view) - start + 1:
                assert(bitmap_view_count_in_range(&bitmap.bitmap_view, start, i - start, value) == test_count_bits_slow(&bitmap, start, i - start, value))

test "bitmap: byte_aligned_access":
    var a = test_bitmap(16, true)
    assert(bitmap_view_count_in_range(&a.bitmap_view, 0, 16, true) == 16)
    assert(bitmap_view_count_in_range(&a.bitmap_view, 8, 8, true) == 8)
    assert(bitmap_view_count_in_range(&a.bitmap_view, 0, 8, true) == 8)
    assert(bitmap_view_count_in_range(&a.bitmap_view, 4, 8, true) == 8)
    var b = test_bitmap(16, false)
    bitmap_set_range(&b, 4, 8, true)
    assert(bitmap_view_count_in_range(&b.bitmap_view, 0, 16, true) == 8)
    assert(bitmap_view_count_in_range(&b.bitmap_view, 8, 8, true) == 4)
    assert(bitmap_view_count_in_range(&b.bitmap_view, 0, 8, true) == 4)
    assert(bitmap_view_count_in_range(&b.bitmap_view, 4, 8, true) == 8)
    var c = test_bitmap(8, false)
    bitmap_set(&c, 2, true)
    bitmap_set(&c, 4, true)
    assert(bitmap_view_count_in_range(&c.bitmap_view, 0, 2, true) == 0)
    assert(bitmap_view_count_in_range(&c.bitmap_view, 0, 4, true) == 1)
    assert(bitmap_view_count_in_range(&c.bitmap_view, 0, 8, true) == 2)
    assert(bitmap_view_count_in_range(&c.bitmap_view, 4, 4, true) == 1)

test "bitmap: randomized set_get and set_range":
    for round in 0..<200:
        _ = round
        let init = (testing.random() & 1) == 1
        let new_value = (testing.random() & 1) == 1
        let size = (usize)(testing.random() % 64) + 1
        let i = (usize)(testing.random() % (u64)size)
        var bitmap = test_bitmap(size, init)
        bitmap_set(&bitmap, i, new_value)
        assert(bitmap_view_get(&bitmap.bitmap_view, i) == new_value)
        let start = (usize)(testing.random() % (u64)size)
        let len = (usize)(testing.random() % (u64)(size - start))
        bitmap_fill(&bitmap, init)
        bitmap_set_range(&bitmap, start, len, new_value)
        for j in 0..<size:
            let expected = new_value if (j >= start and j < start + len) else init
            assert(bitmap_view_get(&bitmap.bitmap_view, j) == expected)
        test_bitmap_free(&bitmap)

test "bitmap: grow, eq and verify-all-bits-flip":
    var bitmap = test_bitmap(10, true)
    bitmap_grow(&bitmap, 30, false)
    assert(bitmap_view_size(&bitmap.bitmap_view) == 30)
    assert(bitmap_view_count_slow(&bitmap.bitmap_view, true) == 10)
    assert(not bitmap_view_get(&bitmap.bitmap_view, 10))
    var other = test_bitmap(30, false)
    bitmap_set_range_and_verify_that_all_bits_flip(&other, 0, 10, true)
    assert(bitmap_view_eq(&bitmap.bitmap_view, other.bitmap_view))
    bitmap_set(&other, 29, true)
    assert(not bitmap_view_eq(&bitmap.bitmap_view, other.bitmap_view))
    var from_: usize = 0
    assert((bitmap_view_find_next_range_of_unset_bits(&bitmap.bitmap_view, &from_, 3) else trap("none")) == 3)
    assert(from_ == 10)
    # find_best_fit on a bitmap of whole words: the trailing-bits pass of
    # find_next_range_of_unset_bits restarts at the first trailing bit whatever `from` is,
    # so on a bitmap shorter than a word the donor's find_best_fit never terminates.
    var words = test_bitmap(128, true)
    bitmap_set_range(&words, 5, 4, false)
    bitmap_set_range(&words, 70, 2, false)
    bitmap_set_range(&words, 100, 3, false)
    assert((bitmap_view_find_best_fit(&words.bitmap_view, 2) else trap("none")) == 70)
    assert((bitmap_view_find_best_fit(&words.bitmap_view, 3) else trap("none")) == 100)
    assert(bitmap_view_find_best_fit(&words.bitmap_view, 5) == none)