Calling Maths Geeks ;)

Complex (well for me) number crunch formula

[trillianjedi]

Hi guys, I'm out of my depth again (ah, living life on the edge has it's problems :)).

I'm using INET_ATON within a MySQL table so that I can store IP addresses as a 32 bit unsigned int (nice and small = fast, generally speaking).

I need an efficient way to check that 32 bit unsigned int to see if it's within a particular C-Class IP range. I therefore don't want to convert back to an INET variable.

The MySQL manual states this:-

Given the dotted-quad representation of a network address as a string, returns an integer that represents the numeric value of the address. Addresses may be 4- or 8-byte addresses.

mysql> SELECT INET_ATON('209.207.224.40');
-> 3520061480

The generated number is always in network byte order. For the example just shown, the number is calculated as 209×256^3 + 207×256^2 + 224×256 + 40.

Emphasis is mine to highlight the maths bit.

Can I do something bit-wise to get that last byte value as fast as possible - in this example, "40"? Or is there a formula I can use, or, alternatively, am I just better off (speed wise) converting back to INET?

Thanks!

TJ

[jatar_k]

it should work if you divid ethe number you have by 256
then take the decimal and multiply it by 256

the only part that isn't divisible by 256 is what you are looking for

3520061480 / 256 = 13750240.15625

.15625 * 256 = 40

you could maybe use this (untested)

$mybit = 256 * (fmod($valfromdb,256));

might work

[eelixduppy]

jatar_k, the behavior you are describing is just a simple modulus, however, when tested, it doesn't yield the correct result. Have any idea why?

$ip = 3520061480;
echo $ip%256; #echos -216

It's not correct, but I did notice if you add 256 to that number you get the correct result. hmm...

[trillianjedi]

I get 10240 output for the following:-

<?php
$mybit = 256 * (fmod(3520061480,256));
echo $mybit;
?>

I was expecting "40". There is a "40" in there, although not sure if that's a red herring.

And I've also noticed an error in my original post, I'm actually after byte #3 - the C-Class, not byte #4. Having said that, I'm sure the maths logic will be the same, it will just be formulated from 256^2?

[eelixduppy]

Well, assuming the modulus is working correctly, which for me it isn't, this should work:

$ip = 3520061480;
echo floor(($ip%65536)/256);

Now, because my modulus isn't working correctly, this produces the correct result on my machine:

$ip = 3520061480;
echo floor((($ip%65536)+65536)/256);

[jatar_k]

>> I'm actually after byte #3

hehe, I was wondering about that

I don't know, it may just be easier to revert it, or store both

[trillianjedi]

$ip = 3520061480;
echo floor((($ip%65536)+65536)/256);

That works for me too, on my machine (Intel).

The only thing that I believe could produce an incorrect result (possibly, and it's a long shot) would be a little-endian processor?

I don't know, it may just be easier to revert it, or store both

Nah, that would be quitting ;)

Reverting it would, in theory, take four times as many processor cycles?

[jatar_k]

the original math seems to work but using mod it doesn't, you could it explicitly

3520061480 / 256 = 13750240.15625

.15625 * 256 = 40

3520061480 - 40 = 3520061440

3520061440 / 65536 = 53711.875

.875 * 256 = 224

<added>i seem to be one post behind every time

I also have no access to test this at the moment so i am using paper and a calculator :)

[PCInk]

I don't do PHP, so this is just pseudocode that someone might be able to help exactly how to do what you want. Assuming $ip contains the 3520061480 value (or IP equivelant of):

$ip = $ip & 0xFF000000
$ip = $ip / (256^3)

Would get you the first part of the ip address. The 0xFF000000 is hexidecimal, you may need to work out how to represent hexidecimal in PHP (if different from C) or you can work it out (use calculator in Windows in scientific mode). If you are crunching lots of these, I would also work out 256^3 and put the actual value in there.

To get the second number the values should be changed to:
0x00FF0000, 256^2
0x0000FF00, 256^1 to get the third number in the IP
0x000000FF, 256^0 (or don't even bother with the divide as it is dividing by 1) to get the last number in the IP.

[edited by: PCInk at 2:45 pm (utc) on Feb. 22, 2007]

[trillianjedi]

Adam - the "floor" version by eelix does work. Your longhand way would be more reliable I think but for the fact that I don't believe byte order has any bearing doing it this way?

So:-

function SameClassC($ip1, $ip2) // two unsigned ints
{
 $result = ( floor((($ip1%65536)+65536)/256) == floor((($ip2%65536)+65536)/256) );
 return $result;
}

Is a working function (and I can't believe anything but way faster than converting back to INET_A and comparing).

PCInk - that looks really interesting. Have never done anything bit-wise in PHP, but I'll have a go at it and see what happens. I'm curious as to whether doing this bitwise creates a big-endian/little-endian problem....?

Would be interesting to run some timing tests between different methods.

[PCInk]

It might have some problems with the divide on the top one. You could try the divide (or better a logical shift) first:

$ip = $ip >> 24
$ip = $ip & 255

Hopefully should work? Changing 24 to 16 or 8 or 0 (if zero you can miss it out)

[eelixduppy]

The following doesn't produce the correct result:

$ip = 3520061480;
$ip = $ip >> 24;
$ip = $ip & 255;
echo $ip; #echos 209

I'm going to mess around with bitwise operators as I haven't touched them in a couple years.

Would be interesting to run some timing tests between different methods.

Looks like I'll be working on something today. I don't have classes all week! ;)

[trillianjedi]

I don't have classes all week!

Hooray!

;)

I got it working. You're using the wrong shift:-

$ip = 3520061480;
$ip = $ip >> 8;
$ip = $ip & 255;
echo $ip;

PCink - you've geeked me out mate, that's just peachy ;)

So, question is which is faster.

In the red corner:-

function SameClassC($ip1, $ip2) // two unsigned ints
{
$result = ( floor((($ip1%65536)+65536)/256) == floor((($ip2%65536)+65536)/256) );
return $result;
} 

In the blue corner:-

function SameClassC($ip1, $ip2) // two unsigned ints
{
$ip1 = $ip1 >> 8;
$ip1 = $ip1 & 255;
$ip2 = $ip2 >> 8;
$ip2 = $ip2 & 255;
$result = $ip1 == $ip2;
return $result;
} 

I'm not sure I've coded that in the most elegant way either....

[edited by: trillianjedi at 2:58 pm (utc) on Feb. 22, 2007]

[eelixduppy]

Ok, results so far (should tell us what we are looking for):
PCInk, your method is consistently working about 5 times faster than my method.

My Method: 7.2002410888672E-005 seconds
#
PCInk's Method: 1.5974044799805E-005 seconds

[eelixduppy]

Ok here's the info for the functions.

Code Used:

<?php
function SameClassC1($ip1, $ip2) // two unsigned ints
{
$result = ( floor((($ip1%65536)+65536)/256) == floor((($ip2%65536)+65536)/256) );
return $result;
} 

function SameClassC2($ip1, $ip2) // two unsigned ints
{
$ip1 = $ip1 >> 8;
$ip1 = $ip1 & 255;

$ip2 = $ip2 >> 8;
$ip2 = $ip2 & 255;

$result = $ip1 == $ip2;
return $result;
} 

$ip1 = 3520061480;
$ip2 = 3520061480;
$time_start = microtime(true);

echo SameClassC1($ip1,$ip2);

$time_end = microtime(true);
$time = $time_end - $time_start;
echo 'Time 1: '.$time.'<br/>';
echo '<br/>';
$time_start = microtime(true);

echo SameClassC2($ip1,$ip2);

$time_end = microtime(true);
$time = $time_end - $time_start;
echo 'Time 2: '.$time;
?>

Output:

1Time 1: 7.3909759521484E-005

1Time 2: 2.3841857910156E-005

Looks like we have a winner! ;)

[trillianjedi]

Looks like we ave a winner!

By a landslide....

Thanks eelix.

PCink is a confirmed genius :)

Is there a more elegant way to write the winning function?

Thanks again guys.

<Added>Just a thought.... following the right shift, is the AND with 255 required? eg, will the right shift drop the last IP byte "off the end", leaving a matching pair of ints without requiring further manipulation?</Added>

[eelixduppy]

Is there a more elegant way to write the winning function?

I guess you can combine some things. It reduces the speed by a very small amount, though:

function SameClassC2($ip1, $ip2) // two unsigned ints
{
$ip1 = ($ip1 >> 8) & 255;
$ip2 = ($ip2 >> 8) & 255;

return($ip1 == $ip2);
}

will the right shift drop the last IP byte "off the end", leaving a matching pair of ints without requiring further manipulation?

I'm not sure about this, but if you are looking for a speed advantage, the difference is practically not noticeable according to my tests.

[trillianjedi]

but if you are looking for a speed advantage

Absolutely - 100% about speed (lots of queries per second going on).

Thanks for all your help!

[jatar_k]

nice PCInk

gee, look away for a few minutes ;)