compressor.js

Jump To … +

compressor.js connection.js endpoint.js flow.js framer.js index.js stream.js

compressor.js
¶

The implementation of the HTTP/2 Header Compression spec is separated from the 'integration' part which handles HEADERS and PUSH_PROMISE frames. The compression itself is implemented in the first part of the file, and consists of three classes: HeaderTable, HeaderSetDecompressor and HeaderSetCompressor. The two latter classes are Transform Stream subclasses that operate in object mode. These transform chunks of binary data into [name, value] pairs and vice versa, and store their state in HeaderTable instances.

The 'integration' part is also implemented by two Transform Stream subclasses that operate in object mode: the Compressor and the Decompressor. These provide a layer between the framer and the connection handling component.
```
exports.HeaderTable = HeaderTable;
exports.HuffmanTable = HuffmanTable;
exports.HeaderSetCompressor = HeaderSetCompressor;
exports.HeaderSetDecompressor = HeaderSetDecompressor;
exports.Compressor = Compressor;
exports.Decompressor = Decompressor;

var TransformStream = require('stream').Transform;
var assert = require('assert');
var util = require('util');
```
¶

Header compression
¶

The HeaderTable class

The Header Table is a component used to associate headers to index values. It is basically an ordered list of [name, value] pairs, so it's implemented as a subclass of Array. In this implementation, the Header Table and the Static Table are handled as a single table.

function HeaderTable(log, limit) {
  var self = HeaderTable.staticTable.map(entryFromPair);
  self._log = log;
  self._limit = limit || DEFAULT_HEADER_TABLE_LIMIT;
  self._staticLength = self.length;
  self._size = 0;
  self._enforceLimit = HeaderTable.prototype._enforceLimit;
  self.add = HeaderTable.prototype.add;
  self.setSizeLimit = HeaderTable.prototype.setSizeLimit;
  return self;
}

There are few more sets that are needed for the compression/decompression process that are all subsets of the Header Table, and are implemented as flags on header table entries:

Reference Set: contains a group of headers used as a reference for the differential encoding of a new set of headers. (reference flag)
Emitted headers: the headers that are already emitted as part of the current decompression process (not part of the spec, emitted flag)
Headers to be kept: headers that should not be removed as the last step of the encoding process (not part of the spec, keep flag)

Relations of the sets:

,----------------------------------.
|           Header Table           |
|                                  |
|  ,----------------------------.  |
|  |        Reference Set       |  |
|  |                            |  |
|  |  ,---------.  ,---------.  |  |
|  |  |  Keep   |  | Emitted |  |  |
|  |  |         |  |         |  |  |
|  |  `---------'  `---------'  |  |
|  `----------------------------'  |
`----------------------------------'

function entryFromPair(pair) {
  var entry = pair.slice();
  entry.reference = false;
  entry.emitted = false;
  entry.keep = false;
  entry._size = size(entry);
  return entry;
}

¶

The encoder decides how to update the header table and as such can control how much memory is used by the header table. To limit the memory requirements on the decoder side, the header table size is bounded.
- The default header table size limit is 4096 bytes.
- The size of an entry is defined as follows: the size of an entry is the sum of its name's length in bytes, of its value's length in bytes and of 32 bytes.
- The size of a header table is the sum of the size of its entries.
```
var DEFAULT_HEADER_TABLE_LIMIT = 4096;

function size(entry) {
  return (new Buffer(entry[0] + entry[1], 'utf8')).length + 32;
}
```

The add(index, entry) can be used to manage the header table:

it pushes the new entry at the beggining of the table

before doing such a modification, it has to be ensured that the header table size will stay lower than or equal to the header table size limit. To achieve this, entries are evicted from the end of the header table until the size of the header table is less than or equal to (this._limit - entry.size), or until the table is empty.

       <----------  Index Address Space ---------->
       <-- Header  Table -->  <-- Static  Table -->
       +---+-----------+---+  +---+-----------+---+
       | 0 |    ...    | k |  |k+1|    ...    | n |
       +---+-----------+---+  +---+-----------+---+
       ^                   |
       |                   V
Insertion Point       Drop Point

HeaderTable.prototype._enforceLimit = function _enforceLimit(limit) {
  var droppedEntries = [];
  var dropPoint = this.length - this._staticLength;
  while ((this._size > limit) && (dropPoint > 0)) {
    dropPoint -= 1;
    var dropped = this.splice(dropPoint, 1)[0];
    this._size -= dropped._size;
    droppedEntries[dropPoint] = dropped;
  }
  return droppedEntries;
};

HeaderTable.prototype.add = function(entry) {
  var limit = this._limit - entry._size;
  var droppedEntries = this._enforceLimit(limit);

  if (this._size <= limit) {
    this.unshift(entry);
    this._size += entry._size;
  }

  return droppedEntries;
};

The table size limit can be changed externally. In this case, the same eviction algorithm is used

HeaderTable.prototype.setSizeLimit = function setSizeLimit(limit) {
  this._limit = limit;
  this._enforceLimit(this._limit);
};

¶

The Static Table

The table is generated with feeding the table from the spec to the following sed command:

sed -re "s/\s*\| [0-9]+\s*\| ([^ ]*)/  [ '\1'/g" -e "s/\|\s([^ ]*)/, '\1'/g" -e 's/ \|/],/g'

HeaderTable.staticTable  = [
  [ ':authority'                  , ''            ],
  [ ':method'                     , 'GET'         ],
  [ ':method'                     , 'POST'        ],
  [ ':path'                       , '/'           ],
  [ ':path'                       , '/index.html' ],
  [ ':scheme'                     , 'http'        ],
  [ ':scheme'                     , 'https'       ],
  [ ':status'                     , '200'         ],
  [ ':status'                     , '204'         ],
  [ ':status'                     , '206'         ],
  [ ':status'                     , '304'         ],
  [ ':status'                     , '400'         ],
  [ ':status'                     , '404'         ],
  [ ':status'                     , '500'         ],
  [ 'accept-charset'              , ''            ],
  [ 'accept-encoding'             , ''            ],
  [ 'accept-language'             , ''            ],
  [ 'accept-ranges'               , ''            ],
  [ 'accept'                      , ''            ],
  [ 'access-control-allow-origin' , ''            ],
  [ 'age'                         , ''            ],
  [ 'allow'                       , ''            ],
  [ 'authorization'               , ''            ],
  [ 'cache-control'               , ''            ],
  [ 'content-disposition'         , ''            ],
  [ 'content-encoding'            , ''            ],
  [ 'content-language'            , ''            ],
  [ 'content-length'              , ''            ],
  [ 'content-location'            , ''            ],
  [ 'content-range'               , ''            ],
  [ 'content-type'                , ''            ],
  [ 'cookie'                      , ''            ],
  [ 'date'                        , ''            ],
  [ 'etag'                        , ''            ],
  [ 'expect'                      , ''            ],
  [ 'expires'                     , ''            ],
  [ 'from'                        , ''            ],
  [ 'host'                        , ''            ],
  [ 'if-match'                    , ''            ],
  [ 'if-modified-since'           , ''            ],
  [ 'if-none-match'               , ''            ],
  [ 'if-range'                    , ''            ],
  [ 'if-unmodified-since'         , ''            ],
  [ 'last-modified'               , ''            ],
  [ 'link'                        , ''            ],
  [ 'location'                    , ''            ],
  [ 'max-forwards'                , ''            ],
  [ 'proxy-authenticate'          , ''            ],
  [ 'proxy-authorization'         , ''            ],
  [ 'range'                       , ''            ],
  [ 'referer'                     , ''            ],
  [ 'refresh'                     , ''            ],
  [ 'retry-after'                 , ''            ],
  [ 'server'                      , ''            ],
  [ 'set-cookie'                  , ''            ],
  [ 'strict-transport-security'   , ''            ],
  [ 'transfer-encoding'           , ''            ],
  [ 'user-agent'                  , ''            ],
  [ 'vary'                        , ''            ],
  [ 'via'                         , ''            ],
  [ 'www-authenticate'            , ''            ]
];

¶

The HeaderSetDecompressor class
¶

A HeaderSetDecompressor instance is a transform stream that can be used to decompress a single header set. Its input is a stream of binary data chunks and its output is a stream of [name, value] pairs.

Currently, it is not a proper streaming decompressor implementation, since it buffer its input until the end os the stream, and then processes the whole header block at once.
```
util.inherits(HeaderSetDecompressor, TransformStream);
function HeaderSetDecompressor(log, table) {
  TransformStream.call(this, { objectMode: true });

  this._log = log.child({ component: 'compressor' });
  this._table = table;
  this._chunks = [];
}
```
¶

_transform is the implementation of the corresponding virtual function of the TransformStream class. It collects the data chunks for later processing.
```
HeaderSetDecompressor.prototype._transform = function _transform(chunk, encoding, callback) {
  this._chunks.push(chunk);
  callback();
};
```

execute(rep) executes the given header representation.

The JavaScript object representation of a header representation:

{
  name: String || Integer,  // string literal or index
  value: String || Integer, // string literal or index
  index: Boolean            // with or without indexing
}

Important: to ease the indexing of the header table, indexes start at 0 instead of 1.

Examples:

Indexed:
{ name: 2  , value: 2  , index: false }
{ name: -1 , value: -1 , index: false } // reference set emptying
Literal:
{ name: 2  , value: 'X', index: false } // without indexing
{ name: 2  , value: 'Y', index: true  } // with indexing
{ name: 'A', value: 'Z', index: true  } // with indexing, literal name

HeaderSetDecompressor.prototype._execute = function _execute(rep) {
  this._log.trace({ key: rep.name, value: rep.value, index: rep.index },
                  'Executing header representation');

  var entry, pair;

  if (rep.contextUpdate) {
    if (rep.clearReferenceSet) {
      for (var i = 0; i < this._table.length; i++) {
        this._table[i].reference = false;
      }
    } else {
      this.setTableSizeLimit(rep.newMaxSize);
    }
  }

¶
- An indexed representation corresponding to an entry present in the reference set entails the following actions:
  - The entry is removed from the reference set.
- An indexed representation corresponding to an entry not present in the reference set entails the following actions:
  - If referencing an element of the static table:
    - The header field corresponding to the referenced entry is emitted
    - The referenced static entry is added to the header table
    - A reference to this new header table entry is added to the reference set (except if this new entry didn't fit in the header table)
  - If referencing an element of the header table:
    - The header field corresponding to the referenced entry is emitted
    - The referenced header table entry is added to the reference set
```
  else if (typeof rep.value === 'number') {
    var index = rep.value;
    entry = this._table[index];

    if (entry.reference) {
      entry.reference = false;
    }

    else {
      pair = entry.slice();
      this.push(pair);

      if (index >= this._table.length - this._table._staticLength) {
        entry = entryFromPair(pair);
        this._table.add(entry);
      }

      entry.reference = true;
      entry.emitted = true;
    }
  }
```

A literal representation that is not added to the header table entails the following action:
- The header is emitted.
A literal representation that is added to the header table entails the following further actions:
- The header is added to the header table.
- The new entry is added to the reference set.

  else {
    if (typeof rep.name === 'number') {
      pair = [this._table[rep.name][0], rep.value];
    } else {
      pair = [rep.name, rep.value];
    }

    if (rep.index) {
      entry = entryFromPair(pair);
      entry.reference = true;
      entry.emitted = true;
      this._table.add(entry);
    }

    this.push(pair);
  }
};

¶

_flush is the implementation of the corresponding virtual function of the TransformStream class. The whole decompressing process is done in _flush. It gets called when the input stream is over.
```
HeaderSetDecompressor.prototype._flush = function _flush(callback) {
  var buffer = concat(this._chunks);
```

processes the header representations

  buffer.cursor = 0;
  while (buffer.cursor < buffer.length) {
    this._execute(HeaderSetDecompressor.header(buffer));
  }

emits the reference set

  for (var index = 0; index < this._table.length; index++) {
    var entry = this._table[index];
    if (entry.reference && !entry.emitted) {
      this.push(entry.slice());
    }
    entry.emitted = false;
  }

  callback();
};

¶

The HeaderSetCompressor class

A HeaderSetCompressor instance is a transform stream that can be used to compress a single header set. Its input is a stream of [name, value] pairs and its output is a stream of binary data chunks.

It is a real streaming compressor, since it does not wait until the header set is complete.

The compression algorithm is (intentionally) not specified by the spec. Therefore, the current compression algorithm can probably be improved in the future.

util.inherits(HeaderSetCompressor, TransformStream);
function HeaderSetCompressor(log, table) {
  TransformStream.call(this, { objectMode: true });

  this._log = log.child({ component: 'compressor' });
  this._table = table;
  this.push = TransformStream.prototype.push.bind(this);
}

HeaderSetCompressor.prototype.send = function send(rep) {
  this._log.trace({ key: rep.name, value: rep.value, index: rep.index },
                  'Emitting header representation');

  if (!rep.chunks) {
    rep.chunks = HeaderSetCompressor.header(rep);
  }
  rep.chunks.forEach(this.push);
};

_transform is the implementation of the corresponding virtual function of the TransformStream class. It processes the input headers one by one:

HeaderSetCompressor.prototype._transform = function _transform(pair, encoding, callback) {
  var name = pair[0].toLowerCase();
  var value = pair[1];
  var entry, rep;

tries to find full (name, value) or name match in the header table

  var nameMatch = -1, fullMatch = -1;
  for (var droppedIndex = 0; droppedIndex < this._table.length; droppedIndex++) {
    entry = this._table[droppedIndex];
    if (entry[0] === name) {
      if (entry[1] === value) {
        fullMatch = droppedIndex;
        break;
      } else if (nameMatch === -1) {
        nameMatch = droppedIndex;
      }
    }
  }

  var mustNeverIndex = (name === 'cookie' || name === 'set-cookie' || name === 'authorization');

¶
- if there's full match, it will be an indexed representation (or more than one) depending on its presence in the reference, the emitted and the keep set:
  - If the entry is outside the reference set, then a single indexed representation puts the entry into it and emits the header. Note that if the matched entry is in the static table, then it has to be added to the header table.
  - If it's already in the keep set, then 4 indexed representations are needed:
    1. removes it from the reference set
    2. puts it back in the reference set and emits the header once
    3. removes it again
    4. puts it back and emits it again for the second time
    It won't be emitted at the end of the decoding process since it's now in the emitted set.
  - If it's in the emitted set, then 2 indexed representations are needed:
    1. removes it from the reference set
    2. puts it back in the reference set and emits the header once
  - If it's in the reference set, but outside the keep set and the emitted set, then this header is common with the previous header set, and is still untouched. We mark it to keep in the reference set (that means don't remove at the end of the encoding process).
```
  if (fullMatch !== -1 && !mustNeverIndex) {
    rep = { name: fullMatch, value: fullMatch, index: false };

    if (!entry.reference) {
      if (fullMatch >= this._table.length - this._table._staticLength) {
        entry = entryFromPair(pair);
        this._table.add(entry);
      }
      this.send(rep);
      entry.reference = true;
      entry.emitted = true;
    }

    else if (entry.keep) {
      this.send(rep);
      this.send(rep);
      this.send(rep);
      this.send(rep);
      entry.keep = false;
      entry.emitted = true;
    }

    else if (entry.emitted) {
      this.send(rep);
      this.send(rep);
    }

    else {
      entry.keep = true;
    }
  }
```

otherwise, it will be a literal representation (with a name index if there's a name match)

  else {
    entry = entryFromPair(pair);
    entry.emitted = true;

    var indexing = (entry._size < this._table._limit / 2) && !mustNeverIndex;

    if (indexing) {
      entry.reference = true;
      var droppedEntries = this._table.add(entry);
      for (droppedIndex in droppedEntries) {
        droppedIndex = Number(droppedIndex)
        var dropped = droppedEntries[droppedIndex];
        if (dropped.keep) {
          rep = { name: droppedIndex, value: droppedIndex, index: false };
          this.send(rep);
          this.send(rep);
        }
      }
    }

    this.send({ name: (nameMatch !== -1) ? nameMatch : name, value: value, index: indexing, mustNeverIndex: mustNeverIndex, contextUpdate: false });
  }

  callback();
};

¶

_flush is the implementation of the corresponding virtual function of the TransformStream class. It gets called when there's no more header to compress. The final step:
```
HeaderSetCompressor.prototype._flush = function _flush(callback) {
```

removing entries from the header set that are not marked to be kept or emitted

  for (var index = 0; index < this._table.length; index++) {
    var entry = this._table[index];
    if (entry.reference && !entry.keep && !entry.emitted) {
      this.send({ name: index, value: index, index: false });
      entry.reference = false;
    }
    entry.keep = false;
    entry.emitted = false;
  }

  callback();
};

¶

Detailed Format

Integer representation

The algorithm to represent an integer I is as follows:

If I < 2^N - 1, encode I on N bits
Else, encode 2^N - 1 on N bits and do the following steps:
1. Set I to (I - (2^N - 1)) and Q to 1
2. While Q > 0
  1. Compute Q and R, quotient and remainder of I divided by 2^7
  2. If Q is strictly greater than 0, write one 1 bit; otherwise, write one 0 bit
  3. Encode R on the next 7 bits
  4. I = Q

HeaderSetCompressor.integer = function writeInteger(I, N) {
  var limit = Math.pow(2,N) - 1;
  if (I < limit) {
    return [new Buffer([I])];
  }

  var bytes = [];
  if (N !== 0) {
    bytes.push(limit);
  }
  I -= limit;

  var Q = 1, R;
  while (Q > 0) {
    Q = Math.floor(I / 128);
    R = I % 128;

    if (Q > 0) {
      R += 128;
    }
    bytes.push(R);

    I = Q;
  }

  return [new Buffer(bytes)];
};

The inverse algorithm:

Set I to the number coded on the lower N bits of the first byte
If I is smaller than 2^N - 1 then return I
Else the number is encoded on more than one byte, so do the following steps:
1. Set M to 0
2. While returning with I
  1. Let B be the next byte (the first byte if N is 0)
  2. Read out the lower 7 bits of B and multiply it with 2^M
  3. Increase I with this number
  4. Increase M by 7
  5. Return I if the most significant bit of B is 0

HeaderSetDecompressor.integer = function readInteger(buffer, N) {
  var limit = Math.pow(2,N) - 1;

  var I = buffer[buffer.cursor] & limit;
  if (N !== 0) {
    buffer.cursor += 1;
  }

  if (I === limit) {
    var M = 0;
    do {
      I += (buffer[buffer.cursor] & 127) << M;
      M += 7;
      buffer.cursor += 1;
    } while (buffer[buffer.cursor - 1] & 128);
  }

  return I;
};

Huffman Encoding

function HuffmanTable(table) {
  function createTree(codes, position) {
    if (codes.length === 1) {
      return [table.indexOf(codes[0])];
    }

    else {
      position = position || 0;
      var zero = [];
      var one = [];
      for (var i = 0; i < codes.length; i++) {
        var string = codes[i];
        if (string[position] === '0') {
          zero.push(string);
        } else {
          one.push(string);
        }
      }
      return [createTree(zero, position + 1), createTree(one, position + 1)];
    }
  }

  this.tree = createTree(table);

  this.codes = table.map(function(bits) {
    return parseInt(bits, 2);
  });
  this.lengths = table.map(function(bits) {
    return bits.length;
  });
}

HuffmanTable.prototype.encode = function encode(buffer) {
  var result = [];
  var space = 8;

  function add(data) {
    if (space === 8) {
      result.push(data);
    } else {
      result[result.length - 1] |= data;
    }
  }

  for (var i = 0; i < buffer.length; i++) {
    var byte = buffer[i];
    var code = this.codes[byte];
    var length = this.lengths[byte];

    while (length !== 0) {
      if (space >= length) {
        add(code << (space - length));
        code = 0;
        space -= length;
        length = 0;
      } else {
        var shift = length - space;
        var msb = code >> shift;
        add(msb);
        code -= msb << shift;
        length -= space;
        space = 0;
      }

      if (space === 0) {
        space = 8;
      }
    }
  }

  if (space !== 8) {
    add(this.codes[256] >> (this.lengths[256] - space));
  }

  return new Buffer(result);
}

HuffmanTable.prototype.decode = function decode(buffer) {
  var result = [];
  var subtree = this.tree;

  for (var i = 0; i < buffer.length; i++) {
    var byte = buffer[i];

    for (var j = 0; j < 8; j++) {
      var bit = (byte & 128) ? 1 : 0;
      byte = byte << 1;

      subtree = subtree[bit];
      if (subtree.length === 1) {
        result.push(subtree[0]);
        subtree = this.tree;
      }
    }
  }

  return new Buffer(result);
}

The initializer arrays for the Huffman tables are generated with feeding the tables from the spec to this sed command:

sed -e "s/^.* [|]//g" -e "s/|//g" -e "s/ .*//g" -e "s/^/  '/g" -e "s/$/',/g"

HuffmanTable.huffmanTable = new HuffmanTable([
  '11111111111111111110111010',
  '11111111111111111110111011',
  '11111111111111111110111100',
  '11111111111111111110111101',
  '11111111111111111110111110',
  '11111111111111111110111111',
  '11111111111111111111000000',
  '11111111111111111111000001',
  '11111111111111111111000010',
  '11111111111111111111000011',
  '11111111111111111111000100',
  '11111111111111111111000101',
  '11111111111111111111000110',
  '11111111111111111111000111',
  '11111111111111111111001000',
  '11111111111111111111001001',
  '11111111111111111111001010',
  '11111111111111111111001011',
  '11111111111111111111001100',
  '11111111111111111111001101',
  '11111111111111111111001110',
  '11111111111111111111001111',
  '11111111111111111111010000',
  '11111111111111111111010001',
  '11111111111111111111010010',
  '11111111111111111111010011',
  '11111111111111111111010100',
  '11111111111111111111010101',
  '11111111111111111111010110',
  '11111111111111111111010111',
  '11111111111111111111011000',
  '11111111111111111111011001',
  '00110',
  '1111111111100',
  '111110000',
  '11111111111100',
  '111111111111100',
  '011110',
  '1100100',
  '1111111111101',
  '1111111010',
  '111110001',
  '1111111011',
  '1111111100',
  '1100101',
  '1100110',
  '011111',
  '00111',
  '0000',
  '0001',
  '0010',
  '01000',
  '100000',
  '100001',
  '100010',
  '100011',
  '100100',
  '100101',
  '100110',
  '11101100',
  '11111111111111100',
  '100111',
  '111111111111101',
  '1111111101',
  '111111111111110',
  '1100111',
  '11101101',
  '11101110',
  '1101000',
  '11101111',
  '1101001',
  '1101010',
  '111110010',
  '11110000',
  '111110011',
  '111110100',
  '111110101',
  '1101011',
  '1101100',
  '11110001',
  '11110010',
  '111110110',
  '111110111',
  '1101101',
  '101000',
  '11110011',
  '111111000',
  '111111001',
  '11110100',
  '111111010',
  '111111011',
  '11111111100',
  '11111111111111111111011010',
  '11111111101',
  '11111111111101',
  '1101110',
  '111111111111111110',
  '01001',
  '1101111',
  '01010',
  '101001',
  '01011',
  '1110000',
  '101010',
  '101011',
  '01100',
  '11110101',
  '11110110',
  '101100',
  '101101',
  '101110',
  '01101',
  '101111',
  '111111100',
  '110000',
  '110001',
  '01110',
  '1110001',
  '1110010',
  '1110011',
  '1110100',
  '1110101',
  '11110111',
  '11111111111111101',
  '111111111100',
  '11111111111111110',
  '111111111101',
  '11111111111111111111011011',
  '11111111111111111111011100',
  '11111111111111111111011101',
  '11111111111111111111011110',
  '11111111111111111111011111',
  '11111111111111111111100000',
  '11111111111111111111100001',
  '11111111111111111111100010',
  '11111111111111111111100011',
  '11111111111111111111100100',
  '11111111111111111111100101',
  '11111111111111111111100110',
  '11111111111111111111100111',
  '11111111111111111111101000',
  '11111111111111111111101001',
  '11111111111111111111101010',
  '11111111111111111111101011',
  '11111111111111111111101100',
  '11111111111111111111101101',
  '11111111111111111111101110',
  '11111111111111111111101111',
  '11111111111111111111110000',
  '11111111111111111111110001',
  '11111111111111111111110010',
  '11111111111111111111110011',
  '11111111111111111111110100',
  '11111111111111111111110101',
  '11111111111111111111110110',
  '11111111111111111111110111',
  '11111111111111111111111000',
  '11111111111111111111111001',
  '11111111111111111111111010',
  '11111111111111111111111011',
  '11111111111111111111111100',
  '11111111111111111111111101',
  '11111111111111111111111110',
  '11111111111111111111111111',
  '1111111111111111110000000',
  '1111111111111111110000001',
  '1111111111111111110000010',
  '1111111111111111110000011',
  '1111111111111111110000100',
  '1111111111111111110000101',
  '1111111111111111110000110',
  '1111111111111111110000111',
  '1111111111111111110001000',
  '1111111111111111110001001',
  '1111111111111111110001010',
  '1111111111111111110001011',
  '1111111111111111110001100',
  '1111111111111111110001101',
  '1111111111111111110001110',
  '1111111111111111110001111',
  '1111111111111111110010000',
  '1111111111111111110010001',
  '1111111111111111110010010',
  '1111111111111111110010011',
  '1111111111111111110010100',
  '1111111111111111110010101',
  '1111111111111111110010110',
  '1111111111111111110010111',
  '1111111111111111110011000',
  '1111111111111111110011001',
  '1111111111111111110011010',
  '1111111111111111110011011',
  '1111111111111111110011100',
  '1111111111111111110011101',
  '1111111111111111110011110',
  '1111111111111111110011111',
  '1111111111111111110100000',
  '1111111111111111110100001',
  '1111111111111111110100010',
  '1111111111111111110100011',
  '1111111111111111110100100',
  '1111111111111111110100101',
  '1111111111111111110100110',
  '1111111111111111110100111',
  '1111111111111111110101000',
  '1111111111111111110101001',
  '1111111111111111110101010',
  '1111111111111111110101011',
  '1111111111111111110101100',
  '1111111111111111110101101',
  '1111111111111111110101110',
  '1111111111111111110101111',
  '1111111111111111110110000',
  '1111111111111111110110001',
  '1111111111111111110110010',
  '1111111111111111110110011',
  '1111111111111111110110100',
  '1111111111111111110110101',
  '1111111111111111110110110',
  '1111111111111111110110111',
  '1111111111111111110111000',
  '1111111111111111110111001',
  '1111111111111111110111010',
  '1111111111111111110111011',
  '1111111111111111110111100',
  '1111111111111111110111101',
  '1111111111111111110111110',
  '1111111111111111110111111',
  '1111111111111111111000000',
  '1111111111111111111000001',
  '1111111111111111111000010',
  '1111111111111111111000011',
  '1111111111111111111000100',
  '1111111111111111111000101',
  '1111111111111111111000110',
  '1111111111111111111000111',
  '1111111111111111111001000',
  '1111111111111111111001001',
  '1111111111111111111001010',
  '1111111111111111111001011',
  '1111111111111111111001100',
  '1111111111111111111001101',
  '1111111111111111111001110',
  '1111111111111111111001111',
  '1111111111111111111010000',
  '1111111111111111111010001',
  '1111111111111111111010010',
  '1111111111111111111010011',
  '1111111111111111111010100',
  '1111111111111111111010101',
  '1111111111111111111010110',
  '1111111111111111111010111',
  '1111111111111111111011000',
  '1111111111111111111011001',
  '1111111111111111111011010',
  '1111111111111111111011011',
  '1111111111111111111011100'
]);

String literal representation

Literal strings can represent header names or header values. There's two variant of the string encoding:

String literal with Huffman encoding:

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |  Value Length Prefix (7)  |
+---+---+---+---+---+---+---+---+
|   Value Length (0-N bytes)    |
+---+---+---+---+---+---+---+---+
...
+---+---+---+---+---+---+---+---+
| Huffman Encoded Data  |Padding|
+---+---+---+---+---+---+---+---+

String literal without Huffman encoding:

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 |  Value Length Prefix (7)  |
+---+---+---+---+---+---+---+---+
|   Value Length (0-N bytes)    |
+---+---+---+---+---+---+---+---+
...
+---+---+---+---+---+---+---+---+
|  Field Bytes Without Encoding |
+---+---+---+---+---+---+---+---+

HeaderSetCompressor.string = function writeString(str) {
  str = new Buffer(str, 'utf8');

  var huffman = HuffmanTable.huffmanTable.encode(str);
  if (huffman.length < str.length) {
    var length = HeaderSetCompressor.integer(huffman.length, 7)
    length[0][0] |= 128;
    return length.concat(huffman);
  }

  else {
    length = HeaderSetCompressor.integer(str.length, 7)
    return length.concat(str);
  }
};

HeaderSetDecompressor.string = function readString(buffer) {
  var huffman = buffer[buffer.cursor] & 128;
  var length = HeaderSetDecompressor.integer(buffer, 7);
  var encoded = buffer.slice(buffer.cursor, buffer.cursor + length);
  buffer.cursor += length;
  return (huffman ? HuffmanTable.huffmanTable.decode(encoded) : encoded).toString('utf8');
};

Header represenations

The JavaScript object representation is described near the HeaderSetDecompressor.prototype._execute() method definition.

All binary header representations start with a prefix signaling the representation type and an index represented using prefix coded integers:

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |        Index (7+)         |  Indexed Representation
+---+---------------------------+

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |      Index (6+)       |
+---+---+---+-------------------+  Literal w/ Indexing
|       Value Length (8+)       |
+-------------------------------+  w/ Indexed Name
| Value String (Length octets)  |
+-------------------------------+

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |           0           |
+---+---+---+-------------------+
|       Name Length (8+)        |
+-------------------------------+  Literal w/ Indexing
|  Name String (Length octets)  |
+-------------------------------+  w/ New Name
|       Value Length (8+)       |
+-------------------------------+
| Value String (Length octets)  |
+-------------------------------+

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |  Index (4+)   |
+---+---+---+-------------------+  Literal w/o Incremental Indexing
|       Value Length (8+)       |
+-------------------------------+  w/ Indexed Name
| Value String (Length octets)  |
+-------------------------------+

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |       0       |
+---+---+---+-------------------+
|       Name Length (8+)        |
+-------------------------------+  Literal w/o Incremental Indexing
|  Name String (Length octets)  |
+-------------------------------+  w/ New Name
|       Value Length (8+)       |
+-------------------------------+
| Value String (Length octets)  |
+-------------------------------+

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 |  Index (4+)   |
+---+---+---+-------------------+  Literal never indexed
|       Value Length (8+)       |
+-------------------------------+  w/ Indexed Name
| Value String (Length octets)  |
+-------------------------------+

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 |       0       |
+---+---+---+-------------------+
|       Name Length (8+)        |
+-------------------------------+  Literal never indexed
|  Name String (Length octets)  |
+-------------------------------+  w/ New Name
|       Value Length (8+)       |
+-------------------------------+
| Value String (Length octets)  |
+-------------------------------+

The Indexed Representation consists of the 1-bit prefix and the Index that is represented as a 7-bit prefix coded integer and nothing else.

After the first bits, all literal representations specify the header name, either as a pointer to the Header Table (Index) or a string literal. When the string literal representation is used, the Index is set to 0 and the string literal starts at the second byte.

For all literal representations, the specification of the header value comes next. It is always represented as a string.

var representations = {
  indexed             : { prefix: 7, pattern: 0x80 },
  literalIncremental  : { prefix: 6, pattern: 0x40 },
  contextUpdate       : { prefix: 0, pattern: 0x20 },
  literalNeverIndexed : { prefix: 4, pattern: 0x10 },
  literal             : { prefix: 4, pattern: 0x00 }
};

HeaderSetCompressor.header = function writeHeader(header) {
  var representation, buffers = [];

  if (header.contextUpdate) {
    representation = representations.contextUpdate;
  } else if (typeof header.value === 'number') {
    representation = representations.indexed;
  } else if (header.index) {
    representation = representations.literalIncremental;
  } else if (header.mustNeverIndex) {
    representation = representations.literalNeverIndexed;
  } else {
    representation = representations.literal;
  }

  if (representation === representations.contextUpdate) {
    if (header.clearReferenceSet) {
      var buffer = new Buffer('10', 'hex');
      buffers.push([buffer]);
    } else {
      buffers.push(HeaderSetCompressor.integer(header.newMaxSize, 4));
    }
  }

  else if (representation === representations.indexed) {
    buffers.push(HeaderSetCompressor.integer(header.value + 1, representation.prefix));
  }

  else {
    if (typeof header.name === 'number') {
      buffers.push(HeaderSetCompressor.integer(header.name + 1, representation.prefix));
    } else {
      buffers.push(HeaderSetCompressor.integer(0, representation.prefix));
      buffers.push(HeaderSetCompressor.string(header.name));
    }
    buffers.push(HeaderSetCompressor.string(header.value));
  }

  buffers[0][0][0] |= representation.pattern;

  return Array.prototype.concat.apply([], buffers); // array of arrays of buffers -> array of buffers
};

HeaderSetDecompressor.header = function readHeader(buffer) {
  var representation, header = {};

  var firstByte = buffer[buffer.cursor];
  if (firstByte & 0x80) {
    representation = representations.indexed;
  } else if (firstByte & 0x40) {
    representation = representations.literalIncremental;
  } else if (firstByte & 0x20) {
    representation = representations.contextUpdate;
  } else if (firstByte & 0x10) {
    representation = representations.literalNeverIndexed;
  } else {
    representation = representations.literal;
  }

  header.value = header.name = -1;
  header.index = false;
  header.contextUpdate = false;
  header.clearReferenceSet = false;
  header.newMaxSize = 0;
  header.mustNeverIndex = false;

  if (representation === representations.contextUpdate) {
    header.contextUpdate = true;
    if (firstByte & 0x10) {
      header.clearReferenceSet = true;
      buffer.cursor += 1;
    } else {
      header.newMaxSize = HeaderSetDecompressor.integer(buffer, 4);
    }
  }

  else if (representation === representations.indexed) {
    header.value = header.name = HeaderSetDecompressor.integer(buffer, representation.prefix) - 1;
  }

  else {
    header.name = HeaderSetDecompressor.integer(buffer, representation.prefix) - 1;
    if (header.name === -1) {
      header.name = HeaderSetDecompressor.string(buffer);
    }
    header.value = HeaderSetDecompressor.string(buffer);
    header.index = (representation === representations.literalIncremental);
    header.mustNeverIndex = (representation === representations.literalNeverIndexed);
  }

  return header;
};

¶

Integration with HTTP/2
¶

This section describes the interaction between the compressor/decompressor and the rest of the HTTP/2 implementation. The Compressor and the Decompressor makes up a layer between the framer and the connection handling component. They let most frames pass through, except HEADERS and PUSH_PROMISE frames. They convert the frames between these two representations:
```
{                                   {
 type: 'HEADERS',                    type: 'HEADERS',
 flags: {},                          flags: {},
 stream: 1,               <===>      stream: 1,
 headers: {                          data: Buffer
  N1: 'V1',                         }
  N2: ['V1', 'V2', ...],
  // ...
 }
}
```
There are possibly several binary frame that belong to a single non-binary frame.
```
var MAX_HTTP_PAYLOAD_SIZE = 16383;
```
¶

The Compressor class

The Compressor transform stream is basically stateless.

util.inherits(Compressor, TransformStream);
function Compressor(log, type) {
  TransformStream.call(this, { objectMode: true });

  this._log = log.child({ component: 'compressor' });

  assert((type === 'REQUEST') || (type === 'RESPONSE'));
  this._table = new HeaderTable(this._log);
}

Changing the header table size

Compressor.prototype.setTableSizeLimit = function setTableSizeLimit(size) {
  this._table.setSizeLimit(size);
};

compress takes a header set, and compresses it using a new HeaderSetCompressor stream instance. This means that from now on, the advantages of streaming header encoding are lost, but the API becomes simpler.

Compressor.prototype.compress = function compress(headers) {
  var compressor = new HeaderSetCompressor(this._log, this._table);
  for (var name in headers) {
    var value = headers[name];
    name = String(name).toLowerCase();

To allow for better compression efficiency, the Cookie header field MAY be split into separate header fields, each with one or more cookie-pairs.

    if (name == 'cookie') {
      if (!(value instanceof Array)) {
        value = [value]
      }
      value = Array.prototype.concat.apply([], value.map(function(cookie) {
        return String(cookie).split(';').map(trim)
      }));
    }

To preserve the order of a comma-separated list, the ordered values for a single header field name appearing in different header fields are concatenated into a single value. A zero-valued octet (0x0) is used to delimit multiple values.
Header fields containing multiple values MUST be concatenated into a single value unless the ordering of that header field is known to be not significant.
Currently, only the Cookie header is considered to be order-insensitive.

    if ((value instanceof Array) && (name !== 'cookie')) {
      value = value.join('\0');
    }

    if (value instanceof Array) {
      for (var i = 0; i < value.length; i++) {
        compressor.write([name, String(value[i])]);
      }
    } else {
      compressor.write([name, String(value)]);
    }
  }
  compressor.end();

  var chunk, chunks = [];
  while (chunk = compressor.read()) {
    chunks.push(chunk);
  }
  return concat(chunks);
};

When a frame arrives

Compressor.prototype._transform = function _transform(frame, encoding, done) {

and it is a HEADERS or PUSH_PROMISE frame
- it generates a header block using the compress method
- cuts the header block into chunks that are not larger than MAX_HTTP_PAYLOAD_SIZE
- for each chunk, it pushes out a chunk frame that is identical to the original, except the data property which holds the given chunk, the type of the frame which is always CONTINUATION except for the first frame, and the END_HEADERS/END_PUSH_STREAM flag that marks the last frame and the END_STREAM flag which is always false before the end

  if (frame.type === 'HEADERS' || frame.type === 'PUSH_PROMISE') {
    var buffer = this.compress(frame.headers);

    var chunks = cut(buffer, MAX_HTTP_PAYLOAD_SIZE);

    for (var i = 0; i < chunks.length; i++) {
      var chunkFrame;
      var first = (i === 0);
      var last = (i === chunks.length - 1);

      if (first) {
        chunkFrame = util._extend({}, frame);
        chunkFrame.flags = util._extend({}, frame.flags);
        chunkFrame.flags['END_' + frame.type] = last;
      } else {
        chunkFrame = {
          type: 'CONTINUATION',
          flags: { END_HEADERS: last },
          stream: frame.stream
        };
      }
      chunkFrame.data = chunks[i];

      this.push(chunkFrame);
    }
  }

¶
- otherwise, the frame is forwarded without taking any action
```
  else {
    this.push(frame);
  }

  done();
};
```
¶

The Decompressor class

The Decompressor is a stateful transform stream, since it has to collect multiple frames first, and the decoding comes after unifying the payload of those frames.

If there's a frame in progress, this._inProgress is true. The frames are collected in this._frames, and the type of the frame and the stream identifier is stored in this._type and this._stream respectively.

util.inherits(Decompressor, TransformStream);
function Decompressor(log, type) {
  TransformStream.call(this, { objectMode: true });

  this._log = log.child({ component: 'compressor' });

  assert((type === 'REQUEST') || (type === 'RESPONSE'));
  this._table = new HeaderTable(this._log);

  this._inProgress = false;
  this._base = undefined;
}

Changing the header table size

Decompressor.prototype.setTableSizeLimit = function setTableSizeLimit(size) {
  this._table.setSizeLimit(size);
};

decompress takes a full header block, and decompresses it using a new HeaderSetDecompressor stream instance. This means that from now on, the advantages of streaming header decoding are lost, but the API becomes simpler.

Decompressor.prototype.decompress = function decompress(block) {
  var decompressor = new HeaderSetDecompressor(this._log, this._table);
  decompressor.end(block);

  var headers = {};
  var pair;
  while (pair = decompressor.read()) {
    var name = pair[0];

After decompression, header fields that have values containing zero octets (0x0) MUST be split into multiple header fields before being processed.

    var values = pair[1].split('\0');
    for (var i = 0; i < values.length; i++) {
      var value = values[i];
      if (name in headers) {
        if (headers[name] instanceof Array) {
          headers[name].push(value);
        } else {
          headers[name] = [headers[name], value];
        }
      } else {
        headers[name] = value;
      }
    }
  }

¶
- If there are multiple Cookie header fields after decompression, these MUST be concatenated into a single octet string using the two octet delimiter of 0x3B, 0x20 (the ASCII string "; ").
```
  if (('cookie' in headers) && (headers['cookie'] instanceof Array)) {
    headers['cookie'] = headers['cookie'].join('; ')
  }

  return headers;
};
```

When a frame arrives

Decompressor.prototype._transform = function _transform(frame, encoding, done) {

and the collection process is already _inProgress, the frame is simply stored, except if it's an illegal frame

  if (this._inProgress) {
    if ((frame.type !== 'CONTINUATION') || (frame.stream !== this._base.stream)) {
      this._log.error('A series of HEADER frames were not continuous');
      this.emit('error', 'PROTOCOL_ERROR');
      return;
    }
    this._frames.push(frame);
  }

and the collection process is not _inProgress, but the new frame's type is HEADERS or PUSH_PROMISE, a new collection process begins

  else if ((frame.type === 'HEADERS') || (frame.type === 'PUSH_PROMISE')) {
    this._inProgress = true;
    this._base = util._extend({}, frame);
    this._frames = [frame];
  }

¶
- otherwise, the frame is forwarded without taking any action
```
  else {
    this.push(frame);
  }
```

When the frame signals that it's the last in the series, the header block chunks are concatenated, the headers are decompressed, and a new frame gets pushed out with the decompressed headers.

  if (this._inProgress && (frame.flags.END_HEADERS || frame.flags.END_PUSH_PROMISE)) {
    var buffer = concat(this._frames.map(function(frame) {
      return frame.data;
    }));
    try {
      var headers = this.decompress(buffer);
    } catch(error) {
      this._log.error({ err: error }, 'Header decompression error');
      this.emit('error', 'COMPRESSION_ERROR');
      return;
    }
    this.push(util._extend(this._base, { headers: headers }));
    this._inProgress = false;
  }

  done();
};

¶

Helper functions

Concatenate an array of buffers into a new buffer

function concat(buffers) {
  var size = 0;
  for (var i = 0; i < buffers.length; i++) {
    size += buffers[i].length;
  }

  var concatenated = new Buffer(size);
  for (var cursor = 0, j = 0; j < buffers.length; cursor += buffers[j].length, j++) {
    buffers[j].copy(concatenated, cursor);
  }

  return concatenated;
}

Cut buffer into chunks not larger than size

function cut(buffer, size) {
  var chunks = [];
  var cursor = 0;
  do {
    var chunkSize = Math.min(size, buffer.length - cursor);
    chunks.push(buffer.slice(cursor, cursor + chunkSize));
    cursor += chunkSize;
  } while(cursor < buffer.length);
  return chunks;
}

function trim(string) {
  return string.trim()
}

compressor.js

Header compression

The HeaderTable class

The Static Table

The HeaderSetDecompressor class

The HeaderSetCompressor class

Detailed Format

Integer representation

Huffman Encoding

String literal representation

Header represenations

Integration with HTTP/2

The Compressor class

The Decompressor class

Helper functions