Bitmasking in DSP Code

[Spogg]

This is going well Martin!

One of the trickiest things for me to grasp in the past was that after a single pass of a DSP “visit” floats can be left changed for the next “visit”. In this way the DSP code remembers the result of the previous visit and acts accordingly. Of course this seems simple and obvious now, otherwise we couldn’t have sample counters etc.

Another thing I found out early on is that some code needs to be executed in the correct order to function correctly. Again, from programming, this may seem obvious but the sequence of some steps seems more critical than others. For example, the order of Float naming doesn’t matter but it can be very critical at what point in the code you increment a counter.

Also I remember I was surprised to find that a streamout value is held until the next visit, so can actually be used in a calculation for the next visit. This was counter-intuitive to me because I tended to think of an output as done and gone once it’s been generated.

I’m looking forward to an explanation of using that HUGE number instead of the abs function.
Many thanks for taking the time to cover all this stuff.

Spogg

[martinvicanek]

Among the functions that FS code offers is the absolute value function abs(x). The implementation, however, is quite inefficient, and so some clever users in the early days came up with a workaround. To see how it works, we need to look at how float numbers are represented in FS according to the IEEE-754 standard, where the available 32 bits (per SSE channel) are used in the following manner:

IEEE-754 format: s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm

The first bit "s" is the sign bit, it is 1 for a negative number and 0 for a positive number. The following 8 bits encode the exponent, and the remaining 23 bits represent the mantissa. Together these 31 bits represent the number's magnitude. Hence taking the abs value amounts to setting the sign bit to zero and leaving the other 31 bits unchanged. This can be achieved by and-ing the number with the following bitmask

abs-bitmask = 0 11111111 11111111111111111111111

The trouble is that this bit pattern does not represent a valid float number (NaN), so it cannot be assigned directly. One way to generate the desired bitmask is to combine other, easier accessible bit patterns. The original "hack" uses the three floats expression 3.4e38 | 0.999999 | 0.1. If you write down the corresponding binary representations it becomes clear:

Code: Select all

decimal   binary
3.4e38    0 11111110 11111111100100110011110
0.999999  0 01111110 11111111111111111101111
0.1       0 01111011 10011001100110011001101

However, other combinations such as 1.9999999|2 or 16777215|1 work as well. Check out this IEEE-754 Floating Point Converter.
(Note: in assembly you can declare the bitmask directly as int abs = 2147483647).

So here is the abs code example:

Code: Select all

streamin in;
streamout absin;

float abs;

stage(0){
  abs = 16777215 | 1;
  }

stage(2){
  absin = abs & in;
  }

Mystery resolved

BTW there is a closely related hack for the sign function sgn(x). The idea is to isolate the sign with the help of the bitmask 10000000000000000000000000000000 and attatch it to the number 1. The sign bitmask is a float NaN so it has to be "assembled" from valid numbers. A suitable choice is -1&-2. Here is the sgn code:

Code: Select all

streamin in;
streamout sgnin;

float sgn;

stage(0){
  sgn = -1 & -2;
  }

stage(2){
  sgnin = 1 | (sgn & in);
  }

[tulamide]

Look at it this way: In the instruction

Code: Select all

z = b + (a - b)&(x > y);

the first term b is the "default" value whereas the second term (a - b) represents a correction in the case that the condition (x > y) is true. In prose you could say:

If nothing else then set z equal to b.
However, in the event that (x > y) replace it by a.
Do so by adding a and subtracting b.

Of course you can reverse the roles of a and b if you prefer a to be the "default":

Code: Select all

z = a + (b - a)&(x <= y);

Did it help?

Not really. Because my issue is not the equation itself. I did understand it already the first time you represented it. My problem is the steps from the first to the second equation. Let me use a picture.
The first humans that made fire used a flintstone. Today we use a lighter. Both share the same principle (creating sparks to ingite an inflammable matter like dry wool or shavings back then, or gas nowadays) and both get to the same result, namely a fire. But, the lighter does it way more efficient than the flintstone. What we are missing is the various steps in between, like the first tinder bags, the first fuse sets with fire striking iron, etc.
And my question is, how am I supposed to (or how do you) come up with all those intermediate steps to get to the final optimzed version?

Part 4 lost me completely. That's already advanced stuff, to much to comprehend if I can't even make simple things happen.

[martinvicanek]

My math tutor used to say: "It is much easier to solve a problem if you already know the result."
I don't have a recipe for the intermediate steps without telling you the result. I suppose it is about doing it a few times yourself, then you get the hang of it. Often there is more than one way to make a code efficient, so I would encourage everyone to try it for themselves.

[tulamide]

I hope I didn't discourage you! I really like to be educated further. For example, what if two conditionals are only to be executed if a third one is true?

[KG_is_back]

For example, what if two conditionals are only to be executed if a third one is true?

What might help you is to learn about boolean algebra. It brings up similarities between logical operations and mathematical operations. You can think of it like this:
TRUE=1, FALSE=0. Those are the only "numbers" in boolean algebra.
AND operation is equivalent with multiplication. It only yelds 1 if both arguments are 1, otherwise it yelds 0.

Code: Select all

0*0=0
1*0=0
1*1=1


OR operation is equivalent with addition. It only yelds 0 if both arguments are 0, otherwise it yelds 1.

Code: Select all

0+0=0
1+0=1
1+1=1 !!! this is the only place where boolean algebra differs from regular algebra


Both AND and OR are commutative and associative:

Code: Select all

A+B=B+A
A*B=B*A
A+(B+C)=(A+B)+C=A+B+C
A*(B*C)=(A*B)*C


They are also distributive:

Code: Select all

A*(B+C)=A*B+A*C


NOT is an unitary operator (meaning it has just 1 argument), it is typically written as !A . It simply reverses the value. Where this becomes important is in how it interacts with AND and OR operators. Negation of AND/OR is OR/AND of negations of arguments. It is called de Morgan's rule:

Code: Select all

!(A*B) = !A + !B
!(A+B) = !A * !B

or written in more FS-like code
NOT( a & b)= NOT(a) | NOT(b)
NOT( a | b)= NOT(a) & NOT(b)
note: FS does not have NOT operation. you can simulate one by as 0==(argument) since conveniently 0 is identical to false.


Comparison operations in math (and thus in programming) all have their natural negated forms:

Code: Select all

!( a > b) = (a <= b)
!( a >= b) = (a < b)
!(a == b)=(a != b)


now, let's look at what Martin did when he constructed the negated expression step by step:

Code: Select all

!( (in > 0)&(in1 <= 0) ) //negation of original expression
!(in > 0) | !(in1 <=0)   //we applied de Morgan's rule
(in <= 0) | (in1 > 0) //we negated the comparisons


The goal was to reduce the number of operations, by distributing all negations directly to the comparisons and then simply use the negated forms of those comparisons. (in this case original had 2 comparisons, 1 negation and 1 AND, while the result has just 1 OR and 2 comparisons)

As for your question "two conditionals are only to be executed if a third one is true?"
You start with your two conditionals (in this case I assume they are connected by OR)
(condition1 | condition2)
The result should be controlled by a third condition, which if it's false the whole expression should be false, otherwise the result should depend on the first two conditions. We simply use multiplication/AND:
(condition1 | condition 2) & condition3

I recommend you search for some boolean algebra basics courses online (there should be plenty available) and then do some exercises. It is typically thought in 1st semester at university, so it shouldn't be too difficult.

[Spogg]

I prefer to think in truth tables, but I get different result to yours for OR:

AND
In1, In2, Out, Not (NAND)
0 0 0 1
1 0 0 1
0 1 0 1
1 1 1 0

OR
In1, In2, Out, Not (NOR)
0 0 0 1
1 0 1 0
0 1 1 0
1 1 1 0

In your code block it says 1+0=0 which is surely not correct…?

I’m probably about to feel very silly…

Cheers

Spogg

[KG_is_back]

oops... ...typo...

[Spogg]

oops... ...typo...

We all do it!

[tulamide]

The more answers I get, the more obvious it becomes that I'm just not made for DSP code. When I cannot descrive my issue properly, how can I expect the people to help me? KG showed me that I was unsuccessful in making my issue understandable.

I started programming at the age of 15 and never stopped since then. One of my first projects was a soundtracker on my beloved Atari 520 ST. Bitwise logic was one of the first things I had to learn for this. A byte needed to carry parallel information for 3 tracks. Only bitwise and/or/not/xor/nand and a comparison of different bytes could accomplish that. I probably know more about bits than anyone ever needs, things like a nibble, for example. I use bitwise logic even today, for example to test for certain bits to be set.

But in the DSP code editor it is not about general bitwise logic. It is about translating conditionals into bitmasks. And the very act of translating human-oriented logic into machine-oriented logic, that's my issue. If I could use If-then-else in the code, I wouldn't despair at all! But the developers decided to go with this weird construction that you'll find nowhere else in any language I know (and I know a lot).

Since I can't explain my problem comprehensible, the conclusion is what I said in another thread: I give up on it.

Or is there somebody that will program a translator? A tool, where I enter normal (nested) conditionals and get the resulting bitmasking line? Optimzed?

I'm afraid not. And believe me, I hate that I can't resolve this issue. Just few people know how much I hate it. For decades I am developing software now, for decades I could realize whatever came to my mind. But the effing Bitmasking in Flowstone's DSP code editor is like a black hole.