Barrett.c

#include <stdio.h>
#include <string.h>
#include "tommath.h"

int mp_barrett_todecimal_rec(mp_int *number, mp_int *nL, mp_int *shiftL, mp_int *mL, int index, int left, char **result) {
    mp_int q, nLq, r;
    int res;

    if (index < 0) {
        char *next_piece = malloc(4 * sizeof(char));
        sprintf(next_piece, left ? "%ld" : "%03ld", mp_get_int(number));
        (*result) = realloc(*result, strlen(*result) + strlen(next_piece) + 2);
        strcat(*result, next_piece);
        return MP_OKAY;
    }

    if ((res = mp_init_multi(&q, &nLq, &r, NULL)) != MP_OKAY) {
        goto LBL_ERR;
    }
    if ((res = mp_mul(number, &mL[index], &q)) != MP_OKAY) {
        goto LBL_ERR;
    }
    if ((res = mp_div_2d(&q, mp_get_int(&shiftL[index]), &q, NULL)) != MP_OKAY) {
        goto LBL_ERR;
    }

    if ((res = mp_mul(&nL[index], &q, &nLq)) != MP_OKAY) {
        goto LBL_ERR;
    }

    if ((res = mp_sub(number, &nLq, &r)) != MP_OKAY) {
        goto LBL_ERR;
    }

    if (mp_isneg(&r)) {
        if ((res = mp_sub_d(&q, 1, &q)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_add(&r, &nL[index], &r)) != MP_OKAY) {
            goto LBL_ERR;
        }
    }

    --index;
    if (left && mp_iszero(&q)) {
        if ((res = mp_barrett_todecimal_rec(&r, nL, shiftL, mL, index, 1, result)) != MP_OKAY) {
            goto LBL_ERR;
        }
    } else {
        if ((res = mp_barrett_todecimal_rec(&q, nL, shiftL, mL, index, left, result)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_barrett_todecimal_rec(&r, nL, shiftL, mL, index, 0, result)) != MP_OKAY) {
            goto LBL_ERR;
        }
    }

    return MP_OKAY;

LBL_ERR:mp_clear_multi (&q, &nLq, &r, NULL);
        printf("to_digits_rec\n");
    return res;
}

int mp_barrett_todecimal(mp_int *number, char **result) {
    mp_int n, shift, M, M2, M22, M4, M44;
    int res, index = 1;

    if ((res = mp_init_multi(&M2, &M22, &M4, &M44, NULL)) != MP_OKAY) {
        goto LBL_ERR;
    }

    if (mp_isneg(number)) {
        if ((res = mp_neg(number, number)) != MP_OKAY) {
            goto LBL_ERR;
        }
        *result[0] = '-';
    }
    if ((res = mp_init_set(&n, 1000)) != MP_OKAY) {
        goto LBL_ERR;
    }

    mp_int *nL = malloc(20 * sizeof(mp_int));
    if ((res = mp_init_copy(&nL[0], &n)) != MP_OKAY) {
        goto LBL_ERR;
    }

    if ((res = mp_init_set(&shift, 20)) != MP_OKAY) {
        goto LBL_ERR;
    }

    mp_int *shiftL = malloc(20 * sizeof(mp_int));
    if ((res = mp_init_copy(&shiftL[0], &shift)) != MP_OKAY) {
        goto LBL_ERR;
    }

    if ((res = mp_init_set(&M, 8389)) != MP_OKAY) {
        goto LBL_ERR;
    }

    mp_int *mL = malloc(20 * sizeof(mp_int));
    if ((res = mp_init_set(&mL[0], 1049)) != MP_OKAY) {
        goto LBL_ERR;
    }

    while (1) {
        if ((res = mp_sqr(&n, &n)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if (mp_cmp(&n, number) == MP_GT) {
            break;
        }

        if ((res = mp_mul_2(&shift, &shift)) != MP_OKAY) {
            goto LBL_ERR;
        }

        if ((res = mp_sqr(&M, &M2)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_sqr(&M2, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }

        if ((res = mp_mul(&M4, &n, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_div_2d(&M4, mp_get_long(&shift) + 6, &M4, NULL)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_mul_2(&M2, &M2)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_sub(&M4, &M2, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_add_d(&M4, 1, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_div_2d(&M4, 3, &M4, NULL)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_sub_d(&M4, 1, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_neg(&M4, &M)) != MP_OKAY) {
            goto LBL_ERR;
        }

        if ((res = mp_init_copy(&nL[index], &n)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_init_copy(&shiftL[index], &shift)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_add_d(&M4, 1, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_div_2d(&M4, 3, &M4, NULL)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_sub_d(&M4, 1, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_neg(&M4, &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        if ((res = mp_init_copy(&mL[index], &M4)) != MP_OKAY) {
            goto LBL_ERR;
        }
        index++;
    }

    if ((res = mp_barrett_todecimal_rec(number, nL, shiftL, mL, index - 1, 1, result)) != MP_OKAY) {
        goto LBL_ERR;
    }

    return MP_OKAY;

LBL_ERR:mp_clear_multi (&n, &shift, &M, &M2, &M22, &M4, &M44, NULL);
        printf("to_digits\n");
    return res;
}

int main(int argc, char *argv[]) {
    mp_int *i = malloc(sizeof(mp_int));
    mp_init(i);
    mp_2expt(i, atoi(argv[1]));
    if (atoi(argv[2]) == 1) {
        mp_neg(i, i);
    }

    char *s = calloc(2, sizeof(char));
    int res = mp_barrett_todecimal(i, &s);
    if (res == MP_OKAY) {
        printf("B: s = %s, chars = %ld\n", strlen(s));
    } else {
        printf("Died, %d\n", res);
    }

    return 0;
}