5

学校のプロジェクトの一環として、Haskell でいくつかの暗号化アルゴリズムを実装しています。おそらくご存知のように、これにはかなりの低レベルのビット操作が含まれます。今、私は頭痛の原因となる特定のサブルーチンに行き詰まっています。256 ビットの順列であるルーチンは、次のように機能します。

入力: 256 ビット ブロック。
次に、入力ブロックのすべての偶数ビット (0、2、...) が、出力ブロックの最初の 128 ビットと見なされます。奇数番号のビットは、出力ブロックの最後の 128 ビットと見なされます。より具体的には、出力のi 番目のビットの式は次のように与えられます (a iは入力ブロックのi 番目のビットで、b は出力です)。

b i = a 2i

b i+2 d-1 = a 2i + 1

iが0 から 2 d-1 -1 の場合、d = 8。

おもちゃの例として、256 ビットの代わりに 16 ビット ブロックで動作するルーチンの縮小バージョンを使用したとします。次に、次のビット文字列は次のように並べ替えられます。

1010 1010 1010 1010 -> 1111 1111 0000 0000

この関数のクリーンな実装を思い付くことができませんでした。特に、私は ByteString -> ByteString 署名を試してきましたが、Word8 のような粒度で作業する必要があります。しかし、出力バイト文字列の各バイトは、他のすべてのバイトのビットの関数であり、非常に面倒な操作が必要です。

この問題に取り組む方法についてのヒントやアドバイスをいただければ幸いです。

4

3 に答える 3

4

これはうまくいくはずです：

import Data.List
import Data.Function

map fst $ sortBy (compare `on` snd) $ zip yourList $ cycle [0,1]

少し説明: sortBy は元の順序を保持するため、偶数位置の各値を「0」、奇数位置の各値を「1」とペアにすることができます。次に、ペアの 2 番目の値でソートします。したがって、偶数の位置にあるすべての値は、奇数の位置にある値の前に配置されますが、それらの順序は維持されます。

クリス

于 2011-09-04T06:24:42.170 に答える
4

効率的な実装が必要な場合は、バイトの操作を避けることはできないと思います。これが解決策の例です。ByteString のバイト数は常に偶数であると想定しています。ボックス化解除や厳密性調整についてはあまり詳しくありませんが、非常に効率的になりたい場合はこれらが必要になると思います。

import Data.ByteString (pack, unpack, ByteString)
import Data.Bits
import Data.Word

-- the main attraction
packString :: ByteString -> ByteString
packString = pack . packWords . unpack

-- main attraction equivalent, in [Word8]
packWords :: [Word8] -> [Word8]
packWords ws = evenPacked ++ unevenPacked
    where evenBits = map packEven ws
          unevenBits = map packUneven ws
          evenPacked = consumePairs packNibbles evenBits
          unevenPacked = consumePairs packNibbles unevenBits

-- combines 2 low nibbles (first 4 bytes) into a (high nibble, low nibble) word
-- assumes that only the low nibble of both arguments can be non-zero. 
packNibbles :: Word8 -> Word8 -> Word8
packNibbles w1 w2 = (shiftL w1 4) .|. w2 

packEven w = packBits w [0, 2, 4, 6]

packUneven w = packBits w [1, 3, 5, 7]

-- packBits 254 [0, 2, 4, 6] = 14 
-- packBits 254 [1, 3, 5, 7] = 15
packBits :: Word8 -> [Int] -> Word8
packBits w is = foldr (.|.) 0 $ map (packBit w) is

-- packBit 255 0 = 1
-- packBit 255 1 = 1
-- packBit 255 2 = 2
-- packBit 255 3 = 2
-- packBit 255 4 = 4
-- packBit 255 5 = 4
-- packBit 255 6 = 8
-- packBit 255 7 = 8
packBit :: Word8 -> Int -> Word8
packBit w i = shiftR (w .&. 2^i) ((i `div` 2) + (i `mod` 2))

-- sort of like map, but halves the list in size by consuming two elements. 
-- Is there a clearer way to write this with built-in function?
consumePairs :: (a -> a -> b) -> [a] -> [b]
consumePairs f (x : x' : xs) = f x x' : consumePairs f xs
consumePairs _ [] = []
consumePairs _ _ = error "list must contain even number of elements"
于 2011-09-04T12:07:54.643 に答える
3

パフォーマンスが重要でない限り、このようなプロジェクトにはビット ベクトル表現を使用することをお勧めします。お気づきのように、個々のビットにランダムにアクセスするのは、パックされた形式の場合は少し面倒ですが、Data.Vectorこの種のタスクには豊富な関数が用意されています。

import Data.Bits
import qualified Data.Vector as V

type BitVector = V.Vector Bool

unpack :: (Bits a) => a -> BitVector
unpack w = V.generate (bitSize w) (testBit w)

pack :: (Bits a) => BitVector -> a
pack v = V.ifoldl' set 0 v
  where
    set w i True = w `setBit` i
    set w _ _    = w

mkPermutationVector :: Int -> V.Vector Int
mkPermutationVector d = V.generate (2^d) b
  where
    b i | i < 2^(d-1) = 2*i
        | otherwise   = let i' = i-2^(d-1)
                        in 2*i'+1

permute :: Int -> BitVector -> BitVector
permute d v = V.backpermute v (mkPermutationVector d)

これにより、数学的な記述を厳密に書き写すことで順列を指定できることに注目してください。これにより、エラーの可能性が大幅に減少し、ビットをいじるコードよりも書きやすくなります。

サンプル ベクトルでテストするには (基数 10):

*Main> import Data.Word
*Main Data.Word> let permute16 = pack . permute 4 . unpack :: Word16 -> Word16
*Main Data.Word> permute16 43690
65280

Numここで、表現をビット ベクトルに移行することで、インスタンスなどの Haskell 型を使用して無料で得られるものの多くを失います。Numただし、表現の操作はいつでも実装できます。ここから始めます：

plus :: BitVector -> BitVector -> BitVector
plus as bs = V.tail sums
  where
    (sums, carries) = V.unzip sumsAndCarries
    sumsAndCarries  = V.scanl' fullAdd (False, False) (V.zip as bs)
    fullAdd (_, cin) (a, b) = ((a /= b) /= cin
                              , (a && b) || (cin && (a /= b)))

Levent Erkok のパッケージも役立つかもしれませんが、特定の質問sbvほど便利な機能が公開されているかどうかはわかりません。backpermute

更新: これは答えるのが楽しい質問だと思ったので、先に進み、ライブラリとしてコードを少し肉付けしました: bit-vector。

于 2011-09-04T18:27:12.967 に答える