//
// Copyright (c) 2017 anygone contributors (see AUTHORS file)
// 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.
//
// * Neither the name of anygone nor the names of its
//   contributors may be used to endorse or promote products derived from
//   this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 COPYRIGHT HOLDER OR CONTRIBUTORS 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.
//

package satp

import (
	"runtime"
	"sync"
	"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
		top     uint32
		head    uint64
		bodyLen int
		valid   bool
	}{
		{-1, 0, 0, 0, false},
		{0, 0, 0, 0, true},
		{1, 0, 0, 1, true},
		{10, 0, 0, 1, true},
		{10, 0x4, 0x40000000F, 1, true},
		{10, 0x12, 0x120003FFFF, 1, true},
		{32, 0, 0, 1, true},
		{32, 0x1F, 0x1F7FFFFFFF, 1, true},
		{32, 0x20, 0x2000000000, 1, true},
		{33, 0, 0, 2, true},
		{33, 1, 0x100000001, 2, true},
		{63, 0, 0, 2, true},
		{64, 0, 0, 2, true},
		{65, 0, 0, 3, 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 {
		w, err := NewSequenceWindow(vector.size, vector.top)
		if vector.valid {
			if err != nil {
				t.Fatal("unexpected error:", err)
			}
			if w.Size() != vector.size {
				t.Fatalf("sequence-window has wrong size, is: %d, should be %d", w.Size(), vector.size)
			}
			if w.Top() != vector.top {
				t.Fatalf("sequence-window(%d/%d) top value invalid, is: 0x%08X, should be 0x%08X", vector.size, vector.top, w.Top(), vector.top)
			}
			if w.head != vector.head {
				t.Fatalf("sequence-window(%d/%d) head invalid, is: 0x%016X, should be 0x%016X", vector.size, vector.top, w.head, vector.head)
			}
			bodyLen := len(w.body)
			if bodyLen != vector.bodyLen {
				t.Fatalf("sequence-window(%d/%d) body length has invalid length, is: %d, should be %d", vector.size, vector.top, bodyLen, vector.bodyLen)
			}
			isEmpty := true
			for _, v := range w.body {
				if v != 0xFFFFFFFF {
					isEmpty = false
				}
			}
			if !isEmpty {
				t.Fatalf("sequence-window(%d/%d) body not full, is: %v", vector.size, vector.top, w.body)
			}
		} else {
			if err == nil {
				t.Fatalf("creating sequence-window(%d/%d) should give an error", vector.size, vector.top)
			}
		}
	}
}

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)
		}
	}
}

func TestSequenceWindowCheckAndSet(t *testing.T) {
	testvectors := []struct {
		size   int
		top    uint32
		seqs   []uint32
		result bool
	}{
		{0, 0, []uint32{0, 1, 2, 3, 4}, true},
		{0, 0, []uint32{^uint32(0)}, true},
		{1, 0, []uint32{0, 1, 2, 3, 5}, true},
		{10, 0, []uint32{^uint32(0)}, false},
		{10, 20, []uint32{^uint32(0), 5, 9, 10, 12, 13}, false},
		{10, 20, []uint32{20, 23, 31, 32, 35}, true},
		{32, 0, []uint32{0, 1, 2, 3, 4}, true},
		{32, 10, []uint32{0, 1, 2, 3, 4}, false},
		{32, 10, []uint32{10, 11, 12, 13, 14}, true},
		{32, 0, []uint32{10, 17, 23, 0, 1, 18, 9, 8, 31}, true},
		{32, 30, []uint32{30, 31, 32, 33, 34}, true},
		{32, 0, []uint32{95, 100, 96, 97, 99, 98}, true},
		{50, 0, []uint32{31, 32, 35, 33, 34, 95}, true},
		{30, ^uint32(0) - 10, []uint32{0, 1, 2, 3, ^uint32(0), ^uint32(0) - 2}, true},
	}

	for _, vector := range testvectors {
		w, err := NewSequenceWindow(vector.size, vector.top)
		if err != nil {
			t.Fatal("unexpected error:", err)
		}
		t.Logf("--- %10d, %v", vector.top, w)
		for _, seq := range vector.seqs {
			result := w.CheckAndSet(seq)
			if result != vector.result {
				t.Fatalf("check-and-set %d on %s returned %v but should be %v", seq, w, result, vector.result)
			}
			t.Logf("chk %10d, %v", seq, w)
		}
	}
}

func BenchmarkSeqWindowCheck(b *testing.B) {
	w, err := NewSequenceWindow(100, 0)
	if err != nil {
		b.Fatal("unexpected error:", err)
	}

	b.ResetTimer()

	for seq := uint32(0); seq < uint32(b.N); seq++ {
		w.Check(seq)
	}
}

func BenchmarkSeqWindowCheckParallel(b *testing.B) {
	w, err := NewSequenceWindow(100, 0)
	if err != nil {
		b.Fatal("unexpected error:", err)
	}

	wg := sync.WaitGroup{}
	numThreads := runtime.NumCPU()
	b.Logf("running test with %d threads", numThreads)
	wg.Add(numThreads)

	b.ResetTimer()

	for i := 0; i < numThreads; i++ {
		go func() {
			for seq := uint32(0); seq < uint32(b.N); seq += uint32(numThreads) {
				w.Check(seq)
			}
			wg.Done()
		}()
	}

	wg.Wait()
}

func BenchmarkSeqWindowCheckAndSet(b *testing.B) {
	w, err := NewSequenceWindow(100, 0)
	if err != nil {
		b.Fatal("unexpected error:", err)
	}

	b.ResetTimer()

	for seq := uint32(0); seq < uint32(b.N); seq++ {
		w.CheckAndSet(seq)
	}
}

func BenchmarkSeqWindowCheckAndSetParallel(b *testing.B) {
	w, err := NewSequenceWindow(100, 0)
	if err != nil {
		b.Fatal("unexpected error:", err)
	}

	wg := sync.WaitGroup{}
	numThreads := runtime.NumCPU()
	b.Logf("running test with %d threads", numThreads)
	wg.Add(numThreads)

	b.ResetTimer()

	for i := 0; i < numThreads; i++ {
		go func() {
			for seq := uint32(0); seq < uint32(b.N); seq += uint32(numThreads) {
				w.CheckAndSet(seq)
			}
			wg.Done()
		}()
	}

	wg.Wait()
}