2

我想用一个lazyBytestring来表示一个比特流。我需要能够有效地从该流中获取任意位片。例如,我可能有一个ByteString长度为 10 的 a,我想ByteString从原始的ByteString.

问题是sByteStrings的数组Word8,所以取不是 8 的倍数的范围很困难。我能想到的最好的就是这个,使用Data.Binaryand 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

它看起来有点难看,有没有更有效的方法可以从 a 中获取任意切片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
4

3 回答 3

2

我认为其他解决方案更好,但您可以使用 Internal 模块来获取底层结构: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

然后,您可以使用标准指针工具生成ByteStrings 指向您想要的位置,通过ForeignPtr直接操作...

于 2013-03-12T03:31:21.120 回答
1

您无法将其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。

于 2013-03-11T20:15:20.117 回答
1

我将把它标记为已解决。这就是我最终使用的:

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
于 2014-04-13T00:51:45.923 回答