[geos-devel] Re: Portable Quadtree
strk
strk at keybit.net
Tue Oct 21 20:53:46 EDT 2003
I forgot: you'll have to run ./autogen; ./configure again for this to work.
Please report any missing 64bit detection (build will #warn a lot)
--strk;
strk wrote:
> I've added an autoconf check to find 64bit integer definition.
> Inserted in platform.h ifdef-switced typedef of int64 to long int
> or long long int. long int will be the default but if that is not really
> 64bits a INT64_IS_REALLY32 macro is defined and a warning issued.
> When (and if) we'll work out an alternative scheme we'll be able to use
> that define to switch between the fast/portable way.
>
> --strk;
>
> mbdavis wrote:
> > > used by bintree/Key.cpp. We might want to go for alternative
> > > implementation of these two functions... what do you think ?
> >
> > Yep, that should work. I don't think those functions are intrinsically dependent on IEEE-754 - they just use knowledge of that format to speed up their performance.
> >
> > > that since they are guaranteed to be 64bits. What about defining
> > > INT64 somewhere in the includes ?
> >
> > Sounds like a good idea. Again, the use of long is only because that's how Java gives you access to the bit pattern of floating-point. C++ might be able to use a union (but this would still be implementation dependent, so I guess that doesn't solve the problem)
> >
> > > Is there any test that would fail in case of a non IEEE-754 compiled
> > > GEOS ?
> >
> > The one thing that *might* fail in non-IEEE-754 is the RobustDeterminant computation. However, I've taken a quick look at the original paper and it doesn't mention any such dependency, so I think we can just plunge ahead and not worry about it.
> >
> > Martin Davis, Senior Technical Architect
> > Vivid Solutions Inc.
> > Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
> > Phone: (250) 385 6040 Fax: (250) 385 6046
> >
> >
> >
> > > -----Original Message-----
> > > From: strk [mailto:strk at keybit.net]
> > > Sent: Tuesday, October 21, 2003 10:47 AM
> > > To: Martin Davis
> > > Cc: Paul Ramsey
> > > Subject: Re: Portable Quadtree
> > >
> > >
> > > I've checked actual usage of bogus methods (powerOf2,biasedExponent).
> > > While biasedExponent is only used by Quadtree.cpp, powerOf2 is also
> > > used by bintree/Key.cpp. We might want to go for alternative
> > > implementation of these two functions... what do you think ?
> > >
> > > Actually I don't know about IEEE-754 popularity. GCC have few
> > > command line switches to modify its support but It looks like
> > > defaulting to that format. My concern was only about shifting
> > > amount bigger then number of bits in data type. It seems that
> > > microsoft environment have no problems in 52-shifting long
> > > integers, while gcc would like to use 'long long integers' for
> > > that since they are guaranteed to be 64bits. What about defining
> > > INT64 somewhere in the includes ? postgresql-7.3.4 typedefs int64
> > > using autoconf checks. Excerpt from configure.in:
> > >
> > > dnl Check to see if we have a working 64-bit integer type.
> > > dnl This breaks down into two steps:
> > > dnl (1) figure out if the compiler has a 64-bit int type with working
> > > dnl arithmetic, and if so
> > > dnl (2) see whether snprintf() can format the type correctly.
> > > (Currently,
> > > dnl snprintf is the only library routine we really need for
> > > int8 support.)
> > > dnl It's entirely possible to have a compiler that handles a
> > > 64-bit type
> > > dnl when the C library doesn't; this is fairly likely when
> > > using gcc on
> > > dnl an older platform, for example.
> > > dnl If there is no native snprintf() or it does not handle
> > > the 64-bit type,
> > > dnl we force our own version of snprintf() to be used instead.
> > > dnl Note this test must be run after our initial check for
> > > snprintf/vsnprintf.
> > >
> > > PGAC_TYPE_64BIT_INT([long int])
> > >
> > > if test x"$HAVE_LONG_INT_64" = x"no" ; then
> > > PGAC_TYPE_64BIT_INT([long long int])
> > > fi
> > >
> > >
> > > Later on, ifdef HAVE_LONG_INT_64 ... typedefs int64 type.
> > >
> > > This might be the first step to take. Then we'll have to make sure
> > > IEEE-754 is supported or find a (maybe slower) alternative
> > > implementation.
> > >
> > > Is there any test that would fail in case of a non IEEE-754 compiled
> > > GEOS ?
> > >
> > > --strk;
> > >
> > > mbdavis wrote:
> > > > uh-oh... The current quadtree implementation in JTS is
> > > highly dependent on the IEEE-754 double-precision floating
> > > point format. This obviously isn't very portable to other
> > > architectures. We may have to think of an alternative
> > > implementation to Quadtree that uses a different scheme to
> > > determine the sizes of the quads.
> > > >
> > > > Alternatively, for all internal GEOS uses it is possible to
> > > use a STRtree instead of a Quadtree. strk, can you try this fix?
> > > >
> > > > Martin Davis, Senior Technical Architect
> > > > Vivid Solutions Inc.
> > > > Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
> > > > Phone: (250) 385 6040 Fax: (250) 385 6046
> > > >
> > > >
> > > >
> > > > > -----Original Message-----
> > > > > From: strk [mailto:strk at keybit.net]
> > > > > Sent: Tuesday, October 21, 2003 12:13 AM
> > > > > To: Paul Ramsey
> > > > > Cc: Martin Davis
> > > > > Subject: Re: Portable Quadtree
> > > > >
> > > > >
> > > > > pramsey wrote:
> > > > > > Ah, OK. I should turn on our old Ultra10 and see if GEOS
> > > > > works at all :/
> > > > > > P.
> > > > >
> > > > > Simple test on my architecture (i686):
> > > > > Size of short: 2
> > > > > Size of int: 4
> > > > > Size of long: 4
> > > > > Size of long long: 8
> > > > >
> > > > > Type 'long long' is a GNU extension. I don't know what
> > > those Quadtree
> > > > > methods are supposed to do, but I'm really not sure about
> > > > > whether or not
> > > > > it is really working here and now. G++ warning is:
> > > > >
> > > > >
> > > > > index/quadtree/DoubleBits.cpp: In function `double
> > > > > geos::DoubleBits::powerOf2 (int)':
> > > > > index/quadtree/DoubleBits.cpp:12: warning: left shift count
> > > > > >= width of type
> > > > > index/quadtree/DoubleBits.cpp: In method `int
> > > > > geos::DoubleBits::biasedExponent ()':
> > > > > ../index/quadtree/DoubleBits.cpp:60: warning: right shift
> > > > > count >= width of type
> > > > >
> > > > > powerOf2(int) and biasedExponent() might be broken. Or
> > > they might know
> > > > > exacly what they are doing ...
> > > > > Martin, can you tell what you think about this ?
> > > > >
> > > > > --strk;
> > > > >
> > > > > >
> > > > > > On Monday, October 20, 2003, at 12:48 PM, strk wrote:
> > > > > >
> > > > > > > pramsey wrote:
> > > > > > >>
> > > > > > >> Explain? We have a non portable qtree right now?
> > > > > > >
> > > > > > > There is a bitwise shift of 52 positions on a long integer
> > > > > > > which is guaranteed to be at least 32 bit. Compiler issues
> > > > > > > a warning so I thought it was a portability issue. Yury
> > > > > > > does not get a warning there, I think we should inspect this.
> > > > > > >
> > > > > > > --strk;
> > > > > > >
> > > > >
> > >
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
More information about the geos-devel
mailing list