Class EncodedInts


  • @GwtCompatible
    public class EncodedInts
    extends java.lang.Object
    Utilities for encoding and decoding integers.
    • Constructor Summary

      Constructors 
      Constructor Description
      EncodedInts()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static long decodeUintWithLength​(java.io.InputStream input, int bytesPerWord)
      Decodes a unsigned integer consisting of bytesPerWord bytes from supplier in little-endian format as an unsigned 64-bit integer.
      static int decodeZigZag32​(int n)
      Decode a ZigZag-encoded 32-bit signed value.
      static long decodeZigZag64​(long n)
      Decode a ZigZag-encoded 64-bit signed value.
      static int deinterleaveBitPairs1​(long pairs)
      Returns the first int de-interleaved from the result of interleaveBitPairs(int, int).
      static int deinterleaveBitPairs2​(long pairs)
      Returns the second int de-interleaved from the result of interleaveBitPairs(int, int).
      static int deinterleaveBits1​(long bits)
      Returns the first int de-interleaved from the result of interleaveBits(int, int).
      static int deinterleaveBits2​(long bits)
      Returns the second int de-interleaved from the result of interleaveBits(int, int).
      static void encodeUintWithLength​(java.io.OutputStream output, long value, int bytesPerWord)
      Encodes an unsigned integer to consumer in little-endian format using bytesPerWord bytes.
      static int encodeZigZag32​(int n)
      Encode a ZigZag-encoded 32-bit value.
      static long encodeZigZag64​(long n)
      Encode a ZigZag-encoded 64-bit value.
      private static long insertBlankBits​(int value)
      Inserts blank bits between the bits of 'value' such that the MSB is blank and the LSB is unchanged.
      private static long insertBlankPairs​(int value)
      Inserts 00 pairs in between the pairs from 'value'.
      static long interleaveBitPairs​(int val1, int val2)
      Like interleaveBits(int, int) but interleaves bit pairs rather than individual bits.
      static long interleaveBits​(int val1, int val2)
      Returns the interleaving of bits of val1 and val2, where the LSB of val1 is the LSB of the result, and the MSB of val2 is the MSB of the result.
      static long readVarint64​(java.io.InputStream input)
      Reads a variable-encoded signed long.
      private static int removeBlankBits​(long bits)
      Reverses insertBlankBits(int) by extracting the even bits (bit 0, 2, ...).
      private static int removeBlankPairs​(long pairs)
      Reverses {#link #insertBitPairs} by selecting the two LSB bits, dropping the next two, selecting the next two, etc.
      static void writeVarint64​(java.io.OutputStream output, long value)
      Writes a signed long using variable encoding.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • EncodedInts

        public EncodedInts()
    • Method Detail

      • readVarint64

        public static long readVarint64​(java.io.InputStream input)
                                 throws java.io.IOException
        Reads a variable-encoded signed long.

        Note that if you frequently read/write negative numbers, you should consider zigzag-encoding your values before storing them as varints. See encodeZigZag32(int) and decodeZigZag32(int).

        Throws:
        java.io.IOException - if input.read() throws an IOException or returns -1 (EOF), or if the variable-encoded signed long is malformed.
      • writeVarint64

        public static void writeVarint64​(java.io.OutputStream output,
                                         long value)
                                  throws java.io.IOException
        Writes a signed long using variable encoding.

        Note that if you frequently read/write negative numbers, you should consider zigzag-encoding your values before storing them as varints. See encodeZigZag32(int) and decodeZigZag32(int).

        Throws:
        java.io.IOException - if output.write(int) throws an IOException.
      • decodeUintWithLength

        public static long decodeUintWithLength​(java.io.InputStream input,
                                                int bytesPerWord)
                                         throws java.io.IOException
        Decodes a unsigned integer consisting of bytesPerWord bytes from supplier in little-endian format as an unsigned 64-bit integer.

        This method is not compatible with readVarint64(InputStream) or writeVarint64(OutputStream, long).

        Throws:
        java.io.IOException - if input.read() throws an IOException or returns -1 (EOF).
      • encodeUintWithLength

        public static void encodeUintWithLength​(java.io.OutputStream output,
                                                long value,
                                                int bytesPerWord)
                                         throws java.io.IOException
        Encodes an unsigned integer to consumer in little-endian format using bytesPerWord bytes. (The client must ensure that the encoder's buffer is large enough).

        This method is not compatible with readVarint64(InputStream) or writeVarint64(OutputStream, long).

        Throws:
        java.io.IOException - if output.write(int) throws an IOException.
      • encodeZigZag32

        public static int encodeZigZag32​(int n)
        Encode a ZigZag-encoded 32-bit value. ZigZag encodes signed integers into values that can be efficiently encoded with varint. (Otherwise, negative values must be sign-extended to 64 bits to be varint encoded, thus always taking 10 bytes on the wire.)
        Parameters:
        n - A signed 32-bit integer.
        Returns:
        An unsigned 32-bit integer, stored in a signed int because Java has no explicit unsigned support.
      • encodeZigZag64

        public static long encodeZigZag64​(long n)
        Encode a ZigZag-encoded 64-bit value. ZigZag encodes signed integers into values that can be efficiently encoded with varint. (Otherwise, negative values must be sign-extended to 64 bits to be varint encoded, thus always taking 10 bytes on the wire.)
        Parameters:
        n - A signed 64-bit integer.
        Returns:
        An unsigned 64-bit integer, stored in a signed int because Java has no explicit unsigned support.
      • decodeZigZag32

        public static int decodeZigZag32​(int n)
        Decode a ZigZag-encoded 32-bit signed value. ZigZag encodes signed integers into values that can be efficiently encoded with varint. (Otherwise, negative values must be sign-extended to 64 bits to be varint encoded, thus always taking 10 bytes on the wire.)
        Parameters:
        n - A 32-bit integer, stored in a signed int because Java has no explicit unsigned support.
        Returns:
        A signed 32-bit integer.
      • decodeZigZag64

        public static long decodeZigZag64​(long n)
        Decode a ZigZag-encoded 64-bit signed value. ZigZag encodes signed integers into values that can be efficiently encoded with varint. (Otherwise, negative values must be sign-extended to 64 bits to be varint encoded, thus always taking 10 bytes on the wire.)
        Parameters:
        n - A 64-bit integer, stored in a signed long because Java has no explicit unsigned support.
        Returns:
        A signed 64-bit integer.
      • interleaveBits

        public static long interleaveBits​(int val1,
                                          int val2)
        Returns the interleaving of bits of val1 and val2, where the LSB of val1 is the LSB of the result, and the MSB of val2 is the MSB of the result.
      • deinterleaveBits1

        public static int deinterleaveBits1​(long bits)
        Returns the first int de-interleaved from the result of interleaveBits(int, int).
      • deinterleaveBits2

        public static int deinterleaveBits2​(long bits)
        Returns the second int de-interleaved from the result of interleaveBits(int, int).
      • insertBlankBits

        private static final long insertBlankBits​(int value)
        Inserts blank bits between the bits of 'value' such that the MSB is blank and the LSB is unchanged.
      • removeBlankBits

        private static int removeBlankBits​(long bits)
        Reverses insertBlankBits(int) by extracting the even bits (bit 0, 2, ...).
      • interleaveBitPairs

        public static long interleaveBitPairs​(int val1,
                                              int val2)
        Like interleaveBits(int, int) but interleaves bit pairs rather than individual bits. This format is faster to decode than the fully interleaved format, and produces the same results for our use case.

        This code is about 10% faster than interleaveBits(int, int).

      • deinterleaveBitPairs1

        public static int deinterleaveBitPairs1​(long pairs)
        Returns the first int de-interleaved from the result of interleaveBitPairs(int, int).
      • deinterleaveBitPairs2

        public static int deinterleaveBitPairs2​(long pairs)
        Returns the second int de-interleaved from the result of interleaveBitPairs(int, int).
      • insertBlankPairs

        private static final long insertBlankPairs​(int value)
        Inserts 00 pairs in between the pairs from 'value'.
      • removeBlankPairs

        private static int removeBlankPairs​(long pairs)
        Reverses {#link #insertBitPairs} by selecting the two LSB bits, dropping the next two, selecting the next two, etc.