New YouTube Channel

squeek502 · September 11, 2025, 3:26am

Fantastic as always.

I coincidentally used similar techniques (on a much smaller scale) in my named character references data structure implementation:

github.com/squeek502/named-character-references

src/named_character_references.zig

abd0912c3


      
          // Get the second layer node by re-using the link.mask.
          // For example, if the first character is 'n' and the second character is 'o':
          //
          // This is the link.mask when the first character is 'n':
          // 0001111110110110111111111100001000100000100001000000
          //            └ bit_index of 'o'
          //
          // Create a mask where all of the less significant bits than the bit index of
          // the current character ('o') are set:
          // 0000000000001111111111111111111111111111111111111111
          //            └ bit_index of 'o'
          //
          // Bitwise AND this new mask with the link.mask to get only the set bits less
          // significant than the bit index of the current character:
          // 0000000000000110111111111100001000100000100001000000
          //
          // Take the popcount of this to get the index of the node within the
          // second layer. In this case, there are 16 bits set, so the index
          // of 'o' in the second layer is link.second_layer_offset + 16.
          const mask = (@as(u52, 1) << bit_index) - 1;

This file has been truncated. show original