循環バッファ作成

最近備忘録的なポストばっかだな・・・。
まぁそれだけ研究してるってことですよ。実戦向きかどうかは別として（ぁ
今日は循環バッファを作ってました。C言語版。DSPに搭載するならC言語だし。全力で循環バッファ使うならアセンブラなんだけど＾＾； DSPアセンブラは追々勉強していこう。せっかく手元にDSPあるんだし、あいつは弄くり倒したい。浮動小数点演算可能ではあるけれど、あえて固定小数で勝負したい。ん〜でもFFTとかのライブラリは全部浮動小数だったな・・・。PCでのシミュレーションなら固定小数と浮動小数に実はそこまで（クリティカルな）差は出ないから無理して使う必要もないけど、DSPでは実クロックは遅いからなぁ。その代わり並列処理が半端じゃないが。
だから余計にC言語じゃその真価を引き出せないからアセンブラ勉強する必要があるんだよなっと。勉強しとけば就職には強そうだ。就活に間に合いそうはないが＾＾；　話のネタに位はなるだろ、うん。
っと、話は逸れたけれど循環バッファ。信号処理では現時点からnサンプル前までのデータ列に対してどーのこーのという処理が多く、配列に対してのランダムアクセスという物はほとんど発生しない。データアクセスはシーケンシャルだし、データの追加、削除というものも先頭と末尾に集中。サンプル長も固定と結構狭い条件で動作します。要は汎用性は気にしなくていいから最適化を掛けやすいという環境といえますかね。
まー大抵実装するときは、nサンプル保存する配列を用意し、サンプルを追加するときはfor文かなんかで値を右ないし左の配列要素にコピーして次のサンプルを配列に書き込むってスタイル。まーシフトレジスタをイメージしたらまさにその通りだし、見やすさも抜群だけれど如何せん無駄が多い。けどシミュレーションではリアルタイム性を考慮してないからこんなコード平気で書いちゃうんだよなぁ・・・。これはすっごくよろしくない。値を１つ捨てて１つ入力するという作業だから大半の値は使い回し。にも関わらずn-1個の値をコピーするからそれだけ無駄に時間を食っちゃう。
で、そんなことするくらいなら捨てる予定だった値のところに新しい値を放り込んでやればいい。つまり、配列が輪になっているとイメージし、末尾まで来たら次は先頭にまた戻る。これが循環バッファ。概念は凄く簡単。アクセス時には先頭をどこにするかという下駄を履かせてやればいい。
配列長が4で、下駄（オフセット）が0ならば通常の配列のアクセスと同じ。この状態で右に要素をシフトしたとイメージする。配列の末尾の値が捨てられ、先頭に空きが出来たというイメージだ。これを下駄だけで表現しようと思ったら、先頭へのアクセスが実際には末尾を指していればよい。配列のある要素を指定した際、下駄を履かせた値が配列の要素数を超えた場合はその合計値から配列の要素数を引いた値が指したい位置になる。例えば、1度右にシフトされ、下駄が配列の末尾を指している（C言語に倣うとオフセット値は3）状態で、3番目の要素にアクセスしたい（C言語では指定する値は2）ときにどうするか。オフセットを合わせた値は3+2=5で要素数を超えている。よって5-4=1番目が本来3番目に用意されていた値、ということになる。
つまり、配列へのアクセス時に毎度毎度要素数を超えていないかのチェックをしなくてはならないと言うことになる。コレはたいそう無駄が多い。コピーは時間が掛かるといって循環バッファにしたのに、アクセスのたびにリミットチェックの条件分岐をしないといけないとなるとパイプラインが生成されず実行効率が悪い。実際そんなコードを書いたらコピーするのと大して処理時間が変わらない。
つまり条件分岐をしなければよいということになる。実はそれは簡単。剰余計算を使えばいい。指したい要素番号とオフセットの合計値を要素数で割ったときの余りが実際に指し示す要素番号となるのだ。例えばさっきの例で言えば、オフセットは3、指定する要素番号は2、要素数は4なので
(3+2)%4=1 (%はCでは剰余を返す演算子）
となる。見事同じ値を返す。アクセスの際にこうして剰余計算を行わせることで条件分岐を行う必要が無くなる。コンパイラによる最適化も掛かりやすくなると言うことなんですな。
が！これでもまだ問題が。剰余計算は基本演算の中ではすこぶる遅い！！！　除算がただでさえ遅いのにさらに余りを返さなくてはいけないと言うことで非常に時間コストがかかるんですな。if分岐に比べればマシですがやっぱり時間が掛かる。
そこでさらなる工夫。配列のサイズを2の冪乗にするという条件はつきますが、剰余計算がビット演算で可能になります。今回の例では配列サイズが4で、見事2の冪乗なので早速やってみましょう。指し示す要素番号とオフセットは同じとしますと
(3+2) & (4-1) = 1 (&はCではビット毎にANDを返す演算子）
となります。AND演算はマスクを掛けるだけなので非常に高速です。これで相当早くなります。信号処理ではFFTの都合などで配列サイズが2の冪乗に揃えられていることが多いですから非常に良く用いられる手法です。
私もこの手法を知ったときには「は〜よく出来てるなぁ・・・」と感心しましたねぇ。C/C++ではどうしても関数を作ってそれを通して配列を操作しなくてはいけないため見た目にちょっと野暮ったい印象がありますが、C#ではプロパティのおかげで見た目に配列と全く同じアクセス方法が使えます。これはかなり嬉しいですね。なんせ、コードの書き換えが配列の型を書き換えるだけで済みますからｗ ん、C++でも[]演算子をオーバーロードしたら同じコトできたっけ・・・？ いやでけんか。
まぁ下駄を履かせる方法とかちょっと混乱しそうになりますが、一度作ってしまえば後はそれを使い回すだけですしね。使う側はアクセスしたい要素番号を関数に飲ませればいいだけですし。
つーことで講座の共有にでもおいとくか。ドキュメントまでつけなくても大体分かるだろう・・・つか分かってｗ