Wasm实例开发002-最长回文字符串-逐梦个人博客

在上一篇文章《Wasm实例开发001-斐波那契数列》我们介绍了wasm开发环境的准备以及如何使用C语言开发计算斐波那契数列的wasm应用，本文我们将介绍如何使用C语言计算最长回文字符串。

一、什么是回文字符串

回文字符串指的是这样一类字符串，从左到右读和从右到左读是完全一样的，比如“aba”，从左往右读是“aba”，从右往左读也是“aba”。

二、C程序编写

char* longestPalindrome(const char *str){
    bool dp[100][100];
    int i,j,len;
    int longest = 1;
    int tmp;
    int n = strlen(str);
    char a[n];
    for(i = 0; i < n; i++)
    {
        dp[i][i] = 1;
        if(str[i] == str[i + 1])
        {
            dp[i][i + 1] = 1;
            longest = 2;
            strncpy(a,str + i,2);
        }
    }
    for(len = 3; len <= n; len++)
    {
        for(i = 0; i <= n - len; i++)
        {
            j = i + len - 1;
            if(str[i] == str[j])
            {
                dp[i][j] = dp[i + 1][j - 1];
                if(dp[i][j] == 1)
                {
                    tmp = j - i + 1;
                    if(longest < tmp)
                    {
                        longest = tmp;
                        strncpy(a,str + i,tmp);
                    }
                }
            }
            else
                dp[i][j] = 0;
        }
    }
    printf("%d\n",longest);
    char *s = a;       
    return s;
}

三、WebAssembly应用编译

通过Emscripten工具链，我们可以使用以下命令将longestPalindrome.c编译为Wasm应用，命令如下：

emcc -Oz -o longestPalindrome.js -s EXPORTED_FUNCTIONS='["_longestPalindrome"]' -s EXPORTED_RUNTIME_METHODS='["ccall", "cwrap"]' longestPalindrome.c

四、使用js调用wasm应用

我们新建一个html文件用于编写调用wasm应用的代码，代码如下：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>回文字符串计算demo</title>
</head>
<body>
    <p>
        请输入字符串：<textarea id="inputTxt" cols="30" rows="10"></textarea>
    </p>
    <p>
        <button id="btn">计算回文字符串</button>
    </p>
    <p>
        结果：<span id="ret"></span>
    </p>
    <script src="longestPalindrome.js"></script>
    <script>
        btn.onclick = () => {
            const str = ccall('longestPalindrome', 'string', ['string'], [inputTxt.value]);
            // const str = cwrap('longestPalindrome', 'string', ['string'])(inputTxt.value);
            ret.innerText = str;
        }
</script>
</body>
</html>

和上一篇文章不一样的是，这里我们使用了ccall/cwrap来调用wasm应用导出的方法，而不是直接使用_longestPalindrome，对于wasm应用直接导出的方法，只支持数字类型的交换，并不支持其他类型数据的交换，比如需要传递非数字类型数据给wasm导出的函数，我们需要做以下步骤：

①、使用Module._malloc在Module堆中分配内存，获取地址ptr；

②、将字符串/数组等数据拷入内存的ptr处；

③、将ptr作为参数，调用C函数进行处理；

④、使用Module._free释放ptr。

可以看出光一个调用过程就已经如此繁琐了，当非数字类型参数个数较多时，js侧的调用代码会急剧膨胀。为了简化调用过程，Emscripten提供了ccall/cwrap封装函数。

我们通过ccall/cwrap调用wasm导出的函数，得到结果并回显即可。

五、结语

虽然ccall/cwrap可以简化非数字类型参数的交换，但这种便利性是有代价的：当输入参数类型为string/array时，ccall/cwrap在C环境的栈上分配了相应的空间，并将数据拷入了其中，然后调用相应的导出函数。相对于堆来说，栈空间是很稀缺的资源，因此使用ccall/cwrap时需要格外注意传入的字符串/数组的大小，避免爆栈。

系列文章导航：

第1节： Wasm实例开发001-斐波那契数列

第3节： wasm实例开发003-简单数据的加密解密

第4节： wasm实例开发004-矩阵乘法

第5节： wasm实例开发005-图像高斯模糊

第6节： wasm实例开发006-证件照换底色

第7节： wasm实例开发007-图片菱形渐变