src/java/org/apache/cassandra/utils/vint/VIntCoding.java - cassandra - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 // Protocol Buffers - Google's data interchange format
 // Copyright 2008 Google Inc.  All rights reserved.
 // https://developers.google.com/protocol-buffers/
 //
 // 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 Google Inc. nor the names of its
 // 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.
 package org.apache.cassandra.utils.vint;

 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
 import java.nio.ByteBuffer;

 import net.nicoulaj.compilecommand.annotations.Inline;

 /**
  * Borrows idea from
  * https://developers.google.com/protocol-buffers/docs/encoding#varints
  */
 public class VIntCoding
 {

     public static long readUnsignedVInt(DataInput input) throws IOException {
         int firstByte = input.readByte();

         //Bail out early if this is one byte, necessary or it fails later
         if (firstByte >= 0)
             return firstByte;

         int size = numberOfExtraBytesToRead(firstByte);
         long retval = firstByte & firstByteValueMask(size);
         for (int ii = 0; ii < size; ii++)
         {
             byte b = input.readByte();
             retval <<= 8;
             retval |= b & 0xff;
         }

         return retval;
     }

     /**
      * Note this method is the same as {@link #readUnsignedVInt(DataInput)},
      * except that we do *not* block if there are not enough bytes in the buffer
      * to reconstruct the value.
      *
      * WARNING: this method is only safe for vints we know to be representable by a positive long value.
      *
      * @return -1 if there are not enough bytes in the input to read the value; else, the vint unsigned value.
      */
     public static long getUnsignedVInt(ByteBuffer input, int readerIndex)
     {
         return getUnsignedVInt(input, readerIndex, input.limit());
     }

     public static long getUnsignedVInt(ByteBuffer input, int readerIndex, int readerLimit)
     {
         if (readerIndex >= readerLimit)
             return -1;

         int firstByte = input.get(readerIndex++);

         //Bail out early if this is one byte, necessary or it fails later
         if (firstByte >= 0)
             return firstByte;

         int size = numberOfExtraBytesToRead(firstByte);
         if (readerIndex + size > readerLimit)
             return -1;

         long retval = firstByte & firstByteValueMask(size);
         for (int ii = 0; ii < size; ii++)
         {
             byte b = input.get(readerIndex++);
             retval <<= 8;
             retval |= b & 0xff;
         }

         return retval;
     }

     public static long readVInt(DataInput input) throws IOException {
         return decodeZigZag64(readUnsignedVInt(input));
     }

     // & this with the first byte to give the value part for a given extraBytesToRead encoded in the byte
     public static int firstByteValueMask(int extraBytesToRead)
     {
         // by including the known 0bit in the mask, we can use this for encodeExtraBytesToRead
         return 0xff >> extraBytesToRead;
     }

     public static int encodeExtraBytesToRead(int extraBytesToRead)
     {
         // because we have an extra bit in the value mask, we just need to invert it
         return ~firstByteValueMask(extraBytesToRead);
     }

     public static int numberOfExtraBytesToRead(int firstByte)
     {
         // we count number of set upper bits; so if we simply invert all of the bits, we're golden
         // this is aided by the fact that we only work with negative numbers, so when upcast to an int all
         // of the new upper bits are also set, so by inverting we set all of them to zero
         return Integer.numberOfLeadingZeros(~firstByte) - 24;
     }

     protected static final ThreadLocal<byte[]> encodingBuffer = new ThreadLocal<byte[]>()
     {
         @Override
         public byte[] initialValue()
         {
             return new byte[9];
         }
     };

     public static void writeUnsignedVInt(long value, DataOutput output) throws IOException {
         int size = VIntCoding.computeUnsignedVIntSize(value);
         if (size == 1)
         {
             output.write((int)value);
             return;
         }

         output.write(VIntCoding.encodeVInt(value, size), 0, size);
     }

     @Inline
     public static byte[] encodeVInt(long value, int size) {
         byte encodingSpace[] = encodingBuffer.get();
         int extraBytes = size - 1;

         for (int i = extraBytes ; i >= 0; --i)
         {
             encodingSpace[i] = (byte) value;
             value >>= 8;
         }
         encodingSpace[0] |= VIntCoding.encodeExtraBytesToRead(extraBytes);
         return encodingSpace;
     }

     public static void writeVInt(long value, DataOutput output) throws IOException {
         writeUnsignedVInt(encodeZigZag64(value), output);
     }

     /**
      * Decode 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.)
      *
      * @param n An unsigned 64-bit integer, stored in a signed int because
      *          Java has no explicit unsigned support.
      * @return A signed 64-bit integer.
      */
     public static long decodeZigZag64(final long n) {
         return (n >>> 1) ^ -(n & 1);
     }

     /**
      * 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.)
      *
      * @param n A signed 64-bit integer.
      * @return An unsigned 64-bit integer, stored in a signed int because
      *         Java has no explicit unsigned support.
      */
     public static long encodeZigZag64(final long n) {
         // Note:  the right-shift must be arithmetic
         return (n << 1) ^ (n >> 63);
     }

     /** Compute the number of bytes that would be needed to encode a varint. */
     public static int computeVIntSize(final long param) {
         return computeUnsignedVIntSize(encodeZigZag64(param));
     }

     /** Compute the number of bytes that would be needed to encode an unsigned varint. */
     public static int computeUnsignedVIntSize(final long value) {
         int magnitude = Long.numberOfLeadingZeros(value | 1); // | with 1 to ensure magntiude <= 63, so (63 - 1) / 7 <= 8
         return 9 - ((magnitude - 1) / 7);
     }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	// Protocol Buffers - Google's data interchange format
	// Copyright 2008 Google Inc. All rights reserved.
	// https://developers.google.com/protocol-buffers/
	//
	// 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 Google Inc. nor the names of its
	// 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.
	package org.apache.cassandra.utils.vint;

	import java.io.DataInput;
	import java.io.DataOutput;
	import java.io.IOException;
	import java.nio.ByteBuffer;

	import net.nicoulaj.compilecommand.annotations.Inline;

	/**
	* Borrows idea from
	* https://developers.google.com/protocol-buffers/docs/encoding#varints
	*/
	public class VIntCoding
	{

	public static long readUnsignedVInt(DataInput input) throws IOException {
	int firstByte = input.readByte();

	//Bail out early if this is one byte, necessary or it fails later
	if (firstByte >= 0)
	return firstByte;

	int size = numberOfExtraBytesToRead(firstByte);
	long retval = firstByte & firstByteValueMask(size);
	for (int ii = 0; ii < size; ii++)
	{
	byte b = input.readByte();
	retval <<= 8;
	retval \|= b & 0xff;
	}

	return retval;
	}

	/**
	* Note this method is the same as {@link #readUnsignedVInt(DataInput)},
	* except that we do not block if there are not enough bytes in the buffer
	* to reconstruct the value.
	*
	* WARNING: this method is only safe for vints we know to be representable by a positive long value.
	*
	* @return -1 if there are not enough bytes in the input to read the value; else, the vint unsigned value.
	*/
	public static long getUnsignedVInt(ByteBuffer input, int readerIndex)
	{
	return getUnsignedVInt(input, readerIndex, input.limit());
	}

	public static long getUnsignedVInt(ByteBuffer input, int readerIndex, int readerLimit)
	{
	if (readerIndex >= readerLimit)
	return -1;

	int firstByte = input.get(readerIndex++);

	//Bail out early if this is one byte, necessary or it fails later
	if (firstByte >= 0)
	return firstByte;

	int size = numberOfExtraBytesToRead(firstByte);
	if (readerIndex + size > readerLimit)
	return -1;

	long retval = firstByte & firstByteValueMask(size);
	for (int ii = 0; ii < size; ii++)
	{
	byte b = input.get(readerIndex++);
	retval <<= 8;
	retval \|= b & 0xff;
	}

	return retval;
	}

	public static long readVInt(DataInput input) throws IOException {
	return decodeZigZag64(readUnsignedVInt(input));
	}

	// & this with the first byte to give the value part for a given extraBytesToRead encoded in the byte
	public static int firstByteValueMask(int extraBytesToRead)
	{
	// by including the known 0bit in the mask, we can use this for encodeExtraBytesToRead
	return 0xff >> extraBytesToRead;
	}

	public static int encodeExtraBytesToRead(int extraBytesToRead)
	{
	// because we have an extra bit in the value mask, we just need to invert it
	return ~firstByteValueMask(extraBytesToRead);
	}

	public static int numberOfExtraBytesToRead(int firstByte)
	{
	// we count number of set upper bits; so if we simply invert all of the bits, we're golden
	// this is aided by the fact that we only work with negative numbers, so when upcast to an int all
	// of the new upper bits are also set, so by inverting we set all of them to zero
	return Integer.numberOfLeadingZeros(~firstByte) - 24;
	}

	protected static final ThreadLocal<byte[]> encodingBuffer = new ThreadLocal<byte[]>()
	{
	@Override
	public byte[] initialValue()
	{
	return new byte[9];
	}
	};

	public static void writeUnsignedVInt(long value, DataOutput output) throws IOException {
	int size = VIntCoding.computeUnsignedVIntSize(value);
	if (size == 1)
	{
	output.write((int)value);
	return;
	}

	output.write(VIntCoding.encodeVInt(value, size), 0, size);
	}

	@Inline
	public static byte[] encodeVInt(long value, int size) {
	byte encodingSpace[] = encodingBuffer.get();
	int extraBytes = size - 1;

	for (int i = extraBytes ; i >= 0; --i)
	{
	encodingSpace[i] = (byte) value;
	value >>= 8;
	}
	encodingSpace[0] \|= VIntCoding.encodeExtraBytesToRead(extraBytes);
	return encodingSpace;
	}

	public static void writeVInt(long value, DataOutput output) throws IOException {
	writeUnsignedVInt(encodeZigZag64(value), output);
	}

	/**
	* Decode 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.)
	*
	* @param n An unsigned 64-bit integer, stored in a signed int because
	* Java has no explicit unsigned support.
	* @return A signed 64-bit integer.
	*/
	public static long decodeZigZag64(final long n) {
	return (n >>> 1) ^ -(n & 1);
	}

	/**
	* 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.)
	*
	* @param n A signed 64-bit integer.
	* @return An unsigned 64-bit integer, stored in a signed int because
	* Java has no explicit unsigned support.
	*/
	public static long encodeZigZag64(final long n) {
	// Note: the right-shift must be arithmetic
	return (n << 1) ^ (n >> 63);
	}

	/** Compute the number of bytes that would be needed to encode a varint. */
	public static int computeVIntSize(final long param) {
	return computeUnsignedVIntSize(encodeZigZag64(param));
	}

	/** Compute the number of bytes that would be needed to encode an unsigned varint. */
	public static int computeUnsignedVIntSize(final long value) {
	int magnitude = Long.numberOfLeadingZeros(value \| 1); // \| with 1 to ensure magntiude <= 63, so (63 - 1) / 7 <= 8
	return 9 - ((magnitude - 1) / 7);
	}
	}