src/openpower/decoder/quine.py

   1 # https://stackoverflow.com/questions/14860967/
   2 # https://stackoverflow.com/questions/7537125/
   3
   4 def collapse(patterns):
   5     """Reduce patterns into compact dash notation"""
   6     newPatterns = []  # reduced patterns
   7     matched = []      # indexes with a string that was already matched
   8     for x, p1 in enumerate(patterns):    # pattern1
   9         if x in matched: continue        # skip if this pattern already matched
  10         for y, p2 in enumerate(patterns[x+1:], 1):
  11             if x+y in matched: continue  # skip if this pattern already matched
  12             diffs = 0                    # number of differences found
  13             for idx, bit in enumerate(zip(p1, p2)):
  14                 if bit[0] != bit[1]:     # count of bits that are different
  15                     diffs += 1
  16                     dbit = idx
  17                 if diffs > 1: break
  18             # if exactly 1 bit different between the two,
  19             # they can be compressed together
  20             if diffs == 1:
  21                 newPatterns.append('-'.join([p1[:dbit], p1[dbit+1:]]))
  22                 matched+=[x,x+y]
  23                 break
  24         # if the pattern wasn't matched, just append it as is.
  25         if x not in matched: newPatterns.append(p1)
  26
  27     # if reductions occurred on this run, then call again
  28     # to check if more are possible.
  29     if matched:
  30         newPatterns = collapse(newPatterns)
  31
  32     return newPatterns
  33
  34 if __name__ == '__main__':
  35
  36     isel = [
  37     "0000001111",
  38     "0000101111",
  39     "0001001111",
  40     "0001101111",
  41     "0010001111",
  42     "0010101111",
  43     "0011001111",
  44     "0011101111",
  45     "0100001111",
  46     "0100101111",
  47     "0101001111",
  48     "0101101111",
  49     "0110001111",
  50     "0110101111",
  51     "0111001111",
  52     "0111101111",
  53     "1000001111",
  54     "1000101111",
  55     "1001001111",
  56     "1001101111",
  57     "1010001111",
  58     "1010101111",
  59     "1011001111",
  60     "1011101111",
  61     "1100001111",
  62     "1100101111",
  63     "1101001111",
  64     "1101101111",
  65     "1110001111",
  66     "1110101111",
  67     "1111001111",
  68     "1111101111",
  69     ]
  70     isel1 = collapse(isel)
  71     print ("isel", isel1)
  72
  73     svshape = [
  74     "0000-011001",
  75     "0001-011001",
  76     "0010-011001",
  77     "0011-011001",
  78     "0100-011001",
  79     "0101-011001",
  80     "0110-011001",
  81     "0111-011001",
  82     "1010-011001",
  83     "1011-011001",
  84     "1100-011001",
  85     "1101-011001",
  86     "1110-011001",
  87     "1111-011001",
  88     ]
  89
  90     svshape1 = collapse(svshape)
  91     print ("svshape", svshape1)