[PATCH] Fix carry bug in 128-bit unsigned integer adding

[PATCH] Fix carry bug in 128-bit unsigned integer adding

[Liu Yu]

This bug exists in math emulation for powerpc.
The macro define are mainly used by multiplication.

When adding two unsigned operands ( r = x + y ),
the carry bit can be counted by whether r is less than x.
However, when adding three unsigned operands, this method does not work.

The original code below uses this method to count carry,
it apparently overlook the case of three operands. 
Assume all the operands is 32-bit wide,
( r = x + y + last_carry , x = 0, y = 0xffffffff, last_carry = 1),
then r is no less than x but it actually gets a carry.

I tried to fix this bug, but this patch seems not that pretty.
Are there any better ideas? 
Comments are always welcomed!


Signed-off-by: Liu Yu <Yu.Liu@freescale.com>
---
 arch/powerpc/math-emu/op-4.h |   22 ++++++++++++++--------
 1 files changed, 14 insertions(+), 8 deletions(-)

diff --git a/arch/powerpc/math-emu/op-4.h b/arch/powerpc/math-emu/op-4.h
index fcdd6d0..93c7390 100644
--- a/arch/powerpc/math-emu/op-4.h
+++ b/arch/powerpc/math-emu/op-4.h
@@ -195,18 +195,24 @@
 
 #ifndef __FP_FRAC_ADD_4
 #define __FP_FRAC_ADD_4(r3,r2,r1,r0,x3,x2,x1,x0,y3,y2,y1,y0)		\
-  (r0 = x0 + y0,							\
-   r1 = x1 + y1 + (r0 < x0),						\
-   r2 = x2 + y2 + (r1 < x1),						\
-   r3 = x3 + y3 + (r2 < x2))
+   do {									\
+	_FP_W_TYPE _x0 = x0, _x1 = x1, _x2 = x2, _y1 = y1, _y2 = y2; 	\
+	r0 = x0 + y0;							\
+	r1 = x1 + y1 + (r0 < _x0);					\
+	r2 = x2 + y2 + (r1 < _x1 || (r1 == _x1 && !(_y1 + 1)));		\
+	r3 = x3 + y3 + (r2 < _x2 || (r2 == _x2 && !(_y2 + 1)));		\
+   } while(0)
 #endif
 
 #ifndef __FP_FRAC_SUB_4
 #define __FP_FRAC_SUB_4(r3,r2,r1,r0,x3,x2,x1,x0,y3,y2,y1,y0)		\
-  (r0 = x0 - y0,                                                        \
-   r1 = x1 - y1 - (r0 > x0),                                            \
-   r2 = x2 - y2 - (r1 > x1),                                            \
-   r3 = x3 - y3 - (r2 > x2))
+   do {									\
+	_FP_W_TYPE _x0 = x0, _x1 = x1, _x2 = x2, _y1 = y1, _y2 = y2; 	\
+	r0 = x0 - y0;							\
+	r1 = x1 - y1 - (r0 > _x0);					\
+	r2 = x2 - y2 - (r1 > _x1 || (r1 == _x1 && !(_y1 + 1)));		\
+	r3 = x3 - y3 - (r2 > _x2 || (r2 == _x2 && !(_y2 + 1)));		\
+   } while(0)
 #endif
 
 #ifndef __FP_FRAC_ADDI_4
-- 

Re: [PATCH] Fix carry bug in 128-bit unsigned integer adding

[Kumar Gala]

On Jan 6, 2008, at 8:26 AM, Liu Yu wrote:

> This bug exists in math emulation for powerpc.
> The macro define are mainly used by multiplication.
>
> When adding two unsigned operands ( r = x + y ),
> the carry bit can be counted by whether r is less than x.
> However, when adding three unsigned operands, this method does not  
> work.
>
> The original code below uses this method to count carry,
> it apparently overlook the case of three operands.
> Assume all the operands is 32-bit wide,
> ( r = x + y + last_carry , x = 0, y = 0xffffffff, last_carry = 1),
> then r is no less than x but it actually gets a carry.
>
> I tried to fix this bug, but this patch seems not that pretty.
> Are there any better ideas?
> Comments are always welcomed!

take a look at how include/math-emu/op-4.h implements __FP_FRAC_ADD_4  
& __FP_FRAC_SUB_4.  Will that fix the bug, if so we should make the  
code match how its done there.

- k

RE: [PATCH] Fix carry bug in 128-bit unsigned integer adding

[Liu Yu]

>=20
> take a look at how include/math-emu/op-4.h implements=20
> __FP_FRAC_ADD_4 & __FP_FRAC_SUB_4.  Will that fix the bug, if=20
> so we should make the code match how its done there.
>=20
> - k
>=20
>=20

The macro define __FP_FRAC_ADD_4 is below. It can fix the carry bug.=20
But still exist a problem that r[0-2] and x[0-2] cannot be referred to
the same variable.
If r0 and x0 are the same variable, the comparison ( r0 < x0 ) will
always fail.
I don't know whether we need to fix this problem.

---
#define __FP_FRAC_ADD_4(r3,r2,r1,r0,x3,x2,x1,x0,y3,y2,y1,y0)    \
  do {                                                          \
    int _c1, _c2, _c3;                                          \
    r0 =3D x0 + y0;                                               \
    _c1 =3D r0 < x0;                                              \
    r1 =3D x1 + y1;                                               \
    _c2 =3D r1 < x1;                                              \
    r1 +=3D _c1;                                                  \
    _c2 |=3D r1 < _c1;                                            \
    r2 =3D x2 + y2;                                               \
    _c3 =3D r2 < x2;                                              \
    r2 +=3D _c2;                                                  \
    _c3 |=3D r2 < _c2;                                            \
    r3 =3D x3 + y3 + _c3;                                         \
  } while (0)
#endif

Re: [PATCH] Fix carry bug in 128-bit unsigned integer adding

[Kumar Gala]

On Jan 8, 2008, at 9:05 PM, Liu Yu wrote:

>
>>
>> take a look at how include/math-emu/op-4.h implements
>> __FP_FRAC_ADD_4 & __FP_FRAC_SUB_4.  Will that fix the bug, if
>> so we should make the code match how its done there.
>>
>> - k
>>
>>
>
> The macro define __FP_FRAC_ADD_4 is below. It can fix the carry bug.
> But still exist a problem that r[0-2] and x[0-2] cannot be referred to
> the same variable.
> If r0 and x0 are the same variable, the comparison ( r0 < x0 ) will
> always fail.
> I don't know whether we need to fix this problem.

Not sure.  Probably worth asking this on the glibc list and see if  
they have theories.  (For the short term I'd say lets use the version  
from include/math-emu/op-4.h as a fix.  If r0 & x0 can be the same  
variable the bug exists in a lot more places (glibc soft-fp and  
generic kernel mathemu)

- k

[PATCH] Fix carry bug in 128-bit unsigned integer adding

[Liu Yu]

Synchronize it to the definition in include/math-emu/op-4.h for short term.

Signed-off-by: Liu Yu <Yu.Liu@freescale.com>
---
 arch/powerpc/math-emu/op-4.h |   40 ++++++++++++++++++++++++++++++----------
 1 files changed, 30 insertions(+), 10 deletions(-)

diff --git a/arch/powerpc/math-emu/op-4.h b/arch/powerpc/math-emu/op-4.h
index fcdd6d0..c9ae626 100644
--- a/arch/powerpc/math-emu/op-4.h
+++ b/arch/powerpc/math-emu/op-4.h
@@ -194,19 +194,39 @@
   (X##_f[3] = I3, X##_f[2] = I2, X##_f[1] = I1, X##_f[0] = I0)
 
 #ifndef __FP_FRAC_ADD_4
-#define __FP_FRAC_ADD_4(r3,r2,r1,r0,x3,x2,x1,x0,y3,y2,y1,y0)		\
-  (r0 = x0 + y0,							\
-   r1 = x1 + y1 + (r0 < x0),						\
-   r2 = x2 + y2 + (r1 < x1),						\
-   r3 = x3 + y3 + (r2 < x2))
+#define __FP_FRAC_ADD_4(r3,r2,r1,r0,x3,x2,x1,x0,y3,y2,y1,y0)	\
+  do {								\
+    int _c1, _c2, _c3;						\
+    r0 = x0 + y0;						\
+    _c1 = r0 < x0;						\
+    r1 = x1 + y1;						\
+    _c2 = r1 < x1;						\
+    r1 += _c1;							\
+    _c2 |= r1 < _c1;						\
+    r2 = x2 + y2;						\
+    _c3 = r2 < x2;						\
+    r2 += _c2;							\
+    _c3 |= r2 < _c2;						\
+    r3 = x3 + y3 + _c3;						\
+  } while (0)
 #endif
 
 #ifndef __FP_FRAC_SUB_4
-#define __FP_FRAC_SUB_4(r3,r2,r1,r0,x3,x2,x1,x0,y3,y2,y1,y0)		\
-  (r0 = x0 - y0,                                                        \
-   r1 = x1 - y1 - (r0 > x0),                                            \
-   r2 = x2 - y2 - (r1 > x1),                                            \
-   r3 = x3 - y3 - (r2 > x2))
+#define __FP_FRAC_SUB_4(r3,r2,r1,r0,x3,x2,x1,x0,y3,y2,y1,y0)	\
+  do {								\
+    int _c1, _c2, _c3;						\
+    r0 = x0 - y0;						\
+    _c1 = r0 > x0;						\
+    r1 = x1 - y1;						\
+    _c2 = r1 > x1;						\
+    r1 -= _c1;							\
+    _c2 |= r1 > _c1;						\
+    r2 = x2 - y2;						\
+    _c3 = r2 > x2;						\
+    r2 -= _c2;							\
+    _c3 |= r2 > _c2;						\
+    r3 = x3 - y3 - _c3;						\
+  } while (0)
 #endif
 
 #ifndef __FP_FRAC_ADDI_4
-- 
1.5.2

Re: [PATCH] Fix carry bug in 128-bit unsigned integer adding

[Kumar Gala]

On Fri, 18 Jan 2008, Liu Yu wrote:

> Synchronize it to the definition in include/math-emu/op-4.h for short term.
>
> Signed-off-by: Liu Yu <Yu.Liu@freescale.com>
> ---
>  arch/powerpc/math-emu/op-4.h |   40 ++++++++++++++++++++++++++++++----------
>  1 files changed, 30 insertions(+), 10 deletions(-)

applied.

- k