Einen 16-Bit-Wert mit Vorzeichen zwischen 0 und 4095 nur mit Bitmanipulation einschränken (ohne Verzweigung)

Question

Ich möchte den Wert einer signed short zwischen 0 und 4095, wobei ich die höchstwertigen 8 Bits als endgültigen Wert für andere Zwecke verwende. Im Moment tue ich es in einer grundlegenden Weise wie unten:

short color     = /* some external source */;
/* 
 * I get the color value as a 16 bit signed integer from an
 * external source I cannot trust. 16 bits are being used here
 * for higher precision.
 */

if ( color < 0 ) {
    color = 0;
}
else if ( color > 4095 ) {
    color = 4095;
}

unsigned char color8bit  = 0xFF & (color >> 4);
/*
 * color8bit is my final value which I would actually use
 * in my application.
 */

Gibt es eine Möglichkeit, dies nur mit Bitmanipulation zu tun, d. h. ohne Verwendung von Konditionalen? Es könnte ziemlich viel helfen, die Dinge zu beschleunigen, da diese Operation Tausende von Zeit in den Code geschieht.

Das Folgende wird nicht helfen, da es sich nicht um Randfälle wie negative Werte und Überläufe kümmert:

unsigned char color8bit = 0xFF & (( 0x0FFF & color ) >> 4 );

Edita: Adam Rosenfields Antwort ist diejenige, die den richtigen Ansatz verfolgt, der aber nicht korrekt umgesetzt wird. Antwort von ouah liefert korrekte Ergebnisse, verfolgt aber einen anderen Ansatz als den, den ich ursprünglich herausfinden wollte.

Das habe ich schließlich verwendet:

const static short min = 0;
const static short max = 4095;
color = min ^ (( min ^ color ) & -( min < color ));
color = max ^ (( color ^ max ) & -( color < max ));
unsigned char color8bit = 0xFF & (( 0x0FFF & color ) >> 4 );

Answer 1

Ja, siehe diese bit-twidriger Hacks :

short color = ...;
color = color ^ (color & -(color < 0));  // color = max(color, 0)
color = 4096 ^ ((color ^ 4096) & -(color < 4096));  // color = min(color, 4096)

unsigned char color8bit  = 0xFF & (color >> 4);

Ob das tatsächlich schneller geht, weiß ich nicht - Sie sollten ein Profil erstellen. Die meisten modernen x86- und x86-64-Chips unterstützen heutzutage "Conditional Move"-Befehle (cmov), die abhängig von den EFLAGS-Statusbits einen Wert speichern, und optimierende Compiler erzeugen diese Befehle oft aus ternären Ausdrücken wie color >= 0 ? color : 0 . Diese werden wahrscheinlich am schnellsten sein, aber sie laufen nicht auf älteren x86-Chips.

Answer 2

Sie können Folgendes tun:

BYTE data[0x10000] = { ..... };

BYTE byte_color = data[(unsiged short)short_color];

Zu Ihrer Zeit ist eine 64kb-Tabelle nichts Ungeheuerliches und kann akzeptabel sein. Die Anzahl der Assembler-Befehle in dieser Variante des Codes wird im Vergleich zu anderen möglichen Ansätzen absolut minimal sein.

Answer 3

Ich nehme an, dass ein short beträgt 16 Bit.

Entfernen Sie negative Werte:

int16_t mask=-(int16_t)((uint16_t)color>>15);//0xFFFF if +ve, 0 if -ve
short value=color&mask;//0 if -ve, colour if +ve

value liegt nun zwischen 0 und 32767 einschließlich.

Sie können dann etwas Ähnliches tun, um den Wert festzuhalten:

mask=(uint16_t)(value-4096)>>15;//1 if <=4095, 0 if >4095
--mask;//0 if <=4095, 0xFFFF if >4095
mask&=0xFFF;//0 if <=4095, 4095 if >4095

value|=mask;//4095 if >4095, color if <4095

Answer 4

short color = /* ... */
color =   ((((!!(color >> 12)) * 0xFFF)) | (!(color >> 12) * color ))
        & (!(color >> 15) * 0xFFF);

unsigned char color8bit  = 0xFF & (color >> 4);

Sie geht von der Zweierkomplement-Darstellung aus.

Dies hat den Vorteil, dass keine Gleichheits- oder Beziehungsoperatoren verwendet werden. Es gibt Situationen, in denen man Verzweigungen um jeden Preis vermeiden möchte: In einigen Sicherheitsanwendungen möchte man nicht, dass die Angreifer Verzweigungsvorhersagen machen können. Ohne Verzweigungen (vor allem in eingebetteten Prozessoren) können Sie Ihre Funktion in konstanter Zeit für alle Eingaben laufen lassen.

Beachten Sie das: x * 0xFFF kann weiter reduziert werden auf (x << 12) - x . Auch die Multiplikation in (!(color >> 12) * color ) kann auch weiter optimiert werden, da der linke Operand von * hier ist 0 ou 1 .

EDITAR:

Ich füge eine kleine Erklärung hinzu: Der obige Ausdruck tut einfach das Gleiche wie der folgende, ohne die Verwendung der bedingten und relationalen Operatoren:

y =   ((y > 4095 ? 4095 : 0) | (y > 4095 ? 0 : y))
    & (y < 0 ? 0 : 4095);

EDIT2:

wie @HotLicks in seinem Kommentar richtig bemerkt hat, die ! ist immer noch ein konzeptioneller Zweig. Dennoch kann er auch mit bitweisen Operatoren berechnet werden. Zum Beispiel !!a kann mit dem Trivialen gemacht werden:

b = (a >> 15 | a >> 14 | ... | a >> 1 | a) & 1

と !a kann erfolgen als b ^ 1 . Und ich bin sicher, dass es einen netten Hack gibt, um dies effektiver zu tun.

Answer 5

Sie könnten dies auch leicht vektorisieren mit Intels SSE-Intrinsik . Ein 128-Bit-Register würde 8 Ihrer Daten enthalten. short und es gibt Funktionen für min/max/shift/mask, die alle parallel laufen. In einer Schleife können die Konstanten für min/max in ein Register vorgeladen werden. Die pshufb Anweisung (Teil von SSSE3) packt sogar die Bytes für Sie.