3

I want to automatically determine length in bytes of a field (addr) that is uint32, based on it's contents. Compiler is GCC. I use this:

uint8 len;

if(addr < 256) len = 1;
else if (addr < 65536) len = 2;
else if (addr < 16777216) len = 3;
else len = 4;

Is there a more efficient way?

This is inside a SPI function for a embedded device. I'm interested in the fastest way except macros, since addr can be a variable.

Jongware
  • 22,200
  • 8
  • 54
  • 100
yo3hcv
  • 1,531
  • 2
  • 17
  • 27

3 Answers3

4

You can do it using an approach similar to binary search: first compare to 65536, then either to 256 or 16777216, depending on the outcome of the first comparison. This way you always finish in two comparisons, while your code sometimes would require three:

uint8 len = (addr < 65536)
    ? ((addr < 256)      ? 1 : 2)
    : ((addr < 16777216) ? 3 : 4);
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • No bit twiddling possible? – Jongware Jan 13 '18 at 17:40
  • Against that, this code will always require two comparisons whereas the original code sometimes only requires one. If the inputs are uniformly distributed across the entire range of possible values, you could average 1-and-a-bit comparisons by checking the largest first. If the inputs are biassed towards the small numbers, the original might be better. It's unlikely that any of this matters — the performance of an application using this function is unlikely to be measurably affected. – Jonathan Leffler Jan 13 '18 at 17:40
  • @JonathanLeffler: some of OP's tests will require *three* comparisons – and with an equal distribution, the average will still be 2 :) – Jongware Jan 13 '18 at 17:50
  • 1
    Agreed, the original code will sometimes require three comparisons. However, if the numbers are uniformly distributed over the entire 32-bit unsigned number range, then 255 out of every 256 will have 4 bytes of data; of the remainder, 255 out of 256 will have 3 bytes of data (only 1 in 65,536 won't have 3 or 4 bytes of data); of the remainder; 255 out of 256 will have 2 bytes of data; only 1 in 16,777,216 will have just 1 byte of data. But the chances of the numbers being uniformly distributed over the entire range is vanishingly small. – Jonathan Leffler Jan 13 '18 at 17:55
1

gcc has a __builtin_ctz() function which can be used like

if (addr == 0)
    len = 0;
else
    len = (sizeof(int) * 8 - __builtin_ctz(addr) + 7) / 8;

Update:

under ARM, this compiles to

    cmp     r0, #0
    rbitne  r0, r0
    clzne   r0, r0
    rsbne   r0, r0, #39
    lsrne   r0, r0, #3
    bx      lr
ensc
  • 6,704
  • 14
  • 22
1

Get the position of the highest bit – the only one that counts for your question (from https://stackoverflow.com/a/14085901). Divide by 8 to get the number of bytes.

addr = 0x20424;
printf ("%d\n", (fls(addr)+7)>>3);

It returns 0 when addr == 0.

fls is conforming to POSIX.1-2001, POSIX.1-2008, 4.3BSD. If your current system does not contain it, look at the above link or What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C? for more suggestions to find the highest bit set.

Jongware
  • 22,200
  • 8
  • 54
  • 100