Получить произвольные фрагменты битов из Bytestring

Я хочу использовать ленивый Bytestring для представления потока битов. Мне нужно иметь возможность эффективно брать произвольные фрагменты битов из этого потока. Например, у меня может быть ByteString длины 10, и я хотел бы нарезать новый ByteString, состоящий из битов 24-36, из исходного ByteString.

Проблема в том, что ByteStrings — это массивы из Word8, поэтому получение диапазонов, не кратных 8, затруднено. Лучшее, что мне удалось придумать, это использование Data.Binary и Data.Binary.Bits. Обратите внимание, что get32BitRange специально для диапазонов ‹= 32.

get32BitRange :: Int -> Int -> ByteString -> ByteString
get32BitRange lo hi = runPut . putWord32be
                    . runGet (runBitGet . block $ word8 (8 - (lo `quot` 8)) *> word32be len)
                    . drop offset
    where len = hi - lo
          lo' = lo `div` 8
          offset = fromIntegral lo' - 1

Алгоритм:

  • найти индекс первого Word8, содержащего биты, которые я хочу
  • падение с ByteString до этого индекса
  • если нижний конец диапазона битов не кратен 8, в начале Word8 будут лишние биты, поэтому пропустите их.
  • получить (hi-lo) биты и сохранить в Word32
  • поместите это Word32 в ByteString

Это выглядит более чем уродливо, есть ли более эффективный способ получить произвольные фрагменты битов из ByteString?

РЕДАКТИРОВАТЬ: вот более эффективная версия

get32BitRange :: Int -> Int -> ByteString -> Word32
get32BitRange lo hi = runGet get
    where get = runBitGet . block $ byteString byteOff *> word8 bitOff *> word32be len
          len = hi - lo
          (byteOff, bitOff) = lo `quotRem` 8

binary haskell bits bitstream bytestring
person cdk    schedule 11.03.2013    source источник
comment
Знаете ли вы, что простое, скучное старое UArray уже использует очень плотно упакованное представление, если оно содержит Bool? Почему бы не использовать это?   -  person Daniel Wagner    schedule 12.03.2013
comment
@DanielWagner: я не думал об этом, и это было бы элегантным решением моей проблемы, но, к сожалению, мне нужно использовать ленивые ByteString, и я не думаю, что смогу сохранить лень при преобразовании в UAarray или распакованный Vector . Хотя я мог бы попробовать коробочное представление и посмотреть, как оно будет выглядеть, но здесь ключевым фактором является эффективность.   -  person cdk    schedule 12.03.2013

Ответы (3)


arrow_upward
2
arrow_downward

Я думаю, что другие решения намного лучше, но вы можете использовать внутренний модуль, чтобы получить базовую структуру: http://hackage.haskell.org/packages/archive/bytestring/0.10.2.0/doc/html/src/Data-ByteString-Internal.html#ByteString

data ByteString = PS {-# UNPACK #-} !(ForeignPtr Word8) -- payload
                     {-# UNPACK #-} !Int                -- offset
                     {-# UNPACK #-} !Int                -- length

Затем вы можете использовать стандартные инструменты указателя для создания ByteString, указывающих именно туда, куда вы хотите, путем прямого манипулирования ForeignPtr...

person sclv    schedule 12.03.2013

arrow_upward
1
arrow_downward

Вы не можете сделать это эффективным с ByteString в качестве типа вашего API, потому что он не несет информации о том, что «биты», которые вы хотите, действительно начинаются с некоторого смещения в первый байт.

Лучше всего сделать тип оболочки:

data BitStream =
    BitStream {
        info :: ByteString,
        -- values from 0-7: ignore all bits in the first byte up to
        -- but not including this offset
        firstBitOffset :: !Int,to but not including this offset
        -- values from 0-7: ignore all bits in the last byte after
        -- but not including this offset
        lastBitOffset :: !Int
    }

Затем вы можете разработать битовый API вокруг этого.

person GS - Apologise to Monica    schedule 11.03.2013
comment
это, безусловно, помогло бы очистить мой пример функции, но меня больше интересует метод, позволяющий фактически извлекать кусочки битов. - person cdk; 12.03.2013
comment
что ты хочешь с ними потом делать? - person GS - Apologise to Monica; 12.03.2013
comment
анализировать их как двоичные данные, возможно, к типу Word или Int - person cdk; 12.03.2013

arrow_upward
1
arrow_downward

Я собираюсь отметить это как решенное. Вот что я в итоге использовал:

get32BitRange :: Int -> Int -> ByteString -> Word32
get32BitRange lo hi = assert (lo < hi) $
    runGet (runBitGet bitGet)
    where bitGet = block $ byteString byteOff
                         *> word8 bitOff
                         *> word32be len
          len = hi - lo
          (byteOff, bitOff) = lo `quotRem` 8
person cdk    schedule 13.04.2014