技术分享 | 前端进阶：如何在 Web 中使用 C++？

这是一个关于矩形排样问题和 WebAssembly 初体验的故事，但一切还要从不学无术的小学妹说起……

1. 问题起因

小学妹的课题需要写一个程序解决矩形排样（即二维矩形装箱）问题。

根据给定的一系列矩形，需要将它们打包到指定大小的二维箱子中，且要求任意两个矩形不能相交或包含。

问：如何排列矩形可使需要的箱子数量最少，且利用率最大？

这是一个极具现实意义的问题，在工业应用中非常重要，排样结果与经济利益密切相关。

同时，这也是一个NP-Hard问题——既无法通过一个简单公式计算，也不可能将所有情况枚举（超级计算机也算不过来）。

2. 解决思路

小学妹不学无术，而我对算法一窍不通，因此只好借前人经验遮荫避凉。历经重重曲折，终于找到一个 RectangleBinPack 库。它提供了一篇介绍二维矩形装箱问题的各种算法的文章，以及各种算法的具体实现。

对算法感兴趣的伙伴可以自行获取 Wasm 仓库中的《算法介绍》文件了解。

Wasm 仓库传送器：https://github.com/ununian/RectangleBinPack-Wasm

目前了解到，解决二维矩形装箱问题有 4 种算法，分别是：货架算法、断头台算法、最大矩形算法、天际线算法，每个算法都有一些策略选项。

小课题不用宰牛刀，我将问题简化，在此只考虑一个箱子的情况。

3.方案选择

该库是用 C++ 写的，但是我对 C++ 并不熟悉，所以需要用我所熟悉的语言使用。在其他语言中使用 C++ 有两种方案：

第一，直接改写成对应语言，适用于简单的库。虽然这个库很适合直接改写，但却无法（在学妹面前）展现我的高超水平❌

第二，将 C++ 库编译成静态库，再通过跨语言调用机制直接调用。这一看就是会吸引崇拜目光的高端玩法，I WANT YOU!✅

那么，要在哪个语言中使用这个库呢？

第一个想到的是 C#，毕竟在 C# 中调用 C++ 是很常见的操作，也有成熟的 Binding 工具（如 Swig）；而且之前也做过这样的尝试，整体准备工作量也会少一点。但使用 C# 有两个问题:

• 使用过程麻烦。毕竟是桌面程序，涉及分发、安装、兼容性等。

• 编译结果不跨平台。虽然 C++ 和 C# 本身都能跨平台，但需要针对每个平台都编译一次，而且 C# 的 GUI 部分跨平台写起来有点麻烦……

紧接着，我想到了 WebAssembly——一个可以完美解决上述问题的方案，既不用担心跨平台，又能直接使用前端技术完成 GUI 部分。方便又高端，还能在小学妹面前装~~（消音）~~，简直非它莫属。

4. 具体实现

4.1 环境需求

最好使用 Linux 环境，可以避免许多奇怪的问题；如果是 Windows，可以试试 WSL。

安装 Emscripten。具体请参考 Download and install - Emscripten 2.0.27 (dev) documentation

还需要 Node 以及网页开发相关的工具。

4.2 项目结构

. ├── XXXX.cpp // 算法本身的 cpp 文件 ├── XXXX.h // 算法本身的头文件 ├── Warp.cc // Warp文件，其中描述了需要导出的类和函数、枚举等 ├── compile.sh // 编译脚本 ├── package.json // package.json 文件，方便发布到 npm 仓库 

4.3 Warp 文件的编写

在 Warp 文件中显式地告诉 Emscripten 需要导出哪些类和函数（这个步骤称为 Binding），让 Emscripten 生成相应的 wasm 代码和 warp 代码，以便在 Web 环境中使用。

本项目的 Warp 文件是：

#include "Rect.cpp" // ... include<xxx.cpp> 引用各个算法的 cpp 文件 #include "emscripten/bind.h" // Emscripten Binding 需要的头文件 using namespace emscripten; // Emscripten Binding 的命名空间 using namespace std; // C++ 标准库命名空间 ，主要是为了使用 vector（可以理解为 C++ 中的可变长度数组） using namespace rbp; // 这个算法库的命名空间 RectangleBinPack EMSCRIPTEN_BINDINGS(c) // 表示我们开始编写 Emscripten 的 Binding { // 下面只要是字符串里面的值都是在 wasm 里面的名字，可以自己取，不要求和 C++ 中的一样。 // 导出 Rect 和 RectSize 的 vector register_vector<Rect>("VectorRect"); register_vector<RectSize>("VectorRectSize"); // Rect.cpp class_<RectSize>("RectSize") // 导出 RectSize 类，他包括 .constructor<>() // 一个没有参数的构造函数 .constructor<int, int>() // 一个有 2 个参数的构造函数，参数的类型分别是 int 和 int .property("width", &RectSize::width) // 一个实例字段 width，对应的地址是 RectSize 的 width .property("height", &RectSize::height); // ... emscripten::function("IsContainedIn", &IsContainedIn); // 导出了一个全局的函数 // SkylineBinPack.cpp // 导出一个叫做 SkylineBinPack_LevelChoiceHeuristic 的枚举， // 他有 2 个值 LevelBottomLeft、LevelMinWasteFit enum_<SkylineBinPack::LevelChoiceHeuristic>("SkylineBinPack_LevelChoiceHeuristic") .value("LevelBottomLeft", SkylineBinPack::LevelChoiceHeuristic::LevelBottomLeft) .value("LevelMinWasteFit", SkylineBinPack::LevelChoiceHeuristic::LevelMinWasteFit); class_<SkylineBinPack>("SkylineBinPack") .constructor<>() .constructor<int, int, bool>() .function("Init", &SkylineBinPack::Init) // 一个实例函数 Init // 一个实例函数 Insert_Range，对应的是 Insert 函数的某个重载 .function("Insert_Range",select_overload<void(vector<RectSize> &, vector<Rect> &, SkylineBinPack::LevelChoiceHeuristic)>(&SkylineBinPack::Insert)) .function("Insert_Single",select_overload<Rect(int, int, SkylineBinPack::LevelChoiceHeuristic)>(&SkylineBinPack::Insert)) .function("Occupancy", &SkylineBinPack::Occupancy); } 

Warp 文件的文件名和文件中字符串的具体值都是在 wasm 里的名字，可以自定义，不要求与 C++ 中的一样。

需要注意，这里直接引入的是 cpp 文件，不是头文件。下面说几个重要部分的处理。

4.3.1 Vector 的处理

vector 是 C++ 标准库提供的一个数据结构，是可以动态改变长度的数组。本项目主要用来传递待排版的 RectSize 数组和接收计算结果的 Rect 数组。

Emscripten 贴心地提供了 vector 自动绑定方法 register_vector，只需传入 vector 的元素类型和导出名字即可。

4.3.2 枚举的处理

JS 中没有枚举概念，所以在 JS 使用时需要用 Object 的形式。绑定也很简单，使用 enum_ 指定名称、类型和对应的值就行。

4.3.3 函数重载的处理

JS 中没有函数重载的概念，因此导出重载函数需要指定不同的名称，并使用 select_overload 函数找到对应的函数（指定函数的返回值、参数类型即可，没有返回值就是 void）。

顺带一提，如果有多个构造函数也需要指定构造函数的参数类型（构造函数不能指定名称和返回值）。

4.4 编译 Wasm

接下来，将写好的 Warp 文件编译成 Wasm，编译脚本如下：

emcc --bind -Oz Warp.cc -o dist/Warp.js \ -s WASM=1 \ -s MODULARIZE=1 

• --bind 表示需要使用 Embind 的绑定功能。

• -Oz 表示优化等级，有O0、O1、O2 等，其中 Oz 表示优化等级最高。此处我们无需调试 Wasm，选 Oz 就行。

• -o 用于指定输出文件。如果指定的文件后缀名是 js，就会生成 wasm 和相应的 js warp 文件（包含一些胶水代码，便于我们使用 wasm）。当然我们也可以指定 html 生成一个 demo 网页；或指定 wasm 只生成 wasm 文件。

• -s WASM=1 表示编译到 wasm 。如果值为 0 会编译到 asm.js，值为 2 就同时编译成两者。

• -s MODULARIZE=1 表示生成的 js 文件会导出一个可以传参工厂函数（后续会看到），否则会直接赋值在 window 对象上。

值得一提的是，-s SINGLE_FILE=1 可以用 base64 的方式将 wasm 嵌入到 warpjs 文件中，使用时只需要引用 js 文件就行。

4.5 生成对应的 TypeScript 描述文件

工具地址：https://github.com/ted537/tsembind

生成 TypeScript 的描述文件在工程使用中非常重要，否则别人根本不知道怎么用（还能减少写文档的工作量），但是目前还没有十全十美的解决方案。

我选用的工具通过读取 wasm 文件分析里面的导出，因此无法获取函数的形参名字；另外，生成的描述文件还需要小小的「后期加工」：

直接运行 tsembind ./dist/Warp.js > ./dist/Warp.d.ts ，修改最下面导出的部分，别忘了添加 @types/emscripten。

export interface CustomEmbindModule { // ... } declare function factory(): Promise<CustomEmbindModule>; export default factory; // =========> export interface RectangleBinPackModule extends EmscriptenModule { // ... } declare const factory: EmscriptenModuleFactory<RectangleBinPackModule>; export default factory; 

4.6 使用 Wasm

效果如下：

详细的使用方法请参考 Demo 仓库的代码，下面补充一些注意事项。

import type { RectangleBinPackModule as PackModule } from 'rectanglebinpack-wasm' // PackWasmInit 就是上面那个工厂函数 import PackWasmInit from 'rectanglebinpack-wasm'; // 我们需要获取 wasm 文件的路径。我们不需要用打包器的 wasm loader， // 只需要这个wasm文件的 url 就行。这里是 vite 的写法，webpack 应该是 file-loader import PackWasm from 'rectanglebinpack-wasm/dist/Warp.wasm?url' // 方便获取枚举的值，主要是用来规避 ts 的类型检查 const toEnumValue = (enumObj: any, value: any) => enumObj[value] export class WasmPackService implements IPackService { private wasm?: PackModule; constructor() { PackWasmInit({ // 这里非常重要，我们需要告诉工厂方法 wasm 文件的位置在哪， // 如果不写，它会去网页的根目录下查找，一般情况下我们不希望这样 locateFile: (url) => url.endsWith('.wasm') ? PackWasm : url }).then(wasm => { this.wasm = wasm; // 初始化完成后，就能获取到 wasm 模块的实例了 }) } public async pack( source: SourcePanelItem[], // width height 这里因为只考虑 1 个箱子的情况，所以这里肯定只有 1 个数据 target: TargetPanelItem[], // width height count algorithms: Algorithms, // 算法 setting: Record<string, boolean | string> // 算法设置 ) { // ... const m = this.wasm; // 首先我们创建一个 RectSize 的 vector，然后把我们需要排版的小矩形都放进去 const targetSizes = new m.VectorRectSize(); target .flatMap(t => range(0, Math.max(t.count, 0)) .map(_ => new m.RectSize(t.width, t.height))) .forEach((i) => targetSizes.push_back(i)); // ... let resultRects = new m.VectorRect(); // 创建一个用来接收结果的 Rect 的 vector switch (algorithms) { // ... case "Skyline": // 调用天际线算法类的构造函数，并传递一些设置，创建一个算法对象 const skyline = new m.SkylineBinPack(sourceWidth, sourceHeight, setting['UseWasteMap'] as boolean); // 调用批量添加函数，函数内部会把结果添加到 resultRects 里面 skyline.Insert_Range( targetSizes, resultRects, toEnumValue(m.SkylineBinPack_LevelChoiceHeuristic, setting['LevelChoiceHeuristic']) ); // 重要：手动释放 skyline 对象。因为 wasm 需要我们手动管理内存， // 所以创建了对象后一定要回收，不存在自动垃圾回收。 skyline.delete(); break; } const result: Rect[] = [] for (let i = 0; i < resultRects.size(); i++) { const item = resultRects.get(i); result.push({ x: item.x, y: item.y, width: item.width, height: item.height }) } // 获取结果后释放掉 targetSizes、resultRects targetSizes.delete(); resultRects.delete(); return { result } } } 

4.6.1 内存管理

Wasm 与 JS 相比最大的区别是对象内存需要手动创建（new 函数）和释放（delete 函数），所以要注意 new 和 delete 的成对使用。

如果 vector 内存的不是指针，则会自动调用析构函数。

4.6.2 指定 wasm 文件的 Url

如果不指定 wasm 文件的 Url，那么 warp 文件会从网站根目录 /xx.wasm 加载。通常我们不希望这样，因此需要在 wasm 加载时通过 locateFile 函数指定 Wasm 文件的 Url。

建议不要通过 webpack 或者 vite 的 loader 加载 wasm，那样会自动转换成 wasm 模块。只获取 wasm 文件的 url，可以在 vite 中的实在资源名后加上 ?url 或者在 webpack 中加上 !file-loader。

5.总结

本项目涉及的内容和知识还是蛮多的，包括 C++、编译器、WebAssembly 、loader等。完成过程也踩了不少坑，主要是缺乏可用度高的相关资料——有些要么特别简单，只是导出一个全局函数，要么就很复杂，如 ffmpeg 的 wasm 版本。

之前一直想学习 WebAssembly，这次也算是借着难得的机会，简单地了解了从编译到使用的全过程。最后的完成效果也很不错，具有一定的实际运用价值，当然小学妹也很满意:)

后续可以改进的空间主要有两点:

• 手动写 warp 文件比较麻烦，而且大都是重复的体力劳动。如果能写一个工具，通过分析 C++ 代码，自动生成 warp 文件和 Typescript 定义，或许可以节省很多工作量；具体实现可以参考 Swig 的做法。
• 之前见过通过 Scope 实现半自动内存管理，或许也可以加进内存管理中使用。

6.彩蛋 ：C# 的做法

6.1 编写描述文件 Warp.idl

%module RectangleBinPack %{ #include "Rect.h" #include "GuillotineBinPack.h" #include "SkylineBinPack.h" #include "ShelfNextFitBinPack.h" #include "ShelfBinPack.h" #include "MaxRectsBinPack.h" %} %include <std_vector.i> %template(vector_Rect) std::vector<rbp::Rect>; %template(vector_RectSize) std::vector<rbp::RectSize>; %include "Rect.h" %include "GuillotineBinPack.h" %include "SkylineBinPack.h" %include "ShelfNextFitBinPack.h" %include "ShelfBinPack.h" %include "MaxRectsBinPack.h" 

确实比 Emscripten 方便很多，毕竟更加成熟。再调用

swig -c++ -csharp Warp.idl 

这一步会生成很多 cs 文件（C# 的源文件）和一个 warp.cxx 文件。

6.2 编译 Dll

幸运的是，RectangleBinPack 自带了 VisualStudio 的工程文件 RectangleBinPack.sln 。打开后将生成的 warp.cxx 文件加入工程，build 一个 x64 的版本即可。

6.3 使用

创建一个 C# GUI 项目，将步骤 6.1 生成的 cs 文件和步骤 6.2 生成的 Dll 复制到目录下（Dll 需要选择较新则复制）。

下面是部分重要代码：

 public (double, List<Rect>) PackImplement(PackRequestDto dto) { // ... var targets = new vector_RectSize(dto.Target.SelectMany(target => Enumerable.Range(1, target.Count).Select(_ => new RectSize {width = target.Width, height = target.Height}))); var resultRects = new vector_Rect(); // ... switch (dto.Algorithms) { case PackAlgorithms.Skyline: var skylineBin = new SkylineBinPack(sourceWidth, sourceHeight, dto.SkylineSetting.UseWasteMap); skylineBin.Insert(targets, resultRects, dto.SkylineSetting.LevelChoiceHeuristic); break; // ... } return (occupancy, resultRects.ToList()); } 

可以看出，C# 和 JS 在调用阶段都差不多，只是 swig 更为贴心地处理了内存管理部分。

7. 附录

本文所提到代码资源：

1. C++库：https://github.com/juj/RectangleBinPack

2. Wasm：https://github.com/ununian/RectangleBinPack-Wasm

3. Demo：https://github.com/ununian/RectangleBinPack-Wasm-Demo

---

LigaAI 重视开发者文化的维护与构建，也将继续分享更多技术分享和趣味技术实践。关注 LigaAI@oschina ，一起做大变强！

也欢迎点击LigaAI-新一代智能研发协作平台，在线申请体验我们的产品。