JHHM

dedit

a tool for Teeworlds demo file shenanigens
git clone https://jhhm.no/repos/dedit.git

dedit/src/merge.c

get raw file: merge.c

1/* This file is part of dedit - a tool for editing Teeworlds/DDNet demo files
2   Copyright (C) 2026 JHHM
3
4   Dedit is free software: you can redistribute it and/or modify
5   it under the terms of the GNU General Public License as published by
6   the Free Software Foundation, either version 3 of the License, or
7   (at your option) any later version.
8
9   Dedit is distributed in the hope that it will be useful,
10   but WITHOUT ANY WARRANTY; without even the implied warranty of
11   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12   GNU General Public License for more details.
13
14   You should have received a copy of the GNU General Public License
15   along with dedit.  If not, see <https://www.gnu.org/licenses/>. */
16
17#define _POSIX_C_SOURCE 200112L
18
19#include "merge.h"
20#include "demo.h"
21#include "pack.h"
22#include "snap.h"
23
24#include <stdio.h>
25#include <stdlib.h>
26#include <string.h>
27
28#define TICK_SPEED 50
29#define KEYFRAME_INTERVAL (TICK_SPEED * 5)
30#define MERGE_MAX_STALE_TICKS TICK_SPEED
31#define MAX_TIMELINE_MARKERS 64
32#define OFFSET_UUID_TYPE 0x4000
33#define ITEMTYPE_EX 0
34
35typedef enum
36{
37    ITEMSKIP = 0,      // never merged
38    ITEMWORLD = 1,     // merged if the primary demo does not have it
39    ITEMEVENT = 2,     // merged if the primary demo does not have it, and it was recorded at the tick
40    ITEMPLAYERINFO = 3 // merged if the primary demo does not have it, and is not marked as local
41} itemkind;
42
43static const itemkind itemkinds06[] = {
44    ITEMSKIP,       // id  0, ex
45    ITEMSKIP,       // id  1, player input
46    ITEMWORLD,      // id  2, projectile
47    ITEMWORLD,      // id  3, laser
48    ITEMWORLD,      // id  4, pickup
49    ITEMWORLD,      // id  5, flag
50    ITEMSKIP,       // id  6, game info
51    ITEMSKIP,       // id  7, game data
52    ITEMSKIP,       // id  8, character core
53    ITEMWORLD,      // id  9, character
54    ITEMPLAYERINFO, // id 10, player info
55    ITEMWORLD,      // id 11, client info
56    ITEMSKIP,       // id 12, spectator info
57    ITEMEVENT,      // id 13, common
58    ITEMEVENT,      // id 14, explosion
59    ITEMEVENT,      // id 15, spawn
60    ITEMEVENT,      // id 16, hammer hit
61    ITEMEVENT,      // id 17, death
62    ITEMEVENT,      // id 18, sound global
63    ITEMEVENT,      // id 19, sound world
64    ITEMEVENT       // id 20, damage indicator
65};
66
67typedef struct
68{
69    unsigned int uuid[4];
70    itemkind kind;
71} extype;
72
73static const extype extypes[] = {
74    {{0x76ce455b, 0xf9eb3a48, 0xadd7e04b, 0x941d045c}, ITEMWORLD}, // character@netobj
75    {{0x22ca938d, 0x13803e2b, 0x9e7bd255, 0x8ea6be11}, ITEMWORLD}, // player@netobj
76    {{0x0e6db85c, 0x2b61386f, 0xbbf2d0d0, 0x471b9272}, ITEMWORLD}, // projectile@netobj
77    {{0x6550fbce, 0xf3173b31, 0x8ffed2b3, 0x7f3ab40e}, ITEMWORLD}, // ddnet-projectile@netobj
78    {{0x29de68a2, 0x692831b8, 0x8360a230, 0x7e0d844f}, ITEMWORLD}, // laser@netobj
79    {{0xea5e4a51, 0x58fb3684, 0x96e4e0d2, 0x67f4ca65}, ITEMWORLD}, // pickup@netobj
80    {{0x2de9aec3, 0x32e43986, 0x8f7ee745, 0x9da7f535}, ITEMWORLD}, // entity-ex@netobj
81    {{0x1fd35746, 0x6263358c, 0xb4d66ef6, 0x0e0efaaa}, ITEMEVENT}, // birthday@netevent
82    {{0x68bf8939, 0xef553878, 0x90821352, 0x7eb0a597}, ITEMEVENT}, // finish@netevent
83    {{0x54ecad2e, 0xbfad3be5, 0x8903621b, 0xa052458e}, ITEMEVENT}, // map-sound-world@netevent
84};
85
86/* demowriter struct, builds demo chunks like the demo recorder */
87typedef struct
88{
89    demodata data;
90    int chunkcap;
91    unsigned char version;
92    int firsttick;
93    int lasttickmarker;
94    int lastkeyframe;
95    demosnap lastsnap;
96} demowriter;
97
98/* Returns how items with type in snap are merged */
99/* Extended item types are looked up by their uuid in snap */
100static itemkind getitemkind(const demosnap *snap, int type)
101{
102    if (type < (int)(sizeof(itemkinds06) / sizeof(itemkinds06[0])))
103        return itemkinds06[type];
104
105    if (type < OFFSET_UUID_TYPE)
106        return ITEMSKIP;
107
108    int index = snapfinditem(snap, ITEMTYPE_EX, type);
109    if (index == -1 || snap->items[index].numdata != 4)
110        return ITEMSKIP;
111
112    for (size_t i = 0; i < sizeof(extypes) / sizeof(extypes[0]); i++)
113    {
114        if (memcmp(snap->items[index].data, extypes[i].uuid, sizeof(extypes[i].uuid)) == 0)
115            return extypes[i].kind;
116    }
117    return ITEMSKIP;
118}
119
120/* Returns 1 if the extended item type has the same uuid in both snapshots, else 0 */
121static int sameextype(const demosnap *a, const demosnap *b, int type)
122{
123    int aindex = snapfinditem(a, ITEMTYPE_EX, type);
124    int bindex = snapfinditem(b, ITEMTYPE_EX, type);
125
126    if (aindex == -1 || bindex == -1)
127        return 0;
128
129    const demosnapitem *aitem = &a->items[aindex];
130    const demosnapitem *bitem = &b->items[bindex];
131
132    if (aitem->numdata != bitem->numdata)
133        return 0;
134
135    return memcmp(aitem->data, bitem->data, aitem->numdata * sizeof(int)) == 0;
136}
137
138/* Merges the snapshots of primary and secondary at tick into out */
139static int mergesnaps(const demostate *primary, const demostate *secondary, int tick, demosnap *out,
140                      char *fullwarned)
141{
142    const demosnap *psnap = &primary->snap;
143    int size = 2 * sizeof(int);
144
145    snapinit(out);
146
147    for (int i = 0; primary->hassnap && i < psnap->numitems; i++)
148    {
149        const demosnapitem *item = &psnap->items[i];
150
151        if (primary->tick != tick && getitemkind(psnap, item->type) == ITEMEVENT)
152            continue;
153
154        if (snapadditem(out, item->type, item->id, item->numdata, item->data) < 0)
155            return -1;
156        size += (2 + item->numdata) * sizeof(int);
157    }
158
159    for (int i = 0; secondary && secondary->hassnap && i < secondary->snap.numitems; i++)
160    {
161        const demosnap *ssnap = &secondary->snap;
162        const demosnapitem *item = &ssnap->items[i];
163        itemkind kind = getitemkind(ssnap, item->type);
164        int itemsize = (2 + item->numdata) * sizeof(int);
165
166        if (kind == ITEMSKIP)
167            continue;
168
169        if (kind == ITEMEVENT && secondary->tick != tick)
170            continue;
171
172        if (item->type >= OFFSET_UUID_TYPE && !sameextype(psnap, ssnap, item->type))
173            continue;
174
175        if (snapfinditem(out, item->type, item->id) != -1)
176            continue;
177
178        if (out->numitems >= SNAP_MAX_ITEMS || size + itemsize > SNAP_MAX_SIZE)
179        {
180            if (!*fullwarned)
181                fprintf(stderr, "Warning: merged snapshot is full, some items are dropped\n");
182            *fullwarned = 1;
183            continue;
184        }
185
186        if (snapadditem(out, item->type, item->id, item->numdata, item->data) < 0)
187            return -1;
188        size += itemsize;
189
190        // there can only be one local player
191        if (kind == ITEMPLAYERINFO && item->numdata > 0)
192            out->items[out->numitems - 1].data[0] = 0;
193    }
194
195    return snapupdateoffsets(out);
196}
197
198/* writer */
199
200static void writerinit(demowriter *w, unsigned char version)
201{
202    w->data.numchunks = 0;
203    w->data.chunks = NULL;
204    w->chunkcap = 0;
205    w->version = version;
206    w->firsttick = -1;
207    w->lasttickmarker = -1;
208    w->lastkeyframe = -1;
209    snapinit(&w->lastsnap);
210}
211
212static void writerfree(demowriter *w)
213{
214    freedemodata(&w->data);
215    snapfree(&w->lastsnap);
216}
217
218static int writechunk(demowriter *w, demochunktype type, chunkdata data)
219{
220    if (w->data.numchunks >= w->chunkcap)
221    {
222        int chunkcap = w->chunkcap ? w->chunkcap * 2 : 1024;
223        demochunk *chunks = (demochunk *)realloc(w->data.chunks, chunkcap * sizeof(demochunk));
224        if (chunks == NULL)
225            return -1;
226        w->data.chunks = chunks;
227        w->chunkcap = chunkcap;
228    }
229
230    w->data.chunks[w->data.numchunks].type = type;
231    w->data.chunks[w->data.numchunks].data = data;
232    w->data.numchunks++;
233
234    return 1;
235}
236
237/*
238  Function is derived from DDNet code (DDNet License).
239  See NOTICES file for full license details.
240
241  https://github.com/ddnet/ddnet/blob/master/src/engine/shared/demo.cpp (CDemoRecorder::WriteTickMarker)
242*/
243static int writetickmarker(demowriter *w, int tick, char keyframe)
244{
245    int maxinline = (w->version >= 5) ? 0x1f : 0x3f;
246    demotick *t = (demotick *)malloc(sizeof(demotick));
247    chunkdata data;
248
249    if (t == NULL)
250        return -1;
251
252    t->keyframe = keyframe;
253    if (keyframe || w->lasttickmarker == -1 || tick <= w->lasttickmarker || tick - w->lasttickmarker > maxinline)
254    {
255        t->innline = 0;
256        t->delta = tick;
257    }
258    else
259    {
260        t->innline = 1;
261        t->delta = tick - w->lasttickmarker;
262    }
263
264    data.tick = t;
265    if (writechunk(w, DEMOTICK, data) < 0)
266    {
267        free(t);
268        return -1;
269    }
270
271    w->lasttickmarker = tick;
272    if (w->firsttick == -1)
273        w->firsttick = tick;
274
275    return 1;
276}
277
278/*
279  Function is derived from DDNet code (DDNet License).
280  See NOTICES file for full license details.
281
282  https://github.com/ddnet/ddnet/blob/master/src/engine/shared/demo.cpp (CDemoRecorder::RecordSnapshot)
283*/
284static int writesnapshot(demowriter *w, int tick, const demosnap *snap)
285{
286    demodelta delta = {0, 0, NULL, NULL};
287    char keyframe = (w->lastkeyframe == -1 || tick - w->lastkeyframe > KEYFRAME_INTERVAL);
288    int ret = 0;
289    chunkdata data;
290
291    if (!keyframe)
292    {
293        ret = snapcreatedelta(&w->lastsnap, snap, &delta);
294        // an item changed size, only a full snapshot can store that
295        if (ret == -2)
296            keyframe = 1;
297        else if (ret < 0)
298            return -1;
299    }
300
301    if (writetickmarker(w, tick, keyframe) < 0)
302    {
303        deltafree(&delta);
304        return -1;
305    }
306
307    if (keyframe)
308    {
309        demosnap *full = (demosnap *)malloc(sizeof(demosnap));
310        if (full == NULL)
311            return -1;
312
313        if (snapcopy(full, snap) < 0)
314        {
315            free(full);
316            return -1;
317        }
318
319        data.snap = full;
320        if (writechunk(w, DEMOSNAP, data) < 0)
321        {
322            snapfree(full);
323            free(full);
324            return -1;
325        }
326        w->lastkeyframe = tick;
327    }
328    else if (ret > 0)
329    {
330        demodelta *d = (demodelta *)malloc(sizeof(demodelta));
331        if (d == NULL)
332        {
333            deltafree(&delta);
334            return -1;
335        }
336
337        *d = delta;
338        data.delta = d;
339        if (writechunk(w, DEMODELTA, data) < 0)
340        {
341            deltafree(d);
342            free(d);
343            return -1;
344        }
345    }
346    else
347    {
348        // snapshot is unchanged, only the tick marker is written
349        deltafree(&delta);
350        return 1;
351    }
352
353    snapfree(&w->lastsnap);
354    return snapcopy(&w->lastsnap, snap);
355}
356
357static int writemessage(demowriter *w, const demomessage *message)
358{
359    demomessage *copy = (demomessage *)malloc(sizeof(demomessage));
360    chunkdata data;
361
362    if (copy == NULL)
363        return -1;
364
365    copy->datasize = message->datasize;
366    copy->data = (char *)malloc(message->datasize > 0 ? message->datasize : 1);
367    if (copy->data == NULL)
368    {
369        free(copy);
370        return -1;
371    }
372    memcpy(copy->data, message->data, message->datasize);
373
374    data.message = copy;
375    if (writechunk(w, DEMOMESSAGE, data) < 0)
376    {
377        free(copy->data);
378        free(copy);
379        return -1;
380    }
381
382    return 1;
383}
384
385/* Writes the chunks of the current tick of state, with snap as the snapshot of the tick */
386static int writetick(demowriter *w, const demostate *state, int tick, const demosnap *snap)
387{
388    demodata *data = &state->demo->data;
389
390    for (int i = state->firstchunk; i < state->chunkidx; i++)
391    {
392        demochunk *chunk = &data->chunks[i];
393        if (chunk->type == DEMOTICK)
394        {
395            if (writesnapshot(w, tick, snap) < 0)
396                return -1;
397        }
398        else if (chunk->type == DEMOMESSAGE)
399        {
400            if (writemessage(w, chunk->data.message) < 0)
401                return -1;
402        }
403    }
404
405    return 1;
406}
407
408static void mergetimelines(demotimeline *base, const demotimeline *other)
409{
410    const demotimeline *timelines[2] = {base, other};
411    int markers[2 * MAX_TIMELINE_MARKERS];
412    int nummarkers = 0;
413
414    for (int t = 0; t < 2; t++)
415    {
416        const unsigned char *data = (const unsigned char *)timelines[t]->data;
417        int num = frombigendian(data);
418
419        if (num < 0)
420            num = 0;
421        if (num > MAX_TIMELINE_MARKERS)
422            num = MAX_TIMELINE_MARKERS;
423
424        for (int i = 0; i < num; i++)
425        {
426            int marker = frombigendian(data + 4 + 4 * i);
427            int pos = nummarkers;
428
429            // insertion sort, skipping duplicates
430            while (pos > 0 && markers[pos - 1] > marker)
431                pos--;
432            if (pos > 0 && markers[pos - 1] == marker)
433                continue;
434
435            memmove(&markers[pos + 1], &markers[pos], (nummarkers - pos) * sizeof(int));
436            markers[pos] = marker;
437            nummarkers++;
438        }
439    }
440
441    if (nummarkers > MAX_TIMELINE_MARKERS)
442        nummarkers = MAX_TIMELINE_MARKERS;
443
444    unsigned char *data = (unsigned char *)base->data;
445    memset(data, 0, DEMO_TIMELINE_LENGTH);
446    tobigendian(nummarkers, data);
447    for (int i = 0; i < nummarkers; i++)
448        tobigendian(markers[i], data + 4 + 4 * i);
449}
450
451int mergedemo(demo *base, demo *other)
452{
453    demostate a, b;
454    demowriter w;
455    char fullwarned = 0;
456    int ret = 1;
457
458    if (strncmp(base->header.mapname, other->header.mapname, sizeof(base->header.mapname)) != 0 ||
459        base->header.mapcrc != other->header.mapcrc)
460        fprintf(stderr, "Warning: demos have different maps\n");
461
462    if (strncmp(base->header.netversion, other->header.netversion, sizeof(base->header.netversion)) != 0)
463        fprintf(stderr, "Warning: demos have different network versions\n");
464
465    demostateinit(&a, base);
466    demostateinit(&b, other);
467
468    if (a.firsttick != -1 && b.firsttick != -1 && (a.lasttick < b.firsttick || b.lasttick < a.firsttick))
469        fprintf(stderr, "Warning: demos do not overlap in time, are they recorded on the same server?\n");
470
471    writerinit(&w, base->header.version);
472
473    while (1)
474    {
475        int atick = demostatepeektick(&a);
476        int btick = demostatepeektick(&b);
477        char anext = 0, bnext = 0, primarynext;
478        demostate *primary, *secondary;
479        demosnap merged;
480        int tick;
481
482        if (atick == -1 && btick == -1)
483            break;
484
485        if (atick == -1)
486            tick = btick;
487        else if (btick == -1)
488            tick = atick;
489        else
490            tick = (atick < btick) ? atick : btick;
491
492        // advance demos that have the tick
493        if (atick == tick)
494        {
495            if (demostatenext(&a) < 0)
496            {
497                ret = -2;
498                break;
499            }
500            anext = 1;
501        }
502        if (btick == tick)
503        {
504            if (demostatenext(&b) < 0)
505            {
506                ret = -2;
507                break;
508            }
509            bnext = 1;
510        }
511
512        if (a.tick != -1 && tick <= a.lasttick)
513        {
514            primary = &a;
515            secondary = &b;
516            primarynext = anext;
517        }
518        else
519        {
520            primary = &b;
521            secondary = &a;
522            primarynext = bnext;
523        }
524
525        // only use secondary while it is recording and has recent data
526
527        if (secondary->tick == -1 || tick > secondary->lasttick || tick - secondary->tick > MERGE_MAX_STALE_TICKS)
528            secondary = NULL;
529
530        if (mergesnaps(primary, secondary, tick, &merged, &fullwarned) < 0)
531        {
532            snapfree(&merged);
533            ret = -3;
534            break;
535        }
536
537        if (primarynext)
538            ret = writetick(&w, primary, tick, &merged);
539        else
540            ret = writesnapshot(&w, tick, &merged);
541
542        snapfree(&merged);
543        if (ret < 0)
544        {
545            ret = -3;
546            break;
547        }
548    }
549
550    demostatefree(&a);
551    demostatefree(&b);
552
553    if (ret < 0)
554    {
555        writerfree(&w);
556        return ret;
557    }
558
559    if (b.firsttick != -1 && (a.firsttick == -1 || b.firsttick < a.firsttick))
560        memcpy(base->header.timestamp, other->header.timestamp, sizeof(base->header.timestamp));
561
562    if (w.firsttick != -1)
563        base->header.length = (w.lasttickmarker - w.firsttick) / TICK_SPEED;
564
565    mergetimelines(&base->timeline, &other->timeline);
566
567    freedemodata(&base->data);
568    base->data = w.data;
569    snapfree(&w.lastsnap);
570
571    return 1;
572}