Storing decimals in minimal bytes

[wvpm]

Background:
Decimals are great for representing human-made data. Humans enter data in decimal format and like to read data in decimal format (ignoring historical alternatives for now). The decimal class in C# is perfect for this but it takes up 16 bytes. 12 bytes are used to store the mantissa and 4 contain a sign flag and the scale (0-28).

In a real life use case, I am storing logs with decimal data. These logs get big. Compression algorithms such as Brotli are great for reducing the size. Still I wondered if the decimals could be stored more efficiently. So I came up with a system that stores decimals in 1-14 bytes.

It works by treating decimals as an 96bit unsigned integer (just like decimal itself) that is multiplied by a power of 10.
The power of 10 is between -28 and 28. The uint96 is split in 3x uint32. These are stored in their smallest representation. Zeroes are left out. The amount of bytes used to store the uint96 is stored in a header byte. The header byte also has bit flags for the sign and whether or not there is a power of 10/scale byte.

The result is:

• 1 header byte (isNegativeFlag + hasScaleFlag + significantBytesCount)
• 0-12 significant bytes representing the uint96
• 0 or 1 scale sbyte reprenting the power of 10

What do you think of this?

Code:

using System;
using System.Buffers.Binary;
using System.IO;

namespace ClassLibrary1;

public static class DecimalCompressor {
	private const byte _isNegativeFlag = 0b1000000, _hasScaleFlag = 0b0100000, _bodySizeMask = 0b0001111;

	private static byte GetSignificantBytes(uint value) {
		return value switch {
			0 => 0,
			<= byte.MaxValue => sizeof(byte),
			<= ushort.MaxValue => sizeof(ushort),
			_ => sizeof(uint),
		};
	}
	private static void WriteSignificantBytes(Span<byte> buffer, uint value) {
		if (value == 0) {
			return;
		}

		if (value <= byte.MaxValue) {
			buffer[0] = (byte)value;
		}
		else if (value <= ushort.MaxValue) {
			BinaryPrimitives.WriteUInt16LittleEndian(buffer, (ushort)value);
		}
		else {
			BinaryPrimitives.WriteUInt32LittleEndian(buffer, value);
		}
	}

	public static byte[] Compress(decimal value) {
		const decimal divisorToNormalise = 1.000000000000000000000000000000000m;

		if (value == 0) {
			return [0];
		}

		sbyte powerOf10;
		decimal mantissa = value;
		if (mantissa % 1 != 0) {
			mantissa /= divisorToNormalise;
			powerOf10 = (sbyte)-value.Scale;
		}
		else if (mantissa != 0) {
			powerOf10 = 0;
			while (mantissa % 10 == 0) {
				mantissa /= 10;
				powerOf10++;
			}
			mantissa /= divisorToNormalise;
		}
		else { powerOf10 = 0; }


		int[] bits = decimal.GetBits(mantissa);
		int low = bits[0], mid = bits[1], high = bits[2];
		bool hasScale;
		byte header = 0;
		if (mantissa < 0) {
			header |= _isNegativeFlag;
		}
		if (hasScale = powerOf10 != 0) {
			header |= _hasScaleFlag;
		}

		const int headerLength = 1;
		int offset = headerLength;
		int scaleLength = hasScale ? 1 : 0;
		int variableSize, bodySize;
		byte[] bytes;
		if (high != 0) {
			uint uhigh = (uint)high;
			variableSize = GetSignificantBytes(uhigh);
			bodySize = variableSize + 2 * sizeof(int);
			bytes = new byte[headerLength + bodySize + scaleLength];
			BinaryPrimitives.WriteInt32LittleEndian(bytes.AsSpan(offset, sizeof(int)), low);
			offset += sizeof(int);
			BinaryPrimitives.WriteInt32LittleEndian(bytes.AsSpan(offset, sizeof(int)), mid);
			offset += sizeof(int);
			WriteSignificantBytes(bytes.AsSpan(offset, variableSize), uhigh);
		}
		else if (mid != 0) {
			uint umid = (uint)mid;
			variableSize = GetSignificantBytes(umid);
			bodySize = variableSize + sizeof(int);
			bytes = new byte[headerLength + bodySize + scaleLength];
			BinaryPrimitives.WriteInt32LittleEndian(bytes.AsSpan(offset, sizeof(int)), low);
			offset += sizeof(int);
			WriteSignificantBytes(bytes.AsSpan(offset, variableSize), umid);
		}
		else {
			uint ulow = (uint)low;
			variableSize = GetSignificantBytes(ulow);
			bodySize = variableSize;
			bytes = new byte[headerLength + bodySize + scaleLength];
			WriteSignificantBytes(bytes.AsSpan(offset, variableSize), ulow);
		}

		bytes[0] = (byte)(header + bodySize);

		if (hasScale) {
			bytes[^1] = (byte)powerOf10;
		}

		return bytes;
	}

	public static decimal Decompress(Stream stream) {
		int readResult = stream.ReadByte();
		if (readResult < 0) {
			throw new EndOfStreamException();
		}
		byte header = (byte)readResult;
		if (header == 0) { return 0; }
		bool isNegative = (header & _isNegativeFlag) == _isNegativeFlag;
		bool hasScale = (header & _hasScaleFlag) == _hasScaleFlag;
		int significantBytesCount = header & _bodySizeMask;
		int bytesToRead = hasScale ? significantBytesCount + 1 : significantBytesCount;

		byte[] buffer = new byte[bytesToRead];
		stream.ReadExactly(buffer);

		int low, mid, high, offset = 0;
		switch (significantBytesCount) {
			case 1:
				low = buffer[offset];
				mid = 0;
				high = 0;
				break;
			case 2:
				low = BinaryPrimitives.ReadUInt16LittleEndian(buffer.AsSpan(offset, sizeof(ushort)));
				mid = 0;
				high = 0;
				break;
			case 4:
				low = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				mid = 0;
				high = 0;
				break;
			case 5:
				low = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				mid = buffer[offset];
				high = 0;
				break;
			case 6:
				low = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				mid = BinaryPrimitives.ReadUInt16LittleEndian(buffer.AsSpan(offset, sizeof(ushort)));
				high = 0;
				break;
			case 8:
				low = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				mid = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				high = 0;
				break;
			case 9:
				low = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				mid = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				high = buffer[offset];
				break;
			case 10:
				low = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				mid = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				high = BinaryPrimitives.ReadUInt16LittleEndian(buffer.AsSpan(offset, sizeof(ushort)));
				break;
			default:
				low = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				mid = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				offset += sizeof(int);
				high = BinaryPrimitives.ReadInt32LittleEndian(buffer.AsSpan(offset, sizeof(int)));
				break;
		}

		if (!hasScale) {
			return new(low, mid, high, isNegative, 0);
		}

		sbyte powerOf10 = (sbyte)buffer[^1];
		byte scale = powerOf10 >= 0 ? byte.MinValue : (byte)-powerOf10;

		decimal value = new(low, mid, high, isNegative, scale);

		if (powerOf10 > 0) {
			value *= powerOf10 switch {
				1 => 10m,
				2 => 100m,
				3 => 1000m,
				4 => 10000m,
				5 => 100000m,
				6 => 1000000m,
				7 => 10000000m,
				8 => 100000000m,
				9 => 1000000000m,
				10 => 10000000000m,
				11 => 100000000000m,
				12 => 1000000000000m,
				13 => 10000000000000m,
				14 => 100000000000000m,
				15 => 1000000000000000m,
				16 => 10000000000000000m,
				17 => 100000000000000000m,
				18 => 1000000000000000000m,
				19 => 10000000000000000000m,
				20 => 100000000000000000000m,
				21 => 1000000000000000000000m,
				22 => 10000000000000000000000m,
				23 => 100000000000000000000000m,
				24 => 1000000000000000000000000m,
				25 => 10000000000000000000000000m,
				26 => 100000000000000000000000000m,
				27 => 1000000000000000000000000000m,
				28 => 10000000000000000000000000000m,
				_ => throw new ArgumentOutOfRangeException(nameof(powerOf10))
			};
		}

		return value;
	}
}

Tests:

using System.IO;
using ClassLibrary1;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TestProject1;

[TestClass]
public class UnitTest1 {
	[TestDecimalValues]
	public void TestMethod1(decimal value) {
		using MemoryStream memoryStream = new(DecimalCompressor.Compress(value));
		Assert.AreEqual(value, DecimalCompressor.Decompress(memoryStream));
	}
}

internal class TestDecimalValuesAttribute : DataTestMethodAttribute {
	private static readonly decimal[] _values = [
	decimal.MinValue, decimal.MaxValue, decimal.Zero, decimal.One,
	0.1m,-0.1m,1.1m,-1.1m,10m,100m,1000m,10000m,
	2.55m,2.56m,6553.5m,6553.6m, 16777.215M,16777.215M,429496.7295M,429496.7296M,
	-2.55m,-2.56m,-6553.5m,-6553.6m, -16777.215M,-16777.215M,-429496.7295M,-429496.7296M
	];

	public override TestResult[] Execute(ITestMethod testMethod) {
		TestResult[] testResults = new TestResult[_values.Length];
		for (int i = 0; i < _values.Length; i++) {
			testResults[i] = testMethod.Invoke([_values[i]]);
			testResults[i].DisplayName = _values[i].ToString();
		}
		return testResults;
	}
}

Edit: I ran some tests where the decimals were compressed using the code below and then brotli compressed vs just brotli compressed.
The files (real world data) contain other data types as well. I ran 3 tests:

• brotli encode the entire file (current solution & baseline): 420858 bytes
• brotli encode the entire file with decimal values removed (for reference): 352697 bytes
• brotli encode the entire file with decimals compressed: 399007 bytes

Based on this I conclude that the decimal values take up 420858 - 352697 = 68161 bytes in the baseline and 399007 - 352697 = 46310 bytes in the test. This means the decimal compression reduced the required bytes for decimals by ~32%, a result that I am happy with.

[huoyaoyuan]

For historical reason, decimal duplicates the layout of OLE DECIMAL type, which is stored in a union of 128 bits. 16 bits of the union is used for type assignment and must be left unused by DECIMAL.

When processing in memory, aligning at whole powers of 2 can make some benefit. For storage, compressing makes sense.

The compression method in this post seems leveraging the fact that only a small amount of significant bits within the uint96 is likely to be used.

If you have clear requirements of precision in your system, you can also look at the IEEE754 Decimal32/64 types (planned for .NET 10). They do not carry excessive unused precision, and is more widely accepted by other systems.

[wvpm]

I wasn't aware of the history or the plans for .NET 10 (#81376 ). Thanks for informing me.

The compression method in this post seems leveraging the fact that only a small amount of significant bits within the uint96 is likely to be used.

Correct. That is one of the optimisations that saves a lot of bytes. Even when dealing with monetary values, there tend to be less than 10 significant digits, which means a single uint32 is enough to store that data.