#56 fix rvals arithmetic wrap-around for byte types

open
nobody
None
1
2013-01-02
2011-08-23
Tim
No

PDL::Basic::rvals causes an arithmetic underflow when $class->type == byte. This causes the computed radial distances to be incorrect when a single dimension exceeds 24. I recommend converting $r to long() since the original datatype of the $class piddle is of no consequence when computing radial distances.

<code>
use PDL;
my $pdl = random(24,24)->convert(byte);
print $pdl->rvals; # BAD
print $pdl->convert(long)->rvals;
</code>

Here is a diff against version 2.4.9 (release) of Basic.pm.

611c611
< my $r = scalar(@_)? $class->new_from_specification(@_) : $class->new_or_inplace;
---
> my $r = PDL::Core::long(scalar(@_)? $class->new_from_specification(@_) : $class->new_or_inplace);

Thanks.

- Tim

Output of perldl -V

perlDL shell v1.354
PDL comes with ABSOLUTELY NO WARRANTY. For details, see the file
'COPYING' in the PDL distribution. This is free software and you
are welcome to redistribute it under certain conditions, see
the same file for details.

Summary of my PDL configuration

VERSION: PDL v2.4.9 (supports bad values)

$%PDL::Config = {
'BADVAL_PER_PDL' => '0',
'WITH_PROJ' => '0',
'FFTW_TYPE' => 'double',
'FFTW_LIBS' => [
'/lib',
'/usr/lib',
'/usr/local/lib'
],
'WITH_FFTW' => '0',
'GSL_LIBS' => undef,
'WITH_IO_BROWSER' => '0',
'PROJ_INC' => undef,
'WHERE_PLPLOT_INCLUDE' => undef,
'HTML_DOCS' => '1',
'SKIP_KNOWN_PROBLEMS' => '0',
'WHERE_PLPLOT_LIBS' => undef,
'WITH_3D' => '0',
'FFTW_INC' => [
'/usr/include/',
'/usr/local/include'
],
'WITH_POSIX_THREADS' => '1',
'POGL_VERSION' => '0.63',
'HIDE_TRYLINK' => '1',
'WITH_HDF' => '0',
'HDF_INC' => undef,
'POGL_WINDOW_TYPE' => 'glut',
'WITH_BADVAL' => '1',
'WITH_GD' => '0',
'FITS_LEGACY' => '1',
'WITH_SLATEC' => '1',
'BADVAL_USENAN' => '0',
'WITH_DEVEL_REPL' => '1',
'TEMPDIR' => '/tmp',
'PROJ_LIBS' => undef,
'USE_POGL' => '0',
'GD_LIBS' => undef,
'GSL_INC' => undef,
'GD_INC' => undef,
'WITH_GSL' => '0',
'OPTIMIZE' => undef,
'HDF_LIBS' => undef,
'MALLOCDBG' => {},
'WITH_MINUIT' => '1',
'WITH_PLPLOT' => '0',
'MINUIT_LIB' => undef
};
Summary of my perl5 (revision 5 version 10 subversion 1) configuration:

Platform:
osname=linux, osvers=2.6.24-29-server, archname=x86_64-linux-gnu-thread-multi
uname='linux crested 2.6.24-29-server #1 smp wed mar 16 19:04:28 utc 2011 x86_64 x86_64 x86_64 gnulinux '
config_args='-Dusethreads -Duselargefiles -Dccflags=-DDEBIAN -Dcccdlflags=-fPIC -Darchname=x86_64-linux-gnu -Dprefix=/usr -Dprivlib=/usr/share/perl/5.10 -Darchlib=/usr/lib/perl/5.10 -Dvendorprefix=/usr -Dvendorlib=/usr/share/perl5 -Dvendorarch=/usr/lib/perl5 -Dsiteprefix=/usr/local -Dsitelib=/usr/local/share/perl/5.10.1 -Dsitearch=/usr/local/lib/perl/5.10.1 -Dman1dir=/usr/share/man/man1 -Dman3dir=/usr/share/man/man3 -Dsiteman1dir=/usr/local/man/man1 -Dsiteman3dir=/usr/local/man/man3 -Dman1ext=1 -Dman3ext=3perl -Dpager=/usr/bin/sensible-pager -Uafs -Ud_csh -Ud_ualarm -Uusesfio -Uusenm -DDEBUGGING=-g -Doptimize=-O2 -Dplibpth=/lib/x86_64-linux-gnu /usr/lib/x86_64-linux-gnu -Duseshrplib -Dlibperl=libperl.so.5.10.1 -Dd_dosuid -des'
hint=recommended, useposix=true, d_sigaction=define
useithreads=define, usemultiplicity=define
useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
use64bitint=define, use64bitall=define, uselongdouble=undef
usemymalloc=n, bincompat5005=undef
Compiler:
cc='cc', ccflags ='-D_REENTRANT -D_GNU_SOURCE -DDEBIAN -fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
optimize='-O2 -g',
cppflags='-D_REENTRANT -D_GNU_SOURCE -DDEBIAN -fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include'
ccversion='', gccversion='4.5.2', gccosandvers=''
intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678
d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16
ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
alignbytes=8, prototype=define
Linker and Libraries:
ld='cc', ldflags =' -fstack-protector -L/usr/local/lib'
libpth=/usr/local/lib /lib/x86_64-linux-gnu /usr/lib/x86_64-linux-gnu /lib /usr/lib /lib64 /usr/lib64
libs=-lgdbm -lgdbm_compat -ldb -ldl -lm -lpthread -lc -lcrypt
perllibs=-ldl -lm -lpthread -lc -lcrypt
libc=, so=so, useshrplib=true, libperl=libperl.so.5.10.1
gnulibc_version='2.13'
Dynamic Linking:
dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
cccdlflags='-fPIC', lddlflags='-shared -O2 -g -L/usr/local/lib -fstack-protector'

Discussion

  • Chris Marshall

    Chris Marshall - 2011-08-23
    • assigned_to: nobody --> marshallch
    • labels: 101697 -->
     
  • Chris Marshall

    Chris Marshall - 2011-08-23

    The $pdl->rvals usage always keeps the type of the $pdl
    by design. This allows one to control memory usage. If
    you need more resolution then you can either use the
    sub call syntax or add a type convert to the method chain:
    E.g., $pdl->long->rvals

    I'm moving this to the Patches tracker for reference.

    For questions about PDL usage or odd behavior, I
    recommend posting to the perldl mailing list first,
    before entering a bug report. That allows discussion
    of the issue and a better statement of the problem
    for any futher action.

     
  • Derek Lamb

    Derek Lamb - 2011-08-23

    The proposed patch causes test failures in basic.t and image2d.t. In addition to the datatype issue Chris mentioned, it also fails when the Center parameter is not an integer:

    p rvals(18,{center=>[0.5]})
    [0 0 1 2 3 4 5 6 7 8]
    instead of the correct
    [0.5 0.5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5]

    I think the original motivation for the patch is good--rvals should not roll over for byte datatypes until r=256, not r=sqrt(256)=16. But if we convert datatypes internally for bytes and then convert back, why not do it for the others as well? It seems like all that datatype conversion would be expensive, but I'm not sure. It's easy to think of ways to break rvals in this way, now that Tim pointed out the flaw:

    p rvals(short,10,{squared=>0,center=>[-180]})
    [180 181 0 0 0 0 0 0 0 0]
    p rvals(ushort,10,{squared=>0,center=>[-250]})
    [250 251 252 253 254 255 0 22 32 39]

     
  • Chris Marshall

    Chris Marshall - 2011-08-23

    Re-architecting the rvals routine so that the wrap-around occurs
    at rval==255 rather than rval**2==255 seems like a good thing.
    It should be a straightforward enhancement.

     
  • Chris Marshall

    Chris Marshall - 2011-08-24

    Updating the title of this report and moving to Feature Request tracker to
    keep on the TODO list, possibly for 2.4.10. Ideally, the algorithm should
    allow rvals to be returned with values up to the capacity of the integer
    datatype before wrapping but would not significantly increase memory
    usage.

    The simplest to code might be to convert to a PP routine. However, it
    would be very cool if someone could use perl level PDL code to implement
    the enhanced capabilities. All are welcome to take the "rvals challenge"!

     
  • Chris Marshall

    Chris Marshall - 2011-08-24
    • priority: 5 --> 3
    • assigned_to: marshallch --> nobody
    • summary: PDL::Basic::rvals arithmetic underflow --> reduce/fix rvals arithmetic wrap-around for byte/short types
     
  • Chris Marshall

    Chris Marshall - 2011-08-24
    • summary: reduce/fix rvals arithmetic wrap-around for byte/short types --> fix rvals arithmetic wrap-around for byte types
     
  • Derek Lamb

    Derek Lamb - 2011-08-27

    See the two papers listed in the "Further Reading" section here for some ideas on how to implement rvals without squares and square roots: http://en.wikipedia.org/w/index.php?title=Pythagorean_addition&oldid=439354331

    Might make sense to have some intelligent switching code that can see if there is going to be a byte, short, ushort, etc overflow and calls the new method, but if not sticks with the tried and true square-root-of-sum-of-squares method.

     
  • Chris Marshall

    Chris Marshall - 2011-08-30

    I took a look at the algorithms---pretty cool---but they seem to
    require a fair number of temporaries and iterations/tests. I think
    it would be simpler to implement a PP routine with a single
    intermediate temp (double or float). That could be applied to
    all flavors of rvals with only the overhead of the single temp and
    the float/double calculation.

     
  • Chris Marshall

    Chris Marshall - 2011-11-11

    I've added some documentation for rvals which should clarify the
    performance for users. I'm leaving the ticket open as a direct PP
    implementation could address the problem without undue performance
    or memory penalty.

     
  • Chris Marshall

    Chris Marshall - 2011-11-11
    • assigned_to: nobody --> marshallch
    • priority: 3 --> 1
     
  • Chris Marshall

    Chris Marshall - 2013-01-02

    Free up this item for another volunteer.

     
  • Chris Marshall

    Chris Marshall - 2013-01-02
    • assigned_to: marshallch --> nobody
     

Log in to post a comment.