关于typescript:前端进阶在-Web-中使用-C我让学妹另眼相看

65次阅读

共计 8614 个字符，预计需要花费 22 分钟才能阅读完成。

这是一个对于矩形排样问题和 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@SegmentFault，一起做大变强！

也欢送点击 LigaAI- 新一代智能研发合作平台，在线申请体验咱们的产品，与咱们交换 :)

正文完
typescript
发表至： typescript
2023-03-20
 0
关于typescript:前端食堂技术周刊第-50-期TypeScript-48Deno-125Terminal-Gif-Maker
关于typescript:typescript-type-分配条件类型
关于typescript:TS中Omit-Pick-Exclude区别关系
Typescript-使用日志