wasmtime wasm trap: integer divide by zero

[guest271314]

Bug description

This appears to be a bug in AssemblyScript

//import "./assemblyscript/std/portable.js";
//import process from "node:process";
// array_nth_permutation
export function array_nth_permutation(len: i32, n: i32): void { //Array<f64>
  let lex = n; // length of the set
  let b: i32[] = []; // copy of the set a.slice()
  for (let x: i32 = 0; x < len; x++) {
    b.push(x);
  }
  const res: i32[] = []; // return value, undefined
  let i: i32 = 1;
  let f: i32 = 1;

  // compute f = factorial(len)
  for (; i <= len; i++) {
    f *= i;
  }

  let fac = f;
  // if the permutation number is within range
  if (n >= 0 && n < f) {
    // start with the empty set, loop for len elements
    // let result_len = 0;
    for (; len > 0; len--) {
      // determine the next element:
      // there are f/len subsets for each possible element,
      f /= len;
      // a simple division gives the leading element index
      i = (n - n % f) / f; // Math.floor(n / f);
      //process.stdout.write(`i: ${i} `);
      // alternately: i = (n - n % f) / f;
      // res[(result_len)++] = b[i];
      // for (let j = i; j < len; j++) {
      //   b[j] = b[j + 1]; // shift elements left
      // }
      res.push(<i32>b.splice(i, 1)[0]);
      // reduce n for the remaining subset:
      // compute the remainder of the above division
      n %= f;
      //process.stdout.write(`n: ${n} `);
      // extract the i-th element from b and push it at the end of res
    }

    let result: string = `[${res}]`;
    /*
    "[";
    for (let x: i32 = 0; x < res.length; x++) {
      let m: string = res[x].toString();
      let i: i32 = 0;
      do {
        result += m[i];
        i++;
      } while (m[i] !== ".");
      if (x < res.length -1) {
        res echo '13 2' | wasmtime --preload javy_quickjs_provider_v3=../plugin.wasm ../nm_javy_permutations.wasm
2 of 6227020799 (0-indexed, factorial 6227020800) => [0,1,2,3,4,5,6,7,8,9,11,10,12]
ult += ",";
      }
    }
    result += "]";
    */
    process.stdout.write(
      `${lex} of ${fac - 1} (0-indexed, factorial ${fac}) => ${result}\n`,
    );

    process.exit(0);
  } else {
    if (n === 0) {
      process.stdout.write(`${n} = 0`);
    }
    process.stdout.write(`${n} >= 0 && ${n} < ${f}: ${n >= 0 && n < f}`);
    process.exit(1);
  }
}

let input: string = "0";
let lex: string = "0";

if (process.argv.length > 1) {
  input = process.argv.at(-2);
  lex = process.argv.at(-1);
} else {
  let stdin = process.stdin;
  let buffer = new ArrayBuffer(64);
  // @ts-ignore
  let n: number = stdin.read(buffer);
  if (n > 0) {
    // @ts-ignore
    let data = String.UTF8.decode(buffer);
    input = data.slice(0, data.indexOf(" "));
    lex = data.slice(data.indexOf(" "), data.length);
  }
}

input = input.trim();
lex = lex.trim();

if (<i32> parseInt(input) < 2 || <i32> parseInt(lex) < 0) {
  process.stdout.write(`Expected n > 2, m >= 0, got ${input}, ${lex}`); // eval(input)
  process.exit(1);
}

array_nth_permutation(<i32> parseInt(input), <i32> parseInt(lex));

Everything works as expected until we get to factorial 13

wasmtime module.wasm 12 2
2 of 479001599 (0-indexed, factorial 479001600) => [0,1,2,3,4,5,6,7,8,10,9,11]

wasmtime module.wasm 13 2
Error: failed to run main module `module.wasm`

Caused by:
    0: failed to invoke command default
    1: error while executing at wasm backtrace:
           0: 0x3683 - <unknown>!<wasm function 131>
           1: 0x3b77 - <unknown>!<wasm function 132>
           2: 0x200d - <unknown>!<wasm function 101>
    2: wasm trap: integer divide by zero

The same algorithm compiled with Bytecode Alliance Javy

// javy build nm_javy_test.js -o nm_javy_test.wasm
// javy build -C dynamic -C plugin=plugin.wasm -o nm_javy_test.wasm nm_javy_test.js
// echo '4 5' | wasmtime nm_javy_test.wasm -
// [119] [4,3,2,1,0]

function main() {
  const stdin = 0;
  const stdout = 1;
  const stderr = 2;

  const decoder = new TextDecoder();
  const encoder = new TextEncoder();

  let offset = 0;

  const message = new Uint8Array(65536);

  function array_nth_permutation(a, n) {
    let lex = n;
    let b = []; // copy of the set a.slice()
    for (let x = 0; x < a.length; x++) {
      b[x] = a[x];
    }
    let len = a.length; // length of the set
    const res = []; // return value, undefined
    let i = 1;
    let f = 1;

    // compute f = factorial(len)
    for (; i <= len; i++) {
      f *= i;
    }
    //console.log(f);
    let fac = f;
    // if the permutation number is within range
    if (n >= 0 && n < f) {
      // start with the empty set, loop for len elements
      //let result_len = 0;
      for (; len > 0; len--) {
        // determine the next element:
        // there are f/len subsets for each possible element,
        f /= len;
        // a simple division gives the leading element index
        i = (n - n % f) / f; // Math.floor(n / f);
        //console.log(i);
        // alternately: i = (n - n % f) / f;
        //res[(result_len)++] = b[i];
        //for (let j = i; j < len; j++) {
        //          b[j] = b[j + 1]; // shift elements left
        //      }
        res.push(b.splice(i, 1)[0]);
        // reduce n for the remaining subset:
        // compute the remainder of the above division
        n %= f;
        // extract the i-th element from b and push it at the end of res
      }
      return `${lex} of ${fac - 1} (0-indexed, factorial ${fac}) => ${
        JSON.stringify(res)
      }\n`;
    } else {
      if (n === 0) {
        return `${JSON.stringify(res)}\n`;
      }
      return `${n} >= 0 && ${n} < ${f}: ${n >= 0 && n < f}\n`;
    }
    //console.log("[" + lex + "]", JSON.stringify(res));
    // return the permutated set or undefined if n is out of range
    // return 0;
  }

  // const input = [0,1,2,3,4], lex = 5;

  while (1) {
    const buffer = new Uint8Array(1);
    const bytesRead = Javy.IO.readSync(stdin, buffer);
    message.set(buffer, offset);
    offset += bytesRead;
    if (bytesRead === 0) {
      break;
    }
  }

  const data = decoder.decode(message.subarray(0, offset));

  const [input, lex] = data.split(" ").map(Math.floor); // JSON.parse(data);
  /*
  if (input >= 2 && lex >= 0) {
    Javy.IO.writeSync(
      stdout,
      encoder.encode(`Expected n > 2, m >= 0`), // eval(input)
    );
    return 1;
  }
  */
  if (input < 2 || lex < 0) {
    //throw new Error(`Expected n > 2, m >= 0, got ${input}, ${lex}`);
    Javy.IO.writeSync(
      stderr,
      encoder.encode(`Expected n > 2, m >= 0, got ${input}, ${lex}\n`), // eval(input)
    );
    return 1;
  } else {
    Javy.IO.writeSync(
      stdout,
      encoder.encode(
        array_nth_permutation([...new Array(input).keys()].map(Number), lex),
      ), // eval(input)
    );
    return 0;
  }
}

main();

 echo '13 2' | wasmtime --preload javy_quickjs_provider_v3=../plugin.wasm ../nm_javy_permutations.wasm
2 of 6227020799 (0-indexed, factorial 6227020800) => [0,1,2,3,4,5,6,7,8,9,11,10,12]

echo '14 2' | wasmtime --preload javy_quickjs_provider_v3=../plugin.wasm ../nm_javy_permutations.wasm
2 of 87178291199 (0-indexed, factorial 87178291200) => [0,1,2,3,4,5,6,7,8,9,10,12,11,13]

The same algorithm compiled to WASM from JavaScript source using Facebook's Static Hermes and WASI-SDK

/**
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

// https://github.com/facebook/hermes/tree/static_h/examples/ffi
"use strict";

// Emulate a module scope, since global scope is unsound.
(function (exports) {
  const c_null = $SHBuiltin.c_null();

  const _getchar = $SHBuiltin.extern_c(
    { include: "stdio.h" },
    function getchar(): c_int {
      throw 0;
    },
  );

  function getchars(): string {
    "use unsafe";
    try {
      let n: number = 50;
      let c: string = String();
      while (--n) {
        let int: number = _getchar();
        if (int === -1) {
          break;
        }
        c += String.fromCodePoint(int);
      }
      return String(c).trim();
    } catch (e) {
      return String(e.message);
    }
  }

  // https://stackoverflow.com/a/34238979
  function array_nth_permutation(a, n) {
    a = Array.from({ length: a }, (_, i) => i);
    let lex = n;
    let b = Array(); // copy of the set a.slice()
    for (let x = 0; x < a.length; x++) {
      b[x] = a[x];
    }
    let len = a.length; // length of the set
    const res = Array(); // return value, undefined
    let i = 1;
    let f = 1;

    // compute f = factorial(len)
    for (; i <= len; i++) {
      f *= i;
    }

    let fac = f;
    // if the permutation number is within range
    if (n >= 0 && n < f) {
      // start with the empty set, loop for len elements
      // let result_len = 0;
      for (; len > 0; len--) {
        // determine the next element:
        // there are f/len subsets for each possible element,
        f /= len;
        // a simple division gives the leading element index
        i = (n - n % f) / f; // Math.floor(n / f);
        // alternately: i = (n - n % f) / f;
        // res[(result_len)++] = b[i];
        // for (let j = i; j < len; j++) {
        //   b[j] = b[j + 1]; // shift elements left
        // }
        res.push(b.splice(i, 1)[0]);
        // reduce n for the remaining subset:
        // compute the remainder of the above division
        n %= f;
        // extract the i-th element from b and push it at the end of res
      }
      return `${lex} of ${fac - 1} (0-indexed, factorial ${fac}) => ${
        JSON.stringify(res)
      }`;
    } else {
      if (n === 0) {
        return `${JSON.stringify(res)}\n`;
      }
      return `${n} >= 0 && ${n} < ${f}: ${n >= 0 && n < f}`;
    }
  }

  let f = getchars();
  //print(f);

  try {
    let [input, lex] = String(f).split(" ").map(Number);
    if (input < 2 || lex < 0) {
      print(`Expected n > 2, m >= 0, got ${input}, ${lex}\n`); // eval(input)
      return 1;
    } else {
      print(
        array_nth_permutation(input, lex),
      );
      return 0;
    }
  } catch (e) {
    print(e);
  }

  // Optionally force some methods to be emitted for debugging.
  // exports.foo = foo;
})({});

echo '13 2' | wasmtime out/fopen.wasm
2 of 6227020799 (0-indexed, factorial 6227020800) => [0,1,2,3,4,5,6,7,8,9,11,10,12]

 echo '14 2' | wasmtime out/fopen.wasm
2 of 87178291199 (0-indexed, factorial 87178291200) => [0,1,2,3,4,5,6,7,8,9,10,12,11,13]

AssemblyScript source compiled to JavaScript with TypeScript tsc, Deno, and/or Bun https://gist.github.com/guest271314/d50e4dd304cf7b3247128e124c619023

echo '13 2' | node --no-warnings node_modules/assemblyscript/std/module.js
2 of 6227020799 (0-indexed, factorial 6227020800) => [0,1,2,3,4,5,6,7,8,9,11,10,12]

echo '14 2' | node --no-warnings node_modules/assemblyscript/std/module2.js
2 of 87178291199 (0-indexed, factorial 87178291200) => [0,1,2,3,4,5,6,7,8,9,10,12,11,13]

Only the AssemblyScript version fails to process factorial 13. That failure winds up showing up in Binaryen wasm2js output from AssemblyScript compiled WASM, first as this

echo '12 2' | node --no-warnings module.js
2 of 49001599 (0-indexed, factorial 49001600) => [0,1,2,3,4,5,6,7,8,10,911]

that 911 should be 9,11.

Then erroring and exiting when input is 13.

I'm thinking it's this part

f /= len;
// a simple division gives the leading element index
i = (n - n % f) / f; // Math.floor(n / f);

What's going on with AssemblyScript here?

Steps to reproduce

Compile the above AssemblyScript to WASM using

node_modules/.bin/asc --exportStart --config ./node_modules/@assemblyscript/wasi-shim/asconfig.json  module.ts -o module.wasm

Pass stdin or arguments to the WASM runtime '13 2'.

Expected result:

2 of 6227020799 (0-indexed, factorial 6227020800) => [0,1,2,3,4,5,6,7,8,9,11,10,12]

What actually happens

wasmtime module.wasm 13 2
Error: failed to run main module `module.wasm`

Caused by:
    0: failed to invoke command default
    1: error while executing at wasm backtrace:
           0: 0x3683 - <unknown>!<wasm function 131>
           1: 0x3b77 - <unknown>!<wasm function 132>
           2: 0x200d - <unknown>!<wasm function 101>
    2: wasm trap: integer divide by zero

AssemblyScript version

0.27.32

[CountBleck]

Try using i64. 13! exceeds the maximum value for a signed 32-bit integer.

[CountBleck]

It would also be nice if you used the same issue instead of creating multiple issues (I count 5 including this one).

[guest271314]

I'm learning AssemblyScript as I go. Not in isolation because I'm compiling WASM to JavaScript, which shows up in the JavaScript output by wasm2js. I don't think of all stress tests at once.

[CountBleck]

Bugs in wasm2js (if you happen to find any) belong to Binaryen.

[guest271314]

I'm just sharing downstream impact.

If you would prefer I don't file issues I can do that, too.

[CountBleck]

I just don't want you to keep closing issues and making new ones, that's all...

Does switching to i64 help things?

[guest271314]

It's organic. My interest in your gear and trying to figure it out should be good enough to field my inquiries and bug reports, as I interpret and encounter them.

My other bug report was because wasm2js from your source code was hanging. We've progressed since then to this.

The output from wasm2js stopped hanging. Nobody said anything about why the WASM was failing at 13! over there.

No. Didn't I change everythingto i64 below?

-o module.wasm
ERROR AS200: Conversion from type 'i64' to 'i32' requires an explicit cast.
    :
 36 │ res.push(<i64>b.splice(i, 1)[0]);
    │                        ~
    └─ in module.ts(36,30)

FAILURE 1 compile error(s)

export function array_nth_permutation(len: i64, n: i64): void { //Array<f64>
  let lex = n; // length of the set
  let b: i64[] = []; // copy of the set a.slice()
  for (let x: i64 = 0; x < len; x++) {
    b.push(x);
  }
  const res: i64[] = []; // return value, undefined
  let i: i64 = 1;
  let f: i64 = 1;

  // compute f = factorial(len)
  for (; i <= len; i++) {
    f *= i;
  }

  let fac = f;
  // if the permutation number is within range
  if (n >= 0 && n < f) {
    // start with the empty set, loop for len elements
    // let result_len = 0;
    for (; len > 0; len--) {
      // determine the next element:
      // there are f/len subsets for each possible element,
      f /= len;
      // a simple division gives the leading element index
      i = (n - n % f) / f; // Math.floor(n / f);
      //process.stdout.write(`i: ${i} `);
      // alternately: i = (n - n % f) / f;
      // res[(result_len)++] = b[i];
      // for (let j = i; j < len; j++) {
      //   b[j] = b[j + 1]; // shift elements left
      // }
      res.push(<i64>b.splice(i, 1)[0]);
      // reduce n for the remaining subset:
      // compute the remainder of the above division
      n %= f;
      //process.stdout.write(`n: ${n} `);
      // extract the i-th element from b and push it at the end of res
    }

    let result: string = `[${res}]`;
    /*
    "[";
    for (let x: i32 = 0; x < res.length; x++) {
      let m: string = res[x].toString();
      let i: i32 = 0;
      do {
        result += m[i];
        i++;
      } while (m[i] !== ".");
      if (x < res.length -1) {
        result += ",";
      }
    }
    result += "]";
    */
    process.stdout.write(
      `${lex} of ${fac - 1} (0-indexed, factorial ${fac}) => ${result}\n`,
    );

    process.exit(0);
  } else {
    if (n === 0) {
      process.stdout.write(`${n} = 0`);
    }
    process.stdout.write(`${n} >= 0 && ${n} < ${f}: ${n >= 0 && n < f}`);
    process.exit(1);
  }
}

let input: string = "0";
let lex: string = "0";

if (process.argv.length > 1) {
  input = process.argv.at(-2);
  lex = process.argv.at(-1);
} else {
  let stdin = process.stdin;
  let buffer = new ArrayBuffer(64);
  // @ts-ignore
  let n: number = stdin.read(buffer);
  if (n > 0) {
    // @ts-ignore
    let data = String.UTF8.decode(buffer);
    input = data.slice(0, data.indexOf(" "));
    lex = data.slice(data.indexOf(" "), data.length);
  }
}

input = input.trim();
lex = lex.trim();

if (<i32> parseInt(input) < 2 || <i32> parseInt(lex) < 0) {
  process.stdout.write(`Expected n > 2, m >= 0, got ${input}, ${lex}`); // eval(input)
  process.exit(1);
}

array_nth_permutation(<i32> parseInt(input), <i32> parseInt(lex));

[CountBleck]

i can be i32 probably...if not, just do the <i32> cast (array indices are expected to be i32s in AS).

[guest271314]

That's it

      res.push(<i64>b.splice(<i32>i, 1)[0]);

wasmtime module.wasm 13 2
2 of 6227020799 (0-indexed, factorial 6227020800) => [0,1,2,3,4,5,6,7,8,9,11,10,12]

echo '14 2' | wasmtime module.wasm
2 of 87178291199 (0-indexed, factorial 87178291200) => [0,1,2,3,4,5,6,7,8,9,10,12,11,13]

[guest271314]

@CountBleck FWIW I figured out how to get the expected output from wasm2js by adjusting AssemblyScript code. Print each i64 individually

    let result: string = "[";
    for (let x: i32 = 0; x < res.length; x++) {
      let m: string = res[x].toString();
      let i: i32 = 0;
      do {
        result += m[i];
        i++;
      } while (m[i] !== ".");
      if (x < res.length -1) {
        result += ",";
      }
    }
    result += "]";

../binaryen/bin/wasm2js module.wasm --llvm-memory-copy-fill-lowering  --llvm-nontrapping-fptoint-lowering --signext-lowering --enable-mutable-globals --enable-bulk-memory  --signext-lowering  --enable-nontrapping-float-to-int --enable-memory64 -o module.js

// import * as wasi_snapshot_preview1 from 'wasi_snapshot_preview1';

  var bufferView;
  var base64ReverseLookup = new Uint8Array(123/*'z'+1*/);
  for (var i = 25; i >= 0; --i) {
    base64ReverseLookup[48+i] = 52+i; // '0-9'
    base64ReverseLookup[65+i] = i; // 'A-Z'
    base64ReverseLookup[97+i] = 26+i; // 'a-z'
  }
  base64ReverseLookup[43] = 62; // '+'
  base64ReverseLookup[47] = 63; // '/'

// ...

 return {
  "array_nth_permutation": legalstub$127, 
  "memory": Object.create(Object.prototype, {
   "grow": {
    "value": __wasm_memory_grow
   }, 
   "buffer": {
    "get": function () {
     return buffer;
    }
    
   }
  }), 
  "_start": $99
 };
}

import WASI from "./wasi.js";
import fs from "node:fs";
let wasi = new WASI();
var memasmFunc = new ArrayBuffer(0);
var retasmFunc = asmFunc({
  "wasi_snapshot_preview1": {
    memory: { buffer: memasmFunc },
    ...wasi.exports,
  }
});

export var array_nth_permutation = retasmFunc.array_nth_permutation;
export var memory = retasmFunc.memory;
export var _start = retasmFunc._start;

wasi.memory = memory;
_start();

echo '15 2' | node  module.js
2 of 107674367999 (0-indexed, factorial 107674368000) => [0,1,2,3,4,5,6,7,8,9,10,11,13,12,14]