# IP to Country (#139)

**URL:** <https://www.ruby-forum.com/t/ip-to-country-139/115086>\
**Category:** Ruby\
**Created:** [September 20, 2007, 2:19pm UTC](https://www.ruby-forum.com/t/ip-to-country-139/115086 "2007-09-20T14:19:07Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 20, 2007, 2:19pm UTC](https://www.ruby-forum.com/t/ip-to-country-139/115086/1 "2007-09-20T14:19:07Z")

</div>

Matthias Wätcher made a classic mistake this week. He sent in his first  
ever  
quiz solution and told us not to expect anything special out of it. We  
later  
learned that it was a lot faster than all of the other solutions, thanks  
to more  
effort from Matthias. His code taught me some new tricks and I want to  
share  
those with you.

But first, let’s talk speed.

Most of the solutions are quite quick, relatively speaking. What’s the  
shared  
secret of speed? Binary search. The records are in sorted order, so  
it’s  
possible to perform a simple  
cut-the-possible-matches-in-half-at-each-step  
lookup. That favored algorithm makes short work of what could otherwise  
be a  
lengthy search.

Now you can do a binary search on the database file as is and several  
solutions  
did. This is a little trickier, because the records are not of a  
standard size.  
You have to be super careful not to accidently skip records. While the  
solutions handled the challenge very well, you can make things quite a  
bit  
easier if you are willing to preprocess the file.

You can also speed things up with some clever preprocessing. That was  
the other  
trick Matthias used to find answers so quickly.

Matthias realized that while the actual records contain quite a bit of  
data, we  
only really care about the start of a range, the end of a range, and the  
country  
code. You can fit all of that in just ten bytes with four for each  
address and  
two for the country.

The file also contains some consecutive ranges that can be collapsed for  
the  
purposes of our search. Such ranges may differ in some attributes, but  
as long  
as their country codes are the same we can treat them as a single unit.

Now that you know the goal, let’s take a look at the packing code  
Matthias sent  
in:

#!/usr/bin/ruby

# comment

last\_start=nil  
last\_end=nil  
last\_country=nil  
File.open(“packed-ip.dat”,“wb”) do |wfile|  
IO.foreach(“geo-ip.csv”) do |line|  
next if !(line =~ /^"/ )  
s,e,d1,d2,co=line.delete!(""").split(",")  
s,e = s.to\_i,e.to\_i  
if !last\_start

# initialize with first entry

```
      last_start,last_end,last_country = s,e,co
    else
      if s==last_end+1 and co==last_country

```

# squeeze if successive ranges have zero gap

```
        last_end=e
      else

```

# append last entry, remember new one

```
        wfile << [last_start,last_end,last_country].pack("NNa2")
        last_start,last_end,last_country = s,e,co
      end
    end
end

```

# print last entry

```
if last_start
  wfile << [last_start,last_end,last_country].pack("NNa2")
end

```

end

The three variables declared up front are for tracking the ranges.  
These will  
be used to collapse consecutive ranges.

The next bit of code creates the binary database we will write into and  
parses  
the CSV formated data. Though the data is in the CSV format, the actual  
content  
is trivial and you don’t need a proper parser to get at it. As you can  
see,  
Matthias just checks for lines starting with a quote, pulls out all  
quote  
characters, and split()s on commas. This is faster than using a parser.

The if/else chain in the middle of the code does most of the work.  
First, it  
stores the initial range in the tracking variables. For all other  
ranges it  
tests to see if it is consecutive with the last one recorded and has the  
same  
country code. When it does, the endpoint of the last range is just  
bumped to  
include them both. When it doesn’t, the last range is written to the  
file and  
the code starts tracking the new range. The final if statement ensures  
that we  
write out the final range before exiting.

This really isn’t too much work and it runs in under two seconds on my  
box.  
That’s a small price to pay for a speed gain every time we look up an  
address.

Let’s dive into the search code now. Here’s how it begins:

#!/usr/bin/ruby

# take command line or stdin – the latter has performance advantage

# for long lists

if ARGV[0]  
arr=ARGV  
else  
arr=$stdin  
end

# …

As the comment tells us, Matthias added another way to feed the program  
addresses. Where I said we should take one from the command-line  
arguments,  
this code actually handles any number of addresses from command-line  
arguments  
or STDIN.

This next bit of code opens up our database:

# …

# the binary table file is looked up with each request

File.open(“packed-ip.dat”,“rb”) do |rfile|  
rfile.seek(0,IO::SEEK\_END)  
record\_max=rfile.pos/10-1

```
# ...

```

The seek() and pos() calls here are used to find the end of the file.  
You need  
to know both ends of a data set to perform a binary search. Note that  
dividing  
by ten gives us the count of records since they are a fixed width and  
Matthias  
subtracts one because we will never need to seek() to the end of the  
last record  
again.

Now there’s a touch more preparation for each address we want to find:

```
# ...

arr.each { |argv|
  # build a 4-char string representation of IP address
  # in network byte order so it can be a string compare below
  ipstr= argv.split(".").map {|x| x.to_i.chr}.join

  # ...

```

In order to avoid a bunch of to\_i() calls on each range extracted from  
the  
database, Matthias just encodes the address we are hunting for into the  
character encoding used in the database. This way simple String  
comparisons can  
determine if the address it in the range.

We’re now ready for the actual search code:

```
  # ...

  # low/high water marks initialized
  low,high=0,record_max
  while true
    mid=(low+high)/2 # binary search median
    rfile.seek(10*mid) # one record is 10 byte, seek to position
    str=rfile.read(8) # for range matching, we need only 8 

```

bytes  
# at comparison, values are big endian, i.e. packed(“N”)  
if ipstr\>=str[0,4] # is this IP not below the current range?  
if ipstr\<=str[4,4] # is this IP not above the current range?  
puts rfile.read(2) # a perfect match, voila!  
break  
else  
low=mid+1 # binary search: raise lower limit  
end  
else  
high=mid-1 # binary search: reduce upper limit  
end  
if low\>high # no entries left? nothing found  
puts “no country”  
break  
end  
end  
}  
end

This is a pretty textbook binary search. You always begin by going to  
the  
middle of the current low and high. In this case that’s a seek() call  
and we  
have to remember to multiply the midpoint by our record size of ten.

Once we are at the right record, the code read()s the first eight bytes  
and  
compares the address against the low and high for the range. When it is  
in the  
range, the final two bytes are read and printed. If the address is  
below the  
current range, we drop the high to below the current range. If it’s  
above, we  
raise the low to above the current range. A final check is added to  
catch the  
cases where no match was found, in which case our low will bypass the  
high.

Remember that a second goal of the quiz described search was to be  
memory  
friendly. This code does terrific on that front since only one record  
needs to  
be in memory at a time. Once the checks are done, it can be replaced by  
the  
next record.

My thanks to all who showed so many great examples of this classic  
algorithm.

Tomorrow we will write programs that can help me to better understand my  
wardrobe…