libmp: support for c-style base prefixes for strtomp(), octal support

5 files changed, 196 insertions, 101 deletions

diff --git a/sys/man/2/mp b/sys/man/2/mp
index c562ccab4..182bca7e2 100644
--- a/sys/man/2/mp
+++ b/sys/man/2/mp
@@ -337,13 +337,22 @@ convert between
 and
 .B mpint
 representations using the base indicated.
-Only the bases 10, 16, 32, and 64 are
-supported.  Anything else defaults to 16.
+Only the bases 2, 4, 8, 10, 16, 32, and 64 are
+supported.  Base 0 defaults to 16.
 .IR Strtomp
 skips any leading spaces or tabs.
 .IR Strtomp 's
 scan stops when encountering a digit not valid in the
 base.  If
+.I base
+is zero then C-style prefixes are interpreted to
+find the base:
+.B 0x
+for hexadecimal,
+.B 0b
+for binary and
+.B 0
+for octal. Otherwise decimal is assumed.
 .I rptr
 is not zero,
 .I *rptr
diff --git a/sys/src/libmp/bigtest.c b/sys/src/libmp/bigtest.c
index 4650916e1..92806c198 100644
--- a/sys/src/libmp/bigtest.c
+++ b/sys/src/libmp/bigtest.c
@@ -52,7 +52,7 @@ main(int argc, char **argv)
 	int i;
 
 	start = time(0);
-	fmtinstall('B', mpconv);
+	fmtinstall('B', mpfmt);
 	mpsetminbits(2*Dbits);
 
 	x = mpnew(0);
diff --git a/sys/src/libmp/port/mpfmt.c b/sys/src/libmp/port/mpfmt.c
index 3e18a8cf1..8f9e5502d 100644
--- a/sys/src/libmp/port/mpfmt.c
+++ b/sys/src/libmp/port/mpfmt.c
@@ -4,7 +4,7 @@
 #include "dat.h"
 
 static int
-to64(mpint *b, char *buf, int len)
+toencx(mpint *b, char *buf, int len, int (*enc)(char*, int, uchar*, int))
 {
 	uchar *p;
 	int n, rv;
@@ -13,30 +13,7 @@ to64(mpint *b, char *buf, int len)
 	n = mptobe(b, nil, 0, &p);
 	if(n < 0)
 		return -1;
-	rv = enc64(buf, len, p, n);
-	free(p);
-	return rv;
-}
-
-static int
-to32(mpint *b, char *buf, int len)
-{
-	uchar *p;
-	int n, rv;
-
-	// leave room for a multiple of 5 buffer size
-	n = b->top*Dbytes + 5;
-	p = malloc(n);
-	if(p == nil)
-		return -1;
-	n = mptobe(b, p, n, nil);
-	if(n < 0)
-		return -1;
-
-	// round up buffer size, enc32 only accepts a multiple of 5
-	if(n%5)
-		n += 5 - (n%5);
-	rv = enc32(buf, len, p, n);
+	rv = (*enc)(buf, len, p, n);
 	free(p);
 	return rv;
 }
@@ -103,6 +80,7 @@ to10(mpint *b, char *buf, int len)
 		return -1;
 
 	d = mpcopy(b);
+	d->flags &= ~MPtimesafe;
 	mpnorm(d);
 	r = mpnew(0);
 	billion = uitomp(1000000000, nil);
@@ -126,32 +104,89 @@ to10(mpint *b, char *buf, int len)
 	return 0;
 }
 
+static int
+to8(mpint *b, char *buf, int len)
+{
+	mpdigit x, y;
+	char *out;
+	int i, j;
+
+	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);
+			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;
+}
+
 int
 mpfmt(Fmt *fmt)
 {
 	mpint *b;
-	char *p, f;
+	char *x, *p;
+	int base;
 
 	b = va_arg(fmt->args, mpint*);
 	if(b == nil)
 		return fmtstrcpy(fmt, "*");
 
-	f = b->flags;
-	b->flags &= ~MPtimesafe;
-
-	p = mptoa(b, fmt->prec, nil, 0);
+	base = fmt->prec;
+	if(base == 0)
+		base = 16;	/* default */
 	fmt->flags &= ~FmtPrec;
-
-	b->flags = f;
-
+	p = mptoa(b, base, nil, 0);
 	if(p == nil)
 		return fmtstrcpy(fmt, "*");
 	else{
-		if((fmt->flags & FmtSharp) != 0 && fmt->prec!=10 && fmt->prec!=32 && fmt->prec!=64)
+		if((fmt->flags & FmtSharp) != 0){
+			switch(base){
+			case 16:
+				x = "0x";
+				break;
+			case 8:
+				x = "0";
+				break;
+			case 2:
+				x = "0b";
+				break;
+			default:
+				x = "";
+			}
 			if(*p == '-')
-				fmtprint(fmt, "-0x%s", p + 1);
+				fmtprint(fmt, "-%s%s", x, p + 1);
 			else
-				fmtprint(fmt, "0x%s", p);
+				fmtprint(fmt, "%s%s", x, p);
+		}
 		else
 			fmtstrcpy(fmt, p);
 		free(p);
@@ -165,9 +200,14 @@ mptoa(mpint *b, int base, char *buf, int len)
 	char *out;
 	int rv, alloced;
 
+	if(base == 0)
+		base = 16;	/* default */
 	alloced = 0;
 	if(buf == nil){
-		len = ((b->top+1)*Dbits+2)/3 + 1;
+		/* rv <= log₂(base) */
+		for(rv=1; (base >> rv) > 1; rv++)
+			;
+		len = 10 + (b->top*Dbits / rv);
 		buf = malloc(len);
 		if(buf == nil)
 			return nil;
@@ -184,24 +224,29 @@ mptoa(mpint *b, int base, char *buf, int len)
 	}
 	switch(base){
 	case 64:
-		rv = to64(b, out, len);
+		rv = toencx(b, out, len, enc64);
 		break;
 	case 32:
-		rv = to32(b, out, len);
+		rv = toencx(b, out, len, enc32);
 		break;
-	default:
 	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();
+		return nil;
 	}
 	if(rv < 0){
 		if(alloced)
diff --git a/sys/src/libmp/port/strtomp.c b/sys/src/libmp/port/strtomp.c
index 59c7dd76b..b5e00f0ef 100644
--- a/sys/src/libmp/port/strtomp.c
+++ b/sys/src/libmp/port/strtomp.c
@@ -53,11 +53,13 @@ frompow2(char *a, mpint *b, int s)
 
 	sn = 1<<s;
 	for(p = a; *p; p++)
-		if((uchar)tab.t16[*(uchar*)p] >= sn)
+		if(tab.t16[*(uchar*)p] >= sn)
 			break;
-	mpbits(b, (p-a)*4);
+
+	mpbits(b, (p-a)*s);
 	b->top = 0;
 	next = p;
+
 	while(p > a){
 		x = 0;
 		for(i = 0; i < Dbits; i += s){
@@ -70,6 +72,40 @@ frompow2(char *a, mpint *b, int s)
 	return next;
 }
 
+static char*
+from8(char *a, mpint *b)
+{
+	char *p, *next;
+	mpdigit x, y;
+	int i;
+
+	for(p = a; *p; p++)
+		if(tab.t10[*(uchar*)p] >= 8)
+			break;
+
+	mpbits(b, (a-p)*3);
+	b->top = 0;
+	next = p;
+
+	i = 0;
+	x = 0;
+	while(p > a){
+		y = tab.t10[*(uchar*)--p];
+		x |= y << i;
+		i += 3;
+		if(i >= Dbits){
+Digout:
+			i -= Dbits;
+			b->p[b->top++] = x;
+			x = y >> 3-i;
+		}
+	}
+	if(i > 0)
+		goto Digout;
+
+	return next;
+}
+
 static ulong mppow10[] = {
 	1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000
 };
@@ -113,42 +149,25 @@ from10(char *a, mpint *b)
 }
 
 static char*
-from64(char *a, mpint *b)
+fromdecx(char *a, mpint *b, uchar tab[256], int (*dec)(uchar*, int, char*, int))
 {
 	char *buf = a;
 	uchar *p;
 	int n, m;
 
-	for(; tab.t64[*(uchar*)a] != INVAL; a++)
-		;
-	n = a-buf;
-	mpbits(b, n*6);
-	p = malloc(n);
-	if(p == nil)
-		return a;
-	m = dec64(p, n, buf, n);
-	betomp(p, m, b);
-	free(p);
-	return a;
-}
-
-static char*
-from32(char *a, mpint *b)
-{
-	char *buf = a;
-	uchar *p;
-	int n, m;
-
-	for(; tab.t64[*(uchar*)a] != INVAL; a++)
+	b->top = 0;
+	for(; tab[*(uchar*)a] != INVAL; a++)
 		;
 	n = a-buf;
-	mpbits(b, n*5);
-	p = malloc(n);
-	if(p == nil)
-		return a;
-	m = dec32(p, n, buf, n);
-	betomp(p, m, b);
-	free(p);
+	if(n > 0){
+		p = malloc(n);
+		if(p == nil)
+			sysfatal("malloc: %r");
+		m = (*dec)(p, n, buf, n);
+		if(m > 0)
+			betomp(p, m, b);
+		free(p);
+	}
 	return a;
 }
 
@@ -179,6 +198,21 @@ strtomp(char *a, char **pp, int base, mpint *b)
 		break;
 	}
 
+	if(base == 0){
+		if(*a == '0'){
+			a++;
+			if(*a == 'x' || *a == 'X') {
+				a++;
+				base = 16;
+			} else if(*a == 'b' || *a == 'B') {
+				a++;
+				base = 2;
+			} else
+				base = 8;
+		} else
+			base = 10;
+	}
+
 	switch(base){
 	case 2:
 		e = frompow2(a, b, 1);
@@ -187,21 +221,23 @@ strtomp(char *a, char **pp, int base, mpint *b)
 		e = frompow2(a, b, 2);
 		break;
 	case 8:
-		e = frompow2(a, b, 3);
+		e = from8(a, b);
 		break;
 	case 10:
 		e = from10(a, b);
 		break;
-	default:
 	case 16:
 		e = frompow2(a, b, 4);
 		break;
 	case 32:
-		e = from32(a, b);
+		e = fromdecx(a, b, tab.t32, dec32);
 		break;
 	case 64:
-		e = from64(a, b);
+		e = fromdecx(a, b, tab.t64, dec64);
 		break;
+	default:
+		abort();
+		return nil;
 	}
 
 	// if no characters parsed, there wasn't a number to convert
diff --git a/sys/src/libmp/test.c b/sys/src/libmp/test.c
index 50838cf01..2bf8b8bc4 100644
--- a/sys/src/libmp/test.c
+++ b/sys/src/libmp/test.c
@@ -30,34 +30,34 @@ prng(uchar *p, int n)
 void
 testconv(char *str)
 {
+	int i, base[] = {2,8,10,16,32,64};
 	mpint *b;
 	char *p;
 
+	print("testconv \"%s\":\n", str);
 	b = strtomp(str, nil, 16, nil);
 
-	p = mptoa(b, 10, nil, 0);
-	print("%s = ", p);
-	strtomp(p, nil, 10, b);
-	free(p);
-	print("%B\n", b);
-
-	p = mptoa(b, 16, nil, 0);
-	print("%s = ", p);
-	strtomp(p, nil, 16, b);
-	free(p);
-	print("%B\n", b);
-
-	p = mptoa(b, 32, nil, 0);
-	print("%s = ", p);
-	strtomp(p, nil, 32, b);
-	free(p);
-	print("%B\n", b);
-
-	p = mptoa(b, 64, nil, 0);
-	print("%s = ", p);
-	strtomp(p, nil, 64, b);
-	free(p);
-	print("%B\n", b);
+	for(i=0; i<nelem(base); i++){
+		p = mptoa(b, base[i], nil, 0);
+		print("base%d: %s = ", base[i], p);
+		strtomp(p, nil, base[i], b);
+		free(p);
+		print("%B\n", b, base[i], b);
+
+		switch(base[i]){
+		case 2:
+		case 8:
+		case 10:
+		case 16:
+			p = smprint("%#.*B", base[i], b);
+			print("# %s = ", p);
+			strtomp(p, nil, 0, b);
+			free(p);
+			print("%#.*B\n", base[i], b);
+			break;
+		}
+
+	}
 
 	mpfree(b);
 }
@@ -419,6 +419,11 @@ main(int argc, char **argv)
 	testconv("0");
 	testconv("-abc0123456789abcedf");
 	testconv("abc0123456789abcedf");
+	testconv("ffffffff");
+	testconv("aaaaaaaaaaaaaaaaa");
+	testconv("1111111111111111");
+	testconv("33333333333333333333333333333333");
+
 	testvecdigmulsub("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 2);
 	testsub1("1FFFFFFFE00000000", "FFFFFFFE00000001");
 	testmul1("ffffffff", "f");