1 | /* (c) Magnus Auvinen. See licence.txt in the root of the distribution for more information. */ |
2 | /* If you are missing that file, acquire a complete release at teeworlds.com. */ |
3 | #include "snapshot.h" |
4 | #include "compression.h" |
5 | #include "uuid_manager.h" |
6 | |
7 | #include <cstdlib> |
8 | #include <limits> |
9 | |
10 | #include <base/math.h> |
11 | #include <base/system.h> |
12 | |
13 | #include <game/generated/protocolglue.h> |
14 | |
15 | // CSnapshot |
16 | |
17 | const CSnapshotItem *CSnapshot::GetItem(int Index) const |
18 | { |
19 | return (const CSnapshotItem *)(DataStart() + Offsets()[Index]); |
20 | } |
21 | |
22 | const CSnapshot CSnapshot::ms_EmptySnapshot; |
23 | |
24 | int CSnapshot::GetItemSize(int Index) const |
25 | { |
26 | if(Index == m_NumItems - 1) |
27 | return (m_DataSize - Offsets()[Index]) - sizeof(CSnapshotItem); |
28 | return (Offsets()[Index + 1] - Offsets()[Index]) - sizeof(CSnapshotItem); |
29 | } |
30 | |
31 | int CSnapshot::GetItemType(int Index) const |
32 | { |
33 | int InternalType = GetItem(Index)->Type(); |
34 | return GetExternalItemType(InternalType); |
35 | } |
36 | |
37 | int CSnapshot::GetExternalItemType(int InternalType) const |
38 | { |
39 | if(InternalType < OFFSET_UUID_TYPE) |
40 | { |
41 | return InternalType; |
42 | } |
43 | |
44 | int TypeItemIndex = GetItemIndex(Key: InternalType); // NETOBJTYPE_EX |
45 | if(TypeItemIndex == -1 || GetItemSize(Index: TypeItemIndex) < (int)sizeof(CUuid)) |
46 | { |
47 | return InternalType; |
48 | } |
49 | const CSnapshotItem *pTypeItem = GetItem(Index: TypeItemIndex); |
50 | CUuid Uuid; |
51 | for(size_t i = 0; i < sizeof(CUuid) / sizeof(int32_t); i++) |
52 | uint_to_bytes_be(bytes: &Uuid.m_aData[i * sizeof(int32_t)], value: pTypeItem->Data()[i]); |
53 | |
54 | return g_UuidManager.LookupUuid(Uuid); |
55 | } |
56 | |
57 | int CSnapshot::GetItemIndex(int Key) const |
58 | { |
59 | // TODO: OPT: this should not be a linear search. very bad |
60 | for(int i = 0; i < m_NumItems; i++) |
61 | { |
62 | if(GetItem(Index: i)->Key() == Key) |
63 | return i; |
64 | } |
65 | return -1; |
66 | } |
67 | |
68 | const void *CSnapshot::FindItem(int Type, int Id) const |
69 | { |
70 | int InternalType = Type; |
71 | if(Type >= OFFSET_UUID) |
72 | { |
73 | CUuid TypeUuid = g_UuidManager.GetUuid(Id: Type); |
74 | int aTypeUuidItem[sizeof(CUuid) / sizeof(int32_t)]; |
75 | for(size_t i = 0; i < sizeof(CUuid) / sizeof(int32_t); i++) |
76 | aTypeUuidItem[i] = bytes_be_to_uint(bytes: &TypeUuid.m_aData[i * sizeof(int32_t)]); |
77 | |
78 | bool Found = false; |
79 | for(int i = 0; i < m_NumItems; i++) |
80 | { |
81 | const CSnapshotItem *pItem = GetItem(Index: i); |
82 | if(pItem->Type() == 0 && pItem->Id() >= OFFSET_UUID_TYPE) // NETOBJTYPE_EX |
83 | { |
84 | if(mem_comp(a: pItem->Data(), b: aTypeUuidItem, size: sizeof(CUuid)) == 0) |
85 | { |
86 | InternalType = pItem->Id(); |
87 | Found = true; |
88 | break; |
89 | } |
90 | } |
91 | } |
92 | if(!Found) |
93 | { |
94 | return nullptr; |
95 | } |
96 | } |
97 | int Index = GetItemIndex(Key: (InternalType << 16) | Id); |
98 | return Index < 0 ? nullptr : GetItem(Index)->Data(); |
99 | } |
100 | |
101 | unsigned CSnapshot::Crc() const |
102 | { |
103 | unsigned int Crc = 0; |
104 | |
105 | for(int i = 0; i < m_NumItems; i++) |
106 | { |
107 | const CSnapshotItem *pItem = GetItem(Index: i); |
108 | int Size = GetItemSize(Index: i); |
109 | |
110 | for(size_t b = 0; b < Size / sizeof(int32_t); b++) |
111 | Crc += pItem->Data()[b]; |
112 | } |
113 | return Crc; |
114 | } |
115 | |
116 | void CSnapshot::DebugDump() const |
117 | { |
118 | dbg_msg(sys: "snapshot" , fmt: "data_size=%d num_items=%d" , m_DataSize, m_NumItems); |
119 | for(int i = 0; i < m_NumItems; i++) |
120 | { |
121 | const CSnapshotItem *pItem = GetItem(Index: i); |
122 | int Size = GetItemSize(Index: i); |
123 | dbg_msg(sys: "snapshot" , fmt: "\ttype=%d id=%d" , pItem->Type(), pItem->Id()); |
124 | for(size_t b = 0; b < Size / sizeof(int32_t); b++) |
125 | dbg_msg(sys: "snapshot" , fmt: "\t\t%3d %12d\t%08x" , (int)b, pItem->Data()[b], pItem->Data()[b]); |
126 | } |
127 | } |
128 | |
129 | bool CSnapshot::IsValid(size_t ActualSize) const |
130 | { |
131 | // validate total size |
132 | if(ActualSize < sizeof(CSnapshot) || m_NumItems < 0 || m_DataSize < 0 || ActualSize != TotalSize()) |
133 | return false; |
134 | |
135 | // validate item offsets |
136 | const int *pOffsets = Offsets(); |
137 | for(int Index = 0; Index < m_NumItems; Index++) |
138 | if(pOffsets[Index] < 0 || pOffsets[Index] > m_DataSize) |
139 | return false; |
140 | |
141 | // validate item sizes |
142 | for(int Index = 0; Index < m_NumItems; Index++) |
143 | if(GetItemSize(Index) < 0) // the offsets must be validated before using this |
144 | return false; |
145 | |
146 | return true; |
147 | } |
148 | |
149 | // CSnapshotDelta |
150 | |
151 | enum |
152 | { |
153 | HASHLIST_SIZE = 256, |
154 | HASHLIST_BUCKET_SIZE = 64, |
155 | }; |
156 | |
157 | struct CItemList |
158 | { |
159 | int m_Num; |
160 | int m_aKeys[HASHLIST_BUCKET_SIZE]; |
161 | int m_aIndex[HASHLIST_BUCKET_SIZE]; |
162 | }; |
163 | |
164 | inline size_t CalcHashId(int Key) |
165 | { |
166 | // djb2 (http://www.cse.yorku.ca/~oz/hash.html) |
167 | unsigned Hash = 5381; |
168 | for(unsigned Shift = 0; Shift < sizeof(int); Shift++) |
169 | Hash = ((Hash << 5) + Hash) + ((Key >> (Shift * 8)) & 0xFF); |
170 | return Hash % HASHLIST_SIZE; |
171 | } |
172 | |
173 | static void GenerateHash(CItemList *pHashlist, const CSnapshot *pSnapshot) |
174 | { |
175 | for(int i = 0; i < HASHLIST_SIZE; i++) |
176 | pHashlist[i].m_Num = 0; |
177 | |
178 | for(int i = 0; i < pSnapshot->NumItems(); i++) |
179 | { |
180 | int Key = pSnapshot->GetItem(Index: i)->Key(); |
181 | size_t HashId = CalcHashId(Key); |
182 | if(pHashlist[HashId].m_Num < HASHLIST_BUCKET_SIZE) |
183 | { |
184 | pHashlist[HashId].m_aIndex[pHashlist[HashId].m_Num] = i; |
185 | pHashlist[HashId].m_aKeys[pHashlist[HashId].m_Num] = Key; |
186 | pHashlist[HashId].m_Num++; |
187 | } |
188 | } |
189 | } |
190 | |
191 | static int GetItemIndexHashed(int Key, const CItemList *pHashlist) |
192 | { |
193 | size_t HashId = CalcHashId(Key); |
194 | for(int i = 0; i < pHashlist[HashId].m_Num; i++) |
195 | { |
196 | if(pHashlist[HashId].m_aKeys[i] == Key) |
197 | return pHashlist[HashId].m_aIndex[i]; |
198 | } |
199 | |
200 | return -1; |
201 | } |
202 | |
203 | int CSnapshotDelta::DiffItem(const int *pPast, const int *pCurrent, int *pOut, int Size) |
204 | { |
205 | int Needed = 0; |
206 | while(Size) |
207 | { |
208 | // subtraction with wrapping by casting to unsigned |
209 | *pOut = (unsigned)*pCurrent - (unsigned)*pPast; |
210 | Needed |= *pOut; |
211 | pOut++; |
212 | pPast++; |
213 | pCurrent++; |
214 | Size--; |
215 | } |
216 | |
217 | return Needed; |
218 | } |
219 | |
220 | void CSnapshotDelta::UndiffItem(const int *pPast, const int *pDiff, int *pOut, int Size, int *pDataRate) |
221 | { |
222 | while(Size) |
223 | { |
224 | // addition with wrapping by casting to unsigned |
225 | *pOut = (unsigned)*pPast + (unsigned)*pDiff; |
226 | |
227 | if(*pDiff == 0) |
228 | *pDataRate += 1; |
229 | else |
230 | { |
231 | unsigned char aBuf[CVariableInt::MAX_BYTES_PACKED]; |
232 | unsigned char *pEnd = CVariableInt::Pack(pDst: aBuf, i: *pDiff, DstSize: sizeof(aBuf)); |
233 | *pDataRate += (int)(pEnd - (unsigned char *)aBuf) * 8; |
234 | } |
235 | |
236 | pOut++; |
237 | pPast++; |
238 | pDiff++; |
239 | Size--; |
240 | } |
241 | } |
242 | |
243 | CSnapshotDelta::CSnapshotDelta() |
244 | { |
245 | mem_zero(block: m_aItemSizes, size: sizeof(m_aItemSizes)); |
246 | mem_zero(block: m_aSnapshotDataRate, size: sizeof(m_aSnapshotDataRate)); |
247 | mem_zero(block: m_aSnapshotDataUpdates, size: sizeof(m_aSnapshotDataUpdates)); |
248 | mem_zero(block: &m_Empty, size: sizeof(m_Empty)); |
249 | } |
250 | |
251 | CSnapshotDelta::CSnapshotDelta(const CSnapshotDelta &Old) |
252 | { |
253 | mem_copy(dest: m_aItemSizes, source: Old.m_aItemSizes, size: sizeof(m_aItemSizes)); |
254 | mem_copy(dest: m_aSnapshotDataRate, source: Old.m_aSnapshotDataRate, size: sizeof(m_aSnapshotDataRate)); |
255 | mem_copy(dest: m_aSnapshotDataUpdates, source: Old.m_aSnapshotDataUpdates, size: sizeof(m_aSnapshotDataUpdates)); |
256 | mem_zero(block: &m_Empty, size: sizeof(m_Empty)); |
257 | } |
258 | |
259 | void CSnapshotDelta::SetStaticsize(int ItemType, size_t Size) |
260 | { |
261 | dbg_assert(ItemType >= 0 && ItemType < MAX_NETOBJSIZES, "ItemType invalid" ); |
262 | dbg_assert(Size <= (size_t)std::numeric_limits<int16_t>::max(), "Size invalid" ); |
263 | m_aItemSizes[ItemType] = Size; |
264 | } |
265 | |
266 | const CSnapshotDelta::CData *CSnapshotDelta::EmptyDelta() const |
267 | { |
268 | return &m_Empty; |
269 | } |
270 | |
271 | // TODO: OPT: this should be made much faster |
272 | int CSnapshotDelta::CreateDelta(const CSnapshot *pFrom, const CSnapshot *pTo, void *pDstData) |
273 | { |
274 | CData *pDelta = (CData *)pDstData; |
275 | int *pData = (int *)pDelta->m_aData; |
276 | |
277 | pDelta->m_NumDeletedItems = 0; |
278 | pDelta->m_NumUpdateItems = 0; |
279 | pDelta->m_NumTempItems = 0; |
280 | |
281 | CItemList aHashlist[HASHLIST_SIZE]; |
282 | GenerateHash(pHashlist: aHashlist, pSnapshot: pTo); |
283 | |
284 | // pack deleted stuff |
285 | for(int i = 0; i < pFrom->NumItems(); i++) |
286 | { |
287 | const CSnapshotItem *pFromItem = pFrom->GetItem(Index: i); |
288 | if(GetItemIndexHashed(Key: pFromItem->Key(), pHashlist: aHashlist) == -1) |
289 | { |
290 | // deleted |
291 | pDelta->m_NumDeletedItems++; |
292 | *pData = pFromItem->Key(); |
293 | pData++; |
294 | } |
295 | } |
296 | |
297 | GenerateHash(pHashlist: aHashlist, pSnapshot: pFrom); |
298 | |
299 | // fetch previous indices |
300 | // we do this as a separate pass because it helps the cache |
301 | int aPastIndices[CSnapshot::MAX_ITEMS]; |
302 | const int NumItems = pTo->NumItems(); |
303 | for(int i = 0; i < NumItems; i++) |
304 | { |
305 | const CSnapshotItem *pCurItem = pTo->GetItem(Index: i); // O(1) .. O(n) |
306 | aPastIndices[i] = GetItemIndexHashed(Key: pCurItem->Key(), pHashlist: aHashlist); // O(n) .. O(n^n) |
307 | } |
308 | |
309 | for(int i = 0; i < NumItems; i++) |
310 | { |
311 | // do delta |
312 | const int ItemSize = pTo->GetItemSize(Index: i); // O(1) .. O(n) |
313 | const CSnapshotItem *pCurItem = pTo->GetItem(Index: i); // O(1) .. O(n) |
314 | const int PastIndex = aPastIndices[i]; |
315 | const bool IncludeSize = pCurItem->Type() >= MAX_NETOBJSIZES || !m_aItemSizes[pCurItem->Type()]; |
316 | |
317 | if(PastIndex != -1) |
318 | { |
319 | int *pItemDataDst = pData + 3; |
320 | |
321 | const CSnapshotItem *pPastItem = pFrom->GetItem(Index: PastIndex); |
322 | |
323 | if(!IncludeSize) |
324 | pItemDataDst = pData + 2; |
325 | |
326 | if(DiffItem(pPast: pPastItem->Data(), pCurrent: pCurItem->Data(), pOut: pItemDataDst, Size: ItemSize / sizeof(int32_t))) |
327 | { |
328 | *pData++ = pCurItem->Type(); |
329 | *pData++ = pCurItem->Id(); |
330 | if(IncludeSize) |
331 | *pData++ = ItemSize / sizeof(int32_t); |
332 | pData += ItemSize / sizeof(int32_t); |
333 | pDelta->m_NumUpdateItems++; |
334 | } |
335 | } |
336 | else |
337 | { |
338 | *pData++ = pCurItem->Type(); |
339 | *pData++ = pCurItem->Id(); |
340 | if(IncludeSize) |
341 | *pData++ = ItemSize / sizeof(int32_t); |
342 | |
343 | mem_copy(dest: pData, source: pCurItem->Data(), size: ItemSize); |
344 | pData += ItemSize / sizeof(int32_t); |
345 | pDelta->m_NumUpdateItems++; |
346 | } |
347 | } |
348 | |
349 | if(!pDelta->m_NumDeletedItems && !pDelta->m_NumUpdateItems && !pDelta->m_NumTempItems) |
350 | return 0; |
351 | |
352 | return (int)((char *)pData - (char *)pDstData); |
353 | } |
354 | |
355 | int CSnapshotDelta::DebugDumpDelta(const void *pSrcData, int DataSize) |
356 | { |
357 | CData *pDelta = (CData *)pSrcData; |
358 | int *pData = (int *)pDelta->m_aData; |
359 | int *pEnd = (int *)(((char *)pSrcData + DataSize)); |
360 | |
361 | dbg_msg(sys: "delta_dump" , fmt: "+-----------------------------------------------" ); |
362 | if(DataSize < 3 * (int)sizeof(int32_t)) |
363 | { |
364 | dbg_msg(sys: "delta_dump" , fmt: "| delta size %d too small. Should at least fit the empty delta header." , DataSize); |
365 | return -505; |
366 | } |
367 | |
368 | dbg_msg(sys: "delta_dump" , fmt: "| data_size=%d" , DataSize); |
369 | |
370 | int DumpIndex = 0; |
371 | |
372 | // dump header |
373 | { |
374 | int * = (int *)pSrcData; |
375 | dbg_msg(sys: "delta_dump" , fmt: "| %3d %12d %08x m_NumDeletedItems=%d" , DumpIndex++, *pDumpHeader, *pDumpHeader, *pDumpHeader); |
376 | pDumpHeader++; |
377 | dbg_msg(sys: "delta_dump" , fmt: "| %3d %12d %08x m_NumUpdatedItems=%d" , DumpIndex++, *pDumpHeader, *pDumpHeader, *pDumpHeader); |
378 | pDumpHeader++; |
379 | dbg_msg(sys: "delta_dump" , fmt: "| %3d %12d %08x _zero=%d" , DumpIndex++, *pDumpHeader, *pDumpHeader, *pDumpHeader); |
380 | pDumpHeader++; |
381 | |
382 | dbg_assert(pDumpHeader == pData, "invalid header size" ); |
383 | } |
384 | |
385 | // unpack deleted stuff |
386 | int *pDeleted = pData; |
387 | if(pDelta->m_NumDeletedItems < 0) |
388 | { |
389 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Number of deleted items %d is negative." , pDelta->m_NumDeletedItems); |
390 | return -201; |
391 | } |
392 | pData += pDelta->m_NumDeletedItems; |
393 | if(pData > pEnd) |
394 | { |
395 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Read past the end." ); |
396 | return -101; |
397 | } |
398 | |
399 | // list deleted items |
400 | // (all other items should be copied from the last full snap) |
401 | for(int d = 0; d < pDelta->m_NumDeletedItems; d++) |
402 | { |
403 | int Type = pDeleted[d] >> 16; |
404 | int Id = pDeleted[d] & 0xffff; |
405 | dbg_msg(sys: "delta_dump" , fmt: " %3d %12d %08x deleted Type=%d Id=%d" , DumpIndex++, pDeleted[d], pDeleted[d], Type, Id); |
406 | } |
407 | |
408 | // unpack updated stuff |
409 | for(int i = 0; i < pDelta->m_NumUpdateItems; i++) |
410 | { |
411 | if(pData + 2 > pEnd) |
412 | { |
413 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. NumUpdateItems=%d can't be fit into DataSize=%d" , pDelta->m_NumUpdateItems, DataSize); |
414 | return -102; |
415 | } |
416 | |
417 | dbg_msg(sys: "delta_dump" , fmt: "| --------------------------------" ); |
418 | dbg_msg(sys: "delta_dump" , fmt: "| %3d %12d %08x updated Type=%d" , DumpIndex++, *pData, *pData, *pData); |
419 | const int Type = *pData++; |
420 | if(Type < 0 || Type > CSnapshot::MAX_TYPE) |
421 | { |
422 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Type=%d out of range (0 - %d)" , Type, CSnapshot::MAX_TYPE); |
423 | return -202; |
424 | } |
425 | |
426 | dbg_msg(sys: "delta_dump" , fmt: "| %3d %12d %08x updated Id=%d" , DumpIndex++, *pData, *pData, *pData); |
427 | const int Id = *pData++; |
428 | if(Id < 0 || Id > CSnapshot::MAX_ID) |
429 | { |
430 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Id=%d out of range (0 - %d)" , Id, CSnapshot::MAX_ID); |
431 | return -203; |
432 | } |
433 | |
434 | // size of the item in bytes |
435 | int ItemSize; |
436 | if(Type < MAX_NETOBJSIZES && m_aItemSizes[Type]) |
437 | { |
438 | ItemSize = m_aItemSizes[Type]; |
439 | dbg_msg(sys: "delta_dump" , fmt: "| updated size=%d (known)" , ItemSize); |
440 | } |
441 | else |
442 | { |
443 | if(pData + 1 > pEnd) |
444 | { |
445 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Expected item size but got end of data." ); |
446 | return -103; |
447 | } |
448 | if(*pData < 0 || (size_t)*pData > std::numeric_limits<int32_t>::max() / sizeof(int32_t)) |
449 | { |
450 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Item size %d out of range (0 - %" PRIzu ")" , *pData, std::numeric_limits<int32_t>::max() / sizeof(int32_t)); |
451 | return -204; |
452 | } |
453 | dbg_msg(sys: "delta_dump" , fmt: "| %3d %12d %08x updated size=%d" , DumpIndex++, *pData, *pData, *pData); |
454 | ItemSize = (*pData++) * sizeof(int32_t); |
455 | } |
456 | |
457 | if(ItemSize < 0) |
458 | { |
459 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Item size %d is negative." , ItemSize); |
460 | return -205; |
461 | } |
462 | if((const char *)pEnd - (const char *)pData < ItemSize) |
463 | { |
464 | dbg_msg(sys: "delta_dump" , fmt: "| Invalid delta. Item with type=%d id=%d size=%d does not fit into the delta." , Type, Id, ItemSize); |
465 | return -205; |
466 | } |
467 | |
468 | // divide item size in bytes by size of integers |
469 | // to get the number of integers we want to increment the pointer |
470 | const int *pItemEnd = pData + (ItemSize / sizeof(int32_t)); |
471 | |
472 | for(size_t b = 0; b < ItemSize / sizeof(int32_t); b++) |
473 | { |
474 | dbg_msg(sys: "delta_dump" , fmt: "| %3d %12d %08x item data" , DumpIndex++, *pData, *pData); |
475 | pData++; |
476 | } |
477 | |
478 | dbg_assert(pItemEnd == pData, "Incorrect amount of data dumped for this item." ); |
479 | } |
480 | |
481 | dbg_msg(sys: "delta_dump" , fmt: "| Finished with expected_data_size=%d parsed_data_size=%" PRIzu, DataSize, (pData - (int *)pSrcData) * sizeof(int32_t)); |
482 | dbg_msg(sys: "delta_dump" , fmt: "+--------------------" ); |
483 | |
484 | return 0; |
485 | } |
486 | |
487 | int CSnapshotDelta::UnpackDelta(const CSnapshot *pFrom, CSnapshot *pTo, const void *pSrcData, int DataSize) |
488 | { |
489 | CData *pDelta = (CData *)pSrcData; |
490 | int *pData = (int *)pDelta->m_aData; |
491 | int *pEnd = (int *)(((char *)pSrcData + DataSize)); |
492 | |
493 | CSnapshotBuilder Builder; |
494 | Builder.Init(); |
495 | |
496 | // unpack deleted stuff |
497 | int *pDeleted = pData; |
498 | if(pDelta->m_NumDeletedItems < 0) |
499 | return -201; |
500 | pData += pDelta->m_NumDeletedItems; |
501 | if(pData > pEnd) |
502 | return -101; |
503 | |
504 | // copy all non deleted stuff |
505 | for(int i = 0; i < pFrom->NumItems(); i++) |
506 | { |
507 | const CSnapshotItem *pFromItem = pFrom->GetItem(Index: i); |
508 | const int ItemSize = pFrom->GetItemSize(Index: i); |
509 | bool Keep = true; |
510 | for(int d = 0; d < pDelta->m_NumDeletedItems; d++) |
511 | { |
512 | if(pDeleted[d] == pFromItem->Key()) |
513 | { |
514 | Keep = false; |
515 | break; |
516 | } |
517 | } |
518 | |
519 | if(Keep) |
520 | { |
521 | void *pObj = Builder.NewItem(Type: pFromItem->Type(), Id: pFromItem->Id(), Size: ItemSize); |
522 | if(!pObj) |
523 | return -301; |
524 | |
525 | // keep it |
526 | mem_copy(dest: pObj, source: pFromItem->Data(), size: ItemSize); |
527 | } |
528 | } |
529 | |
530 | // unpack updated stuff |
531 | for(int i = 0; i < pDelta->m_NumUpdateItems; i++) |
532 | { |
533 | if(pData + 2 > pEnd) |
534 | return -102; |
535 | |
536 | const int Type = *pData++; |
537 | if(Type < 0 || Type > CSnapshot::MAX_TYPE) |
538 | return -202; |
539 | |
540 | const int Id = *pData++; |
541 | if(Id < 0 || Id > CSnapshot::MAX_ID) |
542 | return -203; |
543 | |
544 | int ItemSize; |
545 | if(Type < MAX_NETOBJSIZES && m_aItemSizes[Type]) |
546 | ItemSize = m_aItemSizes[Type]; |
547 | else |
548 | { |
549 | if(pData + 1 > pEnd) |
550 | return -103; |
551 | if(*pData < 0 || (size_t)*pData > std::numeric_limits<int32_t>::max() / sizeof(int32_t)) |
552 | return -204; |
553 | ItemSize = (*pData++) * sizeof(int32_t); |
554 | } |
555 | |
556 | if(ItemSize < 0 || (const char *)pEnd - (const char *)pData < ItemSize) |
557 | return -205; |
558 | |
559 | const int Key = (Type << 16) | Id; |
560 | |
561 | // create the item if needed |
562 | int *pNewData = Builder.GetItemData(Key); |
563 | if(!pNewData) |
564 | pNewData = (int *)Builder.NewItem(Type, Id, Size: ItemSize); |
565 | |
566 | if(!pNewData) |
567 | return -302; |
568 | |
569 | const int FromIndex = pFrom->GetItemIndex(Key); |
570 | if(FromIndex != -1) |
571 | { |
572 | // we got an update so we need to apply the diff |
573 | UndiffItem(pPast: pFrom->GetItem(Index: FromIndex)->Data(), pDiff: pData, pOut: pNewData, Size: ItemSize / sizeof(int32_t), pDataRate: &m_aSnapshotDataRate[Type]); |
574 | } |
575 | else // no previous, just copy the pData |
576 | { |
577 | mem_copy(dest: pNewData, source: pData, size: ItemSize); |
578 | m_aSnapshotDataRate[Type] += ItemSize * 8; |
579 | } |
580 | m_aSnapshotDataUpdates[Type]++; |
581 | |
582 | pData += ItemSize / sizeof(int32_t); |
583 | } |
584 | |
585 | // finish up |
586 | return Builder.Finish(pSnapdata: pTo); |
587 | } |
588 | |
589 | // CSnapshotStorage |
590 | |
591 | void CSnapshotStorage::Init() |
592 | { |
593 | m_pFirst = nullptr; |
594 | m_pLast = nullptr; |
595 | } |
596 | |
597 | void CSnapshotStorage::PurgeAll() |
598 | { |
599 | while(m_pFirst) |
600 | { |
601 | CHolder *pNext = m_pFirst->m_pNext; |
602 | free(ptr: m_pFirst->m_pSnap); |
603 | free(ptr: m_pFirst->m_pAltSnap); |
604 | free(ptr: m_pFirst); |
605 | m_pFirst = pNext; |
606 | } |
607 | m_pLast = nullptr; |
608 | } |
609 | |
610 | void CSnapshotStorage::PurgeUntil(int Tick) |
611 | { |
612 | CHolder *pHolder = m_pFirst; |
613 | |
614 | while(pHolder) |
615 | { |
616 | CHolder *pNext = pHolder->m_pNext; |
617 | if(pHolder->m_Tick >= Tick) |
618 | return; // no more to remove |
619 | free(ptr: pHolder->m_pSnap); |
620 | free(ptr: pHolder->m_pAltSnap); |
621 | free(ptr: pHolder); |
622 | |
623 | // did we come to the end of the list? |
624 | if(!pNext) |
625 | break; |
626 | |
627 | m_pFirst = pNext; |
628 | pNext->m_pPrev = nullptr; |
629 | pHolder = pNext; |
630 | } |
631 | |
632 | // no more snapshots in storage |
633 | m_pFirst = nullptr; |
634 | m_pLast = nullptr; |
635 | } |
636 | |
637 | void CSnapshotStorage::Add(int Tick, int64_t Tagtime, size_t DataSize, const void *pData, size_t AltDataSize, const void *pAltData) |
638 | { |
639 | dbg_assert(DataSize <= (size_t)CSnapshot::MAX_SIZE, "Snapshot data size invalid" ); |
640 | dbg_assert(AltDataSize <= (size_t)CSnapshot::MAX_SIZE, "Alt snapshot data size invalid" ); |
641 | |
642 | CHolder *pHolder = static_cast<CHolder *>(malloc(size: sizeof(CHolder))); |
643 | pHolder->m_Tick = Tick; |
644 | pHolder->m_Tagtime = Tagtime; |
645 | |
646 | pHolder->m_pSnap = static_cast<CSnapshot *>(malloc(size: DataSize)); |
647 | mem_copy(dest: pHolder->m_pSnap, source: pData, size: DataSize); |
648 | pHolder->m_SnapSize = DataSize; |
649 | |
650 | if(AltDataSize) // create alternative if wanted |
651 | { |
652 | pHolder->m_pAltSnap = static_cast<CSnapshot *>(malloc(size: AltDataSize)); |
653 | mem_copy(dest: pHolder->m_pAltSnap, source: pAltData, size: AltDataSize); |
654 | pHolder->m_AltSnapSize = AltDataSize; |
655 | } |
656 | else |
657 | { |
658 | pHolder->m_pAltSnap = nullptr; |
659 | pHolder->m_AltSnapSize = 0; |
660 | } |
661 | |
662 | // link |
663 | pHolder->m_pNext = nullptr; |
664 | pHolder->m_pPrev = m_pLast; |
665 | if(m_pLast) |
666 | m_pLast->m_pNext = pHolder; |
667 | else |
668 | m_pFirst = pHolder; |
669 | m_pLast = pHolder; |
670 | } |
671 | |
672 | int CSnapshotStorage::Get(int Tick, int64_t *pTagtime, const CSnapshot **ppData, const CSnapshot **ppAltData) const |
673 | { |
674 | CHolder *pHolder = m_pFirst; |
675 | |
676 | while(pHolder) |
677 | { |
678 | if(pHolder->m_Tick == Tick) |
679 | { |
680 | if(pTagtime) |
681 | *pTagtime = pHolder->m_Tagtime; |
682 | if(ppData) |
683 | *ppData = pHolder->m_pSnap; |
684 | if(ppAltData) |
685 | *ppAltData = pHolder->m_pAltSnap; |
686 | return pHolder->m_SnapSize; |
687 | } |
688 | |
689 | pHolder = pHolder->m_pNext; |
690 | } |
691 | |
692 | return -1; |
693 | } |
694 | |
695 | // CSnapshotBuilder |
696 | CSnapshotBuilder::CSnapshotBuilder() |
697 | { |
698 | m_NumExtendedItemTypes = 0; |
699 | } |
700 | |
701 | void CSnapshotBuilder::Init(bool Sixup) |
702 | { |
703 | m_DataSize = 0; |
704 | m_NumItems = 0; |
705 | m_Sixup = Sixup; |
706 | |
707 | for(int i = 0; i < m_NumExtendedItemTypes; i++) |
708 | { |
709 | AddExtendedItemType(Index: i); |
710 | } |
711 | } |
712 | |
713 | CSnapshotItem *CSnapshotBuilder::GetItem(int Index) |
714 | { |
715 | return (CSnapshotItem *)&(m_aData[m_aOffsets[Index]]); |
716 | } |
717 | |
718 | int *CSnapshotBuilder::GetItemData(int Key) |
719 | { |
720 | for(int i = 0; i < m_NumItems; i++) |
721 | { |
722 | if(GetItem(Index: i)->Key() == Key) |
723 | return GetItem(Index: i)->Data(); |
724 | } |
725 | return nullptr; |
726 | } |
727 | |
728 | int CSnapshotBuilder::Finish(void *pSnapData) |
729 | { |
730 | // flatten and make the snapshot |
731 | CSnapshot *pSnap = (CSnapshot *)pSnapData; |
732 | pSnap->m_DataSize = m_DataSize; |
733 | pSnap->m_NumItems = m_NumItems; |
734 | mem_copy(dest: pSnap->Offsets(), source: m_aOffsets, size: pSnap->OffsetSize()); |
735 | mem_copy(dest: pSnap->DataStart(), source: m_aData, size: m_DataSize); |
736 | return pSnap->TotalSize(); |
737 | } |
738 | |
739 | int CSnapshotBuilder::GetTypeFromIndex(int Index) const |
740 | { |
741 | return CSnapshot::MAX_TYPE - Index; |
742 | } |
743 | |
744 | void CSnapshotBuilder::AddExtendedItemType(int Index) |
745 | { |
746 | dbg_assert(0 <= Index && Index < m_NumExtendedItemTypes, "index out of range" ); |
747 | int TypeId = m_aExtendedItemTypes[Index]; |
748 | CUuid Uuid = g_UuidManager.GetUuid(Id: TypeId); |
749 | int *pUuidItem = (int *)NewItem(Type: 0, Id: GetTypeFromIndex(Index), Size: sizeof(Uuid)); // NETOBJTYPE_EX |
750 | if(pUuidItem) |
751 | { |
752 | for(size_t i = 0; i < sizeof(CUuid) / sizeof(int32_t); i++) |
753 | pUuidItem[i] = bytes_be_to_uint(bytes: &Uuid.m_aData[i * sizeof(int32_t)]); |
754 | } |
755 | } |
756 | |
757 | int CSnapshotBuilder::GetExtendedItemTypeIndex(int TypeId) |
758 | { |
759 | for(int i = 0; i < m_NumExtendedItemTypes; i++) |
760 | { |
761 | if(m_aExtendedItemTypes[i] == TypeId) |
762 | { |
763 | return i; |
764 | } |
765 | } |
766 | dbg_assert(m_NumExtendedItemTypes < MAX_EXTENDED_ITEM_TYPES, "too many extended item types" ); |
767 | int Index = m_NumExtendedItemTypes; |
768 | m_NumExtendedItemTypes++; |
769 | m_aExtendedItemTypes[Index] = TypeId; |
770 | AddExtendedItemType(Index); |
771 | return Index; |
772 | } |
773 | |
774 | void *CSnapshotBuilder::NewItem(int Type, int Id, int Size) |
775 | { |
776 | if(Id == -1) |
777 | { |
778 | return nullptr; |
779 | } |
780 | |
781 | if(m_DataSize + sizeof(CSnapshotItem) + Size >= CSnapshot::MAX_SIZE || |
782 | m_NumItems + 1 >= CSnapshot::MAX_ITEMS) |
783 | { |
784 | dbg_assert(m_DataSize < CSnapshot::MAX_SIZE, "too much data" ); |
785 | dbg_assert(m_NumItems < CSnapshot::MAX_ITEMS, "too many items" ); |
786 | return nullptr; |
787 | } |
788 | |
789 | bool Extended = false; |
790 | if(Type >= OFFSET_UUID) |
791 | { |
792 | Extended = true; |
793 | Type = GetTypeFromIndex(Index: GetExtendedItemTypeIndex(TypeId: Type)); |
794 | } |
795 | |
796 | CSnapshotItem *pObj = (CSnapshotItem *)(m_aData + m_DataSize); |
797 | |
798 | if(m_Sixup && !Extended) |
799 | { |
800 | if(Type >= 0) |
801 | Type = Obj_SixToSeven(a: Type); |
802 | else |
803 | Type *= -1; |
804 | |
805 | if(Type < 0) |
806 | return pObj; |
807 | } |
808 | else if(Type < 0) |
809 | return nullptr; |
810 | |
811 | mem_zero(block: pObj, size: sizeof(CSnapshotItem) + Size); |
812 | pObj->m_TypeAndId = (Type << 16) | Id; |
813 | m_aOffsets[m_NumItems] = m_DataSize; |
814 | m_DataSize += sizeof(CSnapshotItem) + Size; |
815 | m_NumItems++; |
816 | |
817 | return pObj->Data(); |
818 | } |
819 | |