#### Do you have a question? Post it now! No Registration Necessary

**posted on**

- Robert Scott

August 30, 2003, 3:08 pm

Since the mid-range PICs don't have any built-in overflow detection

circuitry, this must be done in software. I need to detect overflow

in signed 8-bit addition, and I need to do it fairly efficiently. An

overflow can be identified as a condition where the carry-in to bit 7

is not the same as the carry-out from bit 7. The signed range is -128

to +127. Does anyone have any really short way of detecting overflow

in addition of such numbers in a PIC?

-Robert Scott

Ypsilanti, Michigan

(Reply through newsgroups, not by direct e-mail, as automatic reply address is

fake.)

Re: Detecting Arithmetic Overflow in PICs

What is the fastest you have so far?

What are you calculating?

If you do multiple additions in a row, it could be better to use

(semi) 16-bit arithmetic and check range of the final result.

------------

; res = resHigh:W

load_result:

movf opp1,w ; move operand1 to resultLow

clrf resHigh ; sign extend result

btfsc opp1,7

decf resHigh

return

add

___to___result:

addwf opp2,w ; add low bytes

btfsc status,c

incf resHigh ; handle carry

btfsc opp2,7

decf resHigh ; add high bytes

return

check_result: ; this one destroys resHigh

movwf resLow

btfsc resLow,7 ; sets resHigh to zero, if and only iff

incf resHigh ; res[15..7] is all zeros or all ones

movf resHigh,f

btfsc STATUS,Z

goto overflow

...

This makes 5 cycles per addition, if done with a macro insted of a

subroutine.

----------------------

If you only want to add two numbers, it gets

clrf resHigh

btfsc opp1,7

decf resHigh

btfsc opp2,7

decf resHigh

movf opp1,w

addwf opp2,f ; opp2 holds result

btfsc STATUS,C

incf resHigh

btfsc opp2,7 ; note that opp2 is result here

incf resHigh

movf resHigh,f ; test for zero

btfsc STATUS,Z

goto overflow

...

Note 1: bit 7 of resHigh tells wheter it was a negative or positive

overflow. Just in case you want to cap values ;-)

Note 2: resHigh doesn't need clearing for every addition, since it is

zero at the end (if no overflow occured).

That's 14/13 (instruction) cycles. Has someone a faster routine?

Of course, everything is highly untested...

Jan-Hinnerk

Re: Detecting Arithmetic Overflow in PICs

In my application I am using signed overflow detection as a way of

implementing a normal and expected limiting condition. Behaviour near

the limiting condition does not have to be precise, so I have taken

advantage of this fact. I need to add PhaseDelta (-8...+7) to

PhaseAccum (-128...+127) so that PhaseAccum never overflows as a

signed number. PhaseDelta is initially formed by subtracting two

modulo-16 numbers, so it is only 4-bits and it needs to be sign

extended to 8 bits. In the process of sign extending PhaseDelta, I

already have the cases of (+) and (-) separated, so combine sign

extension with overflow limiting as follows:

if(bit_test(PhaseDelta,3)) // -8...-1

{

PhaseDelta |= 0xf0; //..sign extend to 8 bits

if((!bit_test(PhaseAccum,7)) || (unsigned)PhaseAccum > 0x88)

PhaseAccum += PhaseDelta;

}

else // PhaseDelta = 0...+7

{

PhaseDelta &= ~0xf0; //..sign extend to 8 bits

if(bit_test(PhaseAccum,7) || (unsigned)PhaseAccum < 120)

PhaseAccum += PhaseDelta;

}

Even though PhaseAccum is a signed value, I use the unsigned

comparison, because it is much faster (as compiled by the CCS PIC-C

compiler). The limiting behaviour is a little more conservative than

it needs to be because the code shown will limit at values other than

+127 or -128. But to make the limiting precise would have required

more code, and this code is part of a tight DSP loop. Besides, the

approximate limiting behaviour is adequate for the application. But I

was just wondering if there was a slick way of doing signed overflow

detection in general. By the way, the overflow detection in the code

that you posted appears to be for unsigned arithmetic only. But

thanks for responding anyway.

-Robert Scott

Ypsilanti, Michigan

(Reply through newsgroups, not by direct e-mail, as automatic reply address is

fake.)

Re: Detecting Arithmetic Overflow in PICs

By the way, the overflow detection in the

I'm quite sure, that it does signed arithmetic. Look at the first

code, since the second is a bit more cryptic.

"Load_result" converts the signed 8-bit value in op1 to signed 16-bit

and stores the result in resHigh:W

"Add_result" adds the signed 8-bit value in op2 to the signed 16-bit

in resHigh:W. Just test it for some sample numbers.

"Check_result" tests if "resHigh:W" is less than -128 or greater 127.

It is not done in an obvious way, but quite fast.

I could still have made an mistake, so please check it.

Jan-Hinnerk

Re: Detecting Arithmetic Overflow in PICs

Is there any reason you used 2's-complement?

You could also change your representation, so that -128 is represented

by 0 and 127 by 255.

Even if this is not an option, try if the following is shorter/faster:

PhaseAccum += 0x80;

if(bit_test(PhaseDelta,3)) // -8...-1

{

PhaseDelta |= 0xf0; //..sign extend to 8 bits

if((unsigned)PhaseAccum > 0x08)

PhaseAccum += PhaseDelta;

}

else // PhaseDelta = 0...+7

{

PhaseDelta &= ~0xf0; //..sign extend to 8 bits

if((unsigned)PhaseAccum < 0xf8)

PhaseAccum += PhaseDelta;

}

PhaseAccum -= 0x80;

If you do it in assembler a add and restore is usually faster than a

compare based solution:

movlw 0x80

addwf PhaseAccum,f ; change representation

btfss PhaseDelta,3

goto PhaseDelta_positive

PhaseDelta_negative:

movlw 0xf0

iorwf PhaseDelta,w ; W = sign extended PhaseDelta

addwf PhaseAccum,f ; add (negative) PhaseDelta

btfsc STATUS,C ; if (unsigned) overflow

subwf PhaseAccum,f ; restore old value

goto end

PhaseDelta_positive:

movlw 0x0f

andwf PhaseDelta,w ; W = sign extended PhaseDelta

addwf PhaseAccum,f ; add (positive) PhaseDelta

btfss STATUS,C ; if (unsigned) overflow

subwf PhaseAccum,f ; restore old value

end:

movlw 0x80

addwf PhaseAccum,f ; change representation

This gives a slightly different limiting behaviour, but is fast (12

cycles) and uses the same number of cycles for all input values ;-)

The first/last two instructions can be ommited, if you change your

integer representation as noted above.

/Jan-Hinnerk

Re: Detecting Arithmetic Overflow in PICs

On Mon, 01 Sep 2003 02:58:03 +0200, Jan-Hinnerk Reichert

What a wonderful solution! (with the btfsc/btfss corrected). I had

never realized the potential advantage of the offset representation of

signed numbers, but it works perfectly for signed overflow detection.

Thanks a lot.

I will be able maintain the offset representation so that I can avoid

the repeated conversions at the beginning and the end, and just

perform the offset conversion once when the grand total is used. Of

course I will have to initialize the sum to 0x80 instead of 0 after

each grand total is used.

In case you are interested, the application is a tuning device for

pipe organs. Microphone values are quadrature demodulated into a

phase angle (in 16ths of a cycle). Successive phase angles are

subtracted to give the PhaseDelta (-8...+7). The PhaseDeltas are

accumulated to get the overall phase change over a given time period,

which determines pitch error. The limiting mentioned above represents

the fact that if the pitch is off by a large amount, we really don't

need to know how far off it is. Quantitative information becomes

important only when the pipe is tuned somewhat closer to the correct

pitch.

-Robert Scott

Ypsilanti, Michigan

(Reply through newsgroups, not by direct e-mail, as automatic reply address is

fake.)

What a wonderful solution! (with the btfsc/btfss corrected). I had

never realized the potential advantage of the offset representation of

signed numbers, but it works perfectly for signed overflow detection.

Thanks a lot.

I will be able maintain the offset representation so that I can avoid

the repeated conversions at the beginning and the end, and just

perform the offset conversion once when the grand total is used. Of

course I will have to initialize the sum to 0x80 instead of 0 after

each grand total is used.

In case you are interested, the application is a tuning device for

pipe organs. Microphone values are quadrature demodulated into a

phase angle (in 16ths of a cycle). Successive phase angles are

subtracted to give the PhaseDelta (-8...+7). The PhaseDeltas are

accumulated to get the overall phase change over a given time period,

which determines pitch error. The limiting mentioned above represents

the fact that if the pitch is off by a large amount, we really don't

need to know how far off it is. Quantitative information becomes

important only when the pipe is tuned somewhat closer to the correct

pitch.

-Robert Scott

Ypsilanti, Michigan

(Reply through newsgroups, not by direct e-mail, as automatic reply address is

fake.)

Re: Detecting Arithmetic Overflow in PICs

You are welcome.

I haven't realized the potential advantage myself, since I am used to

have an overflow flag ;-)

This solution also works for the general case, if you leave out the

sign extension and relace the "restore"-instruction with a goto/call

to the error handling. This is faster than my first solution...

Lucky you ;-)

Sounds interesting.

Jan-Hinnerk

Re: Detecting Arithmetic Overflow in PICs

Overflow is when the sign of both operands differs from the sign

of the result.

For n-bit numbers as in "x = a + b" you could test like:

#define SIGN (n-1)

if (!(bit

___test (a ^ b, SIGN)) && bit___test (a ^ x, SIGN))

; /

*** overflow ***/

else

; /

*** ok ***/

--

Wil

Wil

Re: Detecting Arithmetic Overflow in PICs

The real problem is that ANSI-C provides no method of handling carry

or overflow. There are many ways to test for overflow. However, it

depends on the architecture which one is fastest (usually, there are

carry/overflow-flags available in hardware).

Your solution is very short in C and may do well enough on some

architectures, but will result in bloated assembler code on PIC ;-(

Jan-Hinnerk

Re: Detecting Arithmetic Overflow in PICs

The question was "detecting overflow in general", that's what I answered

to. And since the principle of detecting signed overflow has nothing to

do with neither carry nor overflow flag (if implemented, they will be set

as a result of) I did not mention them.

For addition/subtraction of "a" and "b" resulting in "x" you only need to

check two combinations of the MSBs of a, b and x, like:

a b x

-------

0 0 1 --> overflow

1 1 0 --> overflow

Does that lead to bloated code on PIC?

--

Wil

Wil

Re: Detecting Arithmetic Overflow in PICs

This is a valid test for overflow and the PIC assembler source

is given below

; a b x

; -------

; 0 0 1 --> overflow

; 1 1 0 --> overflow

movf arg1,w

addwf arg2,w

movwf res ; res = arg1 + arg2

; a is bit 7 of arg1

; b is bit 7 of arg2

; x is bit 7 of res

movf arg1,w

iorwf arg2,w

xorlw $80

andwf res,w ; (+ve) + (+ve) -> (-ve) overflow

movwf overflow ; v = ~(a | b) & x

comf res,w

andwf arg1,w

andwf arg2,w ; (-ve) + (-ve) -> (+ve) overflow

iorwf overflow ; v = v | (~x & a & b)

btfsc overflow,7

goto oflow

___occured ; if (v & 0x80) != 0 then goto oflow___occured

Regards

Sergio Masci

http://www.xcprod.com/titan/XCSB - optimising structured PIC BASIC compiler

Re: Detecting Arithmetic Overflow in PICs

Your problem is that you may have a number such as 50, and if you

add 100 to it, you'll get 150, which is beyond the range of your data

type.

Whenever I have a problem like this, I change to the next larger

data type. In this case, I would go to a signed 16-bit variable.

Assuming that your initial value is always 8-bit signed (which is

cast to 16-bit), then you can never have an overflow.

I realize it may run a little more slowly, and require a little more

ROM, but in my projects that's typically not an issue.

The thing that scares me most is failure in the field. I will do

whatever it takes to avoid having that happen.

Re: Detecting Arithmetic Overflow in PICs

As I said earlier, my problem is not one of handling an exceptional

error condition. The overflow that I get is a normal, expected, and

desireable opportunity to perform a limiting function, which just

happens to make perfect sense for my particular application. Using a

16-number would avoid the overflows, but it would not afford the

opportunity of such an easy limiting action.

-Robert Scott

Ypsilanti, Michigan

(Reply through newsgroups, not by direct e-mail, as automatic reply address is

fake.)

#### Site Timeline

- » Powering a LPC2114 ARM7
- — Next thread in » Embedded Programming

- » can u tell me what kind of relay being used here
- — Previous thread in » Embedded Programming

- » Power On Self Test
- — Newest thread in » Embedded Programming

- » Stare TV zakłócało Internet przez 18 miesięcy
- — The site's Newest Thread. Posted in » Electronics (Polish)