libreda-pnr 0.0.4

// Copyright (c) 2020-2021 Thomas Kramer.
// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Estimate wire lengths.
//!
//! # Example
//!
//! Get the wire length estimation of a cell without any net.
//! ```
//! use libreda_pnr::db;
//! use libreda_pnr::db::traits::*;
//! use libreda_pnr::metrics::wirelength_estimation;
//!
//! let mut chip = db::Chip::new();
//! let cell_top = chip.create_cell("TOP".to_string());
//!
//! let wire_length: i32 = wirelength_estimation::hpwl(&chip.cell_ref(&cell_top));
//! assert_eq!(wire_length, 0)
//! ```

use crate::db;
use crate::db::L2NBase;
use crate::db::reference_access::*;
use crate::db::traits::TryBoundingBox;
use num_traits::{Zero, One, Num, NumCast};

/// Compute the half-perimeter wire length estimation for the cell `top`.
/// Returns the sum of half-perimeters of each nets bounding box.
/// Respects the pin locations at sub cells (instead of just taking the sub cell location).
pub fn hpwl<C: L2NBase, L>(top: &CellRef<C>) -> L
    where C::Coord: NumCast,
          L: Num + NumCast + Zero {
    top.each_net()
        .map(|net| hpwl_for_net(&net))
        .map(|l| L::from(l).expect("Failed to cast HPLW of net to other datatype L."))
        .fold(Zero::zero(), |acc, x| acc + x)
}

/// Compute the half-perimeter wire length of a single net.
///
/// Returns the half perimeter of the bounding box around all pins connected to `net`.
pub fn hpwl_for_net<C: L2NBase>(net: &NetRef<C>) -> C::Coord {
    let bbox = net_bounding_box(&net);

    let hplw = if let Some(bbox) = bbox {
        bbox.width() + bbox.height()
    } else {
        C::Coord::zero()
    };
    debug_assert!(hplw >= C::Coord::zero(), "Half-perimeter wire length should not be negative.");
    hplw
}

/// Get the bounding box around all the pins connected to `net`.
/// `None` is returned when `net` is not connected to any pins or pin instances.
pub fn net_bounding_box<C: L2NBase>(net: &NetRef<C>) -> Option<db::Rect<C::Coord>> {
    let mut bbox: Option<db::Rect<_>> = None;
    let mut update_bbox = |p: db::Point<C::Coord>| {
        if let Some(bbox) = &mut bbox {
            *bbox = bbox.add_point(p);
        } else {
            bbox = Some(db::Rect::new(p, p));
        }
    };

    // Process all connected external pins.
    for pin in net.each_pin() {
        update_bbox(pin_location(&pin));
    }

    // Process all connected pin instances.
    for pin_inst in net.each_pin_instance() {
        update_bbox(pin_instance_location(&pin_inst));
    }

    bbox
}

/// Get an point-like approximation of a absolute pin instance location.
fn pin_instance_location<C: L2NBase>(pin_inst: &PinInstRef<C>) -> db::Point<C::Coord> {
    let pin = pin_inst.pin();
    let pin_loc = pin_location(&pin);
    let chip = pin.base();
    chip.get_transform(&pin_inst.cell_instance().id())
        .transform_point(pin_loc)
}

/// Get an point-like approximation of a pin location (relative to the cell).
/// If the pin has no shapes defined, return `(0, 0)`.
fn pin_location<C: L2NBase>(pin: &PinRef<C>) -> db::Point<C::Coord> {
    let chip = pin.base();

    // Compute the average location of the pin shapes.
    let mut sum: db::Point<C::Coord> = db::Point::zero();
    let mut count = C::Coord::zero();
    chip.shapes_of_pin(&pin.id())
        .filter_map(|shape_id| {
            chip.with_shape(&shape_id, |_layer, shape| {
                shape.try_bounding_box().map(|bbox| bbox.center())
            })
        })
        .for_each(|p| {
            sum = sum + p;
            count = count + C::Coord::one();
        });

    let avg = if count.is_zero() {
        sum
    } else {
        sum / count
    };
    avg
}

#[test]
fn test_hplw() {
    use crate::db;
    use crate::db::traits::*;

    let mut chip = db::Chip::new();
    let cell_top = chip.create_cell("TOP".to_string());
    let cell_sub = chip.create_cell("SUB".to_string());
    let pin_a = chip.create_pin(&cell_sub, "A".to_string(), db::Direction::Input);
    let net1 = chip.create_net(&cell_top, None);
    let inst1 = chip.create_cell_instance(&cell_top, &cell_sub, None);
    let inst2 = chip.create_cell_instance(&cell_top, &cell_sub, None);
    chip.set_transform(&inst1, db::SimpleTransform::translate(db::Vector::new(10, 10)));
    chip.set_transform(&inst2, db::SimpleTransform::translate(db::Vector::new(20, 20)));

    // Connect net to pins.
    chip.connect_pin_instance(&chip.pin_instance(&inst1, &pin_a), Some(net1.clone()));
    chip.connect_pin_instance(&chip.pin_instance(&inst2, &pin_a), Some(net1.clone()));


    let wire_length: i32 = hpwl(&chip.cell_ref(&cell_top));
    assert_eq!(wire_length, 10 + 10)
}