Ints.v3

// Copyright 2020 Ben L. Titzer. All rights reserved.
// See LICENSE for details of Apache 2.0 license.

// Utilities for rendering and parsing integers in various formats, as well
// as additional arithmetic routines.
component Ints {
	private def U32_0 = u32.view('0');
	// Parse a decimal integer value beginning at {a[pos]}. Returns a
	// pair of the status (# of characters read if successful, <= 0 if failure),
	// and the value.
	def parseDecimal(a: Array<byte>, pos: int) -> (/*status:*/int, /*value:*/int) {
		if (pos >= a.length) return (0, 0);
		if (a[pos] == '-') {
			// parse positive decimal and negate
			var r = parseDecM(a, pos + 1, 214748364, 8);
			if (r.0 > 0) {
				if (r.0 == 1 && r.1 == 0) return (-2, 0); // special case of -0
				return (1 + r.0, int.view(0u - r.1));
			}
			return (r.0 - 1, 0);
		}
		var r = parseDecM(a, pos, 214748364, 7);
		if (r.0 > 0) return (r.0, int.view(r.1));
		return (r.0, 0);
	}
	// Parse a positive decimal integer value beginning at {a[pos]}. Returns a
	// pair of the status (# of characters read if successful, <= 0 if failure),
	// and the value.
	def parsePosDecimal(a: Array<byte>, pos: int) -> (/*status:*/int, /*value:*/u32) {
		return parseDecM(a, pos, 429496729, 6);
	}
	private def parseDecM(a: Array<byte>, pos: int, maxdiv10: u32, maxmod10: u32) -> (int, u32) {
		var val = 0u, s = pos;
		var max = s + 9;
		if (max > a.length) max = a.length;
		// first 9 digits cannot overflow u32
		if (s < max) {
			var d = a[s] - U32_0;
			if (d == 0) return (1, 0);
			if (d > 9) return (s - pos, val);
			s++;
			val = val * 10 + d;
		}
		while (s < max) {
			var d = a[s] - U32_0;
			if (d > 9) return (s - pos, val);
			s++;
			val = val * 10 + d;
		}
		// check for 10th digit
		if (s < a.length) {
			var d = a[s] - U32_0;
			if (d > 9) return (s - pos, val);
			s++;
			// check for value overflow
			if (val > maxdiv10 || (val == maxdiv10 && d > maxmod10)) {
				return (-1 - (s - pos), val);
			}
			val = val * 10 + d;
			// check for 11th and more digit
			if (s < a.length) {
				var d = a[s] - U32_0;
				if (d <= 9) return (-1 - (s - pos), val);
			}
		}
		return (s - pos, val);
	}
	// Parse a hexadecimal integer value prefixed with "0x" or "0X" starting at {a[pos]}.
	def parse0xHex(a: Array<byte>, pos: int) -> (int, u32) {
		if (pos >= a.length - 2) return (-1, 0);
		if (a[pos] != '0') return (-1, 0);
		var x = a[pos + 1];
		if (x != 'x' && x != 'X') return (-2, 0);
		return parseHex0(a, pos + 2, 2);
	}
	// Parse a hexadecimal integer value starting at {a[pos]}.
	def parseHex(a: Array<byte>, pos: int) -> (int, u32) {
		return parseHex0(a, pos, 0);
	}
	// Parse a hexadecimal integer value starting at {a[pos]}.
	private def parseHex0(a: Array<byte>, pos: int, prefix: int) -> (int, u32) {
		var accum = 0u, s = pos;
		while (s < a.length) {
			var ch = a[s];
			if (!Chars.isHex(ch)) break;
			if ((s - pos) >= 8) return (-8 - prefix, 0); // too long
			accum = accum << 4 | u32.view(Chars.hexValue(ch));
			s++;
		}
		var len = s - pos;
		return if(len == 0, (-1 - prefix, 0), (len + prefix, accum));
	}
	// Parse a binary integer value prefixed with "0b" or "0B" starting at {a[pos]}.
	def parse0bBin(a: Array<byte>, pos: int) -> (int, u32) {
		if (pos >= a.length - 2) return (-1, 0);
		if (a[pos] != '0') return (-1, 0);
		var b = a[pos + 1];
		if (b != 'b' && b != 'B') return (-2, 0);
		return parseBin0(a, pos + 2, 2);
	}
	// Parse a binary integer value starting at {a[pos]}.
	def parseBin(a: Array<byte>, pos: int) -> (int, u32) {
		return parseBin0(a, pos, 0);
	}
	private def parseBin0(a: Array<byte>, pos: int, prefix: int) -> (int, u32) {
		var accum = 0u, s = pos;
		while (s < a.length) {
			var ch = a[s], v = ch - '0';
			if ((v & ~1) != 0) break;
			if ((s - pos) >= 32) return (-32 - pos, 0); // too long
			accum = accum << 1 | v;
			s++;
		}
		var len = s - pos;
		return if(len == 0, (-1 - prefix, 0), (len + prefix, accum));
	}

	// Render {val} in decimal at the position {pos} in {a}, returning
	// the number of characters output.
	def renderDecimal(val: int, a: Array<byte>, pos: int) -> int {
		if (val < 0) {
			a[pos++] = '-';
			return 1 + renderPosDecimal(u32.view(0 - val), a, pos);
		}
		return renderPosDecimal(u32.view(val), a, pos);
	}
	// Render {val} in decimal at the position {pos} in {a}, returning
	// the number of characters output.
	def renderPosDecimal(val: u32, a: Array<byte>, pos: int) -> int {
		var p = pos;
		if (val < 10) {  // fastpath for small integers.
			a[p] = byte.view('0' + val);
			return 1;
		}
		if (val < 100) { // fastpath for small integers.
			a[p++] = byte.view('0' + (val / 10));
			a[p++] = byte.view('0' + (val % 10));
			return 2;
		}
		var nonZero = false;
		// XXX(fast): worth it to compute digits low to high? 1 divide vs 2.
		for (radix = 1000000000u; radix > 0; radix = radix / 10) {
			var digit = val / radix;
			val = val % radix;
			if (digit != 0) nonZero = true;
			if (nonZero) a[p++] = byte.view('0' + digit);
		}
		return p - pos;
	}
	// Compute the log of a power of two integer {i}.
	def log(i: u32) -> int {
		var r = 0;
		if (i == 0) return -1;
		if (i >= (1u << 16)) { r += 16; i >>= 16; }
		if (i >= (1u << 8)) { r += 8; i >>= 8; }
		if (i >= (1u << 4)) { r += 4; i >>= 4; }
		if (i >= (1u << 2)) { r += 2; i >>= 2; }
		if (i >= (1u << 1)) { r += 1; i >>= 1; }
		return r;
	}
	// Compute the number of 1 bits in {i}.
	def popcnt(i: u32) -> int { // XXX: intrinsic on platforms where possible.
		var count = 0;
		while (i != 0) {
			if ((i & 1) != 0) count++;
			i >>>= 1;
		}
		return count;
	}
	// Return the minimum of {a} and {b}.
	def min(a: int, b: int) -> int {
		return if(a < b, a, b);
	}
	// Return the absolute value of {a}.
	def abs(a: int) -> u32 {
		return u32.view(if(a < 0, 0 - a, a));
	}
	// Return {true} if {a} is a power of 2.
	def isPowerOf2(a: u32) -> bool {
		return (a & (a - 1)) == 0;
	}
}

// Parse result for parsing integers and longs.
enum IntParseResult(code: int) {
	OK(0),
	OVERFLOW(-1),
	UNDERFLOW(-2),
	TOO_LONG(-3),
	EMPTY(-4)
}