seekia/internal/byteRange/byteRange.go

// byteRange provides functions to read and generate byte ranges
// Byte ranges are used to describe what range of identity hashes/inboxes to retrieve from a host
// Hosts share the range of identities/inboxes they host on their profile.

package byteRange

import "seekia/internal/identity"
import "seekia/internal/encoding"

import "math"
import "math/big"
import "errors"

// This is used to retrieve the minimum and maximum identity hash ranges
// This is used when a server request does not need to filter based on a range
func GetMinimumMaximumIdentityHashBounds()([16]byte, [16]byte){

	// minimumBound == "aaaaaaaaaaaaaaaaaaaaaaaam"
	minimumBound := [16]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}

	// maximumBound == "777777777777777777777777r"
	maximumBound := [16]byte{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 3}

	return minimumBound, maximumBound
}

// This is used to retrieve the minimum and maximum inbox ranges
// This is used when a server request does not need to filter based on a range
func GetMinimumMaximumInboxBounds()([10]byte, [10]byte){

	// minimumBound == "aaaaaaaaaaaaaaaa"
	minimumBound := [10]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

	// maximumBound == "7777777777777777"
	maximumBound := [10]byte{255, 255, 255, 255, 255, 255, 255, 255, 255, 255}

	return minimumBound, maximumBound
}

func CheckIfIdentityHashIsWithinRange(rangeStart [16]byte, rangeEnd [16]byte, inputIdentityHash [16]byte)(bool, error){

	isValid, err := identity.VerifyIdentityHash(inputIdentityHash, false, "")
	if (err != nil) { return false, err }
	if (isValid == false){
		inputIdentityHashHex := encoding.EncodeBytesToHexString(inputIdentityHash[:])
		return false, errors.New("CheckIfIdentityHashIsWithinRange called with invalid inputIdentityHash: " + inputIdentityHashHex)
	}

	if (rangeStart == inputIdentityHash || rangeEnd == inputIdentityHash){
		return true, nil
	}
	if (rangeStart == rangeEnd){
		return false, nil
	}

	isWithinRange, err := checkIfBytesAreWithinRange(rangeStart[:], rangeEnd[:], inputIdentityHash[:])
	if (err != nil) { return false, err }

	return isWithinRange, nil
}

func CheckIfInboxIsWithinRange(rangeStart [10]byte, rangeEnd [10]byte, inputInbox [10]byte)(bool, error){

	if (rangeStart == inputInbox || rangeEnd == inputInbox){
		return true, nil
	}
	if (rangeStart == rangeEnd){
		return false, nil
	}

	isWithinRange, err := checkIfBytesAreWithinRange(rangeStart[:], rangeEnd[:], inputInbox[:])
	if (err != nil) { return false, err }

	return isWithinRange, nil
}

func checkIfBytesAreWithinRange(rangeStart []byte, rangeEnd []byte, inputSlice []byte)(bool, error){

	// We check to see if inputSlice is between both values

	slicesAreEqual, comparisonA, err := compareByteSlices(rangeStart, inputSlice)
	if (err != nil) { return false, err }
	if (slicesAreEqual == true){
		return true, nil
	}

	slicesAreEqual, comparisonB, err := compareByteSlices(rangeEnd, inputSlice)
	if (err != nil) { return false, err }
	if (slicesAreEqual == true){
		return true, nil
	}

	if (comparisonA != comparisonB){
		return true, nil
	}

	return false, nil
}



//Outputs:
//	-bool: Any values found
//	-[][16]byte: List of values that are within range
//	-error
func GetAllIdentityHashesInListWithinRange(rangeStart [16]byte, rangeEnd [16]byte, inputList [][16]byte)(bool, [][16]byte, error){

	identitiesWithinRangeList := make([][16]byte, 0)

	for _, identityHash := range inputList{

		isValid, err := identity.VerifyIdentityHash(identityHash, false, "")
		if (err != nil) { return false, nil, err }
		if (isValid == false){
			identityHashHex := encoding.EncodeBytesToHexString(identityHash[:])
			return false, nil, errors.New("GetAllIdentityHashesInListWithinRange called with inputList containing invalid identityHash: " + identityHashHex)
		}

		isWithinRange, err := checkIfBytesAreWithinRange(rangeStart[:], rangeEnd[:], identityHash[:])
		if (err != nil) { return false, nil, err }
		if (isWithinRange == true){
			identitiesWithinRangeList = append(identitiesWithinRangeList, identityHash)
		}
	}

	if (len(identitiesWithinRangeList) == 0){
		return false, nil, nil
	}

	return true, identitiesWithinRangeList, nil
}

//Outputs:
//	-bool: Any inboxes found
//	-[][10]byte: List of inboxes that are within range
//	-error
func GetAllInboxesInListWithinRange(rangeStart [10]byte, rangeEnd [10]byte, inputList [][10]byte)(bool, [][10]byte, error){

	inboxesWithinRangeList := make([][10]byte, 0)

	for _, inbox := range inputList{

		isWithinRange, err := checkIfBytesAreWithinRange(rangeStart[:], rangeEnd[:], inbox[:])
		if (err != nil) { return false, nil, err }
		if (isWithinRange == true){
			inboxesWithinRangeList = append(inboxesWithinRangeList, inbox)
		}
	}

	if (len(inboxesWithinRangeList) == 0){
		return false, nil, nil
	}

	return true, inboxesWithinRangeList, nil
}

// This function will find the shared range from two ranges
//Outputs:
//	-bool: Any intersection found
//	-[16]byte: Intersection range start
//	-[16]byte: Intersection range end
//	-error
func GetIdentityIntersectionRangeFromTwoRanges(range1Start [16]byte, range1End [16]byte, range2Start [16]byte, range2End [16]byte)(bool, [16]byte, [16]byte, error){

	anyIntersectionFound, intersectionRangeStart, intersectionRangeEnd, err := getIntersectionRangeFromTwoRanges(range1Start[:], range1End[:], range2Start[:], range2End[:])
	if (err != nil) { return false, [16]byte{}, [16]byte{}, err }
	if (anyIntersectionFound == false){
		return false, [16]byte{}, [16]byte{}, nil
	}

	if (len(intersectionRangeStart) != 16){
		return false, [16]byte{}, [16]byte{}, errors.New("getIntersectionRangeFromTwoRanges returning invalid length range start.")
	}
	if (len(intersectionRangeEnd) != 16){
		return false, [16]byte{}, [16]byte{}, errors.New("getIntersectionRangeFromTwoRanges returning invalid length range end.")
	}

	intersectionRangeStartArray := [16]byte(intersectionRangeStart)
	intersectionRangeEndArray := [16]byte(intersectionRangeEnd)

	return true, intersectionRangeStartArray, intersectionRangeEndArray, nil
}

// This function will find the shared range from two ranges
//Outputs:
//	-bool: Any intersection found
//	-[10]byte: Intersection range start
//	-[10]byte: Intersection range end
//	-error
func GetInboxIntersectionRangeFromTwoRanges(range1Start [10]byte, range1End [10]byte, range2Start [10]byte, range2End [10]byte)(bool, [10]byte, [10]byte, error){

	anyIntersectionFound, intersectionRangeStart, intersectionRangeEnd, err := getIntersectionRangeFromTwoRanges(range1Start[:], range1End[:], range2Start[:], range2End[:])
	if (err != nil) { return false, [10]byte{}, [10]byte{}, err }
	if (anyIntersectionFound == false){
		return false, [10]byte{}, [10]byte{}, nil
	}

	if (len(intersectionRangeStart) != 10){
		return false, [10]byte{}, [10]byte{}, errors.New("getIntersectionRangeFromTwoRanges returning invalid length rangeStart.")
	}
	if (len(intersectionRangeEnd) != 10){
		return false, [10]byte{}, [10]byte{}, errors.New("getIntersectionRangeFromTwoRanges returning invalid length rangeEnd.")
	}

	intersectionRangeStartArray := [10]byte(intersectionRangeStart)
	intersectionRangeEndArray := [10]byte(intersectionRangeEnd)

	return true, intersectionRangeStartArray, intersectionRangeEndArray, nil
}


// This function will find the shared range from two ranges
//Outputs:
//	-bool: Any intersection found
//	-[]byte: Intersection range start
//	-[]byte: Intersection range end
//	-error
func getIntersectionRangeFromTwoRanges(range1Start []byte, range1End []byte, range2Start []byte, range2End []byte)(bool, []byte, []byte, error){

	if (string(range1Start) == string(range1End) && string(range2Start) == string(range2End)){

		// The intersection is either 1 value, or none
		if (string(range1Start) == string(range2Start)){

			return true, range1Start, range1Start, nil
		}
		return false, nil, nil, nil
	}
	if (string(range1Start) == string(range1End)){

		// We know range2Start != range2End

		isInRange, err := checkIfBytesAreWithinRange(range2Start, range2End, range1Start)
		if (err != nil) { return false, nil, nil, err }
		if (isInRange == true){
			// Intersection is a single value
			return true, range1Start, range1Start, nil
		}

		return false, nil, nil, nil
	}
	if (string(range2Start) == string(range2End)){

		// We know range1Start != range1End

		isInRange, err := checkIfBytesAreWithinRange(range1Start, range1End, range2Start)
		if (err != nil) { return false, nil, nil, err }
		if (isInRange == true){
			// Intersection is a single value
			return true, range2Start, range2Start, nil
		}

		return false, nil, nil, nil
	}

	//Outputs:
	//	-[]byte: Smaller range bound
	//	-[]byte: Larger range bound
	//	-error
	getSmallerAndLargerRangeBounds := func(bound1 []byte, bound2 []byte)([]byte, []byte, error){

		boundsAreEqual, latterIsLarger, err := compareByteSlices(bound1, bound2)
		if (err != nil){ return nil, nil, err }
		if (boundsAreEqual == true){
			return nil, nil, errors.New("compareByteSlices returning bounds are equal after we already checked.")
		}

		if (latterIsLarger == true){

			return bound1, bound2, nil
		}
		return bound2, bound1, nil
	}

	smallerBound1, largerBound1, err := getSmallerAndLargerRangeBounds(range1Start, range1End)
	if (err != nil) { return false, nil, nil, err }

	smallerBound2, largerBound2, err := getSmallerAndLargerRangeBounds(range2Start, range2End)
	if (err != nil) { return false, nil, nil, err }

	boundsAreEqual, latterIsLarger, err := compareByteSlices(largerBound1, smallerBound2)
	if (err != nil) { return false, nil, nil, err }
	if (boundsAreEqual == true){
		// The intersection is only this 1 value
		return true, largerBound1, smallerBound2, nil
	}
	if (latterIsLarger == true){
		// There is no intersection
		return false, nil, nil, nil
	}

	// There is some overlap between the ranges

	getIntersectionSmallerBound := func()([]byte, error){

		// We return the greater of the two bounds

		boundsAreEqual, latterIsLarger, err := compareByteSlices(smallerBound1, smallerBound2)
		if (err != nil) { return nil, err }
		if (boundsAreEqual == true){
			return smallerBound2, nil
		}
		if (latterIsLarger == true){
			return smallerBound2, nil
		}
		return smallerBound1, nil
	}

	intersectionSmallerBound, err := getIntersectionSmallerBound()
	if (err != nil) { return false, nil, nil, err }

	getIntersectionLargerBound := func()([]byte, error){

		// We return the smaller of the two bounds

		boundsAreEqual, latterIsLarger, err := compareByteSlices(largerBound1, largerBound2)
		if (err != nil) { return nil, err }
		if (boundsAreEqual == true){
			return largerBound1, nil
		}
		if (latterIsLarger == true){
			return largerBound1, nil
		}
		return largerBound2, nil
	}

	intersectionLargerBound, err := getIntersectionLargerBound()
	if (err != nil) { return false, nil, nil, err }

	return true, intersectionSmallerBound, intersectionLargerBound, nil
}

func GetEstimatedIdentitySubrangeQuantity(fullRangeStart [16]byte, fullRangeEnd [16]byte, fullRangeQuantity int64, subrangeStart [16]byte, subrangeEnd [16]byte)(int64, error){
	
	estimatedIdentitiesWithinRange, err := getEstimatedSubrangeQuantity(fullRangeStart[:], fullRangeEnd[:], fullRangeQuantity, subrangeStart[:], subrangeEnd[:])
	if (err != nil) { return 0, err }

	return estimatedIdentitiesWithinRange, nil
}

func GetEstimatedInboxSubrangeQuantity(fullRangeStart [10]byte, fullRangeEnd [10]byte, fullRangeQuantity int64, subrangeStart [10]byte, subrangeEnd [10]byte)(int64, error){

	estimatedInboxesWithinRange, err := getEstimatedSubrangeQuantity(fullRangeStart[:], fullRangeEnd[:], fullRangeQuantity, subrangeStart[:], subrangeEnd[:])
	if (err != nil) { return 0, err }

	return estimatedInboxesWithinRange, nil
}

// This function takes a range and its item quantity, and a subset range, and returns the estimated number of items within the subset range
// This is used to determine how many items will be in a request, so that the requestor can know the maximum range to request
// This is because requests and responses have a maximum size, so the requestor must only request enough items to not go over the limit

// Outputs:
//	-int64: Estimated number of items in subrange
//	-error
func getEstimatedSubrangeQuantity(fullRangeStart []byte, fullRangeEnd []byte, fullRangeQuantityInt64 int64, subRangeStart []byte, subRangeEnd []byte)(int64, error){

	// First we make sure the subrange is a valid subrange of the full range.

	isInRange, err := checkIfBytesAreWithinRange(fullRangeStart, fullRangeEnd, subRangeStart)
	if (err != nil) { return 0, err }
	if (isInRange == false){
		return 0, errors.New("getEstimatedSubrangeQuantity called with a start bound out of range.")
	}
	isInRange, err = checkIfBytesAreWithinRange(fullRangeStart, fullRangeEnd, subRangeEnd)
	if (err != nil) { return 0, err }
	if (isInRange == false){
		return 0, errors.New("getEstimatedSubrangeQuantity called with a end bound out of range.")
	}

	if (fullRangeQuantityInt64 == 0){
		return 0, nil
	}

	_, _, _, fullRangeLength, err := getRangeLength(fullRangeStart, fullRangeEnd)
	if (err != nil) { return 0, err }

	fullRangeQuantity := big.NewInt(fullRangeQuantityInt64)

	_, _, _, subRangeLength, err := getRangeLength(subRangeStart, subRangeEnd)
	if (err != nil){ return 0, err }
	
	// FullRangeLength/FullRangeQuantity = SubrangeLength/SubrangeQuantity
	// We solve for SubrangeQuantity
	// SubrangeQuantity/SubrangeLength = FullRangeQuantity/FullRangeLength
	// SubrangeQuantity = (FullRangeQuantity * SubrangeLength)/FullRangeLength
	
	numerator := new(big.Int)
	numerator.Mul(fullRangeQuantity, subRangeLength)

	subrangeQuantity := new(big.Int)
	subrangeQuantity.Div(numerator, fullRangeLength)

	isInt64 := subrangeQuantity.IsInt64()
	if (isInt64 == false){
		// Number is too large to represent as int64
		// This should never happen in practice, so host must be malicious
		// We will return maximum int64 value
		return 9223372036854775807, nil
	}

	result := subrangeQuantity.Int64()

	return result, nil
}

type IdentitySubrange struct{

	SubrangeStart [16]byte
	SubrangeEnd [16]byte
}

type InboxSubrange struct{

	SubrangeStart [10]byte
	SubrangeEnd [10]byte
}

func SplitIdentityRangeIntoEqualSubranges(fullRangeStart [16]byte, fullRangeEnd [16]byte, fullRangeQuantity int64, maximumIdentitiesPerSubrange int64)([]IdentitySubrange, error){

	subrangeObjectsList, err := splitRangeIntoEqualSubranges(16, fullRangeStart[:], fullRangeEnd[:], fullRangeQuantity, maximumIdentitiesPerSubrange)
	if (err != nil) { return nil, err }

	identitySubrangesList := make([]IdentitySubrange, 0, len(subrangeObjectsList))

	for _, subrangeObject := range subrangeObjectsList{

		subrangeStart := subrangeObject.SubrangeStart
		subrangeEnd := subrangeObject.SubrangeEnd

		if (len(subrangeStart) != 16){
			return nil, errors.New("splitRangeIntoEqualSubranges returning invalid subrangeObject with invalid length subrangeStart.")
		}

		if (len(subrangeEnd) != 16){
			return nil, errors.New("splitRangeIntoEqualSubranges returning invalid subrangeObject with invalid length subrangeEnd.")
		}

		subrangeStartArray := [16]byte(subrangeStart)
		subrangeEndArray := [16]byte(subrangeEnd)

		identitySubrangeObject := IdentitySubrange{

			SubrangeStart: subrangeStartArray,
			SubrangeEnd: subrangeEndArray,
		}

		identitySubrangesList = append(identitySubrangesList, identitySubrangeObject)
	}

	return identitySubrangesList, nil
}

func SplitInboxRangeIntoEqualSubranges(fullRangeStart [10]byte, fullRangeEnd [10]byte, fullRangeQuantity int64, maximumInboxesPerSubrange int64)([]InboxSubrange, error){

	subrangeObjectsList, err := splitRangeIntoEqualSubranges(10, fullRangeStart[:], fullRangeEnd[:], fullRangeQuantity, maximumInboxesPerSubrange)
	if (err != nil) { return nil, err }

	inboxSubrangesList := make([]InboxSubrange, 0, len(subrangeObjectsList))

	for _, subrangeObject := range subrangeObjectsList{

		subrangeStart := subrangeObject.SubrangeStart
		subrangeEnd := subrangeObject.SubrangeEnd

		if (len(subrangeStart) != 10){
			return nil, errors.New("splitRangeIntoEqualSubranges returning invalid subrangeObject with invalid length subrangeStart.")
		}

		if (len(subrangeEnd) != 10){
			return nil, errors.New("splitRangeIntoEqualSubranges returning invalid subrangeObject with invalid length subrangeEnd.")
		}

		subrangeStartArray := [10]byte(subrangeStart)
		subrangeEndArray := [10]byte(subrangeEnd)

		inboxSubrangeObject := InboxSubrange{

			SubrangeStart: subrangeStartArray,
			SubrangeEnd: subrangeEndArray,
		}

		inboxSubrangesList = append(inboxSubrangesList, inboxSubrangeObject)
	}

	return inboxSubrangesList, nil
}


type SubrangeObject struct{

	SubrangeStart []byte
	SubrangeEnd []byte
}

//Outputs:
//	-[]subrangeObject
//	-error
func splitRangeIntoEqualSubranges(subrangeBoundBytesLength int, fullRangeStart []byte, fullRangeEnd []byte, fullRangeQuantity int64, maximumItemsPerSubrange int64)([]SubrangeObject, error){

	if (subrangeBoundBytesLength != 10 && subrangeBoundBytesLength != 16){
		return nil, errors.New("splitRangeIntoEqualSubranges called with invalid subrangeBoundBytesLength.")
	}

	if (maximumItemsPerSubrange == 0 || fullRangeQuantity == 0){
		return nil, errors.New("Cannot create subranges: 0 quantity or 0 maximum items")
	}

	boundsAreEqual, fullRangeStartInt, fullRangeEndInt, fullRangeLength, err := getRangeLength(fullRangeStart, fullRangeEnd)
	if (err != nil){ return nil, err }

	if (fullRangeQuantity <= maximumItemsPerSubrange || boundsAreEqual == true){

		subrangeObject := SubrangeObject{

			SubrangeStart: fullRangeStart,
			SubrangeEnd: fullRangeEnd,
		}

		newSubrangeObjectList := []SubrangeObject{subrangeObject}

		return newSubrangeObjectList, nil
	}

	itemsPerSubrange := math.Floor(float64(fullRangeQuantity)/float64(maximumItemsPerSubrange))

	if (itemsPerSubrange > 100000000){
		return nil, errors.New("Items per subrange is too large.")
	}

	itemsPerSubrangeInt := big.NewInt(int64(itemsPerSubrange))	

	// SubrangeIncrement is the integer count of each subrange
	getSubrangeIncrement := func()(*big.Int, error){

		subrangeIncrement := new(big.Int)
		subrangeIncrement.Div(fullRangeLength, itemsPerSubrangeInt)

		zeroInt := big.NewInt(0)
		compareResult := subrangeIncrement.Cmp(zeroInt)
		if (compareResult == -1){
			// This should not happen
			return nil, errors.New("Subrange increment is negative.")
		}
		if (compareResult == 0){
			// Increment is zero
			// We need increment to be at least 1
			oneInt := big.NewInt(1)
			return oneInt, nil
		}

		return subrangeIncrement, nil
	}

	subrangeIncrement, err := getSubrangeIncrement()
	if (err != nil) { return nil, err }

	subrangeObjectsList := make([]SubrangeObject, 0)

	index := fullRangeStartInt

	for {

		subrangeStart := make([]byte, subrangeBoundBytesLength)
		index.FillBytes(subrangeStart)

		// Outputs:
		//	-bool: Is the final subrange
		//	-*big.Int: Subrange end int
		getSubrangeEndInt := func()(bool, *big.Int){

			nextBound := new(big.Int)
			nextBound.Add(index, subrangeIncrement)

			comparisonResult := nextBound.Cmp(fullRangeEndInt)
			if (comparisonResult == -1){
				// This subrange will not take us to the end
				// Another bound remains.
				return false, nextBound
			}
			// This bound takes us either exactly to the end, or exceeds the final value
			// Either way, return the final value
			return true, fullRangeEndInt
		}

		isFinalSubrange, subrangeEndInt := getSubrangeEndInt()

		subrangeEnd := make([]byte, subrangeBoundBytesLength)
		subrangeEndInt.FillBytes(subrangeEnd)

		newSubrangeObject := SubrangeObject{

			SubrangeStart: subrangeStart,
			SubrangeEnd: subrangeEnd,
		}

		subrangeObjectsList = append(subrangeObjectsList, newSubrangeObject)

		if (isFinalSubrange == true){
			break
		}

		index.Set(subrangeEndInt)

		oneInt := big.NewInt(1)

		index.Add(index, oneInt)
	}

	return subrangeObjectsList, nil
}

//Outputs:
//	-bool: Slices are equal
//	-bool: Latter is larger
//	-error
func compareByteSlices(sliceA []byte, sliceB []byte)(bool, bool, error){

	if (len(sliceA) != len(sliceB)){
		return false, false, errors.New("compareByteSlices called with mismatched length slices.")
	}

	for index, sliceAByte := range sliceA{

		sliceBByte := sliceB[index]

		if (sliceAByte == sliceBByte){
			continue
		}
		if (sliceAByte < sliceBByte){
			return false, true, nil
		}

		return false, false, nil
	}

	// Slices are identical

	return true, false, nil
}

//Outputs:
//	-bool: Range bounds are equal
//	-*big.Int: Range start
//	-*big.Int: Range end
//	-*big.Int: Range length (will be 1 if ranges are equal)
//	-error
func getRangeLength(rangeStart []byte, rangeEnd []byte)(bool, *big.Int, *big.Int, *big.Int, error){

	if (len(rangeStart) != len(rangeEnd)){
		return false, nil, nil, nil, errors.New("getRangeLength called with differing length range bounds.")
	}

	// Range length: (absolute value of the difference between both bounds) +1
	// We add 1 to avoid 0 values. A range where rangeStart == rangeEnd contains 1 value.

	rangeStartInt := new(big.Int)
	rangeStartInt.SetBytes(rangeStart)

	rangeEndInt := new(big.Int)
	rangeEndInt.SetBytes(rangeEnd)

	//Outputs:
	//	-bool: Range bounds are equal
	//	-*big.Int: Lesser range bound
	//	-*big.Int: Greater range bound
	getSmallerAndLargerRangeBounds := func()(bool, *big.Int, *big.Int){

		comparisonResult := rangeStartInt.Cmp(rangeEndInt)
		if (comparisonResult == -1){
			return false, rangeStartInt, rangeEndInt
		}
		if (comparisonResult == 0){
			return true, rangeStartInt, rangeEndInt
		}
		// comparisonResult == 1
		return false, rangeEndInt, rangeStartInt
	}

	boundsAreEqual, smallerRangeBound, largerRangeBound := getSmallerAndLargerRangeBounds()
	if (boundsAreEqual == true){

		rangeLength := big.NewInt(1)
	
		return true, smallerRangeBound, largerRangeBound, rangeLength, nil
	}

	result := new(big.Int)
	result.Sub(largerRangeBound, smallerRangeBound)

	oneInt := big.NewInt(1)

	result.Add(result, oneInt)

	return false, smallerRangeBound, largerRangeBound, result, nil
}