Interactive interface for browsing global, full-resolution satellite imagery
/*
gifWriter.js
============
*/
// (c) Dean McNamee <[email protected]>, 2013.
//
// https://github.com/deanm/omggif
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
//
// omggif is a JavaScript implementation of a GIF 89a encoder and decoder,
// including animation and compression. It does not rely on any specific
// underlying system, so should run in the browser, Node, or Plask.
let loop_count;
let global_palette;
let buf;
let p;
export default class gifWriter {
constructor(rs, width, height, gopts) {
const buf = [];
let p = 0;
gopts = gopts === undefined ? {} : gopts;
loop_count = gopts.loop === undefined ? null : gopts.loop;
global_palette = gopts.palette === undefined ? null : gopts.palette;
if (width <= 0 || height <= 0 || width > 65535 || height > 65535) { throw 'Width/Height invalid.'; }
// - Header.
buf[p++] = 0x47;
buf[p++] = 0x49;
buf[p++] = 0x46; // GIF
buf[p++] = 0x38;
buf[p++] = 0x39;
buf[p++] = 0x61; // 89a
// Handling of Global Color Table (palette) and background index.
const gp_num_colors_pow2 = 0;
const background = 0;
// - Logical Screen Descriptor.
// NOTE(deanm): w/h apparently ignored by implementations, but set anyway.
buf[p++] = width & 0xff;
buf[p++] = (width >> 8) & 0xff;
buf[p++] = height & 0xff;
buf[p++] = (height >> 8) & 0xff;
// NOTE: Indicates 0-bpp original color resolution (unused?).
buf[p++] = (global_palette !== null ? 0x80 : 0) | gp_num_colors_pow2; // Global Color Table Flag. // NOTE: No sort flag (unused?).
buf[p++] = background; // Background Color Index.
buf[p++] = 0; // Pixel aspect ratio (unused?).
if (loop_count !== null) {
// Netscape block for looping.
if (loop_count < 0 || loop_count > 65535) throw 'Loop count invalid.';
// Extension code, label, and length.
buf[p++] = 0x21;
buf[p++] = 0xff;
buf[p++] = 0x0b;
// NETSCAPE2.0
buf[p++] = 0x4e;
buf[p++] = 0x45;
buf[p++] = 0x54;
buf[p++] = 0x53;
buf[p++] = 0x43;
buf[p++] = 0x41;
buf[p++] = 0x50;
buf[p++] = 0x45;
buf[p++] = 0x32;
buf[p++] = 0x2e;
buf[p++] = 0x30;
// Sub-block
buf[p++] = 0x03;
buf[p++] = 0x01;
buf[p++] = loop_count & 0xff;
buf[p++] = (loop_count >> 8) & 0xff;
buf[p++] = 0x00; // Terminator.
}
const self = this;
const reader = rs.getReader();
return new ReadableStream({
start: function start(controller) {
controller.enqueue(new Uint8Array(buf));
},
pull: function pull(controller) {
return reader.read().then((_ref2) => {
const { done } = _ref2;
const { value } = _ref2;
if (done) {
controller.enqueue(new Uint8Array([0x3b]));
controller.close();
return;
}
self.addFrame.apply(self, [controller].concat(value));
});
},
});
}
addFrame(controller, x, y, w, h, indexed_pixels, opts) {
buf = [];
p = 0;
opts = opts === undefined ? {} : opts;
// TODO(deanm): Bounds check x, y. Do they need to be within the virtual
// canvas width/height, I imagine?
if (x < 0 || y < 0 || x > 65535 || y > 65535) throw 'x/y invalid.';
if (w <= 0 || h <= 0 || w > 65535 || h > 65535) { throw 'Width/Height invalid.'; }
if (indexed_pixels.length < w * h) { throw 'Not enough pixels for the frame size.'; }
let using_local_palette = true;
let { palette } = opts;
if (palette === undefined || palette === null) {
using_local_palette = false;
palette = global_palette;
}
if (palette === undefined || palette === null) { throw 'Must supply either a local or global palette.'; }
let num_colors = check_palette_and_num_colors(palette);
// Compute the min_code_size (power of 2), destroying num_colors.
let min_code_size = 0;
while (num_colors >>= 1) ++min_code_size;
num_colors = 1 << min_code_size; // Now we can easily get it back.
const delay = opts.delay === undefined ? 0 : opts.delay;
// From the spec:
// 0 - No disposal specified. The decoder is
// not required to take any action.
// 1 - Do not dispose. The graphic is to be left
// in place.
// 2 - Restore to background color. The area used by the
// graphic must be restored to the background color.
// 3 - Restore to previous. The decoder is required to
// restore the area overwritten by the graphic with
// what was there prior to rendering the graphic.
// 4-7 - To be defined.
// NOTE(deanm): Dispose background doesn't really work, apparently most
// browsers ignore the background palette index and clear to transparency.
const disposal = opts.disposal === undefined ? 0 : opts.disposal;
if (disposal < 0 || disposal > 3)
// 4-7 is reserved.
{ throw 'Disposal out of range.'; }
let use_transparency = false;
let transparent_index = 0;
if (opts.transparent !== undefined && opts.transparent !== null) {
use_transparency = true;
transparent_index = opts.transparent;
if (transparent_index < 0 || transparent_index >= num_colors) { throw 'Transparent color index.'; }
}
if (disposal !== 0 || use_transparency || delay !== 0) {
// - Graphics Control Extension
buf[p++] = 0x21;
buf[p++] = 0xf9; // Extension / Label.
buf[p++] = 4; // Byte size.
buf[p++] = (disposal << 2) | (use_transparency === true ? 1 : 0);
buf[p++] = delay & 0xff;
buf[p++] = (delay >> 8) & 0xff;
buf[p++] = transparent_index; // Transparent color index.
buf[p++] = 0; // Block Terminator.
}
// - Image Descriptor
buf[p++] = 0x2c; // Image Seperator.
buf[p++] = x & 0xff;
buf[p++] = (x >> 8) & 0xff; // Left.
buf[p++] = y & 0xff;
buf[p++] = (y >> 8) & 0xff; // Top.
buf[p++] = w & 0xff;
buf[p++] = (w >> 8) & 0xff;
buf[p++] = h & 0xff;
buf[p++] = (h >> 8) & 0xff;
// NOTE: No sort flag (unused?).
// TODO(deanm): Support interlace.
buf[p++] = using_local_palette === true ? 0x80 | (min_code_size - 1) : 0;
// - Local Color Table
if (using_local_palette === true) {
for (let i = 0, il = palette.length; i < il; ++i) {
const rgb = palette[i];
buf[p++] = (rgb >> 16) & 0xff;
buf[p++] = (rgb >> 8) & 0xff;
buf[p++] = rgb & 0xff;
}
}
p = GifWriterOutputLZWCodeStream(
buf,
p,
min_code_size < 2 ? 2 : min_code_size,
indexed_pixels,
);
controller.enqueue(new Uint8Array(buf));
}
}
// Main compression routine, palette indexes -> LZW code stream.
// |index_stream| must have at least one entry.
function GifWriterOutputLZWCodeStream(buf, p, min_code_size, index_stream) {
buf[p++] = min_code_size;
let cur_subblock = p++; // Pointing at the length field.
const clear_code = 1 << min_code_size;
const code_mask = clear_code - 1;
const eoi_code = clear_code + 1;
let next_code = eoi_code + 1;
let cur_code_size = min_code_size + 1; // Number of bits per code.
let cur_shift = 0;
// We have at most 12-bit codes, so we should have to hold a max of 19
// bits here (and then we would write out).
let cur = 0;
function emit_bytes_to_buffer(bit_block_size) {
while (cur_shift >= bit_block_size) {
buf[p++] = cur & 0xff;
cur >>= 8;
cur_shift -= 8;
if (p === cur_subblock + 256) {
// Finished a subblock.
buf[cur_subblock] = 255;
cur_subblock = p++;
}
}
}
function emit_code(c) {
cur |= c << cur_shift;
cur_shift += cur_code_size;
emit_bytes_to_buffer(8);
}
// I am not an expert on the topic, and I don't want to write a thesis.
// However, it is good to outline here the basic algorithm and the few data
// structures and optimizations here that make this implementation fast.
// The basic idea behind LZW is to build a table of previously seen runs
// addressed by a short id (herein called output code). All data is
// referenced by a code, which represents one or more values from the
// original input stream. All input bytes can be referenced as the same
// value as an output code. So if you didn't want any compression, you
// could more or less just output the original bytes as codes (there are
// some details to this, but it is the idea). In order to achieve
// compression, values greater then the input range (codes can be up to
// 12-bit while input only 8-bit) represent a sequence of previously seen
// inputs. The decompressor is able to build the same mapping while
// decoding, so there is always a shared common knowledge between the
// encoding and decoder, which is also important for "timing" aspects like
// how to handle variable bit width code encoding.
//
// One obvious but very important consequence of the table system is there
// is always a unique id (at most 12-bits) to map the runs. 'A' might be
// 4, then 'AA' might be 10, 'AAA' 11, 'AAAA' 12, etc. This relationship
// can be used for an effecient lookup strategy for the code mapping. We
// need to know if a run has been seen before, and be able to map that run
// to the output code. Since we start with known unique ids (input bytes),
// and then from those build more unique ids (table entries), we can
// continue this chain (almost like a linked list) to always have small
// integer values that represent the current byte chains in the encoder.
// This means instead of tracking the input bytes (AAAABCD) to know our
// current state, we can track the table entry for AAAABC (it is guaranteed
// to exist by the nature of the algorithm) and the next character D.
// Therefor the tuple of (table_entry, byte) is guaranteed to also be
// unique. This allows us to create a simple lookup key for mapping input
// sequences to codes (table indices) without having to store or search
// any of the code sequences. So if 'AAAA' has a table entry of 12, the
// tuple of ('AAAA', K) for any input byte K will be unique, and can be our
// key. This leads to a integer value at most 20-bits, which can always
// fit in an SMI value and be used as a fast sparse array / object key.
// Output code for the current contents of the index buffer.
let ib_code = index_stream[0] & code_mask; // Load first input index.
let code_table = {}; // Key'd on our 20-bit "tuple".
emit_code(clear_code); // Spec says first code should be a clear code.
// First index already loaded, process the rest of the stream.
for (let i = 1, il = index_stream.length; i < il; ++i) {
const k = index_stream[i] & code_mask;
const cur_key = (ib_code << 8) | k; // (prev, k) unique tuple.
const cur_code = code_table[cur_key]; // buffer + k.
// Check if we have to create a new code table entry.
if (cur_code === undefined) {
// We don't have buffer + k.
// Emit index buffer (without k).
// This is an inline version of emit_code, because this is the core
// writing routine of the compressor (and V8 cannot inline emit_code
// because it is a closure here in a different context). Additionally
// we can call emit_byte_to_buffer less often, because we can have
// 30-bits (from our 31-bit signed SMI), and we know our codes will only
// be 12-bits, so can safely have 18-bits there without overflow.
// emit_code(ib_code);
cur |= ib_code << cur_shift;
cur_shift += cur_code_size;
while (cur_shift >= 8) {
buf[p++] = cur & 0xff;
cur >>= 8;
cur_shift -= 8;
if (p === cur_subblock + 256) {
// Finished a subblock.
buf[cur_subblock] = 255;
cur_subblock = p++;
}
}
if (next_code === 4096) {
// Table full, need a clear.
emit_code(clear_code);
next_code = eoi_code + 1;
cur_code_size = min_code_size + 1;
code_table = {};
} else {
// Table not full, insert a new entry.
// Increase our variable bit code sizes if necessary. This is a bit
// tricky as it is based on "timing" between the encoding and
// decoder. From the encoders perspective this should happen after
// we've already emitted the index buffer and are about to create the
// first table entry that would overflow our current code bit size.
if (next_code >= 1 << cur_code_size) ++cur_code_size;
code_table[cur_key] = next_code++; // Insert into code table.
}
ib_code = k; // Index buffer to single input k.
} else {
ib_code = cur_code; // Index buffer to sequence in code table.
}
}
emit_code(ib_code); // There will still be something in the index buffer.
emit_code(eoi_code); // End Of Information.
// Flush / finalize the sub-blocks stream to the buffer.
emit_bytes_to_buffer(1);
// Finish the sub-blocks, writing out any unfinished lengths and
// terminating with a sub-block of length 0. If we have already started
// but not yet used a sub-block it can just become the terminator.
if (cur_subblock + 1 === p) {
// Started but unused.
buf[cur_subblock] = 0;
} else {
// Started and used, write length and additional terminator block.
buf[cur_subblock] = p - cur_subblock - 1;
buf[p++] = 0;
}
return p;
}
function check_palette_and_num_colors(palette) {
const num_colors = palette.length;
if (num_colors < 2 || num_colors > 256 || num_colors & (num_colors - 1)) { throw 'Invalid code/color length, must be power of 2 and 2 .. 256.'; }
return num_colors;
}