Bitpacking?

It’s hard to say without knowing what data you’re packing, but there are a few things I can say:

  1. You’re probably not reducing your information in any significant fashion. Just changing the format is no guarantee of better results.

  2. Whenever you change your compression method, it’s always important to include the decoder into the computations. When I use SuperPackME, I’m accepting a fairly hefty cost in the code for the image decoder, but I more than make up for it in the space saved in the images. I did some tests with oNyx’s JetPack game last year and found that the low number of images he used combined with the low number of colors meant that SuperPack (not the ME version) would actually be larger.

Keep in mind that you’re wrestling with the theory of information. If you don’t fully understand how your data is stored, it can be difficult to further reduce it.

[quote]something to note though, as I said before, I’m not familiar with bitpacking, so it is very possible that the String I made just isnt small enough. Do you know a better method to inline that image? do you have a tutorial for bitpacking? Im always open to learning something new :wink:
[/quote]
Bitpacking is a simple concept. There are 8 bits in a byte, right? So let’s say you have an image that only has two colors. If you store it as a PNG, the PNG will store 4 bytes (32 bits) per pixel. That’s a lot of wasted space for only two values! But if you look at each bit as a color, then you can pack the image into 1 bit per pixel. Here’s the results for a 320x200 pixel image:

PNG: 320x200x32 = 2,048,000 bits = 256,000 bytes
Bitpacked: 320x200x1 = 64,000 bits = 8,000 bytes

Does that help explain the concept? :slight_smile:
[/quote]
duno why you’re getting those 404s, so I’ll just attach it to the post.

Anyway, I sort of see the concept but I have some questions about this:

in my particular scenario it would be:
PNG: 256x82 = 20992 pixels = 671744 bits = 83968 bytes = ~82K
Bitpack: 256x82 = 20992 bits = 2624 bytes = ~2.5K

the change is noticable but why is it when you use pngout (or something similiar) it doesn’t come close to 82K? The clouds.gif file itself is only 632 bytes! That’s even smaller than the bitpack example above, unless I’m not doing math right (I am a bit tired :P).

Also, when you say " look at each bit as a color," what do you mean exactly? (code-wise)

Sorry if I’m missing the obvious :slight_smile:

The PNG file format supports all sorts of palettized pixel formats, not just 8bpp.

http://download.mirror.ac.uk/sites/www.libpng.org/pub/png/spec/1.2/png-1.2-pdg.html

[quote]Anyway, I sort of see the concept but I have some questions about this:

in my particular scenario it would be:
PNG: 256x82 = 20992 pixels = 671744 bits = 83968 bytes = ~82K
Bitpack: 256x82 = 20992 bits = 2624 bytes = ~2.5K

the change is noticable but why is it when you use pngout (or something similiar) it doesn’t come close to 82K? The clouds.gif file itself is only 632 bytes! That’s even smaller than the bitpack example above, unless I’m not doing math right (I am a bit tired :P).
[/quote]
Your math is more or less fine. (Except that your image has three colors, meaning that you need 2 bits per pixel. That, and GIFs only store one byte per pixel, making the original ~20K in size.)

It’s the compression you’re not taking into account. The final GIF or PNG file will be compressed. You’re trying to compare that against the raw bitpacked data. You have to look at both of them both before compression (which you do above) and after compression to see how they compare.

Now your clouds.gif file is 632 bytes. It’s fully compressed down from 20K as one would expect it to be. Now when I run it through SuperPackME, the image actually balloons to 5260 bytes*. But if I run it through Infozip (the same step that is taken during JARing), the image drops to 575 bytes! A 57 byte savings! 7Zip would probably do an even better job.

Now if you have a number of these images, the difference in sizes would quickly add up. In addition, since SuperPackME separates the colors from the image data, the ZIP compressor can find further redundancy across multiple images! To give an example, take a look at the attached image. Your GIF and mine are a total of 1,802 bytes in size. SuperPacking again balloons the size to a whopping 15,256 bytes. But if you compress that with Infozip, you find that it’s only 1,381 bytes! That’s now a 421 byte savings! The compressor does so well because it sees that clouds.gif and camo-desert.gif have very similar image data. (3 colors each, many large fields of color. The values are the same since the actual RGB color is separated.) So it’s able to reuse its compression tokens between them, thus resulting in better compression.

[quote]Also, when you say " look at each bit as a color," what do you mean exactly? (code-wise)
[/quote]
Basically, you modify each byte to put the bits where you want them. i.e.:

  1. Start with the byte: byte b = 0; (b = 00000000 in binary)
  2. Add a bit: b |= 1; (b = 00000001 in binary)
  3. Shift the byte to the left by one position: b <<<= 1; (b = 00000010 in binary)
  4. Go to step 2 and repeat for the next bit.

Now with that figured out, you may want to reread the info on the SuperPack formats. It might make a lot more sense now. Also, the source code is available if you want to see bitpacking in action. :slight_smile:

* (256x82x2 bits = 41,984 bits = 5,248 + (3x3 bytes per color) + (1 byte for color count) + (2 bytes for width and height)) 

[quote=“Anon666,post:2,topic:25938”]
The PNG format supports it, but Java doesn’t. It was one of the first things I tried when I was trying to shrink images for the 4K contest. I found that Java’s ImageIO libraries would throw an exception if the PNG had a low number of colors. I’m guessing that the programmers didn’t have the 4K contest in mind when they wrote the loader code. :slight_smile:

[quote=“jbanes,post:4,topic:25938”]

What’s the Sun Bug number for this?

5098176 - Some PNGs fail to load with ImageIO

Personally, I haven’t considered it that important of an issue. There’s almost no reason to bother with low color images for “normal” J[2|5]SE applicaitons.

Try this out. This code will take a gif file and convert it to a simple string one character per color. It will produce source code in the image.gif.txt file. This code should be inlined in the game source file. I find the not doing the bit shifting and leaving the compression to the compression tools is best. I have tried superpackme and direct image loading. This way looks like the smallest.


import java.awt.image.BufferStrategy;
import java.awt.image.BufferedImage;
import javax.imageio.ImageIO;
import java.util.*;
import java.io.*;

public class Convert
{

    public static void main(String args[])
    {
        try
        {
            String colorMap = "*.@0123456789abcdefghijklmnopqrstuvwzyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
            BufferedImage image;
            int color;
            Hashtable hash = new Hashtable();
            String s;
            image = ImageIO.read(Thread.currentThread().getContextClassLoader().getResource(args[0]));
            int width = image.getWidth();
            int height = image.getHeight();

            PrintWriter out = new PrintWriter(new FileWriter(args[0]+".txt"));

            for(int y = 0;y<height;y++)
            {
                if(y ==0)
                    out.print("data = (\"");
                else
                    out.print("        \"");
                for(int x = 0;x<width;x++)
                {
                    color = image.getRGB(x,y);
                    s = (String) hash.get(Integer.toHexString(color));
                    if(s == null)
                    {
                        if((color & 0xFF000000) == 0xFF000000)
                            s = ""+colorMap.charAt(hash.size());
                        else // use space for transparent pixels
                            s = " ";
                        hash.put(Integer.toHexString(color),s);
                    }

                    out.print(s);
                }
                if(y == height-1)
                    out.println("\").getBytes();");
                else
                    out.println("\"+");
                
            }

            out.println("int[] colors = new int[256];");
            Enumeration enumeration = hash.keys();
            while(enumeration.hasMoreElements())
            {
                String key = (String) enumeration.nextElement();
                out.println("colors['"+hash.get(key)+"'] = 0x"+key+";");
            }

            out.println("image = g.getDeviceConfiguration().createCompatibleImage("+width+","+height+", Transparency.BITMASK);");
            out.println("for(int i = 0;i<data.length;i++)");
            out.println("{");
            out.println("image.setRGB(i%"+width+",i/"+width+",colors[data[i]]);");            
            out.println("}");

            out.flush();
            out.close();
        }
        catch(Exception _ex) { }
    }
}

Rick, I tried that earlier with my own converter, both yours and mine aren’t as small as using the GIF, but thanks for the code anyway :wink:

I will look into your format and source, jbanes, thanks for the link :slight_smile:

That realy is quite pathetically disapppointing to be honest.

Writing a codec for png files is incredibly easy, the documentation on the format is both clear and concise,
and its usage of zlib for compression simplifies the task still further.
It is embarrasing that Sun are having such problems implementing such a trivial codec,
and extremely annoying that a problem raised 16 months ago, that could be fixed by one person in less than a week, has been delayed for so long.
Untold man hours have been wasted by different people detecting and having to work around this bug.

Having said that, my confidence in the team overseeing image manipulation related systems within J2SE is already pretty low.
I recently came to install JAI, and was mystified to find a download page with 16 installers!!!

4 different deployment configurations on 4 different platforms!

This, coupled with the poorly documented, and badly designed JAI API makes me think it doesn’t deserve to be branded as an official Sun product.

If Java was Open Source, issues like this would be fixed within days - not years.

BTW, one note on SuperPackME. I’ve said this before and I’ll say it again. If you use SuperPackME, DO NOT UNDER ANY CIRCUMSTANCE tile your images inside a single file. They should be split up into separate and discrete images. If you combine them, you WILL screw up SuperPackME’s attempts to make your data more compressable. :slight_smile:

Well, demystify yourself. The variety of installers was Sun’s attempt to “help”. They stopped providing them with newer APIs when they realized that it was a Good Thing™ when programmers had to learn how to install libraries. Just download a ZIP file and be happy.

[quote]This, coupled with the poorly documented, and badly designed JAI API makes me think it doesn’t deserve to be branded as an official Sun product.
[/quote]
THAT, I agree with. However, the ImageIO stuff came partly from the work on JAI. So I wouldn’t be too critical of the ancient API. I’m actually surprised that anyone uses it anymore. In most situations where exceptional image processing needs to be performed, it tends to be easier to roll your own solution rather than going with a generic one that might meet your needs.

[quote]If Java was Open Source, issues like this would be fixed within days - not years.
[/quote]
cough Anon666, did you fix it yet? :wink:

;D

Uh huh. Excuses, excuses. ;D

While you can also have 1, 2 and 4 bit its usually smaller with 8 bits. (The compression scheme just works best with 8 bit values.)

I have slightly modifed Rick’s Convert program to achieve another 53 bytes from the orignial version posted with my 4bit input gif.

what i have done it anaylsed the frequency of the ‘printable’ characters in a class file which has gone though proguard and jarg and have most frequent colour palette indecies from the input graphic correspond with the hightest ‘printable’ character frequencies.

This 53 byte saving plus the much shorter code needed to create palette swapped images has reduced the size of the jar a total of 203 bytes.

It may or may not help you with your 4k games, but i offer it for people to use if they wish.


import java.awt.image.BufferedImage;
import java.awt.image.IndexColorModel;

import javax.imageio.ImageIO;
import java.util.*;
import java.io.*;

public class Convert
{

    public static void main(String args[])
    {
        try
        {
            //String colorMap = "*.@0123456789abcdefghijklmnopqrstuvwzyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
            String BestOrderColorMap = "a/etl6rYnoigv`{";
            BufferedImage image;
            int color;
            Hashtable hash = new Hashtable();
            String s;
            image = ImageIO.read(Thread.currentThread().getContextClassLoader().getResource(args[0]));
            int width = image.getWidth();
            int height = image.getHeight();

            PrintWriter out = new PrintWriter(new FileWriter(args[0]+".txt"));
            
            
            // order the colormap to correspond with the best order colour map
            IndexColorModel icm = (IndexColorModel) image.getColorModel();
            int[] palette=new int[icm.getMapSize()];
            icm.getRGBs(palette);
            int[] colourFreq=new int [icm.getMapSize()];
            
            
            for(int i = 0;i<height*width;i++)
            {
            	color = image.getRGB(i%width,i/width);
            	

                	for (int j=0;j<palette.length;j++)
                	{
                		if (color==palette[j]) 
                		{
                			colourFreq[j]++;
                			j=1000;
                		}
                	}

            	

            }
            
            List colourItems=new ArrayList();

    		for (int i=0;i<colourFreq.length;i++)
    		{
    			if (colourFreq[i]>0)
    			{
    			Item freq= new Item();
    			freq.value=i;
    			freq.freq=colourFreq[i];
    			colourItems.add(freq);
    			}
    		}


    		Collections.sort(colourItems);
            
            
    		String colorMap="";
    		
    		for (int i=0;i<colourItems.size();i++)
    		{
    			colorMap=colorMap+BestOrderColorMap.charAt(((Item)colourItems.get(i)).value);
    		}
    		


            for(int y = 0;y<height;y++)
            {
                if(y ==0)
                    out.print("data = (\"");
                else
                    out.print("        \"");
                for(int x = 0;x<width;x++)
                {
                    color = image.getRGB(x,y);
                    s = (String) hash.get(Integer.toHexString(color));
                    if(s == null)
                    {
                        if((color & 0xFF000000) == 0xFF000000)
                            s = ""+colorMap.charAt(hash.size());
                        else // use space for transparent pixels
                            s = " ";
                        hash.put(Integer.toHexString(color),s);
                    }

                    out.print(s);
                }
                if(y == height-1)
                    out.println("\").getBytes();");
                else
                    out.println("\"+");
               
            }

            out.println("int[] colors = new int[256];");
            Enumeration enumeration = hash.keys();
            while(enumeration.hasMoreElements())
            {
                String key = (String) enumeration.nextElement();
                out.println("colors['"+hash.get(key)+"'] = 0x"+key+";");
            }

            out.println("image = g.getDeviceConfiguration().createCompatibleImage("+width+","+height+", Transparency.BITMASK);");
            out.println("for(int i = 0;i<data.length;i++)");
            out.println("{");
            out.println("image.setRGB(i%"+width+",i/"+width+",colors[data[i]]);");           
            out.println("}");

            out.flush();
            out.close();
        }
        catch(Exception _ex) { }
    }
}

This code only works with 4bit images, however if you want to use it for 8bit images my anaylsis data is below, you need only ammend the ‘BestOrderColorMap’ String with this data:

() :
a(97) : 248
/(47) : 174
e(101) : 169
t(116) : 135
l(108) : 104
6(54) : 101
r(114) : 101
Y(89) : 95
n(110) : 87
o(111) : 86
i(105) : 81
g(103) : 77
v(118) : 76
`(96) : 72
?(132) : 64
s(115) : 64
:(58) : 63
?(135) : 63
d(100) : 61
((40) : 60
m(109) : 59
j(106) : 58
I(73) : 53
S(83) : 48
1(49) : 48
;(59) : 47
)(41) : 46
w(119) : 45
L(76) : 43
2(50) : 39
k(107) : 36
c(99) : 36
x(120) : 32
D(68) : 30
p(112) : 30
u(117) : 27
U(85) : 25
W(87) : 24
h(104) : 24
C(67) : 23
(91) : 23
V(86) : 21
R(82) : 21
f(102) : 21
^(94) : 20
@(64) : 19
y(121) : 19
9(57) : 19
7(55) : 19
*(42) : 19
T(84) : 18
.(46) : 17
O(79) : 17
~(126) : 15
: 15
_(95) : 14
,(44) : 14
G(71) : 14
M(77) : 13
3(51) : 13
&(38) : 12
B(66) : 12
(32) : 11
<(60) : 11
!(33) : 11
$(36) : 11
z(122) : 10
A(65) : 10
0(48) : 10
Z(90) : 10
4(52) : 9
E(69) : 9
"(34) : 8
X(88) : 8
8(56) : 8
?(130) : 8
b(98) : 8
q(113) : 7
-(45) : 7
+(43) : 7
?(63) : 6
?(128) : 6
P(80) : 6

(62) : 5
F(70) : 5
K(75) : 5
?(133) : 5
}(125) : 4
J(74) : 4
(92) : 4
#(35) : 3
%(37) : 3
'(39) : 3
|(124) : 2
?(136) : 2
5(53) : 2
(127) : 2
H(72) : 2
?(134) : 2
{(123) : 1
=(61) : 1
Q(81) : 1
?(129) : 1
?(131) : 1
N(78) : 1

You will have to padd out the rest of the BestOrderColorMap with unused printable characters to make the BestOrderColorMap string 256 characters long.

Good wook. I have a version that does the same thing. However I did not think to oder the characters by the freq in the class file. I just picked mine by what I thought the freq was. As I hava a bunch of level data. I ordered mine by that order. I will have to try and look at the class file freq and see if my off the cuff ordering is sub optimal

Can you post the code that prints the class file freq.

Sure, it is not pretty but it does the job :


import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class Anaylze {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new Anaylze(args);
		
		
		
	}
	
	public Anaylze(String[] args)
	{
		File file=new File(args[0]);
		
		HashMap chrCounts=new HashMap();
		Count count;
		try
		{
			FileInputStream fis=new FileInputStream(file);
			
			int readval1=fis.read();

			while (readval1>-1  )
			{
				// ignore byte if not within the printable range
				if (readval1<32 || readval1>135 )
				{
					
				}
				// increment the freq count for the printable byte
				else
				{
					String str=""+(char) readval1;
					count=(Count) chrCounts.get(str);
					if (count==null)
					{
						count=new Count();
						count.val=str;
						count.count=1;
						chrCounts.put(str,count);
					}
					else count.count++;
				}
				readval1=fis.read();
			}
			
				
		}
		catch (IOException e)
		{
			
			e.printStackTrace();
		}
		
		// sort and print
		
		
		ArrayList list=new ArrayList(chrCounts.values());
		Collections.sort(list);
		
		for (int i=0;i<list.size();i++)
		{
			count=(Count) list.get(i);
			System.out.println(count.val+"("+(int) count.val.charAt(0)+") : "+count.count);
		}
		
		System.out.println("As a string:");
		for (int i=0;i<list.size();i++)
		{
			count=(Count) list.get(i);
			System.out.print(count.val);
		}
	}
	
	class Count implements Comparable
	{
		String val;
		int count;
		public int compareTo(Object arg0) {
			// TODO Auto-generated method stub
			if (((Count) arg0).count>count) return 1;
			else if (((Count) arg0).count<count) return -1;
			return 0;
		}
		
	}

}

Thanks, for the code. I tried it but it actually added a few bytes. I guess although it was now using more frequent characters it could not find as many long patterns to compress. Also I was already using the top 3 most frequent charaters so it did not have a chance to improve much. Still it was worth the try.

did you remember to analyze the class with out the embedded graphic. including the embedded graphic will skew the statistics.

In my quest for trying save bytes anywhere i can i have revisited my embedded graphics code.

This new code code does not use a seperate array for the palette, instead it embeds the palette information with the pricture index information. This seems to save a significant amount:


import java.awt.image.BufferedImage;
import java.awt.image.IndexColorModel;

import javax.imageio.ImageIO;
import java.util.*;
import java.io.*;

public class Convert
{

    public static void main(String args[])
    {
        try
        {
            //String BestOrderColorMap = "*.@0123456789abcdefghijklmnopqrstuvwzyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
            String BestOrderColorMap = "a/etl6rYnoigv`{";
            
            BufferedImage image;
            int color;
            Hashtable hash = new Hashtable();
            String s;
            image = ImageIO.read(Thread.currentThread().getContextClassLoader().getResource(args[0]));
            int width = image.getWidth();
            int height = image.getHeight();
            int transparentPixelX=0;
            int transparentPixelY=0;
            
            if (args.length==3)
            {
            	transparentPixelX=Integer.parseInt(args[1]);
            	transparentPixelY=Integer.parseInt(args[2]);
            }

            PrintWriter out = new PrintWriter(new FileWriter(args[0]+".txt"));
            //PrintStream out = System.out;
            
            
            // order the colormap to correspond with the best order colour map
            IndexColorModel icm = (IndexColorModel) image.getColorModel();
            int[] palette=new int[icm.getMapSize()];
            icm.getRGBs(palette);
            int[] colourFreq=new int [icm.getMapSize()];
            
            // determine the colour frequences 
            for(int i = 0;i<height*width;i++)
            {
            	color = image.getRGB(i%width,i/width);
            	

                	for (int j=0;j<palette.length;j++)
                	{
                		if (color==palette[j]) 
                		{
                			colourFreq[j]++;
                			j=1000;
                		}
                	}

            	

            }
            
            List colourItems=new ArrayList();

    		for (int i=0;i<colourFreq.length;i++)
    		{
    			if (colourFreq[i]>0)
    			{
    			Item freq= new Item();
    			freq.value=i;
    			freq.freq=colourFreq[i];
    			colourItems.add(freq);
    			}
    		}

    		// sort the colours
    		Collections.sort(colourItems);
            
            
    		String colorMap="";
    		
    		
    		for (int i=0;i<colourItems.size();i++)
    		{
    			colorMap=colorMap+BestOrderColorMap.charAt(((Item)colourItems.get(i)).value);
    		}
    		
    		ArrayList order=new ArrayList();
    		


    		ByteArrayOutputStream baos=new ByteArrayOutputStream();
    		PrintStream dataPS=new PrintStream(baos);

            for(int y = 0;y<height;y++)
            {
                if(y ==0)
                    dataPS.print("");
                else
                    dataPS.print("        \"");
                for(int x = 0;x<width;x++)
                {
                	String str=null;
                    color = image.getRGB(x,y);
                    s = (String) hash.get(Integer.toHexString(color));
                    if(s == null)
                    {
                            s = ""+colorMap.charAt(hash.size());

                        hash.put(Integer.toHexString(color),s);
                        str=Integer.toHexString(color&0xFFFFFF);
                        int temp=str.length()/2;
                        for (int i=temp;i<3;i++)
                        {
                        	str="00"+str;
                        }
                        order.add(str);
                    }

                    dataPS.print(s);
                    
                    if (str!=null && (x!=transparentPixelX || y!=transparentPixelY)) dataPS.print(str);

                }
                if(y == height-1)
                    dataPS.println("\").getBytes();");
                else
                    dataPS.println("\"+");
               
            }
            
            dataPS.close();
            
            String dataString=new String(baos.toByteArray());
            
            out.print("byte[] data = (\"");
            
            color = image.getRGB(transparentPixelX,transparentPixelY);
            out.print(hash.get(Integer.toHexString(color)));
            
            out.print(dataString);

            out.println("int[] colors = new int[256];");
            
            
            out.println("int dataIndex=0;");
            out.println("int temp;");
            out.println("int i=0;");
            out.println("int transparentColourIndex=data[dataIndex++];");
            out.println("");
            out.println("BufferedImage image = new BufferedImage("+width+","+height+", Transparency.BITMASK);");
            out.println("while (dataIndex<data.length)");
            out.println("{");
            out.println("\ttemp=data[dataIndex++];");
            out.println("\tif (temp!=transparentColourIndex && colors[temp]==0)");
            out.println("\t{");
            out.println("\t\tcolors[temp]=0xFF000000|Integer.parseInt(\"\"+(char)data[dataIndex++]+(char)data[dataIndex++]+(char)data[dataIndex++]+(char)data[dataIndex++]+(char)data[dataIndex++]+(char)data[dataIndex++],16);");
            out.println("\t}");
            out.println("\timage.setRGB(i%"+width+",i/"+width+",colors[temp]);");
            out.println("\ti++;");
            out.println("}");
            


            out.flush();
            out.close();
        }
        catch(Exception _ex) {
        	System.out.println("USAGE: java Convert <image> <transparent Colour X> <transparent Colour Y>");
        	System.out.println("Output: <image>.txt - the data and logic to be embedded into your game.");
        	System.out.println("");
        	System.out.println("The transparent Colour X,Y are the co-ordinates of the colour in the image which is to be deemed transparent.");
        	System.out.println("IMPORTANT: THE X,Y CO-ORDINATES MUST BE OF THE *FIRST* OCCURANCE OF THE TRANSPARENT COLOUR.");
        	System.out.println("These co-ordinates are optional. In their absence the pixel (0,0) will be deemed transparent.");
  //      	System.out.println("have no-transparency set the transparent Colour X to -1 and transparent Colour X to -1");
        	
        	
        }
    }
}