From facb87c7f46831281885dbd143306148f5b50fba Mon Sep 17 00:00:00 2001 From: Mora Unie Youer Date: Mon, 28 Apr 2025 12:12:36 +0300 Subject: feat: solution parameter calculation --- src/main.rs | 454 +++++++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 389 insertions(+), 65 deletions(-) (limited to 'src/main.rs') diff --git a/src/main.rs b/src/main.rs index 75c796a..4138a33 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,5 +1,5 @@ use std::{ - collections::{HashMap, HashSet}, + collections::{HashMap, HashSet, VecDeque}, fmt::Display, }; @@ -194,8 +194,7 @@ fn minimize(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec { solve_prime_implicants_table(minterms, &prime_implicants) } -#[derive(Clone, Debug, Hash)] -#[allow(dead_code)] +#[derive(Clone, Debug, Hash, PartialEq, Eq)] enum Logic { Constant(bool), @@ -223,6 +222,32 @@ impl Logic { 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 { @@ -349,21 +374,319 @@ fn cubes_to_nor(cubes: &[Cube], vars: &[&str]) -> Logic { } } -// NOTE: returns inverted result -// NOTE: returns just inverted DNF, which is enough to understand how to build -fn cubes_to_wired_or(cubes: &[Cube], vars: &[&str]) -> Logic { - let mut dnf = cubes_to_dnf(cubes, vars); - - // If we have standalone variables, we need to transform them into NAND gates - if let Logic::Or(logics) = &mut dnf { - for logic in logics { - if matches!(logic, Logic::Not(_) | Logic::Variable(_)) { - *logic = Logic::And(vec![logic.inverse(), logic.inverse()]); +#[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 input_current(&self) -> usize { + std::cmp::min(self.input_current_low, self.input_current_high) + } + + fn output_current(&self) -> usize { + std::cmp::min(self.output_current_low, self.output_current_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())); + } } } } - Logic::Not(Box::new(dnf)) + 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() +} + +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() { @@ -371,63 +694,64 @@ fn main() { let chip_series_file_path = args.next().unwrap(); let truth_table_file_path = args.next().unwrap(); - // TODO: make a use of this - let _chip_series_file = std::fs::read_to_string(chip_series_file_path).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 mut truth_table_lines = truth_table_file.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 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 { + 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); + + println!(" Параметры решения:"); + println!(" - Количество использованных микросхем:"); + if chips.is_empty() { + println!(" - <не требуется микросхем>"); + } + + let mut total_consumption = 0.; + let mut total_used_consumption = 0.; - 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"), + for (chip, (used, size)) in chips { + 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})" + ); } - } - } - for (output, (minterms, maxterms)) in truth_table_outputs - .into_iter() - .zip(truth_table_minterms.into_iter().zip(truth_table_maxterms)) - { - let cubes = minimize(truth_table_inputs.len(), &minterms, &maxterms); - let inv_cubes = minimize(truth_table_inputs.len(), &maxterms, &minterms); - - println!("{output} = {}", cubes_to_dnf(&cubes, &truth_table_inputs)); - println!("{output} = {}", cubes_to_nand(&cubes, &truth_table_inputs)); - println!( - "{output} = {}", - cubes_to_cnf(&inv_cubes, &truth_table_inputs) - ); - println!( - "{output} = {}", - cubes_to_nor(&inv_cubes, &truth_table_inputs) - ); - println!( - "{output} = {}", - cubes_to_wired_or(&inv_cubes, &truth_table_inputs) - ); + println!(" - Задержка (с инверсией входных переменных): {full_delay} нс"); + println!(" - Задержка (без инверсии входных переменных): {reduced_delay} нс"); + println!(" - Полное потребление схемы: {total_consumption} мкВт"); + println!(" - Использованное потребление схемы: {total_used_consumption} мкВт"); + println!(); + } println!(); } -- cgit v1.2.3-70-g09d2