Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bug in translated Hilbert Curve generation code? #27

Closed
d33tah opened this issue Sep 21, 2018 · 1 comment
Closed

Bug in translated Hilbert Curve generation code? #27

d33tah opened this issue Sep 21, 2018 · 1 comment

Comments

@d33tah
Copy link

d33tah commented Sep 21, 2018

This is a copied StackOverflow question.

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
@d33tah
Copy link
Author

d33tah commented Sep 21, 2018

That was a bug in my test code, as answered on SO. Closing.

@d33tah d33tah closed this as completed Sep 21, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant