HKCERT CTF 2023 Postmortem (III): The Remaining Challenges

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <unistd.h>
#include <ws.h>
#include "maze_runner.pb-c.h"

#define GRID_COLS 55
#define GRID_ROWS 55
#define COORD(x, y) (GRID_COLS * y + x)
#define DIST2(x, y) ((x) * (x) + (y) * (y))
#define TILESET_SIZE 12
#define ITEM_COUNT 4
#define MAX_CLIENTS 1024

typedef struct GameTile GameTile;
typedef struct Player Player;
typedef struct Monster Monster;

typedef struct Context
{
    GameTile **tileset;
    GameTile **grid;
    Player *player;
    Monster *monster;
    int *inventory;
    char *message;
    ws_cli_conn_t *client;
} Context;

typedef struct Player
{
    int x;
    int y;
    int facing;
    int health;
} Player;

typedef struct Monster
{
    int x;
    int y;
} Monster;

typedef struct GameTile
{
    int type;
    void (*on_enter)(Context *ctx, int x, int y);
    void (*on_interact)(Context *ctx, int x, int y);
    int is_walkable;
    int is_interactable;
} GameTile;

// ---

unsigned long long int GRID[] = {
    0, 0, 0, 2459530691549855744, 144680483117212162, 2450523355428823554, 2306443351725048354, 137975832616, 9007199793717280, 9042384163708960, 2450558539798685984, 153722729841951266, 2450523492867768866, 2345624797730, 2305843009215791104, 35321811050496, 536879136, 2450523492865671168, 153687544932999714, 2459565738516677154, 2305878202748379682, 2314885393377402912, 2314885530281582624, 2305843147189518368, 2450558676702994944, 2450523492867768834, 153687682908815906, 2305878193621565986, 35321813147648, 9042384163708928, 9007336695791648, 153687544930902562, 144680483115115010, 153687682906718722, 2305878194122793474, 2314885392842629152, 2305843009750573056, 2449958335265374208, 144680483115115010, 2459565876492509730, 144680346215129602, 9007337230565922, 538968064, 9007337230565376, 153685474722979872, 2459565875957735938, 2459530691583549986, 153722729841959426, 2314850345907396610, 9042383628935168, 2305878194122653728, 153722721216233504, 2450523492330897954, 2459565738516677154, 144715668026163714, 2314885530279477280, 2314885393379491872, 0, 2459530554110902272, 144715530048242178, 2459565875955638818, 9607679205057058, 2305878331563704352, 2314885392840532000, 0, 144715530585120768, 2450523354891944450, 2459565875955630626, 9044591812682274, 9007199254749216, 2314885530816356352, 2305843009213693952, 2459565738518774304, 153687544932991490, 2459565875955630626, 2305878339648365090, 2305878331026841600, 2314885530279485472, 2314885392840523776, 153687545467765250, 153687682906726946, 2459565875955630594, 2314885530850034178, 2305878331024736288, 2314885530816356384, 153157709678510080, 2450558539261936130, 153687682369856002, 144715667487195650, 35322350141954, 8192, 2314885530816356352, 2459563668847731234, 2459565876494606882, 5927337589569888802, 144680487954305634, 137438962178, 35184908967936, 2459000718894309408, 2459530683498897442, 144680346213032482, 144680345678250530, 144680346215121410, 2305843146652647458, 9007199254749216, 137977929760, 2459565739021967392, 144715667489292802, 144680346215121442, 2450523355428823586, 9007336693702656, 9007337232662528, 2105376, 144680345678127136, 153722867280912898, 2459530554144588290, 2315415366607708706, 2305878331563712544, 2314885530279485472, 32, 153722729839861792, 144680345678250498, 2459565875955638818, 9044591812682274, 2305843147191615520, 9007199793717248, 0, 153687682371944992, 2450523354889855522, 2459565876494598690, 2305878340187333154, 2305843146652655616, 2105376, 0, 153687682371953152, 2459565875957735970, 153722866744042018, 137474744866, 137977921536, 2305843009750573088, 35184911056928, 153687682906726946, 153687544930902562, 2459565738516677122, 2314850346444390914, 2314885530279477248, 2314885530816348192, 144150509886898208, 2450558539798807074, 2450523492330897922, 153722729302983170, 2305843146654745122, 9042383628935200, 2305878331563712512, 153685474725068832, 2459565739053548066, 144715668024066562, 144715530050339330, 9042384163700738, 9007336695791648, 2305878194122661888, 2459565730432032800, 2450523354889855490, 2450558677237760546, 153722729302991362, 9007337230565408, 2314885530281574432, 9007199791620128, 153722729271402528, 153722729302991362, 144715530048242210, 565157602402850, 2314885393377402880, 2105344, 35184911065088, 2450523424146063392, 144680345678250498, 144680483117203970, 3035428494472512002, 2314850346444267552, 2314850346446364672, 2314885393379500064, 2459530691585638443, 2459530692120420898, 2459565875957735970, 9160491554, 0, 0, 0, 0};

void on_default_enter(Context *ctx, int x, int y) {}

void on_default_interact(Context *ctx, int x, int y) {}

void on_key_1_interact(Context *ctx, int x, int y)
{
    char *message = malloc(20 + 1);
    strcpy(message, "You picked up a key.");
    ctx->message = message;

    ctx->inventory[0] += 1;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_key_2_interact(Context *ctx, int x, int y)
{
    char *message = malloc(20 + 1);
    strcpy(message, "You picked up a key.");
    ctx->message = message;

    ctx->inventory[1] += 1;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_key_3_interact(Context *ctx, int x, int y)
{
    char *message = malloc(20 + 1);
    strcpy(message, "You picked up a key.");
    ctx->message = message;

    ctx->inventory[2] += 1;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_key_4_interact(Context *ctx, int x, int y)
{
    char *message = malloc(20 + 1);
    strcpy(message, "You picked up a key.");
    ctx->message = message;

    ctx->inventory[3] += 1;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_gate_1_interact(Context *ctx, int x, int y)
{
    if (ctx->inventory[0] == 0)
    {
        char *message = malloc(32 + 1);
        strcpy(message, "You don't have the required key!");
        ctx->message = message;
        return;
    }
    else
    {
        char *message = malloc(22 + 1);
        strcpy(message, "You unlocked a gate.");
        ctx->message = message;
    }
    ctx->inventory[0]--;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_gate_2_interact(Context *ctx, int x, int y)
{
    if (ctx->inventory[1] == 0)
    {
        char *message = malloc(32 + 1);
        strcpy(message, "You don't have the required key!");
        ctx->message = message;
        return;
    }
    else
    {
        char *message = malloc(22 + 1);
        strcpy(message, "You unlocked a gate.");
        ctx->message = message;
    }
    ctx->inventory[1]--;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_gate_3_interact(Context *ctx, int x, int y)
{
    if (ctx->inventory[2] == 0)
    {
        char *message = malloc(32 + 1);
        strcpy(message, "You don't have the required key!");
        ctx->message = message;
        return;
    }
    else
    {
        char *message = malloc(22 + 1);
        strcpy(message, "You unlocked a gate.");
        ctx->message = message;
    }
    ctx->inventory[2]--;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_gate_4_interact(Context *ctx, int x, int y)
{
    if (ctx->inventory[3] == 0)
    {
        char *message = malloc(32 + 1);
        strcpy(message, "You don't have the required key!");
        ctx->message = message;
        return;
    }
    else
    {
        char *message = malloc(22 + 1);
        strcpy(message, "You unlocked a gate.");
        ctx->message = message;
    }
    ctx->inventory[3]--;
    ctx->grid[COORD(x, y)]->type = 2;
    ctx->grid[COORD(x, y)]->is_walkable = 1;
    ctx->grid[COORD(x, y)]->on_interact = on_default_interact;
    ctx->grid[COORD(x, y)]->is_interactable = 0;
}

void on_flag_interact(Context *ctx, int x, int y)
{
    FILE *fd = fopen("flag.txt", "r");
    char flag[128];
    char *message = malloc(256);

    fscanf(fd, "%s", flag);
    sprintf(message, "Congratulations! You got the flag: %s.\n", flag);
    ctx->message = message;
}

int walk(Context *ctx, int dx, int dy)
{
    int x1 = ctx->player->x, y1 = ctx->player->y;

    int x2 = x1 + dx, y2 = y1 + dy;

    if (!ctx->grid[COORD(x2, y2)]->is_walkable)
        return 1;
    if (ctx->monster->x == x2 && ctx->monster->y == y2)
        return 1;
    ctx->player->x += dx;
    ctx->player->y += dy;
    ctx->grid[COORD(x2, y2)]->on_enter(ctx, x2, y2);
    return 0;
}

int DXS[4] = {+0, +1, +0, -1};
int DYS[4] = {-1, +0, +1, +0};

int FAN_XXS[4] = {0, +1, 0, -1};
int FAN_XYS[4] = {+1, 0, -1, 0};
int FAN_YXS[4] = {-1, 0, +1, 0};
int FAN_YYS[4] = {0, +1, 0, -1};

Context *ctxs[MAX_CLIENTS];

void send_state_via_ws(Context *ctx)
{
    if (ctx == NULL)
        return;
    ws_cli_conn_t *client = ctx->client;

    int x = ctx->player->x;
    int y = ctx->player->y;

    int x2 = ctx->player->x + DXS[ctx->player->facing];
    int y2 = ctx->player->y + DYS[ctx->player->facing];

    Response res = RESPONSE__INIT;

    // grids
    Tile **grids = malloc(25 * sizeof(Tile *));
    int n_grids = 0;

    for (int i = 0; i < 5; i++)
    {
        for (int j = -i; j <= i; j++)
        {
            Tile *tile = malloc(sizeof(Tile));
            tile__init(tile);
            tile->offset_horizontal = i;
            tile->offset_vertical = j;

            int x = ctx->player->x + FAN_XXS[ctx->player->facing] * i + FAN_XYS[ctx->player->facing] * j;
            int y = ctx->player->y + FAN_YXS[ctx->player->facing] * i + FAN_YYS[ctx->player->facing] * j;

            int type;
            if (x < 0 || x >= GRID_COLS)
                type = 0;
            else if (y < 0 || y >= GRID_ROWS)
                type = 0;
            else
                type = ctx->grid[COORD(x, y)]->type;
            tile->type = type;
            grids[n_grids++] = tile;
        }
    }

    res.n_grids = n_grids;
    res.grids = grids;

    // entities
    Entity **entities = malloc(25 * sizeof(Entity *));
    int n_entities = 0;

    for (int i = 0; i < 5; i++)
    {
        for (int j = -i; j <= i; j++)
        {
            Entity *entity = malloc(sizeof(Entity));
            entity__init(entity);
            entity->offset_horizontal = i;
            entity->offset_vertical = j;

            int x = ctx->player->x + FAN_XXS[ctx->player->facing] * i + FAN_XYS[ctx->player->facing] * j;
            int y = ctx->player->y + FAN_YXS[ctx->player->facing] * i + FAN_YYS[ctx->player->facing] * j;

            if (ctx->monster->x == x && ctx->monster->y == y)
                entity->type = 1;

            entities[n_entities++] = entity;
        }
    }

    res.n_entities = n_entities;
    res.entities = entities;

    // inventory
    res.n_item_counts = ITEM_COUNT;
    res.item_counts = ctx->inventory;

    // message
    res.message = ctx->message;

    // possible moves
    int n_possible_moves = 0;
    Move possible_moves[4] = {0};
    possible_moves[n_possible_moves++] = MOVE__LEFT;
    possible_moves[n_possible_moves++] = MOVE__RIGHT;
    if (0 <= x2 && x2 < GRID_COLS &&
        0 <= y2 && y2 < GRID_ROWS &&
        ctx->grid[COORD(x2, y2)]->is_walkable)
        possible_moves[n_possible_moves++] = MOVE__FORWARD;
    if (0 <= x2 && x2 < GRID_COLS &&
        0 <= y2 && y2 < GRID_ROWS &&
        ctx->grid[COORD(x2, y2)]->is_interactable)
        possible_moves[n_possible_moves++] = MOVE__INTERACT;

    res.n_possible_moves = n_possible_moves;
    res.possible_moves = possible_moves;

    res.health = ctx->player->health;

    size_t packed_response_size = response__get_packed_size(&res);
    char *packed_response = malloc(packed_response_size);
    response__pack(&res, packed_response);
    ws_sendframe_bin(client, packed_response, packed_response_size);

    if (ctx->message != NULL)
    {
        free(ctx->message);
        ctx->message = NULL;
    }
    for (int i = 0; i < 25; i++)
        free(grids[i]);
    free(grids);
    free(packed_response);

void onopen(ws_cli_conn_t *client)
{
    char *cli;
    cli = ws_getaddress(client);

    int client_id = ws_get_id(client);

    // ---

    GameTile *wall_tile = malloc(sizeof(GameTile));
    wall_tile->type = 0;
    wall_tile->on_enter = on_default_enter;
    wall_tile->on_interact = on_default_interact;
    wall_tile->is_walkable = 0;
    wall_tile->is_interactable = 0;

    GameTile *fake_wall_tile = malloc(sizeof(GameTile));
    fake_wall_tile->type = 1;
    fake_wall_tile->on_enter = on_default_enter;
    fake_wall_tile->on_interact = on_default_interact;
    fake_wall_tile->is_walkable = 1;
    fake_wall_tile->is_interactable = 0;

    GameTile *walk_tile = malloc(sizeof(GameTile));
    walk_tile->type = 2;
    walk_tile->on_enter = on_default_enter;
    walk_tile->on_interact = on_default_interact;
    walk_tile->is_walkable = 1;
    walk_tile->is_interactable = 0;

    GameTile *flag_tile = malloc(sizeof(GameTile));
    flag_tile->type = 3;
    flag_tile->on_enter = on_default_enter;
    flag_tile->on_interact = on_flag_interact;
    flag_tile->is_walkable = 0;
    flag_tile->is_interactable = 1;

    GameTile *gate_1_tile = malloc(sizeof(GameTile));
    gate_1_tile->type = 4;
    gate_1_tile->on_enter = on_default_enter;
    gate_1_tile->on_interact = on_gate_1_interact;
    gate_1_tile->is_walkable = 0;
    gate_1_tile->is_interactable = 1;

    GameTile *gate_2_tile = malloc(sizeof(GameTile));
    gate_2_tile->type = 5;
    gate_2_tile->on_enter = on_default_enter;
    gate_2_tile->on_interact = on_gate_2_interact;
    gate_2_tile->is_walkable = 0;
    gate_2_tile->is_interactable = 1;

    GameTile *gate_3_tile = malloc(sizeof(GameTile));
    gate_3_tile->type = 6;
    gate_3_tile->on_enter = on_default_enter;
    gate_3_tile->on_interact = on_gate_3_interact;
    gate_3_tile->is_walkable = 0;
    gate_3_tile->is_interactable = 1;

    GameTile *gate_4_tile = malloc(sizeof(GameTile));
    gate_4_tile->type = 7;
    gate_4_tile->on_enter = on_default_enter;
    gate_4_tile->on_interact = on_gate_4_interact;
    gate_4_tile->is_walkable = 0;
    gate_4_tile->is_interactable = 1;

    GameTile *key_1_tile = malloc(sizeof(GameTile));
    key_1_tile->type = 8;
    key_1_tile->on_enter = on_default_enter;
    key_1_tile->on_interact = on_key_1_interact;
    key_1_tile->is_walkable = 0;
    key_1_tile->is_interactable = 1;

    GameTile *key_2_tile = malloc(sizeof(GameTile));
    key_2_tile->type = 9;
    key_2_tile->on_enter = on_default_enter;
    key_2_tile->on_interact = on_key_2_interact;
    key_2_tile->is_walkable = 0;
    key_2_tile->is_interactable = 1;

    GameTile *key_3_tile = malloc(sizeof(GameTile));
    key_3_tile->type = 10;
    key_3_tile->on_enter = on_default_enter;
    key_3_tile->on_interact = on_key_3_interact;
    key_3_tile->is_walkable = 0;
    key_3_tile->is_interactable = 1;

    GameTile *key_4_tile = malloc(sizeof(GameTile));
    key_4_tile->type = 11;
    key_4_tile->on_enter = on_default_enter;
    key_4_tile->on_interact = on_key_4_interact;
    key_4_tile->is_walkable = 0;
    key_4_tile->is_interactable = 1;

    GameTile **tileset = malloc(TILESET_SIZE * sizeof(GameTile *));
    tileset[0] = wall_tile;
    tileset[1] = fake_wall_tile;
    tileset[2] = walk_tile;
    tileset[3] = flag_tile;
    tileset[4] = gate_1_tile;
    tileset[5] = gate_2_tile;
    tileset[6] = gate_3_tile;
    tileset[7] = gate_4_tile;
    tileset[8] = key_1_tile;
    tileset[9] = key_2_tile;
    tileset[10] = key_3_tile;
    tileset[11] = key_4_tile;

    GameTile **grid = malloc(GRID_ROWS * GRID_COLS * sizeof(GameTile *));
    for (int x = 0; x < GRID_COLS; x++)
        for (int y = 0; y < GRID_ROWS; y++)
        {
            unsigned long long int range_grid = GRID[COORD(x, y) >> 4];
            grid[COORD(x, y)] = tileset[(range_grid >> (4 * (COORD(x, y) & 0xf))) & 0xf];
        }

    Player *player = malloc(sizeof(Player));
    player->x = 3;
    player->y = 27;
    player->facing = 1;
    player->health = 100;

    Monster *monster = malloc(sizeof(Monster));
    monster->x = GRID_COLS - 4;
    monster->y = GRID_ROWS - 4;

    int *inventory = malloc(sizeof(int) * ITEM_COUNT);

    memset(inventory, 0, sizeof(int) * ITEM_COUNT);

    Context *ctx = malloc(sizeof(Context));
    ctx->tileset = tileset;
    ctx->grid = grid;
    ctx->player = player;
    ctx->monster = monster;
    ctx->inventory = inventory;
    ctx->client = client;
    ctx->message = NULL;

    send_state_via_ws(ctx);

    ctxs[client_id] = ctx;
}

void onclose(ws_cli_conn_t *client)
{
    char *cli;
    cli = ws_getaddress(client);
    int client_id = ws_get_id(client);

    Context *ctx = ctxs[client_id];

    for (int i = 0; i < TILESET_SIZE; i++)
        free(ctx->tileset[i]);
    free(ctx->tileset);
    free(ctx->grid);
    free(ctx->player);
    free(ctx->monster);
    free(ctx->inventory);
    free(ctx);
    ctxs[client_id] = NULL;
}

void onmessage(ws_cli_conn_t *client,
               const unsigned char *msg, uint64_t size, int type)
{
    char *cli;
    cli = ws_getaddress(client);

    int client_id = ws_get_id(client);
    Context *ctx = ctxs[client_id];

    Request *req = request__unpack(NULL, size, msg);
    if (req == NULL)
        return;

    switch (req->move)
    {
    case MOVE__LEFT:
        ctx->player->facing = (ctx->player->facing - 1) & 3;
        break;
    case MOVE__RIGHT:
        ctx->player->facing = (ctx->player->facing + 1) & 3;
        break;
    case MOVE__FORWARD:
        int dx = DXS[ctx->player->facing];
        int dy = DYS[ctx->player->facing];
        walk(ctx, dx, dy);
        break;
    case MOVE__INTERACT:
        int x = ctx->player->x + DXS[ctx->player->facing];
        int y = ctx->player->y + DYS[ctx->player->facing];
        ctx->grid[COORD(x, y)]->on_interact(ctx, x, y);
        break;
    default:
        return;
    }
    send_state_via_ws(ctx);
}

int sgn(int x)
{
    if (x == 0)
        return 0;
    if (x < 0)
        return -1;
    return 1;
}

// Return 1 if the game is still running, 0 otherwise
int tick(Context *ctx)
{
    int dx = ctx->player->x - ctx->monster->x;
    int dy = ctx->player->y - ctx->monster->y;

    ctx->player->health -= 1;
    if (ctx->player->health == 0)
        return 0;

    if (DIST2(dx, dy) == 1)
    {
        ctx->player->health -= 10;
        if (ctx->player->health <= 0)
        {
            ctx->player->health = 0;
            return 0;
        }
        char *message = malloc(27 + 1);
        strcpy(message, "You were bitten by a snake!");
        ctx->message = message;
    }
    else if (DIST2(dx, dy) <= 10 * 10)
    {
        int facing = 0;
        if (abs(dx) >= abs(dy))
        {
            facing = 2 - sgn(dx);
        }
        else
        {
            facing = 1 + sgn(dy);
        }

        int x = ctx->monster->x + DXS[facing];
        int y = ctx->monster->y + DYS[facing];
        if (ctx->grid[COORD(x, y)]->is_walkable)
        {
            ctx->monster->x = x;
            ctx->monster->y = y;
        }
    }

    return 1;
}

int main()
{
    struct ws_events evs;
    evs.onopen = &onopen;
    evs.onclose = &onclose;
    evs.onmessage = &onmessage;

    ws_socket(&evs, 8080, 1, 1000);

    while (1)
    {
        for (int i = 0; i < MAX_CLIENTS; i++)
        {
            Context *ctx = ctxs[i];
            if (ctx == NULL)
                continue;
            int is_alive = tick(ctx);
            if (!is_alive)
            {
                char *message = malloc(25 + 1);
                strcpy(message, "You ran out of stamina...");
                ctx->message = message;
            }
            send_state_via_ws(ctx);
            if (!is_alive)
            {
                ws_cli_conn_t *client = ctx->client;
                ws_close_client(client);
            }
        }
        sleep(1);
    }

    return 0;
}