How to effectively check the bitmask?

Question

I use inotify and want to effectively check the reported bitmask event (see inotify man page ).

Now I could carefully check every bit on every event, but that would be very rude, if not stupid, since I would have N conventions every time. Or calling

( bitmask & mask ) == mask 

for a mask is already super effective?

Since the resulting bitmask is basically just a certain number, I have to use basic arithmetic operations for this. But before I came up with something myself, I wanted to ask if there is a well-known effective way to check this bitmask. So there?

Answer 1

If you want to check one bit mask, then

 if ((value & mask) == mask) 

will give you an exact match ("all bits in the mask") and

 if ((value & mask) != 0) 

will provide a free match ("any bit in the mask"). The compiler also optimizes checking against zero.

If you have several bitmasks, you want to extract the maximum information from each check in the time domain (extreme case: if all the values ​​that you get are definitely odd, you do not need to check the 0 bit at all. This will always be 1). Ideally, you need to identify the first round bit, which has a 50% chance of being 1.

In both groups, you then identify a subgroup (possibly not the same in two cases) with the same probability.

 if ((value & SPECIAL_MASK_1) == SPECIAL_MASK_1) { if ((value & SPECIAL_MASK_2) == SPECIAL_MASK_2) { ... } else { ... } } else { if ((value & SPECIAL_MASK_3) == SPECIAL_MASK_3) { ... } else { ... } } 

If you had, say, 32 states, each of which is mapped to one bit, and only one bit can be set for each call - the simplest case - a sequential sequence would be one of 32 checks one by one

 if ((mask & 0x00000001) == 0x00000001) { } else if ((mask & 0x00000002) == 0x00000002) { } ... 

and the first simple optimization was to first establish checks for the most common cases. Let's say that one case out of three seventh bit is set; you first check on the seventh bit.

Thus, you will receive only one check in 33% of cases; then maybe two more checks 20% of the time ... and at the end on average you can run, say, seven checks.

Another possibility is

 if (mask & 0x0000FFFF) { // The bit is in the LSW if (mask & 0x0000FF00) { // MSB of LSW if (mask & 0x0000F000) { ... } else { } } } else { } 

This will be performed exactly five checks each time. However, at this point, considerations about CPU architecture, branch prediction, etc. will probably surpass any optimization you can try to do.

If you have a very complicated setup or some other restriction (for example, an embedded device), I am afraid that the cost of analyzing, building, debugging and maintaining an “optimized” or “brute force” test will most likely be more balanced any advantage that you could squeeze out of the first.

Answer 2

To check for several bits of a mask, I use a loop. If you use a decent compiler, it should optimize the code pretty well. If you do not have significant performance problems, you should not optimize it manually, since all processors that I know implement a logical bit test or bit-wise AND operation in one command. Thus, you have two instructions: a logical instruction and a processor-state branch command for each bit. Not a huge amount of code to run and, as far as I know, it is impossible to win. (Note that since mask is 32 bits wide, if you are running a 16-bit kernel processor, there will be a few more instructions for checking both halves.)

 void processEvents(uint32_t events) { uint32_t bitToTest; // Check each bit in turn for(bitToTest = 1; bitToTest < events; bitToTest << 1) { // Check which bit is set. If none then the default case is used. switch(bitToTest & events) { case IN_ACCESS: // Handle the IN_ACCESS event flag here. break; case IN_ATTRIB: // Handle the IN_ATTRIB event flag here. break; // Et cetera... default: // No flag was set, so do nothing. break; } } } 

Answer 3

If only one bit is set, and if your code should not be portable, you can use the built-in functions that give you the position of the set bit, and then use the result in the switch statement. For gcc, i.e. be

 __builtin_ffs 

Answer 4

If you need to check each bitmask, there is no other way than to check explicitly. However, if specific bit masks are known, bitwise checks can be performed, which in fact leads to a decrease in half of the possible bit masks at each step.