#12371: The graph_decompositions/ code seems to have bounds issues
----------------------------+-----------------------------------------------
Reporter: Snark | Owner: jason, ncohen, rlm
Type: defect | Status: needs_work
Priority: major | Milestone: sage-5.0
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by Snark):
* status: needs_review => needs_work
Old description:
> That makes the code non-portable ; the patch I provide adds either signed
> or unsigned in each place, which makes the ARM platform pass the tests
> happily.
>
> Notice that it does fix the current problem but there are still two
> problems with the code:
> 1. in vertex_separation.pyx, we still have "minimums[i] = n" which is an
> unsigned char getting an unsigned int ;
> 2. in vertex_separation.pyx, we still have "tmp_count = <unsigned char>
> popcount(i)", where popcount returns an "int".
New description:
That makes the code non-portable ; the patch I provide adds either signed
or unsigned in each place, which makes the ARM platform pass the tests
happily.
Notice that it does fix the current problem but there are still two
problems with the code:
1. in vertex_separation.pyx, we still have "minimums[i] = n" which is an
unsigned char getting an unsigned int ;
1. in vertex_separation.pyx, we still have "tmp_count = <unsigned char>
popcount(i)", where popcount returns an "int".
--
Comment:
Eh, this patch is basically mine with s/unsigned char/uint8_t/g and
s/signed char/int8_t/g, so it's no surprise it passes the tests.
But it also means it has all the problems of the original code, plus the
ones of my patch.
When I read the patched code, I see the following (potential or real)
problems :
1. there are loops on "int" counters from 0 to a cardinal (they should be
the same type as the cardinal);
1. the implementation of pop_count uses magical values which seem to
assume a definite sizeof(int);
1. there are "int" which are in fact bit arrays ; it should probably be
"unsigned int" ;
1. there are arrays which are indexed by above, so I'm not sure there is
no risk there (though there is a test to bail out in case of problems,
8*sizeof(int)).
If I remember well, the current doctests just use graphs of cardinal up to
8, so we can only detect signed/unsigned issues, but not other ones.
I'll try to work on a bigger patch ; I'm updating the summary of that
ticket to reflect that much more ambitious scope.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12371#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
