hare

[hare] The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

ftos.ha (22108B)


      1 // License: MPL-2.0
      2 // (c) 2021 Bor Grošelj Simić <bor.groseljsimic@telemach.net>
      3 // (c) 2021 Drew DeVault <sir@cmpwn.com>
      4 // (c) 2021 Ember Sawady <ecs@d2evs.net>
      5 // (c) 2021 Sudipto Mallick <smlckz@disroot.org>
      6 // (c) 2021 Sudipto Mallick <smlckz@envs.net>
      7 // (c) 2021 Vlad-Stefan Harbuz <vlad@vladh.net>
      8 
      9 // Using Ryū: fast float-to-string conversion algorithm by Ulf Adams.
     10 // https://doi.org/10.1145/3192366.3192369
     11 // This Hare implementation is translated from the original
     12 // C implementation here: https://github.com/ulfjack/ryu
     13 
     14 use math;
     15 use types;
     16 
     17 type r128 = struct {
     18 	hi: u64,
     19 	lo: u64,
     20 };
     21 
     22 // TODO: use 128-bit integers when implemented
     23 fn u128mul(a: u64, b: u64) r128 = {
     24 	const a0 = a: u32: u64, a1 = a >> 32;
     25 	const b0 = b: u32: u64, b1 = b >> 32;
     26 	const p00 = a0 * b0, p01 = a0 * b1, p10 = a1 * b0, p11 = a1 * b1;
     27 	const p00_lo = p00: u32: u64, p00_hi = p00 >> 32;
     28 	const mid1 = p10 + p00_hi;
     29 	const mid1_lo = mid1: u32: u64, mid1_hi = mid1 >> 32;
     30 	const mid2 = p01 + mid1_lo;
     31 	const mid2_lo = mid2: u32: u64, mid2_hi = mid2 >> 32;
     32 	const r_hi = p11 + mid1_hi + mid2_hi;
     33 	const r_lo = (mid2_lo << 32) | p00_lo;
     34 	return r128 { hi = r_hi, lo = r_lo };
     35 };
     36 
     37 // TODO: Same as above
     38 fn u128rshift(lo: u64, hi: u64, s: u32) u64 = {
     39 	assert(0 <= s);
     40 	assert(s <= 64);
     41 	return (hi << (64 - s)) | (lo >> s);
     42 };
     43 
     44 fn pow5fac(value: u64) u32 = {
     45 	const m_inv_5: u64 = 14757395258967641293; // 5 * m_inv_5 = 1 (mod 2^64)
     46 	const n_div_5: u64 = 3689348814741910323;
     47 	let count: u32 = 0;
     48 	for (true) {
     49 		assert(value != 0);
     50 		value *= m_inv_5;
     51 		if (value > n_div_5) break;
     52 		count += 1;
     53 	};
     54 	return count;
     55 };
     56 
     57 fn pow5fac32(value: u32) u32 = {
     58 	let count: u32 = 0;
     59 	for (true) {
     60 		assert(value != 0);
     61 		const q = value / 5, r = value % 5;
     62 		if (r != 0) break;
     63 		value = q;
     64 		count += 1;
     65 	};
     66 	return count;
     67 };
     68 
     69 fn ibool(b: bool) u8 = if (b) 1 else 0;
     70 
     71 fn pow5multiple(v: u64, p: u32) bool = pow5fac(v) >= p;
     72 fn pow5multiple32(v: u32, p: u32) bool = pow5fac32(v) >= p;
     73 
     74 fn pow2multiple(v: u64, p: u32) bool = {
     75 	assert(v > 0);
     76 	assert(p < 64);
     77 	return (v & ((1u64 << p) - 1)) == 0;
     78 };
     79 
     80 fn pow2multiple32(v: u32, p: u32) bool = {
     81 	assert(v > 0);
     82 	assert(p < 32);
     83 	return (v & ((1u32 << p) - 1)) == 0;
     84 };
     85 
     86 fn mulshift64(m: u64, mul: (u64, u64), j: u32) u64 = {
     87 	// m is maximum 55 bits
     88 	let r0 = u128mul(m, mul.0), r1 = u128mul(m, mul.1);
     89 	const sum = r1.lo + r0.hi;
     90 	r1.hi += ibool(sum < r0.hi);
     91 	return u128rshift(sum, r1.hi, j - 64);
     92 };
     93 
     94 fn mulshiftall64(m: u64, mul: (u64, u64), j: i32, mm_shift: u32) (u64, u64, u64) = {
     95 	m <<= 1;
     96 	const r0 = u128mul(m, mul.0), r1 = u128mul(m, mul.1);
     97 	const lo = r0.lo, tmp = r0.hi, mid = tmp + r1.lo;
     98 	const hi = r1.hi + ibool(mid < tmp);
     99 	const lo2 = lo + mul.0;
    100 	const mid2 = mid + mul.1 + ibool(lo2 < lo);
    101 	const hi2 = hi + ibool(mid2 < mid);
    102 	const v_plus = u128rshift(mid2, hi2, (j - 64 - 1): u32);
    103 	const v_minus = if (mm_shift == 1) {
    104 		const lo3 = lo - mul.0;
    105 		const mid3 = mid - mul.1 - ibool(lo3 > lo);
    106 		const hi3 = hi - ibool(mid3 > mid);
    107 		yield u128rshift(mid3, hi3, (j - 64 - 1): u32);
    108 	} else {
    109 		const lo3 = lo + lo;
    110 		const mid3 = mid + mid + ibool(lo3 < lo);
    111 		const hi3 = hi + hi + ibool(mid3 < mid);
    112 		const lo4 = lo3 - mul.0;
    113 		const mid4 = mid3 - mul.1 - ibool(lo4 > lo3);
    114 		const hi4 = hi3 - ibool(mid4 > mid3);
    115 		yield u128rshift(mid4, hi4, (j - 64): u32);
    116 	};
    117 	const v_rounded = u128rshift(mid, hi, (j - 64 - 1): u32);
    118 	return (v_plus, v_rounded, v_minus);
    119 };
    120 
    121 fn mulshift32(m: u32, a: u64, s: u32) u32 = {
    122 	assert(s > 32);
    123 	const a_lo = a: u32: u64, a_hi = a >> 32;
    124 	const b0 = m * a_lo, b1 = m * a_hi;
    125 	const sum = (b0 >> 32) + b1, ss = sum >> (s - 32);
    126 	assert(ss <= types::U32_MAX);
    127 	return ss: u32;
    128 };
    129 
    130 fn mulpow5inv_divpow2(m: u32, q: u32, j: i32) u32 = {
    131 	const pow5 = f64computeinvpow5(q);
    132 	return mulshift32(m, pow5.1 + 1, j: u32);
    133 };
    134 
    135 fn mulpow5_divpow2(m: u32, i: u32, j: i32) u32 = {
    136 	const pow5 = f64computepow5(i);
    137 	return mulshift32(m, pow5.1, j: u32);
    138 };
    139 
    140 fn log2pow5(e: u32) u32 = {
    141 	assert(e <= 3528);
    142 	return ((e * 1217359) >> 19);
    143 };
    144 
    145 fn ceil_log2pow5(e: u32) u32 = log2pow5(e) + 1;
    146 
    147 fn pow5bits(e: u32) u32 = ceil_log2pow5(e);
    148 
    149 fn log10pow2(e: u32) u32 = {
    150 	assert(e <= 1650);
    151 	return ((e * 78913) >> 18);
    152 };
    153 
    154 fn log10pow5(e: u32) u32 = {
    155 	assert(e <= 2620);
    156 	return ((e * 732923) >> 20);
    157 };
    158 
    159 def F64_POW5_INV_BITCOUNT: u8 = 125;
    160 def F64_POW5_BITCOUNT: u8 = 125;
    161 
    162 def F32_POW5_INV_BITCOUNT: u8 = F64_POW5_INV_BITCOUNT - 64;
    163 def F32_POW5_BITCOUNT: u8 = F64_POW5_BITCOUNT - 64;
    164 
    165 const F64_POW5_INV_SPLIT2: [15][2]u64 = [
    166 	[1, 2305843009213693952],
    167 	[5955668970331000884, 1784059615882449851],
    168 	[8982663654677661702, 1380349269358112757],
    169 	[7286864317269821294, 2135987035920910082],
    170 	[7005857020398200553, 1652639921975621497],
    171 	[17965325103354776697, 1278668206209430417],
    172 	[8928596168509315048, 1978643211784836272],
    173 	[10075671573058298858, 1530901034580419511],
    174 	[597001226353042382, 1184477304306571148],
    175 	[1527430471115325346, 1832889850782397517],
    176 	[12533209867169019542, 1418129833677084982],
    177 	[5577825024675947042, 2194449627517475473],
    178 	[11006974540203867551, 1697873161311732311],
    179 	[10313493231639821582, 1313665730009899186],
    180 	[12701016819766672773, 2032799256770390445],
    181 ];
    182 
    183 const POW5_INV_OFFSETS: [19]u32 = [
    184 	0x54544554, 0x04055545, 0x10041000, 0x00400414, 0x40010000, 0x41155555,
    185 	0x00000454, 0x00010044, 0x40000000, 0x44000041, 0x50454450, 0x55550054,
    186 	0x51655554, 0x40004000, 0x01000001, 0x00010500, 0x51515411, 0x05555554,
    187 	0x00000000
    188 ];
    189 
    190 const F64_POW5_SPLIT2: [13][2]u64 = [
    191 	[0, 1152921504606846976],
    192 	[0, 1490116119384765625],
    193 	[1032610780636961552, 1925929944387235853],
    194 	[7910200175544436838, 1244603055572228341],
    195 	[16941905809032713930, 1608611746708759036],
    196 	[13024893955298202172, 2079081953128979843],
    197 	[6607496772837067824, 1343575221513417750],
    198 	[17332926989895652603, 1736530273035216783],
    199 	[13037379183483547984, 2244412773384604712],
    200 	[1605989338741628675, 1450417759929778918],
    201 	[9630225068416591280, 1874621017369538693],
    202 	[665883850346957067, 1211445438634777304],
    203 	[14931890668723713708, 1565756531257009982]
    204 ];
    205 
    206 const POW5_OFFSETS: [21]u32 = [
    207 	0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x40000000, 0x59695995,
    208 	0x55545555, 0x56555515, 0x41150504, 0x40555410, 0x44555145, 0x44504540,
    209 	0x45555550, 0x40004000, 0x96440440, 0x55565565, 0x54454045, 0x40154151,
    210 	0x55559155, 0x51405555, 0x00000105
    211 ];
    212 
    213 def POW5_TABLE_SIZE: u8 = 26;
    214 
    215 const POW5_TABLE: [POW5_TABLE_SIZE]u64 = [
    216 	1u64, 5u64, 25u64, 125u64, 625u64, 3125u64, 15625u64, 78125u64,
    217 	390625u64, 1953125u64, 9765625u64, 48828125u64, 244140625u64,
    218 	1220703125u64, 6103515625u64, 30517578125u64, 152587890625u64,
    219 	762939453125u64, 3814697265625u64, 19073486328125u64, 95367431640625u64,
    220 	476837158203125u64, 2384185791015625u64, 11920928955078125u64,
    221 	59604644775390625u64, 298023223876953125u64 //, 1490116119384765625u64
    222 ];
    223 
    224 fn f64computeinvpow5(i: u32) (u64, u64) = {
    225 	const base = ((i + POW5_TABLE_SIZE - 1) / POW5_TABLE_SIZE): u32;
    226 	const base2 = base * POW5_TABLE_SIZE;
    227 	const mul = F64_POW5_INV_SPLIT2[base];
    228 	const off = base2 - i;
    229 	if (off == 0) {
    230 		return (mul[0], mul[1]);
    231 	};
    232 	const m = POW5_TABLE[off];
    233 	const r1 = u128mul(m, mul[1]), r0 = u128mul(m, mul[0] - 1);
    234 	let high1 = r1.hi, low1 = r1.lo, high0 = r0.hi, low0 = r0.lo;
    235 	const sum = high0 + low1;
    236 	if (sum < high0) {
    237 		high1 += 1;
    238 	};
    239 	const delta = pow5bits(base2) - pow5bits(i);
    240 	const res0 = u128rshift(low0, sum, delta) + 1 +
    241 		((POW5_INV_OFFSETS[i / 16] >> ((i % 16) << 1)) & 3);
    242 	const res1 = u128rshift(sum, high1, delta);
    243 	return (res0, res1);
    244 };
    245 
    246 fn f64computepow5(i: u32) (u64, u64) = {
    247 	const base = i / POW5_TABLE_SIZE, base2 = base * POW5_TABLE_SIZE;
    248 	const mul = F64_POW5_SPLIT2[base];
    249 	const off = i - base2;
    250 	if (off == 0) {
    251 		return (mul[0], mul[1]);
    252 	};
    253 	const m = POW5_TABLE[off];
    254 	const r1 = u128mul(m, mul[1]), r0 = u128mul(m, mul[0]);
    255 	let high1 = r1.hi, low1 = r1.lo, high0 = r0.hi, low0 = r0.lo;
    256 	const sum = high0 + low1;
    257 	if (sum < high0) {
    258 		high1 += 1;
    259 	};
    260 	const delta = pow5bits(i) - pow5bits(base2);
    261 	const res0 = u128rshift(low0, sum, delta) +
    262 		((POW5_OFFSETS[i / 16] >> ((i % 16) << 1)) & 3);
    263 	const res1 = u128rshift(sum, high1, delta);
    264 	return (res0, res1);
    265 };
    266 
    267 fn declen(n: u64) u8 = {
    268 	assert(n <= 1e17);
    269 	return if (n >= 1e17) 18
    270 	else if (n >= 1e16) 17
    271 	else if (n >= 1e15) 16
    272 	else if (n >= 1e14) 15
    273 	else if (n >= 1e13) 14
    274 	else if (n >= 1e12) 13
    275 	else if (n >= 1e11) 12
    276 	else if (n >= 1e10) 11
    277 	else if (n >= 1e9) 10
    278 	else if (n >= 1e8) 9
    279 	else if (n >= 1e7) 8
    280 	else if (n >= 1e6) 7
    281 	else if (n >= 1e5) 6
    282 	else if (n >= 1e4) 5
    283 	else if (n >= 1e3) 4
    284 	else if (n >= 100) 3
    285 	else if (n >= 10) 2
    286 	else 1;
    287 };
    288 
    289 type decf64 = struct {
    290 	mantissa: u64,
    291 	exponent: i32,
    292 };
    293 
    294 fn f64todecf64(mantissa: u64, exponent: u32) decf64 = {
    295 	let e2 = (math::F64_EXPONENT_BIAS + math::F64_MANTISSA_BITS + 2): i32;
    296 	let m2: u64 = 0;
    297 	if (exponent == 0) {
    298 		e2 = 1 - e2;
    299 		m2 = mantissa;
    300 	} else {
    301 		e2 = (exponent: i32) - e2;
    302 		m2 = (1u64 << math::F64_MANTISSA_BITS) | mantissa;
    303 	};
    304 	const accept_bounds = (m2 & 1) == 0;
    305 	const mv = 4 * m2;
    306 	const mm_shift = ibool(mantissa != 0 || exponent <= 1);
    307 	let vp: u64 = 0, vr: u64 = 0, vm: u64 = 0;
    308 	let e10: i32 = 0;
    309 	let vm_trailing_zeros = false, vr_trailing_zeros = false;
    310 	if (e2 >= 0) {
    311 		const q = log10pow2(e2: u32) - ibool(e2 > 3);
    312 		e10 = q: i32;
    313 		const k = F64_POW5_INV_BITCOUNT + pow5bits(q) - 1;
    314 		const i = -e2 + (q + k): i32;
    315 		let pow5 = f64computeinvpow5(q);
    316 		const res = mulshiftall64(m2, pow5, i, mm_shift);
    317 		vp = res.0; vr = res.1; vm = res.2;
    318 		if (q <= 21) {
    319 			if ((mv - 5 * (mv / 5)) == 0) {
    320 				vr_trailing_zeros = pow5multiple(mv, q);
    321 			} else if (accept_bounds) {
    322 				vm_trailing_zeros = pow5multiple(mv - 1 - mm_shift, q);
    323 			} else {
    324 				vp -= ibool(pow5multiple(mv + 2, q));
    325 			};
    326 		};
    327 	} else {
    328 		const q = log10pow5((-e2): u32) - ibool(-e2 > 1);
    329 		e10 = e2 + (q: i32);
    330 		const i = -e2 - (q: i32);
    331 		const k = pow5bits(i: u32): i32 - F64_POW5_BITCOUNT: i32;
    332 		const j = (q: i32) - k;
    333 		let pow5 = f64computepow5(i: u32);
    334 		const res = mulshiftall64(m2, pow5, j, mm_shift);
    335 		vp = res.0; vr = res.1; vm = res.2;
    336 		if (q <= 1) {
    337 			vr_trailing_zeros = true;
    338 			if (accept_bounds) {
    339 				vm_trailing_zeros = mm_shift == 1;
    340 			} else {
    341 				vp -= 1;
    342 			};
    343 		} else if (q < 63) {
    344 			vr_trailing_zeros = pow2multiple(mv, q);
    345 		};
    346 	};
    347 	let removed: i32 = 0, last_removed_digit: u8 = 0;
    348 	let output: u64 = 0;
    349 	if (vm_trailing_zeros || vr_trailing_zeros) {
    350 		for (true) {
    351 			const vpby10 = vp / 10, vmby10 = vm / 10;
    352 			if (vpby10 <= vmby10) break;
    353 			const vmmod10 = (vm: u32) - 10 * (vmby10: u32);
    354 			const vrby10 = vr / 10;
    355 			const vrmod10 = (vr: u32) - 10 * (vrby10: u32);
    356 			vm_trailing_zeros &&= vmmod10 == 0;
    357 			vr_trailing_zeros &&= last_removed_digit == 0;
    358 			last_removed_digit = vrmod10: u8;
    359 			vr = vrby10; vp = vpby10; vm = vmby10;
    360 			removed += 1;
    361 		};
    362 		if (vm_trailing_zeros) {
    363 			for (true) {
    364 				const vmby10 = vm / 10;
    365 				const vmmod10 = (vm: u32) - 10 * (vmby10: u32);
    366 				if (vmmod10 != 0) break;
    367 				const vpby10 = vp / 10, vrby10 = vr / 10;
    368 				const vrmod10 = (vr: u32) - 10 * (vrby10: u32);
    369 				vr_trailing_zeros &&= last_removed_digit == 0;
    370 				last_removed_digit = vrmod10: u8;
    371 				vr = vrby10; vp = vpby10; vm = vmby10;
    372 				removed += 1;
    373 			};
    374 		};
    375 		if (vr_trailing_zeros && last_removed_digit == 5 && (vr & 1 == 0)) {
    376 			// round to even
    377 			last_removed_digit = 4;
    378 		};
    379 		output = vr + ibool((vr == vm &&
    380 			(!accept_bounds || !vm_trailing_zeros)) ||
    381 			last_removed_digit >= 5);
    382 	} else {
    383 		let round_up = false;
    384 		const vpby100 = vp / 100, vmby100 = vm / 100;
    385 		if (vpby100 > vmby100) {
    386 			const vrby100 = vr / 100;
    387 			const vrmod100 = (vr: u32) - 100 * (vrby100: u32);
    388 			round_up = vrmod100 >= 50;
    389 			vr = vrby100; vp = vpby100; vm = vmby100;
    390 			removed += 2;
    391 		};
    392 		for (true) {
    393 			const vmby10 = vm / 10, vpby10 = vp / 10;
    394 			if (vpby10 <= vmby10) break;
    395 			const vrby10 = vr / 10;
    396 			const vrmod10 = (vr: u32) - 10 * (vrby10: u32);
    397 			round_up = vrmod10 >= 5;
    398 			vr = vrby10; vp = vpby10; vm = vmby10;
    399 			removed += 1;
    400 		};
    401 		output = vr + ibool(vr == vm || round_up);
    402 	};
    403 	const exp = e10 + removed;
    404 	return decf64 { exponent = exp, mantissa = output };
    405 };
    406 
    407 type decf32 = struct {
    408 	mantissa: u32,
    409 	exponent: i32,
    410 };
    411 
    412 fn f32todecf32(mantissa: u32, exponent: u32) decf32 = {
    413 	let e2 = (math::F32_EXPONENT_BIAS + math::F32_MANTISSA_BITS + 2): i32;
    414 	let m2: u32 = 0;
    415 	if (exponent == 0) {
    416 		e2 = 1 - e2;
    417 		m2 = mantissa;
    418 	} else {
    419 		e2 = (exponent: i32) - e2;
    420 		m2 = (1u32 << math::F32_MANTISSA_BITS: u32) | mantissa;
    421 	};
    422 	const accept_bounds = (m2 & 1) == 0;
    423 	const mv = 4 * m2, mp = mv + 2;
    424 	const mm_shift = ibool(mantissa != 0 || exponent <= 1);
    425 	const mm = mv - 1 - mm_shift;
    426 	let vr: u32 = 0, vp: u32 = 0, vm: u32 = 0;
    427 	let e10: i32 = 0;
    428 	let vm_trailing_zeroes = false, vr_trailing_zeroes = false;
    429 	let last_removed_digit: u8 = 0;
    430 	if (e2 >= 0) {
    431 		const q = log10pow2(e2: u32);
    432 		e10 = q: i32;
    433 		const k = F32_POW5_INV_BITCOUNT + pow5bits(q) - 1;
    434 		const i = -e2 + (q + k): i32;
    435 		vr = mulpow5inv_divpow2(mv, q, i);
    436 		vp = mulpow5inv_divpow2(mp, q, i);
    437 		vm = mulpow5inv_divpow2(mm, q, i);
    438 		if (q != 0 && (vp - 1) / 10 <= vm / 10) {
    439 			const l = F32_POW5_INV_BITCOUNT + pow5bits(q - 1) - 1;
    440 			last_removed_digit = (mulpow5inv_divpow2(mv, q - 1,
    441 				-e2 + ((q + l): i32) - 1) % 10): u8;
    442 		};
    443 		if (q <= 9) {
    444 			if (mv % 5 == 0) {
    445 				vr_trailing_zeroes = pow5multiple32(mv, q);
    446 			} else if (accept_bounds) {
    447 				vm_trailing_zeroes = pow5multiple32(mm, q);
    448 			} else {
    449 				vp -= ibool(pow5multiple32(mp, q));
    450 			};
    451 		};
    452 	} else {
    453 		const q = log10pow5((-e2): u32);
    454 		e10 = (q: i32) + e2;
    455 		const i = (-e2 - (q: i32)): u32;
    456 		const k = pow5bits(i) - F32_POW5_BITCOUNT;
    457 		let j = (q: i32) - k: i32;
    458 		vr = mulpow5_divpow2(mv, i, j);
    459 		vp = mulpow5_divpow2(mp, i, j);
    460 		vm = mulpow5_divpow2(mm, i, j);
    461 		if (q != 0 && (vp - 1) / 10 <= vm / 10) {
    462 			j = (q: i32) - 1 - (pow5bits(i + 1): i32 -
    463 				F32_POW5_BITCOUNT: i32);
    464 			last_removed_digit = (mulpow5_divpow2(mv,
    465 				(i + 1), j) % 10): u8;
    466 		};
    467 		if (q <= 1) {
    468 			vr_trailing_zeroes = true;
    469 			if (accept_bounds) {
    470 				vm_trailing_zeroes = mm_shift == 1;
    471 			} else {
    472 				vp -= 1;
    473 			};
    474 		} else if (q < 31) {
    475 			vr_trailing_zeroes = pow2multiple32(mv, q - 1);
    476 		};
    477 	};
    478 	let removed: i32 = 0, output: u32 = 0;
    479 	if (vm_trailing_zeroes || vr_trailing_zeroes) {
    480 		for (vp / 10 > vm / 10) {
    481 			vm_trailing_zeroes &&= (vm - (vm / 10) * 10) == 0;
    482 			vr_trailing_zeroes &&= last_removed_digit == 0;
    483 			last_removed_digit = (vr % 10): u8;
    484 			vr /= 10;
    485 			vp /= 10;
    486 			vm /= 10;
    487 			removed += 1;
    488 		};
    489 		if (vm_trailing_zeroes) {
    490 			for (vm % 10 == 0) {
    491 				vr_trailing_zeroes &&= last_removed_digit == 0;
    492 				last_removed_digit = (vr % 10): u8;
    493 				vr /= 10;
    494 				vp /= 10;
    495 				vm /= 10;
    496 				removed += 1;
    497 			};
    498 		};
    499 		if (vr_trailing_zeroes && last_removed_digit == 5 && vr % 2 == 0) {
    500 			// round to even
    501 			last_removed_digit = 4;
    502 		};
    503 		output = vr + ibool((vr == vm &&
    504 			(!accept_bounds || !vm_trailing_zeroes)) ||
    505 			last_removed_digit >= 5);
    506 	} else {
    507 		for (vp / 10 > vm / 10) {
    508 			last_removed_digit = (vr % 10): u8;
    509 			vr /= 10;
    510 			vp /= 10;
    511 			vm /= 10;
    512 			removed += 1;
    513 		};
    514 		output = vr + ibool(vr == vm || last_removed_digit >= 5);
    515 	};
    516 	const exp = e10 + removed;
    517 	return decf32 { mantissa = output, exponent = exp };
    518 };
    519 
    520 def F32_DECIMAL_DIGITS: i32 = 9;
    521 def F64_DECIMAL_DIGITS: i32 = 17;
    522 
    523 fn encode_base10(buf: []u8, mantissa: u64, exponent: i32, digits: i32) size = {
    524 	const zch = '0': u8;
    525 	const n = mantissa, e = exponent, olen = declen(n);
    526 	const exp = e + olen: i32 - 1;
    527 	// use scientific notation for numbers whose exponent is beyond the
    528 	// precision available for the underlying type
    529 	if (exp > -4 && exp < digits) {
    530 		if (e >= 0) {
    531 			let k = exp;
    532 			for (let a = e; a > 0; a -= 1) {
    533 				buf[k] = zch;
    534 				k -= 1;
    535 			};
    536 			let m = n;
    537 			for (k >= 0; k -= 1) {
    538 				const mby10 = m / 10;
    539 				const mmod10 = (m: u32) - 10 * (mby10: u32);
    540 				buf[k] = zch + mmod10: u8;
    541 				m = mby10;
    542 			};
    543 			return (e + olen: i32): size;
    544 		} else if (exp < 0) {
    545 			buf[0] = zch;
    546 			buf[1] = '.';
    547 			let k = -e + 1;
    548 			let m = n;
    549 			for (let a = olen: i32; a > 0; a -= 1) {
    550 				const mby10 = m / 10;
    551 				const mmod10 = (m: u32) - 10 * (mby10: u32);
    552 				buf[k] = zch + mmod10: u8;
    553 				k -= 1;
    554 				m = mby10;
    555 			};
    556 			for (k > 1; k -= 1) {
    557 				buf[k] = zch;
    558 			};
    559 			return (-e + 2): size;
    560 		} else {
    561 			let k = olen: i32;
    562 			let m = n;
    563 			for (let a = -e; a > 0; a -= 1) {
    564 				const mby10 = m / 10;
    565 				const mmod10 = (m: u32) - 10 * (mby10: u32);
    566 				buf[k] = zch + mmod10: u8;
    567 				k -= 1;
    568 				m = mby10;
    569 			};
    570 			buf[k] = '.';
    571 			k -= 1;
    572 			for (k >= 0; k -= 1) {
    573 				const mby10 = m / 10;
    574 				const mmod10 = (m: u32) - 10 * (mby10: u32);
    575 				buf[k] = zch + mmod10: u8;
    576 				m = mby10;
    577 			};
    578 			return (olen + 1): size;
    579 		};
    580 	} else {
    581 		let h: i32 = 0;
    582 		let m = n;
    583 		if (olen == 1) {
    584 			buf[0] = zch + m: u8;
    585 			h = 1;
    586 		} else {
    587 			let k = olen: i32;
    588 			for (let a = k; a > 1; a -= 1) {
    589 				const mby10 = m / 10;
    590 				const mmod10 = (m: u32) - 10 * (mby10: u32);
    591 				buf[k] = zch + mmod10: u8;
    592 				k -= 1;
    593 				m = mby10;
    594 			};
    595 			buf[k] = '.';
    596 			buf[0] = zch + m: u8;
    597 			h = olen: i32 + 1;
    598 		};
    599 		buf[h] = 'e';
    600 		h += 1;
    601 		let ex = if (exp < 0) {
    602 			buf[h] = '-';
    603 			h += 1;
    604 			yield -exp;
    605 		} else exp;
    606 		const elen = declen(ex: u64);
    607 		let k = h + elen: i32 - 1;
    608 		for (let a = elen: i32; a > 0; a -= 1) {
    609 			const eby10 = ex / 10;
    610 			const emod10 = (ex: u32) - 10 * (eby10: u32);
    611 			buf[k] = zch + emod10: u8;
    612 			k -= 1;
    613 			ex = eby10;
    614 		};
    615 		h += elen: i32;
    616 		return h: size;
    617 	};
    618 };
    619 
    620 // Converts a f64 to a string in base 10. The return value is statically
    621 // allocated and will be overwritten on subsequent calls; see [[strings::dup]]
    622 // to duplicate the result.
    623 export fn f64tos(n: f64) const str = {
    624 	// The biggest string produced by a f64 number in base 10 would have the
    625 	// negative sign, followed by a digit and decimal point, and then
    626 	// sixteen more decimal digits, followed by 'e' and another negative
    627 	// sign and the maximum of three digits for exponent.
    628 	// (1 + 1 + 1 + 16 + 1 + 1 + 3) = 24
    629 	static let buf: [24]u8 = [0...];
    630 	const bits = math::f64bits(n);
    631 	const sign = (bits >> (math::F64_MANTISSA_BITS +
    632 	math::F64_EXPONENT_BITS)): size; // bits >> 63
    633 	const mantissa = bits & ((1u64 << math::F64_MANTISSA_BITS) - 1);
    634 	const exponent = ((bits >> math::F64_MANTISSA_BITS) &
    635 			(1u64 << math::F64_EXPONENT_BITS) - 1): u32;
    636 	if (mantissa == 0 && exponent == 0) {
    637 		return "0";
    638 	} else if (exponent == ((1 << math::F64_EXPONENT_BITS) - 1)) {
    639 		if (mantissa != 0) {
    640 			return "NaN";
    641 		};
    642 		return if (sign == 0) "Infinity" else "-Infinity";
    643 	};
    644 	const d = f64todecf64(mantissa, exponent);
    645 	if (sign != 0) {
    646 		buf[0] = '-';
    647 	};
    648 	let z = encode_base10(buf[sign..], d.mantissa, d.exponent,
    649 			F64_DECIMAL_DIGITS) + sign;
    650 	let s = types::string { data = &buf, length = z, ... };
    651 	return *(&s: *str);
    652 };
    653 
    654 // Converts a f32 to a string in base 10. The return value is statically
    655 // allocated and will be overwritten on subsequent calls; see [[strings::dup]]
    656 // to duplicate the result.
    657 export fn f32tos(n: f32) const str = {
    658 	// The biggest string produced by a f32 number in base 10 would have the
    659 	// negative sign, followed by a digit and decimal point, and then seven
    660 	// more decimal digits, followed by 'e' and another negative sign and
    661 	// the maximum of two digits for exponent.
    662 	// (1 + 1 + 1 + 7 + 1 + 1 + 2) = 14
    663 	static let buf: [16]u8 = [0...];
    664 	const bits = math::f32bits(n);
    665 	const sign = (bits >> (math::F32_MANTISSA_BITS +
    666 	math::F32_EXPONENT_BITS)): size; // bits >> 31
    667 	const mantissa = bits & ((1u32 << math::F32_MANTISSA_BITS) - 1): u32;
    668 	const exponent = (bits >> math::F32_MANTISSA_BITS): u32 &
    669 		((1u32 << math::F32_EXPONENT_BITS) - 1): u32;
    670 	if (mantissa == 0 && exponent == 0) {
    671 		return "0";
    672 	} else if (exponent == ((1 << math::F32_EXPONENT_BITS) - 1): u32) {
    673 		if (mantissa != 0) {
    674 			return "NaN";
    675 		};
    676 		return if (sign == 0) "Infinity" else "-Infinity";
    677 	};
    678 	const d = f32todecf32(mantissa, exponent);
    679 	if (sign != 0) {
    680 		buf[0] = '-';
    681 	};
    682 	let z = encode_base10(buf[sign..], d.mantissa, d.exponent,
    683 			F32_DECIMAL_DIGITS) + sign;
    684 	const s = types::string { data = &buf, length = z, ... };
    685 	return *(&s: *str);
    686 };
    687 
    688 @test fn f64tos() void = {
    689 	assert(f64tos(0.0) == "0");
    690 	assert(f64tos(1.0 / 0.0) == "Infinity");
    691 	assert(f64tos(-1.0 / 0.0) == "-Infinity");
    692 	assert(f64tos(0.0 / 0.0) == "NaN");
    693 	assert(f64tos(1.0) == "1");
    694 	assert(f64tos(0.3) == "0.3");
    695 	assert(f64tos(0.0031415) == "0.0031415");
    696 	assert(f64tos(0.0000012345678) == "1.2345678e-6");
    697 	assert(f64tos(1.414) == "1.414");
    698 	assert(f64tos(1e234f64) == "1e234");
    699 	assert(f64tos(1.2e-34) == "1.2e-34");
    700 	assert(f64tos(-6345.9721) == "-6345.9721");
    701 	assert(f64tos(1.23456789e67) == "1.23456789e67");
    702 	assert(f64tos(11.2233445566778899e20) == "1.122334455667789e21");
    703 	assert(f64tos(1000000.0e9) == "1000000000000000");
    704 	assert(f64tos(9007199254740991.0) == "9007199254740991");
    705 	assert(f64tos(90071992547409915.0) == "90071992547409920");
    706 	assert(f64tos(90071992547409925.0) == "90071992547409920");
    707 	assert(f64tos(5.0e-324) == "5e-324");
    708 	assert(f64tos(2.2250738585072014e-308) == "2.2250738585072014e-308");
    709 	assert(f64tos(1.7976931348623157e308) == "1.7976931348623157e308");
    710 };
    711 
    712 @test fn f32tos() void = {
    713 	assert(f32tos(0.0) == "0");
    714 	assert(f32tos(1.0 / 0.0) == "Infinity");
    715 	assert(f32tos(-1.0 / 0.0) == "-Infinity");
    716 	assert(f32tos(0.0 / 0.0) == "NaN");
    717 	assert(f32tos(1.0) == "1");
    718 	assert(f32tos(-8.0) == "-8");
    719 	assert(f32tos(1.23) == "1.23");
    720 	assert(f32tos(-0.618) == "-0.618");
    721 	assert(f32tos(0.00456) == "0.00456");
    722 	assert(f32tos(0.00000000000434655) == "4.34655e-12");
    723 	assert(f32tos(123456.78) == "123456.78");
    724 	assert(f32tos(-1.234567) == "-1.234567");
    725 	assert(f32tos(12345.6789) == "12345.679");
    726 	assert(f32tos(1.23e30) == "1.23e30");
    727 	assert(f32tos(1.23e-30) == "1.23e-30");
    728 	assert(f32tos(16777215.0) == "16777215");
    729 	assert(f32tos(167772155.0) == "167772160");
    730 	assert(f32tos(167772145.0) == "167772140");
    731 	assert(f32tos(1.0e-45) == "1e-45");
    732 	assert(f32tos(1.1754944e-38) == "1.1754944e-38");
    733 	assert(f32tos(3.4028235e+38) == "3.4028235e38");
    734 };
    735