From fd96151b2a04667dac73242b72bc62e007b2b543 Mon Sep 17 00:00:00 2001
From: Eugene Kliuchnikov <eustas@google.com>
Date: Tue, 20 Dec 2016 18:00:51 +0100
Subject: Move brotlidump.py to research/ (#487)

---
 research/brotlidump.py | 2361 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 2361 insertions(+)
 create mode 100644 research/brotlidump.py

(limited to 'research')

diff --git a/research/brotlidump.py b/research/brotlidump.py
new file mode 100644
index 0000000..a625368
--- /dev/null
+++ b/research/brotlidump.py
@@ -0,0 +1,2361 @@
+#!python3
+"""Program to dump contents of Brotli compressed files showing the compression format.
+Jurjen N.E. Bos, 2016.
+I found the following issues with the Brotli format:
+- The distance alphabet has size 16+(48<<POSTFIX),
+  but the last symbols are useless.
+  It could be lowered to 16+(44-POSTFIX<<POSTFIX), and this could matter.
+- The block type code is useless if NBLTYPES==2, you would only need 1 symbol
+  anyway, so why don't you just switch to "the other" type?
+"""
+import struct
+from operator import itemgetter, methodcaller
+from itertools import accumulate, repeat
+from collections import defaultdict, deque
+from functools import partial
+
+class InvalidStream(Exception): pass
+#lookup table
+L, I, D = "literal", "insert&copy", "distance"
+pL, pI, pD = 'P'+L, 'P'+I, 'P'+D
+
+def outputCharFormatter(c):
+    """Show character in readable format
+    """
+    #TODO 2: allow hex only output
+    if 32<c<127: return chr(c)
+    elif c==10: return '\\n'
+    elif c==13: return '\\r'
+    elif c==32: return '" "'
+    else: return '\\x{:02x}'.format(c)
+
+def outputFormatter(s):
+    """Show string or char.
+    """
+    result = ''
+    def formatSubString(s):
+        for c in s:
+            if c==32: yield ' '
+            else: yield outputCharFormatter(c)
+    if len(result)<200: return ''.join(formatSubString(s))
+    else:
+        return ''.join(formatSubString(s[:100]))+'...'+ \
+               ''.join(formatSubString(s[-100:]))
+
+
+class BitStream:
+    """Represent a bytes object. Can read bits and prefix codes the way
+    Brotli does.
+    """
+    def __init__(self, byteString):
+        self.data = byteString
+        #position in bits: byte pos is pos>>3, bit pos is pos&7
+        self.pos = 0
+
+    def __repr__(self):
+        """Representation
+        >>> olleke
+        BitStream(pos=0:0)
+        """
+        return "BitStream(pos={:x}:{})".format(self.pos>>3, self.pos&7)
+
+    def read(self, n):
+        """Read n bits from the stream and return as an integer.
+        Produces zero bits beyond the stream.
+        >>> olleke.data[0]==27
+        True
+        >>> olleke.read(5)
+        27
+
+        >>> olleke
+        BitStream(pos=0:5)
+        """
+        value = self.peek(n)
+        self.pos += n
+        if self.pos>len(self.data)*8:
+            raise ValueError('Read past end of stream')
+        return value
+
+    def peek(self, n):
+        """Peek an n bit integer from the stream without updating the pointer.
+        It is not an error to read beyond the end of the stream.
+        >>> olleke.data[:2]==b'\x1b\x2e' and 0x2e1b==11803
+        True
+        >>> olleke.peek(15)
+        11803
+        >>> hex(olleke.peek(32))
+        '0x2e1b'
+        """
+        #read bytes that contain the data: self.data[self.pos>>3:self.pos+n+7>>3]
+        #convert to int: int.from_bytes(..., 'little')
+        #shift out the bits from the first byte: >>(self.pos&7)
+        #mask unwanted bits: & (1<<n)-1
+        return int.from_bytes(
+            self.data[self.pos>>3:self.pos+n+7>>3],
+            'little')>>(self.pos&7) & (1<<n)-1
+
+    def readBytes(self, n):
+        """Read n bytes from the stream on a byte boundary.
+        """
+        if self.pos&7: raise ValueError('readBytes: need byte boundary')
+        result = self.data[self.pos>>3:(self.pos>>3)+n]
+        self.pos += 8*n
+        return result
+
+#-----------------------Symbol-------------------------------------------
+class Symbol:
+    """A symbol in a code.
+    Refers back to the code that contains it.
+    Index is the place in the alphabet of the symbol.
+    """
+    __slots__ = 'code', 'index'
+    def __init__(self, code, value):
+        self.code = code
+        self.index = value
+
+    def __repr__(self):
+        return 'Symbol({}, {})'.format(self.code.name, self.index)
+
+    def __len__(self):
+        """Number of bits in the prefix notation of this symbol
+        """
+        return self.code.length(self.index)
+
+    def __int__(self):
+        return self.index
+
+    #these routines call equivalent routine in Code class
+    def bitPattern(self):
+        """Value of the symbol in the stream
+        """
+        return self.code.bitPattern(self.index)
+
+    def extraBits(self):
+        """Number of extra bits to read for this symbol
+        """
+        return self.code.extraBits(self.index)
+
+    def __str__(self):
+        """Short descriptor of the symbol without extra bits.
+        """
+        return self.code.mnemonic(self.index)
+
+    #requiring optional extra bits, if self.code supports them
+    def value(self, extra=None):
+        """The value used for processing. Can be a tuple.
+        with optional extra bits
+        """
+        if isinstance(self.code, WithExtra):
+            if not 0<=extra<1<<self.extraBits():
+                raise ValueError("value: extra value doesn't fit in extraBits")
+            return self.code.value(self.index, extra)
+        if extra is not None:
+            raise ValueError('value: no extra bits for this code')
+        return self.code.value(self.index)
+
+    def explanation(self, extra=None):
+        """Long explanation of the value from the numeric value
+        with optional extra bits
+        Used by Layout.verboseRead when printing the value
+        """
+        if isinstance(self.code, WithExtra):
+            return self.code.callback(self, extra)
+        return self.code.callback(self)
+
+#========================Code definitions==================================
+class RangeDecoder:
+    """A decoder for the Code class that assumes the symbols
+    are encoded consecutively in binary.
+    It all depends on the "alphabetSize" property.
+    The range runs from 0 to alphabetSize-1.
+    This is the default decoder.
+    """
+    def __init__(self, *, alphabetSize=None, bitLength=None, **args):
+        if bitLength is not None: alphabetSize = 1<<bitLength
+        if alphabetSize is not None:
+            self.alphabetSize = alphabetSize
+            self.maxLength = (alphabetSize-1).bit_length()
+
+    def __len__(self):
+        return self.alphabetSize
+
+    def __iter__(self):
+        """Produce all symbols.
+        """
+        return map(partial(Symbol, self), range(len(self)))
+
+    def __getitem__(self, index):
+        if index>=self.alphabetSize: raise ValueError('index out of range')
+        return Symbol(self, index)
+
+    def bitPattern(self, index):
+        return '{:0{}b}'.format(index, self.maxLength)
+
+    def length(self, index):
+        """Encoding length of given symbol.
+        Does not depend on index in this case.
+        """
+        return self.maxLength
+
+    def decodePeek(self, data):
+        """Find which symbol index matches the given data (from peek, as a number)
+        and return the number of bits decoded.
+        Can also be used to figure out length of a symbol.
+        """
+        return self.maxLength, Symbol(self, data&(1<<self.maxLength)-1)
+
+class PrefixDecoder:
+    """A decoder for the Code class that uses a prefix code.
+    The code is determined by encoding:
+    encode[p] gives the index corresponding to bit pattern p.
+    Used setDecode(decodeTable) to switch the decoder from the default
+    to a prefix decoder, or pass decodeTable at init.
+    You can also use setLength(lengthTable)
+    to define the encoding from the lengths.
+    The set of symbol values does not need to be consecutive.
+    """
+    def __init__(self, *, decodeTable=None, **args):
+        if decodeTable is not None: self.setDecode(decodeTable)
+
+    def __len__(self):
+        return len(self.decodeTable)
+
+    def __iter__(self):
+        def revBits(index):
+            return self.bitPattern(index)[::-1]
+        return (
+            Symbol(self, index)
+            for index in sorted(self.decodeTable.values(), key=revBits)
+            )
+
+    def __getitem__(self, index):
+        if index not in self.lengthTable:
+            raise ValueError('No symbol {}[{}]'.format(
+                self.__class__.__name__, index))
+        return Symbol(self, index)
+
+    def bitPattern(self, index):
+        bits = next(b for (b,s) in self.decodeTable.items() if s==index)
+        return '{:0{}b}'.format(bits, self.length(index))
+
+    def length(self, index):
+        """Encoding length of given symbol.
+        """
+        return self.lengthTable[index]
+
+    def decodePeek(self, data):
+        """Find which symbol index matches the given data (from peek, as a number)
+        and return the number of bits decoded.
+        Can also be used to figure out length of a symbol.
+        """
+        #do binary search for word length
+        #invariant: lo<=length<=hi
+        lo, hi = self.minLength, self.maxLength
+        while lo<=hi:
+            mid = lo+hi>>1
+            #note lo<=mid<hi at this point
+            mask = (1<<mid)-1
+            #lets see what happens if we guess length is mid
+            try: index = self.decodeTable[data&mask]
+            except KeyError:
+                #too many bits specified, reduce estimated length
+                hi = mid-1
+                continue
+            #we found a symbol, but there could be a longer match
+            symbolLength = self.lengthTable[index]
+            if symbolLength<=mid:
+                #all bits match, symbol must be right
+                return symbolLength, Symbol(self, index)
+            #there must be more bits to match
+            lo = mid+1
+        return lo, Symbol(self, index)
+
+    #routine to set up the tables
+    def setDecode(self, decodeTable):
+        """Store decodeTable,
+        and compute lengthTable, minLength, maxLength from encodings.
+        """
+        self.decodeTable = decodeTable
+        #set of symbols with unknown length
+        todo = set(decodeTable)
+        #bit size under investigation
+        maskLength = 0
+        lengthTable = {}
+        while todo:
+            mask = (1<<maskLength)-1
+            #split the encodings that we didn't find yet using b bits
+            splitSymbols = defaultdict(list)
+            for s in todo: splitSymbols[s&mask].append(s)
+            #unique encodings have a length of maskLength bits
+            #set length, and remove from todo list
+            for s,subset in splitSymbols.items():
+                if len(subset)==1:
+                    lengthTable[self.decodeTable[s]] = maskLength
+                    todo.remove(s)
+            #now investigate with longer mask
+            maskLength +=1
+        #save result
+        self.lengthTable = lengthTable
+        self.minLength = min(lengthTable.values())
+        self.maxLength = max(lengthTable.values())
+        self.switchToPrefix()
+
+    def setLength(self, lengthTable):
+        """Given the bit pattern lengths for symbols given in lengthTable,
+        set decodeTable, minLength, maxLength
+        """
+        self.lengthTable = lengthTable
+        self.minLength = min(lengthTable.values())
+        self.maxLength = max(lengthTable.values())
+        #compute the backwards codes first; then reverse them
+        #compute (backwards) first code for every separate lengths
+        nextCodes = []
+        #build codes for each length, from right to left
+        code = 0
+        for bits in range(self.maxLength+1):
+            code <<= 1
+            nextCodes.append(code)
+            code += sum(x==bits for x in lengthTable.values())
+        self.decodeTable = {}
+        #count codes for each length, and store reversed in the table
+        for symbol in sorted(lengthTable):
+            bits = lengthTable[symbol]
+            bitpattern = '{:0{}b}'.format(nextCodes[bits], bits)
+            self.decodeTable[int(bitpattern[::-1], 2)] = symbol
+            nextCodes[bits] += 1
+        self.switchToPrefix()
+
+    def switchToPrefix(self):
+        """This routine makes sure the prefix decoder is activated.
+        """
+        self.mode = PrefixDecoder
+
+class Code(RangeDecoder, PrefixDecoder):
+    """An alphabet of symbols, that can be read from a stream.
+    If you use setDecode or setLength, you have a prefix code,
+    otherwise you have a range code.
+    Features:
+    code[index] produces symbol with given index
+    value(index): value of symbol
+    mnemonic(index): short description of symbol
+    explanation(index): show meaning of symbol, shown in Layout.verboseRead
+    iter(code): produce all symbols in some order
+    name: show as context in Layout.verboseRead
+    """
+    name = '?'
+    #callback is a function that gets the symbol and the extra bits
+    #default callback calls explanation
+    def __init__(self, name=None, *, callback=None, description='', **args):
+        """Don't forget to set either alphabetSize or decodeTable
+        """
+        #set name when provided, otherwise take class variable
+        if name is not None: self.name = name
+        if callback is not None: self.callback = callback
+        self.description = description
+        #mode switch
+        if 'bitLength' in args or 'alphabetSize' in args:
+            self.mode = RangeDecoder
+            RangeDecoder.__init__(self, **args)
+        elif 'decodeTable' in args:
+            self.mode = PrefixDecoder
+            PrefixDecoder.__init__(self, **args)
+        else:
+            super().__init__(**args)
+
+    def __repr__(self):
+        return self.__class__.__name__+' '+self.name
+
+    #the routines that get switched between RangeDecoder and PrefixDecoder
+    def __len__(self): return self.mode.__len__(self)
+    def __iter__(self): return self.mode.__iter__(self)
+    def __getitem__(self, index): return self.mode.__getitem__(self, index)
+    def bitPattern(self, index): return self.mode.bitPattern(self, index)
+    def length(self, index): return self.mode.length(self, index)
+    def decodePeek(self, data): return self.mode.decodePeek(self, data)
+    #general routines
+    def value(self, index, extra=None):
+        """Get value of symbol for computations.
+        Override where needed.
+        """
+        if extra is not None:
+            raise ValueError('value: no extra for this symbol')
+        return index
+
+    def mnemonic(self, index):
+        """Give mnemonic of symbol.
+        Override where needed.
+        """
+        return str(self.value(index))
+
+    def callback(self, symbol):
+        return self.explanation(symbol.index)
+
+    def explanation(self, index):
+        """Long explanation of the value from the numeric value
+        This is a default routine.
+        You can customize in three ways:
+        - set description to add some text
+        - override to get more control
+        - set callback to make it dependent on you local variables
+        """
+        value = self.value(index)
+        return '{0}{1}: {2}'.format(
+            self.description and self.description+': ',
+            self.bitPattern(index),
+            value,
+            )
+
+    def extraBits(self, index):
+        return 0
+
+    #Routines that use the decode interface
+    def showCode(self, width=80):
+        """Show all words of the code in a nice format.
+        """
+        #make table of all symbols with binary strings
+        symbolStrings = [
+            (self.bitPattern(s.index), self.mnemonic(s.index))
+            for s in self
+            ]
+        #determine column widths the way Lisp programmers do it
+        leftColWidth, rightColWidth = map(max, map(
+            map,
+            repeat(len),
+            zip(*symbolStrings)
+            ))
+        colwidth = leftColWidth+rightColWidth
+        columns = 81//(colwidth+2)
+        rows = -(-len(symbolStrings)//columns)
+        def justify(bs):
+            b,s = bs
+            return b.rjust(leftColWidth)+':'+s.ljust(rightColWidth)
+        for i in range(rows):
+            print(' '.join(map(justify, symbolStrings[i::rows])).rstrip())
+
+    def readTuple(self, stream):
+        """Read symbol from stream. Returns symbol, length.
+        """
+        length, symbol = self.decodePeek(stream.peek(self.maxLength))
+        stream.pos += length
+        return length, symbol
+
+    def readTupleAndExtra(self, stream):
+        return self.readTuple(stream)+(0, None)
+
+class WithExtra(Code):
+    """Extension for Code so that symbol may have extra bits associated.
+    If you supply an extraTable, you can use extraBits
+    You can define an extraTable,
+    which allows to call extraBits to get the number of extraBits.
+    Otherwise, you can supply extraBits yourself.
+    Routine readTupleAndExtra now reads the extra bits too.
+    Value probably needs to be overridden; see Enumerator.
+    Note: this does not give you an decodeTable.
+    """
+    #redefine these if you don't want to use an extraTable
+    def extraBits(self, index):
+        """Get the number of extra bits for this symbol.
+        """
+        return self.extraTable[index]
+
+    def mnemonic(self, index):
+        """This value must be independent of extra.
+        """
+        return str(index)
+
+    def readTupleAndExtra(self, stream):
+        """Read symbol and extrabits from stream.
+        Returns symbol length, symbol, extraBits, extra
+        >>> olleke.pos = 6
+        >>> MetablockLengthAlphabet().readTupleAndExtra(olleke)
+        (2, Symbol(MLEN, 4), 16, 46)
+        """
+        length, symbol = self.decodePeek(stream.peek(self.maxLength))
+        stream.pos += length
+        extraBits = self.extraBits(symbol.index)
+        return length, symbol, extraBits, stream.read(extraBits)
+
+    def explanation(self, index, extra=None):
+        """Expanded version of Code.explanation supporting extra bits.
+        If you don't supply extra, it is not mentioned.
+        """
+        extraBits = 0 if extra is None else self.extraBits(index)
+        if not hasattr(self, 'extraTable'):
+            formatString = '{0}{3}'
+            lo = hi = value = self.value(index, extra)
+        elif extraBits==0:
+            formatString = '{0}{2}: {3}'
+            lo, hi = self.span(index)
+            value = lo
+        else:
+            formatString = '{0}{1} {2}: {3}-{4}; {3}+{5}={6}'
+            lo, hi = self.span(index)
+            value = lo+extra
+        return formatString.format(
+            self.description and self.description+': ',
+            'x'*extraBits,
+            self.bitPattern(index),
+            lo, hi,
+            extra,
+            value,
+            )
+
+    def callback(self, symbol, extra):
+        return self.explanation(symbol.index, extra)
+
+class BoolCode(Code):
+    """Same as Code(bitLength=1), but shows a boolean.
+    """
+    def __init__(self, name=None, **args):
+        super().__init__(name, bitLength=1, **args)
+
+    def value(self, index, extra=None):
+        return bool(super().value(index, extra))
+
+class Enumerator(WithExtra):
+    """Code that is defined by the ExtraTable.
+    extraTable is a class variable that contains
+    the extraBits of the symbols from 0
+    value0 contains the value of symbol 0
+    encodings is not neccessary, but allowed.
+    Note: place for FixedCode to make sure extraBits works
+    """
+    def __init__(self, name=None, **args):
+        #if there is no decodeTable to determine length, compute it ourselves
+        if 'decodeTable' not in args:
+            args['alphabetSize'] = len(self.extraTable)
+        super().__init__(name, **args)
+
+    def __len__(self):
+        return len(self.extraTable)
+
+    def __getitem__(self, index):
+        """Faster than PrefixDecoder
+        """
+        if index>=len(self.extraTable):
+            raise ValueError("No symbol {}[{}]".format(
+                self.__class__.__name__, index))
+        return Symbol(self, index)
+
+    def value(self, index, extra):
+        """Override if you don't define value0 and extraTable
+        """
+        lower, upper = self.span(index)
+        value = lower+(extra or 0)
+        if value>upper:
+            raise ValueError('value: extra out of range')
+        return value
+
+    def span(self, index):
+        """Give the range of possible values in a tuple
+        Useful for mnemonic and explanation
+        """
+        lower = self.value0+sum(1<<x for x in self.extraTable[:index])
+        upper = lower+(1<<self.extraTable[index])
+        return lower, upper-1
+
+#======================Code subclasses======================================
+#Alphabets used in the metablock header----------------------------------
+#For prefix codes
+class PrefixCodeHeader(WithExtra):
+    """Header of prefix codes.
+    """
+    def __init__(self, codename):
+        super().__init__('PFX', bitLength=2)
+        #this is the name of the code that it describes
+        self.codename = codename
+
+    def extraBits(self, index):
+        return 2 if index==1 else 0
+
+    def value(self, index, extra):
+        """Returns ('Simple', #codewords) or ('Complex', HSKIP)
+        """
+        if index==1:
+            if extra>3:
+                raise ValueError('value: extra out of range')
+            return 'Simple', extra+1
+        if extra:
+            raise ValueError('value: extra out of range')
+        return 'Complex', index
+
+    def explanation(self, index, extra):
+        if index==1:
+            return '{} is simple with {} code word{}'.format(
+                self.codename, extra+1, 's' if extra else '')
+        lengths = [1, 2, 3, 4, 0, 5, 17, 6]
+        return '{} is complex with lengths {}...'.format(
+            self.codename,
+            ','.join(
+                map(str, lengths[index:index+5]))
+            )
+
+class TreeShapeAlhabet(BoolCode):
+    """The bit used to indicate if four word code is "deep" or "wide"
+    """
+    name = 'SHAPE'
+    def value(self, index):
+        return [(2,2,2,2), (1,2,3,3)][index]
+
+    def explanation(self, index):
+        return str(bool(index))+': lengths {},{},{},{}'.format(*self.value(index))
+
+class LengthOfLengthAlphabet(Code):
+    """For use in decoding complex code descriptors.
+    >>> lengthOfLengthAlphabet = LengthOfLengthAlphabet('')
+    >>> print(lengthOfLengthAlphabet[2])
+    coded with 2 bits
+    >>> len(lengthOfLengthAlphabet[0])
+    2
+    >>> [len(lengthOfLengthAlphabet[x]) for x in range(6)]
+    [2, 4, 3, 2, 2, 4]
+    >>> lengthOfLengthAlphabet.showCode()
+      00:skipped             01:coded with 4 bits 0111:coded with 1 bits
+      10:coded with 3 bits  011:coded with 2 bits 1111:coded with 5 bits
+    """
+    decodeTable = {
+         0b00:0,     0b10:3,
+       0b0111:1,     0b01:4,
+        0b011:2,   0b1111:5,
+       }
+
+    def __init__(self, name=None, **args):
+        super().__init__(name, decodeTable=self.decodeTable, **args)
+
+    def mnemonic(self, index):
+        if index==0: return 'skipped'
+        return 'coded with {} bits'.format(index)
+
+    def explanation(self, index, extra=None):
+        return self.description+': '+self.mnemonic(index)
+
+class LengthAlphabet(WithExtra):
+    """Length of symbols
+    Used during construction of a code.
+    """
+    def __init__(self, name):
+        super().__init__(name, alphabetSize=18)
+
+    def extraBits(self, index):
+        return {16:2, 17:3}.get(index, 0)
+
+    def mnemonic(self, index):
+        if index==0: return 'unused'
+        elif index==16: return 'rep xx'
+        elif index==17: return 'zero xxx'
+        else: return 'len {}'.format(index)
+
+    def explanation(self, index, extra):
+        return self.description.format(self[index], extra)
+
+    def value(self, index, extra):
+        #the caller got the length already, so extra is enough
+        return extra
+
+#Stream header
+class WindowSizeAlphabet(Code):
+    """The alphabet used for window size in the stream header.
+    >>> WindowSizeAlphabet()[10].explanation()
+    'windowsize=(1<<10)-16=1008'
+    """
+    decodeTable = {
+        0b0100001: 10,   0b1100001: 14,   0b0011: 18,   0b1011: 22,
+        0b0110001: 11,   0b1110001: 15,   0b0101: 19,   0b1101: 23,
+        0b1000001: 12,         0b0: 16,   0b0111: 20,   0b1111: 24,
+        0b1010001: 13,   0b0000001: 17,   0b1001: 21,
+        0b0010001: None,
+        }
+
+    name = 'WSIZE'
+
+    def __init__(self, name=None):
+        super().__init__(name, decodeTable=self.decodeTable)
+
+    def value(self, index):
+        #missing value gives index None
+        if index is None: return None
+        return (1<<index)-16
+
+    def explanation(self, index):
+        return 'windowsize=(1<<{})-16={}'.format(
+            index, (1<<index)-16)
+
+#Metablock
+class MetablockLengthAlphabet(WithExtra):
+    """Used for the meta block length;
+    also indicates a block with no data
+    >>> metablockLengthAlphabet = MetablockLengthAlphabet()
+    >>> metablockLengthAlphabet[0]; str(metablockLengthAlphabet[0])
+    Symbol(MLEN, 0)
+    'empty'
+    >>> metablockLengthAlphabet[3]
+    Traceback (most recent call last):
+        ...
+    ValueError: No symbol MetablockLengthAlphabet[3]
+    >>> print(metablockLengthAlphabet[4])
+    hhhh00
+    >>> metablockLengthAlphabet[4].value(0x1000)
+    4097
+    >>> metablockLengthAlphabet[5].value(0x1000)
+    Traceback (most recent call last):
+        ...
+    InvalidStream: Zeros in high nibble of MLEN
+    >>> metablockLengthAlphabet[5].explanation(0x12345)
+    'data length: 12345h+1=74566'
+    >>> metablockLengthAlphabet.showCode()
+    00:hhhh00   10:hhhhhh10 01:hhhhh01  11:empty
+    """
+    decodeTable = {0b11:0, 0b00:4, 0b01:5, 0b10:6}
+
+    name = 'MLEN'
+    def __init__(self, name=None):
+        super().__init__(name, decodeTable=self.decodeTable)
+
+    def extraBits(self, index):
+        return index*4
+
+    def mnemonic(self, index):
+        if index==0: return 'empty'
+        return 'h'*(self.extraBits(index)//4)+self.bitPattern(index)
+
+    def value(self, index, extra):
+        extraBits = self.extraBits(index)
+        if not 0<=extra<1<<extraBits:
+            raise ValueError('value: extra out of range')
+        if index==0: return 0
+        if index>4 and extra>>extraBits-4==0: raise InvalidStream(
+            'Zeros in high nibble of MLEN')
+        return extra+1
+
+    def explanation(self, index, extra):
+        if index==0: return '11: empty block'
+        extraBits = self.extraBits(index)
+        return 'data length: {:0{}x}h+1={}'.format(extra, extraBits//4, extra+1)
+
+
+class ReservedAlphabet(BoolCode):
+    """The reserved bit that must be zero.
+    """
+    name = 'RSVD'
+    def value(self, index):
+        if index: raise ValueError('Reserved bit is not zero')
+
+    def explanation(self, index):
+        return 'Reserved (must be zero)'
+
+class FillerAlphabet(Code):
+    def __init__(self, *, streamPos):
+        super().__init__('SKIP', bitLength=(-streamPos)&7)
+
+    def explanation(self, index):
+        return '{} bit{} ignored'.format(
+            self.length(index),
+            '' if self.length(index)==1 else 's',
+            )
+
+class SkipLengthAlphabet(WithExtra):
+    """Used for the skip length in an empty metablock
+    >>> skipLengthAlphabet = SkipLengthAlphabet()
+    >>> skipLengthAlphabet[0]; str(skipLengthAlphabet[0])
+    Symbol(SKIP, 0)
+    'empty'
+    >>> skipLengthAlphabet[4]
+    Traceback (most recent call last):
+        ...
+    ValueError: index out of range
+    >>> print(skipLengthAlphabet[3])
+    hhhhhh11
+    >>> skipLengthAlphabet[2].value(0x1000)
+    4097
+    >>> skipLengthAlphabet[3].value(0x1000)
+    Traceback (most recent call last):
+        ...
+    InvalidStream: Zeros in high byte of SKIPBYTES
+    >>> skipLengthAlphabet[3].explanation(0x12345)
+    'skip length: 12345h+1=74566'
+    >>> skipLengthAlphabet.showCode()
+    00:empty    01:hh01     10:hhhh10   11:hhhhhh11
+    """
+    def __init__(self):
+        super().__init__('SKIP', bitLength=2)
+
+    def extraBits(self, index):
+        return index*8
+
+    def mnemonic(self, index):
+        if index==0: return 'empty'
+        return 'h'*(self.extraBits(index)//4)+self.bitPattern(index)
+
+    def value(self, index, extra):
+        extraBits = self.extraBits(index)
+        if not 0<=extra<1<<extraBits:
+            raise ValueError('value: extra out of range')
+        if index==0: return 0
+        if index>1 and extra>>extraBits-8==0:
+            raise InvalidStream('Zeros in high byte of SKIPBYTES')
+        return extra+1
+
+    def explanation(self, index, extra):
+        if index==0: return '00: no skip'
+        extraBits = self.extraBits(index)
+        return 'skip length: {:{}x}h+1={}'.format(extra, extraBits//8, extra+1)
+
+
+class TypeCountAlphabet(Enumerator):
+    """Used for giving block type counts and tree counts.
+    >>> TypeCountAlphabet(description='').showCode()
+       0:0            0101:xx,0101      1011:xxxxx,1011
+    0001:0001         1101:xxxxxx,1101  0111:xxx,0111
+    1001:xxxx,1001    0011:x,0011       1111:xxxxxxx,1111
+    """
+    decodeTable = {
+             0b0: 0,   0b1001: 5,
+          0b0001: 1,   0b1011: 6,
+          0b0011: 2,   0b1101: 7,
+          0b0101: 3,   0b1111: 8,
+          0b0111: 4,
+          }
+
+    value0 = 1
+    extraTable = [0, 0, 1, 2, 3, 4, 5, 6, 7]
+    name = 'BT#'
+
+    def __init__(self, name=None, *, description):
+        super().__init__(
+            name,
+            decodeTable=self.decodeTable,
+            description=description)
+
+    def mnemonic(self, index):
+        if index==0: return '0'
+        if index==1: return '0001'
+        return 'x'*(self.extraBits(index))+','+self.bitPattern(index)
+
+    def explanation(self, index, extra):
+        value = self.value(index, extra)
+        description = self.description
+        if value==1: description = description[:-1]
+        return '{}: {} {}'.format(
+            self.mnemonic(index),
+            value,
+            description)
+
+class BlockTypeAlphabet(Code):
+    """The block types; this code works for all three kinds.
+    >>> b = BlockTypeAlphabet('T', NBLTYPES=5)
+    >>> print(*(x for x in b))
+    prev +1 #0 #1 #2 #3 #4
+    """
+    def __init__(self, name, NBLTYPES, **args):
+        super().__init__(name, alphabetSize=NBLTYPES+2, **args)
+        self.NBLTYPES = NBLTYPES
+
+    def mnemonic(self, index):
+        if index==0: return 'prev'
+        elif index==1: return '+1'
+        else: return '#'+str(index-2)
+
+    def value(self, index):
+        return index-2
+
+    def explanation(self, index):
+        if index==0: return '0: previous'
+        elif index==1: return '1: increment'
+        else: return 'Set block type to: '+str(index-2)
+
+class BlockCountAlphabet(Enumerator):
+    """Block counts
+    >>> b = BlockCountAlphabet('L')
+    >>> print(b[25])
+    [24*x]: BC16625-16793840
+    """
+
+    value0 = 1
+    extraTable = [2,2,2,2,3, 3,3,3,4,4, 4,4,5,5,5, 5,6,6,7,8, 9,10,11,12,13, 24]
+    def __init__(self, name, **args):
+        super().__init__(name, alphabetSize=26, **args)
+
+    def mnemonic(self, index):
+        extraBits = self.extraBits(index)
+        return '{}: BC{}-{}'.format(
+            'x'*extraBits if index<5 else '[{}*x]'.format(extraBits),
+            *self.span(index))
+
+    def explanation(self, index, extra):
+        return 'Block count: '+super().explanation(index, extra)
+
+class DistanceParamAlphabet(WithExtra):
+    """The distance parameters NPOSTFIX and NDIRECT.
+    Although these are treated as two in the description, this is easier.
+    """
+    def __init__(self):
+        super().__init__('DIST', bitLength=2)
+
+    def extraBits(self, index):
+        return 4
+
+    def value(self, index, extra):
+        """Returns NPOSTFIX and NDIRECT<<NPOSTFIX
+        """
+        if extra>15:
+            raise ValueError('value: extra out of range')
+        return index, extra<<index
+
+    def explanation(self, index, extra):
+        return '{} postfix bits and {:04b}<<{}={} direct codes'.format(
+            index, extra, index, extra<<index)
+
+    def mnemonic(self, index):
+        return 'PF'+str(index)
+
+class LiteralContextMode(Code):
+    """For the literal context modes.
+    >>> LiteralContextMode().showCode()
+    00:LSB6   01:MSB6   10:UTF8   11:Signed
+    >>> LiteralContextMode().explanation(2)
+    'Context mode for type 9: 2(UTF8)'
+    """
+
+    def __init__(self, *, number=9):
+        super().__init__('LC'+str(number), bitLength=2)
+        self.number = number
+
+    def mnemonic(self, index):
+        return ['LSB6', 'MSB6', 'UTF8', 'Signed'][index]
+
+    def explanation(self, index):
+        return 'Context mode for type {}: {}({})'.format(
+            self.number,
+            index,
+            self.mnemonic(index))
+
+class RLEmaxAlphabet(Enumerator):
+    """Used for describing the run length encoding used for describing context maps.
+    >>> RLEmaxAlphabet().showCode()
+    0:1    1:more
+    """
+    value0 = 0
+    extraTable = [0, 4]
+    name = 'RLE#'
+
+    def mnemonic(self, index):
+        return ['1', 'more'][index]
+
+    def explanation(self, index, extra):
+        description = self.description and self.description+': '
+        if index==0: return description+'No RLE coding'
+        return '{}xxxx 1: RLEMAX={}'.format(description, extra+1)
+
+class TreeAlphabet(WithExtra):
+    """The alphabet to enumerate entries (called trees) in the context map.
+    parameters are RLEMAX and NTREES
+    >>> t = TreeAlphabet('', RLEMAX=3, NTREES=5)
+    >>> len(t)
+    8
+    >>> print(t[2])
+    xx+4 zeroes
+    >>> t[3].explanation(2)
+    '8+010=10 zeroes'
+    >>> t[0].value(0)
+    (1, 0)
+    """
+    name = 'CMI'
+    def __init__(self, name=None, *, RLEMAX, NTREES, **args):
+        super().__init__(name, alphabetSize=RLEMAX+NTREES, **args)
+        self.RLEMAX = RLEMAX
+        self.NTREES = NTREES
+
+    def extraBits(self, index):
+        if 0<index<=self.RLEMAX: return index
+        return 0
+
+    def mnemonic(self, index):
+        if index==0: return 'map #0'
+        if index<=self.RLEMAX:
+            return '{}+{} zeroes'.format('x'*index, 1<<index)
+        return 'map #{}'.format(index-self.RLEMAX)
+
+    def value(self, index, extra):
+        """Give count and value."""
+        index = index
+        if index==0: return 1, 0
+        if index<=self.RLEMAX: return (1<<index)+extra, 0
+        return 1, index-self.RLEMAX
+
+    def explanation(self, index, extra):
+        description = self.description and self.description+': '
+        if index==0: return description+'map #0'
+        if index<=self.RLEMAX:
+            return '{}+{:0{}b}={} zeroes'.format(
+                (1<<index),
+                extra, self.extraBits(index),
+                (1<<index)+extra)
+        return '{}map #{}-{}={}'.format(
+            description,
+            index, self.RLEMAX, index-self.RLEMAX)
+
+#Prefix alphabets for the data stream----------------------------------
+class LiteralAlphabet(Code):
+    """Alphabet of symbols.
+    """
+    minLength = maxLength = 8
+    def __init__(self, number):
+        super().__init__('L'+str(number), alphabetSize=1<<8)
+
+    def mnemonic(self, index):
+        return outputCharFormatter(index)
+
+    def value(self, index, extra=None):
+        return index
+
+    def explanation(self, index, extra=None):
+        return self.mnemonic(index)
+
+class InsertLengthAlphabet(Enumerator):
+    """Intern code for insert counts
+    """
+    value0 = 0
+    extraTable = [0,0,0,0,0, 0,1,1,2,2, 3,3,4,4,5, 5,6,7,8,9, 10,12,14,24]
+
+class CopyLengthAlphabet(Enumerator):
+    value0 = 2
+    extraTable = [0,0,0,0,0, 0,0,0,1,1, 2,2,3,3,4, 4,5,5,6,7, 8,9,10,24]
+
+class InsertAndCopyAlphabet(WithExtra):
+    """The insert and copy code
+    >>> for x in range(0,704,704//13):
+    ...    print('{:10b}'.format(x), InsertAndCopyAlphabet()[x])
+             0 I0C2&D=0
+        110110 I6+xC8&D=0
+       1101100 I5C22+xxx&D=0
+      10100010 I4C4
+      11011000 I3C10+x
+     100001110 I14+xxC8
+     101000100 I10+xxC22+xxx
+     101111010 I98+xxxxxC14+xx
+     110110000 I6+xC70+xxxxx
+     111100110 I1090+[10*x]C8
+    1000011100 I26+xxxC326+[8*x]
+    1001010010 I322+[8*x]C14+xx
+    1010001000 I194+[7*x]C70+xxxxx
+    1010111110 I22594+[24*x]C1094+[10*x]
+    """
+    insertLengthAlphabet = InsertLengthAlphabet(None)
+    copyLengthAlphabet = CopyLengthAlphabet(None)
+
+    def __init__(self, number=''):
+        super().__init__('IC'+str(number), bitLength=10)
+
+    def __len__(self):
+        return 704
+
+    def extraBits(self, index):
+        insertSymbol, copySymbol, dist0 = self.splitSymbol(index)
+        return InsertLengthAlphabet.extraTable[insertSymbol.index] + \
+            CopyLengthAlphabet.extraTable[copySymbol.index]
+
+    def splitSymbol(self, index):
+        """Give relevant values for computations:
+        (insertSymbol, copySymbol, dist0flag)
+        """
+        #determine insert and copy upper bits from table
+        row = [0,0,1,1,2,2,1,3,2,3,3][index>>6]
+        col = [0,1,0,1,0,1,2,0,2,1,2][index>>6]
+        #determine inserts and copy sub codes
+        insertLengthCode = row<<3 | index>>3&7
+        if row: insertLengthCode -= 8
+        copyLengthCode = col<<3 | index&7
+        return (
+            Symbol(self.insertLengthAlphabet, insertLengthCode),
+            Symbol(self.copyLengthAlphabet, copyLengthCode),
+            row==0
+            )
+
+    def mnemonic(self, index):
+        """Make a nice mnemonic
+        """
+        i,c,d0 = self.splitSymbol(index)
+        iLower, _ = i.code.span(i.index)
+        iExtra = i.extraBits()
+        cLower, _ = c.code.span(c.index)
+        cExtra = c.extraBits()
+        return 'I{}{}{}C{}{}{}{}'.format(
+            iLower,
+            '+' if iExtra else '',
+            'x'*iExtra if iExtra<6 else '[{}*x]'.format(iExtra),
+            cLower,
+            '+' if cExtra else '',
+            'x'*cExtra if cExtra<6 else '[{}*x]'.format(cExtra),
+            '&D=0' if d0 else '')
+
+    def value(self, index, extra):
+        i,c,d0 = self.splitSymbol(index)
+        iExtra = i.extraBits()
+        ce, ie = extra>>iExtra, extra&(1<<iExtra)-1
+        insert = i.value(ie)
+        copy = c.value(ce)
+        return insert, copy, d0
+
+    def explanation(self, index, extra):
+        insert, copy, d0 = self.value(index, extra)
+        if d0: return 'Literal: {}, copy: {}, same distance'.format(insert, copy)
+        else: return 'Literal: {}, copy: {}'.format(insert, copy)
+
+class DistanceAlphabet(WithExtra):
+    """Represent the distance encoding.
+    Dynamically generated alphabet.
+    This is what the documentation should have said:
+    Ignoring offsets for the moment, the "long" encoding works as follows:
+    Write the distance in binary as follows:
+    1xy..yz..z, then the distance symbol consists of n..nxz..z
+    Where:
+    n is one less than number of bits in y
+    x is a single bit
+    y..y are n+1 extra bits (encoded in the bit stream)
+    z..z is NPOSTFIX bits that are part of the symbol
+    The offsets are so as to start at the lowest useable value:
+    if 1xyyyyz = distance +(4<<POSTFIX)-NDIRECT-1
+    then n..nxz..z is symbol -NDIRECT-16
+    >>> d = DistanceAlphabet('D', NPOSTFIX=2, NDIRECT=10)
+    >>> print(d[4], d[17], d[34])
+    last-1 1 10xx00-5
+    >>> [str(d[x]) for x in range(26, 32)]
+    ['10x00-5', '10x01-5', '10x10-5', '10x11-5', '11x00-5', '11x01-5']
+    """
+    def __init__(self, number, *, NPOSTFIX, NDIRECT):
+        self.NPOSTFIX = NPOSTFIX
+        self.NDIRECT = NDIRECT
+        #set length
+        #Actually, not all symbols are used,
+        #only NDIRECT+16+(44-2*POSTFIX<<NPOSTFIX)
+        super().__init__('D'+str(number),
+            alphabetSize=self.NDIRECT+16+(48<<self.NPOSTFIX))
+
+    def extraBits(self, index):
+        """Indicate how many extra bits are needed to interpret symbol
+        >>> d = DistanceAlphabet('D', NPOSTFIX=2, NDIRECT=10)
+        >>> [d[i].extraBits() for i in range(26)]
+        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
+        >>> [d[i].extraBits() for i in range(26,36)]
+        [1, 1, 1, 1, 1, 1, 1, 1, 2, 2]
+        """
+        if index<16+self.NDIRECT: return 0
+        return 1 + ((index - self.NDIRECT - 16) >> (self.NPOSTFIX + 1))
+
+    def value(self, dcode, dextra):
+        """Decode value of symbol together with the extra bits.
+        >>> d = DistanceAlphabet('D', NPOSTFIX=2, NDIRECT=10)
+        >>> d[34].value(2)
+        (0, 35)
+        """
+        if dcode<16:
+            return [(1,0),(2,0),(3,0),(4,0),
+                    (1,-1),(1,+1),(1,-2),(1,+2),(1,-3),(1,+3),
+                    (2,-1),(2,+1),(2,-2),(2,+2),(2,-3),(2,+3)
+                ][dcode]
+        if dcode<16+self.NDIRECT:
+            return (0,dcode-16)
+        #we use the original formulas, instead of my clear explanation
+        POSTFIX_MASK = (1 << self.NPOSTFIX) - 1
+        ndistbits = 1 + ((dcode - self.NDIRECT - 16) >> (self.NPOSTFIX + 1))
+        hcode = (dcode - self.NDIRECT - 16) >> self.NPOSTFIX
+        lcode = (dcode - self.NDIRECT - 16) & POSTFIX_MASK
+        offset = ((2 + (hcode & 1)) << ndistbits) - 4
+        distance = ((offset + dextra) << self.NPOSTFIX) + lcode + self.NDIRECT + 1
+        return (0,distance)
+
+    def mnemonic(self, index, verbose=False):
+        """Give mnemonic representation of meaning.
+        verbose compresses strings of x's
+        """
+        if index<16:
+            return ['last', '2last', '3last', '4last',
+                'last-1', 'last+1', 'last-2', 'last+2', 'last-3', 'last+3',
+                '2last-1', '2last+1', '2last-2', '2last+2', '2last-3', '2last+3'
+                ][index]
+        if index<16+self.NDIRECT:
+            return str(index-16)
+        #construct strings like "1xx01-15"
+        index -= self.NDIRECT+16
+        hcode = index >> self.NPOSTFIX
+        lcode = index & (1<<self.NPOSTFIX)-1
+        if self.NPOSTFIX: formatString = '1{0}{1}{2:0{3}b}{4:+d}'
+        else: formatString = '1{0}{1}{4:+d}'
+        return formatString.format(
+            hcode&1,
+            'x'*(2+hcode>>1) if hcode<13 or verbose else '[{}*x]'.format(2+hcode>>1),
+            lcode, self.NPOSTFIX,
+            self.NDIRECT+1-(4<<self.NPOSTFIX))
+
+    def explanation(self, index, extra):
+        """
+        >>> d = DistanceAlphabet('D', NPOSTFIX=2, NDIRECT=10)
+        >>> d[55].explanation(13)
+        '11[1101]01-5: [0]+240'
+        """
+        extraBits = self.extraBits(index)
+        extraString = '[{:0{}b}]'.format(extra, extraBits)
+        return '{0}: [{1[0]}]{1[1]:+d}'.format(
+            self.mnemonic(index, True).replace('x'*(extraBits or 1), extraString),
+            self.value(index, extra))
+
+#Classes for doing actual work------------------------------------------
+class ContextModeKeeper:
+    """For computing the literal context mode.
+    You feed it characters, and it computes indices in the context map.
+    """
+    def __init__(self, mode):
+        self.chars = deque([0,0], maxlen=2)
+        self.mode = mode
+
+    def setContextMode(self, mode):
+        """Switch to given context mode (0..3)"""
+        self.mode = mode
+    def getIndex(self):
+        if self.mode==0:  #LSB6
+            return self.chars[1]&0x3f
+        elif self.mode==1: #MSB6
+            return self.chars[1]>>2
+        elif self.mode==2: #UTF8: character class of previous and a bit of the second
+            p2,p1 = self.chars
+            return self.lut0[p1]|self.lut1[p2]
+        elif self.mode==3: #Signed: initial bits of last two bytes
+            p2,p1 = self.chars
+            return self.lut2[p1]<<3|self.lut2[p2]
+
+    def add(self, index):
+        """Adjust the context for output char (as int)."""
+        self.chars.append(index)
+
+    #0: control     #16: quote  #32: ,:;  #48: AEIOU
+    #4: tab/lf/cr   #20: %      #36: .    #52: BC..Z
+    #8: space       #24: (<[{   #40: =    #56: aeiou
+    #12:!#$&*+-/?@| #28: )>]}   #44: 0-9  #60: bc..z
+    lut0 = [0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  4,  0,  0,  4,  0,  0,
+            0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
+            8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,
+           44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,
+           12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,
+           52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,
+           12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,
+           60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12,  0
+           ]+[0,1]*32+[2,3]*32
+    #0: space  1:punctuation  2:digit/upper 3:lower
+    lut1 = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+             0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+             0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+             2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,
+             1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+             2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
+             1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+             3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0
+           ]+[0]*96+[2]*32
+    #initial bits: 8*0, 4*0, 2*0, 1*0, 1*1, 2*1, 4*1, 8*1
+    lut2 = [0]+[1]*15+[2]*48+[3]*64+[4]*64+[5]*48+[6]*15+[7]
+    assert len(lut0)==len(lut1)==len(lut2)==256
+
+class WordList:
+    """Word list.
+    >>> WordList().word(7, 35555)
+    b'Program to '
+    """
+    NDBITS = [0,  0,  0,  0, 10, 10, 11, 11, 10, 10,
+             10, 10, 10,  9,  9,  8,  7,  7,  8,  7,
+              7,  6,  6,  5,  5]
+    def __init__(self):
+        self.file = open('dict', 'rb')
+        self.compileActions()
+
+    def word(self, size, dist):
+        """Get word
+        """
+        #split dist in index and action
+        ndbits = self.NDBITS[size]
+        index = dist&(1<<ndbits)-1
+        action = dist>>ndbits
+        #compute position in file
+        position = sum(n<<self.NDBITS[n] for n in range(4,size))+size*index
+        self.file.seek(position)
+        return self.doAction(self.file.read(size), action)
+
+    def upperCase1(self, word):
+        word = word.decode('utf8')
+        word = word[0].upper()+word[1:]
+        return word.encode('utf8')
+
+
+    #Super compact form of action table.
+    #_ means space, .U means UpperCaseAll, U(w) means UpperCaseFirst
+    actionTable = r"""
+        0:w        25:w+_for_     50:w+\n\t       75:w+. This_100:w+ize_
+        1:w+_      26:w[3:]       51:w+:          76:w+,      101:w.U+.
+        2:_+w+_    27:w[:-2]      52:_+w+._       77:.+w+_    102:\xc2\xa0+w
+        3:w[1:]    28:w+_a_       53:w+ed_        78:U(w)+(   103:_+w+,
+        4:U(w)+_   29:w+_that_    54:w[9:]        79:U(w)+.   104:U(w)+="
+        5:w+_the_  30:_+U(w)      55:w[7:]        80:w+_not_  105:w.U+="
+        6:_+w      31:w+._        56:w[:-6]       81:_+w+="   106:w+ous_
+        7:s_+w+_   32:.+w         57:w+(          82:w+er_    107:w.U+,_
+        8:w+_of_   33:_+w+,_      58:U(w)+,_      83:_+w.U+_  108:U(w)+=\'
+        9:U(w)     34:w[4:]       59:w[:-8]       84:w+al_    109:_+U(w)+,
+       10:w+_and_  35:w+_with_    60:w+_at_       85:_+w.U    110:_+w.U+="
+       11:w[2:]    36:w+\'        61:w+ly_        86:w+=\'    111:_+w.U+,_
+       12:w[:-1]   37:w+_from_    62:_the_+w+_of_ 87:w.U+"    112:_+w.U+,
+       13:,_+w+_   38:w+_by_      63:w[:-5]       88:U(w)+._  113:w.U+(
+       14:w+,_     39:w[5:]       64:w[:-9]       89:_+w+(    114:w.U+._
+       15:_+U(w)+_ 40:w[6:]       65:_+U(w)+,_    90:w+ful_   115:_+w.U+.
+       16:w+_in_   41:_the_+w     66:U(w)+"       91:_+U(w)+._116:w.U+=\'
+       17:w+_to_   42:w[:-4]      67:.+w+(        92:w+ive_   117:_+w.U+._
+       18:e_+w+_   43:w+. The_    68:w.U+_        93:w+less_  118:_+U(w)+="
+       19:w+"      44:w.U         69:U(w)+">      94:w.U+\'   119:_+w.U+=\'
+       20:w+.      45:w+_on_      70:w+="         95:w+est_   120:_+U(w)+=\'
+       21:w+">     46:w+_as_      71:_+w+.        96:_+U(w)+.
+       22:w+\n     47:w+_is_      72:.com/+w      97:w.U+">
+       23:w[:-3]   48:w[:-7]                      98:_+w+=\'
+       24:w+]      49:w[:-1]+ing_ 74:U(w)+\'      99:U(w)+,
+        """
+
+    def compileActions(self):
+        """Build the action table from the text above
+        """
+        import re
+        self.actionList = actions = [None]*121
+        #Action 73, which is too long, looks like this when expanded:
+        actions[73] = "b' the '+w+b' of the '"
+        #find out what the columns are
+        actionLines = self.actionTable.splitlines()
+        colonPositions = [m.start()
+            for m in re.finditer(':',actionLines[1])
+            ]+[100]
+        columns = [(colonPositions[i]-3,colonPositions[i+1]-3)
+            for i in range(len(colonPositions)-1)]
+        for line in self.actionTable.splitlines(keepends=False):
+            for start,end in columns:
+                action = line[start:end]
+                #skip empty actions
+                if not action or action.isspace(): continue
+                #chop it up, and check if the colon is properly placed
+                index, colon, action = action[:3], action[3], action[4:]
+                assert colon==':'
+                #remove filler spaces at right
+                action = action.rstrip()
+                #replace space symbols
+                action = action.replace('_', ' ')
+                wPos = action.index('w')
+                #add quotes around left string when present
+                #translation: any pattern from beginning, up to
+                #(but not including) a + following by a w later on
+                action = re.sub(r"^(.*)(?=\+[U(]*w)", r"b'\1'", action)
+                #add quotes around right string when present
+                #translation: anything with a w in it, followed by a +
+                #and a pattern up to the end
+                #(there is no variable lookbehind assertion,
+                #so we have to copy the pattern)
+                action = re.sub(r"(w[[:\-1\]).U]*)\+(.*)$", r"\1+b'\2'", action)
+                #expand shortcut for uppercaseAll
+                action = action.replace(".U", ".upper()")
+                #store action
+                actions[int(index)] = action
+
+    def doAction(self, w, action):
+        """Perform the proper action
+        """
+        #set environment for the UpperCaseFirst
+        U = self.upperCase1
+        return eval(self.actionList[action], locals())
+
+class Layout:
+    """Class to layout the output.
+    """
+    #display width of hexdata+bitdata
+    width = 25
+    #general
+    def __init__(self, stream):
+        self.stream = stream
+        self.bitPtr = self.width
+
+    def makeHexData(self, pos):
+        """Produce hex dump of all data containing the bits
+        from pos to stream.pos
+        """
+        firstAddress = pos+7>>3
+        lastAddress = self.stream.pos+7>>3
+        return ''.join(map('{:02x} '.format,
+            self.stream.data[firstAddress:lastAddress]))
+
+    def formatBitData(self, pos, width1, width2=0):
+        """Show formatted bit data:
+        Bytes are separated by commas
+        whole bytes are displayed in hex
+        >>> Layout(olleke).formatBitData(6, 2, 16)
+        '|00h|2Eh,|00'
+        >>> Layout(olleke).formatBitData(4, 1, 0)
+        '1'
+        """
+        result = []
+        #make empty prefix code explicit
+        if width1==0: result = ['()', ',']
+        for width in width1, width2:
+            #skip empty width2
+            if width==0: continue
+            #build result backwards in a list
+            while width>0:
+                availableBits = 8-(pos&7)
+                if width<availableBits:
+                    #read partial byte, beginning nor ending at boundary
+                    data = self.stream.data[pos>>3] >> (pos&7) & (1<<width)-1
+                    result.append('{:0{}b}'.format(data, width))
+                elif availableBits<8:
+                    #read rest of byte, ending at boundary
+                    data = self.stream.data[pos>>3] >> (pos&7)
+                    result.append('|{:0{}b}'.format(data, availableBits))
+                else:
+                    #read whole byte (in hex), beginning and ending at boundary
+                    data = self.stream.data[pos>>3]
+                    result.append('|{:02X}h'.format(data))
+                width -= availableBits
+                pos += availableBits
+            #if width overshot from the availableBits subtraction, fix it
+            pos += width
+            #add comma to separate fields
+            result.append(',')
+        #concatenate pieces, reversed, skipping the last space
+        return ''.join(result[-2::-1])
+
+    def readPrefixCode(self, alphabet):
+        """give alphabet the prefix code that is read from the stream
+        Called for the following alphabets, in this order:
+        The alphabet in question must have a "logical" order,
+        otherwise the assignment of symbols doesn't work.
+        """
+        mode, numberOfSymbols = self.verboseRead(PrefixCodeHeader(alphabet.name))
+        if mode=='Complex':
+            #for a complex code, numberOfSymbols means hskip
+            self.readComplexCode(numberOfSymbols, alphabet)
+            return alphabet
+        else:
+            table = []
+            #Set table of lengths for mnemonic function
+            lengths = [[0], [1,1], [1,2,2], '????'][numberOfSymbols-1]
+            #adjust mnemonic function of alphabet class
+            def myMnemonic(index):
+                return '{} bit{}: {}'.format(
+                    lengths[i],
+                    '' if lengths[i]==1 else 's',
+                    alphabet.__class__.mnemonic(alphabet, index)
+                    )
+            alphabet.mnemonic = myMnemonic
+            for i in range(numberOfSymbols):
+                table.append(self.verboseRead(alphabet, skipExtra=True).index)
+            #restore mnemonic
+            del alphabet.mnemonic
+            if numberOfSymbols==4:
+                #read tree shape to redefine lengths
+                lengths = self.verboseRead(TreeShapeAlhabet())
+            #construct the alphabet prefix code
+            alphabet.setLength(dict(zip(table, lengths)))
+        return alphabet
+
+    def readComplexCode(self, hskip, alphabet):
+        """Read complex code"""
+        stream = self.stream
+        #read the lengths for the length code
+        lengths = [1,2,3,4,0,5,17,6,16,7,8,9,10,11,12,13,14,15][hskip:]
+        codeLengths = {}
+        total = 0
+        lol = LengthOfLengthAlphabet('##'+alphabet.name)
+        #lengthCode will be used for coding the lengths of the new code
+        #we use it for display until now; definition comes below
+        lengthCode = LengthAlphabet('#'+alphabet.name)
+        lengthIter = iter(lengths)
+        while total<32:
+            newSymbol = next(lengthIter)
+            lol.description = str(lengthCode[newSymbol])
+            length = self.verboseRead(lol)
+            if length:
+                codeLengths[newSymbol] = length
+                total += 32>>length
+            if total>=32:
+                break
+        if total>32: raise ValueError("Stream format")
+        #Now set the encoding of the lengthCode
+        lengthCode.setLength(codeLengths)
+        print("***** Lengths for {} will be coded as:".format(alphabet.name))
+        lengthCode.showCode()
+        #Now determine the symbol lengths with the lengthCode
+        symbolLengths = {}
+        total = 0
+        lastLength = 8
+        alphabetIter = iter(alphabet)
+        while total<32768:
+            #look ahead to see what is going to happen
+            length = lengthCode.decodePeek(
+                self.stream.peek(lengthCode.maxLength))[1].index
+            #in every branch, set lengthCode.description to explanatory text
+            #lengthCode calls format(symbol, extra) with this string
+            if length==0:
+                symbol = next(alphabetIter)
+                lengthCode.description = 'symbol {} unused'.format(symbol)
+                self.verboseRead(lengthCode)
+                #unused symbol
+                continue
+            if length==16:
+                lengthCode.description = \
+                    '{1}+3 symbols of length '+str(lastLength)
+                extra = self.verboseRead(lengthCode)
+                #scan series of 16s (repeat counts)
+                #start with repeat count 2
+                repeat = 2
+                startSymbol = next(alphabetIter)
+                endSymbol = next(alphabetIter)
+                symbolLengths[startSymbol.index] = \
+                    symbolLengths[endSymbol.index] = lastLength
+                #count the two just defined symbols
+                total += 2*32768>>lastLength
+                #note: loop may end because we're there
+                #even if a 16 _appears_ to follow
+                while True:
+                    #determine last symbol
+                    oldRepeat = repeat
+                    repeat = (repeat-2<<2)+extra+3
+                    #read as many symbols as repeat increased
+                    for i in range(oldRepeat, repeat):
+                        endSymbol = next(alphabetIter)
+                        symbolLengths[endSymbol.index] = lastLength
+                    #compute new total; it may be end of loop
+                    total += (repeat-oldRepeat)*32768>>lastLength
+                    if total>=32768: break
+                    #see if there is more to do
+                    length = lengthCode.decodePeek(
+                        self.stream.peek(lengthCode.maxLength))[1].index
+                    if length!=16: break
+                    lengthCode.description = 'total {}+{{1}} symbols'.format(
+                        (repeat-2<<2)+3)
+                    extra = self.verboseRead(lengthCode)
+            elif length==17:
+                #read, and show explanation
+                lengthCode.description = '{1}+3 unused'
+                extra = self.verboseRead(lengthCode)
+                #scan series of 17s (groups of zero counts)
+                #start with repeat count 2
+                repeat = 2
+                startSymbol = next(alphabetIter)
+                endSymbol = next(alphabetIter)
+                #note: loop will not end with total==32768,
+                #since total doesn't change here
+                while True:
+                    #determine last symbol
+                    oldRepeat = repeat
+                    repeat = (repeat-2<<3)+extra+3
+                    #read as many symbols as repeat increases
+                    for i in range(repeat-oldRepeat):
+                        endSymbol = next(alphabetIter)
+                    #see if there is more to do
+                    length = lengthCode.decodePeek(
+                        self.stream.peek(lengthCode.maxLength))[1].index
+                    if length!=17: break
+                    lengthCode.description = 'total {}+{{1}} unused'.format(
+                        (repeat-2<<3)+3)
+                    extra = self.verboseRead(lengthCode)
+            else:
+                symbol = next(alphabetIter)
+                #double braces for format
+                char = str(symbol)
+                if char in '{}': char *= 2
+                lengthCode.description = \
+                    'Length for {} is {{0.index}} bits'.format(char)
+                #output is not needed (will be 0)
+                self.verboseRead(lengthCode)
+                symbolLengths[symbol.index] = length
+                total += 32768>>length
+                lastLength = length
+        assert total==32768
+        alphabet.setLength(symbolLengths)
+        print('End of table. Prefix code '+alphabet.name+':')
+        alphabet.showCode()
+
+    #stream
+    def processStream(self):
+        """Process a brotli stream.
+        """
+        print('addr  hex{:{}s}binary context explanation'.format(
+            '', self.width-10))
+        print('Stream header'.center(60, '-'))
+        self.windowSize = self.verboseRead(WindowSizeAlphabet())
+        print('Metablock header'.center(60, '='))
+        self.ISLAST = False
+        self.output = bytearray()
+        while not self.ISLAST:
+            self.ISLAST = self.verboseRead(
+                BoolCode('LAST', description="Last block"))
+            if self.ISLAST:
+                if self.verboseRead(
+                    BoolCode('EMPTY', description="Empty block")): break
+            if self.metablockLength(): continue
+            if not self.ISLAST and self.uncompressed(): continue
+            print('Block type descriptors'.center(60, '-'))
+            self.numberOfBlockTypes = {}
+            self.currentBlockCounts = {}
+            self.blockTypeCodes = {}
+            self.blockCountCodes = {}
+            for blockType in (L,I,D): self.blockType(blockType)
+            print('Distance code parameters'.center(60, '-'))
+            self.NPOSTFIX, self.NDIRECT = self.verboseRead(DistanceParamAlphabet())
+            self.readLiteralContextModes()
+            print('Context maps'.center(60, '-'))
+            self.cmaps = {}
+            #keep the number of each kind of prefix tree for the last loop
+            numberOfTrees = {I: self.numberOfBlockTypes[I]}
+            for blockType in (L,D):
+                numberOfTrees[blockType] = self.contextMap(blockType)
+            print('Prefix code lists'.center(60, '-'))
+            self.prefixCodes = {}
+            for blockType in (L,I,D):
+                self.readPrefixArray(blockType, numberOfTrees[blockType])
+            self.metablock()
+
+    #metablock header
+    def verboseRead(self, alphabet, context='', skipExtra=False):
+        """Read symbol and extra from stream and explain what happens.
+        Returns the value of the symbol
+        >>> olleke.pos = 0
+        >>> l = Layout(olleke)
+        >>> l.verboseRead(WindowSizeAlphabet())
+        0000  1b                   1011 WSIZE   windowsize=(1<<22)-16=4194288
+        4194288
+        """
+        #TODO 2: verbosity level, e.g. show only codes and maps in header
+        stream = self.stream
+        pos = stream.pos
+        if skipExtra:
+            length, symbol = alphabet.readTuple(stream)
+            extraBits, extra = 0, None
+        else:
+            length, symbol, extraBits, extra = alphabet.readTupleAndExtra(
+                stream)
+        #fields: address, hex data, binary data, name of alphabet, explanation
+        hexdata = self.makeHexData(pos)
+        addressField = '{:04x}'.format(pos+7>>3) if hexdata else ''
+        bitdata = self.formatBitData(pos, length, extraBits)
+        #bitPtr moves bitdata so that the bytes are easier to read
+        #jump back to right if a new byte starts
+        if '|' in bitdata[1:]:
+            #start over on the right side
+            self.bitPtr = self.width
+        fillWidth = self.bitPtr-(len(hexdata)+len(bitdata))
+        if fillWidth<0: fillWidth = 0
+        print('{:<5s} {:<{}s} {:7s} {}'.format(
+            addressField,
+            hexdata+' '*fillWidth+bitdata, self.width,
+            context+alphabet.name,
+            symbol if skipExtra else symbol.explanation(extra),
+            ))
+        #jump to the right if we started with a '|'
+        #because we didn't jump before printing
+        if bitdata.startswith('|'): self.bitPtr = self.width
+        else: self.bitPtr -= len(bitdata)
+        return symbol if skipExtra else symbol.value(extra)
+
+    def metablockLength(self):
+        """Read MNIBBLES and meta block length;
+        if empty block, skip block and return true.
+        """
+        self.MLEN = self.verboseRead(MetablockLengthAlphabet())
+        if self.MLEN:
+            return False
+        #empty block; skip and return False
+        self.verboseRead(ReservedAlphabet())
+        MSKIP = self.verboseRead(SkipLengthAlphabet())
+        self.verboseRead(FillerAlphabet(streamPos=self.stream.pos))
+        self.stream.pos += 8*MSKIP
+        print("Skipping to {:x}".format(self.stream.pos>>3))
+        return True
+
+    def uncompressed(self):
+        """If true, handle uncompressed data
+        """
+        ISUNCOMPRESSED = self.verboseRead(
+            BoolCode('UNCMPR', description='Is uncompressed?'))
+        if ISUNCOMPRESSED:
+            self.verboseRead(FillerAlphabet(streamPos=self.stream.pos))
+            print('Uncompressed data:')
+            self.output += self.stream.readBytes(self.MLEN)
+            print(outputFormatter(self.output[-self.MLEN:]))
+        return ISUNCOMPRESSED
+
+    def blockType(self, kind):
+        """Read block type switch descriptor for given kind of blockType."""
+        NBLTYPES = self.verboseRead(TypeCountAlphabet(
+            'BT#'+kind[0].upper(),
+            description='{} block types'.format(kind),
+            ))
+        self.numberOfBlockTypes[kind] = NBLTYPES
+        if NBLTYPES>=2:
+            self.blockTypeCodes[kind] = self.readPrefixCode(
+                BlockTypeAlphabet('BT'+kind[0].upper(), NBLTYPES))
+            self.blockCountCodes[kind] = self.readPrefixCode(
+                BlockCountAlphabet('BC'+kind[0].upper()))
+            blockCount = self.verboseRead(self.blockCountCodes[kind])
+        else:
+            blockCount = 1<<24
+        self.currentBlockCounts[kind] = blockCount
+
+    def readLiteralContextModes(self):
+        """Read literal context modes.
+        LSB6: lower 6 bits of last char
+        MSB6: upper 6 bits of last char
+        UTF8: rougly dependent on categories:
+            upper 4 bits depend on category of last char:
+                control/whitespace/space/ punctuation/quote/%/open/close/
+                comma/period/=/digits/ VOWEL/CONSONANT/vowel/consonant
+            lower 2 bits depend on category of 2nd last char:
+                space/punctuation/digit or upper/lowercase
+        signed: hamming weight of last 2 chars
+        """
+        print('Context modes'.center(60, '-'))
+        self.literalContextModes = []
+        for i in range(self.numberOfBlockTypes[L]):
+            self.literalContextModes.append(
+                self.verboseRead(LiteralContextMode(number=i)))
+
+    def contextMap(self, kind):
+        """Read context maps
+        Returns the number of differnt values on the context map
+        (In other words, the number of prefix trees)
+        """
+        NTREES = self.verboseRead(TypeCountAlphabet(
+            kind[0].upper()+'T#',
+            description='{} prefix trees'.format(kind)))
+        mapSize = {L:64, D:4}[kind]
+        if NTREES<2:
+            self.cmaps[kind] = [0]*mapSize
+        else:
+            #read CMAPkind
+            RLEMAX = self.verboseRead(RLEmaxAlphabet(
+                'RLE#'+kind[0].upper(),
+                description=kind+' context map'))
+            alphabet = TreeAlphabet('CM'+kind[0].upper(), NTREES=NTREES, RLEMAX=RLEMAX)
+            cmapCode = self.readPrefixCode(alphabet)
+            tableSize = mapSize*self.numberOfBlockTypes[kind]
+            cmap = []
+            while len(cmap)<tableSize:
+                cmapCode.description = 'map {}, entry {}'.format(
+                    *divmod(len(cmap), mapSize))
+                count, value = self.verboseRead(cmapCode)
+                cmap.extend([value]*count)
+            assert len(cmap)==tableSize
+            IMTF = self.verboseRead(BoolCode('IMTF', description='Apply inverse MTF'))
+            if IMTF:
+                self.IMTF(cmap)
+            if kind==L:
+                print('Context maps for literal data:')
+                for i in range(0, len(cmap), 64):
+                    print(*(
+                        ''.join(map(str, cmap[j:j+8]))
+                        for j in range(i, i+64, 8)
+                        ))
+            else:
+                print('Context map for distances:')
+                print(*(
+                    ''.join(map('{:x}'.format, cmap[i:i+4]))
+                    for i in range(0, len(cmap), 4)
+                    ))
+            self.cmaps[kind] = cmap
+        return NTREES
+
+    @staticmethod
+    def IMTF(v):
+        """In place inverse move to front transform.
+        """
+        #mtf is initialized virtually with range(infinity)
+        mtf = []
+        for i, vi in enumerate(v):
+            #get old value from mtf. If never seen, take virtual value
+            try: value = mtf.pop(vi)
+            except IndexError: value = vi
+            #put value at front
+            mtf.insert(0, value)
+            #replace transformed value
+            v[i] = value
+
+    def readPrefixArray(self, kind, numberOfTrees):
+        """Read prefix code array"""
+        prefixes = []
+        for i in range(numberOfTrees):
+            if kind==L: alphabet = LiteralAlphabet(i)
+            elif kind==I: alphabet = InsertAndCopyAlphabet(i)
+            elif kind==D: alphabet = DistanceAlphabet(
+                i, NPOSTFIX=self.NPOSTFIX, NDIRECT=self.NDIRECT)
+            self.readPrefixCode(alphabet)
+            prefixes.append(alphabet)
+        self.prefixCodes[kind] = prefixes
+
+    #metablock data
+    def metablock(self):
+        """Process the data.
+        Relevant variables of self:
+        numberOfBlockTypes[kind]: number of block types
+        currentBlockTypes[kind]: current block types (=0)
+        literalContextModes: the context modes for the literal block types
+        currentBlockCounts[kind]: counters for block types
+        blockTypeCodes[kind]: code for block type
+        blockCountCodes[kind]: code for block count
+        cmaps[kind]: the context maps (not for I)
+        prefixCodes[kind][#]: the prefix codes
+        lastDistances: the last four distances
+        lastChars: the last two chars
+        output: the result
+        """
+        print('Meta block contents'.center(60, '='))
+        self.currentBlockTypes = {L:0, I:0, D:0, pL:1, pI:1, pD:1}
+        self.lastDistances = deque([17,16,11,4], maxlen=4)
+        #the current context mode is for block type 0
+        self.contextMode = ContextModeKeeper(self.literalContextModes[0])
+        wordList = WordList()
+
+        #setup distance callback function
+        def distanceCallback(symbol, extra):
+            "callback function for displaying decoded distance"
+            index, offset = symbol.value(extra)
+            if index:
+                #recent distance
+                distance = self.lastDistances[-index]+offset
+                return 'Distance: {}last{:+d}={}'.format(index, offset, distance)
+            #absolute value
+            if offset<=maxDistance:
+                return 'Absolute value: {} (pos {})'.format(offset, maxDistance-offset)
+            #word list value
+            action, word = divmod(offset-maxDistance, 1<<wordList.NDBITS[copyLen])
+            return '{}-{} gives word {},{} action {}'.format(
+                offset, maxDistance, copyLen, word, action)
+        for dpc in self.prefixCodes[D]: dpc.callback = distanceCallback
+
+        blockLen = 0
+        #there we go
+        while blockLen<self.MLEN:
+            #get insert&copy command
+            litLen, copyLen, dist0Flag = self.verboseRead(
+                self.prefixCodes[I][
+                    self.figureBlockType(I)])
+            #literal data
+            for i in range(litLen):
+                bt = self.figureBlockType(L)
+                cm = self.contextMode.getIndex()
+                ct = self.cmaps[L][bt<<6|cm]
+                char = self.verboseRead(
+                    self.prefixCodes[L][ct],
+                    context='{},{}='.format(bt,cm))
+                self.contextMode.add(char)
+                self.output.append(char)
+            blockLen += litLen
+            #check if we're done
+            if blockLen>=self.MLEN: return
+            #distance
+            #distances are computed relative to output length, at most window size
+            maxDistance = min(len(self.output), self.windowSize)
+            if dist0Flag:
+                distance = self.lastDistances[-1]
+            else:
+                bt = self.figureBlockType(D)
+                cm = {2:0, 3:1, 4:2}.get(copyLen, 3)
+                ct = self.cmaps[D][bt<<2|cm]
+                index, offset = self.verboseRead(
+                    self.prefixCodes[D][ct],
+                    context='{},{}='.format(bt,cm))
+                distance = self.lastDistances[-index]+offset if index else offset
+                if index==1 and offset==0:
+                    #to make sure distance is not put in last distance list
+                    dist0Flag = True
+            if distance<=maxDistance:
+                #copy from output
+                for i in range(
+                        maxDistance-distance,
+                        maxDistance-distance+copyLen):
+                    self.output.append(self.output[i])
+                if not dist0Flag: self.lastDistances.append(distance)
+                comment = 'Seen before'
+            else:
+                #fetch from wordlist
+                newWord = wordList.word(copyLen, distance-maxDistance-1)
+                self.output.extend(newWord)
+                #adjust copyLen to reflect actual new data
+                copyLen = len(newWord)
+                comment = 'From wordlist'
+            blockLen += copyLen
+            print(' '*40,
+                comment,
+                ': "',
+                outputFormatter(self.output[-copyLen:]),
+                '"',
+                sep='')
+            self.contextMode.add(self.output[-2])
+            self.contextMode.add(self.output[-1])
+
+    def figureBlockType(self, kind):
+        counts, types = self.currentBlockCounts, self.currentBlockTypes
+        if counts[kind]==0:
+            newType = self.verboseRead(self.blockTypeCodes[kind])
+            if newType==-2: newType = types['P'+kind]
+            elif newType==-1:
+                newType = (types[kind]+1)%self.numberOfBlockTypes[kind]
+            types['P'+kind] = types[kind]
+            types[kind] = newType
+            counts[kind] = self.verboseRead(self.blockCountCodes[kind])
+        counts[kind] -=1
+        return types[kind]
+
+__test__ = {
+'BitStream': """
+    >>> bs = BitStream(b'Jurjen')
+    >>> bs.readBytes(2)
+    b'Ju'
+    >>> bs.read(6) #r=01110010
+    50
+    >>> bs
+    BitStream(pos=2:6)
+    >>> bs.peek(5)  #j=01101010
+    9
+    >>> bs.readBytes(2)
+    Traceback (most recent call last):
+        ...
+    ValueError: readBytes: need byte boundary
+    """,
+
+'Symbol': """
+    >>> a=Symbol(MetablockLengthAlphabet(),5)
+    >>> len(a)
+    2
+    >>> int(a)
+    5
+    >>> a.bitPattern()
+    '01'
+    >>> a.value(200000)
+    200001
+    >>> a.explanation(300000)
+    'data length: 493e0h+1=300001'
+    """,
+
+'RangeDecoder': """
+    >>> a=RangeDecoder(bitLength=3)
+    >>> len(a)
+    8
+    >>> a.name='t'
+    >>> list(a)
+    [Symbol(t, 0), Symbol(t, 1), Symbol(t, 2), Symbol(t, 3), Symbol(t, 4), Symbol(t, 5), Symbol(t, 6), Symbol(t, 7)]
+    >>> a[2]
+    Symbol(t, 2)
+    >>> a.bitPattern(4)
+    '100'
+    >>> a.length(2)
+    3
+    >>> a.decodePeek(15)
+    (3, Symbol(t, 7))
+    >>>
+
+    """,
+
+'PrefixDecoder': """
+    >>> a=PrefixDecoder(decodeTable={0:1,1:2,3:3,7:4})
+    >>> len(a)
+    4
+    >>> a.name='t'
+    >>> list(a)
+    [Symbol(t, 1), Symbol(t, 2), Symbol(t, 3), Symbol(t, 4)]
+    >>> a.decodePeek(22)
+    (1, Symbol(t, 1))
+    >>> a.decodePeek(27)
+    (3, Symbol(t, 3))
+    >>> a.length(1)
+    1
+    >>> a.length(4)
+    3
+    """,
+
+'Code': """
+    >>> a=Code('t',alphabetSize=10)
+    >>> len(a)
+    10
+    >>> a.showCode()
+    0000:0 0001:1 0010:2 0011:3 0100:4 0101:5 0110:6 0111:7 1000:8 1001:9
+    >>> a.setLength({2:1,3:2,5:3,6:3})
+    >>> a.showCode()
+      0:2  01:3 011:5 111:6
+    >>> len(a)
+    4
+    >>> def callback(i): return 'call{}back'.format(i)
+    >>> a=Code('t',callback=callback,bitLength=3)
+    >>> a[6].explanation()
+    'call6back'
+    """,
+
+'WithExtra': """
+    >>> class A(WithExtra):
+    ...    extraTable = [0,1,1,2,2]
+    >>> a=A('t',alphabetSize=5)
+    >>> a[1]
+    Symbol(t, 1)
+    >>> a.extraBits(2)
+    1
+    >>> a.mnemonic(4)
+    '4'
+    >>> a.readTupleAndExtra(BitStream(b'\x5b'))
+    (3, Symbol(t, 3), 2, 3)
+    """,
+
+'BoolCode': """
+    >>> BoolCode('test')[0].explanation()
+    '0: False'
+    """,
+
+'Enumerator': """
+    >>> class A(Enumerator):
+    ...    extraTable = [0,1,1,2,2]
+    ...    value0=3
+    >>> a=A(alphabetLength=5)
+    >>> a.value(3)
+    Traceback (most recent call last):
+        ...
+    TypeError: value() missing 1 required positional argument: 'extra'
+    >>> a.explanation(3,4)
+    'xx 011: 8-11; 8+4=12'
+    """,
+
+'WindowSizeAlphabet': """
+    >>> windowSizeAlphabet = WindowSizeAlphabet()
+    >>> windowSizeAlphabet[0]
+    Traceback (most recent call last):
+        ...
+    ValueError: No symbol WindowSizeAlphabet[0]
+    >>> len(windowSizeAlphabet)
+    16
+    >>> windowSizeAlphabet[21]
+    Symbol(WSIZE, 21)
+    >>> windowSizeAlphabet[21].bitPattern()
+    '1001'
+    >>> windowSizeAlphabet[21].extraBits()
+    0
+    >>> windowSizeAlphabet[21].index
+    21
+    >>> windowSizeAlphabet[10].value()
+    1008
+    >>> windowSizeAlphabet[10].explanation()
+    'windowsize=(1<<10)-16=1008'
+    >>> windowSizeAlphabet.showCode()
+          0:65520    1100001:16368    1110001:32752       0011:262128
+    0000001:131056   0010001:None        1001:2097136     1011:4194288
+    1000001:4080     1010001:8176        0101:524272      0111:1048560
+    0100001:1008     0110001:2032        1101:8388592     1111:16777200
+    """,
+
+'TypeCountAlphabet': """
+    >>> typeCountAlphabet = TypeCountAlphabet(description='bananas')
+    >>> len(typeCountAlphabet)
+    9
+    >>> typeCountAlphabet[3]
+    Symbol(BT#, 3)
+    >>> typeCountAlphabet[9]
+    Traceback (most recent call last):
+        ...
+    ValueError: No symbol TypeCountAlphabet[9]
+    >>> print(typeCountAlphabet[3])
+    xx,0101
+    >>> typeCountAlphabet[8].value(127)
+    256
+    >>> typeCountAlphabet[4].explanation(2)
+    'xxx,0111: 11 bananas'
+    >>> typeCountAlphabet[0].explanation()
+    '0: 1 banana'
+    """,
+
+'DistanceParamAlphabet': """
+    >>> dpa = DistanceParamAlphabet()
+    >>> dpa.showCode()
+    00:PF0 01:PF1 10:PF2 11:PF3
+    >>> dpa.readTupleAndExtra(BitStream(b'\\x29'))
+    (2, Symbol(DIST, 1), 4, 10)
+    >>> dpa.explanation(2, 5)
+    '2 postfix bits and 0101<<2=20 direct codes'
+    """,
+
+'LiteralAlphabet': """
+    >>> LiteralAlphabet(-1).showCode()   #doctest: +ELLIPSIS
+    00000000:\\x00 00110100:4    01101000:h    10011100:\\x9c 11010000:\\xd0
+    00000001:\\x01 00110101:5    01101001:i    10011101:\\x9d 11010001:\\xd1
+    00000010:\\x02 00110110:6    01101010:j    10011110:\\x9e 11010010:\\xd2
+    ...
+    00101111:/    01100011:c    10010111:\\x97 11001011:\\xcb 11111111:\\xff
+    00110000:0    01100100:d    10011000:\\x98 11001100:\\xcc
+    00110001:1    01100101:e    10011001:\\x99 11001101:\\xcd
+    00110010:2    01100110:f    10011010:\\x9a 11001110:\\xce
+    00110011:3    01100111:g    10011011:\\x9b 11001111:\\xcf
+    """,
+
+'BlockCountAlphabet': """
+    >>> bc=BlockCountAlphabet('BCL')
+    >>> len(bc)
+    26
+    >>> bs=BitStream(b'\\x40\\x83\\xc8\\x59\\12\\x02')
+    >>> x = bc.readTupleAndExtra(bs); x[1].explanation(x[3])
+    'Block count: xx 00000: 1-4; 1+2=3'
+    >>> x = bc.readTupleAndExtra(bs); x[1].explanation(x[3])
+    'Block count: xxx 00110: 33-40; 33+0=33'
+    >>> x = bc.readTupleAndExtra(bs); x[1].explanation(x[3])
+    'Block count: xxxxxx 10001: 305-368; 305+28=333'
+    >>> x = bc.readTupleAndExtra(bs); x[1].explanation(x[3])
+    'Block count: xxxxxxxxxxx 10110: 2289-4336; 2289+1044=3333'
+    """,
+
+'Layout': """
+    >>> olleke.pos = 0
+    >>> l = Layout(olleke)
+    >>> l.verboseRead(WindowSizeAlphabet())
+    0000  1b                   1011 WSIZE   windowsize=(1<<22)-16=4194288
+    4194288
+    >>> l.verboseRead(BoolCode('LAST', description="Last block"))
+                              1     LAST    Last block: 1: True
+    True
+    >>> l.verboseRead(BoolCode('EMPTY', description="Empty block"))
+                             0      EMPTY   Empty block: 0: False
+    False
+    >>> l.verboseRead(MetablockLengthAlphabet())
+    0001  2e 00        |00h|2Eh,|00 MLEN    data length: 002eh+1=47
+    47
+    >>> olleke.pos = 76
+    >>> l = Layout(olleke)
+    >>> x = l.verboseRead(DistanceAlphabet(0,NPOSTFIX=0,NDIRECT=0), skipExtra=True)
+    000a  82                10|1100 D0      10[15*x]-3
+    >>> x.explanation(0x86a3)
+    '10[1000011010100011]-3: [0]+100000'
+    """,
+
+'olleke': """
+    >>> olleke.pos = 0
+    >>> try: Layout(olleke).processStream()
+    ... except NotImplementedError: pass
+    ... #doctest: +REPORT_NDIFF
+    addr  hex               binary context explanation
+    -----------------------Stream header------------------------
+    0000  1b                   1011 WSIZE   windowsize=(1<<22)-16=4194288
+    ======================Metablock header======================
+                              1     LAST    Last block: 1: True
+                             0      EMPTY   Empty block: 0: False
+    0001  2e 00        |00h|2Eh,|00 MLEN    data length: 002eh+1=47
+    -------------------Block type descriptors-------------------
+    0003  00                      0 BT#L    0: 1 literal block type
+                                 0  BT#I    0: 1 insert&copy block type
+                                0   BT#D    0: 1 distance block type
+    ------------------Distance code parameters------------------
+    0004  44               0|000,00 DIST    0 postfix bits and 0000<<0=0 direct codes
+    -----------------------Context modes------------------------
+                         10         LC0     Context mode for type 0: 2(UTF8)
+    ------------------------Context maps------------------------
+                        0           LT#     0: 1 literal prefix tree
+                       0            DT#     0: 1 distance prefix tree
+    ---------------------Prefix code lists----------------------
+                     10             PFX     L0 is complex with lengths 3,4,0,5,17...
+    0005  4f                    1|0 ##L0    len 3: coded with 3 bits
+                            0111    ##L0    len 4: coded with 1 bits
+                          10        ##L0    unused: coded with 3 bits
+    0006  d6                    0|0 ##L0    len 5: skipped
+                             011    ##L0    zero xxx: coded with 2 bits
+    ***** Lengths for L0 will be coded as:
+      0:len 4     01:zero xxx 011:unused   111:len 3
+    0007  95                1|11,01 #L0     7+3 unused
+                           0        #L0     Length for \\n is 4 bits
+                     001,01         #L0     1+3 unused
+    0008  44                010,0|1 #L0     total 19+2 unused
+                           0        #L0     Length for " " is 4 bits
+                          0         #L0     Length for ! is 4 bits
+    0009  cb                011,|01 #L0     3+3 unused
+                     |110,01        #L0     total 35+6 unused
+    000a  82                      0 #L0     Length for K is 4 bits
+                            000,01  #L0     0+3 unused
+                           0        #L0     Length for O is 4 bits
+    000b  4d                   01|1 #L0     symbol P unused
+                            011     #L0     symbol Q unused
+                           0        #L0     Length for R is 4 bits
+    000c  88                000,|01 #L0     0+3 unused
+                     |100,01        #L0     total 11+4 unused
+    000d  b6                      0 #L0     Length for b is 4 bits
+                               011  #L0     symbol c unused
+                            011     #L0     symbol d unused
+    000e  27                   11|1 #L0     Length for e is 3 bits
+                         010,01     #L0     2+3 unused
+                       |0           #L0     Length for k is 4 bits
+    000f  1f                    111 #L0     Length for l is 3 bits
+                             011    #L0     symbol m unused
+                            0       #L0     Length for n is 4 bits
+                          |0        #L0     Length for o is 4 bits
+    0010  c1                 000,01 #L0     0+3 unused
+                            0       #L0     Length for s is 4 bits
+    0011  b4                   0|11 #L0     symbol t unused
+                              0     #L0     Length for u is 4 bits
+    End of table. Prefix code L0:
+     000:e   0010:\\n  0110:!   0001:O   0101:b   0011:n   0111:s
+     100:l   1010:" " 1110:K   1001:R   1101:k   1011:o   1111:u
+                         11,01      PFX     IC0 is simple with 4 code words
+    0012  2a                |2Ah|10 IC0     ? bits: I5C4
+    0013  b5 ec              00|B5h IC0     ? bits: I6+xC7
+    0015  22            0010|111011 IC0     ? bits: I8+xC5
+    0016  8c            001100|0010 IC0     ? bits: I0C14+xx
+                       0            SHAPE   False: lengths 2,2,2,2
+    0017  74                 10,0|1 PFX     D0 is simple with 3 code words
+    0018  a6                0|01110 D0      1 bit: 2last-3
+                      010011        D0      2 bits: 11xx-3
+    0019  aa                01010|1 D0      2 bits: 11xxx-3
+    ====================Meta block contents=====================
+                       |1,01        IC0     Literal: 9, copy: 5
+    001a  41                   0001 0,0=L0  O
+                            100     0,48=L0 l
+    001b  a2                   10|0 0,62=L0 l
+                            000     0,63=L0 e
+    001c  a1                  1|101 0,59=L0 k
+                           000      0,63=L0 e
+                      |1010         0,59=L0 " "
+    001d  b5                   0101 0,11=L0 b
+                          |1011     0,60=L0 o
+    001e  24                      0 0,3=D0  Distance: 2last-3=8
+                                            Seen before: "lleke"
+                              0,10  IC0     Literal: 6, copy: 7
+                         |0010      0,59=L0 \\n
+    001f  89                   1001 0,7=L0  R
+                            000     0,52=L0 e
+    0020  fa                  010|1 0,58=L0 b
+                          1111      0,63=L0 u
+    0021  eb                  011|1 0,59=L0 s
+                         11,01      0,3=D0  Absolute value: 12 (pos 8)
+                                            Seen before: "olleke\\n"
+    0022  db                 01,1|1 IC0     Literal: 0, copy: 15
+                      |110,11       0,3=D0  Absolute value: 27 (pos 0)
+                                            Seen before: "Olleke bolleke\\n"
+    0023  f8                     00 IC0     Literal: 5, copy: 4
+                             1110   0,7=L0  K
+    0024  2c                  00|11 0,52=L0 n
+                          1011      0,62=L0 o
+    0025  0d                   1|00 0,59=L0 l
+                           0110     0,63=L0 !
+    """,
+
+'file': """
+    >>> try: Layout(BitStream(
+    ... open("H:/Downloads/brotli-master/tests/testdata/10x10y.compressed",'rb')
+    ...     .read())).processStream()
+    ... except NotImplementedError: pass
+    addr  hex               binary context explanation
+    -----------------------Stream header------------------------
+    0000  1b                   1011 WSIZE   windowsize=(1<<22)-16=4194288
+    ======================Metablock header======================
+                              1     LAST    Last block: 1: True
+                             0      EMPTY   Empty block: 0: False
+    0001  13 00        |00h|13h,|00 MLEN    data length: 0013h+1=20
+    -------------------Block type descriptors-------------------
+    0003  00                      0 BT#L    0: 1 literal block type
+                                 0  BT#I    0: 1 insert&copy block type
+                                0   BT#D    0: 1 distance block type
+    ------------------Distance code parameters------------------
+    0004  a4               0|000,00 DIST    0 postfix bits and 0000<<0=0 direct codes
+    -----------------------Context modes------------------------
+                         10         LC0     Context mode for type 0: 2(UTF8)
+    ------------------------Context maps------------------------
+                        0           LT#     0: 1 literal prefix tree
+                       0            DT#     0: 1 distance prefix tree
+    ---------------------Prefix code lists----------------------
+    0005  b0                 0|1,01 PFX     L0 is simple with 2 code words
+    0006  b2              0|1011000 L0      1 bit: X
+    0007  ea              0|1011001 L0      1 bit: Y
+                     01,01          PFX     IC0 is simple with 2 code words
+    0008  81            0000001|111 IC0     1 bit: I1C9&D=0
+    0009  47 02             0|47h|1 IC0     1 bit: I1C9
+                       00,01        PFX     D0 is simple with 1 code word
+    000b  8a                010|000 D0      0 bits: 10x-3
+    ====================Meta block contents=====================
+                           1        IC0     Literal: 1, copy: 9
+                          0         0,0=L0  X
+                      0,()          0,3=D0  Absolute value: 1 (pos 0)
+                                            Seen before: "XXXXXXXXX"
+                     0              IC0     Literal: 1, copy: 9, same distance
+                   |1               0,54=L0 Y
+                                            Seen before: "YYYYYYYYY"
+    """,
+
+'XY': """
+    >>> try: Layout(BitStream(brotli.compress('X'*10+'Y'*10))).processStream()
+    ... except NotImplementedError: pass
+    addr  hex               binary context explanation
+    -----------------------Stream header------------------------
+    0000  1b                   1011 WSIZE   windowsize=(1<<22)-16=4194288
+    ======================Metablock header======================
+                              1     LAST    Last block: 1: True
+                             0      EMPTY   Empty block: 0: False
+    0001  13 00        |00h|13h,|00 MLEN    data length: 0013h+1=20
+    -------------------Block type descriptors-------------------
+    0003  00                      0 BT#L    0: 1 literal block type
+                                 0  BT#I    0: 1 insert&copy block type
+                                0   BT#D    0: 1 distance block type
+    ------------------Distance code parameters------------------
+    0004  a4               0|000,00 DIST    0 postfix bits and 0000<<0=0 direct codes
+    -----------------------Context modes------------------------
+                         10         LC0     Context mode for type 0: 2(UTF8)
+    ------------------------Context maps------------------------
+                        0           LT#     0: 1 literal prefix tree
+                       0            DT#     0: 1 distance prefix tree
+    ---------------------Prefix code lists----------------------
+    0005  b0                 0|1,01 PFX     L0 is simple with 2 code words
+    0006  b2              0|1011000 L0      1 bit: X
+    0007  82              0|1011001 L0      1 bit: Y
+                     00,01          PFX     IC0 is simple with 1 code word
+    0008  84            0000100|100 IC0     0 bits: I4C6&D=0
+    0009  00                 00,0|1 PFX     D0 is simple with 1 code word
+    000a  e0                0|00000 D0      0 bits: last
+    ====================Meta block contents=====================
+                          ()        IC0     Literal: 4, copy: 6, same distance
+                         0          0,0=L0  X
+                        0           0,52=L0 X
+                       0            0,54=L0 X
+                      0             0,54=L0 X
+                                            Seen before: "XXXXXX"
+                    ()              IC0     Literal: 4, copy: 6, same distance
+                   1                0,54=L0 Y
+                  1                 0,54=L0 Y
+                |1                  0,54=L0 Y
+    000b  01                      1 0,54=L0 Y
+                                            Seen before: "YYYYYY"
+    """,
+
+'empty': """
+    >>> try: Layout(BitStream(b'\\x81\\x16\\x00\\x58')).processStream()
+    ... except NotImplementedError: pass
+    addr  hex               binary context explanation
+    -----------------------Stream header------------------------
+    0000  81                0000001 WSIZE   windowsize=(1<<17)-16=131056
+    ======================Metablock header======================
+                          |1        LAST    Last block: 1: True
+    0001  16                      0 EMPTY   Empty block: 0: False
+                                11  MLEN    11: empty block
+                               0    RSVD    Reserved (must be zero)
+    0002  00           000000|00,01 SKIP    skip length: 0h+1=1
+                    |00             SKIP    2 bits ignored
+    Skipping to 4
+    """,
+
+}
+
+if __name__=='__main__':
+    import sys
+    if len(sys.argv)>1:
+        l = Layout(BitStream(open(sys.argv[1],'rb').read()))
+        l.processStream()
+    else:
+        sys.path.append("h:/Persoonlijk/bin")
+        try:
+            import brotli
+            open('brotlidump.br', 'wb').write(
+                brotli.compress(
+                    open('brotlidump.py', 'r').read()
+                ))
+            olleke = BitStream(brotli.compress(
+                'Olleke bolleke\nRebusolleke\nOlleke bolleke\nKnol!'))
+        except ImportError: pass
+        import doctest
+        doctest.testmod(optionflags=doctest.REPORT_NDIFF
+            #|doctest.FAIL_FAST
+            )
-- 
cgit v1.1