PSE Pre-alpha calculator (Variant)

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <ctype.h>

#include <omp.h>

#define BITS (1u << 21)
#define MAX (BITS * 8)

#define LEN 14



static void eval_r(int64_t *val,
    size_t nval, size_t i, int64_t res, uint8_t *set)
{
    if (i == nval) {
        if (res >= 0 && res <= MAX) {
            int m = res / 8;
            int j = res % 8;

            set[m] |= (1u << j);
        }
    } else {
        if (i == 0) {
            eval_r(val, nval, i + 1, *val, set);
        } else {
            eval_r(val, nval, i + 1, res + val[i], set);
            eval_r(val, nval, i + 1, res - val[i], set);
            eval_r(val, nval, i + 1, res * val[i], set);
            if (res % val[i] == 0) {
                eval_r(val, nval, i + 1, res / val[i], set);
            }
        }
    }
}

static void eval(const char *str, int n, uint8_t *set)
{
    const char *end = str + n;
    int64_t val[5];
    size_t nval = 0;

    while (str < end) {
        int64_t x = 0;

        while (str < end && isdigit(*str)) {
            x = x * 10 + *str++ - '0';
        }

        val[nval++] = x;
        str++;
    }

    eval_r(val, nval, 0, 0, set);
}

static void swap(char *str, int i, int j)
{
    char s = str[i]; str[i] = str[j]; str[j] = s;
}

static void permute(char *str, int n, uint8_t *set)
{
    int op = (str[n - 1] == '#');
    int i;
    int hash = 0;

    if (!op) {
        eval(str, n, set);
    }

    for (i = n; i < LEN; i++) {
        if (!op || isdigit(str[i])) {
            if (op && str[i] == '0') continue;

            if (str[i] == '#') {
                if (hash) continue;
                hash = 1;
            }

            swap(str, i, n);
            permute(str, n + 1, set);
            swap(str, i, n);
        }
    }
}

int main(void)
{
    int mthread = omp_get_max_threads();
    uint8_t *set[mthread];
    int m = 0;
    int i;

    fprintf(stderr, "Maximum number of threads: %d\n", mthread);

    for (i = 0; i < mthread; i++) set[i] = NULL;

    #pragma omp parallel
    {
        int nthread = omp_get_num_threads();
        int ithread = omp_get_thread_num();
        int n;

        set[ithread] = calloc(1, BITS);
        set[ithread][0] = 1;

        #pragma omp for
        for (n = 1; n < 90; n++) {
            char pool[] = "0123456789####";

            swap(pool, 0, 1 + n / 10);
            swap(pool, 1, 1 + n % 10);

            fprintf(stderr,
                "Exploring %c%c... on thread %d/%d.\n",
                pool[0], pool[1], ithread, nthread);

            permute(pool, 2, set[ithread]);
        }
    }

    {
        int nthread = 0;

        while (nthread < mthread && set[nthread]) nthread++;

        for (i = 0; i < BITS; i++) {
            uint8_t mask = 0u;
            int k;

            for (k = 0; k < nthread; k++) {
                mask |= set[k][i];
            }

            for (k = 0; k < 8; k++) {
                if ((mask & (1u << k)) == 0) {
                    printf("%d\n", m);
                }
                m++;
            }
        }

        for (i = 0; i < nthread; i++) free(set[i]);
    }

    return 0;
}