Function ipv4_heatmap::utils::hil_xy_from_s

source · [−]

pub fn hil_xy_from_s(ip_as_int: u32, order: i16) -> (u32, u32)

Expand description

Convert an IPv4 address (in integer form) to a 12th order Hilbert x/y point

This is a funky state-transition table made (in)famous? in “The Hacker’s Delight”.

The license is quite generous, if not adorable by today’s standards. Do not try to visit the site today as spammers nabbed the domain.

In any Hilbert curve, only four of eight possible U-shapes occur:

(A) left-to-right arrow downward facing
(B) bottom-to-top arrow leftward facing
(C) right-to-left arrow upward facing
(D) top-to-bottom arrow rightward facing

In this program, the current state is represented by an integer from 0 to 3 for the above states A through D, respectively. In the assignment to row, the current state is concatenated with the next two bits of s, giving an integer from 0 to 15, which is the applicable row number in the state table (below). row is used to access integers (expressed in hexadecimal) that are used as bit strings to represent the rightmost two columns of the state table (that is, these accesses are in-register table lookups). Left-to-right in the hexadecimal values corresponds to bottom-to-top in the state table.

If the current state is	and the next (to right) 2 bits of s are	then append to (x,y)	and enter state
`A`	`00`	`(0,0)`	`B`
`A`	`01`	`(0,1)`	`A`
`A`	`10`	`(1,1)`	`A`
`A`	`11`	`(1,0)`	`D`
`B`	`00`	`(0,0)`	`A`
`B`	`01`	`(0,1)`	`B`
`B`	`10`	`(1,1)`	`B`
`B`	`11`	`(1,0)`	`C`
`C`	`00`	`(0,0)`	`D`
`C`	`01`	`(0,1)`	`C`
`C`	`10`	`(1,1)`	`C`
`C`	`11`	`(1,0)`	`B`
`D`	`00`	`(0,0)`	`C`
`D`	`01`	`(0,1)`	`D`
`D`	`10`	`(1,1)`	`D`
`D`	`11`	`(1,0)`	`A`

Original C code:

void hil_xy_from_s(unsigned s, int n, unsigned *xp, unsigned *yp) {
  int i;
  unsigned state, x, y, row;
  state = 0; // Initialize state
  x = y = 0;
 
  for (i = 2*n - 2; i >= 0; i -= 2) {  // Do n times.
    row = 4*state | (s>>i) & 3;        // Row in table. 
    x = (x << 1) | (0x936C >> row) & 1;
    y = (y << 1) | (0x39C6 >> row) & 1;
    state = (0x3E6B94C1 >> 2*row) & 3; // New state.
  }
 
  *xp = x; // pass results back
  *yp = y;
}

Grab the book for a few more alternative implementations.