Skip to content

Instantly share code, notes, and snippets.

@Chaosed0
Created Oct 23, 2020
Embed
What would you like to do?
Bit-level replay utilties from Breakpoint. Read the article here: https://straypixels.net/breakpoint-replay-breakdown/
using System.IO;
namespace Breakpoint.Replay
{
// A utility to abstract reading and writing bits to a C# Stream.
public class BitStream
{
private Stream stream;
private BufferedStreamWriter streamWriter;
private bool initialized = false;
private byte buffer = 0;
private int offset = 0;
public BitStream(Stream stream)
{
this.stream = stream;
}
public BitStream(BufferedStreamWriter streamWriter)
{
this.streamWriter = streamWriter;
}
public void WriteBit(bool bit)
{
if (this.streamWriter == null)
{
UnityEngine.Debug.LogWarning("BitStream is not configured for writing");
return;
}
if (bit)
{
buffer = (byte)(buffer | (1 << offset));
}
++offset;
if (offset == 8)
{
streamWriter.Write(buffer);
buffer = 0;
offset = 0;
}
}
public void WriteByte(byte b)
{
for (int i = 0; i < 8; ++i)
{
WriteBit((b & (1 << i)) > 0);
}
}
public void FinishWriting()
{
if (offset > 0)
{
streamWriter.Write(buffer);
}
streamWriter.Flush();
}
public bool ReadBit()
{
if (this.stream == null)
{
UnityEngine.Debug.LogWarning("BitStream is not configured for reading");
return false;
}
if (!initialized || offset == 8)
{
offset = 0;
buffer = (byte)stream.ReadByte();
initialized = true;
}
bool bit = (buffer & (1 << offset)) > 0;
++offset;
return bit;
}
public void ResetReading()
{
buffer = 0;
offset = 0;
}
}
}
using UnityEngine;
using System.IO;
// A utility to buffer writes to a C# Stream.
public class BufferedStreamWriter
{
private int offset = 0;
private byte[] writeBuffer;
private Stream stream;
public BufferedStreamWriter(Stream stream, int bufferSize = 128)
{
this.stream = stream;
this.writeBuffer = new byte[bufferSize];
}
public void Write(byte b)
{
UnityEngine.Profiling.Profiler.BeginSample("BufferedStreamWriter.Write");
writeBuffer[offset] = b;
++offset;
if (offset >= writeBuffer.Length)
{
stream.Write(writeBuffer, 0, writeBuffer.Length);
offset = 0;
}
UnityEngine.Profiling.Profiler.EndSample();
}
public void Flush()
{
if (offset > 0)
{
stream.Write(writeBuffer, 0, offset);
offset = 0;
}
}
}
using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;
namespace Breakpoint.Replay
{
// Based on: https://gafferongames.com/post/snapshot_compression/
public static class ReplayEncoder
{
// Convenience struct so we don't have bare numbers everywhere.
public struct QuantizeParams
{
public float min;
public float max;
public int bits;
public QuantizeParams(float min, float max, int bits)
{
this.min = min;
this.max = max;
this.bits = bits;
}
}
// Converts a bool value (bit) to a byte value.
static byte BoolToByte(bool value, int place = 1)
{
return (byte)BoolToUnsigned(value, place);
}
// Converts a bool value (bit) to an unsigned value.
static uint BoolToUnsigned(bool value, int place = 1)
{
return value ? (uint)(1 << place - 1) : (byte)0;
}
// Converts a float value into an unsigned integer value.
// You can think of this as linearly interpolating min and max against 0 and 2^bitLength.
public static uint Quantize(float value, float min, float max, int bitLength)
{
return (uint)(((value - min) / (max - min)) * Math.Pow(2, bitLength));
}
// Converts a quantized uint value back into a float.
public static float Unquantize(uint value, float min, float max, int bitLength)
{
return (float)((value / Math.Pow(2, bitLength)) * (max - min) + min);
}
// Encodes a given number of bits in a byte into a BitArray.
public static void EncodeByte(BitStream bitStream, byte b, int length)
{
EncodeUnsigned(bitStream, b, length);
}
// Decodes a number of a given bit-length into a byte.
public static byte DecodeByte(BitStream bitStream, int length)
{
return (byte)DecodeUnsigned(bitStream, length);
}
// The following methods (EncodeUnsigned and EncodeEnum) have a subtle difference:
// EncodeUnsigned uses an additional bit to specify whether the value that follows used the short or long bit length.
// EncodeEnum uses the max value that can be encoded with shortBitLength to specify whether the value is continued
// using the longBitLength, and _adds_ the additional value of the following bits to the previous bits.
// There's two implications there:
// 1. EncodeUnsigned is less efficient when most values fall below shortBitLength, because it stores an extra bit.
// 2. However, EncodeEnum cannot take full advantage of the range afforded by longBitLength because it adds two values
// together rather than using the full binary space. That is, the max value of EncodeUnsigned is 2^longBitLength,
// but the max value of EncodeEnum is 2^shortBitLength - 1 + 2^(longBitLength - shortBitLength).
// Encodes an unsigned value using shortBitLength bits if possible.
// Otherwise, uses longBitLength bits (regardless of whether or not it's enough to hold the value).
public static void EncodeVariableLengthUnsigned(BitStream bitStream, uint value, int shortBitLength, int longBitLength)
{
if (value < (1 << shortBitLength))
{
bitStream.WriteBit(false);
EncodeUnsigned(bitStream, value, shortBitLength);
}
else
{
bitStream.WriteBit(true);
EncodeUnsigned(bitStream, value, longBitLength);
}
}
// Decodes an unsigned value that was encoded using EncodeVariableLengthUnsigned.
// The same shortBitLength and longBitLength that were passed to the encode function must be passed to this function.
public static uint DecodeVariableLengthUnsigned(BitStream bitStream, int shortBitLength, int longBitLength)
{
if (bitStream.ReadBit() == false)
{
return DecodeUnsigned(bitStream, shortBitLength);
}
else
{
return DecodeUnsigned(bitStream, longBitLength);
}
}
// Encodes an unsigned value using shortBitLength bits if possible.
// Otherwise, the value is encoded using longBitLength bits.
// See discussion above for the difference between this and EncodeVariableLengthUnsigned.
public static void EncodeVariableLengthEnum(BitStream bitStream, uint value, int shortBitLength, int longBitLength)
{
uint maxShortValue = (uint)(1 << shortBitLength) - 1;
if (value < maxShortValue)
{
EncodeUnsigned(bitStream, value, shortBitLength);
}
else
{
EncodeUnsigned(bitStream, maxShortValue, shortBitLength);
EncodeUnsigned(bitStream, value - maxShortValue, longBitLength - shortBitLength);
}
}
// Decodes an unsigned value that was encoded using EncodeVariableLengthEnum.
// The same shortBitLength and longBitLength that were passed to the encode function must be passed to this function.
public static uint DecodeVariableLengthEnum(BitStream bitStream, int shortBitLength, int longBitLength)
{
uint maxShortValue = (uint)(1 << shortBitLength) - 1;
uint shortValue = DecodeUnsigned(bitStream, shortBitLength);
if (shortValue < maxShortValue)
{
return shortValue;
}
else
{
uint additionalValue = DecodeUnsigned(bitStream, longBitLength - shortBitLength);
return maxShortValue + additionalValue;
}
}
// Encodes a given number of bits in an unsigned int into a bit array.
public static void EncodeUnsigned(BitStream bitStream, uint n, int length)
{
int bits = 1;
for (int i = 0; i < length; i++)
{
bitStream.WriteBit((n & bits) > 0);
bits = bits << 1;
}
}
// Decodes a number of a given bit-length into an unsigned int.
public static uint DecodeUnsigned(BitStream bitStream, int length)
{
uint n = 0;
for (int i = 0; i < length; i++)
{
n |= BoolToUnsigned(bitStream.ReadBit(), i + 1);
}
return n;
}
// Encodes a float, automatically quantizing it to save space.
public static void EncodeFloat(BitStream bitStream, float value, QuantizeParams quantizeParams)
{
EncodeUnsigned(bitStream, Quantize(value, quantizeParams.min, quantizeParams.max, quantizeParams.bits), quantizeParams.bits);
}
// Encodes a float, automatically quantizing it to save space.
public static float DecodeFloat(BitStream bitStream, QuantizeParams quantizeParams)
{
return Unquantize(DecodeUnsigned(bitStream, quantizeParams.bits), quantizeParams.min, quantizeParams.max, quantizeParams.bits);
}
// Encodes a Vector2, automatically quantizing it to save space.
public static void EncodeVector2(BitStream bitStream, Vector2 vec, QuantizeParams quantizeParams)
{
EncodeVector2(bitStream, vec, quantizeParams.min, quantizeParams.max, quantizeParams.bits);
}
// Encodes a Vector2, automatically quantizing it to save space.
public static void EncodeVector2(BitStream bitStream, Vector2 vec, float min, float max, int bitsPerFloat)
{
uint x = Quantize(vec.x, min, max, bitsPerFloat);
uint y = Quantize(vec.y, min, max, bitsPerFloat);
EncodeUnsigned(bitStream, x, bitsPerFloat);
EncodeUnsigned(bitStream, y, bitsPerFloat);
}
// Decodes a Vector2, automatically un-quantizing it.
public static Vector2 DecodeVector2(BitStream bitStream, QuantizeParams quantizeParams)
{
return DecodeVector2(bitStream, quantizeParams.min, quantizeParams.max, quantizeParams.bits);
}
// Decodes a Vector2, automatically un-quantizing it.
public static Vector2 DecodeVector2(BitStream bitStream, float min, float max, int bitsPerFloat)
{
uint x_q = DecodeUnsigned(bitStream, bitsPerFloat);
uint y_q = DecodeUnsigned(bitStream, bitsPerFloat);
float x = Unquantize(x_q, min, max, bitsPerFloat);
float y = Unquantize(y_q, min, max, bitsPerFloat);
return new Vector2(x, y);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment