niko_trust/pkg/tce/number.go

package tce

import "math/big"

// Number canonicalization, implementing PROTOCOL.md section 5.1.
//
// Numbers are carried as decimal text rather than as binary floating point. A
// JSON number is an arbitrary-precision decimal literal, so 1, 1.0 and 1e0 are
// one value written three ways. Converting through an IEEE-754 double would
// lose precision above 2^53 and would make the signed bytes depend on the
// implementation's parsing and rounding, which is exactly the ambiguity the
// canonical encoding exists to remove.
//
// The canonical form is plain decimal with no exponent: an optional minus
// sign, digits without a leading zero, and an optional fractional part without
// trailing zeros. Negative zero is not representable and canonicalizes to "0".

// CanonicalNumber reduces a JSON number token to its unique canonical form.
//
// The input must be the exact source token as it appeared in the document.
// The output is ASCII and is what gets encoded under value tag 0x04.
func CanonicalNumber(token string) (string, error) {
	if len(token) == 0 || len(token) > MaxNumberSource {
		return "", ErrNumberFormat
	}

	intPart, fracPart, expPart, negative, err := splitNumber(token)
	if err != nil {
		return "", err
	}

	// The exponent digit count is bounded before conversion so that a token
	// such as 1e999999999 is refused rather than driving a huge shift.
	if len(expPart) > 4 {
		return "", ErrNumberRange
	}
	exp := 0
	expNeg := false
	if len(expPart) > 0 {
		i := 0
		if expPart[0] == '+' || expPart[0] == '-' {
			expNeg = expPart[0] == '-'
			i = 1
		}
		digits := expPart[i:]
		if len(digits) == 0 || len(digits) > 4 {
			return "", ErrNumberRange
		}
		for _, c := range []byte(digits) {
			exp = exp*10 + int(c-'0')
		}
		if expNeg {
			exp = -exp
		}
	}

	// value = sign * mantissa * 10^scale
	digits := intPart + fracPart
	scale := exp - len(fracPart)

	mantissa, ok := new(big.Int).SetString(digits, 10)
	if !ok {
		return "", ErrNumberFormat
	}

	if mantissa.Sign() == 0 {
		// Maps -0, 0.0 and 0e10 all to "0".
		return "0", nil
	}

	// Strip factors of ten that exist only to pad the fraction.
	ten := big.NewInt(10)
	qr := new(big.Int)
	rem := new(big.Int)
	for scale < 0 {
		qr.QuoRem(mantissa, ten, rem)
		if rem.Sign() != 0 {
			break
		}
		mantissa.Set(qr)
		scale++
	}

	// Bound the work before materialising the decimal form: a positive scale
	// appends that many zeros, so it must be checked before the string is
	// built rather than after.
	ds := mantissa.String()
	if ds[0] == '-' {
		ds = ds[1:]
	}
	if scale > 0 && len(ds)+scale > MaxNumberIntDigs {
		return "", ErrNumberRange
	}
	if scale < 0 && -scale > MaxNumberFracDig+len(ds) {
		return "", ErrNumberRange
	}

	var intDigits, fracDigits string
	if scale >= 0 {
		intDigits = ds + zeros(scale)
	} else {
		point := len(ds) + scale
		if point <= 0 {
			intDigits = "0"
			fracDigits = zeros(-point) + ds
		} else {
			intDigits = ds[:point]
			fracDigits = ds[point:]
		}
	}

	if len(trimLeadingZeros(intDigits)) > MaxNumberIntDigs {
		return "", ErrNumberRange
	}
	if len(fracDigits) > MaxNumberFracDig {
		return "", ErrNumberRange
	}

	n := len(intDigits)
	if negative {
		n++
	}
	if len(fracDigits) > 0 {
		n += 1 + len(fracDigits)
	}
	if n > MaxNumberToken {
		return "", ErrNumberRange
	}

	out := make([]byte, 0, n)
	if negative {
		out = append(out, '-')
	}
	out = append(out, intDigits...)
	if len(fracDigits) > 0 {
		out = append(out, '.')
		out = append(out, fracDigits...)
	}
	return string(out), nil
}

// splitNumber validates the JSON number grammar from RFC 8259 and returns its
// parts:
//
//	-? ( 0 | [1-9][0-9]* ) ( "." [0-9]+ )? ( [eE] [+-]? [0-9]+ )?
//
// The grammar is checked by hand rather than with a regular expression so
// that the accepted language is visible and no regexp engine behaviour is
// involved in deciding what gets signed.
func splitNumber(s string) (intPart, fracPart, expPart string, negative bool, err error) {
	i := 0
	if i < len(s) && s[i] == '-' {
		negative = true
		i++
	}

	// Integer part: a single 0, or a non-zero digit followed by digits.
	start := i
	if i >= len(s) {
		return "", "", "", false, ErrNumberFormat
	}
	if s[i] == '0' {
		i++
	} else if s[i] >= '1' && s[i] <= '9' {
		for i < len(s) && isDigit(s[i]) {
			i++
		}
	} else {
		return "", "", "", false, ErrNumberFormat
	}
	intPart = s[start:i]

	// Leading zeros are rejected by the grammar above, which is what makes
	// "01" invalid rather than a second spelling of 1.
	if len(intPart) > 1 && intPart[0] == '0' {
		return "", "", "", false, ErrNumberFormat
	}

	// Optional fraction.
	if i < len(s) && s[i] == '.' {
		i++
		fs := i
		for i < len(s) && isDigit(s[i]) {
			i++
		}
		if i == fs {
			return "", "", "", false, ErrNumberFormat
		}
		fracPart = s[fs:i]
	}

	// Optional exponent.
	if i < len(s) && (s[i] == 'e' || s[i] == 'E') {
		i++
		es := i
		if i < len(s) && (s[i] == '+' || s[i] == '-') {
			i++
		}
		ds := i
		for i < len(s) && isDigit(s[i]) {
			i++
		}
		if i == ds {
			return "", "", "", false, ErrNumberFormat
		}
		expPart = s[es:i]
	}

	if i != len(s) {
		return "", "", "", false, ErrNumberFormat
	}
	return intPart, fracPart, expPart, negative, nil
}

func isDigit(c byte) bool { return c >= '0' && c <= '9' }

func zeros(n int) string {
	if n <= 0 {
		return ""
	}
	b := make([]byte, n)
	for i := range b {
		b[i] = '0'
	}
	return string(b)
}

func trimLeadingZeros(s string) string {
	i := 0
	for i < len(s)-1 && s[i] == '0' {
		i++
	}
	return s[i:]
}

// IsCanonicalNumber reports whether token is already in canonical form. The
// decoder uses this to reject any other spelling rather than silently
// accepting it.
func IsCanonicalNumber(token string) bool {
	c, err := CanonicalNumber(token)
	return err == nil && c == token
}