on what platform?

msp430

but reverting this adds problems for the posix layer....

I think this is our case: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34210

can we implement __ffshi2 for msp430?

@mehlis Without having looked too far into this (only at your link actually) I guess this would mean patching gcc... we don't want to do that.

isn't it possible to have something like this for the msp430

int
__ffshi2 (UHWtype u)
{
  UHWtype count;

  if (u == 0)
    return 0;

  return 16 - __builtin_clz (u & - u);
}

from https://chromium.googlesource.com/native_client/nacl-toolchain/+/gcc-4.5.0/gcc/gcc/config/stormy16/stormy16-lib2.c

perhaps __builtin_clz is implemented?! :)

I think we shouldn't rely on any compiler builtins as GCC might not be available for all platforms. We could define a ffs for MSP430 ourselves.

@mehlis, no luck: "undefined reference to `__clzhi2'"

I could offer an O(log CHAR_BIT) implementation instead of the "naïve" implementation for ffs/number_of_lowest_bit: https://gist.github.com/Kijewski/7359805. Maybe being used in the scheduler could justify a more complex solution in favor of speed?

On my home x86 my implementation takes 29s to calculate ffs(u) for u in [0, 2^32).
I killed the same test for number_of_lowest_bit after 5 minutes …
YMMV.

With arm-none-eabi-gcc -Os the

• number_of_lowest_bit has 7 instructions.
• ffs has 14 instructions, but could be implemented like @mehlis' quote of __ffshi2, too.
• clz has 12 instructions.

@mehlis the posix wrapper does not rely on it. We could easily replace ffs (which is not dependent on this commit btw) by our own implementation.

@Kijewski, I haven't tested on the MSP430, but on ARM7 your code is - as mentioned - slower (with -Os and -O0). I didn't quite get how you would make it smaller with __ffshi2.

I haven't tested on the MSP430, but on ARM7 your code is - as mentioned - slower (with -Os and -O0).

Darn. Now I see why I had to abort my test. If you supply number_of_lowest_bit with a zero it gets stuck …
With an if (!v) return 0; it is about twice as fast as my implementation.

I didn't quite get how you would make it smaller with __ffshi2.

You only need ffs or clz, not both, b/c clz can emulate ffs.

Now I see why I had to abort my test. If you supply number_of_lowest_bit with a zero it gets stuck …

As the documentation says. So, we continue with the old implementation? If there is something more efficient I'd be happy to use it.

As the documentation says.

Documenting a problem is one step short of fixing a problem. :)
I guess there can't be a better implementation in pure C than the naïve one. More advanced implementations rely heavily on big lookup tables.

But I guess reverting the commit is not the best approach. Why not just implement __ffshi2 for MSP 430?

^{(And Why is the folder called msb-430 if the hardware is called msp-430?)
(You do blockquotes with > text.)}

Documenting a problem is one step short of fixing a problem. :)

You cannot do all kind of error handling on constrained devices, you have to rely on the programmer knowing what he's doing.

Why not just implement __ffshi2 for MSP 430?

Well, that's basically what bitarithm does.

(And Why is the folder called msb-430 if the hardware is called msp-430?)

Don't mix up things: The MSB-430 (modular sensor board) is a hardware platform developed at FU Berlin:
http://www.mi.fu-berlin.de/inf/groups/ag-tech/projects/Z_Finished_Projects/ScatterWeb/modules/mod_MSB-430.html
while MSP430 is a µc familiy from TI:
http://www.ti.com/lsds/ti/microcontroller/16-bit_msp430/overview.page

So, what's the conclusion?

needs rebase

Done

ACK

@OlegHahm merge?

Merge