/* 1000 Points of Light (an interactive drawing project) Phase 1 By AnDYmaN (anti-copyright 1997) This little applet will just write some random data in a *special* format. The special format will not be a list of the coordinates of our 1000 points of light; because we eventually will be sending this data by QUERY_STRING to a CGI program. (That way, each person can make his own picture in a database we'll keep.) You see, 1000 X and 1000 Y numbers would end up creating strings like: URL?23,54,89,150,34,203,50,9,234,133,... \ / \ / \ / \ / \ / \ | / / / \ | / / / five x,y pairs, describing only five of our 1000 points of light. This would require a *long* QUERY_STRING because it's taken us 32 characters to describe only five of our 1000 pixels. Sending 1000 coordinates this way would create a string of about 200x32=6,400 characters. This is almost certainly over the limit of what we can send via the GET method to a CGI script. But if we encode the coordinates more cleverly, we may be able to send the whole image via the GET method. Here's what I propose (feel free to develop an even cleverer algorithm): we will keep track of whether the pixels in our 50x50 window are BLACK (0) or WHITE (1). We will now have 50x50=2500 pixels to keep track of, because the image is 50 wide and 50 tall. Even if we print a string of 0s and 1s, already, 2,500 is less than 6,400! We've cut the data we'll need to about 38% of it's original amount. But we can also take advantage of a sort of "run length compression." Instead of writing: URL?00000000011110101010000000000000 to describe the first 32 pixels, we could write: URL?B9W4B1W1B1W1B13 This reduces our overall data, once again, to about half it's original length. In other words, we'll be looking at about 1,250 characters in our QUERY_STRING, but it will STILL describe the same 50x50 image with 1000 points of light. But there's the possibility that the image will be a grey pattern, (010101010101) which would make our "compressed" format up to 5000 characters long! (B1W1B1W1 > 0101). Can we do better? Sure we can. Now, recall that an int has 32 bits in it (there may be exceptions to this rule on some computer platforms, but it's commonly the case). We will encode the 0s and 1s in two ints, flipping bits to 1 if to indicate white pixels. A typical string of pixels could look like this: 00000000000000000000000000000100 Where only one of the 32 pixels described by this sequence is not black. That sequence could then be encoded into the first 16-bits of two ints which would each be between 0 and 65536. 0000000000000000 0000000000000100 As a decimal number 0 and a decimal 4, these pixels would reduce to the string: URL?0,4, This would describe 32 consecutive pixels. Many of these sequences of 16 pixels will contain more white pixels (ones) than in the example given. But at the most, our decimal representation will contain 5 characters. Another example sequence, representing 32 boolean values, would be: 01000101010010001001111110001001 Now we'll split this into two parts, each sixteen characters long: 0100010101001000 Part A 1001111110001001 Part B In decimal these binary numbers would be: 8 + 64 + 256 + 1024 + 16348 = 17736 Part A 1 + 8 + 128 + 256 + 512 +1024 + 2048 + 4096 + 32768 = 40841 Part B So, our QUERY_STRING for the first 32 pixels could look like this: URL?17736,40841, Which is only 12 characters. Recall that we will have 50x50=2500 total pixels. We divide that number by 32. This gives 2500/32=78.125. It will take us 79 integers to encode all the pixels in a non-lossy fashion. If each of these ints takes up about 12 characters, then our QUERY_STRING will end up being about 12x79=948. We can assume that these numbers often will be less than 12 characters in length, too, so, in the end we will have a QUERY_STRING that is around 850-900 characters long. We may just be able to write that many characters onto our QUERY_STRING and expect them to arrive at the CGI script. Before we go on and make the little sketch pad that will read and export this *special* format, we'd better make an algorithm that will convert the image's data to this encoded QUERY_STRING. First we'll create a 2500-pixel-long array of random 0s and 1s. Then we'll print the encoded QUERY_STRING to the console. (That string can be archived on the server, and later sent by a CGI script to another applet. */ public class write extends java.applet.Applet { int array[]; // declare an array globally, since // we'll use it in two different methods public void init(){ // make an array of ints that has // 50x50=2500 parts array = new int[2500]; // initialize array values to be all zeros for(int i=0;i<2500;i++) array[i] = 0; // create a "random" object r from which we // will "extract" a series of random numbers java.util.Random r = new java.util.Random(); int n; // to be used below for(int i=0;i<1000;i++){ n = r.nextInt()%1250 + 1250; // 0 > n > 2500 while(array[n]==1){ n = r.nextInt()%1250 + 1250; } // the while loop makes sure the pixel isn't // already white, since we want 1000 white pixels array[n]=1; } // keep repeating until i=1000 // Now our array is ready to encode. // (It will also be drawn from the paint() method // when the init() method is done.) // To start with, we will want to create a // second array which will hold our 16-bit // sequences. We'll need 2500/16=l57 (Well, 156.25) // So we'll declare a new array: int encoded[]; int two[]={ 1,2,4,8,16,32,64,128,256,512,1024,2048, 4096,8192,16384,32768 }; // the powers of two up to 16 encoded = new int[157]; n = 0; // we'll reuse n to step through // the 2500-pixel-long array // Now we need a loop that will cycle 157 times. for(int i=0;n<2500-16;i++){ for(int j=0;j<16;j++){ if(array[n++]==1) encoded[i] += two[j]; // If the current pixel is white // we will flip the bit at position j // by adding the power of 2 to the j // to the int encoded[i] } } // Now our encoded[] array is full of values // that we can decrypt later into 2500 black or // white pixel values. So let's write it to // the into a string and print it to the console: StringBuffer QUERY_STRING; // an empty stringbuffer QUERY_STRING = new StringBuffer(); for(int i=0;i<157;i++){ System.out.print(encoded[i]+","); QUERY_STRING.append(encoded[i]+","); } System.out.println(""); System.out.println("Length: "+ QUERY_STRING.length()); } public void paint(java.awt.Graphics g){ java.awt.Image img; // the image we'll put to the screen java.awt.Graphics img_g; img = createImage(50,50); img_g = img.getGraphics(); img_g.setColor(java.awt.Color.black); img_g.fillRect(0,0,50,50); img_g.setColor(java.awt.Color.white); for(int i=0;i<2500;i++){ if(array[i]==1){ img_g.drawLine(i%50,i/50,i%50,i/50); //draw white dots } } g.drawImage(img,0,0,500,500,this); // stretch the image to be 500x500 } }