Lolling at programmers, how many ways are there to create a bitmask ? ;) :)
in [ASM]
|
From: Skybuck Flying on 27 May 2010 02:14 "James Harris" <james.harris.1(a)googlemail.com> wrote in message news:b729c66a-2657-45d8-a31b-4eca0b3dd3d5(a)e28g2000vbd.googlegroups.com... 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. " All four options require typecasting to the correct type in Delphi to surpress "range checking and overflow checking (warnings/exceptions)". So ultimately all methods will need to be adepted to their use... When looking at it from that perspective perhaps the "constant" versions are a bit more clear as to what the new typecast should be... Maybe the typecast and the constants would make it clear to any viewing programmer that they belong together... Then again perhaps not ;) :) and then the other two "auto" options would be better... but if the programmer would fail to add the correct typecasts, then those would fail as well. All would/will probably fail if typecast is not correctly modified, however the constant versions require an additional modifcation. Therefore the constants versions require additional work/effort to adept them to new situations... Thus from a time/programming efficiency view the "auto" versions would be easier to use/require less time/less fiddling around with it ;) Though maybe that's not completely true... because option 2 the minus -1 version is actually harder to understand... and could actually lead to a misunderstandig if the parenthesis weren't there... It could be read by the programmer with the wrong precedence in mind for example : 1 shl (BitCount-1) which would be wrong. This problem is definetly not present with option 1 and option 3. Though option 3 is probably also harder to understand because of hexadecimals and especially the xor, which requires having the xor-table in mind and working it out. My constant version also requires recgonizing the constant value as being "max word"... something I can do but maybe not a newby programmer. Option 4 which uses "not 0" is also interesting... would a newby understand it ? Perhaps not because it could also be written without the parenthesis as follows: not word(not 0 shl BitCount); Since not has a higher precedence in pascal at least then shl it's open to interpretation by those not skilled in the precedence of operators. It could also lead to translating issue's to other languages with different "operator precedence". Again the constant versions do not have this problem. Option 3 is actually the most interesting when it comes to the parenthesis... it probably doesn't need them at all: It could be written as: Mask := $FFFF shl BitCount xor $FFFF; And it would still be correct, shl has a higher precedence than xor in pascal... Therefore option 3 seems most "idiot-proof" :) Option 2 seems to be the worst for or-ing with something else for example: mLongword := mLongword or ( (1 shl mBitCount) - 1 ); ^ This creates a range checking exception in Delphi, while the rest will function happily for longwords... probably just Delphi specific but still... Hmmm... maybe it's better if it produces a range check error early on... though the others seem stable with requiring a typecast but that could change in the future if the delphi compiler is enhanced... I think option 2, the minus -1 is a bit deceptive... it's easy to remember, but also easy to miss-remember and get wrong probably. The xor is a bit strange and not very intuitive. Option 4 is a bit strange as well because it had two not's in it which is kinda hard to understand... like what the hell is it doing ? I shall introduce a new variant, version 5: mLongword := mLongword or ( not (MaxLongword shl BitCount) ); This is not cool... because I don't know the value of max longword out of my head... so that would require a calculator... at least if I wanted to write it in decimal... I actually did not want to do that... I wanted to do it in hexadecimal so here goes again: version 6: mLongword := mLongword or ( not ($FFFFFFFF shl mBitCount) ); I think this one is best for now. It also doesn't require a typecast which is nice ! ;) :) So I guess we didn't have all versions yet after all ! ;) :) slight variations ofcourse... but this slight variation does matter for me ! ;) :) So for now I will use version 6. Bye, Skybuck.
From: Skybuck Flying on 27 May 2010 02:30 "Skybuck Flying" <IntoTheFuture(a)hotmail.com> wrote in message news:471bb$4bfe0fea$54190f09$3689(a)cache4.tilbu1.nb.home.nl... > > "Skybuck Flying" <IntoTheFuture(a)hotmail.com> wrote in message > news:26b1a$4bfe0dd9$54190f09$2585(a)cache4.tilbu1.nb.home.nl... >> >> "James Harris" <james.harris.1(a)googlemail.com> wrote in message >> news:b729c66a-2657-45d8-a31b-4eca0b3dd3d5(a)e28g2000vbd.googlegroups.com... >> 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. >> " >> >> All four options require typecasting to the correct type in Delphi to >> surpress "range checking and overflow checking (warnings/exceptions)". >> >> So ultimately all methods will need to be adepted to their use... >> >> When looking at it from that perspective perhaps the "constant" versions >> are a bit more clear as to what the new typecast should be... >> >> Maybe the typecast and the constants would make it clear to any viewing >> programmer that they belong together... >> >> Then again perhaps not ;) :) and then the other two "auto" options would >> be better... but if the programmer would fail to add the correct >> typecasts, then those would fail as well. >> >> All would/will probably fail if typecast is not correctly modified, >> however the constant versions require an additional modifcation. >> >> Therefore the constants versions require additional work/effort to adept >> them to new situations... >> >> Thus from a time/programming efficiency view the "auto" versions would be >> easier to use/require less time/less fiddling around with it ;) >> >> Though maybe that's not completely true... because option 2 the minus -1 >> version is actually harder to understand... and could actually lead to a >> misunderstandig if the parenthesis weren't there... >> >> It could be read by the programmer with the wrong precedence in mind for >> example : 1 shl (BitCount-1) which would be wrong. >> >> This problem is definetly not present with option 1 and option 3. >> >> Though option 3 is probably also harder to understand because of >> hexadecimals and especially the xor, which requires having the xor-table >> in mind and working it out. >> >> My constant version also requires recgonizing the constant value as being >> "max word"... something I can do but maybe not a newby programmer. >> >> Option 4 which uses "not 0" is also interesting... would a newby >> understand it ? >> >> Perhaps not because it could also be written without the parenthesis as >> follows: >> >> not word(not 0 shl BitCount); >> >> Since not has a higher precedence in pascal at least then shl it's open >> to interpretation by those not skilled in the precedence of operators. >> >> It could also lead to translating issue's to other languages with >> different "operator precedence". >> >> Again the constant versions do not have this problem. >> >> Option 3 is actually the most interesting when it comes to the >> parenthesis... it probably doesn't need them at all: >> >> It could be written as: >> >> Mask := $FFFF shl BitCount xor $FFFF; >> >> And it would still be correct, shl has a higher precedence than xor in >> pascal... >> >> Therefore option 3 seems most "idiot-proof" :) >> >> Option 2 seems to be the worst for or-ing with something else for >> example: >> >> mLongword := >> mLongword or >> ( >> (1 shl mBitCount) - 1 >> ); >> >> ^ This creates a range checking exception in Delphi, while the rest will >> function happily for longwords... probably just Delphi specific but >> still... >> >> Hmmm... maybe it's better if it produces a range check error early on... >> though the others seem stable with requiring a typecast but that could >> change in the future if the delphi compiler is enhanced... >> >> I think option 2, the minus -1 is a bit deceptive... it's easy to >> remember, but also easy to miss-remember and get wrong probably. >> >> The xor is a bit strange and not very intuitive. >> >> Option 4 is a bit strange as well because it had two not's in it which is >> kinda hard to understand... like what the hell is it doing ? >> >> I shall introduce a new variant, version 5: >> >> mLongword := >> mLongword or ( not (MaxLongword shl BitCount) ); >> >> This is not cool... because I don't know the value of max longword out of >> my head... so that would require a calculator... at least if I wanted to >> write >> it in decimal... I actually did not want to do that... I wanted to do it >> in hexadecimal so here goes again: >> >> version 6: >> >> mLongword := >> mLongword or ( not ($FFFFFFFF shl mBitCount) ); >> >> I think this one is best for now. It also doesn't require a typecast >> which is nice ! ;) :) >> >> So I guess we didn't have all versions yet after all ! ;) :) slight >> variations ofcourse... but this slight variation does matter for me ! ;) >> :) >> >> So for now I will use version 6. > Version 6 "un-notted" is also better because it might allow to spot > optimizations as follows: Hmm I don't need an "un-notted" version I think.. so maybe this was a little mistake during the conversion or testing or something ;) So consider it (the unnotted version) destroyed again =D But version 6 "notted" remains ! ;) :) Bye, Skybuck ;) :)
From: Skybuck Flying on 27 May 2010 02:42 "Seebs" <usenet-nospam(a)seebs.net> wrote in message news:slrnhvrj4m.4f0.usenet-nospam(a)guild.seebs.net... > On 2010-05-27, Skybuck Flying <IntoTheFuture(a)hotmail.com> wrote: >> Question is what happens when "shl 32" is done. > > *sigh* > >> According to the intel manual the result would be undefined ?!? > > Yes. > >> Does that mean the result could be garbage ??? > > Tell you what. Try posting this coherently with a reasonable amount of > punctuation, and I'll totally point out that the word "undefined" is > completely unambiguous, since apparently this is not obvious enough. So "shr 32" and "shl 32" could result in garbarge ?! That is pretty shitty ! Suppose one wants to write a longword to some bit stream then bitcount would always be 32 ! And thus this code has the potential to screw up ?! :(( Not good, definetly not good. The "lookup-table" option is starting to look pretty good right now ! ;) :) Bye, Skybuck.
From: Skybuck Flying on 27 May 2010 03:05 Because of this I will introduce new methods/versions/options, here goes: version 7: ShiftedMask := 1 * ShiftLeftMaskLookupTable[BitCount]; ShiftedContent := Content * ShiftLeftContentLookupTable[BitCount]; Initializing lookup tables: ShiftLeftMaskLookUpTable[0] := 0; vMask := 1; for BitCount := 1 to 32 do begin ShiftLeftMaskLookUpTable[BitCount] := vMask; vMask := vMask shl 1; end; ShiftLeftContentLookupTable[0] := 0; vMultiply := 1; for BitCount := 1 to 32 do begin ShiftLeftContentLookupTable[BitCount] := vMultiply; vMultiply := vMultiply * 2; end; Untested but this should do/work conceptually. The muls themselfes are a bit slower... but at least it doesn't require branching... I could also implement each method seperately like: if BitCount < 32 then begin Method1 end else begin Method2 end; This would get nasty though... lot's of code... However another idea could be to maybe do two shift lefts somehow ? Perhaps as follows: version 8: ($FFFFFFFF shl (BitCount and (1+2+4+8+16))) shl ((BitCount shr (1+1+1+1+1))and 1) This would do an extra shift if necessary... since shr 0 and shl 0 will work perfectly... this should work. That's 3 extra instructions to correct the shitty intel mistake ! ;) :) Though they might have had their reasons to limit it to 5 bits instead of 6 ;) Or maybe not and it was just sloppy :) Anyway... the question is now what to use... the mul + lookup table method... Or these 5 instructions ? it's getting close to the mul speed me thinks... One adventage of the mul method is that it might be shorter and thus take up less instruction cache. Another adventage of the mul method is that it could work for "simulated 64 bit integers" as well. The shift method would fail ? Cannot shift 64 bitcount ? However maybe the code can be changed to this to make 64 bit work as well: ($FFFFFFFF shl (BitCount and (1+2+4+8+16))) shl (BitCount shr (1+1+1+1+1)) Since the bit count shouldn't have any garbage bits the "and 1" is not necessary... and thus it can just shr the bit count by 5 bits... to start processing the next 5 bits or so... So I guess this could solve the problem ! :) Now me needs to go test it ! ;) :) Bye, Skybuck.
From: Skybuck Flying on 27 May 2010 03:23
Ok, I tried a couple of things... and it turns out Delphi actually has a "simulated shift left 64 bitcount support" wow ! ;) :) But first I tried to implement it myself in Delphi-code : This seemed to fail miserably, possibly because of shitty Delphi ?!? ;) // 64 bitcount shift left support: // doesn't work it seems. mNewContent := ( mContent shl ( mBitCount and (1+2+4+8+16) ) ) shl ( ( mBitCount shr (1+1+1+1+1) ) and (1+2+4+8+16) ); The funny thing is that this is probably not needed at all, by just using an int64 it could be done as follows: int64's: mNewContent := mContent shl BitCount; The following routine would probably be called by Delphi: @_llshl: 00404D38 80F920 cmp cl,$20 00404D3B 7C11 jl $00404d4e 00404D3D 80F940 cmp cl,$40 00404D40 7C05 jl $00404d47 00404D42 31D2 xor edx,edx 00404D44 31C0 xor eax,eax 00404D46 C3 ret 00404D47 89C2 mov edx,eax 00404D49 D3E2 shl edx,cl 00404D4B 31C0 xor eax,eax 00404D4D C3 ret 00404D4E 0FA5C2 shld edx,eax,cl 00404D51 D3E0 shl eax,cl 00404D53 C3 ret So this would mean 6 instructions for just the call setup and storing the results in memory: TestProgram.dpr.33: mNewContent := mContent shl mBitCount; 00408DF6 8B45F8 mov eax,[ebp-$08] 00408DF9 8B55FC mov edx,[ebp-$04] 00408DFC 8BCB mov ecx,ebx 00408DFE E835BFFFFF call @_llshl 00408E03 8945F0 mov [ebp-$10],eax 00408E06 8955F4 mov [ebp-$0c],edx Plus the one or two branches above plus 3 to 4 instructions... So that's a total of 12 instructions or so... for worst case... It used to be 4 to 5... so now it's double that... but all in all not to bad. However the funny thing is that the problem is still not fully solved. I would bet that shl 64 could still give problems ? I am not sure though ;) Bye, Skybuck. |