В рамках школьного проекта я реализую некоторые криптографические алгоритмы на Haskell. Как вы, наверное, знаете, это включает в себя довольно много низкоуровневых битов. Теперь я застрял на одной конкретной подпрограмме, которая вызывает у меня головную боль. Подпрограмма, представляющая собой перестановку на 256 бит, работает следующим образом:
Вход: 256-битный блок.
Тогда все четные биты (0,2,...) во входном блоке считаются первыми 128 битами в выходном блоке. В то время как нечетные биты считаются последними 128 битами в выходном блоке. В частности, формула для i-го бита на выходе задается как (ai — это i-й бит на входе блок, а b — выход):
бi = а2i
bi+2d-1 = a2i + 1
для i от 0 до 2d-1-1, d = 8.
В качестве игрушечного примера предположим, что мы использовали сокращенную версию подпрограммы, которая работала с 16-битными блоками вместо 256-битных. Тогда следующая битовая строка будет переставлена следующим образом:
1010 1010 1010 1010 -> 1111 1111 0000 0000
Я не смог придумать чистую реализацию этой функции. В частности, я пытался использовать подпись ByteString -> ByteString, но это вынуждает меня работать над степенью детализации Word8. Но каждый байт в выходной строке байтов является функцией битов во всех других байтах, что требует некоторых действительно грязных операций.
Я буду очень признателен за любой намек или совет о том, как подойти к этой проблеме.