#pragma pack(push, 1)
typedef struct _OVERLAP_PAIR_T
{
    union {
        struct
        {
            int16_t PSoverlap;
            int16_t SPoverlap;
        };

        int32_t Overlaps;
    };
} OVERLAP_PAIR_T, *POVERLAP_PAIR_T;
#pragma pack(pop)

// Shift 'val' n bytes to the right (with zero-filling), effectively dividing'val' by 2^(8 * n_bytes) and truncating any fractional parts.
__forceinline __m128i SHRB(__m128i val, int n_bytes);

// Shift 'val' n bytes to the left (with zero-filling), effectively multiplying 'val' by 2^(8 * n_bytes)
__forceinline __m128i SHLB(__m128i val, int n_bytes);


/*
Detects whether one string is contained in another string and if it is not then determines the maximum length of the first string's prefix which constitutes the suffix of the second string 
...and determines the maximum length of the first string's suffix which constitutes the prefix of the second string.
The lengths of the strings are explicitly specified.

Algorithm mechanics:
	- Each string is left-shifted inside a 16-byte XMM register via SHLB before being used as the PCMPESTRI haystack.
	- The shift amount is (16 - len), so the string occupies bytes [16-len .. 15] thus the last byte of the haystack string always occupies the Most Significant Byte of the 16-byte XMM register.
	- PCMPESTRI(_SIDD_CMP_EQUAL_ORDERED | _SIDD_LEAST_SIGNIFICANT) returns the lowest byte offset 'res' where the needle begins to match. IMPORTANT:  This match happens without any looping.
	- Positions past the maximum haystack length are always treated as "implicit agree" by the PCMPESTRI instruction, so a needle that extends beyond the 16 byte haystack still counts as a match at that position.  This allows only a prefix of the needle to be matched, without any looping - this is very important !
	- If (res + len_needle <= 16) the entire needle fit → containment.
	- If (res + len_needle >  16) only a prefix of the needle matched the tail of the haystack → overlap length = (16 - res).
*/
OVERLAP_PAIR_T FindPrefixSuffixOverlap(const char* a, uint8_t len_a, const char* b, uint8_t len_b)
{
	#define MAX_CHUNK_LENGTH 16  //Because only 16 bytes fit into an XMM register

	assert (len_a <= 16 && len_a > 0);	//Currently this function cannot handle strings longer than 16 bytes
	assert (len_b <= 16 && len_b > 0);	//Currently this function cannot handle strings longer than 16 bytes

	unsigned int res;
	OVERLAP_PAIR_T ret = { 0, 0 };

	__m128i mem_vec_a = _mm_loadu_si128((const __m128i*)a);	//Load the strings from memory only once and manipulate them afterwards only in XMM registers.
	__m128i mem_vec_b = _mm_loadu_si128((const __m128i*)b);	//Load the strings from memory only once and manipulate them afterwards only in XMM registers.
	__m128i mem_vec_aMax = SHLB(mem_vec_a, MAX_CHUNK_LENGTH - len_a);  //Ensure that the Haystack is always MAX_CHUNK_LENGTH bytes long, because when the full-size haystack ends before the needle does, then the PCMPESTRI instruction considers that a match — i.e.: it found the complete prefix of the needle that is the same as the suffix of the haystack regardless of the needle's and heystack's lengths (within the 1 to 16 bytes XMM bounds, of course).
	__m128i mem_vec_bMax = SHLB(mem_vec_b, MAX_CHUNK_LENGTH - len_b);  //Ensure that the Haystack is always MAX_CHUNK_LENGTH bytes long, because when the full-size haystack ends before the needle does, then the PCMPESTRI instruction considers that a match — i.e.: it found the complete prefix of the needle that is the same as the suffix of the haystack regardless of the needle's and heystack's lengths (within the 1 to 16 bytes XMM bounds, of course).


	res = _mm_cmpestri(mem_vec_a, len_a, mem_vec_bMax, MAX_CHUNK_LENGTH, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_MASKED_POSITIVE_POLARITY | _SIDD_LEAST_SIGNIFICANT);
	if (res < MAX_CHUNK_LENGTH)
	{
		if (res + len_a <= MAX_CHUNK_LENGTH)
		{
			ret.PSoverlap = -len_a;
#ifdef DEBUG_MODE
			printf("'%s' is CONTAINED!\n", a);
#endif
		}
		else
		{
			ret.PSoverlap = MAX_CHUNK_LENGTH - res; 
#ifdef DEBUG_MODE
			printf("Max Prefix to Suffix Overlap Length: %u\n", MAX_CHUNK_LENGTH - res);
#endif
		}

#ifdef DEBUG_MODE
		printf("%*s\n", res - (MAX_CHUNK_LENGTH - len_b) + len_a, a);  //Pretty print to indent and visualize the overlap between a's prefix and b's suffix
		printf("%s\n\n", b);
#endif
	}

	res = _mm_cmpestri(mem_vec_b, len_b, mem_vec_aMax, MAX_CHUNK_LENGTH, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_MASKED_POSITIVE_POLARITY | _SIDD_LEAST_SIGNIFICANT);
	if (res < MAX_CHUNK_LENGTH)
	{
		if (res + len_b <= MAX_CHUNK_LENGTH)
		{
			ret.SPoverlap = -len_b;
#ifdef DEBUG_MODE
			printf("'%s' is CONTAINED!\n", b);
#endif
		}
		else
		{
			ret.SPoverlap = MAX_CHUNK_LENGTH - res;
#ifdef DEBUG_MODE
			printf("Max Suffix to Prefix Overlap Length: %u\n", MAX_CHUNK_LENGTH - res);
#endif
		}

#ifdef DEBUG_MODE
		printf("%s\n", a);
		printf("%*s\n", res - (MAX_CHUNK_LENGTH - len_a) + len_b, b);  //Pretty print to indent and visualize the overlap between a's suffix and b's prefix
#endif
	}

	return ret;
}


int main(int argc, char* argv[])
{
	if (argc != 3) {
		printf("Bad number of arguments: %u\n", argc);
		return 1;
	}

	char* a = argv[1];
	char* b = argv[2];

	OVERLAP_PAIR_T OverlapPair = FindPrefixSuffixOverlap(a, (uint8_t)strlen(a), b, (uint8_t)strlen(b));

	if (!OverlapPair.Overlaps)
		return 0;	//The strings don't have anything in common (they are disjoint).

	if (OverlapPair.PSoverlap < 0)
	{
		if (OverlapPair.SPoverlap < 0)
		{
			printf("'Strings are EQUAL!\n");
			return 1
		}
		else
			printf("'%s' is CONTAINED!\n", a);
	}
	else if (OverlapPair.PSoverlap > 0)
		printf("Max Prefix to Suffix Overlap Length: %u\n", OverlapPair.PSoverlap);

	if (OverlapPair.SPoverlap < 0)
		printf("'%s' is CONTAINED!\n", b);
	else if (OverlapPair.SPoverlap > 0)
		printf("Max Suffix to Prefix Overlap Length: %u\n", OverlapPair.SPoverlap);

	return 2;

}