// 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.

package gc

//
// return the significant
// words of the argument
//
func mplen(a *Mpint) int {
	n := -1
	for i := 0; i < Mpprec; i++ {
		if a.A[i] != 0 {
			n = i
		}
	}

	return n + 1
}

//
// left shift mpint by one
// ignores sign
//
func mplsh(a *Mpint, quiet int) {
	var x int

	c := 0
	for i := 0; i < Mpprec; i++ {
		x = (a.A[i] << 1) + c
		c = 0
		if x >= Mpbase {
			x -= Mpbase
			c = 1
		}

		a.A[i] = x
	}

	a.Ovf = uint8(c)
	if a.Ovf != 0 && quiet == 0 {
		Yyerror("constant shift overflow")
	}
}

//
// left shift mpint by Mpscale
// ignores sign
//
func mplshw(a *Mpint, quiet int) {
	i := Mpprec - 1
	if a.A[i] != 0 {
		a.Ovf = 1
		if quiet == 0 {
			Yyerror("constant shift overflow")
		}
	}

	for ; i > 0; i-- {
		a.A[i] = a.A[i-1]
	}
	a.A[i] = 0
}

//
// right shift mpint by one
// ignores sign and overflow
//
func mprsh(a *Mpint) {
	var x int

	c := 0
	lo := a.A[0] & 1
	for i := Mpprec - 1; i >= 0; i-- {
		x = a.A[i]
		a.A[i] = (x + c) >> 1
		c = 0
		if x&1 != 0 {
			c = Mpbase
		}
	}

	if a.Neg != 0 && lo != 0 {
		mpaddcfix(a, -1)
	}
}

//
// right shift mpint by Mpscale
// ignores sign and overflow
//
func mprshw(a *Mpint) {
	var i int

	lo := a.A[0]
	for i = 0; i < Mpprec-1; i++ {
		a.A[i] = a.A[i+1]
	}

	a.A[i] = 0
	if a.Neg != 0 && lo != 0 {
		mpaddcfix(a, -1)
	}
}

//
// return the sign of (abs(a)-abs(b))
//
func mpcmp(a *Mpint, b *Mpint) int {
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in cmp")
		}
		return 0
	}

	var x int
	for i := Mpprec - 1; i >= 0; i-- {
		x = a.A[i] - b.A[i]
		if x > 0 {
			return +1
		}
		if x < 0 {
			return -1
		}
	}

	return 0
}

//
// negate a
// ignore sign and ovf
//
func mpneg(a *Mpint) {
	var x int

	c := 0
	for i := 0; i < Mpprec; i++ {
		x = -a.A[i] - c
		c = 0
		if x < 0 {
			x += Mpbase
			c = 1
		}

		a.A[i] = x
	}
}

// shift left by s (or right by -s)
func Mpshiftfix(a *Mpint, s int) {
	if s >= 0 {
		for s >= Mpscale {
			mplshw(a, 0)
			s -= Mpscale
		}

		for s > 0 {
			mplsh(a, 0)
			s--
		}
	} else {
		s = -s
		for s >= Mpscale {
			mprshw(a)
			s -= Mpscale
		}

		for s > 0 {
			mprsh(a)
			s--
		}
	}
}

/// implements fix arihmetic

func mpaddfixfix(a *Mpint, b *Mpint, quiet int) {
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mpaddxx")
		}
		a.Ovf = 1
		return
	}

	c := 0
	var x int
	if a.Neg != b.Neg {
		goto sub
	}

	// perform a+b
	for i := 0; i < Mpprec; i++ {
		x = a.A[i] + b.A[i] + c
		c = 0
		if x >= Mpbase {
			x -= Mpbase
			c = 1
		}

		a.A[i] = x
	}

	a.Ovf = uint8(c)
	if a.Ovf != 0 && quiet == 0 {
		Yyerror("constant addition overflow")
	}

	return

	// perform a-b
sub:
	switch mpcmp(a, b) {
	case 0:
		Mpmovecfix(a, 0)

	case 1:
		var x int
		for i := 0; i < Mpprec; i++ {
			x = a.A[i] - b.A[i] - c
			c = 0
			if x < 0 {
				x += Mpbase
				c = 1
			}

			a.A[i] = x
		}

	case -1:
		a.Neg ^= 1
		var x int
		for i := 0; i < Mpprec; i++ {
			x = b.A[i] - a.A[i] - c
			c = 0
			if x < 0 {
				x += Mpbase
				c = 1
			}

			a.A[i] = x
		}
	}
}

func mpmulfixfix(a *Mpint, b *Mpint) {
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mpmulfixfix")
		}
		a.Ovf = 1
		return
	}

	// pick the smaller
	// to test for bits
	na := mplen(a)

	nb := mplen(b)
	var s Mpint
	var c *Mpint
	if na > nb {
		mpmovefixfix(&s, a)
		c = b
		na = nb
	} else {
		mpmovefixfix(&s, b)
		c = a
	}

	s.Neg = 0

	var q Mpint
	Mpmovecfix(&q, 0)
	var j int
	var x int
	for i := 0; i < na; i++ {
		x = c.A[i]
		for j = 0; j < Mpscale; j++ {
			if x&1 != 0 {
				if s.Ovf != 0 {
					q.Ovf = 1
					goto out
				}

				mpaddfixfix(&q, &s, 1)
				if q.Ovf != 0 {
					goto out
				}
			}

			mplsh(&s, 1)
			x >>= 1
		}
	}

out:
	q.Neg = a.Neg ^ b.Neg
	mpmovefixfix(a, &q)
	if a.Ovf != 0 {
		Yyerror("constant multiplication overflow")
	}
}

func mpmulfract(a *Mpint, b *Mpint) {
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mpmulflt")
		}
		a.Ovf = 1
		return
	}

	var s Mpint
	mpmovefixfix(&s, b)
	s.Neg = 0
	var q Mpint
	Mpmovecfix(&q, 0)

	i := Mpprec - 1
	x := a.A[i]
	if x != 0 {
		Yyerror("mpmulfract not normal")
	}

	var j int
	for i--; i >= 0; i-- {
		x = a.A[i]
		if x == 0 {
			mprshw(&s)
			continue
		}

		for j = 0; j < Mpscale; j++ {
			x <<= 1
			if x&Mpbase != 0 {
				mpaddfixfix(&q, &s, 1)
			}
			mprsh(&s)
		}
	}

	q.Neg = a.Neg ^ b.Neg
	mpmovefixfix(a, &q)
	if a.Ovf != 0 {
		Yyerror("constant multiplication overflow")
	}
}

func mporfixfix(a *Mpint, b *Mpint) {
	x := 0
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mporfixfix")
		}
		Mpmovecfix(a, 0)
		a.Ovf = 1
		return
	}

	if a.Neg != 0 {
		a.Neg = 0
		mpneg(a)
	}

	if b.Neg != 0 {
		mpneg(b)
	}

	for i := 0; i < Mpprec; i++ {
		x = a.A[i] | b.A[i]
		a.A[i] = x
	}

	if b.Neg != 0 {
		mpneg(b)
	}
	if x&Mpsign != 0 {
		a.Neg = 1
		mpneg(a)
	}
}

func mpandfixfix(a *Mpint, b *Mpint) {
	x := 0
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mpandfixfix")
		}
		Mpmovecfix(a, 0)
		a.Ovf = 1
		return
	}

	if a.Neg != 0 {
		a.Neg = 0
		mpneg(a)
	}

	if b.Neg != 0 {
		mpneg(b)
	}

	for i := 0; i < Mpprec; i++ {
		x = a.A[i] & b.A[i]
		a.A[i] = x
	}

	if b.Neg != 0 {
		mpneg(b)
	}
	if x&Mpsign != 0 {
		a.Neg = 1
		mpneg(a)
	}
}

func mpandnotfixfix(a *Mpint, b *Mpint) {
	x := 0
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mpandnotfixfix")
		}
		Mpmovecfix(a, 0)
		a.Ovf = 1
		return
	}

	if a.Neg != 0 {
		a.Neg = 0
		mpneg(a)
	}

	if b.Neg != 0 {
		mpneg(b)
	}

	for i := 0; i < Mpprec; i++ {
		x = a.A[i] &^ b.A[i]
		a.A[i] = x
	}

	if b.Neg != 0 {
		mpneg(b)
	}
	if x&Mpsign != 0 {
		a.Neg = 1
		mpneg(a)
	}
}

func mpxorfixfix(a *Mpint, b *Mpint) {
	x := 0
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mporfixfix")
		}
		Mpmovecfix(a, 0)
		a.Ovf = 1
		return
	}

	if a.Neg != 0 {
		a.Neg = 0
		mpneg(a)
	}

	if b.Neg != 0 {
		mpneg(b)
	}

	for i := 0; i < Mpprec; i++ {
		x = a.A[i] ^ b.A[i]
		a.A[i] = x
	}

	if b.Neg != 0 {
		mpneg(b)
	}
	if x&Mpsign != 0 {
		a.Neg = 1
		mpneg(a)
	}
}

func mplshfixfix(a *Mpint, b *Mpint) {
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mporfixfix")
		}
		Mpmovecfix(a, 0)
		a.Ovf = 1
		return
	}

	s := Mpgetfix(b)
	if s < 0 || s >= Mpprec*Mpscale {
		Yyerror("stupid shift: %d", s)
		Mpmovecfix(a, 0)
		return
	}

	Mpshiftfix(a, int(s))
}

func mprshfixfix(a *Mpint, b *Mpint) {
	if a.Ovf != 0 || b.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("ovf in mprshfixfix")
		}
		Mpmovecfix(a, 0)
		a.Ovf = 1
		return
	}

	s := Mpgetfix(b)
	if s < 0 || s >= Mpprec*Mpscale {
		Yyerror("stupid shift: %d", s)
		if a.Neg != 0 {
			Mpmovecfix(a, -1)
		} else {
			Mpmovecfix(a, 0)
		}
		return
	}

	Mpshiftfix(a, int(-s))
}

func mpnegfix(a *Mpint) {
	a.Neg ^= 1
}

func Mpgetfix(a *Mpint) int64 {
	if a.Ovf != 0 {
		if nsavederrors+nerrors == 0 {
			Yyerror("constant overflow")
		}
		return 0
	}

	v := int64(uint64(a.A[0]))
	v |= int64(uint64(a.A[1]) << Mpscale)
	v |= int64(uint64(a.A[2]) << (Mpscale + Mpscale))
	if a.Neg != 0 {
		v = int64(-uint64(v))
	}
	return v
}

func Mpmovecfix(a *Mpint, c int64) {
	a.Neg = 0
	a.Ovf = 0

	x := c
	if x < 0 {
		a.Neg = 1
		x = int64(-uint64(x))
	}

	for i := 0; i < Mpprec; i++ {
		a.A[i] = int(x & Mpmask)
		x >>= Mpscale
	}
}

func mpdivmodfixfix(q *Mpint, r *Mpint, n *Mpint, d *Mpint) {
	var i int

	ns := int(n.Neg)
	ds := int(d.Neg)
	n.Neg = 0
	d.Neg = 0

	mpmovefixfix(r, n)
	Mpmovecfix(q, 0)

	// shift denominator until it
	// is larger than numerator
	for i = 0; i < Mpprec*Mpscale; i++ {
		if mpcmp(d, r) > 0 {
			break
		}
		mplsh(d, 1)
	}

	// if it never happens
	// denominator is probably zero
	if i >= Mpprec*Mpscale {
		q.Ovf = 1
		r.Ovf = 1
		n.Neg = uint8(ns)
		d.Neg = uint8(ds)
		Yyerror("constant division overflow")
		return
	}

	// shift denominator back creating
	// quotient a bit at a time
	// when done the remaining numerator
	// will be the remainder
	for ; i > 0; i-- {
		mplsh(q, 1)
		mprsh(d)
		if mpcmp(d, r) <= 0 {
			mpaddcfix(q, 1)
			mpsubfixfix(r, d)
		}
	}

	n.Neg = uint8(ns)
	d.Neg = uint8(ds)
	r.Neg = uint8(ns)
	q.Neg = uint8(ns ^ ds)
}

func mpiszero(a *Mpint) bool {
	for i := Mpprec - 1; i >= 0; i-- {
		if a.A[i] != 0 {
			return false
		}
	}
	return true
}

func mpdivfract(a *Mpint, b *Mpint) {
	var n Mpint
	var d Mpint
	var j int
	var x int

	mpmovefixfix(&n, a) // numerator
	mpmovefixfix(&d, b) // denominator

	neg := int(n.Neg) ^ int(d.Neg)

	n.Neg = 0
	d.Neg = 0
	for i := Mpprec - 1; i >= 0; i-- {
		x = 0
		for j = 0; j < Mpscale; j++ {
			x <<= 1
			if mpcmp(&d, &n) <= 0 {
				if !mpiszero(&d) {
					x |= 1
				}
				mpsubfixfix(&n, &d)
			}

			mprsh(&d)
		}

		a.A[i] = x
	}

	a.Neg = uint8(neg)
}

func mptestfix(a *Mpint) int {
	var b Mpint

	Mpmovecfix(&b, 0)
	r := mpcmp(a, &b)
	if a.Neg != 0 {
		if r > 0 {
			return -1
		}
		if r < 0 {
			return +1
		}
	}

	return r
}