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。