gno.land/p/gnoswap/int256/v1⧉

1package int25623import "math/bits"45func udivrem(quot, u []uint64, d *Int) (rem Int) {6	var dLen int7	for i := len(d) - 1; i >= 0; i-- {8		if d[i] != 0 {9			dLen = i + 110			break11		}12	}1314	shift := uint(bits.LeadingZeros64(d[dLen-1]))1516	var dnStorage Int17	dn := dnStorage[:dLen]18	for i := dLen - 1; i > 0; i-- {19		dn[i] = (d[i] << shift) | (d[i-1] >> (64 - shift))20	}21	dn[0] = d[0] << shift2223	var uLen int24	for i := len(u) - 1; i >= 0; i-- {25		if u[i] != 0 {26			uLen = i + 127			break28		}29	}3031	if uLen < dLen {32		copy(rem[:], u)33		return rem34	}3536	var unStorage [9]uint6437	un := unStorage[:uLen+1]38	un[uLen] = u[uLen-1] >> (64 - shift)39	for i := uLen - 1; i > 0; i-- {40		un[i] = (u[i] << shift) | (u[i-1] >> (64 - shift))41	}42	un[0] = u[0] << shift4344	if dLen == 1 {45		r := udivremBy1(quot, un, dn[0])46		rem.SetUint64(r >> shift)47		return rem48	}4950	udivremKnuth(quot, un, dn)5152	for i := 0; i < dLen-1; i++ {53		rem[i] = (un[i] >> shift) | (un[i+1] << (64 - shift))54	}55	rem[dLen-1] = un[dLen-1] >> shift5657	return rem58}5960func udivremBy1(quot, u []uint64, d uint64) (rem uint64) {61	reciprocal := reciprocal2by1(d)62	rem = u[len(u)-1]63	for j := len(u) - 2; j >= 0; j-- {64		quot[j], rem = udivrem2by1(rem, u[j], d, reciprocal)65	}66	return rem67}6869func udivremKnuth(quot, u, d []uint64) {70	dLen := len(d)71	dh := d[dLen-1]72	dl := d[dLen-2]73	reciprocal := reciprocal2by1(dh)7475	for j := len(u) - dLen - 1; j >= 0; j-- {76		u2 := u[j+dLen]77		u1 := u[j+dLen-1]78		u0 := u[j+dLen-2]7980		var qhat, rhat uint6481		if u2 >= dh {82			qhat = ^uint64(0)83		} else {84			qhat, rhat = udivrem2by1(u2, u1, dh, reciprocal)85			ph, pl := bits.Mul64(qhat, dl)86			if ph > rhat || (ph == rhat && pl > u0) {87				qhat--88			}89		}9091		borrow := subMulTo(u[j:], d, qhat)92		u[j+dLen] = u2 - borrow93		if u2 < borrow {94			qhat--95			u[j+dLen] += addTo(u[j:], d)96		}9798		quot[j] = qhat99	}100}101102func reciprocal2by1(d uint64) uint64 {103	reciprocal, _ := bits.Div64(^d, ^uint64(0), d)104	return reciprocal105}106107func udivrem2by1(uh, ul, d, reciprocal uint64) (quot, rem uint64) {108	qh, ql := bits.Mul64(reciprocal, uh)109	ql, carry := bits.Add64(ql, ul, 0)110	qh += uh + carry111	qh++112113	r := ul - qh*d114115	if r > ql {116		qh--117		r += d118	}119120	if r >= d {121		qh++122		r -= d123	}124125	return qh, r126}127128func subMulTo(x, y []uint64, multiplier uint64) uint64 {129	var borrow uint64130	for i := 0; i < len(y); i++ {131		s, carry1 := bits.Sub64(x[i], borrow, 0)132		ph, pl := bits.Mul64(y[i], multiplier)133		t, carry2 := bits.Sub64(s, pl, 0)134		x[i] = t135		borrow = ph + carry1 + carry2136	}137	return borrow138}139140func addTo(x, y []uint64) uint64 {141	var carry uint64142	for i := 0; i < len(y); i++ {143		x[i], carry = bits.Add64(x[i], y[i], carry)144	}145	return carry146}147