From ec71c9fb2f2d458891839b09579829b96f303a22 Mon Sep 17 00:00:00 2001
From: Daniel Kirschten <daniel.kirschten@gmx.de>
Date: Sat, 2 May 2020 13:49:57 +0200
Subject: [PATCH] Wrote a utility optimizing NAND gate count for a given truth
 table

---
 .../mograsim/logic/model/NANDOptimizer.java   | 114 ++++++++++++++++++
 1 file changed, 114 insertions(+)
 create mode 100644 plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/NANDOptimizer.java

diff --git a/plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/NANDOptimizer.java b/plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/NANDOptimizer.java
new file mode 100644
index 00000000..9e5ee62b
--- /dev/null
+++ b/plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/NANDOptimizer.java
@@ -0,0 +1,114 @@
+package net.mograsim.logic.model;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+public class NANDOptimizer
+{
+	public static void main(String[] args)
+	{
+		System.out.println(optimize(3, Set.of(0b001, 0b010, 0b011, 0b100), Set.of(0b000)));
+	}
+
+	private static String optimize(int bitCount, Set<Integer> combinationsRequiredZero, Set<Integer> combinationsRequiredOne)
+	{
+		BigInteger maskZeroes = combinationsRequiredZero.stream().map(BigInteger.ONE::shiftLeft).reduce(BigInteger.ZERO, BigInteger::or);
+		BigInteger maskOnes = combinationsRequiredOne.stream().map(BigInteger.ONE::shiftLeft).reduce(BigInteger.ZERO, BigInteger::or);
+		if (maskZeroes.and(maskOnes).compareTo(BigInteger.ZERO) != 0)
+			throw new IllegalArgumentException("A combination is required to be both 1 and 0");
+		BigInteger mask = maskZeroes.or(maskOnes);
+		BigInteger target = maskOnes;
+
+		return optimize(bitCount, mask, target);
+	}
+
+	public static String optimize(int bitCount, BigInteger mask, BigInteger target)
+	{
+		long start = System.currentTimeMillis();
+		Map<BigInteger, String> atomicCombinations = generateAtomicCombinations(bitCount);
+
+		for (Entry<BigInteger, String> e : atomicCombinations.entrySet())
+			if (check(e.getKey(), target, mask))
+				return e.getValue();
+
+		List<Map<BigInteger, String>> mapPool = new ArrayList<>();
+		mapPool.add(new HashMap<>());
+
+		for (int gateCount = 1;; gateCount++)
+		{
+			mapPool.add(new HashMap<>());
+			System.out.println("Checking gateCount " + gateCount + "...");
+			String optimized = optimize(atomicCombinations, mask, target, gateCount, mapPool.toArray(Map[]::new));
+			if (optimized != null)
+			{
+				long stop = System.currentTimeMillis();
+				System.out.println("Took " + (stop - start));
+				return optimized;
+			}
+		}
+	}
+
+	@SuppressWarnings("null")
+	private static String optimize(Map<BigInteger, String> availableCombinations, BigInteger mask, BigInteger target, int remainingGates,
+			Map<BigInteger, String>[] mapPool)
+	{
+		final boolean deeperLevelExists = remainingGates != 1;
+		Map<BigInteger, String> availableCombinationsCopy;
+		if (deeperLevelExists)
+		{
+			availableCombinationsCopy = mapPool[remainingGates];
+			availableCombinationsCopy.putAll(availableCombinations);
+		} else
+			availableCombinationsCopy = null;
+		for (Entry<BigInteger, String> source1 : availableCombinations.entrySet())
+			for (Entry<BigInteger, String> source2 : availableCombinations.entrySet())
+			{
+				BigInteger nand = nand(source1.getKey(), source2.getKey());
+				if (availableCombinations.containsKey(nand))
+					continue;
+				String name = '(' + source1.getValue() + ' ' + source2.getValue() + ')';
+				if (deeperLevelExists)
+				{
+					availableCombinationsCopy.put(nand, name);
+					String result = optimize(availableCombinationsCopy, mask, target, remainingGates - 1, mapPool);
+					if (result != null)
+						return result;
+					availableCombinationsCopy.remove(nand);
+				} else if (check(nand, target, mask))
+					return name;
+			}
+
+		if (deeperLevelExists)
+			availableCombinationsCopy.clear();
+		return null;
+	}
+
+	private static boolean check(BigInteger combination, BigInteger target, BigInteger mask)
+	{
+		return combination.xor(target).and(mask).compareTo(BigInteger.ZERO) == 0;
+	}
+
+	private static Map<BigInteger, String> generateAtomicCombinations(int bitCount)
+	{
+		Map<BigInteger, String> atomicCombinations = new HashMap<>();
+		for (int bit = 0; bit < bitCount; bit++)
+		{
+			BigInteger atomicCombination = BigInteger.ZERO;
+			for (int i = 1 << bit; i < 1 << bitCount; i += 2 << bit)
+				for (int j = 0; j < 1 << bit; j++)
+					atomicCombination = atomicCombination.or(BigInteger.ONE.shiftLeft(i + j));
+			atomicCombinations.put(atomicCombination, Integer.toString(bit));
+		}
+		return atomicCombinations;
+	}
+
+	private static BigInteger nand(BigInteger a, BigInteger b)
+	{
+		return b.and(a).not();
+	}
+}
-- 
2.17.1