/*
 * Copyright 1996 Thierry Bousch
 * Licensed under the Gnu Public License, Version 2
 *
 * $Id: main.c,v 2.6 1996/09/15 16:08:32 bousch Exp $
 *
 * Factorization of big integers. Main module.
 */

#include <assert.h>
#include <ctype.h>
#include <getopt.h>
#include <pwd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <time.h>
#include <unistd.h>
#include "saml.h"
#include "saml-parse.h"
#include "saml-util.h"
#include "factorint.h"

#define VERSION		"0.50"
#define DEF_PP_TESTS	5
#define DEF_SM_DIV	5000

char *progname;
int quiet;
int pptests = DEF_PP_TESTS;
int mpqs_primes = 0;
int mpqs_exponent = 0;
int mpqs_width = 0;
const char *mpqs_debug_file = NULL;
static int tloops = DEF_SM_DIV;
static int max_pollard = -2;
static int test_only = 0;
static int one_prime = 0;
static int dont_fork = 0;
static const char *mailaddr, *username;
static char mailfile[] = "/tmp/factorsXXXXXX";

static const char Copyright[] = "\
Factorint "VERSION" (compiled "__DATE__") Copyright (C) 1996 Thierry Bousch
This program is FREE SOFTWARE, with absolutely NO WARRANTY.
You are welcome to redistribute it under certain conditions;
read the file \"COPYING\" for details.
";
static const char Usage[] = "\
Usage: %s [options] NUMBERS...
Options:
  -t, --test-prime		Only print prime / composite
  -1, --one-factor		Only print one prime factor
  -m, --mail			Background mode, mail the result to me
      --mailto ADDRESS		or to someone else.
  -n, --nice NUM		Be nice to other processes
  -q, --quiet			Quiet mode, without the rotating cursor
      --small-divisors NUM	Number of small divisors to try
      --pseudo-prime-tests NUM	Number of pseudo-primality tests
      --pollard-loops NUM	Number of loops before giving up
      --mpqs-primes NUM		The factor base size in MPQS
      --mpqs-exponent NUM	Set the tolerance exponent to NUM/1000
      --mpqs-interval NUM	Length of the sieve interval (2*M)
      --mpqs-debug FILENAME	Write debugging information into this file
      --help			Display this menu, and exit
      --version			Display the version number, and exit
";
static const char sh_opt[] = "n:mqt1";
static const struct option lg_opt[] = {
	{ "test-primality",	0, NULL, 't' },
	{ "test-prime",		0, NULL, 't' },
	{ "test",		0, NULL, 't' },
	{ "one-factor",		0, NULL, '1' },
	{ "one",		0, NULL, '1' },
	{ "mail",		0, NULL, 'm' },
	{ "nice",		1, NULL, 'n' },
	{ "quiet",		0, NULL, 'q' },
	{ "silent",		0, NULL, 'q' },
	{ "small-divisors",	1, NULL, 160 },
	{ "pseudo-prime-tests",	1, NULL, 161 },
	{ "pseudo-prime",	1, NULL, 161 },
	{ "pp-tests",		1, NULL, 161 },
	{ "pollard-maxtries",	1, NULL, 162 },
	{ "pollard-loops",	1, NULL, 162 },
	{ "mailto",		1, NULL, 170 },
	{ "mail-to",		1, NULL, 170 },
	{ "dont-fork",		0, NULL, 171 },
	{ "help",		0, NULL, 172 },
	{ "usage",		0, NULL, 172 },
	{ "version",		0, NULL, 173 },
	{ "copyright",		0, NULL, 173 },
	{ "warranty",		0, NULL, 173 },
	{ "mpqs-size",		1, NULL, 183 },
	{ "mpqs-primes",	1, NULL, 183 },
	{ "mpqs-exponent",	1, NULL, 184 },
	{ "mpqs-interval",	1, NULL, 185 },
	{ "mpqs-width",		1, NULL, 185 },
	{ "mpqs-length",	1, NULL, 185 },
	{ "mpqs-debug",		1, NULL, 186 },
	{ "mpqs-debug-file",	1, NULL, 186 },
	{ NULL,	0, NULL, 0 }
};

static void divide_greatest_power (mref_t N, mref_t prime)
{
	int valuation;
	mref_t tmp1, tmp2;

	tmp1 = mref_new();
	tmp2 = mref_new();
	valuation = 0;
	for(;;) {
		mref_div(tmp1, N, prime);
		mref_mul(tmp2, tmp1, prime);
		if (mref_differ(tmp2, N))
			break;
		mref_copy(N, tmp1);
		/*
		 * If the --one-prime option is given, we don't need to
		 * compute the p-adic valuation. Just display p.
		 */
		if (++valuation && one_prime)
			break;
	}
	fputs(mref_string(prime), stdout);
	if (valuation != 1)
		printf("^%d", valuation);
	mref_free(tmp1);
	mref_free(tmp2);
}

static int find_factor (mref_t result, mref_t N)
{
	if (find_factor_pollard(result, N, max_pollard))
		return 1;
	return find_factor_mpqs(result, N);
}

static void factorize (mref_t N)
{
	int ret, position = 0, maxloops = tloops;
	mref_t D, left, tmp, One, Two;

	D = mref_new(); left = mref_new(); tmp = mref_new();
	One = mref_new(); Two = mref_new();

	mref_build(One, ST_INTEGER, "1");
	mref_build(Two, ST_INTEGER, "2");
	mref_copy(left, N);
	mref_copy(D, Two);
	if (!mref_lessthan(One,N)) {
		/* If the number is 0 or 1, print it here */
		printf("%s", mref_string(N));
	}
	while (mref_lessthan(One,left)) {
		while(1) {
			if (maxloops == 0) {
				/* We haven't found any divisor */
				mref_copy(D, One);
				break;
			}
			--maxloops;
			mref_div(tmp, left, D);
			if (mref_lessthan(tmp, D)) {
				/* The remaining number is prime */
				mref_copy(D, left);
				break;
			}
			mref_mul(tmp, tmp, D);
			if (!mref_differ(tmp, left)) {
				/* We have found a divisor */
				break;
			}
			/* Bump the divisor */
			if (!mref_differ(D, Two))
				mref_add(D, D, One);
			else
				mref_add(D, D, Two);
		}
		if (mref_differ(D, One)) {
			/* We have found a divisor, or left is prime */
			if (position++)
				putchar('.');
			divide_greatest_power(left, D);
			if (one_prime)
				break;
		} else if (is_pseudo_prime(left)) {
			/* Assume left is prime */
			if (position++)
				putchar('.');
			fputs(mref_string(left), stdout);
			break;
		} else {
			/* Composite, but without small divisors */
			ret = find_factor(D, left);
			assert(ret != 0);
			assert(is_pseudo_prime(D));
			if (position++)
				putchar('.');
			divide_greatest_power(left, D);
			if (one_prime)
				break;
		}
		fflush(stdout);
	}
	putchar('\n'); fflush(stdout);
	mref_free(D); mref_free(left); mref_free(tmp);
	mref_free(One); mref_free(Two);
}

static void goto_background (void)
{
	int pid = (dont_fork ? 0 : fork());

	switch(pid) {
	    case -1:
	    	/* Out of processes */
		perror("fork");
		mailaddr = NULL;
		break;
	    case 0:
		/* The child goes on */
		close(0); close(1); close(2);
		setsid();
		nice(10);
		mktemp(mailfile);
		quiet = 1;
		break;
	    default:
		/* But the parent exits */
		if (!quiet)
		  fprintf(stderr,"Results will be mailed to %s\n",mailaddr);
		exit(0);
	}
}

static void process_number (const char *number)
{
	mref_t N = mref_new();

	mref_build(N, ST_INTEGER, "0");
	saml_init_lexer_mem(number, strlen(number));
	saml_parse(N, N);

	if (mref_type(N) == ST_VOID) {
		fprintf(stderr, "%s: malformed number `%s'\n", progname,
		  number);
		goto free_N;
	}
	if (mref_isneg(N)) {
		/* Only print the sign for complete factorizations */
		if (!test_only && !one_prime)
			putchar('-');
		/* But make the number positive in all cases */
		mref_negate(N, N);
	}
	if (test_only) {
		int ret = is_pseudo_prime(N);
		puts(ret ? "prime" : "composite");
		fflush(stdout);
	} else
		factorize(N);
free_N:
	mref_free(N);
}

static void mail_number (const char *number)
{
	int fd;
	time_t now;

	if (mailaddr == NULL) {
		/* No redirection, fallback to process_number() */
		process_number(number);
		return;
	}
	fd = open(mailfile, O_RDWR|O_CREAT|O_TRUNC|O_APPEND, 0666);
	assert(fd == 0);
	unlink(mailfile);
	dup2(fd,1); dup2(fd,2); time(&now);
	printf("From: %s\nTo: %s\n", username, mailaddr);
	printf("X-Comment: mail sent by Factorint %s\n", VERSION);
	printf("X-Factorization-Started-At: %s", ctime(&now));
	if (strlen(number) <= 50) {
		/* We can put the number in the subject */
		printf("Subject: factors of %s\n\n", number);
	}
	else {
		/* The number is huge */
		printf("Subject: Your number has been factorized\n\n"
			"Number: %s\n\n", number);
	}
	fflush(stdout);
	process_number(number);
	fflush(stdout); fflush(stderr);
	close(1); close(2);
	lseek(0, 0, SEEK_SET);	/* rewind stdin */
	system("/usr/lib/sendmail -oi -om -oem -t");
	close(0);
}

static void get_username (void)
{
	struct passwd *user;

	/* Get the login name corresponding to our real UID */
	user = getpwuid(getuid());
	username = user? user->pw_name : "nobody";
}

int main (int argc, char **argv)
{
	int c;
	gr_string *grs;

	progname = argv[0];
	quiet = !isatty(1);
	saml_init();
	saml_error_handler = saml_silent_ehandler;

	while ((c = getopt_long(argc,argv,sh_opt,lg_opt,NULL)) != EOF)
	switch(c) {
	    case '1':
	    	/* Just search one factor */
	    	one_prime = 1;
	    	break;
	    case 'n':
	    	/* Renice the process */
	    	if (nice(atoi(optarg)))
	    		perror("nice");
	    	break;
	    case 'q':
		/* Quiet mode */
		quiet = 1;
		break;
	    case 't':
	    	/* Just test primality, don't factorize */
	    	test_only = 1;
	    	break;
	    case 160:
	    	/* Small divisors */
	    	tloops = atoi(optarg);
	    	break;
	    case 161:
	    	/* Pseudo-primality tests */
	    	pptests = atoi(optarg);
	    	break;
	    case 162:
	    	/* Maximum number of loops in Pollard's method */
	    	max_pollard = atoi(optarg);
	    	break;
	    case 'm':
	    	/* Mail to me */
	    	get_username();
	    	mailaddr = username;
	    	break;
	    case 170:
	    	/* Mail to somebody else */
	    	get_username();
	    	mailaddr = optarg;
	    	break;
	    case 171:
	    	/* Don't fork */
	    	dont_fork = 1;
	    	break;
	    case 172:
	    	/* Help */
	    	printf(Usage, progname);
	    	return 0;
	    case 173:
	    	/* Version number */
	    	fputs(Copyright, stdout);
	    	return 0;
	    case 183:
	    	/* The number of primes in MPQS */
	    	mpqs_primes = atoi(optarg);
	    	break;
	    case 184:
	    	/* The tolerance exponent T in MPQS (scaled) */
	    	mpqs_exponent = atoi(optarg);
	    	break;
	    case 185:
	    	/* The length 2*M of the sieve interval */
	    	mpqs_width = atoi(optarg);
	    	break;
	    case 186:
	    	/* Output file for debugging */
	    	mpqs_debug_file = optarg;
	    	break;
	    default:
	    	/* Invalid option */
	    	fprintf(stderr, Usage, progname);
	    	return 1;
	}
	/*
	 * If there are remaining elements on the command line, we
	 * interpret them as the numbers to factorise. Otherwise, we
	 * read numbers from standard input.
	 */
	if (optind < argc) {
		if (mailaddr)
			goto_background();
		for ( ; optind < argc; optind++)
			mail_number(argv[optind]);
	} else {
		grs = new_gr_string(0);
		while ((c = getchar()) != EOF) {
			if (isspace(c))
				continue;
			do {
				grs = grs_append1(grs, c);
				c = getchar();
			} while (c != EOF && !isspace(c));
			grs = grs_append1(grs, '\0');
			process_number(grs->s);
			grs->len = 0;
		}
	}
	return 0;
}