掲示板ランキング  かまぼこ(さつまあげ)  かまぼこ(はんぺん)  かまぼこ(笹かまぼこ)


掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板1

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.6484

戻り値付き関数を引数付きマクロで代用
投稿者---chu-(2006/09/14 20:36:24)


環境:LSI-C

[test.c]のntz()をマクロで代用してみようとNTZ()を組んでいます。
惜しい所までは出来たのですが、引数を操作しているため実引数を破壊してしまう問題があります。

戻り値無し関数の代用ならば[例]のようなテクニックを知っていますが、
戻り値付き関数の代用でローカル変数を使うテクニックはないでしょうか。

[例]
#define SWAP(type, ptr1, ptr2) \
do{ \
    type t = *ptr1; \
    *ptr1 = *ptr2; \
    *ptr2 = t; \
}while(0)

[test.c]
#include <stdio.h>
#include <stdlib.h>

typedef unsigned char uchar;
typedef unsigned long ulong;

int ntz(ulong bits)
{
    bits = (bits - 1) & ~bits;
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0F0F0F0F) + (bits >> 4 & 0x0F0F0F0F);
    bits = (bits & 0x00FF00FF) + (bits >> 8 & 0x00FF00FF);
    return (bits & 0x0000FFFF) + (bits >>16 & 0x0000FFFF);
}

#define NTZ(bits) \
    (bits = (bits - 1) & ~bits, \
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555), \
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333), \
    bits = (bits & 0x0F0F0F0F) + (bits >> 4 & 0x0F0F0F0F), \
    bits = (bits & 0x00FF00FF) + (bits >> 8 & 0x00FF00FF), \
    (bits & 0x0000FFFF) + (bits >>16 & 0x0000FFFF))

int main(void)
{
    char buf[256];
    uchar flag;
    int count[8] = {0};
    int i;

    printf("bit  :[7][6][5][4][3][2][1][0] ");
    while ( 1 ) {
        printf("> ");
        gets(buf);
        flag = (uchar)strtoul(buf, NULL, 0);

        count[NTZ(flag)]++;

        printf("0x%02X > ", flag);
        for ( i = 8 - 1; i >= 0 ; i-- ) {
            printf("%-2d ", count[i]);
        }
    }
    return 0;
}

[出力]
>test
bit  :[7][6][5][4][3][2][1][0] > 0x80
0x07 > 1  0  0  0  0  0  0  0  > 0x80      // 実引数破壊により0x07
0x07 > 2  0  0  0  0  0  0  0  > 0x04      // 実引数破壊により0x07
0x02 > 2  0  0  0  0  1  0  0  > 0x04      // 実引数破壊により0x02
0x02 > 2  0  0  0  0  2  0  0  > 0x04      // 実引数破壊により0x02
0x02 > 2  0  0  0  0  3  0  0  > ^C        // 実引数破壊により0x02

>



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:戻り値付き関数を引数付きマクロで代用 6485 かずま 2006/09/14 21:48:20


No.6485

Re:戻り値付き関数を引数付きマクロで代用
投稿者---かずま(2006/09/14 21:48:20)


> 戻り値付き関数の代用でローカル変数を使うテクニックはないでしょうか。

ローカル変数を使わないといけないのでしょうか?
#define N5(b)  (((b) - 1) & ~(b))
#define N4(b)  ((N5(b) & 0x55555555) + (N5(b) >> 1 & 0x55555555))
#define N3(b)  ((N4(b) & 0x33333333) + (N4(b) >> 2 & 0x33333333))
#define N2(b)  ((N3(b) & 0x0F0F0F0F) + (N3(b) >> 4 & 0x0F0F0F0F))
#define N1(b)  ((N2(b) & 0x00FF00FF) + (N2(b) >> 8 & 0x00FF00FF))
#define NTZ(b) ((N1(b) & 0x0000FFFF) + (N1(b) >>16 & 0x0000FFFF))



この投稿にコメントする

削除パスワード

No.6487

Re:戻り値付き関数を引数付きマクロで代用
投稿者---かずま(2006/09/14 21:57:30)


すみません。
LSI C-86 だと、out of memory と言われてコンパイルできませんでした。


この投稿にコメントする

削除パスワード

No.6495

Re:戻り値付き関数を引数付きマクロで代用
投稿者---chu-(2006/09/15 01:25:07)


素直に新しいコンパイラを使ってインライン関数とするのがいいのでしょうが、
なにか既存のテクニックはないものかと質問させていただきました。

返信ありがとうございます。

なるほど。
しかしよく考えてみると計算量が増えそうですね。

プリプロセッサを通すと[test.i]になりました。
BCB5で[Unit1.cpp]を組んで測定すると[測定結果]になりました。

[test.i]
count[(((((((((((((flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(flag
)) >> 1 & 0x55555555)) & 0x33333333) + ((((((flag) - 1) & ~(flag)) & 0x55555555)
 + ((((flag) - 1) & ~(flag)) >> 1 & 0x55555555)) >> 2 & 0x33333333)) & 0x0F0F0F0
F) + ((((((((flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(flag)) >> 
1 & 0x55555555)) & 0x33333333) + ((((((flag) - 1) & ~(flag)) & 0x55555555) + (((
(flag) - 1) & ~(flag)) >> 1 & 0x55555555)) >> 2 & 0x33333333)) >> 4 & 0x0F0F0F0F
)) & 0x00FF00FF) + ((((((((((flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1
) & ~(flag)) >> 1 & 0x55555555)) & 0x33333333) + ((((((flag) - 1) & ~(flag)) & 0
x55555555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x55555555)) >> 2 & 0x33333333)) &
 0x0F0F0F0F) + ((((((((flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(
flag)) >> 1 & 0x55555555)) & 0x33333333) + ((((((flag) - 1) & ~(flag)) & 0x55555
555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x55555555)) >> 2 & 0x33333333)) >> 4 & 
0x0F0F0F0F)) >> 8 & 0x00FF00FF)) & 0x0000FFFF) + ((((((((((((flag) - 1) & ~(flag
)) & 0x55555555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x55555555)) & 0x33333333) +
 ((((((flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x
55555555)) >> 2 & 0x33333333)) & 0x0F0F0F0F) + ((((((((flag) - 1) & ~(flag)) & 0
x55555555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x55555555)) & 0x33333333) + (((((
(flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x555555
55)) >> 2 & 0x33333333)) >> 4 & 0x0F0F0F0F)) & 0x00FF00FF) + ((((((((((flag) - 1
) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x55555555)) & 0x3
3333333) + ((((((flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(flag))
 >> 1 & 0x55555555)) >> 2 & 0x33333333)) & 0x0F0F0F0F) + ((((((((flag) - 1) & ~(
flag)) & 0x55555555) + ((((flag) - 1) & ~(flag)) >> 1 & 0x55555555)) & 0x3333333
3) + ((((((flag) - 1) & ~(flag)) & 0x55555555) + ((((flag) - 1) & ~(flag)) >> 1 
& 0x55555555)) >> 2 & 0x33333333)) >> 4 & 0x0F0F0F0F)) >> 8 & 0x00FF00FF)) >>16 
& 0x0000FFFF))]++;

[Unit1.cpp]
typedef unsigned long ulong;

int ntz(ulong bits)
{
    bits = (bits - 1) & ~bits;
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0F0F0F0F) + (bits >> 4 & 0x0F0F0F0F);
    bits = (bits & 0x00FF00FF) + (bits >> 8 & 0x00FF00FF);
    return (bits & 0x0000FFFF) + (bits >>16 & 0x0000FFFF);
}

#define NTZ(bits) \
    (bits = (bits - 1) & ~bits, \
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555), \
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333), \
    bits = (bits & 0x0F0F0F0F) + (bits >> 4 & 0x0F0F0F0F), \
    bits = (bits & 0x00FF00FF) + (bits >> 8 & 0x00FF00FF), \
    (bits & 0x0000FFFF) + (bits >>16 & 0x0000FFFF))

#define N5(b)  (((b) - 1) & ~(b))
#define N4(b)  ((N5(b) & 0x55555555) + (N5(b) >> 1 & 0x55555555))
#define N3(b)  ((N4(b) & 0x33333333) + (N4(b) >> 2 & 0x33333333))
#define N2(b)  ((N3(b) & 0x0F0F0F0F) + (N3(b) >> 4 & 0x0F0F0F0F))
#define N1(b)  ((N2(b) & 0x00FF00FF) + (N2(b) >> 8 & 0x00FF00FF))
#define NTZ2(b) ((N1(b) & 0x0000FFFF) + (N1(b) >>16 & 0x0000FFFF))

void __fastcall TForm1::Button1Click(TObject *Sender)
{
    const int n = 100000000;
    const ulong init = 0x80000000;
    int count[32];
    ulong flag;
    DWORD time;
    int i;

    Sleep(500);

    time = timeGetTime();
    for ( i = 0; i < n; i++ ) {
        flag = init;
        count[ntz(flag)]++;
    }
    time = timeGetTime() - time;
    Memo1->Lines->Add(AnsiString().sprintf("%08lX : %lu", flag, time));

    time = timeGetTime();
    for ( i = 0; i < n; i++ ) {
        flag = init;
        count[NTZ(flag)]++;
    }
    time = timeGetTime() - time;
    Memo1->Lines->Add(AnsiString().sprintf("%08lX : %lu", flag, time));

    time = timeGetTime();
    for ( i = 0; i < n; i++ ) {
        flag = init;
        count[NTZ2(flag)]++;
    }
    time = timeGetTime() - time;
    Memo1->Lines->Add(AnsiString().sprintf("%08lX : %lu", flag, time));
}

[測定結果]
80000000 : 2824   // ntz(): 実引数は未変更
000F0010 : 2404   // NTZ(): 実引数を破壊
80000000 : 11637  // NTZ2(): 実引数は未変更



この投稿にコメントする

削除パスワード

No.6496

Re:戻り値付き関数を引数付きマクロで代用
投稿者---かずま(2006/09/15 02:28:13)


> しかしよく考えてみると計算量が増えそうですね。

コンパイラによるんでしょうね。
gcc -O でコンパイルすると、最適化されて小さく速くなります。


この投稿にコメントする

削除パスワード

No.6512

Re:戻り値付き関数を引数付きマクロで代用
投稿者---かずま(2006/09/15 13:53:48)


> しかしよく考えてみると計算量が増えそうですね。

計算量を減らしたかったら、演算の個数を減らしましょう。これで関数
呼び出しのオーバーヘッドも稼げるから、マクロにしなくてもよいのでは?
int ntz2(ulong bits)
{
    bits = (bits - 1) & ~bits;
    bits -= bits >> 1 & 0x55555555;
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits + (bits >> 4)) & 0x0f0f0f0f;
    bits += bits >> 8;
    return (bits + (bits >> 16)) & 0x3f;
}
または
int ntz3(ulong bits)
{
    int n = 0;
    if (!(bits & 0xffff)) n = 16, bits >>= 16;
    if (!(bits & 0x00ff)) n += 8, bits >>= 8;
    if (!(bits & 0x000f)) n += 4, bits >>= 4;
    if (!(bits & 0x0003)) n += 2, bits >>= 2;
    if (!(bits & 0x0001)) n += 1, bits >>= 1;
    return n + (~bits & 1);
}



この投稿にコメントする

削除パスワード

No.6522

Re:戻り値付き関数を引数付きマクロで代用
投稿者---chu-(2006/09/16 02:13:54)


返信ありがとうございます。

> gcc -O でコンパイルすると、最適化されて小さく速くなります。

残念ながらgccの実行環境はありません。
コンパイラの最適化ってすごいですね。
あの巨大なプリプロセッサ出力コードをどこまで小さくしているのか興味が湧きました。

> これで関数呼び出しのオーバーヘッドも稼げるから、マクロにしなくてもよいのでは?

実際には、複雑なマクロは全く使いませんが、
制限の多いマクロでいろんなことをするのがパズルのようで楽しく、興味本位でした。

ntz3()によってずいぶん速くなりました。
ntz()の出力との全値(0〜0xFFFFFFFF)比較テストを行いましたが不一致はありませんでした。

すでに最適化されつくしたコードだと思い完全に思考が停止していたようです。
いい経験になりました。

表題の件については今のところそんなテクニックはなさそうなので、
SWAP()のテクニックを使って引数で戻り値を返す[NTZ4()]を組み、
実引数を破壊する問題は、引数にポインタを要求して警戒感を煽ってみましたが、
使い勝手が悪いですし、やはり微妙ですね。

[測定結果(BCB5:リリースビルド)]
80000000 : 2924   // ntz()
000F0010 : 2393   // NTZ()
80000000 : 2484   // ntz2()
80000000 : 1853   // ntz3()
80000000 : 1191   // NTZ4()

[NTZ4()]
#define NTZ4(/*[int *]*/bitno, /*[ulong *]*/bits) \
do{ \
    int n = 0; \
    if (!(*(bits) & 0xffff)) n = 16, *(bits) >>= 16; \
    if (!(*(bits) & 0x00ff)) n += 8, *(bits) >>= 8; \
    if (!(*(bits) & 0x000f)) n += 4, *(bits) >>= 4; \
    if (!(*(bits) & 0x0003)) n += 2, *(bits) >>= 2; \
    if (!(*(bits) & 0x0001)) n += 1, *(bits) >>= 1; \
    *(bitno) = n + (~*(bits) & 1); \
}while(0)

    for ( i = 0; i < n; i++ ) {
        flag = init;
        temp = flag;
        NTZ4(&ret, &temp);
        count[ret]++;
    }



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧





掲示板提供:(有)リアル・インテグリティ