3 ms·

Two fast (today) instructions: unsigned h = _pext_u32(1264523 * x, 0x1020a01);

• tmyklebu 1y ago
  Same idea, but without BMI2: unsigned h = (1264523 * x & 0x1020a01) * 134746240 >> 27; Alternatively: unsigned h = (1639879 * x & 0x1038040) * 67375104L >> 32 & 31; The multiplication by 67375104L can be a usual 32x32 IMUL where the high half goes to edx, though I'm not sure that conveys a benefit over a 64x64 IMUL in serial code these days.
• mananaysiempre 1y ago
  Where does the constant multiplier come from? Is it just bruteforced, or is there an idea behind it that I can’t see?
  • tmyklebu 1y ago
    Yeah, that was just a search. There are 2^32 multipliers; call them m. For a bit in m*x to be useful, it must be zero for 16 symbols and one for 16 symbols. Call those bits "useful bits." Try every multiplier; for each multiplier, compute all the useful bits (usually not many) and try all masks with 5 useful bits.
    • mananaysiempre 1y ago
      > For a bit in m*x to be useful, it must be zero for 16 symbols and one for 16 symbols. Ahh brilliant, thanks!