Index: uspace/srv/net/tcp/seq_no.c
===================================================================
--- uspace/srv/net/tcp/seq_no.c	(revision 0c37135e2c247d5596135d0f642dda1783ef2043)
+++ uspace/srv/net/tcp/seq_no.c	(revision 0c37135e2c247d5596135d0f642dda1783ef2043)
@@ -0,0 +1,243 @@
+/*
+ * 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;
+}
+
+/**
+ * @}
+ */
