Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Lolling at programmers, how many ways are there to create a bitmask ? ;) :)

Reply
Thread Tools

Lolling at programmers, how many ways are there to create a bitmask ? ;) :)

 
 
Skybuck Flying
Guest
Posts: n/a
 
      05-24-2010
Ok people,

I keep coming across different ways in source codes for creating a bit mask
for a certain ammount of bits and it's kinda funnieing me out ! =D

Therefore to have some fun, it's time to create a thread dedicated to
creating bitmasks... how many ways are there ?

So far I have come across these methods:

1. (My own way Mask := not word(65535 shl BitCount); // not 1111000 =
0000111

2. Mask := (1 shl BitCount)-1; // 10000-1 = 09999 = 01111

3. Mask := ($FFFF shl BitCount) xor $FFFF; // 1111000 xor 1111111 = 0000111

I also wonder which one would be fastest, since processors might execute
instructions in different alu's en such...
Maybe processors have special "boolean/logic" units and "arithmetic units".

To what category would shl belong ? (Maybe "bit logic unit" ?)

Anyway if you know any other way of calculating such bitmasks please add
them to this thread for the fun of it ! =D

Bye,
Skybuck =D








 
Reply With Quote
 
 
 
 
alanglloyd@aol.com
Guest
Posts: n/a
 
      05-24-2010
If you're dealing with meaningful bits then use a set of an enumerated
value.

type
TBitFlags = (bfBit0, bfBit1, bfBit2, bfBit3,
bfBit4, bfBit5, bfBit6, bfBit7);
TBitFlagSet = set of TBitFlags;


const
BitMask : TBitFlagSet = [bfBit0..bfBit3];
AllBits : TBitFlagSet = [bfBit0..bfBit7];
TwoBits : TBitFlagSet = [bfBit2, bfBit5];

You can give your TBitFlags definition meaningful names and get
clarity in your code.

Alan Lloyd
 
Reply With Quote
 
 
 
 
Skybuck Flying
Guest
Posts: n/a
 
      05-24-2010
Sets in pascal are easy to use but they are very slow.

Bye,
Skybuck.


 
Reply With Quote
 
James Harris
Guest
Posts: n/a
 
      05-25-2010
On 24 May, 17:23, "Skybuck Flying" <(E-Mail Removed)> wrote:
> Ok people,
>
> I keep coming across different ways in source codes for creating a bit mask
> for a certain ammount of bits and it's kinda funnieing me out ! =D
>
> Therefore to have some fun, it's time to create a thread dedicated to
> creating bitmasks... how many ways are there ?
>
> So far I have come across these methods:
>
> 1. (My own way * Mask := not word(65535 shl BitCount); *// not 1111000 =
> 0000111
>
> 2. Mask := (1 shl BitCount)-1; *// 10000-1 = 09999 = 01111
>
> 3. Mask := ($FFFF shl BitCount) xor $FFFF; // 1111000 xor 1111111 = 0000111
>
> I also wonder which one would be fastest, since processors might execute
> instructions in different alu's en such...
> Maybe processors have special "boolean/logic" units and "arithmetic units".


"Bitmasks" are just bit patterns used in bitwise logic such as 0b1100.
You mean masks for the lowest N bits of a value, i.e. a specific type
of bitmask.

Your option 2 is very good! As well as being fast it works regardless
of word size, something the other two fail to do.

As for speed, any of these should be much faster than many
alternatives since they use only simple operations which any self-
respecting CPU will have in its armoury. Your option 2 should compile
on x86-32 to something like

mov eax, 1
shl eax, cl
dec eax

Note there's no range checking on the number of bits to shift (in the
cl register). IIRC if too many are specified the processor will mask
the value keeping just the lower five bits rather than maxing it out.
For example, if you specified a shift of 63 (0b0011_1111) it would
shift 31 (0b0001_1111) places. If that's not what's wanted a test for
range would be needed. This also applies to options 1 and 3 and all
solutions where a shift is required if that shift amount is not a
constant.

BTW, your options 1 and 3 are basically the same as each other. An xor
with a mask of all 1s has the same effect as a not operation. Assuming
32-bit arithmetic, not your 16-bit, they should become something like

mov eax, -1
shl eax, cl
not eax

A word about the limits of these code fragments. It looks like both
pieces of code will work with a shift amount in the range 0 to 31.
Anything 32 or above (which is not to be masked) would need a little
bit of extra code.

The object code for your option 2 should be a little bit shorter than
code for the other two.

James
 
Reply With Quote
 
Skybuck Flying
Guest
Posts: n/a
 
      05-25-2010
Cool and handy too ! =D, I shall add this method of yours as number 4.

1. (Skybuck) Mask := not word(65535 shl BitCount); // not 1111000 =
0000111

2. (Michael Vinther) Mask := (1 shl BitCount)-1; // 10000-1 = 09999 = 01111


3. (Skamradt) (Mask := ($FFFF shl BitCount) xor $FFFF; // 1111000 xor
1111111 = 0000111

4. (MitchAlsup) Mask := not word((not 0) shl BitCount); // not((not 0 =
1111111) shl 3 = 1111000) = 0000111

So far it seems method 2 is the best/shortest at least in Delphi 2007
compiler.
Method 2 works well for functions and inlining as well, some of the others
seem to become bigger when inlined ?!?
(Actual speed is yet to be determined )

It could be interesting to see how a C compiler compiles it...

For now here is the Delphi 2007 test program, and the assemblies of inlined
vs non-inlined:

// *** Begin of Test Program ***

program TestProgram;

{$APPTYPE CONSOLE}

{

TestProgram to test and analyze calculation for BitMasks.

version 0.01 created on 25 may 2010 by Skybuck Flying.

When the functions are not inlined all versions use 5 instructions.
(including the return).

However when inline directive happens something interesting happens.

Some versions will be 4 instructions and some 5 some maybe even more.

I guess it depends on how the Delphi 2007 compiler inlines it... ?!?

Re-ordering the code didn't really help...

Mask2MichaelVinther seems to be the best one so far,

Shortest in both modes, uses the least ammount of "instruction bytes".

Actual speed is yet to be determined !

}

uses
SysUtils;

function Mask1Skybuck( ParaBitCount : byte ) : word; inline;
begin
result := not word(65535 shl ParaBitCount);
end;

function Mask2MichaelVinther( ParaBitCount : byte ) : word; inline;
begin
result := (1 shl ParaBitCount)-1;
end;

function Mask3Skamradt( ParaBitCount : byte ) : word; inline;
begin
result := word($FFFF shl ParaBitCount) xor $FFFF;
end;

function Mask4MitchAlsup( ParaBitCount : byte ) : word; inline;
begin
result := not word((not 0) shl ParaBitCount);
end;

procedure Main;
var
vMask : word;
vBitCount : word;
begin
vBitCount := 16;

vMask := Mask1Skybuck( vBitCount );
writeln( vMask );

vMask := Mask2MichaelVinther( vBitCount );
writeln( vMask );

vMask := Mask3Skamradt( vBitCount );
writeln( vMask );

vMask := Mask4MitchAlsup( vBitCount );
writeln( vMask );
end;

begin
try
{ TODO -oUser -cConsole Main : Insert code here }
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
ReadLn;
end.


{
Inlined version:

TestProgram.dpr.51: begin
00408E44 53 push ebx
00408E45 56 push esi
00408E46 57 push edi
TestProgram.dpr.52: vBitCount := 16;
00408E47 66BE1000 mov si,$0010
TestProgram.dpr.54: vMask := Mask1Skybuck( vBitCount );
00408E4B 8BDE mov ebx,esi
00408E4D 8BCB mov ecx,ebx
00408E4F 66BFFFFF mov di,$ffff
00408E53 66D3E7 shl di,cl
00408E56 66F7D7 not di
TestProgram.dpr.55: writeln( vMask );
00408E59 0FB7D7 movzx edx,di
00408E5C A1F0A94000 mov eax,[$0040a9f0]
00408E61 E8CEA8FFFF call @Write0Long
00408E66 E801A9FFFF call @WriteLn
00408E6B E86C9FFFFF call @_IOTest
TestProgram.dpr.57: vMask := Mask2MichaelVinther( vBitCount );
00408E70 8BCB mov ecx,ebx
00408E72 66BF0100 mov di,$0001
00408E76 66D3E7 shl di,cl
00408E79 4F dec edi
TestProgram.dpr.58: writeln( vMask );
00408E7A 0FB7D7 movzx edx,di
00408E7D A1F0A94000 mov eax,[$0040a9f0]
00408E82 E8ADA8FFFF call @Write0Long
00408E87 E8E0A8FFFF call @WriteLn
00408E8C E84B9FFFFF call @_IOTest
TestProgram.dpr.60: vMask := Mask3Skamradt( vBitCount );
00408E91 8BCE mov ecx,esi
00408E93 66BFFFFF mov di,$ffff
00408E97 66D3E7 shl di,cl
00408E9A 6681F7FFFF xor di,$ffff
TestProgram.dpr.61: writeln( vMask );
00408E9F 0FB7D7 movzx edx,di
00408EA2 A1F0A94000 mov eax,[$0040a9f0]
00408EA7 E888A8FFFF call @Write0Long
00408EAC E8BBA8FFFF call @WriteLn
00408EB1 E8269FFFFF call @_IOTest
TestProgram.dpr.63: vMask := Mask4MitchAlsup( vBitCount );
00408EB6 8BCE mov ecx,esi
00408EB8 66BFFFFF mov di,$ffff
00408EBC 66D3E7 shl di,cl
00408EBF 66F7D7 not di
TestProgram.dpr.64: writeln( vMask );
00408EC2 0FB7D7 movzx edx,di
00408EC5 A1F0A94000 mov eax,[$0040a9f0]
00408ECA E865A8FFFF call @Write0Long
00408ECF E898A8FFFF call @WriteLn
00408ED4 E8039FFFFF call @_IOTest
TestProgram.dpr.65: end;
00408ED9 5F pop edi
00408EDA 5E pop esi
00408EDB 5B pop ebx
00408EDC C3 ret

}

{

Non-inlined/function version:

TestProgram.dpr.29: result := not word(65535 shl ParaBitCount);
00408E44 8BC8 mov ecx,eax
00408E46 66B8FFFF mov ax,$ffff
00408E4A 66D3E0 shl ax,cl
00408E4D 66F7D0 not ax
TestProgram.dpr.30: end;
00408E50 C3 ret
00408E51 8D4000 lea eax,[eax+$00] // ignored/filling
TestProgram.dpr.34: result := (1 shl ParaBitCount)-1;
00408E54 8BC8 mov ecx,eax
00408E56 66B80100 mov ax,$0001
00408E5A 66D3E0 shl ax,cl
00408E5D 48 dec eax
TestProgram.dpr.35: end;
00408E5E C3 ret
00408E5F 90 nop // ignored/filling
TestProgram.dpr.39: result := word($FFFF shl ParaBitCount) xor $FFFF;
00408E60 8BC8 mov ecx,eax
00408E62 66B8FFFF mov ax,$ffff
00408E66 66D3E0 shl ax,cl
00408E69 6635FFFF xor ax,$ffff
TestProgram.dpr.40: end;
00408E6D C3 ret
00408E6E 8BC0 mov eax,eax // ignored/filling
TestProgram.dpr.44: result := not word((not 0) shl ParaBitCount);
00408E70 8BC8 mov ecx,eax
00408E72 66B8FFFF mov ax,$ffff
00408E76 66D3E0 shl ax,cl
00408E79 66F7D0 not ax
TestProgram.dpr.45: end;
00408E7C C3 ret
00408E7D 8D4000 lea eax,[eax+$00]
TestProgram.dpr.51: begin
00408E80 53 push ebx
00408E81 56 push esi
00408E82 57 push edi
TestProgram.dpr.52: vBitCount := 16;
00408E83 66BE1000 mov si,$0010
TestProgram.dpr.54: vMask := Mask1Skybuck( vBitCount );
00408E87 8BDE mov ebx,esi
00408E89 8BC3 mov eax,ebx
00408E8B E8B4FFFFFF call Mask1Skybuck
00408E90 8BF8 mov edi,eax
TestProgram.dpr.55: writeln( vMask );
00408E92 0FB7D7 movzx edx,di
00408E95 A1F0A94000 mov eax,[$0040a9f0]
00408E9A E895A8FFFF call @Write0Long
00408E9F E8C8A8FFFF call @WriteLn
00408EA4 E8339FFFFF call @_IOTest
TestProgram.dpr.57: vMask := Mask2MichaelVinther( vBitCount );
00408EA9 8BC3 mov eax,ebx
00408EAB E8A4FFFFFF call Mask2MichaelVinther
00408EB0 8BF8 mov edi,eax
TestProgram.dpr.58: writeln( vMask );
00408EB2 0FB7D7 movzx edx,di
00408EB5 A1F0A94000 mov eax,[$0040a9f0]
00408EBA E875A8FFFF call @Write0Long
00408EBF E8A8A8FFFF call @WriteLn
00408EC4 E8139FFFFF call @_IOTest
TestProgram.dpr.60: vMask := Mask3Skamradt( vBitCount );
00408EC9 8BC3 mov eax,ebx
00408ECB E890FFFFFF call Mask3Skamradt
00408ED0 8BF8 mov edi,eax
TestProgram.dpr.61: writeln( vMask );
00408ED2 0FB7D7 movzx edx,di
00408ED5 A1F0A94000 mov eax,[$0040a9f0]
00408EDA E855A8FFFF call @Write0Long
00408EDF E888A8FFFF call @WriteLn
00408EE4 E8F39EFFFF call @_IOTest
TestProgram.dpr.63: vMask := Mask4MitchAlsup( vBitCount );
00408EE9 8BC3 mov eax,ebx
00408EEB E880FFFFFF call Mask4MitchAlsup
00408EF0 8BF8 mov edi,eax
TestProgram.dpr.64: writeln( vMask );
00408EF2 0FB7D7 movzx edx,di
00408EF5 A1F0A94000 mov eax,[$0040a9f0]
00408EFA E835A8FFFF call @Write0Long
00408EFF E868A8FFFF call @WriteLn
00408F04 E8D39EFFFF call @_IOTest
TestProgram.dpr.65: end;
00408F09 5F pop edi
00408F0A 5E pop esi
00408F0B 5B pop ebx
00408F0C C3 ret


}

// *** End of Test Program ***

Bye,
Skybuck.


 
Reply With Quote
 
Skybuck Flying
Guest
Posts: n/a
 
      05-25-2010
However Michael's Code is a bit dangerous because of the way Delphi compiles
it:

At first glance during testing apperently it doesn't require a "word"
typecast to make it safe:

function Mask2MichaelVinther( ParaBitCount : byte ) : word; inline;
begin
result := (1 shl ParaBitCount)-1;
end;

Carefully looking at this function makes it suspicious

1 shl 16 would become 0.

0 - 1 should trigger a range checking exception... but the exception never
occurs.

Even when range+overflow checking is on and inlining is off the code doesn't
trip:

It seems to be a Delphi 2007 compiler range/overflow checking bug not being
able to detect this scenerio:

"
TestProgram.dpr.40: result := (1 shl ParaBitCount)-1;
00408E4C 8BC8 mov ecx,eax
00408E4E B801000000 mov eax,$00000001
00408E53 D3E0 shl eax,cl
00408E55 83E801 sub eax,$01
00408E58 7105 jno $00408e5f
00408E5A E851ADFFFF call @IntOver
00408E5F 3DFFFF0000 cmp eax,$0000ffff // probably bug here... eax will
be $FFFF FFFF

Unable to determine from intel documentation what cmp and jbe do...
is it A <= B ? or B <= A ?

00408E64 7605 jbe $00408e6b
00408E66 E83DADFFFF call @BoundErr
TestProgram.dpr.41: end;
00408E6B C3 ret
"

Bye,
Skybuck.


 
Reply With Quote
 
Skybuck Flying
Guest
Posts: n/a
 
      05-25-2010
I tested it in Delphi 2010 as well... bug seems to be present there as well.

Same behaviour there... no range/underflow warnings/exceptions for method 2
for BitCount 16.

Bye,
Skybuck.


 
Reply With Quote
 
Skybuck Flying
Guest
Posts: n/a
 
      05-25-2010
The other methods have problems too ofcourse, that's why I added the "word"
typecasts... though when leaving out the "word" typecast not all problems
are detected by Delphi's range checking capabilities.

Therefore it's worth bitching about Delphi not being able to detect
problems:

> 1. (Skybuck) Mask := not word(65535 shl BitCount); // not 1111000 =
> 0000111


This method without the typecast should have raised an exception since 65535
is being shifted out and becomes to large for a word...

Therefore in 16 bit it will work but in 32 bit it will still bug out, a
typecast for longword will fix it again.

All methods have this problem, therefore all methods require a typecast to
be on the safe side if range/overflow checking is to be enabled.

>
> 2. (Michael Vinther) Mask := (1 shl BitCount)-1; // 10000-1 = 09999 =
> 01111
>
> 3. (Skamradt) (Mask := ($FFFF shl BitCount) xor $FFFF; // 1111000 xor
> 1111111 = 0000111
>
> 4. (MitchAlsup) Mask := not word((not 0) shl BitCount); // not((not 0 =
> 1111111) shl 3 = 1111000) = 0000111


Moral of the story:

Code designed will work in 16 bit in Delphi but would present problems in 32
bit.

The typecasts were added because I already had experience with 32 bit
problems/versions.

Bye,
Skybuck.


 
Reply With Quote
 
Skybuck Flying
Guest
Posts: n/a
 
      05-25-2010
Hmm kinda interesting... method 3 does bitch about the shl being to large...
in 16 bit version.

The other ones don't do that...

Apperently it all depends on what kind of assembler is generated by the
compiler

The method is almost similiar except for the xor...

Maybe the xor triggers a different way of assembling the code...

Or maybe it's just the code order... but I would place my bet on the xor
triggering something inside the compiler

Bye,
Skybuck.


 
Reply With Quote
 
Skybuck Flying
Guest
Posts: n/a
 
      05-25-2010
Wow when the bit count changes from 16 to 15 then suddenly my method starts
to trip range checking exceptions as well !

Totally funny ! =D

This is some fun code we have here ladies and gentlemen !

Bye,
Skybuck =D


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
The Hack of bitmask used as Predicate Parameters Xah Lee Java 0 04-23-2007 10:53 AM
Schema representation of a "bitmask" type? Andrey Brozhko XML 1 12-10-2004 05:12 PM
Bitmask & Graphics Question Rod Nibbe Java 2 10-26-2004 03:56 PM
Bitmask representation of integers =?iso-8859-9?Q?Tongu=E7?= Yumruk Python 3 10-08-2003 02:50 PM



Advertisments