X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fcraftdef.cpp;h=286d1eadaf8dc699ec4c492f23b09b284d1ea5f2;hb=48cd217e3b6f53af32802c1897ddd1914d215078;hp=e8f67442fe9b6e930a359d4b9759fc7326ac6815;hpb=037b2591971d752e67fa7d47095b996b3f56da5a;p=minetest.git

diff --git a/src/craftdef.cpp b/src/craftdef.cpp
index e8f67442f..286d1eada 100644
--- a/src/craftdef.cpp
+++ b/src/craftdef.cpp
@@ -1,6 +1,6 @@
 /*
-Minetest-c55
-Copyright (C) 2011 celeron55, Perttu Ahola <celeron55@gmail.com>
+Minetest
+Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>
 
 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU Lesser General Public License as published by
@@ -23,10 +23,81 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "log.h"
 #include <sstream>
 #include <set>
-#include "utility.h"
+#include <algorithm>
 #include "gamedef.h"
 #include "inventory.h"
+#include "util/serialize.h"
+#include "util/string.h"
+#include "util/numeric.h"
+#include "util/strfnd.h"
+#include "exceptions.h"
 
+inline bool isGroupRecipeStr(const std::string &rec_name)
+{
+	return str_starts_with(rec_name, std::string("group:"));
+}
+
+inline u64 getHashForString(const std::string &recipe_str)
+{
+	/*errorstream << "Hashing craft string  \"" << recipe_str << '"';*/
+	return murmur_hash_64_ua(recipe_str.data(), recipe_str.length(), 0xdeadbeef);
+}
+
+static u64 getHashForGrid(CraftHashType type, const std::vector<std::string> &grid_names)
+{
+	switch (type) {
+		case CRAFT_HASH_TYPE_ITEM_NAMES: {
+			std::ostringstream os;
+			bool is_first = true;
+			for (size_t i = 0; i < grid_names.size(); i++) {
+				if (grid_names[i] != "") {
+					os << (is_first ? "" : "\n") << grid_names[i];
+					is_first = false;
+				}
+			}
+			return getHashForString(os.str());
+		} case CRAFT_HASH_TYPE_COUNT: {
+			u64 cnt = 0;
+			for (size_t i = 0; i < grid_names.size(); i++)
+				if (grid_names[i] != "")
+					cnt++;
+			return cnt;
+		} case CRAFT_HASH_TYPE_UNHASHED:
+			return 0;
+	}
+	// invalid CraftHashType
+	assert(false);
+	return 0;
+}
+
+// Check if input matches recipe
+// Takes recipe groups into account
+static bool inputItemMatchesRecipe(const std::string &inp_name,
+		const std::string &rec_name, IItemDefManager *idef)
+{
+	// Exact name
+	if (inp_name == rec_name)
+		return true;
+
+	// Group
+	if (isGroupRecipeStr(rec_name) && idef->isKnown(inp_name)) {
+		const struct ItemDefinition &def = idef->get(inp_name);
+		Strfnd f(rec_name.substr(6));
+		bool all_groups_match = true;
+		do {
+			std::string check_group = f.next(",");
+			if (itemgroup_get(def.groups, check_group) == 0) {
+				all_groups_match = false;
+				break;
+			}
+		} while (!f.at_end());
+		if (all_groups_match)
+			return true;
+	}
+
+	// Didn't match
+	return false;
+}
 
 // Deserialize an itemstring then return the name of the item
 static std::string craftGetItemName(const std::string &itemstring, IGameDef *gamedef)
@@ -41,11 +112,9 @@ static std::vector<std::string> craftGetItemNames(
 		const std::vector<std::string> &itemstrings, IGameDef *gamedef)
 {
 	std::vector<std::string> result;
-	for(std::vector<std::string>::const_iterator
-			i = itemstrings.begin();
-			i != itemstrings.end(); i++)
-	{
-		result.push_back(craftGetItemName(*i, gamedef));
+	for (std::vector<std::string>::size_type i = 0;
+			i < itemstrings.size(); i++) {
+		result.push_back(craftGetItemName(itemstrings[i], gamedef));
 	}
 	return result;
 }
@@ -55,11 +124,22 @@ static std::vector<std::string> craftGetItemNames(
 		const std::vector<ItemStack> &items, IGameDef *gamedef)
 {
 	std::vector<std::string> result;
-	for(std::vector<ItemStack>::const_iterator
-			i = items.begin();
-			i != items.end(); i++)
-	{
-		result.push_back(i->name);
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < items.size(); i++) {
+		result.push_back(items[i].name);
+	}
+	return result;
+}
+
+// convert a list of item names, to ItemStacks.
+static std::vector<ItemStack> craftGetItems(
+		const std::vector<std::string> &items, IGameDef *gamedef)
+{
+	std::vector<ItemStack> result;
+	for (std::vector<std::string>::size_type i = 0;
+			i < items.size(); i++) {
+		result.push_back(ItemStack(std::string(items[i]), (u16)1,
+			(u16)0, gamedef->getItemDefManager()));
 	}
 	return result;
 }
@@ -73,32 +153,26 @@ static bool craftGetBounds(const std::vector<std::string> &items, unsigned int w
 	bool success = false;
 	unsigned int x = 0;
 	unsigned int y = 0;
-	for(std::vector<std::string>::const_iterator
-			i = items.begin();
-			i != items.end(); i++)
-	{
-		if(*i != "")  // Is this an actual item?
-		{
-			if(!success)
-			{
+	for (std::vector<std::string>::size_type i = 0;
+			i < items.size(); i++) {
+		// Is this an actual item?
+		if (items[i] != "") {
+			if (!success) {
 				// This is the first nonempty item
 				min_x = max_x = x;
 				min_y = max_y = y;
 				success = true;
-			}
-			else
-			{
-				if(x < min_x) min_x = x;
-				if(x > max_x) max_x = x;
-				if(y < min_y) min_y = y;
-				if(y > max_y) max_y = y;
+			} else {
+				if (x < min_x) min_x = x;
+				if (x > max_x) max_x = x;
+				if (y < min_y) min_y = y;
+				if (y > max_y) max_y = y;
 			}
 		}
 
 		// Step coordinate
 		x++;
-		if(x == width)
-		{
+		if (x == width) {
 			x = 0;
 			y++;
 		}
@@ -106,29 +180,13 @@ static bool craftGetBounds(const std::vector<std::string> &items, unsigned int w
 	return success;
 }
 
-// Convert a list of item names to a multiset
-static std::multiset<std::string> craftMakeMultiset(const std::vector<std::string> &names)
-{
-	std::multiset<std::string> set;
-	for(std::vector<std::string>::const_iterator
-			i = names.begin();
-			i != names.end(); i++)
-	{
-		if(*i != "")
-			set.insert(*i);
-	}
-	return set;
-}
-
 // Removes 1 from each item stack
 static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 {
-	for(std::vector<ItemStack>::iterator
-			i = input.items.begin();
-			i != input.items.end(); i++)
-	{
-		if(i->count != 0)
-			i->remove(1);
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+		if (input.items[i].count != 0)
+			input.items[i].remove(1);
 	}
 }
 
@@ -136,11 +194,11 @@ static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 // Example: if replacements contains the pair ("bucket:bucket_water", "bucket:bucket_empty"),
 //   a water bucket will not be removed but replaced by an empty bucket.
 static void craftDecrementOrReplaceInput(CraftInput &input,
+		std::vector<ItemStack> &output_replacements,
 		const CraftReplacements &replacements,
 		IGameDef *gamedef)
 {
-	if(replacements.pairs.empty())
-	{
+	if (replacements.pairs.empty()) {
 		craftDecrementInput(input, gamedef);
 		return;
 	}
@@ -148,37 +206,33 @@ static void craftDecrementOrReplaceInput(CraftInput &input,
 	// Make a copy of the replacements pair list
 	std::vector<std::pair<std::string, std::string> > pairs = replacements.pairs;
 
-	for(std::vector<ItemStack>::iterator
-			i = input.items.begin();
-			i != input.items.end(); i++)
-	{
-		if(i->count == 1)
-		{
-			// Find an appropriate replacement
-			bool found_replacement = false;
-			for(std::vector<std::pair<std::string, std::string> >::iterator
-					j = pairs.begin();
-					j != pairs.end(); j++)
-			{
-				ItemStack from_item;
-				from_item.deSerialize(j->first, gamedef->idef());
-				if(i->name == from_item.name)
-				{
-					i->deSerialize(j->second, gamedef->idef());
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+		ItemStack &item = input.items[i];
+		// Find an appropriate replacement
+		bool found_replacement = false;
+		for (std::vector<std::pair<std::string, std::string> >::iterator
+				j = pairs.begin();
+				j != pairs.end(); ++j) {
+			if (inputItemMatchesRecipe(item.name, j->first, gamedef->idef())) {
+				if (item.count == 1) {
+					item.deSerialize(j->second, gamedef->idef());
 					found_replacement = true;
 					pairs.erase(j);
 					break;
+				} else {
+					ItemStack rep;
+					rep.deSerialize(j->second, gamedef->idef());
+					item.remove(1);
+					found_replacement = true;
+					output_replacements.push_back(rep);
+					break;
 				}
 			}
-			// No replacement was found, simply decrement count to zero
-			if(!found_replacement)
-				i->remove(1);
-		}
-		else if(i->count >= 2)
-		{
-			// Ignore replacements for items with count >= 2
-			i->remove(1);
 		}
+		// No replacement was found, simply decrement count by one
+		if (!found_replacement && item.count > 0)
+			item.remove(1);
 	}
 }
 
@@ -187,24 +241,19 @@ static std::string craftDumpMatrix(const std::vector<std::string> &items,
 		unsigned int width)
 {
 	std::ostringstream os(std::ios::binary);
-	os<<"{ ";
+	os << "{ ";
 	unsigned int x = 0;
-	for(std::vector<std::string>::const_iterator
-			i = items.begin();
-			i != items.end(); i++, x++)
-	{
-		if(x == width)
-		{
-			os<<"; ";
+	for(std::vector<std::string>::size_type i = 0;
+			i < items.size(); i++, x++) {
+		if (x == width) {
+			os << "; ";
 			x = 0;
+		} else if (x != 0) {
+			os << ",";
 		}
-		else if(x != 0)
-		{
-			os<<",";
-		}
-		os<<"\""<<(*i)<<"\"";
+		os << '"' << items[i] << '"';
 	}
-	os<<" }";
+	os << " }";
 	return os.str();
 }
 
@@ -213,24 +262,19 @@ std::string craftDumpMatrix(const std::vector<ItemStack> &items,
 		unsigned int width)
 {
 	std::ostringstream os(std::ios::binary);
-	os<<"{ ";
+	os << "{ ";
 	unsigned int x = 0;
-	for(std::vector<ItemStack>::const_iterator
-			i = items.begin();
-			i != items.end(); i++, x++)
-	{
-		if(x == width)
-		{
-			os<<"; ";
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < items.size(); i++, x++) {
+		if (x == width) {
+			os << "; ";
 			x = 0;
+		} else if (x != 0) {
+			os << ",";
 		}
-		else if(x != 0)
-		{
-			os<<",";
-		}
-		os<<"\""<<(i->getItemString())<<"\"";
+		os << '"' << (items[i].getItemString()) << '"';
 	}
-	os<<" }";
+	os << " }";
 	return os.str();
 }
 
@@ -242,7 +286,8 @@ std::string craftDumpMatrix(const std::vector<ItemStack> &items,
 std::string CraftInput::dump() const
 {
 	std::ostringstream os(std::ios::binary);
-	os<<"(method="<<((int)method)<<", items="<<craftDumpMatrix(items, width)<<")";
+	os << "(method=" << ((int)method) << ", items="
+		<< craftDumpMatrix(items, width) << ")";
 	return os.str();
 }
 
@@ -253,77 +298,31 @@ std::string CraftInput::dump() const
 std::string CraftOutput::dump() const
 {
 	std::ostringstream os(std::ios::binary);
-	os<<"(item=\""<<item<<"\", time="<<time<<")";
+	os << "(item=\"" << item << "\", time=" << time << ")";
 	return os.str();
 }
 
 /*
 	CraftReplacements
 */
+
 std::string CraftReplacements::dump() const
 {
 	std::ostringstream os(std::ios::binary);
 	os<<"{";
 	const char *sep = "";
-	for(std::vector<std::pair<std::string, std::string> >::const_iterator
-			i = pairs.begin();
-			i != pairs.end(); i++)
-	{
-		os<<sep<<"\""<<(i->first)<<"\"=>\""<<(i->second)<<"\"";
+	for (std::vector<std::pair<std::string, std::string> >::size_type i = 0;
+			i < pairs.size(); i++) {
+		const std::pair<std::string, std::string> &repl_p = pairs[i];
+		os << sep
+			<< '"' << (repl_p.first)
+			<< "\"=>\"" << (repl_p.second) << '"';
 		sep = ",";
 	}
-	os<<"}";
+	os << "}";
 	return os.str();
 }
 
-
-/*
-	CraftDefinition
-*/
-
-void CraftDefinition::serialize(std::ostream &os) const
-{
-	writeU8(os, 1); // version
-	os<<serializeString(getName());
-	serializeBody(os);
-}
-
-CraftDefinition* CraftDefinition::deSerialize(std::istream &is)
-{
-	int version = readU8(is);
-	if(version != 1) throw SerializationError(
-			"unsupported CraftDefinition version");
-	std::string name = deSerializeString(is);
-	CraftDefinition *def = NULL;
-	if(name == "shaped")
-	{
-		def = new CraftDefinitionShaped;
-	}
-	else if(name == "shapeless")
-	{
-		def = new CraftDefinitionShapeless;
-	}
-	else if(name == "toolrepair")
-	{
-		def = new CraftDefinitionToolRepair;
-	}
-	else if(name == "cooking")
-	{
-		def = new CraftDefinitionCooking;
-	}
-	else if(name == "fuel")
-	{
-		def = new CraftDefinitionFuel;
-	}
-	else
-	{
-		infostream<<"Unknown CraftDefinition name=\""<<name<<"\""<<std::endl;
-                throw SerializationError("Unknown CraftDefinition name");
-	}
-	def->deSerializeBody(is, version);
-	return def;
-}
-
 /*
 	CraftDefinitionShaped
 */
@@ -335,57 +334,64 @@ std::string CraftDefinitionShaped::getName() const
 
 bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) const
 {
-	if(input.method != CRAFT_METHOD_NORMAL)
+	if (input.method != CRAFT_METHOD_NORMAL)
 		return false;
 
 	// Get input item matrix
 	std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
 	unsigned int inp_width = input.width;
-	if(inp_width == 0)
+	if (inp_width == 0)
 		return false;
-	while(inp_names.size() % inp_width != 0)
+	while (inp_names.size() % inp_width != 0)
 		inp_names.push_back("");
 
 	// Get input bounds
-	unsigned int inp_min_x=0, inp_max_x=0, inp_min_y=0, inp_max_y=0;
-	if(!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x, inp_min_y, inp_max_y))
+	unsigned int inp_min_x = 0, inp_max_x = 0, inp_min_y = 0, inp_max_y = 0;
+	if (!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x,
+			inp_min_y, inp_max_y))
 		return false;  // it was empty
 
+	std::vector<std::string> rec_names;
+	if (hash_inited)
+		rec_names = recipe_names;
+	else
+		rec_names = craftGetItemNames(recipe, gamedef);
+
 	// Get recipe item matrix
-	std::vector<std::string> rec_names = craftGetItemNames(recipe, gamedef);
 	unsigned int rec_width = width;
-	if(rec_width == 0)
+	if (rec_width == 0)
 		return false;
-	while(rec_names.size() % rec_width != 0)
+	while (rec_names.size() % rec_width != 0)
 		rec_names.push_back("");
 
 	// Get recipe bounds
 	unsigned int rec_min_x=0, rec_max_x=0, rec_min_y=0, rec_max_y=0;
-	if(!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x, rec_min_y, rec_max_y))
+	if (!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x,
+			rec_min_y, rec_max_y))
 		return false;  // it was empty
 
 	// Different sizes?
-	if(inp_max_x - inp_min_x != rec_max_x - rec_min_x)
-		return false;
-	if(inp_max_y - inp_min_y != rec_max_y - rec_min_y)
+	if (inp_max_x - inp_min_x != rec_max_x - rec_min_x ||
+			inp_max_y - inp_min_y != rec_max_y - rec_min_y)
 		return false;
 
 	// Verify that all item names in the bounding box are equal
 	unsigned int w = inp_max_x - inp_min_x + 1;
 	unsigned int h = inp_max_y - inp_min_y + 1;
-	for(unsigned int y=0; y<h; y++)
-	for(unsigned int x=0; x<w; x++)
-	{
-		unsigned int inp_x = inp_min_x + x;
-		unsigned int inp_y = inp_min_y + y;
-		unsigned int rec_x = rec_min_x + x;
-		unsigned int rec_y = rec_min_y + y;
-
-		if(
-			inp_names[inp_y * inp_width + inp_x] !=
-			rec_names[rec_y * rec_width + rec_x]
-		){
-			return false;
+
+	for (unsigned int y=0; y < h; y++) {
+		unsigned int inp_y = (inp_min_y + y) * inp_width;
+		unsigned int rec_y = (rec_min_y + y) * rec_width;
+
+		for (unsigned int x=0; x < w; x++) {
+			unsigned int inp_x = inp_min_x + x;
+			unsigned int rec_x = rec_min_x + x;
+
+			if (!inputItemMatchesRecipe(
+					inp_names[inp_y + inp_x],
+					rec_names[rec_y + rec_x], gamedef->idef())) {
+				return false;
+			}
 		}
 	}
 
@@ -397,53 +403,59 @@ CraftOutput CraftDefinitionShaped::getOutput(const CraftInput &input, IGameDef *
 	return CraftOutput(output, 0);
 }
 
-void CraftDefinitionShaped::decrementInput(CraftInput &input, IGameDef *gamedef) const
+CraftInput CraftDefinitionShaped::getInput(const CraftOutput &output, IGameDef *gamedef) const
 {
-	craftDecrementOrReplaceInput(input, replacements, gamedef);
+	return CraftInput(CRAFT_METHOD_NORMAL,width,craftGetItems(recipe,gamedef));
 }
 
-std::string CraftDefinitionShaped::dump() const
+void CraftDefinitionShaped::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+	 IGameDef *gamedef) const
 {
-	std::ostringstream os(std::ios::binary);
-	os<<"(shaped, output=\""<<output
-		<<"\", recipe="<<craftDumpMatrix(recipe, width)
-		<<", replacements="<<replacements.dump()<<")";
-	return os.str();
+	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 }
 
-void CraftDefinitionShaped::serializeBody(std::ostream &os) const
+CraftHashType CraftDefinitionShaped::getHashType() const
 {
-	os<<serializeString(output);
-	writeU16(os, width);
-	writeU16(os, recipe.size());
-	for(u32 i=0; i<recipe.size(); i++)
-		os<<serializeString(recipe[i]);
-	writeU16(os, replacements.pairs.size());
-	for(u32 i=0; i<replacements.pairs.size(); i++)
-	{
-		os<<serializeString(replacements.pairs[i].first);
-		os<<serializeString(replacements.pairs[i].second);
+	assert(hash_inited); // Pre-condition
+	bool has_group = false;
+	for (size_t i = 0; i < recipe_names.size(); i++) {
+		if (isGroupRecipeStr(recipe_names[i])) {
+			has_group = true;
+			break;
+		}
 	}
+	if (has_group)
+		return CRAFT_HASH_TYPE_COUNT;
+	else
+		return CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionShaped::deSerializeBody(std::istream &is, int version)
+u64 CraftDefinitionShaped::getHash(CraftHashType type) const
 {
-	if(version != 1) throw SerializationError(
-			"unsupported CraftDefinitionShaped version");
-	output = deSerializeString(is);
-	width = readU16(is);
-	recipe.clear();
-	u32 count = readU16(is);
-	for(u32 i=0; i<count; i++)
-		recipe.push_back(deSerializeString(is));
-	replacements.pairs.clear();
-	count = readU16(is);
-	for(u32 i=0; i<count; i++)
-	{
-		std::string first = deSerializeString(is);
-		std::string second = deSerializeString(is);
-		replacements.pairs.push_back(std::make_pair(first, second));
-	}
+	assert(hash_inited); // Pre-condition
+	assert((type == CRAFT_HASH_TYPE_ITEM_NAMES)
+		|| (type == CRAFT_HASH_TYPE_COUNT)); // Pre-condition
+
+	std::vector<std::string> rec_names = recipe_names;
+	std::sort(rec_names.begin(), rec_names.end());
+	return getHashForGrid(type, rec_names);
+}
+
+void CraftDefinitionShaped::initHash(IGameDef *gamedef)
+{
+	if (hash_inited)
+		return;
+	hash_inited = true;
+	recipe_names = craftGetItemNames(recipe, gamedef);
+}
+
+std::string CraftDefinitionShaped::dump() const
+{
+	std::ostringstream os(std::ios::binary);
+	os << "(shaped, output=\"" << output
+		<< "\", recipe=" << craftDumpMatrix(recipe, width)
+		<< ", replacements=" << replacements.dump() << ")";
+	return os.str();
 }
 
 /*
@@ -457,19 +469,55 @@ std::string CraftDefinitionShapeless::getName() const
 
 bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
 {
-	if(input.method != CRAFT_METHOD_NORMAL)
+	if (input.method != CRAFT_METHOD_NORMAL)
 		return false;
 
-	// Get input item multiset
-	std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
-	std::multiset<std::string> inp_names_multiset = craftMakeMultiset(inp_names);
+	// Filter empty items out of input
+	std::vector<std::string> input_filtered;
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+		const ItemStack &item = input.items[i];
+		if (item.name != "")
+			input_filtered.push_back(item.name);
+	}
 
-	// Get recipe item multiset
-	std::vector<std::string> rec_names = craftGetItemNames(recipe, gamedef);
-	std::multiset<std::string> rec_names_multiset = craftMakeMultiset(rec_names);
+	// If there is a wrong number of items in input, no match
+	if (input_filtered.size() != recipe.size()) {
+		/*dstream<<"Number of input items ("<<input_filtered.size()
+				<<") does not match recipe size ("<<recipe.size()<<") "
+				<<"of recipe with output="<<output<<std::endl;*/
+		return false;
+	}
+
+	std::vector<std::string> recipe_copy;
+	if (hash_inited)
+		recipe_copy = recipe_names;
+	else {
+		recipe_copy = craftGetItemNames(recipe, gamedef);
+		std::sort(recipe_copy.begin(), recipe_copy.end());
+	}
 
-	// Recipe is matched when the multisets coincide
-	return inp_names_multiset == rec_names_multiset;
+	// Try with all permutations of the recipe,
+	// start from the lexicographically first permutation (=sorted),
+	// recipe_names is pre-sorted
+	do {
+		// If all items match, the recipe matches
+		bool all_match = true;
+		//dstream<<"Testing recipe (output="<<output<<"):";
+		for (size_t i=0; i<recipe.size(); i++) {
+			//dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
+			if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
+					gamedef->idef())) {
+				all_match = false;
+				break;
+			}
+		}
+		//dstream<<" -> match="<<all_match<<std::endl;
+		if (all_match)
+			return true;
+	} while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
+
+	return false;
 }
 
 CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDef *gamedef) const
@@ -477,51 +525,57 @@ CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDe
 	return CraftOutput(output, 0);
 }
 
-void CraftDefinitionShapeless::decrementInput(CraftInput &input, IGameDef *gamedef) const
+CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
 {
-	craftDecrementOrReplaceInput(input, replacements, gamedef);
+	return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
 }
 
-std::string CraftDefinitionShapeless::dump() const
+void CraftDefinitionShapeless::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+	IGameDef *gamedef) const
 {
-	std::ostringstream os(std::ios::binary);
-	os<<"(shapeless, output=\""<<output
-		<<"\", recipe="<<craftDumpMatrix(recipe, recipe.size())
-		<<", replacements="<<replacements.dump()<<")";
-	return os.str();
+	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 }
 
-void CraftDefinitionShapeless::serializeBody(std::ostream &os) const
+CraftHashType CraftDefinitionShapeless::getHashType() const
 {
-	os<<serializeString(output);
-	writeU16(os, recipe.size());
-	for(u32 i=0; i<recipe.size(); i++)
-		os<<serializeString(recipe[i]);
-	writeU16(os, replacements.pairs.size());
-	for(u32 i=0; i<replacements.pairs.size(); i++)
-	{
-		os<<serializeString(replacements.pairs[i].first);
-		os<<serializeString(replacements.pairs[i].second);
+	assert(hash_inited); // Pre-condition
+	bool has_group = false;
+	for (size_t i = 0; i < recipe_names.size(); i++) {
+		if (isGroupRecipeStr(recipe_names[i])) {
+			has_group = true;
+			break;
+		}
 	}
+	if (has_group)
+		return CRAFT_HASH_TYPE_COUNT;
+	else
+		return CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionShapeless::deSerializeBody(std::istream &is, int version)
+u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
 {
-	if(version != 1) throw SerializationError(
-			"unsupported CraftDefinitionShapeless version");
-	output = deSerializeString(is);
-	recipe.clear();
-	u32 count = readU16(is);
-	for(u32 i=0; i<count; i++)
-		recipe.push_back(deSerializeString(is));
-	replacements.pairs.clear();
-	count = readU16(is);
-	for(u32 i=0; i<count; i++)
-	{
-		std::string first = deSerializeString(is);
-		std::string second = deSerializeString(is);
-		replacements.pairs.push_back(std::make_pair(first, second));
-	}
+	assert(hash_inited); // Pre-condition
+	assert(type == CRAFT_HASH_TYPE_ITEM_NAMES
+		|| type == CRAFT_HASH_TYPE_COUNT); // Pre-condition
+	return getHashForGrid(type, recipe_names);
+}
+
+void CraftDefinitionShapeless::initHash(IGameDef *gamedef)
+{
+	if (hash_inited)
+		return;
+	hash_inited = true;
+	recipe_names = craftGetItemNames(recipe, gamedef);
+	std::sort(recipe_names.begin(), recipe_names.end());
+}
+
+std::string CraftDefinitionShapeless::dump() const
+{
+	std::ostringstream os(std::ios::binary);
+	os << "(shapeless, output=\"" << output
+		<< "\", recipe=" << craftDumpMatrix(recipe, recipe.size())
+		<< ", replacements=" << replacements.dump() << ")";
+	return os.str();
 }
 
 /*
@@ -535,10 +589,9 @@ static ItemStack craftToolRepair(
 		IGameDef *gamedef)
 {
 	IItemDefManager *idef = gamedef->idef();
-	if(item1.count != 1 || item2.count != 1 || item1.name != item2.name
+	if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
 			|| idef->get(item1.name).type != ITEM_TOOL
-			|| idef->get(item2.name).type != ITEM_TOOL)
-	{
+			|| idef->get(item2.name).type != ITEM_TOOL) {
 		// Failure
 		return ItemStack();
 	}
@@ -547,9 +600,9 @@ static ItemStack craftToolRepair(
 	s32 item2_uses = 65536 - (u32) item2.wear;
 	s32 new_uses = item1_uses + item2_uses;
 	s32 new_wear = 65536 - new_uses + floor(additional_wear * 65536 + 0.5);
-	if(new_wear >= 65536)
+	if (new_wear >= 65536)
 		return ItemStack();
-	if(new_wear < 0)
+	if (new_wear < 0)
 		new_wear = 0;
 
 	ItemStack repaired = item1;
@@ -564,21 +617,19 @@ std::string CraftDefinitionToolRepair::getName() const
 
 bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
 {
-	if(input.method != CRAFT_METHOD_NORMAL)
+	if (input.method != CRAFT_METHOD_NORMAL)
 		return false;
 
 	ItemStack item1;
 	ItemStack item2;
-	for(std::vector<ItemStack>::const_iterator
-			i = input.items.begin();
-			i != input.items.end(); i++)
-	{
-		if(!i->empty())
-		{
-			if(item1.empty())
-				item1 = *i;
-			else if(item2.empty())
-				item2 = *i;
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+		const ItemStack &item = input.items[i];
+		if (!item.empty()) {
+			if (item1.empty())
+				item1 = item;
+			else if (item2.empty())
+				item2 = item;
 			else
 				return false;
 		}
@@ -591,23 +642,29 @@ CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameD
 {
 	ItemStack item1;
 	ItemStack item2;
-	for(std::vector<ItemStack>::const_iterator
-			i = input.items.begin();
-			i != input.items.end(); i++)
-	{
-		if(!i->empty())
-		{
-			if(item1.empty())
-				item1 = *i;
-			else if(item2.empty())
-				item2 = *i;
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+		const ItemStack &item = input.items[i];
+		if (!item.empty()) {
+			if (item1.empty())
+				item1 = item;
+			else if (item2.empty())
+				item2 = item;
 		}
 	}
 	ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 	return CraftOutput(repaired.getItemString(), 0);
 }
 
-void CraftDefinitionToolRepair::decrementInput(CraftInput &input, IGameDef *gamedef) const
+CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
+{
+	std::vector<ItemStack> stack;
+	stack.push_back(ItemStack());
+	return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
+}
+
+void CraftDefinitionToolRepair::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+	IGameDef *gamedef) const
 {
 	craftDecrementInput(input, gamedef);
 }
@@ -615,22 +672,10 @@ void CraftDefinitionToolRepair::decrementInput(CraftInput &input, IGameDef *game
 std::string CraftDefinitionToolRepair::dump() const
 {
 	std::ostringstream os(std::ios::binary);
-	os<<"(toolrepair, additional_wear="<<additional_wear<<")";
+	os << "(toolrepair, additional_wear=" << additional_wear << ")";
 	return os.str();
 }
 
-void CraftDefinitionToolRepair::serializeBody(std::ostream &os) const
-{
-	writeF1000(os, additional_wear);
-}
-
-void CraftDefinitionToolRepair::deSerializeBody(std::istream &is, int version)
-{
-	if(version != 1) throw SerializationError(
-			"unsupported CraftDefinitionToolRepair version");
-	additional_wear = readF1000(is);
-}
-
 /*
 	CraftDefinitionCooking
 */
@@ -642,19 +687,28 @@ std::string CraftDefinitionCooking::getName() const
 
 bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
 {
-	if(input.method != CRAFT_METHOD_COOKING)
+	if (input.method != CRAFT_METHOD_COOKING)
 		return false;
 
-	// Get input item multiset
-	std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
-	std::multiset<std::string> inp_names_multiset = craftMakeMultiset(inp_names);
+	// Filter empty items out of input
+	std::vector<std::string> input_filtered;
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+		const std::string &name = input.items[i].name;
+		if (name != "")
+			input_filtered.push_back(name);
+	}
 
-	// Get recipe item multiset
-	std::multiset<std::string> rec_names_multiset;
-	rec_names_multiset.insert(craftGetItemName(recipe, gamedef));
+	// If there is a wrong number of items in input, no match
+	if (input_filtered.size() != 1) {
+		/*dstream<<"Number of input items ("<<input_filtered.size()
+				<<") does not match recipe size (1) "
+				<<"of cooking recipe with output="<<output<<std::endl;*/
+		return false;
+	}
 
-	// Recipe is matched when the multisets coincide
-	return inp_names_multiset == rec_names_multiset;
+	// Check the single input item
+	return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 }
 
 CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
@@ -662,34 +716,56 @@ CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef
 	return CraftOutput(output, cooktime);
 }
 
-void CraftDefinitionCooking::decrementInput(CraftInput &input, IGameDef *gamedef) const
+CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef *gamedef) const
 {
-	craftDecrementInput(input, gamedef);
+	std::vector<std::string> rec;
+	rec.push_back(recipe);
+	return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
 }
 
-std::string CraftDefinitionCooking::dump() const
+void CraftDefinitionCooking::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+	IGameDef *gamedef) const
 {
-	std::ostringstream os(std::ios::binary);
-	os<<"(cooking, output=\""<<output
-		<<"\", recipe=\""<<recipe
-		<<"\", cooktime="<<cooktime<<")";
-	return os.str();
+	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 }
 
-void CraftDefinitionCooking::serializeBody(std::ostream &os) const
+CraftHashType CraftDefinitionCooking::getHashType() const
 {
-	os<<serializeString(output);
-	os<<serializeString(recipe);
-	writeF1000(os, cooktime);
+	if (isGroupRecipeStr(recipe_name))
+		return CRAFT_HASH_TYPE_COUNT;
+	else
+		return CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionCooking::deSerializeBody(std::istream &is, int version)
+u64 CraftDefinitionCooking::getHash(CraftHashType type) const
 {
-	if(version != 1) throw SerializationError(
-			"unsupported CraftDefinitionCooking version");
-	output = deSerializeString(is);
-	recipe = deSerializeString(is);
-	cooktime = readF1000(is);
+	if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
+		return getHashForString(recipe_name);
+	} else if (type == CRAFT_HASH_TYPE_COUNT) {
+		return 1;
+	} else {
+		//illegal hash type for this CraftDefinition (pre-condition)
+		assert(false);
+		return 0;
+	}
+}
+
+void CraftDefinitionCooking::initHash(IGameDef *gamedef)
+{
+	if (hash_inited)
+		return;
+	hash_inited = true;
+	recipe_name = craftGetItemName(recipe, gamedef);
+}
+
+std::string CraftDefinitionCooking::dump() const
+{
+	std::ostringstream os(std::ios::binary);
+	os << "(cooking, output=\"" << output
+		<< "\", recipe=\"" << recipe
+		<< "\", cooktime=" << cooktime << ")"
+		<< ", replacements=" << replacements.dump() << ")";
+	return os.str();
 }
 
 /*
@@ -703,19 +779,28 @@ std::string CraftDefinitionFuel::getName() const
 
 bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
 {
-	if(input.method != CRAFT_METHOD_FUEL)
+	if (input.method != CRAFT_METHOD_FUEL)
 		return false;
 
-	// Get input item multiset
-	std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
-	std::multiset<std::string> inp_names_multiset = craftMakeMultiset(inp_names);
+	// Filter empty items out of input
+	std::vector<std::string> input_filtered;
+	for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+		const std::string &name = input.items[i].name;
+		if (name != "")
+			input_filtered.push_back(name);
+	}
 
-	// Get recipe item multiset
-	std::multiset<std::string> rec_names_multiset;
-	rec_names_multiset.insert(craftGetItemName(recipe, gamedef));
+	// If there is a wrong number of items in input, no match
+	if (input_filtered.size() != 1) {
+		/*dstream<<"Number of input items ("<<input_filtered.size()
+				<<") does not match recipe size (1) "
+				<<"of fuel recipe with burntime="<<burntime<<std::endl;*/
+		return false;
+	}
 
-	// Recipe is matched when the multisets coincide
-	return inp_names_multiset == rec_names_multiset;
+	// Check the single input item
+	return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 }
 
 CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
@@ -723,31 +808,54 @@ CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *ga
 	return CraftOutput("", burntime);
 }
 
-void CraftDefinitionFuel::decrementInput(CraftInput &input, IGameDef *gamedef) const
+CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *gamedef) const
 {
-	craftDecrementInput(input, gamedef);
+	std::vector<std::string> rec;
+	rec.push_back(recipe);
+	return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
 }
 
-std::string CraftDefinitionFuel::dump() const
+void CraftDefinitionFuel::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+	IGameDef *gamedef) const
 {
-	std::ostringstream os(std::ios::binary);
-	os<<"(fuel, recipe=\""<<recipe
-		<<"\", burntime="<<burntime<<")";
-	return os.str();
+	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
+}
+
+CraftHashType CraftDefinitionFuel::getHashType() const
+{
+	if (isGroupRecipeStr(recipe_name))
+		return CRAFT_HASH_TYPE_COUNT;
+	else
+		return CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionFuel::serializeBody(std::ostream &os) const
+u64 CraftDefinitionFuel::getHash(CraftHashType type) const
 {
-	os<<serializeString(recipe);
-	writeF1000(os, burntime);
+	if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
+		return getHashForString(recipe_name);
+	} else if (type == CRAFT_HASH_TYPE_COUNT) {
+		return 1;
+	} else {
+		//illegal hash type for this CraftDefinition (pre-condition)
+		assert(false);
+		return 0;
+	}
 }
 
-void CraftDefinitionFuel::deSerializeBody(std::istream &is, int version)
+void CraftDefinitionFuel::initHash(IGameDef *gamedef)
 {
-	if(version != 1) throw SerializationError(
-			"unsupported CraftDefinitionFuel version");
-	recipe = deSerializeString(is);
-	burntime = readF1000(is);
+	if (hash_inited)
+		return;
+	hash_inited = true;
+	recipe_name = craftGetItemName(recipe, gamedef);
+}
+std::string CraftDefinitionFuel::dump() const
+{
+	std::ostringstream os(std::ios::binary);
+	os << "(fuel, recipe=\"" << recipe
+		<< "\", burntime=" << burntime << ")"
+		<< ", replacements=" << replacements.dump() << ")";
+	return os.str();
 }
 
 /*
@@ -757,127 +865,264 @@ void CraftDefinitionFuel::deSerializeBody(std::istream &is, int version)
 class CCraftDefManager: public IWritableCraftDefManager
 {
 public:
+	CCraftDefManager()
+	{
+		m_craft_defs.resize(craft_hash_type_max + 1);
+	}
+
 	virtual ~CCraftDefManager()
 	{
 		clear();
 	}
+
 	virtual bool getCraftResult(CraftInput &input, CraftOutput &output,
-			bool decrementInput, IGameDef *gamedef) const
+			std::vector<ItemStack> &output_replacement, bool decrementInput,
+			IGameDef *gamedef) const
 	{
 		output.item = "";
 		output.time = 0;
 
 		// If all input items are empty, abort.
 		bool all_empty = true;
-		for(std::vector<ItemStack>::const_iterator
-				i = input.items.begin();
-				i != input.items.end(); i++)
-		{
-			if(!i->empty())
-			{
+		for (std::vector<ItemStack>::size_type i = 0;
+			i < input.items.size(); i++) {
+			if (!input.items[i].empty()) {
 				all_empty = false;
 				break;
 			}
 		}
-		if(all_empty)
+		if (all_empty)
 			return false;
 
-		// Walk crafting definitions from back to front, so that later
-		// definitions can override earlier ones.
-		for(std::vector<CraftDefinition*>::const_reverse_iterator
-				i = m_craft_definitions.rbegin();
-				i != m_craft_definitions.rend(); i++)
-		{
-			CraftDefinition *def = *i;
+		std::vector<std::string> input_names;
+		input_names = craftGetItemNames(input.items, gamedef);
+		std::sort(input_names.begin(), input_names.end());
+
+		// Try hash types with increasing collision rate, and return if found.
+		for (int type = 0; type <= craft_hash_type_max; type++) {
+			u64 hash = getHashForGrid((CraftHashType) type, input_names);
+
+			/*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/
+
+			// We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];"
+			// but that doesn't compile for some reason. This does.
+			std::map<u64, std::vector<CraftDefinition*> >::const_iterator
+				col_iter = (m_craft_defs[type]).find(hash);
 
-			/*infostream<<"Checking "<<input.dump()<<std::endl
-					<<" against "<<def->dump()<<std::endl;*/
+			if (col_iter == (m_craft_defs[type]).end())
+				continue;
 
-			try {
-				if(def->check(input, gamedef))
-				{
+			const std::vector<CraftDefinition*> &hash_collisions = col_iter->second;
+			// Walk crafting definitions from back to front, so that later
+			// definitions can override earlier ones.
+			for (std::vector<CraftDefinition*>::size_type
+					i = hash_collisions.size(); i > 0; i--) {
+				CraftDefinition *def = hash_collisions[i - 1];
+
+				/*errorstream << "Checking " << input.dump() << std::endl
+					<< " against " << def->dump() << std::endl;*/
+
+				if (def->check(input, gamedef)) {
 					// Get output, then decrement input (if requested)
 					output = def->getOutput(input, gamedef);
-					if(decrementInput)
-						def->decrementInput(input, gamedef);
+					if (decrementInput)
+						def->decrementInput(input, output_replacement, gamedef);
+					/*errorstream << "Check RETURNS TRUE" << std::endl;*/
 					return true;
 				}
 			}
-			catch(SerializationError &e)
-			{
-				errorstream<<"getCraftResult: ERROR: "
-						<<"Serialization error in recipe "
-						<<def->dump()<<std::endl;
-				// then go on with the next craft definition
-			}
 		}
 		return false;
 	}
+
+	virtual std::vector<CraftDefinition*> getCraftRecipes(CraftOutput &output,
+			IGameDef *gamedef, unsigned limit=0) const
+	{
+		std::vector<CraftDefinition*> recipes;
+
+		std::map<std::string, std::vector<CraftDefinition*> >::const_iterator
+			vec_iter = m_output_craft_definitions.find(output.item);
+
+		if (vec_iter == m_output_craft_definitions.end())
+			return recipes;
+
+		const std::vector<CraftDefinition*> &vec = vec_iter->second;
+
+		recipes.reserve(limit ? MYMIN(limit, vec.size()) : vec.size());
+
+		for (std::vector<CraftDefinition*>::size_type i = vec.size();
+				i > 0; i--) {
+			CraftDefinition *def = vec[i - 1];
+			if (limit && recipes.size() >= limit)
+				break;
+			recipes.push_back(def);
+		}
+
+		return recipes;
+	}
+
+	virtual bool clearCraftRecipesByOutput(const CraftOutput &output, IGameDef *gamedef)
+	{
+		std::map<std::string, std::vector<CraftDefinition*> >::iterator vec_iter =
+			m_output_craft_definitions.find(output.item);
+
+		if (vec_iter == m_output_craft_definitions.end())
+			return false;
+
+		std::vector<CraftDefinition*> &vec = vec_iter->second;
+		for (std::vector<CraftDefinition*>::iterator i = vec.begin();
+				i != vec.end(); ++i) {
+			CraftDefinition *def = *i;
+			// Recipes are not yet hashed at this point
+			std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
+			std::vector<CraftDefinition*> new_vec_by_input;
+			/* We will preallocate necessary memory addresses, so we don't need to reallocate them later.
+				This would save us some performance. */
+			new_vec_by_input.reserve(unhashed_inputs_vec.size());
+			for (std::vector<CraftDefinition*>::iterator i2 = unhashed_inputs_vec.begin();
+					i2 != unhashed_inputs_vec.end(); ++i2) {
+				if (def != *i2) {
+					new_vec_by_input.push_back(*i2);
+				}
+			}
+			m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
+		}
+		m_output_craft_definitions.erase(output.item);
+		return true;
+	}
+
+	virtual bool clearCraftRecipesByInput(CraftMethod craft_method, unsigned int craft_grid_width,
+		const std::vector<std::string> &recipe, IGameDef *gamedef)
+	{
+		bool all_empty = true;
+		for (std::vector<std::string>::size_type i = 0;
+				i < recipe.size(); i++) {
+			if (!recipe[i].empty()) {
+				all_empty = false;
+				break;
+			}
+		}
+		if (all_empty)
+			return false;
+
+		CraftInput input(craft_method, craft_grid_width, craftGetItems(recipe, gamedef));
+		// Recipes are not yet hashed at this point
+		std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
+		std::vector<CraftDefinition*> new_vec_by_input;
+		bool got_hit = false;
+		for (std::vector<CraftDefinition*>::size_type
+				i = unhashed_inputs_vec.size(); i > 0; i--) {
+			CraftDefinition *def = unhashed_inputs_vec[i - 1];
+			/* If the input doesn't match the recipe definition, this recipe definition later
+				will be added back in source map. */
+			if (!def->check(input, gamedef)) {
+				new_vec_by_input.push_back(def);
+				continue;
+			}
+			CraftOutput output = def->getOutput(input, gamedef);
+			got_hit = true;
+			std::map<std::string, std::vector<CraftDefinition*> >::iterator
+				vec_iter = m_output_craft_definitions.find(output.item);
+			if (vec_iter == m_output_craft_definitions.end())
+				continue;
+			std::vector<CraftDefinition*> &vec = vec_iter->second;
+			std::vector<CraftDefinition*> new_vec_by_output;
+			/* We will preallocate necessary memory addresses, so we don't need
+				to reallocate them later. This would save us some performance. */
+			new_vec_by_output.reserve(vec.size());
+			for (std::vector<CraftDefinition*>::iterator i = vec.begin();
+					i != vec.end(); ++i) {
+				/* If pointers from map by input and output are not same,
+					we will add 'CraftDefinition*' to a new vector. */
+				if (def != *i) {
+					/* Adding dereferenced iterator value (which are
+						'CraftDefinition' reference) to a new vector. */
+					new_vec_by_output.push_back(*i);
+				}
+			}
+			// Swaps assigned to current key value with new vector for output map.
+			m_output_craft_definitions[output.item].swap(new_vec_by_output);
+		}
+		if (got_hit)
+			// Swaps value with new vector for input map.
+			m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
+
+		return got_hit;
+	}
+
 	virtual std::string dump() const
 	{
 		std::ostringstream os(std::ios::binary);
-		os<<"Crafting definitions:\n";
-		for(std::vector<CraftDefinition*>::const_iterator
-				i = m_craft_definitions.begin();
-				i != m_craft_definitions.end(); i++)
-		{
-			os<<(*i)->dump()<<"\n";
+		os << "Crafting definitions:\n";
+		for (int type = 0; type <= craft_hash_type_max; ++type) {
+			for (std::map<u64, std::vector<CraftDefinition*> >::const_iterator
+					it = (m_craft_defs[type]).begin();
+					it != (m_craft_defs[type]).end(); ++it) {
+				for (std::vector<CraftDefinition*>::size_type i = 0;
+						i < it->second.size(); i++) {
+					os << "type " << type
+						<< " hash " << it->first
+						<< " def " << it->second[i]->dump()
+						<< "\n";
+				}
+			}
 		}
 		return os.str();
 	}
-	virtual void registerCraft(CraftDefinition *def)
+	virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef)
 	{
-		verbosestream<<"registerCraft: registering craft definition: "
-				<<def->dump()<<std::endl;
-		m_craft_definitions.push_back(def);
+		verbosestream << "registerCraft: registering craft definition: "
+				<< def->dump() << std::endl;
+		m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def);
+
+		CraftInput input;
+		std::string output_name = craftGetItemName(
+				def->getOutput(input, gamedef).item, gamedef);
+		m_output_craft_definitions[output_name].push_back(def);
 	}
 	virtual void clear()
 	{
-		for(std::vector<CraftDefinition*>::iterator
-				i = m_craft_definitions.begin();
-				i != m_craft_definitions.end(); i++){
-			delete *i;
-		}
-		m_craft_definitions.clear();
-	}
-	virtual void serialize(std::ostream &os) const
-	{
-		writeU8(os, 0); // version
-		u16 count = m_craft_definitions.size();
-		writeU16(os, count);
-		for(std::vector<CraftDefinition*>::const_iterator
-				i = m_craft_definitions.begin();
-				i != m_craft_definitions.end(); i++){
-			CraftDefinition *def = *i;
-			// Serialize wrapped in a string
-			std::ostringstream tmp_os(std::ios::binary);
-			def->serialize(tmp_os);
-			os<<serializeString(tmp_os.str());
+		for (int type = 0; type <= craft_hash_type_max; ++type) {
+			for (std::map<u64, std::vector<CraftDefinition*> >::iterator
+					it = m_craft_defs[type].begin();
+					it != m_craft_defs[type].end(); ++it) {
+				for (std::vector<CraftDefinition*>::iterator
+						iit = it->second.begin();
+						iit != it->second.end(); ++iit) {
+					delete *iit;
+				}
+				it->second.clear();
+			}
+			m_craft_defs[type].clear();
 		}
+		m_output_craft_definitions.clear();
 	}
-	virtual void deSerialize(std::istream &is)
+	virtual void initHashes(IGameDef *gamedef)
 	{
-		// Clear everything
-		clear();
-		// Deserialize
-		int version = readU8(is);
-		if(version != 0) throw SerializationError(
-				"unsupported CraftDefManager version");
-		u16 count = readU16(is);
-		for(u16 i=0; i<count; i++){
-			// Deserialize a string and grab a CraftDefinition from it
-			std::istringstream tmp_is(deSerializeString(is), std::ios::binary);
-			CraftDefinition *def = CraftDefinition::deSerialize(tmp_is);
-			// Register
-			registerCraft(def);
+		// Move the CraftDefs from the unhashed layer into layers higher up.
+		std::vector<CraftDefinition *> &unhashed =
+			m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
+		for (std::vector<CraftDefinition*>::size_type i = 0;
+			i < unhashed.size(); i++) {
+			CraftDefinition *def = unhashed[i];
+
+			// Initialize and get the definition's hash
+			def->initHash(gamedef);
+			CraftHashType type = def->getHashType();
+			u64 hash = def->getHash(type);
+
+			// Enter the definition
+			m_craft_defs[type][hash].push_back(def);
 		}
+		unhashed.clear();
 	}
 private:
-	std::vector<CraftDefinition*> m_craft_definitions;
+	//TODO: change both maps to unordered_map when c++11 can be used
+	std::vector<std::map<u64, std::vector<CraftDefinition*> > > m_craft_defs;
+	std::map<std::string, std::vector<CraftDefinition*> > m_output_craft_definitions;
 };
 
 IWritableCraftDefManager* createCraftDefManager()
 {
 	return new CCraftDefManager();
 }
-