From 196af3b1ccb51fef55be48a4e1da59004e04f123 Mon Sep 17 00:00:00 2001 From: Bradley Bell Date: Mon, 28 Oct 2002 20:12:48 +0000 Subject: [PATCH] fix infinite loop in quad_sqrt. courtesy of Martin Schaffner --- maths/fixc.c | 61 ++++++++++++++++++++++------------------------------ 1 file changed, 26 insertions(+), 35 deletions(-) diff --git a/maths/fixc.c b/maths/fixc.c index 4d1c34d3..c121fcf6 100644 --- a/maths/fixc.c +++ b/maths/fixc.c @@ -1,3 +1,4 @@ +/* $Id: fixc.c,v 1.5 2002-10-28 20:12:48 btb Exp $ */ /* THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX SOFTWARE CORPORATION ("PARALLAX"). PARALLAX, IN DISTRIBUTING THE CODE TO @@ -7,37 +8,15 @@ IN USING, DISPLAYING, AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE FREE PURPOSES. IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES. THE END-USER UNDERSTANDS -AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE. +AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE. COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION. ALL RIGHTS RESERVED. */ + /* - * $Source: /cvs/cvsroot/d2x/maths/fixc.c,v $ - * $Revision: 1.4 $ - * $Author: btb $ - * $Date: 2002-10-28 19:49:15 $ - * - * C version of fixed point library - * - * $Log: not supported by cvs2svn $ - * Revision 1.3 2001/10/31 07:41:54 bradleyb - * Sync with d1x - * - * Revision 1.2 2001/01/31 15:18:04 bradleyb - * Makefile and conf.h fixes - * - * Revision 1.1.1.1 2001/01/19 03:29:58 bradleyb - * Import of d2x-0.0.8 - * - * Revision 1.3 1999/10/18 00:31:01 donut - * more alpha fixes from Falk Hueffner * - * Revision 1.2 1999/08/05 22:53:41 sekmu - * - * D3D patch(es) from ADB - * - * Revision 1.1.1.1 1999/06/14 22:13:35 donut - * Import of d1x 1.37 source. + * C version of fixed point library * + * Old Log: * Revision 1.7 1995/09/22 14:08:16 allender * fixed fix_atan2 to work correctly with doubles * @@ -63,8 +42,8 @@ COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION. ALL RIGHTS RESERVED. * --- PC RCS Info --- * Revision 1.1 1995/03/08 18:55:09 matt * Initial revision - * - * + * + * */ #ifdef HAVE_CONFIG_H @@ -72,7 +51,7 @@ COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION. ALL RIGHTS RESERVED. #endif #ifdef RCS -static char rcsid[] = "$Id: fixc.c,v 1.4 2002-10-28 19:49:15 btb Exp $"; +static char rcsid[] = "$Id: fixc.c,v 1.5 2002-10-28 20:12:48 btb Exp $"; #endif #include @@ -321,11 +300,23 @@ int32_t fixdivquadlong(u_int32_t nl,u_int32_t nh,u_int32_t d) return r; } +#if 0 +// this version caused inf loop with: +// quad_sqrt(0x27eb7121/*low=669741345*/, +// 0x4cd40ad8/*high=1288964824*/); unsigned int fixdivquadlongu(uint nl, uint nh, uint d) { return fixdivquadlong((u_int32_t) nl,(u_int32_t) nh,(u_int32_t) d); } -#else +#endif + +unsigned int fixdivquadlongu(uint nl, uint nh, uint d) +{ + u_int64_t n = (u_int64_t)nl | (((u_int64_t)nh) << 32 ); + return n / ((u_int64_t)d); +} + +#else //of ifdef NO_FIX_INLINE int32_t fixdivquadlong(u_int32_t nl,u_int32_t nh,u_int32_t d) { int32_t a; __asm__("idivl %3" @@ -344,7 +335,7 @@ __asm__("divl %3" ); return (a); } -#endif +#endif //def NO_FIX_INLINE u_int32_t quad_sqrt(u_int32_t low,int32_t high) { @@ -372,9 +363,9 @@ u_int32_t quad_sqrt(u_int32_t low,int32_t high) //quad loop usually executed 4 times - r = (fixdivquadlongu(low,high,r)+r)/2; - r = (fixdivquadlongu(low,high,r)+r)/2; - r = (fixdivquadlongu(low,high,r)+r)/2; + r = fixdivquadlongu(low,high,r)/2 + r/2; + r = fixdivquadlongu(low,high,r)/2 + r/2; + r = fixdivquadlongu(low,high,r)/2 + r/2; do { @@ -384,7 +375,7 @@ u_int32_t quad_sqrt(u_int32_t low,int32_t high) if (t==r) //got it! return r; - r = (t+r)/2; + r = t/2 + r/2; } while (!(r==t || r==old_r)); -- 2.39.2