summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/main.rs454
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!();
}