From a8b95ce6ed5e84d34748ecdd0ff1db4d03377cf0 Mon Sep 17 00:00:00 2001
From: "Wladimir J. van der Laan" <laanwj@gmail.com>
Date: Wed, 28 Sep 2011 21:35:58 +0200
Subject: use median filter for peer-reported reported number of blocks - fixes
 problem that one misconfigured or malicious node can mess up progress bar -
 implementation in src/util.h - testcase in src/test/util_tests.cpp

---
 src/util.h | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)

(limited to 'src/util.h')

diff --git a/src/util.h b/src/util.h
index fabcaf9303..290195cbfa 100644
--- a/src/util.h
+++ b/src/util.h
@@ -565,6 +565,50 @@ inline uint160 Hash160(const std::vector<unsigned char>& vch)
 }
 
 
+// Median filter over a stream of values
+// Returns the median of the last N numbers
+template <typename T> class CMedianFilter
+{
+private:
+    std::vector<T> vValues;
+    std::vector<T> vSorted;
+    int nSize;
+public:
+    CMedianFilter(int size, T initial_value):
+        nSize(size)
+    {
+        vValues.reserve(size);
+        vValues.push_back(initial_value);
+        vSorted = vValues;
+    }
+    
+    void input(T value)
+    {
+        if(vValues.size() == nSize)
+        {
+            vValues.erase(vValues.begin());
+        }
+        vValues.push_back(value);
+
+        vSorted.resize(vValues.size());
+        std::copy(vValues.begin(), vValues.end(), vSorted.begin());
+        std::sort(vSorted.begin(), vSorted.end());
+    }
+
+    T median() const
+    {
+        int size = vSorted.size();
+        if(size & 1) // Odd number of elements
+        {
+            return vSorted[size/2];
+        }
+        else // Even number of elements
+        {
+            return (vSorted[size/2-1] + vSorted[size/2]) / 2;
+        }
+    }
+};
+
 
 
 
-- 
cgit v1.2.3


From 20091df725e56376f6df0f71d19c63a34a5bf71d Mon Sep 17 00:00:00 2001
From: "Wladimir J. van der Laan" <laanwj@gmail.com>
Date: Thu, 29 Sep 2011 17:17:42 +0200
Subject: Add assertion size>0 to MedianFilter

---
 src/util.h | 1 +
 1 file changed, 1 insertion(+)

(limited to 'src/util.h')

diff --git a/src/util.h b/src/util.h
index 97d638c93e..60e99431b1 100644
--- a/src/util.h
+++ b/src/util.h
@@ -599,6 +599,7 @@ public:
     T median() const
     {
         int size = vSorted.size();
+        assert(size>0);
         if(size & 1) // Odd number of elements
         {
             return vSorted[size/2];
-- 
cgit v1.2.3