Computer Science Canada

Insectoid's Summer Programming Challenge

Author:  Insectoid [ Tue Apr 19, 2011 5:28 pm ]
Post subject:  Insectoid's Summer Programming Challenge

So, I was watching a first-year Harvard lecture on C programming the other day. One of the assignments given to the students involved writing a program that takes a bmp file and a number n as input, and outputs the image multiplied in area by n to a bmp file. It was then that I realized that I had never done I/O on anything but text files. I didn't have a clue how other file types worked.


My challenge for compsci.ca users (primarily students, but other people to, if you want) this summer is to write a program that does something with a common file format. A bitmap is a good place to start, as it's a fairly basic format. Add a watermark, change the colors, be creative! After that, move into more involved formats such as ZIP files or other compression formats, MS Word documents, etc. Maybe even design your own format for something.

This isn't a contest. It's a challenge. Everybody wins, unless you don't learn anything. Then only everyone who learned something wins.

~Insectoid

Author:  Raknarg [ Tue Apr 19, 2011 5:59 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

Is turing legal? Razz

Author:  Tony [ Tue Apr 19, 2011 6:05 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

As a file format?

Author:  Insectoid [ Tue Apr 19, 2011 6:19 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

Use whatever language you want. The objective is that it isn't a text format- this includes .txt, .t, .cpp, .rb, etc.

Author:  Dratino [ Wed Apr 20, 2011 8:55 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

I've worked with Microsoft BMP files before, but only to generate visual versions of certain types of output.

Author:  SNIPERDUDE [ Thu Apr 21, 2011 12:09 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

Sounds fun, I might take a stab at it.
I haven't worked with anything other than text files as well (besides my own encrypted "text" files for program saves).

Author:  RandomLetters [ Thu Apr 21, 2011 9:50 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

I'm trying to write the header input for a bmp file editor right now in java. How can one convert a byte array into an integer?

(stupid, stupid signed integers >>)

Author:  DemonWasp [ Thu Apr 21, 2011 10:28 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

Err...

long i = b[3] << 24 | b[2] << 16 | b[1] << 8 | b[0]

You may have to fiddle with the indicies, depending on whether the source is big or little endian and whether or not I've screwed them up.

Alternately, DataInputStream, which you can extend to fill in the missing unsigned-int, unsigned-long logic (why they didn't include those is beyond me).

Author:  btiffin [ Thu Apr 21, 2011 11:14 pm ]
Post subject:  Re: Insectoid's Summer Programming Challenge

Do me a favour;
code:

       identification division.
       program-id. indexing.

       environment division.
       configuration section.

       input-output section.
       file-control.
          select optional indexing
          assign to "indexing.dat"
          organization is indexed
          access mode is dynamic
          record key is keyfield of indexing-record
              alternate record key is splitkey of indexing-record
              with duplicates
          .

      *> ** OpenCOBOL does not yet support split keys **
      *>  alternate record key is newkey
      *>      source is first-part of indexing-record
      *>                last-part of indexing-record
      *>      with duplicates

       data division.
       file section.
       fd indexing.
       01 indexing-record.
          03 keyfield          pic x(8).
          03 splitkey.
             05 first-part     pic 99.
             05 middle-part    pic x.
             05 last-part      pic 99.
          03 data-part         pic x(54).


learn some of this. If you ever want to work at a bank, insurance company or government agency, understanding the above code can get you a great big resume++
Cheers

Author:  RandomLetters [ Fri Apr 22, 2011 1:13 pm ]
Post subject:  Re: RE:Insectoid\'s Summer Programming Challenge

DemonWasp @ Thu Apr 21, 2011 10:28 pm wrote:
Err...

long i = b[3] << 24 | b[2] << 16 | b[1] << 8 | b[0]

You may have to fiddle with the indicies, depending on whether the source is big or little endian and whether or not I've screwed them up.

Alternately, DataInputStream, which you can extend to fill in the missing unsigned-int, unsigned-long logic (why they didn't include those is beyond me).


Ah, I got it, thanks!
All the bytes were in reverse order Razz

Author:  DemonWasp [ Fri Apr 22, 2011 1:43 pm ]
Post subject:  Re: Insectoid's Summer Programming Challenge

btiffin @ Thu Apr 21, 2011 11:14 pm wrote:
learn some of this. If you ever want to work at a bank, insurance company or government agency, understanding the above code can get you a great big resume++


I suppose it's a good thing I never want to work for a bank, insurance company, or government agency, because that code is terrifyingly ugly. Not that these organizations generally do any better in any other language.

Author:  DtY [ Fri Apr 22, 2011 7:44 pm ]
Post subject:  Re: RE:Insectoid\'s Summer Programming Challenge

RandomLetters @ Fri Apr 22, 2011 1:13 pm wrote:
Ah, I got it, thanks!
All the bytes were in reverse order Razz
That's the endianess, this great computer science concept in which you can put the bytes in any order because it doesn't matter to the computer. You never put the individual bits in the byte backward though.

I might be missing something, but is there any useful reason to use little endian?

Author:  ultimatebuster [ Sat Apr 23, 2011 11:40 am ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

isn't this just non-text binary formats?

Author:  Insectoid [ Sat Apr 23, 2011 11:52 am ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

Pretty much. But you have to deal with things you usually don't with text files. Most languages have advanced functions for dealing with text (fscanf & getchar in C, for example). With non-text formats you're limited to raw byte reading and writing* (fread and fwrite in C), and all the formatting has to be done yourself. Also, doing this forces you to learn about how files are stored on a drive, which isn't really taught in school until 2nd year uni or higher (at least 2nd year- I still haven't been taught it).

*Yes, I know libraries exist to read popular formats, but that would defeat the purpose of this challenge.

Author:  ultimatebuster [ Sat Apr 23, 2011 1:17 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

I'm not sure if Python can write non-text format via file.write

nm it can. though i think i has to be direct HEX code or via struct.

Following writes a text file in binary directly.
code:

with open("test.dat", "wb") as f: f.write('\x75\x6C\x74\x69\x6D\x61\x74\x65\x62\x75\x73\x74\x65\x72')

Author:  DtY [ Sat Apr 23, 2011 5:23 pm ]
Post subject:  Re: RE:Insectoid\'s Summer Programming Challenge

ultimatebuster @ Sat Apr 23, 2011 1:17 pm wrote:
I'm not sure if Python can write non-text format via file.write

nm it can. though i think i has to be direct HEX code or via struct.

Following writes a text file in binary directly.
code:

with open("test.dat", "wb") as f: f.write('\x75\x6C\x74\x69\x6D\x61\x74\x65\x62\x75\x73\x74\x65\x72')
You can also use ord() to convert a single character to it's ordinal code (the character's numeric value) and chr() to go back.

Author:  RandomLetters [ Sat Apr 23, 2011 7:30 pm ]
Post subject:  Re: Insectoid's Summer Programming Challenge

Well, finished the program to load a 24 bit bitmap, and apply a tunnel effect, like that terrible, terrible feature in ipad photobooth Razz
It's still extremely slow to something like MS paint however, which most of the time is taken because of loading the bitmap into an array.

code:
       
public void loadBmpPixelArray() throws IOException {
                FileInputStream in = new FileInputStream(file);
               
                bmpPixelArray = new byte[Math.abs(bmpInfoHeader.height)]
                                          [Math.abs(bmpInfoHeader.width)]
                                           [3];
               
                for(int i = 0; i < bmpHeader.offset; i++) {                             //reads in bytes from offset of bitmap
                        in.read();
                }
               
                byte[] buffer = new byte[(bmpInfoHeader.width % 4)];          //buffer at the end of each row to keep multiple of 4

                if(bmpInfoHeader.height >= 0) {                                          //check sign of "height" info, if it's positive, the image is "upside down"
                        for(int r = bmpPixelArray.length - 1; r >= 0; r--) {
                                for(byte[] bmpPixel : bmpPixelArray[r]) {
                                        in.read(bmpPixel);                                      //reads 3 bytes into the pixel array
                                }
                                in.read(buffer);
                        }
                } else {
                        for(int r = 0; r < bmpPixelArray.length; r++) {             //not upside down
                                for(byte[] bmpPixel : bmpPixelArray[r]) {
                                        in.read(bmpPixel);
                                }
                                in.read(buffer);
                        }
                }
                bmpOriginal = bmpPixelArray.clone();
        }

Is there any way to optimize this? Currently, I have a 2D array of pixels, which are themselves an array of 3 bytes.

Author:  DemonWasp [ Sun Apr 24, 2011 10:28 am ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

BufferedInputStream:

code:

InputStream in = new BufferedInputStream ( new FileInputStream ( file ) );

// Or, for extra fun:
DataInputStream in = new DataInputStream ( new BufferedInputStream ( new FileInputStream ( file ) ) );

// that last one allows you to read whole integers and so on easily


Also, don't forget to close your input streams when you're done with them.

Author:  DtY [ Sun Apr 24, 2011 12:07 pm ]
Post subject:  Re: Insectoid's Summer Programming Challenge

RandomLetters @ Sat Apr 23, 2011 7:30 pm wrote:
Well, finished the program to load a 24 bit bitmap, and apply a tunnel effect, like that terrible, terrible feature in ipad photobooth Razz
It's still extremely slow to something like MS paint however, which most of the time is taken because of loading the bitmap into an array.

code:
       
---snip

Is there any way to optimize this? Currently, I have a 2D array of pixels, which are themselves an array of 3 bytes.
There's a lot of overhead in using an array for each pixel. Instead, make each pixel a single integer, made up of red<<16+green<<8+blue. You'll have to use some weird bitmasking stuff to get the individual components, but it will be a lot more space efficient. It may seem odd at first that storing 24 bits in 32 bits is more space efficient, but to creating an array requires creating a pointer, which is itself 32 bits, and then 8 bits for each index in the array.

Author:  RandomLetters [ Sat Apr 30, 2011 9:01 pm ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

Thank's for the advice. It's almost instantaneous now.

Here's the mostly complete product. Bit operations are surprisingly useful.

Java:

import java.applet.*;
import java.awt.*;
import java.io.*;
import javax.swing.JFileChooser;

//by randomletters
public class BitmapEditor extends Applet {
        File file;
        BitmapHeader bmpHeader;
        BitmapInfoHeader bmpInfoHeader;
        int [][] bmpPixelArray;
        boolean isCleared = false;
        /**
         * @param args
         */
        public void init() {
                JFileChooser fileChooser = new JFileChooser();
                int fcValue = fileChooser.showOpenDialog(this);
                System.out.println();
                if(fcValue == JFileChooser.APPROVE_OPTION) {
                        file = fileChooser.getSelectedFile();
                        try {
                                System.out.println("opening");
                                loadBmpHeader();
                                System.out.println("loading");
                                loadBmpPixelArray();
                                System.out.println("applying effect");
                                applyTunnelEffect();
                                this.setSize(Math.abs(bmpInfoHeader.width), Math.abs(bmpInfoHeader.height));
                        } catch (Exception e) {
                                System.out.println(e.getMessage());
                                e.printStackTrace();
                        }
                }
        }
       
        //makes the circle tunnel effect on pictures by changing pixels
        public void applyTunnelEffect() {
                int r = bmpPixelArray.length/3;
                int xC = bmpPixelArray[0].length/2;
                int yC = bmpPixelArray.length/2;
                int dx, dy;
                int x1, y1;
                double angle;
               
                int[][] bmpOriginal = new int[bmpPixelArray.length][bmpPixelArray[0].length];
                for(int i = 0; i < bmpOriginal.length; i++) {
                        bmpOriginal[i] = bmpPixelArray[i].clone();
                }
               
                for(int y = 0; y < bmpPixelArray.length; y++) {
                        for(int x = 0; x < bmpPixelArray[y].length; x++) {
                                dx = x-xC;
                                dy = y-yC;
                                if(dx*dx + dy*dy > (r)*(r)) {
                                        angle = Math.atan(dy/(double)dx);
                                        if(dx < 0) {
                                                angle += Math.PI;
                                        }
                                        x1 = (int) (xC + r*Math.cos(angle));
                                        y1 = (int) (yC + r*Math.sin(angle));
                                        bmpPixelArray[y][x] = bmpOriginal[y1][x1];
                                }
                        }
                }
        }
        public void loadBmpPixelArray() throws IOException {
                BufferedInputStream in = new BufferedInputStream(new FileInputStream(file));
               
                bmpPixelArray = new int[Math.abs(bmpInfoHeader.height)]
                                          [Math.abs(bmpInfoHeader.width)];
                System.out.println(bmpPixelArray.length);
                System.out.println(bmpPixelArray[0].length);
               
                for(int i = 0; i < bmpHeader.offset; i++) {
                        in.read();
                }
               
                byte[] buffer = new byte[(bmpInfoHeader.width % 4)];
                System.out.println("Buffer length: " + buffer.length);
               
                if(bmpInfoHeader.height >= 0) { //upside down
                        for(int r = bmpPixelArray.length - 1; r >= 0; r--) {
                                for(int c = 0; c < bmpPixelArray[r].length; c++) {
                                        bmpPixelArray[r][c] = (in.read()<<16) | (in.read()<<8) | (in.read());
                                }
                                in.read(buffer);
                        }
                } else {
                        for(int r = 0; r < bmpPixelArray.length; r++) {
                                for(int c = 0; c < bmpPixelArray[r].length; c++) {
                                        bmpPixelArray[r][c] = (in.read()<<16) | (in.read()<<8) | (in.read());
                                }
                                in.read(buffer);
                        }
                }
                in.close();
        }

        public void paint(Graphics g) {
                if(isCleared) {
                        try {
                                for(int r = 0; r < bmpPixelArray.length; r++) {
                                        for(int c = 0; c < bmpPixelArray[r].length; c++) {
                                                g.setColor(new Color((bmpPixelArray[r][c] & 0xFF),
                                                                                                (bmpPixelArray[r][c] & 0xFF00) >>> 8,
                                                                                                (bmpPixelArray[r][c] & 0xFF0000) >>> 16));
                                                g.drawLine(c,r,c,r);
                                        }
                                }
                        } catch(NullPointerException e) {
                                System.out.println("Bitmap failed to load");
                        }
                } else {
                        isCleared = true;
                }
        }
       
        public void loadBmpHeader() throws Exception {
                BufferedInputStream in = new BufferedInputStream(new FileInputStream(file));
                BitmapHeader bmpHeader = new BitmapHeader();
                BitmapInfoHeader bmpInfoHeader = new BitmapInfoHeader();
               
                byte[] buffer2 = new byte[2];
                byte[] buffer4 = new byte[4];
               
                if(!(in.read() == 'B' && in.read() == 'M')) {
                        throw new Exception("Signature is not \"BM\"");
                }
                in.read(buffer4);
                bmpHeader.filesize = unsignedIntToLong(buffer4);
                in.read(buffer2);
                bmpHeader.reserved1 = unsignedShortToInt(buffer2);
                in.read(buffer2);
                bmpHeader.reserved2 = unsignedShortToInt(buffer2);
                in.read(buffer4);
                bmpHeader.offset = unsignedIntToLong(buffer4);
               
                in.read(buffer4);
                bmpInfoHeader.headersize = unsignedIntToLong(buffer4);
                in.read(buffer4);
                bmpInfoHeader.width = byteArrayToInt(buffer4);
                in.read(buffer4);
                bmpInfoHeader.height = byteArrayToInt(buffer4);
                in.read(buffer2);
                bmpInfoHeader.nplanes = unsignedShortToInt(buffer2);
                in.read(buffer2);
                bmpInfoHeader.bitspp = unsignedShortToInt(buffer2);
                in.read(buffer4);
                bmpInfoHeader.compresstype = unsignedIntToLong(buffer4);
                in.read(buffer4);
                bmpInfoHeader.imgsize = unsignedIntToLong(buffer4);
                in.read(buffer4);
                bmpInfoHeader.hres = byteArrayToInt(buffer4);
                in.read(buffer4);
                bmpInfoHeader.vres = byteArrayToInt(buffer4);
                in.read(buffer4);
                bmpInfoHeader.ncolors = unsignedIntToLong(buffer4);
                in.read(buffer4);
                bmpInfoHeader.nimpcolors = unsignedIntToLong(buffer4);
               
                this.bmpHeader = bmpHeader;
                this.bmpInfoHeader = bmpInfoHeader;
               
                System.out.println(this.bmpHeader.toString());
                System.out.println(this.bmpInfoHeader.toString());
                in.close();
        }
       
        public static final int byteArrayToInt(byte[] b) {
        return (b[3] << 24)
        + ((b[2] & 0xFF) << 16)
        + ((b[1] & 0xFF) << 8)
        + (b[0] & 0xFF);
        }
       
        public static final long unsignedIntToLong(byte[] b)
        {
            long l = 0;
            l |= b[3] & 0xFF;
            l <<= 8;
            l |= b[2] & 0xFF;
            l <<= 8;
            l |= b[1] & 0xFF;
            l <<= 8;
            l |= b[0] & 0xFF;
            return l;
        }
            
        public static final int unsignedShortToInt(byte[] b)
        {
            int i = 0;
            i |= b[1] & 0xFF;
            i <<= 8;
            i |= b[0] & 0xFF;
            return i;
        }
}

class BitmapHeader {
    public long filesize;       //size of file (unreliable?)
        public int reserved1;   //unused
        public int reserved2;
        public long offset;          //offset of start of pixel array
       
        @Override public String toString() {
                StringBuilder result = new StringBuilder();
                String NL = System.getProperty("line.separator");
               
                result.append(this.getClass().getName() + " Object {" + NL);
                result.append(" filesize: " + this.filesize + NL);
                result.append(" reserved1: " + this.reserved1 + NL);
                result.append(" reserved2: " + this.reserved2 + NL );
                result.append(" offset: " + this.offset + NL);
                result.append("}");
               
                return result.toString();
        }
}

class BitmapInfoHeader {
    public long headersize;     //size of this header in the file (must 40)
    public int width;      //width of bitmap (in pixels)
    public int height;    //height of bitmap (in pixels)
    public int nplanes; //number of color planes (must 1)
    public int bitspp;  //bits per pixel (color depth)
    public long compresstype;   //compression method (must 0 for this)
    public long imgsize;                //raw bitmap data size
    public int hres;        //horizontal res (pixels/meter)
    public int vres;        //vertical res (pixels/meter)
    public long ncolors;                //number of colors
    public long nimpcolors;     //number of important colors (unused)
   
        @Override public String toString() {
                StringBuilder result = new StringBuilder();
                String NL = System.getProperty("line.separator");
               
                result.append(this.getClass().getName() + " Object {" + NL);
                result.append(" headersize: " + this.headersize + NL);
                result.append(" width: " + this.width + NL);
                result.append(" height: " + this.height + NL );
                result.append(" nplanes: " + this.nplanes + NL);
                result.append(" bitspp: " + this.bitspp + NL);
                result.append(" compresstype: " + this.compresstype + NL);
                result.append(" imgsize: " + this.imgsize + NL);
                result.append(" hres: " + this.hres + NL);
                result.append(" vres: " + this.vres + NL);
                result.append(" ncolors: " + this.ncolors + NL);
                result.append(" nimpcolors: " + this.nimpcolors + NL);
                result.append("}");
               
                return result.toString();
        }
}

Author:  Brightguy [ Mon May 02, 2011 2:47 am ]
Post subject:  Re: RE:Insectoid\'s Summer Programming Challenge

DtY @ Sat Apr 23, 2011 5:23 pm wrote:
You can also use ord() to convert a single character to it's ordinal code (the character's numeric value) and chr() to go back.

In high school the first time I worked with a binary format I opened the file in text mode, translated the characters to their ordinal codes, made the requried modifications, translated the ordinal codes back to characters and outputted the file in text mode. Heh.

Author:  ultimatebuster [ Mon May 02, 2011 9:40 am ]
Post subject:  Re: RE:Insectoid\'s Summer Programming Challenge

Brightguy @ Mon May 02, 2011 2:47 am wrote:
DtY @ Sat Apr 23, 2011 5:23 pm wrote:
You can also use ord() to convert a single character to it's ordinal code (the character's numeric value) and chr() to go back.

In high school the first time I worked with a binary format I opened the file in text mode, translated the characters to their ordinal codes, made the requried modifications, translated the ordinal codes back to characters and outputted the file in text mode. Heh.


Now that's how you do it. Rebel.

Author:  Velocity [ Thu Jan 12, 2012 12:29 am ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

what is the difference between binary and trinary?

Author:  Insectoid [ Thu Jan 12, 2012 7:48 am ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

What's the difference between a bicycle and a tricycle?

Author:  mirhagk [ Thu Jan 12, 2012 10:49 am ]
Post subject:  RE:Insectoid\'s Summer Programming Challenge

1001010101

1210120120


: