import java.util.*;
import java.awt.image.*;
import java.io.*;
import javax.imageio.*;

public class ChipFont {

    static final String FONT_NAME = "chipfontraw.png";
    static final String OUT_NAME  = "compressed.png";
    static final String CHARSET   = "ABCDEFGHIJKLMNOPQRSTUVWXYZ!' ";
    static final String TEXT      = "YOU'RE A    LOOSE CANNON JONES! TURNIN YOUR GUN AND BADGE!";
    static final int CHAR_HEIGHT  = 5;

    public static void main(String[] args) throws Exception {
        // load image and split it apart into pixel lists for each character
        BufferedImage font = ImageIO.read(new File(FONT_NAME));
        List<Chunk> chunks = new ArrayList<Chunk>();
        {
            int offset = 0;
            for(char c : CHARSET.toCharArray()) {
                Chunk chunk = new Chunk();
                chunks.add(chunk);
                for(int y = 0; y < CHAR_HEIGHT; y++) {
                    byte row = 0;
                    for(int x = 0; x < 8; x++) {
                        int pixel = font.getRGB(x, y+offset);
                        row = (byte)((row << 1) | (((pixel & 0xFF000000) != 0) ? 1 : 0));
                    }
                    chunk.data.add(row);
                }
                chunk.offsets.put(c, 0);
                offset += CHAR_HEIGHT;
            }
        }

        // compress the bitmap
        // by greedily overlapping pairs of chunks
        // until only one chunk remains.
        while(chunks.size() > 1) {
            Chunk bestA = null;
            Chunk bestB = null;
            Chunk bestC = null;
            int bestSize = Integer.MAX_VALUE;

            for(Chunk a : chunks) {
                for(Chunk b : chunks) {
                    if (a == b) { continue; }
                    Chunk c = a.overlap(b);
                    if (c.size() >= bestSize) { continue; }
                    bestA = a;
                    bestB = b;
                    bestC = c;
                    bestSize = c.size();
                }
            }

            chunks.remove(bestA);
            chunks.remove(bestB);
            chunks.add(bestC);
        }

        // print out the compressed bitmap in hex
        System.out.format("final bitmap data: (%d bytes)%n", chunks.get(0).size());
        {
            int z = -1;
            for(byte b : chunks.get(0).data) {
                System.out.format("0x%02X ", b);
                if (++z % 16 == 15) { System.out.println(); }
            }
        }
        System.out.println();

        // print out the converted text
        System.out.format("final text data: (%d bytes)%n", TEXT.length());
        {
            int z = -1;
            for(char c : TEXT.toCharArray()) {
                System.out.format("0x%02X ", chunks.get(0).offsets.get(c));
                if (++z % 16 == 15) { System.out.println(); }
            }
        }
        System.out.println();

        // write out our final font as a bitmap for visual inspection
        BufferedImage out = new BufferedImage(8, chunks.get(0).size(), BufferedImage.TYPE_BYTE_BINARY);
        {
            int y = 0;
            for(byte b : chunks.get(0).data) {
                for(int x = 0; x < 8; x++) {
                    out.setRGB(x, y,
                        ((b >> (7-x))&1) != 0 ? 0xFF000000 : 0xFFFFFFFF
                    );
                }
                y++;
            }
        }
        ImageIO.write(out, "PNG", new File(OUT_NAME));

        System.exit(0);
    }

}

class Chunk {
    List<Byte> data = new ArrayList<>();
    Map<Character, Integer> offsets = new HashMap<>();

    int size() {
        return data.size();
    }

    private Chunk overlap(Chunk next, int index) {
        Chunk ret = new Chunk();
        ret.data.addAll(data);
        ret.offsets.putAll(offsets);

        for(int z = index; z < next.data.size(); z++) {
            ret.data.add(next.data.get(z));
        }
        for(Map.Entry<Character, Integer> e : next.offsets.entrySet()) {
            ret.offsets.put(e.getKey(), e.getValue() + data.size() - index);
        }
        return ret;
    }

    private boolean canOverlap(Chunk next, int index) {
        if (index > size()) { return false; }
        for(int z = 0; z < index; z++) {
            byte a = data.get(data.size() - index + z);
            byte b = next.data.get(z);
            if (a != b) { return false; }
        }
        return true;
    }

    Chunk overlap(Chunk next) {
        for(int index = next.size(); index > 0; index--) {
            if (canOverlap(next, index)) {
                return overlap(next, index);
            }
        }
        return overlap(next, 0);
    }
}