michael@0: // The implementation of the [HTTP/2 Header Compression][http2-compression] spec is separated from
michael@0: // the 'integration' part which handles HEADERS and PUSH_PROMISE frames. The compression itself is
michael@0: // implemented in the first part of the file, and consists of three classes: `HeaderTable`,
michael@0: // `HeaderSetDecompressor` and `HeaderSetCompressor`. The two latter classes are
michael@0: // [Transform Stream][node-transform] subclasses that operate in [object mode][node-objectmode].
michael@0: // These transform chunks of binary data into `[name, value]` pairs and vice versa, and store their
michael@0: // state in `HeaderTable` instances.
michael@0: //
michael@0: // The 'integration' part is also implemented by two [Transform Stream][node-transform] subclasses
michael@0: // that operate in [object mode][node-objectmode]: the `Compressor` and the `Decompressor`. These
michael@0: // provide a layer between the [framer](framer.html) and the
michael@0: // [connection handling component](connection.html).
michael@0: //
michael@0: // [node-transform]: http://nodejs.org/api/stream.html#stream_class_stream_transform
michael@0: // [node-objectmode]: http://nodejs.org/api/stream.html#stream_new_stream_readable_options
michael@0: // [http2-compression]: http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05
michael@0: 
michael@0: exports.HeaderTable = HeaderTable;
michael@0: exports.HuffmanTable = HuffmanTable;
michael@0: exports.HeaderSetCompressor = HeaderSetCompressor;
michael@0: exports.HeaderSetDecompressor = HeaderSetDecompressor;
michael@0: exports.Compressor = Compressor;
michael@0: exports.Decompressor = Decompressor;
michael@0: 
michael@0: var TransformStream = require('stream').Transform;
michael@0: var assert = require('assert');
michael@0: var util = require('util');
michael@0: 
michael@0: // Header compression
michael@0: // ==================
michael@0: 
michael@0: // The HeaderTable class
michael@0: // ---------------------
michael@0: 
michael@0: // The [Header Table] is a component used to associate headers to index values. It is basically an
michael@0: // ordered list of `[name, value]` pairs, so it's implemented as a subclass of `Array`.
michael@0: // In this implementation, the Header Table and the [Static Table] are handled as a single table.
michael@0: // [Header Table]: http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-3.1.2
michael@0: // [Static Table]: http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-B
michael@0: function HeaderTable(log, limit) {
michael@0:   var self = HeaderTable.staticTable.map(entryFromPair);
michael@0:   self._log = log;
michael@0:   self._limit = limit || DEFAULT_HEADER_TABLE_LIMIT;
michael@0:   self._staticLength = self.length;
michael@0:   self._size = 0;
michael@0:   self._enforceLimit = HeaderTable.prototype._enforceLimit;
michael@0:   self.add = HeaderTable.prototype.add;
michael@0:   self.setSizeLimit = HeaderTable.prototype.setSizeLimit;
michael@0:   return self;
michael@0: }
michael@0: 
michael@0: // There are few more sets that are needed for the compression/decompression process that are all
michael@0: // subsets of the Header Table, and are implemented as flags on header table entries:
michael@0: //
michael@0: // * [Reference Set][referenceset]: contains a group of headers used as a reference for the
michael@0: //   differential encoding of a new set of headers. (`reference` flag)
michael@0: // * Emitted headers: the headers that are already emitted as part of the current decompression
michael@0: //   process (not part of the spec, `emitted` flag)
michael@0: // * Headers to be kept: headers that should not be removed as the last step of the encoding process
michael@0: //   (not part of the spec, `keep` flag)
michael@0: //
michael@0: // [referenceset]: http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-3.1.3
michael@0: //
michael@0: // Relations of the sets:
michael@0: //
michael@0: //     ,----------------------------------.
michael@0: //     |           Header Table           |
michael@0: //     |                                  |
michael@0: //     |  ,----------------------------.  |
michael@0: //     |  |        Reference Set       |  |
michael@0: //     |  |                            |  |
michael@0: //     |  |  ,---------.  ,---------.  |  |
michael@0: //     |  |  |  Keep   |  | Emitted |  |  |
michael@0: //     |  |  |         |  |         |  |  |
michael@0: //     |  |  `---------'  `---------'  |  |
michael@0: //     |  `----------------------------'  |
michael@0: //     `----------------------------------'
michael@0: function entryFromPair(pair) {
michael@0:   var entry = pair.slice();
michael@0:   entry.reference = false;
michael@0:   entry.emitted = false;
michael@0:   entry.keep = false;
michael@0:   entry._size = size(entry);
michael@0:   return entry;
michael@0: }
michael@0: 
michael@0: // The encoder decides how to update the header table and as such can control how much memory is
michael@0: // used by the header table.  To limit the memory requirements on the decoder side, the header table
michael@0: // size is bounded.
michael@0: //
michael@0: // * The default header table size limit is 4096 bytes.
michael@0: // * The size of an entry is defined as follows: the size of an entry is the sum of its name's
michael@0: //   length in bytes, of its value's length in bytes and of 32 bytes.
michael@0: // * The size of a header table is the sum of the size of its entries.
michael@0: var DEFAULT_HEADER_TABLE_LIMIT = 4096;
michael@0: 
michael@0: function size(entry) {
michael@0:   return (new Buffer(entry[0] + entry[1], 'utf8')).length + 32;
michael@0: }
michael@0: 
michael@0: // The `add(index, entry)` can be used to [manage the header table][tablemgmt]:
michael@0: // [tablemgmt]: http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-3.3
michael@0: //
michael@0: // * it pushes the new `entry` at the beggining of the table
michael@0: // * before doing such a modification, it has to be ensured that the header table size will stay
michael@0: //   lower than or equal to the header table size limit. To achieve this, entries are evicted from
michael@0: //   the end of the header table until the size of the header table is less than or equal to
michael@0: //   `(this._limit - entry.size)`, or until the table is empty.
michael@0: //
michael@0: //              <----------  Index Address Space ---------->
michael@0: //              <-- Header  Table -->  <-- Static  Table -->
michael@0: //              +---+-----------+---+  +---+-----------+---+
michael@0: //              | 0 |    ...    | k |  |k+1|    ...    | n |
michael@0: //              +---+-----------+---+  +---+-----------+---+
michael@0: //              ^                   |
michael@0: //              |                   V
michael@0: //       Insertion Point       Drop Point
michael@0: 
michael@0: HeaderTable.prototype._enforceLimit = function _enforceLimit(limit) {
michael@0:   var droppedEntries = [];
michael@0:   var dropPoint = this.length - this._staticLength;
michael@0:   while ((this._size > limit) && (dropPoint > 0)) {
michael@0:     dropPoint -= 1;
michael@0:     var dropped = this.splice(dropPoint, 1)[0];
michael@0:     this._size -= dropped._size;
michael@0:     droppedEntries[dropPoint] = dropped;
michael@0:   }
michael@0:   return droppedEntries;
michael@0: };
michael@0: 
michael@0: HeaderTable.prototype.add = function(entry) {
michael@0:   var limit = this._limit - entry._size;
michael@0:   var droppedEntries = this._enforceLimit(limit);
michael@0: 
michael@0:   if (this._size <= limit) {
michael@0:     this.unshift(entry);
michael@0:     this._size += entry._size;
michael@0:   }
michael@0: 
michael@0:   return droppedEntries;
michael@0: };
michael@0: 
michael@0: // The table size limit can be changed externally. In this case, the same eviction algorithm is used
michael@0: HeaderTable.prototype.setSizeLimit = function setSizeLimit(limit) {
michael@0:   this._limit = limit;
michael@0:   this._enforceLimit(this._limit);
michael@0: };
michael@0: 
michael@0: // [The Static Table](http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-B)
michael@0: // ------------------
michael@0: // [statictable]:http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-B
michael@0: 
michael@0: // The table is generated with feeding the table from the spec to the following sed command:
michael@0: //
michael@0: //     sed -re "s/\s*\| [0-9]+\s*\| ([^ ]*)/  [ '\1'/g" -e "s/\|\s([^ ]*)/, '\1'/g" -e 's/ \|/],/g'
michael@0: 
michael@0: HeaderTable.staticTable  = [
michael@0:   [ ':authority'                  , ''            ],
michael@0:   [ ':method'                     , 'GET'         ],
michael@0:   [ ':method'                     , 'POST'        ],
michael@0:   [ ':path'                       , '/'           ],
michael@0:   [ ':path'                       , '/index.html' ],
michael@0:   [ ':scheme'                     , 'http'        ],
michael@0:   [ ':scheme'                     , 'https'       ],
michael@0:   [ ':status'                     , '200'         ],
michael@0:   [ ':status'                     , '500'         ],
michael@0:   [ ':status'                     , '404'         ],
michael@0:   [ ':status'                     , '403'         ],
michael@0:   [ ':status'                     , '400'         ],
michael@0:   [ ':status'                     , '401'         ],
michael@0:   [ 'accept-charset'              , ''            ],
michael@0:   [ 'accept-encoding'             , ''            ],
michael@0:   [ 'accept-language'             , ''            ],
michael@0:   [ 'accept-ranges'               , ''            ],
michael@0:   [ 'accept'                      , ''            ],
michael@0:   [ 'access-control-allow-origin' , ''            ],
michael@0:   [ 'age'                         , ''            ],
michael@0:   [ 'allow'                       , ''            ],
michael@0:   [ 'authorization'               , ''            ],
michael@0:   [ 'cache-control'               , ''            ],
michael@0:   [ 'content-disposition'         , ''            ],
michael@0:   [ 'content-encoding'            , ''            ],
michael@0:   [ 'content-language'            , ''            ],
michael@0:   [ 'content-length'              , ''            ],
michael@0:   [ 'content-location'            , ''            ],
michael@0:   [ 'content-range'               , ''            ],
michael@0:   [ 'content-type'                , ''            ],
michael@0:   [ 'cookie'                      , ''            ],
michael@0:   [ 'date'                        , ''            ],
michael@0:   [ 'etag'                        , ''            ],
michael@0:   [ 'expect'                      , ''            ],
michael@0:   [ 'expires'                     , ''            ],
michael@0:   [ 'from'                        , ''            ],
michael@0:   [ 'host'                        , ''            ],
michael@0:   [ 'if-match'                    , ''            ],
michael@0:   [ 'if-modified-since'           , ''            ],
michael@0:   [ 'if-none-match'               , ''            ],
michael@0:   [ 'if-range'                    , ''            ],
michael@0:   [ 'if-unmodified-since'         , ''            ],
michael@0:   [ 'last-modified'               , ''            ],
michael@0:   [ 'link'                        , ''            ],
michael@0:   [ 'location'                    , ''            ],
michael@0:   [ 'max-forwards'                , ''            ],
michael@0:   [ 'proxy-authenticate'          , ''            ],
michael@0:   [ 'proxy-authorization'         , ''            ],
michael@0:   [ 'range'                       , ''            ],
michael@0:   [ 'referer'                     , ''            ],
michael@0:   [ 'refresh'                     , ''            ],
michael@0:   [ 'retry-after'                 , ''            ],
michael@0:   [ 'server'                      , ''            ],
michael@0:   [ 'set-cookie'                  , ''            ],
michael@0:   [ 'strict-transport-security'   , ''            ],
michael@0:   [ 'transfer-encoding'           , ''            ],
michael@0:   [ 'user-agent'                  , ''            ],
michael@0:   [ 'vary'                        , ''            ],
michael@0:   [ 'via'                         , ''            ],
michael@0:   [ 'www-authenticate'            , ''            ]
michael@0: ];
michael@0: 
michael@0: // The HeaderSetDecompressor class
michael@0: // -------------------------------
michael@0: 
michael@0: // A `HeaderSetDecompressor` instance is a transform stream that can be used to *decompress a
michael@0: // single header set*. Its input is a stream of binary data chunks and its output is a stream of
michael@0: // `[name, value]` pairs.
michael@0: //
michael@0: // Currently, it is not a proper streaming decompressor implementation, since it buffer its input
michael@0: // until the end os the stream, and then processes the whole header block at once.
michael@0: 
michael@0: util.inherits(HeaderSetDecompressor, TransformStream);
michael@0: function HeaderSetDecompressor(log, table) {
michael@0:   TransformStream.call(this, { objectMode: true });
michael@0: 
michael@0:   this._log = log.child({ component: 'compressor' });
michael@0:   this._table = table;
michael@0:   this._chunks = [];
michael@0: }
michael@0: 
michael@0: // `_transform` is the implementation of the [corresponding virtual function][_transform] of the
michael@0: // TransformStream class. It collects the data chunks for later processing.
michael@0: // [_transform]: http://nodejs.org/api/stream.html#stream_transform_transform_chunk_encoding_callback
michael@0: HeaderSetDecompressor.prototype._transform = function _transform(chunk, encoding, callback) {
michael@0:   this._chunks.push(chunk);
michael@0:   callback();
michael@0: };
michael@0: 
michael@0: // `execute(rep)` executes the given [header representation][representation].
michael@0: // [representation]: http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-3.1.4
michael@0: 
michael@0: // The *JavaScript object representation* of a header representation:
michael@0: //
michael@0: //     {
michael@0: //       name: String || Integer,  // string literal or index
michael@0: //       value: String || Integer, // string literal or index
michael@0: //       index: Boolean            // with or without indexing
michael@0: //     }
michael@0: //
michael@0: // *Important:* to ease the indexing of the header table, indexes start at 0 instead of 1.
michael@0: //
michael@0: // Examples:
michael@0: //
michael@0: //     Indexed:
michael@0: //     { name: 2  , value: 2  , index: false }
michael@0: //     { name: -1 , value: -1 , index: false } // reference set emptying
michael@0: //     Literal:
michael@0: //     { name: 2  , value: 'X', index: false } // without indexing
michael@0: //     { name: 2  , value: 'Y', index: true  } // with indexing
michael@0: //     { name: 'A', value: 'Z', index: true  } // with indexing, literal name
michael@0: HeaderSetDecompressor.prototype._execute = function _execute(rep) {
michael@0:   this._log.trace({ key: rep.name, value: rep.value, index: rep.index },
michael@0:                   'Executing header representation');
michael@0: 
michael@0:   var entry, pair;
michael@0: 
michael@0:   // * An _indexed representation_ with an index value of 0 (in our representation, it means -1)
michael@0:   //   entails the following actions:
michael@0:   //   * If the following byte starts with a set bit, the reference set is emptied.
michael@0:   //   * Else, reduce the size of the header table to the value encoded with a 7-bit prefix
michael@0:   // * An _indexed representation_ corresponding to an entry _present_ in the reference set
michael@0:   //   entails the following actions:
michael@0:   //   * The entry is removed from the reference set.
michael@0:   // * An _indexed representation_ corresponding to an entry _not present_ in the reference set
michael@0:   //   entails the following actions:
michael@0:   //   * If referencing an element of the static table:
michael@0:   //     * The header field corresponding to the referenced entry is emitted
michael@0:   //     * The referenced static entry is added to the header table
michael@0:   //     * A reference to this new header table entry is added to the reference set (except if
michael@0:   //       this new entry didn't fit in the header table)
michael@0:   //   * If referencing an element of the header table:
michael@0:   //     * The header field corresponding to the referenced entry is emitted
michael@0:   //     * The referenced header table entry is added to the reference set
michael@0:   if (typeof rep.value === 'number') {
michael@0:     var index = rep.value;
michael@0:     entry = this._table[index];
michael@0: 
michael@0:     if (index == -1) {
michael@0:       if (rep.index) {
michael@0:         for (var i = 0; i < this._table.length; i++) {
michael@0:           this._table[i].reference = false;
michael@0:         }
michael@0:       } else {
michael@0:         // Set a new maximum size
michael@0:         this.setTableSizeLimit(rep.name);
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     else if (entry.reference) {
michael@0:       entry.reference = false;
michael@0:     }
michael@0: 
michael@0:     else {
michael@0:       pair = entry.slice();
michael@0:       this.push(pair);
michael@0: 
michael@0:       if (index >= this._table.length - this._table._staticLength) {
michael@0:         entry = entryFromPair(pair);
michael@0:         this._table.add(entry);
michael@0:       }
michael@0: 
michael@0:       entry.reference = true;
michael@0:       entry.emitted = true;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // * A _literal representation_ that is _not added_ to the header table entails the following
michael@0:   //   action:
michael@0:   //   * The header is emitted.
michael@0:   // * A _literal representation_ that is _added_ to the header table entails the following further
michael@0:   //   actions:
michael@0:   //   * The header is added to the header table.
michael@0:   //   * The new entry is added to the reference set.
michael@0:   else {
michael@0:     if (typeof rep.name === 'number') {
michael@0:       pair = [this._table[rep.name][0], rep.value];
michael@0:     } else {
michael@0:       pair = [rep.name, rep.value];
michael@0:     }
michael@0: 
michael@0:     if (rep.index) {
michael@0:       entry = entryFromPair(pair);
michael@0:       entry.reference = true;
michael@0:       entry.emitted = true;
michael@0:       this._table.add(entry);
michael@0:     }
michael@0: 
michael@0:     this.push(pair);
michael@0:   }
michael@0: };
michael@0: 
michael@0: // `_flush` is the implementation of the [corresponding virtual function][_flush] of the
michael@0: // TransformStream class. The whole decompressing process is done in `_flush`. It gets called when
michael@0: // the input stream is over.
michael@0: // [_flush]: http://nodejs.org/api/stream.html#stream_transform_flush_callback
michael@0: HeaderSetDecompressor.prototype._flush = function _flush(callback) {
michael@0:   var buffer = concat(this._chunks);
michael@0: 
michael@0:   // * processes the header representations
michael@0:   buffer.cursor = 0;
michael@0:   while (buffer.cursor < buffer.length) {
michael@0:     this._execute(HeaderSetDecompressor.header(buffer));
michael@0:   }
michael@0: 
michael@0:   // * [emits the reference set](http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-3.2.2)
michael@0:   for (var index = 0; index < this._table.length; index++) {
michael@0:     var entry = this._table[index];
michael@0:     if (entry.reference && !entry.emitted) {
michael@0:       this.push(entry.slice());
michael@0:     }
michael@0:     entry.emitted = false;
michael@0:   }
michael@0: 
michael@0:   callback();
michael@0: };
michael@0: 
michael@0: // The HeaderSetCompressor class
michael@0: // -----------------------------
michael@0: 
michael@0: // A `HeaderSetCompressor` instance is a transform stream that can be used to *compress a single
michael@0: // header set*. Its input is a stream of `[name, value]` pairs and its output is a stream of
michael@0: // binary data chunks.
michael@0: //
michael@0: // It is a real streaming compressor, since it does not wait until the header set is complete.
michael@0: //
michael@0: // The compression algorithm is (intentionally) not specified by the spec. Therefore, the current
michael@0: // compression algorithm can probably be improved in the future.
michael@0: 
michael@0: util.inherits(HeaderSetCompressor, TransformStream);
michael@0: function HeaderSetCompressor(log, table) {
michael@0:   TransformStream.call(this, { objectMode: true });
michael@0: 
michael@0:   this._log = log.child({ component: 'compressor' });
michael@0:   this._table = table;
michael@0:   this.push = TransformStream.prototype.push.bind(this);
michael@0: }
michael@0: 
michael@0: HeaderSetCompressor.prototype.send = function send(rep) {
michael@0:   this._log.trace({ key: rep.name, value: rep.value, index: rep.index },
michael@0:                   'Emitting header representation');
michael@0: 
michael@0:   if (!rep.chunks) {
michael@0:     rep.chunks = HeaderSetCompressor.header(rep);
michael@0:   }
michael@0:   rep.chunks.forEach(this.push);
michael@0: };
michael@0: 
michael@0: // `_transform` is the implementation of the [corresponding virtual function][_transform] of the
michael@0: // TransformStream class. It processes the input headers one by one:
michael@0: // [_transform]: http://nodejs.org/api/stream.html#stream_transform_transform_chunk_encoding_callback
michael@0: HeaderSetCompressor.prototype._transform = function _transform(pair, encoding, callback) {
michael@0:   var name = pair[0].toLowerCase();
michael@0:   var value = pair[1];
michael@0:   var entry, rep;
michael@0: 
michael@0:   // * tries to find full (name, value) or name match in the header table
michael@0:   var nameMatch = -1, fullMatch = -1;
michael@0:   for (var droppedIndex = 0; droppedIndex < this._table.length; droppedIndex++) {
michael@0:     entry = this._table[droppedIndex];
michael@0:     if (entry[0] === name) {
michael@0:       if (entry[1] === value) {
michael@0:         fullMatch = droppedIndex;
michael@0:         break;
michael@0:       } else if (nameMatch === -1) {
michael@0:         nameMatch = droppedIndex;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // * if there's full match, it will be an indexed representation (or more than one) depending
michael@0:   //   on its presence in the reference, the emitted and the keep set:
michael@0:   //
michael@0:   //   * If the entry is outside the reference set, then a single indexed representation puts the
michael@0:   //     entry into it and emits the header. Note that if the matched entry is in the static table,
michael@0:   //     then it has to be added to the header table.
michael@0:   //
michael@0:   //   * If it's already in the keep set, then 4 indexed representations are needed:
michael@0:   //
michael@0:   //     1. removes it from the reference set
michael@0:   //     2. puts it back in the reference set and emits the header once
michael@0:   //     3. removes it again
michael@0:   //     4. puts it back and emits it again for the second time
michael@0:   //
michael@0:   //     It won't be emitted at the end of the decoding process since it's now in the emitted set.
michael@0:   //
michael@0:   //   * If it's in the emitted set, then 2 indexed representations are needed:
michael@0:   //
michael@0:   //     1. removes it from the reference set
michael@0:   //     2. puts it back in the reference set and emits the header once
michael@0:   //
michael@0:   //   * If it's in the reference set, but outside the keep set and the emitted set, then this
michael@0:   //     header is common with the previous header set, and is still untouched. We mark it to keep
michael@0:   //     in the reference set (that means don't remove at the end of the encoding process).
michael@0:   if (fullMatch !== -1) {
michael@0:     rep = { name: fullMatch, value: fullMatch, index: false };
michael@0: 
michael@0:     if (!entry.reference) {
michael@0:       if (fullMatch >= this._table.length - this._table._staticLength) {
michael@0:         entry = entryFromPair(pair);
michael@0:         this._table.add(entry);
michael@0:       }
michael@0:       this.send(rep);
michael@0:       entry.reference = true;
michael@0:       entry.emitted = true;
michael@0:     }
michael@0: 
michael@0:     else if (entry.keep) {
michael@0:       this.send(rep);
michael@0:       this.send(rep);
michael@0:       this.send(rep);
michael@0:       this.send(rep);
michael@0:       entry.keep = false;
michael@0:       entry.emitted = true;
michael@0:     }
michael@0: 
michael@0:     else if (entry.emitted) {
michael@0:       this.send(rep);
michael@0:       this.send(rep);
michael@0:     }
michael@0: 
michael@0:     else {
michael@0:       entry.keep = true;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // * otherwise, it will be a literal representation (with a name index if there's a name match)
michael@0:   else {
michael@0:     entry = entryFromPair(pair);
michael@0:     entry.emitted = true;
michael@0: 
michael@0:     var indexing = (entry._size < this._table._limit / 2);
michael@0: 
michael@0:     if (indexing) {
michael@0:       entry.reference = true;
michael@0:       var droppedEntries = this._table.add(entry);
michael@0:       for (droppedIndex in droppedEntries) {
michael@0:         droppedIndex = Number(droppedIndex)
michael@0:         var dropped = droppedEntries[droppedIndex];
michael@0:         if (dropped.keep) {
michael@0:           rep = { name: droppedIndex, value: droppedIndex, index: false };
michael@0:           this.send(rep);
michael@0:           this.send(rep);
michael@0:         }
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     this.send({ name: (nameMatch !== -1) ? nameMatch : name, value: value, index: indexing });
michael@0:   }
michael@0: 
michael@0:   callback();
michael@0: };
michael@0: 
michael@0: // `_flush` is the implementation of the [corresponding virtual function][_flush] of the
michael@0: // TransformStream class. It gets called when there's no more header to compress. The final step:
michael@0: // [_flush]: http://nodejs.org/api/stream.html#stream_transform_flush_callback
michael@0: HeaderSetCompressor.prototype._flush = function _flush(callback) {
michael@0:   // * removing entries from the header set that are not marked to be kept or emitted
michael@0:   for (var index = 0; index < this._table.length; index++) {
michael@0:     var entry = this._table[index];
michael@0:     if (entry.reference && !entry.keep && !entry.emitted) {
michael@0:       this.send({ name: index, value: index, index: false });
michael@0:       entry.reference = false;
michael@0:     }
michael@0:     entry.keep = false;
michael@0:     entry.emitted = false;
michael@0:   }
michael@0: 
michael@0:   callback();
michael@0: };
michael@0: 
michael@0: // [Detailed Format](http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-4)
michael@0: // -----------------
michael@0: 
michael@0: // ### Integer representation ###
michael@0: //
michael@0: // The algorithm to represent an integer I is as follows:
michael@0: //
michael@0: // 1. If I < 2^N - 1, encode I on N bits
michael@0: // 2. Else, encode 2^N - 1 on N bits and do the following steps:
michael@0: //    1. Set I to (I - (2^N - 1)) and Q to 1
michael@0: //    2. While Q > 0
michael@0: //       1. Compute Q and R, quotient and remainder of I divided by 2^7
michael@0: //       2. If Q is strictly greater than 0, write one 1 bit; otherwise, write one 0 bit
michael@0: //       3. Encode R on the next 7 bits
michael@0: //       4. I = Q
michael@0: 
michael@0: HeaderSetCompressor.integer = function writeInteger(I, N) {
michael@0:   var limit = Math.pow(2,N) - 1;
michael@0:   if (I < limit) {
michael@0:     return [new Buffer([I])];
michael@0:   }
michael@0: 
michael@0:   var bytes = [];
michael@0:   if (N !== 0) {
michael@0:     bytes.push(limit);
michael@0:   }
michael@0:   I -= limit;
michael@0: 
michael@0:   var Q = 1, R;
michael@0:   while (Q > 0) {
michael@0:     Q = Math.floor(I / 128);
michael@0:     R = I % 128;
michael@0: 
michael@0:     if (Q > 0) {
michael@0:       R += 128;
michael@0:     }
michael@0:     bytes.push(R);
michael@0: 
michael@0:     I = Q;
michael@0:   }
michael@0: 
michael@0:   return [new Buffer(bytes)];
michael@0: };
michael@0: 
michael@0: // The inverse algorithm:
michael@0: //
michael@0: // 1. Set I to the number coded on the lower N bits of the first byte
michael@0: // 2. If I is smaller than 2^N - 1 then return I
michael@0: // 2. Else the number is encoded on more than one byte, so do the following steps:
michael@0: //    1. Set M to 0
michael@0: //    2. While returning with I
michael@0: //       1. Let B be the next byte (the first byte if N is 0)
michael@0: //       2. Read out the lower 7 bits of B and multiply it with 2^M
michael@0: //       3. Increase I with this number
michael@0: //       4. Increase M by 7
michael@0: //       5. Return I if the most significant bit of B is 0
michael@0: 
michael@0: HeaderSetDecompressor.integer = function readInteger(buffer, N) {
michael@0:   var limit = Math.pow(2,N) - 1;
michael@0: 
michael@0:   var I = buffer[buffer.cursor] & limit;
michael@0:   if (N !== 0) {
michael@0:     buffer.cursor += 1;
michael@0:   }
michael@0: 
michael@0:   if (I === limit) {
michael@0:     var M = 0;
michael@0:     do {
michael@0:       I += (buffer[buffer.cursor] & 127) << M;
michael@0:       M += 7;
michael@0:       buffer.cursor += 1;
michael@0:     } while (buffer[buffer.cursor - 1] & 128);
michael@0:   }
michael@0: 
michael@0:   return I;
michael@0: };
michael@0: 
michael@0: // ### Huffman Encoding ###
michael@0: 
michael@0: function HuffmanTable(table) {
michael@0:   function createTree(codes, position) {
michael@0:     if (codes.length === 1) {
michael@0:       return [table.indexOf(codes[0])];
michael@0:     }
michael@0: 
michael@0:     else {
michael@0:       position = position || 0;
michael@0:       var zero = [];
michael@0:       var one = [];
michael@0:       for (var i = 0; i < codes.length; i++) {
michael@0:         var string = codes[i];
michael@0:         if (string[position] === '0') {
michael@0:           zero.push(string);
michael@0:         } else {
michael@0:           one.push(string);
michael@0:         }
michael@0:       }
michael@0:       return [createTree(zero, position + 1), createTree(one, position + 1)];
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   this.tree = createTree(table);
michael@0: 
michael@0:   this.codes = table.map(function(bits) {
michael@0:     return parseInt(bits, 2);
michael@0:   });
michael@0:   this.lengths = table.map(function(bits) {
michael@0:     return bits.length;
michael@0:   });
michael@0: }
michael@0: 
michael@0: HuffmanTable.prototype.encode = function encode(buffer) {
michael@0:   var result = [];
michael@0:   var space = 8;
michael@0: 
michael@0:   function add(data) {
michael@0:     if (space === 8) {
michael@0:       result.push(data);
michael@0:     } else {
michael@0:       result[result.length - 1] |= data;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   for (var i = 0; i < buffer.length; i++) {
michael@0:     var byte = buffer[i];
michael@0:     var code = this.codes[byte];
michael@0:     var length = this.lengths[byte];
michael@0: 
michael@0:     while (length !== 0) {
michael@0:       if (space >= length) {
michael@0:         add(code << (space - length));
michael@0:         code = 0;
michael@0:         space -= length;
michael@0:         length = 0;
michael@0:       } else {
michael@0:         var shift = length - space;
michael@0:         var msb = code >> shift;
michael@0:         add(msb);
michael@0:         code -= msb << shift;
michael@0:         length -= space;
michael@0:         space = 0;
michael@0:       }
michael@0: 
michael@0:       if (space === 0) {
michael@0:         space = 8;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (space !== 8) {
michael@0:     add(this.codes[256] >> (this.lengths[256] - space));
michael@0:   }
michael@0: 
michael@0:   return new Buffer(result);
michael@0: }
michael@0: 
michael@0: HuffmanTable.prototype.decode = function decode(buffer) {
michael@0:   var result = [];
michael@0:   var subtree = this.tree;
michael@0: 
michael@0:   for (var i = 0; i < buffer.length; i++) {
michael@0:     var byte = buffer[i];
michael@0: 
michael@0:     for (var j = 0; j < 8; j++) {
michael@0:       var bit = (byte & 128) ? 1 : 0;
michael@0:       byte = byte << 1;
michael@0: 
michael@0:       subtree = subtree[bit];
michael@0:       if (subtree.length === 1) {
michael@0:         result.push(subtree[0]);
michael@0:         subtree = this.tree;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return new Buffer(result);
michael@0: }
michael@0: 
michael@0: // The initializer arrays for the Huffman tables are generated with feeding the tables from the
michael@0: // spec to this sed command:
michael@0: //
michael@0: //     sed -e "s/^.* [|]//g" -e "s/|//g" -e "s/ .*//g" -e "s/^/  '/g" -e "s/$/',/g"
michael@0: 
michael@0: HuffmanTable.huffmanTable = new HuffmanTable([
michael@0:   '111111111111111111110111010',
michael@0:   '111111111111111111110111011',
michael@0:   '111111111111111111110111100',
michael@0:   '111111111111111111110111101',
michael@0:   '111111111111111111110111110',
michael@0:   '111111111111111111110111111',
michael@0:   '111111111111111111111000000',
michael@0:   '111111111111111111111000001',
michael@0:   '111111111111111111111000010',
michael@0:   '111111111111111111111000011',
michael@0:   '111111111111111111111000100',
michael@0:   '111111111111111111111000101',
michael@0:   '111111111111111111111000110',
michael@0:   '111111111111111111111000111',
michael@0:   '111111111111111111111001000',
michael@0:   '111111111111111111111001001',
michael@0:   '111111111111111111111001010',
michael@0:   '111111111111111111111001011',
michael@0:   '111111111111111111111001100',
michael@0:   '111111111111111111111001101',
michael@0:   '111111111111111111111001110',
michael@0:   '111111111111111111111001111',
michael@0:   '111111111111111111111010000',
michael@0:   '111111111111111111111010001',
michael@0:   '111111111111111111111010010',
michael@0:   '111111111111111111111010011',
michael@0:   '111111111111111111111010100',
michael@0:   '111111111111111111111010101',
michael@0:   '111111111111111111111010110',
michael@0:   '111111111111111111111010111',
michael@0:   '111111111111111111111011000',
michael@0:   '111111111111111111111011001',
michael@0:   '11101000',
michael@0:   '111111111100',
michael@0:   '11111111111010',
michael@0:   '111111111111100',
michael@0:   '111111111111101',
michael@0:   '100100',
michael@0:   '1101110',
michael@0:   '111111111111110',
michael@0:   '11111111010',
michael@0:   '11111111011',
michael@0:   '1111111010',
michael@0:   '11111111100',
michael@0:   '11101001',
michael@0:   '100101',
michael@0:   '00100',
michael@0:   '0000',
michael@0:   '00101',
michael@0:   '00110',
michael@0:   '00111',
michael@0:   '100110',
michael@0:   '100111',
michael@0:   '101000',
michael@0:   '101001',
michael@0:   '101010',
michael@0:   '101011',
michael@0:   '101100',
michael@0:   '111101100',
michael@0:   '11101010',
michael@0:   '111111111111111110',
michael@0:   '101101',
michael@0:   '11111111111111100',
michael@0:   '111101101',
michael@0:   '11111111111011',
michael@0:   '1101111',
michael@0:   '11101011',
michael@0:   '11101100',
michael@0:   '11101101',
michael@0:   '11101110',
michael@0:   '1110000',
michael@0:   '111101110',
michael@0:   '111101111',
michael@0:   '111110000',
michael@0:   '111110001',
michael@0:   '1111111011',
michael@0:   '111110010',
michael@0:   '11101111',
michael@0:   '111110011',
michael@0:   '111110100',
michael@0:   '111110101',
michael@0:   '111110110',
michael@0:   '111110111',
michael@0:   '11110000',
michael@0:   '11110001',
michael@0:   '111111000',
michael@0:   '111111001',
michael@0:   '111111010',
michael@0:   '111111011',
michael@0:   '111111100',
michael@0:   '1111111100',
michael@0:   '11111111111100',
michael@0:   '111111111111111111111011010',
michael@0:   '1111111111100',
michael@0:   '11111111111101',
michael@0:   '101110',
michael@0:   '1111111111111111110',
michael@0:   '01000',
michael@0:   '101111',
michael@0:   '01001',
michael@0:   '110000',
michael@0:   '0001',
michael@0:   '110001',
michael@0:   '110010',
michael@0:   '110011',
michael@0:   '01010',
michael@0:   '1110001',
michael@0:   '1110010',
michael@0:   '01011',
michael@0:   '110100',
michael@0:   '01100',
michael@0:   '01101',
michael@0:   '01110',
michael@0:   '11110010',
michael@0:   '01111',
michael@0:   '10000',
michael@0:   '10001',
michael@0:   '110101',
michael@0:   '1110011',
michael@0:   '110110',
michael@0:   '11110011',
michael@0:   '11110100',
michael@0:   '11110101',
michael@0:   '11111111111111101',
michael@0:   '11111111101',
michael@0:   '11111111111111110',
michael@0:   '111111111101',
michael@0:   '111111111111111111111011011',
michael@0:   '111111111111111111111011100',
michael@0:   '111111111111111111111011101',
michael@0:   '111111111111111111111011110',
michael@0:   '111111111111111111111011111',
michael@0:   '111111111111111111111100000',
michael@0:   '111111111111111111111100001',
michael@0:   '111111111111111111111100010',
michael@0:   '111111111111111111111100011',
michael@0:   '111111111111111111111100100',
michael@0:   '111111111111111111111100101',
michael@0:   '111111111111111111111100110',
michael@0:   '111111111111111111111100111',
michael@0:   '111111111111111111111101000',
michael@0:   '111111111111111111111101001',
michael@0:   '111111111111111111111101010',
michael@0:   '111111111111111111111101011',
michael@0:   '111111111111111111111101100',
michael@0:   '111111111111111111111101101',
michael@0:   '111111111111111111111101110',
michael@0:   '111111111111111111111101111',
michael@0:   '111111111111111111111110000',
michael@0:   '111111111111111111111110001',
michael@0:   '111111111111111111111110010',
michael@0:   '111111111111111111111110011',
michael@0:   '111111111111111111111110100',
michael@0:   '111111111111111111111110101',
michael@0:   '111111111111111111111110110',
michael@0:   '111111111111111111111110111',
michael@0:   '111111111111111111111111000',
michael@0:   '111111111111111111111111001',
michael@0:   '111111111111111111111111010',
michael@0:   '111111111111111111111111011',
michael@0:   '111111111111111111111111100',
michael@0:   '111111111111111111111111101',
michael@0:   '111111111111111111111111110',
michael@0:   '111111111111111111111111111',
michael@0:   '11111111111111111110000000',
michael@0:   '11111111111111111110000001',
michael@0:   '11111111111111111110000010',
michael@0:   '11111111111111111110000011',
michael@0:   '11111111111111111110000100',
michael@0:   '11111111111111111110000101',
michael@0:   '11111111111111111110000110',
michael@0:   '11111111111111111110000111',
michael@0:   '11111111111111111110001000',
michael@0:   '11111111111111111110001001',
michael@0:   '11111111111111111110001010',
michael@0:   '11111111111111111110001011',
michael@0:   '11111111111111111110001100',
michael@0:   '11111111111111111110001101',
michael@0:   '11111111111111111110001110',
michael@0:   '11111111111111111110001111',
michael@0:   '11111111111111111110010000',
michael@0:   '11111111111111111110010001',
michael@0:   '11111111111111111110010010',
michael@0:   '11111111111111111110010011',
michael@0:   '11111111111111111110010100',
michael@0:   '11111111111111111110010101',
michael@0:   '11111111111111111110010110',
michael@0:   '11111111111111111110010111',
michael@0:   '11111111111111111110011000',
michael@0:   '11111111111111111110011001',
michael@0:   '11111111111111111110011010',
michael@0:   '11111111111111111110011011',
michael@0:   '11111111111111111110011100',
michael@0:   '11111111111111111110011101',
michael@0:   '11111111111111111110011110',
michael@0:   '11111111111111111110011111',
michael@0:   '11111111111111111110100000',
michael@0:   '11111111111111111110100001',
michael@0:   '11111111111111111110100010',
michael@0:   '11111111111111111110100011',
michael@0:   '11111111111111111110100100',
michael@0:   '11111111111111111110100101',
michael@0:   '11111111111111111110100110',
michael@0:   '11111111111111111110100111',
michael@0:   '11111111111111111110101000',
michael@0:   '11111111111111111110101001',
michael@0:   '11111111111111111110101010',
michael@0:   '11111111111111111110101011',
michael@0:   '11111111111111111110101100',
michael@0:   '11111111111111111110101101',
michael@0:   '11111111111111111110101110',
michael@0:   '11111111111111111110101111',
michael@0:   '11111111111111111110110000',
michael@0:   '11111111111111111110110001',
michael@0:   '11111111111111111110110010',
michael@0:   '11111111111111111110110011',
michael@0:   '11111111111111111110110100',
michael@0:   '11111111111111111110110101',
michael@0:   '11111111111111111110110110',
michael@0:   '11111111111111111110110111',
michael@0:   '11111111111111111110111000',
michael@0:   '11111111111111111110111001',
michael@0:   '11111111111111111110111010',
michael@0:   '11111111111111111110111011',
michael@0:   '11111111111111111110111100',
michael@0:   '11111111111111111110111101',
michael@0:   '11111111111111111110111110',
michael@0:   '11111111111111111110111111',
michael@0:   '11111111111111111111000000',
michael@0:   '11111111111111111111000001',
michael@0:   '11111111111111111111000010',
michael@0:   '11111111111111111111000011',
michael@0:   '11111111111111111111000100',
michael@0:   '11111111111111111111000101',
michael@0:   '11111111111111111111000110',
michael@0:   '11111111111111111111000111',
michael@0:   '11111111111111111111001000',
michael@0:   '11111111111111111111001001',
michael@0:   '11111111111111111111001010',
michael@0:   '11111111111111111111001011',
michael@0:   '11111111111111111111001100',
michael@0:   '11111111111111111111001101',
michael@0:   '11111111111111111111001110',
michael@0:   '11111111111111111111001111',
michael@0:   '11111111111111111111010000',
michael@0:   '11111111111111111111010001',
michael@0:   '11111111111111111111010010',
michael@0:   '11111111111111111111010011',
michael@0:   '11111111111111111111010100',
michael@0:   '11111111111111111111010101',
michael@0:   '11111111111111111111010110',
michael@0:   '11111111111111111111010111',
michael@0:   '11111111111111111111011000',
michael@0:   '11111111111111111111011001',
michael@0:   '11111111111111111111011010',
michael@0:   '11111111111111111111011011',
michael@0:   '11111111111111111111011100'
michael@0: ]);
michael@0: 
michael@0: // ### String literal representation ###
michael@0: //
michael@0: // Literal **strings** can represent header names or header values. There's two variant of the
michael@0: // string encoding:
michael@0: //
michael@0: // String literal with Huffman encoding:
michael@0: //
michael@0: //       0   1   2   3   4   5   6   7
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | 1 |  Value Length Prefix (7)  |
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     |   Value Length (0-N bytes)    |
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     ...
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | Huffman Encoded Data  |Padding|
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //
michael@0: // String literal without Huffman encoding:
michael@0: //
michael@0: //       0   1   2   3   4   5   6   7
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | 0 |  Value Length Prefix (7)  |
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     |   Value Length (0-N bytes)    |
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     ...
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     |  Field Bytes Without Encoding |
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: 
michael@0: HeaderSetCompressor.string = function writeString(str) {
michael@0:   str = new Buffer(str, 'utf8');
michael@0: 
michael@0:   var huffman = HuffmanTable.huffmanTable.encode(str);
michael@0:   if (huffman.length < str.length) {
michael@0:     var length = HeaderSetCompressor.integer(huffman.length, 7)
michael@0:     length[0][0] |= 128;
michael@0:     return length.concat(huffman);
michael@0:   }
michael@0: 
michael@0:   else {
michael@0:     length = HeaderSetCompressor.integer(str.length, 7)
michael@0:     return length.concat(str);
michael@0:   }
michael@0: };
michael@0: 
michael@0: HeaderSetDecompressor.string = function readString(buffer) {
michael@0:   var huffman = buffer[buffer.cursor] & 128;
michael@0:   var length = HeaderSetDecompressor.integer(buffer, 7);
michael@0:   var encoded = buffer.slice(buffer.cursor, buffer.cursor + length);
michael@0:   buffer.cursor += length;
michael@0:   return (huffman ? HuffmanTable.huffmanTable.decode(encoded) : encoded).toString('utf8');
michael@0: };
michael@0: 
michael@0: // ### Header represenations ###
michael@0: 
michael@0: // The JavaScript object representation is described near the
michael@0: // `HeaderSetDecompressor.prototype._execute()` method definition.
michael@0: //
michael@0: // **All binary header representations** start with a prefix signaling the representation type and
michael@0: // an index represented using prefix coded integers:
michael@0: //
michael@0: //       0   1   2   3   4   5   6   7
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | 1 |        Index (7+)         |  Indexed Representation
michael@0: //     +---+---------------------------+
michael@0: //
michael@0: //       0   1   2   3   4   5   6   7
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | 0 | 1 |      Index (6+)       |
michael@0: //     +---+---+---+-------------------+  Literal w/o Indexing
michael@0: //     |       Value Length (8+)       |
michael@0: //     +-------------------------------+  w/ Indexed Name
michael@0: //     | Value String (Length octets)  |
michael@0: //     +-------------------------------+
michael@0: //
michael@0: //       0   1   2   3   4   5   6   7
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | 0 | 1 |           0           |
michael@0: //     +---+---+---+-------------------+
michael@0: //     |       Name Length (8+)        |
michael@0: //     +-------------------------------+  Literal w/o Indexing
michael@0: //     |  Name String (Length octets)  |
michael@0: //     +-------------------------------+  w/ New Name
michael@0: //     |       Value Length (8+)       |
michael@0: //     +-------------------------------+
michael@0: //     | Value String (Length octets)  |
michael@0: //     +-------------------------------+
michael@0: //
michael@0: //       0   1   2   3   4   5   6   7
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | 0 | 0 |      Index (6+)       |
michael@0: //     +---+---+---+-------------------+  Literal w/ Incremental Indexing
michael@0: //     |       Value Length (8+)       |
michael@0: //     +-------------------------------+  w/ Indexed Name
michael@0: //     | Value String (Length octets)  |
michael@0: //     +-------------------------------+
michael@0: //
michael@0: //       0   1   2   3   4   5   6   7
michael@0: //     +---+---+---+---+---+---+---+---+
michael@0: //     | 0 | 0 |           0           |
michael@0: //     +---+---+---+-------------------+
michael@0: //     |       Name Length (8+)        |
michael@0: //     +-------------------------------+  Literal w/ Incremental Indexing
michael@0: //     |  Name String (Length octets)  |
michael@0: //     +-------------------------------+  w/ New Name
michael@0: //     |       Value Length (8+)       |
michael@0: //     +-------------------------------+
michael@0: //     | Value String (Length octets)  |
michael@0: //     +-------------------------------+
michael@0: //
michael@0: // The **Indexed Representation** consists of the 1-bit prefix and the Index that is represented as
michael@0: // a 7-bit prefix coded integer and nothing else.
michael@0: //
michael@0: // After the first bits, **all literal representations** specify the header name, either as a
michael@0: // pointer to the Header Table (Index) or a string literal. When the string literal representation
michael@0: // is used, the Index is set to 0 and the string literal starts at the second byte.
michael@0: //
michael@0: // For **all literal representations**, the specification of the header value comes next. It is
michael@0: // always represented as a string.
michael@0: 
michael@0: var representations = {
michael@0:   indexed             : { prefix: 7, pattern: 0x80 },
michael@0:   literal             : { prefix: 6, pattern: 0x40 },
michael@0:   literalIncremental  : { prefix: 6, pattern: 0x00 }
michael@0: };
michael@0: 
michael@0: HeaderSetCompressor.header = function writeHeader(header) {
michael@0:   var representation, buffers = [];
michael@0: 
michael@0:   if (typeof header.value === 'number') {
michael@0:     representation = representations.indexed;
michael@0:   } else if (header.index) {
michael@0:     representation = representations.literalIncremental;
michael@0:   } else {
michael@0:     representation = representations.literal;
michael@0:   }
michael@0: 
michael@0:   if (representation === representations.indexed) {
michael@0:     buffers.push(HeaderSetCompressor.integer(header.value + 1, representation.prefix));
michael@0:     if (header.value == -1) {
michael@0:       if (header.index) {
michael@0:         buffers.push(HeaderSetCompressor.integer(0x80, 8));
michael@0:       } else {
michael@0:         buffers.push(HeaderSetCompressor.integer(header.name, 7));
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   else {
michael@0:     if (typeof header.name === 'number') {
michael@0:       buffers.push(HeaderSetCompressor.integer(header.name + 1, representation.prefix));
michael@0:     } else {
michael@0:       buffers.push(HeaderSetCompressor.integer(0, representation.prefix));
michael@0:       buffers.push(HeaderSetCompressor.string(header.name));
michael@0:     }
michael@0:     buffers.push(HeaderSetCompressor.string(header.value));
michael@0:   }
michael@0: 
michael@0:   buffers[0][0][0] |= representation.pattern;
michael@0: 
michael@0:   return Array.prototype.concat.apply([], buffers); // array of arrays of buffers -> array of buffers
michael@0: };
michael@0: 
michael@0: HeaderSetDecompressor.header = function readHeader(buffer) {
michael@0:   var representation, header = {};
michael@0: 
michael@0:   var firstByte = buffer[buffer.cursor];
michael@0:   if (firstByte & 0x80) {
michael@0:     representation = representations.indexed;
michael@0:   } else if (firstByte & 0x40) {
michael@0:     representation = representations.literal;
michael@0:   } else {
michael@0:     representation = representations.literalIncremental;
michael@0:   }
michael@0: 
michael@0:   if (representation === representations.indexed) {
michael@0:     header.value = header.name = HeaderSetDecompressor.integer(buffer, representation.prefix) - 1;
michael@0:     header.index = false;
michael@0:     if (header.value === -1) {
michael@0:       if (buffer[buffer.cursor] & 0x80) {
michael@0:         header.index = true;
michael@0:         buffer.cursor += 1;
michael@0:       } else {
michael@0:         header.name = HeaderSetDecompressor.integer(buffer, 7);
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   else {
michael@0:     header.name = HeaderSetDecompressor.integer(buffer, representation.prefix) - 1;
michael@0:     if (header.name === -1) {
michael@0:       header.name = HeaderSetDecompressor.string(buffer);
michael@0:     }
michael@0:     header.value = HeaderSetDecompressor.string(buffer);
michael@0:     header.index = (representation === representations.literalIncremental);
michael@0:   }
michael@0: 
michael@0:   return header;
michael@0: };
michael@0: 
michael@0: // Integration with HTTP/2
michael@0: // =======================
michael@0: 
michael@0: // This section describes the interaction between the compressor/decompressor and the rest of the
michael@0: // HTTP/2 implementation. The `Compressor` and the `Decompressor` makes up a layer between the
michael@0: // [framer](framer.html) and the [connection handling component](connection.html). They let most
michael@0: // frames pass through, except HEADERS and PUSH_PROMISE frames. They convert the frames between
michael@0: // these two representations:
michael@0: //
michael@0: //     {                                   {
michael@0: //      type: 'HEADERS',                    type: 'HEADERS',
michael@0: //      flags: {},                          flags: {},
michael@0: //      stream: 1,               <===>      stream: 1,
michael@0: //      headers: {                          data: Buffer
michael@0: //       N1: 'V1',                         }
michael@0: //       N2: ['V1', 'V2', ...],
michael@0: //       // ...
michael@0: //      }
michael@0: //     }
michael@0: //
michael@0: // There are possibly several binary frame that belong to a single non-binary frame.
michael@0: 
michael@0: var MAX_HTTP_PAYLOAD_SIZE = 16383;
michael@0: 
michael@0: // The Compressor class
michael@0: // --------------------
michael@0: 
michael@0: // The Compressor transform stream is basically stateless.
michael@0: util.inherits(Compressor, TransformStream);
michael@0: function Compressor(log, type) {
michael@0:   TransformStream.call(this, { objectMode: true });
michael@0: 
michael@0:   this._log = log.child({ component: 'compressor' });
michael@0: 
michael@0:   assert((type === 'REQUEST') || (type === 'RESPONSE'));
michael@0:   this._table = new HeaderTable(this._log);
michael@0: }
michael@0: 
michael@0: // Changing the header table size
michael@0: Compressor.prototype.setTableSizeLimit = function setTableSizeLimit(size) {
michael@0:   this._table.setSizeLimit(size);
michael@0: };
michael@0: 
michael@0: // `compress` takes a header set, and compresses it using a new `HeaderSetCompressor` stream
michael@0: // instance. This means that from now on, the advantages of streaming header encoding are lost,
michael@0: // but the API becomes simpler.
michael@0: Compressor.prototype.compress = function compress(headers) {
michael@0:   var compressor = new HeaderSetCompressor(this._log, this._table);
michael@0:   for (var name in headers) {
michael@0:     var value = headers[name];
michael@0:     name = String(name).toLowerCase();
michael@0: 
michael@0:     // * To allow for better compression efficiency, the Cookie header field MAY be split into
michael@0:     //   separate header fields, each with one or more cookie-pairs.
michael@0:     if (name == 'cookie') {
michael@0:       if (!(value instanceof Array)) {
michael@0:         value = [value]
michael@0:       }
michael@0:       value = Array.prototype.concat.apply([], value.map(function(cookie) {
michael@0:         return String(cookie).split(';').map(trim)
michael@0:       }));
michael@0:     }
michael@0: 
michael@0:     // * To preserve the order of a comma-separated list, the ordered values for a single header
michael@0:     //   field name appearing in different header fields are concatenated into a single value.
michael@0:     //   A zero-valued octet (0x0) is used to delimit multiple values.
michael@0:     // * Header fields containing multiple values MUST be concatenated into a single value unless
michael@0:     //   the ordering of that header field is known to be not significant.
michael@0:     // * Currently, only the Cookie header is considered to be order-insensitive.
michael@0:     if ((value instanceof Array) && (name !== 'cookie')) {
michael@0:       value = value.join('\0');
michael@0:     }
michael@0: 
michael@0:     if (value instanceof Array) {
michael@0:       for (var i = 0; i < value.length; i++) {
michael@0:         compressor.write([name, String(value[i])]);
michael@0:       }
michael@0:     } else {
michael@0:       compressor.write([name, String(value)]);
michael@0:     }
michael@0:   }
michael@0:   compressor.end();
michael@0: 
michael@0:   var chunk, chunks = [];
michael@0:   while (chunk = compressor.read()) {
michael@0:     chunks.push(chunk);
michael@0:   }
michael@0:   return concat(chunks);
michael@0: };
michael@0: 
michael@0: // When a `frame` arrives
michael@0: Compressor.prototype._transform = function _transform(frame, encoding, done) {
michael@0:   // * and it is a HEADERS or PUSH_PROMISE frame
michael@0:   //   * it generates a header block using the compress method
michael@0:   //   * cuts the header block into `chunks` that are not larger than `MAX_HTTP_PAYLOAD_SIZE`
michael@0:   //   * for each chunk, it pushes out a chunk frame that is identical to the original, except
michael@0:   //     the `data` property which holds the given chunk, the type of the frame which is always
michael@0:   //     CONTINUATION except for the first frame, and the END_HEADERS/END_PUSH_STREAM flag that
michael@0:   //     marks the last frame and the END_STREAM flag which is always false before the end
michael@0:   if (frame.type === 'HEADERS' || frame.type === 'PUSH_PROMISE') {
michael@0:     var buffer = this.compress(frame.headers);
michael@0: 
michael@0:     var chunks = cut(buffer, MAX_HTTP_PAYLOAD_SIZE);
michael@0: 
michael@0:     for (var i = 0; i < chunks.length; i++) {
michael@0:       var chunkFrame;
michael@0:       var first = (i === 0);
michael@0:       var last = (i === chunks.length - 1);
michael@0: 
michael@0:       if (first) {
michael@0:         chunkFrame = util._extend({}, frame);
michael@0:         chunkFrame.flags = util._extend({}, frame.flags);
michael@0:         chunkFrame.flags['END_' + frame.type] = last;
michael@0:       } else {
michael@0:         chunkFrame = {
michael@0:           type: 'CONTINUATION',
michael@0:           flags: { END_HEADERS: last },
michael@0:           stream: frame.stream
michael@0:         };
michael@0:       }
michael@0:       chunkFrame.data = chunks[i];
michael@0: 
michael@0:       this.push(chunkFrame);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // * otherwise, the frame is forwarded without taking any action
michael@0:   else {
michael@0:     this.push(frame);
michael@0:   }
michael@0: 
michael@0:   done();
michael@0: };
michael@0: 
michael@0: // The Decompressor class
michael@0: // ----------------------
michael@0: 
michael@0: // The Decompressor is a stateful transform stream, since it has to collect multiple frames first,
michael@0: // and the decoding comes after unifying the payload of those frames.
michael@0: //
michael@0: // If there's a frame in progress, `this._inProgress` is `true`. The frames are collected in
michael@0: // `this._frames`, and the type of the frame and the stream identifier is stored in `this._type`
michael@0: // and `this._stream` respectively.
michael@0: util.inherits(Decompressor, TransformStream);
michael@0: function Decompressor(log, type) {
michael@0:   TransformStream.call(this, { objectMode: true });
michael@0: 
michael@0:   this._log = log.child({ component: 'compressor' });
michael@0: 
michael@0:   assert((type === 'REQUEST') || (type === 'RESPONSE'));
michael@0:   this._table = new HeaderTable(this._log);
michael@0: 
michael@0:   this._inProgress = false;
michael@0:   this._base = undefined;
michael@0: }
michael@0: 
michael@0: // Changing the header table size
michael@0: Decompressor.prototype.setTableSizeLimit = function setTableSizeLimit(size) {
michael@0:   this._table.setSizeLimit(size);
michael@0: };
michael@0: 
michael@0: // `decompress` takes a full header block, and decompresses it using a new `HeaderSetDecompressor`
michael@0: // stream instance. This means that from now on, the advantages of streaming header decoding are
michael@0: // lost, but the API becomes simpler.
michael@0: Decompressor.prototype.decompress = function decompress(block) {
michael@0:   var decompressor = new HeaderSetDecompressor(this._log, this._table);
michael@0:   decompressor.end(block);
michael@0: 
michael@0:   var headers = {};
michael@0:   var pair;
michael@0:   while (pair = decompressor.read()) {
michael@0:     var name = pair[0];
michael@0:     // * After decompression, header fields that have values containing zero octets (0x0) MUST be
michael@0:     //   split into multiple header fields before being processed.
michael@0:     var values = pair[1].split('\0');
michael@0:     for (var i = 0; i < values.length; i++) {
michael@0:       var value = values[i];
michael@0:       if (name in headers) {
michael@0:         if (headers[name] instanceof Array) {
michael@0:           headers[name].push(value);
michael@0:         } else {
michael@0:           headers[name] = [headers[name], value];
michael@0:         }
michael@0:       } else {
michael@0:         headers[name] = value;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // * If there are multiple Cookie header fields after decompression, these MUST be concatenated
michael@0:   //   into a single octet string using the two octet delimiter of 0x3B, 0x20 (the ASCII
michael@0:   //   string "; ").
michael@0:   if (('cookie' in headers) && (headers['cookie'] instanceof Array)) {
michael@0:     headers['cookie'] = headers['cookie'].join('; ')
michael@0:   }
michael@0: 
michael@0:   return headers;
michael@0: };
michael@0: 
michael@0: // When a `frame` arrives
michael@0: Decompressor.prototype._transform = function _transform(frame, encoding, done) {
michael@0:   // * and the collection process is already `_inProgress`, the frame is simply stored, except if
michael@0:   //   it's an illegal frame
michael@0:   if (this._inProgress) {
michael@0:     if ((frame.type !== 'CONTINUATION') || (frame.stream !== this._base.stream)) {
michael@0:       this._log.error('A series of HEADER frames were not continuous');
michael@0:       this.emit('error', 'PROTOCOL_ERROR');
michael@0:       return;
michael@0:     }
michael@0:     this._frames.push(frame);
michael@0:   }
michael@0: 
michael@0:   // * and the collection process is not `_inProgress`, but the new frame's type is HEADERS or
michael@0:   //   PUSH_PROMISE, a new collection process begins
michael@0:   else if ((frame.type === 'HEADERS') || (frame.type === 'PUSH_PROMISE')) {
michael@0:     this._inProgress = true;
michael@0:     this._base = util._extend({}, frame);
michael@0:     this._frames = [frame];
michael@0:   }
michael@0: 
michael@0:   // * otherwise, the frame is forwarded without taking any action
michael@0:   else {
michael@0:     this.push(frame);
michael@0:   }
michael@0: 
michael@0:   // * When the frame signals that it's the last in the series, the header block chunks are
michael@0:   //   concatenated, the headers are decompressed, and a new frame gets pushed out with the
michael@0:   //   decompressed headers.
michael@0:   if (this._inProgress && (frame.flags.END_HEADERS || frame.flags.END_PUSH_PROMISE)) {
michael@0:     var buffer = concat(this._frames.map(function(frame) {
michael@0:       return frame.data;
michael@0:     }));
michael@0:     try {
michael@0:       var headers = this.decompress(buffer);
michael@0:     } catch(error) {
michael@0:       this._log.error({ err: error }, 'Header decompression error');
michael@0:       this.emit('error', 'COMPRESSION_ERROR');
michael@0:       return;
michael@0:     }
michael@0:     this.push(util._extend(this._base, { headers: headers }));
michael@0:     this._inProgress = false;
michael@0:   }
michael@0: 
michael@0:   done();
michael@0: };
michael@0: 
michael@0: // Helper functions
michael@0: // ================
michael@0: 
michael@0: // Concatenate an array of buffers into a new buffer
michael@0: function concat(buffers) {
michael@0:   var size = 0;
michael@0:   for (var i = 0; i < buffers.length; i++) {
michael@0:     size += buffers[i].length;
michael@0:   }
michael@0: 
michael@0:   var concatenated = new Buffer(size);
michael@0:   for (var cursor = 0, j = 0; j < buffers.length; cursor += buffers[j].length, j++) {
michael@0:     buffers[j].copy(concatenated, cursor);
michael@0:   }
michael@0: 
michael@0:   return concatenated;
michael@0: }
michael@0: 
michael@0: // Cut `buffer` into chunks not larger than `size`
michael@0: function cut(buffer, size) {
michael@0:   var chunks = [];
michael@0:   var cursor = 0;
michael@0:   do {
michael@0:     var chunkSize = Math.min(size, buffer.length - cursor);
michael@0:     chunks.push(buffer.slice(cursor, cursor + chunkSize));
michael@0:     cursor += chunkSize;
michael@0:   } while(cursor < buffer.length);
michael@0:   return chunks;
michael@0: }
michael@0: 
michael@0: function trim(string) {
michael@0:   return string.trim()
michael@0: }