Applied Pokology

Back to blog... _____ ---' __\_______ ______)

Interesting poke idiom: sparse tables

__) __) ---._______) Jose E. Marchesi January 28, 2023 During tonight poke online office hours our friend hdzki came with an interesting use case. He is poking at some binary structures that are like sparse tables whose entries are distributed in the file in an arbitrary way. Each sparse table is characterized by an array of consecutive non-NULL pointers. Each pointer points to an entry in the table. The table entries can be anywhere in the IO space, and are not necessarily consecutive, nor be in order. Example of such a table with three entries: ,---- | IO space | | | | | +-->| item2 | | | | | | | : ... : | | | | | | +----------------+ <------- table | | | ptr1 |------+ | +---| ptr2 | | | | ptr3 |---+ | | +----------------+ | | | | | | | | | | | | | : ... : | | | | | | | | | item3 |<- + | | | | | | : ... : | | | | | | | item1 |<-----+ | | | | : ... : `---- How to poke at this? First, we define the things themselves. This can be any structure, but this will serve for this example: ,---- | type Thing = | struct | { | byte control; | string data; | }; `---- Then, the pointers, which are 32-bit long, in bytes, and not NULL: ,---- | type Pointer = | struct | { | offset<uint<32>,B> ptr : ptr != 0#B; | }; `---- Then the sparse table itself: ,---- | type Sparse_Table = | struct | { | Pointer[] ptrs; | computed Thing[] items; | | method get_items = Thing[]: | { | var items = Thing[](); | | for (p in ptrs) | apush (items, Thing @ p.ptr); | return items; | } | | method _print = void: | { | printf "#<%v>", items; | } | }; `---- Interesting things to note: - The array of pointers will cover every consecutive 32-bit pointer until the first NULL pointer, exclusive. This is achieved by having the constraint in the Pointer struct. Remember that unbounded array types are mapped until either EOF is encountered or a constraint fails. - The computed field items constructs a _non-mapped_ array that contains mapped Things at the right place. This is an interesting example where poke's ability to mix mapped and non-mapped values transparently really pays back. - The pretty-printer helps to visualize the items stored in the sparse table. However, we follow the poke convention of enclosing pretty-printed values between #<...> so the casual user of the definitions above won't be induced to thing that a sparse table is an array: it is not. Let's see this in action. First, we open an all-zeroed memory IO space as our play ground: ,---- | (poke) .mem foo `---- Then, lets plant a few Things around at some memorable offsets and the table of consecutive pointers at offset 0: ,---- | (poke) Thing @ 100#B = Thing { control = 1UB, data = "one" } | (poke) Thing @ 200#B = Thing { control = 2UB, data = "two" } | (poke) Thing @ 300#B = Thing { control = 3UB, data = "three" } | (poke) Pointer[] @ 0#B = [Pointer { ptr = 100#B }, Pointer { ptr = 200#B }, Pointer { ptr = 300#B }] `---- And finally let's map our sparse table: ,---- | (poke) var table = Sparse_Table @ 0#B | (poke) table | #<[Thing {control=1UB,data="one"},Thing {control=2UB,data="two"},Thing {control=3UB,data="three"}]> `---- At this point, we can access the items comfortably by using the computed field. Since the array elements are mapped, they will always show actual contents, and modifying them modifies the underlying bytes in the IO space: ,---- | (poke) table.items[1].data = "quux" | (poke) Thing @ 200#B | Thing { | control=2UB, | data="quux" | } `---- Disabling the pretty-printer we see the crude reality of what a Sparse_Table structure really is, a sequence of pointers: ,---- | (poke) .set pretty-print no | (poke) table | Sparse_Table { | ptrs=[Pointer { | ptr=100U#B | },Pointer { | ptr=200U#B | },Pointer { | ptr=300U#B | }] `---- Happy poking!