postgis/liblwgeom/varint.c

/**********************************************************************
 *
 * PostGIS - Spatial Types for PostgreSQL
 * http://postgis.net
 *
 * PostGIS is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * PostGIS is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with PostGIS.  If not, see <http://www.gnu.org/licenses/>.
 *
 **********************************************************************
 *
 * Copyright (C) 2014 Sandro Santilli <strk@kbt.io>
 * Copyright (C) 2013 Nicklas Avén
 *
 **********************************************************************/


#include "varint.h"
#include "lwgeom_log.h"
#include "liblwgeom.h"

/* -------------------------------------------------------------------------------- */

static size_t
_varint_u64_encode_buf(uint64_t val, uint8_t *buf)
{
	uint8_t grp;
	uint64_t q = val;
	uint8_t *ptr = buf;
	while (1)
	{
		/* We put the 7 least significant bits in grp */
		grp = 0x7f & q;
		/* We rightshift our input value 7 bits */
		/* which means that the 7 next least significant bits */
		/* becomes the 7 least significant */
		q = q >> 7;
		/* Check if, after our rightshifting, we still have */
		/* anything to read in our input value. */
		if ( q > 0 )
		{
			/* In the next line quite a lot is happening. */
			/* Since there is more to read in our input value */
			/* we signal that by setting the most significant bit */
			/* in our byte to 1. */
			/* Then we put that byte in our buffer and move the pointer */
			/* forward one step */
			*ptr = 0x80 | grp;
			ptr++;
		}
		else
		{
			/* The same as above, but since there is nothing more */
			/* to read in our input value we leave the most significant bit unset */
			*ptr = grp;
			ptr++;
			return ptr - buf;
		}
	}
	/* This cannot happen */
	lwerror("%s: Got out of infinite loop. Consciousness achieved.", __func__);
	return (size_t)0;
}


size_t
varint_u64_encode_buf(uint64_t val, uint8_t *buf)
{
	return _varint_u64_encode_buf(val, buf);
}


size_t
varint_u32_encode_buf(uint32_t val, uint8_t *buf)
{
	return _varint_u64_encode_buf((uint64_t)val, buf);
}

size_t
varint_s64_encode_buf(int64_t val, uint8_t *buf)
{
	return _varint_u64_encode_buf(zigzag64(val), buf);
}

size_t
varint_s32_encode_buf(int32_t val, uint8_t *buf)
{
	return _varint_u64_encode_buf((uint64_t)zigzag32(val), buf);
}

/* Read from signed 64bit varint */
int64_t
varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
{
	return unzigzag64(varint_u64_decode(the_start, the_end, size));
}

/* Read from unsigned 64bit varint */
uint64_t
varint_u64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
{
	uint64_t nVal = 0;
	int nShift = 0;
	uint8_t nByte;
	const uint8_t *ptr = the_start;

	/* Check so we don't read beyond the twkb */
	while( ptr < the_end )
	{
		nByte = *ptr;
		/* Hibit is set, so this isn't the last byte */
		if (nByte & 0x80)
		{
			/* We get here when there is more to read in the input varInt */
			/* Here we take the least significant 7 bits of the read */
			/* byte and put it in the most significant place in the result variable. */
			nVal |= ((uint64_t)(nByte & 0x7f)) << nShift;
			/* move the "cursor" of the input buffer step (8 bits) */
			ptr++;
			/* move the cursor in the resulting variable (7 bits) */
			nShift += 7;
		}
		else
		{
			/* move the "cursor" one step */
			ptr++;
			/* Move the last read byte to the most significant */
			/* place in the result and return the whole result */
			*size = ptr - the_start;
			return nVal | ((uint64_t)nByte << nShift);
		}
	}
	lwerror("%s: varint extends past end of buffer", __func__);
	*size = 0;
	return 0;
}

size_t
varint_size(const uint8_t *the_start, const uint8_t *the_end)
{
	const uint8_t *ptr = the_start;

	/* Check so we don't read beyond the twkb */
	while( ptr < the_end )
	{
		/* Hibit is set, this isn't the last byte */
		if (*ptr & 0x80)
		{
			ptr++;
		}
		else
		{
			ptr++;
			return ptr - the_start;
		}
	}
	return 0;
}

uint64_t zigzag64(int64_t val)
{
	return val >= 0 ?
		((uint64_t)val) << 1 :
		((((uint64_t)(-1 - val)) << 1) | 0x01);
}

uint32_t zigzag32(int32_t val)
{
	return val >= 0 ?
		((uint32_t)val) << 1 :
		((((uint32_t)(-1 - val)) << 1) | 0x01);
}

uint8_t zigzag8(int8_t val)
{
	return val >= 0 ?
		((uint8_t)val) << 1 :
		((((uint8_t)(-1 - val)) << 1) | 0x01);
}

int64_t unzigzag64(uint64_t val)
{
	return !(val & 0x01) ?
		((int64_t)(val >> 1)) :
		(-1 * (int64_t)((val+1) >> 1));
}

int32_t unzigzag32(uint32_t val)
{
	return !(val & 0x01) ?
		((int32_t)(val >> 1)) :
		(-1 * (int32_t)((val+1) >> 1));
}

int8_t unzigzag8(uint8_t val)
{
	return !(val & 0x01) ?
		((int8_t)(val >> 1)) :
		(-1 * (int8_t)((val+1) >> 1));
}