check-only for sequence window is done (needs more testing)

2 files changed, 184 insertions, 23 deletions

diff --git a/satp/sequence-window.go b/satp/sequence-window.go
index 4c53ee5..c527f4e 100644
--- a/satp/sequence-window.go
+++ b/satp/sequence-window.go
@@ -32,9 +32,29 @@ package satp
 
 import (
 	"errors"
+	"fmt"
 	"sync"
 )
 
+// calculate distance of seq from top and whether it is less than top
+func seqDistance(top, seq uint32) (less bool, distance uint32) {
+	d := int32(seq - top)
+	if d < 0 {
+		return true, uint32(-d)
+	}
+	return false, uint32(d)
+}
+
+// index will only be valid if seq is inside the window
+// aka: top >= seq && (top-seq) <= window_size
+//        (with both conditions compensated for value wrap around)
+func bitSliceIndex(top, seq uint32) int {
+	if top > seq {
+		return int(top/32) - int(seq/32)
+	}
+	return int(top/32) + int(1<<(32-5)) - int(seq/32)
+}
+
 type SequenceWindow struct {
 	size int
 	head uint64
@@ -42,39 +62,96 @@ type SequenceWindow struct {
 	mtx  *sync.RWMutex
 }
 
+func octet2str(octet uint8) (str string) {
+	for i := 0; i < 8; i++ {
+		if (octet & 0x80) == 0 {
+			str += "."
+		} else {
+			str += "x"
+		}
+		octet <<= 1
+	}
+	return
+}
+
+func octet2str4(octets uint32) (str string) {
+	str += octet2str(uint8(octets>>24)) + " "
+	str += octet2str(uint8(octets>>16)) + " "
+	str += octet2str(uint8(octets>>8)) + " "
+	str += octet2str(uint8(octets))
+	return
+}
+
+func (w *SequenceWindow) String() string {
+	w.mtx.RLock()
+	defer w.mtx.RUnlock()
+
+	str := fmt.Sprintf("%d/[%d]{", w.top(), w.size)
+	str += octet2str4(w.bitSlice(0))
+	for i := 1; i <= len(w.body); i++ {
+		str += "  " + octet2str4(w.bitSlice(i))
+	}
+	return str + "}"
+}
+
 func (w *SequenceWindow) Size() int {
 	return w.size
 }
 
+func (w *SequenceWindow) bitSlice(idx int) uint32 {
+	if idx <= 0 {
+		// return uint32(atomic.LoadUint64(&w.head))
+		return uint32(w.head)
+	}
+	// return atomic.LoadUint32(&w.body[idx-1])
+	return w.body[idx-1]
+}
+
+func (w *SequenceWindow) top() uint32 {
+	// return uint32(atomic.LoadUint64(&w.head) >> 32)
+	return uint32(w.head >> 32)
+}
+
 func (w *SequenceWindow) Top() uint32 {
 	w.mtx.RLock()
 	defer w.mtx.RUnlock()
-	// return uint32(atomic.LoadUint64(&w.head) >> 32)
-	return uint32(w.head >> 32)
+	return w.top()
 }
 
-func (w *SequenceWindow) Check(sequenceNumber uint32) (bool, error) {
+func (w *SequenceWindow) Check(sequenceNumber uint32) bool {
 	if w.size <= 0 {
-		return false, nil
+		return true
 	}
 	w.mtx.RLock()
 	defer w.mtx.RUnlock()
-	// TODO: implement this
-	return false, nil
-}
 
-func (w *SequenceWindow) CheckAndSet(sequenceNumber uint32) (bool, error) {
-	if w.size <= 0 {
-		return false, nil
+	top := w.top()
+	lt, d := seqDistance(top, sequenceNumber)
+	if lt {
+		if d > uint32(w.size) {
+			return false
+		}
+		bits := w.bitSlice(bitSliceIndex(top, sequenceNumber))
+		return ((bits >> (sequenceNumber % 32)) & 1) != 1
 	}
-	w.mtx.Lock()
-	defer w.mtx.Unlock()
-	// TODO: implement this
-	return false, nil
+	return true
 }
 
+// func (w *SequenceWindow) advanceTop(sequenceNumber uint32) {
+// }
+
+// func (w *SequenceWindow) CheckAndSet(sequenceNumber uint32) bool {
+// 	if w.size <= 0 {
+// 		return true
+// 	}
+// 	w.mtx.Lock()
+// 	defer w.mtx.Unlock()
+// 	// TODO: implement this
+// 	return false
+// }
+
 func NewSequenceWindow(size int, top uint32) (w *SequenceWindow, err error) {
-	if size < 0 {
+	if size < 0 || size > int(^uint32(0)/4) {
 		return nil, errors.New("invalid sequence window size")
 	}
 	w = &SequenceWindow{size: size, head: uint64(top) << 32, mtx: &sync.RWMutex{}}
diff --git a/satp/sequence-window_test.go b/satp/sequence-window_test.go
index 2f38a23..097cacd 100644
--- a/satp/sequence-window_test.go
+++ b/satp/sequence-window_test.go
@@ -34,6 +34,47 @@ import (
 	"testing"
 )
 
+func TestSequenceWindowDistance(t *testing.T) {
+	testvectors := []struct {
+		top      uint32
+		seq      uint32
+		less     bool
+		distance uint32
+	}{
+		{0, 0, false, 0},
+		{1, 0, true, 1},
+		{1, 1, false, 0},
+		{10, 0, true, 10},
+		{0, 1, false, 1},
+		{0, 10, false, 10},
+		{10, 10, false, 0},
+		{10, 11, false, 1},
+		{10, 12, false, 2},
+		{0, ^uint32(0), true, 1},
+		{10, ^uint32(0), true, 11},
+		{^uint32(0), ^uint32(0), false, 0},
+		{^uint32(0), 0, false, 1},
+		{((^uint32(0)) / 2) - 1, 0, true, 2147483646},
+		{((^uint32(0)) / 2), 0, true, 2147483647},
+		{((^uint32(0)) / 2) + 1, 0, true, 2147483648},
+		{((^uint32(0)) / 2) + 1, 1, true, 2147483647},
+		{((^uint32(0)) / 2) + 1, 18, true, 2147483630},
+		{((^uint32(0)) / 2) + 1, ^uint32(0), false, 2147483647},
+		{((^uint32(0)) / 2) + 2, 0, false, 2147483647},
+	}
+
+	for _, vector := range testvectors {
+		less, distance := seqDistance(vector.top, vector.seq)
+		if less != vector.less {
+			t.Fatalf("top=%d > seq=%d is %v but should be %v", vector.top, vector.seq, less, vector.less)
+		}
+
+		if distance != vector.distance {
+			t.Fatalf("distance between top=%d and seq=%d is %d but should be %d", vector.top, vector.seq, distance, vector.distance)
+		}
+	}
+}
+
 func TestSequenceWindowNew(t *testing.T) {
 	testvectors := []struct {
 		size    int
@@ -56,14 +97,16 @@ func TestSequenceWindowNew(t *testing.T) {
 		{63, 0, 0, 2, true},
 		{64, 0, 0, 2, true},
 		{65, 0, 0, 3, true},
-		{100, 0, 0, 4, true},
-		{100, 0xFFFF0000, 0xFFFF000000000000, 4, true},
-		{100, 0xFFFF0001, 0xFFFF000100000001, 4, true},
-		{100, 0xFFFF0002, 0xFFFF000200000003, 4, true},
-		{100, 0xFFFF0003, 0xFFFF000300000007, 4, true},
-		{100, 0xFFFF0004, 0xFFFF00040000000F, 4, true},
-		{100, 0xFFFF0005, 0xFFFF00050000001F, 4, true},
-		{100, 0xAAAA5555, 0xAAAA5555001FFFFF, 4, true},
+		{80, 0, 0, 3, true},
+		{80, 0xFFFF0000, 0xFFFF000000000000, 3, true},
+		{80, 0xFFFF0001, 0xFFFF000100000001, 3, true},
+		{80, 0xFFFF0002, 0xFFFF000200000003, 3, true},
+		{80, 0xFFFF0003, 0xFFFF000300000007, 3, true},
+		{80, 0xFFFF0004, 0xFFFF00040000000F, 3, true},
+		{80, 0xFFFF0005, 0xFFFF00050000001F, 3, true},
+		{80, 0xAAAA5555, 0xAAAA5555001FFFFF, 3, true},
+		{96, 0, 0, 3, true},
+		{97, 0, 0, 4, true},
 	}
 
 	for _, vector := range testvectors {
@@ -100,5 +143,46 @@ func TestSequenceWindowNew(t *testing.T) {
 			}
 		}
 	}
+}
+
+func TestSequenceWindowCheck(t *testing.T) {
+	testvectors := []struct {
+		size   int
+		top    uint32
+		seq    uint32
+		result bool
+	}{
+		{0, 0, 0, true},
+		{0, 0, ^uint32(0), true},
+		{0, 17, 12, true},
+		{10, 17, 12, false},
+		{10, 17, 17, true},
+		{10, 17, 18, true},
+		{10, 0, ^uint32(0), false},
+		{32, 0, 0, true},
+		{32, 0, 12, true},
+		{32, 13, 12, false},
+		{32, 100, 12, false},
+		{32, 33, 12, false},
+		{32, 33, 32, false},
+		{64, 36, 0, false},
+		{64, 36, 12, false},
+		{64, 36, ^uint32(0), false},
+		{64, 100, ^uint32(0), false},
+		{64, 100, 96, false},
+		{64, 100, 95, false},
+		{64, 100, 63, false},
+		{64, 100, 110, true},
+	}
 
+	for _, vector := range testvectors {
+		w, err := NewSequenceWindow(vector.size, vector.top)
+		if err != nil {
+			t.Fatal("unexpected error:", err)
+		}
+		result := w.Check(vector.seq)
+		if result != vector.result {
+			t.Fatalf("checking %d against %s returned %v but should be %v", vector.seq, w, result, vector.result)
+		}
+	}
 }