バレルシフト その１

食わず嫌いはいけないなと思って、最近はソフトウェア関係の書籍も意識的に読むように心がけています。

その中で"配列の要素の回転"というものがあって、例えば次のような配列があった場合

abcdefgh

これを3要素回転させると結果は

defghabc

となります。

ソフトの場合、エレガントなアルゴリズムがあって
i要素分回転させたい場合、まず配列をはじめのi個と残りのn-i個にわけます。

abc, defgh

次に分割したそれぞれにおいて、要素の並びを逆転します。

cba, hgfed

分割した配列を再び１つにまとめて、

cbahgfed

最後にこの配列全部の並びを逆転させます。

defghabc

すると、見事回転が完成しているというもの。


私のような凡人にとってはこれでちゃんとできているという事実だけでもスゴイと思ってしまうのですが
実行時間やメモリの消費量及びコードのシンプルさという観点からもこのアルゴリズムは優れているとの事です。

で、これをハードウェアにそのまま応用できるか？
というとそううまく行かないのが悲しいところです。

このような操作は、ハードでは"バレルシフタ"と呼ばれるものに相当します。

次回はHDLによるバレルシフタの記述と実装について書いてみたいと思います。