podman

1
// Copyright (c) 2012-2020 Ugorji Nwoke. All rights reserved.
2
// Use of this source code is governed by a MIT license found in the LICENSE file.
3

4
package codec
5

6
import (
7
	"math"
8
	"strconv"
9
)
10

11
// Per go spec, floats are represented in memory as
12
// IEEE single or double precision floating point values.
13
//
14
// We also looked at the source for stdlib math/modf.go,
15
// reviewed https://github.com/chewxy/math32
16
// and read wikipedia documents describing the formats.
17
//
18
// It became clear that we could easily look at the bits to determine
19
// whether any fraction exists.
20

21
func parseFloat32(b []byte) (f float32, err error) {
22
	return parseFloat32_custom(b)
23
}
24

25
func parseFloat64(b []byte) (f float64, err error) {
26
	return parseFloat64_custom(b)
27
}
28

29
func parseFloat32_strconv(b []byte) (f float32, err error) {
30
	f64, err := strconv.ParseFloat(stringView(b), 32)
31
	f = float32(f64)
32
	return
33
}
34

35
func parseFloat64_strconv(b []byte) (f float64, err error) {
36
	return strconv.ParseFloat(stringView(b), 64)
37
}
38

39
// ------ parseFloat custom below --------
40

41
// JSON really supports decimal numbers in base 10 notation, with exponent support.
42
//
43
// We assume the following:
44
//   - a lot of floating point numbers in json files will have defined precision
45
//     (in terms of number of digits after decimal point), etc.
46
//   - these (referenced above) can be written in exact format.
47
//
48
// strconv.ParseFloat has some unnecessary overhead which we can do without
49
// for the common case:
50
//
51
//    - expensive char-by-char check to see if underscores are in right place
52
//    - testing for and skipping underscores
53
//    - check if the string matches ignorecase +/- inf, +/- infinity, nan
54
//    - support for base 16 (0xFFFF...)
55
//
56
// The functions below will try a fast-path for floats which can be decoded
57
// without any loss of precision, meaning they:
58
//
59
//    - fits within the significand bits of the 32-bits or 64-bits
60
//    - exponent fits within the exponent value
61
//    - there is no truncation (any extra numbers are all trailing zeros)
62
//
63
// To figure out what the values are for maxMantDigits, use this idea below:
64
//
65
// 2^23 =                 838 8608 (between 10^ 6 and 10^ 7) (significand bits of uint32)
66
// 2^32 =             42 9496 7296 (between 10^ 9 and 10^10) (full uint32)
67
// 2^52 =      4503 5996 2737 0496 (between 10^15 and 10^16) (significand bits of uint64)
68
// 2^64 = 1844 6744 0737 0955 1616 (between 10^19 and 10^20) (full uint64)
69
//
70
// Note: we only allow for up to what can comfortably fit into the significand
71
// ignoring the exponent, and we only try to parse iff significand fits.
72

73
const (
74
	fMaxMultiplierForExactPow10_64 = 1e15
75
	fMaxMultiplierForExactPow10_32 = 1e7
76

77
	fUint64Cutoff = (1<<64-1)/10 + 1
78
	// fUint32Cutoff = (1<<32-1)/10 + 1
79

80
	fBase = 10
81
)
82

83
const (
84
	thousand    = 1000
85
	million     = thousand * thousand
86
	billion     = thousand * million
87
	trillion    = thousand * billion
88
	quadrillion = thousand * trillion
89
	quintillion = thousand * quadrillion
90
)
91

92
// Exact powers of 10.
93
var uint64pow10 = [...]uint64{
94
	1, 10, 100,
95
	1 * thousand, 10 * thousand, 100 * thousand,
96
	1 * million, 10 * million, 100 * million,
97
	1 * billion, 10 * billion, 100 * billion,
98
	1 * trillion, 10 * trillion, 100 * trillion,
99
	1 * quadrillion, 10 * quadrillion, 100 * quadrillion,
100
	1 * quintillion, 10 * quintillion,
101
}
102
var float64pow10 = [...]float64{
103
	1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
104
	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
105
	1e20, 1e21, 1e22,
106
}
107
var float32pow10 = [...]float32{
108
	1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10,
109
}
110

111
type floatinfo struct {
112
	mantbits uint8
113

114
	// expbits uint8 // (unused)
115
	// bias    int16 // (unused)
116
	// is32bit bool // (unused)
117

118
	exactPow10 int8 // Exact powers of ten are <= 10^N (32: 10, 64: 22)
119

120
	exactInts int8 // Exact integers are <= 10^N (for non-float, set to 0)
121

122
	// maxMantDigits int8 // 10^19 fits in uint64, while 10^9 fits in uint32
123

124
	mantCutoffIsUint64Cutoff bool
125

126
	mantCutoff uint64
127
}
128

129
var fi32 = floatinfo{23, 10, 7, false, 1<<23 - 1}
130
var fi64 = floatinfo{52, 22, 15, false, 1<<52 - 1}
131

132
var fi64u = floatinfo{0, 19, 0, true, fUint64Cutoff}
133

134
func noFrac64(fbits uint64) bool {
135
	if fbits == 0 {
136
		return true
137
	}
138

139
	exp := uint64(fbits>>52)&0x7FF - 1023 // uint(x>>shift)&mask - bias
140
	// clear top 12+e bits, the integer part; if the rest is 0, then no fraction.
141
	return exp < 52 && fbits<<(12+exp) == 0 // means there's no fractional part
142
}
143

144
func noFrac32(fbits uint32) bool {
145
	if fbits == 0 {
146
		return true
147
	}
148

149
	exp := uint32(fbits>>23)&0xFF - 127 // uint(x>>shift)&mask - bias
150
	// clear top 9+e bits, the integer part; if the rest is 0, then no fraction.
151
	return exp < 23 && fbits<<(9+exp) == 0 // means there's no fractional part
152
}
153

154
func strconvParseErr(b []byte, fn string) error {
155
	return &strconv.NumError{
156
		Func: fn,
157
		Err:  strconv.ErrSyntax,
158
		Num:  string(b),
159
	}
160
}
161

162
func parseFloat32_reader(r readFloatResult) (f float32, fail bool) {
163
	f = float32(r.mantissa)
164
	if r.exp == 0 {
165
	} else if r.exp < 0 { // int / 10^k
166
		f /= float32pow10[uint8(-r.exp)]
167
	} else { // exp > 0
168
		if r.exp > fi32.exactPow10 {
169
			f *= float32pow10[r.exp-fi32.exactPow10]
170
			if f > fMaxMultiplierForExactPow10_32 { // exponent too large - outside range
171
				fail = true
172
				return // ok = false
173
			}
174
			f *= float32pow10[fi32.exactPow10]
175
		} else {
176
			f *= float32pow10[uint8(r.exp)]
177
		}
178
	}
179
	if r.neg {
180
		f = -f
181
	}
182
	return
183
}
184

185
func parseFloat32_custom(b []byte) (f float32, err error) {
186
	r := readFloat(b, fi32)
187
	if r.bad {
188
		return 0, strconvParseErr(b, "ParseFloat")
189
	}
190
	if r.ok {
191
		f, r.bad = parseFloat32_reader(r)
192
		if !r.bad {
193
			return
194
		}
195
	}
196
	return parseFloat32_strconv(b)
197
}
198

199
func parseFloat64_reader(r readFloatResult) (f float64, fail bool) {
200
	f = float64(r.mantissa)
201
	if r.exp == 0 {
202
	} else if r.exp < 0 { // int / 10^k
203
		f /= float64pow10[-uint8(r.exp)]
204
	} else { // exp > 0
205
		if r.exp > fi64.exactPow10 {
206
			f *= float64pow10[r.exp-fi64.exactPow10]
207
			if f > fMaxMultiplierForExactPow10_64 { // exponent too large - outside range
208
				fail = true
209
				return
210
			}
211
			f *= float64pow10[fi64.exactPow10]
212
		} else {
213
			f *= float64pow10[uint8(r.exp)]
214
		}
215
	}
216
	if r.neg {
217
		f = -f
218
	}
219
	return
220
}
221

222
func parseFloat64_custom(b []byte) (f float64, err error) {
223
	r := readFloat(b, fi64)
224
	if r.bad {
225
		return 0, strconvParseErr(b, "ParseFloat")
226
	}
227
	if r.ok {
228
		f, r.bad = parseFloat64_reader(r)
229
		if !r.bad {
230
			return
231
		}
232
	}
233
	return parseFloat64_strconv(b)
234
}
235

236
func parseUint64_simple(b []byte) (n uint64, ok bool) {
237
	var i int
238
	var n1 uint64
239
	var c uint8
240
LOOP:
241
	if i < len(b) {
242
		c = b[i]
243
		// unsigned integers don't overflow well on multiplication, so check cutoff here
244
		// e.g. (maxUint64-5)*10 doesn't overflow well ...
245
		// if n >= fUint64Cutoff || !isDigitChar(b[i]) { // if c < '0' || c > '9' {
246
		if n >= fUint64Cutoff || c < '0' || c > '9' {
247
			return
248
		} else if c == '0' {
249
			n *= fBase
250
		} else {
251
			n1 = n
252
			n = n*fBase + uint64(c-'0')
253
			if n < n1 {
254
				return
255
			}
256
		}
257
		i++
258
		goto LOOP
259
	}
260
	ok = true
261
	return
262
}
263

264
func parseUint64_reader(r readFloatResult) (f uint64, fail bool) {
265
	f = r.mantissa
266
	if r.exp == 0 {
267
	} else if r.exp < 0 { // int / 10^k
268
		if f%uint64pow10[uint8(-r.exp)] != 0 {
269
			fail = true
270
		} else {
271
			f /= uint64pow10[uint8(-r.exp)]
272
		}
273
	} else { // exp > 0
274
		f *= uint64pow10[uint8(r.exp)]
275
	}
276
	return
277
}
278

279
func parseInteger_bytes(b []byte) (u uint64, neg, ok bool) {
280
	if len(b) == 0 {
281
		ok = true
282
		return
283
	}
284
	if b[0] == '-' {
285
		if len(b) == 1 {
286
			return
287
		}
288
		neg = true
289
		b = b[1:]
290
	}
291

292
	u, ok = parseUint64_simple(b)
293
	if ok {
294
		return
295
	}
296

297
	r := readFloat(b, fi64u)
298
	if r.ok {
299
		var fail bool
300
		u, fail = parseUint64_reader(r)
301
		if fail {
302
			f, err := parseFloat64(b)
303
			if err != nil {
304
				return
305
			}
306
			if !noFrac64(math.Float64bits(f)) {
307
				return
308
			}
309
			u = uint64(f)
310
		}
311
		ok = true
312
		return
313
	}
314
	return
315
}
316

317
// parseNumber will return an integer if only composed of [-]?[0-9]+
318
// Else it will return a float.
319
func parseNumber(b []byte, z *fauxUnion, preferSignedInt bool) (err error) {
320
	var ok, neg bool
321
	var f uint64
322

323
	if len(b) == 0 {
324
		return
325
	}
326

327
	if b[0] == '-' {
328
		neg = true
329
		f, ok = parseUint64_simple(b[1:])
330
	} else {
331
		f, ok = parseUint64_simple(b)
332
	}
333

334
	if ok {
335
		if neg {
336
			z.v = valueTypeInt
337
			if chkOvf.Uint2Int(f, neg) {
338
				return strconvParseErr(b, "ParseInt")
339
			}
340
			z.i = -int64(f)
341
		} else if preferSignedInt {
342
			z.v = valueTypeInt
343
			if chkOvf.Uint2Int(f, neg) {
344
				return strconvParseErr(b, "ParseInt")
345
			}
346
			z.i = int64(f)
347
		} else {
348
			z.v = valueTypeUint
349
			z.u = f
350
		}
351
		return
352
	}
353

354
	z.v = valueTypeFloat
355
	z.f, err = parseFloat64_custom(b)
356
	return
357
}
358

359
type readFloatResult struct {
360
	mantissa uint64
361
	exp      int8
362
	neg      bool
363
	trunc    bool
364
	bad      bool // bad decimal string
365
	hardexp  bool // exponent is hard to handle (> 2 digits, etc)
366
	ok       bool
367
	// sawdot   bool
368
	// sawexp   bool
369
	//_ [2]bool // padding
370
}
371

372
func readFloat(s []byte, y floatinfo) (r readFloatResult) {
373
	var i uint // uint, so that we eliminate bounds checking
374
	var slen = uint(len(s))
375
	if slen == 0 {
376
		// read an empty string as the zero value
377
		// r.bad = true
378
		r.ok = true
379
		return
380
	}
381

382
	if s[0] == '-' {
383
		r.neg = true
384
		i++
385
	}
386

387
	// we considered punting early if string has length > maxMantDigits, but this doesn't account
388
	// for trailing 0's e.g. 700000000000000000000 can be encoded exactly as it is 7e20
389

390
	var nd, ndMant, dp int8
391
	var sawdot, sawexp bool
392
	var xu uint64
393

394
LOOP:
395
	for ; i < slen; i++ {
396
		switch s[i] {
397
		case '.':
398
			if sawdot {
399
				r.bad = true
400
				return
401
			}
402
			sawdot = true
403
			dp = nd
404
		case 'e', 'E':
405
			sawexp = true
406
			break LOOP
407
		case '0':
408
			if nd == 0 {
409
				dp--
410
				continue LOOP
411
			}
412
			nd++
413
			if r.mantissa < y.mantCutoff {
414
				r.mantissa *= fBase
415
				ndMant++
416
			}
417
		case '1', '2', '3', '4', '5', '6', '7', '8', '9':
418
			nd++
419
			if y.mantCutoffIsUint64Cutoff && r.mantissa < fUint64Cutoff {
420
				r.mantissa *= fBase
421
				xu = r.mantissa + uint64(s[i]-'0')
422
				if xu < r.mantissa {
423
					r.trunc = true
424
					return
425
				}
426
				r.mantissa = xu
427
			} else if r.mantissa < y.mantCutoff {
428
				// mantissa = (mantissa << 1) + (mantissa << 3) + uint64(c-'0')
429
				r.mantissa = r.mantissa*fBase + uint64(s[i]-'0')
430
			} else {
431
				r.trunc = true
432
				return
433
			}
434
			ndMant++
435
		default:
436
			r.bad = true
437
			return
438
		}
439
	}
440

441
	if !sawdot {
442
		dp = nd
443
	}
444

445
	if sawexp {
446
		i++
447
		if i < slen {
448
			var eneg bool
449
			if s[i] == '+' {
450
				i++
451
			} else if s[i] == '-' {
452
				i++
453
				eneg = true
454
			}
455
			if i < slen {
456
				// for exact match, exponent is 1 or 2 digits (float64: -22 to 37, float32: -1 to 17).
457
				// exit quick if exponent is more than 2 digits.
458
				if i+2 < slen {
459
					r.hardexp = true
460
					return
461
				}
462
				var e int8
463
				if s[i] < '0' || s[i] > '9' { // !isDigitChar(s[i]) { //
464
					r.bad = true
465
					return
466
				}
467
				e = int8(s[i] - '0')
468
				i++
469
				if i < slen {
470
					if s[i] < '0' || s[i] > '9' { // !isDigitChar(s[i]) { //
471
						r.bad = true
472
						return
473
					}
474
					e = e*fBase + int8(s[i]-'0') // (e << 1) + (e << 3) + int8(s[i]-'0')
475
					i++
476
				}
477
				if eneg {
478
					dp -= e
479
				} else {
480
					dp += e
481
				}
482
			}
483
		}
484
	}
485

486
	if r.mantissa != 0 {
487
		r.exp = dp - ndMant
488
		// do not set ok=true for cases we cannot handle
489
		if r.exp < -y.exactPow10 ||
490
			r.exp > y.exactInts+y.exactPow10 ||
491
			(y.mantbits != 0 && r.mantissa>>y.mantbits != 0) {
492
			r.hardexp = true
493
			return
494
		}
495
	}
496

497
	r.ok = true
498
	return
499
}
500