Bit Vectors and my first steps into assembly

Another trick for classifying bytes is to use pshufb. That instruction works like:

  fn pshufb(a: [i8; 16], b: [i8; 16]) -> [i8; 16] {
    result = [0; 16]
    for j in 0, 1, …, 15 {
      if b[j] >= 0 {
        result[j] = a[b[j] & 15];
      }
    }
    return result;
  }

  a = pshufb(m1, input & 0xf)
  b = pshufb(m2, (unsigned_input) >> 4)
  x = f(a,b)

This technique can sometimes be used to mark a few special characters.

In certain conditions gcc will actually generate instructions that use this same bitvector described: https://godbolt.org/z/6Gfjv6PGd (notice the funny 130159 value in there)

The only thing I did was to adjust the range of characters so that the bitvector fits 64 bits. Sadly, I do not this it would work for the author's bigger range.

Hey i just discovered that my blog post was posted here i indeed have little experience with assembly and the idea was just could i use a 'larger register' like you would use a 64bit register to keep the table hot in the CPU. But sadly i failed and kinda gave up and made the post as is.

The good news is i will do a 'second' step into assembly programming where i will try to implement the algorithm of `dan-robertson`. There will also be a switch case and other tricks suggested in this thread.

With my experience i noticed that i'm missing breakpoints and unit tests to better understand what each assembly step does. Which things read from memory etc. What also doesn't help is that x86 feels a bit like an 'arbitrary patchwork of instructions' where some instructions exists for float and doubles but not int etc.

It seems a lot of implicit knowledge is needed to do assembly programming, for example `xor A A` to zero the register. So i probably have to read hackers delight from back to back.

The only assembly i have done in the past was AVR which is very limited and it was easy to understand. I could just put a JTAG debugger and see the registers directly.

Golang is used because it is a nice balance between high and low level, unlike the JVM/Python (JIT compilers) you can't disassemble and see the native code.

Ideally there would be a 'modern hackers delight' which would also include some simple simd tricks.

My goal is to eventually reimplement 'write a compiler/interpeter in go' in zig and rust to learn those languages. After 1h of trying it seems zig is 'quite' easy to include assembly as well and to do SIMD. But currently i'm on page 40 of 'write a compiler in go' so i'm still a long way off. For the zig/rust implementation i probably need to include a GC in this simple VM https://craftinginterpreters.com/garbage-collection.html so still a lot to learn.

Also one 'clever' idea i implemented in the lexer was to allow full UTF8 but only in string literal parsing mode. This avoids that you can use emoijs as variable and function names.

I know the post only uses SIMD as an attempt to do bitmask lookup for each byte, but a good alternative use of SIMD is for parallel data processing, i.e. operating on more than one character. Being able to identify a range of characters making up the identifier is much faster than checking one character at a time, especially for avoiding branching.

Did a bit of xmas hacking to come up with the function to find identifiers in parallel in 32-byte chunks. I used Zig since it makes vector/SIMD programming easy.

The code is in: https://github.com/williamw520/misc_zig/blob/main/identifier...

The generated code of the nextBitmask32() function has about 38 instructions. https://godbolt.org/z/7ME3sW55e

That's 38 instructions for processing every 32 bytes. With no branching!

> Since go doesn’t inline assembly i decided to include the search loop into the assembly itself and to return the index of the non matching character. Sadly i didn’t get it to work fully because i’m missing tools to actually debug the assembly itself.

Um... "gdb <my_binary>", "break <my_function>", "run", just like any other tool.

Then "disassemble" to see the instructions around the PC, "stepi" to execute one instruction. "info register" to get current state (or use registers in an expression as e.g. "print $rax" or "print $r11").

And that's it. Debuggers are actually natively tools operating at the level of machine instructions. The language syntax support is a level on top.

I’m surprised he didn’t use a switch statement, as that is the canonical way to ask the compiler to make the jump table for you.

This article is kind of fine overall but gets so many specifics wrong. I guess this is to be expected from someone just beginning to verse in assembly, but still.

    if '0' <= x && x <= '9' || 'a' <= x && x <= 'z' || 'A' <= x && x <= 'Z' {
 ...
    }

If you really want to optimize code like `a <= x && x <= b` by hand, you can rewrite it to `x - a <= b - a`, where the comparison is unsigned; GCC and LLVM do that for you. Next, you can optimize the case-insensitive check by masking out the case bit:

    void f();
    void test(char x) {
        if ((unsigned char)(x - '0') < 10 || (unsigned char)((x & 0x5f) - 'A') < 26) {
            f();
        }
    }

    lea     eax, [rdi - 48]
    cmp     al, 10
    jb      f
    and     dil, 95
    add     dil, -65
    cmp     dil, 25
    jbe     f
    ret

    unsigned short test(__m128i x) {
        return _mm_movemask_epi8(_mm_or_si128(
            _mm_cmplt_epi8(_mm_sub_epi8(x, _mm_set1_epi8(0xb0)), _mm_set1_epi8(0x8a)),
            _mm_cmplt_epi8(_mm_sub_epi8(_mm_and_si128(x, _mm_set1_epi8(0x5f)), _mm_set1_epi8(0xc1)), _mm_set1_epi8(0x9a))
        ));
    }

The section about bitvectors is fine.

x86 processors don't have 128-bit MMX registers and 256-bit MMY registers. They have legacy 64-bit MMX registers, modern 128-bit XMM registers, and modern 256-bit YMM registers. This MMX/XMM duality sure does confuse people, so I don't blame the author. But come on, at least read the article before publishing; broken GitHub URLs without `blob/master` and broken ()[] Markdown syntax is not funny.

To those trying to make sense of Zig output, don't forget `-O ReleaseFast`. The codegen here is very simple, just a 128-bit integer simulated with two 64-bit ones.