1 | module strconv |
2 | |
3 | import math |
4 | |
5 | fn (d Dec64) get_string_64(neg bool, i_n_digit int, i_pad_digit int) string { |
6 | mut n_digit := i_n_digit + 1 |
7 | pad_digit := i_pad_digit + 1 |
8 | mut out := d.m |
9 | mut d_exp := d.e |
10 | // mut out_len := decimal_len_64(out) |
11 | mut out_len := dec_digits(out) |
12 | out_len_original := out_len |
13 | |
14 | mut fw_zeros := 0 |
15 | if pad_digit > out_len { |
16 | fw_zeros = pad_digit - out_len |
17 | } |
18 | |
19 | mut buf := []u8{len: (out_len + 6 + 1 + 1 + fw_zeros)} // sign + mant_len + . + e + e_sign + exp_len(2) + \0} |
20 | mut i := 0 |
21 | |
22 | if neg { |
23 | #buf.arr.arr[i.val] = '-'.charCodeAt() |
24 | i++ |
25 | } |
26 | |
27 | mut disp := 0 |
28 | if out_len <= 1 { |
29 | disp = 1 |
30 | } |
31 | |
32 | // rounding last used digit |
33 | if n_digit < out_len { |
34 | // println("out:[$out]") |
35 | out += ten_pow_table_64[out_len - n_digit - 1] * 5 // round to up |
36 | out /= ten_pow_table_64[out_len - n_digit] |
37 | // println("out1:[$out] ${d.m / ten_pow_table_64[out_len - n_digit ]}") |
38 | if d.m / ten_pow_table_64[out_len - n_digit] < out { |
39 | d_exp++ |
40 | n_digit++ |
41 | } |
42 | |
43 | // println("cmp: ${d.m/ten_pow_table_64[out_len - n_digit ]} ${out/ten_pow_table_64[out_len - n_digit ]}") |
44 | |
45 | out_len = n_digit |
46 | // println("orig: ${out_len_original} new len: ${out_len} out:[$out]") |
47 | } |
48 | |
49 | y := i + out_len |
50 | mut x := 0 |
51 | for x < (out_len - disp - 1) { |
52 | #buf.arr.arr[y.val - x.val].val = '0'.charCodeAt() + Number(out.valueOf() % 10n) |
53 | |
54 | out /= 10 |
55 | i++ |
56 | x++ |
57 | } |
58 | |
59 | // no decimal digits needed, end here |
60 | if i_n_digit == 0 { |
61 | res := '' |
62 | #buf.arr.arr.forEach((it) => it.val == 0 ? res.str : res.str += String.fromCharCode(it.val)) |
63 | |
64 | return res |
65 | } |
66 | |
67 | if out_len >= 1 { |
68 | buf[y - x] = `.` |
69 | x++ |
70 | i++ |
71 | } |
72 | |
73 | if y - x >= 0 { |
74 | #buf.arr.arr[y.val - x.val].val = '0'.charCodeAt() + Number(out.valueOf() % 10n) |
75 | i++ |
76 | } |
77 | |
78 | for fw_zeros > 0 { |
79 | #buf.arr.arr[i.val].val = '0'.charCodeAt() |
80 | i++ |
81 | fw_zeros-- |
82 | } |
83 | |
84 | #buf.arr.arr[i.val].val = 'e'.charCodeAt() |
85 | i++ |
86 | |
87 | mut exp := d_exp + out_len_original - 1 |
88 | if exp < 0 { |
89 | #buf.arr.arr[i.val].val = '-'.charCodeAt() |
90 | i++ |
91 | exp = -exp |
92 | } else { |
93 | #buf.arr.arr[i.val].val = '+'.charCodeAt() |
94 | i++ |
95 | } |
96 | |
97 | // Always print at least two digits to match strconv's formatting. |
98 | d2 := exp % 10 |
99 | exp /= 10 |
100 | d1 := exp % 10 |
101 | _ := d1 |
102 | _ := d2 |
103 | d0 := exp / 10 |
104 | if d0 > 0 { |
105 | #buf.arr.arr[i].val = '0'.charCodeAt() + d0.val |
106 | i++ |
107 | } |
108 | #buf.arr.arr[i].val = '0'.charCodeAt() + d1.val |
109 | i++ |
110 | #buf.arr.arr[i].val = '0' + d2.val |
111 | i++ |
112 | #buf.arr.arr[i].val = 0 |
113 | |
114 | res := '' |
115 | #buf.arr.arr.forEach((it) => it.val == 0 ? res.str : res.str += String.fromCharCode(it.val)) |
116 | |
117 | return res |
118 | } |
119 | |
120 | fn f64_to_decimal_exact_int(i_mant u64, exp u64) (Dec64, bool) { |
121 | mut d := Dec64{} |
122 | e := exp - bias64 |
123 | if e > mantbits64 { |
124 | return d, false |
125 | } |
126 | shift := mantbits64 - e |
127 | mant := i_mant | u64(0x0010_0000_0000_0000) // implicit 1 |
128 | // mant := i_mant | (1 << mantbits64) // implicit 1 |
129 | d.m = mant >> shift |
130 | if (d.m << shift) != mant { |
131 | return d, false |
132 | } |
133 | |
134 | for (d.m % 10) == 0 { |
135 | d.m /= 10 |
136 | d.e++ |
137 | } |
138 | return d, true |
139 | } |
140 | |
141 | fn f64_to_decimal(mant u64, exp u64) Dec64 { |
142 | mut e2 := 0 |
143 | mut m2 := u64(0) |
144 | if exp == 0 { |
145 | // We subtract 2 so that the bounds computation has |
146 | // 2 additional bits. |
147 | e2 = 1 - bias64 - int(mantbits64) - 2 |
148 | m2 = mant |
149 | } else { |
150 | e2 = int(exp) - bias64 - int(mantbits64) - 2 |
151 | m2 = (u64(1) << mantbits64) | mant |
152 | } |
153 | even := (m2 & 1) == 0 |
154 | accept_bounds := even |
155 | |
156 | // Step 2: Determine the interval of valid decimal representations. |
157 | mv := u64(4 * m2) |
158 | mm_shift := bool_to_u64(mant != 0 || exp <= 1) |
159 | |
160 | // Step 3: Convert to a decimal power base uing 128-bit arithmetic. |
161 | mut vr := u64(0) |
162 | mut vp := u64(0) |
163 | mut vm := u64(0) |
164 | mut e10 := 0 |
165 | mut vm_is_trailing_zeros := false |
166 | mut vr_is_trailing_zeros := false |
167 | |
168 | if e2 >= 0 { |
169 | // This expression is slightly faster than max(0, log10Pow2(e2) - 1). |
170 | q := log10_pow2(e2) - bool_to_u32(e2 > 3) |
171 | e10 = int(q) |
172 | k := pow5_inv_num_bits_64 + pow5_bits(int(q)) - 1 |
173 | i := -e2 + int(q) + k |
174 | |
175 | mul := pow5_inv_split_64[q] |
176 | vr = mul_shift_64(u64(4) * m2, mul, i) |
177 | vp = mul_shift_64(u64(4) * m2 + u64(2), mul, i) |
178 | vm = mul_shift_64(u64(4) * m2 - u64(1) - mm_shift, mul, i) |
179 | if q <= 21 { |
180 | // This should use q <= 22, but I think 21 is also safe. |
181 | // Smaller values may still be safe, but it's more |
182 | // difficult to reason about them. Only one of mp, mv, |
183 | // and mm can be a multiple of 5, if any. |
184 | if mv % 5 == 0 { |
185 | vr_is_trailing_zeros = multiple_of_power_of_five_64(mv, q) |
186 | } else if accept_bounds { |
187 | // Same as min(e2 + (^mm & 1), pow5Factor64(mm)) >= q |
188 | // <=> e2 + (^mm & 1) >= q && pow5Factor64(mm) >= q |
189 | // <=> true && pow5Factor64(mm) >= q, since e2 >= q. |
190 | vm_is_trailing_zeros = multiple_of_power_of_five_64(mv - 1 - mm_shift, |
191 | q) |
192 | } else if multiple_of_power_of_five_64(mv + 2, q) { |
193 | vp-- |
194 | } |
195 | } |
196 | } else { |
197 | // This expression is slightly faster than max(0, log10Pow5(-e2) - 1). |
198 | q := log10_pow5(-e2) - bool_to_u32(-e2 > 1) |
199 | e10 = int(q) + e2 |
200 | i := -e2 - int(q) |
201 | k := pow5_bits(i) - pow5_num_bits_64 |
202 | j := int(q) - k |
203 | mul := pow5_split_64[i] |
204 | vr = mul_shift_64(u64(4) * m2, mul, j) |
205 | vp = mul_shift_64(u64(4) * m2 + u64(2), mul, j) |
206 | vm = mul_shift_64(u64(4) * m2 - u64(1) - mm_shift, mul, j) |
207 | if q <= 1 { |
208 | // {vr,vp,vm} is trailing zeros if {mv,mp,mm} has at least q trailing 0 bits. |
209 | // mv = 4 * m2, so it always has at least two trailing 0 bits. |
210 | vr_is_trailing_zeros = true |
211 | if accept_bounds { |
212 | // mm = mv - 1 - mmShift, so it has 1 trailing 0 bit iff mmShift == 1. |
213 | vm_is_trailing_zeros = (mm_shift == 1) |
214 | } else { |
215 | // mp = mv + 2, so it always has at least one trailing 0 bit. |
216 | vp-- |
217 | } |
218 | } else if q < 63 { // TODO(ulfjack/cespare): Use a tighter bound here. |
219 | // We need to compute min(ntz(mv), pow5Factor64(mv) - e2) >= q - 1 |
220 | // <=> ntz(mv) >= q - 1 && pow5Factor64(mv) - e2 >= q - 1 |
221 | // <=> ntz(mv) >= q - 1 (e2 is negative and -e2 >= q) |
222 | // <=> (mv & ((1 << (q - 1)) - 1)) == 0 |
223 | // We also need to make sure that the left shift does not overflow. |
224 | vr_is_trailing_zeros = multiple_of_power_of_two_64(mv, q - 1) |
225 | } |
226 | } |
227 | |
228 | // Step 4: Find the shortest decimal representation |
229 | // in the interval of valid representations. |
230 | mut removed := 0 |
231 | mut last_removed_digit := u8(0) |
232 | mut out := u64(0) |
233 | // On average, we remove ~2 digits. |
234 | if vm_is_trailing_zeros || vr_is_trailing_zeros { |
235 | // General case, which happens rarely (~0.7%). |
236 | for { |
237 | vp_div_10 := vp / 10 |
238 | vm_div_10 := vm / 10 |
239 | if vp_div_10 <= vm_div_10 { |
240 | break |
241 | } |
242 | vm_mod_10 := vm % 10 |
243 | vr_div_10 := vr / 10 |
244 | vr_mod_10 := vr % 10 |
245 | vm_is_trailing_zeros = vm_is_trailing_zeros && vm_mod_10 == 0 |
246 | vr_is_trailing_zeros = vr_is_trailing_zeros && last_removed_digit == 0 |
247 | last_removed_digit = u8(vr_mod_10) |
248 | vr = vr_div_10 |
249 | vp = vp_div_10 |
250 | vm = vm_div_10 |
251 | removed++ |
252 | } |
253 | if vm_is_trailing_zeros { |
254 | for { |
255 | vm_div_10 := vm / 10 |
256 | vm_mod_10 := vm % 10 |
257 | if vm_mod_10 != 0 { |
258 | break |
259 | } |
260 | vp_div_10 := vp / 10 |
261 | vr_div_10 := vr / 10 |
262 | vr_mod_10 := vr % 10 |
263 | vr_is_trailing_zeros = vr_is_trailing_zeros && last_removed_digit == 0 |
264 | last_removed_digit = u8(vr_mod_10) |
265 | vr = vr_div_10 |
266 | vp = vp_div_10 |
267 | vm = vm_div_10 |
268 | removed++ |
269 | } |
270 | } |
271 | if vr_is_trailing_zeros && last_removed_digit == 5 && (vr % 2) == 0 { |
272 | // Round even if the exact number is .....50..0. |
273 | last_removed_digit = 4 |
274 | } |
275 | out = vr |
276 | // We need to take vr + 1 if vr is outside bounds |
277 | // or we need to round up. |
278 | if (vr == vm && (!accept_bounds || !vm_is_trailing_zeros)) || last_removed_digit >= 5 { |
279 | out++ |
280 | } |
281 | } else { |
282 | // Specialized for the common case (~99.3%). |
283 | // Percentages below are relative to this. |
284 | mut round_up := false |
285 | for vp / 100 > vm / 100 { |
286 | // Optimization: remove two digits at a time (~86.2%). |
287 | round_up = (vr % 100) >= 50 |
288 | vr /= 100 |
289 | vp /= 100 |
290 | vm /= 100 |
291 | removed += 2 |
292 | } |
293 | // Loop iterations below (approximately), without optimization above: |
294 | // 0: 0.03%, 1: 13.8%, 2: 70.6%, 3: 14.0%, 4: 1.40%, 5: 0.14%, 6+: 0.02% |
295 | // Loop iterations below (approximately), with optimization above: |
296 | // 0: 70.6%, 1: 27.8%, 2: 1.40%, 3: 0.14%, 4+: 0.02% |
297 | for vp / 10 > vm / 10 { |
298 | round_up = (vr % 10) >= 5 |
299 | vr /= 10 |
300 | vp /= 10 |
301 | vm /= 10 |
302 | removed++ |
303 | } |
304 | // We need to take vr + 1 if vr is outside bounds |
305 | // or we need to round up. |
306 | out = vr + bool_to_u64(vr == vm || round_up) |
307 | } |
308 | |
309 | return Dec64{ |
310 | m: out |
311 | e: e10 + removed |
312 | } |
313 | } |
314 | |
315 | //============================================================================= |
316 | // String Functions |
317 | //============================================================================= |
318 | |
319 | // f64_to_str return a string in scientific notation with max n_digit after the dot |
320 | pub fn f64_to_str(f f64, n_digit int) string { |
321 | u := math.f64_bits(f) |
322 | neg := (u >> (mantbits64 + expbits64)) != 0 |
323 | mant := u & ((u64(1) << mantbits64) - u64(1)) |
324 | exp := (u >> mantbits64) & ((u64(1) << expbits64) - u64(1)) |
325 | // println("s:${neg} mant:${mant} exp:${exp} float:${f} byte:${u1.u:016lx}") |
326 | |
327 | // Exit early for easy cases. |
328 | if exp == maxexp64 || (exp == 0 && mant == 0) { |
329 | return get_string_special(neg, exp == 0, mant == 0) |
330 | } |
331 | |
332 | mut d, ok := f64_to_decimal_exact_int(mant, exp) |
333 | if !ok { |
334 | // println("to_decimal") |
335 | d = f64_to_decimal(mant, exp) |
336 | } |
337 | // println("${d.m} ${d.e}") |
338 | return d.get_string_64(neg, n_digit, 0) |
339 | } |