spork build fails on Windows ARM

[rwtolbert]

Trying to build spork on Windows ARM64 using MSVC runs into a couple of problems.

> janet
Janet 1.37.1-local windows/aarch64/msvc - '(doc)' for help
repl:1:>

> janet .\bundle\build.janet
cl.exe /c /std:c11 /utf-8 /nologo /IC:\Users\cohor\AppData\Local\Apps\Janet\C\ /IC:\Users\cohor\AppData\Local\Apps\Janet\Library\ /O2 /MD /DJANET_BUILD_TYPE=develop /I C:\Users\cohor\AppData\Local\Apps\Janet\Library\ src/crc.c /Fobuild/objects\src___crc.c.o
crc.c
link.exe /nologo /DLL /OUT:build/spork/crc.dll build/objects\src___crc.c.o /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\C\ /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\Library\ C:\Users\cohor\AppData\Local\Apps\Janet\C\\janet.lib
   Creating library build\spork\crc.lib and object build\spork\crc.exp
cl.exe /c /std:c11 /utf-8 /nologo /IC:\Users\cohor\AppData\Local\Apps\Janet\C\ /IC:\Users\cohor\AppData\Local\Apps\Janet\Library\ /O2 /MD /DJANET_BUILD_TYPE=develop /I C:\Users\cohor\AppData\Local\Apps\Janet\Library\ src/json.c /Fobuild/objects\src___json.c.o
json.c
link.exe /nologo /DLL /OUT:build/spork/json.dll build/objects\src___json.c.o /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\C\ /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\Library\ C:\Users\cohor\AppData\Local\Apps\Janet\C\\janet.lib
   Creating library build\spork\json.lib and object build\spork\json.exp
cl.exe /c /std:c11 /utf-8 /nologo /IC:\Users\cohor\AppData\Local\Apps\Janet\C\ /IC:\Users\cohor\AppData\Local\Apps\Janet\Library\ /O2 /MD /DJANET_BUILD_TYPE=develop /I C:\Users\cohor\AppData\Local\Apps\Janet\Library\ src/cmath.c /Fobuild/objects\src___cmath.c.o
cmath.c
src/cmath.c(110): error C2440: 'return': cannot convert from 'int' to 'Janet'
error: command failed with non-zero exit code 2
  in os/execute [src/core/os.c] on line 1399

this error occurs in this code, which assumes _MSC_VER uses NAN boxing regardless of platform.

Janet wrap_nan() {
#ifdef NAN
    return janet_wrap_number(NAN);
#elif defined(_MSC_VER)
    return janet_wrap_nan(nan("nan"));
#else
    return janet_wrap_number(0.0 / 0.0);
#endif
}

so as an experiment, let's build a new version of Janet with NAN box ON on ARM64 Windows. Small change in janet.h and rebuild Janet.

/* Use nanboxed values - uses 8 bytes per value instead of 12 or 16.
 * To turn of nanboxing, for debugging purposes or for certain
 * architectures (Nanboxing only tested on x86 and x64), comment out
 * the JANET_NANBOX define.*/

#if defined(_M_ARM64) || defined(_M_ARM) || defined(__aarch64__)
#ifndef _MSC_VER  // don't turn off if on Windows - sorry for the double-negative
#define JANET_NO_NANBOX
#endif
#endif

then use this new Janet to build spork:

> janet .\bundle\build.janet
cl.exe /c /std:c11 /utf-8 /nologo /IC:\Users\cohor\AppData\Local\Apps\Janet\C\ /IC:\Users\cohor\AppData\Local\Apps\Janet\Library\ /O2 /MD /DJANET_BUILD_TYPE=develop /I C:\Users\cohor\AppData\Local\Apps\Janet\Library\ src/cmath.c /Fobuild/objects\src___cmath.c.o
cmath.c
link.exe /nologo /DLL /OUT:build/spork/cmath.dll build/objects\src___cmath.c.o /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\C\ /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\Library\ C:\Users\cohor\AppData\Local\Apps\Janet\C\\janet.lib
   Creating library build\spork\cmath.lib and object build\spork\cmath.exp
src___cmath.c.o : error LNK2019: unresolved external symbol _mul128 referenced in function _mulmod_impl
src___cmath.c.o : error LNK2019: unresolved external symbol _div128 referenced in function _mulmod_impl
build\spork\cmath.dll : fatal error LNK1120: 2 unresolved externals

Ok, this is progress, but we hit this new problem. These two symbols are x86_64 intrinsics, not available on Arm. But cmath.c has some fallback code for _mulmod_impl so let's change the macro to skip the x86_64 intrinsics on Arm.

// need to skip the _mul128/_div128 on ARM Windows
#elif defined(_WIN64) && defined(_MSC_VER) && !defined(_M_ARM64)

#include <intrin.h>
int64_t _mulmod_impl(int64_t a, int64_t b, int64_t m) {
    if (m == 0) return a * b;

    int64_t r;
    int64_t s = _mul128(a, b, &r);
    (void)_div128(r, s, m, &r);
    return (((a ^ b ^ m) < 0) && (r != 0)) ? r + m : r;
}

#else // fall through to here on Windows ARM64

int64_t _mulmod_impl(int64_t a, int64_t b, int64_t m) {
    int64_t res = 0;
    a = _mod_impl(a, m);
    b = _mod_impl(b, m);
    if (a < b) {
        int64_t tmpa = a;
        a = b;
        b = tmpa;
    }
    if (b < 0) b -= m;
    while (b > 0) {
        if ((b & 1) == 1)
            res += (((m - res - a) ^ m) < 0) ? a - m : a;
        a += (((m - a - a) ^ m) < 0) ? a - m : a;
        b >>= 1;
    }
    return res;
}

#endif

with that change in place, spork will now build

❯ janet .\bundle\build.janet
cl.exe /c /std:c11 /utf-8 /nologo /IC:\Users\cohor\AppData\Local\Apps\Janet\C\ /IC:\Users\cohor\AppData\Local\Apps\Janet\Library\ /O2 /MD /DJANET_BUILD_TYPE=develop /I C:\Users\cohor\AppData\Local\Apps\Janet\Library\ src/cmath.c /Fobuild/objects\src___cmath.c.o
cmath.c
link.exe /nologo /DLL /OUT:build/spork/cmath.dll build/objects\src___cmath.c.o /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\C\ /LIBPATH:C:\Users\cohor\AppData\Local\Apps\Janet\Library\ C:\Users\cohor\AppData\Local\Apps\Janet\C\\janet.lib
   Creating library build\spork\cmath.lib and object build\spork\cmath.exp
lib.exe /nologo /OUT:build/spork/cmath.lib build/objects\src___cmath.c.o
done!

But we have a new problem. The math tests hang in an infinite loop. The code _molmod_impl covered by the #else never converges.

This made me wonder about the fallback code on other platforms. As a further experiment, changing the macro to run the fall-back _mulmod_impl on Linux, causes the math tests to hang there as well. So, I think there is something awry with that code, but I don't know enough to understand it.

[sogaiu]

AFAIK, I don't have access to appropriate hardware to make a direct investigation. May be there's some kind of qemu-based solution that could work (though it seems like it could be rather slow)...

I found the following, but may be others know of better resources or approaches?

• https://github.com/raspiduino/waq
• https://www.reddit.com/r/ARMWindows/comments/1gb6m9l/running_win11_arm64_on_x86_via_qemu/
• https://gist.github.com/Vogtinator/293c4f90c5e92838f7e72610725905fd

[rwtolbert]

@sogaiu

I think you can reproduce this on Windows and Linux on x86_64. In cmath.c

If I change the #ifdef conditions (like below) to force the fallback code to run on x86_64 Windows, I get the same hang in the math tests.

#elif defined(_WIN64) && defined(_MSC_VER) && defined(FOO)

On Linux x86_64. Change the first #ifdef

#if defined(__SIZEOF_INT128__) && defined(FOO) 

and the math tests will hang there as well.

[sogaiu]

I don't know enough to understand it.

I don't either (^^;

IIUC, @primo-ppcg wrote nearly all of the code in cmath.c [1]. Perhaps if he sees this issue and he has some time, may be he can give some hints :)

---

[1] Hmm, does the @ construct work for notifying someone when included as part of a link...

[chamaeleon]

Having recently acquired a Snapdragon X Elite laptop, I have found myself running into the same issue. Following in the footsteps of @rwtolbert, I too ended up with the infinite loop as a result of the test suite, with the code hanging in math.janet's, pollard-rho function, when evaluating (mulmod q (- n x) n). Printing out the values used here, I copied the for _mulmod_impl() into a little standalone C program for debugging.

For q=586101, x=915963, y=501852, and n=1530787, I then compared the output of what __int128 versions of modmul computes versus the hanging version, and got 0 for the correct, terminating, value, and 1530787 for the version that hangs.

I then tried to find some good references online for performing the calculation, and ended up at https://stackoverflow.com/questions/20971888/modular-multiplication-of-large-numbers-in-c. I noticed the answer by Kevin Hopps towards the end was very similar to the implementation in spork, but it uses a helper add() function to avoid some issues.

So I put these two functions in instead of the original _mulmod_impl() (the change made in it is only for the _add_impl() calls), and the test suite now passes the math tests (and the others as well).

int64_t _add_impl(int64_t a, int64_t b, int64_t c)
{
    int64_t room = (c - 1) - a;
    if (b <= room) a += b;
    else a  = b - room - 1;
    return a;
}

int64_t _mulmod_impl(int64_t a, int64_t b, int64_t m) {
    int64_t res = 0;
    a = _mod_impl(a, m);
    b = _mod_impl(b, m);
    if (a < b) {
        int64_t tmpa = a;
        a = b;
        b = tmpa;
    }
    if (b < 0) b -= m;
    while (b > 0) {
        if ((b & 1))
            res = _add_impl(res, a, m);
        a = _add_impl(a, a, m);
        b >>= 1;
    }
    return res;
}

I don't know if the performance is very much impacted or not by this change. I also couldn't say with 100% certainty that it will be correct for any given input, as I haven't quite digested the algorithm yet.

Edit: removed an unused variable i I used during debugging

[bakpakin]

@chamaeleon Thanks for the fix, this looks like something we may want to merge. However, really there are two issues here - spork not building correctly on Windows arm, and the bad _mulmod_impl function.

For the nan issue, I think we don't actually need the _MSC_VER check:

Janet wrap_nan() {
#ifdef NAN
    return janet_wrap_number(NAN);
#else
    return janet_wrap_number(0.0 / 0.0);
#endif
}

should work for all platforms we support (this is actually how math/nan is defined more or less).

[chamaeleon]

For NaN,

Janet wrap_nan() {
#ifdef NAN
    return janet_wrap_number(NAN);
#elif defined(_MSC_VER)
    return janet_wrap_number(nan("nan"));
#else
    return janet_wrap_number(0.0 / 0.0);
#endif
}

I used janet_wrap_number() instead of janet_wrap_nan(). I figured it was good enough seeing how there is a nan() in the C library. I have don't have a strong opinion on the matter though.

[chamaeleon]

As for the error when compiling Janet_wrap_nan() without the fix, I'm guessing it is because there was no janet_wrap_nan() function declared in a header or anything, so the C compiler assumed there will be a function with that name returning an int (hence the type mismatch). If such a function was implemented in wrap.c like there is for janet_wrap_nil(), janet_wrap_true(), and janet_wrap_false(), I imagine the error would also have gone away too.

[rwtolbert]

@chamaeleon Thanks for having a look at this. I too tried to find an alternate implementation for that mulmod code but none of my alternates would pass all the test cases.

As for the nan, another alternative is to turn nanboxing on on Windows ARM64 (it is off on all ARM OSs for now) though I'm not sure what other ramifications, pros or cons that might have.

[chamaeleon]

Using the 0/0 version gives a compile error for me.

PS C:\Projects\Janet\spork> cl.exe /c /std:c11 /utf-8 /nologo /IC:\Devtools\Janet\C\ /IC:\Devtools\Janet\Library /O2 /MD /DJANET_BUILD_TYPE=develop /I C:\Devtools\Janet\Library src/cmath.c /Fobuild/objects\src___cmath.c.o
cmath.c
src/cmath.c(120): error C2124: divide or mod by zero

Edit: given the state of cmath.c at the commit as of writing (b7c931f)

[chamaeleon]

The _mulmod_impl() function required for ARM64 isn't used as is, due to not checking whether _M_ARM64 is defined or not like @rwtolbert indicated in the first post.

#elif defined(_WIN64) && defined(_MSC_VER) && !defined(_M_ARM64)
...
#endif