从字节串获取任意位bits

我想用懒惰的Bytestring来表示位流。我需要能够有效地从这个流中获取任意位的位。例如，我可能有一个长度为10的ByteString，并且我想要分割由原始ByteString的第24-36位组成的新ByteString。从字节串获取任意位bits

问题是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的开头将会有一些额外的位，所以跳过那些
GET（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

来源

2013-03-11 cdk

你知不知道那个平淡无味的'旧'UArray'如果包含'Bool'，它已经使用了非常紧凑的表示形式？为什么不使用它？ – 2013-03-11 22:46:50

@DanielWagner：我没有想到这一点，这将是我的问题的一个优雅的解决方案，但不幸的是我需要使用懒惰的'ByteString's，我不认为我能够保持懒惰，而转换为'UAarray'或取消装箱的'Vector'。尽管我可以尝试一个盒装表示，并看看它如何展示，但效率是关键。 – cdk 2013-03-11 23:05:28

我打算将其标记为已解决。这就是我最终使用的：

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-13 00:51:45 cdk

你不能让这种高效与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-11 20:15:20

这肯定会帮助清理我的示例函数，但我更感兴趣的是实际提取切片位的方法。 – cdk 2013-03-11 20:26:22

之后你想怎么做？ – 2013-03-11 22:13:00

将它们解析为二进制数据，可能是“Word”或“Int”类型 – cdk 2013-03-11 22:18:14

我觉得其他的解决方案是更好的方式但您可以使用内置模块，以获得在底层结构：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 ...

来源

2013-03-12 03:31:21 sclv

从字节串获取任意位bits

回答

相关问题