Skip to content

Instantly share code, notes, and snippets.

@gafferongames
Last active July 31, 2024 22:29
Show Gist options
  • Save gafferongames/bb7e593ba1b05da35ab6 to your computer and use it in GitHub Desktop.
Save gafferongames/bb7e593ba1b05da35ab6 to your computer and use it in GitHub Desktop.
Delta Compression
/*
Delta Compression by Glenn Fiedler.
This source code is placed in the public domain.
http://gafferongames.com/2015/03/14/the-networked-physics-data-compression-challenge/
*/
#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <math.h>
static const int MaxContexts = 8;
static const int NumCubes = 901;
static const int MaxPacketSize = 4 * 1024;
static const int UnitsPerMeter = 512;
static const int OrientationBits = 9;
static const int PositionBoundXY = 32;
static const int PositionBoundZ = 16;
static const int QuantizedPositionBoundXY = UnitsPerMeter * PositionBoundXY - 1;
static const int QuantizedPositionBoundZ = UnitsPerMeter * PositionBoundZ - 1;
template <uint32_t x> struct PopCount
{
enum { a = x - ( ( x >> 1 ) & 0x55555555 ),
b = ( ( ( a >> 2 ) & 0x33333333 ) + ( a & 0x33333333 ) ),
c = ( ( ( b >> 4 ) + b ) & 0x0f0f0f0f ),
d = c + ( c >> 8 ),
e = d + ( d >> 16 ),
result = e & 0x0000003f
};
};
template <uint32_t x> struct Log2
{
enum { a = x | ( x >> 1 ),
b = a | ( a >> 2 ),
c = b | ( b >> 4 ),
d = c | ( c >> 8 ),
e = d | ( d >> 16 ),
f = e >> 1,
result = PopCount<f>::result
};
};
template <int64_t min, int64_t max> struct BitsRequired
{
static const uint32_t result = ( min == max ) ? 0 : Log2<uint32_t(max-min)>::result + 1;
};
inline uint32_t popcount( uint32_t x )
{
const uint32_t a = x - ( ( x >> 1 ) & 0x55555555 );
const uint32_t b = ( ( ( a >> 2 ) & 0x33333333 ) + ( a & 0x33333333 ) );
const uint32_t c = ( ( ( b >> 4 ) + b ) & 0x0f0f0f0f );
const uint32_t d = c + ( c >> 8 );
const uint32_t e = d + ( d >> 16 );
const uint32_t result = e & 0x0000003f;
return result;
}
#ifdef __GNUC__
inline int bits_required( uint32_t min, uint32_t max )
{
return 32 - __builtin_clz( max - min );
}
#else
inline uint32_t log2( uint32_t x )
{
const uint32_t a = x | ( x >> 1 );
const uint32_t b = a | ( a >> 2 );
const uint32_t c = b | ( b >> 4 );
const uint32_t d = c | ( c >> 8 );
const uint32_t e = d | ( d >> 16 );
const uint32_t f = e >> 1;
return popcount( f );
}
inline int bits_required( uint32_t min, uint32_t max )
{
return ( min == max ) ? 0 : log2( max-min ) + 1;
}
#endif
template <typename T> const T & min( const T & a, const T & b )
{
return ( a < b ) ? a : b;
}
template <typename T> const T & max( const T & a, const T & b )
{
return ( a > b ) ? a : b;
}
template <typename T> T clamp( const T & value, const T & min, const T & max )
{
if ( value < min )
return min;
else if ( value > max )
return max;
else
return value;
}
template <typename T> void swap( T & a, T & b )
{
T tmp = a;
a = b;
b = tmp;
};
template <typename T> T abs( const T & value )
{
return ( value < 0 ) ? -value : value;
}
#define CPU_LITTLE_ENDIAN 1
#define CPU_BIG_ENDIAN 2
#if defined(__386__) || defined(i386) || defined(__i386__) \
|| defined(__X86) || defined(_M_IX86) \
|| defined(_M_X64) || defined(__x86_64__) \
|| defined(alpha) || defined(__alpha) || defined(__alpha__) \
|| defined(_M_ALPHA) \
|| defined(ARM) || defined(_ARM) || defined(__arm__) \
|| defined(WIN32) || defined(_WIN32) || defined(__WIN32__) \
|| defined(_WIN32_WCE) || defined(__NT__) \
|| defined(__MIPSEL__)
#define CPU_ENDIAN CPU_LITTLE_ENDIAN
#else
#define CPU_ENDIAN CPU_BIG_ENDIAN
#endif
inline uint32_t host_to_network( uint32_t value )
{
#if CPU_ENDIAN == CPU_BIG_ENDIAN
return __builtin_bswap32( value );
#else
return value;
#endif
}
inline uint32_t network_to_host( uint32_t value )
{
#if CPU_ENDIAN == CPU_BIG_ENDIAN
return __builtin_bswap32( value );
#else
return value;
#endif
}
class BitWriter
{
public:
BitWriter( void * data, int bytes ) : m_data( (uint32_t*)data ), m_numWords( bytes / 4 )
{
assert( data );
assert( ( bytes % 4 ) == 0 ); // IMPORTANT: buffer size must be a multiple of four!
m_numBits = m_numWords * 32;
m_bitsWritten = 0;
m_scratch = 0;
m_bitIndex = 0;
m_wordIndex = 0;
m_overflow = false;
memset( m_data, 0, bytes );
}
void WriteBits( uint32_t value, int bits )
{
assert( bits > 0 );
assert( bits <= 32 );
assert( m_bitsWritten + bits <= m_numBits );
if ( m_bitsWritten + bits > m_numBits )
{
m_overflow = true;
return;
}
value &= ( uint64_t( 1 ) << bits ) - 1;
m_scratch |= uint64_t( value ) << ( 64 - m_bitIndex - bits );
m_bitIndex += bits;
if ( m_bitIndex >= 32 )
{
assert( m_wordIndex < m_numWords );
m_data[m_wordIndex] = host_to_network( uint32_t( m_scratch >> 32 ) );
m_scratch <<= 32;
m_bitIndex -= 32;
m_wordIndex++;
}
m_bitsWritten += bits;
}
void WriteAlign()
{
const int remainderBits = m_bitsWritten % 8;
if ( remainderBits != 0 )
{
uint32_t zero = 0;
WriteBits( zero, 8 - remainderBits );
assert( m_bitsWritten % 8 == 0 );
}
}
void WriteBytes( const uint8_t * data, int bytes )
{
assert( GetAlignBits() == 0 );
if ( m_bitsWritten + bytes * 8 >= m_numBits )
{
m_overflow = true;
return;
}
assert( m_bitIndex == 0 || m_bitIndex == 8 || m_bitIndex == 16 || m_bitIndex == 24 );
int headBytes = ( 4 - m_bitIndex / 8 ) % 4;
if ( headBytes > bytes )
headBytes = bytes;
for ( int i = 0; i < headBytes; ++i )
WriteBits( data[i], 8 );
if ( headBytes == bytes )
return;
assert( GetAlignBits() == 0 );
int numWords = ( bytes - headBytes ) / 4;
if ( numWords > 0 )
{
assert( m_bitIndex == 0 );
memcpy( &m_data[m_wordIndex], data + headBytes, numWords * 4 );
m_bitsWritten += numWords * 32;
m_wordIndex += numWords;
m_scratch = 0;
}
assert( GetAlignBits() == 0 );
int tailStart = headBytes + numWords * 4;
int tailBytes = bytes - tailStart;
assert( tailBytes >= 0 && tailBytes < 4 );
for ( int i = 0; i < tailBytes; ++i )
WriteBits( data[tailStart+i], 8 );
assert( GetAlignBits() == 0 );
assert( headBytes + numWords * 4 + tailBytes == bytes );
}
void FlushBits()
{
if ( m_bitIndex != 0 )
{
assert( m_wordIndex < m_numWords );
if ( m_wordIndex >= m_numWords )
{
m_overflow = true;
return;
}
m_data[m_wordIndex++] = host_to_network( uint32_t( m_scratch >> 32 ) );
}
}
int GetAlignBits() const
{
return ( 8 - m_bitsWritten % 8 ) % 8;
}
int GetBitsWritten() const
{
return m_bitsWritten;
}
int GetBitsAvailable() const
{
return m_numBits - m_bitsWritten;
}
const uint8_t * GetData() const
{
return (uint8_t*) m_data;
}
int GetBytesWritten() const
{
return m_wordIndex * 4;
}
int GetTotalBytes() const
{
return m_numWords * 4;
}
bool IsOverflow() const
{
return m_overflow;
}
private:
uint32_t * m_data;
uint64_t m_scratch;
int m_numBits;
int m_numWords;
int m_bitsWritten;
int m_bitIndex;
int m_wordIndex;
bool m_overflow;
};
class BitReader
{
public:
BitReader( const void * data, int bytes ) : m_data( (const uint32_t*)data ), m_numWords( bytes / 4 )
{
assert( data );
assert( ( bytes % 4 ) == 0 ); // IMPORTANT: buffer size must be a multiple of four!
m_numBits = m_numWords * 32;
m_bitsRead = 0;
m_bitIndex = 0;
m_wordIndex = 0;
m_scratch = network_to_host( m_data[0] );
m_overflow = false;
}
uint32_t ReadBits( int bits )
{
assert( bits > 0 );
assert( bits <= 32 );
assert( m_bitsRead + bits <= m_numBits );
if ( m_bitsRead + bits > m_numBits )
{
m_overflow = true;
return 0;
}
m_bitsRead += bits;
assert( m_bitIndex < 32 );
if ( m_bitIndex + bits < 32 )
{
m_scratch <<= bits;
m_bitIndex += bits;
}
else
{
m_wordIndex++;
assert( m_wordIndex < m_numWords );
const uint32_t a = 32 - m_bitIndex;
const uint32_t b = bits - a;
m_scratch <<= a;
m_scratch |= network_to_host( m_data[m_wordIndex] );
m_scratch <<= b;
m_bitIndex = b;
}
const uint32_t output = uint32_t( m_scratch >> 32 );
m_scratch &= 0xFFFFFFFF;
return output;
}
void ReadAlign()
{
const int remainderBits = m_bitsRead % 8;
if ( remainderBits != 0 )
{
#ifdef NDEBUG
ReadBits( 8 - remainderBits );
#else
uint32_t value = ReadBits( 8 - remainderBits );
assert( value == 0 );
assert( m_bitsRead % 8 == 0 );
#endif
}
}
void ReadBytes( uint8_t * data, int bytes )
{
assert( GetAlignBits() == 0 );
if ( m_bitsRead + bytes * 8 >= m_numBits )
{
memset( data, 0, bytes );
m_overflow = true;
return;
}
assert( m_bitIndex == 0 || m_bitIndex == 8 || m_bitIndex == 16 || m_bitIndex == 24 );
int headBytes = ( 4 - m_bitIndex / 8 ) % 4;
if ( headBytes > bytes )
headBytes = bytes;
for ( int i = 0; i < headBytes; ++i )
data[i] = ReadBits( 8 );
if ( headBytes == bytes )
return;
assert( GetAlignBits() == 0 );
int numWords = ( bytes - headBytes ) / 4;
if ( numWords > 0 )
{
assert( m_bitIndex == 0 );
memcpy( data + headBytes, &m_data[m_wordIndex], numWords * 4 );
m_bitsRead += numWords * 32;
m_wordIndex += numWords;
m_scratch = network_to_host( m_data[m_wordIndex] );
}
assert( GetAlignBits() == 0 );
int tailStart = headBytes + numWords * 4;
int tailBytes = bytes - tailStart;
assert( tailBytes >= 0 && tailBytes < 4 );
for ( int i = 0; i < tailBytes; ++i )
data[tailStart+i] = ReadBits( 8 );
assert( GetAlignBits() == 0 );
assert( headBytes + numWords * 4 + tailBytes == bytes );
}
int GetAlignBits() const
{
return ( 8 - m_bitsRead % 8 ) % 8;
}
int GetBitsRead() const
{
return m_bitsRead;
}
int GetBytesRead() const
{
return ( m_wordIndex + 1 ) * 4;
}
int GetBitsRemaining() const
{
return m_numBits - m_bitsRead;
}
int GetTotalBits() const
{
return m_numBits;
}
int GetTotalBytes() const
{
return m_numBits * 8;
}
bool IsOverflow() const
{
return m_overflow;
}
private:
const uint32_t * m_data;
uint64_t m_scratch;
int m_numBits;
int m_numWords;
int m_bitsRead;
int m_bitIndex;
int m_wordIndex;
bool m_overflow;
};
class WriteStream
{
public:
enum { IsWriting = 1 };
enum { IsReading = 0 };
WriteStream( uint8_t * buffer, int bytes ) : m_writer( buffer, bytes ), m_context( nullptr ), m_aborted( false ) {}
void SerializeInteger( int32_t value, int32_t min, int32_t max )
{
assert( min < max );
assert( value >= min );
assert( value <= max );
const int bits = bits_required( min, max );
uint32_t unsigned_value = value - min;
m_writer.WriteBits( unsigned_value, bits );
}
void SerializeBits( uint32_t value, int bits )
{
assert( bits > 0 );
assert( bits <= 32 );
m_writer.WriteBits( value, bits );
}
void SerializeBytes( const uint8_t * data, int bytes )
{
Align();
m_writer.WriteBytes( data, bytes );
}
void Align()
{
m_writer.WriteAlign();
}
int GetAlignBits() const
{
return m_writer.GetAlignBits();
}
bool Check( uint32_t magic )
{
Align();
SerializeBits( magic, 32 );
return true;
}
void Flush()
{
m_writer.FlushBits();
}
const uint8_t * GetData() const
{
return m_writer.GetData();
}
int GetBytesProcessed() const
{
return m_writer.GetBytesWritten();
}
int GetBitsProcessed() const
{
return m_writer.GetBitsWritten();
}
int GetBitsRemaining() const
{
return GetTotalBits() - GetBitsProcessed();
}
int GetTotalBits() const
{
return m_writer.GetTotalBytes() * 8;
}
int GetTotalBytes() const
{
return m_writer.GetTotalBytes();
}
bool IsOverflow() const
{
return m_writer.IsOverflow();
}
void SetContext( const void ** context )
{
m_context = context;
}
const void * GetContext( int index ) const
{
assert( index >= 0 );
assert( index < MaxContexts );
return m_context ? m_context[index] : nullptr;
}
void Abort()
{
m_aborted = true;
}
bool Aborted() const
{
return m_aborted;
}
private:
BitWriter m_writer;
const void ** m_context;
bool m_aborted;
};
class ReadStream
{
public:
enum { IsWriting = 0 };
enum { IsReading = 1 };
ReadStream( uint8_t * buffer, int bytes ) : m_bitsRead(0), m_reader( buffer, bytes ), m_context( nullptr ), m_aborted( false ) {}
void SerializeInteger( int32_t & value, int32_t min, int32_t max )
{
assert( min < max );
const int bits = bits_required( min, max );
uint32_t unsigned_value = m_reader.ReadBits( bits );
value = (int32_t) unsigned_value + min;
m_bitsRead += bits;
}
void SerializeBits( uint32_t & value, int bits )
{
assert( bits > 0 );
assert( bits <= 32 );
uint32_t read_value = m_reader.ReadBits( bits );
value = read_value;
m_bitsRead += bits;
}
void SerializeBytes( uint8_t * data, int bytes )
{
Align();
m_reader.ReadBytes( data, bytes );
m_bitsRead += bytes * 8;
}
void Align()
{
m_reader.ReadAlign();
}
int GetAlignBits() const
{
return m_reader.GetAlignBits();
}
bool Check( uint32_t magic )
{
Align();
uint32_t value = 0;
SerializeBits( value, 32 );
assert( value == magic );
return value == magic;
}
int GetBitsProcessed() const
{
return m_bitsRead;
}
int GetBytesProcessed() const
{
return m_bitsRead / 8 + ( m_bitsRead % 8 ? 1 : 0 );
}
bool IsOverflow() const
{
return m_reader.IsOverflow();
}
void SetContext( const void ** context )
{
m_context = context;
}
const void * GetContext( int index ) const
{
assert( index >= 0 );
assert( index < MaxContexts );
return m_context ? m_context[index] : nullptr;
}
void Abort()
{
m_aborted = true;
}
bool Aborted() const
{
return m_aborted;
}
int GetBytesRead() const
{
return m_reader.GetBytesRead();
}
private:
int m_bitsRead;
BitReader m_reader;
const void ** m_context;
bool m_aborted;
};
class MeasureStream
{
public:
enum { IsWriting = 1 };
enum { IsReading = 0 };
MeasureStream( int bytes ) : m_totalBytes( bytes ), m_bitsWritten(0), m_context( nullptr ), m_aborted( false ) {}
void SerializeInteger( int32_t value, int32_t min, int32_t max )
{
assert( min < max );
assert( value >= min );
assert( value <= max );
const int bits = bits_required( min, max );
m_bitsWritten += bits;
}
void SerializeBits( uint32_t value, int bits )
{
assert( bits > 0 );
assert( bits <= 32 );
m_bitsWritten += bits;
}
void SerializeBytes( const uint8_t * data, int bytes )
{
Align();
m_bitsWritten += bytes * 8;
}
void Align()
{
const int alignBits = GetAlignBits();
m_bitsWritten += alignBits;
}
int GetAlignBits() const
{
return 7; // worst case
}
bool Check( uint32_t magic )
{
Align();
m_bitsWritten += 32;
return true;
}
int GetBitsProcessed() const
{
return m_bitsWritten;
}
int GetBytesProcessed() const
{
return m_bitsWritten / 8 + ( m_bitsWritten % 8 ? 1 : 0 );
}
int GetTotalBytes() const
{
return m_totalBytes;
}
int GetTotalBits() const
{
return m_totalBytes * 8;
}
bool IsOverflow() const
{
return m_bitsWritten > m_totalBytes * 8;
}
void SetContext( const void ** context )
{
m_context = context;
}
const void * GetContext( int index ) const
{
assert( index >= 0 );
assert( index < MaxContexts );
return m_context ? m_context[index] : nullptr;
}
void Abort()
{
m_aborted = true;
}
bool Aborted() const
{
return m_aborted;
}
private:
int m_totalBytes;
int m_bitsWritten;
const void ** m_context;
bool m_aborted;
};
template <typename T> void serialize_object( ReadStream & stream, T & object )
{
object.SerializeRead( stream );
}
template <typename T> void serialize_object( WriteStream & stream, T & object )
{
object.SerializeWrite( stream );
}
template <typename T> void serialize_object( MeasureStream & stream, T & object )
{
object.SerializeMeasure( stream );
}
#define serialize_int( stream, value, min, max ) \
do \
{ \
assert( min < max ); \
int32_t int32_value; \
if ( Stream::IsWriting ) \
{ \
assert( value >= min ); \
assert( value <= max ); \
int32_value = (int32_t) value; \
} \
stream.SerializeInteger( int32_value, min, max ); \
if ( Stream::IsReading ) \
{ \
value = (decltype(value)) int32_value; \
assert( value >= min ); \
assert( value <= max ); \
} \
} while (0)
#define serialize_bits( stream, value, bits ) \
do \
{ \
assert( bits > 0 ); \
assert( bits <= 32 ); \
uint32_t uint32_value; \
if ( Stream::IsWriting ) \
uint32_value = (uint32_t) value; \
stream.SerializeBits( uint32_value, bits ); \
if ( Stream::IsReading ) \
value = (decltype(value)) uint32_value; \
} while (0)
#define serialize_bool( stream, value ) serialize_bits( stream, value, 1 )
template <typename Stream> void serialize_uint16( Stream & stream, uint16_t & value )
{
serialize_bits( stream, value, 16 );
}
template <typename Stream> void serialize_uint32( Stream & stream, uint32_t & value )
{
serialize_bits( stream, value, 32 );
}
template <typename Stream> void serialize_uint64( Stream & stream, uint64_t & value )
{
uint32_t hi,lo;
if ( Stream::IsWriting )
{
lo = value & 0xFFFFFFFF;
hi = value >> 32;
}
serialize_bits( stream, lo, 32 );
serialize_bits( stream, hi, 32 );
if ( Stream::IsReading )
value = ( uint64_t(hi) << 32 ) | lo;
}
template <typename Stream> void serialize_int16( Stream & stream, int16_t & value )
{
serialize_bits( stream, value, 16 );
}
template <typename Stream> void serialize_int32( Stream & stream, int32_t & value )
{
serialize_bits( stream, value, 32 );
}
template <typename Stream> void serialize_int64( Stream & stream, int64_t & value )
{
uint32_t hi,lo;
if ( Stream::IsWriting )
{
lo = uint64_t(value) & 0xFFFFFFFF;
hi = uint64_t(value) >> 32;
}
serialize_bits( stream, lo, 32 );
serialize_bits( stream, hi, 32 );
if ( Stream::IsReading )
value = ( int64_t(hi) << 32 ) | lo;
}
template <typename Stream> void serialize_float( Stream & stream, float & value )
{
union FloatInt
{
float float_value;
uint32_t int_value;
};
FloatInt tmp;
if ( Stream::IsWriting )
tmp.float_value = value;
serialize_uint32( stream, tmp.int_value );
if ( Stream::IsReading )
value = tmp.float_value;
}
template <typename Stream> inline void internal_serialize_float( Stream & stream, float & value, float min, float max, float res )
{
const float delta = max - min;
const float values = delta / res;
const uint32_t maxIntegerValue = (uint32_t) ceil( values );
const int bits = bits_required( 0, maxIntegerValue );
uint32_t integerValue = 0;
if ( Stream::IsWriting )
{
float normalizedValue = clamp( ( value - min ) / delta, 0.0f, 1.0f );
integerValue = (uint32_t) floor( normalizedValue * maxIntegerValue + 0.5f );
}
stream.SerializeBits( integerValue, bits );
if ( Stream::IsReading )
{
const float normalizedValue = integerValue / float( maxIntegerValue );
value = normalizedValue * delta + min;
}
}
#define serialize_compressed_float( stream, value, min, max, res ) \
do \
{ \
internal_serialize_float( stream, value, min, max, res ); \
} \
while(0)
template <typename Stream> void serialize_double( Stream & stream, double & value )
{
union DoubleInt
{
double double_value;
uint64_t int_value;
};
DoubleInt tmp;
if ( Stream::IsWriting )
tmp.double_value = value;
serialize_uint64( stream, tmp.int_value );
if ( Stream::IsReading )
value = tmp.double_value;
}
template <typename Stream> void serialize_bytes( Stream & stream, uint8_t * data, int bytes )
{
stream.SerializeBytes( data, bytes );
}
template <typename Stream> void serialize_string( Stream & stream, char * string, int buffer_size )
{
uint32_t length;
if ( Stream::IsWriting )
length = strlen( string );
stream.Align();
stream.SerializeBits( length, 32 );
assert( length < buffer_size - 1 );
stream.SerializeBytes( (uint8_t*)string, length );
if ( Stream::IsReading )
string[length] = '\0';
}
template <typename Stream> bool serialize_check( Stream & stream, uint32_t magic )
{
return stream.Check( magic );
}
#define SERIALIZE_OBJECT( stream ) \
void SerializeRead( class ReadStream & stream ) { Serialize( stream ); }; \
void SerializeWrite( class WriteStream & stream ) { Serialize( stream ); }; \
void SerializeMeasure( class MeasureStream & stream ) { Serialize( stream ); }; \
template <typename Stream> void Serialize( Stream & stream )
template <int bits> struct compressed_quaternion
{
enum { max_value = (1<<bits)-1 };
uint32_t largest : 2;
uint32_t integer_a : bits;
uint32_t integer_b : bits;
uint32_t integer_c : bits;
void Load( float x, float y, float z, float w )
{
assert( bits > 1 );
assert( bits <= 10 );
const float minimum = - 1.0f / 1.414214f; // 1.0f / sqrt(2)
const float maximum = + 1.0f / 1.414214f;
const float scale = float( ( 1 << bits ) - 1 );
const float abs_x = fabs( x );
const float abs_y = fabs( y );
const float abs_z = fabs( z );
const float abs_w = fabs( w );
largest = 0;
float largest_value = abs_x;
if ( abs_y > largest_value )
{
largest = 1;
largest_value = abs_y;
}
if ( abs_z > largest_value )
{
largest = 2;
largest_value = abs_z;
}
if ( abs_w > largest_value )
{
largest = 3;
largest_value = abs_w;
}
float a = 0;
float b = 0;
float c = 0;
switch ( largest )
{
case 0:
if ( x >= 0 )
{
a = y;
b = z;
c = w;
}
else
{
a = -y;
b = -z;
c = -w;
}
break;
case 1:
if ( y >= 0 )
{
a = x;
b = z;
c = w;
}
else
{
a = -x;
b = -z;
c = -w;
}
break;
case 2:
if ( z >= 0 )
{
a = x;
b = y;
c = w;
}
else
{
a = -x;
b = -y;
c = -w;
}
break;
case 3:
if ( w >= 0 )
{
a = x;
b = y;
c = z;
}
else
{
a = -x;
b = -y;
c = -z;
}
break;
default:
assert( false );
}
const float normal_a = ( a - minimum ) / ( maximum - minimum );
const float normal_b = ( b - minimum ) / ( maximum - minimum );
const float normal_c = ( c - minimum ) / ( maximum - minimum );
integer_a = floor( normal_a * scale + 0.5f );
integer_b = floor( normal_b * scale + 0.5f );
integer_c = floor( normal_c * scale + 0.5f );
}
void Save( float & x, float & y, float & z, float & w ) const
{
// note: you're going to want to normalize the quaternion returned from this function
assert( bits > 1 );
assert( bits <= 10 );
const float minimum = - 1.0f / 1.414214f; // 1.0f / sqrt(2)
const float maximum = + 1.0f / 1.414214f;
const float scale = float( ( 1 << bits ) - 1 );
const float inverse_scale = 1.0f / scale;
const float a = integer_a * inverse_scale * ( maximum - minimum ) + minimum;
const float b = integer_b * inverse_scale * ( maximum - minimum ) + minimum;
const float c = integer_c * inverse_scale * ( maximum - minimum ) + minimum;
switch ( largest )
{
case 0:
{
x = sqrtf( 1 - a*a - b*b - c*c );
y = a;
z = b;
w = c;
}
break;
case 1:
{
x = a;
y = sqrtf( 1 - a*a - b*b - c*c );
z = b;
w = c;
}
break;
case 2:
{
x = a;
y = b;
z = sqrtf( 1 - a*a - b*b - c*c );
w = c;
}
break;
case 3:
{
x = a;
y = b;
z = c;
w = sqrtf( 1 - a*a - b*b - c*c );
}
break;
default:
{
assert( false );
x = 0;
y = 0;
z = 0;
w = 1;
}
}
}
SERIALIZE_OBJECT( stream )
{
serialize_bits( stream, largest, 2 );
serialize_bits( stream, integer_a, bits );
serialize_bits( stream, integer_b, bits );
serialize_bits( stream, integer_c, bits );
}
bool operator == ( const compressed_quaternion & other ) const
{
if ( largest != other.largest )
return false;
if ( integer_a != other.integer_a )
return false;
if ( integer_b != other.integer_b )
return false;
if ( integer_c != other.integer_c )
return false;
return true;
}
bool operator != ( const compressed_quaternion & other ) const
{
return ! ( *this == other );
}
};
inline int count_relative_index_bits( bool * changed )
{
int bits = 8; // 0..255 num changed
bool first = true;
int previous_index = 0;
for ( int i = 0; i < NumCubes; ++i )
{
if ( !changed[i] )
continue;
if ( first )
{
bits += 10;
first = false;
previous_index = i;
}
else
{
const int difference = i - previous_index;
if ( difference == 1 )
{
bits += 1;
}
else if ( difference <= 6 )
{
bits += 1 + 1 + 2;
}
else if ( difference <= 14 )
{
bits += 1 + 1 + 1 + 3;
}
else if ( difference <= 30 )
{
bits += 1 + 1 + 1 + 1 + 4;
}
else if ( difference <= 62 )
{
bits += 1 + 1 + 1 + 1 + 1 + 5;
}
else if ( difference <= 126 )
{
bits += 1 + 1 + 1 + 1 + 1 + 1 + 6;
}
else
{
bits += 1 + 1 + 1 + 1 + 1 + 1 + 1 + 10;
}
previous_index = i;
}
}
return bits;
}
template <typename Stream> void serialize_relative_index( Stream & stream, int previous, int & current )
{
uint32_t difference;
if ( Stream::IsWriting )
{
assert( previous < current );
difference = current - previous;
assert( difference > 0 );
}
// +1 (1 bit)
bool plusOne;
if ( Stream::IsWriting )
plusOne = difference == 1;
serialize_bool( stream, plusOne );
if ( plusOne )
{
current = previous + 1;
return;
}
// [+2,6] (2 bits)
bool twoBits;
if ( Stream::IsWriting )
twoBits = difference <= 6;
serialize_bool( stream, twoBits );
if ( twoBits )
{
serialize_int( stream, difference, 2, 6 );
if ( Stream::IsReading )
current = previous + difference;
return;
}
// [7,14] -> [0,7] (3 bits)
bool threeBits;
if ( Stream::IsWriting )
threeBits = difference <= 14;
serialize_bool( stream, threeBits );
if ( threeBits )
{
serialize_int( stream, difference, 7, 14 );
if ( Stream::IsReading )
current = previous + difference;
return;
}
// [15,30] -> [0,15] (4 bits)
bool fourBits;
if ( Stream::IsWriting )
fourBits = difference <= 30;
serialize_bool( stream, fourBits );
if ( fourBits )
{
serialize_int( stream, difference, 15, 30 );
if ( Stream::IsReading )
current = previous + difference;
return;
}
// [31,62] -> [0,31] (5 bits)
bool fiveBits;
if ( Stream::IsWriting )
fiveBits = difference <= 62;
serialize_bool( stream, fiveBits );
if ( fiveBits )
{
serialize_int( stream, difference, 31, 62 );
if ( Stream::IsReading )
current = previous + difference;
return;
}
// [63,126] -> [0,63] (6 bits)
bool sixBits;
if ( Stream::IsWriting )
sixBits = difference <= 126;
serialize_bool( stream, sixBits );
if ( sixBits )
{
serialize_int( stream, difference, 63, 126 );
if ( Stream::IsReading )
current = previous + difference;
return;
}
// [127,NumCubes]
serialize_int( stream, difference, 127, NumCubes - 1 );
if ( Stream::IsReading )
current = previous + difference;
}
struct QuantizedCubeState
{
bool interacting;
int position_x;
int position_y;
int position_z;
compressed_quaternion<OrientationBits> orientation;
bool operator == ( const QuantizedCubeState & other ) const
{
if ( interacting != other.interacting )
return false;
if ( position_x != other.position_x )
return false;
if ( position_y != other.position_y )
return false;
if ( position_z != other.position_z )
return false;
if ( orientation != other.orientation )
return false;
return true;
}
bool operator != ( const QuantizedCubeState & other ) const
{
return ! ( *this == other );
}
};
struct QuantizedSnapshot
{
QuantizedCubeState cubes[NumCubes];
bool operator == ( const QuantizedSnapshot & other ) const
{
for ( int i = 0; i < NumCubes; ++i )
{
if ( cubes[i] != other.cubes[i] )
return false;
}
return true;
}
bool operator != ( const QuantizedSnapshot & other ) const
{
return ! ( *this == other );
}
};
inline int signed_to_unsigned( int n )
{
return ( n << 1 ) ^ ( n >> 31 );
}
inline int unsigned_to_signed( uint32_t n )
{
return ( n >> 1 ) ^ ( -( n & 1 ) );
}
template <typename Stream> void serialize_unsigned_range( Stream & stream, uint32_t & value, int num_ranges, const int * range_bits )
{
assert( num_ranges > 0 );
int range_min = 0;
for ( int i = 0; i < num_ranges - 1; ++i )
{
const int range_max = range_min + ( ( 1 << range_bits[i] ) - 1 );
bool in_range = Stream::IsWriting && value <= range_max;
serialize_bool( stream, in_range );
if ( in_range )
{
serialize_int( stream, value, range_min, range_max );
return;
}
range_min += ( 1 << range_bits[i] );
}
serialize_int( stream, value, range_min, range_min + ( ( 1 << range_bits[num_ranges-1] ) - 1 ) );
}
inline int unsigned_range_limit( int num_ranges, const int * range_bits )
{
int range_limit = 0;
for ( int i = 0; i < num_ranges; ++i )
range_limit += ( 1 << range_bits[i] );
return range_limit;
}
template <typename Stream> void serialize_relative_position( Stream & stream,
int & position_x,
int & position_y,
int & position_z,
int base_position_x,
int base_position_y,
int base_position_z )
{
bool all_small;
bool too_large;
uint32_t dx,dy,dz;
const int range_bits[] = { 5, 6, 7 };
const int num_ranges = sizeof( range_bits ) / sizeof( int );
const int small_limit = 15;
const int large_limit = unsigned_range_limit( num_ranges, range_bits );
const int max_delta = 2047;
if ( Stream::IsWriting )
{
dx = signed_to_unsigned( position_x - base_position_x );
dy = signed_to_unsigned( position_y - base_position_y );
dz = signed_to_unsigned( position_z - base_position_z );
all_small = dx <= small_limit && dy <= small_limit && dz <= small_limit;
too_large = dx >= large_limit || dy >= large_limit || dz >= large_limit;
}
serialize_bool( stream, all_small );
if ( all_small )
{
serialize_int( stream, dx, 0, small_limit );
serialize_int( stream, dy, 0, small_limit );
serialize_int( stream, dz, 0, small_limit );
}
else
{
serialize_bool( stream, too_large );
if ( !too_large )
{
serialize_unsigned_range( stream, dx, num_ranges, range_bits );
serialize_unsigned_range( stream, dy, num_ranges, range_bits );
serialize_unsigned_range( stream, dz, num_ranges, range_bits );
}
else
{
serialize_int( stream, dx, 0, max_delta );
serialize_int( stream, dy, 0, max_delta );
serialize_int( stream, dz, 0, max_delta );
}
}
if ( Stream::IsReading )
{
int signed_dx = unsigned_to_signed( dx );
int signed_dy = unsigned_to_signed( dy );
int signed_dz = unsigned_to_signed( dz );
position_x = base_position_x + signed_dx;
position_y = base_position_y + signed_dy;
position_z = base_position_z + signed_dz;
}
}
template <typename Stream> void serialize_relative_orientation( Stream & stream,
compressed_quaternion<OrientationBits> & orientation,
const compressed_quaternion<OrientationBits> & base_orientation )
{
const int range_bits[] = { 4, 5, 7 };
const int num_ranges = sizeof( range_bits ) / sizeof( int );
const int small_limit = 3;
const int large_limit = unsigned_range_limit( num_ranges, range_bits );
uint32_t da,db,dc;
bool all_small = false;
bool relative_orientation = false;
if ( Stream::IsWriting && orientation.largest == base_orientation.largest )
{
da = signed_to_unsigned( orientation.integer_a - base_orientation.integer_a );
db = signed_to_unsigned( orientation.integer_b - base_orientation.integer_b );
dc = signed_to_unsigned( orientation.integer_c - base_orientation.integer_c );
all_small = da <= small_limit && db <= small_limit && dc <= small_limit;
relative_orientation = da < large_limit && db < large_limit && dc < large_limit;
}
serialize_bool( stream, relative_orientation );
if ( relative_orientation )
{
serialize_bool( stream, all_small );
if ( all_small )
{
serialize_int( stream, da, 0, small_limit );
serialize_int( stream, db, 0, small_limit );
serialize_int( stream, dc, 0, small_limit );
}
else
{
serialize_unsigned_range( stream, da, num_ranges, range_bits );
serialize_unsigned_range( stream, db, num_ranges, range_bits );
serialize_unsigned_range( stream, dc, num_ranges, range_bits );
}
if ( Stream::IsReading )
{
int signed_da = unsigned_to_signed( da );
int signed_db = unsigned_to_signed( db );
int signed_dc = unsigned_to_signed( dc );
orientation.largest = base_orientation.largest;
orientation.integer_a = base_orientation.integer_a + signed_da;
orientation.integer_b = base_orientation.integer_b + signed_db;
orientation.integer_c = base_orientation.integer_c + signed_dc;
}
}
else
{
serialize_object( stream, orientation );
}
}
template <typename Stream> void serialize_cube_relative_to_base( Stream & stream, QuantizedCubeState & cube, const QuantizedCubeState & base, int base_dx, int base_dy, int base_dz )
{
serialize_bool( stream, cube.interacting );
bool position_changed;
if ( Stream::IsWriting )
position_changed = cube.position_x != base.position_x || cube.position_y != base.position_y || cube.position_z != base.position_z;
serialize_bool( stream, position_changed );
if ( position_changed )
{
const int gravity = 3;
const int ground_limit = 105;
const int drag_x = - ceil( base_dx * 0.062f );
const int drag_y = - ceil( base_dy * 0.062f );
const int drag_z = - ceil( base_dz * 0.062f );
const int position_estimate_x = base.position_x + base_dx + drag_x;
const int position_estimate_y = base.position_y + base_dy + drag_y;
const int position_estimate_z = max( base.position_z + base_dz - gravity + drag_z, ground_limit );
serialize_relative_position( stream, cube.position_x, cube.position_y, cube.position_z, position_estimate_x, position_estimate_y, position_estimate_z );
}
else if ( Stream::IsReading )
{
cube.position_x = base.position_x;
cube.position_y = base.position_y;
cube.position_z = base.position_z;
}
serialize_relative_orientation( stream, cube.orientation, base.orientation );
}
struct CompressionState
{
float delta_x[NumCubes];
float delta_y[NumCubes];
float delta_z[NumCubes];
};
void calculate_compression_state( CompressionState & compression_state, QuantizedSnapshot & current_snapshot, QuantizedSnapshot & baseline_snapshot )
{
for ( int i = 0; i < NumCubes; ++i )
{
compression_state.delta_x[i] = current_snapshot.cubes[i].position_x - baseline_snapshot.cubes[i].position_x;
compression_state.delta_y[i] = current_snapshot.cubes[i].position_y - baseline_snapshot.cubes[i].position_y;
compression_state.delta_z[i] = current_snapshot.cubes[i].position_z - baseline_snapshot.cubes[i].position_z;
}
}
template <typename Stream> void serialize_snapshot_relative_to_baseline( Stream & stream, CompressionState & compression_state, QuantizedSnapshot & current_snapshot, QuantizedSnapshot & baseline_snapshot )
{
QuantizedCubeState * quantized_cubes = &current_snapshot.cubes[0];
QuantizedCubeState * quantized_base_cubes = &baseline_snapshot.cubes[0];
const int MaxChanged = 256;
int num_changed = 0;
bool use_indices = false;
bool changed[NumCubes];
if ( Stream::IsWriting )
{
for ( int i = 0; i < NumCubes; ++i )
{
changed[i] = quantized_cubes[i] != quantized_base_cubes[i];
if ( changed[i] )
num_changed++;
}
if ( num_changed > 0 )
{
int relative_index_bits = count_relative_index_bits( changed );
if ( num_changed <= MaxChanged && relative_index_bits <= NumCubes )
use_indices = true;
}
}
serialize_bool( stream, use_indices );
if ( use_indices )
{
serialize_int( stream, num_changed, 1, MaxChanged );
if ( Stream::IsWriting )
{
int num_written = 0;
bool first = true;
int previous_index = 0;
for ( int i = 0; i < NumCubes; ++i )
{
if ( changed[i] )
{
if ( first )
{
serialize_int( stream, i, 0, NumCubes - 1 );
first = false;
}
else
{
serialize_relative_index( stream, previous_index, i );
}
serialize_cube_relative_to_base( stream, quantized_cubes[i], quantized_base_cubes[i], compression_state.delta_x[i], compression_state.delta_y[i], compression_state.delta_z[i] );
num_written++;
previous_index = i;
}
}
assert( num_written == num_changed );
}
else
{
memset( changed, 0, sizeof( changed ) );
int previous_index = 0;
for ( int j = 0; j < num_changed; ++j )
{
int i;
if ( j == 0 )
serialize_int( stream, i, 0, NumCubes - 1 );
else
serialize_relative_index( stream, previous_index, i );
serialize_cube_relative_to_base( stream, quantized_cubes[i], quantized_base_cubes[i], compression_state.delta_x[i], compression_state.delta_y[i], compression_state.delta_z[i] );
changed[i] = true;
previous_index = i;
}
for ( int i = 0; i < NumCubes; ++i )
{
if ( !changed[i] )
memcpy( &quantized_cubes[i], &quantized_base_cubes[i], sizeof( QuantizedCubeState ) );
}
}
}
else
{
for ( int i = 0; i < NumCubes; ++i )
{
serialize_bool( stream, changed[i] );
if ( changed[i] )
{
serialize_cube_relative_to_base( stream, quantized_cubes[i], quantized_base_cubes[i], compression_state.delta_x[i], compression_state.delta_y[i], compression_state.delta_z[i] );
}
else if ( Stream::IsReading )
{
memcpy( &quantized_cubes[i], &quantized_base_cubes[i], sizeof( QuantizedCubeState ) );
}
}
}
}
struct FrameCubeData
{
int orientation_largest;
int orientation_a;
int orientation_b;
int orientation_c;
int position_x;
int position_y;
int position_z;
int interacting;
};
struct Frame
{
FrameCubeData cubes[NumCubes];
};
struct Packet
{
int size;
uint8_t data[MaxPacketSize];
};
void convert_frame_to_snapshot( const Frame & frame, QuantizedSnapshot & snapshot )
{
for ( int j = 0; j < NumCubes; ++j )
{
assert( frame.cubes[j].orientation_largest >= 0 );
assert( frame.cubes[j].orientation_largest <= 3 );
snapshot.cubes[j].orientation.largest = frame.cubes[j].orientation_largest;
assert( frame.cubes[j].orientation_a >= 0 );
assert( frame.cubes[j].orientation_b >= 0 );
assert( frame.cubes[j].orientation_c >= 0 );
assert( frame.cubes[j].orientation_a <= ( 1 << OrientationBits ) - 1 );
assert( frame.cubes[j].orientation_b <= ( 1 << OrientationBits ) - 1 );
assert( frame.cubes[j].orientation_c <= ( 1 << OrientationBits ) - 1 );
snapshot.cubes[j].orientation.integer_a = frame.cubes[j].orientation_a;
snapshot.cubes[j].orientation.integer_b = frame.cubes[j].orientation_b;
snapshot.cubes[j].orientation.integer_c = frame.cubes[j].orientation_c;
assert( frame.cubes[j].position_x >= -QuantizedPositionBoundXY );
assert( frame.cubes[j].position_y >= -QuantizedPositionBoundXY );
assert( frame.cubes[j].position_z >= 0 );
assert( frame.cubes[j].position_x <= QuantizedPositionBoundXY );
assert( frame.cubes[j].position_y <= QuantizedPositionBoundXY );
assert( frame.cubes[j].position_z <= QuantizedPositionBoundZ );
snapshot.cubes[j].position_x = frame.cubes[j].position_x;
snapshot.cubes[j].position_y = frame.cubes[j].position_y;
snapshot.cubes[j].position_z = frame.cubes[j].position_z;
assert( frame.cubes[j].interacting == 0 || frame.cubes[j].interacting == 1 );
snapshot.cubes[j].interacting = frame.cubes[j].interacting;
}
}
int main( int argc, char ** argv )
{
FILE * file = fopen( "delta_data.bin", "rb" );
if ( !file )
{
printf( "error: can't open file\n" );
return 1;
}
// count number of frames in file
fseek( file, 0L, SEEK_END );
uint64_t file_size = ftell( file );
fseek( file, 0L, SEEK_SET );
const int num_frames = (int) floor( double(file_size) / sizeof( Frame ) );
printf( "%d input frames\n", num_frames );
assert( num_frames > 6 );
// read in frames
Frame * frames = new Frame[num_frames];
uint64_t frames_read = fread( frames, sizeof( Frame ), num_frames, file );
assert( frames_read == num_frames );
fclose( file );
// convert frames to snapshots
QuantizedSnapshot * snapshots = new QuantizedSnapshot[num_frames];
for ( int i = 0; i < num_frames; ++i )
convert_frame_to_snapshot( frames[i], snapshots[i] );
// write packets
const int num_packets = num_frames - 6;
printf( "writing %d packets\n", num_packets );
assert( num_packets > 0 );
CompressionState * compression_state = new CompressionState[num_frames];
int packet_index = 0;
Packet * packets = new Packet[num_packets];
uint64_t total_bytes = 0;
for ( int i = 6; i < num_frames; ++i )
{
Packet & packet = packets[packet_index];
WriteStream stream( packet.data, MaxPacketSize );
QuantizedSnapshot & current_snapshot = snapshots[i];
QuantizedSnapshot & baseline_snapshot = snapshots[i-6];
calculate_compression_state( compression_state[i], current_snapshot, baseline_snapshot );
serialize_snapshot_relative_to_baseline( stream, compression_state[i-6], current_snapshot, baseline_snapshot );
stream.Flush();
int bits_written = stream.GetBitsProcessed();
int bytes_written = ( bits_written / 8 ) + ( ( bits_written % 8 ) ? 1 : 0 );
while ( packet.data[bytes_written] == 0 && bytes_written > 0 )
--bytes_written;
assert( bytes_written >= 0 );
packet.size = bytes_written;
total_bytes += bytes_written;
++packet_index;
}
// read packets and verify reconstruction of snapshot
printf( "reading %d packets\n", num_packets );
for ( int i = 0; i < num_packets; ++i )
{
Packet & packet = packets[i];
ReadStream stream( packet.data, MaxPacketSize );
QuantizedSnapshot current_snapshot;
QuantizedSnapshot & baseline_snapshot = snapshots[i];
serialize_snapshot_relative_to_baseline( stream, compression_state[i], current_snapshot, baseline_snapshot );
assert( current_snapshot == snapshots[i+6] );
}
printf( "all packets verify ok!\n" );
// print results
printf( "total packet bytes: %llu\n", total_bytes );
printf( "average bytes per-packet: %f\n", total_bytes / double(num_packets) );
printf( "average bytes per-second: %f\n", total_bytes / double(num_packets) * 60 * 8 );
printf( "average kilobits per-second: %f\n", total_bytes / double(num_packets) * 60 * 8 / 1000.0 );
printf( "compression ratio: %.2f%% of original size\n", total_bytes / ( num_packets * ( 4 + 3 + 3 ) * 32 * NumCubes / 8.0 ) * 100.0 );
// clean up everything
delete [] snapshots;
delete [] packets;
delete [] frames;
return 0;
}
/*
2837 input frames
writing 2831 packets
reading 2831 packets
all packets verify ok!
total packet bytes: 1505956
average bytes per-packet: 531.951960
average bytes per-second: 255336.941010
average kilobits per-second: 255.336941
compression ratio: 1.48% of original size
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment