4

変数の値を0から4095の間に制限したいのですがsigned short、その後、最上位の8ビットを他の場所で使用するための最終値として使用します。現在、私は以下のような基本的な方法でそれを行っています:

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.
 */

これをビット操作のみを使用して、つまり条件を使用せずに実行できる方法はありますか?この操作はコード内で何千回も行われているため、処理を高速化するのにかなり役立つ可能性があります。

以下は、負の値やオーバーフローなどのエッジケースを処理しないため、役に立ちません。

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

編集: アダムローゼンフィールドの答えは、正しいアプローチを取りますが、正しく実装されていないものです。ouahの答えは正しい結果をもたらしますが、私が最初に見つけようとしていたものとは異なるアプローチを取ります。

これは私が使用することになったものです:

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 );
4

7 に答える 7

7

はい、これらのビットをいじるハックを参照してください:

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);

これが実際に高速であることが判明したかどうかはわかりません。プロファイルを作成する必要があります。最近のほとんどのx86およびx86-64チップは、EFLAGSステータスビットに応じて値を条件付きで格納する「条件付き移動」命令(cmov)をサポートしており、最適化コンパイラは、などの3値式からこれらの命令を生成することがよくありcolor >= 0 ? color : 0ます。これらはおそらく最速ですが、古いx86チップでは動作しません。

于 2012-09-06T21:51:29.683 に答える
5

次のことができます。

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

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

あなたの時代には、64kbのテーブルはとんでもないものではなく、許容できるかもしれません。このバリアントのコードのアセンブラコマンドの数は、他の可能なアプローチと比較して絶対的に最小になります。

于 2012-09-06T21:50:14.060 に答える
2

ashortは16ビットだと思います。

負の値を削除します。

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現在、0から32767までです。

次に、値をクランプするのと同様のことを行うことができます。

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
于 2012-09-06T22:05:33.913 に答える
2
short color = /* ... */
color =   ((((!!(color >> 12)) * 0xFFF)) | (!(color >> 12) * color ))
        & (!(color >> 15) * 0xFFF);

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

2の補数表現を想定しています。

これには、等式演算子または関係演算子を使用しないという利点があります。ブランチを絶対に避けたい状況があります。一部のセキュリティアプリケーションでは、攻撃者にブランチ予測を実行させたくない場合があります。ブランチがない場合(特に組み込みプロセッサの場合)、すべての入力に対して関数を一定時間で実行できます。

注:x * 0xFFFはさらにに減らすことができます(x << 12) - x。また、ここ(!(color >> 12) * color )の左側のオペランドはまたはであるため、の乗算をさらに最適化することもできます。*01

編集:

少し説明を追加します。上記の式は、条件演算子と関係演算子を使用せずに、以下と同じように機能します。

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

EDIT2:

@HotLicksが彼のコメントで正しく指摘しているように、これ!はまだ概念的なブランチです。それでも、ビット演算子を使用して計算することもできます。たとえば!!a、些細なことで行うことができます:

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

として!a行うことができますb ^ 1。そして、それをより効果的に行うための素晴らしいハックがあると確信しています。

于 2012-09-06T23:03:52.143 に答える
1

IntelのSSE組み込み関数を使用してこれを簡単にベクトル化することもできます。1つの128ビットレジスタは8つを保持shortし、それらすべてを並列に最小/最大/シフト/マスクする機能があります。ループでは、最小/最大の定数をレジスタにプリロードできます。命令(SSSE3のpshufb一部)は、バイトをパックします。

于 2012-09-06T23:44:03.880 に答える
0

元の質問に直接答えることはできませんが、最終的にはもっと便利だと思うので、答えを残しておきます。

あなたの色は12ビットで動作するカメラまたは画像スキャナーから来ていると思います。その後に0から4095の範囲を超える値を作成する可能性のある未決定の処理ステップが続きます。その場合、値はほぼ確実に線形に導出されます。問題は、ディスプレイがガンマ補正されているため、12ビットから8ビットへの変換には、単純な右シフトではなく、非線形ガンマ関数が必要になることです。これは、質問が最適化しようとしているクランプ操作よりもはるかに遅くなります。ガンマ関数を使用しない場合、画像は暗くなりすぎます。

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));

この時点で、KirillKobelevによって提案されたルックアップテーブルを検討することができます。

于 2012-09-07T00:01:47.507 に答える
0

これはTomSeddonの答えにいくぶん似ていますが、上記のクランプを行うために少しクリーンな方法を使用しています。セドン氏の答えと私の答えはどちらも、符号付きの値を右にシフトすることは実装で定義された動作であり、したがってすべてのアーキテクチャで機能することが保証されていないというouahの答えの問題を回避することに注意してください。

#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;
}

これは完全なテストプログラムです(OK、0x3fffをテストしません-私を訴えます。;))。そこからclamp()必要なルーチンを抽出できます。

また、わかりやすくするために、クランプを「1行に1ステップ」に分割しました。コンパイラーに中途半端なオプティマイザーがある場合は、そのままにして、コンパイラーに依存して可能な限り最高のコードを生成することができます。コンパイラのオプティマイザがそれほど優れていない場合は、読みやすさは少し犠牲になりますが、どうしても行数を減らすことができます。

「効率のために明快さを決して犠牲にしないでください」-ボブバックリー、comp sci教授、U-ワーウィック、コベントリー、イギリス、1980年。

私が今までに得た最高のアドバイス。;)

于 2017-06-27T03:02:33.720 に答える