/*-
# X-BASED ABACUS
#
#  AbacusM.c
#
###
#
#  Copyright (c) 1994 - 2007	David Albert Bagley, bagleyd@tux.org
#
#                   All Rights Reserved
#
#  Permission to use, copy, modify, and distribute this software and
#  its documentation for any purpose and without fee is hereby granted,
#  provided that the above copyright notice appear in all copies and
#  that both that copyright notice and this permission notice appear in
#  supporting documentation, and that the name of the author not be
#  used in advertising or publicity pertaining to distribution of the
#  software without specific, written prior permission.
#
#  This program is distributed in the hope that it will be "useful",
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
#
*/

/* Methods string math file for Abacus */

/* What fancy mathematics could be here?
   Well, whenever possible math here is done with strings.
   (Roman math is limited by definition.)
   I use long long when I can't figure out how to do it by
   strings, as in Display Base.
 */

#include "AbacusP.h"

#define LONGEST_ROMANNUMERAL "mmmdccclxxxvMMMDCCCLXXXVIII" /* 3,888,888 */
#define MAX_ROMANNUMERAL 3999999
#define MAX_ROMANDIGIT 1000000
#define ROMANFRACTIONBASE 12

static char roman[] =
{
	'I', 'V', 'X', 'L', 'C', 'D', 'M',
	     'v', 'x', 'l', 'c', 'd', 'm'
/* Here we have lower case to represent the letters with bars on top.
   Pardon the non-standard notation (case historically was ignored).
   Think of it as room to add the line by hand... :)
_
V = v,
_
X = x, etc
It has been suggested to put more bars on top for bigger numbers
but there is no recorded usage of a larger Roman numeral in
Roman times.
An older notation for Roman numerals was represented thus:
( = C, I) = D, (I) = M, I)) = v, ((I)) = x, I))) = l, (((I))) = c,
 _
|X| = m
Fractions
12 ounces (uncia) in a as
S = 1/2 ounce
) = 1/4 ounce
Z = 1/12 ounce
*/
};

#define MAX_TWELFTH 9
#define MAX_SUBTWELFTH 18
#define MAX_SUBEIGHTH 18
#define MAX_ROMANFRACT 36 /* MAX_TWELFTH+MAX_SUBTWELFTH+strlen(HALF_UNCIA) */
#define MAX_ROMANLEN 28 /* strlen(LONGEST_ROMANNUMERAL) */
#define MAX_ROMAN (MAX_ROMANFRACT+MAX_ROMANLEN)
static char twelfthStrings[][MAX_TWELFTH] = {
	"", "uncia", "sextans", "quadrans",
	"triens", "quincunx", "semis", "septunx",
	"bes", "dodrans", "dextans", "deunix",
	"as"};
static char twelfthGlyphs[][5] = {
	"", "-", "=", "=-",
	"==", "==-", "S", "S-",
	"S=", "S=-", "S==", "S==-",
	"|"};

#define HALF_UNCIA "semuncia" /* E, (actually a Greek letter sigma) */
#define ONEANDAHALF_UNCIA "sescuncia" /* E- */
static char halftwelfthStrings[][10] = {
	HALF_UNCIA, ONEANDAHALF_UNCIA};
static char halftwelfthGlyphs[][3] = {
	"E", "E-"};

/* Fractions of Uncia had these names, took shortest variant */
#define TWELFTH_UNCIA "semisextula" /*  z (actually, a "Z" with a "-" through
  the middle) AKA dimidia sextula, dimidio sextula */
#define SIXTH_UNCIA "sextula" /* Z */
#define QUARTER_UNCIA "sicilicus" /* Q (a ")" may be better but more like a
  backwards C */
#define THIRD_UNCIA "duella" /* (actually a Greek letter mu), AKA
  binae sextulae */
#define FIVETWELFTHS_UNCIA "sicilicus sextula" /* not sure if this is best
  representation */
#define EIGHTH_UNCIA "drachma"
#define THREEEIGHTHS_UNCIA "sicilicus drachma" /* not sure if this is best
  representation */
/* Combining fractions (not sure how this was done in practice
   but this seems reasonable). Combine with the representation
   for HALF_UNCIA or ONEANDAHALF_UNCIA as required. */
static char subtwelfthStrings[][MAX_SUBTWELFTH] = {
	"", TWELFTH_UNCIA, SIXTH_UNCIA,
	QUARTER_UNCIA, THIRD_UNCIA, FIVETWELFTHS_UNCIA};
static char subeighthStrings[][MAX_SUBEIGHTH] = {
	"", EIGHTH_UNCIA, QUARTER_UNCIA, THREEEIGHTHS_UNCIA};
static char subtwelfthGlyphs[][3] = {
	"", "z", "Z",
	"Q", "u", "QZ"};
static char subeighthGlyphs[][3] = {
	"", "t", "Q", "Qt"};

#ifdef HAVE_LONG_LONG
#define LONG unsigned long long
#else
#define LONG unsigned long
#endif

int
char2Int(char character)
{
	if (character >= '0' && character <= '9') {
		character += 0 - '0';
	/* ASCII or EBCDIC */
	} else if (character >= 'a' && character <= 'i') {
		character += 10 - 'a';
	} else if (character >= 'j' && character <= 'r') {
		character += 19 - 'j';
	} else if (character >= 's' && character <= 'z') {
		character += 28 - 's';
	} else if (character >= 'A' && character <= 'I') {
		character += 10 - 'A';
	} else if (character >= 'J' && character <= 'R') {
		character += 19 - 'J';
	} else if (character >= 'S' && character <= 'Z') {
		character += 28 - 'S';
	} else
		character = 36;
	return character;
}

char
int2Char(int digit)
{
	digit += '0';
	/* ASCII or EBCDIC */
	if (digit > '9' || digit < '0') {
		digit += ('A' - '9' - 1);
		if (digit > 'I')
			digit += ('J' - 'I' - 1);
		if (digit > 'R')
			digit += ('S' - 'R' - 1);
	}
	return ((char) digit);
}

static int
int2String(char *buf, LONG number, int base, Boolean negative)
{
	int digit, last, position = 0, i;
	LONG mult = 1;

	last = 1;
	while (number >= mult * base) {
		mult *= base;
		last++;
		if (mult > mult * base) {
			buf[0] = '\0';
			return 0;
		}
	}
	if (negative) {
		buf[position] = '-';
		position++;
	}
	for (i = 0; i < last; i++) {
		digit = (int) (number / mult);
		number -= mult * digit;
		buf[position] = int2Char(digit);
		mult /= base;
		if (mult == 0 && i != last - 1) {
			buf[0] = '\0';
			return 0;
		}
		position++;
	}
	buf[position] = '\0';
	return last;
}

static int
flt2String(char *buf, LONG number, int abacusBase, int base, int places,
		int decimalPosition)
{
	int position = 0, digit;
	double mult = 1.0 / base;
	double fraction = number;

	for (position = 0; position < places; position++) {
		fraction /= abacusBase;
	}
	for (position = 0; position < decimalPosition; position++) {
		digit = (int) (fraction / mult);
		fraction -= mult * digit;
		buf[position] = int2Char(digit);
		mult /= base;
		if (mult == 0 && position != places - 1) {
			buf[0] = '\0';
			return 0;
		}
	}
	buf[position] = '\0';
	for (digit = position - 1; digit > 0; digit--) {
		if (buf[digit] == '0')
			buf[digit] = '\0';
		else
			break;
	}
	return places;
}

#if 0
int
string2Int(char *buf, int base)
{
	int digit, position = 0, value = 0, last;

	if (buf[position] == '-') {
		return 0;
	}
	last = strlen(buf);
	for (; position < last; position++) {
		if (buf[position] == '.') {
			break;
		}
		digit = char2Int(buf[position]);
		value = value * base + digit;
		if (value >= ((base >= 8) ? base / 2 - 1 : base) *
				base * base * base * base * base * base)
			return 0;
	}
	return value;
}
#endif

/* Try not to use since this restricts the size of abacus. */
static LONG power(int x, int n)
{				/* raise x to the nth power n >= 0 */
	int i;
	LONG p = 1;

	for (i = 1; i <= n; ++i)
		p *= ((LONG) x);
	return p;
}

/* This is fast for small i, a -1 is returned for negative i. */
static int
squareroot(int i)
{
	int j = 0;

	while (j * j <= i)
		j++;
	return (j - 1);
}

void
dividePieces(char *buf, int base, int pieces, int mult, int places)
{
	int position, digit, inter;

#ifdef DEBUG
	(void) printf("dividePieces: base %d, pieces %d, mult %d, places %d\n",
		base, pieces, mult, places);
#endif
	digit = mult / pieces;
	inter = mult % pieces;
	(void) sprintf(buf, "%1d.", digit);
	for (position = 2; position < places;) {
		digit = (inter * base) / pieces;
		inter = (inter * base) % pieces;
		buf[position] = int2Char(digit);
		position++;
		if (inter == 0)
			break;
	}
	buf[position] = '\0';
#ifdef DEBUG
	(void) printf("dividePieces: buf %s\n", buf);
#endif
}

void
shiftDecimal(char *buf, char *aBuf, int shift, int place)
{
	int size = strlen(aBuf);
	int loc = 0, i = 0, integerDigits;

#ifdef DEBUG
	(void) printf("shiftDecimal: aBuf %s, shift %d, place %d\n", aBuf,
		shift, place);
#endif
	while (aBuf[i] != '.' && i < size) {
		buf[i] = aBuf[i];
		i++;
	}
	integerDigits = i;
	buf[i] = aBuf[i];
	loc = i;
	i++;
	while (i - 1 < place + integerDigits && i < size) {
		buf[i] = aBuf[i];
		i++;
	}
	loc = i - 1;
	if (shift > 0) {
		/* shift right */
		for (i = place + 2; i < shift + place + 2; i++)
			buf[i] = '0';
	} else {
		/* shift left */
		loc -= shift;
	}
	while (loc < size - 1) {
		loc++;
		buf[i] = aBuf[loc];
		i++;
	}
	buf[i] = '\0';
#ifdef DEBUG
	(void) printf("shiftDecimal: buf %s\n", buf);
#endif
}

/* 2nd grade math made hard */
/* May disregard sign if different */
void
addStrings(char *buf, char *aBuf, char *bBuf, int base)
{
	int aEnd = strlen(aBuf), bEnd = strlen(bBuf); /* zeros included */
	int aDecimal = aEnd, bDecimal = bEnd;
	int aSign = ((aBuf[0] == '-') ? 1 : 0);
	int bSign = ((bBuf[0] == '-') ? 1 : 0);
	int i, carry = 0, digit;

#ifdef DEBUG
	(void) printf("addStrings: aBuf %s, bBuf %s, base %d\n", aBuf, bBuf, base);
#endif
	for (i = 0; i < aEnd; i++) {
		if (aBuf[i] == '.' && aDecimal == aEnd) {
			aDecimal = i;
			break;
		}
	}
	for (i = 0; i < bEnd; i++) {
		if (bBuf[i] == '.' && bDecimal == bEnd) {
			bDecimal = i;
			break;
		}
	}
	if (bEnd - bDecimal < aEnd - aDecimal) {
		for (i = 0; i < aEnd - bEnd - aDecimal + bDecimal; i++)
			bBuf[bEnd + i] = '0';
		bEnd += i;
		bBuf[bEnd] = '\0';
	}
	if (bEnd - bDecimal > aEnd - aDecimal) {
		for (i = 0; i < bEnd - aEnd - bDecimal + aDecimal; i++)
			aBuf[aEnd + i] = '0';
		aEnd += i;
		aBuf[aEnd] = '\0';
	}
	if (aDecimal + aSign >= bDecimal + bSign) {
		for (i = aEnd - 1; i > aDecimal; i--) {
			digit = char2Int(aBuf[i]) +
				char2Int(bBuf[i - aEnd + bEnd]) + carry;
			aBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		for (i = aDecimal - 1; i >= aSign ; i--) {
			digit = char2Int(aBuf[i]) +
				((i - aEnd + bEnd >= bSign) ?
				char2Int(bBuf[i - aEnd + bEnd]) : 0) + carry;
			aBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		if (aSign == 1) {
			buf[0] = '-';
			buf[1] = '\0';
		}
		if (carry > 0) {
			buf[aSign] = (char) (carry + '0');
			(void) strcpy(&buf[aSign + 1], &aBuf[aSign]);
		} else
			(void) strcpy(buf, aBuf);
	} else {
		for (i = bEnd - 1; i > bDecimal; i--) {
			digit = char2Int(bBuf[i]) +
				char2Int(aBuf[i - bEnd + aEnd]) + carry;
			bBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		for (i = bDecimal - 1; i >= bSign ; i--) {
			digit = char2Int(bBuf[i]) +
				((i - bEnd + aEnd >= aSign) ?
				char2Int(aBuf[i - bEnd + aEnd]) : 0) + carry;
			bBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		if (bSign == 1) {
			buf[0] = '-';
			buf[1] = '\0';
		}
		if (carry > 0) {
			buf[bSign] = (char) (carry + '0');
			(void) strcpy(&buf[bSign + 1], &bBuf[bSign]);
		} else
			(void) strcpy(buf, bBuf);
	}
	i = strlen(buf) - 1;
	while (buf[i] == '0' && buf[i - 1] != '.')
		i--;
	buf[i + 1] = '\0';
#ifdef DEBUG
	(void) printf("addStrings: buf %s\n", buf);
#endif
}

void
convertString(char * buf, char * inbuf, int base, int displayBase,
		int decimalPosition,
		int anomaly, int shiftAnomaly, Boolean carryAnomaly,
		int anomalySq, int shiftAnomalySq, Boolean carryAnomalySq)
{
	char fltbuf[256];
	int i, last, place = -1, decimalPlace, decimalPointPlace;
	Boolean negative, gotDecimal = False;
	LONG intPart = 0, floatPart = 0;

	last = strlen(inbuf);
	negative = (inbuf[0] == '-');
	for (i = (negative) ? 1 : 0; i < last; i++) {
		if (inbuf[i] == '.') {
			place = i - 1 - ((negative) ? 1 : 0);
			break;
		}
	}
	if (place == -1)
		place = last - 1 - ((negative) ? 1 : 0);
	decimalPlace = place;
	decimalPointPlace = last - 2 - ((negative) ? 1 : 0) - place;
	for (i = (negative) ? 1 : 0; i < last; i++) {
		if (inbuf[i] == '.') {
			gotDecimal = True;
			place = last - decimalPlace - 2 - ((negative) ? 1 : 0);
			floatPart = 0;
			place--;
		} else if (gotDecimal) {
			floatPart += (((LONG) power(base, place)) *
				char2Int(inbuf[i]));
			place--;
		} else {
			if (place >= shiftAnomaly && anomaly != 0) {
			  if (place >= shiftAnomaly + shiftAnomalySq &&
						anomalySq != 0)
			    intPart += (((LONG) power(base, place - 2))) *
				char2Int(inbuf[i]) * (base - anomaly) *
				(base - anomalySq) + ((carryAnomalySq &&
				place == shiftAnomaly + shiftAnomalySq) ?
				(base - anomaly) * anomalySq * power(base,
				shiftAnomaly + shiftAnomalySq - 2) : 0);
			  else
			    intPart += (((LONG) power(base, place - 1))) *
				char2Int(inbuf[i]) * (base - anomaly) +
				((carryAnomaly && place == shiftAnomaly) ?
				anomaly * power(base, shiftAnomaly - 1) : 0);
			} else
			  intPart += (((LONG) power(base, place)) *
			      char2Int(inbuf[i]));
			place--;
		}
	}
	(void) int2String(buf, intPart, displayBase, negative);
	(void) flt2String(fltbuf, floatPart, base, displayBase,
		decimalPointPlace, decimalPosition);
	(void) sprintf(buf, "%s.%s", buf, fltbuf);
}

int
sizeofRoman(int base, Boolean romanNumerals)
{
	int romanWidth = ((base < 8) ? base : base / 2 - 1);

	return ((romanNumerals) ? ((sizeof(roman) + 1) / 2) *
		romanWidth + 12 + MAX_ROMANFRACT: 0);
}

static void
romanFraction(char *buf, int base, int fraction, int subfraction,
		int subbase, Boolean latin)
{
	Boolean gotFraction = False;
	int halfBase = subbase / 2;

	fraction %= base;
	if (fraction == 1 && subfraction >= halfBase) {
		subfraction -= halfBase;
		if (latin) {
			(void) strcat(buf, halftwelfthStrings[1]);
			gotFraction = True;
		} else {
			(void) strcat(buf, halftwelfthGlyphs[1]);
		}
	} else if (fraction > 0) {
		if (latin) {
			(void) strcat(buf, twelfthStrings[fraction *
				ROMANFRACTIONBASE / base]);
			gotFraction = True;
		} else {
			(void) strcat(buf, twelfthGlyphs[fraction *
				ROMANFRACTIONBASE / base]);
		}
	}
	if (subfraction >= halfBase) {
		subfraction -= halfBase;
		if (latin) {
			if (gotFraction)
				(void) strcat(buf, " ");
			gotFraction = True;
			(void) strcat(buf, halftwelfthStrings[0]);
		} else {
			(void) strcat(buf, halftwelfthGlyphs[0]);
		}
	}
	if (subfraction != 0) {
		if (latin) {
			if (gotFraction)
				(void) strcat(buf, " ");
			if (subbase == 8)
				(void) strcat(buf, subeighthStrings[subfraction]);
			else
				(void) strcat(buf, subtwelfthStrings[subfraction]);
		} else {
			if (subbase == 8)
				(void) strcat(buf, subeighthGlyphs[subfraction]);
			else
				(void) strcat(buf, subtwelfthGlyphs[subfraction]);
		}
	}
}

int
string2Roman(char *buf, char *inbuf, int base,
		int pieces, int number, int subnumber, int subbase)
{
	int i = 0, position = 0, digit, last, j;
	int loga = (sizeof(roman) + 1) / 2;

	buf[position] = '[';
	position++;
	if (inbuf[i] == '-') {
		buf[position] = ']';
		position++;
		buf[position] = '\0';
		return 0;
	}
	last = strlen(inbuf);
	for (i = 0; i < last; i++) {
		if (inbuf[i] == '.') {
			break;
		}
	}
	last = i;
	i = 0;
	digit = char2Int(inbuf[i]);
	if (last > loga || (last == loga &&
			digit >= ((base >= 8) ? base / 2 - 1 : base))) {
		buf[position] = '?';
		position++;
		buf[position] = ']';
		position++;
		buf[position] = '\0';
		return 0;
	}
	for (i = 0; i < last; i++) {
		digit = char2Int(inbuf[i]);
		/* IX */
		if (digit >= base + 1 - base / 4 && base >= 8) {
			for (j = 0; j < base - digit; j++) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
			}
			buf[position] = roman[2 * (last - i)];
			position++;
		/* VI */
		} else if (digit >= (base + 1) / 2 && base >= 4) {
			buf[position] = roman[2 * (last - i) - 1];
			position++;
			digit = digit - (base + 1) / 2;
			while (digit > 0) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
				digit--;
			}
		/* IV */
		} else if (digit >= (base + 1) / 2 + 1 - base / 4 &&
				base >= 8) {
			for (j = 0; j < (base + 1) / 2 - digit; j++) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
			}
			buf[position] = roman[2 * (last - i) - 1];
			position++;
		/* I */
		} else {
			while (digit > 0) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
				digit--;
			}
		}
	}
	buf[position] = '\0';
	if (pieces > 0 && ROMANFRACTIONBASE % pieces == 0) {
		char fractbuf[MAX_ROMANFRACT] = "";
		Boolean latin = False;

		if (pieces != ROMANFRACTIONBASE)
			subnumber = 0; /* words not scalable */
		if (latin) {
			if (position > 1 && (number != 0 || subnumber != 0))
				(void) strcat(buf, " ");
		}
		romanFraction(fractbuf, pieces, number, subnumber,
			subbase, latin);
		(void) strcat(buf, fractbuf);
	}
	(void) strcat(buf, "]");
	return 0;
}

#if 0
int
int2Roman(char *buf, int arabic)
{
	int i = 0, position = 0, digit;
	int loga = (sizeof(roman) + 1) / 2;
	int place = MAX_ROMANDIGIT;
	int base = DEFAULTBASE;

	buf[position] = '[';
	position++;
	if (arabic < 0 || arabic > MAX_ROMANNUMERAL) {
		buf[position] = ']';
		position++;
		buf[position] = '\0';
		return 0;
	}
	for (i = 0; i < loga; i++) {
		digit = arabic / place;
		arabic = arabic - digit * place;
		if (digit >= base - 1) {
			buf[position] = roman[2 * (loga - i - 1)];
			position++;
			buf[position] = roman[2 * (loga - i)];
			position++;
		} else if (digit >= (base + 1) / 2) {
			buf[position] = roman[2 * (loga - i) - 1];
			position++;
			digit = digit - (base + 1) / 2;
			while (digit > 0) {
				buf[position] = roman[2 * (loga - i - 1)];
				position++;
				digit--;
			}
		} else if (digit >= (base + 1) / 2 - 1) {
			buf[position] = roman[2 * (loga - i - 1)];
			position++;
			buf[position] = roman[2 * (loga - i) - 1];
			position++;
		} else {
			while (digit > 0) {
				buf[position] = roman[2 * (loga - i - 1)];
				position++;
				digit--;
			}
		}
		place /= base;
	}
	buf[position] = ']';
	position++;
	buf[position] = '\0';
	return 0;
}
#endif

void string2Group(char *buf, char *inbuf, int groupSize) {
	int i, j, len;

	for (i = 0; i < (int) strlen(inbuf); i++) {
		if (inbuf[i] == ' ' || inbuf[i] == '.') {
			break;
		}
	}
	len = i;
	j = 0;
	if (inbuf[j] == '-' || inbuf[j] == '+' ) {
		buf[j] = inbuf[0];
		j = 1;
	}
	for (i = j; i < len - 1; i++) {
		buf[j] = inbuf[i];
		if ((len - i + groupSize - 1) % groupSize == 0) {
			j++;
			buf[j] = ',';
		}
		j++;
	}
	buf[j] = '\0';
	(void) sprintf(buf, "%s%s", buf, &inbuf[len - 1]);
}

int
baseToBottom(int base)
{
	int j;

	for (j = squareroot(base); j > 1; j--) {
		if (base % j == 0) {
			return (base / j);
		}
	}
	return base;
}