From b979b0be8ac5623ff3f4c3b5a5331edd953aa0bb Mon Sep 17 00:00:00 2001
From: Christian Pointner <equinox@anytun.org>
Date: Mon, 12 Jan 2009 23:39:51 +0000
Subject: ported uAnytun sequence window to anytun

---
 src/seqWindow.cpp | 118 +++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 90 insertions(+), 28 deletions(-)

(limited to 'src/seqWindow.cpp')

diff --git a/src/seqWindow.cpp b/src/seqWindow.cpp
index 1a36392..1ddd3ca 100644
--- a/src/seqWindow.cpp
+++ b/src/seqWindow.cpp
@@ -34,55 +34,118 @@
 
 #include "seqWindow.h"
 
-SeqWindow::SeqWindow(window_size_t w) : window_size_(w)
+SeqWindowElement::SeqWindowElement()
 {
+  window_ = NULL;
+  pos_ = 0;
+  max_ = 0;
 }
 
-SeqWindow::~SeqWindow()
+SeqWindowElement::~SeqWindowElement()
 {
+  if(window_)
+    delete[] window_;
 }
 
-SeqWindow::SeqDeque::size_type SeqWindow::getLength(sender_id_t sender)
+void SeqWindowElement::init(window_size_t w, seq_nr_t m)
 {
-  Lock lock(mutex_);
-  SenderMap::const_iterator s = sender_.find(sender);
-  if(s == sender_.end())
-    return 0;
+  if(window_)
+    delete[] window_;
+  window_ = new u_int8_t[w];
+  memset(window_, 0, w); 
+  pos_ = 0;
+  max_ = m;
+  window_[pos_] = 1;
+}
 
-  return s->second.size();
+SeqWindow::SeqWindow(window_size_t w) : window_size_(w)
+{
 }
 
-bool SeqWindow::hasSeqNr(sender_id_t sender, seq_nr_t seq)
+SeqWindow::~SeqWindow()
+{
+}
+
+bool SeqWindow::checkAndAdd(sender_id_t sender, seq_nr_t seq_nr)
 {
   Lock lock(mutex_);
   if (!window_size_)
     return false;
-  SenderMap::const_iterator s = sender_.find(sender);
-  if(s == sender_.end())
+
+  SenderMap::iterator s = sender_.find(sender);
+  if(s == sender_.end()) {
+    sender_[sender].init(window_size_, seq_nr);
     return false;
+  }
 
-  SeqDeque::const_iterator it;
-  for(it = s->second.begin(); it != s->second.end(); it++)
-    if(*it == seq)
-      return true;
+  int shifted = 0;
+  if(s->second.max_ < window_size_) {
+    s->second.max_ += SEQ_NR_MAX/2;
+    seq_nr += SEQ_NR_MAX/2;
+    shifted = 1;
+  }
+  else if(s->second.max_ > (SEQ_NR_MAX - window_size_)) {
+    s->second.max_ -= SEQ_NR_MAX/2;
+    seq_nr -= SEQ_NR_MAX/2;
+    shifted = 2;
+  }
   
-  return false;
-}
-
-void SeqWindow::addSeqNr(sender_id_t sender, seq_nr_t seq)
-{
-  Lock lock(mutex_);
-  if (!window_size_)
-    return;
-  if(sender_[sender].size() >= window_size_)
-    sender_[sender].pop_front();
-  sender_[sender].push_back(seq);
+  seq_nr_t min = s->second.max_ - window_size_ + 1;
+  if(seq_nr < min || seq_nr == s->second.max_) {
+    if(shifted == 1)
+      s->second.max_ -= SEQ_NR_MAX/2;
+    else if(shifted == 2)
+      s->second.max_ += SEQ_NR_MAX/2;
+    return true;
+  }
+  
+  if(seq_nr > s->second.max_) {
+    seq_nr_t diff = seq_nr - s->second.max_;
+    if(diff >= window_size_)
+      diff = window_size_;
+    
+    window_size_t new_pos = s->second.pos_ + diff;
+    
+    if(new_pos >= window_size_) {
+      new_pos -= window_size_;
+      
+      if(s->second.pos_ < window_size_ - 1)
+        memset(&(s->second.window_[s->second.pos_ + 1]), 0, window_size_ - s->second.pos_ - 1);
+      
+      memset(s->second.window_, 0, new_pos);
+    }
+    else {
+      memset(&(s->second.window_[s->second.pos_ + 1]), 0, diff);
+    }
+    s->second.pos_ = new_pos;
+    s->second.window_[s->second.pos_] = 1;
+    s->second.max_ = seq_nr;
+    
+    if(shifted == 1)
+      s->second.max_ -= SEQ_NR_MAX/2;
+    else if(shifted == 2)
+      s->second.max_ += SEQ_NR_MAX/2;
+    
+    return false;
+  }
+  
+  seq_nr_t diff = s->second.max_ - seq_nr;
+  window_size_t pos = diff > s->second.pos_ ? s->second.pos_ + window_size_ : s->second.pos_; 
+  pos -= diff;
+  
+  if(shifted == 1)
+    s->second.max_ -= SEQ_NR_MAX/2;
+  else if(shifted == 2)
+    s->second.max_ += SEQ_NR_MAX/2;
+  
+  int ret = s->second.window_[pos];
+  s->second.window_[pos] = 1;
+  return ret;
 }
 
 void SeqWindow::clear(sender_id_t sender)
 {
   Lock lock(mutex_);
-  sender_[sender].clear();
   sender_.erase(sender);
 }
 
@@ -91,4 +154,3 @@ void SeqWindow::clear()
   Lock lock(mutex_);
   sender_.clear();
 }
-
-- 
cgit v1.2.3