Lesson3

Lesson3: RLE compression for BMP

Lesson 3： RLE压缩BMP

RLE

put it in few words

for original data like WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

count the repeated words and save data in format len+charactor as 12W1B12W3B24W1B14W

简单来说，对于原始数据 WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

计算其中的重复的字符数目，并表示成 长度+字符的形式 WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

---

In the previous lesson, we treat BMP as non-compressed RGB data, just read the data and feed it to SDL api for display.

在上一课中，我们是将bmp的数据作为未压缩的RGB数据，仅仅是读取数据然后直接交给了SDL去显示了。

However for a bmp, it could use RLE for compression.

但是对于bmp，它可能是用RLE来做压缩的。

For a bmp with palette, especially when it is a greyscale picture. The pixels data is the index number of color table entries.

一个使用调色板的bmp，尤其当它是灰度图，那么像素数据是用调色板的颜色编号来表示的。

For RLE in bmp format, see the last part of BMP.

对于RLE的格式，看BMP最后一部分。

For 8 bit RLE pseudo code is like:

8bit的RLE解码的伪代码如下：

read first byte as n
if n > 0:
    read 1 byte and repeat it as pixels
else if n == 0:
    read 1 byte as c
    if c == 0:
        end of line
    else if c == 1:
        end of image
    else if c == 2:
        read 1 byte as right shift in image
        read 1 byte as down shift in image
    else:
        absolute mode, read c bytes and each as one pixel
        read (4 - c % 4) % 4 bytes so aligned to 4 bytes

---

For RLE 4bit compression, it also uses encoded and absolute modes.

4bit RLE的压缩，额外存在编码模式和绝对模式。

In encoded mode, the first byte of the pair contains the number of pixels to be drawn using the color indexes in the second byte. The second byte contains two color indexes, one in its high-order nibble (that is, its low-order four bits) and one in its low-order nibble. The first of the pixels is drawn using the color specified by the high-order nibble, the second is drawn using the color in the low-order nibble, the third is drawn with the color in the high-order nibble, and so on, until all the pixels specified by the first byte have been drawn.

在编码模式下，第一个字节表示后一个字节所代表的像素所重复的次数。第二个字节实际上包含两个色彩编号。一个是高4bit表示，一个是底4bit表示。当解码绘制时，按照第一个像素，第二个像素，第一个像素... 如此重复，直至第一个字节所表示的重复次数都解码绘制完成。

In absolute mode, the first byte contains zero, the second byte contains the number of color indexes that follow, and subsequent bytes contain color indexes in their high- and low-order nibbles, one color index for each pixel. In absolute mode, each run must be aligned on a word boundary. The end-of-line, end-of-bitmap, and delta escapes also apply to BI_RLE4.

在绝对模式下，第一个字节是0，第二个字节表示的是色彩编号，用高4bit，然后低4bit来表示每个像素。在此模式下，每次解码都应当已word为边界对齐。每行结束、图片结束、还有delta 空也需要按照RLE4来解码。

An example is 03 04 05 06 00 06 45 56 67 00 04 78 00 02 05 01 04 78 00 00 09 1E 00 01 This bitmap is interpreted as follows:

一个例子 03 04 05 06 00 06 45 56 67 00 04 78 00 02 05 01 04 78 00 00 09 1E 00 01 解码后是如下：

• 03 04: Encoded mode, specifying 3 pixels with the value in 0x04, the pixels are 0, 4, 0. 编码模式，表示3个像素，分别是0， 4， 0
• 05 06: Encoded mode, specifying 5 pixels with the value in 0x06, the pixels are 0, 6, 0, 6, 0 编码模式，表示6个像素，分别是0, 6, 0, 6, 0
• 00 06 45 56 67 00: Absolute mode, specifying 6 pixels with the values 4, 5, 5, 6, 6, 7 padded to a word boundary. 绝对模式，6个像素，4, 5, 5, 6, 6, 7，因为需要对其word，所以有00
• 04 78: Encoded mode, specifying 4 pixels with the value in 0x78. the pixels are 7, 8, 7, 8 编码模式，4个像素，7，8，7，8
• 00 02 05 01: Encoded mode, specifying a new relative position 5 pixels to the right and 1 line down. 编码模式，表示一个新的位置，向右移5个像素，向下移一行
• 04 78: Encoded mode, specifying 4 pixels with the value in 0x78, the pixels are 7, 8, 7, 8 编码模式，4个像素，7，8，7，8
• 00 00: Encoded mode, specifying the end of a line. 编码模式，行结尾
• 09 1E: Encoded mode, specifying 9 pixels with the value in 0x1E, the pixels are 1 E 1 E 1 E 1 E 1 编码模式，9个像素， 1 E 1 E 1 E 1 E 1
• 00 01: Encoded mode, specifying the end of the bitmap. 编码模式，图片结尾。

For 4 bit RLE pseudo code is like:

4bit的RLE解码伪代码如下：

read first byte as n
if n > 0:
    read 1 byte split to and hi and lo, and repeat it as pixels in turn
else if n == 0:
    read 1 byte as c
    if c == 0:
        end of line
    else if c == 1:
        end of image
    else if c == 2:
        read 1 byte as right shift in image
        read 1 byte as down shift in image
    else:
        absolute mode, read (c+1)/2 bytes and split each to hi and lo as pixels
        read (4 - ((c+1)/2) % 4) % 4 bytes so aligned to 4 bytes

Then feed the decoded data to SDL for display.

之后将解码的数据喂给SDL显示

This lesson shows that BMP could use RLE for compression. It is a start in image compression.

本节课展示了BMP使用RLE来压缩数据，可以看作开始涉及图像压缩了。

---

The full code is below 完整代码如下

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

#include <SDL.h>

#pragma pack(push, 2)

struct bmp_file_header {
    uint16_t signature;
    uint32_t filesize;
    uint32_t rsd;
    uint32_t offset;
};

enum {
    BI_RGB = 0,
    BI_RLE8 = 1,
    BI_RLE4 = 2,
};

struct bmp_info_header {
    uint32_t size;
    uint32_t width;
    uint32_t height;
    uint16_t planes;
    uint16_t bitsperpixels;
    uint32_t compression;
    uint32_t image_size;
    uint32_t resolution_x;
    uint32_t resolution_y;
    uint32_t color_used;
    uint32_t color_important;
};

struct color_table_entry {
    uint8_t blue;
    uint8_t green;
    uint8_t red;
    uint8_t alpha;
};

#pragma pack(pop)

struct BMP {
    int width;
    int height;
    int depth;
    int pitch;
    int format;
    uint8_t *data;
};

void RLE8_decode(uint8_t *com, int len, uint8_t *data, int pitch, int height,
                 struct color_table_entry *ct) {
    int p = 0;
    int y = height ? height -1 : 0;
    int x = 0;
    int delta = height ? -1: 1;
    while (p < len) {
        uint8_t n = com[p++];
        if (n > 0) {
            uint8_t px = com[p++];
            for (int i = 0; i < n; i++) {
                data[y * pitch + x * 4] = ct[px].blue;
                data[y * pitch + x * 4 + 1] = ct[px].green;
                data[y * pitch + x * 4 + 2] = ct[px].red;
                data[y * pitch + x * 4 + 3] = 0xFF;
                printf("%02x ", px);
                x ++;
                if (x * 4 >= pitch) {
                    x = 0;
                    y+= delta;
                }
            }
        } else {
            uint8_t c = com[p++];
            if (c == 0) {
                printf("\n");
                y+= delta;
                x = 0;
            } else if (c == 1) {
                return;
            } else if (c == 2) {
                x += com[p++];
                y += com[p++]* delta;
            } else {
                for (int i = 0; i < c; i++) {
                    uint8_t px = com[p++];
                    data[y * pitch + x * 4] = ct[px].blue;
                    data[y * pitch + x * 4 + 1] = ct[px].green;
                    data[y * pitch + x * 4 + 2] = ct[px].red;
                    data[y * pitch + x * 4 + 3] = 0xFF;
                    printf("%02x ", px);
                    x++;
                    if (4 *x >= pitch) {
                        x = 0;
                        y+= delta;
                    }
                }
                for (int i = 0; i < (4 - c % 4) % 4; i++) {
                    p++;
                }
            }
        }
    }
}

void RLE4_decode(uint8_t *com, int len, uint8_t *data, int pitch, int height,
                 struct color_table_entry *ct) {
    int p = 0;
    int y = height ? height - 1 : 0;
    int x = 0;
    int delta = height ? -1 : 1;
    while (p < len) {
        uint8_t n = com[p++];
        if (n > 0) {
            uint8_t px = com[p++];
            for (int i = 0; i < n; i++) {
                data[y * pitch + x * 4] = ct[px>>4].blue;
                data[y * pitch + x * 4 + 1] = ct[px>>4].green;
                data[y * pitch + x * 4 + 2] = ct[px>>4].red;
                data[y * pitch + x * 4 + 3] = 0xFF;
                px = (px >> 4) | (px << 4);
                x++;
                if (x * 4 >= pitch) {
                    x = 0;
                    y += delta;
                }
            }
        } else {
            uint8_t c = com[p++];
            if (c == 0) {
                y += delta;
                x = 0;
            } else if (c == 1) {
                return;
            } else if (c == 2) {
                x += com[p++];
                y += com[p++] * delta;
            } else {
                uint8_t px;
                for (int i = 0; i < c; i++) {
                    if (i % 2 == 0) {
                        px = com[p++];
                    }
                    data[y * pitch + x * 4] = ct[px>>4].blue;
                    data[y * pitch + x * 4 + 1] = ct[px>>4].green;
                    data[y * pitch + x * 4 + 2] = ct[px>>4].red;
                    data[y * pitch + x * 4 + 3] = 0xFF;
                    px = (px >> 4)| (px << 4);
                    x++;
                    if (4 * x >= pitch) {
                        x = 0;
                        y += delta;
                    }
                }
                for (int i = 0; i < (4 - ((c + 1) / 2) % 4) % 4; i++) {
                    p++;
                }
            }
        }
    }
}

struct BMP *load_bmp(FILE *fp) {
    struct BMP *b = malloc(sizeof(struct BMP));
    struct bmp_file_header fh;
    int len = fread(&fh, sizeof(fh), 1, fp);
    if (len < 1) {
        return NULL;
    }
    printf("%C%C\n", fh.signature&0xFF, fh.signature>>8);
    printf("file size %d\n", fh.filesize);
    struct bmp_info_header info;
    fread(&info, sizeof(info), 1, fp);
    printf("width %d, height %d, depth %d\n",info.width, info.height, info.bitsperpixels);
    printf("color used %d\n", info.color_used);
    printf("image size %d\n", info.image_size);

    struct color_table_entry *ct;
    if (info.color_used > 0) {
        ct = malloc(sizeof(struct color_table_entry) * info.color_used);
        fread(ct, 4, info.color_used, fp);
        for (int i = 0; i < info.color_used; i++) {
            printf("R %x, G %x, B %x, A %x\n", ct[i].red, ct[i].green, ct[i].blue, ct[i].alpha);
        }
    }

    fseek(fp, fh.offset, SEEK_SET);
    b->width = info.width;
    b->height = info.height;

    if (info.compression == BI_RGB) {
        b->depth = info.bitsperpixels;
        b->pitch = (((info.width + 3) >> 2) << 2) * b->depth / 8;
        b->data = malloc(info.height * b->pitch);
        b->format = SDL_PIXELFORMAT_BGR24;
        for (int y = 0; y < info.height; y++) {
            fread(b->data + (info.height-1-y)*b->pitch, b->width*b->depth/8, 1, fp);
        }
    } else if (info.compression == BI_RLE8) {
        b->depth = 32;
        b->format = SDL_PIXELFORMAT_BGRA32;
        b->pitch = (((b->width + 3) >> 2) << 2) * b->depth / 8;
        printf("pitch %d\n", b->pitch);
        b->data = malloc(b->height * b->pitch);
        uint8_t *compressed = malloc(info.image_size);
        fread(compressed, info.image_size, 1, fp);
        RLE8_decode(compressed, info.image_size, b->data, b->pitch, b->height,ct);
        free(compressed);
    } else if (info.compression == BI_RLE4) {
        b->depth = 32;
        b->pitch = (((b->width + 3) >> 2) << 2) * b->depth / 8;
        printf("pitch %d\n", b->pitch);
        b->data = malloc(b->height * b->pitch);
        uint8_t *compressed = malloc(info.image_size);
        fread(compressed, info.image_size, 1, fp);
        RLE4_decode(compressed, info.image_size, b->data, b->pitch, b->height, ct);
        free(compressed);
    }
    return b;
}

void display_bmp(uint8_t *data, int width, int height, int pitch, int depth, int format)
{
    int ret = SDL_Init(SDL_INIT_EVERYTHING);
    if (ret == -1) {
        return;
    }

    SDL_Window *w = SDL_CreateWindow("show", SDL_WINDOWPOS_UNDEFINED,
                                     SDL_WINDOWPOS_UNDEFINED, 640, 480,
                                     SDL_WINDOW_SHOWN | SDL_WINDOW_RESIZABLE);

    SDL_Renderer *r = SDL_CreateRenderer(
        w, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
    SDL_SetRenderDrawBlendMode(r, SDL_BLENDMODE_BLEND);
    
    SDL_RenderClear(r);

    SDL_Surface *s = SDL_CreateRGBSurfaceWithFormatFrom(data, width, height, depth, pitch, format);
    SDL_Texture *t = SDL_CreateTextureFromSurface(r, s);
    SDL_SetRenderTarget(r, t);
    SDL_RenderCopy(r, t, NULL, NULL);
    SDL_RenderPresent(r);
    bool quit = false;
    while (!quit) {
        SDL_Event e;
        while(SDL_PollEvent(&e)) {
            if (e.type == SDL_KEYDOWN) {
                quit = true;
                break;
            }
        };
    }
    SDL_DestroyTexture(t);
    SDL_DestroyRenderer(r);
    SDL_FreeSurface(s);
    SDL_DestroyWindow(w);
    SDL_Quit();
}

int
main(int argc, const char *argv[])
{
    FILE *f = fopen(argv[1], "rb");
    struct BMP *b = load_bmp(f);
    fclose(f);

    printf("w %d, h %d, pitch %d, depth %d\n", b->width, b->height, b->pitch, b->depth);
    display_bmp(b->data, b->width, b->height, b->pitch, b->depth, b->format);

    free(b->data);
    free(b);
    return 0;
}