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。

作为一个玩具示例，假设我们使用了使用 16 位块而不是 256 位的例程的简化版本。然后以下位串将被排列如下：

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”，然后我们只需对配对的第二个值进行排序。因此，偶数位置的所有值都将放在奇数位置的值之前，但它们的顺序将保持不变。

克里斯

于 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

现在，通过使用位向量作为表示，您会失去很多使用 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)))

您可能还会发现 Levent Erkok 的sbv包很有用，尽管我不确定它是否公开了与backpermute您的特定问题一样方便的功能。

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

于 2011-09-04T18:27:12.967 回答