From 47ab3d4a42e9ab51c465c4322d2ec233f6324e6b Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 15:16:40 +0200 Subject: Adding upstream version 1.18.10. Signed-off-by: Daniel Baumann --- misc/cgo/gmp/fib.go | 46 +++++++ misc/cgo/gmp/gmp.go | 380 ++++++++++++++++++++++++++++++++++++++++++++++++++++ misc/cgo/gmp/pi.go | 74 ++++++++++ 3 files changed, 500 insertions(+) create mode 100644 misc/cgo/gmp/fib.go create mode 100644 misc/cgo/gmp/gmp.go create mode 100644 misc/cgo/gmp/pi.go (limited to 'misc/cgo/gmp') diff --git a/misc/cgo/gmp/fib.go b/misc/cgo/gmp/fib.go new file mode 100644 index 0000000..f453fcf --- /dev/null +++ b/misc/cgo/gmp/fib.go @@ -0,0 +1,46 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build ignore +// +build ignore + +// Compute Fibonacci numbers with two goroutines +// that pass integers back and forth. No actual +// concurrency, just threads and synchronization +// and foreign code on multiple pthreads. + +package main + +import ( + big "." + "runtime" +) + +func fibber(c chan *big.Int, out chan string, n int64) { + // Keep the fibbers in dedicated operating system + // threads, so that this program tests coordination + // between pthreads and not just goroutines. + runtime.LockOSThread() + + i := big.NewInt(n) + if n == 0 { + c <- i + } + for { + j := <-c + out <- j.String() + i.Add(i, j) + c <- i + } +} + +func main() { + c := make(chan *big.Int) + out := make(chan string) + go fibber(c, out, 0) + go fibber(c, out, 1) + for i := 0; i < 200; i++ { + println(<-out) + } +} diff --git a/misc/cgo/gmp/gmp.go b/misc/cgo/gmp/gmp.go new file mode 100644 index 0000000..971a10a --- /dev/null +++ b/misc/cgo/gmp/gmp.go @@ -0,0 +1,380 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +/* +An example of wrapping a C library in Go. This is the GNU +multiprecision library gmp's integer type mpz_t wrapped to look like +the Go package big's integer type Int. + +This is a syntactically valid Go program—it can be parsed with the Go +parser and processed by godoc—but it is not compiled directly by gc. +Instead, a separate tool, cgo, processes it to produce three output +files. The first two, 6g.go and 6c.c, are a Go source file for 6g and +a C source file for 6c; both compile as part of the named package +(gmp, in this example). The third, gcc.c, is a C source file for gcc; +it compiles into a shared object (.so) that is dynamically linked into +any 6.out that imports the first two files. + +The stanza + + // #include + import "C" + +is a signal to cgo. The doc comment on the import of "C" provides +additional context for the C file. Here it is just a single #include +but it could contain arbitrary C definitions to be imported and used. + +Cgo recognizes any use of a qualified identifier C.xxx and uses gcc to +find the definition of xxx. If xxx is a type, cgo replaces C.xxx with +a Go translation. C arithmetic types translate to precisely-sized Go +arithmetic types. A C struct translates to a Go struct, field by +field; unrepresentable fields are replaced with opaque byte arrays. A +C union translates into a struct containing the first union member and +perhaps additional padding. C arrays become Go arrays. C pointers +become Go pointers. C function pointers become Go's uintptr. +C void pointers become Go's unsafe.Pointer. + +For example, mpz_t is defined in as: + + typedef unsigned long int mp_limb_t; + + typedef struct + { + int _mp_alloc; + int _mp_size; + mp_limb_t *_mp_d; + } __mpz_struct; + + typedef __mpz_struct mpz_t[1]; + +Cgo generates: + + type _C_int int32 + type _C_mp_limb_t uint64 + type _C___mpz_struct struct { + _mp_alloc _C_int; + _mp_size _C_int; + _mp_d *_C_mp_limb_t; + } + type _C_mpz_t [1]_C___mpz_struct + +and then replaces each occurrence of a type C.xxx with _C_xxx. + +If xxx is data, cgo arranges for C.xxx to refer to the C variable, +with the type translated as described above. To do this, cgo must +introduce a Go variable that points at the C variable (the linker can +be told to initialize this pointer). For example, if the gmp library +provided + + mpz_t zero; + +then cgo would rewrite a reference to C.zero by introducing + + var _C_zero *C.mpz_t + +and then replacing all instances of C.zero with (*_C_zero). + +Cgo's most interesting translation is for functions. If xxx is a C +function, then cgo rewrites C.xxx into a new function _C_xxx that +calls the C xxx in a standard pthread. The new function translates +its arguments, calls xxx, and translates the return value. + +Translation of parameters and the return value follows the type +translation above except that arrays passed as parameters translate +explicitly in Go to pointers to arrays, as they do (implicitly) in C. + +Garbage collection is the big problem. It is fine for the Go world to +have pointers into the C world and to free those pointers when they +are no longer needed. To help, the Go code can define Go objects +holding the C pointers and use runtime.SetFinalizer on those Go objects. + +It is much more difficult for the C world to have pointers into the Go +world, because the Go garbage collector is unaware of the memory +allocated by C. The most important consideration is not to +constrain future implementations, so the rule is that Go code can +hand a Go pointer to C code but must separately arrange for +Go to hang on to a reference to the pointer until C is done with it. +*/ +package gmp + +/* +#cgo LDFLAGS: -lgmp +#include +#include + +// gmp 5.0.0+ changed the type of the 3rd argument to mp_bitcnt_t, +// so, to support older versions, we wrap these two functions. +void _mpz_mul_2exp(mpz_ptr a, mpz_ptr b, unsigned long n) { + mpz_mul_2exp(a, b, n); +} +void _mpz_div_2exp(mpz_ptr a, mpz_ptr b, unsigned long n) { + mpz_div_2exp(a, b, n); +} +*/ +import "C" + +import ( + "os" + "unsafe" +) + +/* + * one of a kind + */ + +// An Int represents a signed multi-precision integer. +// The zero value for an Int represents the value 0. +type Int struct { + i C.mpz_t + init bool +} + +// NewInt returns a new Int initialized to x. +func NewInt(x int64) *Int { return new(Int).SetInt64(x) } + +// Int promises that the zero value is a 0, but in gmp +// the zero value is a crash. To bridge the gap, the +// init bool says whether this is a valid gmp value. +// doinit initializes z.i if it needs it. This is not inherent +// to FFI, just a mismatch between Go's convention of +// making zero values useful and gmp's decision not to. +func (z *Int) doinit() { + if z.init { + return + } + z.init = true + C.mpz_init(&z.i[0]) +} + +// Bytes returns z's representation as a big-endian byte array. +func (z *Int) Bytes() []byte { + b := make([]byte, (z.Len()+7)/8) + n := C.size_t(len(b)) + C.mpz_export(unsafe.Pointer(&b[0]), &n, 1, 1, 1, 0, &z.i[0]) + return b[0:n] +} + +// Len returns the length of z in bits. 0 is considered to have length 1. +func (z *Int) Len() int { + z.doinit() + return int(C.mpz_sizeinbase(&z.i[0], 2)) +} + +// Set sets z = x and returns z. +func (z *Int) Set(x *Int) *Int { + z.doinit() + C.mpz_set(&z.i[0], &x.i[0]) + return z +} + +// SetBytes interprets b as the bytes of a big-endian integer +// and sets z to that value. +func (z *Int) SetBytes(b []byte) *Int { + z.doinit() + if len(b) == 0 { + z.SetInt64(0) + } else { + C.mpz_import(&z.i[0], C.size_t(len(b)), 1, 1, 1, 0, unsafe.Pointer(&b[0])) + } + return z +} + +// SetInt64 sets z = x and returns z. +func (z *Int) SetInt64(x int64) *Int { + z.doinit() + // TODO(rsc): more work on 32-bit platforms + C.mpz_set_si(&z.i[0], C.long(x)) + return z +} + +// SetString interprets s as a number in the given base +// and sets z to that value. The base must be in the range [2,36]. +// SetString returns an error if s cannot be parsed or the base is invalid. +func (z *Int) SetString(s string, base int) error { + z.doinit() + if base < 2 || base > 36 { + return os.ErrInvalid + } + p := C.CString(s) + defer C.free(unsafe.Pointer(p)) + if C.mpz_set_str(&z.i[0], p, C.int(base)) < 0 { + return os.ErrInvalid + } + return nil +} + +// String returns the decimal representation of z. +func (z *Int) String() string { + if z == nil { + return "nil" + } + z.doinit() + p := C.mpz_get_str(nil, 10, &z.i[0]) + s := C.GoString(p) + C.free(unsafe.Pointer(p)) + return s +} + +func (z *Int) destroy() { + if z.init { + C.mpz_clear(&z.i[0]) + } + z.init = false +} + +/* + * arithmetic + */ + +// Add sets z = x + y and returns z. +func (z *Int) Add(x, y *Int) *Int { + x.doinit() + y.doinit() + z.doinit() + C.mpz_add(&z.i[0], &x.i[0], &y.i[0]) + return z +} + +// Sub sets z = x - y and returns z. +func (z *Int) Sub(x, y *Int) *Int { + x.doinit() + y.doinit() + z.doinit() + C.mpz_sub(&z.i[0], &x.i[0], &y.i[0]) + return z +} + +// Mul sets z = x * y and returns z. +func (z *Int) Mul(x, y *Int) *Int { + x.doinit() + y.doinit() + z.doinit() + C.mpz_mul(&z.i[0], &x.i[0], &y.i[0]) + return z +} + +// Div sets z = x / y, rounding toward zero, and returns z. +func (z *Int) Div(x, y *Int) *Int { + x.doinit() + y.doinit() + z.doinit() + C.mpz_tdiv_q(&z.i[0], &x.i[0], &y.i[0]) + return z +} + +// Mod sets z = x % y and returns z. +// Like the result of the Go % operator, z has the same sign as x. +func (z *Int) Mod(x, y *Int) *Int { + x.doinit() + y.doinit() + z.doinit() + C.mpz_tdiv_r(&z.i[0], &x.i[0], &y.i[0]) + return z +} + +// Lsh sets z = x << s and returns z. +func (z *Int) Lsh(x *Int, s uint) *Int { + x.doinit() + z.doinit() + C._mpz_mul_2exp(&z.i[0], &x.i[0], C.ulong(s)) + return z +} + +// Rsh sets z = x >> s and returns z. +func (z *Int) Rsh(x *Int, s uint) *Int { + x.doinit() + z.doinit() + C._mpz_div_2exp(&z.i[0], &x.i[0], C.ulong(s)) + return z +} + +// Exp sets z = x^y % m and returns z. +// If m == nil, Exp sets z = x^y. +func (z *Int) Exp(x, y, m *Int) *Int { + m.doinit() + x.doinit() + y.doinit() + z.doinit() + if m == nil { + C.mpz_pow_ui(&z.i[0], &x.i[0], C.mpz_get_ui(&y.i[0])) + } else { + C.mpz_powm(&z.i[0], &x.i[0], &y.i[0], &m.i[0]) + } + return z +} + +func (z *Int) Int64() int64 { + if !z.init { + return 0 + } + return int64(C.mpz_get_si(&z.i[0])) +} + +// Neg sets z = -x and returns z. +func (z *Int) Neg(x *Int) *Int { + x.doinit() + z.doinit() + C.mpz_neg(&z.i[0], &x.i[0]) + return z +} + +// Abs sets z to the absolute value of x and returns z. +func (z *Int) Abs(x *Int) *Int { + x.doinit() + z.doinit() + C.mpz_abs(&z.i[0], &x.i[0]) + return z +} + +/* + * functions without a clear receiver + */ + +// CmpInt compares x and y. The result is +// +// -1 if x < y +// 0 if x == y +// +1 if x > y +// +func CmpInt(x, y *Int) int { + x.doinit() + y.doinit() + switch cmp := C.mpz_cmp(&x.i[0], &y.i[0]); { + case cmp < 0: + return -1 + case cmp == 0: + return 0 + } + return +1 +} + +// DivModInt sets q = x / y and r = x % y. +func DivModInt(q, r, x, y *Int) { + q.doinit() + r.doinit() + x.doinit() + y.doinit() + C.mpz_tdiv_qr(&q.i[0], &r.i[0], &x.i[0], &y.i[0]) +} + +// GcdInt sets d to the greatest common divisor of a and b, +// which must be positive numbers. +// If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y. +// If either a or b is not positive, GcdInt sets d = x = y = 0. +func GcdInt(d, x, y, a, b *Int) { + d.doinit() + x.doinit() + y.doinit() + a.doinit() + b.doinit() + C.mpz_gcdext(&d.i[0], &x.i[0], &y.i[0], &a.i[0], &b.i[0]) +} + +// ProbablyPrime performs n Miller-Rabin tests to check whether z is prime. +// If it returns true, z is prime with probability 1 - 1/4^n. +// If it returns false, z is not prime. +func (z *Int) ProbablyPrime(n int) bool { + z.doinit() + return int(C.mpz_probab_prime_p(&z.i[0], C.int(n))) > 0 +} diff --git a/misc/cgo/gmp/pi.go b/misc/cgo/gmp/pi.go new file mode 100644 index 0000000..5ea0349 --- /dev/null +++ b/misc/cgo/gmp/pi.go @@ -0,0 +1,74 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build ignore +// +build ignore + +package main + +import ( + big "." + "fmt" + "runtime" +) + +var ( + tmp1 = big.NewInt(0) + tmp2 = big.NewInt(0) + numer = big.NewInt(1) + accum = big.NewInt(0) + denom = big.NewInt(1) + ten = big.NewInt(10) +) + +func extractDigit() int64 { + if big.CmpInt(numer, accum) > 0 { + return -1 + } + tmp1.Lsh(numer, 1).Add(tmp1, numer).Add(tmp1, accum) + big.DivModInt(tmp1, tmp2, tmp1, denom) + tmp2.Add(tmp2, numer) + if big.CmpInt(tmp2, denom) >= 0 { + return -1 + } + return tmp1.Int64() +} + +func nextTerm(k int64) { + y2 := k*2 + 1 + accum.Add(accum, tmp1.Lsh(numer, 1)) + accum.Mul(accum, tmp1.SetInt64(y2)) + numer.Mul(numer, tmp1.SetInt64(k)) + denom.Mul(denom, tmp1.SetInt64(y2)) +} + +func eliminateDigit(d int64) { + accum.Sub(accum, tmp1.Mul(denom, tmp1.SetInt64(d))) + accum.Mul(accum, ten) + numer.Mul(numer, ten) +} + +func main() { + i := 0 + k := int64(0) + for { + d := int64(-1) + for d < 0 { + k++ + nextTerm(k) + d = extractDigit() + } + eliminateDigit(d) + fmt.Printf("%c", d+'0') + + if i++; i%50 == 0 { + fmt.Printf("\n") + if i >= 1000 { + break + } + } + } + + fmt.Printf("\n%d calls; bit sizes: %d %d %d\n", runtime.NumCgoCall(), numer.Len(), accum.Len(), denom.Len()) +} -- cgit v1.2.3