Last active
July 31, 2024 22:29
-
-
Save gafferongames/bb7e593ba1b05da35ab6 to your computer and use it in GitHub Desktop.
Delta Compression
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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 = ¤t_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