Detecting Arithmetic Overflow in PICs

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

Translate This Thread From English to

Threaded View

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

Quoted text here. Click to load it

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

Quoted text here. Click to load it

Of course, I mean
        decf    resHigh,f

Same for all other "decf" and "incf" ;-(


Re: Detecting Arithmetic Overflow in PICs
On Sun, 31 Aug 2003 14:38:20 +0200, Jan-Hinnerk Reichert

Quoted text here. Click to load it

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
Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Quoted text here. Click to load it

Damn it! Of course I got the condition wrong. It must be
        btfss STATUS,C

Quoted text here. Click to load it

        btfsc   STATUS,C

Quoted text here. Click to load it


Re: Detecting Arithmetic Overflow in PICs
On Mon, 01 Sep 2003 02:58:03 +0200, Jan-Hinnerk Reichert

Quoted text here. Click to load it

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

Quoted text here. Click to load it


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...
 
Quoted text here. Click to load it

Lucky you ;-)

Quoted text here. Click to load it

Sounds interesting.

 Jan-Hinnerk


Re: Detecting Arithmetic Overflow in PICs

Quoted text here. Click to load it

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

Re: Detecting Arithmetic Overflow in PICs

Quoted text here. Click to load it

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
 
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Re: Detecting Arithmetic Overflow in PICs

Quoted text here. Click to load it

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

Quoted text here. Click to load it

Okay, I must admit, that the code is shorter than I expected. Is it
hand-optimized or compiler-generated? If it is from a compiler, which
one?

Nevertheless, it can be done faster, but probably not in C ;-(

 Jan-Hinnerk


Re: Detecting Arithmetic Overflow in PICs
Quoted text here. Click to load it

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

Quoted text here. Click to load it

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