# A Rust/C Wrapper over the C++ NTL Library

This document describes the process I employed in order to use the fast NTL library for polynomial operations through C and Rust. The idea is that instead of implementing every polynomial operation we want (such as multiplication) we can simply convert the polynomial to the corresponding NTL type, perform the operations we want there, and and then return the completed polynomial back to our native Rust/C type.

In particular, another benefit is that NTL provides is that it intelligently chooses what kind of algorithm to apply depending on the prime that you're working over. The particular class I implemented was `ZZ_pX`, representing a polynomial over a finite field. Depending on the size of the prime, NTL chooses between:

* Classical Multiplication,
* Karatsuba Multiplication,
* FFT,
* Schönhage–Strassen.

Thus any solution would have to utilize these different types. It's easier to simply use NTL instead.

The code can be found [here](https://github.com/matcauthon49/ntl-wrapper).

## The C wrapper

The C wrapper is the easier of the two to write. In this case, since C++ already supports `.h` header files, we simply need to wrap every function that we want to support in the form of a C function. This is usually easy, but the inclusion of classes makes it slightly non-trivial.

### Ensuring C linkages

One major difference we have to take care of is that since we're going to be running this using the C compiler, we have to make sure that we're using C linkages. This can be accomplished by including

extern "C" {
    // code
}

and writing all the information in the `wrapper.h` file inside this. However, we can also optimize for the situation in which the code is called by C++. This follows by letting

#ifdef __cplusplus
extern "C" {
#endif
    
    // code
    
#ifdef __cplusplus
}
#endif

### New ```struct```

Since C doesn't have classes, for each class we implement we will define a `struct` and the functions which return the class or take it as an argument will do that to the `struct` instead. In our case,

#ifdef __cplusplus
    #include <NTL/ZZ_pX.h>
    #include <NTL/ZZ_p.h>
    #include <NTL/ZZ.h>

    using namespace NTL;
extern "C" {
#else
    typedef struct ZZ_pX ZZ_pX;
    typedef struct ZZ_p ZZ_p;
    typedef struct ZZ ZZ;
#endif

ensures that if C is used then the structs are appropriately defined, but if C++ is used then we simply import the library.

### Header Functions

We now have to write a header function in `wrapper.h` for each function that we plan to implement. In my case, I chose the nomenclature as `class_function_name();`, so the function looks like

ZZ_pX *ZZ_pX_zero();

which takes in nothing, and returns a pointer to a `ZZ_pX` of value `0`. Another function

void ZZ_pX_mul(ZZ_pX *x, const ZZ_pX *a, const ZZ_pX *b);

is similarly defined, where our arguments are pointers to `ZZ_pX`.

### Writing the Functions

The `wrapper.cpp` file invokes the functions we want and returns them. So the zero function would be implemented as

ZZ_pX *ZZ_pX_zero() {
    ZZ_pX *z = new ZZ_pX();
    return z;
}; 

:::info
There is a particular issue with the NTL wrapper, which is that NTL takes `references&` to objects instead of `pointers*` as inputs. Converting between them involves some dereferencing and is simple but annoying. I encountered a bunch of segmentation faults throughout the ordeal; it's probably best just to take a look at the code and copy whatever I've done there.
:::

### Conclusion

After this, all you have to do is write a normal program in C and the compiler will do all the work for you. Make sure to include the

#include "wrapper.h"

header. To run, compile all the files together. In my case, that was simply

gcc -g -O2 -std=c++11 -pthread -march=native test.c wrapper.cpp -lstdc++ -o foo -lntl -lgmp -lm

This is a bit loaded, and the flags do different things. The flags marked with ** at the beginning are necessary, the others aren't.

* `-g` generates debugging information,
* `-O2` is for optimization,
* `-std=c++11` specifies which C++ version,
* `-pthread` runs multithreading using the pthread library,
* `-march-native` tweaks the compiled output for the specific machine architecture. *You can remove this. Only use it if you're recompiling a program every time.*
* ** `-lstdc++` compiles the C++ standard library. *Can be omitted if using* `g++` *instead of* `gcc`.
* ** `-o` specifies compilation to an output file,
* ** `-lntl` links to NTL,
* ** `-lgmp` links to GMP,
* ** `-lm` links to `math.h`.

## The Rust Wrapper

It's necessary to have a C wrapper prepared before C++ functions can be called in Rust. This is because Rust's FFI supports C bindings, but not C++ bindings. It's also necessary to wrap each C function into a Rust function, but Rust has a crate to do that.

### Bindgen

Rust's Bindgen Crate writes the Rust bindings for you. To utilize it, add the crate to the dependencies in the `cargo.toml` file:

[build-dependencies]
bindgen = "0.63.0"

To initiate bindgen, navigate over to the `build.rs` file and enter the following code.

extern crate bindgen;

use std::env;
use std::path::PathBuf;

fn main() {
    // Define the bindings build keyword
    let bindings = bindgen::Builder::default()
        .header("wrapper.h")
        .parse_callbacks(Box::new(bindgen::CargoCallbacks))
        .generate()
        .expect("Unable to generate bindings");

    // Write the bindings to the $OUT_DIR/bindings.rs file.
    let out_path = PathBuf::from(env::var("OUT_DIR").unwrap());
    bindings
        .write_to_file(out_path.join("bindings.rs"))
        .expect("Couldn't write bindings!");
}

`$OUT_DIR` is some repository in which the output will occur; typically it is a weirdly-named folder inside `target/build`. After running the code with `cargo build`, you can browse through the folders until you find a file called `bindings.rs` which has the Rust bindings.

/* automatically generated by rust-bindgen 0.63.0 */

#[repr(C)]
#[derive(Debug, Copy, Clone)]
pub struct ZZ_pX {
    _unused: [u8; 0],
}

extern "C" {
    pub fn ZZ_pX_zero() -> *mut ZZ_pX;
}

Of course, it is also possible to write this by yourself, but bindgen makes it a lot easier when working with large files, and prevents the type of errors you'd make by hand.

### Using `bindings.rs`

To use the bindings just created, begin by adding the following header to `lib.rs`.

#![allow(non_upper_case_globals)]
#![allow(non_camel_case_types)]
#![allow(non_snake_case)]

include!(concat!(env!("OUT_DIR"), "/bindings.rs"));

The first 3 lines are to ward off some errors, while the last line includes the code directly into the library of the package. My package is called `wrapper_bindings`, so any time that I want to use a function from the library I can call it as

use wrapper_bindings::ZZ_pX_zero;
use wrapper_bindings::ZZ_pX_mul;

and so on.

### C datatypes

The code that bindgen constructs will use C datatypes. You will have to add

[dependencies]
cty = "0.2.2"

to `cargo.toml` to use C datatypes, which look like `cty::c_long` or `cty::c_const`. Some other datatypes, like `const char*`, are formed using different methods. In particular, to create a `const char*`, you'll need to do something like

use std::ffi::CString;

let s1 = CString::new("String".to_string()).unwrap();
let p = ZZ_set_string(s1.as_ptr() as *const i8);

### Building

The final piece of the puzzle is to ensure that C++ also compiles every time Rust is compiled, so we'll have to make more changes to `build.rs` so that the compilation is correct. Begin by using the `cc` crate in `cargo.toml`, that gives access to `gcc`.

[build-dependencies]
cc = "1.0.78"

In our `test.c` build code, we used flags like `-lgmp` and `-lntl` to include the libraries. These have to be externally introduced to `build.rs`.

fn main() {
    
    // code
    
    println!("cargo:rustc-link-lib=ntl");
    println!("cargo:rustc-link-lib=gmp");
    
    // code
}

The `cc::Build::new()` method runs `gcc`. Note that it doesn't run `g++`; you'll have to enable that. The bash code looks somewhat like this:

cc::Build::new()
    .cpp(true)
    .flag("-g")
    .flag("-O2")
    .flag("-pthread")
    .flag("-march=native")
    .file("wrapper.cpp")
    .compile("foo.a");

`.cpp(true)` specifies that C++ will be compiled. This is important, because otherwise Rust will assume that `wrapper.h` contains only C code and you'll get annoying errors that are difficult to debug. `.flag()` adds the flags as required, and `.file()` adds the file to be compiled (note that since we're inside `fn main()`, we don't need to describe how the other files will compile). We also don't need to add the library linkage flags, since we've done that in the previous step.

Finally, the `.compile()` method outputs the compiled executable as `foo.a` inside `$OUT_DIR`.

## Benchmarks

To test the code, head over [to the github repostitory and test it yourself.](https://github.com/matcauthon49/ntl-wrapper)

Benchmark information as well as running information is included in the `README.md`.