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

[Seebs]

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.

-s

 

[Skybuck Flying]

Question is what happens when "shl 32" is done.

According to the intel manual the result would be undefined ?!?

Does that mean the result could be garbage ???

Bye,
Skybuck.

 

[Skybuck Flying]

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.

 

[Skybuck Flying]

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

mLongword :=
mLongword or (($FFFFFFFF shl mBitCount) shl mBitShift);

Which might be optimized as follows:

mLongword :=
mLongword or ($FFFFFFFF shl (mBitCount + mBitShift));

This would be harder to see with the minus 1 version (option 2).

I am not sure if this is an actual optimization... time will tell.

Maybe somebody already knows or can tell ?

Anyway.. it does **** up the logic a little bit... from an algorithm
perspective it does a shiftleft first and then another shiftleft.

It just happens to be two shifts...

If the mask needs to be changed this second code version could **** up bad.

So for now I will use the double shl after all... just for clearity sakes...
"pre-mature optimization root-of-all-evil and all that !"

Unless it's a really good optimization ??

Bye,
Skybuck.

 

[Skybuck Flying]

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

 

[Skybuck Flying]

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.

 

[Skybuck Flying]

Except the lookup table option doesn't really solve it...

Since the shl and shr are to be used for non-masks as well...

Thus content longwords... which need to be shifted... so those have the same
problem.

A lookup table for that would be 16 GigaBytes big !

Ouch !

Shit, sucks, sigh.

I guess only option is to add a fricking branch to prevent the shifts from
happening that can become very messy if there are many shifts ?! (

Bye,
Skybuck.

 

[Skybuck Flying]

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.

 

[Skybuck Flying]

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.

 

[Skybuck Flying]

Ok,

I just checked it...

Content shl 64 will be executed by this branch !:

00404D42 31D2 xor edx,edx
00404D44 31C0 xor eax,eax
00404D46 C3 ret

^ The developers of Delphi just got some major love points from me ! =D

I think this will solve all of my problems for now !

Bye,
Skybuck =D

 

[Skybuck Flying]

Wow good thing I tested it...

Shifting "contents" has to be done slightly different than shifting "masks".

Content needs to be shifted as follows:

Content shl (mBitCount-1)

Proof: when bitcount is exactly 1 bit, no shift should happen this it should
be shift 0, thus minus -1.

However for the mask the opposite needs to be happen:

not ($FFFFFFFFetc shl mBitCount);

if the bitcount is 1 then the mask needs to shift up 1 place to make room
for a zero, which will then be converted to a 1.

That's kinda funny... little inconsistency here...

I wonder if the mask calculation can be slightly altered to make it more
consistent with the content...

Perhaps ($FFFFFFFF-1) might do the trick...

Then it could be written as:

not (($FFFFFFFF-1) shl (mBitCount-1))

This could be handy to "recycle" mBitCount-1 calculation by storing it in a
variable or so...

Hmmm...

Tricky stuff as usual

Bye,
Skybck =D

 

[Skybuck Flying]

Oh shit...

I am not thinking straight... it's way past my bedtime anyway... but ok...

This is fun stuff ! =D

The content doesn't need to be shifted by BitCount...

The content needs to be shifted by BitIndex... which is something totally
different and could be zero.

So now I am starting to mix things through one another again which ain't
good

Too funny =D

Gotta stay sharp !

Bye,
Skybuck.

 

[Skybuck Flying]

Oh my god !

I think Delphi just showed me the light/the solution/the way !!! =D

Another method WOOOOOWWW this just doesn't stop ever/never! OH YEAH gooooddd
stuff ! =D

Method 9:

Mask := not (-1 shl BitCount);

^^^ Awesomeness ^^^ ! =D

Now I go test it ! =D

Bye,
Skybuck =D

 

[Skybuck Flying]

Oh my god !

I think Delphi just showed me the light/the solution/the way !!! =D

Another method WOOOOOWWW this just doesn't stop ever/never! OH YEAH
gooooddd stuff ! =D

Method 9:

Mask := not (-1 shl BitCount);

^^^ Awesomeness ^^^ ! =D

Now I go test it ! =D

Hmm very nice... seems to work just nicely for 16 bits... also signed
integers tested, seems to work as well...

For unsigned version not even typecasts needed it seems...

The int64 version will probably work as well...

Pretty nice.

Bye,
Skybuck.

 

[Skybuck Flying]

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.

Yeah but maybe that documentation is old...

And maybe intel/amd have secretly fixed the problem by now ?!

Bye,
Skybuck.

 

[Skybuck Flying]

Hmm I just realized something, the algorithm I was using/working needs a
"cache" the size of the largest supported write method...

So if I were to add int64 support, the cache would need to be 64 bits big.

I just tested int64 support, and it's almost twice as slow.

I just tested TableLookUp support with 32 bits, and it's twice as fast as
the int64 method.

The int64 method actually becomes three times as slow in combination with
the lookup table method.

The interesting thing is that the LookUpTable method actually caught this
algorithm shortcoming because of access violation...

I totally looked over this algorithm shortcoming (not my algorthm to start
with, just an extension/modified version of it... made more flexible too).

So the lookup table has saved me from doing stupid things like trying to
make the internal cache 8 bits or 16 bits will trying to store 32 bits in it
! haha.

I was kinda curious though to smaller cache support... I could test it with
a new test program but I am not interested in it because I need at least 24
bits and
preferably 32 bit support.

32 bit will last a long time... it's 64 K x 64 K

So for now it looks like I will be going with 32 bit and lookup tables...
unless practice turns up different results... or unless I really wants 64
bit writes and reads... but for now I don't really need them... maybe I will
also make a general read/write which can write any ammount of bits/bytes...
though this algorithm
is starting to give me some doubts here and there.

The nice thing could be that in the future if true 64 bit computers arrive
with faster 64 bit operations, and true 64 bit compilers, maybe the code
would run
much faster, time will tell I am not holding my breath though

Bye,
Skybuck.

 

[Skybuck Flying]

The lookup table right now seems to be the best solution for 32 bit support.

This seems unthinkable !

Yesterday I saw some kid playing the piano, it was this song, it was
slightly playing through my head at the end of this
"research/design/development day"

"Lady Gaga - Paparazzi"

I guess this code is very delicate just like the song...

And I guess shl and shr is over/dead just like the Lady lol.

What's that I see over the horizon ? Hmmm I think it's a bunch of flying
lookups tables ! =D

Bye,
Skybuck.

 

[Seebs]

So "shr 32" and "shl 32" could result in garbarge ?!

On many systems.

That is pretty shitty !

No, it isn't. Don't do something incoherent.

Suppose one wants to write a longword to some bit stream then bitcount would
always be 32 !

I have no idea what you think you are talking about. There is no reason you
need to use shifts to write to a bitstream. Perhaps more importantly, what
on earth do you think you're shifting? If you have a 32-bit value, and you
shift it by 32, you have shifted ALL of the data out of it. Why bother?
If you're not going to be using any remaining bits at all, why are you
performing an operation?

And thus this code has the potential to screw up ?! (

If so, the code sucks.

-s

 

[Seebs]

The lookup table right now seems to be the best solution for 32 bit support.

I think at this point I'm plonking you. You're extremely verbose without
saying much of anything, you overuse exclamation marks, you're overly
exciteable, and apparently you don't have any clue how to frame a problem,
think about what you need, and develop a plan for approaching it. Maybe
you should consider decaf.

-s

 

[Keith Thompson]

I think at this point I'm plonking you. You're extremely verbose without
saying much of anything, you overuse exclamation marks, you're overly
exciteable, and apparently you don't have any clue how to frame a problem,
think about what you need, and develop a plan for approaching it. Maybe
you should consider decaf.

A quick look at Skybuck Flying's posting history in other newsgroups
might be illuminating.