2

Bytestringレイジーを使用してビット ストリームを表現したいと考えています。このストリームからビットの任意のスライスを効率的に取得できる必要があります。たとえば、長さが10 の があり、元の からビット 24 ～ 36 で構成されるByteString新しい をスライスしたいとします。ByteStringByteString

問題は、ByteStringsが の配列であるWord8ため、8 の倍数ではない範囲を取得するのが難しいことです。私が思いついた最高のものは、 and を使用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) ビットを取得し、a に格納します。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
4

3 に答える 3

2

他のソリューションの方がはるかに優れていると思いますが、内部モジュールを使用して基になる構造を取得できます: 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操作することにより、必要な場所を正確に指す sを生成できますForeignPtr...

于 2013-03-12T03:31:21.120 に答える
1

ByteStringAPIタイプとしてこれを効率的にすることはできません。これは、必要な「ビット」が最初のバイトのオフセットから実際に開始するという情報を伝達しないためです。

最善の策は、ラッパータイプを作成することです。

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 に答える