zigzag (empty) → 0.0.1.0
raw patch · 6 files changed
+253/−0 lines, 6 filesdep +basedep +tastydep +tasty-hunit
Dependencies added: base, tasty, tasty-hunit, tasty-quickcheck, zigzag
Files
- CHANGELOG.md +5/−0
- LICENSE +30/−0
- README.md +4/−0
- src/Data/Word/Zigzag.hs +97/−0
- test/Main.hs +77/−0
- zigzag.cabal +40/−0
+ CHANGELOG.md view
@@ -0,0 +1,5 @@+# Revision history for zigzag++## 0.0.1.0 -- YYYY-mm-dd++* First version. Released on an unsuspecting world.
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Eric Demko (c) 2022++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Eric Demko nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,4 @@+# zigzag++[Zig-Zag encoding](https://developers.google.com/protocol-buffers/docs/encoding#signed-ints) of integers into natural numbers.+This encoding scheme has the advantage that LEB128, which is normally only specified for unsigned integers, will naturally represent small-magnitude signed integers (positive or negative) in few bytes.
+ src/Data/Word/Zigzag.hs view
@@ -0,0 +1,97 @@+{-# 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/+module Data.Word.Zigzag+ ( toZigzag+ , fromZigzag+ , toZigzagNative+ , fromZigzagNative+ , toZigzag32+ , fromZigzag32+ , toZigzag64+ , fromZigzag64+ ) where++import Data.Bits (unsafeShiftL, unsafeShiftR, complement, (.&.), 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'.+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'.+fromZigzag :: Natural -> Integer+fromZigzag n+ | n `mod` 2 == 0 = 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))+toZigzagNative :: Int -> Word+toZigzagNative = fromIntegral . toZigzag64 . fromIntegral++-- | 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)+toZigzag32 :: Int32 -> Word32+toZigzag32 = fromIntegral . toZigzag64 . fromIntegral++-- | 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)+toZigzag64 :: Int64 -> Word64+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)+fromZigzag64 :: Word64 -> Int64+fromZigzag64 n = fromIntegral $+ (n `unsafeShiftR` 1) `xor` (complement (n .&. 1) + 1)
+ test/Main.hs view
@@ -0,0 +1,77 @@+{-# LANGUAGE TypeApplications #-}++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,(===))+++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+ ]+ ]+ ]++instance Arbitrary Natural where+ arbitrary = fromIntegral @Integer @Natural <$> arbitrary `suchThat` (>=0)+ shrink = fmap (fromIntegral @Integer @Natural)+ . shrink+ . fromIntegral @Natural @Integer
+ zigzag.cabal view
@@ -0,0 +1,40 @@+cabal-version: 3.0+name: zigzag+version: 0.0.1.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++library+ hs-source-dirs: src+ exposed-modules:+ Data.Word.Zigzag+ -- other-modules:+ build-depends:+ , base >=4.11.1 && <4.17+ default-language: Haskell2010+ ghc-options: -O2 -Wall -Wunticked-promoted-constructors++test-suite test+ 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