#include "platform.h"
#include "mp.h"

#define between(x,min,max)	(((min-1-x) & (x-max-1))>>8)

static int
enc32chr(int o)
{
	int c;

	c  = between(o,  0, 25) & ('A'+o);
	c |= between(o, 26, 31) & ('2'+(o-26));
	return c;
}

static int
enc32x(char *dest, int ndest, const u8int *src, int nsrc, int (*chr)(int))
{
	char *start;
	int j;

	if(ndest <= (8*nsrc+4)/5)
		return -1;
	start = dest;
	while(nsrc>=5){
		j = (0x1f & (src[0]>>3));
		*dest++ = chr(j);
		j = (0x1c & (src[0]<<2)) | (0x03 & (src[1]>>6));
		*dest++ = chr(j);
		j = (0x1f & (src[1]>>1));
		*dest++ = chr(j);
		j = (0x10 & (src[1]<<4)) | (0x0f & (src[2]>>4));
		*dest++ = chr(j);
		j = (0x1e & (src[2]<<1)) | (0x01 & (src[3]>>7));
		*dest++ = chr(j);
		j = (0x1f & (src[3]>>2));
		*dest++ = chr(j);
		j = (0x18 & (src[3]<<3)) | (0x07 & (src[4]>>5));
		*dest++ = chr(j);
		j = (0x1f & (src[4]));
		*dest++ = chr(j);
		src  += 5;
		nsrc -= 5;
	}
	if(nsrc){
		j = (0x1f & (src[0]>>3));
		*dest++ = chr(j);
		j = (0x1c & (src[0]<<2));
		if(nsrc == 1)
			goto out;
		j |= (0x03 & (src[1]>>6));
		*dest++ = chr(j);
		j = (0x1f & (src[1]>>1));
		*dest++ = chr(j);
		j = (0x10 & (src[1]<<4));
		if(nsrc == 2)
			goto out;
		j |= (0x0f & (src[2]>>4));
		*dest++ = chr(j);
		j = (0x1e & (src[2]<<1));
		if(nsrc == 3)
			goto out;
		j |= (0x01 & (src[3]>>7));
		*dest++ = chr(j);
		j = (0x1f & (src[3]>>2));
		*dest++ = chr(j);
		j = (0x18 & (src[3]<<3));
out:
		*dest++ = chr(j);
	}
	*dest = 0;
	return dest-start;
}

int
enc32(char *dest, int ndest, const u8int *src, int nsrc)
{
	return enc32x(dest, ndest, src, nsrc, enc32chr);
}

static int
toencx(mpint *b, char *buf, int len, int (*enc)(char*, int, const u8int*, int))
{
	u8int *p;
	int n, rv;

	p = nil;
	n = mptobe(b, nil, 0, &p);
	if(n < 0)
		return -1;
	rv = enc(buf, len, p, n);
	MEM_FREE(p);
	return rv;
}

static int
topow2(mpint *b, char *buf, int len, int s)
{
	mpdigit *p, x;
	int i, j, sn;
	char *out, *eout;

	if(len < 1)
		return -1;

	sn = 1<<s;
	out = buf;
	eout = buf+len;
	for(p = b->p+b->top-1; p >= b->p; p--){
		x = *p;
		for(i = Dbits-s; i >= 0; i -= s){
			j = x >> i & (sn - 1);
			if(j != 0 || out != buf){
				if(out >= eout)
					return -1;
				*out++ = enc16chr(j);
			}
		}
	}
	if(out == buf)
		*out++ = '0';
	if(out >= eout)
		return -1;
	*out = 0;
	return 0;
}

static char *
modbillion(int rem, u32int r, char *out, char *buf)
{
	u32int rr;
	int i;

	for(i = 0; i < 9; i++){
		rr = r%10;
		r /= 10;
		if(out <= buf)
			return nil;
		*--out = '0' + rr;
		if(rem == 0 && r == 0)
			break;
	}
	return out;
}

static int
to10(mpint *b, char *buf, int len)
{
	mpint *d, *r, *billion;
	char *out;

	if(len < 1)
		return -1;

	d = mpcopy(b);
	d->flags &= ~MPtimesafe;
	mpnorm(d);
	r = mpnew(0);
	billion = uitomp(1000000000, nil);
	out = buf+len;
	*--out = 0;
	do {
		mpdiv(d, billion, d, r);
		out = modbillion(d->top, r->p[0], out, buf);
		if(out == nil)
			break;
	} while(d->top != 0);
	mpfree(d);
	mpfree(r);
	mpfree(billion);

	if(out == nil)
		return -1;
	len -= out-buf;
	if(out != buf)
		memmove(buf, out, len);
	return 0;
}

static int
to8(mpint *b, char *buf, int len)
{
	mpdigit x, y;
	char *out;
	u32int j;
	int i;

	if(len < 2)
		return -1;

	out = buf+len;
	*--out = 0;

	i = j = 0;
	x = y = 0;
	while(j < b->top){
		y = b->p[j++];
		if(i > 0)
			x |= y << i;
		else
			x = y;
		i += Dbits;
		while(i >= 3){
Digout:
			i -= 3;
			if(out > buf)
				out--;
			else if(x != 0)
				return -1;
			*out = '0' + (x & 7);
			if((Dbits-i) >= 64)
				x = 0;
			else
				x = y >> (Dbits-i);
		}
	}
	if(i > 0)
		goto Digout;

	while(*out == '0') out++;
	if(*out == '\0')
		*--out = '0';

	len -= out-buf;
	if(out != buf)
		memmove(buf, out, len);
	return 0;
}

char *
mptoa(mpint *b, int base, char *buf, int len)
{
	bool alloced;
	char *out;
	int rv;

	if(base == 0)
		base = 16;	/* default */
	alloced = false;
	if(buf == nil){
		/* rv <= log₂(base) */
		for(rv=1; (base >> rv) > 1; rv++)
			;
		len = 10 + (b->top*Dbits / rv);
		buf = MEM_ALLOC(len);
		if(buf == nil)
			return nil;
		alloced = true;
	}

	if(len < 2)
		goto leave;

	out = buf;
	if(b->sign < 0){
		*out++ = '-';
		len--;
	}
	switch(base){
	case 32:
		rv = toencx(b, out, len, enc32);
		break;
	case 16:
		rv = topow2(b, out, len, 4);
		break;
	case 10:
		rv = to10(b, out, len);
		break;
	case 8:
		rv = to8(b, out, len);
		break;
	case 4:
		rv = topow2(b, out, len, 2);
		break;
	case 2:
		rv = topow2(b, out, len, 1);
		break;
	default:
		abort();
	}
	if(rv < 0){
leave:
		if(alloced)
			MEM_FREE(buf);
		return nil;
	}
	return buf;
}