Negating 16 bits

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

In a constant effort to speed up and save memory, I confronted a simple but uncomfortable situation.

Needing to find the ABS value between two 16 bits, already set in four low AVR Registers, the easier and automatically way was like this:

R6:R5 = first 16 bits number
R8:R7 = second 16 bits number
R0:R1 = resulting ABSolute Value

Just a reminder for those a little bit lost about ABS value, it means the "positive result" between the two numbers. For example, the ABS between 8 and 5 is 3, but also is 3 the ABS between 5 and 8. So, subtracting 8-5 result in 3, but 5-8 results in -3, removing the sign, it ends in pure 3. The problem is when the AVR subtracts (8 bits operation) 5-8 it results in 0xFD (-3) with cy bit on, and ABS needs to be 0x03, so a simple NEG operation does the trick. But for 16 bits it is a little bit tricky.

Okay, at first I wrote:

      Mov R0,R6     Mov R1,R7
      Sub R0,R8     Sbc R1,R9    Brcc PC+5
      Mov R0,R8     Mov R1,R9
      Sub R0,R6     Sbc R1,R7

and at this point I'd have the ABS value in R0:R1.

Oh, yeah! you never saw more than one assembly instruction in the same line? hmmm. Let me tell you, it works, and in most cases it is easier to understand the flow.

See, the first line (Mov R0,R6 Mov R1,R7) makes two instructions that represent moving 16 bits, they work together, they are a pack, so why not group them together in the same line?

The second line, makes the subtraction, and the Brcc at the end decides if we already have the ABS value or not, based on the carry bit. So, if it will jump the next 4 instructions or not, it depends on the registers on the second line. It is another pack tied together. So, why not make it another group of operation and decision, just in one line? I don't know how you see it, but it is easier for me.

Okay, the 4 lines of code above just tried to subtract two registers from other two, if it results with cy bit on, means overflow, negative number, so not ABS value yet. Then the subtraction is done with the value reversed, and now ABSolute value as result.

Well, that pestered me for days, and finally I was able to dedicate few minutes trying to make that decision smarter.

Okay, if the result is negative (cy=1), it would be just a matter of subtract that negative number from zero, right? Yes. Right. Riiiiight. It would end up in a worse and ugly code.

      Mov R0,R6     Mov R1,R7
      Sub R0,R8     Sbc R1,R9    Brcc PC+11
      Push R8       Push R9
      Clr  R8       Clr  R9
      Sub  R9,R1    Sbc  R8,R0
      Mov  R1,R9    Mov  R0,R8
      Pop  R9       Pop  R8 

Yuck!

But wait, there are the NEG and COM instructions, right? Riiiiight, again!

I made few attempts and to make sure, I run some simulations with R5,R6,R7,R8 increasing from 0x00000000 to 0xFFFFFFFF.

The AVR Studio is a very fat old lady desperately in need to cut donuts and carbohydrates, when dealing with simulation speed. It would take few days to complete the almost 4.3 billion loops in the test.

Solution? Dump it into an AVR chip and test, the AtMega128 running 16MHz takes only 3 hours!!!!

And No!, the devil lives in the little and inocent details, mostly around 0x01 and 0xFF, so I need to turn every single rock in the way.

For my desperation, I couldn't find an easier solution, but I found the name of what I was looking for: 16 bits Negate. Easier. Googhelp!!

Found Atmel suggestion for "16 bits Negate" at application Doc0937 http://www.atmel.com/Images/doc0937.pdf as

      Com xl
      Com xh
      Subi xl,$ff
      sbci xh,$ff 

So, my little piece of code will end up:

      Mov R0,R6     Mov R1,R7
      Sub R0,R8     Sbc R1,R9    Brcc PC+5
      Com R0        Com R1
      Subi R1,$FF   Sbci R0,$FF

Whaaaat? It seems life is miserable. The problem is that Subi and Sbci doesn't work with lower registers.

Then, after few more minutes (I wish) of thinking I came up with:

      Neg R0
      Neg R1
      Brcc PC+2
      Dec R0 

So, my final code would be:

      Mov R0,R6     Mov R1,R7
      Sub R0,R8     Sbc R1,R9    Brcc PC+5
      Neg R1        Neg R0       Brcc PC+2
      Dec R0

Wow. Same instruction count as before, same cpu cycles, no gain at all. Well, but it's different :)

The advantage is that it gains from Atmel suggestion, since it runs on the all 32 registers.

But no, it is not the same cpu cycles, since the Brcc PC+2 may take or give one extra cycle. Humpf!

Solution:

See, the subtract instruction in AVR for lower registers are only the SUB and SBC, but it needs an extra register. The "Brcc PC+ 2 Dec R0", could be done in a single instruction (that doesn't exist) SBCI R0,0x00.

The solution comes from a trick. Subtract any register other than itself, and add it back again, the result is zero, right? RIGHT! Subtract with Carry and you are a winner.

      Sbc R20,R31    Add R20,R31
      ; is the same as
      Sbci R31,0x00
      ; since you subtracted and added R31 

This takes always the same CPU cycles, and will work for lower and higher registers.

So, my code ended up as:

      Mov R0,R6     Mov R1,R7
      Sub R0,R8     Sbc R1,R9    Brcc PC+5
      Neg R1        Neg R0
      Sbc R0,R31    Add R0,R31 

But wait, still four instructions after the Brcc PC+5, I started like that. But I found the tricky thing.

SBC Ra, Rb
Add Ra, Rb

while Rb can be any register, except Ra, and praying it will not be modified by an interrupt between the two instructions, is the same as

Sbci Ra,0x00

for all 32 registers.

We don't always gain, but we learn.

Wagner Lipnharski
Orlando Florida USA

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

You can speed up a code by using all kinds of clever tricks, e.g by using skip instructions and making the code more dense. A program can have more instructions (more flash memory) while the number of instructions executed is less. Often you have enough flash memory when writing ASM.
Example.

	cbi	GPIOR0, 7			;clear Y sign flag
	sbrc	Yval, 7				;if sign positive,
	sbi	GPIOR0, 7			; set Y sign flag
	sbrc	Yval, 7				;if sign positive,
	neg	Yval				;make value positive

3 or 5 clocks while length of code is 5 instructions.

RES

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

Any reason for not using MOVW ?

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

Negate 16 bit (on high register) can be done this way:

com  r17
neg  r16
sbci r17,255
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

1) Are these 16-bit values signed or unsigned?
2) You go through some contortions to work around lack of SBI on low registers. Then, R31 is used. Perhaps you could alter the code-generation model?

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

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

?

Quote:
signed or unsigned

Negate and abs only make sense if signed!

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

Quote:

Negate and abs only make sense if signed!

OK, then riddle me this, given OP's original description.

What is the desired result when the two input numbers are 0xffff and 0x0003?

I'd say it is 0x0004 if the input 16-bit values are "signed", and 0xfffc if they are "unsigned".

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

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

Shirley you can just subtract one register-pair from the other.
If CARRY flag is set, you negate the result.

No, I did not read past the first few lines of the original post.

Everything depends on whether you are dealing with signed or unsigned arguments in the first place.

Whatever you do, it should only be a few cycles to execute. Even if you have to negate.
If the input numbers are within a known range, you might be able to save the odd cycle. But who cares ?

David.

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

2's complement, signed numbers.
1's complement, generally flag bits or a boolean, not arithmetic value

The bible
http://www.amazon.com/Computer-P...

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

Quote:
But wait, there are the NEG and COM instructions, right? Riiiiight, again!

Deja Vu..

No RSTDISBL, no fun!

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

sparrow2 wrote:
Any reason for not using MOVW ?
Not all cores support it. The OP didn't mention which mcu this was for... but, as an example, the ATtiny4/5/9/10 lack it.

JJ

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

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

Quote:

The OP didn't mention which mcu this was for... but, as an example, the ATtiny4/5/9/10 lack it.

It lacks other things, too. Such as the GP registers in use.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

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

Quote:
the ATtiny4/5/9/10 lack it
But they also lack R0 through R15 which the OP is using (though he doesn't explain why he is restricting himself to those registers).

Regards,
Steve A.

The Board helps those that help themselves.

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

And the registers op uses.
I don't think that there are many "org" AVR's without MOVW and still have all 32 registers, they seem all to have a modern part as a replacement.

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

okay, sorry by the delay in clarify things.

Both 16 bits values are unsigned. They are positioning coordinates. If the new is higher, motion is forward.

The ABSolute result is the distance between the actual and new position. The distance, in ABS value, represents the steps the motors will do.

Obviously the subtraction is "NEWposition - ACTUALposition", if CY bit is off, result is already the ABS value and motion is forward. If CY is on, then the result needs to be negated (16 bits) and motion will be backward.

Sparrow2:

Movw could be used, but will restrict the AVR models to be used.

   com  r17  
   neg  r16 
   sbci r17,255 

works, but only if the high byte is a upper register.

RES:
I can't do it testing the N flag, or the bit 7 of the registers, since values are not signed.

Interesting that a NEG16 or NEGW could be easily implemented in hardware, perhaps Atmel could think about it for some new models...

Wagner Lipnharski
Orlando Florida USA

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

Quote:
Movw could be used, but will restrict the AVR models to be used.
As stated above, modern AVRs except for the brain dead models have MOVW, and you have already eliminated those models by using registers below R16.
Quote:
They are positioning coordinates. If the new is higher, motion is forward.
Then why would you think that this operation is time critical?

Regards,
Steve A.

The Board helps those that help themselves.

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

Quote:
perhaps Atmel could think about it for some new models...

They did!
ARM ARMv7M wrote:
USADA8: Unsigned Sum of Absolute Differences and Accumulate performs four unsigned 8-bit subtractions, and adds the absolute values of the differences to a 32-bit accumulate operand.

So it is:

out+=abs(x0-y0)+abs(x1-y1)+abs(x2-y2)+abs(x3-y3);

That takes one click.

No RSTDISBL, no fun!

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

I always thought to negate (unary -), you invert all the bits then add 1.

0001 +1

1110 inverted

1111 add one to get -1

 

"We trained hard... but it seemed that every time we were beginning to form up into a team, we would be reorganized. I was to learn later in life that we tend to meet any new situation by reorganizing. And a wonderful method it can be of creating the illusion of progress while producing confusion, inefficiency and demoralization." Petronius Arbiter, approx. 2000 years ago.

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

Yes, for 2's complement binary you do, but there is more than one way to accomplish that task.

Regards,
Steve A.

The Board helps those that help themselves.

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

Quote:
Interesting that a NEG16 or NEGW could be easily implemented in hardware, perhaps Atmel could think about it for some new models...

The AVR is a 8 bit CPU, and has a 8 bit NEG. done
There was other things I rather would like to have as 16 bit.

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

sparrow2 wrote:

The AVR is a 8 bit CPU, and has a 8 bit NEG. done
There was other things I rather would like to have as 16 bit.

sparrow2,
even so, we have Adiw, Movw, Sbiw, being the Movw a true 16 bits operation in a single clock cycle. "Negw" would be a nice addition to the them. ;)

Wagner Lipnharski
Orlando Florida USA

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

Koshchi wrote:
Then why would you think that this operation is time critical?

Not time critical. I just love to see waveforms without jitter, and I love very much to write assembly code always faster and smaller than C ;)

Wagner Lipnharski
Orlando Florida USA

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

Quote:
I just love to see waveforms without jitter

Since there a no 16 bit OUT I don't see how it can make jítter! (at least the code I gave you) :)

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

hi all,
This is the first time that I have to deal with negative result’s operations. Where can I learn how to work with this numbers, and what's the difference between signed , unsigned and negative? (regarding to binary digits and how are they differenced on the register.
(I'm working on C language) and the numbers are 16 bits long.
thanks!

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

Quote:

s. Where can I learn how to work with this numbers, and what's the difference between signed , unsigned and negative? (regarding to binary digits and how are they differenced on the register.
(I'm working on C language)

Get a copy of K&R.

The choice/use of signed/unsigned in C is actually pretty easy. If you expect the values you are storing to hold values less than 0 (negative) use "signed". Otherwise use "unsigned".

Note also that at the end of the day a 16 bit "int" in memory will hold 0x0000..0xFFFF. It's only at the point of interpretation that whether it is treated signed or unsigned that matters:

clawson@ws-czc1138h0b:~$ cat test.c
#include 

signed short a;
unsigned short b;

int main(void) {
  a = 123 - 456;
  b = 123 - 456;
  printf("a=%hd, b=%hu\n", a, b);
  printf("a=%hu, b=%hd\n", a, b);
  printf("hex: a=%04hX, b=%04hX\n", a, b);
}

clawson@ws-czc1138h0b:~$ gcc test.c -o test
clawson@ws-czc1138h0b:~$ ./test
a=-333, b=65203
a=65203, b=-333
hex: a=FEB3, b=FEB3

As I wrote that on my desktop PC I used "short" and 'h' in the printf() output to keep things to 16 bit to act like AVR int's.

EDIT: apologies top OP, I hadn't realised I was responding to a thread hijack :oops: