From 664e03afd3850b68580f5c7cfe087ace07c50674 Mon Sep 17 00:00:00 2001 From: Christian Pointner Date: Wed, 31 Dec 2008 13:39:10 +0000 Subject: added sequence window --- src/seq_window.c | 223 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 223 insertions(+) create mode 100644 src/seq_window.c (limited to 'src/seq_window.c') diff --git a/src/seq_window.c b/src/seq_window.c new file mode 100644 index 0000000..f5c0bf8 --- /dev/null +++ b/src/seq_window.c @@ -0,0 +1,223 @@ +/* + * ľAnytun + * + * ľAnytun is a tiny implementation of SATP. Unlike Anytun which is a full + * featured implementation ľAnytun has no support for multiple connections + * or synchronisation. It is a small single threaded implementation intended + * to act as a client on small platforms. + * The secure anycast tunneling protocol (satp) defines a protocol used + * for communication between any combination of unicast and anycast + * tunnel endpoints. It has less protocol overhead than IPSec in Tunnel + * mode and allows tunneling of every ETHER TYPE protocol (e.g. + * ethernet, ip, arp ...). satp directly includes cryptography and + * message authentication based on the methodes used by SRTP. It is + * intended to deliver a generic, scaleable and secure solution for + * tunneling and relaying of packets of any protocol. + * + * + * Copyright (C) 2007-2008 Christian Pointner + * + * This file is part of ľAnytun. + * + * ľAnytun is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 3 as + * published by the Free Software Foundation. + * + * ľAnytun is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with ľAnytun. If not, see . + */ + +#include "datatypes.h" + +#include "seq_window.h" + +#include +#include + +#include + +void seq_win_init(seq_win_t** win, window_size_t size) +{ + if(!win) + return; + + *win = malloc(sizeof(seq_win_t)); + if(!*win) + return; + + (*win)->size_ = size; + (*win)->first_ = NULL; +} + +void seq_win_clear(seq_win_t** win) +{ + if(!win || !(*win)) + return; + + seq_win_element_t* ptr = (*win)->first_; + while(ptr) { + seq_win_element_t* to_free = ptr; + ptr = ptr->next_; + if(to_free->window_) + free(to_free->window_); + + free(to_free); + } + + free(*win); + *win = NULL; +} + +seq_win_element_t* seq_win_new_element(sender_id_t sender_id, seq_nr_t max, window_size_t size) +{ + if(!size) + return NULL; + + seq_win_element_t* e = malloc(sizeof(seq_win_element_t)); + if(!e) + return NULL; + + e->sender_id_ = sender_id; + e->max_ = max; + e->pos_ = 0; + e->window_ = malloc(sizeof(seq_nr_t)*size); + if(!e->window_) { + free(e); + return NULL; + } + memset(e->window_, 0, size); + e->window_[e->pos_] = 1; + e->next_ = NULL; + + return e; +} + +int seq_win_check_and_add(seq_win_t* win, sender_id_t sender_id, seq_nr_t seq_nr) +{ + if(!win) + return -1; + + if(!win->size_) + return 0; + + seq_win_element_t* ptr = win->first_; + while(ptr) { + if(ptr->sender_id_ == sender_id) { + + int shifted = 0; + if(ptr->max_ < win->size_) { + ptr->max_ += SEQ_NR_MAX/2; + seq_nr += SEQ_NR_MAX/2; + shifted = 1; + } + else if(ptr->max_ > (SEQ_NR_MAX - win->size_)) { + ptr->max_ -= SEQ_NR_MAX/2; + seq_nr -= SEQ_NR_MAX/2; + shifted = 2; + } + + seq_nr_t min = ptr->max_ - win->size_ + 1; + if(seq_nr < min || seq_nr == ptr->max_) { + if(shifted == 1) + ptr->max_ -= SEQ_NR_MAX/2; + else if(shifted == 2) + ptr->max_ += SEQ_NR_MAX/2; + return 1; + } + + if(seq_nr > ptr->max_) { + seq_nr_t diff = seq_nr - ptr->max_; + if(diff >= win->size_) + diff = win->size_; + + window_size_t new_pos = ptr->pos_ + diff; + + if(new_pos >= win->size_) { + new_pos -= win->size_; + + if(ptr->pos_ < win->size_ - 1) + memset(&(ptr->window_[ptr->pos_ + 1]), 0, win->size_ - ptr->pos_ - 1); + + memset(ptr->window_, 0, new_pos); + } + else { + memset(&(ptr->window_[ptr->pos_ + 1]), 0, diff); + } + ptr->pos_ = new_pos; + ptr->window_[ptr->pos_] = 1; + ptr->max_ = seq_nr; + + if(shifted == 1) + ptr->max_ -= SEQ_NR_MAX/2; + else if(shifted == 2) + ptr->max_ += SEQ_NR_MAX/2; + + return 0; + } + + seq_nr_t diff = ptr->max_ - seq_nr; + window_size_t pos = diff > ptr->pos_ ? ptr->pos_ + win->size_ : ptr->pos_; + pos -= diff; + + if(shifted == 1) + ptr->max_ -= SEQ_NR_MAX/2; + else if(shifted == 2) + ptr->max_ += SEQ_NR_MAX/2; + + int ret = ptr->window_[pos]; + ptr->window_[pos] = 1; + return ret; + } + ptr = ptr->next_; + } + if(!win->first_) { + win->first_ = seq_win_new_element(sender_id, seq_nr, win->size_); + if(!win->first_) + return -2; + } + else { + ptr = win->first_; + while(ptr->next_) + ptr = ptr->next_; + ptr->next_ = seq_win_new_element(sender_id, seq_nr, win->size_); + if(!ptr->next_) + return -2; + } + + return 0; +} + +void seq_win_print(seq_win_t* win) +{ + printf("Sequence Window:\n"); + + if(!win) + return; + + seq_win_element_t* ptr = win->first_; + while(ptr) { + printf(" [%u]: (%u)-", ptr->sender_id_, ptr->max_, ptr->pos_); + window_size_t i = ptr->pos_; + while(1) { + if(ptr->window_[i]) + printf("O"); + else + printf("."); + + if(i) + i--; + else + i = win->size_ - 1; + + if(i == ptr->pos_) + break; + } + printf("\n"); + ptr = ptr->next_; + } +} -- cgit v1.2.3