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