Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.0

0.6.0 / src / ak / circular_buffer_2.lucb

#==============================================================================================
#
#   circular_buffer_2 - SearchableCircularBuffer: seekback search with a chunk-hash index
#
#   DESCRIPTION:
#       Port of AK/CircularBuffer.cpp (lines 278-587). SearchableCircularBuffer embeds its
#       CircularBuffer base (`circular_buffer`); the base's members are called on it. The
#       chunk hash is StringView::hash of the chunk's bytes, which is string_hash of them.
#
#==============================================================================================

# The length of an optional match (only read when it is present).
func searchable_match_length(match_: SearchableCircularBufferMatch?) -> usize:
    let found = match_ else return 0
    return found.length

# StringView { bytes }.hash(): string_hash of the bytes (0 for none).
func searchable_chunk_hash(bytes: const u8[]) -> u32:
    if bytes.length == 0:
        return 0
    return string_hash(bytes.data, bytes.length)

## Ported from AK/CircularBuffer.cpp:280 AK::SearchableCircularBuffer::SearchableCircularBuffer.
pub func searchable_circular_buffer_construct(this: SearchableCircularBuffer*, buffer: ByteBuffer):
    circular_buffer_construct(&this.circular_buffer, buffer)

## Ported from AK/CircularBuffer.cpp:285 AK::SearchableCircularBuffer::create_empty.
pub func searchable_circular_buffer_create_empty(size: usize) -> SearchableCircularBuffer!:
    let temporary_buffer = try byte_buffer_create_uninitialized(size)

    var circular_buffer: SearchableCircularBuffer
    searchable_circular_buffer_construct(&circular_buffer, temporary_buffer)

    return circular_buffer

## Ported from AK/CircularBuffer.cpp:294 AK::SearchableCircularBuffer::create_initialized.
pub func searchable_circular_buffer_create_initialized(buffer: ByteBuffer) -> SearchableCircularBuffer!:
    var circular_buffer: SearchableCircularBuffer
    searchable_circular_buffer_construct(&circular_buffer, buffer)

    circular_buffer.circular_buffer.m_used_space = byte_buffer_size(&circular_buffer.circular_buffer.m_buffer)

    var i: usize = 0
    while i + searchable_circular_buffer_hash_chunk_size <= byte_buffer_size(&circular_buffer.circular_buffer.m_buffer):
        let chunk = byte_buffer_span(&circular_buffer.circular_buffer.m_buffer)[i..<(i + searchable_circular_buffer_hash_chunk_size)]
        try searchable_circular_buffer_insert_location_hash(&circular_buffer, chunk, i)
        i += 1

    return circular_buffer

## Ported from AK/CircularBuffer.cpp:306 AK::SearchableCircularBuffer::read.
# These functions update the read pointer, so we need to hash any data that we have processed.
pub func searchable_circular_buffer_read(this: SearchableCircularBuffer*, bytes: u8[]) -> u8[]!:
    let read_bytes_span = circular_buffer_read(&this.circular_buffer, bytes)
    try searchable_circular_buffer_hash_last_bytes(this, read_bytes_span.length)
    return read_bytes_span

## Ported from AK/CircularBuffer.cpp:313 AK::SearchableCircularBuffer::discard.
pub func searchable_circular_buffer_discard(this: SearchableCircularBuffer*, discarded_bytes: usize) -> !:
    try circular_buffer_discard(&this.circular_buffer, discarded_bytes)
    try searchable_circular_buffer_hash_last_bytes(this, discarded_bytes)

## Ported from AK/CircularBuffer.cpp:320 AK::SearchableCircularBuffer::flush_to_stream.
pub func searchable_circular_buffer_flush_to_stream(this: SearchableCircularBuffer*, stream: Stream*) -> usize!:
    let flushed_byte_count = try circular_buffer_flush_to_stream(&this.circular_buffer, stream)
    try searchable_circular_buffer_hash_last_bytes(this, flushed_byte_count)
    return flushed_byte_count

## Ported from AK/CircularBuffer.cpp:327 AK::SearchableCircularBuffer::find_copy_in_seekback.
# This searches the seekback buffer (between read head and limit) for occurrences where it matches the next `length` bytes from the read buffer.
# Note that, since we only start searching at the read head, the length between read head and write head is excluded from the distance.
pub func searchable_circular_buffer_find_copy_in_seekback_usize(this: SearchableCircularBuffer*, maximum_length: usize, minimum_length: usize = 2) -> SearchableCircularBufferMatch?:
    assert(minimum_length > 0)
    let base = &this.circular_buffer

    # Clip the maximum length to the amount of data that we actually store.
    var max_length = maximum_length
    if max_length > base.m_used_space:
        max_length = base.m_used_space

    if max_length < minimum_length:
        return none

    var best_match: SearchableCircularBufferMatch?

    var needle_storage: u8[3]
    let needle = needle_storage[0..<min(searchable_circular_buffer_hash_chunk_size, max_length)]

    let needle_read_bytes = circular_buffer_read_with_seekback(base, needle, circular_buffer_used_space(base)) else trap("MUST: read_with_seekback")
    assert(needle_read_bytes.length == needle.length)

    # Try an efficient hash-based search first.
    if needle.length >= searchable_circular_buffer_hash_chunk_size:
        let needle_hash = searchable_chunk_hash(needle)

        let maybe_starting_offset = hash_map_get_k(&this.m_hash_location_map, needle_hash)

        if let starting_offset = maybe_starting_offset:
            var previous_buffer_offset: usize?
            var current_buffer_offset = *starting_offset

            while true:
                let current_search_offset = (circular_buffer_capacity(base) + base.m_reading_head - current_buffer_offset) % circular_buffer_capacity(base)

                # Validate the hash. In case it is invalid, we can discard the rest of the chain, as the data (and everything older) got updated.
                var hash_chunk_at_offset: u8[3]
                let hash_chunk_at_offset_span = circular_buffer_read_with_seekback(base, hash_chunk_at_offset, current_search_offset + circular_buffer_used_space(base)) else trap("MUST: read_with_seekback")
                assert(hash_chunk_at_offset_span.length == searchable_circular_buffer_hash_chunk_size)
                let found_chunk_hash = searchable_chunk_hash(hash_chunk_at_offset)
                if needle_hash != found_chunk_hash:
                    if let previous = previous_buffer_offset:
                        _ = hash_map_remove_k(&this.m_location_chain_map, previous)
                    else:
                        _ = hash_map_remove_k(&this.m_hash_location_map, needle_hash)
                    break

                # Validate the match through the set-distance-based implementation.
                let distances: usize[1] = [current_search_offset]
                let maybe_new_match = searchable_circular_buffer_find_copy_in_seekback_span_u64(this, distances, max_length, searchable_circular_buffer_hash_chunk_size)

                # If we found a match, record it.
                # If we haven't found a match, we simply got a hash collision, so skip.
                if let new_match = maybe_new_match:
                    let best_length = searchable_match_length(best_match)
                    if best_match == none or best_length < new_match.length:
                        best_match = new_match

                        # If we already found a result with the best possible length, then stop searching.
                        if new_match.length >= max_length:
                            break

                # Get the next location with the same hash from the location chain.
                let maybe_next_buffer_offset = hash_map_get_k(&this.m_location_chain_map, current_buffer_offset)

                # End of the chain, nothing more to check.
                let next_buffer_offset = maybe_next_buffer_offset else break

                previous_buffer_offset = current_buffer_offset
                current_buffer_offset = *next_buffer_offset

            # If we found a match, return it now.
            if best_match != none:
                return best_match

    # Try a plain memory search for smaller values.
    # Note: This overlaps with the hash search for chunks of size HASH_CHUNK_SIZE for the purpose of validation.
    if minimum_length <= searchable_circular_buffer_hash_chunk_size:
        var haystack_offset_from_start: usize = 0
        var haystack: Vector[const u8[]]
        let search_limit = searchable_circular_buffer_search_limit(this)
        vector_append_t(&haystack, searchable_circular_buffer_next_search_span(this, search_limit))
        if vector_at(&haystack, 0).length < search_limit:
            vector_append_t(&haystack, searchable_circular_buffer_next_search_span(this, search_limit - vector_at(&haystack, 0).length))

        # TODO: `memmem` searches the memory in "natural" order, which means that it finds matches with a greater distance first.
        #       Hash-based searching finds the shortest distances first, which is most likely better for encoding and memory efficiency.
        #       Look into creating a `memmem_reverse`, which starts searching from the end.
        var memmem_match = memmem_spans(vector_span(&haystack), needle)
        while let match_offset = memmem_match:
            let corrected_match_distance = search_limit - haystack_offset_from_start - match_offset

            # Validate the match through the set-distance-based implementation and extend it to the largest size possible.
            let distances: usize[1] = [corrected_match_distance]
            let maybe_new_match = searchable_circular_buffer_find_copy_in_seekback_span_u64(this, distances, min(max_length, searchable_circular_buffer_hash_chunk_size), minimum_length)

            # If we weren't able to validate the match at all, either our memmem search returned garbage or our validation function is incorrect. Investigate.
            let new_match = maybe_new_match else trap("VERIFY: memmem match did not validate")

            let best_length = searchable_match_length(best_match)
            if best_match == none or best_length < new_match.length:
                best_match = new_match

                # If we already found a result with the best possible length, then stop searching.
                if new_match.length >= max_length:
                    break

            var size_to_discard = match_offset + 1

            # Trim away the already processed bytes from the haystack.
            haystack_offset_from_start += size_to_discard
            while size_to_discard > 0:
                let first = vector_at(&haystack, 0)
                if first.length < size_to_discard:
                    size_to_discard -= first.length
                    vector_remove(&haystack, 0)
                else:
                    *first = (*first)[size_to_discard..]
                    break

            if vector_size(&haystack) == 0:
                break

            # Try and find the next match.
            memmem_match = memmem_spans(vector_span(&haystack), needle)

        # If we found a match of size HASH_CHUNK_SIZE, we should have already found that using the hash search. Investigate.
        if let best = best_match:
            assert(best.length < searchable_circular_buffer_hash_chunk_size)

    return best_match

## Ported from AK/CircularBuffer.cpp:469 AK::SearchableCircularBuffer::find_copy_in_seekback(distances).
# Supplying any hints will only consider those distances, in case existing offsets need to be validated.
pub func searchable_circular_buffer_find_copy_in_seekback_span_u64(this: const SearchableCircularBuffer*, distances: const usize[], maximum_length: usize, minimum_length: usize = 2) -> SearchableCircularBufferMatch?:
    assert(minimum_length > 0)
    let base = &this.circular_buffer

    # Clip the maximum length to the amount of data that we actually store.
    var max_length = maximum_length
    if max_length > base.m_used_space:
        max_length = base.m_used_space

    if max_length < minimum_length:
        return none

    var best_match: SearchableCircularBufferMatch?

    for distance in distances:
        # Discard distances outside the valid range.
        if distance > searchable_circular_buffer_search_limit(this) or distance <= 0:
            continue

        # TODO: This does not yet support looping repetitions.
        if distance < minimum_length:
            continue

        var current_match_length: usize = 0

        while current_match_length < max_length:
            let haystack_span = searchable_circular_buffer_next_search_span(this, distance - current_match_length)
            let haystack = haystack_span[0..<min(haystack_span.length, max_length - current_match_length)]
            let needle_span = circular_buffer_next_read_span(base, current_match_length)
            let needle = needle_span[0..<min(needle_span.length, max_length - current_match_length)]

            let submatch_length = bytes_matching_prefix_length(haystack, needle)

            if submatch_length == 0:
                break

            current_match_length += submatch_length

        # Discard matches that don't reach the minimum length.
        if current_match_length < minimum_length:
            continue

        let best_length = searchable_match_length(best_match)
        if best_match == none or best_length < current_match_length:
            best_match = SearchableCircularBufferMatch(distance = distance, length = current_match_length)

    return best_match

## Ported from AK/CircularBuffer.cpp:516 AK::SearchableCircularBuffer::insert_location_hash.
pub func searchable_circular_buffer_insert_location_hash(this: SearchableCircularBuffer*, value: const u8[], raw_offset: usize) -> !:
    assert(value.length == searchable_circular_buffer_hash_chunk_size)

    let value_hash = searchable_chunk_hash(value)

    # Discard any old entries for this offset first. This should eliminate accidental loops by breaking the chain.
    # The actual cleanup is done on access, since we can only remove invalid references when actually walking the chain.
    _ = hash_map_remove_k(&this.m_location_chain_map, raw_offset)

    # Check if we have any existing entries for this hash.
    # If so, we need to add it to the location chain map instead, as we will soon replace the entry in the hash location map.
    let existing_entry = hash_map_get_k(&this.m_hash_location_map, value_hash)

    if let existing = existing_entry:
        _ = try hash_map_try_set(&this.m_location_chain_map, raw_offset, *existing)

    _ = try hash_map_try_set(&this.m_hash_location_map, value_hash, raw_offset)

## Ported from AK/CircularBuffer.cpp:538 AK::SearchableCircularBuffer::hash_last_bytes.
pub func searchable_circular_buffer_hash_last_bytes(this: SearchableCircularBuffer*, count: usize) -> !:
    # Stop early if we don't have enough data overall to hash a full chunk.
    if searchable_circular_buffer_search_limit(this) < searchable_circular_buffer_hash_chunk_size:
        return

    let buffer_data = byte_buffer_data(&this.circular_buffer.m_buffer) else trap("VERIFY: no buffer")
    var remaining_recalculations = count
    while remaining_recalculations > 0:
        # Note: We offset everything by HASH_CHUNK_SIZE because we have up to HASH_CHUNK_SIZE - 1 bytes that we couldn't hash before (as we had missing data).
        #       The number of recalculations stays the same, since we now have up to HASH_CHUNK_SIZE - 1 bytes that we can't hash now.
        var recalculation_span = searchable_circular_buffer_next_search_span(this, min(remaining_recalculations + searchable_circular_buffer_hash_chunk_size - 1, searchable_circular_buffer_search_limit(this)))

        # If the span is smaller than a hash chunk, we need to manually craft some consecutive data to do the hashing.
        if recalculation_span.length < searchable_circular_buffer_hash_chunk_size:
            let auxiliary_span = circular_buffer_next_seekback_span(&this.circular_buffer, remaining_recalculations)

            # Ensure that our math is correct and that both spans are "adjacent".
            assert(recalculation_span.data + recalculation_span.length == buffer_data + byte_buffer_size(&this.circular_buffer.m_buffer))
            assert(auxiliary_span.data == buffer_data)

            while recalculation_span.length > 0 and recalculation_span.length + auxiliary_span.length >= searchable_circular_buffer_hash_chunk_size:
                var temporary_hash_chunk: u8[3]

                let copied_from_recalculation_span = bytes_copy_trimmed_to(recalculation_span, temporary_hash_chunk)
                assert(copied_from_recalculation_span == recalculation_span.length)

                let copied_from_auxiliary_span = bytes_copy_trimmed_to(auxiliary_span, temporary_hash_chunk[copied_from_recalculation_span..])
                assert(copied_from_recalculation_span + copied_from_auxiliary_span == searchable_circular_buffer_hash_chunk_size)

                try searchable_circular_buffer_insert_location_hash(this, temporary_hash_chunk, (usize)(recalculation_span.data - buffer_data))

                recalculation_span = recalculation_span[1..]
                remaining_recalculations -= 1

            continue

        var i: usize = 0
        while i + searchable_circular_buffer_hash_chunk_size <= recalculation_span.length:
            let value = recalculation_span[i..<(i + searchable_circular_buffer_hash_chunk_size)]
            let raw_offset = (usize)(value.data - buffer_data)
            try searchable_circular_buffer_insert_location_hash(this, value, raw_offset)
            remaining_recalculations -= 1
            i += 1