Source file misc/cgo/gmp/gmp.go

     1  // 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  /*
     6  An example of wrapping a C library in Go. This is the GNU
     7  multiprecision library gmp's integer type mpz_t wrapped to look like
     8  the Go package big's integer type Int.
     9  
    10  This is a syntactically valid Go program—it can be parsed with the Go
    11  parser and processed by godoc—but it is not compiled directly by gc.
    12  Instead, a separate tool, cgo, processes it to produce three output
    13  files.  The first two, 6g.go and 6c.c, are a Go source file for 6g and
    14  a C source file for 6c; both compile as part of the named package
    15  (gmp, in this example).  The third, gcc.c, is a C source file for gcc;
    16  it compiles into a shared object (.so) that is dynamically linked into
    17  any 6.out that imports the first two files.
    18  
    19  The stanza
    20  
    21  	// #include <gmp.h>
    22  	import "C"
    23  
    24  is a signal to cgo.  The doc comment on the import of "C" provides
    25  additional context for the C file.  Here it is just a single #include
    26  but it could contain arbitrary C definitions to be imported and used.
    27  
    28  Cgo recognizes any use of a qualified identifier C.xxx and uses gcc to
    29  find the definition of xxx.  If xxx is a type, cgo replaces C.xxx with
    30  a Go translation.  C arithmetic types translate to precisely-sized Go
    31  arithmetic types.  A C struct translates to a Go struct, field by
    32  field; unrepresentable fields are replaced with opaque byte arrays.  A
    33  C union translates into a struct containing the first union member and
    34  perhaps additional padding.  C arrays become Go arrays.  C pointers
    35  become Go pointers.  C function pointers become Go's uintptr.
    36  C void pointers become Go's unsafe.Pointer.
    37  
    38  For example, mpz_t is defined in <gmp.h> as:
    39  
    40  	typedef unsigned long int mp_limb_t;
    41  
    42  	typedef struct
    43  	{
    44  		int _mp_alloc;
    45  		int _mp_size;
    46  		mp_limb_t *_mp_d;
    47  	} __mpz_struct;
    48  
    49  	typedef __mpz_struct mpz_t[1];
    50  
    51  Cgo generates:
    52  
    53  	type _C_int int32
    54  	type _C_mp_limb_t uint64
    55  	type _C___mpz_struct struct {
    56  		_mp_alloc _C_int;
    57  		_mp_size _C_int;
    58  		_mp_d *_C_mp_limb_t;
    59  	}
    60  	type _C_mpz_t [1]_C___mpz_struct
    61  
    62  and then replaces each occurrence of a type C.xxx with _C_xxx.
    63  
    64  If xxx is data, cgo arranges for C.xxx to refer to the C variable,
    65  with the type translated as described above.  To do this, cgo must
    66  introduce a Go variable that points at the C variable (the linker can
    67  be told to initialize this pointer).  For example, if the gmp library
    68  provided
    69  
    70  	mpz_t zero;
    71  
    72  then cgo would rewrite a reference to C.zero by introducing
    73  
    74  	var _C_zero *C.mpz_t
    75  
    76  and then replacing all instances of C.zero with (*_C_zero).
    77  
    78  Cgo's most interesting translation is for functions.  If xxx is a C
    79  function, then cgo rewrites C.xxx into a new function _C_xxx that
    80  calls the C xxx in a standard pthread.  The new function translates
    81  its arguments, calls xxx, and translates the return value.
    82  
    83  Translation of parameters and the return value follows the type
    84  translation above except that arrays passed as parameters translate
    85  explicitly in Go to pointers to arrays, as they do (implicitly) in C.
    86  
    87  Garbage collection is the big problem.  It is fine for the Go world to
    88  have pointers into the C world and to free those pointers when they
    89  are no longer needed.  To help, the Go code can define Go objects
    90  holding the C pointers and use runtime.SetFinalizer on those Go objects.
    91  
    92  It is much more difficult for the C world to have pointers into the Go
    93  world, because the Go garbage collector is unaware of the memory
    94  allocated by C.  The most important consideration is not to
    95  constrain future implementations, so the rule is that Go code can
    96  hand a Go pointer to C code but must separately arrange for
    97  Go to hang on to a reference to the pointer until C is done with it.
    98  */
    99  package gmp
   100  
   101  /*
   102  #cgo LDFLAGS: -lgmp
   103  #include <gmp.h>
   104  #include <stdlib.h>
   105  
   106  // gmp 5.0.0+ changed the type of the 3rd argument to mp_bitcnt_t,
   107  // so, to support older versions, we wrap these two functions.
   108  void _mpz_mul_2exp(mpz_ptr a, mpz_ptr b, unsigned long n) {
   109  	mpz_mul_2exp(a, b, n);
   110  }
   111  void _mpz_div_2exp(mpz_ptr a, mpz_ptr b, unsigned long n) {
   112  	mpz_div_2exp(a, b, n);
   113  }
   114  */
   115  import "C"
   116  
   117  import (
   118  	"os"
   119  	"unsafe"
   120  )
   121  
   122  /*
   123   * one of a kind
   124   */
   125  
   126  // An Int represents a signed multi-precision integer.
   127  // The zero value for an Int represents the value 0.
   128  type Int struct {
   129  	i    C.mpz_t
   130  	init bool
   131  }
   132  
   133  // NewInt returns a new Int initialized to x.
   134  func NewInt(x int64) *Int { return new(Int).SetInt64(x) }
   135  
   136  // Int promises that the zero value is a 0, but in gmp
   137  // the zero value is a crash.  To bridge the gap, the
   138  // init bool says whether this is a valid gmp value.
   139  // doinit initializes z.i if it needs it.  This is not inherent
   140  // to FFI, just a mismatch between Go's convention of
   141  // making zero values useful and gmp's decision not to.
   142  func (z *Int) doinit() {
   143  	if z.init {
   144  		return
   145  	}
   146  	z.init = true
   147  	C.mpz_init(&z.i[0])
   148  }
   149  
   150  // Bytes returns z's representation as a big-endian byte array.
   151  func (z *Int) Bytes() []byte {
   152  	b := make([]byte, (z.Len()+7)/8)
   153  	n := C.size_t(len(b))
   154  	C.mpz_export(unsafe.Pointer(&b[0]), &n, 1, 1, 1, 0, &z.i[0])
   155  	return b[0:n]
   156  }
   157  
   158  // Len returns the length of z in bits.  0 is considered to have length 1.
   159  func (z *Int) Len() int {
   160  	z.doinit()
   161  	return int(C.mpz_sizeinbase(&z.i[0], 2))
   162  }
   163  
   164  // Set sets z = x and returns z.
   165  func (z *Int) Set(x *Int) *Int {
   166  	z.doinit()
   167  	C.mpz_set(&z.i[0], &x.i[0])
   168  	return z
   169  }
   170  
   171  // SetBytes interprets b as the bytes of a big-endian integer
   172  // and sets z to that value.
   173  func (z *Int) SetBytes(b []byte) *Int {
   174  	z.doinit()
   175  	if len(b) == 0 {
   176  		z.SetInt64(0)
   177  	} else {
   178  		C.mpz_import(&z.i[0], C.size_t(len(b)), 1, 1, 1, 0, unsafe.Pointer(&b[0]))
   179  	}
   180  	return z
   181  }
   182  
   183  // SetInt64 sets z = x and returns z.
   184  func (z *Int) SetInt64(x int64) *Int {
   185  	z.doinit()
   186  	// TODO(rsc): more work on 32-bit platforms
   187  	C.mpz_set_si(&z.i[0], C.long(x))
   188  	return z
   189  }
   190  
   191  // SetString interprets s as a number in the given base
   192  // and sets z to that value.  The base must be in the range [2,36].
   193  // SetString returns an error if s cannot be parsed or the base is invalid.
   194  func (z *Int) SetString(s string, base int) error {
   195  	z.doinit()
   196  	if base < 2 || base > 36 {
   197  		return os.ErrInvalid
   198  	}
   199  	p := C.CString(s)
   200  	defer C.free(unsafe.Pointer(p))
   201  	if C.mpz_set_str(&z.i[0], p, C.int(base)) < 0 {
   202  		return os.ErrInvalid
   203  	}
   204  	return nil
   205  }
   206  
   207  // String returns the decimal representation of z.
   208  func (z *Int) String() string {
   209  	if z == nil {
   210  		return "nil"
   211  	}
   212  	z.doinit()
   213  	p := C.mpz_get_str(nil, 10, &z.i[0])
   214  	s := C.GoString(p)
   215  	C.free(unsafe.Pointer(p))
   216  	return s
   217  }
   218  
   219  func (z *Int) destroy() {
   220  	if z.init {
   221  		C.mpz_clear(&z.i[0])
   222  	}
   223  	z.init = false
   224  }
   225  
   226  /*
   227   * arithmetic
   228   */
   229  
   230  // Add sets z = x + y and returns z.
   231  func (z *Int) Add(x, y *Int) *Int {
   232  	x.doinit()
   233  	y.doinit()
   234  	z.doinit()
   235  	C.mpz_add(&z.i[0], &x.i[0], &y.i[0])
   236  	return z
   237  }
   238  
   239  // Sub sets z = x - y and returns z.
   240  func (z *Int) Sub(x, y *Int) *Int {
   241  	x.doinit()
   242  	y.doinit()
   243  	z.doinit()
   244  	C.mpz_sub(&z.i[0], &x.i[0], &y.i[0])
   245  	return z
   246  }
   247  
   248  // Mul sets z = x * y and returns z.
   249  func (z *Int) Mul(x, y *Int) *Int {
   250  	x.doinit()
   251  	y.doinit()
   252  	z.doinit()
   253  	C.mpz_mul(&z.i[0], &x.i[0], &y.i[0])
   254  	return z
   255  }
   256  
   257  // Div sets z = x / y, rounding toward zero, and returns z.
   258  func (z *Int) Div(x, y *Int) *Int {
   259  	x.doinit()
   260  	y.doinit()
   261  	z.doinit()
   262  	C.mpz_tdiv_q(&z.i[0], &x.i[0], &y.i[0])
   263  	return z
   264  }
   265  
   266  // Mod sets z = x % y and returns z.
   267  // Like the result of the Go % operator, z has the same sign as x.
   268  func (z *Int) Mod(x, y *Int) *Int {
   269  	x.doinit()
   270  	y.doinit()
   271  	z.doinit()
   272  	C.mpz_tdiv_r(&z.i[0], &x.i[0], &y.i[0])
   273  	return z
   274  }
   275  
   276  // Lsh sets z = x << s and returns z.
   277  func (z *Int) Lsh(x *Int, s uint) *Int {
   278  	x.doinit()
   279  	z.doinit()
   280  	C._mpz_mul_2exp(&z.i[0], &x.i[0], C.ulong(s))
   281  	return z
   282  }
   283  
   284  // Rsh sets z = x >> s and returns z.
   285  func (z *Int) Rsh(x *Int, s uint) *Int {
   286  	x.doinit()
   287  	z.doinit()
   288  	C._mpz_div_2exp(&z.i[0], &x.i[0], C.ulong(s))
   289  	return z
   290  }
   291  
   292  // Exp sets z = x^y % m and returns z.
   293  // If m == nil, Exp sets z = x^y.
   294  func (z *Int) Exp(x, y, m *Int) *Int {
   295  	m.doinit()
   296  	x.doinit()
   297  	y.doinit()
   298  	z.doinit()
   299  	if m == nil {
   300  		C.mpz_pow_ui(&z.i[0], &x.i[0], C.mpz_get_ui(&y.i[0]))
   301  	} else {
   302  		C.mpz_powm(&z.i[0], &x.i[0], &y.i[0], &m.i[0])
   303  	}
   304  	return z
   305  }
   306  
   307  func (z *Int) Int64() int64 {
   308  	if !z.init {
   309  		return 0
   310  	}
   311  	return int64(C.mpz_get_si(&z.i[0]))
   312  }
   313  
   314  // Neg sets z = -x and returns z.
   315  func (z *Int) Neg(x *Int) *Int {
   316  	x.doinit()
   317  	z.doinit()
   318  	C.mpz_neg(&z.i[0], &x.i[0])
   319  	return z
   320  }
   321  
   322  // Abs sets z to the absolute value of x and returns z.
   323  func (z *Int) Abs(x *Int) *Int {
   324  	x.doinit()
   325  	z.doinit()
   326  	C.mpz_abs(&z.i[0], &x.i[0])
   327  	return z
   328  }
   329  
   330  /*
   331   * functions without a clear receiver
   332   */
   333  
   334  // CmpInt compares x and y. The result is
   335  //
   336  //	-1 if x <  y
   337  //	 0 if x == y
   338  //	+1 if x >  y
   339  func CmpInt(x, y *Int) int {
   340  	x.doinit()
   341  	y.doinit()
   342  	switch cmp := C.mpz_cmp(&x.i[0], &y.i[0]); {
   343  	case cmp < 0:
   344  		return -1
   345  	case cmp == 0:
   346  		return 0
   347  	}
   348  	return +1
   349  }
   350  
   351  // DivModInt sets q = x / y and r = x % y.
   352  func DivModInt(q, r, x, y *Int) {
   353  	q.doinit()
   354  	r.doinit()
   355  	x.doinit()
   356  	y.doinit()
   357  	C.mpz_tdiv_qr(&q.i[0], &r.i[0], &x.i[0], &y.i[0])
   358  }
   359  
   360  // GcdInt sets d to the greatest common divisor of a and b,
   361  // which must be positive numbers.
   362  // If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y.
   363  // If either a or b is not positive, GcdInt sets d = x = y = 0.
   364  func GcdInt(d, x, y, a, b *Int) {
   365  	d.doinit()
   366  	x.doinit()
   367  	y.doinit()
   368  	a.doinit()
   369  	b.doinit()
   370  	C.mpz_gcdext(&d.i[0], &x.i[0], &y.i[0], &a.i[0], &b.i[0])
   371  }
   372  
   373  // ProbablyPrime performs n Miller-Rabin tests to check whether z is prime.
   374  // If it returns true, z is prime with probability 1 - 1/4^n.
   375  // If it returns false, z is not prime.
   376  func (z *Int) ProbablyPrime(n int) bool {
   377  	z.doinit()
   378  	return int(C.mpz_probab_prime_p(&z.i[0], C.int(n))) > 0
   379  }
   380  

View as plain text