/*	$OpenBSD: __divqu.S,v 1.1 2007/11/25 18:25:34 deraadt Exp $	*/
/*	$NetBSD: divrem.m4,v 1.5 1996/10/17 04:26:25 cgd Exp $	*/

/*
 * Copyright (c) 1994, 1995 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Author: Chris G. Demetriou
 * 
 * Permission to use, copy, modify and distribute this software and
 * its documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 * 
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 
 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 * 
 * Carnegie Mellon requests users of this software to return to
 *
 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 *
 * any improvements or extensions that they make and grant Carnegie the
 * rights to redistribute these changes.
 */

/*
 * Division and remainder.
 *
 * The use of m4 is modeled after the sparc code, but the algorithm is
 * simple binary long division.
 *
 * Note that the loops could probably benefit from unrolling.
 */

/*
 * M4 Parameters
 * __divqu		name of function to generate
 * div		div=div: t10 / t11 -> t12; div=rem: t10 % t11 -> t12
 * false		false=true: signed; false=false: unsigned
 * 64	total number of bits
 */











#include <machine/asm.h>

LEAF(__divqu, 0)					/* XXX */
	lda	sp, -64(sp)
	stq	t0, 0(sp)
	stq	t1, 8(sp)
	stq	t2, 16(sp)
	stq	t3, 24(sp)

	stq	t10, 40(sp)
	stq	t11, 48(sp)
	mov	zero, t12			/* Initialize result to zero */




	/* kill the special cases. */
	beq	t11, Ldotrap			/* division by zero! */

	cmpult	t10, t11, t2			/* t10 < t11? */
	/* t12 is already zero, from above.  t10 is untouched. */
	bne	t2, Lret_result

	cmpeq	t10, t11, t2			/* t10 == t11? */
	cmovne	t2, 1, t12
	cmovne	t2, zero, t10
	bne	t2, Lret_result

	/*
	 * Find out how many bits of zeros are at the beginning of the divisor.
	 */
LBbits:
	ldiq	t3, 1				/* t1 = 0; t0 = 1<<64-1 */
	mov	zero, t1
	sll	t3, 64-1, t0
LBloop:
	and	t11, t0, t2			/* if bit in t11 is set, done. */
	bne	t2, LAbits
	addq	t1, 1, t1				/* increment t1,  bit */
	srl	t0, 1, t0
	cmplt	t1, 64-1, t2		/* if t1 leaves one bit, done. */
	bne	t2, LBloop

LAbits:
	beq	t1, Ldodiv			/* If t1 = 0, divide now.  */
	ldiq	t3, 1				/* t0 = 1<<64-1 */
	sll	t3, 64-1, t0

LAloop:
	and	t10, t0, t2			/* if bit in t10 is set, done. */
	bne	t2, Ldodiv
	subq	t1, 1, t1				/* decrement t1,  bit */
	srl     t0, 1, t0 
	bne	t1, LAloop			/* If t1 != 0, loop again */

Ldodiv:
	sll	t11, t1, t11				/* t11 <<= i */
	ldiq	t3, 1
	sll	t3, t1, t0

Ldivloop:
	cmpult	t10, t11, t2
	or	t12, t0, t3
	cmoveq	t2, t3, t12
	subq	t10, t11, t3
	cmoveq	t2, t3, t10
	srl	t0, 1, t0	
	srl	t11, 1, t11
	beq	t10, Lret_result
	bne	t0, Ldivloop

Lret_result:



	ldq	t0, 0(sp)
	ldq	t1, 8(sp)
	ldq	t2, 16(sp)
	ldq	t3, 24(sp)

	ldq	t10, 40(sp)
	ldq	t11, 48(sp)
	lda	sp, 64(sp)
	ret	zero, (t9), 1

Ldotrap:
	ldiq	a0, -2			/* This is the signal to SIGFPE! */
	call_pal PAL_gentrap

	br	zero, Lret_result

END(__divqu)