http://bugs.meego.com/show_bug.cgi?id=1007
--- Comment #8 from pohly <[email protected]> 2010-05-26 08:27:58 PDT --- (In reply to comment #6) > > For this issue, I find the root cause: read over the size of the buffer. > > In lcs.h line 196: > > class accessor { > > static C cost(const T &b, ssize_t start, size_t end) { > > return b[end].second - (start == -1 ? 0 : b[start].second); > > } > > } > > for(int j = 0; j <=b.size(); j++) > > 196 C cost_left = sub[i][j-1].cost += access.cost(b, j-1, > > j); > > > > access.cost(b, j-1, j) will read b[j] and j may equal the size of b, so this > > will cause reading an invalid value > The fix is below. The reason is that sub[i][j] is calculated for a[i-1] and > b[j-1]. Thus the new cost is a[i-1] - a[i-2]. Right? I agree with your root cause analysis, but not with this solution. I believe it leads to accessing the cost value at index #-2, which falls of the lower end of the array. IMHO the cost function was called with correct indices. Basically both one before array and one after the end are valid and should give the same result as the indices just inside the array. The implementation only handled index -1, but not index == size(). It also did not work for empty arrays. Here's a more complete solution, committed to branch mbc1007_pohly. Yongsheng, do you agree? diff --git a/src/syncevo/lcs.h b/src/syncevo/lcs.h index 084b849..d7b0245 100644 --- a/src/syncevo/lcs.h +++ b/src/syncevo/lcs.h @@ -75,7 +75,21 @@ public: typedef typename T::value_type::first_type F; typedef typename T::value_type::second_type C; - static C cost(const T &a, ssize_t start, size_t end) { return a[end].second - (start == -1 ? 0 : a[start].second); } + /** + * @param a container holding sequence of items as passed to lcs() + * @param start index of first item in the gap, may be -1 + * @param end index of the last item in the gap, may be one beyond end of sequence, always >= start + * @return cost 0 for start == end, > 0 for start < end + */ + static C cost(const T &a, ssize_t start, size_t end) { + return a.empty() ? 0 : + ((end >= a.size() ? a[a.size() - 1].second : a[end].second) - + (start < 0 ? a[0].second : a[start].second)); + } + /** + * @param index valid index (>= 0, < a.size()) + * @return entry at index + */ static const F &entry_at(const T &a, size_t index) { return a[index].first; } }; -- Configure bugmail: http://bugs.meego.com/userprefs.cgi?tab=email ------- You are receiving this mail because: ------- You are watching someone on the CC list of the bug. _______________________________________________ Syncevolution-issues mailing list [email protected] http://lists.syncevolution.org/listinfo/syncevolution-issues
