Source file
src/math/big/natconv_test.go
1
2
3
4
5 package big
6
7 import (
8 "bytes"
9 "fmt"
10 "io"
11 "math/bits"
12 "strings"
13 "testing"
14 )
15
16 func TestMaxBase(t *testing.T) {
17 if MaxBase != len(digits) {
18 t.Fatalf("%d != %d", MaxBase, len(digits))
19 }
20 }
21
22
23
24
25 func log2(x Word) int {
26 return bits.Len(uint(x)) - 1
27 }
28
29 func itoa(x nat, base int) []byte {
30
31 switch {
32 case base < 2:
33 panic("illegal base")
34 case len(x) == 0:
35 return []byte("0")
36 }
37
38
39 i := x.bitLen()/log2(Word(base)) + 1
40 s := make([]byte, i)
41
42
43 q := nat(nil).set(x)
44
45
46 for len(q) > 0 {
47 i--
48 var r Word
49 q, r = q.divW(q, Word(base))
50 s[i] = digits[r]
51 }
52
53 return s[i:]
54 }
55
56 var strTests = []struct {
57 x nat
58 b int
59 s string
60 }{
61 {nil, 2, "0"},
62 {nat{1}, 2, "1"},
63 {nat{0xc5}, 2, "11000101"},
64 {nat{03271}, 8, "3271"},
65 {nat{10}, 10, "10"},
66 {nat{1234567890}, 10, "1234567890"},
67 {nat{0xdeadbeef}, 16, "deadbeef"},
68 {nat{0x229be7}, 17, "1a2b3c"},
69 {nat{0x309663e6}, 32, "o9cov6"},
70 {nat{0x309663e6}, 62, "TakXI"},
71 }
72
73 func TestString(t *testing.T) {
74
75 var panicStr string
76 func() {
77 defer func() {
78 panicStr = recover().(string)
79 }()
80 natOne.utoa(1)
81 }()
82 if panicStr != "invalid base" {
83 t.Errorf("expected panic for invalid base")
84 }
85
86 for _, a := range strTests {
87 s := string(a.x.utoa(a.b))
88 if s != a.s {
89 t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s)
90 }
91
92 x, b, _, err := nat(nil).scan(strings.NewReader(a.s), a.b, false)
93 if x.cmp(a.x) != 0 {
94 t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
95 }
96 if b != a.b {
97 t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.b)
98 }
99 if err != nil {
100 t.Errorf("scan%+v\n\tgot error = %s", a, err)
101 }
102 }
103 }
104
105 var natScanTests = []struct {
106 s string
107 base int
108 frac bool
109 x nat
110 b int
111 count int
112 err error
113 next rune
114 }{
115
116 {"", 0, false, nil, 10, 0, errNoDigits, 0},
117 {"_", 0, false, nil, 10, 0, errNoDigits, 0},
118 {"?", 0, false, nil, 10, 0, errNoDigits, '?'},
119 {"?", 10, false, nil, 10, 0, errNoDigits, '?'},
120 {"", 10, false, nil, 10, 0, errNoDigits, 0},
121 {"", 36, false, nil, 36, 0, errNoDigits, 0},
122 {"", 62, false, nil, 62, 0, errNoDigits, 0},
123 {"0b", 0, false, nil, 2, 0, errNoDigits, 0},
124 {"0o", 0, false, nil, 8, 0, errNoDigits, 0},
125 {"0x", 0, false, nil, 16, 0, errNoDigits, 0},
126 {"0x_", 0, false, nil, 16, 0, errNoDigits, 0},
127 {"0b2", 0, false, nil, 2, 0, errNoDigits, '2'},
128 {"0B2", 0, false, nil, 2, 0, errNoDigits, '2'},
129 {"0o8", 0, false, nil, 8, 0, errNoDigits, '8'},
130 {"0O8", 0, false, nil, 8, 0, errNoDigits, '8'},
131 {"0xg", 0, false, nil, 16, 0, errNoDigits, 'g'},
132 {"0Xg", 0, false, nil, 16, 0, errNoDigits, 'g'},
133 {"345", 2, false, nil, 2, 0, errNoDigits, '3'},
134
135
136 {"._", 0, true, nil, 10, 0, errNoDigits, 0},
137 {".0", 0, false, nil, 10, 0, errNoDigits, '.'},
138 {".0", 10, false, nil, 10, 0, errNoDigits, '.'},
139 {".", 0, true, nil, 10, 0, errNoDigits, 0},
140 {"0x.", 0, true, nil, 16, 0, errNoDigits, 0},
141 {"0x.g", 0, true, nil, 16, 0, errNoDigits, 'g'},
142 {"0x.0", 0, false, nil, 16, 0, errNoDigits, '.'},
143
144
145 {"_0", 0, false, nil, 10, 1, errInvalSep, 0},
146 {"0_", 0, false, nil, 10, 1, errInvalSep, 0},
147 {"0__0", 0, false, nil, 8, 1, errInvalSep, 0},
148 {"0x___0", 0, false, nil, 16, 1, errInvalSep, 0},
149 {"0_x", 0, false, nil, 10, 1, errInvalSep, 'x'},
150 {"0_8", 0, false, nil, 10, 1, errInvalSep, '8'},
151 {"123_.", 0, true, nat{123}, 10, 0, errInvalSep, 0},
152 {"._123", 0, true, nat{123}, 10, -3, errInvalSep, 0},
153 {"0b__1000", 0, false, nat{0x8}, 2, 4, errInvalSep, 0},
154 {"0o60___0", 0, false, nat{0600}, 8, 3, errInvalSep, 0},
155 {"0466_", 0, false, nat{0466}, 8, 3, errInvalSep, 0},
156 {"01234567_8", 0, false, nat{01234567}, 8, 7, errInvalSep, '8'},
157 {"1_.", 0, true, nat{1}, 10, 0, errInvalSep, 0},
158 {"0._1", 0, true, nat{1}, 10, -1, errInvalSep, 0},
159 {"2.7_", 0, true, nat{27}, 10, -1, errInvalSep, 0},
160 {"0x1.0_", 0, true, nat{0x10}, 16, -1, errInvalSep, 0},
161
162
163 {"0_", 10, false, nil, 10, 1, nil, '_'},
164 {"1__0", 10, false, nat{1}, 10, 1, nil, '_'},
165 {"0__8", 10, false, nil, 10, 1, nil, '_'},
166 {"xy_z_", 36, false, nat{33*36 + 34}, 36, 2, nil, '_'},
167
168
169 {"0", 0, false, nil, 10, 1, nil, 0},
170 {"0", 36, false, nil, 36, 1, nil, 0},
171 {"0", 62, false, nil, 62, 1, nil, 0},
172 {"1", 0, false, nat{1}, 10, 1, nil, 0},
173 {"1", 10, false, nat{1}, 10, 1, nil, 0},
174 {"0 ", 0, false, nil, 10, 1, nil, ' '},
175 {"00 ", 0, false, nil, 8, 1, nil, ' '},
176 {"0b1", 0, false, nat{1}, 2, 1, nil, 0},
177 {"0B11000101", 0, false, nat{0xc5}, 2, 8, nil, 0},
178 {"0B110001012", 0, false, nat{0xc5}, 2, 8, nil, '2'},
179 {"07", 0, false, nat{7}, 8, 1, nil, 0},
180 {"08", 0, false, nil, 10, 1, nil, '8'},
181 {"08", 10, false, nat{8}, 10, 2, nil, 0},
182 {"018", 0, false, nat{1}, 8, 1, nil, '8'},
183 {"0o7", 0, false, nat{7}, 8, 1, nil, 0},
184 {"0o18", 0, false, nat{1}, 8, 1, nil, '8'},
185 {"0O17", 0, false, nat{017}, 8, 2, nil, 0},
186 {"03271", 0, false, nat{03271}, 8, 4, nil, 0},
187 {"10ab", 0, false, nat{10}, 10, 2, nil, 'a'},
188 {"1234567890", 0, false, nat{1234567890}, 10, 10, nil, 0},
189 {"A", 36, false, nat{10}, 36, 1, nil, 0},
190 {"A", 37, false, nat{36}, 37, 1, nil, 0},
191 {"xyz", 36, false, nat{(33*36+34)*36 + 35}, 36, 3, nil, 0},
192 {"XYZ?", 36, false, nat{(33*36+34)*36 + 35}, 36, 3, nil, '?'},
193 {"XYZ?", 62, false, nat{(59*62+60)*62 + 61}, 62, 3, nil, '?'},
194 {"0x", 16, false, nil, 16, 1, nil, 'x'},
195 {"0xdeadbeef", 0, false, nat{0xdeadbeef}, 16, 8, nil, 0},
196 {"0XDEADBEEF", 0, false, nat{0xdeadbeef}, 16, 8, nil, 0},
197
198
199 {"0.", 0, false, nil, 10, 1, nil, '.'},
200 {"0.", 10, true, nil, 10, 0, nil, 0},
201 {"0.1.2", 10, true, nat{1}, 10, -1, nil, '.'},
202 {".000", 10, true, nil, 10, -3, nil, 0},
203 {"12.3", 10, true, nat{123}, 10, -1, nil, 0},
204 {"012.345", 10, true, nat{12345}, 10, -3, nil, 0},
205 {"0.1", 0, true, nat{1}, 10, -1, nil, 0},
206 {"0.1", 2, true, nat{1}, 2, -1, nil, 0},
207 {"0.12", 2, true, nat{1}, 2, -1, nil, '2'},
208 {"0b0.1", 0, true, nat{1}, 2, -1, nil, 0},
209 {"0B0.12", 0, true, nat{1}, 2, -1, nil, '2'},
210 {"0o0.7", 0, true, nat{7}, 8, -1, nil, 0},
211 {"0O0.78", 0, true, nat{7}, 8, -1, nil, '8'},
212 {"0xdead.beef", 0, true, nat{0xdeadbeef}, 16, -4, nil, 0},
213
214
215 {"1_000", 0, false, nat{1000}, 10, 4, nil, 0},
216 {"0_466", 0, false, nat{0466}, 8, 3, nil, 0},
217 {"0o_600", 0, false, nat{0600}, 8, 3, nil, 0},
218 {"0x_f0_0d", 0, false, nat{0xf00d}, 16, 4, nil, 0},
219 {"0b1000_0001", 0, false, nat{0x81}, 2, 8, nil, 0},
220 {"1_000.000_1", 0, true, nat{10000001}, 10, -4, nil, 0},
221 {"0x_f00d.1e", 0, true, nat{0xf00d1e}, 16, -2, nil, 0},
222 {"0x_f00d.1E2", 0, true, nat{0xf00d1e2}, 16, -3, nil, 0},
223 {"0x_f00d.1eg", 0, true, nat{0xf00d1e}, 16, -2, nil, 'g'},
224 }
225
226 func TestScanBase(t *testing.T) {
227 for _, a := range natScanTests {
228 r := strings.NewReader(a.s)
229 x, b, count, err := nat(nil).scan(r, a.base, a.frac)
230 if err != a.err {
231 t.Errorf("scan%+v\n\tgot error = %v; want %v", a, err, a.err)
232 }
233 if x.cmp(a.x) != 0 {
234 t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
235 }
236 if b != a.b {
237 t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.base)
238 }
239 if count != a.count {
240 t.Errorf("scan%+v\n\tgot count = %d; want %d", a, count, a.count)
241 }
242 next, _, err := r.ReadRune()
243 if err == io.EOF {
244 next = 0
245 err = nil
246 }
247 if err == nil && next != a.next {
248 t.Errorf("scan%+v\n\tgot next = %q; want %q", a, next, a.next)
249 }
250 }
251 }
252
253 var pi = "3" +
254 "14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651" +
255 "32823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461" +
256 "28475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920" +
257 "96282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179" +
258 "31051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798" +
259 "60943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901" +
260 "22495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837" +
261 "29780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083" +
262 "81420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909" +
263 "21642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151" +
264 "55748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035" +
265 "63707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104" +
266 "75216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992" +
267 "45863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818" +
268 "34797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548" +
269 "16136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179" +
270 "04946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886" +
271 "26945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645" +
272 "99581339047802759009946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745" +
273 "53050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382" +
274 "68683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244" +
275 "13654976278079771569143599770012961608944169486855584840635342207222582848864815845602850601684273945226746767" +
276 "88952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288" +
277 "79710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821" +
278 "68299894872265880485756401427047755513237964145152374623436454285844479526586782105114135473573952311342716610" +
279 "21359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435" +
280 "06430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675" +
281 "14269123974894090718649423196156794520809514655022523160388193014209376213785595663893778708303906979207734672" +
282 "21825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539" +
283 "05796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007" +
284 "23055876317635942187312514712053292819182618612586732157919841484882916447060957527069572209175671167229109816" +
285 "90915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398" +
286 "31501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064" +
287 "20467525907091548141654985946163718027098199430992448895757128289059232332609729971208443357326548938239119325" +
288 "97463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100" +
289 "44929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915" +
290 "44110104468232527162010526522721116603966655730925471105578537634668206531098965269186205647693125705863566201" +
291 "85581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318" +
292 "58676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797" +
293 "27082668306343285878569830523580893306575740679545716377525420211495576158140025012622859413021647155097925923" +
294 "09907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111" +
295 "79042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043" +
296 "06332175182979866223717215916077166925474873898665494945011465406284336639379003976926567214638530673609657120" +
297 "91807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862" +
298 "94726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939" +
299 "78054193414473774418426312986080998886874132604721569516239658645730216315981931951673538129741677294786724229" +
300 "24654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001" +
301 "59377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541" +
302 "34189948544473456738316249934191318148092777710386387734317720754565453220777092120190516609628049092636019759" +
303 "88281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267" +
304 "94561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337"
305
306
307 func TestScanPi(t *testing.T) {
308 var x nat
309 z, _, _, err := x.scan(strings.NewReader(pi), 10, false)
310 if err != nil {
311 t.Errorf("scanning pi: %s", err)
312 }
313 if s := string(z.utoa(10)); s != pi {
314 t.Errorf("scanning pi: got %s", s)
315 }
316 }
317
318 func TestScanPiParallel(t *testing.T) {
319 const n = 2
320 c := make(chan int)
321 for i := 0; i < n; i++ {
322 go func() {
323 TestScanPi(t)
324 c <- 0
325 }()
326 }
327 for i := 0; i < n; i++ {
328 <-c
329 }
330 }
331
332 func BenchmarkScanPi(b *testing.B) {
333 for i := 0; i < b.N; i++ {
334 var x nat
335 x.scan(strings.NewReader(pi), 10, false)
336 }
337 }
338
339 func BenchmarkStringPiParallel(b *testing.B) {
340 var x nat
341 x, _, _, _ = x.scan(strings.NewReader(pi), 0, false)
342 if string(x.utoa(10)) != pi {
343 panic("benchmark incorrect: conversion failed")
344 }
345 b.RunParallel(func(pb *testing.PB) {
346 for pb.Next() {
347 x.utoa(10)
348 }
349 })
350 }
351
352 func BenchmarkScan(b *testing.B) {
353 const x = 10
354 for _, base := range []int{2, 8, 10, 16} {
355 for _, y := range []Word{10, 100, 1000, 10000, 100000} {
356 if isRaceBuilder && y > 1000 {
357 continue
358 }
359 b.Run(fmt.Sprintf("%d/Base%d", y, base), func(b *testing.B) {
360 b.StopTimer()
361 var z nat
362 z = z.expWW(x, y)
363
364 s := z.utoa(base)
365 if t := itoa(z, base); !bytes.Equal(s, t) {
366 b.Fatalf("scanning: got %s; want %s", s, t)
367 }
368 b.StartTimer()
369
370 for i := 0; i < b.N; i++ {
371 z.scan(bytes.NewReader(s), base, false)
372 }
373 })
374 }
375 }
376 }
377
378 func BenchmarkString(b *testing.B) {
379 const x = 10
380 for _, base := range []int{2, 8, 10, 16} {
381 for _, y := range []Word{10, 100, 1000, 10000, 100000} {
382 if isRaceBuilder && y > 1000 {
383 continue
384 }
385 b.Run(fmt.Sprintf("%d/Base%d", y, base), func(b *testing.B) {
386 b.StopTimer()
387 var z nat
388 z = z.expWW(x, y)
389 z.utoa(base)
390 b.StartTimer()
391
392 for i := 0; i < b.N; i++ {
393 _ = z.utoa(base)
394 }
395 })
396 }
397 }
398 }
399
400 func BenchmarkLeafSize(b *testing.B) {
401 for n := 0; n <= 16; n++ {
402 b.Run(fmt.Sprint(n), func(b *testing.B) { LeafSizeHelper(b, 10, n) })
403 }
404
405 for _, n := range []int{32, 64} {
406 b.Run(fmt.Sprint(n), func(b *testing.B) { LeafSizeHelper(b, 10, n) })
407 }
408 }
409
410 func LeafSizeHelper(b *testing.B, base, size int) {
411 b.StopTimer()
412 originalLeafSize := leafSize
413 resetTable(cacheBase10.table[:])
414 leafSize = size
415 b.StartTimer()
416
417 for d := 1; d <= 10000; d *= 10 {
418 b.StopTimer()
419 var z nat
420 z = z.expWW(Word(base), Word(d))
421 _ = z.utoa(base)
422 b.StartTimer()
423
424 for i := 0; i < b.N; i++ {
425 _ = z.utoa(base)
426 }
427 }
428
429 b.StopTimer()
430 resetTable(cacheBase10.table[:])
431 leafSize = originalLeafSize
432 b.StartTimer()
433 }
434
435 func resetTable(table []divisor) {
436 if table != nil && table[0].bbb != nil {
437 for i := 0; i < len(table); i++ {
438 table[i].bbb = nil
439 table[i].nbits = 0
440 table[i].ndigits = 0
441 }
442 }
443 }
444
445 func TestStringPowers(t *testing.T) {
446 var p Word
447 for b := 2; b <= 16; b++ {
448 for p = 0; p <= 512; p++ {
449 if testing.Short() && p > 10 {
450 break
451 }
452 x := nat(nil).expWW(Word(b), p)
453 xs := x.utoa(b)
454 xs2 := itoa(x, b)
455 if !bytes.Equal(xs, xs2) {
456 t.Errorf("failed at %d ** %d in base %d: %s != %s", b, p, b, xs, xs2)
457 }
458 }
459 if b >= 3 && testing.Short() {
460 break
461 }
462 }
463 }
464
View as plain text