224 lines
5.6 KiB
Python
224 lines
5.6 KiB
Python
from itertools import combinations
|
|
import sys
|
|
|
|
import queue
|
|
|
|
#sys.setrecursionlimit(500)
|
|
|
|
ops = {"SET1":0,"FLIP":1}
|
|
|
|
|
|
def generate_truth_table(inp_offsets,ans_offsets,logic,size = -1):
|
|
if(size == -1):
|
|
size = len(inp_offsets)+len(ans_offsets)
|
|
inp_list = [x for x in range(0,1<<size)]
|
|
ans_list = []
|
|
for inp in inp_list:
|
|
actual_paras = [((inp >> x) &1) for x in inp_offsets]
|
|
outs = logic(actual_paras)
|
|
ans = 0
|
|
for i in range(0,len(outs)):
|
|
ans += outs[i] << ans_offsets[i]
|
|
ans_list.append(ans)
|
|
return [[inp_list[i],ans_list[i]] for i in range(0,1<<size)]
|
|
|
|
def logic_and(inp):
|
|
return [inp[0],inp[1],inp[0] & inp[1]]
|
|
def logic_or(inp):
|
|
return [inp[0],inp[1],inp[0] | inp[1]]
|
|
|
|
def logic_full_adder(inp):
|
|
return [inp[0],inp[1],inp[2],(inp[0] ^ inp[1]) ^ inp[2], ((inp[0] ^ inp[1]) & inp[2]) | (inp[1] & inp[2]) ]
|
|
truthTable = generate_truth_table([0,1],[0,1,2],logic_and,5)
|
|
|
|
|
|
cell_size = (bin(len(truthTable)-1)).count('1')
|
|
inp = 0
|
|
for index,_ in truthTable:
|
|
inp <<= cell_size
|
|
inp |= index
|
|
|
|
ans = 0
|
|
for _,index in truthTable:
|
|
ans <<= cell_size
|
|
ans |= index
|
|
|
|
def generate_ins(exception,size = cell_size):
|
|
lst = [index for index in range(0,size+1) if index != exception+1]
|
|
ans = []
|
|
for i in range(1,len(lst)+1):
|
|
for com in combinations(lst,i):
|
|
tmp = 0
|
|
for j in com:
|
|
tmp += 1<<j
|
|
ans.append(tmp)
|
|
return(ans)
|
|
|
|
def ror_to_next(operand,size = cell_size,numeric = (1<<cell_size)):
|
|
return ((operand << size*(numeric-1)) | (operand >> size)) & ((1<<(size*numeric))-1)
|
|
|
|
visited_stat = {}
|
|
visited_op = {}
|
|
def operate(stat,sacrifice,ins = ops["FLIP"]):
|
|
#
|
|
next_stat = stat
|
|
if (stat,(sacrifice,ins)) in visited_stat:
|
|
return(visited_stat[(stat,(sacrifice,ins))])
|
|
for _ in range(0,1<<cell_size):
|
|
if((next_stat >> sacrifice) & 1):
|
|
next_stat &= ~(1<<sacrifice)
|
|
if not (ins & 1):
|
|
next_stat |= (ins>>1)
|
|
else:
|
|
next_stat ^= (ins>>1)
|
|
next_stat = ror_to_next(next_stat)
|
|
visited_stat[(stat,(sacrifice,ins))] = next_stat
|
|
if not next_stat in visited_op:
|
|
visited_op[next_stat] = (stat,(sacrifice,ins))
|
|
return(next_stat)
|
|
|
|
|
|
ins_table = [generate_ins(i) for i in range(0,cell_size)]
|
|
|
|
|
|
stat_que = queue.Queue()
|
|
|
|
remembered_stat = set()
|
|
|
|
def bfs(layer = 1):
|
|
print("LAYER:",layer,"STAT_COUNT:",stat_que.qsize())
|
|
for _ in range(0,stat_que.qsize()):
|
|
stat = stat_que.get()
|
|
if(stat == ans):
|
|
return (True)
|
|
for i in range(0,len(ins_table)):
|
|
for ins in ins_table[i]:
|
|
next_stat = operate(stat,i,ins)
|
|
if not next_stat in remembered_stat:
|
|
stat_que.put(next_stat)
|
|
remembered_stat.add(next_stat)
|
|
|
|
if stat_que.empty():
|
|
return False
|
|
return bfs(layer+1)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
tmp_inp = inp
|
|
|
|
def calculate_influence(truth_table):
|
|
influence_list = []
|
|
for k in range(0,cell_size):
|
|
influence=0
|
|
for i in range(0,len(truth_table)):
|
|
before = truth_table[i].copy()
|
|
after = truth_table[(before[0]) ^ (1<<k)].copy()
|
|
for j in range(0,cell_size):
|
|
if(((before[1]) & 1) != ((after[1]) &1) ):
|
|
influence += 1
|
|
before[1] >>=1
|
|
after[1] >>=1
|
|
influence_list.append(influence)
|
|
return influence_list
|
|
|
|
bitInfluences = calculate_influence(truthTable)
|
|
tmp_stat = inp
|
|
|
|
for i in [index for index in range(0,len(bitInfluences)) if bitInfluences[index] == 0]:
|
|
remembered_stat.add(tmp_stat)
|
|
tmp_stat = operate(tmp_stat,i)
|
|
remembered_stat.add(tmp_stat)
|
|
stat_que.put(tmp_stat)
|
|
|
|
|
|
|
|
|
|
|
|
bit_nickname = {}
|
|
for i in range(0,cell_size):
|
|
bit_nickname[i] = '%'+str(i+1)
|
|
|
|
|
|
|
|
|
|
bit_nickname[0] = "%1"
|
|
bit_nickname[1] = "%2"
|
|
bit_nickname[2] = "%3"
|
|
bit_nickname[3] = "bit_and_buf_1"
|
|
bit_nickname[4] = "bit_and_buf_2"
|
|
|
|
|
|
|
|
|
|
bit_path = {}
|
|
for i in range(0,cell_size):
|
|
bit_path[i] = ".tp "+bit_nickname[i]
|
|
|
|
|
|
|
|
|
|
if(bfs()):
|
|
path = []
|
|
print("---PATH FOUND---")
|
|
this_stat = ans
|
|
while(this_stat != inp):
|
|
last_stat,last_op = visited_op[this_stat]
|
|
path.insert(0,last_op)
|
|
this_stat = last_stat
|
|
for i in path:
|
|
operand = []
|
|
tmp = i[1]
|
|
count = 0
|
|
while(tmp != 0):
|
|
tmp >>= 1
|
|
if((tmp&1) == 1):
|
|
operand.append(count)
|
|
count += 1
|
|
print(bit_path[i[0]])
|
|
if(i[1] == 0 or i[1] == 1):
|
|
print("set_0")
|
|
else:
|
|
print("biz")
|
|
for op in operand:
|
|
print("\t"+bit_path[op])
|
|
if(i[1] &1 == ops["SET1"]):
|
|
print("\tset_1")
|
|
else:
|
|
print("\tflb")
|
|
print("\t"+bit_path[i[0]])
|
|
print("\tflb")
|
|
print("rnz")
|
|
"""
|
|
print("---DEBUG---")
|
|
def bin_stat(stat):
|
|
sstat = bin(stat)[2:]
|
|
for _ in range(0,cell_size-len(sstat)):
|
|
sstat = '0'+sstat
|
|
sstat = "0b"+sstat
|
|
return(sstat)
|
|
|
|
|
|
for i in truthTable:
|
|
print("INP:",bin_stat(i[0]),"OUT:",bin_stat(i[1]))
|
|
for i in path:
|
|
operand = []
|
|
tmp = i[1]
|
|
count = 0
|
|
while(tmp != 0):
|
|
tmp >>= 1
|
|
if((tmp&1) == 1):
|
|
operand.append(count)
|
|
count += 1
|
|
if(i[1] == 0 or i[1] == 1):
|
|
print("ERASE ",i[0])
|
|
else:
|
|
if(i[1] &1 != 1):
|
|
print("ERASE ",i[0]," SET1 ",operand)
|
|
else:
|
|
print("ERASE ",i[0]," FLIP ",operand)
|
|
"""
|
|
else:
|
|
print("---!!!PATH NOT FOUND!!!---") |