feat: solution parameter calculation

1 files changed, 389 insertions, 65 deletions

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<Cube> {
     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<Vec<(&'input str, &'input str)>> {
+    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<Vec<usize>>,
+    maxterms: Vec<Vec<usize>>,
+}
+
+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<Logic>> {
+        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!();
     }