LCC Bug: Negative number divisions

[victor]

Code: Select all

#define USE_STDOUT

#include <stdlib.h>
#include <stdio.h>

int a = -123;
int c = 2;

main(void) {
	int b = -123;
	printf("a=%d, a/2=%d, divide16signed(a,2)=%d, a%%2=%d, (a/2)*2+a%%2=%d\n", a, a/2, a/c, a%c, (a/c)*c+a%c);
	printf("b=%d, b/2=%d, divide16signed(b,2)=%d, b%%2=%d, (b/2)*2+b%%2=%d\n", b, b/2, b/c, b%2, (b/2)*c+b%c);
	return 0;
}

The output is (code generated by LCC v1.47 (Dec 11 2013 14:49:00)):

Code: Select all

a=-123, a/2=-62, divide16signed(a,2)=-62, a%2=1, (a/2)*2+a%2=-123
b=-123, b/2=-61, divide16signed(b,2)=-62, b%2=-1, (b/2)*2+b%2=-121

If I use gcc to compile the code, I get the following output:

Code: Select all

a=-123, a/2=-61, divide16signed(a,2)=-61, a%2=-1, (a/2)*2+a%2=-123
b=-123, b/2=-61, divide16signed(b,2)=-61, b%2=-1, (b/2)*2+b%2=-123

The results generated by LCC is quite interesting. The first a/2 is calculated by right shifting one bit, so the result is -62. In the second line, the b/2 and b%2 is calculated during the compilation time (since both b and 2 are constants), and the quotient is truncated toward zero. The library function divide16signed() always tries to return a positive quotient, so it actually rounds the quotient down when dividend is negative.

However, in gcc (and most C compilers), division of signed binary numbers round towards 0 (which, if the result is negative, means it rounds up). And it is actually a C standard:

Code: Select all

6.5.5 Multiplicative operators

6 When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded (Note 88).  If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

(88) This is often called "truncation toward zero".

So, based on this standard, the compiler shouldn't optimize a/2 as a>>1, and the library function should also truncate the quotient towards zero. I am not sure if it is a feature of LCC (since it doesn't have to be ANSI-C complaint), but I think at least LCC should generate consistent code (-123/2 can't be both -61 and -62).

If we want to follow the ANSI-C, the compiler is still possible to optimize division as right shift, by just doing the following:

Code: Select all

/* We want to do A0/2 */
ldc C0, -15
ashl A0, C0, A1     // if A0 is a negative number, A1 = -1; 0 elsewise
asr A0,A0              // right shift A0 as usual
sub A0,A1,A0             // add the result by 1 if A0 is negative

Currently, since LCC optimizes a/2 as a>>1 the result is not the same as gcc. It makes porting a working program to VSDSP even harder and error-prone, because a bug like this is very hard to discover...

Workaround:
Replace code a/(2^n) with:

Code: Select all

(a>>n)-(a>>15)

if a is 16-bit, or

Code: Select all

(a>>n)-(a>>31)

if a is 32-bit.

[Henrik]

Thanks for perhaps our most in-depth and detailed error report ever!

Your results are quite interesting indeed. I'll forward this to Lasse, so we'll probably have this fixed by the next VSIDE release.

Kind regards,
- Henrik

[Lasse]

The original ANSI C standard states that the exact rounding behavior of the division operator is implementation-specific. In our case the behavior should be truncating towards negative infinity. Apparently the more recent C99 standard gives less freedom but we won't comply to that -- at least for the time being (we definitely want to use a shift instruction instead of a library call whenever possible...)

But you're right. There is a bug in LCC which causes inconsistent behavior. The easiest way to highlight the issue is by writing "int b=-123; printf("%d == %d\n",b/2,-123/2); which yields "-61 == -62". Value number optimization in LCC (pre)calculates division incorrectly by truncating towards zero. I have fixed this now, the updated compiler will be included in the next VSIDE release... Also thank you for bringing this to our attention

[victor]

That makes sense. Thank you, Lasse.
But please do mention this difference in compiler manuals and programming guides (I am not quite sure if it is there or not). Since sometimes users port an existing application to VSDSP and this kind of discrepancy between LCC and GCC could cause unexpected bugs.

Thanks,
Victor