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}