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

Ich werde eine Antwort hinterlassen, auch wenn sie nicht direkt auf die ursprüngliche Frage antwortet, weil ich denke, dass Sie sie letztendlich viel nützlicher finden werden.

Ich gehe davon aus, dass Ihre Farbe von einer Kamera oder einem Bildscanner stammt, der mit 12 Bit arbeitet, gefolgt von einem unbestimmten Verarbeitungsschritt, der möglicherweise Werte jenseits des Bereichs von 0 bis 4095 erzeugt. Wenn das der Fall ist, werden die Werte fast sicher linear abgeleitet. Das Problem ist, dass Bildschirme gammakorrigiert sind, so dass die Umwandlung von 12 Bit in 8 Bit eine nichtlineare Gammafunktion und nicht nur eine einfache Rechtsverschiebung erfordert. Dies ist viel langsamer als der Klemmvorgang, den Ihre Frage zu optimieren versucht. Wenn Sie keine Gammafunktion verwenden, erscheint das Bild zu dunkel.

short color     = /* some external source */;
unsigned char color8bit;
if (color <= 0)
    color8bit = 0;
else if (color >= 4095)
    color8bit = 255;
else
    color8bit = (unsigned char)(255.99 * pow(color / 4095.0, 1/2.2));

An diesem Punkt könnten Sie eine Nachschlagetabelle in Betracht ziehen wie von Kirill Kobelev vorgeschlagen .

Answer 2

Dies ähnelt in gewisser Weise der Antwort von Tom Seddon, verwendet aber eine etwas sauberere Methode, um die obige Klammer zu lösen. Beachten Sie, dass sowohl die Antwort von Tom Seddon als auch meine Antwort das Problem der Antwort von ouah umgehen, dass das Verschieben eines vorzeichenbehafteten Wertes nach rechts ein durch die Implementierung definiertes Verhalten ist und daher nicht garantiert auf allen Architekturen funktioniert.

#include <inttypes.h>
#include <iostream>

int16_t clamp(int16_t value)
{
    // clampBelow is 0xffff for -ve, 0x0000 for +ve
        int16_t const clampBelow = -static_cast<int16_t>(static_cast<uint16_t>(value) >> 15);

    // value is now clamped below at zero
    value &= ~clampBelow;
    // subtract 4095 so we can do the same trick again
    value -= 4095;
    // clampAbove is 0xffff for -ve, 0x0000 for +ve,
    // i.e. 0xffff for original value < 4095, 0x0000 for original >= 4096
        int16_t const clampAbove = -static_cast<int16_t>(static_cast<uint16_t>(value) >> 15);

    // adjusted value now clamped above at zero
    value &= clampAbove;
    // and restore to original value.
    value += 4095;
    return value;
}

void verify(int16_t value)
{
    int16_t const clamped = clamp(value);
    int16_t const check = (value < 0 ? 0 : value > 4095 ? 4095 : value);
    if (clamped != check)
    {
        std::cout << "Verification falure for value: " << value << ", clamped: " << clamped << ", check: " << check << std::endl;
    }
}

int main()
{
    for (int16_t i = 0x4000; i != 0x3fff; i++)
    {
        verify(i);
    }
    return 0;
}

Das ist ein vollständiges Testprogramm (OK, es testet also nicht 0x3fff - verklagt mich. ;) ), aus dem man die clamp() Routine für alles, was Sie brauchen.

Der Übersichtlichkeit halber habe ich die Klammer auch auf "einen Schritt pro Zeile" heruntergebrochen. Wenn Ihr Compiler einen halbwegs vernünftigen Optimierer hat, können Sie ihn so belassen und sich darauf verlassen, dass der Compiler den bestmöglichen Code erzeugt. Wenn der Optimierer Ihres Compilers nicht so gut ist, kann die Zeilenzahl auf jeden Fall reduziert werden, wenn auch auf Kosten der Lesbarkeit.

"Opfern Sie niemals Klarheit für Effizienz" - Bob Buckley, Informatikprofessor, U-Warwick, Coventry, England, 1980.

Der beste Rat, den ich je bekommen habe ;)