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-图片菱形渐变

  • 支付宝二维码 支付宝
  • 微信二维码 微信

本文地址: /wasm-palindrome-string.html

版权声明: 本文为原创文章,版权归 逐梦个人博客 所有,欢迎分享本文,转载请保留出处!

相关文章