從字節串獲取任意位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

回答

相關問題