plugins/net.mograsim.logic.model.am2900/src/net/mograsim/logic/model/NANDOptimizer.java

   1 package net.mograsim.logic.model;
   2
   3 import java.math.BigInteger;
   4 import java.util.ArrayList;
   5 import java.util.HashMap;
   6 import java.util.List;
   7 import java.util.Map;
   8 import java.util.Map.Entry;
   9 import java.util.Set;
  10
  11 public class NANDOptimizer
  12 {
  13         public static void main(String[] args)
  14         {
  15                 System.out.println(optimize(3, Set.of(0b001, 0b010, 0b011, 0b100), Set.of(0b000)));
  16         }
  17
  18         private static String optimize(int bitCount, Set<Integer> combinationsRequiredZero, Set<Integer> combinationsRequiredOne)
  19         {
  20                 BigInteger maskZeroes = combinationsRequiredZero.stream().map(BigInteger.ONE::shiftLeft).reduce(BigInteger.ZERO, BigInteger::or);
  21                 BigInteger maskOnes = combinationsRequiredOne.stream().map(BigInteger.ONE::shiftLeft).reduce(BigInteger.ZERO, BigInteger::or);
  22                 if (maskZeroes.and(maskOnes).compareTo(BigInteger.ZERO) != 0)
  23                         throw new IllegalArgumentException("A combination is required to be both 1 and 0");
  24                 BigInteger mask = maskZeroes.or(maskOnes);
  25                 BigInteger target = maskOnes;
  26
  27                 return optimize(bitCount, mask, target);
  28         }
  29
  30         public static String optimize(int bitCount, BigInteger mask, BigInteger target)
  31         {
  32                 long start = System.currentTimeMillis();
  33                 Map<BigInteger, String> atomicCombinations = generateAtomicCombinations(bitCount);
  34
  35                 for (Entry<BigInteger, String> e : atomicCombinations.entrySet())
  36                         if (check(e.getKey(), target, mask))
  37                                 return e.getValue();
  38
  39                 List<Map<BigInteger, String>> mapPool = new ArrayList<>();
  40                 mapPool.add(new HashMap<>());
  41
  42                 for (int gateCount = 1;; gateCount++)
  43                 {
  44                         mapPool.add(new HashMap<>());
  45                         System.out.println("Checking gateCount " + gateCount + "...");
  46                         String optimized = optimize(atomicCombinations, mask, target, gateCount, mapPool.toArray(Map[]::new));
  47                         if (optimized != null)
  48                         {
  49                                 long stop = System.currentTimeMillis();
  50                                 System.out.println("Took " + (stop - start));
  51                                 return optimized;
  52                         }
  53                 }
  54         }
  55
  56         @SuppressWarnings("null")
  57         private static String optimize(Map<BigInteger, String> availableCombinations, BigInteger mask, BigInteger target, int remainingGates,
  58                         Map<BigInteger, String>[] mapPool)
  59         {
  60                 final boolean deeperLevelExists = remainingGates != 1;
  61                 Map<BigInteger, String> availableCombinationsCopy;
  62                 if (deeperLevelExists)
  63                 {
  64                         availableCombinationsCopy = mapPool[remainingGates];
  65                         availableCombinationsCopy.putAll(availableCombinations);
  66                 } else
  67                         availableCombinationsCopy = null;
  68                 for (Entry<BigInteger, String> source1 : availableCombinations.entrySet())
  69                         for (Entry<BigInteger, String> source2 : availableCombinations.entrySet())
  70                         {
  71                                 BigInteger nand = nand(source1.getKey(), source2.getKey());
  72                                 if (availableCombinations.containsKey(nand))
  73                                         continue;
  74                                 String name = '(' + source1.getValue() + ' ' + source2.getValue() + ')';
  75                                 if (deeperLevelExists)
  76                                 {
  77                                         availableCombinationsCopy.put(nand, name);
  78                                         String result = optimize(availableCombinationsCopy, mask, target, remainingGates - 1, mapPool);
  79                                         if (result != null)
  80                                                 return result;
  81                                         availableCombinationsCopy.remove(nand);
  82                                 } else if (check(nand, target, mask))
  83                                         return name;
  84                         }
  85
  86                 if (deeperLevelExists)
  87                         availableCombinationsCopy.clear();
  88                 return null;
  89         }
  90
  91         private static boolean check(BigInteger combination, BigInteger target, BigInteger mask)
  92         {
  93                 return combination.xor(target).and(mask).compareTo(BigInteger.ZERO) == 0;
  94         }
  95
  96         private static Map<BigInteger, String> generateAtomicCombinations(int bitCount)
  97         {
  98                 Map<BigInteger, String> atomicCombinations = new HashMap<>();
  99                 for (int bit = 0; bit < bitCount; bit++)
 100                 {
 101                         BigInteger atomicCombination = BigInteger.ZERO;
 102                         for (int i = 1 << bit; i < 1 << bitCount; i += 2 << bit)
 103                                 for (int j = 0; j < 1 << bit; j++)
 104                                         atomicCombination = atomicCombination.or(BigInteger.ONE.shiftLeft(i + j));
 105                         atomicCombinations.put(atomicCombination, Integer.toString(bit));
 106                 }
 107                 return atomicCombinations;
 108         }
 109
 110         private static BigInteger nand(BigInteger a, BigInteger b)
 111         {
 112                 return b.and(a).not();
 113         }
 114 }