uscale.go

     1  // Copyright 2026 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Floating point binary↔decimal conversion by fast unrounded scaling.
     6  // See “Floating-Point Printing and Parsing Can Be Simple And Fast”,
     7  // https://research.swtch.com/fp
     8  
     9  package strconv
    10  
    11  import (
    12  	"math/bits"
    13  	"unsafe"
    14  )
    15  
    16  // bool2 converts b to an integer: 1 for true, 0 for false.
    17  func bool2[T ~int | ~uint32 | ~uint64](b bool) T {
    18  	if b {
    19  		return 1
    20  	}
    21  	return 0
    22  }
    23  
    24  // pack64 takes m, e and returns f = m * 2**e.
    25  // It assumes the caller has provided a 53-bit mantissa m
    26  // and an exponent that is in range for the mantissa.
    27  func pack64(m uint64, e int) (float64, error) {
    28  	if m&(1<<52) == 0 {
    29  		return float64frombits(m), nil
    30  	}
    31  	if e >= 0x7FF-1075 {
    32  		return float64frombits(m&(1<<63) | 0x7ff<<52), ErrRange
    33  	}
    34  	return float64frombits(m&^(1<<52) | uint64(1075+e)<<52), nil
    35  }
    36  
    37  // pack32 takes m, e and returns f = m * 2**e.
    38  // It assumes the caller has provided a 24-bit mantissa m
    39  // and an exponent that is in range for the mantissa.
    40  func pack32(m uint32, e int) (float32, error) {
    41  	if m&(1<<23) == 0 {
    42  		return float32frombits(m), nil
    43  	}
    44  	if e >= 0xFF-150 {
    45  		return float32frombits(m&(1<<31) | 0xff<<23), ErrRange
    46  	}
    47  	return float32frombits(m&^(1<<23) | uint32(150+e)<<23), nil
    48  }
    49  
    50  // An unrounded represents an unrounded value.
    51  type unrounded uint64
    52  
    53  func (u unrounded) floor() uint64         { return uint64((u + 0) >> 2) }
    54  func (u unrounded) roundHalfDown() uint64 { return uint64((u + 1) >> 2) }
    55  func (u unrounded) round() uint64         { return uint64((u + 1 + (u>>2)&1) >> 2) }
    56  func (u unrounded) roundHalfUp() uint64   { return uint64((u + 2) >> 2) }
    57  func (u unrounded) ceil() uint64          { return uint64((u + 3) >> 2) }
    58  func (u unrounded) nudge(δ int) unrounded { return u + unrounded(δ) }
    59  
    60  func (u unrounded) div(d uint64) unrounded {
    61  	x := uint64(u)
    62  	return unrounded(x/d) | u&1 | bool2[unrounded](x%d != 0)
    63  }
    64  
    65  func (u unrounded) rsh(s int) unrounded {
    66  	return u>>s | u&1 | bool2[unrounded](u&((1<<s)-1) != 0)
    67  }
    68  
    69  // log10Pow2(x) returns ⌊log₁₀ 2**x⌋ = ⌊x * log₁₀ 2⌋.
    70  func log10Pow2(x int) int {
    71  	// log₁₀ 2 ≈ 0.30102999566 ≈ 78913 / 2^18
    72  	return (x * 78913) >> 18
    73  }
    74  
    75  // log2Pow10(x) returns ⌊log₂ 10**x⌋ = ⌊x * log₂ 10⌋.
    76  func log2Pow10(x int) int {
    77  	// log₂ 10 ≈ 3.32192809489 ≈ 108853 / 2^15
    78  	return (x * 108853) >> 15
    79  }
    80  
    81  // uint64pow10[x] is 10**x.
    82  var uint64pow10 = [...]uint64{
    83  	1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
    84  	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
    85  }
    86  
    87  // fixedWidthFloat returns the n-digit decimal form of f = m * 2**e as d * 10**p.
    88  // n can be at most 18.
    89  // If fmt == 'f' then n is a conservative estimate of the number of digits,
    90  // and digits are discarded to match prec.
    91  func fixedWidthFloat(m uint64, e, n, prec int, fmt byte) (d uint64, p int) {
    92  	p = n - 1 - log10Pow2(e+63)
    93  	var pre scaler
    94  	prescale(&pre, e, p, log2Pow10(p))
    95  	u := uscale(m, &pre)
    96  	if u >= unmin(uint64pow10[n]) {
    97  		u = u.div(10)
    98  		p--
    99  	}
   100  	if fmt == 'f' {
   101  		for p > prec {
   102  			u = u.div(10)
   103  			p--
   104  		}
   105  	}
   106  	return u.round(), -p
   107  }
   108  
   109  // parseFloat64 rounds d * 10**p to the nearest float64 f.
   110  // d can have at most 19 digits.
   111  // It returns ErrRange if the result rounds to infinity.
   112  func parseFloat64(d uint64, p int, sign uint64) (float64, error) {
   113  	b := bits.Len64(d)
   114  	lp := log2Pow10(p)
   115  	e := min(1074, 53-b-lp)
   116  	var pre scaler
   117  	prescale(&pre, e-(64-b), p, lp)
   118  	if pre.s >= 64 {
   119  		return float64frombits(sign | 0), nil
   120  	}
   121  	u := uscale(d<<(64-b), &pre)
   122  
   123  	// This block is branch-free code for:
   124  	//	if u.round() >= 1<<53 {
   125  	//		u = u.rsh(1)
   126  	//		e = e - 1
   127  	//	}
   128  	s := bool2[int](u >= unmin(1<<53))
   129  	u = u>>s | u&1
   130  	e = e - s
   131  
   132  	return pack64(sign|u.round(), -e)
   133  }
   134  
   135  // parseFloat32 rounds d * 10**p to the nearest float32 f.
   136  // d can have at most 19 digits.
   137  // It returns ErrRange if the result rounds to infinity.
   138  func parseFloat32(d uint64, p int, sign uint32) (float32, error) {
   139  	b := bits.Len64(d)
   140  	lp := log2Pow10(p)
   141  	e := min(149, 24-b-lp)
   142  	var pre scaler
   143  	prescale(&pre, e-(64-b), p, lp)
   144  	if pre.s >= 64 {
   145  		return float32frombits(sign | 0), nil
   146  	}
   147  	u := uscale(d<<(64-b), &pre)
   148  
   149  	// This block is branch-free code for:
   150  	//	if u.round() >= 1<<24 {
   151  	//		u = u.rsh(1)
   152  	//		e = e - 1
   153  	//	}
   154  	s := bool2[int](u >= unmin(1<<24))
   155  	u = u>>s | u&1
   156  	e = e - s
   157  
   158  	return pack32(sign|uint32(u.round()), -e)
   159  }
   160  
   161  // unmin returns the minimum unrounded that rounds to x.
   162  func unmin(x uint64) unrounded {
   163  	return unrounded(x<<2 - 2)
   164  }
   165  
   166  // shortFloat computes the shortest formatting of f,
   167  // using as few digits as possible that will still round trip
   168  // back to the original float.
   169  func shortFloat[F float32 | float64](m uint64, e int) (d uint64, p int) {
   170  	var mantBits, minExp int // parameterized constants
   171  	switch 8 * unsafe.Sizeof(F(0)) {
   172  	case 32:
   173  		mantBits = float32MantBits
   174  		minExp = float32MinExp
   175  	case 64:
   176  		mantBits = float64MantBits
   177  		minExp = float64MinExp
   178  	}
   179  
   180  	// Note: these cases could be factored a little more,
   181  	// but in the first two branches, z is a constant,
   182  	// allowing the compiler to greatly simplify the code.
   183  	var min, max uint64
   184  	var odd int
   185  	z := 63 - mantBits
   186  	if m == 1<<63 && e > minExp {
   187  		p = -skewed(e + z)
   188  		min = m - 1<<(z-2) // min = m - 1/4 * 2**(e+z)
   189  		max = m + 1<<(z-1) // max = m + 1/2 * 2**(e+z)
   190  		odd = int(m>>z) & 1
   191  	} else if e >= minExp {
   192  		p = -log10Pow2(e + z)
   193  		min = m - 1<<(z-1) // min = m - 1/2 * 2**(e+z)
   194  		max = m + 1<<(z-1) // max = m + 1/2 * 2**(e+z)
   195  		odd = int(m>>z) & 1
   196  	} else {
   197  		z = z + (minExp - e)
   198  		p = -log10Pow2(e + z)
   199  		min = m - 1<<(z-1) // min = m - 1/2 * 2**(e+z)
   200  		max = m + 1<<(z-1) // max = m + 1/2 * 2**(e+z)
   201  		odd = int(m>>z) & 1
   202  	}
   203  
   204  	var pre scaler
   205  	prescale(&pre, e, p, log2Pow10(p))
   206  	dmin := uscale(min, &pre).nudge(+odd).ceil()
   207  	dmax := uscale(max, &pre).nudge(-odd).floor()
   208  
   209  	if d = dmax / 10; d*10 >= dmin {
   210  		return d, -(p - 1)
   211  	}
   212  	if d = dmin; d < dmax {
   213  		d = uscale(m, &pre).round()
   214  	}
   215  	return d, -p
   216  }
   217  
   218  // skewed computes the skewed footprint of m * 2**e,
   219  // which is ⌊log₁₀ 3/4 * 2**e⌋ = ⌊e*(log₁₀ 2)-(log₁₀ 4/3)⌋.
   220  func skewed(e int) int {
   221  	return (e*631305 - 261663) >> 21
   222  }
   223  
   224  // A pmHiLo represents hi<<64 - lo.
   225  type pmHiLo struct {
   226  	hi uint64
   227  	lo uint64
   228  }
   229  
   230  // A scaler holds derived scaling constants for a given e, p pair.
   231  type scaler struct {
   232  	// Note: using pm pmHiLo here nudges uscale just over the inlining boundary. Don't.
   233  	pmHi uint64
   234  	pmLo uint64
   235  	s    int
   236  }
   237  
   238  // prescale returns the scaling constants for e, p.
   239  // lp must be log2Pow10(p).
   240  // The caller is responsible for either avoiding e, p pairs
   241  // that cause pre.s < 0 or pre.s >= 64, or else handling
   242  // those cases before passing the result to uscale.
   243  // In practice, pre.s < 0 would indicate a buggy caller
   244  // and pre.s >= 64 can only happen for parsing and is
   245  // picked off at those call sites.
   246  func prescale(pre *scaler, e, p, lp int) {
   247  	pre.pmHi = pow10Tab[p-pow10Min].hi
   248  	pre.pmLo = pow10Tab[p-pow10Min].lo
   249  	pre.s = -(e + lp + 3)
   250  }
   251  
   252  // uscale returns unround(x * 2**e * 10**p).
   253  // The caller should pass &pre for prescale(&pre, e, p, log2Pow10(p))
   254  // and should have left-justified x so its high bit is set.
   255  // The caller is also responsible for checking that c.s < 64.
   256  // For formatting, that's always true.
   257  // For parsing, the caller needs to pick it off early and return a signed 0.
   258  func uscale(x uint64, c *scaler) unrounded {
   259  	hi, mid := bits.Mul64(x, c.pmHi)
   260  	s := c.s & 63 // make shifts cheaper
   261  	if hi>>s<<s != hi {
   262  		return unrounded(hi>>s | 1)
   263  	}
   264  	mid2, _ := bits.Mul64(x, c.pmLo)
   265  	hi -= bool2[uint64](mid < mid2)
   266  	return unrounded(hi>>s | bool2[uint64](mid-mid2 > 1))
   267  }
   268  
   269  // setDigits sets digs to the nd digits described by d, p.
   270  func setDigits(s []byte, d uint64, p, nd int) (dp, nzd int) {
   271  	// Note: nd <= len(s) is guaranteed by caller,
   272  	// but writing it explicitly here lets the compiler know,
   273  	// so that it can remove the bounds check in the loop.
   274  	// (The slice s[:nd] not panicking only establishes nd <= cap(s).)
   275  	if nd <= len(s) {
   276  		formatBase10(s[:nd], d)
   277  		dp = nd + p
   278  		for nd > 0 && s[nd-1] == '0' {
   279  			nd--
   280  		}
   281  	}
   282  	return dp, nd
   283  }
   284  
   285  // numDigits returns the number of decimal digits in d.
   286  // It requires d ≥ 1.
   287  func numDigits(d uint64) int {
   288  	nd := log10Pow2(bits.Len64(d))
   289  	return nd + bool2[int](d >= uint64pow10[nd])
   290  }
   291
View as plain text