/*
 * Copyright (c) 2011 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup tcp
 * @{
 */

/**
 * @file Sequence number computations
 */

#include <assert.h>
#include <bool.h>
#include <sys/types.h>
#include "seq_no.h"
#include "tcp_type.h"

/** a <= b < c modulo sequence space */
static bool seq_no_le_lt(uint32_t a, uint32_t b, uint32_t c)
{
	if (a <= c) {
		return (a <= b) && (b < c);
	} else {
		return (b < c) || (a <= b);
	}
}

/** a < b <= c modulo sequence space */
static bool seq_no_lt_le(uint32_t a, uint32_t b, uint32_t c)
{
	if (a <= c) {
		return (a < b) && (b <= c);
	} else {
		return (b <= c) || (a < b);
	}
}

/** Determine wheter ack is acceptable (new acknowledgement) */
bool seq_no_ack_acceptable(tcp_conn_t *conn, uint32_t seg_ack)
{
	/* SND.UNA < SEG.ACK <= SND.NXT */
	return seq_no_lt_le(conn->snd_una, seg_ack, conn->snd_nxt);
}

/** Determine wheter ack is duplicate.
 *
 * ACK is duplicate if it refers to a sequence number that has
 * aleady been acked (SEG.ACK <= SND.UNA).
 */
bool seq_no_ack_duplicate(tcp_conn_t *conn, uint32_t seg_ack)
{
	uint32_t diff;

	/*
	 * There does not seem to be a three-point comparison
	 * equivalent of SEG.ACK < SND.UNA. Thus we do it
	 * on a best-effort basis, based on the difference.
	 * [-2^31, 0) means less-than, 0 means equal, [0, 2^31)
	 * means greater-than. Less-than or equal means duplicate.
	 */
	diff = seg_ack - conn->snd_una;
	return diff == 0 || (diff & (0x1 << 31)) != 0;
}

/** Determine if sequence number is in receive window. */
bool seq_no_in_rcv_wnd(tcp_conn_t *conn, uint32_t sn)
{
	return seq_no_le_lt(conn->rcv_nxt, sn, conn->rcv_nxt + conn->rcv_wnd);
}

/** Determine segment has new window update.
 *
 * Window update is new if either SND.WL1 < SEG.SEQ or
 * (SND.WL1 = SEG.SEQ and SND.WL2 <= SEG.ACK).
 */
bool seq_no_new_wnd_update(tcp_conn_t *conn, tcp_segment_t *seg)
{
	bool n_seq, n_ack;

	assert(seq_no_segment_acceptable(conn, seg));

	/*
	 * We make use of the fact that the peer should not ACK anything
	 * beyond our send window (we surely haven't sent that yet)
	 * as we should have filtered those acks out.
	 * We use SND.UNA+SND.WND as the third point of comparison.
	 */

	n_seq = seq_no_lt_le(conn->snd_wl1, seg->seq,
	    conn->snd_una + conn->snd_wnd);

	n_ack = conn->snd_wl1 == seg->seq &&
	    seq_no_le_lt(conn->snd_wl2, seg->ack,
	    conn->snd_una + conn->snd_wnd + 1);

	return n_seq || n_ack;
}

/** Determine if segment is ready for processing.
 *
 * Assuming segment is acceptable, a segment is ready if it intersects
 * RCV.NXT, that is we can process it immediately.
 */
bool seq_no_segment_ready(tcp_conn_t *conn, tcp_segment_t *seg)
{
	assert(seq_no_segment_acceptable(conn, seg));

	return seq_no_le_lt(seg->seq, conn->rcv_nxt, seg->seq + seg->len + 1);
}

/** Determine whether segment is fully acked */
bool seq_no_segment_acked(tcp_conn_t *conn, tcp_segment_t *seg, uint32_t ack)
{
	assert(seg->len > 0);
	return seq_no_lt_le(seg->seq, seg->seq + seg->len, ack);
}

/** Determine whether initial SYN is acked */
bool seq_no_syn_acked(tcp_conn_t *conn)
{
	return seq_no_lt_le(conn->iss, conn->snd_una, conn->snd_nxt);
}

/** Determine whether segment overlaps the receive window */
bool seq_no_segment_acceptable(tcp_conn_t *conn, tcp_segment_t *seg)
{
	bool b_in, e_in;

	b_in = seq_no_le_lt(conn->rcv_nxt, seg->seq, conn->rcv_nxt
	    + conn->rcv_wnd);

	e_in = seq_no_le_lt(conn->rcv_nxt, seg->seq + seg->len - 1,
	    conn->rcv_nxt + conn->rcv_wnd);

	if (seg->len == 0 && conn->rcv_wnd == 0) {
		return seg->seq == conn->rcv_nxt;
	} else if (seg->len == 0 && conn->rcv_wnd != 0) {
		return b_in;
	} else if (seg->len > 0 && conn->rcv_wnd == 0) {
		return false;
	} else {
		return b_in || e_in;
	}
}

/** Determine size that control bits occupy in sequence space. */
uint32_t seq_no_control_len(tcp_control_t ctrl)
{
	uint32_t len = 0;

	if ((ctrl & CTL_SYN) != 0)
		++len;

	if ((ctrl & CTL_FIN) != 0)
		++len;

	return len;
}

/** Calculate the amount of trim needed to fit segment in receive window. */
void seq_no_seg_trim_calc(tcp_conn_t *conn, tcp_segment_t *seg,
    uint32_t *left, uint32_t *right)
{
	assert(seq_no_segment_acceptable(conn, seg));

	/*
	 * If RCV.NXT is between SEG.SEQ and RCV.NXT+RCV.WND, then
	 * left trim amount is positive
	 */
	if (seq_no_lt_le(seg->seq, conn->rcv_nxt,
	    conn->rcv_nxt + conn->rcv_wnd)) {
		*left = conn->rcv_nxt - seg->seq;
	} else {
		*left = 0;
	}

	/*
	 * If SEG.SEQ+SEG.LEN is between SEG.SEQ and RCV.NXT+RCV.WND,
	 * then right trim is zero.
	 */
	if (seq_no_lt_le(seg->seq - 1, seg->seq + seg->len,
	    conn->rcv_nxt + conn->rcv_wnd)) {
		*right = 0;
	} else {
		*right = (seg->seq + seg->len) -
		    (conn->rcv_nxt + conn->rcv_wnd);
	}
}

/** Segment order comparison.
 *
 * Compare sequence order of two acceptable segments.
 *
 * @param conn		Connection
 * @param sa		Segment A
 * @param sb		Segment B
 *
 * @return		-1, 0, 1, resp. if A < B, A == B, A > B in terms
 *			of sequence order of the beginning of the segment.
 */
int seq_no_seg_cmp(tcp_conn_t *conn, tcp_segment_t *sa, tcp_segment_t *sb)
{
	assert(seq_no_segment_acceptable(conn, sa));
	assert(seq_no_segment_acceptable(conn, sb));

	if (seq_no_lt_le(sa->seq, sb->seq, conn->rcv_nxt + conn->rcv_wnd))
		return -1;

	if (seq_no_lt_le(sb->seq, sa->seq, conn->rcv_nxt + conn->rcv_wnd))
		return +1;

	assert(sa->seq == sb->seq);
	return 0;
}

/**
 * @}
 */