Basic Understanding of Branchless Vectorised Parsing
To understand this better, I will be starting with a simpler form, that does not involve vectorisation. The target of this will be a programming language I am currently developing, called stormc, and these techniques are already used for it.
Short Detour
The words "parsing" and "lexing" and "tokenizing" all sound kind of the same. In a pure definitional sense, they're all "parsing". What it is usually (but not always) talked about as "parsing" is in reference to going through tokens and building an AST / walking the AST. Lexing or tokenizing is getting raw text (like in here) and transforming it into tokens, which you decide what they are and how they're classified.
The target for this parser will be this code. I will not go into how this code works or what things mean in there, since this isn't the purpose here.
module("main");
import{
println :: "io".println,
};
println :: config {
.bytes_reserved = @kib(64)
};
main :: function_mutate(p: &StcProcess) -> Error
{
lane main {
err := try println("{} = {}", .{"result", 5 + 5}) onfail {
return err;
};
}
return Error.OK;
}
As you can see, there are a few things that you can probably classify just by looking at them.
For example, it's clear that there are literal digits (like the number 5), arithmetic symbols, compound symbols (such as ::),
strings (such as "result") and keywords (such as return, try, onfail etc.).
One classification can be:
- Digits: anything that is a number, such as:
1,2.01 - Strings: anything that starts with double quotes and ends in double quotes, such as:
"some text" - Symbols: single and compound symbols, such as:
:=,::,@,{etc. - Identifiers: anything that is not the other 3, such as:
return,err,onfailetc.
If we were to walk the text character by character, we could do something like: (pseudocode)
token_array = [];
for text in source:
if text == "return":
token_array.append(TOKEN_KIND_KEYWORD);
if text == "+":
token_array.append(TOKEN_SYMBOL_PLUS);
/*and so on for others*/
We would need the starting position of the token, but that is not relevant right now, pretend that we also got the position as well. I am not going to get into parsing character-by-character. There are many videos, books and courses out there on compilers that cover this. For identifiers and digits (among some other ones) you'd need to check if the first character is a character that is allowed for an identifier, which is usually an alphanumeric or an underscore, and then walk the entire word/digit till the end. This is very slow. We can ingest 16, 32 or even 64 bytes at a time and compare without any branching using SIMD, instead of taking 1 character at a time and if/else'ing everywhere.
To do so, we need to build a table. That table is very specific to what you are parsing, so it is kind of hard to codegenerate it, but not impossible.
The reason it is very specific is because you get to decide what gets classified with what. For example, maybe in what text you're dealing with, something like a symbol doesn't exist,
or maybe the double quote '"' doesn't exist and there are no such things as "strings" etc. It is very open ended.
Step One: Classification
The order in which you write the enums here does not matter (as long as you do the assignments like that of course).
#include <unistd.h>
#include <stdint.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
};
bit value class
7 0x80 -
6 0x40 CLASS_QUOTE
5 0x20 CLASS_LETTER_P_TO_Z
4 0x10 CLASS_LETTER_A_TO_O
3 0x08 CLASS_DIGIT
2 0x04 CLASS_CONTROL_SPACE
1 0x02 CLASS_UNDERSCORE
0 0x01 CLASS_SPACE
CLASS_LETTER_A_TO_Z 0x30 bits 5, 4
CLASS_WHITESPACE 0x05 bits 2, 0
CLASS_WORD 0x3A bits 5, 4, 3, 1
Next, we will build two tables and I will explain the logic behind both of them. The comments inside the tables are very important, so please do read them. I am using hex values for indices intentionally, so you can map the index to the square bracket and see the relationship. We are using 7 bits of the 8 only, so we would have space for another CLASS if required.
/* *
* 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] '_']*/,
};
As you can see by reading through the table and comments (you did read them, right?) we are splitting the ASCII character into two parts:
- The lower 4 bits (low nibble)
0x0[0] - The higher 4 bits (high nibble)
0x[0]0
0x H L
| |
| +-- low nibble: table_low_class[L]
+---- high nibble: table_high_class[H]
There is logic behind these classifications, though, so fear not.
The A_TO_O and P_TO_Z classification
With a single letter class, '@' (0x40) would get "letter" from high nibble 4 and from low nibble 0 (because of 'P'). This is the key idea of the table and the A_TO_O and P_TO_Z split.
'@' = 0x40 high[4] low[0] &
one letter class LETTER SPACE | DIGIT | LETTER LETTER
A_TO_O, P_TO_Z A_TO_O SPACE | DIGIT | P_TO_Z CLASS_NONE
HEX CHARACTER
0x50 P 0x70 p
0x41 A 0x51 Q 0x61 a 0x71 q
0x42 B 0x52 R 0x62 b 0x72 r
0x43 C 0x53 S 0x63 c 0x73 s
0x44 D 0x54 T 0x64 d 0x74 t
0x45 E 0x55 U 0x65 e 0x75 u
0x46 F 0x56 V 0x66 f 0x76 v
0x47 G 0x57 W 0x67 g 0x77 w
0x48 H 0x58 X 0x68 h 0x78 x
0x49 I 0x59 Y 0x69 i 0x79 y
0x4A J 0x5A Z 0x6A j 0x7A z
0x4B K 0x6B k
0x4C L 0x6C l
0x4D M 0x6D m
0x4E N 0x6E n
0x4F O 0x6F o
Look closely at A to O and a to o, for the low nibbles:
1,2,3,4,5,6,7,8,9, A, B, C, D, E, F
Now look at our low nibble table again ( I will be including 2 entries that do not have A TO O):
NOTE: With the flags I wrote, the A_TO_Z is a union of A_TO_O and P_TO_Z. This means that BOTH sets show in that range.
[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']*/,
Notice: the 0x00 index and 0x10 do NOT have CLASS_LETTER_A_TO_O. That is because they're not a value betwixt 1 through F.
Now, let's look at the high nibbles: 4, 5, 6 7. That's all for the high nibbles.
Let's look at the high nibble table and keep in mind that bracket relationship with the index.
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,
};
As you can see, 0x04, 0x05, 0x06, 0x07, 0x14, 0x15, 0x16 and 0x17 have the letter classes.
If you're wondering why the 0x15...0x17 are also in there, the answer is: because they also have 4, 5, 6, 7.
Now let's go back to the code and see how does all of this even help? We will be looking at this part of the code only, to keep it simple:
module("main");
Let's say we load all those characters. We can load up to 32 on AVX2, so we will just pad the rest with 0 ( more on this later).
current = ['m' 'o' 'd' 'u' 'l' 'e' '(' '"' 'm' 'a' 'i' 'n' '"' ')' ';']
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0..15 'm' 'o' 'd' 'u' 'l' 'e' '(' '"' 'm' 'a' 'i' 'n' '"' ')' ';' 0
16..31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Now, let's take the first letter one, 'm'. The first thing we want to do with it, is to split its high and low nibbles, to match our tables of high and low nibbles.
- We lookup where 'm' is and what hex value it has:
0x6D m - We look at our low nibble table to see what [D] (the low nibble of [m]) has for classes:
- the low nibble D appears twice:
[0D]and[1D] - we look what classes those are:
0D = CLASS_CONTROL_SPACE | CLASS_LETTER_A_TO_O1D = CLASS_CONTROL_SPACE | CLASS_LETTER_A_TO_O- Candidates for low nibble:
[CLASS_CONTROL_SPACE, CLASS_LETTER_A_TO_O]
- the low nibble D appears twice:
- We look at our high nibble table to see what 6 (the high nibble of m) has for classes:
- the high nibble 6 appears twice:
0x06and0x16 - we look what classes those are:
0x06 = CLASS_LETTER_A_TO_O0x16 = CLASS_LETTER_A_TO_O- Candidates for high nibble:
[CLASS_LETTER_A_TO_O]
- the high nibble 6 appears twice:
What do we get after this:
(CLASS_CONTROL_SPACE | CLASS_LETTER_A_TO_O) & CLASS_LETTER_A_TO_O
The answer is, obviously, CLASS_LETTER_A_TO_O, which the character [m] is.
'm' = 0x6D = 0110 1101
bit 7 6 5 4 3 2 1 0
table_low_class[0xD] 0 0 0 1 0 1 0 0 CONTROL_SPACE | A_TO_O
table_high_class[0x6] 0 0 0 1 0 0 0 0 A_TO_O
& 0 0 0 1 0 0 0 0 A_TO_O
You might be wondering at this point, why did I skip some of them? Like, what happened with 2D, 3D, 4D...7D? How come they are not included? They do have [D] as well, so why doesn't our table go all the way to 7D? Let's look what those values actually are:
2D = [-]
3D = [=]
4D = [M]
5D = []]
6D = [m]
7D = [}]
As you can see, only 2 of those are actually the character [m] (either upper or lower case) but that's not the important part. Our tables are specifically up to 32 characters and we can lookup the class of a character by splitting its higher and lower nibbles, which go from 0 to 15.
high \ low 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 . . . . . . . . c c c c c c . .
1 . . . . . . . . . . . . . . . .
2 s . q . . . . . . . . . . . . .
3 d d d d d d d d d d . . . . . .
4 . A A A A A A A A A A A A A A A
5 P P P P P P P P P P P . . . . _
6 . A A A A A A A A A A A A A A A
7 P P P P P P P P P P P . . . . .
8..F . . . . . . . . . . . . . . . .
s CLASS_SPACE d CLASS_DIGIT _ CLASS_UNDERSCORE
c CLASS_CONTROL_SPACE A CLASS_LETTER_A_TO_O . CLASS_NONE
q CLASS_QUOTE P CLASS_LETTER_P_TO_Z
Sidenote: single symbols will be discussed later, as they can be derived from the existing classes.
For a character like [m] we would do (scalar form to keep it simple, which will look very redundant, but the steps are what is important).
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*/
The last 2 may look confusing, especially in this scalar version. The [not_word] is [0] when it is not not word (double negation), so when we get to [is_word], it being 0 flips it to 1, telling us it is a word. So what does this buy us, even if we do this on the entire array? Let's see what the results would be. We already know we can identify a word correctly, so let's see side-by-side, the characters, and the output of 0s and 1s:
['m' 'o' 'd' 'u' 'l' 'e' '(' '"' 'm' 'a' 'i' 'n' '"' ')' ';']
['1' '1' '1' '1' '1' '1' '0' '0' '1' '1' '1' '1' '0' '0' '0']
character m o d u l e ( " m a i n " ) ;
hex 6D 6F 64 75 6C 65 28 22 6D 61 69 6E 22 29 3B
high 6 6 6 7 6 6 2 2 6 6 6 6 2 2 3
low D F 4 5 C 5 8 2 D 1 9 E 2 9 B
class A A A P A A . q A A A A q . .
is_word 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0
After we have the second array of 1s and 0s, it is trivial to calculate the length of the word without a loop, its starting position and we already know its type. How we do this for all of them at once, in one operation, and how to get the starting position and length will be the next post in this series.
Note: for length, we actually don't really need it, because if you know the starting position of a token and the next token, you can just count backwards to get the length if you need it.
That is all for this post.
Found this useful? Support the writing on Ko-fi.