[Boost-bugs] [Boost C++ Libraries] #5050: Crash inside 'accumulators::median' for p_square_cumulative_distribution

Subject: [Boost-bugs] [Boost C++ Libraries] #5050: Crash inside 'accumulators::median' for p_square_cumulative_distribution
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-01-07 15:39:57

#5050: Crash inside 'accumulators::median' for p_square_cumulative_distribution
------------------------------------------------------+---------------------
 Reporter:  Jeevaka Dassanayake <jeevaka0@…>          |       Owner:  eric_niebler
     Type:  Bugs                                      |      Status:  new         
Milestone:  To Be Determined                          |   Component:  accumulator 
  Version:  Boost 1.45.0                              |    Severity:  Problem     
 Keywords:                                            |  
------------------------------------------------------+---------------------
 Code to reproduce is below. Also I looked at the code in median.hpp and
 commented on the relevant lines below.

 accumulator_set<double, stats<tag::p_square_cumulative_distribution,
 tag::median(with_p_square_cumulative_distribution)>>
 m_HistogramAccumulator(
 tag::p_square_cumulative_distribution::num_cells = 5 );

 m_HistogramAccumulator( 1566 );

 m_HistogramAccumulator( 1345 );

 cout << accumulators::median( m_HistogramAccumulator ) << endl;

 ----
 median.hpp line 151 – 158 (boost 1_45_0):

 range_type histogram = p_square_cumulative_distribution(args);

 typename range_type::iterator it = histogram.begin();

 while (it->second < 0.5)

 {

    ++it;

 }

 float_type over = numeric::average(it->second - 0.5, it->second - (it -
 1)->second);

 this->median = it->first * over + (it + 1)->first * ( 1. - over );


 1) If the very first bin in the histogram has a density of 0.5 or more
 then the ‘while’ loop does not get executed at all and ‘it’ is still
 pointing to the ‘begin()’ when the code try to compute the local variable
 ‘over’. However this computation involves ‘(it – 1)’ and in this specific
 scenario it will try to decrement the iterator beyond ‘begin’ and access
 an element. This causes a crash.

 2) Also I suspect that there is a small computation bug unrelated to the
 crash in the last line. It is using ‘(it+1)’ instead of ‘(it-1)’ in the
 last line. It seems like it should interpolate between the current element
 and the previous one, but it is interpolating between the current element
 and the next one.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/5050>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.