Lolling at programmers, how many ways are there to create a bitmask ? ;) :)
in [ASM]
|
From: Skybuck Flying on 24 May 2010 12:23 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
From: alanglloyd on 24 May 2010 15:28 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
From: Skybuck Flying on 24 May 2010 19:10 Sets in pascal are easy to use but they are very slow. Bye, Skybuck.
From: James Harris on 24 May 2010 20:09 On 24 May, 17:23, "Skybuck Flying" <IntoTheFut...(a)hotmail.com> 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
From: Skybuck Flying on 25 May 2010 09:09
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. |