Add clz functions (Count number of Leading Zero bits), 32-and 64-bit variants

Add clz functions (Count number of Leading Zero bits), 32-and 64-bit variants

Using __builtin_clz on gcc/clang, and a fallback implementation
otherwise.

Also redefine WebRtcSpl_GetSizeInBits(x) as simply 32 - clz32(x).

BUG=chromium:601787
Committed: https://crrev.com/729b21f97f3d849b1ef2bd61114e4b39d073884d
Cr-Commit-Position: refs/heads/master@{#13014}

[kwiberg-webrtc, 2016-05-25 21:25:37]

Patchset #1 (id:1) has been deleted

[kwiberg-webrtc, 2016-05-25 23:49:22]

kwiberg@webrtc.org changed reviewers:
+ tina.legrand@webrtc.org

[tlegrand-webrtc, 2016-05-26 12:01:47]

I liked Patch Set 1 more than Patch Set 2. What was the reason for the change?

We have the old Norm-functions, that could probably use the new 32 bit function
as well.

https://codereview.chromium.org/2014023002/diff/20001/webrtc/common_audio/sig...
File webrtc/common_audio/signal_processing/include/spl_inl.h (right):

https://codereview.chromium.org/2014023002/diff/20001/webrtc/common_audio/sig...
webrtc/common_audio/signal_processing/include/spl_inl.h:120: static __inline
int16_t WebRtcSpl_NormW32(int32_t a) {
Maybe use your new function here as well?

https://codereview.chromium.org/2014023002/diff/20001/webrtc/common_audio/sig...
webrtc/common_audio/signal_processing/include/spl_inl.h:143: static __inline
int16_t WebRtcSpl_NormU32(uint32_t a) {
And here.

https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
File webrtc/common_audio/signal_processing/spl_inl.c (right):

https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
webrtc/common_audio/signal_processing/spl_inl.c:23: -1, 15, -1, 21, -1, 29, 19,
-1, -1, -1, -1, -1, 1,  27, 5,  12,
I would prefer keeping it as in Patch Set 1, since this add memory usage for a
function that should mostly be used in tests, right?

[kwiberg-webrtc, 2016-05-26 12:18:00]

https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
File webrtc/common_audio/signal_processing/spl_inl.c (right):

https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
webrtc/common_audio/signal_processing/spl_inl.c:23: -1, 15, -1, 21, -1, 29, 19,
-1, -1, -1, -1, -1, 1,  27, 5,  12,
On 2016/05/26 12:01:46, tlegrand-webrtc wrote:
> I would prefer keeping it as in Patch Set 1, since this add memory usage for a
> function that should mostly be used in tests, right?

Yes, this global table adds 64 bytes to the program (about the same as a few
lines of code). But at each call site, the inlined code is ~50 instead of ~100
bytes (unless we use GCC or clang, in which case the inlined code is ~10 bytes
and doesn't use this table).

No, WebRtcSpl_CountLeadingZeros32_NotBuiltin isn't just used in tests (then what
would be the point?)---it's used wherever we don't use gcc or clang, such as on
Windows.

I could preprocessor-magick this table away if we're on GCC or clang, but it's
going to be ugly since we still want the tests. Frankly, I'd rather lose the 64
bytes...

[kwiberg-webrtc, 2016-05-26 13:03:08]

On 2016/05/26 12:01:47, tlegrand-webrtc wrote:
> I liked Patch Set 1 more than Patch Set 2. What was the reason for the change?

I looked at the compiler output for ps1 and wasn't happy. ~40 instructions (~100
bytes) each time we inline that function. ps2 cuts that in half, and is 4 times
faster.

> We have the old Norm-functions, that could probably use the new 32 bit
function
> as well.

Ah, yes. The unsigned norm functions appear to be straight Count Leading Zeros.
The signed ones look like they negate negative numbers and force the least
significant bit to 1, which is easy to implement in terms of Count Leading
Zeros. But do you happen to know what they do? (That is, what math are they
implementing?)

[kwiberg-webrtc, 2016-05-26 13:04:25]

(A little late, since you've already seen it, but...) Changed to another clz
algorithm. A simple benchmark on my desktop says the new algorithm uses ~half
the number of instructions (~20 instead of ~40) and runs ~4 times faster than
the old one (but still ~5 times slower than the implementation that uses
__builtin_clz).

[kwiberg-webrtc, 2016-05-26 13:28:02]

On 2016/05/26 13:03:08, kwiberg-webrtc wrote:
> On 2016/05/26 12:01:47, tlegrand-webrtc wrote:
> > I liked Patch Set 1 more than Patch Set 2. What was the reason for the
change?
> 
> I looked at the compiler output for ps1 and wasn't happy. ~40 instructions
(~100
> bytes) each time we inline that function. ps2 cuts that in half, and is 4
times
> faster.
> 
> > We have the old Norm-functions, that could probably use the new 32 bit
> function
> > as well.
> 
> Ah, yes. The unsigned norm functions appear to be straight Count Leading
Zeros.
> The signed ones look like they negate negative numbers and force the least
> significant bit to 1, which is easy to implement in terms of Count Leading
> Zeros. But do you happen to know what they do? (That is, what math are they
> implementing?)

I think I figured it out: they return the number of steps you can left-shift the
argument without overflow, right?

And for some reason they make an extra effort to return 0 instead of 32 when the
argument is 0.

[tlegrand-webrtc, 2016-05-26 14:18:52]

On 2016/05/26 13:28:02, kwiberg-webrtc wrote:
> On 2016/05/26 13:03:08, kwiberg-webrtc wrote:
> > On 2016/05/26 12:01:47, tlegrand-webrtc wrote:
> > > I liked Patch Set 1 more than Patch Set 2. What was the reason for the
> change?
> > 
> > I looked at the compiler output for ps1 and wasn't happy. ~40 instructions
> (~100
> > bytes) each time we inline that function. ps2 cuts that in half, and is 4
> times
> > faster.
> > 
> > > We have the old Norm-functions, that could probably use the new 32 bit
> > function
> > > as well.
> > 
> > Ah, yes. The unsigned norm functions appear to be straight Count Leading
> Zeros.
> > The signed ones look like they negate negative numbers and force the least
> > significant bit to 1, which is easy to implement in terms of Count Leading
> > Zeros. But do you happen to know what they do? (That is, what math are they
> > implementing?)
> 
> I think I figured it out: they return the number of steps you can left-shift
the
> argument without overflow, right?
> 
> And for some reason they make an extra effort to return 0 instead of 32 when
the
> argument is 0.

Right, that's what they do. And I think there is some definition somewhere that
says norm(0)=0. I think "norm" comes from Matlab, but I'm not sure.

[tlegrand-webrtc, 2016-06-02 09:49:11]

Thanks for running the extra benchmark tests!

LGTM with a small nit.

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
File webrtc/common_audio/signal_processing/include/spl_inl.h (right):

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
webrtc/common_audio/signal_processing/include/spl_inl.h:128: // Return the
number of steps a can be left-shifted without overflow, or 0 if a
Nit: move 'a' to next line.

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
webrtc/common_audio/signal_processing/include/spl_inl.h:135: // == 0.
Same nit.

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
webrtc/common_audio/signal_processing/include/spl_inl.h:140: // Return the
number of steps a can be left-shifted without overflow, or 0 if a
...and here. :)

[kwiberg-webrtc, 2016-06-02 09:55:34]

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
File webrtc/common_audio/signal_processing/include/spl_inl.h (right):

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
webrtc/common_audio/signal_processing/include/spl_inl.h:128: // Return the
number of steps a can be left-shifted without overflow, or 0 if a
On 2016/06/02 09:49:11, tlegrand-webrtc wrote:
> Nit: move 'a' to next line.

Done.

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
webrtc/common_audio/signal_processing/include/spl_inl.h:135: // == 0.
On 2016/06/02 09:49:11, tlegrand-webrtc wrote:
> Same nit.

Done.

https://codereview.webrtc.org/2014023002/diff/80001/webrtc/common_audio/signa...
webrtc/common_audio/signal_processing/include/spl_inl.h:140: // Return the
number of steps a can be left-shifted without overflow, or 0 if a
On 2016/06/02 09:49:11, tlegrand-webrtc wrote:
> ...and here. :)

Done.

[kwiberg-webrtc, 2016-06-02 09:55:40]

The CQ bit was checked by kwiberg@webrtc.org

[kwiberg-webrtc, 2016-06-02 09:55:40]

The patchset sent to the CQ was uploaded after l-g-t-m from
tina.legrand@webrtc.org
Link to the patchset: https://codereview.webrtc.org/2014023002/#ps100001 (title:
"fix comments")

[commit-bot: I haz the power, 2016-06-02 09:55:53]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2014023002/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/2014023002/100001

[commit-bot: I haz the power, 2016-06-02 11:02:18]

Committed patchset #5 (id:100001)

[commit-bot: I haz the power, 2016-06-02 11:02:30]

Description was changed from

==========
Add clz functions (Count number of Leading Zero bits), 32-and 64-bit variants

Using __builtin_clz on gcc/clang, and a fallback implementation
otherwise.

Also redefine WebRtcSpl_GetSizeInBits(x) as simply 32 - clz32(x).

BUG=chromium:601787
==========

to

==========
Add clz functions (Count number of Leading Zero bits), 32-and 64-bit variants

Using __builtin_clz on gcc/clang, and a fallback implementation
otherwise.

Also redefine WebRtcSpl_GetSizeInBits(x) as simply 32 - clz32(x).

BUG=chromium:601787

Committed: https://crrev.com/729b21f97f3d849b1ef2bd61114e4b39d073884d
Cr-Commit-Position: refs/heads/master@{#13014}
==========

[commit-bot: I haz the power, 2016-06-02 11:02:37]

Patchset 5 (id:??) landed as
https://crrev.com/729b21f97f3d849b1ef2bd61114e4b39d073884d
Cr-Commit-Position: refs/heads/master@{#13014}

[jridges, 2016-06-02 16:15:53]

On 2016/05/26 12:18:00, kwiberg-webrtc wrote:
>
https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
> File webrtc/common_audio/signal_processing/spl_inl.c (right):
> 
>
https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
> webrtc/common_audio/signal_processing/spl_inl.c:23: -1, 15, -1, 21, -1, 29,
19,
> -1, -1, -1, -1, -1, 1,  27, 5,  12,
> On 2016/05/26 12:01:46, tlegrand-webrtc wrote:
> > I would prefer keeping it as in Patch Set 1, since this add memory usage for
a
> > function that should mostly be used in tests, right?
> 
> Yes, this global table adds 64 bytes to the program (about the same as a few
> lines of code). But at each call site, the inlined code is ~50 instead of ~100
> bytes (unless we use GCC or clang, in which case the inlined code is ~10 bytes
> and doesn't use this table).
> 
> No, WebRtcSpl_CountLeadingZeros32_NotBuiltin isn't just used in tests (then
what
> would be the point?)---it's used wherever we don't use gcc or clang, such as
on
> Windows.
> 
> I could preprocessor-magick this table away if we're on GCC or clang, but it's
> going to be ugly since we still want the tests. Frankly, I'd rather lose the
64
> bytes...

It might be worth it to use the _BitScanReverse intrinsic in Windows. I believe
it compiles to a single instruction.

[kwiberg-webrtc, 2016-06-02 16:54:33]

On 2016/06/02 16:15:53, jridges wrote:
> On 2016/05/26 12:18:00, kwiberg-webrtc wrote:
> >
>
https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
> > File webrtc/common_audio/signal_processing/spl_inl.c (right):
> > 
> >
>
https://codereview.chromium.org/2014023002/diff/40001/webrtc/common_audio/sig...
> > webrtc/common_audio/signal_processing/spl_inl.c:23: -1, 15, -1, 21, -1, 29,
> 19,
> > -1, -1, -1, -1, -1, 1,  27, 5,  12,
> > On 2016/05/26 12:01:46, tlegrand-webrtc wrote:
> > > I would prefer keeping it as in Patch Set 1, since this add memory usage
for
> a
> > > function that should mostly be used in tests, right?
> > 
> > Yes, this global table adds 64 bytes to the program (about the same as a few
> > lines of code). But at each call site, the inlined code is ~50 instead of
~100
> > bytes (unless we use GCC or clang, in which case the inlined code is ~10
bytes
> > and doesn't use this table).
> > 
> > No, WebRtcSpl_CountLeadingZeros32_NotBuiltin isn't just used in tests (then
> what
> > would be the point?)---it's used wherever we don't use gcc or clang, such as
> on
> > Windows.
> > 
> > I could preprocessor-magick this table away if we're on GCC or clang, but
it's
> > going to be ugly since we still want the tests. Frankly, I'd rather lose the
> 64
> > bytes...
> 
> It might be worth it to use the _BitScanReverse intrinsic in Windows. I
believe
> it compiles to a single instruction.

Yes. I looked into that, but somewhy Microsoft has made it ridiculously
complicated to use, compared to __builtin_clz. I could add support for it, but
it's not just a question of five minutes.

For reference: https://msdn.microsoft.com/en-us/library/fbxyd7zd.aspx