bsq.c

#include <fcntl.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

#define cat(x) #x
#define xcat(x) cat(x)
#define lenof(s) (sizeof (s) - sizeof (char))

#define comp constexpr static const
#define _MAP_WIDTH 10000 // constepxr are not xcat-able :<

comp size_t MAP_WIDTH = _MAP_WIDTH;
comp size_t MAP_SIZE = (MAP_WIDTH + 1) * MAP_WIDTH;
comp size_t MAP_DIM_HINT_LENGTH = lenof(xcat(_MAP_WIDTH)) + 1;
comp size_t MAP_STAT_SIZE = MAP_SIZE + MAP_DIM_HINT_LENGTH;

comp size_t MTX_SIZE = ((MAP_WIDTH + 1) << 1);

typedef struct {
    uint16_t size;
    uint16_t x;
    uint16_t y;
} square_t;

typedef struct {
    uint16_t x;
    uint16_t y;
    square_t best;
} solver_t;

[[gnu::hot]] static inline
int min3(uint16_t x, uint16_t y, uint16_t z)
{
    if (x > y)
        return (y < z) ? y : z;
    return (x < z) ? x : z;
}

[[gnu::hot]] static inline
void check_square(
    const uint8_t c,
    uint16_t *restrict sv,
    uint16_t *restrict psv, solver_t *sol)
{
    register uint16_t sz;

    if (c == 'o')
        sv[sol->x] = 0;
    else {
        sv[sol->x] = sz = (!sol->x || !sol->y) ? 1
            : 1 + min3(psv[sol->x - 1], psv[sol->x], sv[sol->x - 1]);
        if (sol->best.size < sz)
            sol->best = (square_t) { sz, sol->x, sol->y };
    }
}

int main(int argc [[maybe_unused]], char **argv)
{
    uint16_t sv[2][MAP_WIDTH + 1] = {0};
    uint8_t (*arr)[MAP_WIDTH][MAP_WIDTH + 1];

    int fd = open(argv[1], O_RDONLY); // assume argv[1] is set

#define unlikely(x) __builtin_expect(!!(x), 0)
    if (unlikely(fd < 0))
        abort();

    solver_t sol = { 0 };
    uint8_t *buff = mmap(NULL,
        MAP_STAT_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);

    buff += MAP_DIM_HINT_LENGTH; // THIS HAS DO BE DONE FIRST
    arr = (uint8_t (*)[MAP_WIDTH][MAP_WIDTH + 1])(buff);

#define CQX(q) { \
    check_square((*arr)[sol.y][sol.x], sv[q], sv[((q)+1)&1], &sol); \
    sol.x++; \
}

// this is aggressive unrolling ! :o
#define CQY(q)                          \
    for(sol.x=0;sol.x<(MAP_WIDTH/2);) { \
        CQX(q);                         \
        CQX(q);                         \
    };                                  \
    sol.y++;                            \
    __COUNTER__; // inc ref

    sol.y = 0;
    do {
        CQY(0) CQY(1)
        CQY(0) CQY(1)
        CQY(0) CQY(1)
        CQY(0) CQY(1)
    } while (sol.y < (MAP_WIDTH / __COUNTER__));

    for (uint16_t i = 0; i < sol.best.size; i++)
        for (uint16_t j = 0; j < sol.best.size; j++)
            (*arr)[sol.best.y - i][sol.best.x - j] = 'x';

    write(STDOUT_FILENO, buff, MAP_SIZE);
    return EXIT_SUCCESS;
}