Binrep.Type.Varint

Variable-length integers (varints), a method to store arbitrarily large integers in a space efficient manner.

Note that varints aren't particularly efficient due to their decoding being slow. They are most interesting when you wish to provide support for large integers, but know that many (most?) inputs will be small, and want to be space efficient for them. Protocol Buffers uses them extensively, while Cap'n Proto swears them off.

TODO

• https://en.wikipedia.org/wiki/Variable-length_quantity
• I've defined basic unsigned varints. Signed varints have lots of options. You can use twos comp, zigzag, a sign bit, whatever.

Documentation

newtype Varnat (enc :: Encoding) (cont :: ContinuationBitBehaviour) (e :: Endianness) i

A variable-length unsigned integer (natural).

The base algorithm is to split the natural into groups of 7 bits, and use the MSB to indicate whether another octet follows. You must specify a handful of type variables, which select precise varint behaviour beyond this. See their documentation for details.

You may select the type to use varnats at, but error handling isn't provided: negatives won't work correctly, and overflow cannot be detected. So most of the time, you probably want Natural and Integer.

Some examples:

• @Varnat 'Redundant 'OnContinues 'BE matches VLQ.
• @Varnat 'Redundant 'OnContinues 'LE matches LEB128, protobuf.
• @Varnat 'Bijective 'OnContinues 'LE matches Git's varints.
• @Varnat 'Bijective 'OffContinues 'LE matches BPS's varints.

Constructors

Varnat

Fields

• getVarnat :: i

Instances

Enum i => Enum (Varnat enc cont e i)

Defined in Binrep.Type.Varint

Methods

succ :: Varnat enc cont e i -> Varnat enc cont e i

pred :: Varnat enc cont e i -> Varnat enc cont e i

toEnum :: Int -> Varnat enc cont e i

fromEnum :: Varnat enc cont e i -> Int

enumFrom :: Varnat enc cont e i -> [Varnat enc cont e i]

enumFromThen :: Varnat enc cont e i -> Varnat enc cont e i -> [Varnat enc cont e i]

enumFromTo :: Varnat enc cont e i -> Varnat enc cont e i -> [Varnat enc cont e i]

enumFromThenTo :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i -> [Varnat enc cont e i]

Num i => Num (Varnat enc cont e i)

Defined in Binrep.Type.Varint

Methods

(+) :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

(-) :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

(*) :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

negate :: Varnat enc cont e i -> Varnat enc cont e i

abs :: Varnat enc cont e i -> Varnat enc cont e i

signum :: Varnat enc cont e i -> Varnat enc cont e i

fromInteger :: Integer -> Varnat enc cont e i

Integral i => Integral (Varnat enc cont e i)

Defined in Binrep.Type.Varint

Methods

quot :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

rem :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

div :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

mod :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

quotRem :: Varnat enc cont e i -> Varnat enc cont e i -> (Varnat enc cont e i, Varnat enc cont e i)

divMod :: Varnat enc cont e i -> Varnat enc cont e i -> (Varnat enc cont e i, Varnat enc cont e i)

toInteger :: Varnat enc cont e i -> Integer

Real i => Real (Varnat enc cont e i)

Defined in Binrep.Type.Varint

Methods

toRational :: Varnat enc cont e i -> Rational

Show i => Show (Varnat enc cont e i)

Defined in Binrep.Type.Varint

Methods

showsPrec :: Int -> Varnat enc cont e i -> ShowS

show :: Varnat enc cont e i -> String

showList :: [Varnat enc cont e i] -> ShowS

(VarintContinuation cont, Integral i, Bits i) => Get (Varnat 'Bijective cont 'BE i)

TODO nothing to test against - unsure if correct

Defined in Binrep.Type.Varint

Methods

get :: Getter (Varnat 'Bijective cont 'BE i)

(VarintContinuation cont, Integral i, Bits i) => Get (Varnat 'Bijective cont 'LE i)

Git varint (cont=on), BPS (beat patches) (cont=off)

Defined in Binrep.Type.Varint

Methods

get :: Getter (Varnat 'Bijective cont 'LE i)

(VarintContinuation cont, Integral i, Bits i) => Get (Varnat 'Redundant cont 'BE i)

VLQ (cont=on)

Defined in Binrep.Type.Varint

Methods

get :: Getter (Varnat 'Redundant cont 'BE i)

(VarintContinuation cont, Integral i, Bits i) => Get (Varnat 'Redundant cont 'LE i)

protobuf (cont=on), LEB128 (cont=on)

not truly infinite length since shifters take Int, but practically infinite

Defined in Binrep.Type.Varint

Methods

get :: Getter (Varnat 'Redundant cont 'LE i)

(VarintContinuation cont, Integral i, Bits i) => Put (Varnat 'Redundant cont 'BE i)

Defined in Binrep.Type.Varint

Methods

put :: Varnat 'Redundant cont 'BE i -> Builder

(VarintContinuation cont, Integral i, Bits i) => Put (Varnat 'Redundant cont 'LE i)

Defined in Binrep.Type.Varint

Methods

put :: Varnat 'Redundant cont 'LE i -> Builder

Eq i => Eq (Varnat enc cont e i)

Defined in Binrep.Type.Varint

Methods

(==) :: Varnat enc cont e i -> Varnat enc cont e i -> Bool

(/=) :: Varnat enc cont e i -> Varnat enc cont e i -> Bool

Ord i => Ord (Varnat enc cont e i)

Defined in Binrep.Type.Varint

Methods

compare :: Varnat enc cont e i -> Varnat enc cont e i -> Ordering

(<) :: Varnat enc cont e i -> Varnat enc cont e i -> Bool

(<=) :: Varnat enc cont e i -> Varnat enc cont e i -> Bool

(>) :: Varnat enc cont e i -> Varnat enc cont e i -> Bool

(>=) :: Varnat enc cont e i -> Varnat enc cont e i -> Bool

max :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

min :: Varnat enc cont e i -> Varnat enc cont e i -> Varnat enc cont e i

data ContinuationBitBehaviour

Constructors

OnContinues

on=continue, off=end

OffContinues

on=end, off=continue

data Encoding

Constructors

Redundant

simple, some varints have the same value

Bijective

each integer has exactly 1 varint encoding

class VarintContinuation (cont :: ContinuationBitBehaviour) where

Methods

varintContinue :: Bool

Instances

VarintContinuation 'OffContinues

Defined in Binrep.Type.Varint

Methods

varintContinue :: Bool

VarintContinuation 'OnContinues

Defined in Binrep.Type.Varint

Methods

varintContinue :: Bool

testVarintCont :: forall cont a. VarintContinuation cont => Bits a => a -> Int -> Bool

setVarintCont :: forall cont a. VarintContinuation cont => Bits a => a -> Int -> a