Two's complement signed byte division

Go To Last Post
5 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Suppose r17 and r18 each have a 3-bit value between 0 and 7.

I want to subtract r18 from r17, multiply the difference by 16, then divide it by 7.

I'm doing something wrong... but I'm not quite sure what.

r17 = 0, r18 = 7

r17 - r18 = 0-7 =11111001 (two's complement of -7)

test bit 7; if 0, left-shift the value 4 times... otherwise:

subtract 1: 11111000, then invert: 00000111 ("7")
left-shift 4 times: 07 -> 0E -> 1C -> 38 -> 70
invert: ~70 = 8F, then add one: 8F + 1 = 90 (binary: 10010000)

Now, I KNOW -112 / 7 = -16, and -16 in binary is 11110000. But when I try repeatedly subtracting 7 from 0x90 until I overshoot, I get 0x14 (00010100)

SO... what SHOULD I be doing to 10010000 with 00000111 so I end up with a 11110000 somewhere? With positive values, I'd repeatedly subtract 7 from the first value (incrementing a counter each time carry is still clear and zero isn't set), and it works perfectly. But when one of the values is negative (like the example above), something goes astray.

There's no place like ~/

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Just to make it obvious what I'm trying to do... assume that StartValue and EndValue represent the starting and ending luminance index values of a LED element... 0 = off completely, 7 = brightest. I'm trying to calculate 8 integer values, starting with StartValue and ending with EndValue, with 6 more as evenly-spaced between them as possible.

Giving a few "clean" examples...
0 to 7: 0, 1, 2, 3, 4, 5, 6, 7
7 to 0: 7, 6, 5, 4, 3, 2, 1, 0
0 to 1: 0, 0, 0, 0, 1, 1, 1, 1
0 to 3: 0, 0, 1, 1, 2, 2, 3, 3
3 to 0: 3, 3, 2, 2, 1, 1, 0, 0

The reason for multiplying by 16 is so I can deal with them as integers, without completely butchering fractional precision. If I simply subtracted the end value from start value, divided it by 7, then tried to subtract(n x v) (where "n" is the step number and "v" is the difference divided by 7), it wouldn't work for any of the ranges besides 0-7, because it would truncate down to 0 (or, if I tried to round, increase to 1) and either subtract nothing or reach the endpoint too soon. By multiplying the range by 16, dividing it by 7, then dividing the quotient by 16, I can preserve enough precision in between to make the less-straightforward ranges work. At least, the positive ones (so far).

Here's the relevant code:

/**
 *	@param r16 = step [0-7]
 *	@param r17 = start value [0-7]
 *	@param r18 = end value [0-7]
 *	@return r16 = intermediate luminance value
 */
GetIntermediateLuminanceValue:
	cpi r16, 0
	brne notReturningStep0
	mov r16, r17
	ret
notReturningStep0:
	cpi r16, 7
	brne notReturningStep7
	mov r16, r18
	ret
notReturningStep7:
	mov r19, r17
	// subtract r18 from r19
	sub r19, r18
	// multiply by 16
	sbrc r19, 7
	rjmp multiplySigned1
	lsl r19
	lsl r19
	lsl r19
	lsl r19
	rjmp doneMultiplying
multiplySigned1:
	dec r19
	com r19
	lsl r19
	lsl r19
	lsl r19
	lsl r19
	com r19
	inc r19
doneMultiplying:

	// divide by 7
	clr r20
	push r19
	dividingBy7:
		inc r20
		subi r19, 7
		breq doneDividing
		brcc dividingBy7
		dec r20
doneDividing:
	
	pop r19

	dividingByR20:	
		sub r19, r20
		dec r16
		brne dividingByR20
	asr r19
	asr r19
	asr r19
	asr r19
	andi r19, 0x07
	mov r16, r19
	ret

There's no place like ~/

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You'll want to divide before you do the second two's complement. You'll have to set a flag when you do the first complement so you know to do the second one later.

By the way, there is a NEG opcode that does the two's complement for you. no need to do the 'dec-com'.

Edit: Also you can do the left shifting with:

andi r19, 0x0f
swap r19

(after the first two's complement)
and similarly with the right shifting

andi r19, 0xf0
swap r19

(before the second two's complement)

Regards,
Steve A.

The Board helps those that help themselves.

Last Edited: Tue. Jul 4, 2006 - 06:49 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

After the subtract there are only 15 possible values
( from 0-7=-7 to 7-0=7), use a simple table-lookup with a
15-entry table. Its flexible, fast, and you dont have to worry about div/mul.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What chip are you using? Is it one that supports MULSU?

If so, you can use it to multiply (end - start) * step.

And!.. You can use MULSU to divide by 7: Multiply by round(256/7) then divide by 256.

Dividing by 256 is essentially a no-op, since it is just a matter throwing out the low byte of the two-byte result.

Here's the divide by 7 code:

; Assume: R18 = (end - start) * step
; The result will be placed in R1

    ; multiply by round(256/7)
    ldi R16, 37     ;37 = round(256/7)
    mulsu R18, R16    

    ;round result.  If  lowbyte >=128  then  high-byte += 1
    sbrc R0, 7
    inc R1

--Brian