C: Bithack geht nicht

[Nop (Gast)]

Es geht um eine Popcount-Routine mit Bit-Twiddling. Die funktioniert 
auch, aber nicht mehr, wenn man die Konstanten alle mit dem Suffix UL 
als unsigned long markiert, obwohl das gehen sollte. Gemäß integer 
promotion müßte das IMO ohnehin nach UL (32 bit) promoted werden.

Drei Versionen: die erste ohne Suffixe, die zweite soweit, daß es noch 
geht, die dritte geht nicht mehr. Also wenn man in der Zeile mit der 
Multiplikation nicht nur U, sondern UL hinzufügt (egal zu welcher der 
Konstanten), scheitert es mit verkehrtem Ergebnis.

Getestet mit GCC 9.3.0 64 Bit unter Linux, keine Warnungen erschienen.

/*
  compile with: gcc -O0 -std=c99 -Wall -Wextra
  see Bit Twiddling Hacks:
  https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
*/

#include <stdint.h>
#include <stdio.h>

/*works*/
uint32_t popcnt_1(uint32_t v) {
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}

/*works*/
uint32_t popcnt_2(uint32_t v) {
    v = v - ((v >> 1) & 0x55555555UL);
    v = (v & 0x33333333UL) + ((v >> 2) & 0x33333333UL);
    return (((v + (v >> 4)) & 0xF0F0F0FU) * 0x1010101U) >> 24;
}

/*wrong result*/
uint32_t popcnt_3(uint32_t v) {
    v = v - ((v >> 1) & 0x55555555UL);
    v = (v & 0x33333333UL) + ((v >> 2) & 0x33333333UL);
    return (((v + (v >> 4)) & 0xF0F0F0FUL) * 0x1010101UL) >> 24;
}

int main (void) {
    printf("1: 0xFF00 ones: %u\n", popcnt_1(0xFF00UL)); /*result: 8*/
    printf("2: 0xFF00 ones: %u\n", popcnt_2(0xFF00UL)); /*result: 8*/
    printf("3: 0xFF00 ones: %u\n", popcnt_3(0xFF00UL)); /*result: 2056*/
    return 0;
}

[Egon D. (Gast)]

Nop schrieb:

> UL (32 bit)

???

> Getestet mit GCC 9.3.0 64 Bit unter Linux,
.........................^^^^^^

[Jemand (Gast)]

Die letzte Multiplikation nutzt die modulare Arithmetik eines 32 Bit 
Integers aus, und UL macht das eben kaputt weil

Egon D. schrieb:
>> Getestet mit GCC 9.3.0 64 Bit unter Linux,
> .........................^^^^^^

[Nop (Gast)]

Egon D. schrieb:
> Nop schrieb:
>
>> UL (32 bit)
>
> ???
>
>> Getestet mit GCC 9.3.0 64 Bit unter Linux,
> .........................^^^^^^

Ah, danke. Mir war nicht klar, daß "long" 64 Bit hat unter einem 
64-Bit-Linux. Der Code kam von einem Windowssystem mit 64 Bit, wo "long" 
nur 32 Bit hat.

[Rolf M. (rmagnus)]

Wenn's ein uint32_t sein soll, nimmt man am besten UINT32_C(0x55555555). 
Dann macht der Präprozessor den auf dem System passenden Suffix draus.

[Nop (Gast)]

Rolf M. schrieb:
> Wenn's ein uint32_t sein soll, nimmt man am besten
> UINT32_C(0x55555555).
> Dann macht der Präprozessor den auf dem System passenden Suffix draus.

Auch ein interessanter Tip, gerade für solche Bithacks.

Wobei einfach nur U als Suffix ja im Normalfall ohnehin passend promoten 
sollte, selbst wenn man auf einem System mit int als 16 Bit ist, da 
müßte das dann nach unsigned long gehen. Also, auch ohne daß es wie hier 
zusammen mit einem uint32_t in einem Ausdruck steht.

[Programmierer (Gast)]

Alternativ: __builtin_popcount benutzen...

[Nop (Gast)]

Programmierer schrieb:
> Alternativ: __builtin_popcount benutzen...

Das mache ich schon, wenn eine entsprechende Build-Option mitgegeben 
wurde. Das Bitgeschubse ist der Fallback, wenn nicht.

[Michael X. (Gast)]

Nop schrieb:
> Rolf M. schrieb:
>> Wenn's ein uint32_t sein soll, nimmt man am besten
>> UINT32_C(0x55555555).
>> Dann macht der Präprozessor den auf dem System passenden Suffix draus.
>
> Auch ein interessanter Tip, gerade für solche Bithacks.

Allgemein sind die Makros in <stdint.h> einen Blick wert. Manche sind 
zwar richtig hässlich, aber wenn mans brauch ist man trotzdem froh.

[Walter T. (nicolas)]

Nop schrieb:
> Das mache ich schon, wenn eine entsprechende Build-Option mitgegeben
> wurde. Das Bitgeschubse ist der Fallback, wenn nicht.

Semi-OT: Wie machst Du die Auswahl, welche Lösung verwendet wird? Bei 
mir sieht das oft unschön aus:

    static_inline uint8_t ctz(unsigned int x)
    {
        #if (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)
            return __builtin_ctz(x);
        #else
            /* Bitwise binary search */
            /* Quelle https://graphics.stanford.edu/~seander/bithacks.html */
            unsigned int c = 32; /* c will be the number of zero bits on the right */
            x &= -signed(x);
            if (x) c--;
            if (x & 0x0000FFFF) c -= 16;
            if (x & 0x00FF00FF) c -= 8;
            if (x & 0x0F0F0F0F) c -= 4;
            if (x & 0x33333333) c -= 2;
            if (x & 0x55555555) c -= 1;
            return c;
        #endif
    }

[Nop (Gast)]

Walter T. schrieb:

> Semi-OT: Wie machst Du die Auswahl, welche Lösung verwendet wird?

Ich verwende die portable Lösung als Default, wenn kein entsprechendes 
define über die Buildchain gesetzt ist. Die Auto-Detection wie in Deinem 
Beispiel nehme ich nicht, weil ich das manuell kontrollieren will.

Das brauche ich z.B., wenn ich im Mockup auf dem Host teste, der popcnt 
unterstützt, aber die spätere embedded-Anwendung auf einer Plattform 
laufen soll, die das nicht tut. Zugleich bekomme ich eine Vorstellung, 
wieviel Geschwindigkeitsgewinn in der konkreten Anwendung denn über 
natives popcnt drin wäre.