Haskell中的位交换问题

Question

作为学校项目的一部分，我在Haskell中实现了一些crypthographic算法。正如你可能知道这涉及到很多低级别的小技巧。现在我被困在一个特殊的子程序中，这使我头痛。该例程是256位置换，其工作原理如下：

输入：一个256位块。
然后，输入块中的所有偶数位（0,2，...）将被视为输出块中的前128位。而奇数位被认为是输出块中最后128位。更具体地，在输出端上的第i个位式被给出为（一个_我是第i个位在输入块，以及b是输出）：

b _我 =一个 _2I

b _{I + 2 ^d-1} =一个 _{2I + 1}

为我 0-2 ^d-1 -1，d = 8

作为玩具例如，假定我们使用与16工作的程序的简化版本而不是256位。 - > 1111 1111 0000 0000

我一直没能拿出一个干净实现这个

1010 1010 1010 1010。再后来，遵循以下比特串将被置换功能。特别是我一直在尝试使用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" 

Answer 2

这应该工作：

import Data.List 
import Data.Function 

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

的解释的位： 作为sortBy保留原来的顺序，就可以在一个对中的每个值，即使在奇数位置上的“0”，并且每个值位置“ 1“，那么我们简单地排序该对的第二个值。因此，所有在偶数位置的数值都会放在奇数位置的数值之前，但是他们的顺序将会保持不变。

Chris

Answer 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 

，通过移动到位向量作为你的表现，你使用的Haskell类型，这样会失去很多，你得到了什么免费作为Num实例。但是，您始终可以为您的表示实施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))) 

您也可以找到勒Erkok的sbv包是有用的，但我不知道它暴露一样便利backpermute功能为您的特定问题。

更新：我认为这是一个有趣的问题来回答，所以我继续充实码出位的库：bit-vector。