bytebuild 0.3.9.0 → 0.3.10.0

raw patch · 5 files changed

+157/−20 lines, 5 filesdep +zigzagdep ~QuickCheckdep ~basedep ~bytestringPVP ok

version bump matches the API change (PVP)

Dependencies added: zigzag

Dependency ranges changed: QuickCheck, base, bytestring

API changes (from Hackage documentation)

Files

• CHANGELOG.md +9/−0
• bytebuild.cabal +5/−4
• src/Data/Bytes/Builder.hs +128/−15
• src/Data/Bytes/Builder/Bounded.hs +5/−1
• test/Main.hs +10/−0

@@ -5,6 +5,15 @@ `small-bytearray-builder` is now just a compatibility shim to ease the migration process. +## 0.3.10.0 -- 2022-03-01++* Add upper bound on base since this does not build with GHC 9.2.+* Add `rebuild`+* Add `copyCons` for copying small byte sequences with extra byte in front+* Use `zigzag` library from hackage+* Seven eights encoding+* Finish out LEB for 32-bit and signed 32/64+ ## 0.3.9.0 -- 2021-11-19  * Add `cstring#`

@@ -1,6 +1,6 @@ cabal-version: 2.2 name: bytebuild-version: 0.3.9.0+version: 0.3.10.0 synopsis: Serialize to a small byte arrays description:   This is similar to the builder facilities provided by@@ -46,9 +46,9 @@   reexported-modules:     Data.Bytes.Chunks   build-depends:-    , base >=4.12.0.0 && <5+    , base >=4.12.0.0 && <4.16     , byteslice >=0.2.6 && <0.3-    , bytestring >=0.10.8.2 && <0.11+    , bytestring >=0.10.8.2 && <0.12     , haskell-src-meta >=0.8     , integer-logarithms >=1.0.3 && <1.1     , natural-arithmetic >=0.1 && <0.2@@ -58,6 +58,7 @@     , template-haskell >=2.16     , text-short >=0.1.3 && <0.2     , wide-word >=0.1.0.9 && <0.2+    , zigzag   if flag(checked)     build-depends: primitive-checked >= 0.7 && <0.8   else@@ -77,7 +78,7 @@     HexWord64     Word16Tree   build-depends:-    , QuickCheck >=2.13.1 && <2.14+    , QuickCheck >=2.13.1 && <2.15     , base >=4.12.0.0 && <5     , bytebuild     , byteslice

@@ -22,6 +22,7 @@     -- * Materialized Byte Sequences   , bytes   , copy+  , copyCons   , copy2   , insert   , byteArray@@ -32,6 +33,9 @@   , cstring#   , cstringLen   , stringUtf8+    -- * Byte Sequence Encodings+  , sevenEightRight+  , sevenEightSmile     -- * Encode Integral Types     -- ** Human-Readable   , word64Dec@@ -91,7 +95,10 @@   , int16LE     -- **** LEB128   , intLEB128+  , int32LEB128+  , int64LEB128   , wordLEB128+  , word32LEB128   , word64LEB128     -- *** Many   , word8Array@@ -125,24 +132,26 @@   , replicate     -- * Control   , flush+    -- * Rebuild+  , rebuild   ) where  import Prelude hiding (replicate)  import Control.Exception (SomeException,toException)-import Control.Monad.ST (ST,runST) import Control.Monad.IO.Class (MonadIO,liftIO)-import Data.Bits (unsafeShiftR,unsafeShiftL,xor,finiteBitSize)+import Control.Monad.ST (ST,runST)+import Data.Bits ((.&.),(.|.),unsafeShiftL,unsafeShiftR)+import Data.Bytes.Builder.Unsafe (addCommitsLength,copyReverseCommits) import Data.Bytes.Builder.Unsafe (Builder(Builder),commitDistance1) import Data.Bytes.Builder.Unsafe (BuilderState(BuilderState),pasteIO) import Data.Bytes.Builder.Unsafe (Commits(Initial,Mutable,Immutable))-import Data.Bytes.Builder.Unsafe (reverseCommitsOntoChunks) import Data.Bytes.Builder.Unsafe (commitsOntoChunks)+import Data.Bytes.Builder.Unsafe (reverseCommitsOntoChunks) import Data.Bytes.Builder.Unsafe (stringUtf8,cstring,fromEffect)-import Data.Bytes.Builder.Unsafe (addCommitsLength,copyReverseCommits)-import Data.ByteString.Short.Internal (ShortByteString(SBS)) import Data.Bytes.Chunks (Chunks(ChunksNil)) import Data.Bytes.Types (Bytes(Bytes),MutableBytes(MutableBytes))+import Data.ByteString.Short.Internal (ShortByteString(SBS)) import Data.Char (ord) import Data.Foldable (foldlM) import Data.Int (Int64,Int32,Int16,Int8)@@ -150,11 +159,12 @@ import Data.Text.Short (ShortText) import Data.WideWord (Word128,Word256) import Data.Word (Word64,Word32,Word16,Word8)+import Data.Word.Zigzag (toZigzagNative,toZigzag32,toZigzag64) import Foreign.C.String (CStringLen) import GHC.ByteOrder (ByteOrder(BigEndian,LittleEndian),targetByteOrder)+import GHC.Exts (Addr#,(*#),oneShot) import GHC.Exts (Int(I#),Char(C#),Int#,State#,ByteArray#,(>=#)) import GHC.Exts (RealWorld,(+#),(-#),(<#))-import GHC.Exts (Addr#,(*#)) import GHC.Integer.Logarithms.Compat (integerLog2#) import GHC.IO (IO(IO),stToIO) import GHC.Natural (naturalFromInteger,naturalToInteger)@@ -164,6 +174,7 @@  import qualified Arithmetic.Nat as Nat import qualified Arithmetic.Types as Arithmetic+import qualified Data.Bytes as Bytes import qualified Data.Bytes.Builder.Bounded as Bounded import qualified Data.Bytes.Builder.Bounded.Unsafe as UnsafeBounded import qualified Data.Primitive as PM@@ -192,8 +203,8 @@   reverseCommitsOntoChunks cs0 cs  -- | Variant of 'runOnto' that conses the additional chunks--- in reverse order. -reversedOnto :: +-- in reverse order.+reversedOnto ::      Int -- ^ Size of initial chunk (use 4080 if uncertain)   -> Builder -- ^ Builder   -> Chunks@@ -392,6 +403,22 @@   where   !(I# newSz) = max (I# slen#) 4080 +-- | Variant of 'copy' that additionally pastes an extra byte in+-- front of the bytes.+copyCons :: Word8 -> Bytes -> Builder+copyCons (W8# w0) (Bytes (ByteArray src# ) (I# soff# ) (I# slen# )) = Builder+  (\buf0 off0 len0 cs0 s0 -> case len0 <# (slen# +# 1#) of+    1# -> case Exts.newByteArray# newSz s0 of+        (# s1, buf1 #) -> case Exts.copyByteArray# src# soff# buf1 1# slen# s1 of+          s2 -> case Exts.writeWord8Array# buf1 0# w0 s2 of+            s3 -> (# s3, buf1, slen# +# 1#, newSz -# (slen# +# 1#), Mutable buf0 off0 cs0 #)+    _ -> let !s1 = Exts.copyByteArray# src# soff# buf0 (off0 +# 1#) slen# s0+             !s2 = Exts.writeWord8Array# buf0 off0 w0 s1+          in (# s2, buf0, off0 +# (slen# +# 1#), len0 -# (slen# +# 1#), cs0 #)+  )+  where+  !(I# newSz) = max ((I# slen#) + 1) 4080+ cstring# :: Addr# -> Builder {-# inline cstring# #-} cstring# x = cstring (Exts.Ptr x)@@ -410,6 +437,66 @@   where   !(I# newSz) = max (I# slen#) 4080 +-- | Encode seven bytes into eight so that the encoded form is eight-bit clean.+-- Specifically segment the input bytes inot 7-bit groups (lowest-to-highest+-- index byte, most-to-least significant bit within a byte), pads the last group+-- with trailing zeros, and forms octects by prepending a zero to each group.+--+-- The name was chosen because this pads the input bits with zeros on the right,+-- and also because this was likely the originally-indended behavior of the+-- SMILE standard (see 'sevenEightSmile'). Right padding the input bits to a+-- multiple of seven, as in this variant, is consistent with base64 encodings+-- (which encodes 3 bytes in 4) and base85 (which encodes 4 bytes in 5).+sevenEightRight :: Bytes -> Builder+sevenEightRight bs0 = case toWord 0 0 bs0 of+  (0, _) -> mempty+  (len, w) -> go (len * 8) w <> sevenEightSmile (Bytes.unsafeDrop len bs0)+  where+  go :: Int -> Word64 -> Builder+  go !nBits !_ | nBits <= 0 = mempty+  go !nBits !w =+    let octet = (fromIntegral $ unsafeShiftR w (8*7+1)) .&. 0x7f+     in word8 octet <> go (nBits - 7) (unsafeShiftL w 7)+  toWord :: Int -> Word64 -> Bytes -> (Int, Word64)+  toWord !i !acc !bs+    | Bytes.length bs == 0 = (i, acc)+    | otherwise =+        let b = fromIntegral @Word8 @Word64 $ Bytes.unsafeIndex bs 0+            acc' = acc .|. unsafeShiftL b (fromIntegral $ 8 * (7 - i))+         in if i < 7+            then toWord (i + 1) acc' (Bytes.unsafeDrop 1 bs)+            else (i, acc)++-- | Encode seven bytes into eight so that the encoded form is eight-bit clean.+-- Specifically segment the input bytes inot 7-bit groups (lowest-to-highest+-- index byte, most-to-least significant bit within a byte), then pad each group+-- with zeros on the left until each group is an octet.+--+-- The name was chosen because this is the implementation that is used (probably+-- unintentionally) in the reference SMILE implementation, and so is expected tp+-- be accepted by existing SMILE consumers.+sevenEightSmile :: Bytes -> Builder+sevenEightSmile bs0 = case toWord 0 0 bs0 of+  (0, _) -> mempty+  (len, w) -> go (len * 8) w <> sevenEightSmile (Bytes.unsafeDrop len bs0)+  where+  go :: Int -> Word64 -> Builder+  go !nBits !w+    | nBits == 0 = mempty+    | nBits < 7 = go 7 (unsafeShiftR w (7 - nBits))+  go !nBits !w =+    let octet = (fromIntegral $ unsafeShiftR w (8*7+1)) .&. 0x7f+     in word8 octet <> go (nBits - 7) (unsafeShiftL w 7)+  toWord :: Int -> Word64 -> Bytes -> (Int, Word64)+  toWord !i !acc !bs+    | Bytes.length bs == 0 = (i, acc)+    | otherwise =+        let b = fromIntegral @Word8 @Word64 $ Bytes.unsafeIndex bs 0+            acc' = acc .|. unsafeShiftL b (fromIntegral $ 8 * (7 - i))+         in if i < 7+            then toWord (i + 1) acc' (Bytes.unsafeDrop 1 bs)+            else (i, acc)+ -- | Create a builder from two byte sequences. This always results in two -- calls to @memcpy@. This is beneficial when the byte sequences are -- known to be small (less than 256 bytes).@@ -1058,20 +1145,27 @@ c2w :: Char -> Word8 c2w = fromIntegral . ord --- In C, this is: (n << 1) ^ (n >> (BIT_WIDTH - 1))-zigZagNative :: Int -> Word-zigZagNative s = fromIntegral @Int @Word-  ((unsafeShiftL s 1) `xor` (unsafeShiftR s (finiteBitSize (undefined :: Word) - 1)))- -- | Encode a signed machine-sized integer with LEB-128. This uses -- zig-zag encoding. intLEB128 :: Int -> Builder-intLEB128 = wordLEB128 . zigZagNative+intLEB128 = wordLEB128 . toZigzagNative +-- | Encode a 32-bit signed integer with LEB-128. This uses zig-zag encoding.+int32LEB128 :: Int32 -> Builder+int32LEB128 = word32LEB128 . toZigzag32++-- | Encode a 64-bit signed integer with LEB-128. This uses zig-zag encoding.+int64LEB128 :: Int64 -> Builder+int64LEB128 = word64LEB128 . toZigzag64+ -- | Encode a machine-sized word with LEB-128. wordLEB128 :: Word -> Builder wordLEB128 w = fromBounded Nat.constant (Bounded.wordLEB128 w) +-- | Encode a 32-bit word with LEB-128.+word32LEB128 :: Word32 -> Builder+word32LEB128 w = fromBounded Nat.constant (Bounded.word32LEB128 w)+ -- | Encode a 64-bit word with LEB-128. word64LEB128 :: Word64 -> Builder word64LEB128 w = fromBounded Nat.constant (Bounded.word64LEB128 w)@@ -1169,7 +1263,7 @@ -- For numbers less than 1073741829, this gives a correct answer. approxDiv10 :: Word -> Word approxDiv10 !n = unsafeShiftR (0x1999999A * n) 32-  + -- -- A weird beast useful for rewrite rules. Not yet used. This will -- -- ultimately replace fromEffect and fromBounded. -- require :: Int -> Builder@@ -1184,3 +1278,22 @@  unsafeWordToWord8 :: Word -> Word8 unsafeWordToWord8 (W# w) = W8# w++-- | This function and the documentation for it are copied from+-- Takano Akio's fast-builder library.+--+-- @'rebuild' b@ is equivalent to @b@, but it allows GHC to assume+-- that @b@ will be run at most once. This can enable various+-- optimizations that greately improve performance.+--+-- There are two types of typical situations where a use of 'rebuild'+-- is often a win:+--+-- * When constructing a builder using a recursive function. e.g.+--  @rebuild $ foldr ...@.+-- * When constructing a builder using a conditional expression. e.g.+--  @rebuild $ case x of ... @+rebuild :: Builder -> Builder+{-# inline rebuild #-}+rebuild (Builder f) = Builder $ oneShot $ \a -> oneShot $ \b -> oneShot $ \c -> oneShot $ \d -> oneShot $ \e ->+  f a b c d e

@@ -97,6 +97,7 @@   , int16LE     -- **** LEB128   , wordLEB128+  , word32LEB128   , word64LEB128     -- * Encode Floating-Point Types   , doubleDec@@ -850,6 +851,10 @@ wordLEB128 :: Word -> Builder 10 wordLEB128 (W# w) = lebCommon (W# w) +-- | Encode a 32-bit word with LEB-128.+word32LEB128 :: Word32 -> Builder 5+word32LEB128 (W32# w) = lebCommon (W# w)+ -- | Encode a 64-bit word with LEB-128. word64LEB128 :: Word64 -> Builder 10 word64LEB128 (W64# w) = lebCommon (W# w)@@ -1071,4 +1076,3 @@  foreign import ccall unsafe "bytebuild_paste_double" c_paste_double ::   MutableByteArray# s -> Int# -> Double# -> IO Int-

@@ -255,6 +255,16 @@         runConcat 1 (naturalDec y)         ===         pack (show y)+    , testGroup "seven/eight encoding"+      [ THU.testCase "deadbeef" $ do+        let inp = Latin1.fromString "\xDE\xAD\xBE\xEF"+        (Chunks.concat . run 16) (sevenEightRight inp)+          @=? Latin1.fromString "\x6F\x2B\x37\x6E\x78"+      , THU.testCase "deadbeef-smile" $ do+        let inp = Latin1.fromString "\xDE\xAD\xBE\xEF"+        (Chunks.concat . run 16) (sevenEightSmile inp)+          @=?Latin1.fromString "\x6F\x2B\x37\x6E\x0F"+      ]     ]   , testGroup "alternate"     [ TQC.testProperty "HexWord64" $ \x y ->