Adapted create_kyradat to use an automatic offset search. (Hopefully no regressions).

svn-id: r44118

1 files changed, 195 insertions, 0 deletions

diff --git a/tools/create_kyradat/search.cpp b/tools/create_kyradat/search.cpp
new file mode 100644
index 0000000000..a12eb231ef
--- /dev/null
+++ b/tools/create_kyradat/search.cpp
@@ -0,0 +1,195 @@
+#include "search.h"
+#include "md5.h"
+
+#include <algorithm>
+#include <cassert>
+
+Hasher::Hash Hasher::createHash(const byte *data, uint32 size) {
+	md5_context ctx;
+	md5_starts(&ctx);
+	md5_update(&ctx, data, size);
+
+	Hash hash;
+	md5_finish(&ctx, hash.digest);
+	return hash;
+}
+
+SearchData SearchCreator::create(const char *filename) {
+	FILE *f = fopen(filename, "rb");
+	assert(f);
+
+	SearchData data;
+	data.size = fileSize(f);
+
+	byte *buffer = new byte[data.size];
+	fread(buffer, 1, data.size, f);
+	fclose(f);
+
+	data = create(buffer, data.size);
+	delete[] buffer;
+
+	return data;
+}
+
+SearchData SearchCreator::create(const byte *buffer, uint32 size) {
+	SearchData data;
+
+	data.size = size;
+	data.hash = Hasher::createHash(buffer, data.size);
+	data.byteSum = 0;
+
+	for (uint32 i = 0; i < data.size; ++i)
+		data.byteSum += buffer[i];
+
+	return data;
+}
+
+SumCreator::SumCreator(InputList list, const DataInput &input) : _curOffset(0), _input(input), _sums() {
+	// Sort in ascending order
+	list.sort(std::less<uint32>());
+
+	uint32 byteSum = 0;
+	uint32 oldSize = 0;
+
+	for (InputList::const_iterator i = list.begin(); i != list.end(); ++i) {
+		// Strip out entries, which exceed the buffer size
+		if (*i > _input.size())
+			continue;
+
+		// Strip out duplicates
+		if (_sums.find(*i) != _sums.end())
+			continue;
+
+		// Only add the bytes exceeding the old sum's size
+		// to the sum. This saves a few accesses.
+		for (uint32 j = oldSize; j < *i; ++j)
+			byteSum += _input[j];
+
+		_sums[*i] = byteSum;
+
+		// Save this sum's size
+		oldSize = *i;
+	}
+}
+
+bool SumCreator::nextByte() {
+	// Calculate the bytes available for summing. We need to add
+	// 1 here, since we will only update the offset AFTER everything
+	// is done.
+	const uint32 sizeLeft = _input.size() - (_curOffset + 1);
+
+	if (!sizeLeft) {
+		_sums.clear();
+		return false;
+	}
+
+	// Grab the old first byte.
+	const byte firstByte = _input[_curOffset];
+
+	typedef std::list<uint32> DeletionList;
+	DeletionList toRemove;
+
+	for (SumMap::iterator i = _sums.begin(); i != _sums.end(); ++i) {
+		// If this entry needs to sum up a larger buffer than the buffer
+		// size left, we will remove the entry and continue to the next
+		// one.
+		if (i->first > sizeLeft) {
+			// Add the current entry to the removal list.
+			toRemove.push_back(i->first);
+			continue;
+		}
+
+		// Update the byte sum. First we remove the old first byte
+		// from the sum, next we add the next available byte.
+		i->second -= firstByte;
+		i->second += _input[_curOffset + i->first];
+	}
+
+	// Remove all entries flagged for removal
+	for (DeletionList::const_iterator i = toRemove.begin(); i != toRemove.end(); ++i)
+		_sums.erase(*i);
+
+	// Update out offset.
+	++_curOffset;
+
+	// We return whether there are still some sums left available.
+	return !_sums.empty();
+}
+
+bool SumCreator::hasSum(uint32 size) const {
+	return _sums.find(size) != _sums.end();
+}
+
+uint32 SumCreator::getSum(uint32 size) const {
+	SumMap::const_iterator s = _sums.find(size);
+
+	if (s == _sums.end())
+		return 0;
+
+	return s->second;
+}
+
+Search::Search(const char *filename) : _data(), _search() {
+	FILE *src = fopen(filename, "rb");
+	assert(src);
+
+	uint32 size = fileSize(src);
+	byte *data = new byte[size];
+	fread(data, 1, size, src);
+	fclose(src);
+
+	_data.resize(size);
+	for (uint32 i = 0; i < size; ++i)
+		_data[i] = data[i];
+	delete[] data;
+}
+
+Search::Search(const byte *data, uint32 size) : _data(), _search() {
+	_data.resize(size);
+	for (uint32 i = 0; i < size; ++i)
+		_data[i] = data[i];
+}
+
+void Search::addData(SearchData data) {
+	for (SearchList::const_iterator i = _search.begin(); i != _search.end(); ++i) {
+		// Do not add any duplicates
+		if (*i == data)
+			return;
+	}
+
+	_search.push_back(data);
+}
+
+bool Search::search(ResultList &res) {
+	SumCreator::InputList list;
+	for (SearchList::const_iterator i = _search.begin(); i != _search.end(); ++i)
+		list.push_back(i->size);
+
+	SumCreator sum(list, _data);
+	list.clear();
+
+	do {
+		const uint32 offset = sum.getOffset();
+
+		for (SearchList::iterator i = _search.begin(); i != _search.end(); ) {
+			if (!sum.hasSum(i->size)) {
+				i = _search.erase(i);
+				continue;
+			}
+
+			const uint32 byteSum = sum.getSum(i->size);
+			if (byteSum == i->byteSum) {
+				if (Hasher::createHash(&_data[offset], i->size) == i->hash) {
+					res.push_back(ResultData(*i, offset));
+					i = _search.erase(i);
+					continue;
+				}
+			}
+
+			++i;
+		}
+	} while (sum.nextByte());
+
+	return !res.empty();
+}
+