rusttranspilerhilbert-curve

Why does this Hilbert Curve implementation ported from C (from Wikipedia) seem to fail?


I found the following code for drawing Hilbert Curves on Wikipedia:

//convert (x,y) to d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(s, &x, &y, rx, ry);
    }
    return d;
}

//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s<n; s*=2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;
    }
}

//rotate/flip a quadrant appropriately
void rot(int n, int *x, int *y, int rx, int ry) {
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;
        }

        //Swap x and y
        int t  = *x;
        *x = *y;
        *y = t;
    }
}

I put it into c2rust.com with definition of rot() put as the first function and got the following code:

#![allow(dead_code,
         mutable_transmutes,
         non_camel_case_types,
         non_snake_case,
         non_upper_case_globals,
         unused_mut)]
#![feature(libc)]
extern crate libc;
// rotate/flip a quadrant appropriately
#[no_mangle]
pub unsafe extern "C" fn rot(mut n: libc::c_int,
                             mut x: *mut libc::c_int,
                             mut y: *mut libc::c_int,
                             mut rx: libc::c_int,
                             mut ry: libc::c_int)
                             -> () {
    if ry == 0i32 {
        if rx == 1i32 {
            *x = n - 1i32 - *x;
            *y = n - 1i32 - *y
        }
        // Swap x and y
        let mut t: libc::c_int = *x;
        *x = *y;
        *y = t
    };
}
// convert (x,y) to d
#[no_mangle]
pub unsafe extern "C" fn xy2d(mut n: libc::c_int,
                              mut x: libc::c_int,
                              mut y: libc::c_int)
                              -> libc::c_int {
    let mut rx: libc::c_int = 0;
    let mut ry: libc::c_int = 0;
    let mut s: libc::c_int = 0;
    let mut d: libc::c_int = 0i32;
    s = n / 2i32;
    while s > 0i32 {
        rx = (x & s > 0i32) as libc::c_int;
        ry = (y & s > 0i32) as libc::c_int;
        d += s * s * (3i32 * rx ^ ry);
        rot(s, &mut x, &mut y, rx, ry);
        s /= 2i32
    }
    return d;
}
// convert d to (x,y)
#[no_mangle]
pub unsafe extern "C" fn d2xy(mut n: libc::c_int,
                              mut d: libc::c_int,
                              mut x: *mut libc::c_int,
                              mut y: *mut libc::c_int)
                              -> () {
    let mut rx: libc::c_int = 0;
    let mut ry: libc::c_int = 0;
    let mut s: libc::c_int = 0;
    let mut t: libc::c_int = d;
    *y = 0i32;
    *x = *y;
    s = 1i32;
    while s < n {
        rx = 1i32 & t / 2i32;
        ry = 1i32 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4i32;
        s *= 2i32
    }
}

fn main() {
    let mut x: libc::c_int = 0;
    let mut y: libc::c_int = 0;
    let d: libc::c_int = 10;
    unsafe {
        for n in 1..10 {
            d2xy(n, d, &mut x, &mut y);
            println!("n={}, x={}, y={}", n, x, y);
        }
    }
}

The problem is that the results seem to make no sense:

   Compiling x v0.1.0 (file:///tmp/x)
warning: value assigned to `rx` is never read                            ] 0/1: x                                                                                                                
  --> src/main.rs:34:13
   |
34 |     let mut rx: libc::c_int = 0;
   |             ^^
   |
   = note: #[warn(unused_assignments)] on by default

warning: value assigned to `ry` is never read
  --> src/main.rs:35:13
   |
35 |     let mut ry: libc::c_int = 0;
   |             ^^

warning: value assigned to `s` is never read
  --> src/main.rs:36:13
   |
36 |     let mut s: libc::c_int = 0;
   |             ^

warning: value assigned to `rx` is never read
  --> src/main.rs:55:13
   |
55 |     let mut rx: libc::c_int = 0;
   |             ^^

warning: value assigned to `ry` is never read
  --> src/main.rs:56:13
   |
56 |     let mut ry: libc::c_int = 0;
   |             ^^

warning: value assigned to `s` is never read
  --> src/main.rs:57:13
   |
57 |     let mut s: libc::c_int = 0;
   |             ^

    Finished dev [unoptimized + debuginfo] target(s) in 0.25s                                                                                                                                    
     Running `target/debug/x`
n=1, x=0, y=0
n=2, x=1, y=1
n=3, x=3, y=3
n=4, x=3, y=3
n=5, x=3, y=3
n=6, x=3, y=3
n=7, x=3, y=3
n=8, x=3, y=3
n=9, x=3, y=3

I definitely didn't expect repeated coordinates for different Ns. What could have gone wrong? Here's C test code for comparison:

int main() {
    int n=32, d=0, x=0, y=0;
    for (d=0; d<10; d++) {
        d2xy(n, d, &x, &y);
        printf("d=%d, x=%d, y=%d\n", d, x, y);
    }
}

And the expected output (as generated by C):

d=0, x=0, y=0
d=1, x=0, y=1
d=2, x=1, y=1
d=3, x=1, y=0
d=4, x=2, y=0
d=5, x=3, y=0
d=6, x=3, y=1
d=7, x=2, y=1
d=8, x=2, y=2
d=9, x=3, y=2

Solution

  • Well, if you change the test code, you'll naturally get different output. The original C test code fixes n and varies d; you fix d and vary n.

    Once I changed the Rust test code to do the same thing as the C test code, I get the same output.

    fn main() {
        let mut x: libc::c_int = 0;
        let mut y: libc::c_int = 0;
        let d: libc::c_int = 10;
        unsafe {
            for n in 1..10 {
                d2xy(n, d, &mut x, &mut y);
                println!("n={}, x={}, y={}", n, x, y);
            }
        }
    }