3 files changed, 498 insertions, 0 deletions
diff --git a/misc/cgo/gmp/fib.go b/misc/cgo/gmp/fib.go
new file mode 100644
index 0000000..f1091b1
--- /dev/null
+++ b/misc/cgo/gmp/fib.go
@@ -0,0 +1,45 @@
+// 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.
+
+// +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 <gmp.h>
+	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 <gmp.h> 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 <gmp.h>
+#include <stdlib.h>
+
+// 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..d5851e8
--- /dev/null
+++ b/misc/cgo/gmp/pi.go
@@ -0,0 +1,73 @@
+// 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.
+
+// +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())
+}