Posts

简单记录一下在 EndeavourOS 上手动编译 Linux 内核的过程。 环境准备 整个过程在虚拟机上完成，具体配置参数如下： Hypervisor: VMware Workstation Pro 17 OS: EndeavourOS Mercury Neo Bootloader: systemd-boot Old Kernel: 6.16.8-arch3-1 New Kernel: 6.17.1 CPU: 8 x 13th Gen Intel(R) Core(TM) i7-13700HX @ 2.30 GHz RAM: 8 GB IP：VMnet8 (NAT) 192.168.255.11 为了操作方便，通过 SSH 从宿主机连接到虚拟机，运行以下命令连接，其中 starryreverie 为已创建用户： ssh starryreverie@192.168.255.11 获取内核源码 内核源码可以从 kernel.org 下载。选择 linux-6.17.1.tar.xz 源码包，并使用以下命令下载： wget https://cdn.kernel.org/pub/linux/kernel/v6.x/linux-6.17.1.tar.xz 在本地新建目录 build，并解压源码包： mkdir build tar -xvf linux-6.17.1.tar.xz -C build 进入源码目录并查看目录： cd build/linux-6.17.1 ls -alh 配置编译环境 在编译内核前，需要安装必要的工具和依赖包。使用以下命令安装： ...

随机渐进式光子映射（Stochastic Progressive Photon Mapping, SPPM）是光子映射系列算法的进阶算法，本文介绍如何实现 SPPM 以及如何将 SPPM 与路径追踪（Path Tracing, PT）结合。 光子映射系列算法 光子映射 光子映射（Photon Mapping, PM）是光子映射系列算法中的初代算法，是一个两阶段算法，包括光子追踪和光子映射。其思想就是首先从光源发射光子，光子在场景中不断反弹，模拟现实世界的过程，然后再使用 Path Tracing，过程中在合适的地方使用光子来估计 radiance，加速渲染。 光子的发射 光子是光源的通量/功率的载体，光源实质上是通过发射光子来实现照明。PM 中的光子与物理中的光子不同，物理学中的光子是光能传递的最小单元，即量子化的性质，单个光子的能量是 $E = h\nu$，而 PM 中的光子实际上是一堆物理中的光子，是更符合应用的模型。所以，接下来所讨论的光子都是 PM 意义下的光子。 如何计算单个光子的通量呢？发射光子的过程实际上就类似于对光源的总通量进行 Monte Carlo 估计的过程，每个光子都是一个样本，每一份通量相加就得到了总通量。所以我们就对光源表面和出射方向进行采样，按照类似的过程计算每一个光子的通量。总通量按照以下积分计算 $$ \begin{aligned} \Phi & = \int_M \int_{\Omega^+} L_e(x, \omega) (n \cdot \omega) \mathrm d\omega \mathrm dA \\ & \approx \dfrac{1}{N} \sum_{i = 1}^N \dfrac{L_e(x, \omega) (n \cdot \omega)}{p(x)p(\omega)} \end{aligned} $$所以单个光子的通量就是 $\dfrac{1}{N} \dfrac{L_e(x, \omega) (n \cdot \omega)}{p(x)p(\omega)}$，$N$ 表示被发射光子的总数。严格意义上来说，通量的定义是不考虑立体角和照明面积的，所以所谓的单个光子的通量实际上是通量的二阶差分 $\Delta^2 \Phi$。在实际实现中，我们在计算通量时并不会除以 $N$，这是因为在 SPPM 中光子数量会随着迭代次数增加而增加，因此我们也将其 $\dfrac{L_e(x, \omega) (n \cdot \omega)}{p(x)p(\omega)}$ 视为一种没有放缩的通量，直到最后再除以 $N$ 得到真正的通量。 ...

本文主要介绍多重重要性采样（Multiple Importance Sampling）及其在光线追踪中的典型应用。 Multiple Importance Sampling Monte Carlo Path Tracing 在 Ray Tracing 中，最核心的技术就是 Monte Carlo Estimation。通过使用 Monte Carlo Estimation，我们可以求解 Rendering Equation。对于 Monte Carlo Estimation 来说，一个合适的采样方法可以极大提升收敛的速度，具体来说，对于以下积分及其 Estimator $$ I = \int_D f(x) \mathrm dx \approx \dfrac{1}{N} \sum_{i = 1}^N \dfrac{f(X_i)}{p(X_i)} $$$X_i$ 的最佳的采样分布应该满足 $p(X_i) \propto f(X_i)$。 然而对于 Rendering Equation 来说，这个条件难以满足，因为其被积函数包含了 cosine-weighted BSDF 和 radiance 两部分因子，后者更是需要递归求解的未知项，显然没有办法进行完美的采样。 $$ L_o(x, \omega_o) = L_e(x, \omega_o) + \int_{\Omega^+} f_s(x, \omega_o, \omega_i) L_i(x, \omega_i) (n \cdot \omega_i) \mathrm d\omega_i $$一般情况下，我们只能选择让采样分布于其中一部分因子的形状近似，也就产生了两种采样——BSDF 采样（包括了余弦项）和光源采样（光源贡献的 radiance 应该比非直接的更大）。 ...

std::any::Any 是 Rust 在运行时进行类型擦除和转换的工具，所有 'static 类型都实现了 Any，因此装箱为 Box<dyn Any> 后可以借助 Any::type_id() 获取 TypeId，还可以通过 dyn Any 的 downcast_*() 等方法再转换回具体类型。 然而问题也出在 dyn Any 的 downcast_*() 方法。这些方法是 dyn Any 的方法，而不是 Any trait 中的方法，所以其他任何 dyn Trait 都不会拥有这些方法，即使有 Trait: Any。另一方面，由于 trait upcasting 直到最近才成为稳定特性，且还没进入 stable 版本，所以依赖语言支持的 trait upcasting 来转换为 dyn Any 对于较早版本的项目并不合适。 因此，本文则通过纯 Rust 语法来扩展 trait object，以实现 Any 的所有功能。这些实现都可以在 better-as-any 找到。 现有解决方案 downcast downcast crate 通过宏来生成代码，直接为指定的 dyn Trait 添加 is()、downcast_*() 方法。这种做法在最终效果上与 dyn Any 完全一样，但是需要使用 impl_downcast!() 宏来实现。我个人则偏好能使用语言特性实现就不使用宏。 as-any 这个 crate 不使用宏实现了功能，其中的 AsAny 可以把任意类型的引用转换为对 dyn Any 的应用，即 trait upcasting。同时其有 Downcast trait 可以把引用向下转型为具体类型的引用。 ...

在对 Rust 错误处理的思考和 anyerr一文中，我介绍了 anyerr 这一个错误处理库，其可以携带上下文信息，且储存上下文的数据结构是可定制的。本文则聚焦 anyerr 是如何实现这样的特性的。 上下文的核心特性 基本结构和表示 在设计之前，首先我们要明确需求。什么样的上下文数据结构是我们所需要的？携带上下文是为了能够记录某些变量所保存的值，我们需要记录变量的名称和其中的值。上下文可以有很多种类，但所有的上下文都可以表示为一个键值映射表。 所以以下是我们对一个上下文储存的基本特性的定义： pub trait AbstractContext: Default + Debug + Send + Sync + 'static { type Key; type Value; type Entry: Entry<Key = Self::Key, Value = Self::Value>; type Iter<'a>: Iter<'a, Entry = Self::Entry> where Self: 'a; fn iter(&self) -> Self::Iter<'_>; } 这样的一个 trait 定义仅仅规定了一个上下文的键值对类型和迭代其中元素的方法，却没有插入或者其他查询的方法。这是因为一个上下文不一定需要真的携带有信息，如果不需要上下文，那么一个不带有任何信息的上下文就可以非常好地适用于这种场景，这也是为什么这个 trait 叫做 AbstractContext。anyerr 针对这样的情况有特殊的优化，这些后面再说。 上下文的元素 AbstractContext::Entry 规定了上下文中每一个元素的类型，其应当实现 Entry trait。以下则是 Entry 的定义： pub trait Entry: Debug + Send + Sync + 'static { type Key: Borrow<Self::KeyBorrowed> + Debug + Send + Sync + 'static; type KeyBorrowed: Debug + Display + Eq + Hash + ?Sized + Send + Sync + 'static; type Value: Borrow<Self::ValueBorrowed> + Debug + Send + Sync + 'static; type ValueBorrowed: Debug + ?Sized + Send + Sync + 'static; fn new<Q, R>(key: Q, value: R) -> Self where Q: Into<Self::Key>, R: Into<Self::Value>; fn key(&self) -> &Self::KeyBorrowed; fn value(&self) -> &Self::ValueBorrowed; } Entry trait 具体规定了键和值的类型以及创建和访问的方法。在 AbstractContext 中，还要将 AbstractContext::Key、AbstractContext::Value 和 Entry::Key、Entry::Value 匹配。 ...

错误处理是 Rust 中核心的一部分，从标准库中的 Result<T, E> 和 Error 到社区的 anyhow、thiserror、color-eyre、snafu 等 crates，可见其重要地位。但是在我看来，这些仅仅是错误处理机制的基础，而不是一个十分完备的框架，同时某些 crate 的设计，要么不能符合实际需要，要么使用起来很麻烦。本文将阐述我对 Rust 错误处理的理解和自己的实践 anyerr。 std 中的基础设施 在讨论我对错误处理的理解之前，有必要先回顾标准库中与错误处理相关的基础设施。 截至本文写作时间，Rust 的最新版本为 1.84.1，接下来将以此版本为基础进行讨论。 错误与结果 标准库中最广为人知的一个类型就是 Result<T, E>，用来表示一个可能成功或失败的结果。这是一个非常精妙的设计，主要体现其可以编码成功或失败中的一者，而不是将失败结果糅合进成功结果的值中。C 广泛采用后一种处理方式，导致 API 的混乱，当然这很大一部分是历史原因。在 Java 等以异常为主要错误处理机制的语言中，这一问题有了很大改善，但这又引入了隐式控制流的问题，Result<T, E> 则又避开了这个问题。所以，Result<T, E> 应该是一个很不错的机制。 尽管 Result<T, E> 中的 E 代表错误，但标准库对其具体应是什么类型没有什么限制。一般情况下，E 是一个实现了 Error trait 的类型，或者是其他可以间接地访问到内部的错误的类型，如 Box<dyn Error>。 错误类型的统一契约 若某类型实现了 Error，那么其就可以以一种标准的形式来被集成的错误处理的框架中。Error 规定了如何显示错误信息（通过 Display trait）和如何溯源错误（通过 <Self as Error>::source()）。 在 Rust 早期，并没有 Error，错误处理是处于一种野蛮生长的状态。直到 Error 的引入，Rust 才可以算是有了一套标准的错误处理机制。 错误的传播 Result<T, E> 虽好，但在深层函数调用中，一次次手动向上传播错误却很麻烦。? 运算符则有效解决了这个问题，实现了把错误方便的提前返回，传播给调用方。 ? 的使用不要求被传播错误类型和接受的错误类型完全相同，只需要有 From 的联系，即如果 E1: From<E2>，那么对 Result<U, E2> 使用 ? 就可以把错误传播为 Result<T, E1>。 ...

在 Linux 下，GUI 外观配置一直是一个复杂的话题。本文试图梳理 Qt 和 GTK 两种 GUI 框架的相关概念，并给出不同情况下的配置方案，实现外观的统一。 本文讨论的 Qt 包括 Qt 5 和 Qt 6，GTK 包括 GTK 2、GTK 3、GTK 4，并且将以 Qt 6 和 GTK 4 为重点。测试的 DE 和 WM 包括 GNOME 4.46、KDE Plamsa 6.1、Hyprland 0.41。 配置组成 基本概念 外观配置一般包括以下几个方面： 主题/Theme：这是一个比较广泛的概念，一般包括了样式、图标和鼠标指针等各配置项在内。 样式/Style：一般指程序窗口、面板、组件的外观。 图标/Icon 指针/Cursor 字体/Font 配色方案/Color Scheme：较细粒度的配置项，诸如主要颜色、强调颜色的配置都属于配置方案。 声音/Sound …… 这是一个比较广泛的定义，具体到各框架，又会产生一定的变化。 GTK GTK 中可直接配置的部分相对较少，主要是： 主题/Theme：主要与一般定义中的样式/Style 对应。 图标/Icon Theme：与一般定义中的图标/Icon 相同。 指针/Cursor Theme：与一般定义中的指针/Cursor 相同。 字体/Font：与一般定义中的字体/Font 相同。 包括 GNOME 在内的基于 GTK 开发的 DE 基本上直接使用上述概念，利用这些 DE 的工具配置外观，基本上就是对 GTK 的配置直接修改。 ...

紧张的考试周过后，终于有时间和朋友玩 Minecraft 了。为了方便进行多人游戏，我和 @whitepaperdog 决定购买一台云主机作为服务器。鉴于 NixOS 强大的 reproducibility 以及我这半年使用 NixOS 的优秀体验，我决定将服务器的系统更换为 NixOS，并在其之上部署 Minecraft 服务。 准备工作 NixOS 安装 这台服务器并不是用我的账号买的，所以我没有办法直接在控制台上传 NixOS 的镜像进行安装。等我拿到 root 密码后，系统就已经是 Ubuntu 了。在此情况下，我选择了使用 NixOS-infect。NixOS-infect 是一个 shell 脚本，其在服务器上安装 Nix，再用 Nix 构建出 NixOS，最后修改 bootloader 配置，添加 NixOS 的启动项并删除其他东西。 使用 NixOS-infect 前需要配置好访问 root 的 SSH 公钥，这是因为 NixOS-infect 并没有提供设置 root 密码的步骤，并且 NixOS 默认情况下将禁用 SSH 通过密码登录 root。NixOS-infect 脚本会将原有的 root 的公钥重新导入到新的 NixOS 里。 由于服务器在国内，所以访问 nixpkgs 的 cache 将会非常慢，在安装 NixOS 之前需要配置好 cache 镜像。编辑脚本，在完成 Nix 的安装后，配置镜像源： infect() { # ... NIX_INSTALL_URL="${NIX_INSTALL_URL:-https://nixos.org/nix/install}" curl -L "${NIX_INSTALL_URL}" | sh -s -- --no-channel-add # 添加以下 3 行 cat << EOF > /etc/nix/nix.conf substituters = https://mirror.sjtu.edu.cn/nix-channels/store https://mirrors.ustc.edu.cn/nix-channels/store https://cache.nixos.org/ EOF # shellcheck disable=SC1090 source ~/.nix-profile/etc/profile.d/nix.sh # ... } 随后就是运行脚本，等待 SSH 断开，安装完成。 ...

最近发现了一个用 Rust 写的 Vim-like 编辑器 Helix，用有强大的性能和各种开箱即用的功能。经过短暂时间的体验，我认为 Helix 已经可以在大部分领域替代 Vim/Neovim/VS Code。 性能 作为一款用 Rust 写的编辑器，Helix 自然拥有优异的性能。得益于其丰富的内置功能，Helix 无需插件就可以完成许多 Vim 只能用插件做到的事，并且还通过 Rust 获得了性能上的优势。现在我的 Neovim 安装有 coc.nvim、vim-visual-multi 等插件，共十个，启动需要延迟近 0.5 秒，虽然已经显著快于 VS Code，但相比 Helix 的小于 0.1 秒，还是稍显逊色。（当然这可能与我现在用的是 Windows 有关） 虽然现在（2023年4月8日）Helix 还没有插件系统，但未来的插件系统大概率会用 WASM 实现，相比 Vim Script 以及 Neovim 用的 Lua 等脚本语言会更快。 编辑体验 整体思路 首先 Helix 和 Vim 一样都是模态编辑器，具有多种模式，最基本的操作思路是一样的，比如都使用 hjkl 进行移动，都使用 i、a 等进行插入，都使用 y，d、p 进行复制删除粘贴。但是 Helix 采用了 selection -> action 模式，比如向右删除 3 个字符需要按 3ld 而不是 d3l，先选择在操作，就我个人而言，这种方式确实更舒适。 另外，Helix 的命令有丰富的提示，而且还可以通过 <space> ? 打开命令面板查找命令，并带有相关键位提示，包括自定义的键位。 ...

项目地址：https://github.com/StarryReverie/brainfuck-interpreter Brainfuck 是什么就不具体介绍了，可以看这里。以下简称 bf。 这个解释器实现总体上是比较简单的，但是相比其他的大多数解释器还是有比较多的不同之处，具体如下： 更多的配置选项 内存的长度与地址范围：可配置为负数 单个内存单元的数据类型 数据溢出处理机制：wrap 或错误 读到 EOF 的处理机制：返回 0、EOF 本身或不改变 优化指令 采用类似编译为字节码的机制 这个项目可以算是学习 Rust 的练手项目，尝试着用了如 clap 这样的 crate。接下来就介绍一些技术细节。 使用方法 具体说明在项目 README. 编译、安装、执行全过程： $ git clone https://github.com/StarryReverie/brainfuck-interpreter.git $ cd brainfuck-interpreter $ cargo install --path ./crates/bf-exec # The program will be installed to ~/.cargo/bin $ bf-exec ./examples/helloworld.bf Hello World! ./examples/helloworld.bf： ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>. 实现原理 目前，项目分为两个 crate：common 与 bf-exec，其中 common 实现了解释器的所有逻辑，而 bf-exec 是 common 的前端，负责处理输入和配置。 common 的模块树如下： complier：解析代码并转换为 IR (Intermediate Representation，中间表示) lexer：词法分析 parser：语法分析并优化，生成 AST SyntaxTree syntax：AST 生成 optimizer：AST 优化 instruction：根据 AST 生成 IR，同时也是最终执行的指令 execution：IR 的执行与相关环境 memory：按照 bf 的内存模型实现的可配置内存 strategy：基于策略模式实现的可配置组件 config：构建 Memory 的配置 stream：bf 的 IO 实现 config：构建 InStream、OutStream 的配置 context：Memory 与 InStream、OutStream 的组合 processor：运行指令，并调用 Context 实现细节 代码优化 同质代码合并 首先最简单的就是这个优化，它是指把相邻的 + 与 -、< 与 > 合并到一起并加上一个重复次数。 ...