1557738 - [BinAST] Context Huffman tables lookup

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P1)

Description

[David Teller [:Yoric] - still alive but not very active]

Bug 1552435 puts content in Huffman tables, now we need to be able to look up data in them.

Comment 1

[David Teller [:Yoric] - still alive but not very active]

I think that I'm going to start with a linear lookup, which should already be pretty fast for small tables, then determine where to go from there.

Comment 2

[David Teller [:Yoric] - still alive but not very active]

Attachment: Bug 1557738 - Huffman table lookup;r?arai

This implements lookup in Huffman tables. We try to avoid pulling bits one at a time from the stream (because that's annoying and inefficient and requires abstractions that we don't really have), so we pull about 32 bits at a time and keep them in a bitbuffer. The Huffman table is in charge of looking at
~32 bits and keeping as many as it needs to produce a value.

For the moment, Huffman lookup is O(n), where n is the number of entries, which is very inefficient, but should be simple to test. In the future, we may wish to change representation of Huffman tables to something like
vector (indexed by a 32 bit key) -> vector (indexed by a 8 bit number of bits) -> *T
this would give us bounded time lookup, which should be better.

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/d028bd4f77db
Huffman table lookup;r=arai

Comment 4

[Razvan Maries]

https://hg.mozilla.org/mozilla-central/rev/d028bd4f77db