/*
vim:tw=76:ts=4:sts=4:sw=4:cindent:expandtab
 */

/* gcc safari-lotto.c -lgmp -lm -O2 -flto charcrandom.c */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <mpir.h>
#include <math.h>
#include <limits.h>

#include "charcrandom.h"

#define VERSION "1.0.3"
#define RNDBUFSZ (1024)
#define LOTTOMAX (INT_MAX/sizeof(uint32_t))

/* Max factorial we are willing to calculate with GMP */
static const uint32_t max_mp_factorial = 5000000; /* at max 4s CPU time on SandyBridge */

static int qsort_cmp_long(const void *lp1, const void *lp2)
{
    uint32_t u1 = *(uint32_t*)lp1;
    uint32_t u2 = *(uint32_t*)lp2;

    if (u1 < u2) return -1;
    else if (u1 > u2) return 1;
    else return 0;
}

/*
   result = factorial(max) / (factorial(chosen) * factorial(max - chosen))
   result is base10 string which is not to be modified by caller
 */
static char *mp_calc_odds(unsigned long max, unsigned long chosen)
{
    mpz_t mpf1;
    mpz_t mpf2;
    mpz_t mpf3;
    mpz_t mpf4;
    mpz_t mpfres;
    static char str_many[] = "many";
    static char str_1[] = "1";
    static char str_long[21];

    /* Quick checks */
    if (chosen >= max) {
        return str_1; 
    }
    if ((chosen == 1) || (chosen == (max - 1))) {
        snprintf(str_long, sizeof(str_long), "%lu", max);
        return str_long;
    }
    if (max > max_mp_factorial) {
        return str_many;
    }

    mpz_init(mpf1);
    mpz_init(mpf2);
    mpz_init(mpf3);
    mpz_init(mpf4);
    mpz_init(mpfres);
    mpz_fac_ui(mpf1, max);
    mpz_fac_ui(mpf2, chosen);
    mpz_fac_ui(mpf3, max - chosen);
    mpz_mul(mpf4, mpf2, mpf3);
    mpz_divexact(mpfres, mpf1, mpf4);
    return mpz_get_str(NULL, 10, mpfres);
}

int main(int argc, char *argv[])
{
    uint32_t i, rnd, tmp;
    unsigned long loops;
    unsigned long max;
    unsigned long chosen;
    uint32_t *numbers = NULL;
    int digits;
    char *endptr;
    char *retnum;
    unsigned char calc_odds;

    if (argc != 5) {
        fprintf(stderr, "usage: %s max chosen loops calc_odds [e.g., 39 7 10 1]\n", argv[0]);
        exit(1);
    }

    errno = 0;
    max = strtoul(argv[1], &endptr, 10);
    if ((errno != 0) || (endptr == argv[1]) || (max < 2) || (max > LOTTOMAX)) {
        fprintf(stderr, "%s: valid range for max is 2..%zu\n", argv[0], LOTTOMAX);
        exit(1);
    }
    chosen = strtoul(argv[2], &endptr, 10);
    if ((errno != 0) || (endptr == argv[2]) || (chosen < 1) || (chosen > (max-1))) {
        fprintf(stderr, "%s: valid range for chosen is 1..%lu\n", argv[0], (max-1));
        exit(1);
    }
    loops = strtoul(argv[3], &endptr, 10);
    if ((errno != 0) || (endptr == argv[3])) {
        fprintf(stderr, "%s: invalid value for loops\n", argv[0]);
        exit(1);
    }
    calc_odds = argv[4][0] - '0';
    if (calc_odds > 1) {
        fprintf(stderr, "%s: invalid value for calc_odds, must be 0 or 1\n", argv[0]);
        exit(1);
    }

    if ((chosen > 1) && (loops > 0)) {
        numbers = malloc(sizeof(uint32_t) * max);
        if (numbers == NULL) {
            fprintf(stderr, "%s: malloc failed: %s\n", argv[0], strerror(errno));
            exit(1);
        }    
        for (i = 0; i < max; i++) {
            numbers[i] = i + 1;
        }
    }

    if (!calc_odds) {
        retnum = "many";
    } else {
        retnum = mp_calc_odds(max, chosen);
    }

    fprintf(stderr, "Executing Safari Lotto v" VERSION ", loops=%lu, %lu number%s chosen from range 1..%lu (%s possibilities).\n",
            loops, chosen, (chosen == 1) ? "" : "s", max, retnum);
    if (loops == 0) exit(0);

    /* Format fprintf nicely */
    digits = log10(max) + 1;

    if (chosen > 1) {
        while (loops--) {
            /* Knuth shuffle */
            i = max;
            while (i > 1) {
                rnd = charcrandom_uniform32(i);
                i--;
                tmp = numbers[rnd];
                numbers[rnd] = numbers[i];
                numbers[i] = tmp;
            }

            qsort(numbers, chosen, sizeof(uint32_t), qsort_cmp_long);
            for (i = 0; i < chosen; i++) {
                fprintf(stdout, "%*u ", digits, numbers[i]);
            }
            fprintf(stdout, "\n");
        }
    } else {
        while (loops--) {
            fprintf(stdout, "%*u\n", digits, charcrandom_uniform32(max) + 1);
        }
    }

    fflush(stdout);
    exit(0);
}