Rylik

Counting Classified Pairs

This (and probably the next too) will be a shorter post, as most of the work was already done in the first post. Quick recap from the first post since it is quite large:

  1. Before doing any SIMD, a classification of what is tokenised was needed. The classification (in short) was done like this:
    • an array for the classes of a low nibble of an ASCII character
    • an array for the classes of a high nibble of an ASCII character
    • the low nibble and high nibble are used as indices into those arrays in order to get the class flags
    • the class flags are unique and combined.
enum CLASSES {
        CLASS_NONE          = 0u,
        CLASS_SPACE         = 1u << 0u,
        CLASS_UNDERSCORE    = 1u << 1u,
        CLASS_CONTROL_SPACE = 1u << 2u,
        CLASS_DIGIT         = 1u << 3u,
        CLASS_LETTER_A_TO_O = 1u << 4u,
        CLASS_LETTER_P_TO_Z = 1u << 5u,
        CLASS_QUOTE         = 1u << 6u,
        CLASS_LETTER_A_TO_Z = CLASS_LETTER_A_TO_O | CLASS_LETTER_P_TO_Z,
        CLASS_WHITESPACE    = CLASS_SPACE | CLASS_CONTROL_SPACE,
        CLASS_WORD          = CLASS_DIGIT | CLASS_LETTER_A_TO_O | CLASS_LETTER_P_TO_Z | CLASS_UNDERSCORE
};

Now, for the code in assembly for this post together with the code for one ASCII character from the previous post as comparison:

bits 64
default rel

extern table_low_class
extern table_high_class

section .rodata
align 32
nibble_mask:     times 32 db 0x0F

section .text
global extract_mask_32

%define vec_source ymm0
%define vec_nibble_mask ymm1
%define vec_table_low_class ymm2
%define vec_table_high_class ymm3
%define vec_class ymm4

%macro order_indices 3
        vpshufb %1, %2, %3   ; dest = table[indices]
%endmacro

%macro select_32 3
        vpcmpeqb %1, %2, %3
%endmacro

%define SIMD_WIDTH 32

%macro ALIGN_UP 1
        add %1, SIMD_WIDTH - 1
        and %1, -SIMD_WIDTH
%endmacro

;extern void extract_mask_32(char *buff, u8 class_bits[32], u64 bytes_read, u32 *output);
extract_mask_32:
        ALIGN_UP rdx
        xor r10, r10

.loop:
        vmovdqu vec_source, [rdi + r10]
        vmovdqu vec_nibble_mask, [nibble_mask]
        vmovdqu vec_table_low_class, [table_low_class]
        vmovdqu vec_table_high_class, [table_high_class]

        vpand ymm5, vec_source, vec_nibble_mask
        vpsrlw ymm6, vec_source, 4
        vpand ymm7, ymm6, vec_nibble_mask

        order_indices ymm5, vec_table_low_class,  ymm5
        order_indices ymm7, vec_table_high_class, ymm7
        vpand vec_class, ymm5, ymm7

        vpxor ymm8, ymm8, ymm8

        vpand ymm9, vec_class, [rsi]
        select_32 ymm9, ymm9, ymm8
        vpmovmskb eax, ymm9
        not eax
        mov [rcx], eax
        add rcx, 4
        add r10, SIMD_WIDTH
        cmp r10, rdx
        jb .loop

.loop_exit:
        vzeroupper
        ret

section .note.GNU-stack noalloc noexec nowrite progbits
char character = 'm';
u8 low = character & 0xF;
u8 high = (character >> 4u) & 0xF;
u8 class_low = table_low_class[low];            /*CLASS_CONTROL_SPACE | CLASS_LETTER_A_TO_O*/
u8 class_high = table_high_class[high]          /*CLASS_LETTER_A_TO_O*/;
u8 class_word = class_low & class_high;         /*CLASS_LETTER_A_TO_O*/
u8 word_flags = class_word & CLASS_WORD;        /* CLASS_LETTER_A_TO_O*/
u8 not_word = (word_flags == 0) ? 0xFF : 0x00;  /* if flags is 0 set to 8bits of all 1s, otherwise 0*/
u8 is_word = (not_word >> 7) ^ 1;               /* shifts the top bit to the right, at position 0, and then xors. if it is 0 it turns it to 1 and if it is 1 it switches it to 0*/

This isn't a crash course on assembly and I hope you can read assembly, but if not, here's a quick breakdown:

  1. On Linux (which uses the System V ABI which you can read on here) the function parameters go into these registers: rdi, rsi, rdx, rcx, r8 and r9. In the comment above the assembly function, you can see the function signature on the C side.
    • rdi = buff (the source file that we open from file.stc)
    • rsi = class_bits (the flags that we use to discriminate a class out)
    • rdx = the file size (of file.stc)
    • rcx = in this buffer, we store a u32, which contains 1s in the positions matched in buff (more about this in the C code)
  2. We use the r10 register to increment the pointer. This is equivalent to doing:
u8 *buff = &file_data;
u64 r10_register = 0;
const u64 rdx_as_file_size = bytes_read;
const u64 SIMD_WIDTH = 32;
while (r10_register < rdx_as_file_size) {
    u8 *window = buff + r10_register;
    r10_register += SIMD_WIDTH;
}

This fills the [output] parameter, 4 bytes at a time, with the current simd "window".

mov [rcx], eax
add rcx, 4
add r10, SIMD_WIDTH
cmp r10, rdx

We take 32 characters at a time and increment by r10 (it starts at 0, so the first addition adds nothing), which increments by 32 (we have a different 32 byte window at the start of the loop):

vmovdqu vec_source, [rdi + r10]

The nibble mask defined here:

nibble_mask:     times 32 db 0x0F

Gives us this:

u8 nibble_mask[32] = {0};
/*all 32 entries are 0x0F or 0b00001111 in binary*/
memset(nibble_mask, 0x0F, sizeof(nibble_mask));

Then we load them into simd registers (AVX2). The tables are the ones from the previous post, existing in C (the C code comes later)

vmovdqu vec_nibble_mask, [nibble_mask]
vmovdqu vec_table_low_class, [table_low_class]
vmovdqu vec_table_high_class, [table_high_class]

This here is going to match for all 32 bytes their low nibble, logical shift right by 4 and then do the same for the high nibble:

vpand ymm5, vec_source, vec_nibble_mask
vpsrlw ymm6, vec_source, 4
vpand ymm7, ymm6, vec_nibble_mask

Is the equivalent of this:

u8 low = character & 0xF;
u8 high = (character >> 4u) & 0xF;
bytes 0, 1          'm' = 6D       'o' = 6F
one 16-bit word     0x6F6D = 01101111 01101101
vpsrlw 4            0x06F6 = 00000110 11110110
bytes 0, 1 after    F6              06
& 0x0F              06              06

For a character that would have bytes such as 'm' = 01101101:

  1. low part is 1101 AND'ed with our mask of 1111 gives exactly 1101 back (D in hex so 13).
  2. high part is 0110 AND'ed with our mask of 1111 gives exactly 0110 back (6 in hex so 6).
  3. we use the result for low in the low table and that gives us: low_table[13]
  4. we use the result for high in the high table and that gives us: high_table[6]

From our tables:

high_table...
[0x06] = CLASS_LETTER_A_TO_O /*[0x[6]1..0x[6]F 'a'..'o']*/,

low_table...
[0x0D] = CLASS_CONTROL_SPACE /*[0x0[D] CARRIAGE RETURN]*/
       | CLASS_LETTER_A_TO_O /*[0x4[D] 'M', 0x6[D] 'm']*/,

The next one might look confusing:

%macro order_indices 3
        vpshufb %1, %2, %3   ; dest = table[indices]
%endmacro

        order_indices ymm5, vec_table_low_class,  ymm5
        order_indices ymm7, vec_table_high_class, ymm7
        vpand vec_class, ymm5, ymm7

It really is just this:

u8 class_low = table_low_class[low];            /*CLASS_CONTROL_SPACE | CLASS_LETTER_A_TO_O*/
u8 class_high = table_high_class[high]          /*CLASS_LETTER_A_TO_O*/;
u8 class_word = class_low & class_high;         /*CLASS_LETTER_A_TO_O*/

What this did was to index all 32 bytes at the same time and then AND the two results. For our "m" example, it would be: (pseudocode)

high_nibble = [0x06] = CLASS_LETTER_A_TO_O /*[0x[6]1..0x[6]F 'a'..'o']*/,

low_nibble = [0x0D] = CLASS_CONTROL_SPACE /*[0x0[D] CARRIAGE RETURN]*/
                    | CLASS_LETTER_A_TO_O /*[0x4[D] 'M', 0x6[D] 'm']*/,
final_class = high_nibble & low_nibble;
/*the only flag matching is CLASS_LETTER_A_TO_O, which the character 'm' is, so the final mask is that class*/

For the 32 characters, this will eliminate any flag that doesn't match both high and low and will give us only the ones that match both. This is why in the previous post I mentioned that it really depends what you're working with. You make the rules for what goes together with what and you must study the input to see how to optimise that classification.

Finally, we clear a simd register to make sure it's all 0s, then we AND the class_bits with this resulting "final_class" (which we give as 2nd parameter, so it went in rsi):

%macro select_32 3
        vpcmpeqb %1, %2, %3
%endmacro

        vpxor ymm8, ymm8, ymm8

        vpand ymm9, vec_class, [rsi]
        select_32 ymm9, ymm9, ymm8
        vpmovmskb eax, ymm9
        not eax

Then, we compare and store it. What we compare (equal): ymm8 (which is all 0s) with ymm9 (which has our final_class masks across all 32). The resulting ymm9, across the 32 values, will have 1s (0xFF) where ymm9 was 0 before the comparison. Since ymm8 was all 0s, that means anything that did not match gets a 1 and everything else is 0. Finally, we store those 32 values into a single u32, in eax, which gets 1s and 0s in the positions that ymm9 had 1s and 0s. The not eax after that flips every bit, so the characters that matched are the 1s and everything else is 0. To use a small example, say the register is only 4 characters: (pseudocode):

register = [1, 0, 0, 1];
eax before: 0b0000
vpmovmskb eax, register;
eax after: 0b1001
byte          m  o  d  u  l  e  (  "  m  a  i  n  "  )  ; \n
low nibble    D  F  4  5  C  5  8  2  D  1  9  E  2  9  B  A
high nibble   6  6  6  7  6  6  2  2  6  6  6  6  2  2  3  0
vec_class    10 10 10 20 10 10 00 80 10 10 10 10 80 00 00 04
vpand [rsi]  10 10 10 20 10 10 00 00 10 10 10 10 00 00 00 00
vpcmpeqb     00 00 00 00 00 00 FF FF 00 00 00 00 FF FF FF FF
vpmovmskb     0  0  0  0  0  0  1  1  0  0  0  0  1  1  1  1
not eax       1  1  1  1  1  1  0  0  1  1  1  1  0  0  0  0

Now, for the C code:

#include <unistd.h>
#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef uint8_t         u8;
typedef uint16_t        u16;
typedef uint32_t        u32;
typedef uint64_t        u64;
typedef int8_t          i8;
typedef int16_t         i16;
typedef int32_t         i32;
typedef int64_t         i64;
typedef float           f32;

/* *
 * CLASS_QUOTE = ["]
 * */

enum CLASSES {
        CLASS_NONE          = 0u,
        CLASS_SPACE         = 1u << 0u,
        CLASS_UNDERSCORE    = 1u << 1u,
        CLASS_CONTROL_SPACE = 1u << 2u,
        CLASS_DIGIT         = 1u << 3u,
        CLASS_LETTER_A_TO_O = 1u << 4u,
        CLASS_LETTER_P_TO_Z = 1u << 5u,
        CLASS_QUOTE         = 1u << 6u,
        CLASS_LETTER_A_TO_Z = CLASS_LETTER_A_TO_O | CLASS_LETTER_P_TO_Z,
        CLASS_WHITESPACE    = CLASS_SPACE | CLASS_CONTROL_SPACE,
        CLASS_WORD          = CLASS_DIGIT | CLASS_LETTER_A_TO_O | CLASS_LETTER_P_TO_Z | CLASS_UNDERSCORE
};

/* *
 * this table cannot follow the same indexing visual logic as the low_nibbles table of 0xHL where low_nibbles[L] is the index.
 * because high_nibbles[H] from a 0xHL would be incorrect
 * therefore, the high part of the ASCII is the low part of the index:
 * Index (low part in bracket []) = 0x0[2] PAIRS 0x[2]2, 0x[2]3, 0x[2]7 and so on (high part in bracket [])
 * */
const u8 table_high_class[32] = {
        [0x00] = CLASS_CONTROL_SPACE /*[0x[0]8 BACKSPACE, 0x[0]9 TAB SPACE, 0x[0]A LINE FEED, 0x[0]B VERTICAL TAB, 0x[0]C FORM FEED, 0x[0]D CARRIAGE RETURN]*/,
        [0x01] = CLASS_NONE,
        [0x02] = CLASS_SPACE         /*[0x[2]0 SPACE]*/
               | CLASS_QUOTE         /*[0x[2]2 '"']*/,
        [0x03] = CLASS_DIGIT         /*[0x[3]0..0x[3]9 '0'..'9']*/,
        [0x04] = CLASS_LETTER_A_TO_O /*[0x[4]1..0x[4]F 'A'..'O']*/,
        [0x05] = CLASS_LETTER_P_TO_Z /*[0x[5]0..0x[5]A 'P'..'Z']*/
               | CLASS_UNDERSCORE    /*[0x[5]F '_']*/,
        [0x06] = CLASS_LETTER_A_TO_O /*[0x[6]1..0x[6]F 'a'..'o']*/,
        [0x07] = CLASS_LETTER_P_TO_Z /*[0x[7]0..0x[7]A 'p'..'z']*/,
        [0x08] = CLASS_NONE,
        [0x09] = CLASS_NONE,
        [0x0A] = CLASS_NONE,
        [0x0B] = CLASS_NONE,
        [0x0C] = CLASS_NONE,
        [0x0D] = CLASS_NONE,
        [0x0E] = CLASS_NONE,
        [0x0F] = CLASS_NONE,

        [0x10] = CLASS_CONTROL_SPACE /*[0x[0]8 BACKSPACE, 0x[0]9 TAB SPACE, 0x[0]A LINE FEED, 0x[0]B VERTICAL TAB, 0x[0]C FORM FEED, 0x[0]D CARRIAGE RETURN]*/,
        [0x11] = CLASS_NONE,
        [0x12] = CLASS_SPACE         /*[0x[2]0 SPACE]*/
               | CLASS_QUOTE         /*[0x[2]2 '"']*/,
        [0x13] = CLASS_DIGIT         /*[0x[3]0..0x[3]9 '0'..'9']*/,
        [0x14] = CLASS_LETTER_A_TO_O /*[0x[4]1..0x[4]F 'A'..'O']*/,
        [0x15] = CLASS_LETTER_P_TO_Z /*[0x[5]0..0x[5]A 'P'..'Z']*/
               | CLASS_UNDERSCORE    /*[0x[5]F '_']*/,
        [0x16] = CLASS_LETTER_A_TO_O /*[0x[6]1..0x[6]F 'a'..'o']*/,
        [0x17] = CLASS_LETTER_P_TO_Z /*[0x[7]0..0x[7]A 'p'..'z']*/,
        [0x18] = CLASS_NONE,
        [0x19] = CLASS_NONE,
        [0x1A] = CLASS_NONE,
        [0x1B] = CLASS_NONE,
        [0x1C] = CLASS_NONE,
        [0x1D] = CLASS_NONE,
        [0x1E] = CLASS_NONE,
        [0x1F] = CLASS_NONE,
};

/*this represents the matching low nibble of an ASCII byte indexed in this table*/
/*
 * if an ASCII character is of the form 0xN0, that low nibble (0 zero) means it should be at index 0 in this table
 * same for any other one. The general form is 0xHL (high/low) where low_nibbles[L] = the combined flags
 * for L = 0 the low_nibbles[L] = CLASS_SPACE | CLASS_DIGIT | CLASS_LETTER_P_TO_Z
 * that is because: 0x2[0] = Space, 0x3[0] = '0', 0x5[0] = 'P' and 0x7[0] = 'p'. All have a low nibble of 0 (zero).
 * The other characters that have 0 (zero) at their nibbles (such as 0x10 ) are elided, because they're not characters you would encounter in a text editor.
 */
const u8 table_low_class[32] = {
        [0x00] = CLASS_SPACE         /*[0x2[0] SPACE]*/
               | CLASS_DIGIT         /*[0x3[0] '0']*/
               | CLASS_LETTER_P_TO_Z /*[0x5[0] 'P', 0x7[0] 'p']*/,
        [0x01] = CLASS_DIGIT         /*[0x3[1] '1']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[1] 'A', 0x6[1] 'a', 0x5[1] 'Q', 0x7[1] 'q']*/,
        [0x02] = CLASS_DIGIT         /*[0x3[2] '2']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[2] 'B', 0x6[2] 'b', 0x5[2] 'R', 0x7[2] 'r']*/
               | CLASS_QUOTE         /*[0x2[2] '"']*/,
        [0x03] = CLASS_DIGIT         /*[0x3[3] '3']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[3] 'C', 0x6[3] 'c', 0x5[3] 'S', 0x7[3] 's']*/,
        [0x04] = CLASS_DIGIT         /*[0x3[4] '4']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[4] 'D', 0x6[4] 'd', 0x5[4] 'T', 0x7[4] 't']*/,
        [0x05] = CLASS_DIGIT         /*[0x3[5] '5']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[5] 'E', 0x6[5] 'e', 0x5[5] 'U', 0x7[5] 'u']*/,
        [0x06] = CLASS_DIGIT         /*[0x3[6] '6']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[6] 'F', 0x6[6] 'f', 0x5[6] 'V', 0x7[6] 'v']*/,
        [0x07] = CLASS_DIGIT         /*[0x3[7] '7']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[7] 'G', 0x6[7] 'g', 0x5[7] 'W', 0x7[7] 'w']*/,
        [0x08] = CLASS_CONTROL_SPACE /*[0x0[8] BACKSPACE]*/
               | CLASS_DIGIT         /*[0x3[8] '8']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[8] 'H', 0x6[8] 'h', 0x5[8] 'X', 0x7[8] 'x']*/,
        [0x09] = CLASS_CONTROL_SPACE /*[0x0[9] TAB SPACE]*/
               | CLASS_DIGIT         /*[0x3[9] '9']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[9] 'I', 0x6[9] 'i', 0x5[9] 'Y', 0x7[9] 'y']*/,
        [0x0A] = CLASS_CONTROL_SPACE /*[0x0[A] LINE FEED]*/
               | CLASS_LETTER_A_TO_Z /*[0x4[A] 'J', 0x6[A] 'j', 0x5[A] 'Z', 0x7[A] 'z']*/,
        [0x0B] = CLASS_CONTROL_SPACE /*[0x0[B] VERTICAL TAB]*/
               | CLASS_LETTER_A_TO_O /*[0x4[B] 'K', 0x6[B] 'k']*/,
        [0x0C] = CLASS_CONTROL_SPACE /*0x0[C] FORM FEED / NEW PAGE*/
               | CLASS_LETTER_A_TO_O /*[0x4[C] 'L', 0x6[C] 'l']*/,
        [0x0D] = CLASS_CONTROL_SPACE /*[0x0[D] CARRIAGE RETURN]*/
               | CLASS_LETTER_A_TO_O /*[0x4[D] 'M', 0x6[D] 'm']*/,
        [0x0E] = CLASS_LETTER_A_TO_O /*[0x4[E] 'N', 0x6[E] 'n']*/,
        [0x0F] = CLASS_LETTER_A_TO_O /*[0x4[F] 'O', 0x6[F] 'o']*/
               | CLASS_UNDERSCORE    /*[0x5[F] '_']*/,

        [0x10] = CLASS_SPACE         /*[0x2[0] SPACE]*/
               | CLASS_DIGIT         /*[0x3[0] '0']*/
               | CLASS_LETTER_P_TO_Z /*[0x5[0] 'P', 0x7[0] 'p']*/,
        [0x11] = CLASS_DIGIT         /*[0x3[1] '1']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[1] 'A', 0x6[1] 'a', 0x5[1] 'Q', 0x7[1] 'q']*/,
        [0x12] = CLASS_DIGIT         /*[0x3[2] '2']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[2] 'B', 0x6[2] 'b', 0x5[2] 'R', 0x7[2] 'r']*/
               | CLASS_QUOTE         /*[0x2[2] '"']*/,
        [0x13] = CLASS_DIGIT         /*[0x3[3] '3']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[3] 'C', 0x6[3] 'c', 0x5[3] 'S', 0x7[3] 's']*/,
        [0x14] = CLASS_DIGIT         /*[0x3[4] '4']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[4] 'D', 0x6[4] 'd', 0x5[4] 'T', 0x7[4] 't']*/,
        [0x15] = CLASS_DIGIT         /*[0x3[5] '5']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[5] 'E', 0x6[5] 'e', 0x5[5] 'U', 0x7[5] 'u']*/,
        [0x16] = CLASS_DIGIT         /*[0x3[6] '6']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[6] 'F', 0x6[6] 'f', 0x5[6] 'V', 0x7[6] 'v']*/,
        [0x17] = CLASS_DIGIT         /*[0x3[7] '7']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[7] 'G', 0x6[7] 'g', 0x5[7] 'W', 0x7[7] 'w']*/,
        [0x18] = CLASS_CONTROL_SPACE /*[0x0[8] BACKSPACE]*/
               | CLASS_DIGIT         /*[0x3[8] '8']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[8] 'H', 0x6[8] 'h', 0x5[8] 'X', 0x7[8] 'x']*/,
        [0x19] = CLASS_CONTROL_SPACE /*[0x0[9] TAB SPACE]*/
               | CLASS_DIGIT         /*[0x3[9] '9']*/
               | CLASS_LETTER_A_TO_Z /*[0x4[9] 'I', 0x6[9] 'i', 0x5[9] 'Y', 0x7[9] 'y']*/,
        [0x1A] = CLASS_CONTROL_SPACE /*[0x0[A] LINE FEED]*/
               | CLASS_LETTER_A_TO_Z /*[0x4[A] 'J', 0x6[A] 'j', 0x5[A] 'Z', 0x7[A] 'z']*/,
        [0x1B] = CLASS_CONTROL_SPACE /*[0x0[B] VERTICAL TAB]*/
               | CLASS_LETTER_A_TO_O /*[0x4[B] 'K', 0x6[B] 'k']*/,
        [0x1C] = CLASS_LETTER_A_TO_O /*[0x4[C] 'L', 0x6[C] 'l']*/
               | CLASS_CONTROL_SPACE /*0x0[C] FORM FEED / NEW PAGE*/,
        [0x1D] = CLASS_CONTROL_SPACE /*[0x0[D] CARRIAGE RETURN]*/
               | CLASS_LETTER_A_TO_O /*[0x4[D] 'M', 0x6[D] 'm']*/,
        [0x1E] = CLASS_LETTER_A_TO_O /*[0x4[E] 'N', 0x6[E] 'n']*/,
        [0x1F] = CLASS_LETTER_A_TO_O /*[0x4[F] 'O', 0x6[F] 'o']*/
               | CLASS_UNDERSCORE    /*[0x5[F] '_']*/,
};

extern void extract_mask_32(char *buff, u8 class_bits[32], u64 bytes_read, u32 *output);

int main(int argc, char **argv)
{
        int fd = open("file.stc", O_RDONLY);
        u64 length = lseek(fd, 0, SEEK_END);
        lseek(fd, 0, SEEK_SET);
        /*The code is meant for this exercise and I know that the file is small, so the buffer is guaranteed to be way larger than it.*/
        char buff[8192] = {0};
        ssize_t bytes_read = read(fd, buff, length);
        buff[bytes_read] = '\0';
        u64 blocks = (bytes_read + 31) / 32;
        u32 *output = malloc(blocks * sizeof(*output));

        u8 class_mask[32] = {0};

        memset(class_mask, CLASS_WORD, sizeof(class_mask));
        extract_mask_32(buff, class_mask, bytes_read, output);

        printf("words:\n");

        u32 word_count = 0;
        for (u64 i = 0; i < (u64)bytes_read; ++i) {
                u32 batch_number = i >> 5; /*this tells us which u32*/
                u32 relative_index = i & 31; /*this gives the index inside the batch_number, since we did 32 at a time in the assembly*/
                u32 mask = (output[batch_number] >> relative_index) & 1u;
                if (mask == 1) {
                        printf("word match: %c\n", buff[i] == '\n' ? ' ' : buff[i]);
                        word_count++;
                }
        }
        printf("word count: %u\n", word_count);

        memset(class_mask, CLASS_DIGIT, sizeof(class_mask));
        extract_mask_32(buff, class_mask, bytes_read, output);

        printf("digits:\n");
        u32 digit_count = 0;
        for (u64 i = 0; i < (u64)bytes_read; ++i) {
                u32 mask = (output[i / 32] >> (i & 31)) & 1u;
                if (mask == 1) {
                        printf("digit match: %c\n", buff[i] == '\n' ? ' ' : buff[i]);
                        digit_count++;
                }
        }
        printf("digit count: %u\n", digit_count);

        free(output);
        close(fd);

        return 0;
}

The function [extract_mask_32] is the assembly code. The file.stc contains the following code:

module("main");

import{
        println :: "io".println,
};

println :: config {
        .bytes_reserved = @kib(64)
};

main :: function_mutate(p: &StcProcess) -> Error.StcError
{
        err := try println("{}", .{5 + 5}) onfail {
                return err;
        };
        return Error.OK;
}
byte i      0         1         2         3
            01234567890123456789012345678901
buff[i]     module("main");..import{.
bit i       11111100111100000111111000000000

output[0] = 0x007E0F3F
bit 31..0  = 0000 0000 0111 1110 0000 1111 0011 1111
(. is '\n')

The C code prints:

words:
word match: m
word match: o
word match: d
word match: u
word match: l
word match: e
word match: m
word match: a
word match: i
word match: n
word match: i
word match: m
word match: p
word match: o
word match: r
word match: t
word match: p
word match: r
word match: i
word match: n
word match: t
word match: l
word match: n
word match: i
word match: o
word match: p
word match: r
word match: i
word match: n
word match: t
word match: l
word match: n
word match: p
word match: r
word match: i
word match: n
word match: t
word match: l
word match: n
word match: c
word match: o
word match: n
word match: f
word match: i
word match: g
word match: b
word match: y
word match: t
word match: e
word match: s
word match: _
word match: r
word match: e
word match: s
word match: e
word match: r
word match: v
word match: e
word match: d
word match: k
word match: i
word match: b
word match: 6
word match: 4
word match: m
word match: a
word match: i
word match: n
word match: f
word match: u
word match: n
word match: c
word match: t
word match: i
word match: o
word match: n
word match: _
word match: m
word match: u
word match: t
word match: a
word match: t
word match: e
word match: p
word match: S
word match: t
word match: c
word match: P
word match: r
word match: o
word match: c
word match: e
word match: s
word match: s
word match: E
word match: r
word match: r
word match: o
word match: r
word match: S
word match: t
word match: c
word match: E
word match: r
word match: r
word match: o
word match: r
word match: e
word match: r
word match: r
word match: t
word match: r
word match: y
word match: p
word match: r
word match: i
word match: n
word match: t
word match: l
word match: n
word match: 5
word match: 5
word match: o
word match: n
word match: f
word match: a
word match: i
word match: l
word match: r
word match: e
word match: t
word match: u
word match: r
word match: n
word match: e
word match: r
word match: r
word match: r
word match: e
word match: t
word match: u
word match: r
word match: n
word match: E
word match: r
word match: r
word match: o
word match: r
word match: O
word match: K
word count: 150
digits:
digit match: 6
digit match: 4
digit match: 5
digit match: 5
digit count: 4
module("main");
^^^^^^  ^^^^

import{
^^^^^^
        println :: "io".println,
        ^^^^^^^     ^^  ^^^^^^^
};

println :: config {
^^^^^^^    ^^^^^^
        .bytes_reserved = @kib(64)
         ^^^^^^^^^^^^^^    ^^^ ##
};

main :: function_mutate(p: &StcProcess) -> Error.StcError
^^^^    ^^^^^^^^^^^^^^^ ^   ^^^^^^^^^^     ^^^^^ ^^^^^^^^
{
        err := try println("{}", .{5 + 5}) onfail {
        ^^^    ^^^ ^^^^^^^         #   #   ^^^^^^
                return err;
                ^^^^^^ ^^^
        };
        return Error.OK;
        ^^^^^^ ^^^^^ ^^
}

Everything matched correctly. Nothing more and nothing less. We haven't handled all classes yet, but you can see how you can apply the same logic to all of them. There are two unknowns right now that I haven't explicitly explained and one of them is potentially tricky:

  1. What about symbols? There is no class for symbols. The fact that there is no class means that symbols are anything that's NOT 0 AND are NOT matching any of the other classes.
  2. What about strings? Something like "my string" would match at the exact positions and whatever is in that start/end double quote window is the string, right? Well, that's not as easy.

Let's see what happens here:

"mystring \" "

Now we have 3 double quotes and one is escaped, so the entire string should contain that escaped double quote as well. In the next post, I will explain how to deal with that final quote as well as appending some of the tokens to arrays, so we can print them. I won't be doing it for all, because it's pretty mechanical, but you'll hopefully get the idea to do it for the rest of them.

Found this useful? Support the writing on Ko-fi.