Page 1 of 1
Is my code OK??
Posted: Wed Aug 16, 2006 8:18 am
by matthias
Hi,
I wrote code for setting bits within 32-bit integers. I defined all masks needed. When I set a bit I just give my variable an or operation, that's ok. But when I want to unset it I don't know if I do the right thing. Now I use the xor operator (^) Is this a good idea? Or is there a simpler idea?
bits.h:
Code: Select all
#ifndef BITS_H_INCLUDED
#define BITS_H_INCLUDED
/* bits 0 to 7 */
#define BIT_0 0x00000001 // (0000 0000 0000 0000 0000 0000 0000 0001)
#define BIT_1 0x00000002 // (0000 0000 0000 0000 0000 0000 0000 0010)
#define BIT_2 0x00000004 // (0000 0000 0000 0000 0000 0000 0000 0100)
#define BIT_3 0x00000008 // (0000 0000 0000 0000 0000 0000 0000 1000)
#define BIT_4 0x00000010 // (0000 0000 0000 0000 0000 0000 0001 0000)
#define BIT_5 0x00000020 // (0000 0000 0000 0000 0000 0000 0010 0000)
#define BIT_6 0x00000040 // (0000 0000 0000 0000 0000 0000 0100 0000)
#define BIT_7 0x00000080 // (0000 0000 0000 0000 0000 0000 1000 0000)
/* byte */
/* bits 8 to 15 */
#define BIT_8 0x00000100 // (0000 0000 0000 0000 0000 0001 0000 0000)
#define BIT_9 0x00000200 // (0000 0000 0000 0000 0000 0010 0000 0000)
#define BIT_10 0x00000400 // (0000 0000 0000 0000 0000 0100 0000 0000)
#define BIT_11 0x00000800 // (0000 0000 0000 0000 0000 1000 0000 0000)
#define BIT_12 0x00001000 // (0000 0000 0000 0000 0001 0000 0000 0000)
#define BIT_13 0x00002000 // (0000 0000 0000 0000 0010 0000 0000 0000)
#define BIT_14 0x00004000 // (0000 0000 0000 0000 0100 0000 0000 0000)
#define BIT_15 0x00008000 // (0000 0000 0000 0000 1000 0000 0000 0000)
/* word */
/* bits 16 to 31 */
#define BIT_16 0x00010000 // (0000 0000 0000 0001 0000 0000 0000 0000)
#define BIT_17 0x00020000 // (0000 0000 0000 0010 0000 0000 0000 0000)
#define BIT_18 0x00040000 // (0000 0000 0000 0100 0000 0000 0000 0000)
#define BIT_19 0x00080000 // (0000 0000 0000 1000 0000 0000 0000 0000)
#define BIT_20 0x00100000 // (0000 0000 0001 0000 0000 0000 0000 0000)
#define BIT_21 0x00200000 // (0000 0000 0010 0000 0000 0000 0000 0000)
#define BIT_22 0x00400000 // (0000 0000 0100 0000 0000 0000 0000 0000)
#define BIT_23 0x00800000 // (0000 0000 1000 0000 0000 0000 0000 0000)
#define BIT_24 0x01000000 // (0000 0001 0000 0000 0000 0000 0000 0000)
#define BIT_25 0x02000000 // (0000 0010 0000 0000 0000 0000 0000 0000)
#define BIT_26 0x04000000 // (0000 0100 0000 0000 0000 0000 0000 0000)
#define BIT_27 0x08000000 // (0000 1000 0000 0000 0000 0000 0000 0000)
#define BIT_28 0x10000000 // (0001 0000 0000 0000 0000 0000 0000 0000)
#define BIT_29 0x20000000 // (0010 0000 0000 0000 0000 0000 0000 0000)
#define BIT_30 0x40000000 // (0100 0000 0000 0000 0000 0000 0000 0000)
#define BIT_31 0x80000000 // (1000 0000 0000 0000 0000 0000 0000 0000)
/* double word */
/* set a bit */
#define SET_BIT(a,b) a = a | b;
/* clear a bit */
#define CLEAR_BIT(a,b) a = a ^ b;
/* test if bit is set */
#define BIT_SET(a,b) a & b
/* define mask type */
typedef unsigned long mask_t;
/* lookup table */
extern mask_t bitmask_lookup_tbl[32];
#endif
I use the code as follows (just an example):
Code: Select all
unsigned long flags;
SET_BIT(flags, BIT_7);
SET_BIT(flags, BIT_8);
if(BIT_SET(flags, BIT_7)
{
CLEAR_BIT(flags, BIT_8);
}
I've tested it and it works but is it correct? I mean is this the fastest way?
edit:
When I try:
It fails, I'm sure that the bits are zero. But still it returns 1
Posted: Wed Aug 16, 2006 9:28 am
by matthias
Solved the BIT_SET:
Code: Select all
#define BIT_SET(a,b) ((a & b) > 0)
But still I wonna know if my xor method is correct
Posted: Wed Aug 16, 2006 9:57 am
by spix
Code: Select all
/* clear a bit */
#define CLEAR_BIT(a,b) a = a ^ b;
I would use :
Code: Select all
#define CLEAR_BIT(a,b) (a &= ~(b))
[/code]
Posted: Wed Aug 16, 2006 10:02 am
by Mikae
I think, the best variant is something like this:
Code: Select all
#define CLEAR_BIT(a, b) (a &= ~(b))
without semicolon in the end.
Posted: Wed Aug 16, 2006 10:17 am
by gaf
XOR is defined as "(X AND NOT(Y)) OR (NOT(X) AND Y)":
Code: Select all
X | Y | result
-----|-----|----------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Your macro CLEAR_BIT(X, Y) takes two parameters: The first is the value that shall be changed, and the second is a bitmask that defines the bits to be cleared. Y is thus always one, while the value of X is unknown. If you now have a look at the table I posted above, you can see that the outcome of the operation can be either zero (when the bit is actually set in X) or one (if you attempt to clear a bit that is not set in X). As you often don't know whether the bit you want to clear is actually set, it would be much more convenient to have a function that works regardless of the state of X.
In theory you could replace the XOR (^) instruction with the somewhat more complex expression I gave above. The left side of the expression (up to the OR) defines the 3rd case listed in the table, while the right part is the second case. As you don't want CLEAR_BIT() to actually set a bit if it's already zero in X, you simply remove the right side of the expression. What remains is "X AND NOT(X)", which never happends as X is always set.
Code: Select all
#define CLEAR_BIT(a, b) a = a & (~b);
The tilde (~) negates b so that all ones become zeroes, and all zeroes become ones. The result is then taken to reset the bit in A. As only the bit that has originally been one is no longer set after the negation, the correct bit gets cleared.
regards,
gaf
Re: Is my code OK??
Posted: Wed Aug 16, 2006 10:25 am
by gaf
matthias wrote:if(!BIT_SET(flags, BIT_8));
It fails, I'm sure that the bits are zero. But still it returns 1
After the preprocessor resolves that directive the resulting code is "if(!a & b)". As the !-operator has a higher priority than &-operator, the expression is not interpreted the way you inteded. It should actually be enought to just add some brackets - the "> 0" shouldn't be necessary.
cheers,
gaf
Re: Is my code OK??
Posted: Wed Aug 16, 2006 11:17 am
by rexlunae
gaf wrote:matthias wrote:if(!BIT_SET(flags, BIT_8));
It fails, I'm sure that the bits are zero. But still it returns 1
After the preprocessor resolves that directive the resulting code is "if(!a & b)". As the !-operator has a higher priority than &-operator, the expression is not interpreted the way you inteded. It should actually be enought to just add some brackets - the "> 0" shouldn't be necessary.
cheers,
gaf
Yup. I just wanted to add that you should probably do the same for all of these macros, because they could all have similar problems. Also, it would probably be wise to add parens around the parameters to the macro itself to avoid the potential for internal precedence problems.
Example:
Code: Select all
#define SET_BIT(a,b) ((a) = (a) | (b));
Although, to be honest, I think these sorts of macros only serve to obfusticate code.
Posted: Wed Aug 16, 2006 12:23 pm
by matthias
gaf wrote:XOR is defined as "(X AND NOT(Y)) OR (NOT(X) AND Y)":
Code: Select all
X | Y | result
-----|-----|----------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Your macro CLEAR_BIT(X, Y) takes two parameters: The first is the value that shall be changed, and the second is a bitmask that defines the bits to be cleared. Y is thus always one, while the value of X is unknown. If you now have a look at the table I posted above, you can see that the outcome of the operation can be either zero (when the bit is actually set in X) or one (if you attempt to clear a bit that is not set in X). As you often don't know whether the bit you want to clear is actually set, it would be much more convenient to have a function that works regardless of the state of X.
In theory you could replace the XOR (^) instruction with the somewhat more complex expression I gave above. The left side of the expression (up to the OR) defines the 3rd case listed in the table, while the right part is the second case. As you don't want CLEAR_BIT() to actually set a bit if it's already zero in X, you simply remove the right side of the expression. What remains is "X AND NOT(X)", which never happends as X is always set.
Code: Select all
#define CLEAR_BIT(a, b) a = a & (~b);
The tilde (~) negates b so that all ones become zeroes, and all zeroes become ones. The result is then taken to reset the bit in A. As only the bit that has originally been one is no longer set after the negation, the correct bit gets cleared.
regards,
gaf
xor isn't a problem in my code becaus I always have to chek if the bit is set in my usage
So I'll keep on using the xor method. Though I would like to thank you for your advice
But I have one further question. Nowadays I use a lookup table to set a certain bit which is given by a variable x. Then I do table[x] and I have the value to do a |= b with. But I also found an option of shifting bits like:
Code: Select all
lookup:
SET_BIT(flags, lookup[x];
shift:
SET_BIT(flags, 1 << x);
I think the bit shifting method is faster (no adding or multiplying, you get a direct result) or am I missing somethin' here? I'm trying to get the most effeciency out of my C code.
(1 << 1) = 0000000000000010.
(1 << 2) = 0000000000000100.
(1 << 3) = 0000000000001000.
Posted: Wed Aug 16, 2006 12:53 pm
by gaf
xor isn't a problem in my code becaus I always have to chek if the bit is set in my usage
I don't know what exactly you're planning to do, but normally it should be much faster to not use XOR here. As the other method does not require the value to be checked in advance an expensive if() construction can be avoided. Even if you have to check the value anyway I would guess, that it's normally not any faster to use XOR. Keep in mind that it's a much more complex instruction compared to NOT or AND..
I think the bit shifting method is faster (no adding or multiplying, you get a direct result) or am I missing somethin' here? I'm trying to get the most effeciency out of my C code.
Bitshifting is definitly faster than your table lock-up methode as it doesn't require any memory access. Provided that X is a constant value (which it will be most of the time) the compiler/optimizer can even resolve the expression at compile-time. Your binary will then use a direct number, so that no calculations at all are needed at run-time.
regards,
gaf
Posted: Wed Aug 16, 2006 3:08 pm
by matthias
gaf wrote:xor isn't a problem in my code becaus I always have to chek if the bit is set in my usage
I don't know what exactly you're planning to do, but normally it should be much faster to not use XOR here. As the other method does not require the value to be checked in advance an expensive if() construction can be avoided. Even if you have to check the value anyway I would guess, that it's normally not any faster to use XOR. Keep in mind that it's a much more complex instruction compared to NOT or AND..
I think the bit shifting method is faster (no adding or multiplying, you get a direct result) or am I missing somethin' here? I'm trying to get the most effeciency out of my C code.
Bitshifting is definitly faster than your table lock-up methode as it doesn't require any memory access. Provided that X is a constant value (which it will be most of the time) the compiler/optimizer can even resolve the expression at compile-time. Your binary will then use a direct number, so that no calculations at all are needed at run-time.
regards,
gaf
I'm writing a memory manager. But still I have to chek the bit before testing, because I want to know when debugging if I'm freeing a page that doesn't excist
In the final code I will scratch it of my kernel.
Well I do the bit shifting with a variable x
so it has got to be calculated at runtime, since x holds a page number (very variable), well actually it is not (combo of x & y) but let's keep it easy
Now after this I tested my code using a lookup table and a bit shifting method. Results where rather funny. I recorded the tick count before 77 page allocations and after. Then I calculated the difference. For testing I used Microsoft Virtual PC. All conditions for the test are the same, no exceptions made. Here are my results:
Code: Select all
/* bit shifting */
loop1: 31 (clockticks)
loop2: 27
loop3: 29
loop4: 28
loop5: 29
loop6: 28
loop7: 29
loop8: 30
average: 28.875 clockticks 0.0375 miliseconds/allocation
/* lookup */
loop1: 29
loop2: 28
loop3: 28
loop4: 27
loop5: 28
loop6: 28
loop7: 30
loop8: 30
average: 28.5 clockticks 0.037 milisecond/allocation
Looks like a lookup table is faster, but I don't agree since bit shifting returns a very variable amount of clockticks. I think MSVPC is the cause of this, because it's in general not stable at all. The difference is small, but should I choose bit shifting or lookup table method?? Or should I test this at a real machine first??
btw, then this will be a good method to change a bit into the opposite right??
Code: Select all
/* if bit is 0, result is 1 -- if bit is 1, result is 0 */
#define CHANGE_BIT(a,b) a ^= b;
Posted: Thu Aug 17, 2006 6:12 am
by gaf
Now after this I tested my code using a lookup table and a bit shifting method. Results where rather funny. (snip) Should I test this at a real machine first??
Definitly. Emulators in general only mimic the functionality of the code and not its performance. They use a very simplified model of the CPU that does not account for all the details that decide about the code's run-time behaviour in real-life. If you really have to run a benchmark, you should do it on several real computers to get reliable results. As processor models often use different architectures, the results will be somewhat different on each machine: Nevertheless the bit-shifting approach should always be considerable faster.
You do keep in mind that this is actually only a very small detail ? The performance of your OS depends much more on the efficiency of the algorithms used, than on such low-level optimizations..
Then this will be a good method to change a bit into the opposite right??
That should do the job, although you actually hardly ever have to invert a bit..
regards,
gaf
Posted: Thu Aug 17, 2006 6:41 am
by matthias
Thanks all, especially gaf
I'll just go for bit shifting
My defentive code:
Code: Select all
/* set a bit */
#define SET_BIT(a,b) a |= b;
/* set a bit accoring to position n */
#define SET_BIT_N(a,n) a |= (1 << n)
/* clear a bit */
#define CLEAR_BIT(a,b) a &= ~b;
/* clear a bit accoring to position n */
#define CLEAR_BIT_N(a,n) a &= ~(1 << n)
/* test if bit is set */
#define BIT_SET(a,b) (a & b)
/* test if bit with index n is set */
#define BIT_SET_N(a,n) (a & (1 << n))
/* if bit is 0, result is 1 -- if bit is 1, result is 0 */
#define CHANGE_BIT(a,b) a ^= b;
/* same as above, only we determine mask by bit shifting n */
#define CHANGE_BIT_N(a,n) a ^= (1 << n)
/* functions with *_N are for variable bits, n is index */
/* normal functions are for setting bits using the defined BIT_X masks */