时间戳

首页 > 解决方案 > JavaScript 数组到 WebAssembly

javascript - JavaScript 数组到 WebAssembly

问题描述

我目前正在尝试实现 JavaScript 数组的二维 FFT。尽管在 JS 中是可行的，但矩阵通常足够大（例如，3000x4000），这使得它有点慢。我想过在 C 中获得 2D FFT 并使用 WebAssembly 来加速它。

2D FFT 实现来自http://paulbourke.net/miscellaneous/dft/。我做了一些修改，以在不同的指针中有实数和虚数。我在这里粘贴代码：

/*-------------------------------------------------------------------------
Perform a 2D FFT inplace given a complex 2D array
The direction dir, 1 for forward, -1 for reverse
The size of the array (nx,ny)
*/
#include <stdlib.h>
#include <math.h>


/* This computes an in-place complex-to-complex FFT */
int FFT(int dir,int m, double *x,double *y)
{
  long nn,i,i1,j,k,i2,l,l1,l2;
  double c1,c2,tx,ty,t1,t2,u1,u2,z;
  
  /* Calculate the number of points */
  nn = 1;
  for (i=0;i<m;i++)
  nn *= 2;
  
  /* Do the bit reversal */
  i2 = nn >> 1;
  j = 0;
  for (i=0;i<nn-1;i++) {
    if (i < j) {
      tx = x[i];
      ty = y[i];
      x[i] = x[j];
      y[i] = y[j];
      x[j] = tx;
      y[j] = ty;
    }
    k = i2;
    while (k <= j) {
      j -= k;
      k >>= 1;
    }
    j += k;
  }
  
  /* Compute the FFT */
  c1 = -1.0;
  c2 = 0.0;
  l2 = 1;
  for (l=0;l<m;l++) {
    l1 = l2;
    l2 <<= 1;
    u1 = 1.0;
    u2 = 0.0;
    for (j=0;j<l1;j++) {
      for (i=j;i<nn;i+=l2) {
        i1 = i + l1;
        t1 = u1 * x[i1] - u2 * y[i1];
        t2 = u1 * y[i1] + u2 * x[i1];
        x[i1] = x[i] - t1;
        y[i1] = y[i] - t2;
        x[i] += t1;
        y[i] += t2;
      }
      z =  u1 * c1 - u2 * c2;
      u2 = u1 * c2 + u2 * c1;
      u1 = z;
    }
    c2 = sqrt((1.0 - c1) / 2.0);
    if (dir == 1)
    c2 = -c2;
    c1 = sqrt((1.0 + c1) / 2.0);
  }
  
  /* Scaling for forward transform */
  if (dir == 1) {
    for (i=0;i<nn;i++) {
      x[i] /= (double)nn;
      y[i] /= (double)nn;
    }
  }
  
  return 0;
}

int FFT2D(double **c_real, double **c_imag, int nx, int ny, int dir)
{
  int i,j,m;
  double *real,*imag;
  
  /* Transform the rows */
  real = (double *)malloc(nx * sizeof(double));
  imag = (double *)malloc(nx * sizeof(double));
  m = log(nx)/log(2);
  for (j=0;j<ny;j++) {
    for (i=0;i<nx;i++) {
      real[i] = c_real[j][i];
      imag[i] = c_imag[j][i];
    }
    FFT(dir,m,real,imag);
    for (i=0;i<nx;i++) {
      c_real[j][i] = real[i];
      c_imag[j][i] = imag[i];
    }
  }
  free(real);
  free(imag);
  
  /* Transform the columns */
  real = (double *)malloc(ny * sizeof(double));
  imag = (double *)malloc(ny * sizeof(double));
  m = log(ny)/log(2);
  for (i=0;i<nx;i++) {
    for (j=0;j<ny;j++) {
      real[j] = c_real[j][i];
      imag[j] = c_imag[j][i];
    }
    FFT(dir,m,real,imag);
    for (j=0;j<ny;j++) {
      c_real[j][i] = real[j];
      c_imag[j][i] = imag[j];
    }
  }
  free(real);
  free(imag);
  return 0;
}

int HL_2DFFT(double **real, double **imag, double **real_ptr, double **imag_ptr, int nx, int ny, int nx_pw2, int ny_pw2){
  int i, j, diff_nx, diff_ny;
  
  diff_nx = nx_pw2 - nx;
  diff_ny = ny_pw2 - ny;
  
  // copy matrix and expand to power of 2.
  for (i = diff_ny/2; i < ny; ++i) {
    for (j = 0; j < nx_pw2; ++j) {
      if(j<diff_nx/2){
        real_ptr[i][j] = real[i-(diff_ny/2)][0];
        imag_ptr[i][j] = imag[i-(diff_ny/2)][0];
      }
      else if(j>(diff_nx/2 - 1) && j<nx){
        real_ptr[i][j] = real[i-(diff_ny/2)][j-(diff_nx/2)];
        imag_ptr[i][j] = imag[i-(diff_ny/2)][j-(diff_ny/2)];
      } else{
        real_ptr[i][j] = real[i-(diff_ny/2)][nx-1];
        imag_ptr[i][j] = imag[i-(diff_ny/2)][nx-1];
      }
    }
  };
  // Top padding
  for(i=0; i<diff_ny/2;++i){
    for (j = 0; j < nx_pw2; ++j) {
      real_ptr[i][j] = real_ptr[diff_ny/2][j];
      imag_ptr[i][j] = imag_ptr[diff_ny/2][j];
    };
  };
  // Bottom padding
  for(i=ny; i<ny_pw2;++i){
    for (j = 0; j < nx_pw2; ++j) {
      real_ptr[i][j] = real_ptr[ny-1][j];
      imag_ptr[i][j] = imag_ptr[ny-1][j];
    };
  };
  FFT2D(real_ptr, imag_ptr, nx_pw2, ny_pw2, 1);
  
  return 0;
}

当我在 C 中传递二维数组的指针时，这些函数可以很好地使用 Emscripten 编译并工作。我现在的问题是，虽然我已经看到了如何将 JS 数组（1D）传递给 WebAssembly 中的指针的示例，并制作了它有效，我不确定如何为数组数组（或二维数组）执行此操作。我认为它必须作为 C 函数转换为指针指针，但我不确定如何在 JS 端执行此操作。我尝试使用https://github.com/frederikhermans/js-kiss-fft2中的 _malloc 和 _free 函数为数组分配内存。我粘贴功能：

/** Create a heap array from the array ar. */
function allocFromArray(ar) {
  /* Allocate */
  var nbytes = ar.length * ar.BYTES_PER_ELEMENT;
  var heapArray = alloc(nbytes);
  /* Copy */
  heapArray.set(new Uint8Array(ar.buffer));
  return heapArray;
};
/** Allocate a heap array to be passed to a compiled function. */
function alloc(nbytes) {
  var ptr = Module._malloc(nbytes);
  return new Uint8Array(Module.HEAPU8.buffer, ptr, nbytes);
};
/** Free a heap array. */
function free(heapArray) {
  Module._free(heapArray.byteOffset);
};

function hl_2dfft(data){
  let nx = data[0].length;
  let ny = data.length;
  let nx_pw2 = Math.pow(2, Math.ceil(Math.log2(nx)));
  let ny_pw2 = Math.pow(2, Math.ceil(Math.log2(ny)));
  let heap_real = allocFromArray(data.map(x => allocFromArray(x)));
  let heap_imag = allocFromArray(new Array(ny).map(x => allocFromArray(new Array(nx))));
  let heap_spectrum_real = allocFromArray(new Array(ny_pw2).map(x => allocFromArray(new Array(nx_pw2))));
  let heap_spectrum_imag = allocFromArray(new Array(ny_pw2).map(x => allocFromArray(new Array(nx_pw2))));
  _HL_2DFFT(heap_real.byteOffset, heap_imag.byteOffset, heap_spectrum_real.byteOffset, heap_spectrum_real.byteOffset, nx, ny, nx_pw2, ny_pw2);
}

作为可变数据，JS中的数组数组。hl_2dfft 函数返回错误消息： 未捕获的 RuntimeError: memory access out of bounds

任何帮助将非常感激！

标签： javascriptcpointerswebassemblyemscripten

解决方案

对于任何感兴趣的人，我找不到任何与如何将指针指针传递给 WASM 相关的内容，而且我可以尝试的任何东西到目前为止都不起作用。目前，我已经实现了 0__ 给出的解决方案，即展平 JS 数组（使用下面的展平函数）并将单个指针传递给 WASM。

const flatten = function(arr, result = []) {
   for (let i = 0, length = arr.length; i < length; i++) {
      const value = arr[i];
      if (Array.isArray(value)) {
         flatten(value, result)
      } else {
         result.push(value)
      }
   };
return result;
};

如果您将大型数组存储为 JS 中的数组数组，这会带来一些不便，即需要花费一些时间来线性化大型数组，但是在 JS 端创建一个指针指针似乎并非易事。如果有人知道解决方法，那仍然会很棒。

推荐阅读