せっかちな人々(まったりも可)

せっかちな人々(まったりも可)

どんなささいなことでも構いません.
面白い最適化のアイデアがありましたら書き込んで下さい.
無論雑談も大歓迎です.

管理者公開画面｜管理者削除画面｜管理者ダウンロード画面｜日付順表示｜スレッド表示｜トップページに戻る｜ヘルプ

｜メッセージボードを変更する｜　

投稿記事の削除を行う管理者ページです。
投稿記事の公開、ダウンロードを行う場合は上記リンクをクリックしてください。

削除したい記事の削除チェックボックスをチェックしてください。まだ公開されていない記事は投稿番号（no.)が太字で表示されています。削除する記事を選択したら「削除」ボタンを押してください。
　

次へ ← 609-692 / 240 件表示 → 前へ

件／頁　　　

すべてのチェックを / 　　　


no.　｜　subject　｜　name　｜　url　｜　date	削除

692.　Pentium4のMMXについて　yosirin-hello　URL　　2002/09/17 (火) 13:02

へるみさん、お久しぶりです。
今、MersenneTwister(htp://www.math.keio.ac.jp/~matumoto/mt.html)
のSSE2化ができないかどうか考えています。

それで、Cで書かれたプログラム(http://www.math.keio.ac.jp/matumoto/CODES/MT2002/MTARCOK/mt19937ar-cok.c)とMMXで高速化されたプログラム(http://www.bellew.net/rand/MMXRand.html)
とstdlibのrand()の性能を計測して、どれくらいMMX版の方が高速なのか試してみました。

実験結果は以下のようになりました。
(100,000,000個の乱数を生成する時間を計測)
// 実行結果(Pen4 1.5GHz)
// COK randomMT 2.4840[sec]
// MMX randomMT 3.6450[sec]
// Normal rand 2.2740[sec]
//
// 実行結果(Pen2 233MHz)
// COK randomMT 20.3190[sec]
// MMX randomMT 7.8510[sec]
// Normal rand 5.2680[sec]
//
// 実行結果(celeron 433MHz)
// COK randomMT 7.9100[sec]
// MMX randomMT 3.2300[sec]
// Normal rand 1.8700[sec]

何故かPen4のMMX版の方がCOK randomMTよりも遅い結果が出ました。
他のマシンではMMX版の法が高速に動作していました。（←予想通り）

原因は何だと思いますか？
MersenneTwisterは論理演算を多用するので、Pen4のRapid Execution Engineの効果がMMXよりも大きいということなのでしょうか？

実験したソースをここに置いておきました。
http://isweb9.infoseek.co.jp/art/yosirin9/beta/MT_test.zip

691.　Re^2: レジスタによって、速度は違いますか？　へるみ　2002/08/28 (水) 21:55
> ６本ある汎用レジスタの内、ebx, edi, esiの３本は、関数内で値を変更してはいけない規定になっています。ライブラリによっては使えなかったりするようですが私は ebp も使っちゃいます。あと eax を使うと他のレジスタに比べて1byte命令長が小さくなることがありますね。

690.　Re: レジスタによって、速度は違いますか？　ＱＷＥＲＴＳ　 URL　　2002/08/28 (水) 21:22

> コンパイラが吐き出すコードはeax,ecx,edxが
> 主に使われているようなのですが、
> ebx,ediなどを使うことに何か問題があるのでしょうか？

６本ある汎用レジスタの内、ebx, edi, esiの３本は、関数内で値を変更してはいけない規定になっています。

すなわち、関数内でこれらのレジスタを使う場合は、値をスタックに退避しなければなりません。

そのため、push, pop等の操作が必要ないeax, ecx, edxが主に利用されます。

687.　面白そうな話なので参加　うるり　2002/07/04 (木) 00:05

YUKIさんT98-Nextの開発お疲れ様です。
以前から音源部などがSIMD対応しそうだなぁと思ってました。
あ、どうでも良い話が長いですね(^^;

メモリアクセス速度が問題のようですが、グラフィックボード上の
メモリはキャッシュが効かない事があるので、直接読み書きしない方が
良いかもしれません。
仮想の画面メモリを用意してそこを読み書きして、表示時にのみ
グラフィックボードに転送する方法も考えられます(ただ、仮想画面が
キャッシュをはみ出る、仮想画面<=>VGA間転送が遅い、VGA内の高速転送が
使用できない、などの副作用の方がきついかもしれません^^;)

256要素毎に処理して作業用バッファに書き出し、バッファからVGAに転送する、
を繰り返す方法も効果があるかもしれません。(ないかもしれない^^;)

結局、(1)メインメモリ(CPU)<=>VGA間転送が遅い、(2)メインメモリ上でも
キャッシュをはみ出ると遅い、この2点がどうにもならない可能性が
あります。この場合は他の方が指摘されているように複数の処理を
一度に集めて処理する(処理のレイテンシを増やす)ようにしないと、
どーにもなりません。
＃パソコンの限界性能は速くなってもこの手の処理は速くならないんだよなぁ。

686.　いろいろありがとうございます　YUKI　URL　　2002/07/03 (水) 22:33

YUKIです

>水平同期にあわせて変更されるなどの・・・
無いことも無いですが、実装ははっきり言って不可能なので（出来なくも無いけど）実装はしてません
しかしながら、データは変更せず、パレットのみいじってフラッシュさせるなどの、さまざまな効果を出しているものは多く居ます
16Bitカラー以上だと、必ず色とデータが一対一になってしまうので、全部書き換える以外に道はありません

また、書き込み先がDirectXのLOCKされたバッファーなので、レイテンシが物（カード）によって違ったりいろいろです

AGPならよい結果を得ますが、メインメモリと共用のオンボードも多いので（エミュ使うような方は、VGAカードくらい入れてると思いますが　滝汗）いずれにせよ帯域は厳しいです

他の処理と並列するにも、なかなか難しいですね・・・

帯域がこんなに曲者とは思いませんでした
今まで、処理とレイテンシだけ考えていたので（やっぱりそういう部分は非常に多いです）見逃してました

ちっと考えればわかるような、無駄な題材で、申し訳ありませんでした
YUKIのレベルの低さが、ばれちゃいましたね（苦笑

685.　Re^2: これだけでも苦労したりして　へるみ　2002/07/03 (水) 00:15
> もし可能なら src1 や src2 の中味を作っているループとこのループをマージするとメモリアクセス的に楽かもしれないですね．そうですね。ただ200%憶測ですがその場合はパレットが水平同期にあわせて変更されるなどのアクロバティックなソフト(あるのか?)への適応は難しいでしょうね。

684.　Re: これだけでも苦労したりして　計　 URL　　2002/07/02 (火) 22:14

> for (i=0;i<256*1000;i++)
> {
> 　if (src2[i])
> 　　dst[i]=pal2[src2[i]];
> 　else
> 　　dst[i]=pal1[src1[i]];
> }

前後の処理がわからないので，100%憶測ですが．

もし可能なら src1 や src2 の中味を作っているループとこのループをマージするとメモリアクセス的に楽かもしれないですね．src1 や src2 の中味も保存しないでも済むかもしれないし．

683.　Re: メモリが原因とは・・・　へるみ　2002/07/02 (火) 15:44
> メモリアクセスがボトルネックになって、どうにもならないという結論に達しました（汗そうですね。試しに prefetch や pextrw+pinsrw も試してみましたが殆ど変わらず。同様の経験では24bitRGB=>32bitRGBA変換を MMX 使ってやってみたけど報われないというのがありました。

682.　メモリが原因とは・・・　YUKI　URL　　2002/07/02 (火) 12:37

福地さん、アドバイスありがとうございます

実は自己解決しました
メモリアクセスがボトルネックになって、どうにもならないという結論に達しました（汗

御察しのとおり、何もしないのが吉のようです・・・

>何かのエミュレータ
私の作っているPC98エミュレータのコードです
現在、多くの部分をMMXで高速化中です

681.　何もしないというのは　福地　2002/07/02 (火) 12:27
分岐予測が外れる心配をあまりしなくてもよく、またパレットが16色とかその程度なのであればキャッシュのノリも良いだろうし、何もしないってのもアリじゃないですかね。あ、命令間の依存度が高いのが問題なのか。ところでこれは何かのエミュレータですか?

680.　これだけでも苦労したりして　YUKI　URL　　2002/07/01 (月) 20:58

連続投稿、申し訳ありません

WORD *dst;
WORD *pal;
BYTE *src;
for (i=0;i<256*1000;i++)
　　dst[i]=pal[src[i]];

何気に、これだけでも苦労したりします
まずはこっちから取り掛かったほうがよろしいかと（汗

あと、先の投稿にはミスがあり実際はこのソースです

WORD *dst;
WORD *pal1;
WORD *pal2;
BYTE *src1;
BYTE *src2;
int i;

for (i=0;i<256*1000;i++)
{
　if (src2[i])
　　dst[i]=pal2[src2[i]];
　else
　　dst[i]=pal1[src1[i]];
}

要は、パレットも２種類居ます
実際は、src2のほうには、ほとんど分岐しないので、レジスタが足りなくなることはありません
分岐の比率は、src2は、ALL0の場合がほとんどです　＜なんだそりゃ！

679.　はじめまして♪　YUKI　URL　　2002/07/01 (月) 20:47

はじめまして、YUKIと申します

面白い最適化の、アイデアということで、一つ挙げさせてください

・パレットの画像を、RGBの画像に展開するアルゴリズム
です

これを、256K要素繰り返します

BYTE型の配列があり、これをWORD型の配列に展開します
このとき、WORD型の配列であるパレットをBYTE型でIndexします
ただ、一点、曲者物が居て、ソースが二つあり、ソース２は0でないときは、優先させるというものです

説明しにくいので、Cで書くと

WORD *dst;
WORD *pal;
BYTE *src1;
BYTE *src2;
int i;

for (i=0;i<256*1000;i++)
{
if (src2[i])
dst[i]=pal[src2[i]];
else
dst[i]=pal[src1[i]];
}

これだけ、です

わたしも、多くの最適化は行っているのですが、最近のCPUではついていけません（笑
皆様のお知恵をお借りしたいと思います

自分で作った限りでは、MMXに読み込んでも、パレット参照する部分で、ボトルネックのような・・・
分岐が曲者・・・
結局、C++の最適化に勝てそうに無いです　T_T
あと、に分岐は、src2の内容は、ほぼ0で1の場合は稀です
（0固定で予測して外れても、たいした回数ではありません）

ちなみに、自分の作っているソフトの、ちょっとした部分です
これ以外のところは、効率よく最適化できているのですが、このループばかりはどうにもなりません（汗

671.　Re^3: パイプライン　へるみ　2002/05/27 (月) 22:12

> なるほど。CPUの処理はそこで言うEだけではなくてFやDのような、結果が出ていなくてもできることもあるのですね。

整数用レジスタは見た目は8個ですが内部にはたくさんあってx86-opがRISC-uopに変換されるときに適当に割り振られて命令順序を入れ替えて演算されるそうです。
その後依存関係をクリアにしてから8個のレジスタに復元してretireするんですがいったいどういうからくりなのか想像もつきません。

670.　Re^2: パイプライン　とっこ　2002/05/27 (月) 13:23

ありがとうございます。
なるほど。CPUの処理はそこで言うEだけではなくてFやDのような、
結果が出ていなくてもできることもあるのですね。

しかし、FやDやRが細かくなり段数が15～20になるとは。
ほとんどEだけに時間を使っているのだと思っていました。
だから最近のCPUではEも細かくせざるを得なくなってFPUの
レイテンシが長くなっているのですかね。

669.　Re: パイプライン　へるみ　2002/05/24 (金) 23:19

> はっきり言ってしまえば、パイプラインが10段ならすべての命令の
> レイテンシが10になり
パイプラインの段数とレイテンシとは直接は関係がないと思います。
例えば仮想的にF(etch), D(ecode), E(xec), S(tore), R(etire)というパイプラインがあって実行部が先日の
addps=[addssH:addssL]
みたいだったらパイプラインがスムーズに流れていると
ＦＤＥＥＥＳＲ (L1)
＿ＦＤＥＥＥＳＲ (H1)
＿＿ＦＤ＿ＥＥＥＳＲ (L2)
＿＿＿ＦＤ＿ＥＥＥＳＲ (H2)
＿＿＿＿ＦＤ＿＿ＥＥＥＳＲ (L3)
＿＿＿＿＿ＦＤ＿＿ＥＥＥＳＲ (H3)
...
という感じになって平均的にはレイテンシ3で動いています。
AthlonやP4みたいにFやDやRが細かくなり段数が15～20(?)になっても原理は同じです。
けれども分岐予測が外れればそれまでしていたFやDが全て破棄してやり直しになるのでパイプラインが満たされるまで出てきません(ペナルティが発生)。
ホースで水を出しているとき水の勢いはホースの長さに無関係ですが、一度水を止めてもう一度流しだすときはホースが長いと出てくるまで時間が掛かるようなものかな。
#あってる?

668.　パイプライン　とっこ　2002/05/24 (金) 13:20

再びお邪魔します。

また質問をさせて頂きたいのですが、
パイプラインが10段だったら分岐予測が外れたときに
おおざっぱに言って10clk損します。
それなら、faddが3-1のタイミングというのは、3clk経つと計算結果が使えるようにはなっても本格的に(？)終わるのはやはり10clk後ということなのでしょうか。

はっきり言ってしまえば、パイプラインが10段ならすべての命令の
レイテンシが10になり、レイテンシの短い命令ばかりなら分岐予測が
外れても大したペナルティもないと思えてしまうのです。
どうなのでしょうか・・・

667.　Re^11: P6のSSE　とっこ　2002/05/17 (金) 13:43
お忙しい中僕の話に付き合ってくださり、ありがとうございました。これからも来たいと思うのでよそしくおねがいします。

666.　Re^10: P6のSSE　へるみ　2002/05/16 (木) 21:29
> ところでここのMMX2の解説がしてあるところで > movqntqという命令がありますがこれはmovntqではないでしょうか。ありがとうございました。訂正しておきます。

665.　Re^9: P6のSSE　とっこ　2002/05/16 (木) 11:12

> 割り算が高速にできる
なるほど。それは大きいですね。1loopあたりで1clk単位の最適化をしているときに割り算なんかに入ってこられたらもう意味がないというか、むなしい気分になりましたし。

ところでここのMMX2の解説がしてあるところで
movqntqという命令がありますがこれはmovntqではないでしょうか。

664.　Re^8: P6のSSE　へるみ　2002/05/15 (水) 21:55
>MMXは非常に役立ったのですがSSEの使い道があまりないです。整数演算主体だとどうしてもSSEは使いにくいですね。ただmpegの量子化などの割り算がたくさんある処理では整数<=>小数の行き来のコストを考慮しても割り算が高速にできる恩恵の方が大きいです。

663.　Re^7: P6のSSE　とっこ　2002/05/15 (水) 10:10

> andpsは本当に2-2
そんな感じがしますね。でもただのandに何で2clkなのでしょう。
将来のPen4でクロックを半分にするから？
(Pen4のSSEってスループットもレイテンシもmov以外みんな偶数なところからしてクロック半分ですよね？)

addpsとmulps同時実行はできました。理想状態にすれば相当いけますね。実際のコードでは難しそうですが。

まあ、SSEはスループットが２なのでレイテンシが簡単に隠れます。
結局レジスタがでかいことの恩恵ですね。
FPUではストールをなくすのはきつかったので。
もっとも、ストールをなくすことじゃなくて実行速度が目的ですから1clkぐらいストールしていても本当はいいんですが。

SSEを使えるようになったはいいものの、MMXは非常に役立ったのですがSSEの使い道があまりないです。いつの間にか目的と手段がごっちゃになっていますね。

662.　Re^6: P6のSSE　へるみ　2002/05/13 (月) 23:49

>実はaddpsはデコーダによってaddphsとaddplsに分解されて実行されている。
mulpsも実は(4-1)x2=5-2と考えると
addps xmm0, xmm0
mulps xmm0, xmm0
が連続した場合に1命令辺り3.5clkになるのも納得いきますね。
andpsも(1-1)x2=2-2と考えると
addps xmm0, xmm0
andps xmm0, xmm0
は2.5clkになりそうですが実測値は3clkなのでandpsは本当に2-2
なのかな(andssが無いのはそういう意味か?)。

660.　Re^5: P6のSSE　へるみ　2002/05/13 (月) 21:36

>僕は、addps xmm0,xmm0を繰り返すような並列性の全くないコードではレイテンシは原理的に隠せないと思っているのですが。
はいそうです。おもいっきり勘違いしました。すいません。

>実はaddpsはデコーダによってaddphsとaddplsに分解されて実行されている。
>http://www.softek.co.jp/CLSTML/200102/msg00003.html
にもそれっぽいことがかいてありますね。
ここらへん、うるりさんがお詳しいのでできれば登場お願い(^^;

659.　Re^4: P6のSSE　とっこ　2002/05/13 (月) 12:20

> 立てこんでいて返事が遅くなってすいません。
いやいや・・個人的なことに丁寧に答えてくれてこちらこそありがとうございます。
> うーん、法則性がわからん(^^;
僕の勝手な予想です。
xmh0をxmm0の上位2つ、xml0をxmm0の下位2つとして、
addphs xmh0,xmh0
addpls xml0,xml0
がaddps xmm0,xmm0と同じ動作となる。
実はaddpsはデコーダによってaddphsとaddplsに分解されて実行されている。addphsのレイテンシ－スループットは3-1で、addphsとaddplsをオーバーラップさせると4-2になる。ただし、addps xmm0,xmm0を連続してやるとxml0の結果が出ていないうちからxmh0を使った計算はできるのでレイテンシが隠され、3-2になる。
というものです。
> ただループさせて計測している限りはレイテンシを算出することは(隠蔽されるので)不可能な気がするのですが間違ってますか?
僕は、addps xmm0,xmm0を繰り返すような並列性の全くないコードではレイテンシは原理的に隠せないと思っているのですが。
> なふうにすると1命令あたり1.5clk程度だったので並列実行されています。
試してみます。ちなみに僕はCoppermine-128kの400MHzです。いまどき珍しく倍率がたったの4倍。だから、ここだけの話、午後べんちをやるまで66*6のMendocinoだと思ってました。みすみすSSEを捨てるところだったよー（あぶなかったです）。
> xorps xmm0, xmm0
これを入れればオーバーフローの心配ないですね(笑)

658.　Re^3: P6のSSE　へるみ　2002/05/12 (日) 22:37

立てこんでいて返事が遅くなってすいません。
私も実験してみました(PIII)。
xorps xmm0, xmm0
mov ecx, 10000
lp:
??? xmm0, xmm0
...(10回同じ)
??? xmm0, xmm0
dec ecx
jnz .lp
()内はマニュアルのレイテンシ-スループット
addps(4-2) => 3clk/1命令辺り(平均)
addss(3-1) => 3
andps(2-2) => 2
mulps(5-2) => 4
mulss(4-1) => 4
うーん、法則性がわからん(^^; addps と mulss を比べるとどうみてもmulss の方が速いように思えるのですが。
命令デコーダは1clockに3つしかデコードできないことや{add, mul}ssは{add, mul}psに比べて命令長が1byte長いことが複雑に絡んでるんですかね。すいません今私は答えられません。もしかしたらマニュアルが出た頃のKatmaiと今のCoppermineで変わったという可能性もありますけど。
ただループさせて計測している限りはレイテンシを算出することは(隠蔽されるので)不可能な気がするのですが間違ってますか?

>あと、addpsとmulpsは実行ユニットが違うと思うのですが、同時実行>できないのでしょうか？
addps xm0, xm0
addps xm2, xm2
addps xm0, xm0
addps xm2, xm2
addps xm0, xm0

mulps xm1, xm1
mulps xm3, xm3
mulps xm1, xm1
mulps xm3, xm3
mulps xm1, xm1
なふうにすると1命令あたり1.5clk程度だったので並列実行されています。

657.　Re^2: P6のSSE　とっこ　2002/05/09 (木) 11:15

> どうやって算出されました?
mov ecx,10000
lp:
addps xmm0,xmm0
subps xmm0,xmm0 ；足してばっかだとオーバーフローしてclk数がめちゃくちゃになって悩みました・・・
・；上の2行の繰り返し
・
dec ecx
jnz lp
これでループの中に入れる命令の数を変えて、20命令のときのclk数から10命令のときのclk数を引いて算出しています。addpsした結果がsubpsで使えるようになるまでは3clkに見えます。
addpsで3-2、mulpsで4-2でした。でもaddpsしてからandpsできるようになるまでのレイテンシは3ではなく4でした。やっぱりaddpsは3-1の2要素の足し算を2回しているとしか見えないんです・・・。
あと、addpsとmulpsは実行ユニットが違うと思うのですが、同時実行できないのでしょうか？僕のやったかぎりではaddpsとmulpsをどうまぜても1命令/2clkのスループットしかでません。

> 厳密に測定するのはなかなか難しそうです
10000回のループで75000clkとか83333clkとかになるときがあるんですけど・・・。先読みがはげしいのでしょうか。そのわりに命令をちょっと並べ替えただけで遅くなったりして、あれ？スケジューリングしてくれるんじゃないの？とか思ったり。

うーん。自分の意見ばっかり書いてすみません。でもMMXと比べてSSEはなんか変ですねえ。

656.　Re: P6のSSE　へるみ　2002/05/08 (水) 23:40

>addpsは4-2のクロックタイミングなのに
>addps xmm0,xmm0を繰り返すとなんだか
>3clk/回で済んでしまいます。
どうやって算出されました?
ノーマルペンティアムの頃だと2命令で1clock
だったので測定できましたがPIIIでは厳密に
測定するのはなかなか難しそうです。

それに最近のCPUはかしこくなったので私はあんまり
気合をいれなくなってしまってCPUのデコーダ
やスケジューラに任せてしまってます。
#だから「ぬるい」と言われるのですが(^^;

メモリアクセスが入ると予想したクロックになる
ことはまず無いですね。難しいです。

655.　P6のSSE　とっこ　2002/05/07 (火) 16:03

はじめまして
僕は今までVBで色々作っていたのですが、このページで前から使いたかったMMXを覚えて、VC++の_asm{}でアセンブラを書いています。ちなみにCはほとんどわかりません(笑)DLLにしてVBから呼んで使っています。

ライフゲームとか画像処理とか、あらかたMMX化してVBのネイティブコードコンパイルより２～１０倍も速くなり感動です。もっとも、VBのｐコードコンパイルは更に数十倍遅かったですが。

最近SSEも使ってみたのですが、addpsは4-2のクロックタイミングなのにaddps xmm0,xmm0を繰り返すとなんだか3clk/回で済んでしまいます。P6のSSEは複数命令にデコードされると聞いたので、思ったのですが、これは２要素に対する3-1の計算を２回しているのでしょうか？

レイテンシやスループットをちゃんと測れているのかもわからないのであれですが、デコーダとか実行ユニットとかメモリの遅さとか、ちゃんとデータを知ってないと最適化できないですね。これだ！というコードを書いてもなかなかこっちの期待したclk数では完了してくれませんのです。

654.　補足　dsk　2002/04/22 (月) 13:13

途中の式の右辺第4項目以降は
(2/189)(x_n)^4 + (1/675)(x_n)^6 + ..... <
(2/189)( (x_n)^4 + (x_n)^6 + (x_n)^8 + ..... ) <
(2/{27n^2})(1 + 3/n + (3/n)^2 + .... ) =
(2/{27n^2})/(1 - 3/n) = 2/{27n(n-3)}
であるから、そのｎに関する総和は、
Σ(n=4,∞) 2/{27n(n-3)} = 11/243で抑えられる。

よって、 1/(x_n)^2 の支配項は n/3 であるから、1/x_n ～ N
となるｎは n ～ 3N^2となる。
よって答えはスモールO記法を用いると3N^2 + o(N^2)となる。

653.　Re: 17日の　dsk　2002/04/22 (月) 12:22

(x/sin(x))^2 = 1 + (1/3)x^2 + (1/15)x^4 + (2/189)x^6 + ....
だから　
(x/sin(x))^2 ＞ 1 + (1/3)x^2
x = x_nを代入すると、
1/(x_n+1)^2 ＞ 1/(x_n)^2 + 1/3
{1/(x_n)^2}は n/3よりは速く大きくなる。よって、
元の式にx = x_nを代入して、
1/(x_n+1)^2 = 1/(x_n)^2 + 1/3 +(1/15)(x_n)^2 + (2/189)(x_n)^4 + ....
＜ 1/(x_n)^2 + 1/3 + 1/(5n) + 2/(27n^2) + ....
だからn/3 + (log n)/5 よりは遅く大きくなる。

よって　lim(n→∞）{1/(n(x_n)^2)} = 1/3 ■

652.　17日の　dsk　2002/04/22 (月) 11:13
> xが十分小なら tan x <= x それはおかしいよ。 f(x) := tan x とすると、 f'(x) = 1 + tan^2 x だから f'(0) = 1 でもって f''(x) = 2tan x(1 + tan^2 x) > 0 (x > 0) だから x > 0 のとき下に凸で、y = f(x)は y = x に原点(変曲点）で接し、x > 0 では　y = x より上側にある。よって、　tan x > x (x > 0) ■

651.　avgを使うなら　dsk　2002/04/18 (木) 10:53

たぶんこれが最速。でもunpackに負けてる。

p = avg(x, y);
q = avg(z, w);
r = (x^y)&0x1010101;
s = (z^w)&0x1010101;
p -= r;
q -= s;
t = avg(p, q);
t += r&s;

avg以外の計算はどのレジスタでやってもOKです。8bit単位で
桁あふれをおこさないものばかりなのでmmx演算である必要は
ありません。mmxばっかり使うと以下のように。同時実行性は
高いと思います。

mm0 = [x]
mm1 = [y]
mm2 = [z]
mm3 = [w]
mm4 = mm0
mm5 = mm2
mm6 = mm0
mm7 = mm2
mm4 = avgb(mm4, mm1)
mm5 = avgb(mm5, mm3)
mm6 &= mm1
mm7 &= mm3
mm6 &= #0x1010101
mm7 &= #0x1010101
mm4 -= mm6
mm5 -= mm7
mm4 = avgb(mm4, mm5)
mm6 &= mm7
mm4 += mm6
[x] = mm4

650.　下の　dsk　2002/04/17 (水) 20:14
うそでした。後で考えます。

649.　日記の　dsk　2002/04/17 (水) 20:09

駄目だ遅そう。ちなみに単純な１では、x,y,z,wのうち「LSB」が
1であるものの数が1のときに限り意図より1多く計算され、それ
以外のときは正しく計算されます。
１．x, y, z, w に f(f(x,y),f(z,w))の形で命令を摘要する。
２．x, y, z, w をそれぞれ0x1010101でmaskし合計する。
３．２と0x1010101のANDをとる
４．２を1ビット右シフトし、0x1010101とANDしてビット反転
　　(0←→1)する
５．３と４のANDをとる
６．１から５を引く

648.　Re^5: 日記　へるみ　2002/04/13 (土) 00:18
ねばったけど計さんの素直なコードが一番短かった(^^; 無念...

647.　Re^4: 日記　計　2002/04/11 (木) 22:11

参考にならない上にバグってる可能性大のpunpcklbwしない方法(^^;;
movd mm0, [x]
movd mm1, [y]
movd mm2, [z]
movd mm3, [w]
movq mm4, mm0
movq mm5, mm1
movq mm6, mm0
movq mm7, mm1
pxor mm0, mm2
pxor mm1, mm3
pand mm4, mm2
pand mm5, mm3
pavgb mm6, mm2
pavgb mm7, mm3
pxor mm0, mm1
por mm4, mm5
pand mm0, [MASK] ; MASK dd 0x1010101, 0
pavgb mm6, mm7
pandn mm4, mm0
psubusb mm6, mm4
movd [X], mm6

pavgb を連ねると1大きくなっちゃうことがあるわけで，それをさくっと判定して後からその分を引いちゃえばいいんだろうけど，さくっと判定するロジックが思いつかず．

646.　Re^3: 日記　へるみ　2002/04/11 (木) 15:49
> 降参^^;;punpcklbw して普通に計算しちゃダメ？^^;; やっぱそうするしかないんですかね. もちっとすぱっとできる方法ないかなあ...

645.　Re^2: 日記　計　2002/04/10 (水) 19:26
降参^^;;punpcklbw して普通に計算しちゃダメ？^^;; pxor mm7, mm7 movd mm0, x movd mm1, y movd mm2, z movd mm3, w punpcklbw mm0, mm7 punpcklbw mm1, mm7 punpcklbw mm2, mm7 punpcklbw mm3, mm7 paddw mm0, mm1 paddw mm2, mm3 paddw mm0, mm2 paddw mm0, [Q_iw2] psrlw mm0, 2 packuswb mm0, mm7 movd [X], mm0 って．こんなベタベタで良ければわざわざ出題せんわね^^;;

644.　Re: 日記　へるみ　2002/04/09 (火) 23:43

ごめん。はしょりすぎました(^^;
x=[x3:x2:x1:x0] が unsigned 8bit データ4つの組で
x, y, z, w という 4つの 32bitデータに対して
Xi=(xi+yi+zi+wi+2)/4
[X3:X2:X1:X0]を求めたいのだけど MMX 命令には
(xi+yi+1)/2 を求める命令があるのでそれを有効活用したいな
ということです。
ところでなんで psrlb っていう 8bit 単位の shift 命令が
ないんでしょう???

643.　RE:日記　計　2002/04/09 (火) 22:35
「簡単に求められるとき」を定義してもらわないと．それとも，「簡単に求められるとき」が何を意味するかの謎解きも含めた問題なのか？^^;;

642.　Re^2: 音声引き伸ばし　へるみ　2002/04/01 (月) 12:08
>別に難しいことを考えずに、似た波形を >近傍から抽出して、挿入したりオーバー >ラップすればいいのです。情報ありがとうございます。やはり餅は餅屋ですね。 Cマガのとどう違うのかとか理解したらまた報告します。

641.　Re: 音声引き伸ばし　池田　2002/03/29 (金) 23:21

別に難しいことを考えずに、似た波形を近傍から抽出して、挿入したりオーバーラップすればいいのです。TDHS という方法が、古典的で、完全なハーモニクスを仮定すれば、周波数領域の操作を時間領域の重複加算に変更できることが示されています。
http://keizai.yokkiachi-u.ac.jp/~ikeda/sp_soft.html
に類似の PICOLA というアルゴリズムがあります。これは、MPEG4 にもオプションとして採択されています。

640.　Re^4: オーバーラップ　炎羅　URL　　2002/03/04 (月) 21:20
ご無沙汰しております^^ > 今月のCマガジンにアルゴリズムが載ってます。　やられましたね(笑) 　記事の方はいまひとつ歯切れが悪かったので、　これという解決案は出ていないのでしょうね。

639.　Re^3: オーバーラップ　へるみ　2002/02/18 (月) 12:36
やられた(^^; 今月のCマガジンにアルゴリズムが載ってます。今度試してみよっと。

638.　Re^2: オーバーラップ　Hash　2002/02/09 (土) 19:48
> dskさんの音声辞書を持ってデータに付加させるってアイデアに近そうですね。そうなると簡単には出来そうに無いですが(^^; 1チップLSIなので、それ程たいそうな事はしてないんじゃないかな？とか思ってるんですが激甘でしょうか(^^;;

637.　Re: オーバーラップ　へるみ　2002/02/05 (火) 09:41
>用途限定っぽいですが、これで十分な音質（違和感なし）を確保できちゃってました。 dskさんの音声辞書を持ってデータに付加させるってアイデアに近そうですね。そうなると簡単には出来そうに無いですが(^^;

636.　オーバーラップ　Hash　2002/02/03 (日) 15:15

９０％以上重ねないと音質が保てないみたいですね。
オーバーラップしすぎてもエコーかかって聞きにくいですし、難しいですね(^^;

それと前にTVで見たとき結構音が良かったんでコレもFFTつかってるのかな？
と思ってたんですが、つかってなかったようです＞ゆっくり通話
用途限定っぽいですが、これで十分な音質（違和感なし）を確保できちゃってました。
http://www.sanyo.co.jp/koho/hypertext4/0011news-j/1122-1.html

635.　Re^3: 何かちがうような　へるみ　2002/01/31 (木) 21:58

うーん、試してみたけどなんか変。
むろん間違った実装の可能もかなりあるけど。

ちょっと心配なのがデータを処理する時に
w(x) = (1 - cos(t))/2という窓関数を
かけてN/2ずつオーバーラップさせてます。
同じデータでもFFTの前半にあるときと後半に
あるときとで微妙に位相がずれてしまうと
重ねあわせるときに音質低下の原因になりそうで。
どうなのかなあ。

634.　Re^2: 何かちがうような　へるみ　2002/01/31 (木) 00:05

>だから、周波数2πνの位相は2πν乗すると良いのでは？
なるほど。私のだと聞いていてなんか音の鳴り方がばらばら
(例えば手前にあったドラムが向こうにいってしまったような)
感じがあったのでもうしかしたら、そうやれば揃うのかもしれませんね。
リアルタイム処理がちょっときつそうですが近いうちに試してみます。

633.　Re^2: 何かちがうような　なべちゃん　2002/01/29 (火) 17:08

> f(t) := sin t + sin(t + θ)として、求めたいのは
> F(t) := sin 2t + sin 2(t + θ)であり、それぞれの

うむむ、F(t) := sin Kt + sin (Kt + θ) だと
Kが整数以外で問題発生か………。たしかに。
問題は２倍速にしろ1/2倍速にしろ、元データが半分欠損するのと
同じだから(n倍なら(n-1)/n欠損)、それによる品質低下か...。
(最高周波数が半分になったり、基本周波数が倍になったり...と)

632.　Re: 何かちがうような　dsk　2002/01/29 (火) 14:40

にょ、勘違い。
速さ変えずに音の高さ2倍を求めているのだから位相飛ばしちゃ駄目だからz'[s]のほうが合理的ですね。と思ったけど
簡単な具体例で考えると、
f(t) := sin t + sin(t + θ)として、求めたいのは
F(t) := sin 2t + sin 2(t + θ)であり、それぞれの
Fourier変換は
x(s) := (1 + e^iθ)δ1(s)
X(s) := (1 + e^2iθ)δ2(s)

だから、周波数2πνの位相は2πν乗すると良いのでは？
即ちz'''[s] := e[s/2](z[s]/e[s])^sを求めたらどうでしょうか？

631.　用途にもよりますが　dsk　2002/01/29 (火) 13:32

最高に音質のいい引き伸ばしはループを見つけて（AIかな？）
そこを繰返す（ただし減衰を考えないと駄目ですが...）のが
良いようです。なぜなら、人間の発声でも
（例えば「あ」と「あー」を比べる）楽器の発声でも、
そうなっているからです。

1.音質辞書により音を分解。
2.音質辞書に登録されたループ部を取り出し繰返す。
　（そのときに減衰も考える）

というのが理想ですが、音質辞書が凄くなりそうですね。

630.　何かちがうような　dsk　2002/01/29 (火) 13:22

FFTしたものを{z[s]}、e[s] := |z[s]|、p[s] := z[s]/e[s]として、
1/2倍速のときならz'[s] := e[s/2] p[s]を求めていますよね。
そうじゃなくて
z''[s] := z[s/2] で位相も1/2倍速に飛ばさないと巧くいかない
気がするのですが...ってなべちゃん氏と同じこと？

z'だと抑揚だけが1/2倍速で、しゃべった内容は等倍のままのような気が....

629.　補足　なべちゃん　2002/01/23 (水) 22:28
>1/2倍速で再生する場合は22kHzのデータとして再生もちろん1度DFTをして周波数スペクトルを加工してIDFTした後のデータ。うう、考えてみれば当たり前だった。

628.　Re: 音声引き伸ばし　なべちゃん　2002/01/23 (水) 21:05

> やっぱり引き伸ばすほうは苦手っぽいですねぇ。

速くするならばデータの欠損はない訳ですけど、
（２倍速ならデータを半分捨てればいい）
遅くするときはデータが足りないと。
1/2倍速のときは、離散化してあるために周波数スペクトルが
とびとびになりますからねぇ（2n+1=0とか）。

へるみさん>そもそもスペクトルをどう補完したらいいのかも分からない(^^;

少し考えてみたのですけど、44KHz(sampling)のデータをたとえば1/2倍速で再生する場合は22kHzのデータとして再生しなきゃいけないのかな（もしかして当たり前？）

627.　音声引き伸ばし　Hash　URL　　2002/01/23 (水) 09:56
GoldWAVEってシェアウエアにそういう機能がついてましたが、やっぱり引き伸ばすほうは苦手っぽいですねぇ。なんか、ぎーぎーいってます(^^;

626.　音もの　福地　URL　　2002/01/16 (水) 23:19

XMMS(winampみたいなののUNIX用ソフト)のプラグインを
いくつか拾ってきて試してみましたが、納得できる音質の
ものはないですね。速くする方はまだしも、遅くすると
きびしい。難しそうだなぁ。

音ものでいうと、Teddyの五十嵐さんの最近の仕事が気に
なっているので、イフェクトものと組み合わせようかなと
思ってたところです。下記(上記?)URL参照。

625.　Re^2: 便乗(?)質問(^^;　へるみ　2002/01/16 (水) 18:10
> 単純に位相分布をそのままずらしたらダメなのかなとか >思ってしまいますが。むしろ位相をずらしちゃうと駄目でそれを保ったままエネルギーの方をずらさないといけないみたいです。難しい...

624.　Re: 便乗(?)質問(^^;　なべちゃん@abk　2002/01/15 (火) 22:51
その昔、同じ事を考えたことがありますが(FFTも知らない頃)、アルゴリズムまでは考えなかった。単純に位相分布をそのままずらしたらダメなのかなとか思ってしまいますが。 #相変わらず役立ちそうもないな >自分

623.　Re: REAL FILEを　なべちゃん@abk　2002/01/15 (火) 22:38

うーん、ここにくるの久々。

> REAL FILEから自然にWAVE　FILEへと変換できる
> フリーソフトってありますか?

RealEditorならできるかなと思ったのですが、配布停止中の模様。
RealAudio関連ライブラリのAPIを調べるのが１つの方法で、
あとひとつは、Audioカードでなくファイルへ出力するダミーの
Wave(PCM) driverを探すことかと。これならあるかもしれません。

622.　Re:ストレッチ　へるみ　2002/01/15 (火) 15:55

>昔Oh!FMTOWNSで戸田浩さんがそんな記事を書いておられた
>ような気がします。
はい。ただあれは適当に音を切ってたはずです。
単なる推測ですが昔あった倍速再生でも音は普通に聞こえるビデオ
と同じようなものかと。
#当時のマシンレベルでは流石にリアルタイムFFTは無理でしょう(^^;

もう一度やりたいサンプルを置きました(下と同じURLです)。
[A]と[Z]で変化するのは同じですが、[Q]のトグルで単なる周波数
変換とピッチ変換が変わります。

PS. ビデオエフェクトの次はこんなのしませんか?(^^;

621.　ストレッチ　福地　2002/01/15 (火) 12:46
昔Oh!FMTOWNSで戸田浩さんがそんな記事を書いておられたような気がします。それともあれはピッチを変えずに音程を変えるんだったけかな?

620.　Re:タイムストレッチ　へるみ　2002/01/14 (月) 08:08

>結局サンプリングレートコンバートですよね。
えと言葉の定義が違うのかもしれませんがそうではないつもりです。
サンプリングコンバートでは例えば44.1kHzから48kHzに変換して
それを44.1kHzのままで出力すればゆっくり(48/44.1倍)出力されます。だけどそれだとゆっくりになったぶん、音程がさがりますよね。
私がやりたいのは音程がさがらずにゆっくりすることなんです。

ちらっとしか見てませんがCマガの記事も単なるサンプリング
コンバータに思えました。

619.　タイムストレッチ　小次郎　2002/01/14 (月) 01:39
結局サンプリングレートコンバートですよね。この辺は手を出そうとしたんですが、知り合いが卒論のときに大量の資料を抱えていたので止めました（根性なし）。今月のCマガジンにそんな記事もあったような覚えがあります。

618.　RM2WAV　小次郎　2002/01/14 (月) 00:48

> REAL FILEから自然にWAVE　FILEへと変換できるフリーソフトって

　RealPlayer形式はたしかClosedな規格だったような
覚えがあるので多分ないんではないでしょうか？

＃不確かなので信じないほうがイイかもしれません（笑）

　UN!X系でのオープンソースなPlayerがあれば
どうにかできるかもしれませんが。

　早急に解決したいなら無難な線では光か同軸で出力させたのを
そのまま盗り込むのが楽ではないでしょうか？

＃44.1kHzのデータはSB Live!系などには鬼門ですが

616.　便乗(?)質問(^^;　へるみ　2002/01/13 (日) 22:55

音声を、その音程を変えずに速度を変えるアルゴリズムを
考えています。
今試しているのはこんなアルゴリズムです。
1. FFTをして{R[i], I[i]}を求める。
2. パワースペクトルE[i]=(R[i]*R[i]+I[i]*I[i])^0.5を求める。
(例えば高音方向に2倍ずらすなら)
3. ベクトル{R[2i], I[2i]}の大きさをE[i]/E[2i]倍する。
つまり位相は保ったままパワースペクトルの分布だけずらすという
イメージです。
サンプルプログラム
>http://homepage1.nifty.com/herumi/soft/filter.lzh
(コマンドラインでwavを引数にとります。[A]と[Z]でずらします)
それっぽくは聞こえるんですが、どうも音質が悪いです。
そもそもスペクトルをどう補完したらいいのかも分からない(^^;
何かよいアルゴリズムはないでしょうか。

#もちょっとコードを整理したらソースも出そうかと思ってますが。

613.　Re: 画像圧縮の方法　小次郎　2002/01/11 (金) 02:12

　あけましておめでとうさまです。

＞ＲＧＢ形式の画像を圧縮したいのですがどのような方法がいいですか？
＞オススメの方法があったら教えてください。
＞言語としてはＣを使っています。

　この辺の情報があるとアドバイスされやすいのでは？
・実写調なのかアニメ調なのか
・オリジナル圧縮を作りたいのか、既在の圧縮方式を利用したいのか
・色数はどれくらいなのか
・画像サイズはどの程度なのか
・可逆必須なのか、不可逆でもいいのか
・速度優先なのか圧縮優先なのか

　適当に答えますと…

　既在の圧縮方式ならば不可逆でいいならJPEG、可逆必須ならPNGあたりが
ライブラリの使用条件なども含め、楽ではないでしょうか。

　オリジナル方式を作りたい場合はまず汎用圧縮の
・ランレングス法
・ハフマン法
・Lampel-Ziv法
・BlockSorting法
・MoveToFront法
・算術圧縮
あたりを調べて見てください。

＃Lampel-Ziv法と算術圧縮は特許的に危険ですが

　さらにBPE法などマイナーなものに手を伸ばすと
いろいろありますので奥は果てしなく深いですね。

　あと、RGB-YCC変換やDCT、Waveletなどを
調べるのもいいかもしれません。

　アニメ調ならMAGやPIC（稲妻の走る方（笑））あたりも
大変参考になります。

　個人的には劣化しないようにSVGに変換できるライブラリを
ライセンスフリーで公開して欲しいです（爆）

611.　画像圧縮の方法　ＨＩＤＥ　2002/01/09 (水) 19:26
こんにちわ。初投稿となります。ＲＧＢ形式の画像を圧縮したいのですがどのような方法がいいですか？オススメの方法があったら教えてください。言語としてはＣを使っています。

610.　あけましておめでとうございます。　へるみ　2002/01/01 (火) 08:45
今年もよろしくお願いします。 #って何を?(^^;

609.　いまごろ気づいたが　dsk　2001/11/13 (火) 10:20
最後の ret -= 32768; は ret += -32768; のほうが良いね。

すべてのチェックを / 　　

@homepageメッセージボード