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
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);
}
}
}