use std::{ collections::{HashMap, HashSet, VecDeque}, fmt::Display, }; use itertools::Itertools; // NOTE: PartialOrd and Ord have no sense, but it is needed to sort them somehow #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] struct Cube { t: usize, f: usize, } impl Cube { fn cost(&self) -> usize { self.t.count_ones() as usize + self.f.count_ones() as usize } fn covers(&self, minterm: usize) -> bool { let mask = self.t | self.f; minterm & mask == self.t && !minterm & mask == self.f } fn combine(&self, other: &Self) -> Option { let dt = self.t ^ other.t; let df = self.f ^ other.f; // NOTE: this should be compiled with all optimizations possible // as `.count_ones()` is bottleneck if dt == df && dt.count_ones() == 1 { Some(Self { t: self.t & other.t, f: self.f & other.f, }) } else { None } } } fn minimize_prime_implicants(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec { let minterms_set: HashSet<_> = minterms.iter().copied().collect(); let maxterms_set: HashSet<_> = maxterms.iter().copied().collect(); let mut anyterms_set = HashSet::new(); for i in 0..2usize.pow(n as u32) { if !minterms_set.contains(&i) && !maxterms_set.contains(&i) { anyterms_set.insert(i); } } let mask = (1 << n) - 1; let initial_cubes: Vec<_> = minterms_set .union(&anyterms_set) .sorted() .map(|&i| Cube { t: i, f: !i & mask }) .collect(); let mut covered = vec![vec![false; initial_cubes.len()]]; let mut cubes = vec![initial_cubes]; for iteration in 0..n { let current_covered = &mut covered[iteration]; let current_cubes = &cubes[iteration]; let mut new_cubes = HashSet::new(); for i in 0..current_cubes.len() { let a = ¤t_cubes[i]; for j in i + 1..current_cubes.len() { let b = ¤t_cubes[j]; if let Some(combined_cube) = a.combine(b) { current_covered[i] = true; current_covered[j] = true; new_cubes.insert(combined_cube); } } } covered.push(vec![false; new_cubes.len()]); cubes.push(new_cubes.into_iter().collect()); } let mut final_cubes = vec![]; for (iteration, iteration_cubes) in cubes.into_iter().enumerate() { for (i, cube) in iteration_cubes.into_iter().enumerate() { if !covered[iteration][i] { final_cubes.push(cube); } } } final_cubes.sort(); final_cubes } fn solve_prime_implicants_table(minterms: &[usize], prime_implicants: &[Cube]) -> Vec { let mut table: HashSet<(usize, usize)> = (0..prime_implicants.len()) .cartesian_product(0..minterms.len()) .filter(|&(i, j)| prime_implicants[i].covers(minterms[j])) .collect(); let mut selected_implicants = vec![false; prime_implicants.len()]; loop { // Select essential minterms let mut minterms_freq = vec![0; minterms.len()]; table.iter().for_each(|&(_, j)| minterms_freq[j] += 1); table .iter() .for_each(|&(i, j)| selected_implicants[i] |= minterms_freq[j] == 1); // Check if minterms are fully covered let mut covered_minterms = vec![false; minterms.len()]; table .iter() .filter(|&&(i, _)| selected_implicants[i]) .for_each(|&(_, j)| covered_minterms[j] = true); if table.is_empty() || covered_minterms.iter().all(|&v| v) { break; } // Removing essential implicants let new_table: HashSet<_> = table .iter() .filter(|&&(i, j)| !selected_implicants[i] && !covered_minterms[j]) .cloned() .collect(); table = new_table; if table.is_empty() { // All implicants are used break; } // Finding minterm coverage by implicants let mut implicants = HashSet::new(); let mut covered_by_implicants: HashMap> = HashMap::new(); table.iter().for_each(|&(i, j)| { implicants.insert(i); covered_by_implicants.entry(i).or_default().insert(j); }); // Removing implicants by cost when essentials are not found // NOTE: when checking combinations, implicants must be sorted, to give constant result // (If not, it will variate due to order in HashSet) let mut removed = false; let mut implicants_to_remove = vec![false; prime_implicants.len()]; for (a, b) in implicants.iter().sorted().tuple_combinations() { let a_set = &covered_by_implicants[a]; let b_set = &covered_by_implicants[b]; let eq = a_set == b_set; let a_cost = prime_implicants[*a].cost(); let b_cost = prime_implicants[*b].cost(); if eq && a_cost >= b_cost { implicants_to_remove[*a] = true; removed = true; } else if eq { implicants_to_remove[*b] = true; removed = true; } } if removed { let new_table: HashSet<_> = table .iter() .filter(|&&(i, _)| !implicants_to_remove[i]) .cloned() .collect(); table = new_table; } else { // We can't remove implicants by cost, have to choose by ourselves. // NOTE: this leads to non-minimal solution // NOTE: this SHOULD NOT happen, as we are filtering equal implicant costs too todo!() } } prime_implicants .iter() .zip(selected_implicants) .filter(|&(_, select)| select) .map(|(cube, _)| cube) .copied() .collect() } fn minimize(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec { let prime_implicants = minimize_prime_implicants(n, minterms, maxterms); // print_prime_implicants_table(n, minterms, &prime_implicants); solve_prime_implicants_table(minterms, &prime_implicants) } #[derive(Clone, Debug, Hash, PartialEq, Eq)] enum Logic { Constant(bool), Variable(String), Not(Box), And(Vec), Or(Vec), Nand(Vec), Nor(Vec), } impl Logic { fn inverse(&self) -> Self { match self { Logic::Constant(v) => Logic::Constant(!*v), Logic::Variable(name) => Logic::Not(Box::new(Logic::Variable(name.clone()))), Logic::Not(logic) => *logic.clone(), Logic::And(logics) => Logic::Nand(logics.clone()), Logic::Or(logics) => Logic::Nor(logics.clone()), Logic::Nand(logics) => Logic::And(logics.clone()), Logic::Nor(logics) => Logic::Or(logics.clone()), } } fn to_full_nand(&self) -> Self { match self { Logic::Not(logic) => Logic::Nand(vec![*logic.clone(), *logic.clone()]), Logic::And(logics) => Logic::And(logics.iter().map(|l| l.to_full_nand()).collect()), Logic::Or(logics) => Logic::Or(logics.iter().map(|l| l.to_full_nand()).collect()), Logic::Nand(logics) => Logic::Nand(logics.iter().map(|l| l.to_full_nand()).collect()), Logic::Nor(logics) => Logic::Nor(logics.iter().map(|l| l.to_full_nand()).collect()), logic => logic.clone(), } } fn to_full_nor(&self) -> Self { match self { Logic::Not(logic) => Logic::Nor(vec![*logic.clone(), *logic.clone()]), Logic::And(logics) => Logic::And(logics.iter().map(|l| l.to_full_nor()).collect()), Logic::Or(logics) => Logic::Or(logics.iter().map(|l| l.to_full_nor()).collect()), Logic::Nand(logics) => Logic::Nand(logics.iter().map(|l| l.to_full_nor()).collect()), Logic::Nor(logics) => Logic::Nor(logics.iter().map(|l| l.to_full_nor()).collect()), logic => logic.clone(), } } } impl Display for Logic { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { Logic::Constant(v) => f.write_str(if *v { "1" } else { "0" }), Logic::Variable(name) => f.write_str(name), Logic::Not(logic) => f.write_fmt(format_args!("!{}", logic)), Logic::And(logics) => { let s = logics.iter().map(|logic| logic.to_string()).join(" & "); f.write_fmt(format_args!("({s})")) } Logic::Or(logics) => { let s = logics.iter().map(|logic| logic.to_string()).join(" | "); f.write_fmt(format_args!("({s})")) } Logic::Nand(logics) => { let s = logics.iter().map(|logic| logic.to_string()).join(" !& "); f.write_fmt(format_args!("({s})")) } Logic::Nor(logics) => { let s = logics.iter().map(|logic| logic.to_string()).join(" !| "); f.write_fmt(format_args!("({s})")) } } } } fn cubes_to_dnf(cubes: &[Cube], vars: &[&str]) -> Logic { if cubes.is_empty() { return Logic::Constant(false); } else if cubes.len() == 1 && cubes[0].t == 0 && cubes[0].f == 0 { return Logic::Constant(true); } let mut dnf = vec![]; for &Cube { mut t, mut f } in cubes { let mut used_vars = Vec::new(); for i in (0..vars.len()).rev() { match (t & 1, f & 1) { (1, 0) => used_vars.push(Logic::Variable(vars[i].to_owned())), (0, 1) => used_vars.push(Logic::Not(Box::new(Logic::Variable(vars[i].to_owned())))), (0, 0) => (), _ => unreachable!(), } t >>= 1; f >>= 1; } if used_vars.len() == 1 { dnf.push(used_vars[0].clone()); } else { dnf.push(Logic::And(used_vars)); } } if dnf.len() == 1 { dnf[0].clone() } else { Logic::Or(dnf) } } // NOTE: returns inverted result fn cubes_to_cnf(cubes: &[Cube], vars: &[&str]) -> Logic { if cubes.is_empty() { return Logic::Constant(true); } else if cubes.len() == 1 && cubes[0].t == 0 && cubes[0].f == 0 { return Logic::Constant(false); } let mut dnf = vec![]; for &Cube { mut t, mut f } in cubes { let mut used_vars = Vec::new(); for i in (0..vars.len()).rev() { match (t & 1, f & 1) { (1, 0) => used_vars.push(Logic::Not(Box::new(Logic::Variable(vars[i].to_owned())))), (0, 1) => used_vars.push(Logic::Variable(vars[i].to_owned())), (0, 0) => (), _ => unreachable!(), } t >>= 1; f >>= 1; } if used_vars.len() == 1 { dnf.push(used_vars[0].clone()); } else { dnf.push(Logic::Or(used_vars)); } } if dnf.len() == 1 { dnf[0].clone() } else { Logic::And(dnf) } } fn cubes_to_nand(cubes: &[Cube], vars: &[&str]) -> Logic { let dnf = cubes_to_dnf(cubes, vars); match dnf { Logic::Or(logics) => Logic::Nand(logics.into_iter().map(|logic| logic.inverse()).collect()), Logic::And(logics) => Logic::Not(Box::new(Logic::Nand(logics))), logic => logic, } } // NOTE: returns inverted result fn cubes_to_nor(cubes: &[Cube], vars: &[&str]) -> Logic { let cnf = cubes_to_cnf(cubes, vars); match cnf { Logic::Or(logics) => Logic::Not(Box::new(Logic::Nor(logics))), Logic::And(logics) => Logic::Nor(logics.into_iter().map(|logic| logic.inverse()).collect()), logic => logic, } } #[derive(Clone, Copy, Debug)] #[allow(dead_code)] struct ChipInfo<'input> { gate_type: &'input str, input_count: usize, gate_count: usize, book_page: usize, consumption_low: usize, consumption_high: usize, input_current_low: usize, input_current_high: usize, output_current_low: usize, output_current_high: usize, delay_off: usize, delay_on: usize, } impl ChipInfo<'_> { fn consumption(&self) -> usize { std::cmp::max(self.consumption_low, self.consumption_high) } fn delay(&self) -> usize { std::cmp::max(self.delay_off, self.delay_on) } } #[derive(Clone, Debug)] struct ChipSeries<'input> { logic_to_chip: HashMap<(&'input str, usize), &'input str>, chip_specification: HashMap<&'input str, ChipInfo<'input>>, } impl<'input> From<&'input str> for ChipSeries<'input> { fn from(input: &'input str) -> Self { let lines = input .lines() .filter(|line| !line.is_empty() && !line.starts_with("//")); let mut logic_to_chip = HashMap::new(); let mut chip_specification = HashMap::new(); for line in lines { let mut parts = line.split_whitespace(); let gate = parts.next().unwrap(); let (gate_count, gate_type) = gate.split_once('x').unwrap(); let (gate_type, input_count) = ( &gate_type[..gate_type.len() - 1], gate_type[gate_type.len() - 1..].parse().unwrap(), ); let book_page = parts.next().unwrap().parse().unwrap(); let chip_name = parts.next().unwrap(); let chip_info = ChipInfo { gate_type, input_count, gate_count: gate_count.parse().unwrap(), book_page, consumption_low: parts.next().unwrap().parse().unwrap(), consumption_high: parts.next().unwrap().parse().unwrap(), input_current_low: parts.next().unwrap().parse().unwrap(), input_current_high: parts.next().unwrap().parse().unwrap(), output_current_low: parts.next().unwrap().parse().unwrap(), output_current_high: parts.next().unwrap().parse().unwrap(), delay_off: parts.next().unwrap().parse().unwrap(), delay_on: parts.next().unwrap().parse().unwrap(), }; logic_to_chip.insert((gate_type, input_count), chip_name); chip_specification.insert(chip_name, chip_info); } Self { logic_to_chip, chip_specification, } } } fn logic_to_chips<'input>( logic: &Logic, series: &ChipSeries<'input>, ) -> HashMap<&'input str, (usize, usize)> { let mut chips = HashMap::new(); let mut visited = HashSet::new(); let mut queue = VecDeque::from([logic]); while let Some(logic) = queue.pop_front() { if !visited.insert(logic) { continue; } let gate = match logic { Logic::Constant(_) => continue, Logic::Variable(_) => continue, Logic::Not(logic) => { queue.push_back(logic); ("NOT", 1) } Logic::And(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("AND", logics.len()) } Logic::Or(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("OR", logics.len()) } Logic::Nand(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("NAND", logics.len()) } Logic::Nor(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("NOR", logics.len()) } }; let chip = series.logic_to_chip[&gate]; chips .entry(chip) .or_insert((0, series.chip_specification[chip].gate_count)) .0 += 1; } chips } fn logic_to_sequences<'input>( logic: &Logic, series: &ChipSeries<'input>, ) -> Vec> { let mut sequences = vec![]; let mut queue = VecDeque::from([(logic, vec![])]); while let Some((logic, mut seq)) = queue.pop_front() { match logic { Logic::Constant(_) => sequences.push(seq), Logic::Variable(_) => sequences.push(seq), Logic::Not(logic) => { let chip = series.logic_to_chip[&("NOT", 1)]; seq.push(("NOT", chip)); queue.push_back((logic, seq)); } Logic::And(logics) => { let chip = series.logic_to_chip[&("AND", logics.len())]; seq.push(("AND", chip)); for logic in logics { queue.push_back((logic, seq.clone())); } } Logic::Or(logics) => { let chip = series.logic_to_chip[&("OR", logics.len())]; seq.push(("OR", chip)); for logic in logics { queue.push_back((logic, seq.clone())); } } Logic::Nand(logics) => { let chip = series.logic_to_chip[&("NAND", logics.len())]; seq.push(("NAND", chip)); for logic in logics { queue.push_back((logic, seq.clone())); } } Logic::Nor(logics) => { let chip = series.logic_to_chip[&("NOR", logics.len())]; seq.push(("NOR", chip)); for logic in logics { queue.push_back((logic, seq.clone())); } } } } sequences } fn sequence_to_delay<'input>( sequence: &[(&'input str, &'input str)], series: &ChipSeries<'input>, ) -> usize { sequence .iter() .map(|(_, chip)| series.chip_specification[chip].delay()) .sum() } fn logic_to_full_delay(logic: &Logic, series: &ChipSeries) -> usize { let sequences = logic_to_sequences(logic, series); sequences .iter() .map(|seq| sequence_to_delay(seq, series)) .max() .unwrap() } fn logic_to_reduced_delay(logic: &Logic, series: &ChipSeries) -> usize { let mut sequences = logic_to_sequences(logic, series); sequences.iter_mut().for_each(|seq| { // NOTE: sequence is reversed, so we are using last element to check for variable inversion seq.pop_if(|(gate, _)| *gate == "NOT"); }); sequences .iter() .map(|seq| sequence_to_delay(seq, series)) .max() .unwrap() } fn logic_to_input_current<'input>( logic: &'input Logic, series: &ChipSeries<'input>, ) -> HashMap<&'input str, (usize, usize)> { let mut consumptions = HashMap::new(); let mut visited = HashSet::new(); let mut queue = VecDeque::from([logic]); while let Some(logic) = queue.pop_front() { if !visited.insert(logic) { continue; } let gate = match logic { Logic::Constant(_) => continue, Logic::Variable(_) => continue, Logic::Not(logic) => { queue.push_back(logic); ("NOT", 1) } Logic::And(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("AND", logics.len()) } Logic::Or(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("OR", logics.len()) } Logic::Nand(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("NAND", logics.len()) } Logic::Nor(logics) => { logics.iter().for_each(|logic| queue.push_back(logic)); ("NOR", logics.len()) } }; let chip = series.logic_to_chip[&gate]; let ChipInfo { input_current_low, input_current_high, .. } = series.chip_specification[chip]; // Checking if children of this logic has variable // TODO: rewrite this shit better, by generating children of any logic match logic { Logic::Not(l) => { if let Logic::Variable(name) = &**l { let (low, high) = consumptions.entry(name.as_str()).or_default(); *low += input_current_low; *high += input_current_high; } } Logic::And(logics) => { for l in logics { if let Logic::Variable(name) = l { let (low, high) = consumptions.entry(name.as_str()).or_default(); *low += input_current_low; *high += input_current_high; } } } Logic::Or(logics) => { for l in logics { if let Logic::Variable(name) = l { let (low, high) = consumptions.entry(name.as_str()).or_default(); *low += input_current_low; *high += input_current_high; } } } Logic::Nand(logics) => { for l in logics { if let Logic::Variable(name) = l { let (low, high) = consumptions.entry(name.as_str()).or_default(); *low += input_current_low; *high += input_current_high; } } } Logic::Nor(logics) => { for l in logics { if let Logic::Variable(name) = l { let (low, high) = consumptions.entry(name.as_str()).or_default(); *low += input_current_low; *high += input_current_high; } } } _ => (), } } consumptions } struct TruthTable<'input> { inputs: Vec<&'input str>, outputs: Vec<&'input str>, minterms: Vec>, maxterms: Vec>, } impl<'input> From<&'input str> for TruthTable<'input> { fn from(input: &'input str) -> Self { let mut truth_table_lines = input.lines(); let truth_table_inputs = truth_table_lines .next() .map(|line| line.split_whitespace().collect_vec()) .unwrap(); let truth_table_outputs = truth_table_lines .next() .map(|line| line.split_whitespace().collect_vec()) .unwrap(); let mut truth_table_minterms = vec![vec![]; truth_table_outputs.len()]; let mut truth_table_maxterms = vec![vec![]; truth_table_outputs.len()]; for line in truth_table_lines { let (input, output) = line.split_once(char::is_whitespace).unwrap(); if input.len() != truth_table_inputs.len() || output.len() != truth_table_outputs.len() { panic!("Truth table is incorrect: invalid input/output size"); } let input_term = usize::from_str_radix(input, 2).unwrap(); for (i, ch) in output.chars().enumerate() { match ch { '1' => truth_table_minterms[i].push(input_term), '0' => truth_table_maxterms[i].push(input_term), '-' => (), _ => panic!("Truth table is incorrect: invalid char in output section"), } } } Self { inputs: truth_table_inputs, outputs: truth_table_outputs, minterms: truth_table_minterms, maxterms: truth_table_maxterms, } } } impl<'input> TruthTable<'input> { // Returns 4 solutions to all functions fn solve(&self) -> HashMap<&'input str, Vec> { let mut solutions = HashMap::new(); for (i, &output) in self.outputs.iter().enumerate() { let cubes = minimize(self.inputs.len(), &self.minterms[i], &self.maxterms[i]); let inv_cubes = minimize(self.inputs.len(), &self.maxterms[i], &self.minterms[i]); let output_solutions = [ cubes_to_dnf(&cubes, &self.inputs), cubes_to_nand(&cubes, &self.inputs), cubes_to_nand(&cubes, &self.inputs).to_full_nand(), cubes_to_cnf(&inv_cubes, &self.inputs), cubes_to_nor(&inv_cubes, &self.inputs), cubes_to_nor(&inv_cubes, &self.inputs).to_full_nor(), ]; solutions.insert(output, output_solutions.to_vec()); } solutions } } fn main() { let mut args = std::env::args().skip(1); let chip_series_file_path = args.next().unwrap(); let truth_table_file_path = args.next().unwrap(); let chip_series_file = std::fs::read_to_string(chip_series_file_path).unwrap(); let truth_table_file = std::fs::read_to_string(truth_table_file_path).unwrap(); // Parsing chip series let chip_series = ChipSeries::from(chip_series_file.as_str()); // Parsing truth table let truth_table = TruthTable::from(truth_table_file.as_str()); let all_solutions = truth_table.solve(); const SOLUTIONS: [&str; 6] = ["DNF", "NAND", "FULL_NAND", "CNF", "NOR", "FULL_NOR"]; for (output, solutions) in all_solutions.iter().sorted_by_key(|(output, _)| *output) { println!("Решения для {output}:"); for (solution_type, solution) in SOLUTIONS.into_iter().zip(solutions) { println!("- {solution_type}:"); println!(" {solution}"); println!(); let chips = logic_to_chips(solution, &chip_series); let full_delay = logic_to_full_delay(solution, &chip_series); let reduced_delay = logic_to_reduced_delay(solution, &chip_series); let input_currents = logic_to_input_current(solution, &chip_series); println!(" Параметры решения:"); println!(" - Количество использованных микросхем:"); if chips.is_empty() { println!(" - <не требуется микросхем>"); } let mut total_consumption = 0.; let mut total_used_consumption = 0.; for (chip, (used, size)) in chips.into_iter().sorted() { let chip_info = chip_series.chip_specification[chip]; let chip_usage = used as f32 / size as f32; let chip_consumption = used.div_ceil(size) * chip_info.consumption(); let chip_used_consumption = chip_usage * chip_info.consumption() as f32; total_consumption += chip_consumption as f32; total_used_consumption += chip_used_consumption as f32; println!( " - {chip}: {} шт (использовано {used} элементов -> {used}/{size} = {})", used.div_ceil(size), used as f32 / size as f32 ); println!( " Максимальное потребление: {chip_consumption} мкВт (реальное использованное: {chip_used_consumption})" ); } println!(" - Задержка (с инверсией входных переменных): {full_delay} нс"); println!(" - Задержка (без инверсии входных переменных): {reduced_delay} нс"); println!(" - Полное потребление схемы: {total_consumption} мкВт"); println!(" - Использованное потребление схемы: {total_used_consumption} мкВт"); println!(" - Потребляемый ток со входных сигналов:"); for (input, (low_current, high_current)) in input_currents.into_iter().sorted() { println!(" - {input} - {low_current}/{high_current} мкА"); } println!(); } println!(); } }