lcs: fixed out-of-bounds array access (MBC #1007)mbc1007_pohly

Found by valgrind: the cost function is called with indices just
outside the array, causing it to read unitialized (and potentially
unavailable) memory.

Calling it like this is intentional, as the original LCS algorithm
works like that. The cost function has to map access outside of the
array to the cost at the boundaries. It also has to handle empty
arrays.

1 files changed, 15 insertions, 1 deletions

diff --git a/src/syncevo/lcs.h b/src/syncevo/lcs.h
index 084b849a..d7b02451 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; }
 };