/*-GNU-GPL-BEGIN-*
nepim - network pipemeter
Copyright (C) 2005 Everton da Silva Marques

nepim is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

nepim 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 nepim; see the file COPYING.  If not, write to
the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.
*-GNU-GPL-END-*/

/* $Id: win.c,v 1.9 2005/09/30 11:55:40 evertonm Exp $ */

#include <stdio.h>
#include <assert.h>

#include "win.h"

void nepim_win_init(nepim_win_t *win, uint32_t max_size)
{
  assert(max_size > 0);
  
  nepim_bit_init(&win->bit_set, max_size);

  win->seq_expect       = 0;
  win->highest_seen_seq = 0;
  win->max_size         = max_size;
}

void nepim_win_del(nepim_win_t *win)
{
  nepim_bit_del(&win->bit_set);
}

static int ring_interval(uint32_t begin, uint32_t past_end, uint32_t i)
{
  if (begin <= past_end)
    return (i >= begin) && (i < past_end);

  return (i >= begin) || (i < past_end);
}

static int strict_ring_interval(uint32_t max, uint32_t begin, uint32_t past_end, uint32_t i)
{
  assert(begin < max);
  assert(past_end < max);
  assert(i < max);

  return ring_interval(begin, past_end, i);
}

static void seen_seq(nepim_win_t *win, uint32_t seq)
{
  long long distance = win->highest_seen_seq;
  distance -= seq;
  if (distance < 0)
    distance = -distance;

  /* seq wrapped? */
  if (distance > (1 << 31)) {
    win->highest_seen_seq = seq;
    return;
  }

  if (seq > win->highest_seen_seq)
    win->highest_seen_seq = seq;
}

#define NEPIM_WIN_PAST_MARK(seq, max) (((seq) + ((max) >> 1)) % (max))
#define NEPIM_WIN_LOSS_MARK(seq, max) (((seq) + ((max) >> 2)) % (max))

void nepim_win_add(nepim_win_t *win, uint32_t seq, int *lost, int *dup)
{
  int mod_seq;
  int mod_expect;
  int mod_past_mark;
  int mod_loss_mark;

  assert(lost);
  assert(dup);
  assert(*lost >= 0);
  assert(*dup >= 0);

  seen_seq(win, seq);

  mod_seq       = seq % win->max_size;
  mod_expect    = win->seq_expect % win->max_size;
  mod_past_mark = NEPIM_WIN_PAST_MARK(win->seq_expect, win->max_size);
  mod_loss_mark = NEPIM_WIN_LOSS_MARK(win->seq_expect, win->max_size);

  assert(!nepim_bit_isset(&win->bit_set, mod_expect));

  /* Expected seq ? */
  if (mod_seq == mod_expect) {
    for (++win->seq_expect;
	 nepim_bit_isset(&win->bit_set, win->seq_expect % win->max_size); 
	 ++win->seq_expect) {
      nepim_bit_clear(&win->bit_set, win->seq_expect % win->max_size);
    }

    return;
  }

  /* Future seq ? -> check possible duplicate, mark as seen */
  if (strict_ring_interval(win->max_size, mod_expect, mod_loss_mark, mod_seq)) {

    if (nepim_bit_isset(&win->bit_set, mod_seq))
      ++*lost;

    nepim_bit_set(&win->bit_set, mod_seq);

    return;
  }

  /* Far future seq ? -> push "expect" mark forward while registering losses */
  if (strict_ring_interval(win->max_size, mod_loss_mark, mod_past_mark, mod_seq)) {

    int step = win->max_size >> 3;
    int mod_seq_1 = (mod_seq + step) % win->max_size;

    assert(step > 0);

    nepim_bit_set(&win->bit_set, mod_seq);

    for (; !strict_ring_interval(win->max_size,
				 win->seq_expect % win->max_size,
				 NEPIM_WIN_LOSS_MARK(win->seq_expect, win->max_size),
				 mod_seq_1);
	 ++win->seq_expect) {

      int mod_exp = win->seq_expect % win->max_size;
      
      if (nepim_bit_isset(&win->bit_set, mod_exp))
	nepim_bit_clear(&win->bit_set, mod_exp);
      else
	++*lost;
    }

    /* find first non-received position */
    for (; nepim_bit_isset(&win->bit_set, win->seq_expect % win->max_size);
	 ++win->seq_expect) {
      nepim_bit_clear(&win->bit_set, win->seq_expect % win->max_size);
    }

    assert(!nepim_bit_isset(&win->bit_set, win->seq_expect % win->max_size));
    
    return;
  }

  /* Past seq? -> register as duplicate */

  assert(strict_ring_interval(win->max_size, mod_past_mark, mod_expect, mod_seq));

  assert(!nepim_bit_isset(&win->bit_set, mod_seq));

  ++*dup;
}

int nepim_win_extract_loss(nepim_win_t *win)
{
  int mod_exp = win->seq_expect % win->max_size;
  int mod_seq = win->highest_seen_seq % win->max_size;
  int mod_loss_mark = NEPIM_WIN_LOSS_MARK(win->highest_seen_seq, win->max_size);
  int lost = 0;

  assert(strict_ring_interval(win->max_size, mod_exp, mod_loss_mark, mod_seq));

  for (; mod_exp != mod_seq; ++mod_exp, mod_exp %= win->max_size) {
    if (!nepim_bit_isset(&win->bit_set, mod_exp)) {
      ++lost;
#if 0
      fprintf(stderr, "LOSS: exp=%d seq=%d loss=%d\n", mod_exp, mod_seq, lost);
#endif
    }
  }

  return lost;
}