Bitmasking in DSP Code

[Spogg]

I found DSP difficult to understand, and I still have to experiment until I get the intended outcome. If something even simple works first time, it’s a cause for immediately getting a coffee to celebrate.

But in my case I don’t think about the bit masking itself. I’ve kinda learnt the syntax of what to do to get what I want, and I never refer to the process under the hood. I look at work by others and try to figure out what’s going on. I remember totally struggling to modify an AHD envelope generator to work in sample increments rather than 16-sample hops. I got there but never once thought about bit masking. And that applies to literally all my DSP modules.

The only time I found it necessary to think about it was Martin’s tutorial, in relation to the abs alternative. This method was very odd to me but happily it makes sense to me now, but of course I could use it without remembering the explanation itself.

I think the method of learning that I’m proposing goes against the grain for you though. I personally find favour with top-down learning to some extent, with a lot of trial and much error. I like to learn what to do to get what I want and worry about what’s behind it all only when necessary or interesting. This is a bit like a child learning a language, they make certain noises and when they get it right, or good enough, stuff happens. It gets more polished as they practice.

On the technical reason for bit masking I believe that it’s simply faster and so more CPU efficient than conditional branching etc. but I hope Martin will correct me if that’s not right.


Cheers

Spogg

[adamszabo]

At first I didnt understand it either, but once it 'clicks' you get it. Working with streams is a bit different than normal coding where you use objects, and, if, else, clauses. You have think like an engineer instead of a programmer. Streams are a flow of data, just like electricity would be. Look at this schematic:

http://www.electroschematics.com/wp-content/uploads/2011/10/simple-water-detector.gif

There are streams, additions, comparisons with conditions etc. You have to take everything step by step. If you learn to think this way the code box will be much simpler. You need to take everything bit by bit. What do I need? I need to compare this value with that, to get an answer, then use that answer to do something else and so on.

[KG_is_back]

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

If you want to just convert ternary operator into bitmasks quick and dirty, that is rather easy to do:

Code: Select all

C ? A : B
= B +(A-B)&C //faster version, but has rounding errors if A and B are dissimilar size
= (A&C) + (B&(C==0)) //slower, but not sensitive to rounding errors
in case when one branch is zero
C ? A : 0 = A&C


To optimize it, just put as much of the stuff outside the ternary operator as possible, because unlike in C where only the picked branch A/B gets executed, in DSP both are executed. Example:

Code: Select all

y= condition ? (x*x*x) :( x*x);
y=x*x * ( condition ? x : 1);
//now convert
y=x*x* ( x + (1-x)&condition);


In case you need to nest them, just nest them. I recommend converting from inside out, because you may notice possible optimizations in the process. The branches may end up with a few identical terms inside them, which you can just put outside the conditional or merge them.

Code: Select all

expression & condition1 + expression & condition2 = expression & (condition1 | condition2)

C ? (A+B&D) : (E+B&D) = B&D + C ? A : E


This is how I think about the expressions with bitwise logic in DSP code. Simply first imagine them with ternary operators (or case statements that return value like in ruby, in case of multi-branching) and then just simplify them.

I guess it should be possible to automate the process and write some sort of "C to DSP" translator, but to make the result somewhat optimized it would have to parse the code. If I recall correctly, the newest version of FS implements the ternary operator directly, which solves most of these issues anyway...

[MichaelBenjamin]

.

[martinvicanek]

I would argue the code box should be as readable as possible, then the asm box can be optuscated to hell and back.

Makes sense.

The second example also could have some problems with floating point behaviour, since b+a-b in float might not be the same as a.

True, as also pointed out by KG.

[Spogg]

Yes FS uses the ! symbol for not expressions so != means not equal to.

Cheers

Spogg

[martinvicanek]

I think what he means is negate a boolean expression. I believe there is a NOT operator in the betas, but not in 3.0.8.1 or before. However, in FS Version >= 3.0.8 we have the xorps and the andnps operators which you can use to create a negation:

Code: Select all

streamin A;
streamout NOTA;
int TRUE=-1;

movaps xmm0,A;
xorps xmm0,TRUE;
movaps NOTA,xmm0;

and similarly for andnps, refer to Adams post above.

[martinvicanek]

Here is another example.

A Schmitt trigger is a comparator [...] which converts an analog input signal to a digital output signal. [...] When the input is higher than a chosen threshold, the output is high. When the input is below a different (lower) chosen threshold the output is low, and when the input is between the two levels the output retains its value.

Here is the code:

Code: Select all

streamin in;
streamout out;
streamin thr1;   // on threshold
streamin thr2;   // off threshold

out = out&(in>thr2);     // keep state if input above thr2 else set to 0

out = out|(1&(in>thr1)); // keep state if input below thr1 else set to 1



[tulamide]

Here is another example.

A Schmitt trigger is a comparator [...] which converts an analog input signal to a digital output signal. [...] When the input is higher than a chosen threshold, the output is high. When the input is below a different (lower) chosen threshold the output is low, and when the input is between the two levels the output retains its value.

Here is the code:

Code: Select all

streamin in;
streamout out;
streamin thr1;   // on threshold
streamin thr2;   // off threshold

out = out&(in>thr2);     // keep state if input above thr2 else set to 0

out = out|(1&(in>thr1)); // keep state if input below thr1 else set to 1



I'm so sorry, Martin, but I see a big question mark once again. the first "out =" line is now readable for me, thanks to your efforts. But I'm not sure about the second line. You're "or-ing", but I'm not sure what exactly. The right part will either be 1 or 0, but bitwise or would mean "if either bit is set, resulting bit is set". So 0 would not change anything, and 1 would change the lsb. What am I missing?

[martinvicanek]

I'm not sure about the second line.

Thanks for asking. Yes, this one is a bit tricky so let me explain step by step.

Consider thus the instruction
out = out|(1&(in>thr1));

The expression (in>thr1) is either true or false.

If false then 1&(in>thr1) is zero (both as a float variable and bitwise). Hence "or"-ing it with the out variable will bring no change, because
out|0 = out.

If (in>thr1) is true then 1&(in>thr1) is simply 1 or, in binary representation,
0 01111111 00000000000000000000000 (the two spaces are for better readability).
Now this expression is bitwise "or"-ed with the out variable, which can only have the the float values 1 or 0. (It has its value from previous code evaluations.)
Either way, the result will be 1 because both 1|1 = 1 and 0|1 = 1.

So to summarize in pseudocode:

Code: Select all

if (in>thr1) then
  out = 1
else
  out = out // no change
end if


Hope that helps!