From: Daniel Kirschten Date: Sat, 2 May 2020 12:26:28 +0000 (+0200) Subject: Moved NANDOptimizer to the examples package X-Git-Url: https://mograsim.net/gitweb/?p=Mograsim.git;a=commitdiff_plain;h=20805251537990b39583d79e4a8934c32f79e1ae Moved NANDOptimizer to the examples package --- 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 deleted file mode 100644 index 9e5ee62b..00000000 --- a/plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/NANDOptimizer.java +++ /dev/null @@ -1,114 +0,0 @@ -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 combinationsRequiredZero, Set 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 atomicCombinations = generateAtomicCombinations(bitCount); - - for (Entry e : atomicCombinations.entrySet()) - if (check(e.getKey(), target, mask)) - return e.getValue(); - - List> 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 availableCombinations, BigInteger mask, BigInteger target, int remainingGates, - Map[] mapPool) - { - final boolean deeperLevelExists = remainingGates != 1; - Map availableCombinationsCopy; - if (deeperLevelExists) - { - availableCombinationsCopy = mapPool[remainingGates]; - availableCombinationsCopy.putAll(availableCombinations); - } else - availableCombinationsCopy = null; - for (Entry source1 : availableCombinations.entrySet()) - for (Entry 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 generateAtomicCombinations(int bitCount) - { - Map 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(); - } -} diff --git a/plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/examples/NANDOptimizer.java b/plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/examples/NANDOptimizer.java new file mode 100644 index 00000000..d5f37a52 --- /dev/null +++ b/plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/examples/NANDOptimizer.java @@ -0,0 +1,114 @@ +package net.mograsim.logic.model.examples; + +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 combinationsRequiredZero, Set 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 atomicCombinations = generateAtomicCombinations(bitCount); + + for (Entry e : atomicCombinations.entrySet()) + if (check(e.getKey(), target, mask)) + return e.getValue(); + + List> 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 availableCombinations, BigInteger mask, BigInteger target, int remainingGates, + Map[] mapPool) + { + final boolean deeperLevelExists = remainingGates != 1; + Map availableCombinationsCopy; + if (deeperLevelExists) + { + availableCombinationsCopy = mapPool[remainingGates]; + availableCombinationsCopy.putAll(availableCombinations); + } else + availableCombinationsCopy = null; + for (Entry source1 : availableCombinations.entrySet()) + for (Entry 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 generateAtomicCombinations(int bitCount) + { + Map 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(); + } +}