Problema con lo scambio di bit in Haskell

Question

Come parte di un progetto scolastico sto implementando alcuni algoritmi crittografici in Haskell. Come probabilmente saprai, questo comporta un bel po 'di giochetti di basso livello. Ora sono bloccato su una particolare routine secondaria che mi provoca mal di testa. La routine, che è una permutazione su 256 bit, funziona come segue:

Input: un blocco a 256 bit.
Quindi tutti i bit con numero pari (0,2, ...) nel blocco di input sono considerati i primi 128 bit nel blocco di uscita. Mentre i bit con numeri dispari sono considerati come gli ultimi 128 bit nel blocco di uscita. Più specificamente, la formula per la -esimo bit nella uscita è data come (a _i è il -esima bit nel blocco d'ingresso, e b è l'uscita):

b _i = a _2i

b _{i + 2 ^d-1} = a _{2i + 1}

per i da 0 a 2 ^d-1 -1, d = 8.

Come esempio giocattolo, supponiamo abbiamo usato una versione ridotta della routine che ha lavorato con 16 blocchi di bit anziché 256 bit. Poi il seguente bitstring sarebbe permutata come segue:

1010 1010 1010 1010 -> 1111 1111 0000 0000

non sono stato in grado di trovare un'implementazione pulita per questo funzione. In particolare, ho provato con una firma ByteString -> ByteString, ma questo mi costringe a lavorare su un tipo di granularità di Word8. Ma ogni byte nell'outtestring dell'output è una funzione di bit in tutti gli altri byte, che richiede alcune operazioni davvero disordinate.

Sarò davvero grato per qualsiasi tipo di suggerimento o consiglio su come affrontare questo problema.

Answer 1

Se si desidera un'implementazione efficiente, non credo che si può evitare di lavorare con i byte. Ecco una soluzione di esempio. Suppone che ci sia sempre un numero pari di byte in ByteString. Non ho molta familiarità con il twisting di unboxing o strict, ma penso che sarebbero necessari se si vuole essere molto efficienti.

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

questo dovrebbe funzionare:

import Data.List 
import Data.Function 

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

Un po 'di spiegazione: Come sortby conservare l'ordine originale, possiamo accoppiare ciascun valore in una posizione pari a "0" e ogni valore in una posizione dispari un " 1 ", quindi ordiniamo semplicemente il secondo valore della coppia. Quindi tutti i valori nelle posizioni pari saranno posizionati prima dei valori in posizioni dispari ma il loro ordine sarà mantenuto.

Chris

Answer 3

A meno che la prestazione non sia critica, mi consiglia di utilizzare una rappresentazione vettoriale di bit per un progetto come questo. Come hai scoperto, l'accesso casuale a singoli bit è qualcosa di doloroso quando sono in forma compressa, ma lo Data.Vector offre una vasta gamma di funzioni per questi tipi di attività.

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) 

Nota come questo ti consente di specificare la permutazione mediante una trascrizione accurata della descrizione matematica. Ciò riduce sostanzialmente la probabilità di errori ed è più piacevole scrivere rispetto al codice bit-twiddly.

provare con il tuo esempio vettore (in base 10):

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

Ora, passando a vettori di bit come rappresentazione, si perde un sacco di quello che si ottiene gratuitamente utilizzando i tipi di Haskell, come ad come istanze Num. Tuttavia, è sempre possibile implementare le operazioni Num per la propria rappresentazione; qui è un inizio:

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))) 

È inoltre possibile trovare il pacchetto di Levent Erkok sbv utile, anche se non sono sicuro che espone una funzione così conveniente come backpermute per la tua domanda particolare.

Aggiornamento: ho pensato che fosse una domanda divertente a cui rispondere, quindi sono andato avanti e ho arricchito il codice un po 'come una libreria: bit-vector.