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 件のコメント:
コメントを投稿