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
17const CSnapshotItem *CSnapshot::GetItem(int Index) const
18{
19 return (const CSnapshotItem *)(DataStart() + Offsets()[Index]);
20}
21
22const CSnapshot CSnapshot::ms_EmptySnapshot;
23
24int 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
31int CSnapshot::GetItemType(int Index) const
32{
33 int InternalType = GetItem(Index)->Type();
34 return GetExternalItemType(InternalType);
35}
36
37int 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
57int 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
68const 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
101unsigned 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
116void 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
129bool 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
151enum
152{
153 HASHLIST_SIZE = 256,
154 HASHLIST_BUCKET_SIZE = 64,
155};
156
157struct CItemList
158{
159 int m_Num;
160 int m_aKeys[HASHLIST_BUCKET_SIZE];
161 int m_aIndex[HASHLIST_BUCKET_SIZE];
162};
163
164inline 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
173static 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
191static 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
203int 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
220void 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
243CSnapshotDelta::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
251CSnapshotDelta::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
259void 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
266const CSnapshotDelta::CData *CSnapshotDelta::EmptyDelta() const
267{
268 return &m_Empty;
269}
270
271// TODO: OPT: this should be made much faster
272int 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
355int 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 *pDumpHeader = (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
487int 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
591void CSnapshotStorage::Init()
592{
593 m_pFirst = nullptr;
594 m_pLast = nullptr;
595}
596
597void 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
610void 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
637void 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
672int 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
696CSnapshotBuilder::CSnapshotBuilder()
697{
698 m_NumExtendedItemTypes = 0;
699}
700
701void 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
713CSnapshotItem *CSnapshotBuilder::GetItem(int Index)
714{
715 return (CSnapshotItem *)&(m_aData[m_aOffsets[Index]]);
716}
717
718int *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
728int 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
739int CSnapshotBuilder::GetTypeFromIndex(int Index) const
740{
741 return CSnapshot::MAX_TYPE - Index;
742}
743
744void 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
757int 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
774void *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