OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [math/] [big/] [int_test.go] - Blame information for rev 801

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 747 jeremybenn 
// Copyright 2009 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 
package big
6 
 
7 
import (
8 
        "bytes"
9 
        "encoding/gob"
10 
        "encoding/hex"
11 
        "fmt"
12 
        "math/rand"
13 
        "testing"
14 
        "testing/quick"
15 
)
16 
 
17 
func isNormalized(x *Int) bool {
18 
        if len(x.abs) == 0 {
19 
                return !x.neg
20 
        }
21 
        // len(x.abs) > 0
22 
        return x.abs[len(x.abs)-1] != 0
23 
}
24 
 
25 
type funZZ func(z, x, y *Int) *Int
26 
type argZZ struct {
27 
        z, x, y *Int
28 
}
29 
 
30 
var sumZZ = []argZZ{
31 
        {NewInt(0), NewInt(0), NewInt(0)},
32 
        {NewInt(1), NewInt(1), NewInt(0)},
33 
        {NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
34 
        {NewInt(-1), NewInt(-1), NewInt(0)},
35 
        {NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
36 
        {NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
37 
}
38 
 
39 
var prodZZ = []argZZ{
40 
        {NewInt(0), NewInt(0), NewInt(0)},
41 
        {NewInt(0), NewInt(1), NewInt(0)},
42 
        {NewInt(1), NewInt(1), NewInt(1)},
43 
        {NewInt(-991 * 991), NewInt(991), NewInt(-991)},
44 
        // TODO(gri) add larger products
45 
}
46 
 
47 
func TestSignZ(t *testing.T) {
48 
        var zero Int
49 
        for _, a := range sumZZ {
50 
                s := a.z.Sign()
51 
                e := a.z.Cmp(&zero)
52 
                if s != e {
53 
                        t.Errorf("got %d; want %d for z = %v", s, e, a.z)
54 
                }
55 
        }
56 
}
57 
 
58 
func TestSetZ(t *testing.T) {
59 
        for _, a := range sumZZ {
60 
                var z Int
61 
                z.Set(a.z)
62 
                if !isNormalized(&z) {
63 
                        t.Errorf("%v is not normalized", z)
64 
                }
65 
                if (&z).Cmp(a.z) != 0 {
66 
                        t.Errorf("got z = %v; want %v", z, a.z)
67 
                }
68 
        }
69 
}
70 
 
71 
func TestAbsZ(t *testing.T) {
72 
        var zero Int
73 
        for _, a := range sumZZ {
74 
                var z Int
75 
                z.Abs(a.z)
76 
                var e Int
77 
                e.Set(a.z)
78 
                if e.Cmp(&zero) < 0 {
79 
                        e.Sub(&zero, &e)
80 
                }
81 
                if z.Cmp(&e) != 0 {
82 
                        t.Errorf("got z = %v; want %v", z, e)
83 
                }
84 
        }
85 
}
86 
 
87 
func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
88 
        var z Int
89 
        f(&z, a.x, a.y)
90 
        if !isNormalized(&z) {
91 
                t.Errorf("%s%v is not normalized", z, msg)
92 
        }
93 
        if (&z).Cmp(a.z) != 0 {
94 
                t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
95 
        }
96 
}
97 
 
98 
func TestSumZZ(t *testing.T) {
99 
        AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
100 
        SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
101 
        for _, a := range sumZZ {
102 
                arg := a
103 
                testFunZZ(t, "AddZZ", AddZZ, arg)
104 
 
105 
                arg = argZZ{a.z, a.y, a.x}
106 
                testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
107 
 
108 
                arg = argZZ{a.x, a.z, a.y}
109 
                testFunZZ(t, "SubZZ", SubZZ, arg)
110 
 
111 
                arg = argZZ{a.y, a.z, a.x}
112 
                testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
113 
        }
114 
}
115 
 
116 
func TestProdZZ(t *testing.T) {
117 
        MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
118 
        for _, a := range prodZZ {
119 
                arg := a
120 
                testFunZZ(t, "MulZZ", MulZZ, arg)
121 
 
122 
                arg = argZZ{a.z, a.y, a.x}
123 
                testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
124 
        }
125 
}
126 
 
127 
// mulBytes returns x*y via grade school multiplication. Both inputs
128 
// and the result are assumed to be in big-endian representation (to
129 
// match the semantics of Int.Bytes and Int.SetBytes).
130 
func mulBytes(x, y []byte) []byte {
131 
        z := make([]byte, len(x)+len(y))
132 
 
133 
        // multiply
134 
        k0 := len(z) - 1
135 
        for j := len(y) - 1; j >= 0; j-- {
136 
                d := int(y[j])
137 
                if d != 0 {
138 
                        k := k0
139 
                        carry := 0
140 
                        for i := len(x) - 1; i >= 0; i-- {
141 
                                t := int(z[k]) + int(x[i])*d + carry
142 
                                z[k], carry = byte(t), t>>8
143 
                                k--
144 
                        }
145 
                        z[k] = byte(carry)
146 
                }
147 
                k0--
148 
        }
149 
 
150 
        // normalize (remove leading 0's)
151 
        i := 0
152 
        for i < len(z) && z[i] == 0 {
153 
                i++
154 
        }
155 
 
156 
        return z[i:]
157 
}
158 
 
159 
func checkMul(a, b []byte) bool {
160 
        var x, y, z1 Int
161 
        x.SetBytes(a)
162 
        y.SetBytes(b)
163 
        z1.Mul(&x, &y)
164 
 
165 
        var z2 Int
166 
        z2.SetBytes(mulBytes(a, b))
167 
 
168 
        return z1.Cmp(&z2) == 0
169 
}
170 
 
171 
func TestMul(t *testing.T) {
172 
        if err := quick.Check(checkMul, nil); err != nil {
173 
                t.Error(err)
174 
        }
175 
}
176 
 
177 
var mulRangesZ = []struct {
178 
        a, b int64
179 
        prod string
180 
}{
181 
        // entirely positive ranges are covered by mulRangesN
182 
        {-1, 1, "0"},
183 
        {-2, -1, "2"},
184 
        {-3, -2, "6"},
185 
        {-3, -1, "-6"},
186 
        {1, 3, "6"},
187 
        {-10, -10, "-10"},
188 
        {0, -1, "1"},                      // empty range
189 
        {-1, -100, "1"},                   // empty range
190 
        {-1, 1, "0"},                      // range includes 0
191 
        {-1e9, 0, "0"},                    // range includes 0
192 
        {-1e9, 1e9, "0"},                  // range includes 0
193 
        {-10, -1, "3628800"},              // 10!
194 
        {-20, -2, "-2432902008176640000"}, // -20!
195 
        {-99, -1,
196 
                "-933262154439441526816992388562667004907159682643816214685929" +
197 
                        "638952175999932299156089414639761565182862536979208272237582" +
198 
                        "511852109168640000000000000000000000", // -99!
199 
        },
200 
}
201 
 
202 
func TestMulRangeZ(t *testing.T) {
203 
        var tmp Int
204 
        // test entirely positive ranges
205 
        for i, r := range mulRangesN {
206 
                prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
207 
                if prod != r.prod {
208 
                        t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
209 
                }
210 
        }
211 
        // test other ranges
212 
        for i, r := range mulRangesZ {
213 
                prod := tmp.MulRange(r.a, r.b).String()
214 
                if prod != r.prod {
215 
                        t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
216 
                }
217 
        }
218 
}
219 
 
220 
var stringTests = []struct {
221 
        in   string
222 
        out  string
223 
        base int
224 
        val  int64
225 
        ok   bool
226 
}{
227 
        {in: "", ok: false},
228 
        {in: "a", ok: false},
229 
        {in: "z", ok: false},
230 
        {in: "+", ok: false},
231 
        {in: "-", ok: false},
232 
        {in: "0b", ok: false},
233 
        {in: "0x", ok: false},
234 
        {in: "2", base: 2, ok: false},
235 
        {in: "0b2", base: 0, ok: false},
236 
        {in: "08", ok: false},
237 
        {in: "8", base: 8, ok: false},
238 
        {in: "0xg", base: 0, ok: false},
239 
        {in: "g", base: 16, ok: false},
240 
        {"0", "0", 0, 0, true},
241 
        {"0", "0", 10, 0, true},
242 
        {"0", "0", 16, 0, true},
243 
        {"+0", "0", 0, 0, true},
244 
        {"-0", "0", 0, 0, true},
245 
        {"10", "10", 0, 10, true},
246 
        {"10", "10", 10, 10, true},
247 
        {"10", "10", 16, 16, true},
248 
        {"-10", "-10", 16, -16, true},
249 
        {"+10", "10", 16, 16, true},
250 
        {"0x10", "16", 0, 16, true},
251 
        {in: "0x10", base: 16, ok: false},
252 
        {"-0x10", "-16", 0, -16, true},
253 
        {"+0x10", "16", 0, 16, true},
254 
        {"00", "0", 0, 0, true},
255 
        {"0", "0", 8, 0, true},
256 
        {"07", "7", 0, 7, true},
257 
        {"7", "7", 8, 7, true},
258 
        {"023", "19", 0, 19, true},
259 
        {"23", "23", 8, 19, true},
260 
        {"cafebabe", "cafebabe", 16, 0xcafebabe, true},
261 
        {"0b0", "0", 0, 0, true},
262 
        {"-111", "-111", 2, -7, true},
263 
        {"-0b111", "-7", 0, -7, true},
264 
        {"0b1001010111", "599", 0, 0x257, true},
265 
        {"1001010111", "1001010111", 2, 0x257, true},
266 
}
267 
 
268 
func format(base int) string {
269 
        switch base {
270 
        case 2:
271 
                return "%b"
272 
        case 8:
273 
                return "%o"
274 
        case 16:
275 
                return "%x"
276 
        }
277 
        return "%d"
278 
}
279 
 
280 
func TestGetString(t *testing.T) {
281 
        z := new(Int)
282 
        for i, test := range stringTests {
283 
                if !test.ok {
284 
                        continue
285 
                }
286 
                z.SetInt64(test.val)
287 
 
288 
                if test.base == 10 {
289 
                        s := z.String()
290 
                        if s != test.out {
291 
                                t.Errorf("#%da got %s; want %s", i, s, test.out)
292 
                        }
293 
                }
294 
 
295 
                s := fmt.Sprintf(format(test.base), z)
296 
                if s != test.out {
297 
                        t.Errorf("#%db got %s; want %s", i, s, test.out)
298 
                }
299 
        }
300 
}
301 
 
302 
func TestSetString(t *testing.T) {
303 
        tmp := new(Int)
304 
        for i, test := range stringTests {
305 
                // initialize to a non-zero value so that issues with parsing
306 
                // 0 are detected
307 
                tmp.SetInt64(1234567890)
308 
                n1, ok1 := new(Int).SetString(test.in, test.base)
309 
                n2, ok2 := tmp.SetString(test.in, test.base)
310 
                expected := NewInt(test.val)
311 
                if ok1 != test.ok || ok2 != test.ok {
312 
                        t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
313 
                        continue
314 
                }
315 
                if !ok1 {
316 
                        if n1 != nil {
317 
                                t.Errorf("#%d (input '%s') n1 != nil", i, test.in)
318 
                        }
319 
                        continue
320 
                }
321 
                if !ok2 {
322 
                        if n2 != nil {
323 
                                t.Errorf("#%d (input '%s') n2 != nil", i, test.in)
324 
                        }
325 
                        continue
326 
                }
327 
 
328 
                if ok1 && !isNormalized(n1) {
329 
                        t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1)
330 
                }
331 
                if ok2 && !isNormalized(n2) {
332 
                        t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2)
333 
                }
334 
 
335 
                if n1.Cmp(expected) != 0 {
336 
                        t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
337 
                }
338 
                if n2.Cmp(expected) != 0 {
339 
                        t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
340 
                }
341 
        }
342 
}
343 
 
344 
var formatTests = []struct {
345 
        input  string
346 
        format string
347 
        output string
348 
}{
349 
        {"", "%x", ""},
350 
        {"", "%#x", ""},
351 
        {"", "%#y", "%!y(big.Int=)"},
352 
 
353 
        {"10", "%b", "1010"},
354 
        {"10", "%o", "12"},
355 
        {"10", "%d", "10"},
356 
        {"10", "%v", "10"},
357 
        {"10", "%x", "a"},
358 
        {"10", "%X", "A"},
359 
        {"-10", "%X", "-A"},
360 
        {"10", "%y", "%!y(big.Int=10)"},
361 
        {"-10", "%y", "%!y(big.Int=-10)"},
362 
 
363 
        {"10", "%#b", "1010"},
364 
        {"10", "%#o", "012"},
365 
        {"10", "%#d", "10"},
366 
        {"10", "%#v", "10"},
367 
        {"10", "%#x", "0xa"},
368 
        {"10", "%#X", "0XA"},
369 
        {"-10", "%#X", "-0XA"},
370 
        {"10", "%#y", "%!y(big.Int=10)"},
371 
        {"-10", "%#y", "%!y(big.Int=-10)"},
372 
 
373 
        {"1234", "%d", "1234"},
374 
        {"1234", "%3d", "1234"},
375 
        {"1234", "%4d", "1234"},
376 
        {"-1234", "%d", "-1234"},
377 
        {"1234", "% 5d", " 1234"},
378 
        {"1234", "%+5d", "+1234"},
379 
        {"1234", "%-5d", "1234 "},
380 
        {"1234", "%x", "4d2"},
381 
        {"1234", "%X", "4D2"},
382 
        {"-1234", "%3x", "-4d2"},
383 
        {"-1234", "%4x", "-4d2"},
384 
        {"-1234", "%5x", " -4d2"},
385 
        {"-1234", "%-5x", "-4d2 "},
386 
        {"1234", "%03d", "1234"},
387 
        {"1234", "%04d", "1234"},
388 
        {"1234", "%05d", "01234"},
389 
        {"1234", "%06d", "001234"},
390 
        {"-1234", "%06d", "-01234"},
391 
        {"1234", "%+06d", "+01234"},
392 
        {"1234", "% 06d", " 01234"},
393 
        {"1234", "%-6d", "1234  "},
394 
        {"1234", "%-06d", "1234  "},
395 
        {"-1234", "%-06d", "-1234 "},
396 
 
397 
        {"1234", "%.3d", "1234"},
398 
        {"1234", "%.4d", "1234"},
399 
        {"1234", "%.5d", "01234"},
400 
        {"1234", "%.6d", "001234"},
401 
        {"-1234", "%.3d", "-1234"},
402 
        {"-1234", "%.4d", "-1234"},
403 
        {"-1234", "%.5d", "-01234"},
404 
        {"-1234", "%.6d", "-001234"},
405 
 
406 
        {"1234", "%8.3d", "    1234"},
407 
        {"1234", "%8.4d", "    1234"},
408 
        {"1234", "%8.5d", "   01234"},
409 
        {"1234", "%8.6d", "  001234"},
410 
        {"-1234", "%8.3d", "   -1234"},
411 
        {"-1234", "%8.4d", "   -1234"},
412 
        {"-1234", "%8.5d", "  -01234"},
413 
        {"-1234", "%8.6d", " -001234"},
414 
 
415 
        {"1234", "%+8.3d", "   +1234"},
416 
        {"1234", "%+8.4d", "   +1234"},
417 
        {"1234", "%+8.5d", "  +01234"},
418 
        {"1234", "%+8.6d", " +001234"},
419 
        {"-1234", "%+8.3d", "   -1234"},
420 
        {"-1234", "%+8.4d", "   -1234"},
421 
        {"-1234", "%+8.5d", "  -01234"},
422 
        {"-1234", "%+8.6d", " -001234"},
423 
 
424 
        {"1234", "% 8.3d", "    1234"},
425 
        {"1234", "% 8.4d", "    1234"},
426 
        {"1234", "% 8.5d", "   01234"},
427 
        {"1234", "% 8.6d", "  001234"},
428 
        {"-1234", "% 8.3d", "   -1234"},
429 
        {"-1234", "% 8.4d", "   -1234"},
430 
        {"-1234", "% 8.5d", "  -01234"},
431 
        {"-1234", "% 8.6d", " -001234"},
432 
 
433 
        {"1234", "%.3x", "4d2"},
434 
        {"1234", "%.4x", "04d2"},
435 
        {"1234", "%.5x", "004d2"},
436 
        {"1234", "%.6x", "0004d2"},
437 
        {"-1234", "%.3x", "-4d2"},
438 
        {"-1234", "%.4x", "-04d2"},
439 
        {"-1234", "%.5x", "-004d2"},
440 
        {"-1234", "%.6x", "-0004d2"},
441 
 
442 
        {"1234", "%8.3x", "     4d2"},
443 
        {"1234", "%8.4x", "    04d2"},
444 
        {"1234", "%8.5x", "   004d2"},
445 
        {"1234", "%8.6x", "  0004d2"},
446 
        {"-1234", "%8.3x", "    -4d2"},
447 
        {"-1234", "%8.4x", "   -04d2"},
448 
        {"-1234", "%8.5x", "  -004d2"},
449 
        {"-1234", "%8.6x", " -0004d2"},
450 
 
451 
        {"1234", "%+8.3x", "    +4d2"},
452 
        {"1234", "%+8.4x", "   +04d2"},
453 
        {"1234", "%+8.5x", "  +004d2"},
454 
        {"1234", "%+8.6x", " +0004d2"},
455 
        {"-1234", "%+8.3x", "    -4d2"},
456 
        {"-1234", "%+8.4x", "   -04d2"},
457 
        {"-1234", "%+8.5x", "  -004d2"},
458 
        {"-1234", "%+8.6x", " -0004d2"},
459 
 
460 
        {"1234", "% 8.3x", "     4d2"},
461 
        {"1234", "% 8.4x", "    04d2"},
462 
        {"1234", "% 8.5x", "   004d2"},
463 
        {"1234", "% 8.6x", "  0004d2"},
464 
        {"1234", "% 8.7x", " 00004d2"},
465 
        {"1234", "% 8.8x", " 000004d2"},
466 
        {"-1234", "% 8.3x", "    -4d2"},
467 
        {"-1234", "% 8.4x", "   -04d2"},
468 
        {"-1234", "% 8.5x", "  -004d2"},
469 
        {"-1234", "% 8.6x", " -0004d2"},
470 
        {"-1234", "% 8.7x", "-00004d2"},
471 
        {"-1234", "% 8.8x", "-000004d2"},
472 
 
473 
        {"1234", "%-8.3d", "1234    "},
474 
        {"1234", "%-8.4d", "1234    "},
475 
        {"1234", "%-8.5d", "01234   "},
476 
        {"1234", "%-8.6d", "001234  "},
477 
        {"1234", "%-8.7d", "0001234 "},
478 
        {"1234", "%-8.8d", "00001234"},
479 
        {"-1234", "%-8.3d", "-1234   "},
480 
        {"-1234", "%-8.4d", "-1234   "},
481 
        {"-1234", "%-8.5d", "-01234  "},
482 
        {"-1234", "%-8.6d", "-001234 "},
483 
        {"-1234", "%-8.7d", "-0001234"},
484 
        {"-1234", "%-8.8d", "-00001234"},
485 
 
486 
        {"16777215", "%b", "111111111111111111111111"}, // 2**24 - 1
487 
 
488 
        {"0", "%.d", ""},
489 
        {"0", "%.0d", ""},
490 
        {"0", "%3.d", ""},
491 
}
492 
 
493 
func TestFormat(t *testing.T) {
494 
        for i, test := range formatTests {
495 
                var x *Int
496 
                if test.input != "" {
497 
                        var ok bool
498 
                        x, ok = new(Int).SetString(test.input, 0)
499 
                        if !ok {
500 
                                t.Errorf("#%d failed reading input %s", i, test.input)
501 
                        }
502 
                }
503 
                output := fmt.Sprintf(test.format, x)
504 
                if output != test.output {
505 
                        t.Errorf("#%d got %q; want %q, {%q, %q, %q}", i, output, test.output, test.input, test.format, test.output)
506 
                }
507 
        }
508 
}
509 
 
510 
var scanTests = []struct {
511 
        input     string
512 
        format    string
513 
        output    string
514 
        remaining int
515 
}{
516 
        {"1010", "%b", "10", 0},
517 
        {"0b1010", "%v", "10", 0},
518 
        {"12", "%o", "10", 0},
519 
        {"012", "%v", "10", 0},
520 
        {"10", "%d", "10", 0},
521 
        {"10", "%v", "10", 0},
522 
        {"a", "%x", "10", 0},
523 
        {"0xa", "%v", "10", 0},
524 
        {"A", "%X", "10", 0},
525 
        {"-A", "%X", "-10", 0},
526 
        {"+0b1011001", "%v", "89", 0},
527 
        {"0xA", "%v", "10", 0},
528 
        {"0 ", "%v", "0", 1},
529 
        {"2+3", "%v", "2", 2},
530 
        {"0XABC 12", "%v", "2748", 3},
531 
}
532 
 
533 
func TestScan(t *testing.T) {
534 
        var buf bytes.Buffer
535 
        for i, test := range scanTests {
536 
                x := new(Int)
537 
                buf.Reset()
538 
                buf.WriteString(test.input)
539 
                if _, err := fmt.Fscanf(&buf, test.format, x); err != nil {
540 
                        t.Errorf("#%d error: %s", i, err)
541 
                }
542 
                if x.String() != test.output {
543 
                        t.Errorf("#%d got %s; want %s", i, x.String(), test.output)
544 
                }
545 
                if buf.Len() != test.remaining {
546 
                        t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining)
547 
                }
548 
        }
549 
}
550 
 
551 
// Examples from the Go Language Spec, section "Arithmetic operators"
552 
var divisionSignsTests = []struct {
553 
        x, y int64
554 
        q, r int64 // T-division
555 
        d, m int64 // Euclidian division
556 
}{
557 
        {5, 3, 1, 2, 1, 2},
558 
        {-5, 3, -1, -2, -2, 1},
559 
        {5, -3, -1, 2, -1, 2},
560 
        {-5, -3, 1, -2, 2, 1},
561 
        {1, 2, 0, 1, 0, 1},
562 
        {8, 4, 2, 0, 2, 0},
563 
}
564 
 
565 
func TestDivisionSigns(t *testing.T) {
566 
        for i, test := range divisionSignsTests {
567 
                x := NewInt(test.x)
568 
                y := NewInt(test.y)
569 
                q := NewInt(test.q)
570 
                r := NewInt(test.r)
571 
                d := NewInt(test.d)
572 
                m := NewInt(test.m)
573 
 
574 
                q1 := new(Int).Quo(x, y)
575 
                r1 := new(Int).Rem(x, y)
576 
                if !isNormalized(q1) {
577 
                        t.Errorf("#%d Quo: %v is not normalized", i, *q1)
578 
                }
579 
                if !isNormalized(r1) {
580 
                        t.Errorf("#%d Rem: %v is not normalized", i, *r1)
581 
                }
582 
                if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
583 
                        t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
584 
                }
585 
 
586 
                q2, r2 := new(Int).QuoRem(x, y, new(Int))
587 
                if !isNormalized(q2) {
588 
                        t.Errorf("#%d Quo: %v is not normalized", i, *q2)
589 
                }
590 
                if !isNormalized(r2) {
591 
                        t.Errorf("#%d Rem: %v is not normalized", i, *r2)
592 
                }
593 
                if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
594 
                        t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
595 
                }
596 
 
597 
                d1 := new(Int).Div(x, y)
598 
                m1 := new(Int).Mod(x, y)
599 
                if !isNormalized(d1) {
600 
                        t.Errorf("#%d Div: %v is not normalized", i, *d1)
601 
                }
602 
                if !isNormalized(m1) {
603 
                        t.Errorf("#%d Mod: %v is not normalized", i, *m1)
604 
                }
605 
                if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
606 
                        t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
607 
                }
608 
 
609 
                d2, m2 := new(Int).DivMod(x, y, new(Int))
610 
                if !isNormalized(d2) {
611 
                        t.Errorf("#%d Div: %v is not normalized", i, *d2)
612 
                }
613 
                if !isNormalized(m2) {
614 
                        t.Errorf("#%d Mod: %v is not normalized", i, *m2)
615 
                }
616 
                if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
617 
                        t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
618 
                }
619 
        }
620 
}
621 
 
622 
func checkSetBytes(b []byte) bool {
623 
        hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
624 
        hex2 := hex.EncodeToString(b)
625 
 
626 
        for len(hex1) < len(hex2) {
627 
                hex1 = "0" + hex1
628 
        }
629 
 
630 
        for len(hex1) > len(hex2) {
631 
                hex2 = "0" + hex2
632 
        }
633 
 
634 
        return hex1 == hex2
635 
}
636 
 
637 
func TestSetBytes(t *testing.T) {
638 
        if err := quick.Check(checkSetBytes, nil); err != nil {
639 
                t.Error(err)
640 
        }
641 
}
642 
 
643 
func checkBytes(b []byte) bool {
644 
        b2 := new(Int).SetBytes(b).Bytes()
645 
        return bytes.Compare(b, b2) == 0
646 
}
647 
 
648 
func TestBytes(t *testing.T) {
649 
        if err := quick.Check(checkSetBytes, nil); err != nil {
650 
                t.Error(err)
651 
        }
652 
}
653 
 
654 
func checkQuo(x, y []byte) bool {
655 
        u := new(Int).SetBytes(x)
656 
        v := new(Int).SetBytes(y)
657 
 
658 
        if len(v.abs) == 0 {
659 
                return true
660 
        }
661 
 
662 
        r := new(Int)
663 
        q, r := new(Int).QuoRem(u, v, r)
664 
 
665 
        if r.Cmp(v) >= 0 {
666 
                return false
667 
        }
668 
 
669 
        uprime := new(Int).Set(q)
670 
        uprime.Mul(uprime, v)
671 
        uprime.Add(uprime, r)
672 
 
673 
        return uprime.Cmp(u) == 0
674 
}
675 
 
676 
var quoTests = []struct {
677 
        x, y string
678 
        q, r string
679 
}{
680 
        {
681 
                "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
682 
                "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
683 
                "50911",
684 
                "1",
685 
        },
686 
        {
687 
                "11510768301994997771168",
688 
                "1328165573307167369775",
689 
                "8",
690 
                "885443715537658812968",
691 
        },
692 
}
693 
 
694 
func TestQuo(t *testing.T) {
695 
        if err := quick.Check(checkQuo, nil); err != nil {
696 
                t.Error(err)
697 
        }
698 
 
699 
        for i, test := range quoTests {
700 
                x, _ := new(Int).SetString(test.x, 10)
701 
                y, _ := new(Int).SetString(test.y, 10)
702 
                expectedQ, _ := new(Int).SetString(test.q, 10)
703 
                expectedR, _ := new(Int).SetString(test.r, 10)
704 
 
705 
                r := new(Int)
706 
                q, r := new(Int).QuoRem(x, y, r)
707 
 
708 
                if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
709 
                        t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
710 
                }
711 
        }
712 
}
713 
 
714 
func TestQuoStepD6(t *testing.T) {
715 
        // See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
716 
        // a code path which only triggers 1 in 10^{-19} cases.
717 
 
718 
        u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
719 
        v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
720 
 
721 
        r := new(Int)
722 
        q, r := new(Int).QuoRem(u, v, r)
723 
        const expectedQ64 = "18446744073709551613"
724 
        const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
725 
        const expectedQ32 = "4294967293"
726 
        const expectedR32 = "39614081266355540837921718287"
727 
        if q.String() != expectedQ64 && q.String() != expectedQ32 ||
728 
                r.String() != expectedR64 && r.String() != expectedR32 {
729 
                t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
730 
        }
731 
}
732 
 
733 
var bitLenTests = []struct {
734 
        in  string
735 
        out int
736 
}{
737 
        {"-1", 1},
738 
        {"0", 0},
739 
        {"1", 1},
740 
        {"2", 2},
741 
        {"4", 3},
742 
        {"0xabc", 12},
743 
        {"0x8000", 16},
744 
        {"0x80000000", 32},
745 
        {"0x800000000000", 48},
746 
        {"0x8000000000000000", 64},
747 
        {"0x80000000000000000000", 80},
748 
        {"-0x4000000000000000000000", 87},
749 
}
750 
 
751 
func TestBitLen(t *testing.T) {
752 
        for i, test := range bitLenTests {
753 
                x, ok := new(Int).SetString(test.in, 0)
754 
                if !ok {
755 
                        t.Errorf("#%d test input invalid: %s", i, test.in)
756 
                        continue
757 
                }
758 
 
759 
                if n := x.BitLen(); n != test.out {
760 
                        t.Errorf("#%d got %d want %d", i, n, test.out)
761 
                }
762 
        }
763 
}
764 
 
765 
var expTests = []struct {
766 
        x, y, m string
767 
        out     string
768 
}{
769 
        {"5", "0", "", "1"},
770 
        {"-5", "0", "", "-1"},
771 
        {"5", "1", "", "5"},
772 
        {"-5", "1", "", "-5"},
773 
        {"-2", "3", "2", "0"},
774 
        {"5", "2", "", "25"},
775 
        {"1", "65537", "2", "1"},
776 
        {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
777 
        {"0x8000000000000000", "2", "6719", "4944"},
778 
        {"0x8000000000000000", "3", "6719", "5447"},
779 
        {"0x8000000000000000", "1000", "6719", "1603"},
780 
        {"0x8000000000000000", "1000000", "6719", "3199"},
781 
        {
782 
                "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
783 
                "298472983472983471903246121093472394872319615612417471234712061",
784 
                "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
785 
                "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
786 
        },
787 
}
788 
 
789 
func TestExp(t *testing.T) {
790 
        for i, test := range expTests {
791 
                x, ok1 := new(Int).SetString(test.x, 0)
792 
                y, ok2 := new(Int).SetString(test.y, 0)
793 
                out, ok3 := new(Int).SetString(test.out, 0)
794 
 
795 
                var ok4 bool
796 
                var m *Int
797 
 
798 
                if len(test.m) == 0 {
799 
                        m, ok4 = nil, true
800 
                } else {
801 
                        m, ok4 = new(Int).SetString(test.m, 0)
802 
                }
803 
 
804 
                if !ok1 || !ok2 || !ok3 || !ok4 {
805 
                        t.Errorf("#%d: error in input", i)
806 
                        continue
807 
                }
808 
 
809 
                z := y.Exp(x, y, m)
810 
                if !isNormalized(z) {
811 
                        t.Errorf("#%d: %v is not normalized", i, *z)
812 
                }
813 
                if z.Cmp(out) != 0 {
814 
                        t.Errorf("#%d: got %s want %s", i, z, out)
815 
                }
816 
        }
817 
}
818 
 
819 
func checkGcd(aBytes, bBytes []byte) bool {
820 
        a := new(Int).SetBytes(aBytes)
821 
        b := new(Int).SetBytes(bBytes)
822 
 
823 
        x := new(Int)
824 
        y := new(Int)
825 
        d := new(Int)
826 
 
827 
        d.GCD(x, y, a, b)
828 
        x.Mul(x, a)
829 
        y.Mul(y, b)
830 
        x.Add(x, y)
831 
 
832 
        return x.Cmp(d) == 0
833 
}
834 
 
835 
var gcdTests = []struct {
836 
        a, b    int64
837 
        d, x, y int64
838 
}{
839 
        {120, 23, 1, -9, 47},
840 
}
841 
 
842 
func TestGcd(t *testing.T) {
843 
        for i, test := range gcdTests {
844 
                a := NewInt(test.a)
845 
                b := NewInt(test.b)
846 
 
847 
                x := new(Int)
848 
                y := new(Int)
849 
                d := new(Int)
850 
 
851 
                expectedX := NewInt(test.x)
852 
                expectedY := NewInt(test.y)
853 
                expectedD := NewInt(test.d)
854 
 
855 
                d.GCD(x, y, a, b)
856 
 
857 
                if expectedX.Cmp(x) != 0 ||
858 
                        expectedY.Cmp(y) != 0 ||
859 
                        expectedD.Cmp(d) != 0 {
860 
                        t.Errorf("#%d got (%s %s %s) want (%s %s %s)", i, x, y, d, expectedX, expectedY, expectedD)
861 
                }
862 
        }
863 
 
864 
        quick.Check(checkGcd, nil)
865 
}
866 
 
867 
var primes = []string{
868 
        "2",
869 
        "3",
870 
        "5",
871 
        "7",
872 
        "11",
873 
 
874 
        "13756265695458089029",
875 
        "13496181268022124907",
876 
        "10953742525620032441",
877 
        "17908251027575790097",
878 
 
879 
        // http://code.google.com/p/go/issues/detail?id=638
880 
        "18699199384836356663",
881 
 
882 
        "98920366548084643601728869055592650835572950932266967461790948584315647051443",
883 
        "94560208308847015747498523884063394671606671904944666360068158221458669711639",
884 
 
885 
        // http://primes.utm.edu/lists/small/small3.html
886 
        "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
887 
        "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
888 
        "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
889 
        "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
890 
}
891 
 
892 
var composites = []string{
893 
        "21284175091214687912771199898307297748211672914763848041968395774954376176754",
894 
        "6084766654921918907427900243509372380954290099172559290432744450051395395951",
895 
        "84594350493221918389213352992032324280367711247940675652888030554255915464401",
896 
        "82793403787388584738507275144194252681",
897 
}
898 
 
899 
func TestProbablyPrime(t *testing.T) {
900 
        nreps := 20
901 
        if testing.Short() {
902 
                nreps = 1
903 
        }
904 
        for i, s := range primes {
905 
                p, _ := new(Int).SetString(s, 10)
906 
                if !p.ProbablyPrime(nreps) {
907 
                        t.Errorf("#%d prime found to be non-prime (%s)", i, s)
908 
                }
909 
        }
910 
 
911 
        for i, s := range composites {
912 
                c, _ := new(Int).SetString(s, 10)
913 
                if c.ProbablyPrime(nreps) {
914 
                        t.Errorf("#%d composite found to be prime (%s)", i, s)
915 
                }
916 
                if testing.Short() {
917 
                        break
918 
                }
919 
        }
920 
}
921 
 
922 
type intShiftTest struct {
923 
        in    string
924 
        shift uint
925 
        out   string
926 
}
927 
 
928 
var rshTests = []intShiftTest{
929 
        {"0", 0, "0"},
930 
        {"-0", 0, "0"},
931 
        {"0", 1, "0"},
932 
        {"0", 2, "0"},
933 
        {"1", 0, "1"},
934 
        {"1", 1, "0"},
935 
        {"1", 2, "0"},
936 
        {"2", 0, "2"},
937 
        {"2", 1, "1"},
938 
        {"-1", 0, "-1"},
939 
        {"-1", 1, "-1"},
940 
        {"-1", 10, "-1"},
941 
        {"-100", 2, "-25"},
942 
        {"-100", 3, "-13"},
943 
        {"-100", 100, "-1"},
944 
        {"4294967296", 0, "4294967296"},
945 
        {"4294967296", 1, "2147483648"},
946 
        {"4294967296", 2, "1073741824"},
947 
        {"18446744073709551616", 0, "18446744073709551616"},
948 
        {"18446744073709551616", 1, "9223372036854775808"},
949 
        {"18446744073709551616", 2, "4611686018427387904"},
950 
        {"18446744073709551616", 64, "1"},
951 
        {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
952 
        {"340282366920938463463374607431768211456", 128, "1"},
953 
}
954 
 
955 
func TestRsh(t *testing.T) {
956 
        for i, test := range rshTests {
957 
                in, _ := new(Int).SetString(test.in, 10)
958 
                expected, _ := new(Int).SetString(test.out, 10)
959 
                out := new(Int).Rsh(in, test.shift)
960 
 
961 
                if !isNormalized(out) {
962 
                        t.Errorf("#%d: %v is not normalized", i, *out)
963 
                }
964 
                if out.Cmp(expected) != 0 {
965 
                        t.Errorf("#%d: got %s want %s", i, out, expected)
966 
                }
967 
        }
968 
}
969 
 
970 
func TestRshSelf(t *testing.T) {
971 
        for i, test := range rshTests {
972 
                z, _ := new(Int).SetString(test.in, 10)
973 
                expected, _ := new(Int).SetString(test.out, 10)
974 
                z.Rsh(z, test.shift)
975 
 
976 
                if !isNormalized(z) {
977 
                        t.Errorf("#%d: %v is not normalized", i, *z)
978 
                }
979 
                if z.Cmp(expected) != 0 {
980 
                        t.Errorf("#%d: got %s want %s", i, z, expected)
981 
                }
982 
        }
983 
}
984 
 
985 
var lshTests = []intShiftTest{
986 
        {"0", 0, "0"},
987 
        {"0", 1, "0"},
988 
        {"0", 2, "0"},
989 
        {"1", 0, "1"},
990 
        {"1", 1, "2"},
991 
        {"1", 2, "4"},
992 
        {"2", 0, "2"},
993 
        {"2", 1, "4"},
994 
        {"2", 2, "8"},
995 
        {"-87", 1, "-174"},
996 
        {"4294967296", 0, "4294967296"},
997 
        {"4294967296", 1, "8589934592"},
998 
        {"4294967296", 2, "17179869184"},
999 
        {"18446744073709551616", 0, "18446744073709551616"},
1000 
        {"9223372036854775808", 1, "18446744073709551616"},
1001 
        {"4611686018427387904", 2, "18446744073709551616"},
1002 
        {"1", 64, "18446744073709551616"},
1003 
        {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
1004 
        {"1", 128, "340282366920938463463374607431768211456"},
1005 
}
1006 
 
1007 
func TestLsh(t *testing.T) {
1008 
        for i, test := range lshTests {
1009 
                in, _ := new(Int).SetString(test.in, 10)
1010 
                expected, _ := new(Int).SetString(test.out, 10)
1011 
                out := new(Int).Lsh(in, test.shift)
1012 
 
1013 
                if !isNormalized(out) {
1014 
                        t.Errorf("#%d: %v is not normalized", i, *out)
1015 
                }
1016 
                if out.Cmp(expected) != 0 {
1017 
                        t.Errorf("#%d: got %s want %s", i, out, expected)
1018 
                }
1019 
        }
1020 
}
1021 
 
1022 
func TestLshSelf(t *testing.T) {
1023 
        for i, test := range lshTests {
1024 
                z, _ := new(Int).SetString(test.in, 10)
1025 
                expected, _ := new(Int).SetString(test.out, 10)
1026 
                z.Lsh(z, test.shift)
1027 
 
1028 
                if !isNormalized(z) {
1029 
                        t.Errorf("#%d: %v is not normalized", i, *z)
1030 
                }
1031 
                if z.Cmp(expected) != 0 {
1032 
                        t.Errorf("#%d: got %s want %s", i, z, expected)
1033 
                }
1034 
        }
1035 
}
1036 
 
1037 
func TestLshRsh(t *testing.T) {
1038 
        for i, test := range rshTests {
1039 
                in, _ := new(Int).SetString(test.in, 10)
1040 
                out := new(Int).Lsh(in, test.shift)
1041 
                out = out.Rsh(out, test.shift)
1042 
 
1043 
                if !isNormalized(out) {
1044 
                        t.Errorf("#%d: %v is not normalized", i, *out)
1045 
                }
1046 
                if in.Cmp(out) != 0 {
1047 
                        t.Errorf("#%d: got %s want %s", i, out, in)
1048 
                }
1049 
        }
1050 
        for i, test := range lshTests {
1051 
                in, _ := new(Int).SetString(test.in, 10)
1052 
                out := new(Int).Lsh(in, test.shift)
1053 
                out.Rsh(out, test.shift)
1054 
 
1055 
                if !isNormalized(out) {
1056 
                        t.Errorf("#%d: %v is not normalized", i, *out)
1057 
                }
1058 
                if in.Cmp(out) != 0 {
1059 
                        t.Errorf("#%d: got %s want %s", i, out, in)
1060 
                }
1061 
        }
1062 
}
1063 
 
1064 
var int64Tests = []int64{
1065 
        0,
1066 
        1,
1067 
        -1,
1068 
        4294967295,
1069 
        -4294967295,
1070 
        4294967296,
1071 
        -4294967296,
1072 
        9223372036854775807,
1073 
        -9223372036854775807,
1074 
        -9223372036854775808,
1075 
}
1076 
 
1077 
func TestInt64(t *testing.T) {
1078 
        for i, testVal := range int64Tests {
1079 
                in := NewInt(testVal)
1080 
                out := in.Int64()
1081 
 
1082 
                if out != testVal {
1083 
                        t.Errorf("#%d got %d want %d", i, out, testVal)
1084 
                }
1085 
        }
1086 
}
1087 
 
1088 
var bitwiseTests = []struct {
1089 
        x, y                 string
1090 
        and, or, xor, andNot string
1091 
}{
1092 
        {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
1093 
        {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
1094 
        {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
1095 
        {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
1096 
        {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
1097 
        {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
1098 
        {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
1099 
        {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
1100 
        {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
1101 
        {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
1102 
        {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
1103 
        {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
1104 
        {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
1105 
        {
1106 
                "0x1000009dc6e3d9822cba04129bcbe3401",
1107 
                "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1108 
                "0x1000001186210100001000009048c2001",
1109 
                "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1110 
                "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1111 
                "0x8c40c2d8822caa04120b8321400",
1112 
        },
1113 
        {
1114 
                "0x1000009dc6e3d9822cba04129bcbe3401",
1115 
                "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1116 
                "0x8c40c2d8822caa04120b8321401",
1117 
                "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
1118 
                "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
1119 
                "0x1000001186210100001000009048c2000",
1120 
        },
1121 
        {
1122 
                "-0x1000009dc6e3d9822cba04129bcbe3401",
1123 
                "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1124 
                "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1125 
                "-0x1000001186210100001000009048c2001",
1126 
                "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1127 
                "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
1128 
        },
1129 
}
1130 
 
1131 
type bitFun func(z, x, y *Int) *Int
1132 
 
1133 
func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1134 
        expected := new(Int)
1135 
        expected.SetString(exp, 0)
1136 
 
1137 
        out := f(new(Int), x, y)
1138 
        if out.Cmp(expected) != 0 {
1139 
                t.Errorf("%s: got %s want %s", msg, out, expected)
1140 
        }
1141 
}
1142 
 
1143 
func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1144 
        self := new(Int)
1145 
        self.Set(x)
1146 
        expected := new(Int)
1147 
        expected.SetString(exp, 0)
1148 
 
1149 
        self = f(self, self, y)
1150 
        if self.Cmp(expected) != 0 {
1151 
                t.Errorf("%s: got %s want %s", msg, self, expected)
1152 
        }
1153 
}
1154 
 
1155 
func altBit(x *Int, i int) uint {
1156 
        z := new(Int).Rsh(x, uint(i))
1157 
        z = z.And(z, NewInt(1))
1158 
        if z.Cmp(new(Int)) != 0 {
1159 
                return 1
1160 
        }
1161 
        return 0
1162 
}
1163 
 
1164 
func altSetBit(z *Int, x *Int, i int, b uint) *Int {
1165 
        one := NewInt(1)
1166 
        m := one.Lsh(one, uint(i))
1167 
        switch b {
1168 
        case 1:
1169 
                return z.Or(x, m)
1170 
        case 0:
1171 
                return z.AndNot(x, m)
1172 
        }
1173 
        panic("set bit is not 0 or 1")
1174 
}
1175 
 
1176 
func testBitset(t *testing.T, x *Int) {
1177 
        n := x.BitLen()
1178 
        z := new(Int).Set(x)
1179 
        z1 := new(Int).Set(x)
1180 
        for i := 0; i < n+10; i++ {
1181 
                old := z.Bit(i)
1182 
                old1 := altBit(z1, i)
1183 
                if old != old1 {
1184 
                        t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
1185 
                }
1186 
                z := new(Int).SetBit(z, i, 1)
1187 
                z1 := altSetBit(new(Int), z1, i, 1)
1188 
                if z.Bit(i) == 0 {
1189 
                        t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
1190 
                }
1191 
                if z.Cmp(z1) != 0 {
1192 
                        t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
1193 
                }
1194 
                z.SetBit(z, i, 0)
1195 
                altSetBit(z1, z1, i, 0)
1196 
                if z.Bit(i) != 0 {
1197 
                        t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
1198 
                }
1199 
                if z.Cmp(z1) != 0 {
1200 
                        t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
1201 
                }
1202 
                altSetBit(z1, z1, i, old)
1203 
                z.SetBit(z, i, old)
1204 
                if z.Cmp(z1) != 0 {
1205 
                        t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
1206 
                }
1207 
        }
1208 
        if z.Cmp(x) != 0 {
1209 
                t.Errorf("bitset: got %s want %s", z, x)
1210 
        }
1211 
}
1212 
 
1213 
var bitsetTests = []struct {
1214 
        x string
1215 
        i int
1216 
        b uint
1217 
}{
1218 
        {"0", 0, 0},
1219 
        {"0", 200, 0},
1220 
        {"1", 0, 1},
1221 
        {"1", 1, 0},
1222 
        {"-1", 0, 1},
1223 
        {"-1", 200, 1},
1224 
        {"0x2000000000000000000000000000", 108, 0},
1225 
        {"0x2000000000000000000000000000", 109, 1},
1226 
        {"0x2000000000000000000000000000", 110, 0},
1227 
        {"-0x2000000000000000000000000001", 108, 1},
1228 
        {"-0x2000000000000000000000000001", 109, 0},
1229 
        {"-0x2000000000000000000000000001", 110, 1},
1230 
}
1231 
 
1232 
func TestBitSet(t *testing.T) {
1233 
        for _, test := range bitwiseTests {
1234 
                x := new(Int)
1235 
                x.SetString(test.x, 0)
1236 
                testBitset(t, x)
1237 
                x = new(Int)
1238 
                x.SetString(test.y, 0)
1239 
                testBitset(t, x)
1240 
        }
1241 
        for i, test := range bitsetTests {
1242 
                x := new(Int)
1243 
                x.SetString(test.x, 0)
1244 
                b := x.Bit(test.i)
1245 
                if b != test.b {
1246 
                        t.Errorf("#%d got %v want %v", i, b, test.b)
1247 
                }
1248 
        }
1249 
        z := NewInt(1)
1250 
        z.SetBit(NewInt(0), 2, 1)
1251 
        if z.Cmp(NewInt(4)) != 0 {
1252 
                t.Errorf("destination leaked into result; got %s want 4", z)
1253 
        }
1254 
}
1255 
 
1256 
func BenchmarkBitset(b *testing.B) {
1257 
        z := new(Int)
1258 
        z.SetBit(z, 512, 1)
1259 
        b.ResetTimer()
1260 
        b.StartTimer()
1261 
        for i := b.N - 1; i >= 0; i-- {
1262 
                z.SetBit(z, i&512, 1)
1263 
        }
1264 
}
1265 
 
1266 
func BenchmarkBitsetNeg(b *testing.B) {
1267 
        z := NewInt(-1)
1268 
        z.SetBit(z, 512, 0)
1269 
        b.ResetTimer()
1270 
        b.StartTimer()
1271 
        for i := b.N - 1; i >= 0; i-- {
1272 
                z.SetBit(z, i&512, 0)
1273 
        }
1274 
}
1275 
 
1276 
func BenchmarkBitsetOrig(b *testing.B) {
1277 
        z := new(Int)
1278 
        altSetBit(z, z, 512, 1)
1279 
        b.ResetTimer()
1280 
        b.StartTimer()
1281 
        for i := b.N - 1; i >= 0; i-- {
1282 
                altSetBit(z, z, i&512, 1)
1283 
        }
1284 
}
1285 
 
1286 
func BenchmarkBitsetNegOrig(b *testing.B) {
1287 
        z := NewInt(-1)
1288 
        altSetBit(z, z, 512, 0)
1289 
        b.ResetTimer()
1290 
        b.StartTimer()
1291 
        for i := b.N - 1; i >= 0; i-- {
1292 
                altSetBit(z, z, i&512, 0)
1293 
        }
1294 
}
1295 
 
1296 
func TestBitwise(t *testing.T) {
1297 
        x := new(Int)
1298 
        y := new(Int)
1299 
        for _, test := range bitwiseTests {
1300 
                x.SetString(test.x, 0)
1301 
                y.SetString(test.y, 0)
1302 
 
1303 
                testBitFun(t, "and", (*Int).And, x, y, test.and)
1304 
                testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
1305 
                testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1306 
                testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1307 
                testBitFun(t, "or", (*Int).Or, x, y, test.or)
1308 
                testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
1309 
                testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
1310 
                testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
1311 
        }
1312 
}
1313 
 
1314 
var notTests = []struct {
1315 
        in  string
1316 
        out string
1317 
}{
1318 
        {"0", "-1"},
1319 
        {"1", "-2"},
1320 
        {"7", "-8"},
1321 
        {"0", "-1"},
1322 
        {"-81910", "81909"},
1323 
        {
1324 
                "298472983472983471903246121093472394872319615612417471234712061",
1325 
                "-298472983472983471903246121093472394872319615612417471234712062",
1326 
        },
1327 
}
1328 
 
1329 
func TestNot(t *testing.T) {
1330 
        in := new(Int)
1331 
        out := new(Int)
1332 
        expected := new(Int)
1333 
        for i, test := range notTests {
1334 
                in.SetString(test.in, 10)
1335 
                expected.SetString(test.out, 10)
1336 
                out = out.Not(in)
1337 
                if out.Cmp(expected) != 0 {
1338 
                        t.Errorf("#%d: got %s want %s", i, out, expected)
1339 
                }
1340 
                out = out.Not(out)
1341 
                if out.Cmp(in) != 0 {
1342 
                        t.Errorf("#%d: got %s want %s", i, out, in)
1343 
                }
1344 
        }
1345 
}
1346 
 
1347 
var modInverseTests = []struct {
1348 
        element string
1349 
        prime   string
1350 
}{
1351 
        {"1", "7"},
1352 
        {"1", "13"},
1353 
        {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1354 
}
1355 
 
1356 
func TestModInverse(t *testing.T) {
1357 
        var element, prime Int
1358 
        one := NewInt(1)
1359 
        for i, test := range modInverseTests {
1360 
                (&element).SetString(test.element, 10)
1361 
                (&prime).SetString(test.prime, 10)
1362 
                inverse := new(Int).ModInverse(&element, &prime)
1363 
                inverse.Mul(inverse, &element)
1364 
                inverse.Mod(inverse, &prime)
1365 
                if inverse.Cmp(one) != 0 {
1366 
                        t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse)
1367 
                }
1368 
        }
1369 
}
1370 
 
1371 
// used by TestIntGobEncoding and TestRatGobEncoding
1372 
var gobEncodingTests = []string{
1373 
        "0",
1374 
        "1",
1375 
        "2",
1376 
        "10",
1377 
        "42",
1378 
        "1234567890",
1379 
        "298472983472983471903246121093472394872319615612417471234712061",
1380 
}
1381 
 
1382 
func TestIntGobEncoding(t *testing.T) {
1383 
        var medium bytes.Buffer
1384 
        enc := gob.NewEncoder(&medium)
1385 
        dec := gob.NewDecoder(&medium)
1386 
        for i, test := range gobEncodingTests {
1387 
                for j := 0; j < 2; j++ {
1388 
                        medium.Reset() // empty buffer for each test case (in case of failures)
1389 
                        stest := test
1390 
                        if j != 0 {
1391 
                                // negative numbers
1392 
                                stest = "-" + test
1393 
                        }
1394 
                        var tx Int
1395 
                        tx.SetString(stest, 10)
1396 
                        if err := enc.Encode(&tx); err != nil {
1397 
                                t.Errorf("#%d%c: encoding failed: %s", i, 'a'+j, err)
1398 
                        }
1399 
                        var rx Int
1400 
                        if err := dec.Decode(&rx); err != nil {
1401 
                                t.Errorf("#%d%c: decoding failed: %s", i, 'a'+j, err)
1402 
                        }
1403 
                        if rx.Cmp(&tx) != 0 {
1404 
                                t.Errorf("#%d%c: transmission failed: got %s want %s", i, 'a'+j, &rx, &tx)
1405 
                        }
1406 
                }
1407 
        }
1408 
}
1409 
 
1410 
func TestIssue2607(t *testing.T) {
1411 
        // This code sequence used to hang.
1412 
        n := NewInt(10)
1413 
        n.Rand(rand.New(rand.NewSource(9)), n)
1414 
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.