zigzag 0.0.1.0 → 0.1.0.0
raw patch · 4 files changed
+174/−147 lines, 4 filesnew-uploader
Files
- CHANGELOG.md +6/−2
- src/Data/Word/Zigzag.hs +69/−58
- test/Main.hs +70/−62
- zigzag.cabal +29/−25
CHANGELOG.md view
@@ -1,5 +1,9 @@ # Revision history for zigzag -## 0.0.1.0 -- YYYY-mm-dd+## 0.1.0.0 -- 2024-01-31 -* First version. Released on an unsuspecting world.+* Update package metadata.++## 0.0.1.0 -- 2022-01-31++* First version.
src/Data/Word/Zigzag.hs view
@@ -1,17 +1,18 @@ {-# LANGUAGE TypeApplications #-} --- | Zigzag encoding maps signed integers to unsigned integers so that numbers--- with a small absolute value (for instance, -1) have a small varint encoded--- value too. It does this in a way that "zig-zags" back and forth through the--- positive and negative integers, so that -1 is encoded as 1, 1 is encoded as--- 2, -2 is encoded as 3, and so on.------ > zigzag(n) = { 2 * n if 0 <= n--- > { -2 * n - 1 if n < 0------ This description was adapted from--- https://developers.google.com/protocol-buffers/docs/encoding#signed-ints--- which is released under https://creativecommons.org/licenses/by/4.0/+{- | Zigzag encoding maps signed integers to unsigned integers so that numbers+with a small absolute value (for instance, -1) have a small varint encoded+value too. It does this in a way that "zig-zags" back and forth through the+positive and negative integers, so that -1 is encoded as 1, 1 is encoded as+2, -2 is encoded as 3, and so on.++> zigzag(n) = { 2 * n if 0 <= n+> { -2 * n - 1 if n < 0++This description was adapted from+https://developers.google.com/protocol-buffers/docs/encoding#signed-ints+which is released under https://creativecommons.org/licenses/by/4.0/+-} module Data.Word.Zigzag ( toZigzag , fromZigzag@@ -23,75 +24,85 @@ , fromZigzag64 ) where -import Data.Bits (unsafeShiftL, unsafeShiftR, complement, (.&.), xor)-import Data.Int(Int32,Int64)-import Data.Word(Word32,Word64)+import Data.Bits (complement, unsafeShiftL, unsafeShiftR, xor, (.&.))+import Data.Int (Int32, Int64)+import Data.Word (Word32, Word64) import Numeric.Natural (Natural) --- | Encode a big integer with zigzag.------ If you know the size of the data, it is likely more efficient to use one of--- 'toZigzagNative', 'toZigzag32', or 'toZigzag64'.+{- | Encode a big integer with zigzag.++If you know the size of the data, it is likely more efficient to use one of+'toZigzagNative', 'toZigzag32', or 'toZigzag64'.+-} toZigzag :: Integer -> Natural toZigzag n | 0 <= n = fromIntegral $ 2 * n | otherwise = fromIntegral $ (-2) * n - 1 --- | Decode a zigzag-encoded big ingeter.------ If you know the size of the data, it is likely more efficient to use one of--- 'fromZigzagNative', 'fromZigzag32', or 'fromZigzag64'.+{- | Decode a zigzag-encoded big ingeter.++If you know the size of the data, it is likely more efficient to use one of+'fromZigzagNative', 'fromZigzag32', or 'fromZigzag64'.+-} fromZigzag :: Natural -> Integer fromZigzag n- | n `mod` 2 == 0 = fromIntegral $ n `div` 2+ | even n = fromIntegral $ n `div` 2 | otherwise = negate . fromIntegral $ (n + 1) `div` 2 --- | Encode a native-size integer with zigzag.------ In C, this is:------ > (n << 1) ^ (n >> (CHAR_BIT * sizeof(int) - 1))+{- | Encode a native-size integer with zigzag.++In C, this is:++> (n << 1) ^ (n >> (CHAR_BIT * sizeof(int) - 1))+-} toZigzagNative :: Int -> Word toZigzagNative = fromIntegral . toZigzag64 . fromIntegral --- | Decode a native-size zigzag-encoded integer.------ In C, this is:------ > (n >> 1) ^ (~(n & 1) + 1)+{- | Decode a native-size zigzag-encoded integer.++In C, this is:++> (n >> 1) ^ (~(n & 1) + 1)+-} fromZigzagNative :: Word -> Int fromZigzagNative = fromIntegral . fromZigzag64 . fromIntegral --- | Encode a 32-bit integer with zigzag.------ In C, this is:------ > (n << 1) ^ (n >> 31)+{- | Encode a 32-bit integer with zigzag.++In C, this is:++> (n << 1) ^ (n >> 31)+-} toZigzag32 :: Int32 -> Word32 toZigzag32 = fromIntegral . toZigzag64 . fromIntegral --- | Decode a 32-bit zigzag-encoded integer.------ In C, this is:------ > (n >> 1) ^ (~(n & 1) + 1)+{- | Decode a 32-bit zigzag-encoded integer.++In C, this is:++> (n >> 1) ^ (~(n & 1) + 1)+-} fromZigzag32 :: Word32 -> Int32 fromZigzag32 = fromIntegral . fromZigzag64 . fromIntegral --- | Encode a 64-bit integer with zigzag.------ In C, this is:------ > (n << 1) ^ (n >> 63)+{- | Encode a 64-bit integer with zigzag.++In C, this is:++> (n << 1) ^ (n >> 63)+-} toZigzag64 :: Int64 -> Word64-toZigzag64 i = fromIntegral @Int64 @Word64 $- (i `unsafeShiftL` 1) `xor` (i `unsafeShiftR` 63)+toZigzag64 i =+ fromIntegral @Int64 @Word64 $+ (i `unsafeShiftL` 1) `xor` (i `unsafeShiftR` 63) --- | Decode a 64-bit zigzag-encoded integer.------ In C, this is:------ > (n >> 1) ^ (~(n & 1) + 1)+{- | Decode a 64-bit zigzag-encoded integer.++In C, this is:++> (n >> 1) ^ (~(n & 1) + 1)+-} fromZigzag64 :: Word64 -> Int64-fromZigzag64 n = fromIntegral $- (n `unsafeShiftR` 1) `xor` (complement (n .&. 1) + 1)+fromZigzag64 n =+ fromIntegral $+ (n `unsafeShiftR` 1) `xor` (complement (n .&. 1) + 1)
test/Main.hs view
@@ -1,77 +1,85 @@ {-# LANGUAGE TypeApplications #-}+{-# OPTIONS_GHC -Wno-orphans #-} module Main where import Data.Word.Zigzag import Numeric.Natural (Natural)-import Test.Tasty (TestTree,defaultMain,testGroup)-import Test.Tasty.HUnit (testCase,(@=?))-import Test.Tasty.QuickCheck (Arbitrary(..),suchThat)-import Test.Tasty.QuickCheck (testProperty,(===))-+import Test.Tasty (TestTree, defaultMain, testGroup)+import Test.Tasty.HUnit (testCase, (@=?))+import Test.Tasty.QuickCheck (Arbitrary (..), suchThat, testProperty, (===)) main :: IO () main = defaultMain tests tests :: TestTree-tests = testGroup "zigzag"- [ testGroup "inverses"- [ testProperty "to-from-bigint" $ \i ->- (fromZigzag . toZigzag) i === i- , testProperty "from-to-bigint" $ \i ->- (toZigzag . fromZigzag) i === i- , testProperty "to-from-int" $ \i ->- (fromZigzagNative . toZigzagNative) i === i- , testProperty "from-to-int" $ \i ->- (toZigzagNative . fromZigzagNative) i === i- , testProperty "to-from-i32" $ \i ->- (fromZigzag32 . toZigzag32) i === i- , testProperty "from-to-i32" $ \i ->- (toZigzag32 . fromZigzag32) i === i- , testProperty "to-from-i64" $ \i ->- (fromZigzag64 . toZigzag64) i === i- , testProperty "from-to-i64" $ \i ->- (toZigzag64 . fromZigzag64) i === i- ]- , testGroup "spec-examples"- [ testGroup "bigint"- [ testCase "0" $ toZigzag 0 @=? 0- , testCase "1" $ toZigzag 1 @=? 2- , testCase "-1" $ toZigzag (-1) @=? 1- , testCase "-2" $ toZigzag (-2) @=? 3- , testCase "2147483647" $ toZigzag 2147483647 @=? 4294967294- , testCase "-2147483648" $ toZigzag (-2147483648) @=? 4294967295- ]- , testGroup "native"- [ testCase "0" $ toZigzagNative 0 @=? 0- , testCase "1" $ toZigzagNative 1 @=? 2- , testCase "-1" $ toZigzagNative (-1) @=? 1- , testCase "-2" $ toZigzagNative (-2) @=? 3- , testCase "2147483647" $ toZigzagNative 2147483647 @=? 4294967294- , testCase "-2147483648" $ toZigzagNative (-2147483648) @=? 4294967295- ]- , testGroup "i32"- [ testCase "0" $ toZigzag32 0 @=? 0- , testCase "1" $ toZigzag32 1 @=? 2- , testCase "-1" $ toZigzag32 (-1) @=? 1- , testCase "-2" $ toZigzag32 (-2) @=? 3- , testCase "2147483647" $ toZigzag32 2147483647 @=? 4294967294- , testCase "-2147483648" $ toZigzag32 (-2147483648) @=? 4294967295- ]- , testGroup "i64"- [ testCase "0" $ toZigzag64 0 @=? 0- , testCase "1" $ toZigzag64 1 @=? 2- , testCase "-1" $ toZigzag64 (-1) @=? 1- , testCase "-2" $ toZigzag64 (-2) @=? 3- , testCase "2147483647" $ toZigzag64 2147483647 @=? 4294967294- , testCase "-2147483648" $ toZigzag64 (-2147483648) @=? 4294967295- ]+tests =+ testGroup+ "zigzag"+ [ testGroup+ "inverses"+ [ testProperty "to-from-bigint" $ \i ->+ (fromZigzag . toZigzag) i === i+ , testProperty "from-to-bigint" $ \i ->+ (toZigzag . fromZigzag) i === i+ , testProperty "to-from-int" $ \i ->+ (fromZigzagNative . toZigzagNative) i === i+ , testProperty "from-to-int" $ \i ->+ (toZigzagNative . fromZigzagNative) i === i+ , testProperty "to-from-i32" $ \i ->+ (fromZigzag32 . toZigzag32) i === i+ , testProperty "from-to-i32" $ \i ->+ (toZigzag32 . fromZigzag32) i === i+ , testProperty "to-from-i64" $ \i ->+ (fromZigzag64 . toZigzag64) i === i+ , testProperty "from-to-i64" $ \i ->+ (toZigzag64 . fromZigzag64) i === i+ ]+ , testGroup+ "spec-examples"+ [ testGroup+ "bigint"+ [ testCase "0" $ toZigzag 0 @=? 0+ , testCase "1" $ toZigzag 1 @=? 2+ , testCase "-1" $ toZigzag (-1) @=? 1+ , testCase "-2" $ toZigzag (-2) @=? 3+ , testCase "2147483647" $ toZigzag 2147483647 @=? 4294967294+ , testCase "-2147483648" $ toZigzag (-2147483648) @=? 4294967295+ ]+ , testGroup+ "native"+ [ testCase "0" $ toZigzagNative 0 @=? 0+ , testCase "1" $ toZigzagNative 1 @=? 2+ , testCase "-1" $ toZigzagNative (-1) @=? 1+ , testCase "-2" $ toZigzagNative (-2) @=? 3+ , testCase "2147483647" $ toZigzagNative 2147483647 @=? 4294967294+ , testCase "-2147483648" $ toZigzagNative (-2147483648) @=? 4294967295+ ]+ , testGroup+ "i32"+ [ testCase "0" $ toZigzag32 0 @=? 0+ , testCase "1" $ toZigzag32 1 @=? 2+ , testCase "-1" $ toZigzag32 (-1) @=? 1+ , testCase "-2" $ toZigzag32 (-2) @=? 3+ , testCase "2147483647" $ toZigzag32 2147483647 @=? 4294967294+ , testCase "-2147483648" $ toZigzag32 (-2147483648) @=? 4294967295+ ]+ , testGroup+ "i64"+ [ testCase "0" $ toZigzag64 0 @=? 0+ , testCase "1" $ toZigzag64 1 @=? 2+ , testCase "-1" $ toZigzag64 (-1) @=? 1+ , testCase "-2" $ toZigzag64 (-2) @=? 3+ , testCase "2147483647" $ toZigzag64 2147483647 @=? 4294967294+ , testCase "-2147483648" $ toZigzag64 (-2147483648) @=? 4294967295+ ]+ ] ]- ] instance Arbitrary Natural where- arbitrary = fromIntegral @Integer @Natural <$> arbitrary `suchThat` (>=0)- shrink = fmap (fromIntegral @Integer @Natural)- . shrink- . fromIntegral @Natural @Integer+ arbitrary = fromIntegral @Integer @Natural <$> arbitrary `suchThat` (>= 0)+ shrink =+ fmap (fromIntegral @Integer @Natural)+ . shrink+ . fromIntegral @Natural @Integer
zigzag.cabal view
@@ -1,40 +1,44 @@-cabal-version: 3.0-name: zigzag-version: 0.0.1.0-synopsis: Zigzag encoding of integers into unsigned integers.+cabal-version: 3.0+name: zigzag+version: 0.1.0.0+synopsis: Zigzag encoding of integers into unsigned integers. description: Zigzag encoding is usually a precursor to a varint encoding such as LEB128. It has the advantage that numbers nearer zero are represented with only the lower-order bits set.-category: Data-homepage: https://github.com/byteverse/zigzag-bug-reports: https://github.com/byteverse/zigzag/issues-author: Eric Demko-maintainer: edemko@layer3com.com-copyright: 2022 Eric Demko-license: BSD-3-Clause-license-file: LICENSE-extra-source-files: CHANGELOG.md, README.md +category: Data+homepage: https://github.com/byteverse/zigzag+bug-reports: https://github.com/byteverse/zigzag/issues+author: Eric Demko+maintainer: amartin@layer3com.com+copyright: 2022 Eric Demko+license: BSD-3-Clause+license-file: LICENSE+extra-doc-files:+ CHANGELOG.md+ README.md+ library- hs-source-dirs: src- exposed-modules:- Data.Word.Zigzag- -- other-modules:- build-depends:- , base >=4.11.1 && <4.17+ hs-source-dirs: src+ exposed-modules: Data.Word.Zigzag+ build-depends: base >=4.11.1 && <5 default-language: Haskell2010- ghc-options: -O2 -Wall -Wunticked-promoted-constructors+ ghc-options: -O2 -Wall -Wunticked-promoted-constructors test-suite test- hs-source-dirs: test- main-is: Main.hs- type: exitcode-stdio-1.0+ hs-source-dirs: test+ main-is: Main.hs+ type: exitcode-stdio-1.0 build-depends: , base- -- , quickcheck-classes , tasty , tasty-hunit , tasty-quickcheck , zigzag+ default-language: Haskell2010- ghc-options: -Wall -O2+ ghc-options: -Wall -O2++source-repository head+ type: git+ location: git://github.com/byteverse/zigzag.git