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