#!/usr/bin/env python

import cgi
import errno
import math
import md5
import os
import re
import sys
import time
import urllib2
import urlparse

DATADIR = "find-data"
LOCATIONS_DIR = "locations"
DOMAINS_DIR = "domains"
RESOLUTION = 600
X_OFFSET = 9360
Y_OFFSET = 9360
# The target screen size of icons automatically zoomed on.
AUTOZOOM_SIZE = 400

class loc (object):
	def __init__(self, x, y, size):
		self.x = x
		self.y = y
		self.size = size

class timer (object):
	def __init__(self):
		self.a = None
		self.b = None

	def start(self):
		self.a = time.clock()

	def end(self):
		self.b = time.clock()

	def elapsed(self):
		return self.b - self.a

def fmt_float(f):
	return ("%.3f" % f).replace("-", "−");

def is_md5(s):
	if len(s) != 32:
		return False
	for c in s:
		if c not in "ABCDEF0123456789":
			return False
	return True

def split_coords(s):
	try:
		x, y = s.split(",")
		x = float(x)
		y = float(y)
	except ValueError:
		return None
	else:
		return (x, y)

def get_favicon_url(data):
	for link in re.finditer(r'<\s*link\s+([^>]*)>', data, re.I):
		attrs = link.groups()[0]
		rel = None
		href = None
		for m in re.finditer(r'(\w+)\s*=\s*["\'](.*?)["\']', attrs, re.I):
			name, value = m.groups()
			if name.lower() == "rel":
				rel = value
			if name.lower() == "href":
				href = value
			if rel and "icon" in rel.lower().split() and href:
				return href
	return "/favicon.ico"

def print_loc(prefix, loc):
	if loc is None:
		print "<p>%s: Not found.</p>" % cgi.escape(prefix)
	else:
		x_f = float(loc.x + X_OFFSET) / RESOLUTION
		y_f = float(Y_OFFSET - loc.y) / RESOLUTION
		print "<p>%s: The icon is at (%s, %s) and is %d &times; %d pixels.</p>" % (cgi.escape(prefix), fmt_float(x_f), fmt_float(y_f), loc.size, loc.size)

def lookup(base, hash):
	result = None
	filename = os.path.join(DATADIR, base, LOCATIONS_DIR, hash[0:2], hash[2:4])
	try:
		f = open(filename, "r")
	except IOError, e:
		if e.errno == errno.ENOENT:
			return None
		else:
			raise
	else:
		for line in f:
			h, l, t, s = line.split()
			if h == hash:
				l = int(l)
				t = int(t)
				s = int(s)
				result = loc(l + s / 2, t + s / 2, s * 2)
				break
		f.close()
	return result

def lookup_domain_single(domain, filename):
	f = open(filename, "r")
	try:
		for line in f:
			host, hash = line.strip().split("\t")
			if host == domain:
				return hash
	finally:
		f.close()

def lookup_domain_aux(domain, dir, remaining):
	if len(remaining) == 0:
		return lookup_domain_single(domain, os.path.join(dir, "term"))
	else:
		k, remaining = remaining[0], remaining[1:]
		filename = os.path.join(dir, k)
		if os.path.isdir(filename):
			return lookup_domain_aux(domain, filename, remaining)
		else:
			return lookup_domain_single(domain, filename)

def collapse_domain(domain):
	r = []
	for c in domain.lower():
		if c.isalnum():
			r.append(c)
	return "".join(r)

def lookup_domain(base, domain):
	remaining = collapse_domain(domain)
	return lookup_domain_aux(domain, os.path.join(DATADIR, base, DOMAINS_DIR), remaining)

def handle_md5(hash):
	alexa_loc = lookup("alexa", hash)
	print_loc("MD5 lookup", alexa_loc)
	return alexa_loc

def handle_coords(coords):
	x, y = coords
	x = int(x * RESOLUTION + 0.5) - X_OFFSET
	y = Y_OFFSET - int(y * RESOLUTION + 0.5)
	return loc(x, y, 16)

def get_url(url):
	t = timer()
	print "<p>"
	print "<b>%s</b>" % cgi.escape(url)
	sys.stdout.flush()
	t.start()
	try:
		root = urllib2.urlopen(url, None)
	except Exception, e:
		print " failed: %s." % cgi.escape(str(e))
		print "</p>"
		return None, None
	if root.geturl() != url:
		print " &rarr; <b>%s</b>" % cgi.escape(root.geturl())
		sys.stdout.flush()
	data = root.read(10000)
	t.end()
	print " %d bytes in %.2f seconds.<br>" % (len(data), t.elapsed())
	sys.stdout.flush()

	favicon_url = urlparse.urljoin(root.geturl(), get_favicon_url(data))
	print "<b>%s</b>" % cgi.escape(favicon_url)
	sys.stdout.flush()
	parts = urlparse.urlparse(favicon_url)
	if not (parts[0] == "http" or parts[0] == "https"):
		print " only http and https URLs are supported."
		print "</p>"
		return None, None
	t.start()
	try:
		favicon = urllib2.urlopen(favicon_url, None)
	except Exception, e:
		print " failed: %s." % cgi.escape(str(e))
		print "</p>"
		return None, None
	if favicon.geturl() != favicon_url:
		print " &rarr; <b>%s</b>" % cgi.escape(favicon.geturl())
		sys.stdout.flush()
	favicon_data = favicon.read(20000)
	t.end()
	print " %d bytes in %.2f seconds.<br>" % (len(favicon_data), t.elapsed())
	print "</p>"
	sys.stdout.flush()

	m = md5.new()
	m.update(favicon_data)
	hash = m.hexdigest().upper()

	return hash, favicon.geturl()

def handle_url(url):
	parts = urlparse.urlparse(url)
	if not parts[0]:
		url = "http://" + url
		parts = urlparse.urlparse(url)
	if not (parts[0] == "http" or parts[0] == "https"):
		print "<p><b>%s</b> only http and https URLs are supported.</p>" % cgi.escape(url)
		return
	url = urlparse.urlunparse(parts)

	alexa_loc = None
	hash, url = get_url(url)
	if hash:
		alexa_loc = lookup("alexa", hash)
		print "<img src=%s width=96 style='float:left;margin-left:1em;margin-right:1em;margin-bottom:1em'>" % \
			cgi.escape(url, True)
		print_loc("Online lookup", alexa_loc)

	if not alexa_loc:
		domain = parts[1]
		hash = lookup_domain("alexa", domain)
		if not hash and domain.startswith("www."):
			hash = lookup_domain("alexa", domain[4:])
		if hash:
			alexa_loc = lookup("alexa", hash)
		else:
			alexa_loc = None
		print_loc("Survey database lookup", alexa_loc)

	if not alexa_loc:
		print """\
<p>Why not found? See the <a href="#faq-1">FAQ</a> for more information.</p>
"""

	return alexa_loc

def handle_query(q):
	coords = split_coords(q)
	if is_md5(q.upper()):
		return handle_md5(q.upper())
	elif coords:
		return handle_coords(coords)
	else:
		return handle_url(q)

def box(n, low, high):
	if n < low:
		return low
	elif n > high:
		return high
	else:
		return n

def zoom_for_size(s):
	"""Return a good zoom level for an icon of the given size."""
	return box(int(math.log(float(s) / AUTOZOOM_SIZE, 2) + 0.5), 0, 6)

form = cgi.FieldStorage()
q = form.getfirst("q")

print "Content-type: text/html\r"
print "Connection: close\r"
print "\r"

print """\
<html>
<head>
<title>Icons of the Web</title>
<link rel="stylesheet" href="gsv.css" type="text/css">
<link rel="image_src" href="http://nmap.org/favicon/images/fb-thumbnail-150x150.png">
<script src="gsv.js" type="text/javascript"></script>
<!--#include virtual="/shared/templates/standard_body_top.html" -->
<!--#include virtual="/shared/templates/nmap_header.html" -->

<h2 class="purpleheader">Icons of the Web</h2>

<p>A large-scale scan of the top million web sites (per <a
href="http://www.alexa.com/topsites">Alexa traffic data</a>) was
performed in early 2010 using the <a href="http://nmap.org">Nmap
Security Scanner</a> and its <a
href="http://nmap.org/book/nse.html">scripting engine</a>.  As seen in the 
<a href="http://bits.blogs.nytimes.com/2010/08/26/bits-pics-visualizing-the-webs-icons/">New York Times</a>, 
<a href="http://news.slashdot.org/story/10/08/23/1911247/Nmap-Developers-Release-a-Picture-of-the-Web">Slashdot</a>,
<a href="http://gizmodo.com/5620681/all-300000-biggest-websites-visualized-with-their-icons">Gizmodo</a>,
<a href="http://www.engadget.com/2010/08/25/visualized-worlds-most-trafficked-websites-and-their-favicons/">Engadget</a>, and
<a href="http://www.telegraph.co.uk/technology/internet/7963908/The-worlds-top-300000-websites-visualised-by-favicon.html">Telegraph.co.uk</a> ...</p>

<p>We retrieved each site's <a
href="http://en.wikipedia.org/wiki/Favicon">icon</a> by first parsing
the HTML for a link tag and then falling back to /favicon.ico if that
failed.  328,427 unique icons were collected, of which 288,945 were
proper images.  The remaining 39,482 were error strings and other
non-image files.  Our original goal was just to improve our <a
href="http://nmap.org/nsedoc/scripts/http-favicon.html">http-favicon.nse</a>
script, but we had enough fun browsing so many icons that we used them
to create the visualization below.</p>

<p>The area of each icon is proportional to the sum of the reach of
all sites using that icon.  When both a bare domain name and its
"www."  counterpart used the same icon, only one of them was counted.
The smallest icons--those corresponding to sites with approximately
0.0001% reach--are scaled to 16x16 pixels.  The largest icon (Google)
is 11,936 x 11,936 pixels, and the whole diagram is 37,440 x 37,440
(1.4 gigapixels).  Since your web browser would choke on that, we have
created the interactive viewer below (click and drag to pan,
double-click to zoom, or type in a site name to go right to it).</p>

</p>
"""
sys.stdout.flush()

alexa_loc = None
if q:
	alexa_loc = handle_query(q)

print """\
<form>
<p>
Find icon (enter site name)
<input type="text" name="q" len=40 value="%s">
<input type="submit">
</p>
</form>
""" % (cgi.escape(q and q or "", True))

print """\
<div class="imageViewer" id="viewer">
<div class="well"> </div>
<div class="surface"> </div>
<p class="status"> </p>
<p class="zoom">
<a class="up" href="#" onclick="zoomIn(this.parentNode.parentNode, undefined); return false;">+</a> 
<a class="down" href="#" onclick="zoomOut(this.parentNode.parentNode, undefined); return false;">&minus;</a> 
</p>
</div>
"""

print """\
<script type="text/javascript">
	window.onload = function() {
		prepareViewer(document.getElementById("viewer"), "tiles", 256, 37440, 37440, 0, 6);
"""
if alexa_loc:
	print """\
		goTo(document.getElementById("viewer"), %d, %d, %d);
""" % (alexa_loc.x * 2, alexa_loc.y * 2, zoom_for_size(alexa_loc.size))
print """\
	}
</script>
"""

print """\
<br><br><h2 class="purpleheader">Printed Poster</h2>

<p>
<a href="alexa-1.2-small.jpg"><img src="alexa-1.2-tiny.jpg" border=0 style="float:left; margin-left: 1em; margin-right: 1em;"></a>
The graphic has been made into a 24x36 inch poster. Click to see a larger version.
</p>

<p> We have only printed 15 posters (for Nmap developers) so far, but
we're considering an offset print run if there is enough demand.  If
you might be interested in buying a physical copy of the poster,
please fill out this short form:</p>

<form action="poster-interest" method="POST">
<table style="background-color: #f5f1f9">
<tr>
<td>
Email address (used only to contact you about posters)<br>
<input type="text" name="email" len=60>
</td>
</tr>
<tr>
<td>
Country (for shipping cost estimate)<br>
<select name=country>
<option value=unanswered>Country
<option value=Australia>Australia
<option value=Brazil>Brazil
<option value=Canada>Canada
<option value=China>China
<option value=France>France
<option value=Germany>Germany
<option value=India>India
<option value=Italy>Italy
<option value=Japan>Japan
<option value=Russia>Russia
<option value=SouthKorea>South Korea
<option value=Spain>Spain
<option value=Sweden>Sweden
<option value=UnitedKingdom>United Kingdom
<option value=UnitedStates>United States
<option value=separator>-----------
<option value=Afghanistan>Afghanistan
<option value=Albania>Albania
<option value=Algeria>Algeria
<option value=Andorra>Andorra
<option value=Angola>Angola
<option value=Anguilla>Anguilla
<option value=AntiguaandBarbuda>Antigua and Barbuda
<option value=Argentina>Argentina
<option value=Armenia>Armenia
<option value=Aruba>Aruba
<option value=Australia>Australia
<option value=Austria>Austria
<option value=Azerbaijan>Azerbaijan
<option value=Bahamas>Bahamas
<option value=Bahrain>Bahrain
<option value=Bangladesh>Bangladesh
<option value=Barbados>Barbados
<option value=Belarus>Belarus
<option value=Belgium>Belgium
<option value=Belize>Belize
<option value=Benin>Benin
<option value=Bermuda>Bermuda
<option value=Bhutan>Bhutan
<option value=Bolivia>Bolivia
<option value=BosniaandHerzegovina>Bosnia and Herzegovina
<option value=Botswana>Botswana
<option value=Brazil>Brazil
<option value=Brunei>Brunei
<option value=Bulgaria>Bulgaria
<option value=BurkinaFaso>Burkina Faso
<option value=Burundi>Burundi
<option value=Cambodia>Cambodia
<option value=Cameroon>Cameroon
<option value=Canada>Canada
<option value=CanaryIsland>Canary Island
<option value=CapeVerde>Cape Verde
<option value=CentralAfricanRepublic>Central African Republic
<option value=Chad>Chad
<option value=Chile>Chile
<option value=China>China
<option value=Colombia>Colombia
<option value=Comoros>Comoros
<option value=Congo>Congo
<option value=CostaRica>Costa Rica
<option value=Croatia>Croatia
<option value=Cuba>Cuba
<option value=Curacao>Curacao
<option value=CzechRepublic>Czech Republic
<option value=Denmark>Denmark
<option value=Djibouti>Djibouti
<option value=Dominica>Dominica
<option value=DominicanRepublic>Dominican Republic
<option value=Ecuador>Ecuador
<option value=Egypt>Egypt
<option value=ElSalvador>El Salvador
<option value=Eq.Guinea>Eq. Guinea
<option value=Eritrea>Eritrea
<option value=Estonia>Estonia
<option value=Ethiopia>Ethiopia
<option value=Finland>Finland
<option value=France>France
<option value=G.Bissau>G.Bissau
<option value=Gabon>Gabon
<option value=Gambia>Gambia
<option value=Georgia>Georgia
<option value=Germany>Germany
<option value=Ghana>Ghana
<option value=Gibraltar>Gibraltar
<option value=GrandCayman>Grand Cayman
<option value=Greece>Greece
<option value=Greenland>Greenland
<option value=Grenada>Grenada
<option value=Guadeloupe>Guadeloupe
<option value=Guatemala>Guatemala
<option value=Guinea>Guinea
<option value=Guyana>Guyana
<option value=Haiti>Haiti
<option value=Honduras>Honduras
<option value=HongKong>Hong Kong
<option value=Hungary>Hungary
<option value=Iceland>Iceland
<option value=India>India
<option value=Indonesia>Indonesia
<option value=Iran>Iran
<option value=Iraq>Iraq
<option value=Ireland>Ireland
<option value=Israel>Israel
<option value=Italy>Italy
<option value=IvoryCoast>Ivory Coast
<option value=Jamaica>Jamaica
<option value=Japan>Japan
<option value=Jordan>Jordan
<option value=Kazakhstan>Kazakhstan
<option value=Kenya>Kenya
<option value=Kuwait>Kuwait
<option value=Kyrgyzstan>Kyrgyzstan
<option value=Laos>Laos
<option value=Latvia>Latvia
<option value=Lebanon>Lebanon
<option value=Lesotho>Lesotho
<option value=Liberia>Liberia
<option value=Libya>Libya
<option value=Liechtenstein>Liechtenstein
<option value=Lithuania>Lithuania
<option value=Luxembourg>Luxembourg
<option value=Macedonia>Macedonia
<option value=Madagascar>Madagascar
<option value=Madeira>Madeira
<option value=Malawi>Malawi
<option value=Malaysia>Malaysia
<option value=Maldives>Maldives
<option value=Mali>Mali
<option value=Malta>Malta
<option value=Martinique>Martinique
<option value=Mauritania>Mauritania
<option value=Mauritius>Mauritius
<option value=Mayotte>Mayotte
<option value=Mexico>Mexico
<option value=Moldova>Moldova
<option value=Monaco>Monaco
<option value=Montserrat>Montserrat
<option value=Morocco>Morocco
<option value=Mozambique>Mozambique
<option value=Namibia>Namibia
<option value=Nepal>Nepal
<option value=Netherlands>Netherlands
<option value=NetherlandsAntilles>Netherlands Antilles
<option value=NewZealand>New Zealand
<option value=Nicaragua>Nicaragua
<option value=Niger>Niger
<option value=Nigeria>Nigeria
<option value=NorthernAfrica>Northern Africa
<option value=Norway>Norway
<option value=Oman>Oman
<option value=Pakistan>Pakistan
<option value=Palau>Palau
<option value=Palestine>Palestine
<option value=Panama>Panama
<option value=PapuaNewGuinea>Papua New Guinea
<option value=Paraguay>Paraguay
<option value=Peru>Peru
<option value=Philippines>Philippines
<option value=Poland>Poland
<option value=Portugal>Portugal
<option value=PuertoRico>Puerto Rico
<option value=Qatar>Qatar
<option value=Reunion>Reunion
<option value=Romania>Romania
<option value=Russia>Russia
<option value=Rwanda>Rwanda
<option value=S.TomeandPrinicipe>S.Tome and Prinicipe
<option value=SanMarino>San Marino
<option value=SaudiArabia>Saudi Arabia
<option value=Senegal>Senegal
<option value=SerbiaandMontenegro>Serbia and Montenegro
<option value=Seychelles>Seychelles
<option value=Sierra-Leone>Sierra-Leone
<option value=Singapore>Singapore
<option value=SintMaarten>Sint Maarten
<option value=SlovakRepublic>Slovak Republic
<option value=Slovenia>Slovenia
<option value=Somalia>Somalia
<option value=SouthAfrica>South Africa
<option value=SouthKorea>South Korea
<option value=Spain>Spain
<option value=SriLanka>Sri Lanka
<option value=St.KittsandNevis>St. Kitts and Nevis
<option value=St.Lucia>St. Lucia
<option value=St.VincentandTheGrenadines>St. Vincent and The Grenadines
<option value=Sudan>Sudan
<option value=Suriname>Suriname
<option value=Swaziland>Swaziland
<option value=Sweden>Sweden
<option value=Switzerland>Switzerland
<option value=Syria>Syria
<option value=Taiwan>Taiwan
<option value=Tanzania>Tanzania
<option value=Thailand>Thailand
<option value=Togo>Togo
<option value=TrinidadyTobago>Trinidad y Tobago
<option value=Tunisia>Tunisia
<option value=Turkey>Turkey
<option value=Turkmenistan>Turkmenistan
<option value=TurksandCaicosIslands>Turks and Caicos Islands
<option value=UAE>UAE
<option value=Uganda>Uganda
<option value=Ukraine>Ukraine
<option value=UnitedKingdom>United Kingdom
<option value=UnitedStates>United States
<option value=Uruguay>Uruguay
<option value=Uzbekistan>Uzbekistan
<option value=VaticanCityState>Vatican City State
<option value=Venezuela>Venezuela
<option value=Vietnam>Vietnam
<option value=VirginIslands>Virgin Islands
<option value=Yemen>Yemen
<option value=Zambia>Zambia
<option value=Zimbabwe>Zimbabwe
</select>
</td>
</tr>
<tr>
<td>
<input type="submit">
</td>
</tr>
</table>
</form>

<p>
For downloads of programs and data files, go to
<a href="http://www.bamsoftware.com/computers/favicon/">this page</a>.
</p>

<br><br><h2 class="purpleheader" id="faq">FAQ</h2>
<dl>
<dt id="faq-1"><b>Why are some sites not found?</b></dt>
<dd>There are a few possible causes. First, the site may not have been
among the top million at the time the survey was done.
<a href="http://bamsoftware.com/computers/favicon/top-1m-20100119.csv.gz">Check
the data file</a> to see if it was present. Second, the site may have
changed its icon since the survey was done. This page downloads the
current icon of the site you type in, and looks up its hash in a
database. Failing that, it will look up the site name in the database,
but that only works if you use the exact same name we did when doing the
survey. Third, it's possible that the site timed out or didn't have an
icon at the time of the survey. Fourth, this page limits the size of the
icons it will download. If an icon file is too big, it won't be found.
Calculate the MD5 sum of the icon yourself and enter it in the search
box.</dd>
<p><dt id="faq-2"><b>Why are some icons (Amazon, Bing, Baidu) so small?</b></dt>
<dd>This usually indicates that the main site timed out during the
survey, and only less popular sites using the same icon responded.  In
other words, it represents a data collection error. For example,
baidu.com didn't respond, but baidu.hk and baidu.jp did, and so what
would have been one of the biggest icons is instead small.
<a href="http://www.bamsoftware.com/computers/favicon/">See this
page</a> for more technical details and caveats. We didn't fudge the
data after the survey or attempt to fill in any obviously "missing"
icons.</dd>
<p><dt id="faq-3"><b>Why are there two "&#x042f" Yandex icons?</b></dt>
<dd>Look closely. The icons are different. The uniqueness of icons is
based on their MD5 hash, so even icons that are visually identical may
in fact be different. Remember, the original impetus for this scan was
to improve the hash database of an
<a href="http://nmap.org/book/nse.html">Nmap Scripting Engine</a>
script.</dd>
</dl>

<h2 class="purpleheader">Credits</h2>
<p>Programming and design was done by David Fifield and
scanning performed by Brandon Enright.</p>

<h2 class="purpleheader">Nmap Site Navigation</h2>

<CENTER>
<!--#include virtual="/shared/templates/nmap_pagemap.html" -->
</CENTER>
<!--#include virtual="/shared/templates/standard_body_bottom.html" -->
"""

sys.stdout.flush()