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