2011年6月14日火曜日

ビットスワップ

MOR命令4つで完全シャッフルをするのは超絶技巧だ. Schemeで書いたMORのシミュレータを使い, 実際にシャッフルしてみる.

MMIXのMORは$Yと$ZをMORして$Xに置くが, Schemeは関数なので, MORした値を返す.

まず行列の転置の関数がいる.

(define (tr m) ;行列mの転置
(map (lambda (i)
(map (lambda (b) (list-ref b i)) m))
(a2b 0 (length (car m)))))
;(tr '((1 1 1 1) (0 0 1 0) (0 1 0 0) (1 1 1 1)))
;=>((1 0 0 1) (1 0 1 1) (1 1 0 1) (1 0 0 1))

真理値に0,1を使うor関数もいる.

(define (or x y) (quotient (+ x y 2) 3))
;(or 0 0)=>0, (or 0 1)=>1, (or 1 0)=>1, (or 1 1)=>1

するとmorは

(define (mor y z)
(let ((zb (map (lambda (n) (n2bs n 8)) (n2bytes z 8)))
(yb (tr (map (lambda (n) (n2bs n 8)) (n2bytes y 8)))))
(bytes2n
(map bs2n
(map (lambda (z)
(map (lambda (y)
(fold-right or 0 (map * z y))) yb)) zb)))))

と書ける. (n2bs n w)は整数nをwビットのリストにする. n2bytesはバイトのリストにする.

あと, MUX関数も必要だ.

(define (mux m y z)
(let ((ms (n2bs m 64)) (ys (n2bs y 64)) (zs (n2bs z 64)))
(define (mx m y z)
(if (null? m) '()
(cons (if (= (car m) 1) (car y) (car z))
(mx (cdr m) (cdr y) (cdr z)))))
(bs2n (mx ms ys zs))))

この準備のもとで, 完全シャッフル関数は

(define (perfectshuffle z)
(let ((t (mor z #x8008400420021001)) (u 0))
(set! t (mor #x8020080240100401 t))
(set! u (mor t #x4080102004080102))
(set! u (mor #x4080102004080102 u))
(mux #xaa55aa55aa55aa55 t u)))

である. どのビットがどこへいったかを調べるには,

(define bin '(
#xffffffff00000000
#xffff0000ffff0000
#xff00ff00ff00ff00
#xf0f0f0f0f0f0f0f0
#xcccccccccccccccc
#xaaaaaaaaaaaaaaaa))

を次々とシャッフルし, 結果を二進法で出力する. それには

(define (bs x)
(substring (number->string (+ x (expt 2 64))2) 1 65))

を使う.

(map (lambda (n) (display (bs (perfectshuffle n))) (newline))
bin)

をやってみると,


が得られる. つまり, 左から元の位置は63, 31, 62, 30,...,32,0であったことが分かる.

0 件のコメント: