//
// 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 (
	"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 {
	idxTop := int(top / 32)
	idxSeq := int(seq / 32)
	if idxTop >= idxSeq {
		return idxTop - idxSeq
	}
	return idxTop + int(1<<(32-5)) - idxSeq
}

type SequenceWindow struct {
	mtx  *sync.RWMutex
	size int
	head uint64
	body []uint32
}

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("%10d/[%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) check(sequenceNumber uint32) bool {
	idx := bitSliceIndex(w.top(), sequenceNumber)
	bit := int(sequenceNumber % 32)
	return ((w.bitSlice(idx) >> uint(bit)) & 1) == 0
}

func (w *SequenceWindow) checkAndSet(sequenceNumber uint32) bool {
	idx := bitSliceIndex(w.top(), sequenceNumber)
	bit := int(sequenceNumber % 32)

	// TODO: use atomic.CompareAndSwap and loop

	oldSlice := w.bitSlice(idx)
	newSlice := oldSlice | 1<<uint(bit)
	if oldSlice == newSlice {
		return false
	}
	if idx <= 0 {
		newTop := w.top()
		if sequenceNumber >= newTop {
			newTop = sequenceNumber + 1
		}
		w.head = uint64(newTop)<<32 | uint64(newSlice)
	} else {
		w.body[idx-1] = newSlice
	}
	return true
}

func (w *SequenceWindow) advanceTop(newTop uint32) {
	oldIdx := int(w.top() / 32)
	newIdx := int(newTop / 32)
	diff := newIdx - oldIdx
	if oldIdx > newIdx {
		diff = oldIdx - newIdx
	}
	oldHeadSlice := uint32(w.head)
	w.head = uint64(newTop) << 32
	for i := len(w.body) - 1; i >= 0; i-- {
		if i < (diff - 1) {
			w.body[i] = 0
		} else if i < diff {
			w.body[i] = oldHeadSlice
		} else {
			w.body[i] = w.body[i-diff]
		}
	}
}

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 w.top()
}

func (w *SequenceWindow) Check(sequenceNumber uint32) bool {
	if w.size <= 0 {
		return true
	}
	w.mtx.RLock()
	defer w.mtx.RUnlock()

	lt, d := seqDistance(w.top(), sequenceNumber)
	if lt {
		if d > uint32(w.size) {
			return false
		}
		return w.check(sequenceNumber)
	}
	return true
}

func (w *SequenceWindow) CheckAndSet(sequenceNumber uint32) bool {
	if w.size <= 0 {
		return true
	}
	w.mtx.Lock()
	defer w.mtx.Unlock()

	top := w.top()
	lt, d := seqDistance(top, sequenceNumber)
	if lt && d > uint32(w.size) {
		return false
	}
	if lt || top/32 == (sequenceNumber+1)/32 {
		result := w.checkAndSet(sequenceNumber)
		return result
	}
	// TODO: only now we would need the writers lock
	w.advanceTop(sequenceNumber + 1)
	return w.checkAndSet(sequenceNumber)
}

func NewSequenceWindow(size int, top uint32) (w *SequenceWindow, err error) {
	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{}}
	if w.size > 0 {
		bodyLen := w.size / 32
		if (w.size % 32) != 0 {
			bodyLen++
		}
		w.body = make([]uint32, bodyLen, bodyLen)

		remain := uint(top % 32)
		for i := uint(0); i < remain; i++ {
			w.head |= 1 << i
		}
		for i := range w.body {
			w.body[i] = 0xFFFFFFFF
		}
	}
	return
}