标准CMOS电路原理图的自动布局布线绘制工具 2025-04-17 technotes

背景

前段时间，全重筹划开展智能电路设计工作，准备材料时经常需要一些电路原理图作为示例。 然而却没有现成的工具方便绘制这些原理图。 现有画原理图的工具需要一个一个元件手工码放、一条一条线手工连接，画一个小规模示例都需要非常繁重的操作。 4位加法器就包含了上百个晶体管，更大规模的例子手工码放，成本都快要接近从头设计一个4004了。 而真实的综合、布局布线工具不仅调用繁琐，最终画出的图也不美观。 因此，我一直以来都是自己写脚本来绘制这些图。

一开始是在Python中，通过PIL来画。 写了几个基本的函数，能在指定位置绘制晶体管和逻辑门， 但布局布线仍然需要手工设计，工作效率不高。 于是我决定给脚本加上简单的布局布线逻辑，实现从输入电路网表到输出原理图的全流程自动化。 以下是最终效果：

涉及到布局布线这样比较繁重的运算流程，我立刻决定抛弃Python，改用C++来实现，不然画一张图要等一天。 布线算法挪用了之前曾为绘制另一幅图写过的迷宫布线。 然后我直接将布线的代码贴给DeepSeek，让它给我补全布局的代码。 DeepSeek-V3-0324展现出非常强的代码能力，写出的代码立刻就能运行，功能完整。 在大语言模型的帮助下，加上一些搜索和一点巧思，抛弃PIL也并未带来多少痛苦。 DeepSeek提供了输出PNG的代码、抽取BDF点阵字体的代码，帮我调试了斜线栅格化算法中的Bug。

因此，我很快实现了这份约800行的自动电路布局布线程序，输入BLIF、输出PNG。 它完全自包含，依赖仅限于C++标准STL。 即使从小就在写程序，这次编码经历对我来说是全新的，展示了大语言模型时代对编程体验的重塑。 如果不是有大模型，去阅读PNG、BDF、DEFLATE这些标准的RFC然后去写底层函数，是非常痛苦的，我是断然不会去尝试的。

抛弃Python回归C++从未如此简单，想必抛弃CUDA亦如是。 在这个时代，生态壁垒正在被全方位削弱，这是令人兴奋的趋势！

代码

用到了C++26。当前只有GCC 15.0能编译，但15.0尚未发布，我为此从源码编译了最新的GCC。

这是我第一次大量使用ranges库，体验很好，很多时候能节省大量不必要的啰嗦。 当前的ranges还缺一些功能，例如反向的drop（从区间尾部去除一定数量的元素）； 想从循环中得知是否是循环的第一次/最后一次执行还不方便，不如过去的旧写法。

C++标准还缺乏一些关键容器，比如不知为何至今没有trie？ 一些老容器的性能一直被人诟病，也是时候翻新一遍了。 最新标准已经提供了flat_map，只是在我的场景里测试下来未见有性能优势；未见unordered_flat_map。 希望这些新功能要避免重走regex的老路才好。

展开代码

cirschem.cppview raw

/* ============================================================================
     place and route a standard CMOS circuit schematic.
         input:  Berkeley Logic Interchange Format (BLIF)
         output: black-white schematic image (PNG)

     compiling options: g++ cirschem.cpp -std=c++26 -O3
     requires c++26 (g++15 or above)

     Copyright (c) 2025 zhaoyongwei<zhaoyongwei@ict.ac.cn>
     IPRC, ICT CAS. Visit https://yongwei.site/pnr-circuit-schematic

     Permission is hereby granted, free of charge, to any person obtaining a copy
     of this software and associated documentation files (the "Software"), to deal
     in the Software without restriction, including without limitation the rights
     to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
     copies of the Software, and to permit persons to whom the Software is
     furnished to do so, subject to the following conditions:
     
     The above copyright notice and this permission notice shall be included in all
     copies or substantial portions of the Software.
     
     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
     AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
     OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
     SOFTWARE.
 
 * ============================================================================ */

#include <iostream>
#include <format>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <array>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <ranges>
#include <random>
#include <cmath>
#include <cstdint>
#include <chrono>
using namespace std::chrono_literals;
using namespace std::literals;

// simulated annealing placement parameters
constexpr double initial_temperature = std::exp(5);
constexpr double cooling_rate        = 0.99999;
constexpr double stop_temperature    = 0.1;
constexpr auto step_timeout          = 5ms;
// placement optimizing target
constexpr double initial_area_margins = std::exp(1);
constexpr int area_cost = 5;
constexpr int cross_track_penalty = 50;
// output file name
constexpr auto schematic_filename = "schematic.png";

enum {
  NOT = 0,
  NAND = 1,
};

std::tuple<std::set<int>,
           std::set<int>,
           std::unordered_map<int, std::pair<int, std::vector<int>>>,
           std::vector<std::string>>
parse(int argc, char* argv[]) {

    std::set<int> inputs;
    std::set<int> outputs;
    std::unordered_map<int, std::pair<int, std::vector<int>>> gates;
    std::vector<std::string> names {"NOT"s, "NAND"s};
    std::map<std::string, int> name_ids {{"NOT"s, 0}, {"NAND"s, 1}}; // compromised alt for trie.
    auto parse_name = [&](std::string str) {
        if (!name_ids.contains(str)) {
            name_ids.emplace(str, names.size());
            names.push_back(str);
        }
        return name_ids.at(str);
    };

    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " <blif_file>\n";
        return {inputs, outputs, gates, names};
    }

    std::ifstream blif(argv[1]);
    if (!blif.is_open()) {
        std::cerr << "Error opening file: " << argv[1] << '\n';
        return {inputs, outputs, gates, names};
    }

    std::string line;
    while (std::getline(blif, line)) {
        if (line.starts_with(".inputs")) {
            size_t start = 7; // length of ".inputs"
            while (start < line.size()) {
                size_t end = line.find(' ', start);
                if (end == std::string::npos) end = line.size();
                std::string token = line.substr(start, end - start);
                if (!token.empty()) {
                    inputs.insert(parse_name(token));
                }
                start = end + 1;
            }
        } else if (line.starts_with(".outputs")) {
            size_t start = 8; // length of ".outputs"
            while (start < line.size()) {
                size_t end = line.find(' ', start);
                if (end == std::string::npos) end = line.size();
                std::string token = line.substr(start, end - start);
                if (!token.empty()) {
                    outputs.insert(parse_name(token));
                }
                start = end + 1;
            }
        } else if (line.starts_with(".subckt")) {
            std::vector<int> ports;
            size_t start = 8; // length of ".subckt"
            while (start < line.size()) {
                size_t end = line.find(' ', start);
                if (end == std::string::npos) end = line.size();
                std::string token = line.substr(start, end - start);
                if (!token.empty()) {
                    size_t start = token.find('=', 0);
                    if (start != std::string::npos) {
                        token = token.substr(start+1, token.size());
                    }
                    ports.push_back(parse_name(token));
                }
                start = end + 1;
            }
            int gate = ports.front();
            int name = ports.back();
            ports.erase(ports.begin());
            ports.pop_back();
            gates[name] = { gate, ports };
        }
    }

    return {inputs, outputs, gates, names};
}

template<typename T, T... Ints>
constexpr auto make_crc_table(std::integer_sequence<T, Ints...> is) {
    return std::array<T, sizeof...(Ints)>{ [](T n){
               for (int k : std::views::iota(0,8)) n = (n>>1)^(n&1?0xedb88320:0); return n;
           }(Ints)...};
}
constexpr auto crc_table{ make_crc_table(std::make_integer_sequence<uint32_t, 256>{}) };

template<typename T>
constexpr uint32_t crc(const T& buf) {
    return ~std::ranges::fold_left(buf, 0xffffffff, [](uint32_t c, uint8_t d){
                return crc_table[(c ^ d) & 0xff] ^ (c>>8);
            });
}

template<typename T>
constexpr uint32_t adler32(const T& buf) {
    return std::ranges::fold_left(buf, 1, [](uint32_t ab, uint8_t d){
               auto a = ((ab & 0xffff) + d) % 65521; return a | ((((ab >> 16) + a) % 65521) << 16);
           });
}

template<typename Iter, typename T>
void insert_be(Iter it, T value) {
    auto value_be = std::endian::native == std::endian::little ? std::byteswap(value) : value;
    auto arr = std::bit_cast<std::array<uint8_t,sizeof(T)>>(value_be);
    std::ranges::copy(arr, it);
}
template<typename Iter, typename T>
void insert_le(Iter it, T value) {
    auto value_le = std::endian::native == std::endian::big ? std::byteswap(value) : value;
    auto arr = std::bit_cast<std::array<uint8_t,sizeof(T)>>(value_le);
    std::ranges::copy(arr, it);
}

std::vector<uint8_t> deflate(const std::vector<uint8_t>& data) {
    std::vector<uint8_t> compressed_data;
    auto it = std::back_inserter(compressed_data);
    for (auto chunk : data | std::views::chunk(0xfffb)) {
        *it = 0;
        insert_le(it, static_cast<uint16_t>( chunk.size()));
        insert_le(it, static_cast<uint16_t>(~chunk.size()));
        std::ranges::copy(chunk | std::views::transform(std::bit_not<uint8_t>{}), it);
    }
    compressed_data[(compressed_data.size()-1) & ~0xffffULL] = 0x1;
    return compressed_data;
}

constexpr std::array<std::tuple<int,std::array<uint16_t,8>>,96> font {{
{ 0, {0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000}}, //
{ 0, {0x0000,0x0000,0x0380,0x6FC0,0x6FC0,0x0380,0x0000,0x0000}}, // !
{ 6, {0x0000,0x3800,0x7800,0x0000,0x0000,0x7800,0x3800,0x0000}}, // "
{ 0, {0x1100,0x7FC0,0x7FC0,0x1100,0x7FC0,0x7FC0,0x1100,0x0000}}, // #
{-2, {0x0CE0,0x19F0,0x1110,0x711C,0x711C,0x1F30,0x0E60,0x0000}}, // $
{ 0, {0x4300,0x6300,0x3000,0x1800,0x0C00,0x6600,0x6300,0x0000}}, // %
{ 0, {0x3800,0x7D80,0x47C0,0x4E40,0x3BC0,0x7D80,0x4400,0x0000}}, // &
{ 6, {0x0000,0x4000,0x7800,0x3800,0x0000,0x0000,0x0000,0x0000}}, // '
{ 0, {0x0000,0x0000,0x1F00,0x3F80,0x60C0,0x4040,0x0000,0x0000}}, // (
{ 0, {0x0000,0x0000,0x4040,0x60C0,0x3F80,0x1F00,0x0000,0x0000}}, // )
{ 2, {0x1000,0x5400,0x7C00,0x3800,0x3800,0x7C00,0x5400,0x1000}}, // *
{ 2, {0x0000,0x1000,0x1000,0x7C00,0x7C00,0x1000,0x1000,0x0000}}, // +
{-1, {0x0000,0x0000,0x4000,0x7800,0x3800,0x0000,0x0000,0x0000}}, // ,
{ 4, {0x4000,0x4000,0x4000,0x4000,0x4000,0x4000,0x4000,0x0000}}, // -
{ 0, {0x0000,0x0000,0x0000,0x6000,0x6000,0x0000,0x0000,0x0000}}, // .
{ 1, {0x6000,0x3000,0x1800,0x0C00,0x0600,0x0300,0x0180,0x0000}}, // /
{ 0, {0x3F80,0x7FC0,0x4C40,0x4640,0x4340,0x7FC0,0x3F80,0x0000}}, // 0
{ 0, {0x0000,0x4100,0x4180,0x7FC0,0x7FC0,0x4000,0x4000,0x0000}}, // 1
{ 0, {0x6080,0x70C0,0x5840,0x4C40,0x4640,0x63C0,0x6180,0x0000}}, // 2
{ 0, {0x2080,0x60C0,0x4440,0x4440,0x4440,0x7FC0,0x3B80,0x0000}}, // 3
{ 0, {0x0C00,0x0E00,0x0B00,0x4980,0x7FC0,0x7FC0,0x4800,0x0000}}, // 4
{ 0, {0x27C0,0x67C0,0x4440,0x4440,0x4440,0x7C40,0x3840,0x0000}}, // 5
{ 0, {0x3F00,0x7F80,0x44C0,0x4440,0x4440,0x7C00,0x3800,0x0000}}, // 6
{ 0, {0x00C0,0x00C0,0x7840,0x7C40,0x0640,0x03C0,0x01C0,0x0000}}, // 7
{ 0, {0x3B80,0x7FC0,0x4440,0x4440,0x4440,0x7FC0,0x3B80,0x0000}}, // 8
{ 0, {0x0380,0x47C0,0x4440,0x4440,0x6440,0x3FC0,0x1F80,0x0000}}, // 9
{ 1, {0x0000,0x0000,0x0000,0x6300,0x6300,0x0000,0x0000,0x0000}}, // :
{ 0, {0x0000,0x0000,0x4000,0x7180,0x3180,0x0000,0x0000,0x0000}}, // ;
{ 0, {0x0000,0x0400,0x0E00,0x1B00,0x3180,0x60C0,0x4040,0x0000}}, // <
{ 2, {0x0000,0x4800,0x4800,0x4800,0x4800,0x4800,0x4800,0x0000}}, // =
{ 0, {0x0000,0x4040,0x60C0,0x3180,0x1B00,0x0E00,0x0400,0x0000}}, // >
{ 0, {0x0180,0x01C0,0x0040,0x6C40,0x6E40,0x03C0,0x0180,0x0000}}, // ?
{ 0, {0x3F80,0x7FC0,0x4040,0x5E40,0x5E40,0x5FC0,0x0F80,0x0000}}, // @
{ 0, {0x7E00,0x7F00,0x0980,0x08C0,0x0980,0x7F00,0x7E00,0x0000}}, // A
{ 0, {0x4040,0x7FC0,0x7FC0,0x4440,0x4440,0x7FC0,0x3B80,0x0000}}, // B
{ 0, {0x1F00,0x3F80,0x60C0,0x4040,0x4040,0x60C0,0x3180,0x0000}}, // C
{ 0, {0x4040,0x7FC0,0x7FC0,0x4040,0x60C0,0x3F80,0x1F00,0x0000}}, // D
{ 0, {0x4040,0x7FC0,0x7FC0,0x4440,0x4E40,0x60C0,0x71C0,0x0000}}, // E
{ 0, {0x4040,0x7FC0,0x7FC0,0x4440,0x0E40,0x00C0,0x01C0,0x0000}}, // F
{ 0, {0x1F00,0x3F80,0x60C0,0x4840,0x4840,0x38C0,0x7980,0x0000}}, // G
{ 0, {0x7FC0,0x7FC0,0x0400,0x0400,0x0400,0x7FC0,0x7FC0,0x0000}}, // H
{ 0, {0x0000,0x0000,0x4040,0x7FC0,0x7FC0,0x4040,0x0000,0x0000}}, // I
{ 0, {0x3000,0x7000,0x4000,0x4040,0x7FC0,0x3FC0,0x0040,0x0000}}, // J
{ 0, {0x4040,0x7FC0,0x7FC0,0x0400,0x1F00,0x7BC0,0x60C0,0x0000}}, // K
{ 0, {0x4040,0x7FC0,0x7FC0,0x4040,0x4000,0x6000,0x7000,0x0000}}, // L
{ 0, {0x7FC0,0x7FC0,0x0380,0x0700,0x0380,0x7FC0,0x7FC0,0x0000}}, // M
{ 0, {0x7FC0,0x7FC0,0x0380,0x0700,0x0E00,0x7FC0,0x7FC0,0x0000}}, // N
{ 0, {0x1F00,0x3F80,0x60C0,0x4040,0x60C0,0x3F80,0x1F00,0x0000}}, // O
{ 0, {0x4040,0x7FC0,0x7FC0,0x4440,0x0440,0x07C0,0x0380,0x0000}}, // P
{-1, {0x0FC0,0x1FE0,0x1020,0x1C20,0x7820,0x7FE0,0x4FC0,0x0000}}, // Q
{ 0, {0x4040,0x7FC0,0x7FC0,0x0440,0x0C40,0x7FC0,0x7380,0x0000}}, // R
{ 0, {0x3180,0x73C0,0x4640,0x4440,0x4C40,0x79C0,0x3180,0x0000}}, // S
{ 0, {0x0000,0x01C0,0x40C0,0x7FC0,0x7FC0,0x40C0,0x01C0,0x0000}}, // T
{ 0, {0x3FC0,0x7FC0,0x4000,0x4000,0x4000,0x7FC0,0x3FC0,0x0000}}, // U
{ 0, {0x0FC0,0x1FC0,0x3000,0x6000,0x3000,0x1FC0,0x0FC0,0x0000}}, // V
{ 0, {0x1FC0,0x7FC0,0x7000,0x3C00,0x7000,0x7FC0,0x1FC0,0x0000}}, // W
{ 0, {0x60C0,0x71C0,0x1F00,0x0E00,0x1F00,0x71C0,0x60C0,0x0000}}, // X
{ 0, {0x0000,0x03C0,0x47C0,0x7C00,0x7C00,0x47C0,0x03C0,0x0000}}, // Y
{ 0, {0x71C0,0x78C0,0x4C40,0x4640,0x4340,0x61C0,0x70C0,0x0000}}, // Z
{ 0, {0x0000,0x0000,0x7FC0,0x7FC0,0x4040,0x4040,0x0000,0x0000}}, // [
{ 0, {0x01C0,0x0380,0x0700,0x0E00,0x1C00,0x3800,0x7000,0x0000}}, //'\'
{ 0, {0x0000,0x0000,0x4040,0x4040,0x7FC0,0x7FC0,0x0000,0x0000}}, // ]
{ 7, {0x4000,0x6000,0x3000,0x1800,0x3000,0x6000,0x4000,0x0000}}, // ^
{-2, {0x4000,0x4000,0x4000,0x4000,0x4000,0x4000,0x4000,0x4000}}, // _
{ 8, {0x0000,0x0000,0x3000,0x7000,0x4000,0x0000,0x0000,0x0000}}, // `
{ 0, {0x3000,0x7A00,0x4A00,0x4A00,0x3E00,0x7C00,0x4000,0x0000}}, // a
{ 0, {0x0040,0x7FC0,0x7FC0,0x4200,0x4600,0x7C00,0x3800,0x0000}}, // b
{ 0, {0x3C00,0x7E00,0x4200,0x4200,0x4200,0x6600,0x2400,0x0000}}, // c
{ 0, {0x3800,0x7C00,0x4600,0x4240,0x3FC0,0x7FC0,0x4000,0x0000}}, // d
{ 0, {0x3C00,0x7E00,0x4A00,0x4A00,0x4A00,0x6E00,0x2C00,0x0000}}, // e
{ 0, {0x4400,0x7F80,0x7FC0,0x4440,0x00C0,0x0180,0x0000,0x0000}}, // f
{-2, {0x2700,0x6F80,0x4880,0x4880,0x7F00,0x3F80,0x0080,0x0000}}, // g
{ 0, {0x4040,0x7FC0,0x7FC0,0x0400,0x0200,0x7E00,0x7C00,0x0000}}, // h
{ 0, {0x0000,0x0000,0x4200,0x7EC0,0x7EC0,0x4000,0x0000,0x0000}}, // i
{-2, {0x0000,0x3000,0x7000,0x4000,0x4080,0x7FB0,0x3FB0,0x0000}}, // j
{ 0, {0x4040,0x7FC0,0x7FC0,0x0800,0x1C00,0x7600,0x6200,0x0000}}, // k
{ 0, {0x0000,0x0000,0x4040,0x7FC0,0x7FC0,0x4000,0x0000,0x0000}}, // l
{ 0, {0x7E00,0x7E00,0x0600,0x3C00,0x0600,0x7E00,0x7C00,0x0000}}, // m
{ 0, {0x0200,0x7E00,0x7C00,0x0200,0x0200,0x7E00,0x7C00,0x0000}}, // n
{ 0, {0x3C00,0x7E00,0x4200,0x4200,0x4200,0x7E00,0x3C00,0x0000}}, // o
{-2, {0x4080,0x7F80,0x7F00,0x4880,0x0880,0x0F80,0x0700,0x0000}}, // p
{-2, {0x0700,0x0F80,0x0880,0x4880,0x7F00,0x7F80,0x4080,0x0000}}, // q
{ 0, {0x4200,0x7E00,0x7C00,0x4600,0x0200,0x0E00,0x0C00,0x0000}}, // r
{ 0, {0x2400,0x6E00,0x4A00,0x5A00,0x5200,0x7600,0x2400,0x0000}}, // s
{ 0, {0x0200,0x0200,0x3F80,0x7FC0,0x4200,0x6200,0x2000,0x0000}}, // t
{ 0, {0x3E00,0x7E00,0x4000,0x4000,0x3E00,0x7E00,0x4000,0x0000}}, // u
{ 0, {0x0000,0x1E00,0x3E00,0x6000,0x6000,0x3E00,0x1E00,0x0000}}, // v
{ 0, {0x3E00,0x7E00,0x6000,0x3800,0x6000,0x7E00,0x3E00,0x0000}}, // w
{ 0, {0x4200,0x6600,0x3C00,0x1800,0x3C00,0x6600,0x4200,0x0000}}, // x
{-2, {0x4780,0x4F80,0x4800,0x4800,0x6800,0x3F80,0x1F80,0x0000}}, // y
{ 0, {0x4600,0x6600,0x7200,0x5A00,0x4E00,0x6600,0x6200,0x0000}}, // z
{ 0, {0x0000,0x0400,0x0400,0x3F80,0x7BC0,0x4040,0x4040,0x0000}}, // {
{ 0, {0x0000,0x0000,0x0000,0x7BC0,0x7BC0,0x0000,0x0000,0x0000}}, // |
{ 0, {0x0000,0x4040,0x4040,0x7BC0,0x3F80,0x0400,0x0400,0x0000}}, // }
{ 7, {0x4000,0x6000,0x2000,0x6000,0x4000,0x6000,0x2000,0x0000}}, // ~
{ 1, {0x7000,0x7800,0x4C00,0x4600,0x4C00,0x7800,0x7000,0x0000}}  //
}};

struct draw_t {
    size_t w, row_bytes;
    size_t h;
    std::vector<uint8_t> pixels;
    draw_t(size_t w, size_t h) : w(w), row_bytes(1 + (w+7)/8), h(h), pixels(h * row_bytes) {
        for (auto & x: pixels | std::views::stride(row_bytes))
            x = 0xff;
    }

    void set_pixel(int x, int y, bool value) {
        uint8_t m = 0x80 >> (x & 7);
        size_t addr = y * row_bytes + 1 + x/8;
        if (value) {
            pixels[addr] |= m;
        } else {
            pixels[addr] &= ~m;
        }
    }
    void set_hline(int x1, int x2, int y, bool value) {
        uint8_t m1 =  ((0x100 >> (x1 & 7)) - 1);
        uint8_t m2 = ~((0x080 >> (x2 & 7)) - 1);
        size_t base_addr = y * row_bytes + 1;
        if (x1/8 == x2/8) {
            if (value) {
                pixels[base_addr + x1/8] |= m1 & m2;
            } else {
                pixels[base_addr + x1/8] &= ~(m1 & m2);
            }
        } else {
            if (value) {
                pixels[base_addr + x1/8] |= m1;
                pixels[base_addr + x2/8] |= m2;
            } else {
                pixels[base_addr + x1/8] &= ~m1;
                pixels[base_addr + x2/8] &= ~m2;
            }
            for (int addr : std::views::iota(base_addr + x1/8 + 1, base_addr + x2/8))
                pixels[addr] = -!!value;
        }
    }
    void set_slope(int x1, int x2, int y1, int y2, float thick, bool value) {
        float slope = 1.0 * (x2 - x1) / std::abs(y2 - y1);
        float tan = 0.5 / std::sqrt(1. + slope*slope);
        int x_low  = std::min<int>(std::max<int>(0, x1 - tan*thick), w-1);
        int x_high = std::min<int>(std::max<int>(0, x2 + tan*thick), w-1);
        for (int d : std::views::iota(0, std::abs(y2-y1)+1)) {
            int l = (d + 0.5) * slope - tan * thick;
            int r = (d + 1.5) * slope + tan * thick;
            int y = y2 > y1 ? y1 + d : y1 - d;
            l = std::max(x_low, std::min(l + x1, x_high));
            r = std::max(l,     std::min(r - 1 + x1, x_high));
            set_hline(l, r, y, value);
        }
    }

    void write_png(const std::string& filename) { 
        std::ofstream out(filename, std::ios::binary);
        uint32_t width = w;
        uint32_t height = h;
        std::vector<uint8_t> png_data {137, 80, 78, 71, 13, 10, 26, 10};
        auto png = std::back_inserter(png_data);
        std::vector<uint8_t> ihdr_data {'I', 'H', 'D', 'R'};
        auto ihdr = std::back_inserter(ihdr_data);
        insert_be(ihdr, width);
        insert_be(ihdr, height);
        std::ranges::copy(std::array<uint8_t,5>{1,0,0,0,0}, ihdr);
        insert_be(png, uint32_t{13});
        std::ranges::copy(ihdr_data, png);
        insert_be(png, crc(ihdr_data));
        std::vector<uint8_t> compressed_data { deflate(pixels) };
        insert_be(std::back_inserter(compressed_data), adler32(pixels));
        constexpr std::array<uint8_t,6> idat_type {'I', 'D', 'A', 'T', 0x78, 0x01};
        insert_be(png, static_cast<uint32_t>(compressed_data.size() + 2));
        std::ranges::copy(idat_type, png);
        std::ranges::copy(compressed_data, png);
        insert_be(png, crc(std::views::concat(idat_type, compressed_data)));
        constexpr std::array<uint8_t, 4> iend_type {'I', 'E', 'N', 'D'};
        insert_be(png, uint32_t{0});
        std::ranges::copy(iend_type, png);
        insert_be(png, crc(iend_type));
        out.write(reinterpret_cast<const char*>(png_data.data()), png_data.size());
    }

    struct kwargs_t {int fill = 0; int outline=0; int width = 1; int m = 0; int os = 0;};
    void line(std::tuple<int,int,int,int> coord, kwargs_t kwargs) {
        auto [x1,y1,x2,y2] = coord;
        x1 = std::min<int>(w-1, std::max<int>(x1, 0));
        x2 = std::min<int>(w-1, std::max<int>(x2, 0));
        y1 = std::min<int>(h-1, std::max<int>(y1, 0));
        y2 = std::min<int>(h-1, std::max<int>(y2, 0));
        if (y1 == y2)
            for (int i : std::views::iota(0,kwargs.width))
                set_hline(std::min(x1, x2), std::max(x1, x2), y1 + (i+1)/2 * ((i&1)*2-1), !kwargs.fill);
        else {
            if (x1 > x2) {
                std::tie(x1, x2) = std::tuple{x2, x1};
                std::tie(y1, y2) = std::tuple{y2, y1};
            }
            set_slope(x1, x2, y1, y2, kwargs.width, !kwargs.fill);
        }
    }
    void ellipse(std::tuple<int,int,int,int> coord, kwargs_t kwargs) {
        auto [x1,y1,x2,y2] = coord;
        std::tie(x1, x2) = std::tuple{std::min(x1, x2), std::max(x1, x2)};
        std::tie(y1, y2) = std::tuple{std::min(y1, y2), std::max(y1, y2)};
        int dx = (x2 - x1) + kwargs.width;
        float ox = (x1 + x2) * 0.5;
        float oy = (y1 + y2) * 0.5;
        float ro = dx * 0.5, ri = dx * 0.5 - kwargs.width;
        for (int y : std::views::iota(std::max(0,y1-kwargs.width), std::min<int>(h-1,y2+kwargs.width+1))) {
            for (int x : std::views::iota(std::max(0,x1-kwargs.width), std::min<int>(w-1,x2+kwargs.width+1))) {
                float rsq = (x-ox)*(x-ox) + (y-oy)*(y-oy);
                if (rsq <= ri*ri)
                    set_pixel(x, y, !kwargs.fill);
                else if (rsq <= ro*ro)
                    set_pixel(x, y, !kwargs.outline);
            }
        }
    }
    void text(std::tuple<int,int> coord, std::string text, std::string anchor) {
        auto [l,t] = coord;
        int length = text.size() * 8;
        auto [r,b] = std::tuple{l + length, t + 15};
        if (anchor[0] == 'r') {
            l -= length; r -= length;
        }
        for (int x : std::views::iota(std::max(l,0),std::min<int>(r,w))) {
            size_t nchr = (x - l) / 8;
            size_t ncol = (x - l) & 7;
            int chr = text[nchr];
            if (chr > 0x7f or chr < 0x20) chr = '?';
            const auto& [offset, dots] = font[chr - 0x20];
            
            for (int y : std::views::iota(std::max(t-offset,0), std::min<int>(b-offset,h))) {
                if ((dots[ncol] >> (y - t + offset)) & 1)
                    set_pixel(x, y, 1);
            }
        }
        
    }
    void mos(int x, int y) {
        line({x+15,y+25,x+20,y+25},{.fill=1,.width=2});
        line({x+15,y+10,x+15,y+40},{.fill=0,.width=2});
        line({x+20,y+10,x+20,y+40},{.fill=0,.width=2});
        line({x+25,y   ,x+25,y+10},{.fill=0,.width=2});
        line({x+25,y+40,x+25,y+50},{.fill=0,.width=2});
        line({x+20,y+10,x+25,y+10},{.fill=0,.width=2});
        line({x+20,y+40,x+25,y+40},{.fill=0,.width=2});
    }
    void nmos(std::tuple<int,int> coord) {
        auto [x,y] = coord;
        line({x,y+25,x+15,y+25},{.fill=0,.width=2});
        mos(x, y);
    }
    void pmos(std::tuple<int,int> coord) {
        auto [x,y] = coord;
        line({x,y+25,x+11,y+25},{.fill=0,.width=2});
        ellipse({x+11,y+22,x+15,y+27},{.fill=1,.outline=0,.width=2});
        mos(x, y);
    }
    void inv(std::tuple<int,int> coord) {
        auto [x,y] = coord;
        ellipse({x+35-2,y-2,x+35+2,y+2},{.fill=0,.outline=0,.width=2});
        line({x+35,y,    x+35,y+10}, {.fill=0,.width=2});
        pmos({x+10,y+10});
        line({x+35,y+60, x+35,y+80}, {.fill=0,.width=2});
        line({x+35,y+70, x+60,y+70}, {.fill=0,.width=2});
        nmos({x+10,y+80});
        line({x+35,y+130,x+35,y+140},{.fill=0,.width=2});
        line({x+30,y+140,x+40,y+140},{.fill=0,.width=1});
        line({x+30,y+140,x+35,y+145},{.fill=0,.width=1});
        line({x+40,y+140,x+35,y+145},{.fill=0,.width=1});
        line({x,   y+35, x,   y+105},{.fill=0,.width=2});
        line({x,   y+35, x+10,y+35}, {.fill=0,.width=2});
        line({x,   y+105,x+10,y+105},{.fill=0,.width=2});
    }
    void nand(std::tuple<int,int> coord) {
        auto [x,y] = coord;
        ellipse({x+35-2, y-2,x+35+2, y+2},{.fill=0,.outline=0,.width=2});
        ellipse({x+115-2,y-2,x+115+2,y+2},{.fill=0,.outline=0,.width=2});
        line({x+35, y,    x+35, y+10}, {.fill=0,.width=2});
        pmos({x+10,y+10});
        line({x+115,y,    x+115,y+10}, {.fill=0,.width=2});
        pmos({x+90,y+10});
        line({x+35, y+60, x+35, y+80}, {.fill=0,.width=2});
        line({x+115,y+60, x+115,y+70}, {.fill=0,.width=2});
        line({x+35, y+70, x+140,y+70}, {.fill=0,.width=2});
        nmos({x+10,y+80});
        nmos({x+90,y+80});
        line({x+35, y+130,x+115,y+130},{.fill=0,.width=2});
        line({x+115,y+80, x+130,y+80}, {.fill=0,.width=2});
        line({x+130,y+80, x+130,y+140},{.fill=0,.width=2});
        line({x+125,y+140,x+135,y+140},{.fill=0,.width=1});
        line({x+125,y+140,x+130,y+145},{.fill=0,.width=1});
        line({x+135,y+140,x+130,y+145},{.fill=0,.width=1});
        line({x,    y+35, x,    y+105},{.fill=0,.width=2});
        line({x,    y+35, x+10, y+35}, {.fill=0,.width=2});
        line({x,    y+105,x+10, y+105},{.fill=0,.width=2});
        line({x+80, y+35, x+80, y+105},{.fill=0,.width=2});
        line({x+80, y+35, x+90, y+35}, {.fill=0,.width=2});
        line({x+80, y+105,x+90, y+105},{.fill=0,.width=2});
    }
};

const std::unordered_map<int, std::tuple<int, int>> CELL_SIZE = {
    {NOT,  {12, 28}},
    {NAND, {28, 28}}
};
const std::unordered_map<int, std::vector<std::tuple<int, int>>> PORT_OFFSET = {
    {NOT,  {{0,14},{12,14}}},
    {NAND, {{0,14},{16,14},{28,14}}}
};

constexpr auto operator+(const std::tuple<int,int>& lhs, const std::tuple<int,int>& rhs) {
    return std::tuple{std::get<0>(lhs)+std::get<0>(rhs), std::get<1>(lhs)+std::get<1>(rhs)};
}

std::tuple<long,
           std::vector<std::vector<std::tuple<int,int>>>,
           std::vector<std::tuple<int,int>>>
route(const std::set<int>& inputs,
      const std::set<int>& outputs,
      const std::unordered_map<int, std::pair<int, std::vector<int>>>& gates,
      const std::unordered_map<int, std::tuple<int,int>>& placement,
                        size_t canvas_w, size_t canvas_h) {
    std::vector<std::tuple<int,int,int,int,int,int>> todo;
    std::vector<std::vector<std::tuple<int,int>>> paths;
    std::vector<std::tuple<int,int>> solders;
    std::vector<int> drive(canvas_w*canvas_h);
    std::vector<int> mask(canvas_w*canvas_h);
    auto at = [canvas_h](size_t x, size_t y){ return x*canvas_h + y; };
    long cost = 0;
    for (const auto& [sink, values] : gates) {
        const auto& [sinkgatetype, inports] = values;
        for (const auto& [i, source] : std::views::enumerate(inports)) {
            if (inputs.contains(source) or outputs.contains(source)) continue;
            auto sourcegatetype = gates.at(source).first;
            auto [x1, y1] = placement.at(source) + PORT_OFFSET.at(sourcegatetype).back();
            auto [x2, y2] = placement.at(sink)   + PORT_OFFSET.at(sinkgatetype)[i];
            auto semipm = std::abs(x1 - (int)canvas_w/2) + std::abs(y1 - (int)canvas_h/2);

            todo.emplace_back(semipm, x1, y1, x2, y2, source);
        }
        static const std::unordered_map<int, void(*)(int,int,size_t,decltype(mask)&)> mask_func {
            {NOT,  +[](int X, int Y, size_t canvas_h, decltype(mask)& mask){
                       for (size_t x = X+1; x <= X+11; x++) for (size_t y = Y-2; y <= Y+30; y++) {
                           mask[x*canvas_h + y] = 3;
                       }
                   } },
            {NAND, +[](int X, int Y, size_t canvas_h, decltype(mask)& mask){
                       for (size_t x = X+1; x <= X+15; x++) for (size_t y = Y-2; y <= Y+30; y++) {
                           mask[x*canvas_h + y] = 3;
                       }
                       for (size_t x = X+15; x <= X+17; x++) for (size_t y = Y+8; y <= Y+20; y++) {
                           mask[x*canvas_h + y] = 3;
                       }
                       for (size_t x = X+17; x <= X+27; x++) for (size_t y = Y-2; y <= Y+30; y++) {
                           mask[x*canvas_h + y] = 3;
                       }
                   } },
        };
        auto [X, Y] = placement.at(sink);
        (*mask_func.at(sinkgatetype))(X, Y, canvas_h, mask);
    }
    for (size_t x = 0; x < canvas_w; x++) for (size_t y = 5; y < canvas_h; y+=40) {
        mask[at(x,y)] = 1;
    }
    std::sort(todo.begin(), todo.end());
    int done = 0;
    for (auto [_, x1, y1, x2, y2, driver_id] : todo) {
        std::vector<int> mark(canvas_w*canvas_h);
        bool marked = true, reached = false;
        int i = 0;
        size_t x, y;
        for (y = y2-7; y <= y2+7; y++)
            mark[at(x2,y)] = 1;
        do { i++;
            [&](){
                marked = false;
                for (x = 0; x < canvas_w; x++) for (y = 0; y < canvas_h; y++) {
                    if (mark[at(x,y)] == i) {
                        marked = true;
                        if (drive[at(x,y)] == driver_id or (x == x1 and y == y1)) {
                            reached = true; return;
                        }
                        if (x+1<canvas_w and (mask[at(x,y)]   & 1) == 0 and !mark[at(x+1,y)])
                            mark[at(x+1,y)] = i+1;
                        if (x>=1         and (mask[at(x-1,y)] & 1) == 0 and !mark[at(x-1,y)])
                            mark[at(x-1,y)] = i+1;
                        if (y+1<canvas_h and (mask[at(x,y)]   & 2) == 0 and !mark[at(x,y+1)])
                            mark[at(x,y+1)] = i+1;
                        if (y>=1         and (mask[at(x,y-1)] & 2) == 0 and !mark[at(x,y-1)])
                            mark[at(x,y-1)] = i+1;
                    }
                }
            }();
        } while (marked and !reached);
        if (!marked) {
            std::cout << "\nerror: routing failed" << std::endl;
            return { -1, paths, solders };
        }
        if (x != x1 or y != y1) solders.emplace_back(x,y);
        decltype(paths)::value_type path;
        int k = 1;
        while (mark[at(x,y)] > 1) {
            path.emplace_back(x,y);
            drive[at(x,y)] = driver_id;
            cost += 1;
            if        (k == 0 and x>=1           and mark[at(x-1,y)] > 0 and mark[at(x-1,y)] < mark[at(x,y)]) {
                mask[at(x-1,y)] |= 1;
                x--;
            } else if (k == 1 and x+1 < canvas_w and mark[at(x+1,y)] > 0 and mark[at(x+1,y)] < mark[at(x,y)]) {
                mask[at(x,y)]   |= 1;
                x++;
            } else if (k == 2 and y>=1           and mark[at(x,y-1)] > 0 and mark[at(x,y-1)] < mark[at(x,y)]) {
                mask[at(x,y-1)] |= 2;
                y--;
            } else if (k == 3 and y+1 < canvas_h and mark[at(x,y+1)] > 0 and mark[at(x,y+1)] < mark[at(x,y)]) {
                mask[at(x,y)]   |= 2;
                y++;
            } else if (x>=1           and mark[at(x-1,y)] > 0 and mark[at(x-1,y)] < mark[at(x,y)]) {
                mask[at(x-1,y)] |= 1;
                mask[at(x,y)]   |= 2;
                x--; k = 0;
            } else if (x+1 < canvas_w and mark[at(x+1,y)] > 0 and mark[at(x+1,y)] < mark[at(x,y)]) {
                mask[at(x,y)]   |= 3;
                x++; k = 1;
            } else if (y>=1           and mark[at(x,y-1)] > 0 and mark[at(x,y-1)] < mark[at(x,y)]) {
                mask[at(x,y)]   |= 1;
                mask[at(x,y-1)] |= 2;
                y--; k = 2;
            } else if (y+1 < canvas_h and mark[at(x,y+1)] > 0 and mark[at(x,y+1)] < mark[at(x,y)]) {
                mask[at(x,y)]   |= 3;
                y++; k = 3;
            } else {
                std::cout << "\nerror: routing failed" << std::endl;
                return { -1, paths, solders };
            }
        }
        path.emplace_back(x,y);
        drive[at(x,y)] = driver_id;
        paths.push_back(std::move(path));
        solders.emplace_back(x,y);
        for (y = y2-7; y <= y2+7; y++)
            drive[at(x2,y)] = driver_id;
        done++;
        std::cout << "[" << std::string(done * 70 / todo.size(), '=')
                  << '>' << std::string(70 - done * 70 / todo.size(), '.')
                  << std::format("] {:3d}%\r", done * 100 / todo.size());
    }
    std::cout << std::endl;
    return { cost, paths, solders };
}

std::tuple<size_t,size_t> snap_to_microgrid(
        std::unordered_map<int, std::tuple<int,int>>& placement,
        const std::unordered_map<int, std::pair<int, std::vector<int>>>& gates,
        double slackness) {
    int min_x = std::numeric_limits<int>::max();
    int min_y = std::numeric_limits<int>::max();
    int max_x = 0;
    int max_y = 0;
    for (auto& [gate, coord] : placement) {
        auto& [x, y] = coord;
        x = std::ceil(x * 2 * slackness); y = y * 40;
        min_x = std::min(x, min_x);
        min_y = std::min(y, min_y);
    }
    for (auto& [gate, coord] : placement) {
        auto& [x, y] = coord;
        x = x - min_x + 10; y = y - min_y + 5;
        auto [gate_size_x, gate_size_y] = CELL_SIZE.at(std::get<0>(gates.at(gate)));
        max_x = std::max(max_x, x + gate_size_x);
        max_y = std::max(max_y, y + gate_size_y);
    }
    return std::tuple<size_t,size_t>{ max_x + 10, max_y + 5 };
}

double fast_route_estimate(
        const std::unordered_map<int, std::tuple<int,int>>& placement,
        const std::set<int>& inputs, const std::set<int>& outputs,
        const std::unordered_map<int, std::pair<int, std::vector<int>>>& gates) {
    std::vector<std::tuple<int,int,int>> connections;
    auto [l, t] = placement.cbegin()->second;
    auto [r, b] = placement.cbegin()->second;
    for (const auto& [sink, values] : gates) {
        const auto& [sinkgatetype, inports] = values;
        auto [x, y] = placement.at(sink);
        l = std::min(l, x); t = std::min(t, y);
        r = std::max(r, x); b = std::max(b, y);
        for (const auto& [i, source] : std::views::enumerate(inports)) {
            if (inputs.contains(source) or outputs.contains(source)) continue;
            connections.emplace_back(source, sink, i);
        }
    }
    double cost = (r-l) * (b-t) * area_cost;
    for (const auto& [source, sink, port_id] : connections) {
        auto [sx, sy] = placement.at(source);
        auto [dx, dy] = placement.at(sink);
        auto [source_xoff, source_yoff] = PORT_OFFSET.at(std::get<0>(gates.at(source))).back();
        auto [sink_xoff, sink_yoff]     = PORT_OFFSET.at(std::get<0>(gates.at(sink  )))[port_id];
        cost += std::abs((sx+source_xoff)-(dx+sink_xoff)) + std::abs(((sy+source_yoff)-(dy+sink_yoff))*40);
        cost += (sy == dy) ? 0 : cross_track_penalty;
    }
    return cost;
}

std::unordered_map<int, std::tuple<int,int>> place(
        std::set<int> inputs, std::set<int> outputs,
        const std::unordered_map<int, std::pair<int, std::vector<int>>>& gates) {
    double temperature = initial_temperature;
    std::unordered_map<int, std::tuple<int,int>> placement;
    auto is_overlapping = [&](const decltype(placement)& placement) {
        std::deque<std::map<int,int>> track;
        int min_track = 0;
        for (const auto& [gate, coord] : placement) {
            const auto& [x, y] = coord;
            const auto& gatetype = std::get<0>(gates.at(gate));
            auto [width, _] = CELL_SIZE.at(gatetype);
            int l = x, r = x + width/2; 
            
            if (y - min_track >= (int)track.size()) {
                track.append_range(std::views::repeat(std::map<int,int>{}, y - min_track - track.size() + 1));
                track.back().emplace(l, r);
            } else if (y - min_track < 0) {
                track.prepend_range(std::views::repeat(std::map<int,int>{}, min_track - y));
                min_track = y;
                track.front().emplace(l, r);
            } else {
                auto& occupacy = track[y - min_track];
                auto il = std::ranges::upper_bound(std::views::values(occupacy), l).base();
                auto ir = occupacy.lower_bound(r);
                if (il == ir) occupacy.emplace_hint(ir, l, r);
                else return true;
            }
        }
        return false;
    };
    int estimated_tracks = std::round(std::sqrt(gates.size() * initial_area_margins));
    std::mt19937 rng(std::random_device{}());
    for (const auto& [gate, values] : gates) {
        const auto& gatetype = std::get<0>(values);
        do {
            int new_x = std::uniform_int_distribution<int>(0, estimated_tracks * 20)(rng);
            int new_y = std::uniform_int_distribution<int>(0, estimated_tracks     )(rng);
            placement[gate] = {new_x, new_y};
        } while (is_overlapping(placement));
    }
    double current_energy = fast_route_estimate(placement, inputs, outputs, gates);
    auto best_placement{ placement };
    auto best_energy{ current_energy };
    auto choice = std::uniform_int_distribution<int>(0, placement.size()-1);
    auto gauss = std::normal_distribution<double>(0, 1);
    auto dice = std::uniform_real_distribution<double>(0, 1);
    auto tick = std::chrono::system_clock::now();
    auto tock = tick;
    for (int iteration = 0; temperature > stop_temperature; iteration++) {
        auto new_placement{ placement };
        do {
            std::array<int,2> ridx { choice(rng), choice(rng) };
            std::tie(ridx[0], ridx[1]) = std::tuple<int,int>{ std::min(ridx[0], ridx[1]), std::abs(ridx[0]-ridx[1]) };
            auto iter = new_placement.begin();
            for (auto i : ridx) {
                std::advance(iter, i);
                std::get<0>(iter->second) += int(gauss(rng)*std::log(temperature)*20);
                std::get<1>(iter->second) += int(gauss(rng)*std::log(temperature));
            }
        } while (is_overlapping(new_placement));
        double new_energy = fast_route_estimate(new_placement, inputs, outputs, gates);
        if (new_energy < current_energy or dice(rng) < std::exp((current_energy-new_energy)/temperature)) {
            placement = std::move(new_placement);
            current_energy = new_energy;
            if (current_energy < best_energy) {
                best_placement = placement;
                best_energy = current_energy;
            }
        }
        temperature *= cooling_rate;
        auto now = std::chrono::system_clock::now();
        if (now - tick > 50ms) {
            std::cout << std::format("Temperature {:3.3f}, Energy {}  \r", temperature, current_energy) << std::flush;
            tick = now;
        }
        if (now - tock > step_timeout) break;
        tock = now;
    }
    std::cout << std::format("Temperature {:3.3f}, Energy {}  \n", temperature, best_energy);
    return best_placement;
}

void draw_schematic(
        const std::set<int>& inputs, const std::set<int>& outputs,
        const std::unordered_map<int, std::pair<int, std::vector<int>>>& gates,
        const std::vector<std::string> names,
        const std::vector<std::vector<std::tuple<int,int>>>& wires,
        const std::vector<std::tuple<int,int>>& solders,
        const std::unordered_map<int, std::tuple<int,int>>& placement,
        size_t canvas_w, size_t canvas_h) {
    draw_t draw(canvas_w*5, canvas_h*5);
    static const std::unordered_map<int, void(draw_t::*)(std::tuple<int,int>)> DRAWFN {
        {NOT, &draw_t::inv}, {NAND, &draw_t::nand}
    };
    // draw stdcells
    for (const auto& [name, values] : gates) {
        const auto& [gatetype, _] = values;
        const auto& [x, y] = placement.at(name);
        (draw.*DRAWFN.at(gatetype))({x*5,y*5});
    }
    // draw powergrid
    for (size_t y = 25; y < canvas_h*5; y+=200)
        draw.line({0,y,canvas_w*5,y},{.width=2});
    // draw wires
    for (const auto& wire : wires) {
        auto [x1, y1] = wire.front();
        for (const auto& [x2, y2] : wire | std::views::drop(1)) {
            draw.line({x1*5, y1*5, x2*5, y2*5},{.fill=0,.width=2});
            std::tie(x1, y1) = std::tuple{x2, y2};
        }
    }
    // draw solder joints
    for (const auto& [x, y] : solders) {
        draw.ellipse({x*5-2, y*5-2, x*5+2, y*5+2},{.fill=0,.outline=0,.width=1});
    }
    // draw port labels
    for (const auto& [sink, values] : gates) {
        const auto& [sinkgatetype, inports] = values;
        for (const auto& [i, source] : std::views::enumerate(inports)) {
            if (inputs.contains(source)) {
                auto [x, y] = placement.at(sink) + PORT_OFFSET.at(sinkgatetype)[i];
                y = y + 2;
                draw.text({x*5-12, y*5-8}, names[source], "rt");
                draw.line({x*5-10,y*5-2,x*5-6,y*5-2},   {.fill=0,.width=1});
                draw.line({x*5-10,y*5-1,x*5-4,y*5-1},   {.fill=0,.width=1});
                draw.line({x*5-10,y*5-0,x*5-2,y*5-0},   {.fill=0,.width=1});
                draw.line({x*5-10,y*5+1,x*5-4,y*5+1},   {.fill=0,.width=1});
                draw.line({x*5-10,y*5+2,x*5-6,y*5+2},   {.fill=0,.width=1});
            }
        }
    }
    for (const auto& output : outputs) {
        const auto& gatetype = gates.at(output).first;
        auto [x, y] = placement.at(output) + PORT_OFFSET.at(gatetype).back();
        draw.text({x*5+10, y*5-8}, names[output], "lt");
        draw.line({x*5+8,y*5-2,x*5+4,y*5-2},   {.fill=0,.width=1});
        draw.line({x*5+8,y*5-1,x*5+2,y*5-1},   {.fill=0,.width=1});
        draw.line({x*5+8,y*5-0,x*5+0,y*5-0},   {.fill=0,.width=1});
        draw.line({x*5+8,y*5+1,x*5+2,y*5+1},   {.fill=0,.width=1});
        draw.line({x*5+8,y*5+2,x*5+4,y*5+2},   {.fill=0,.width=1});
    }
    draw.write_png(schematic_filename);
}

int main(int argc, char *argv[]) {
    auto [inputs, outputs, gates, names] = parse(argc, argv);
    if (gates.empty()) return 0;
    auto placement = place(inputs, outputs, gates);
    for (double slackness = 1.0; slackness < 10.; slackness *= 1.05) {
        std::cout << "slackness: " << slackness << std::endl;
        decltype(placement) micro_placement(placement);
        auto [canvas_w, canvas_h] = snap_to_microgrid(micro_placement, gates);
        auto [cost, wires, solders] = route(inputs, outputs, gates, micro_placement, canvas_w, canvas_h);
        if (cost < 0) continue;
        std::cout << "total wire length: " << cost << std::endl;
        draw_schematic(inputs, outputs, gates, names, wires, solders, micro_placement, canvas_w, canvas_h);
        std::cout << "schematic generated." << std::endl;
        return 0;
    }
    std::cout << "error: all routing attempts failed, no schematic generated." << std::endl;
    return 0;
}

附一段DeepSeek-R1对代码的解析：

展开解析

这个程序是一个用于生成标准CMOS电路原理图的工具，支持从BLIF格式输入并输出PNG图像。以下是其核心功能和工作流程的解读：

1. 输入解析（parse函数）

   • 功能：解析BLIF文件，提取电路的输入、输出端口及逻辑门信息。
   • 关键数据结构：
     • inputs/outputs：存储输入/输出端口的ID。
     • gates：以哈希表形式存储逻辑门，键为门ID，值为门类型（如NOT、NAND）及其连接的端口列表。
     • names：将门类型名称映射为唯一ID，支持动态扩展。
   • 处理逻辑：
     • 通过逐行解析.inputs、.outputs和.subckt段，提取端口和子电路信息。
     • 使用parse_name函数将字符串类型的门名称转换为整数ID，便于后续处理。

2. 布局优化（place函数）

   • 算法：基于模拟退火算法进行布局优化，目标是最小化布线成本和面积。
   • 关键参数：
     • initial_temperature：初始温度，控制算法早期接受较差解的概率。
     • cooling_rate：冷却速率，逐步降低温度以收敛到最优解。
     • area_cost和cross_track_penalty：分别惩罚面积和交叉布线。
   • 流程：
     • 初始布局：随机生成门的位置，确保无重叠。
     • 迭代优化：通过调整门的位置，计算新的布局成本，根据Metropolis准则接受或拒绝新解。
     • 终止条件：温度降至阈值或超时。

3. 布线（route函数）

   • 目标：为逻辑门之间的连接生成路径，避免冲突。
   • 关键步骤：
     • 障碍标记：使用mask数组标记不可布线区域（如门周围的空间）。
     • 路径搜索：基于BFS算法，从目标端口反向搜索到源端口，记录路径。
     • 成本计算：累加路径长度和交叉轨道惩罚。
   • 输出：
     • paths：存储所有连接的路径坐标。
     • solders：记录焊点位置。

4. 绘图（draw_t结构体）

   • 功能：将布局和布线结果绘制为PNG图像。
   • 核心方法：
     • 基本图形：line、ellipse用于绘制线段和焊点。
     • 逻辑门绘制：nmos、pmos、inv、nand等函数实现CMOS门的具体绘制。
     • 文本标签：text函数利用预定义字体位图标注端口名称。
   • PNG生成：通过手动构造PNG文件格式（包括IHDR、IDAT、IEND块），结合DEFLATE压缩和CRC校验，输出最终图像。

5. 主流程（main函数）

   • 解析输入：读取BLIF文件，提取电路信息。
   • 布局优化：调用place生成初始布局。
   • 网格对齐：通过snap_to_microgrid将布局坐标对齐到微网格。
   • 多次布线尝试：逐步增加松弛度（slackness），调用route进行布线，直至成功。
   • 生成图像：成功布线后，调用draw_schematic绘制原理图并保存为PNG。

关键技术与挑战

• 模拟退火算法：平衡全局搜索与局部优化，避免陷入局部最优。
• 路径搜索算法：在动态障碍环境中高效寻找可行路径。
• 低层级绘图：直接操作像素数据并生成符合PNG标准的文件，需处理压缩和校验细节。

总结

该程序通过解析电路描述、优化布局、自动布线和绘图，实现了从逻辑描述到原理图的自动化生成。其核心优势在于结合了算法优化（模拟退火）与底层图形处理，适用于中小规模CMOS电路的快速可视化。

使用

输入读取的是BLIF格式的网表。 可以用开源的Yosys，从Verilog综合得到。

例如先让DeepSeek给我写一个4位加法器作例子：

adder4.v

module adder4 (
    input [3:0] a,      // 4位输入a
    input [3:0] b,      // 4位输入b
    input cin,         // 进位输入
    output [3:0] sum,  // 4位和输出
    output cout        // 进位输出
);

// 使用连续赋值语句实现加法器
assign {cout, sum} = a + b + cin;

endmodule

写一个标准单元库。 当前我在代码里只放了非、与非两种门，要告诉Yosys只用这两种单元。

nandcell.lib

library(demo) {
  cell(NOT) {
    area: 3;
    pin(A) { direction: input; }
    pin(Y) { direction: output;
              function: "A'"; }
  }
  cell(NAND) {
    area: 4;
    pin(A) { direction: input; }
    pin(B) { direction: input; }
    pin(Y) { direction: output;
             function: "(A*B)'"; }
  }
}

启动Yosys，在其中运行这些命令：

read_verilog adder4.v
hierarchy -check
abc -liberty nandcell.lib
synth
splitnets -ports
opt
write_blif -top adder4

最后一步会输出BLIF格式的网表，复制保存到文件adder4.blif里。

adder4.blif

# Generated by Yosys 0.51+104 (git sha1 c08f72b80, g++ 13.3.0-6ubuntu2~24.04 -fPIC -O3)

.model adder4
.inputs a[0] a[1] a[2] a[3] b[0] b[1] b[2] b[3] cin
.outputs sum[0] sum[1] sum[2] sum[3] cout
.names $false
.names $true
1
.names $undef
.subckt NOT A=a[3] Y=$abc$170$new_n15
.subckt NOT A=b[3] Y=$abc$170$new_n16
.subckt NOT A=a[2] Y=$abc$170$new_n17
.subckt NOT A=b[2] Y=$abc$170$new_n18
.subckt NOT A=a[1] Y=$abc$170$new_n19
.subckt NOT A=b[1] Y=$abc$170$new_n20
.subckt NOT A=a[0] Y=$abc$170$new_n21
.subckt NOT A=b[0] Y=$abc$170$new_n22
.subckt NOT A=cin Y=$abc$170$new_n23
.subckt NAND A=a[3] B=b[3] Y=$abc$170$new_n24
.subckt NAND A=a[2] B=b[2] Y=$abc$170$new_n25
.subckt NAND A=$abc$170$new_n17 B=$abc$170$new_n18 Y=$abc$170$new_n26
.subckt NAND A=$abc$170$new_n25 B=$abc$170$new_n26 Y=$abc$170$new_n27
.subckt NOT A=$abc$170$new_n27 Y=$abc$170$new_n28
.subckt NAND A=a[1] B=b[1] Y=$abc$170$new_n29
.subckt NAND A=a[0] B=b[0] Y=$abc$170$new_n30
.subckt NAND A=$abc$170$new_n21 B=$abc$170$new_n22 Y=$abc$170$new_n31
.subckt NAND A=$abc$170$new_n30 B=$abc$170$new_n31 Y=$abc$170$new_n32
.subckt NOT A=$abc$170$new_n32 Y=$abc$170$new_n33
.subckt NAND A=cin B=$abc$170$new_n33 Y=$abc$170$new_n34
.subckt NAND A=$abc$170$new_n30 B=$abc$170$new_n34 Y=$abc$170$new_n35
.subckt NOT A=$abc$170$new_n35 Y=$abc$170$new_n36
.subckt NAND A=$abc$170$new_n19 B=$abc$170$new_n20 Y=$abc$170$new_n37
.subckt NAND A=$abc$170$new_n29 B=$abc$170$new_n37 Y=$abc$170$new_n38
.subckt NOT A=$abc$170$new_n38 Y=$abc$170$new_n39
.subckt NAND A=$abc$170$new_n35 B=$abc$170$new_n39 Y=$abc$170$new_n40
.subckt NAND A=$abc$170$new_n29 B=$abc$170$new_n40 Y=$abc$170$new_n41
.subckt NOT A=$abc$170$new_n41 Y=$abc$170$new_n42
.subckt NAND A=$abc$170$new_n28 B=$abc$170$new_n41 Y=$abc$170$new_n43
.subckt NAND A=$abc$170$new_n25 B=$abc$170$new_n43 Y=$abc$170$new_n44
.subckt NOT A=$abc$170$new_n44 Y=$abc$170$new_n45
.subckt NAND A=$abc$170$new_n15 B=$abc$170$new_n16 Y=$abc$170$new_n46
.subckt NAND A=$abc$170$new_n24 B=$abc$170$new_n46 Y=$abc$170$new_n47
.subckt NOT A=$abc$170$new_n47 Y=$abc$170$new_n48
.subckt NAND A=$abc$170$new_n44 B=$abc$170$new_n48 Y=$abc$170$new_n49
.subckt NAND A=$abc$170$new_n24 B=$abc$170$new_n49 Y=cout
.subckt NAND A=$abc$170$new_n23 B=$abc$170$new_n32 Y=$abc$170$new_n51
.subckt NAND A=$abc$170$new_n34 B=$abc$170$new_n51 Y=$abc$170$new_n52
.subckt NOT A=$abc$170$new_n52 Y=sum[0]
.subckt NAND A=$abc$170$new_n36 B=$abc$170$new_n38 Y=$abc$170$new_n54
.subckt NAND A=$abc$170$new_n40 B=$abc$170$new_n54 Y=$abc$170$new_n55
.subckt NOT A=$abc$170$new_n55 Y=sum[1]
.subckt NAND A=$abc$170$new_n27 B=$abc$170$new_n42 Y=$abc$170$new_n57
.subckt NAND A=$abc$170$new_n43 B=$abc$170$new_n57 Y=$abc$170$new_n58
.subckt NOT A=$abc$170$new_n58 Y=sum[2]
.subckt NAND A=$abc$170$new_n45 B=$abc$170$new_n47 Y=$abc$170$new_n60
.subckt NAND A=$abc$170$new_n49 B=$abc$170$new_n60 Y=$abc$170$new_n61
.subckt NOT A=$abc$170$new_n61 Y=sum[3]
.end

编译cirschem.cpp：g++ cirschem.cpp -std=c++26 -O3

运行：./a.out adder4.blif

稍等半分钟布局布线完成，输出保存为schematic.png