Wie undefiniert sind, __builtin_ctz(0) oder __builtin_clz(0)?
Hintergrund
Für eine lange Zeit, gcc zur Verfügung gestellt hat eine Reihe von builtin-bit-twiddling-Funktionen, insbesondere die Anzahl der Leerzeichen am Anfang und Ende 0-bits (auch für long unsigned
und long long unsigned
, die Suffixe l
und ll
):
— Built-in-Funktion:
int __builtin_clz (unsigned int x)
Gibt die
Nummer mit führenden 0-bits inx
, beginnend mit dem most significant bit
position. Wennx
0 ist, ist das Ergebnis undefiniert.— Built-in-Funktion:
int __builtin_ctz (unsigned int x)
Gibt die
Anzahl der nachgestellten 0-bits inx
, beginnend bei dem niederwertigsten bit
position. Wennx
0 ist, ist das Ergebnis undefiniert.
Auf jeden online (disclaimer: nur 64-bit) compiler, die ich getestet, aber das Ergebnis war, dass beide clz(0)
und ctz(0)
Gegenzug die Anzahl der bits der zugrunde liegenden builtin-Typ, z.B.
#include <iostream>
#include <limits>
int main()
{
//prints 32 32 32 on most systems
std::cout << std::numeric_limits<unsigned>::digits << " " << __builtin_ctz(0) << " " << __builtin_clz(0);
}
Versucht Abhilfe
Den neuesten Clang SVN trunk in std=c++1y
mode hat all diese Funktionen entspannt C++14 constexpr
, das macht Sie zu Kandidaten für die Verwendung in einem SFINAE-Ausdruck für eine wrapper-Funktion, die Vorlage um die 3 ctz
/clz
gelieferten für unsigned
, unsigned long
, und unsigned long long
template<class T> //wrapper class specialized for u, ul, ull (not shown)
constexpr int ctznz(T x) { return wrapper_class_around_builtin_ctz<T>()(x); }
//overload for platforms where ctznz returns size of underlying type
template<class T>
constexpr auto ctz(T x)
-> typename std::enable_if<ctznz(0) == std::numeric_limits<T>::digits, int>::type
{ return ctznz(x); }
//overload for platforms where ctznz does something else
template<class T>
constexpr auto ctz(T x)
-> typename std::enable_if<ctznz(0) != std::numeric_limits<T>::digits, int>::type
{ return x ? ctznz(x) : std::numeric_limits<T>::digits; }
Der Gewinn aus dieser hack ist, dass Plattformen, die das erforderliche Ergebnis geben für ctz(0)
weglassen können, eine zusätzliche bedingte test für x==0
(der mag eine Mikro-Optimierung, aber wenn Sie sind bereits bis auf die Ebene der builtin-bit-twiddling-Funktionen, es kann einen großen Unterschied machen)
Fragen
Wie undefiniert ist die Familie von builtin-Funktionen clz(0)
und ctz(0)
?
- können Sie werfen eine
std::invalid_argument
Ausnahme? - für x64, wird Sie für die aktuelle gcc-Distribution, die Rückgabe der Größe des underyling geben?
- sind die ARM/x86-Plattformen anders (ich habe keinen Zugang, um das zu testen)?
- ist die oben SFINAE-trick eine gut definierte Möglichkeit zum trennen von solchen Plattformen?
- Wenn Sie Ihre Hände bekommen können die Datei
longlong.h
im gcc/gmp/glibc, suchen das makro COUNT_LEADING_ZEROS_0...
Du musst angemeldet sein, um einen Kommentar abzugeben.
Leider auch die x86-64-Implementierungen unterscheiden sich von Intel instruction set reference,
BSF
undBSR
mit einem source-operand den Wert(0)
lässt das Ziel undefined, und legt dieZF
(zero-flag). So ist das Verhalten nicht konsistent zwischen Mikro-Architekturen oder, sagen wir, AMD und Intel. (Ich glaube AMD lässt das Ziel unverändert.)Den neueren
LZCNT
undTZCNT
Anweisungen sind nicht allgegenwärtig. Beide sind nur vorhanden, da der Haswell-Architektur (Intel).ctz(0)
nennen deterministisch ist, gibt immer die gleiche Antwort auf dieser Plattform (also nicht zu undefiniertem Verhalten), so dass meine SFINAE hack macht eigentlich Sinn?bsr
/bsf
mit einer null als Quelle nicht ändern das Ziel, jedem Intel-Prozessor, den ich jemals in der Lage zu testen (oder hören) tut es auch. Intel einfach nicht es zu dokumentieren, dass Art und Weise.Der Grund ist der Wert undefiniert ist, dass es ermöglicht, dass der compiler Prozessor-Anweisungen, für die ist das Ergebnis undefiniert, wenn diese Anweisungen sind der Schnellste Weg, eine Antwort bekommen.
Aber es ist wichtig zu verstehen, dass nicht nur sind die Ergebnisse nicht definiert; Sie sind undeterministic. Es ist gültig, da Intel-instruction-Referenz, nach der Anweisung zurückzukehren, die niedrigen 7 bits von der aktuellen Zeit, zum Beispiel.
- Und hier wird es interessant/gefährlich: der compiler writer kann diese situation ausnutzen, um die Herstellung von kleineren code. Betrachten Sie dieses non-template-Spezialisierung-version von code:
Funktioniert dies auch auf einem Prozessor/compiler, die beschlossen haben, zurück zu kehren #bits für ctznz(0). Aber un-Prozessor/compiler, der für eine Rückkehr entscheiden pseudo-random-Werte, die der compiler entscheiden kann, "ich darf zurückgeben, was ich will für ctznz(0), und der code wird kleiner, wenn ich wieder #bits, also werde ich". Dann wird der code endet Aufruf ctznz die ganze Zeit, obwohl es produziert die falsche Antwort.
Anders ausgedrückt: der compiler Undefinierte Ergebnisse sind nicht garantiert undefiniert in der gleichen Weise, dass das laufende Programm die Undefinierte Ergebnisse.
Gibt es wirklich keinen Weg, um dieses. Wenn Sie verwenden müssen, __builtin_clz, mit einem Quell-Operanden, der auch null sein kann, müssen Sie die überprüfen, die ganze Zeit.