Self-displaying image

Question

Background

There are self-extracting .ZIP files. Typically they have the extension .EXE (and by executing the file they will be extracted) but when renaming them to .ZIP, you can open the file with some ZIP extracting software.

(This is possible because .EXE files require a certain header but .ZIP files require a certain trailer so it is possible to build a file that both has an .EXE header and a .ZIP trailer.)

Your task:

Create a program that creates "self-displaying" image files:

• The program shall take some 64x64 image (at least 4 colors shall be supported) as input and some "combined" file as output
• The output file of the program shall be recognized as image file by common image viewers
• When opening the output file with the image viewer, the input image shall be displayed

• The output file shall also be recognized as executable file for any operating system or computer type

  (If a file for an uncommon operating system or computer is produced, it would be nice if an open-source PC emulator exists. However, this is not required.)

• When executing the output file, the input image shall also be displayed
• It is probable that renaming the file (for example from .PNG to .COM) is necessary
• It is not required that the program and it's output file run on the same OS; the program may for example be a Windows program and output files that can be executed on a Commodore C64.

Winning criterion

• The program that produces the smallest output file wins
• If the size of the output file differs depending on the input image (for example because the program compresses the image), the the largest possible output file created by the program representing a 64x64 image with up to 4 colors counts

By the way

I had the idea for the following programming puzzle when reading this question on StackOverflow.

Answer 1

8086 MS-DOS .COM file / BMP, output file size = 2192 bytes

Encoder

The encoder is written in C. It takes two arguments: Input file and output file. The input file is a 64x64 RAW RGB image (meaning it is simply 4096 RGB triplets). Number of colours is limited to 4, so that the palette can be as short as possible. It is very straight-forward in its doings; it merely builds a palette, packs pixels pairs into bytes and glues it together with pre-made headers and the decoder program.

#include <stdio.h>
#include <stdlib.h>

#define MAXPAL      4
#define IMAGESIZE   64 * 64

int main(int argc, char **argv)
{
    FILE *fin, *fout;
    unsigned char *imgdata = malloc(IMAGESIZE * 3), *outdata = calloc(IMAGESIZE / 2, 1);
    unsigned palette[MAXPAL] = {0};
    int pal_size = 0;

    if (!(fin = fopen(argv[1], "rb")))
    {
        fprintf(stderr, "Could not open \"%s\".\n", argv[1]);
        exit(1);
    }

    if (!(fout = fopen(argv[2], "wb")))
    {
        fprintf(stderr, "Could not open \"%s\".\n", argv[2]);
        exit(2);
    }

    fread(imgdata, 1, IMAGESIZE * 3, fin);

    for (int i = 0; i < IMAGESIZE; i++)
    {
        // BMP saves the palette in BGR order
        unsigned col = (imgdata[i * 3] << 16) | (imgdata[i * 3 + 1] << 8) | (imgdata[i * 3 + 2]), palindex;
        int is_in_pal = 0;

        for (int j = 0; j < pal_size; j++)
        {
            if (palette[j] == col)
            {
                palindex = j;
                is_in_pal = 1;
            }
        }

        if (!is_in_pal)
        {
            if (pal_size == MAXPAL)
            {
                fprintf(stderr, "Too many unique colours in input image.\n");
                exit(3);
            }

            palindex = pal_size;
            palette[pal_size++] = col;
        }

        // High nibble is left-most pixel of the pair
        outdata[i / 2] |= (palindex << !(i & 1) * 4);
    }

    char BITMAPFILEHEADER[14] = {
        0x42, 0x4D,                 // "BM" magic marker
        0x90, 0x08, 0x00, 0x00,     // FileSize
        0x00, 0x00,                 // Reserved1
        0x00, 0x00,                 // Reserved2
        0x90, 0x00, 0x00, 0x00      // ImageOffset
    };

    char BITMAPINFOHEADER[40] = {
        0x28, 0x00, 0x00, 0x00,     // StructSize 
        0x40, 0x00, 0x00, 0x00,     // ImageWidth
        0x40, 0x00, 0x00, 0x00,     // ImageHeight
        0x01, 0x00,                 // Planes
        0x04, 0x00,                 // BitsPerPixel
        0x00, 0x00, 0x00, 0x00,     // CompressionType (0 = none)
        0x00, 0x00, 0x00, 0x00,     // RawImagDataSize (0 is fine for non-compressed,)
        0x00, 0x00, 0x00, 0x90,     // HorizontalRes
                                    //      db 0, 0, 0
                                    //      nop
        0xEB, 0x1A, 0x90, 0x90,     // VerticalRes
                                    //      jmp Decoder
                                    //      nop
                                    //      nop
        0x04, 0x00, 0x00, 0x00,     // NumPaletteColours
        0x00, 0x00, 0x00, 0x00,     // NumImportantColours (0 = all)
    };

    char DECODER[74] = {
        0xB8, 0x13, 0x00, 0xCD, 0x10, 0xBA, 0x00, 0xA0, 0x8E, 0xC2, 0xBA,
        0xC8, 0x03, 0x31, 0xC0, 0xEE, 0x42, 0xBE, 0x38, 0x01, 0xB1, 0x04,
        0xFD, 0x51, 0xB1, 0x03, 0xAC, 0xD0, 0xE8, 0xD0, 0xE8, 0xEE, 0xE2,
        0xF8, 0x83, 0xC6, 0x07, 0x59, 0xE2, 0xEF, 0xFC, 0xB9, 0x00, 0x08,
        0xBE, 0x90, 0x01, 0xBF, 0xC0, 0x4E, 0xAC, 0xD4, 0x10, 0x86, 0xC4,
        0xAB, 0xF7, 0xC7, 0x3F, 0x00, 0x75, 0x04, 0x81, 0xEF, 0x80, 0x01,
        0xE2, 0xEE, 0x31, 0xC0, 0xCD, 0x16, 0xCD, 0x20,
    };

    fwrite(BITMAPFILEHEADER, 1, 14, fout);
    fwrite(BITMAPINFOHEADER, 1, 40, fout);
    fwrite(palette, 4, 4, fout);
    fwrite(DECODER, 1, 74, fout);

    // BMPs are stored upside-down, because why not
    for (int i = 64; i--; )
        fwrite(outdata + i * 32, 1, 32, fout);

    fclose(fin);
    fclose(fout);
    return 0;
}

Output file

The output file is a BMP file which can be renamed .COM and run in a DOS environment. Upon execution, it will change to video mode 13h and display the image.

A BMP file has a first header BITMAPFILEHEADER, which contains among other things the field ImageOffset, which denotes where in the file the image data begins. After this comes BITMAPINFOHEADER with various de-/encoding information, followed by a palette, if one is used. ImageOffset can have a value that points beyond the end of any headers, allowing us to make a gap for the decoder to reside in. Roughly:

BITMAPFILEHEADER
BITMAPINFOHEADER
PALETTE
<gap>
IMAGE DATA

Another problem is to enter the decoder. BITMAPFILEHEADER and BITMAPINFOHEADER can be tinkered with to make sure they are legal machine code (which does not produce a non-recoverable state), but the palette is trickier. We could of course have made the palette artificially longer, and put the machine code there, but I opted to instead use the fields biXPelsPerMeter and biYPelsPerMeter, the former to make the code aligned properly, and the latter to jump into the decoder. These fields will of course then have garbage in them, but any image viewer I have tested with displays the image fine. Printing it might produce peculiar results, though.

It is, as far as I know, standard-compliant.

One could make a shorter file if the JMP instruction was put in one of the reserved fields in BITMAPFILEHEADER. This would allow us to store the image height as -64 instead of 64, which in the magical wonderland of BMP files means that the image data is stored the right way up, which in turn would allow for a simplified decoder.

Decoder

No particular tricks in the decoder. The palette is populated by the encoder, and shown here with dummy-values. It could be slightly shorter if it did not return to DOS upon a keypress, but it was not fun testing without that. If you feel you must, you can replace the last three instructions with jmp $ to save a few bytes. (Don't forget to update the file headers if you do!)

BMP stores palettes as BGR (not RGB) triplets, padded with zeroes. This makes setting up the VGA palette more annoying than usual. The fact that BMPs are stored upside-down only adds to the flavour (and size).

Listed here in NASM style:

Palette:
    db 0, 0, 0, 0
    db 0, 0, 0, 0
    db 0, 0, 0, 0
    db 0, 0, 0, 0

Decoder:
    ; Set screen mode
    mov ax, 0x13
    int 0x10

    mov dx, 0xa000
    mov es, dx

    ; Prepare to set palette
    mov dx, 0x3c8
    xor ax, ax
    out dx, al

    inc dx
    mov si, Palette + 2
    mov cl, 4
    std
pal_loop:
    push cx
    mov cl, 3
pal_inner:
    lodsb
    shr al, 1
    shr al, 1
    out dx, al
    loop pal_inner

    add si, 7
    pop cx
    loop pal_loop
    cld

    ; Copy image data to video memory
    mov cx, 64 * 64 / 2
    mov si, ImageData
    mov di, 20160
img_loop:
    lodsb
    aam 16
    xchg al, ah
    stosw
    test di, 63
    jnz skip
    sub di, 384
skip:
    loop img_loop

    ; Eat a keypress
    xor ax, ax
    int 0x16

    ; Return to DOS
    int 0x20

ImageData: