在Haskell中进行位交换的问题

Question

作为学校项目的一部分,我正在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.

作为玩具示例,假设我们使用了例程的简化版本,该例程使用16位块而不是256位.然后,以下位串将被置换如下:

1010 1010 1010 1010 - > 1111 1111 0000 0000

我无法为此功能提供干净的实现.特别是我一直尝试使用ByteString - > ByteString签名,但这种强迫我使用Word8的粒度.但是输出字节串中的每个字节都是所有其他字节中的位的函数,这需要一些非常混乱的操作.

对于如何解决这个问题,我会非常感激.

Answer 1

如果你想要一个有效的实现，我认为你不能避免使用字节。这是一个示例解决方案。它假定 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"