diff options
Diffstat (limited to 'src/engine/e_snapshot.cpp')
| -rw-r--r-- | src/engine/e_snapshot.cpp | 571 |
1 files changed, 571 insertions, 0 deletions
diff --git a/src/engine/e_snapshot.cpp b/src/engine/e_snapshot.cpp new file mode 100644 index 00000000..65487665 --- /dev/null +++ b/src/engine/e_snapshot.cpp @@ -0,0 +1,571 @@ +/* copyright (c) 2007 magnus auvinen, see licence.txt for more info */ +#include <stdlib.h> +#include "e_snapshot.h" +#include "e_engine.h" +#include "e_compression.h" +#include "e_common_interface.h" + + +/* TODO: strange arbitrary number */ +static short item_sizes[64] = {0}; + +void snap_set_staticsize(int itemtype, int size) +{ + item_sizes[itemtype] = size; +} + +CSnapshotItem *CSnapshot::GetItem(int Index) +{ + return (CSnapshotItem *)(DataStart() + Offsets()[Index]); +} + +int CSnapshot::GetItemSize(int Index) +{ + if(Index == m_NumItems-1) + return (m_DataSize - Offsets()[Index]) - sizeof(CSnapshotItem); + return (Offsets()[Index+1] - Offsets()[Index]) - sizeof(CSnapshotItem); +} + +int CSnapshot::GetItemIndex(int Key) +{ + /* TODO: OPT: this should not be a linear search. very bad */ + for(int i = 0; i < m_NumItems; i++) + { + if(GetItem(i)->Key() == Key) + return i; + } + return -1; +} + +// TODO: clean up this +typedef struct +{ + int num; + int keys[64]; + int index[64]; +} ITEMLIST; + +static ITEMLIST sorted[256]; + +int CSnapshot::GenerateHash() +{ + for(int i = 0; i < 256; i++) + sorted[i].num = 0; + + for(int i = 0; i < m_NumItems; i++) + { + int Key = GetItem(i)->Key(); + int HashID = ((Key>>8)&0xf0) | (Key&0xf); + if(sorted[HashID].num != 64) + { + sorted[HashID].index[sorted[HashID].num] = i; + sorted[HashID].keys[sorted[HashID].num] = Key; + sorted[HashID].num++; + } + } + return 0; +} + +int CSnapshot::GetItemIndexHashed(int Key) +{ + int HashID = ((Key>>8)&0xf0) | (Key&0xf); + for(int i = 0; i < sorted[HashID].num; i++) + { + if(sorted[HashID].keys[i] == Key) + return sorted[HashID].index[i]; + } + + return -1; +} + + + +static const int MAX_ITEMS = 512; +static CSnapshotDelta empty = {0,0,0,{0}}; + +CSnapshotDelta *CSnapshot::EmptyDelta() +{ + return ∅ +} + +int CSnapshot::Crc() +{ + int crc = 0; + + for(int i = 0; i < m_NumItems; i++) + { + CSnapshotItem *pItem = GetItem(i); + int Size = GetItemSize(i); + + for(int b = 0; b < Size/4; b++) + crc += pItem->Data()[b]; + } + return crc; +} + +void CSnapshot::DebugDump() +{ + dbg_msg("snapshot", "data_size=%d num_items=%d", m_DataSize, m_NumItems); + for(int i = 0; i < m_NumItems; i++) + { + CSnapshotItem *pItem = GetItem(i); + int Size = GetItemSize(i); + dbg_msg("snapshot", "\ttype=%d id=%d", pItem->Type(), pItem->ID()); + for(int b = 0; b < Size/4; b++) + dbg_msg("snapshot", "\t\t%3d %12d\t%08x", b, pItem->Data()[b], pItem->Data()[b]); + } +} + + +// TODO: remove these +int snapshot_data_rate[0xffff] = {0}; +int snapshot_data_updates[0xffff] = {0}; +static int snapshot_current = 0; + +static int diff_item(int *past, int *current, int *out, int size) +{ + int needed = 0; + while(size) + { + *out = *current-*past; + needed |= *out; + out++; + past++; + current++; + size--; + } + + return needed; +} + +static void undiff_item(int *past, int *diff, int *out, int size) +{ + while(size) + { + *out = *past+*diff; + + if(*diff == 0) + snapshot_data_rate[snapshot_current] += 1; + else + { + unsigned char buf[16]; + unsigned char *end = vint_pack(buf, *diff); + snapshot_data_rate[snapshot_current] += (int)(end - (unsigned char*)buf) * 8; + } + + out++; + past++; + diff++; + size--; + } +} + + +/* TODO: OPT: this should be made much faster */ +int CSnapshot::CreateDelta(CSnapshot *from, CSnapshot *to, void *dstdata) +{ + static PERFORMACE_INFO hash_scope = {"hash", 0}; + CSnapshotDelta *delta = (CSnapshotDelta *)dstdata; + int *data = (int *)delta->m_pData; + int i, itemsize, pastindex; + CSnapshotItem *pFromItem; + CSnapshotItem *pCurItem; + CSnapshotItem *pPastItem; + int count = 0; + int size_count = 0; + + delta->m_NumDeletedItems = 0; + delta->m_NumUpdateItems = 0; + delta->m_NumTempItems = 0; + + perf_start(&hash_scope); + to->GenerateHash(); + perf_end(); + + /* pack deleted stuff */ + { + static PERFORMACE_INFO scope = {"delete", 0}; + perf_start(&scope); + + for(i = 0; i < from->m_NumItems; i++) + { + pFromItem = from->GetItem(i); + if(to->GetItemIndexHashed(pFromItem->Key()) == -1) + { + /* deleted */ + delta->m_NumDeletedItems++; + *data = pFromItem->Key(); + data++; + } + } + + perf_end(); + } + + perf_start(&hash_scope); + from->GenerateHash(); + perf_end(); + + /* pack updated stuff */ + { + static PERFORMACE_INFO scope = {"update", 0}; + int pastindecies[1024]; + perf_start(&scope); + + /* fetch previous indices */ + /* we do this as a separate pass because it helps the cache */ + { + static PERFORMACE_INFO scope = {"find", 0}; + perf_start(&scope); + for(i = 0; i < to->m_NumItems; i++) + { + pCurItem = to->GetItem(i); /* O(1) .. O(n) */ + pastindecies[i] = from->GetItemIndexHashed(pCurItem->Key()); /* O(n) .. O(n^n)*/ + } + perf_end(); + } + + for(i = 0; i < to->m_NumItems; i++) + { + /* do delta */ + itemsize = to->GetItemSize(i); /* O(1) .. O(n) */ + pCurItem = to->GetItem(i); /* O(1) .. O(n) */ + pastindex = pastindecies[i]; + + if(pastindex != -1) + { + static PERFORMACE_INFO scope = {"diff", 0}; + int *item_data_dst = data+3; + perf_start(&scope); + + pPastItem = from->GetItem(pastindex); + + if(item_sizes[pCurItem->Type()]) + item_data_dst = data+2; + + if(diff_item((int*)pPastItem->Data(), (int*)pCurItem->Data(), item_data_dst, itemsize/4)) + { + + *data++ = pCurItem->Type(); + *data++ = pCurItem->ID(); + if(!item_sizes[pCurItem->Type()]) + *data++ = itemsize/4; + data += itemsize/4; + delta->m_NumUpdateItems++; + } + perf_end(); + } + else + { + static PERFORMACE_INFO scope = {"copy", 0}; + perf_start(&scope); + + *data++ = pCurItem->Type(); + *data++ = pCurItem->ID(); + if(!item_sizes[pCurItem->Type()]) + *data++ = itemsize/4; + + mem_copy(data, pCurItem->Data(), itemsize); + size_count += itemsize; + data += itemsize/4; + delta->m_NumUpdateItems++; + count++; + + perf_end(); + } + } + + perf_end(); + } + + if(0) + { + dbg_msg("snapshot", "%d %d %d", + delta->m_NumDeletedItems, + delta->m_NumUpdateItems, + delta->m_NumTempItems); + } + + /* + // TODO: pack temp stuff + + // finish + //mem_copy(delta->offsets, deleted, delta->num_deleted_items*sizeof(int)); + //mem_copy(&(delta->offsets[delta->num_deleted_items]), update, delta->num_update_items*sizeof(int)); + //mem_copy(&(delta->offsets[delta->num_deleted_items+delta->num_update_items]), temp, delta->num_temp_items*sizeof(int)); + //mem_copy(delta->data_start(), data, data_size); + //delta->data_size = data_size; + * */ + + if(!delta->m_NumDeletedItems && !delta->m_NumUpdateItems && !delta->m_NumTempItems) + return 0; + + return (int)((char*)data-(char*)dstdata); +} + +static int range_check(void *end, void *ptr, int size) +{ + if((const char *)ptr + size > (const char *)end) + return -1; + return 0; +} + +int CSnapshot::UnpackDelta(CSnapshot *from, CSnapshot *to, void *srcdata, int data_size) +{ + CSnapshotBuilder builder; + CSnapshotDelta *delta = (CSnapshotDelta *)srcdata; + int *data = (int *)delta->m_pData; + int *end = (int *)(((char *)srcdata + data_size)); + + CSnapshotItem *fromitem; + int i, d, keep, itemsize; + int *deleted; + int id, type, key; + int fromindex; + int *newdata; + + builder.Init(); + + /* unpack deleted stuff */ + deleted = data; + data += delta->m_NumDeletedItems; + if(data > end) + return -1; + + /* copy all non deleted stuff */ + for(i = 0; i < from->m_NumItems; i++) + { + /* dbg_assert(0, "fail!"); */ + fromitem = from->GetItem(i); + itemsize = from->GetItemSize(i); + keep = 1; + for(d = 0; d < delta->m_NumDeletedItems; d++) + { + if(deleted[d] == fromitem->Key()) + { + keep = 0; + break; + } + } + + if(keep) + { + /* keep it */ + mem_copy( + builder.NewItem(fromitem->Type(), fromitem->ID(), itemsize), + fromitem->Data(), itemsize); + } + } + + /* unpack updated stuff */ + for(i = 0; i < delta->m_NumUpdateItems; i++) + { + if(data+2 > end) + return -1; + + type = *data++; + id = *data++; + if(item_sizes[type]) + itemsize = item_sizes[type]; + else + { + if(data+1 > end) + return -2; + itemsize = (*data++) * 4; + } + snapshot_current = type; + + if(range_check(end, data, itemsize) || itemsize < 0) return -3; + + key = (type<<16)|id; + + /* create the item if needed */ + newdata = builder.GetItemData(key); + if(!newdata) + newdata = (int *)builder.NewItem(key>>16, key&0xffff, itemsize); + + /*if(range_check(end, newdata, itemsize)) return -4;*/ + + fromindex = from->GetItemIndex(key); + if(fromindex != -1) + { + /* we got an update so we need to apply the diff */ + undiff_item((int *)from->GetItem(fromindex)->Data(), data, newdata, itemsize/4); + snapshot_data_updates[snapshot_current]++; + } + else /* no previous, just copy the data */ + { + mem_copy(newdata, data, itemsize); + snapshot_data_rate[snapshot_current] += itemsize*8; + snapshot_data_updates[snapshot_current]++; + } + + data += itemsize/4; + } + + /* finish up */ + return builder.Finish(to); +} + +/* CSnapshotStorage */ + +void CSnapshotStorage::Init() +{ + m_pFirst = 0; + m_pLast = 0; +} + +void CSnapshotStorage::PurgeAll() +{ + CHolder *pHolder = m_pFirst; + CHolder *pNext; + + while(pHolder) + { + pNext = pHolder->m_pNext; + mem_free(pHolder); + pHolder = pNext; + } + + /* no more snapshots in storage */ + m_pFirst = 0; + m_pLast = 0; +} + +void CSnapshotStorage::PurgeUntil(int Tick) +{ + CHolder *pHolder = m_pFirst; + CHolder *pNext; + + while(pHolder) + { + pNext = pHolder->m_pNext; + if(pHolder->m_Tick >= Tick) + return; /* no more to remove */ + mem_free(pHolder); + + /* did we come to the end of the list? */ + if (!pNext) + break; + + m_pFirst = pNext; + pNext->m_pPrev = 0x0; + + pHolder = pNext; + } + + /* no more snapshots in storage */ + m_pFirst = 0; + m_pLast = 0; +} + +void CSnapshotStorage::Add(int Tick, int64 Tagtime, int DataSize, void *pData, int CreateAlt) +{ + /* allocate memory for holder + snapshot_data */ + int TotalSize = sizeof(CHolder)+DataSize; + + if(CreateAlt) + TotalSize += DataSize; + + CHolder *pHolder = (CHolder *)mem_alloc(TotalSize, 1); + + /* set data */ + pHolder->m_Tick = Tick; + pHolder->m_Tagtime = Tagtime; + pHolder->m_SnapSize = DataSize; + pHolder->m_pSnap = (CSnapshot*)(pHolder+1); + mem_copy(pHolder->m_pSnap, pData, DataSize); + + if(CreateAlt) /* create alternative if wanted */ + { + pHolder->m_pAltSnap = (CSnapshot*)(((char *)pHolder->m_pSnap) + DataSize); + mem_copy(pHolder->m_pAltSnap, pData, DataSize); + } + else + pHolder->m_pAltSnap = 0; + + + /* link */ + pHolder->m_pNext = 0; + pHolder->m_pPrev = m_pLast; + if(m_pLast) + m_pLast->m_pNext = pHolder; + else + m_pFirst = pHolder; + m_pLast = pHolder; +} + +int CSnapshotStorage::Get(int Tick, int64 *pTagtime, CSnapshot **ppData, CSnapshot **ppAltData) +{ + CHolder *pHolder = m_pFirst; + + while(pHolder) + { + if(pHolder->m_Tick == Tick) + { + if(pTagtime) + *pTagtime = pHolder->m_Tagtime; + if(ppData) + *ppData = pHolder->m_pSnap; + if(ppAltData) + *ppData = pHolder->m_pAltSnap; + return pHolder->m_SnapSize; + } + + pHolder = pHolder->m_pNext; + } + + return -1; +} + +/* CSnapshotBuilder */ + +void CSnapshotBuilder::Init() +{ + m_DataSize = 0; + m_NumItems = 0; +} + +CSnapshotItem *CSnapshotBuilder::GetItem(int Index) +{ + return (CSnapshotItem *)&(m_aData[m_aOffsets[Index]]); +} + +int *CSnapshotBuilder::GetItemData(int key) +{ + int i; + for(i = 0; i < m_NumItems; i++) + { + if(GetItem(i)->Key() == key) + return (int *)GetItem(i)->Data(); + } + return 0; +} + +int CSnapshotBuilder::Finish(void *snapdata) +{ + /* flattern and make the snapshot */ + CSnapshot *pSnap = (CSnapshot *)snapdata; + int OffsetSize = sizeof(int)*m_NumItems; + pSnap->m_DataSize = m_DataSize; + pSnap->m_NumItems = m_NumItems; + mem_copy(pSnap->Offsets(), m_aOffsets, OffsetSize); + mem_copy(pSnap->DataStart(), m_aData, m_DataSize); + return sizeof(CSnapshot) + OffsetSize + m_DataSize; +} + +void *CSnapshotBuilder::NewItem(int Type, int ID, int Size) +{ + CSnapshotItem *pObj = (CSnapshotItem *)(m_aData + m_DataSize); + + mem_zero(pObj, sizeof(CSnapshotItem) + Size); + pObj->m_TypeAndID = (Type<<16)|ID; + m_aOffsets[m_NumItems] = m_DataSize; + m_DataSize += sizeof(CSnapshotItem) + Size; + m_NumItems++; + + dbg_assert(m_DataSize < CSnapshot::MAX_SIZE, "too much data"); + dbg_assert(m_NumItems < MAX_ITEMS, "too many items"); + + return pObj->Data(); +} |