|
cowboyro
Premium Member
2013-Jan-23 2:18 pm
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 Member join:2000-05-04 not in ohio |
dave
Premium Member
2013-Jan-23 10:53 pm
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 |
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 Member
2013-Jan-24 8:55 am
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 Member join:2000-05-04 not in ohio 1 edit |
dave
Premium Member
2013-Jan-24 11:06 am
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 Member
2013-Jan-24 11:43 am
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 Member join:2000-05-04 not in ohio |
dave
Premium Member
2013-Jan-24 12:40 pm
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. |
|