Longs.v3

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

// Utilities for rendering and parsing (long) integers in various formats, as well
// as additional arithmetic routines.
component Longs {
	def parseDecimal(a: Array<byte>, pos: int) -> i64;
	def parsePosDecimal(a: Array<byte>, pos: int) -> u64;
	// Parse a hexadecimal integer value prefixed with "0x" or "0X" starting at {a[pos]}.
	def parse0xHex(a: Array<byte>, pos: int) -> (int, u64) {
		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, u64) {
		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, u64) {
		var accum = 0uL, s = pos;
		while (s < a.length) {
			var ch = a[s];
			if (!Chars.isHex(ch)) break;
			if ((s - pos) >= 16) return (-16 - prefix, 0); // too long
			accum = accum << 4 | u64.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, u64) {
		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, u64) {
		return parseBin0(a, pos, 0);
	}
	private def parseBin0(a: Array<byte>, pos: int, prefix: int) -> (int, u64) {
		var accum = 0uL, s = pos;
		while (s < a.length) {
			var ch = a[s], v = ch - '0';
			if ((v & ~1) != 0) break;
			if ((s - pos) >= 64) return (-64 - pos, 0); // too long
			accum = accum << 1 | v;
			s++;
		}
		var len = s - pos;
		return if(len == 0, (-1 - prefix, 0), (len + prefix, accum));
	}

	// Render {i} in decimal at the position {pos} in {a}, returning
	// the number of characters output.
	def renderDecimal(i: i64, a: Array<byte>, pos: int) -> int {
		var small = i32.view(i);
		if (small == i) return Ints.renderDecimal(small, a, pos); // faster
		if (i < 0) {
			a[pos++] = '-';
			return 1 + renderPosDecimal(u64.view(0 - i), a, pos);
		}
		return renderPosDecimal(u64.view(i), a, pos);
	}
	// Render {i} in decimal at the position {pos} in {a}, returning
	// the number of characters output.
	def renderPosDecimal(i: u64, a: Array<byte>, pos: int) -> int {
		var small = u32.view(i);
		if (small == i) return Ints.renderPosDecimal(small, a, pos); // faster
		var nonZero = false;
		// XXX(fast): divide by 1000000000 and print two (or three) ints, to avoid repeated 64-bit divide.
		// XXX(fast): worth it to compute digits low to high? 1 divide vs 2.
		var p = pos;
		for (radix = 10000000000000000000ul; radix > 0; radix = radix / 10) {
			var digit = i / radix;
			i = i % radix;
			if (digit != 0) nonZero = true;
			if (nonZero) a[p++] = byte.view('0' + digit);
		}
		return p - pos;
	}
	// Compute the number of 1 bits in {i}.
	def popcnt(i: u64) -> int {
		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: long, b: long) -> long {
		return if(a < b, a, b);
	}
	// Compute the floor of the log base 2 of {i}.
	def log(i: u64) -> int {
		var r = 0;
		if (i == 0) return -1;
		if (i >= (1uL << 32)) { r += 32; i >>= 32; }
		var j = u32.view(i);
		if (j >= (1u << 16)) { r += 16; j >>= 16; }
		if (j >= (1u << 8)) { r += 8; j >>= 8; }
		if (j >= (1u << 4)) { r += 4; j >>= 4; }
		if (j >= (1u << 2)) { r += 2; j >>= 2; }
		if (j >= (1u << 1)) { r += 1; j >>= 1; }
		return r;
	}
}