IndexOfAnyCpp

IndexOfAny.cpp

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <chrono>
#include <iostream>
#define PROBABILISTICMAP_BLOCK_INDEX_MASK    0X7
#define PROBABILISTICMAP_BLOCK_INDEX_SHIFT   0x3
#define PROBABILISTICMAP_SIZE                0X8
typedef unsigned short WCHAR;

void InitializeProbabilisticMap(int* charMap, __in_ecount(length) const WCHAR* charArray, int length);
void InitializeProbabilisticMap_SpecialAscii(int* charMap, __in_ecount(length) const WCHAR* charArray, int length);
bool InitializeProbabilisticMap_PassAscii(int* charMap, __in_ecount(length) const WCHAR* charArray, int length);
inline bool ProbablyContains(const int* charMap, WCHAR searchValue);
inline bool ProbablyContains_SpecialAscii(const int* charMap, WCHAR searchValue);
inline bool ProbablyContains_PassAscii(const int* charMap, WCHAR searchValue, bool hasAscii);
void SetBit(int* value, int bitPos);
inline bool IsBitSet(int value, int bitPos);

int main()
{
	int valueLength = 10;
	WCHAR *valueChars = new WCHAR[valueLength];
	int charMap[PROBABILISTICMAP_SIZE] = { 0 };
	int charMap_SpecialAscii[PROBABILISTICMAP_SIZE] = { 0 };
	int charMap_PassAscii[PROBABILISTICMAP_SIZE] = { 0 };
	int charRangeOffset = 50;
	WCHAR checkChar = 52;
	bool hasAscii;

	for (int i = 0; i < valueLength; i++)
	{
		valueChars[i] = i + charRangeOffset;
	}

	auto begin = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 100000000; i++)
	{
		InitializeProbabilisticMap(charMap, valueChars, valueLength);
	}
	auto end = std::chrono::high_resolution_clock::now();
	std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "ns" << std::endl;


	begin = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 100000000; i++)
	{
		InitializeProbabilisticMap_SpecialAscii(charMap_SpecialAscii, valueChars, valueLength);
	}
	end = std::chrono::high_resolution_clock::now();
	std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "ns" << std::endl;

	for (int i = 0; i < PROBABILISTICMAP_SIZE; i++)
	{
		std::cout << i << " - " << charMap[i];

		if (charMap[i] != charMap_SpecialAscii[i]) {
			std::cout << " different " << charMap_SpecialAscii[i];
		}

		std::cout << std::endl;
	}


	begin = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 100000000; i++)
	{
		hasAscii = InitializeProbabilisticMap_PassAscii(charMap_PassAscii, valueChars, valueLength);
	}
	end = std::chrono::high_resolution_clock::now();
	std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "ns" << std::endl;

	for (int i = 0; i < PROBABILISTICMAP_SIZE; i++)
	{
		std::cout << i << " - " << charMap[i];

		if (charMap[i] != charMap_PassAscii[i]) {
			std::cout << " different " << charMap_PassAscii[i];
		}

		std::cout << std::endl;
	}


	int doesContain = 0;
	begin = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 1000000000; i++)
	{
		if (ProbablyContains(charMap, checkChar))
		{
			doesContain++;
		}
	}
	end = std::chrono::high_resolution_clock::now();
	std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "ns " << doesContain << std::endl;

	doesContain = 0;
	begin = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 1000000000; i++)
	{
		if (ProbablyContains_SpecialAscii(charMap_SpecialAscii, checkChar))
		{
			doesContain++;
		}
	}
	end = std::chrono::high_resolution_clock::now();
	std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "ns " << doesContain << std::endl;
	
	doesContain = 0;
	begin = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 1000000000; i++)
	{
			if (ProbablyContains_PassAscii(charMap_PassAscii, checkChar, hasAscii))
		{
			doesContain++;
		}
	}
	end = std::chrono::high_resolution_clock::now();
	std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "ns " << doesContain << std::endl;
	

    return 0;
}

void InitializeProbabilisticMap(int* charMap, __in_ecount(length) const WCHAR* charArray, int length) {
	for (int i = 0; i < length; ++i) {
		int hi, lo;

		WCHAR c = charArray[i];

		hi = (c >> 8) & 0xFF;
		lo = c & 0xFF;

		int* value = &charMap[lo & PROBABILISTICMAP_BLOCK_INDEX_MASK];
		SetBit(value, lo >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);

		value = &charMap[hi & PROBABILISTICMAP_BLOCK_INDEX_MASK];
		SetBit(value, hi >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);
	}
}

void InitializeProbabilisticMap_SpecialAscii(int* charMap, __in_ecount(length) const WCHAR* charArray, int length) {
	bool hasAscii = false;

	for (int i = 0; i < length; ++i) {
		int hi, lo;

		int c = charArray[i];

		lo = c & 0xFF;
		hi = (c >> 8) & 0xFF;

		int* value = &charMap[lo & PROBABILISTICMAP_BLOCK_INDEX_MASK];
		SetBit(value, lo >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);

		if (hi > 0) {
			value = &charMap[hi & PROBABILISTICMAP_BLOCK_INDEX_MASK];
			SetBit(value, hi >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);
		}
		else {
			hasAscii = true;
		}
	}

	if (hasAscii) {
		charMap[0] |= 1;
	}
}

bool InitializeProbabilisticMap_PassAscii(int* charMap, __in_ecount(length) const WCHAR* charArray, int length) {
	bool hasAscii = false;

	for (int i = 0; i < length; ++i) {
		int hi, lo;

		WCHAR c = charArray[i];

		hi = (c >> 8) & 0xFF;
		lo = c & 0xFF;

		int* value = &charMap[lo & PROBABILISTICMAP_BLOCK_INDEX_MASK];
		SetBit(value, lo >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);

		if (hi > 0) {
			value = &charMap[hi & PROBABILISTICMAP_BLOCK_INDEX_MASK];
			SetBit(value, hi >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);
		}
		else {
			hasAscii = true;
		}
	}

	return hasAscii;
}

inline bool ProbablyContains(const int* charMap, WCHAR searchValue) {
	int lo, hi;

	lo = searchValue & 0xFF;
	int value = charMap[lo & PROBABILISTICMAP_BLOCK_INDEX_MASK];

	if (IsBitSet(value, lo >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT)) {
		hi = (searchValue >> 8) & 0xFF;
		value = charMap[hi & PROBABILISTICMAP_BLOCK_INDEX_MASK];

		return IsBitSet(value, hi >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);
	}

	return false;
}

inline bool ProbablyContains_SpecialAscii(const int* charMap, WCHAR searchValue) {
	int lo, hi;

	lo = searchValue & 0xFF;
	int value = charMap[lo & PROBABILISTICMAP_BLOCK_INDEX_MASK];

	if (IsBitSet(value, lo >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT)) {
		hi = (searchValue >> 8) & 0xFF;
		value = charMap[hi & PROBABILISTICMAP_BLOCK_INDEX_MASK];

		return IsBitSet(value, hi >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);
	}

	return false;
}

inline bool ProbablyContains_PassAscii(const int* charMap, WCHAR searchValue, bool hasAscii) {
	int lo, hi;

	lo = searchValue & 0xFF;
	int value = charMap[lo & PROBABILISTICMAP_BLOCK_INDEX_MASK];

	if (IsBitSet(value, lo >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT)) {
		hi = (searchValue >> 8) & 0xFF;

		return hi == 0 ? 
			hasAscii :
			IsBitSet(charMap[hi & PROBABILISTICMAP_BLOCK_INDEX_MASK], hi >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);
	}

	return false;
}

inline void SetBit(int* value, int bitPos) {
	*value |= (1 << bitPos);
}

inline bool IsBitSet(int value, int bitPos) {
	return (value & (1 << bitPos)) != 0;
}