org	$3000

START

main:	move.w	#987,d0		; compute 987 * $8123
	move.w	#$8123,d1
	jsr	_mulu

	move.l	d0,d1		; print result
	move.l	#3,d0
	trap	#15

	move.b	#9,d0		; exit
	trap	#15

*******************************************************************************
* Computes (d0.l) := (d0.w) * (d1.w) using bits ops and addition.
*
* The algorithm is the one that we all know from elementary school for doing
* "long" multiplication.
*******************************************************************************
_mulu:	movem.l	d2-d4,-(sp)	; save d2.w, d3.w

	andi.l	#$FFFF,d0	; multiplier is in bottom word of d0
	beq	done		; if multiplier is 0, then product is 0
	lsl.l	#8,d1		; put multiplicand in upper word of d1
	lsl.l	#8,d1

	move.w	d0,d2		; compute floor(lg (d0)) to compute
	jsr	flg		;   necessary number of loop iterations
	andi.w	#$FF,d2		; clear second byte since dbf acts on word
	move.b	#15,d3
	sub.b	d2,d3		; d3 holds final number of shifts

loop	btst	#0,d0		; do long multiplication
	beq	shift		; nothing to add if bit is 0
	clr.l	d4		; UPDATE after 9/11 lecture:
	add.l	d1,d0		;   Pierce pointed out that we need to hold
	bcc	shift		;   onto the carry bit.  So if it's set,
	move.l	#$80000000,d4   ;   prepare to OR it into d0 after the shift.
shift	lsr.l	#1,d0
	or.l	d4,d0		; OR in the carry bit.
	dbf	d2,loop
	lsr.l	d3,d0		; final set of shifts

done	movem.l	(sp)+,d2-d4	; restore d2.w, d3.w
	rts


*******************************************************************************
* The function "flg," short for "floor of log-base-2," implements the following
* algorithm for finding the highest 1-bit in a 16-bit input.  The goal is to
* find the highest 1-bit in a lot fewer steps (in fact, a logarithmic number of
* steps) than a linear search through the 16 bits would take.
* 
* static unsigned short masks[] = {0x2, 0xC, 0xF0, 0xFF00};
* static unsigned char pow2[] = {1, 2, 4, 8};
* unsigned char floor_lg(unsigned short v) {
*   unsigned char r = 0;
*   int i;
*   for(i = 3; i >= 0; --i)
*     if (v & masks[i]) {
*       v >>= pow2[i];
*       r |= pow2[i];     // same effect as r += pow2[i]
*     }
*   return r;
* }
*
* For example, suppose v = 0000 0010 1101 0111.  Then
*
* i = 3: v & 0xFF00 is non-0, so
*   v becomes 0000 0010
*   r becomes 1000 in binary, or 8 in decimal
* i = 2: v & 0xF0 is 0, so nothing happens
* i = 1: v & 0xC is 0, so nothing happens
* i = 0: v & 0x2 is non-0, so
*   v becomes 0000 0001
*   r becomes 1001 in binary, or 9 in decimal
* So 9 is returned.
*
* And, indeed, the 9th bit of the input is the highest 1-bit.
*
* Input in (d2.w), output in (d2.b).
*******************************************************************************
flg:	andi.l	#$FFFF,d2	; clear upper word to hold result
	move.w	d2,d3
	andi.w	#$FF00,d3	; step 3: 1 in upper byte?
	beq	st2
	lsr.w	#8,d2
	bset	#19,d2
st2	move.w	d2,d3
	andi.w	#$F0,d3		; step 2: 1 in upper nibble?
	beq	st1
	lsr.w	#4,d2
	bset	#18,d2
st1	move.w	d2,d3
	andi.w	#$C,d3		; step 1: 1 in upper half-nibble?
	beq	st0
	lsr.w	#2,d2
	bset	#17,d2
st0	move.w	d2,d3
	andi.w	#$2,d3		; step 0: 1 in bit 1?
	beq	done_flg
	bset	#16,d2
done_flg
	swap	d2		; put result in lower word
	rts

	end	START