Is my code OK??

[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:

Code: Select all

if(!BIT_SET(flags, BIT_8));

It fails, I'm sure that the bits are zero. But still it returns 1

[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

[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]

[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.

[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

[gaf]

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.

Code: Select all

#define BIT_SET(a,b)   (a & b )

cheers,
gaf

[rexlunae]

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.

Code: Select all

#define BIT_SET(a,b)   (a & b )

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.

[matthias]

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.

[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

[matthias]

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

Code: Select all

Bitmap[y] |= (1 << 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;

[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

[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 */