画像ファイルの圧縮を実装したら、pngよりファイルサイズ小さくなった

## はじめに
JavaScriptで減色処理して遊んでいた時に、バイナリを扱う練習として画像ファイルを自分の考えた形式で保存してみようと思い実装してみて動かしたら、<b>条件付きではあるもののpngよりファイルサイズが小さくなった</b>ので記事を書くことにしました。
あと、自分がバイナリの操作を忘れた時用です。
<b>フォーマットもアルゴリズムもかなり易しい</b>ので、プログラム始めたての人でも十分理解できると思います。

## フォーマット
拡張子は.orz
色数は16色まで
画像の幅と高さは 65536 まで

|項目|サイズ (bytes)|備考|
|---|---|---|
|ヘッダ|4|固定 ORZ1|
|幅と高さ|4|2bytes$\times$ 2|
|色数|1|1～16|
|パレット情報|4$\times$c|cは色数。RGBAで保存|
|画素情報|1$\times$p|pは画素数。|

可逆圧縮であり、JPEGのように劣化はしない。
RGBAで保存しているので、透過色にも対応している。

画素情報は 4色の場合、上位2ビットに色情報(パレットのインデックス)、下位6ビットにその色が何連続しているかを保持している。

## 実験
画像サイズは 256x256 で色数を2～16でorzとpngでファイルサイズを比較してみました。
orzのファイルサイズはpngの2/3程度であることが分かります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/163605/79f3d582-f151-45a7-b34c-932021fc6d2a.png)

## ソース

```js
// Orz file
export default class Orz {
    static header = 'ORZ';
    static version = 1;
    static maxColorCount = 16;
    static maxSize = 65536;
    
    /**
     * load orz file
     * @param {string} url url
     * @returns {ImageData} image data
     */
    static async load(url) {
        const buffer = await loadBuffer(url);
        if(!buffer) { 
            console.error('Not found.');
            return null; 
        }
        return Orz.arrayBufferToImageData(buffer);
        
        /**
         * load array buffer
         * @param {string} url url
         * @returns {Promise<ArrayBuffer>} array buffer
         */
        async function loadBuffer(url) {
            if(!url) {// url not exist
                const fileoptions = {
                    multiple : false,
                    excludeAcceptAllOption : false, 
                    types : [// filter
                        {
                            description: 'Orz',
                            accept: {
                            },                
                        },
                    ],
                };
                try {
                    const fileHandles = await window.showOpenFilePicker(fileoptions);
                    if(fileHandles.length !== 1) {
                        throw 'file count is not one.';
                    }
                    const file = await fileHandles[0].getFile();
                    return await loadBuffer(URL.createObjectURL(file));
                } catch(e) {// No file selected  
                    return null;
                }
            } else {// url exist
                return new Promise(resolve => {
                    const req = new XMLHttpRequest();
                    req.open('get', url, true);
                    req.responseType = 'arraybuffer';
                    req.onload = () => {
                        if(req.status === 200) {
                            resolve(req.response); // ArrayBuffer
                        } else {
                            resolve(null);					
                        }
                    }
                    req.send();
                });
            }
        }
    }

    /**
     * convert array buffer to image data
     * @param {ArrayBuffer} buffer array buffer
     * @returns {ImageData} image data
     */
    static arrayBufferToImageData(buffer) {
        const dataview = new DataView(buffer);
        let byteOffset = 0; // pointer
        
        // header
        const headers = [...Array(4)].map(() => dataview.getUint8(byteOffset++));
        const r = headers.slice(0, 3).every((e, i) => String.fromCharCode(e) === Orz.header[i]);
        if(!r) { 
            console.error('Not orz file.');
            return null; 
        }
                
        // width and height
        const width = dataview.getUint16(byteOffset);
        byteOffset += 2;
        const height = dataview.getUint16(byteOffset);
        byteOffset += 2;

        // color count
        const colorCount = dataview.getUint8(byteOffset++);        
        const colorBits = Orz._computeColorBits(colorCount);    
        
        // color info
        const colors = [...Array(colorCount)].map(e => {
            const r = dataview.getUint8(byteOffset++);
            const g = dataview.getUint8(byteOffset++);
            const b = dataview.getUint8(byteOffset++);
            const a = dataview.getUint8(byteOffset++);
            return { r, g, b, a, };  
        });

        // pixel info
        const pixels = [];
        while(byteOffset < buffer.byteLength) {
            const data = dataview.getUint8(byteOffset++);
            const [index, count] = splitByte(data, colorBits);
            pixels.push({ index, count: count + 1, });
        }
        
        // to image data
        const imgData = new ImageData(width, height);
        const { data, } = imgData;  
        let index = 0;      
        for(let i = 0; i < pixels.length; i += 1) {            
            const pixel = pixels[i];
            const color = colors[pixel.index];
            for(let q = 0; q < pixel.count; q += 1) {
                const p = index * 4;
                data[p + 0] = color.r;
                data[p + 1] = color.g;
                data[p + 2] = color.b;
                data[p + 3] = color.a;
                index += 1;
            }
        }
        return imgData;

        /**
         * split byte data
         * @param {number} data byte data 
         * @param {number} colorBits color bits depth 
         * @returns {Array<number>} splited data
         */
        function splitByte(data, colorBits) {
            const high = data >> (8 - colorBits);
            const low = data & (0xff >> colorBits);
            return [high, low];
        }
    }

    /**
     * save orz file
     * @param {HTMLCanvasElement} canvas source canvas 
     * @param {string} fileName file name
     * @returns {void} nothing
     */
    static async save(canvas, fileName) {
        // Get array buffer        
        const buffer = Orz.canvasToArrayBuffer(canvas);
        if(!buffer) { return null; }

        // Generate Blob of array buffer
        const blob = new Blob([buffer]);
        try {
            const fh = await window.showSaveFilePicker({ suggestedName: fileName });   // Display a file save dialog and get a FileSystemFileHandle object
            const stream = await fh.createWritable();   // Get a FileSystemWritableFileStream object
            await stream.write(blob);   // write blob
            await stream.close();   // close
        } catch(e) {
            return; // No file selected
        }
    }

    /**
     * convert canvas to array buffer of orz
     * @param {HTMLCanvasElement} canvas source canvas 
     * @returns {ArrayBuffer} array buffer
     */
    static canvasToArrayBuffer(canvas) {
        // get colors
        const colors = getColors(canvas);
        if(colors.length > Orz.maxColorCount) {
            console.error('Too many colors. Must not exceed 16 colors.');
            return null;
        }
        const colorBits = Orz._computeColorBits(colors.length);

        // get width and height
        const { width, height, } = canvas;
        if(width > Orz.maxSize || height > Orz.maxSize) {
            console.error('Width and height must not exceed 65536.');
            return null;
        }        

        // get pixel array
        const pixels = scan(canvas, colors, colorBits);

        // write file
        const fileSize = 4                    // header 
                       + 4                    // width + height
                       + 1                    // color count
                       + 4 * colors.length    // color info
                       + 1 * pixels.length;   // pixel info
        
        const buffer = new ArrayBuffer(fileSize);
        const dataview = new DataView(buffer);
        let byteOffset = 0; // pointer
        
        // header
        Orz.header.split('').forEach(e => {
            dataview.setUint8(byteOffset++, e.charCodeAt());
        });
        dataview.setUint8(byteOffset++, Orz.version);   
        
        // width and height
        dataview.setUint16(byteOffset, width);
        byteOffset += 2;
        dataview.setUint16(byteOffset, height);
        byteOffset += 2;          
        
        // color count
        dataview.setUint8(byteOffset++, colors.length);

        // color info
        colors.forEach(e => {
            dataview.setUint8(byteOffset++, e.r);
            dataview.setUint8(byteOffset++, e.g);
            dataview.setUint8(byteOffset++, e.b);
            dataview.setUint8(byteOffset++, e.a);
        });
        
        // pixel info
        pixels.forEach(e => {
            const high = e.index;
            const low = e.count - 1;
            dataview.setUint8(byteOffset++, combineToByte(high, low, colorBits));
        });

        return buffer;

        /**
         * get pixel data
         * @param {HTMLCanvasElement} canvas 
         * @param {Array<Object>} colors color data
         * @param {number} colorBits color bits depth
         * @returns {Array<Object>} pixel array
         */
        function scan(canvas, colors, colorBits) {
            const ctx = canvas.getContext('2d');
            const imgData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
            const { data, } = imgData;
    
            let preColor = { r: -1, g: -1, b: -1, a: -1, };
            let continuousCount = 0;
            const maxCount = 2 ** (8 - colorBits);
            let pixels = [];
            for(let p = 0; p < data.length; p += 4) {
                const color = getColor(data, p);
                continuousCount++;
                if(continuousCount > maxCount || !isSameColor(color, preColor)) {
                    const index = colors.findIndex((e => isSameColor(e, color)));
                    if(pixels.length) {
                        pixels[pixels.length - 1].count = continuousCount - 1;
                    }
                    continuousCount = 1;
                    pixels.push({ index, count: 1, });                    
                }
                if(p === data.length - 4) {
                    if(pixels.length) {
                        pixels[pixels.length - 1].count = continuousCount;
                    }
                }
                preColor = color;
            }

            return pixels;
    
            function getColor(data, p) {
                return { r: data[p], g: data[p + 1], b: data[p + 2], a: data[p + 3], };
            }
            function isSameColor(src, dst) {
                return src.r === dst.r && src.g === dst.g && src.b === dst.b && src.a === dst.a;
            }
        }
        /**
         * get color array
         * @param {HTMLCanvasElement} canvas Canvas
         * @returns {Array<Object>} color array
         */
        function getColors(canvas) {
            const ctx = canvas.getContext('2d');
            const imgData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
            const { data, } = imgData;
            // get color map
            const colorMap = {};
            for(let i = 0; i < data.length; i += 4) {
                const [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]];
                colorMap[`${r.toString().padStart(3, '0')}${g.toString().padStart(3, '0')}${b.toString().padStart(3, '0')}${a.toString().padStart(3, '0')}`] = 0;
            }
            // to color array
            const colors = Object.keys(colorMap).map(e => {
                const r = parseInt(e.substring(0, 3), 10);
                const g = parseInt(e.substring(3, 6), 10);
                const b = parseInt(e.substring(6, 9), 10);
                const a = parseInt(e.substring(9), 10);
                return { r, g, b, a, };
            });
            return colors;
        }
        /**
         * combined 2 bits
         * @param {number} high high-order bits
         * @param {number} low low-order bits
         * @param {number} colorBits color bits
         * @returns {number} combined
         */
        function combineToByte(high, low, colorBits) {
            return (high << (8 - colorBits)) | low;
        }
    } 

    /**
     * compute color bits from color count
     * @param {number} colorCount color count 
     * @returns {number} color bits
     */
    static _computeColorBits(colorCount) {
        return Math.max(1, Math.ceil(Math.log2(colorCount)));
    }
}
```

## 呼び出し方
テスト用のコードをそのまま貼り付けておきます。
orzファイルを読み込むときは load メソッドを、
canvas をバイナリ(ArrayBuffer)に変換するときは toArrayBuffer メソッドを読んでください。
save メソッドは内部的に toArrayBuffer メソッドを呼んで、ファイルダイアログを開いているだけです。
詳細はコメント読んでください。

```js
const $ = a => document.querySelector(a); 
$('#debug-button').addEventListener('click', async () => {
    const imgData = await Orz.load('debug.orz');
    $('#debug-canvas').width = imgData.width;            
    $('#debug-canvas').height = imgData.height;
    const ctx = $('#debug-canvas').getContext('2d');
    ctx.putImageData(imgData, 0, 0)
});
$('#debug2-button').addEventListener('click', () => {
    Orz.save($('#dst-canvas'), 'debug.orz');
});
```

## 最後に
条件付きでpngよりファイルサイズが小さくなりますが、おもちゃの域は越えません。
プログラムの練習としてご活用ください。
簡単なテストしかしていません。バグが出ても直しません。