Javascript BMP Parser

Вступление

Еще с появления скриптов для отображения PDF, извлечения информации с MP3 и декодировки H.264 меня очень заинтересовала тема чтения и работы с бинарными данными в JavaScript.

В этом посте хотелось бы рассказать про свои эксперименты и рассмотреть эти возможности на примере «ручного» парсинга и отображения BMP-файлов (а заодно и освежить память о школьных временах работы с BMP на Паскале :) ).

Сразу хочу предупредить, что речь будет идти именно о написании JavaScript самостоятельно, а не его генерации с исходных кодов других языков с помощью какого-либо транслятора типа Emscripten.

Общие принципы

Пускай у нас будут два возможные источники для изображений, один внешний — на удаленном сервере, заданный с помощью URL, и один локальный — файл на компьютере пользователя).

Надо как-то формализовать доступ к ним в едином формате. Поскольку чтение и обработку bitmap-файла удобнее всего организовать в последовательном режиме (у него нет внутренней запутанной структуры с прыжками позиций, вызванными алгоритмами сжатия или другой подобной фигней), то руки сами сходу начали писать что-то наподобие FileStreamReader из других языков. К счастью, вскоре сознание прояснилось и пришла наконец одна умная, но, как всегда, немного запоздалая, мысль — “а не изобретаю ли я велосипед?”. Если предварительный быстрый гуглинг ничего полезного не дал, то на этот раз более глубокий поиск вывел на замечательную библиотеку jDataView от vjeux.

В чем ее суть? Все довольно просто. На вход (в конструктор) подаем буффер данных в виде объекта типа ArrayBuffer (MSDN, MDN) или бинарной строки. Внутри для объекта типа ArrayBuffer и при условии поддержки браузером нативного DataView (MSDN, MDN) библиотека будет просто проксировать все вызовы, в других же случаях будет выполняться авторская реализация потокового чтения различных типов данных из указанного источника. Для тех, кто до этого момента не работал с вышеупомянутыми объектами, настоятельно рекоммендую прочитать эту статью о работе с бинарными данными с испольованием типизированных массивов.

Кроме того, немногим позже все тот же vjeux разработал над ней удобную обертку для парсинга сложных бинарных структур данных - jParser. Внутри инстанс jParser содержит инстанс jDataView, к которому при необходимости можно обращаться напрямую (нам это еще пригодится), а сам jParser создается из все того же ArrayBuffer или строки (что пригодится для старых браузеров) и описания структуры в качестве второго параметра.

Опишем нашу структуру следующим образом:

{
    bgr: {
        b: 'uint8',
        g: 'uint8',
        r: 'uint8'
    },
    bgra: {
        b: 'uint8',
        g: 'uint8',
        r: 'uint8',
        a: 'uint8'
    },
    size: {
        horz: 'uint32',
        vert: 'uint32'
    },
    header: {
        // bitmap "magic" signature
        signature: function() {
            var magic = this.parse(['string', 2]);
            if (magic != 'BM') {
                throw new TypeError('Sorry, but only Windows BMP files are supported.');
            }
            return magic;
        },
        // full file size
        fileSize: 'uint32',
        // reserved
        reserved: 'uint32',
        // offset of bitmap data
        dataOffset: 'uint32',
        // size of DIB header
        dibHeaderSize: 'uint32',
        // image dimensions
        size: 'size',
        // color planes count (equals 1)
        planesCount: 'uint16',
        // color depth (bits per pixel)
        bpp: 'uint16',
        // compression type
        compression: 'uint32',
        // size of bitmap data
        dataSize: 'uint32',
        // resolutions (pixels per meter)
        resolution: 'size',
        // total color count
        colorsCount: function() { return this.parse('uint32') || Math.pow(2, this.current.bpp) /* (1 << bpp) not applicable for 32bpp */ },
        // count of colors that are required for displaying image
        importantColorsCount: function() { return this.parse('uint32') || this.current.colorsCount },
        // color palette (mandatory for <=8bpp images)
        palette: [
            'array',
            function() {
                var color = this.parse('bgr');
                // align to 4 bytes
                this.skip(1);
                return color;
            },
            function() { return this.current.bpp <= 8 ? this.current.colorsCount : 0 }
        ],
        // color masks (needed for 16bpp images)
        mask: {
            r: 'uint32',
            g: 'uint32',
            b: 'uint32'
        }
    }
}

Рассмотрим ее подробнее. bgr и bgra - вспомогательные описания структур цветов (RGB и RGBA соответственно), именно в таком виде как они записаны в файле (обратный порядок, следует полагать, вызван использованием little-endian записи цвета, закодированного в виде целочисленных значений). size - также вспомогательная структура, содержащая два целочисленных значения для вертикали и горизонтали (название для структуры не слишком удачное, но более абстрактного в голову на тот момент ничего не пришло).

Дальше идет header - само описание заголовка BMP-файла. Эту структуру подробно описывать здесь не буду, так как в основном она довольно проста и при желании ее детальные описания можно найти на MSDN, Википедии и ряде других ресурсов.

Все, описание структуры для парсера у нас есть. Тепер следует разобраться с получением самих бинарных данных.

Загрузка через AJAX

Для начала разберемся с удаленным источником. Поскольку мы пишем под новые браузеры + хотим разобраться с получением данных сами, то можем позволить себе не использовать обертки типа jQuery и написать:

var xhr = new XMLHttpRequest;
xhr.open('GET', source, true);

Дальше. В идеале мы хотим получить данные в формате ArrayBuffer. Для этого в браузерах, поддерживающих XMLHttpRequest 2.0 (все свежие версии Chrome, Firefox, Opera и IE10), можем написать:

xhr.responseType = 'arraybuffer';

Для более старых браузеров придется использовать бинарные строки. Для того, чтобы этого достичь (чтобы та или иная кодировка не искажала коды символов, а сохраняла оригинальные байт-коды), для большинства браузеров необходимо использовать:

xhr.overrideMimeType('text/plain; charset=x-user-defined');

За одним исключением. IE9 имеет свои особенности реализации XMLHttpRequest (а точнее, на тот момент он по сути был алиасом для реализации Microsoft.XMLHTTP), поэтому он не содержит метода overrideMimeType и вместо него надо писать:

xhr.setRequestHeader('Accept-Charset', 'x-user-defined');

Комбинируя эти три способа с помощью feature detection, мы получим запрос бинарных данных, работающий во всех браузерах с заявленной поддержкой HTML5.

Дальше необходимо прописать callback на получение данных. В общем виде он будет довольно прост, за исключением одного маленького подвоха опять-таки в IE9 (в IE10 уже все работает отлично):

xhr.onload = function() {
    if (this.status != 200) {
        throw new Error(this.statusText);
    }
    // emulating response field for IE9
    if (!('response' in this)) {
        this.response = new VBArray(this.responseBody).toArray().map(String.fromCharCode).join('');
    }
    // ... (process this.response) ...
}

Обьясню строки посредине. Дело в том, что практически во всех браузерах вы можете использовать поле response для получения данных, независимо от того, пришли они в виде строки, ArrayBuffer или в каком-то другом виде. В IE9-реализации же этого поля не существовало, но зато было поле responseBody, в котором собственно и хранились бинарные данные при использовании кодировки x-user-defined (responseText тоже доступен, но содержит фиг знает что строку с поврежденными байт-кодами). Основная загвоздка в том, что этот самый responseBody сохранен в формате массивов VBScript и недоступному для работы из JavaScript, и, как показали первичные поиски, соответственно может быть распарсен и обработан либо с помощью вставки vbs-скрипта, либо с использованием ActiveX-обьектов (пруф). Ни один из этих вариантов мне не понравился и поиски продолжились. Вскоре обнаружился обьект VBArray, который позволяет оборачивать эти самые VB-массивы и превращать их в обычный Array с помощью метода toArray. Таким образом, проблема решилась и с получением бинарных данных из удаленного источника было покончено.

Чтение с файлов

Теперь об использовании локальных файлов. Для работы с ними из JavaScript надо использовать File API. Понятно, что в связи с этим возможность работы с файлами будет иметь более узкий круг поддерживаемых браузеров, чем их загрузка через AJAX.

Для начала создадим поле для выбора файлов. Укажем поддержку выбора нескольких файлов за раз и ограничим их типы до bitmap-изображений:

<input type="file" id="file" multiple accept="image/bmp,image/*-bmp" />

Вешаем обработчик на изменение этого поля (выбор файлов):

document.getElementById('file').addEventListener('change', function() {
    // files list as array
    var files = Array.prototype.slice.call(this.files);

    // accept field doesn't work in some browsers so we create own RegExp from it's value for file list filtering
    if (this.accept) {
        var acceptRegExp = new RegExp('^(' + this.accept.replace(/*/, '.*').replace(/,/, '|') + ')$');
        files = files.filter(function(file) { return acceptRegExp.test(file.type) });
    }

    files.forEach(function(file) { BMPImage.readFrom(file, bmpDisplay) });
});

В строках 5-9 — небольшой фолбек для браузеров, не понимающих поле accept и соответственно позволяющих пользователю выбрать файлы неподдерживаемых форматов (их мы просто фильтруем).

Дальше просто пробегаемся по массиву файлов, читаем данные, парсим структуру заголовка, и передаем все это в bmpDisplay, отвечающий за дальнейший вывод изображения.

Само чтение файлов не представляет сложности:

// reading image from File instance

var reader = new FileReader;
reader.onload = function() { /* ... (process this.result) ... */ }
reader.readAsArrayBuffer(source);

Разбор и прорисовка

Теперь разберемся с отображением изображения. Из самой постановки задачи очевидно, что использовать <img /> для нашего «хардкорчика» нет смысла, и единственный вариант, с помощью которого мы сможем вывести изображение вручную — это <canvas /> .

Думаю, о самом элементе рассказывать детально нужды нет, так как скорее каждый разработчик уже сталкивался в худшем случае с его аналогами в других языках, а в лучшем — уже успел поковырять его реализацию конкретно в JavaScript. Детально ознакомиться с документацией к API этого элемента можно на порталах MSDN и MDN.

Отдельно остановлюсь только на раскрашивании пикселей. Фактически в API 2D-контекста канваса CanvasRenderingContext2D наряду с рисованием линий, прямоугольников, эллипсов, их дуг и прочих более замысловатых фигур не предусмотрено отдельного метода для раскрашивания отдельных пикселей. Конечно, можно было бы обойти это путем представления пикселя как линии одиночной длины (ну или прямоугольника 1x1, кому как больше по вкусу), но очевидно, что такой способ является довольно медленным из-за необходимости выставления параметров цвета и собственно вызова относительно дорогостоящих функций прорисовки для каждой отдельной точки. 
К счастью, нам это и не нужно, так как разработчики API предусмотрели возможное необузданное желание веб-разработчиков выводить уже готовые, отдельно обработанные блоки с bitmap-данными изображений непосредственно на прорисовку. Это достигается за счет:

1. предварительного вызова CanvasRenderingContext2D::createImageData который выделяет участок в памяти, определяющий raw-данные блока изображения с заданными размерами;
2. его записи в побайтовом режиме;
3. собственно прорисовки этого блока, начиная с левого верхнего угла элемента при помощи CanvasRenderingContext2D::putImageData.

В псевдокоде это можно записать следующим образом:

var imgData = context.createImageData(width, height), i = 0;
for (var y = 0; y < imgData.height; y++) {
  for (var x = 0; x < imgData.width; x++) {
    imgData.data[i++] = colors[x][y].red;
    imgData.data[i++] = colors[x][y].green;
    imgData.data[i++] = colors[x][y].blue;
    imgData.data[i++] = colors[x][y].alpha;
  }
}
context.putImageData(imgData, 0, 0);

Понятно, что этот код всего лишь отображает концепцию и для реальных изображений его придется усложнить.

С учетом всего вышесказанного, попробуем написать окончательную библиотеку для чтения и отображения BMP:

function BMPImage(data) {
    this.parser = new jParser(data, BMPImage.structure);
    this.meta = this.parser.parse('header');
}

BMPImage.structure = { /* here we put structure for parser as described in the start of article */ }

BMPImage.readFrom = function(source, callback) {
    function callbackImg(data) { callback.call(new BMPImage(data)) }
    if (source instanceof File) {
        // ... loading image from File instance and passing result to callbackImg ...
    } else {
        // ... loading image with AJAX request and passing response to callbackImg ...
    }
}

BMPImage.prototype.drawToCanvas = function(canvas) {
    canvas.width = this.meta.size.horz;
    canvas.height = this.meta.size.vert;
    this.drawToContext(canvas.getContext('2d'));
}

Реализация прорисовки BMPImage::drawToContext(context)  представляет собой отдельный интерес из-за необходимости конвертации цвета из любого формата в RGBA, поэтому позволю себе рассмотреть ее более детально.

Для начала откажемся от реализации распаковки сжатых изображений (это отдельная тема и сейчас она не представляет особого интереса):

if (this.meta.compression && this.meta.compression != 3) {
    throw new TypeError('Sorry, but RLE compressed images are not supported.');
}

" Перепрыгиваем" на позицию начала bitmap-данных, определенную в заголовке:

this.parser.seek(this.meta.dataOffset);

Сохраняем размеры изображения, выделяем область памяти с raw-данными:

var
// saving image sizes
size = this.meta.size,
// creating image data
imgData = context.createImageData(size.horz, size.vert);

Для изображений с глубиной цвета меньше 8 (метод сжатия BI_BITFIELDS) вычисляем маску для извлечения необходимого количества битов цвета, позицию сдвига внутри байта и весь байт индексов цвета, из которого будем извлекать цвета для каждого отдельного пикселя:

var
// color bit offset for <8bpp images
bitNumber,
// color index (should be stored between iterations for <8bpp images)
colorIndex;

Данные в BMP-изображении записаны снизу вверх и слева направо, причем в конце каждой строки осуществляется выравнивание по позиции в файле, кратной 4 байтам. В связи с этим цикл будет иметь вид:

// iterating over resulting bitmap bottom-to-top, left-to-right
for (var y = size.vert - 1; y > 0; y--) {
    // calculating image data offset for row [y]
    var dataPos = 4 * y * size.horz;

    // iterating over row pixels
    for (var x = 0; x < size.horz; x++) {
        var color;

        // ... read color and put it into `color` variable in {r, g, b[, a]} format ...

        // putting resulting RGBA values to image data
        imgData.data[dataPos++] = color.r;
        imgData.data[dataPos++] = color.g;
        imgData.data[dataPos++] = color.b;
        imgData.data[dataPos++] = color.a || 255;
    }

    // padding new row's alignment to 4 bytes
    var offsetOverhead = (this.parser.tell() - this.meta.dataOffset) % 4;
    if (offsetOverhead) {
        this.parser.skip(4 - offsetOverhead);
        bitNumber = 0;
    }
}

Чтение цвета и конвертация в RGB[A]-формат будет разбита на несколько частей для разных вариантов глубины цвета:

• Для сжатия BI_BITFIELDS (глубина цвета 1bpp, 2bpp, 4bpp) цвет на каждой итерации определяется как:

  if (!bitNumber) {
      bitNumber = 8;
      colorIndex = this.parser.view.getUint8();
  }
  bitNumber -= this.meta.bpp;
  color = this.meta.palette[(colorIndex >> bitNumber) & bitMask];

  Здесь мы извлекаем промежутки бит из текущего байта, двигаясь от старших к младшим и переходя на следующий байт по окончании текущего. С каждого такого набора бит формируем число, которое определяет индекс в цветовой палитре изображения.

• Для 8-битных изображений определяем цвет также из палитры, но в качестве индекса на этот раз просто используем значения байтов:

  color = this.meta.palette[this.parser.view.getUint8()];

• Для 16-битных изображений в формате реализована более сложная схема  5-6-5 (или, в старом варианте, 5-5-5) бит для каждого слова цвета с использованием маски из заголовка. Общий алгоритм конвертации в RGB примет следующий вид:

  colorIndex = this.parser.view.getUint16();
  color = {
      b: (colorIndex & this.meta.mask.b) << 3,
      g: (colorIndex & this.meta.mask.g) >> 3,
      r: (colorIndex & this.meta.mask.r) >> 8
  };

• 24- и 32-битные изображения читаются с использованием ранее определенных структур —

  color = this.parser.parse('bgr');

  и

  color = this.parser.parse('bgra');

  соответственно.

Все, мы готовы читать и отображать BMP-изображения :)

Выводы

Целью данной статьи было показать возможности парсинга и обработки бинарных данных с помощью новых (и не очень) возможностей JavaScript на относительно простом примере, показать что можно уже использовать, где можно наткнуться на грабли, а где — не изобретать велосипеды и использовать уже готовые решения. Заодно для понимания сложностей, которые могут возникнуть при ручной работе с бинарными форматами данных, был приведен базовый пример с парсингом BMP-изображений (хочу еще раз обратить внимание, это лишь пример, никто не призывает писать подобные решения там, где можно использовать нативные быстрые методы самого языка). Надеюсь, статья сможет кому-то помочь и послужить хорошим толчком для начала собственных исследований в этой области.

Полный код BMPImage можно найти здесь: http://pastebin.com/yAPpNez2.
Рабочий пример доступен по адресу: http://rreverser.com/dev/bmp/ (в качестве демок можно использовать URL-ы изображений 24bpp.bmp, 16bpp.bmp, 1bpp.bmp).

Автор: RReverser