Add a bunch of overflow checks around malloc()

[clav.git] / quiver.c

/*
 * Copyright (c) 2017, S. Gilles <sgilles@math.umd.edu>
 *
 * Permission to use, copy, modify, and/or distribute this software
 * for any purpose with or without fee is hereby granted, provided
 * that the above copyright notice and this permission notice appear
 * in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "macros.h"
#include "quiver.h"

#define MAX_SUPPORTED_EDGE_NUM           (((size_t) -1) >> 2)
#define MAX_SUPPORTED_VERTEX_NUM         (((size_t) -1) >> 2)

/* Primes for reducing fractions */
static uint32_t primes[] = {
        /* */
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
        71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
        149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
        227, 229, 233, 239, 241, 251
};

/* GCD */
static int gcd(uint_fast8_t x, uint_fast8_t y)
{
        uint_fast8_t r = 0;

        if (!x &&
            !y) {
                return 1;
        }

        while (y) {
                r = x % y;
                x = y;
                y = r;
        }

        return x;
}

/* Attempt to store a fraction in out, reducing if possible */
static int reduce_fraction(int_fast32_t n, uint_fast32_t d, struct
                           rational *out, const char **out_errstr)
{
        if (!n &&
            d) {
                *out = (struct rational) { .p = 0, .q = 1 };

                return 0;
        }

        /* We special-case 1-3 since, in those cases, this actually needs to go fast */
        if (d == 1) {
                goto calculated;
        } else if (d == 2) {
                if (n % 2) {
                } else {
                        n /= 2;
                        d = 1;
                }

                goto calculated;
        } else if (d == 3) {
                if (n % 3) {
                } else {
                        n /= 3;
                        d = 1;
                }

                goto calculated;
        }

        for (size_t j = 0; j < ((sizeof primes) / (sizeof primes[0])); ++j) {
                uint32_t p = primes[j];

                if (j &&
                    p > d) {
                        break;
                }

                while (n % p == 0 &&
                       d % p == 0) {
                        n = n / p;
                        d = d / p;
                }
        }

calculated:

        if (n > INT_FAST8_MAX ||
            n < INT_FAST8_MIN ||
            d == 0 ||
            d > UINT_FAST8_MAX) {
                IF_NZ_SET(out_errstr, L("unrepresentable fraction"));

                return EDOM;
        }

        *out = (struct rational) { .p = n, .q = d };

        return 0;
}

/* out += a/b */
static int add_to_fraction(int_fast8_t a, uint_fast8_t b, struct rational *out,
                           const char **out_errstr)
{
        int_fast32_t n = a * out->q + out->p * b;
        uint_fast32_t d = b * out->q;

        return reduce_fraction(n, d, out, out_errstr);
}

/* Add an arrow of weight a/b from i -> j, affecting e(i,j) and e(j,i) */
int quiver_add_to_edge(struct quiver *q, size_t i, size_t j, int_fast8_t a,
                       uint_fast8_t b, const char **out_errstr)
{
        int ret = 0;

        if (!q) {
                IF_NZ_SET(out_errstr, L("nonexistant quiver"));

                return EINVAL;
        }

        if (i >= q->v_num ||
            j >= q->v_num) {
                IF_NZ_SET(out_errstr, L("edge includes nonexistant vertex"));

                return EINVAL;
        }

        if (i == j) {
                IF_NZ_SET(out_errstr, L("loops are not allowed"));

                return EINVAL;
        }

        struct rational *eij = &(q->e[i * q->v_len + j]);
        struct rational *eji = &(q->e[j * q->v_len + i]);
        uint_fast8_t d = gcd(q->v[i].fatness, q->v[j].fatness);

        if ((ret = add_to_fraction(a * q->v[j].fatness, b * d, eij,
                                   out_errstr))) {
                return ret;
        }

        if ((ret = add_to_fraction(-1 * a * q->v[i].fatness, b * d, eji,
                                   out_errstr))) {
                return ret;
        }

        return 0;
}

/* Add a vertex with a name and weight */
int quiver_add_vertex(struct quiver *q, size_t *out_i, const char *name,
                      uint_fast16_t fatness, int x, int y, const
                      char **out_errstr)
{
        void *newmem = 0;
        char *newname;
        size_t len = 0;

        if (!q) {
                IF_NZ_SET(out_errstr, L("invalid quiver"));

                return EINVAL;
        }

        if (!name) {
                len = snprintf(0, 0, "%zu", q->v_num);

                if (len + 1 < len) {
                        IF_NZ_SET(out_errstr, L("overflow"));

                        return EOVERFLOW;
                }

                if (!(newname = malloc(len + 1))) {
                        int sv_err = errno;

                        IF_NZ_SET(out_errstr, L("malloc"));

                        return sv_err;
                }

                sprintf(newname, "%zu", q->v_num);
        } else {
                /*
                 * Should be no need to check overflow, either name
                 * was malloc'd, or came from a file which was read
                 * in with a length cap.
                 */
                if (!(newname = malloc(strlen(name) + 1))) {
                        int sv_err = errno;

                        IF_NZ_SET(out_errstr, L("malloc"));

                        return sv_err;
                }

                strcpy(newname, name);
        }

        if (q->v_num >= q->v_len) {
                size_t newlen = q->v_len + 8;

                if (newlen >= ((size_t) -1) / newlen ||
                    (newlen * newlen) / newlen != newlen) {
                        IF_NZ_SET(out_errstr, L("too many vertices"));

                        return EDOM;
                }

                if (!(newmem = calloc(newlen * newlen, sizeof (*q->e)))) {
                        int sv_err = errno;

                        IF_NZ_SET(out_errstr, L("too many vertices"));

                        return sv_err;
                }

                for (size_t j = 0; j < q->v_num; ++j) {
                        for (size_t k = 0; k < q->v_num; ++k) {
                                ((struct rational *) newmem)[j * newlen + k] =
                                        q->e[j * q->v_len + k];
                        }

                        for (size_t k = q->v_num; k < newlen; ++k) {
                                ((struct rational *) newmem)[j * newlen + k] =
                                        (struct rational) { .p = 0, .q = 1 };
                        }
                }

                for (size_t j = q->v_num; j < newlen; ++j) {
                        for (size_t k = 0; k < newlen; ++k) {
                                ((struct rational *) newmem)[j * newlen + k] =
                                        (struct rational) { .p = 0, .q = 1 };
                        }
                }

                if (q->e) {
                        free(q->e);
                }

                q->e = newmem;

                if (!(newmem = (realloc(q->v, newlen * sizeof (*q->v))))) {
                        int sv_err = errno;

                        IF_NZ_SET(out_errstr, L("too many vertices"));

                        return sv_err;
                }

                q->v = newmem;
                q->v_len = newlen;
        }

        for (size_t k = 0; k <= q->v_num; ++k) {
                q->e[k * q->v_len + q->v_num] = (struct rational) { .p = 0, .q =
                                                                            1 };
                q->e[q->v_num * q->v_len + k] = (struct rational) { .p = 0, .q =
                                                                            1 };
        }

        q->v[q->v_num] = (struct vertex) { .name = newname, .fatness = fatness,
                                           .x = x, .y = y };

        if (out_i) {
                *out_i = q->v_num;
        }

        q->v_num++;

        return 0;
}

/* Increase or decrease the fatness of a vertex, readjusting edges as well */
int quiver_adjust_fatness(struct quiver *q, size_t i, int_fast8_t fatness_adj,
                          const char **out_errstr)
{
        int ret = 0;

        if (i >= q->v_num) {
                IF_NZ_SET(out_errstr, L("invalid vertex"));

                return EINVAL;
        }

        int new_fatness = q->v[i].fatness + fatness_adj;

        if (new_fatness <= 0 ||
            new_fatness > UINT_FAST8_MAX) {
                IF_NZ_SET(out_errstr, L("invalid new fatness"));

                return EINVAL;
        }

        for (size_t j = 0; j < q->v_num; ++j) {
                if (i == j) {
                        continue;
                }

                uint_fast8_t d_orig = gcd(q->v[i].fatness, q->v[j].fatness);
                uint_fast8_t d_new = gcd(new_fatness, q->v[j].fatness);
                size_t k = i * q->v_len + j;

                if ((ret = reduce_fraction(q->e[k].p * d_orig, q->e[k].q *
                                           d_new, &(q->e[k]), out_errstr))) {
                        return ret;
                }

                k = j * q->v_len + i;

                if ((ret = reduce_fraction(q->e[k].p * d_orig * q->v[i].fatness,
                                           q->e[k].q * d_new * new_fatness,
                                           &(q->e[k]), out_errstr))) {
                        return ret;
                }
        }

        q->v[i].fatness = new_fatness;

        return ret;
}

/* Free all memory used by this quiver, resetting it to { 0 } */
int quiver_clean(struct quiver *q)
{
        if (!q) {
                return 0;
        }

        for (size_t j = 0; j < q->v_num; ++j) {
                free(q->v[j].name);
        }

        free(q->v);
        free(q->e);
        *q = (struct quiver) { 0 };

        return 0;
}

/* Delete a vertex (and all associated edges) */
int quiver_delete_vertex(struct quiver *q, size_t i, const char **out_errstr)
{
        if (i >= q->v_num) {
                IF_NZ_SET(out_errstr, L("invalid vertex"));

                return EINVAL;
        }

        if (q->v_num == 1) {
                q->v_num = 0;
                free(q->v[0].name);
                q->v[0].name = 0;

                return 0;
        }

        /* First, shift everything over to the left */
        for (size_t j = 0; j < q->v_num; ++j) {
                for (size_t k = i + 1; k < q->v_num; ++k) {
                        q->e[q->v_len * j + k - 1] = q->e[q->v_len * j + k];
                }
        }

        /* Second, shift everything below row i up */
        for (size_t j = i + 1; j < q->v_num; ++j) {
                for (size_t k = 0; k < q->v_num; ++k) {
                        q->e[q->v_len * (j - 1) + k] = q->e[q->v_len * j + k];
                }
        }

        /* Now shift the vertex names/lengths over */
        free(q->v[i].name);
        q->v[i].name = 0;

        for (size_t j = i + 1; j < q->v_num; ++j) {
                q->v[j - 1] = q->v[j];
        }

        q->v_num--;
        q->v[q->v_num] = (struct vertex) { 0 };

        return 0;
}

/* Read quiver from file */
int quiver_load_from_file(struct quiver *q, FILE *f, const char **out_errstr)
{
        if (!q) {
                IF_NZ_SET(out_errstr, L("invalid quiver"));

                return EINVAL;
        }

        int ret = 0;

        for (size_t k = 0; k < q->v_num; ++k) {
                struct vertex *v = &(q->v[k]);

                free(v->name);
                v->name = 0;
        }

        q->v_num = 0;
        size_t new_vnum = 0;
        char *p = 0;

        if (fscanf(f, "%zu Vertices\n", &new_vnum) != 1) {
                IF_NZ_SET(out_errstr, L("Invalid file (|V| unspecified)"));

                return EINVAL;
        }

        for (size_t k = 0; k < new_vnum; ++k) {
                size_t j = 0;
                size_t fatness = 0;
                int x = 0;
                int y = 0;
                size_t len = 0;

                if (fscanf(f, " v[%zu] f:%zu x:%d y:%d l:%zu n:", &j, &fatness,
                           &x, &y, &len) != 5) {
                        IF_NZ_SET(out_errstr, L("Invalid file"));

                        return EINVAL;
                } else if (j != k) {
                        IF_NZ_SET(out_errstr, L(
                                          "Invalid file (vertices out of order)"));

                        return EINVAL;
                } else if (fatness >= UINT_FAST16_MAX) {
                        IF_NZ_SET(out_errstr, L(
                                          "Invalid file (fatness unsupported)"));

                        return EINVAL;
                }

                if (p) {
                        free(p);
                        p = 0;
                }

                if (!len) {
                        IF_NZ_SET(out_errstr, L(
                                          "Invalid file (nameless vertex)"));

                        return EINVAL;
                }

                if (len > 1024) {
                        IF_NZ_SET(out_errstr, L(
                                          "Invalid file (vertex with name too large)"));

                        return EINVAL;
                }

                if (!(p = malloc(len + 1))) {
                        ret = errno;
                        perror(L("malloc"));
                        IF_NZ_SET(out_errstr, L("malloc error"));

                        return ret;
                }

                if (fread(p, sizeof *p, len, f) != (sizeof *p) * len) {
                        IF_NZ_SET(out_errstr, L(
                                          "Invalid file (short vertex name)"));

                        return EINVAL;
                }

                p[len] = '\0';

                if ((ret = quiver_add_vertex(q, 0, p, (uint_fast16_t) fatness,
                                             x, y, out_errstr))) {
                        goto done;
                }
        }

        while (!feof(f)) {
                size_t i = 0;
                size_t j = 0;
                long n = 0;
                size_t d = 0;

                if (fscanf(f, " e[%zu][%zu] %ld/%zu ", &i, &j, &n, &d) != 4) {
                        IF_NZ_SET(out_errstr, L("Invalid file (bad edge)"));
                        ret = EINVAL;
                        goto done;
                }

                if (i >= q->v_num ||
                    j >= q->v_num) {
                        IF_NZ_SET(out_errstr, L(
                                          "Invalid file (edge between nonexistent vertices)"));
                        ret = EINVAL;
                        goto done;
                }

                struct rational *e = &(q->e[i * q->v_len + j]);

                if (n <= INT_FAST32_MIN ||
                    n >= INT_FAST32_MAX ||
                    d > UINT_FAST32_MAX) {
                        IF_NZ_SET(out_errstr, L(
                                          "Invalid file (edge weight out of range)"));
                        ret = EINVAL;
                        goto done;
                }

                if ((ret = reduce_fraction((int_fast32_t) n, (uint_fast32_t) d,
                                           e, out_errstr))) {
                        goto done;
                }
        }

        ret = 0;
done:
        free(p);

        return ret;
}

/* Rename a vertex */
int quiver_rename_vertex(struct quiver *q, size_t i, const char *new_name, const
                         char **out_errstr)
{
        if (!q) {
                IF_NZ_SET(out_errstr, L("invalid quiver"));

                return EINVAL;
        }

        if (i >= q->v_num) {
                IF_NZ_SET(out_errstr, L("vertex out of range"));

                return EINVAL;
        }

        void *newmem = 0;
        int ret = 0;

        if (!(newmem = strdup(new_name))) {
                ret = errno;
                IF_NZ_SET(out_errstr, L("cannot strdup()"));
                goto done;
        }

        free(q->v[i].name);
        q->v[i].name = newmem;
done:

        return ret;
}

/* Serialize the quiver */
int quiver_save_to_file(struct quiver *q, FILE *f, const char **out_errstr)
{
        if (!q) {
                IF_NZ_SET(out_errstr, L("invalid quiver"));

                return EINVAL;
        }

        int ret = 0;

        if (fprintf(f, "%zu Vertices\n", q->v_num) < 0) {
                ret = errno;
                IF_NZ_SET(out_errstr, L("write failed"));
                goto done;
        }

        for (size_t k = 0; k < q->v_num; ++k) {
                struct vertex *v = &(q->v[k]);

                if (fprintf(f, "v[%zu] f:%zu x:%d y:%d l:%zu n:%s\n", k,
                            (size_t) v->fatness, v->x, v->y, strlen(v->name),
                            v->name) <
                    0) {
                        ret = errno;
                        IF_NZ_SET(out_errstr, L("write failed"));
                        goto done;
                }
        }

        for (size_t i = 0; i < q->v_num; ++i) {
                for (size_t j = 0; j < q->v_num; ++j) {
                        struct rational *e = &(q->e[i * q->v_len + j]);

                        if (!e->p) {
                                continue;
                        }

                        if (fprintf(f, "e[%zu][%zu] %d/%u\n", i, j, (int) e->p,
                                    (unsigned) e->q) < 0) {
                                ret = errno;
                                IF_NZ_SET(out_errstr, L("write failed"));
                                goto done;
                        }
                }
        }

        if (fflush(f)) {
                ret = errno;
                IF_NZ_SET(out_errstr, L("flush failed"));
        }

done:

        return ret;
}

/* Set threshold: if quiver_mutate() creates an edge above, warn_out is set */
int quiver_set_warning_threshold(struct quiver *q, unsigned int warn_threshold,
                                 const char **out_errstr)
{
        if (!q) {
                IF_NZ_SET(out_errstr, L("invalid quiver"));

                return EINVAL;
        }

        q->edge_weight_threshold = warn_threshold;

        return 0;
}

/* Mutate the quiver at vertex k */
int quiver_mutate(struct quiver *q, size_t k, int *out_warn, const
                  char **out_errstr)
{
        int ret = 0;

        if (!q) {
                IF_NZ_SET(out_errstr, L("invalid quiver"));

                return EINVAL;
        }

        /* Step one: complete all triangles */
        for (size_t i = 0; i < q->v_num; ++i) {
                if (i == k) {
                        continue;
                }

                struct rational *eik = &(q->e[i * q->v_len + k]);

                for (size_t j = 0; j < q->v_num; ++j) {
                        if (j == k ||
                            j == i) {
                                continue;
                        }

                        struct rational *eij = &(q->e[i * q->v_len + j]);
                        struct rational *ekj = &(q->e[k * q->v_len + j]);

                        if (eik->p * ekj->p <= 0) {
                                continue;
                        }

                        if ((ret = add_to_fraction(abs(eik->p) * ekj->p,
                                                   eik->q * ekj->q, eij,
                                                   out_errstr))) {
                                return ret;
                        }

                        if (out_warn &&
                            q->edge_weight_threshold &&
                            eij->q * q->edge_weight_threshold <= (unsigned
                                                                  int) abs(
                                    eij->p)) {
                                *out_warn = 1;
                        }
                }
        }

        /* Step two: invert all edges that touch k */
        for (size_t i = 0; i < q->v_num; ++i) {
                if (i == k) {
                        continue;
                }

                struct rational *eik = &(q->e[i * q->v_len + k]);
                struct rational *eki = &(q->e[k * q->v_len + i]);

                eik->p = -eik->p;
                eki->p = -eki->p;
        }

        return 0;
}