You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This is a followup issue to #5. Issue #5 demonstrates an array compilation technique for strings. Namely we can encode a string into a field element, by simply concatenating the binary representation padded to the nearest byte. The code for this is quite simple and can be seen below
(defconstant+byte-size+8)
(-> string-to-number (string) integer)
(defunstring-to-number (string)
"converts a string to a numerical encoding"
(let ((cont 0))
(sum (map'list
(lambda (c)
(prog1
(ash (char-code c) (* cont +byte-size+))
(incf cont (char-byte-size c))))
string))))
(-> char-byte-size (character) fixnum)
(defunchar-byte-size (char)
"Calculates how many bytes is needed to model the current char"
(ceiling (integer-length (char-codechar))
+byte-size+))
We can thus view strings as a subset of a proper array compilation technique
Encoding Technique
The string code shows a good strategy for encoding utf8 style strings, for arrays we can actually simplify the technique quite a bit as instead of working on values with variable size dimensons (我 has a size of 15 bits, thus 2 bytes to encode. 🤕 takes 3 bytes to encode proper.), we can work on a fixed sized type to properly encode.
Thus if we have an array of size arr we can enocde it as the following
(defunsequence-to-number (size arr)
"converts an array to a numerical encoding"
(sum (map'list
(lambda (ele count) (ash ele (*count size)))
arr
(alexandria:iota (length arr)))))
Since the field element may overflow, we require arrays to be of a fixed size, as if we overflow, we have to split it into multiple field elements.
An amusing fact is that we can grow the array in O(1) given no overflow by simply noting the size and adding by the appropriate value.
(For I8's we can only fit 30 field elements before overflow as (ash 2 (* 8 31)) = 250 bits. Thus we can't even use the full size of the array due to byte alignment).
Indexing technique
So far we've only dealt with constructing an array, but how do we index into it? We can do this with a carry bit along with a condition that returns 1 when we hit the condition we want
preamble
This is a followup issue to #5. Issue #5 demonstrates an array compilation technique for strings. Namely we can encode a string into a field element, by simply concatenating the binary representation padded to the nearest byte. The code for this is quite simple and can be seen below
We can thus view strings as a subset of a proper array compilation technique
Encoding Technique
The string code shows a good strategy for encoding
utf8
style strings, for arrays we can actually simplify the technique quite a bit as instead of working on values with variable size dimensons (我 has a size of 15 bits, thus 2 bytes to encode. 🤕 takes 3 bytes to encode proper.), we can work on a fixed sized type to properly encode.Thus if we have an array of size
arr
we can enocde it as the followingSince the field element may overflow, we require arrays to be of a fixed size, as if we overflow, we have to split it into multiple field elements.
An amusing fact is that we can grow the array in O(1) given no overflow by simply noting the size and adding by the appropriate value.
(For I8's we can only fit 30 field elements before overflow as
(ash 2 (* 8 31)) = 250 bits
. Thus we can't even use the full size of the array due to byte alignment).Indexing technique
So far we've only dealt with constructing an array, but how do we index into it? We can do this with a carry bit along with a condition that returns 1 when we hit the condition we want
[TODO write more about the condition value and how we can compute it]
The text was updated successfully, but these errors were encountered: