search

jameysharp / corrode

C to Rust translator
GNU General Public License v2.0
2.16k stars 116 forks source link

Complex numbers and complex.h are not handled #56

Open harpocrates opened 8 years ago

harpocrates commented 8 years ago

As far as I can tell, there are only two things stopping us from compiling anything that includes <complex.h> (section 7.3).

For the first problem, I think we should translate using num_complex::Complex. That works especially nicely since the aforementioned struct is parametrized over the type of the components, so we can easily bundle together all the types of complex numbers: double complex, float complex, long double complex etc. In terms of code in corrode, we'd be extending baseTypeOf to support CComplexType.

Furthermore, almost all the required functions in <complex.h> match up to something in num_complex::Complex (and they have the same branch cuts 😅), with three easily circumvented exceptions: cpow, csqrt, and cproj.

However, I'm not sure how we link up these implementations to the extern declarations in <complex.h>, and that seems like a more general problem we should solve...

Is there some list of builtin functions for which implementations are automatically linked? Aren't there conflicts if functions of the same names are defined in a program (and what about if the builtin function is only in scope after an include - like cabs)? Maybe someone with more C experience can weigh in...

harpocrates commented 8 years ago

Couple edits to make. When I started looking at this initially, I must've been looking at an old version of Rust's Complex. Actually, cpow and csqrt do have equivalents. Only cproj doesn't have a Rust counterpart. Just for completeness, from section 7.3.9.4

Description

  1. The cproj functions compute a projection of z onto the Riemann sphere: z projects to z except that all complex infinities (even those with one infinite part and one NaN part) project to positive infinity on the real axis. If z has an infinite part, then cproj(z) is equivalent to
          INFINITY + I * copysign(0.0, cimag(z))

Returns

  1. The cproj functions return the value of the projection onto the Riemann sphere.

Also, to make this interesting, we should be able to parse complex literals. GCC preprocesses literals like double complex c = 1.0 + 2.5 * I into double _Complex c = 1.0 + 2.5 * (__extension__ 1.0iF) (which is a GCC specific complex-literal extension).

jameysharp commented 8 years ago

I think the key trick is to ensure that the Rust representation of complex numbers is ABI-compatible with the native C toolchain's representation when used through FFI. (Which strikes me as non-trivial!) This is necessary for translating the C library itself (such as musl libc), and it's also necessary if you're trying to use project-local C code together with your newly-Corroded Rust.

If you can ensure that you can pass complex numbers from Rust to extern C functions, and also that C can pass complex numbers to extern/no_mangle Rust functions... then you don't need to recognize library calls or translate them to Rust library equivalents, because the current strategy of setting up FFI calls to the C library implementation of the function will just work. This is just like any other library call; we don't translate printf to print!, for example.

Now, I'd love to see a tool that does recognize calls to cexp and transforms them to num_complex::Complex::exp, for instance. But I think that's out of scope for Corrode, and should be a post-processor on Corrode's output.

Does that help?

harpocrates commented 8 years ago

Ah! I am starting to see what is happening here. (I'm still in school and my experience with this stuff is thin bordering on nonexistent 😄...)

On this topic, here is some commentary I've started to dig through. This ticket to rust-lang and this ticket to rust-num discuss the not-quite C compatibility of num::complex::Complex. AFAIC tell x86-64, ARM, and ARM 64bit (AArch64) don't really have any problem at all (save for a missing repr(C) which gives a bunch of warnings - that is the subject of the ticket on rust-num). From the first link (the other two have very similar formulations):

Arguments of complexT where T is one of the types float or double are treated as if they are implemented as:

struct complexT {
  T real;
  T imag;
}

On my machine (x86-64), for example, I have no problem with the following

extern crate libc;
extern crate num;

use num::complex::Complex;

#[link(name="m")]
extern {
    pub fn cexp(z: Complex<f64>) -> Complex<f64>;
    pub fn cexpf(z: Complex<f32>) -> Complex<f32>;

    pub fn clog(z: Complex<f64>) -> Complex<f64>;
    pub fn clogf(z: Complex<f32>) -> Complex<f32>;
}

fn main() {
    unsafe {
        println!("cexp");
        println!("e^0 =     {:?}", cexp(Complex { re: 0.0, im: 0.0 }));
        println!("e^1 =     {:?}", cexp(Complex { re: 1.0, im: 0.0 }));
        println!("e^i =     {:?}", cexp(Complex { re: 0.0, im: 1.0 }));
        println!("e^(1+i) = {:?}", cexp(Complex { re: 1.0, im: 1.0 }));

        println!("cexpf");
        println!("e^0 =     {:?}", cexpf(Complex { re: 0.0, im: 0.0 }));
        println!("e^1 =     {:?}", cexpf(Complex { re: 1.0, im: 0.0 }));
        println!("e^i =     {:?}", cexpf(Complex { re: 0.0, im: 1.0 }));
        println!("e^(1+i) = {:?}", cexpf(Complex { re: 1.0, im: 1.0 }));

        println!("clog");
        println!("log(0) =       {:?}", clog(Complex { re: 0.0, im: 0.0 }));
        println!("log(e^0) =     {:?}", clog(Complex { re: 1.0, im: 0.0 }));
        println!("log(e^1) =     {:?}", clog(Complex { re: 2.718281828459045, im: 0.0 }));
        println!("log(e^i) =     {:?}", clog(Complex { re: 0.5403023058681398, im: 0.8414709848078965 }));
        println!("log(e^(1+i)) = {:?}", clog(Complex { re: 1.4686939399158851, im: 2.2873552871788423 }));

        println!("clogf");
        println!("log(0) =       {:?}", clogf(Complex { re: 0.0, im: 0.0 }));
        println!("log(e^0) =     {:?}", clogf(Complex { re: 1.0, im: 0.0 }));
        println!("log(e^1) =     {:?}", clogf(Complex { re: 2.718281828459045, im: 0.0 }));
        println!("log(e^i) =     {:?}", clogf(Complex { re: 0.5403023058681398, im: 0.8414709848078965 }));
        println!("log(e^(1+i)) = {:?}", clogf(Complex { re: 1.4686939399158851, im: 2.2873552871788423 }));
    }
}

The issue is that on other architectures, the behavior can depend on T (some architectures just put the components in separate registers). This problem is only for when we are passing complex numbers by value - as long as everything is accessed only behind pointers, we are fine.

Should we push on with this in the hopes that num::Complex eventually becomes compatible with the C complex types (given that there are several tickets open about this, one hopes that eventually this will be solved)? Or table it for the moment? Thoughts?

jameysharp commented 8 years ago

This wouldn't be the first portability problem in Corrode-generated code (see the translation for main for instance, which relies on POSIX), so getting an implementation that generates code which is only correct on the most popular architectures seems fine to me... By the time someone tries to use Corroded software on another architecture, maybe the upstream limitations will be fixed. :smile:

harpocrates commented 8 years ago

Alright. This is going to be several steps.

I'm not sure what the best way is to proceed with the last of these. I have not yet found a standard crate for libm like there is for libc, although there appears to be a lot of discussion about making one. We may have to temporarily just link ourselves the functions used (although that thought definitely makes me cringe).

There is also the problem I've already mentioned about the missing #[repr(C)] for num::complex::Complex. I've (hopefully) re-awoken an issue about this with rust-num. This is not a blocker either though. Just another annoyance.

jameysharp commented 8 years ago

That's a sound plan!

I initially wondered why IsComplex would wrap an arbitrary CType instead of just an Int indicating the floating point bit width. Reading your link on the GNU extensions made me aware that they support complex integers, which is super weird, but fine, that's easy enough for us I guess.

Note that Corrode-generated code doesn't use the libc crate, so I'd be surprised if it needs a libm crate either. The trick is that Corrode generates the necessary FFI bindings itself rather than relying on any other crate to provide them. The only additional thing needed here is to ensure that the system's native libm is included in the library link list, and that doesn't strictly have to be our problem.

I do want to see a tool that recognizes FFI bindings that already exist in other crates, then replaces those extern blocks with suitable crate imports. But, you know, later. :smile: