2
$\begingroup$

I have the following byte: 0x0A and I need to test if a quadword contains it or no using standard bitwise operarion (or, nor, xor). For instance:

0x1689FFBB768922AC ---> false 0x106489320A792399 ---> true

Unfortunately I cannot use intel SSE2 extension because this will make the code heavily depndent on the platform.

Can we find some bitmask to bitwise or with? Or maybe something else...?

$\endgroup$
  • 1
    $\begingroup$ If you're looking for specific implementation details, you might have more luck on stackoverflow.com . $\endgroup$ – Draconis May 27 '18 at 22:41
3
$\begingroup$

Yes, it can be done. Here is one reasonable approach. First XOR the value with 0x0A0A..0A:

t = x ^ 0x0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A;

So now the problem becomes testing whether y contains a zero byte. First we'll replace every byte with a single bit that is 1 if the byte is non-zero, or 0 if the byte is zero:

u = t | (t>>4);
u = u | (u>>2);
u = u | (u>>1);

(Here we only care about the least significant bit of each byte; the remaining bit positions hold garbage that we don't care about.) Now we'll flip each of those bits:

v = ~u;

At this point the LSB of each byte is 1 if the original value contained a 0x0A there, or 0 otherwise. So, we'll test whether any of these bits are 1:

w = v | (v>>64);
w = w | (w>>32);
w = w | (w>>16);
w = w | (w>>8);
y = w & 1;

At this point, y is the result you are looking for: it will be 1 if the original value had a 0x0A byte anywhere, or 0 otherwise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.