技術分享 | 前端進階:如何在 Web 中使用 C++?

語言: CN / TW / HK

這是一個關於矩形排樣問題和 WebAssembly 初體驗的故事,但一切還要從不學無術的小學妹說起……

1. 問題起因

小學妹的課題需要寫一個程式解決矩形排樣(即二維矩形裝箱)問題。

根據給定的一系列矩形,需要將它們打包到指定大小的二維箱子中,且要求任意兩個矩形不能相交或包含。

問:如何排列矩形可使需要的箱子數量最少,且利用率最大?

二維矩陣裝箱.png

這是一個極具現實意義的問題,在工業應用中非常重要,排樣結果與經濟利益密切相關。

同時,這也是一個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

效果如下:

11.gif

詳細的使用方法請參考 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 或者 viteloader 載入 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. Wasmhttps://github.com/ununian/RectangleBinPack-Wasm

3. Demohttps://github.com/ununian/RectangleBinPack-Wasm-Demo


LigaAI 重視開發者文化的維護與構建,也將繼續分享更多技術分享和趣味技術實踐。關注 LigaAI@oschina ,一起做大變強!

也歡迎點選LigaAI-新一代智慧研發協作平臺,線上申請體驗我們的產品。