>これって参照テーブルを使わないシバリかなんかかかってるんですか?
さ〜さんところで17命令で記述されているというシバリがあります(笑)。
FFTのビットリバースはテーブル参照してますけど
どっちがいいのかしらん。>酒居さん(^^;

あ・・・

気が付かなかった・・・

いくつか言い訳を考えて見ましたが無駄でした(笑)
くそー、BA=Bx2+A
に気が付いた時点で LEA に行くべきだったのかー
ビット道は奥が深いなぁ。

＞へるみさんの攻撃！
＞ビットマニアの称号をへるみさんに奪われた！

福地さん：
参照テーブルは2^32byte必要になるので却下(違
単に、森田さんが使ってなかったので使わなかった
だけです。ネタ的に面白くないかなーというのも
ありますが。

17命令のルーチンを「安直」と言えるへるみさんが凄い…。
(とっさには何やってるかわかんなかった。きっちりlea使える
形になってるし…)
これって参照テーブルを使わないシバリかなんかかかって
るんですか?その方がさらに安直だと思うんですが。(実効速度
はさて置き)

突然ですが、eaxのビットリバースって安直に
ebx = eax;
eax ^= 0x55555555;
ebx ^= 0xAAAAAAAA;
ebx >>= 1;
eax = ebx + eax*2;
ebx = eax;
eax ^= 0x33333333;
ebx ^= 0xCCCCCCCC;
ebx >>= 2;
eax = ebx + eax*4;
ebx = eax;
eax ^= 0x0F0F0F0F;
ebx ^= 0xF0F0F0F0;
ebx >>= 4;
eax <<= 4;
eax |= ebx;
bswap eax
ってのは駄目なんでしょうか。
ROR, ROLの多ビットシフト(遅い)を使うよりは
よいと思うのですけど。

いい音楽をたくさん聴きたい。

MP3を活用したい

以前に午後の不具合について書き込んだ者です。

沖縄はぼくの故郷なんですが、あの島は暑い事を除けば快適に過ごせる善い土地です。
皆さんも是非、堪能してください。
輸入物が格安で買えるんで、そのあたりチェックすると面白いですよ。

前の書き込み、名前とタイトルが化けてましたが、僕でした。
まぁEffecTVと書いた時点でばれてると思いますが。
SWoPPには残念ながら行けないのですが後輩が何人か行くので
話を聞いといてもらおっと。沖縄かぁ、いいなぁ…。

>でわ、へるみさんを発表者にしましょうかねぇ。
あわわ、ごめんなさい。それだけはご勘弁を(^^;

＞ 半分冗談みたいなもんです。

あ〜、んなこと書いてる。
でわ、へるみさんを発表者にしましょうかねぇ。

半分冗談みたいなもんです。
私はほとんど何もしてないし、そもそも仕事休めるのかという問題が(^^;

さ〜さん
>neg eaxではないですか(笑)
ちょっと最近アセンブラから遠ざかっていたのでろくな返事
してないですね(汗)。週末久しぶりに何か考えてみます。

午後のこ〜だ方面ではSWoPPで発表だそうですね。
かく言う私もEffecTV方面で「夏のプログラミングシンポジウム」
で画像処理小手先高速化について発表してきます。なんぞ面白い
ネタがありましたら教えていただけたら幸いです。

> >not eax
> >inc eax

ってゆーか、これは
neg eax
ではないですか(笑)

なぜ誰も気がつかない････

>not eax
>inc eax
>でもいけますね。

そうでしたね(^^;

ただいまP4の最適化マニュアル読んでます。
果たして役に立つことがあるのか???
#ネタには使えるか(^^;

久しぶりです。

> 逆向きのbit列
> 11...1100...0から
> 00...0100...0を作るのは少し前に書いた
> mov ebx, eax
> neg ebx
> and ebx, eaxでいけますね。
> これまた使い道が思いつきませんが(^^;

ふと気が付きましたが、
11...1100...0から
00...0100...0は、

not eax
inc eax
でもいけますね。

> ソフトウェアでUARTのエミュレーションを高速に処理したい時
> とかは役立ちそうですね。
それにはあらゆる種類の姑息なbit演算の高速な手段が役立ちそう
ですね。

> えと、複数回の立ち上がりも検出できます(^^;
> だからどうだと言われると使い道が思いつかないので
> どうということもありませんけど。

ソフトウェアでUARTのエミュレーションを高速に処理したい時
とかは役立ちそうですね。

> 立ち上がりの検出って
> 00...011...1っていうbit列から
> 00...010...0っていうのをのことでしょうか?
> inc eax
> rcr eax,1
> で駄目???

えと、複数回の立ち上がりも検出できます(^^;
だからどうだと言われると使い道が思いつかないので
どうということもありませんけど。

>これまた使い道が思いつきませんが(^^;
少し前のnifでnが2ベキであることの判定法として
紹介されていました。
(n>0)&&(n==(n&-n));
とか別解の
(n>1)&&(n&(n-1)==0);
とか
nが2べきであることが分かったら何が嬉しいかは
私は思いつきませんが(^^;

立ち上がりの検出って
00...011...1っていうbit列から
00...010...0っていうのをのことでしょうか?
inc eax
rcr eax,1
で駄目???
逆向きのbit列
11...1100...0から
00...0100...0を作るのは少し前に書いた
mov ebx, eax
neg ebx
and ebx, eaxでいけますね。
これまた使い道が思いつきませんが(^^;

初めての長期旅行から帰ってきました。
めっちゃ疲れてます。

寝起きに5秒で思いついたのですが、
使い道が思いつかないのでネタに
なりません。

EAX: 入力ビット列
mov ebx, eax
shr ebx, 1
xor ebx, eax
and ebx, eax

何かに使えませんかね。

> 問題は、ビデオカードから渡される画像データがVRAMに直で書き込まれる事なんだよなぁ。
>あれがメインメモリーに書き込まれるのだったらどれ程楽か。
>今の仕様のせいで32K色でダブルバッファリング表示する事もできない…。

静止画だとちょっときついかもしれないですが動画なら２５６ｘ２５６（横長）で
わりとまともに見えるんではないでしょうか。
元々、そんなに奇麗には取り込めないですし（^^;;

という訳で背景差分のコードを書いてみました。

unsigned int *p;//入力画像
short *q;//計算済み背景画像
unsigned char *r;//差分書き込み先
int t;//閾値

R = (*p&0xff0000)>>(16-1);
G = (*p&0xff00)>>(8-2);
B = *p&0xff;
v = R + G + B - *q;
//*r = (abs(v)>t)?0xff:0;
*r = ((v+t)>>24)|((t-v)>>24);

最後の行を工夫してみたのですが、いかがでしょう。

> とりあえず、TOWNS版を作ろうとは思ってます(^^;
> #あとハイレゾTOWNSのCRTCを知りたいのでLinuxのソース眺めてます(^^)
一段落したらTOWNS版にとりかかりたいなぁと思っていました。是非やりましょう。
問題は、ビデオカードから渡される画像データがVRAMに直で書き込まれる事なんだよなぁ。あれがメインメモリーに書き込まれるのだったらどれ程楽か。今の仕様のせいで32K色でダブルバッファリング表示する事もできない…。

ふぇりさん
>今はビデオカードでできてしまうので、
>メリットないかなぁとか思ってます。
それを言っちゃお終い(^^;というか↓のもSIMDを使えば楽勝ですしね。

福地さん
>へるみさん、EffecTVの開発に参加しません^^)?

とりあえず、TOWNS版を作ろうとは思ってます(^^;
#あとハイレゾTOWNSのCRTCを知りたいのでLinuxのソース眺めてます(^^)

> RGB->YCrCB変換は結構重い(今は軽いのか?)ので
> 2*R+4*G+Bをおおざっぱな鮮度の指標とする方法もありますね。

以前に同じこと考えてやってましたが、デコード(YCbCr->RGB)のことを
考えると、今はビデオカードでできてしまうので、
メリットないかなぁとか思ってます。
YUV 4:1:1とかだとビデオカードに転送するデータ量も半分(?)になります。

> 2*R+4*G+Bをおおざっぱな鮮度の指標とする方法もありますね。
これはいいですね。早速取り入れてみます。

> 以前、木目調の画像データにリアルタイム入力画像をレリーフ
> として埋め込むプログラムを書いたことがありますが、

へるみさん、EffecTVの開発に参加しません^^)?

>RGBじゃなくてYCrCbとかHSIとか、他の色系を試した方が
>良いかも。(実際、輝度だけで差分抽出してもそこそこの
>結果が出ます)

RGB->YCrCB変換は結構重い(今は軽いのか?)ので
2*R+4*G+Bをおおざっぱな鮮度の指標とする方法もありますね。

以前、木目調の画像データにリアルタイム入力画像をレリーフ
として埋め込むプログラムを書いたことがありますが、
そのときはRGB->YCrCB変換は`掛け算1回+半分だけテーブル引き'
が一番速かった気がします。

この辺のやり方を応用して背景差分(「ささやかな考察」のNo.16)
をうまくやれないかと試しています。基本的には、二値化と
同じ考え方でキャリーを捉え、正負反転のためのマスクを作る、
という手順を踏みます。ただ、ビットが逆なので一回反転しな
ければいけないのが悔しいところです。

で、結局No.16での結果と比べてたいして変わりませんでした。
閾値を下げると出てくるノイズは後でフィルタリング処理で
消す、という手段の方が良いのかもしれません。さらに、
RGBじゃなくてYCrCbとかHSIとか、他の色系を試した方が
良いかも。(実際、輝度だけで差分抽出してもそこそこの
結果が出ます)

> はい、そのつもりです。下一ビットが0であるという制限以外は
> 閾値は自由に設定できます。

そのかわりでもないですが、誤差がでないので
十分に使えそうですね。
閾値の２の補数を加えれば飽和加算と同様に
処理できます。そう考えると、閾値が0-127の
範囲なら飽和加算より多少短くなるですが。
bを閾値のバイトごとの２の補数[7bit]とする
例：閾値=0x123456 → b=0x6e4c2a
　　b=((~閾値) & 0x7f7f7f) + 0x010101;

a = p & 0x7f7f7f;
a = ((a + b) | p) & 0x808080;
a = ((a >> 7) + 0x7f7f7f) ^ 0x7f7f7f;

最上位ビットを捨てるよりは最下位ビットを
捨てたほうがいい気がしますけど(笑)

> > >...
> > >ではダメなのでしょうか?
> > 多分閾値を自由に変更できるというのが利点なんだと思います。
> はい、そのつもりです。下一ビットが0であるという制限以外は
> 閾値は自由に設定できます。そんなに細かく設定できてもあまり
> 使い途はないんですが。EffecTVの最新版で一箇所使ってます。

なるほど、やっと意図を理解できました。
大小比較でマスクを作るって、結構使い道ありそうですね。

> >...
> >ではダメなのでしょうか?
> 多分閾値を自由に変更できるというのが利点なんだと思います。
はい、そのつもりです。下一ビットが0であるという制限以外は
閾値は自由に設定できます。そんなに細かく設定できてもあまり
使い途はないんですが。EffecTVの最新版で一箇所使ってます。

>...
>ではダメなのでしょうか?
多分閾値を自由に変更できるというのが利点なんだと思います。
ふぇりさんの方法では2ベキしか閾値に取れないですよね。
#寝ぼけ頭なので間違ってるかも。

> 最近書いたコードから;RGB各8bitのピクセルで、RGBそれぞれで独立に
> 二値化(0か0xff)するというもの。
> p: ピクセルの値(RGB32)

p = p & 0x808080;
p = ((p>>7) + 0x7f7f7f) ^ 0x7f7f7f;

ではダメなのでしょうか?

最近書いたコードから;RGB各8bitのピクセルで、RGBそれぞれで独立に
二値化(0か0xff)するというもの。
p: ピクセルの値(RGB32)

a = p | 0x1010100;
a = (a - 0x808080) & 0x1010100;
a = a - (a>>8);

0x808080が閾値で、RGB独立に変更できます。細かく見ていくと誤差が
あるのですが、その辺が問われない場合であれば充分かと思います。
(このフィルターそのものが使い途に困るという話もありますが…)

自己レス
>最近CodeWarriorでPPCアセンブリ
>言語をいじってるのですが、
>うまくやってくれてなかなか優秀です。
最適化生成コードがバグバグで使えないことが判明。
最適化レベルにするとOSごと落ちます。使えん。

#4月から就職。
#小学生以来の学校生活うん十年(?)についに終止符が。
#といいつつ今ごろ論文書いてる奴。

> 最近CodeWarriorでPPCアセンブリ言語をいじってるのですが、
> それだと、
> vector float a, b, c;
> c = vec_add(a,b);
> みたいにかけます。しかもループ展開やレジスタ割り当ても
> うまくやってくれてなかなか優秀です。
> printf("c=%vf\n",c);ってやるとちゃんとレジスタの中身も出力されますし。

便利ですね。
GCCも目指してるのはそういうところみたいですが、まだ全貌はわかりません。
SIMD用のデータタイプ(というかマシンモード?)は定義されていて、
MMX/SSEのSIMD命令は、そのデータタイプ用の組み込み関数として定義されてる
ようです。

(なので、先に挙げたpaddd(pand(...),pand(...))という式はデータタイプが
違うために、実は組み込み関数ではコンパイルできなかったりするわけですが、
GCCではインラインアセンブラでレジスタ割当をコンパイラ任せにすることが
できるので、それを使った自前インライン関数で同等のことができます)

>なぜxorだけなのでしょう？
なぜなんでしょう?忘れました(^^;

>でも、 paddd(pand(psrlq(d0,1), mask),
>pand(d0, mask))
>みたいな式がコンパイルできるのはいいです。

最近CodeWarriorでPPCアセンブリ言語をいじってるのですが、
それだと、
vector float a, b, c;
c = vec_add(a,b);
みたいにかけます。しかもループ展開やレジスタ割り当ても
うまくやってくれてなかなか優秀です。
printf("c=%vf\n",c);ってやるとちゃんとレジスタの中身も出力されますし。

> >((A<B) AND (A-B))+B
> >のような式だったように思います。
> 福地さんのコードも基本概念はそれですね。

はい、福地さんのを見てから、そうか、こんな感じだったかも?と出てきたのが
上の式でした。(XORじゃないと動かないかも..?)

> 似たようなものだけど
> eax=a
> ebx=b
> xor ecx, ecx
> sub eax, ebx
> adc ecx, byte -1
> and eax, ecx
> add eax, ebx
> ではどうかしらん。xorを遠くに置けば気持ち早くならないかな。

遠くに置くというのは、P6用に依存関係を少なくしたいということでしょうか?
なぜxorだけなのでしょう？

>((A<B) AND (A-B))+B
>のような式だったように思います。

福地さんのコードも基本概念はそれですね。
似たようなものだけど
eax=a
ebx=b
xor ecx, ecx
sub eax, ebx
adc ecx, byte -1
and eax, ecx
add eax, ebx
ではどうかしらん。xorを遠くに置けば気持ち早くならないかな。

マスクを作ってスプライトと同じようにやればいいわけですね。
ありがとうございました。

私が見た(ような気がしていた)のは昔のBASICで
((A<B) AND (A-B))+B
のような式だったように思います。

GCCといえば、3.0ではMMX/SSEがサポートされるようですね。
これが使ってみたいばかりに、CVSのスナップショットではsegfaultするばかりで
まともに動かないため、RedHatのGCC 2.96にMMX関連のパッチだけを
あてたものを作ってみたりしたのですが、とても使える品質のコードを吐く
コンパイラはできませんでした。
(中間値をedx:eaxに保存して、スタック経由でMMXレジスタに入れようとしたり...)
でも、 paddd(pand(psrlq(d0,1), mask), pand(d0, mask))
みたいな式がコンパイルできるのはいいです。
3.0のリリース時にはまともになってることに期待しています。

>この掲示板のどこかに書いてあったような記憶があるのですが、
>探すのが面倒なので書いてみました。

耳が痛いです(^^;
最適化なんて所詮は個別理論だからまとまりがなくなるのは仕方ないとは
思いますが、クリッピングやマスク関係をBBSの過去logにほっておくのは
もったいないと思うのでそのうち発掘して整理しようと考えています。

下のコードをgccにかけたらもっと素敵なコードに変換して
くれました。
max(a,b)
x=a-b;
y=(c>>31)-1;
return(x&y)+b;

もちろん、二行目がdec regになる訳です。ちなみに、簡単な
ベンチマークプログラムを書いて-O3でコンパイルしたら、
ループごと消えてしまいました(ループの内側にc=max(a,b)としか
書いてなかった為か)。

この掲示板のどこかに書いてあったような記憶があるのですが、
探すのが面倒なので書いてみました。

max(a,b)
x=a-b;
y=0xffffffff+(x>>31);
return (x&y)+b;

2行目で即値を使っているのが弱いですね。

はじめまして。
ここを読んで皆さんのテクニックに驚かされています。

ところで、max(a,b) (で分かりますよね?) を分岐を使わないで計算する式があったと思うのですが、どうしても思い出せません。
みなさんならどうやるのでしょう?
(cmovはなしということで)

お久しぶりです。
ビデオエフェクトは昔からとても興味があるのですが、
友達に借りたビデオカメラを壊してしまって以来(汗)
ご無沙汰してます。

>ここの記事を読んで、ついつい中毒的にのめり込んでしまい
>ました。

はまってやってください(笑)
過去のBBSでは何人かの方がすごいテクニックの紹介&閃き
がありましたね。

## 下のPIII vs. PPCのPPCのclockは8clcokほど余計に加算していた
## 可能性があります。というわけでその分PPCのを減らして読んでくださいm(__)m

そこそこ速いマシン(Athlon600)で開発していたため、Cで
思いつくままに適当に組んでも30fps出てたのであまり最適化
(というよりかは高速化)の努力を払っていなかったのですが、
ここの記事を読んで、ついつい中毒的にのめり込んでしまい
ました。研究室の老頭児も巻き込んで盛り上がっています。

今はとりあえず速度よりもコードの読みやすさと保守性の高さ
を追及する段階なのですが、TOWNSに移植する際にはカツカツの
高速化に取り組まざるをえないだろうなぁ。面白い最適化のネタ
振りができれば幸いです。

こんにちは、福地と申します。TOWNS方面では、ここの常連の
方々に一度くらいはお目にかかった事があるかと思います。

最近、昔TOWNSで作っていたビデオエフェクターをlinuxで
動くようにしてみました。中身を見ていただければおわかり
いただけるかと思いますが、自分ではかなり「そそる」もの
があると思っています。
実際、飽和加算について散々考えたあげくに作り出したもの
とほぼ同じアイディアが過去ログにあったりして、しまった
もっと早く見ときゃよかったと思ったりしています。
今のバージョンはまだまだ最適化の余地がありますので、
存分にいじっていただければ幸いです。linuxが動くマシン
でビデオキャプチャーカードをお持ちの方は、是非開発に
参加していただきたく思います。

また、これをTOWNSに移植する作業も始めたいと思っており
ますので、TOWNSハッカーの方にも参加してもらえると嬉しく
思います。(さらにWindowsに移植してくれる方も募集中…)

そのソース
<pre>
/* for x86 */
proc nextC_A
mov eax, [esp+4]
test al, 1
jz .even
.odd:
lea edx, [eax+1] ;a+1
xor edx, eax ;b
lea ecx, [edx+1] ;b+1
shr edx, 1 ;b/2
bsf ecx, ecx
sub edx, eax ;-c = b/2 - a
mov eax, edx ;-c
neg eax ;c
and edx, eax ;c&-c
shr edx, cl ;(c&-c)/(b+1)
sub eax, edx ;c-(c&-c)/(b+1)
ret
.even:
mov ecx, eax
neg ecx
and ecx, eax
shr ecx, 1
sub eax, ecx
ret

/* for PPC */
uint32 nextC_A(uint32 a){
asm{
clrlwi r0, r3, 31
cmplwi r0, 0
beq even
odd:
addi r0, r3, 1 // r0 = a+1
xor r4, r3, r0 // r4 = b = a ^ (a+1)
srwi r0, r4, 1 // r0 = r4/2
sub r3, r3, r0 // r3 = c
neg r0, r3 // r0 = -c
and r0, r3, r0 // r0 = c &-c
cntlzw r4, r4
subi r4, r4, 32
neg r4, r4 // r4 = 31 - r4 = bfs(r4)
srw r0, r0, r4 // r0 = (c&-c)/(b+1)
sub r3, r3, r0
blr
even:
neg r0, r3 // r0 = -a
and r0, r3, r0 // r0 = a & -a
srwi r0, r0, 1 // r0 >>=1
subf r3, r0, r3
blr
}
}
</pre>