[an error occurred while processing this directive]

複数のビットフィールドを持つ数値の並列演算

32bit整数に8bit整数を4つ格納している場合などで、それらを同時に加算したり、減算したりしたいことがあります。 Intel PentiumプロセッサのMMX命令は、こういった問題を解決するものですが、機種依存するアセンブラによるコーディングではなく、C言語レベルでなんとか高速化したい場合もあります。そういったときは、以下の方法を用いる事で高速化できます。

例えば以下のように平均値を求める場合、

struct Hoge{
    unsigned char p0;
    unsigned char p1;
    unsigned char p2;
    unsigned char p3;
};

Hoge v0, v1, v2;

v2.p0 = (v0.p0 + v1.p0) / 2;
v2.p1 = (v0.p1 + v1.p1) / 2;
v2.p2 = (v0.p2 + v1.p2) / 2;
v2.p3 = (v0.p3 + v1.p3) / 2;

これを、下のように書く事で高速化できます。

unsigned long v0, v1, v2;
// v0, v1 にはキャストするなり、あらかじめデータを入れておく
v2 = (v0 & v1) + (((v0 ^ v1) & 0xfefefefe) >> 1);

応用例

RGB各5bitを持つピクセルデータの半透明演算は以下のようになります。

u_short NormalBlend(u_short c0, u_short c1)
{
    return (c0 & c1) + (((c0 ^ c1) & 0x7bde) >> 1);
}

少し工夫することで、サチュレーション付き演算も可能です。たとえば、最大値で飽和する加算混合なら以下のように書けます。

u_short AddBlend(u_short c0, u_short c1)
{
    u_short c, m;
    c = (((c0 & c1) << 1) + ((c0 ^ c1) & 0x7bde)) & 0x8420;
    m = c - (c >> 5);
    return (c0 + c1 - c) | m;
}

// やねうらお様とさ～様から更に最適化する方法を教えていただきました。
// マスクの生成部が改善されている点に注目。
u_short AddBlend(u_short c0, u_short c1)
{
    u_short c;
    c = (((c0 & c1) << 1) + ((c0 ^ c1) & 0x7bde)) & 0x8420;
    c = ((c >> 5) + 0x3def) ^ 0x3def;
    return (c0 + c1 - c) | c;
}

当然減算混合もこのように簡単に書ける。

u_short SubBlend(u_short c0, u_short c1)
{
    u_short c, m;
    c = (((~c0 & c1) << 1) + ((~c0 ^ c1) & 0x7bde)) & 0x8420;
    m = c - (c >> 5);
    return (c0 - c1 + c) & ~m;
}


// こちらも同様に、やねうらお様とさ～様による更なる最適化の方法です。
// マスクの生成部が改善されている点に注目。

u_short SubBlend(u_short c0, u_short c1)
{
    u_short c, m;
    c = (((~c0 & c1) << 1) + ((~c0 ^ c1) & 0x7bde)) & 0x8420;
    m = (( c >> 5) + 0x3def) ^ 0x4210;
    return (c0 - c1 + c) & m;
}


// さ～様による更なる最適化の方法です。
// 凄すぎ。

u_short SubBlend(u_short c0, u_short c1)
{
    u_short c;
    c = (((~c0 & c1) << 1) + ((~c0 ^ c1) & 0x7bde)) & 0x8420;
    c = (( c >> 5) + 0x3def) ^ 0x3def;
    return (c0 | c) - (c1 | c);
}

その他

4バイト同時サチュレーション(飽和、0xffを超えないようにする)付きインクリメント

DWORD P_INC_US_B(DWORD x)
{
    DWORD dwNum = ((~(x & ((x & 0x7f7f7f7f) + 0x01010101))) & 0x80808080) >> 7;
    return x + dwNum;
}

4バイト同時サチュレーション(飽和、0未満にならないようにする)付きデクリメント

DWORD P_DEC_US_B(DWORD x)
{
    DWORD dwNum = ((x | ((x | 0x80808080) - 0x01010101)) & 0x80808080) >> 7;
    return x - dwNum;
}

MMX比較命令もどき(各バイト単位で比較し、同じなら0xff、違う場合は0x00をセットする)

DWORD P_CMP_EQ_B(DWORD a, DWORD b)
{
    DWORD c = a ^ b;
    c = (((c & 0x7f7f7f7f) + 0x7f7f7f7f) | c) & 0x80808080;
    c |= c - (c >> 7);
    return ~c;
}

// イタリアの Carlo Bramini さんから、改良案をいただきました。
DWORD P_CMP_EQ_B(DWORD a, DWORD b)
{
    DWORD c = a ^ b;
    c = (((c & 0x7f7f7f7f) + 0x7f7f7f7f) | c) & 0x80808080;
    return ((c >> 7) + 0x7f7f7f7f) ^ 0x80808080;
}

同じくMMXシフト命令もどき

DWORD P_SLL_W(DWORD x, DWORD s)
{
    DWORD m = 0xffff0000 ^ (0x0000ffff << s);
    return (x << s) & m;
}

余談

数年前に必要に迫られて考えたテクニックですが、現在でも十分有効に通用するようです。 NetNewsなどでくどいほど投稿して以来、世の中に浸透していったようで、あちらこちらの掲示板で見かけるようになりました。ただ、投稿者の私を忘れられて、転載した人に驚嘆が集まるのを見るとちょっとさびしいものを感じます(笑)。広く知っていただけることは本望なのですが(笑)。

しかし、それだけにとどまらず、一部のマニアの間で、この手の論理演算が研究され、多くのテクニックが開発されたのを見ると、やっぱり公開してよかったと思いますし、望外の喜びでもあります。