What pseudo_pext_t does is different from what the pext instruction does

[jason7708]

trafficstars

I'm not sure if this is a bug or an intentional design. You can reproduce it through the following unit test.

constexpr auto p = lookup::detail::pseudo_pext_t(21u);
CHECK(p(21u) == 7u);

In this case, the coefficient will become (4 + 2 + 1) = 7 but the result will be 4.

    0 0 0 1 0 1 0 1   (value << 0)
    0 0 1 0 1 0 1 0   (value << 1)
    0 1 0 1 0 1 0 0   (value << 2)    +
---------------------------------------

When the gaps between the bits we are interested in are too small, multiplying by a coefficient can cause addition that leads to a carry, which makes the result incorrect.

However, the result of the lookup is correct because your implementation uses pseudo_pext_t to ensure that hash value is unique when selecting masks. Therefore, even if pseudo_pext_t is incorrect, it will still select a mask that avoids this issue.

I'm not sure if this is a pext function that only supports specific masks, but since its result differs from the actual pext instruction, I am posting this issue.

[elbeno]

I think this is intended. Implementing the full pext would be more expensive, hence pseudo_pext_t is an incorrect approximation that is made correct by mask selection, as you say. @lukevalenty

[lukevalenty]

@elbeno is correct here. It's not a real parallel bit extract because we can get overlap that causes carry. Intended to make this somewhat clear by naming it a "pseudo pext".

For the purposes of finding an efficient hash function for a set of keys, it happens to work nearly as well as a true pext.