A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using System;
2using System.Diagnostics;
3using Unity.Burst;
4using Unity.Mathematics;
5
6namespace Unity.Collections
7{
8 /// <summary>
9 /// A type that uses Huffman encoding to encode values in a lossless manner.
10 /// </summary>
11 /// <remarks>
12 /// This type puts values into a manageable number of power-of-two-sized buckets.
13 /// It codes the bucket index with Huffman, and uses several raw bits that correspond
14 /// to the size of the bucket to code the position in the bucket.
15 ///
16 /// For example, if you want to send a 32-bit integer over the network, it's
17 /// impractical to create a Huffman tree that encompasses every value the integer
18 /// can take because it requires a tree with 2^32 leaves. This type manages that situation.
19 ///
20 /// The buckets are small, around 0, and become progressively larger as the data moves away from zero.
21 /// Because most data is deltas against predictions, most values are small and most of the redundancy
22 /// is in the error's size and not in the values of that size we end up hitting.
23 ///
24 /// The context is as a sub-model that has its own statistics and uses its own Huffman tree.
25 /// When using the context to read and write a specific value, the context must always be the same.
26 /// The benefit of using multiple contexts is that it allows you to separate the statistics of things that have
27 /// different expected distributions, which leads to more precise statistics, which again yields better compression.
28 /// More contexts does, however, result in a marginal cost of a slightly larger model.
29 /// </remarks>
30 [GenerateTestsForBurstCompatibility]
31 public unsafe struct StreamCompressionModel
32 {
33 internal static readonly byte[] k_BucketSizes =
34 {
35 0, 0, 1, 2, 3, 4, 6, 8, 10, 12, 15, 18, 21, 24, 27, 32
36 };
37
38 internal static readonly uint[] k_BucketOffsets =
39 {
40 0, 1, 2, 4, 8, 16, 32, 96, 352, 1376, 5472, 38240, 300384, 2397536, 19174752, 153392480
41 };
42 internal static readonly int[] k_FirstBucketCandidate =
43 {
44 // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
45 15, 15, 15, 15, 14, 14, 14, 13, 13, 13, 12, 12, 12, 11, 11, 11, 10, 10, 10, 9, 9, 8, 8, 7, 7, 6, 5, 4, 3, 2, 1, 1, 0
46 };
47 internal static readonly byte[] k_DefaultModelData = { 16, // 16 symbols
48 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6,
49 0, 0 }; // no contexts
50 internal const int k_AlphabetSize = 16;
51 internal const int k_MaxHuffmanSymbolLength = 6;
52 internal const int k_MaxContexts = 1;
53 byte m_Initialized;
54
55 static class SharedStaticCompressionModel
56 {
57 internal static readonly SharedStatic<StreamCompressionModel> Default = SharedStatic<StreamCompressionModel>.GetOrCreate<StreamCompressionModel>();
58 }
59
60 /// <summary>
61 /// A shared singleton instance of <see cref="StreamCompressionModel"/>, this instance is initialized using
62 /// hardcoded bucket parameters and model.
63 /// </summary>
64 public static StreamCompressionModel Default {
65 get
66 {
67 if (SharedStaticCompressionModel.Default.Data.m_Initialized == 1)
68 {
69 return SharedStaticCompressionModel.Default.Data;
70 }
71 Initialize();
72 SharedStaticCompressionModel.Default.Data.m_Initialized = 1;
73
74 return SharedStaticCompressionModel.Default.Data;
75 }
76 }
77
78 static void Initialize()
79 {
80 for (int i = 0; i < k_AlphabetSize; ++i)
81 {
82 SharedStaticCompressionModel.Default.Data.bucketSizes[i] = k_BucketSizes[i];
83 SharedStaticCompressionModel.Default.Data.bucketOffsets[i] = k_BucketOffsets[i];
84 }
85 var modelData = new NativeArray<byte>(k_DefaultModelData.Length, Allocator.Temp);
86 for (var index = 0; index < k_DefaultModelData.Length; index++)
87 {
88 modelData[index] = k_DefaultModelData[index];
89 }
90
91 //int numContexts = NetworkConfig.maxContexts;
92 int numContexts = 1;
93 var symbolLengths = new NativeArray<byte>(numContexts * k_AlphabetSize, Allocator.Temp);
94
95 int readOffset = 0;
96 {
97 // default model
98 int defaultModelAlphabetSize = modelData[readOffset++];
99 CheckAlphabetSize(defaultModelAlphabetSize);
100
101 for (int i = 0; i < k_AlphabetSize; i++)
102 {
103 byte length = modelData[readOffset++];
104 for (int context = 0; context < numContexts; context++)
105 {
106 symbolLengths[numContexts * context + i] = length;
107 }
108 }
109
110 // other models
111 int numModels = modelData[readOffset] | (modelData[readOffset + 1] << 8);
112 readOffset += 2;
113 for (int model = 0; model < numModels; model++)
114 {
115 int context = modelData[readOffset] | (modelData[readOffset + 1] << 8);
116 readOffset += 2;
117
118 int modelAlphabetSize = modelData[readOffset++];
119 CheckAlphabetSize(modelAlphabetSize);
120 for (int i = 0; i < k_AlphabetSize; i++)
121 {
122 byte length = modelData[readOffset++];
123 symbolLengths[numContexts * context + i] = length;
124 }
125 }
126 }
127
128 // generate tables
129 var tmpSymbolLengths = new NativeArray<byte>(k_AlphabetSize, Allocator.Temp);
130 var tmpSymbolDecodeTable = new NativeArray<ushort>(1 << k_MaxHuffmanSymbolLength, Allocator.Temp);
131 var symbolCodes = new NativeArray<byte>(k_AlphabetSize, Allocator.Temp);
132
133 for (int context = 0; context < numContexts; context++)
134 {
135 for (int i = 0; i < k_AlphabetSize; i++)
136 tmpSymbolLengths[i] = symbolLengths[numContexts * context + i];
137
138 GenerateHuffmanCodes(symbolCodes, 0, tmpSymbolLengths, 0, k_AlphabetSize, k_MaxHuffmanSymbolLength);
139 GenerateHuffmanDecodeTable(tmpSymbolDecodeTable, 0, tmpSymbolLengths, symbolCodes, k_AlphabetSize, k_MaxHuffmanSymbolLength);
140 for (int i = 0; i < k_AlphabetSize; i++)
141 {
142 SharedStaticCompressionModel.Default.Data.encodeTable[context * k_AlphabetSize + i] = (ushort)((symbolCodes[i] << 8) | symbolLengths[numContexts * context + i]);
143 }
144 for (int i = 0; i < (1 << k_MaxHuffmanSymbolLength); i++)
145 {
146 SharedStaticCompressionModel.Default.Data.decodeTable[context * (1 << k_MaxHuffmanSymbolLength) + i] = tmpSymbolDecodeTable[i];
147 }
148 }
149 }
150
151 static void GenerateHuffmanCodes(NativeArray<byte> symbolCodes, int symbolCodesOffset, NativeArray<byte> symbolLengths, int symbolLengthsOffset, int alphabetSize, int maxCodeLength)
152 {
153 CheckAlphabetAndMaxCodeLength(alphabetSize, maxCodeLength);
154
155 var lengthCounts = new NativeArray<byte>(maxCodeLength + 1, Allocator.Temp);
156 var symbolList = new NativeArray<byte>((maxCodeLength + 1) * alphabetSize, Allocator.Temp);
157
158 //byte[] symbol_list[(MAX_HUFFMAN_CODE_LENGTH + 1u) * MAX_NUM_HUFFMAN_SYMBOLS];
159 for (int symbol = 0; symbol < alphabetSize; symbol++)
160 {
161 int symbolLength = symbolLengths[symbol + symbolLengthsOffset];
162 CheckExceedMaxCodeLength(symbolLength, maxCodeLength);
163 symbolList[(maxCodeLength + 1) * symbolLength + lengthCounts[symbolLength]++] = (byte)symbol;
164 }
165
166 uint nextCodeWord = 0;
167 for (int length = 1; length <= maxCodeLength; length++)
168 {
169 int length_count = lengthCounts[length];
170 for (int i = 0; i < length_count; i++)
171 {
172 int symbol = symbolList[(maxCodeLength + 1) * length + i];
173 CheckSymbolLength(symbolLengths, symbolLengthsOffset, symbol, length);
174 symbolCodes[symbol + symbolCodesOffset] = (byte)ReverseBits(nextCodeWord++, length);
175 }
176 nextCodeWord <<= 1;
177 }
178 }
179
180 static uint ReverseBits(uint value, int num_bits)
181 {
182 value = ((value & 0x55555555u) << 1) | ((value & 0xAAAAAAAAu) >> 1);
183 value = ((value & 0x33333333u) << 2) | ((value & 0xCCCCCCCCu) >> 2);
184 value = ((value & 0x0F0F0F0Fu) << 4) | ((value & 0xF0F0F0F0u) >> 4);
185 value = ((value & 0x00FF00FFu) << 8) | ((value & 0xFF00FF00u) >> 8);
186 value = (value << 16) | (value >> 16);
187 return value >> (32 - num_bits);
188 }
189
190 // decode table entries: (symbol << 8) | length
191 static void GenerateHuffmanDecodeTable(NativeArray<ushort> decodeTable, int decodeTableOffset, NativeArray<byte> symbolLengths, NativeArray<byte> symbolCodes, int alphabetSize, int maxCodeLength)
192 {
193 CheckAlphabetAndMaxCodeLength(alphabetSize, maxCodeLength);
194
195 uint maxCode = 1u << maxCodeLength;
196 for (int symbol = 0; symbol < alphabetSize; symbol++)
197 {
198 int length = symbolLengths[symbol];
199 CheckExceedMaxCodeLength(length, maxCodeLength);
200 if (length > 0)
201 {
202 uint code = symbolCodes[symbol];
203 uint step = 1u << length;
204 do
205 {
206 decodeTable[(int)(decodeTableOffset + code)] = (ushort)(symbol << 8 | length);
207 code += step;
208 }
209 while (code < maxCode);
210 }
211 }
212 }
213
214 /// <summary>
215 /// Bucket n starts at bucketOffsets[n] and ends at bucketOffsets[n] + (1 << bucketSizes[n]).
216 /// (code << 8) | length
217 /// </summary>
218 internal fixed ushort encodeTable[k_MaxContexts * k_AlphabetSize];
219 /// <summary>
220 /// Bucket n starts at bucketOffsets[n] and ends at bucketOffsets[n] + (1 << bucketSizes[n]).
221 /// (symbol << 8) | length
222 /// </summary>
223 internal fixed ushort decodeTable[k_MaxContexts * (1 << k_MaxHuffmanSymbolLength)];
224 /// <summary>
225 /// Specifies the sizes of the buckets in bits, so a bucket of n bits has 2^n values.
226 /// </summary>
227 internal fixed byte bucketSizes[k_AlphabetSize];
228 /// <summary>
229 /// Specifies the starting positions of the bucket.
230 /// </summary>
231 internal fixed uint bucketOffsets[k_AlphabetSize];
232
233 /// <summary>
234 /// Calculates the bucket index into the <see cref="encodeTable"/> where the specified value should be written.
235 /// </summary>
236 /// <param name="value">A 4-byte unsigned integer value to find a bucket for.</param>
237 /// <returns>The bucket index where to put the value.</returns>
238 readonly public int CalculateBucket(uint value)
239 {
240 int bucketIndex = k_FirstBucketCandidate[math.lzcnt(value)];
241 if (bucketIndex + 1 < k_AlphabetSize && value >= bucketOffsets[bucketIndex + 1])
242 bucketIndex++;
243
244 return bucketIndex;
245 }
246
247 /// <summary>
248 /// The compressed size in bits of the given unsigned integer value
249 /// </summary>
250 /// <param name="value">the unsigned int value you want to compress</param>
251 /// <returns></returns>
252 public readonly int GetCompressedSizeInBits(uint value)
253 {
254 int bucket = CalculateBucket(value);
255 int bits = bucketSizes[bucket];
256 ushort encodeEntry = encodeTable[bucket];
257 return (encodeEntry & 0xff) + bits;
258 }
259
260 [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS"), Conditional("UNITY_DOTS_DEBUG")]
261 static void CheckAlphabetSize(int alphabetSize)
262 {
263 if (alphabetSize != k_AlphabetSize)
264 {
265 throw new InvalidOperationException("The alphabet size of compression models must be " + k_AlphabetSize);
266 }
267 }
268
269 [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS"), Conditional("UNITY_DOTS_DEBUG")]
270 static void CheckSymbolLength(NativeArray<byte> symbolLengths, int symbolLengthsOffset, int symbol, int length)
271 {
272 if (symbolLengths[symbol + symbolLengthsOffset] != length)
273 throw new InvalidOperationException("Incorrect symbol length");
274 }
275
276 [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS"), Conditional("UNITY_DOTS_DEBUG")]
277 static void CheckAlphabetAndMaxCodeLength(int alphabetSize, int maxCodeLength)
278 {
279 if (alphabetSize > 256 || maxCodeLength > 8)
280 throw new InvalidOperationException("Can only generate huffman codes up to alphabet size 256 and maximum code length 8");
281 }
282
283 [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS"), Conditional("UNITY_DOTS_DEBUG")]
284 static void CheckExceedMaxCodeLength(int length, int maxCodeLength)
285 {
286 if (length > maxCodeLength)
287 throw new InvalidOperationException("Maximum code length exceeded");
288 }
289 }
290}