dslreports logo
site
 
    All Forums Hot Topics Gallery
spc

spacer




how-to block ads


Search Topic:
uniqs
766
share rss forum feed


cowboyro
Premium
join:2000-10-11
Shelton, CT

Logic bitwise operators help needed...

Given 2 32-bit words, one a sample S and one a mask M, I need to find a match true/false condition based on

If Sn = Mn OR Mn = 0b00000000 for ALL the 4 bytes in the word (n=0...3) then TRUE
Otherwise FALSE.

Sounds simple and I could do it easily by individually checking the 4 bytes, the problem is that it is time-critical and I want to do it as fast as I can - if possible using bitwise operators on the entire 32-bit words, in as few as possible operations.

C++ if it matters, although it would really be exactly the same for all languages...

Example:
S = 0b10101010 11001100 01010101 11110000
M = 0b00000000 11001100 00000000 11110000
would be a match (TRUE result)
but
S = 0b10101010 11001100 01010101 11111111
M = 0b00000000 11001100 00000000 11000110
would be no match (FALSE) because byte 0 is a mismatch and the mask is not 0

Thoughts?


dave
Premium,MVM
join:2000-05-04
not in ohio
kudos:8
Reviews:
·Verizon FiOS

You're calling Mn a mask, but when you want it to be equal to Mn, you're not using it in any way that I'd call 'a mask'.

If you had a true mask as well, let's call it Xn, that was all ones if Mn != 0, and all zero if Mn == 0, then

result Vn = (Sn & Xn) == (Mn & Xn)

or for the whole thing V = (S & X) == (M & X)

Given f(y) = (x & y) ? y : 0
then X = f(0xff) | f(0xff00) | f(0xff0000 | f(0xff000000)

but that still seems kind of clunky. It's tractable if you don't have to compute X for every sample, I guess.

Attempt #2:

given B0 = 0xff, B1 = 0xff00, B2 = 0xff0000, B3 = 0xff000000

and V(n) = (Sn & Bn) == (Mn & Bn) || (Mn & Bn) == 0

then V = V(0) | V(1) | V(2) | V(3)


dave
Premium,MVM
join:2000-05-04
not in ohio
kudos:8
Reviews:
·Verizon FiOS
reply to cowboyro

Final answer:

T = S ^ M;
V =
(T & M & 0xff) == 0 &&
(T & M & 0xff00) == 0 &&
(T & M & 0xff0000) == 0 &&
(T & M & 0xff000000) == 0;

Explanation: T is the bits that differ between the two comparands.
For any byte position, if S and M are identical (in that byte position) then T is zero, so T & anything is zero. If M is zero (in that byte position) then anything & M is zero.

Depending on your expected data, it may be a useful optimization to add T == 0 as a first alternative:

T = S ^ M;
V = (T == 0) ||
(T & M & 0xff) == 0 &&
(T & M & 0xff00) == 0 &&
(T & M & 0xff0000) == 0 &&
(T & M & 0xff000000) == 0;



cowboyro
Premium
join:2000-10-11
Shelton, CT
reply to cowboyro

I get your solution, but that still deals with one byte at a time.
I am trying to come up with something that will handle the entire word (all 4 bytes) at the same time as execution time is critical.


dave
Premium,MVM
join:2000-05-04
not in ohio
kudos:8
Reviews:
·Verizon FiOS

1 edit

Actually, my final answer does not work. Consider one byte only

S = 0000 0101
M = 0000 0100

Clearly this should result in 'false'.

T = S ^ M = 0000 0001
T & M = 0000 0000

which gives the answer 'true'.

My error came from knowing that (T & M) == 0 could be written in C as !(T & M) and then I treated than as ~(T & M), which it ain't.

---

I believe there is no such solution. The trouble is that, essentially, each bit in the 'mask' has to carry 3 possible meanings:

1 = corresponding bit in S must be 1
0 = corresponding bit in S must be 0
0 = corresponding bit in S does not matter (but this only applies if the entire byte of M is zero)

It is that last consideration that forces byte-wise examination of the operands.



cowboyro
Premium
join:2000-10-11
Shelton, CT

Yeah, I finally put a sample in a Karnaugh map and the result couldn't be minimized to bit-independent operations.
Guess I'll have to handle it one bite at a time...


dave
Premium,MVM
join:2000-05-04
not in ohio
kudos:8

Yes, I have a napkin on my desk with maps and truth-tables scribbled on it... this was a fun diversion while I was waiting for a system build or two.