#!/usr/bin/env python
from PIL import Image

def gchannel(Val):
	return (Val >> 4) & 0xE

threshold = 127

def get_color_info(pixels, rng, threshold, exclude={}):
	gencolors = {}
	A = 255
	for idx in rng:
		color = pixels[idx]
		if len(color) == 4:
			(R, G, B, A) = color
		else:
			(R, G, B) = color
		if A > threshold:
			gcolor = (gchannel(R), gchannel(G), gchannel(B))
			if not gcolor in exclude:
				if gcolor in gencolors:
					gencolors[gcolor] += 1
				else:
					gencolors[gcolor] = 1
	glist = [(gencolors[color], color) for color in gencolors]
	glist.sort()
	glist.reverse()
	return glist

def get_color_info_error(pixels, rng, threshold, exclude={}):
	gencolors = {}
	A = 255
	for idx in rng:
		color = pixels[idx]
		if len(color) == 4:
			(R, G, B, A) = color
		else:
			(R, G, B) = color
		if A > threshold:
			gcolor = (gchannel(R), gchannel(G), gchannel(B))
			if not gcolor in exclude:
				if not gcolor in gencolors:
					_,best = best_match(gcolor, (exclude,))
					gencolors[gcolor] = color_dist(gcolor, best)
	glist = [(gencolors[color], color) for color in gencolors]
	glist.sort()
	glist.reverse()
	return glist

def get_color_info_both(pixels, rng, threshold, exclude={}):
	gencolors = {}
	A = 255
	for idx in rng:
		color = pixels[idx]
		if len(color) == 4:
			(R, G, B, A) = color
		else:
			(R, G, B) = color
		if A > threshold:
			gcolor = (gchannel(R), gchannel(G), gchannel(B))
			if not gcolor in exclude:
				if not gcolor in gencolors:
					_,best = best_match(gcolor, (exclude,))
					gencolors[gcolor] = (color_dist(gcolor, best), 1)
				else:
					(dist, count) = gencolors[gcolor]
					gencolors[gcolor] = (dist, count+1)
	glist = [(gencolors[color][0] * gencolors[color][1], color) for color in gencolors]
	glist.sort()
	glist.reverse()
	return glist

def totiles(im, palette):
	pass

def make_palette(im, trans_thresh, max_global, max_line):
	pixels = im.getdata()
	(width, height) = im.size
	colors = get_color_info(pixels, xrange(0, height * width), trans_thresh)
	print len(colors), 'distinct 9-bit colors in image'
	glob_pal = {}
	print 'Static Palette:'
	for idx in xrange(0, min(max_global, len(colors))):
		(count, color) = colors[idx]
		print str(idx) + ':', color, '(used', count, 'times)'
		glob_pal[color] = idx
	line_pals = []
	if max_global < len(colors):
		for line in xrange(0, height):
			linestart = line * width
			#linecolors = get_color_info(pixels, xrange(linestart, linestart+width), trans_thresh, glob_pal)
			#linecolors = get_color_info_error(pixels, xrange(linestart, linestart+width), trans_thresh, glob_pal)
			linecolors = get_color_info_both(pixels, xrange(linestart, linestart+width), trans_thresh, glob_pal)
			line_pal = {}
			for idx in xrange(0, min(max_line, len(linecolors))):
				(count, color) = linecolors[idx]
				line_pal[color] = idx + max_global
			line_pals.append(line_pal)
	return (glob_pal, line_pals, max_global, max_line)

def color_dist(a, b):
	(ra, ga, ba) = a
	(rb, gb, bb) = b
	return (ra-rb)**2 + (ga-gb)**2 + (ba-bb)**2

def best_match(gpixel, pals):
	bestdist = color_dist((0,0,0), (15, 15, 15))
	bestpalidx = 0
	bestcolor = (0,0,0)
	for i in xrange(0, len(pals)):
		pal = pals[i]
		for cur in pal:
			curdist = color_dist(gpixel, cur)
			if curdist < bestdist:
				bestdist = curdist
				bestpalidx = pal[cur]
				bestcolor = cur
	return (bestpalidx, bestcolor)

def trans_image(im, trans_thresh, pal):
	(global_pal, line_pals, _, _) = pal
	pixels = im.getdata()
	(width, height) = im.size
	gpixels = []
	A = 255
	x = 0
	y = 0
	for pixel in pixels:
		if x == width:
			x = 0
			y += 1
			if width % 8:
				for i in xrange(0, 8-(width%8)):
					gpixels.append(0)
		if len(pixel) == 4:
			(R, G, B, A) = pixel
		else:
			(R, G, B) = pixel
		if A > trans_thresh:
			gpixel = (gchannel(R), gchannel(G), gchannel(B))
			if gpixel in global_pal:
				gpixels.append(global_pal[gpixel])
			elif gpixel in line_pals[y]:
				gpixels.append(line_pals[y][gpixel])
			else:
				bestpal,color = best_match(gpixel, (global_pal, line_pals[y]))
				gpixels.append(bestpal)
		else:
			gpixels.append(0)
		x += 1
	if width % 8:
		for i in xrange(0, 8-(width%8)):
			gpixels.append(0)
		width += 8-(width%8)
	if height % 8:
		for y in xrange(0, 8-(height%8)):
			for x in xrange(0, width):
				gpixels.append(0)
		height += 8-(height%8)

	return (width, height, gpixels)

def appendword(b, word):
	b.append(word >> 8)
	b.append(word & 0xff)

def to_tiles(palpix):
	(width, height, pixels) = palpix
	b = bytearray()
	cwidth = width/8
	cheight = height/8
	words = len(pixels)/4
	appendword(b, words)
	appendword(b, cwidth)
	appendword(b, cheight)

	for cy in xrange(0, cheight):
		ystart = cy*8*width
		for cx in xrange(0, cwidth):
			startoff = (cx*8) + ystart
			for row in xrange(0, 8):
				rowoff = startoff + row*width
				for bytecol in xrange(0, 4):
					boff = bytecol * 2 + rowoff
					#print 'boff:', boff, 'len(pixels)', len(pixels), 'cx', cx, 'cy', cy, 'cwidth', cwidth, 'cheight', cheight
					#print 'pixels[boff]:', pixels[boff]
					b.append(pixels[boff] << 4 | pixels[boff+1])
	return b

def add_pal_entries(tiles, pal):
	(global_pal, line_pals, max_global, max_line) = pal
	pal_list = [(0, 0, 0)] * max_global
	for entry in global_pal:
		pal_list[global_pal[entry]] = entry
	for entry in pal_list:
		(R, G, B) = entry
		tiles.append(B)
		tiles.append(G << 4 | R)
	for line in line_pals:
		pal_list = [(0, 0, 0)] * max_line
		for entry in line:
			pal_list[line[entry]-max_global] = entry
		for entry in pal_list:
			(R, G, B) = entry
			tiles.append(B)
			tiles.append(G << 4 | R)



def main(argv):
	if len(argv) < 3:
		print "Not enough arguments"
		return
	fname = argv[1]
	static_colors = 8
	dynamic_colors = 8
	if len(argv) > 3:
		static_colors = int(argv[3])
		dynamic_colors = min(dynamic_colors, 16-static_colors)
	if len(argv) > 4:
		dynamic_colors = int(argv[4])
	if dynamic_colors + static_colors > 16:
		print "No more than 16 combined dynamic and static colors are allowed"
		return
	im = Image.open(fname)
	pal = make_palette(im, threshold, static_colors, dynamic_colors)
	palpix = trans_image(im, threshold, pal)
	tiles = to_tiles(palpix)
	bits = add_pal_entries(tiles, pal)
	out = open(argv[2], 'wb')
	out.write(tiles)

if __name__ == '__main__':
	import sys
	main(sys.argv)