1 | module strconv |
2 | |
3 | /*============================================================================= |
4 | |
5 | f32 to string |
6 | |
7 | Copyright (c) 2019-2023 Dario Deledda. All rights reserved. |
8 | Use of this source code is governed by an MIT license |
9 | that can be found in the LICENSE file. |
10 | |
11 | This file contains the f32 to string functions |
12 | |
13 | These functions are based on the work of: |
14 | Publication:PLDI 2018: Proceedings of the 39th ACM SIGPLAN |
15 | Conference on Programming Language Design and ImplementationJune 2018 |
16 | Pages 270–282 https://doi.org/10.1145/3192366.3192369 |
17 | |
18 | inspired by the Go version here: |
19 | https://github.com/cespare/ryu/tree/ba56a33f39e3bbbfa409095d0f9ae168a595feea |
20 | |
21 | =============================================================================*/ |
22 | |
23 | // pow of ten table used by n_digit reduction |
24 | const ( |
25 | ten_pow_table_32 = [ |
26 | u32(1), |
27 | u32(10), |
28 | u32(100), |
29 | u32(1000), |
30 | u32(10000), |
31 | u32(100000), |
32 | u32(1000000), |
33 | u32(10000000), |
34 | u32(100000000), |
35 | u32(1000000000), |
36 | u32(10000000000), |
37 | u32(100000000000), |
38 | ]! |
39 | ) |
40 | |
41 | //============================================================================= |
42 | // Conversion Functions |
43 | //============================================================================= |
44 | const ( |
45 | mantbits32 = u32(23) |
46 | expbits32 = u32(8) |
47 | bias32 = 127 // f32 exponent bias |
48 | maxexp32 = 255 |
49 | ) |
50 | |
51 | // max 46 char |
52 | // -3.40282346638528859811704183484516925440e+38 |
53 | [direct_array_access] |
54 | pub fn (d Dec32) get_string_32(neg bool, i_n_digit int, i_pad_digit int) string { |
55 | n_digit := i_n_digit + 1 |
56 | pad_digit := i_pad_digit + 1 |
57 | mut out := d.m |
58 | // mut out_len := decimal_len_32(out) |
59 | mut out_len := dec_digits(out) |
60 | out_len_original := out_len |
61 | |
62 | mut fw_zeros := 0 |
63 | if pad_digit > out_len { |
64 | fw_zeros = pad_digit - out_len |
65 | } |
66 | |
67 | mut buf := []u8{len: int(out_len + 5 + 1 + 1)} // sign + mant_len + . + e + e_sign + exp_len(2) + \0} |
68 | mut i := 0 |
69 | |
70 | if neg { |
71 | if buf.data != 0 { |
72 | // The buf.data != 0 check here, is needed for clean compilation |
73 | // with `-cc gcc -cstrict -prod`. Without it, gcc produces: |
74 | // error: potential null pointer dereference |
75 | buf[i] = `-` |
76 | } |
77 | i++ |
78 | } |
79 | |
80 | mut disp := 0 |
81 | if out_len <= 1 { |
82 | disp = 1 |
83 | } |
84 | |
85 | if n_digit < out_len { |
86 | // println("orig: ${out_len_original}") |
87 | out += strconv.ten_pow_table_32[out_len - n_digit - 1] * 5 // round to up |
88 | out /= strconv.ten_pow_table_32[out_len - n_digit] |
89 | out_len = n_digit |
90 | } |
91 | |
92 | y := i + out_len |
93 | mut x := 0 |
94 | for x < (out_len - disp - 1) { |
95 | buf[y - x] = `0` + u8(out % 10) |
96 | out /= 10 |
97 | i++ |
98 | x++ |
99 | } |
100 | |
101 | // no decimal digits needed, end here |
102 | if i_n_digit == 0 { |
103 | unsafe { |
104 | buf[i] = 0 |
105 | return tos(&u8(&buf[0]), i) |
106 | } |
107 | } |
108 | |
109 | if out_len >= 1 { |
110 | buf[y - x] = `.` |
111 | x++ |
112 | i++ |
113 | } |
114 | |
115 | if y - x >= 0 { |
116 | buf[y - x] = `0` + u8(out % 10) |
117 | i++ |
118 | } |
119 | |
120 | for fw_zeros > 0 { |
121 | buf[i] = `0` |
122 | i++ |
123 | fw_zeros-- |
124 | } |
125 | |
126 | buf[i] = `e` |
127 | i++ |
128 | |
129 | mut exp := d.e + out_len_original - 1 |
130 | if exp < 0 { |
131 | buf[i] = `-` |
132 | i++ |
133 | exp = -exp |
134 | } else { |
135 | buf[i] = `+` |
136 | i++ |
137 | } |
138 | |
139 | // Always print two digits to match strconv's formatting. |
140 | d1 := exp % 10 |
141 | d0 := exp / 10 |
142 | buf[i] = `0` + u8(d0) |
143 | i++ |
144 | buf[i] = `0` + u8(d1) |
145 | i++ |
146 | buf[i] = 0 |
147 | |
148 | return unsafe { |
149 | tos(&u8(&buf[0]), i) |
150 | } |
151 | } |
152 | |
153 | fn f32_to_decimal_exact_int(i_mant u32, exp u32) (Dec32, bool) { |
154 | mut d := Dec32{} |
155 | e := exp - strconv.bias32 |
156 | if e > strconv.mantbits32 { |
157 | return d, false |
158 | } |
159 | shift := strconv.mantbits32 - e |
160 | mant := i_mant | 0x0080_0000 // implicit 1 |
161 | // mant := i_mant | (1 << mantbits32) // implicit 1 |
162 | d.m = mant >> shift |
163 | if (d.m << shift) != mant { |
164 | return d, false |
165 | } |
166 | for (d.m % 10) == 0 { |
167 | d.m /= 10 |
168 | d.e++ |
169 | } |
170 | return d, true |
171 | } |
172 | |
173 | fn f32_to_decimal(mant u32, exp u32) Dec32 { |
174 | mut e2 := 0 |
175 | mut m2 := u32(0) |
176 | if exp == 0 { |
177 | // We subtract 2 so that the bounds computation has |
178 | // 2 additional bits. |
179 | e2 = 1 - strconv.bias32 - int(strconv.mantbits32) - 2 |
180 | m2 = mant |
181 | } else { |
182 | e2 = int(exp) - strconv.bias32 - int(strconv.mantbits32) - 2 |
183 | m2 = (u32(1) << strconv.mantbits32) | mant |
184 | } |
185 | even := (m2 & 1) == 0 |
186 | accept_bounds := even |
187 | |
188 | // Step 2: Determine the interval of valid decimal representations. |
189 | mv := u32(4 * m2) |
190 | mp := u32(4 * m2 + 2) |
191 | mm_shift := bool_to_u32(mant != 0 || exp <= 1) |
192 | mm := u32(4 * m2 - 1 - mm_shift) |
193 | |
194 | mut vr := u32(0) |
195 | mut vp := u32(0) |
196 | mut vm := u32(0) |
197 | mut e10 := 0 |
198 | mut vm_is_trailing_zeros := false |
199 | mut vr_is_trailing_zeros := false |
200 | mut last_removed_digit := u8(0) |
201 | |
202 | if e2 >= 0 { |
203 | q := log10_pow2(e2) |
204 | e10 = int(q) |
205 | k := pow5_inv_num_bits_32 + pow5_bits(int(q)) - 1 |
206 | i := -e2 + int(q) + k |
207 | |
208 | vr = mul_pow5_invdiv_pow2(mv, q, i) |
209 | vp = mul_pow5_invdiv_pow2(mp, q, i) |
210 | vm = mul_pow5_invdiv_pow2(mm, q, i) |
211 | if q != 0 && (vp - 1) / 10 <= vm / 10 { |
212 | // We need to know one removed digit even if we are not |
213 | // going to loop below. We could use q = X - 1 above, |
214 | // except that would require 33 bits for the result, and |
215 | // we've found that 32-bit arithmetic is faster even on |
216 | // 64-bit machines. |
217 | l := pow5_inv_num_bits_32 + pow5_bits(int(q - 1)) - 1 |
218 | last_removed_digit = u8(mul_pow5_invdiv_pow2(mv, q - 1, -e2 + int(q - 1) + l) % 10) |
219 | } |
220 | if q <= 9 { |
221 | // The largest power of 5 that fits in 24 bits is 5^10, |
222 | // but q <= 9 seems to be safe as well. Only one of mp, |
223 | // mv, and mm can be a multiple of 5, if any. |
224 | if mv % 5 == 0 { |
225 | vr_is_trailing_zeros = multiple_of_power_of_five_32(mv, q) |
226 | } else if accept_bounds { |
227 | vm_is_trailing_zeros = multiple_of_power_of_five_32(mm, q) |
228 | } else if multiple_of_power_of_five_32(mp, q) { |
229 | vp-- |
230 | } |
231 | } |
232 | } else { |
233 | q := log10_pow5(-e2) |
234 | e10 = int(q) + e2 |
235 | i := -e2 - int(q) |
236 | k := pow5_bits(i) - pow5_num_bits_32 |
237 | mut j := int(q) - k |
238 | vr = mul_pow5_div_pow2(mv, u32(i), j) |
239 | vp = mul_pow5_div_pow2(mp, u32(i), j) |
240 | vm = mul_pow5_div_pow2(mm, u32(i), j) |
241 | if q != 0 && ((vp - 1) / 10) <= vm / 10 { |
242 | j = int(q) - 1 - (pow5_bits(i + 1) - pow5_num_bits_32) |
243 | last_removed_digit = u8(mul_pow5_div_pow2(mv, u32(i + 1), j) % 10) |
244 | } |
245 | if q <= 1 { |
246 | // {vr,vp,vm} is trailing zeros if {mv,mp,mm} has at |
247 | // least q trailing 0 bits. mv = 4 * m2, so it always |
248 | // has at least two trailing 0 bits. |
249 | vr_is_trailing_zeros = true |
250 | if accept_bounds { |
251 | // mm = mv - 1 - mm_shift, so it has 1 trailing 0 bit |
252 | // if mm_shift == 1. |
253 | vm_is_trailing_zeros = mm_shift == 1 |
254 | } else { |
255 | // mp = mv + 2, so it always has at least one |
256 | // trailing 0 bit. |
257 | vp-- |
258 | } |
259 | } else if q < 31 { |
260 | vr_is_trailing_zeros = multiple_of_power_of_two_32(mv, q - 1) |
261 | } |
262 | } |
263 | |
264 | // Step 4: Find the shortest decimal representation |
265 | // in the interval of valid representations. |
266 | mut removed := 0 |
267 | mut out := u32(0) |
268 | if vm_is_trailing_zeros || vr_is_trailing_zeros { |
269 | // General case, which happens rarely (~4.0%). |
270 | for vp / 10 > vm / 10 { |
271 | vm_is_trailing_zeros = vm_is_trailing_zeros && (vm % 10) == 0 |
272 | vr_is_trailing_zeros = vr_is_trailing_zeros && last_removed_digit == 0 |
273 | last_removed_digit = u8(vr % 10) |
274 | vr /= 10 |
275 | vp /= 10 |
276 | vm /= 10 |
277 | removed++ |
278 | } |
279 | if vm_is_trailing_zeros { |
280 | for vm % 10 == 0 { |
281 | vr_is_trailing_zeros = vr_is_trailing_zeros && last_removed_digit == 0 |
282 | last_removed_digit = u8(vr % 10) |
283 | vr /= 10 |
284 | vp /= 10 |
285 | vm /= 10 |
286 | removed++ |
287 | } |
288 | } |
289 | if vr_is_trailing_zeros && last_removed_digit == 5 && (vr % 2) == 0 { |
290 | // Round even if the exact number is .....50..0. |
291 | last_removed_digit = 4 |
292 | } |
293 | out = vr |
294 | // We need to take vr + 1 if vr is outside bounds |
295 | // or we need to round up. |
296 | if (vr == vm && (!accept_bounds || !vm_is_trailing_zeros)) || last_removed_digit >= 5 { |
297 | out++ |
298 | } |
299 | } else { |
300 | // Specialized for the common case (~96.0%). Percentages below |
301 | // are relative to this. Loop iterations below (approximately): |
302 | // 0: 13.6%, 1: 70.7%, 2: 14.1%, 3: 1.39%, 4: 0.14%, 5+: 0.01% |
303 | for vp / 10 > vm / 10 { |
304 | last_removed_digit = u8(vr % 10) |
305 | vr /= 10 |
306 | vp /= 10 |
307 | vm /= 10 |
308 | removed++ |
309 | } |
310 | // We need to take vr + 1 if vr is outside bounds |
311 | // or we need to round up. |
312 | out = vr + bool_to_u32(vr == vm || last_removed_digit >= 5) |
313 | } |
314 | |
315 | return Dec32{ |
316 | m: out |
317 | e: e10 + removed |
318 | } |
319 | } |
320 | |
321 | //============================================================================= |
322 | // String Functions |
323 | //============================================================================= |
324 | |
325 | // f32_to_str returns a `string` in scientific notation with max `n_digit` after the dot. |
326 | pub fn f32_to_str(f f32, n_digit int) string { |
327 | mut u1 := Uf32{} |
328 | u1.f = f |
329 | u := unsafe { u1.u } |
330 | |
331 | neg := (u >> (strconv.mantbits32 + strconv.expbits32)) != 0 |
332 | mant := u & ((u32(1) << strconv.mantbits32) - u32(1)) |
333 | exp := (u >> strconv.mantbits32) & ((u32(1) << strconv.expbits32) - u32(1)) |
334 | |
335 | // println("${neg} ${mant} e ${exp-bias32}") |
336 | |
337 | // Exit early for easy cases. |
338 | if exp == strconv.maxexp32 || (exp == 0 && mant == 0) { |
339 | return get_string_special(neg, exp == 0, mant == 0) |
340 | } |
341 | |
342 | mut d, ok := f32_to_decimal_exact_int(mant, exp) |
343 | if !ok { |
344 | // println("with exp form") |
345 | d = f32_to_decimal(mant, exp) |
346 | } |
347 | |
348 | // println("${d.m} ${d.e}") |
349 | return d.get_string_32(neg, n_digit, 0) |
350 | } |
351 | |
352 | // f32_to_str_pad returns a `string` in scientific notation with max `n_digit` after the dot. |
353 | pub fn f32_to_str_pad(f f32, n_digit int) string { |
354 | mut u1 := Uf32{} |
355 | u1.f = f |
356 | u := unsafe { u1.u } |
357 | |
358 | neg := (u >> (strconv.mantbits32 + strconv.expbits32)) != 0 |
359 | mant := u & ((u32(1) << strconv.mantbits32) - u32(1)) |
360 | exp := (u >> strconv.mantbits32) & ((u32(1) << strconv.expbits32) - u32(1)) |
361 | |
362 | // println("${neg} ${mant} e ${exp-bias32}") |
363 | |
364 | // Exit early for easy cases. |
365 | if exp == strconv.maxexp32 || (exp == 0 && mant == 0) { |
366 | return get_string_special(neg, exp == 0, mant == 0) |
367 | } |
368 | |
369 | mut d, ok := f32_to_decimal_exact_int(mant, exp) |
370 | if !ok { |
371 | // println("with exp form") |
372 | d = f32_to_decimal(mant, exp) |
373 | } |
374 | |
375 | // println("${d.m} ${d.e}") |
376 | return d.get_string_32(neg, n_digit, n_digit) |
377 | } |