#!/usr/bin/env python3

#
# ハフマン符号の生成
#
class Huffman:

    # 生成される符号
    class Code:
        def __init__(self, code, length, literal, freq):
            self.code = code
            self.length = length
            self.literal = literal
            self.freq = freq
            self.set_binary()
            self.set_char()

        def set_binary(self):
            self.binary = ('{0:0%sb}' % self.length).format(self.code)

        def set_char(self):
            c = chr(self.literal)
            if c.isprintable():
                self.char = '\'%s\'' % c
            else:
                self.char = '%#x' % self.literal

        def key_code(self): return self.code
        def key_length(self): return self.length
        def key_length_literal(self): return (self.length, self.literal)
        def key_literal(self): return self.literal
        def key_freq_literal(self): return (self.freq, self.literal)
        def key_binary(self): return self.binary


    # 葉(Leaf)または節(Node)となる要素
    class Element:
        def __init__(self, freq, literal, branch):
            self.freq = freq
            self.literal = literal
            self.branch = branch

        def key_freq_literal(self):
            return (self.freq, self.literal)


    # 葉 情報
    class Leaf(Element):
        def __init__(self, freq, literal):
            super().__init__(freq, literal, None)


    # 節 情報
    class Node(Element):
        def __init__(self, freq, branch):
            super().__init__(freq, 0, branch)


    # 木の生成
    @staticmethod
    def build_tree(data):
        tree = []

        # 葉の一覧を作る
        for literal in range(min(data), max(data) + 1):
            freq = data.count(literal)
            if freq != 0:
                tree.append(Huffman.Leaf(freq, literal))

        # 木を作る
        while len(tree) > 1:
            # 頻度,文字の優先順位でソート
            tree = sorted(tree, key=Huffman.Element.key_freq_literal)

            # 頻度の下位2つを、１つの節にまとめる
            branch = tree[:2]
            tree = tree[2:]
            freq = branch[0].freq + branch[1].freq
            tree.append(Huffman.Node(freq, branch))

        return tree[0]


    # 辞書の生成
    @staticmethod
    def make_dictionary(top):
        dictionary = []
        nodes = [(top, 0, 0)]
        while len(nodes) != 0:
            elem, code, length = nodes.pop()
            if elem.branch is None:
                dictionary.append(Huffman.Code(code, length, elem.literal, elem.freq))
                continue
            nodes.append((elem.branch[0], code * 2 + 0, length + 1))
            nodes.append((elem.branch[1], code * 2 + 1, length + 1))
        return sorted(dictionary, key=Huffman.Code.key_literal)


    # RFC 1951: DEFLATE 形式に変換
    @staticmethod
    def to_deflate(dictionary):
        dictionary = sorted(dictionary, key=Huffman.Code.key_literal)

        length_min = min(dictionary, key=Huffman.Code.key_length).length
        length_max = max(dictionary, key=Huffman.Code.key_length).length
        length_size = length_max + 1

        length_count = [0] * length_size
        for code in dictionary:
            length_count[code.length] += 1

        code = 0
        length_code = [0] * length_size
        for n in range(length_max+1):
            code <<= 1
            length_code[n] = code
            code += length_count[n]

        for code in dictionary:
            code.code = length_code[code.length]
            code.set_binary()
            length_code[code.length] += 1


    #
    # Huffman クラスの初期化
    #
    def __init__(self, data, deflate=False):
        self.tree = Huffman.build_tree(data)
        self.dictionary = Huffman.make_dictionary(self.tree)
        if deflate:
            Huffman.to_deflate(self.dictionary)


    # 統計情報の取得
    def statistics(huff):
        length = 0
        freq = 0
        max_code = 0
        max_length = 0
        max_literal = 0
        max_char = 0
        max_freq = 0
        max_binary = 0
        for code in huff.dictionary:
            c = code.code
            b = code.length
            l = code.literal
            s = len(code.char)
            w = code.freq
            p = len(code.binary)

            max_code = max(c, max_code)
            max_length = max(b, max_length)
            max_literal = max(l, max_literal)
            max_char = max(s, max_char)
            max_freq = max(w, max_freq)
            max_binary = max(p, max_binary)

            length += (b * w)
            freq += w

        return {
            'total': {
                'length': length,
                'freq': freq,
            },
            'max': {
                'code': max_code,
                'length': max_length,
                'literal': max_literal,
                'char': max_char,
                'freq': max_freq,
                'binary': max_binary,
            },
        }


#
# コマンド ラインから呼び出し
#
if __name__ == '__main__':
    def main():
        import sys
        import codecs
        import argparse

        #
        # コマンド ライン引数の解析
        #
        parser = argparse.ArgumentParser(description='データからハフマン符号を生成します')
        parser.add_argument('-T', '--text', help='入力文字列 (FILE は無視される)')
        parser.add_argument('-SF', '--sort-freq', action='store_true', help='頻度でソート')
        parser.add_argument('-SL', '--sort-literal', action='store_true', help='文字(値)でソート')
        parser.add_argument('-SB', '--sort-length', action='store_true', help='符号長でソート')
        parser.add_argument('-SC', '--sort-code-be', action='store_true', help='符号(左詰)でソート [デフォルト]')
        parser.add_argument('-Sc', '--sort-code-le', action='store_true', help='符号(右詰)でソート')
        parser.add_argument('-p', '--padding', metavar='CHAR', help='符号に CHAR 文字を追加')
        parser.add_argument('-r', '--reverse', action='store_true', help='降順でソート')
        parser.add_argument('-D', '--deflate', action='store_true', help='DEFLATE 形式の辞書にする')
        parser.add_argument('-DL', '--deflate-literal', action='store_true',
                            help='RFC 1951 literal/length 固定辞書モード (FILE は無視される)')
        parser.add_argument('-DD', '--deflate-distance', action='store_true',
                            help='RFC 1951 の distance 固定辞書モード (FILE は無視される)')
        parser.add_argument('-F', '--format', metavar='STR', help='出力形式を指定')
        parser.add_argument('-N', '--no-total', action='store_true', help='合計の出力を抑制する')
        parser.add_argument('FILE', nargs='?')
        args = parser.parse_args()

        # 出力形式：
        #   %B: 符号長
        #   %C: 符号（10進数）
        #   %P: 符号（左詰：2進数）
        #   %p: 符号（右詰：2進数）
        #   %L: 文字
        #   %D: 文字の値(10進数)
        #   %X: 文字の値(16進数大文字)
        #   %x: 文字の値(16進数小文字)
        #   %F: 頻度

        line_format = args.format
        if line_format is None:
            if args.deflate_literal:
                line_format = '%D=0x%X %B:%P'
            elif args.deflate_distance:
                line_format = '%D %B:%P'
            else:
                line_format = '%L (%D=0x%X)[%F] %B:%P'

        #
        # ソート方法の設定
        #
        if args.sort_freq:
            sort_key = Huffman.Code.key_freq_literal
        elif args.sort_literal:
            sort_key = Huffman.Code.key_literal
        elif args.sort_length:
            sort_key = Huffman.Code.key_length_literal
        elif args.sort_code_be:
            sort_key = Huffman.Code.key_code
        else:  # if args.sort_binary: # default
            sort_key = Huffman.Code.key_binary

        #
        # データの読み込みとハフマン符号の作成
        #
        flag_deflate = args.deflate
        flag_total = not args.no_total
        if args.deflate_literal:
            # RFC 1951 literal/length 固定辞書用
            flag_deflate = True
            flag_total = False
            data = []
            for n in range(144):
                data += [(n + 0)] * 2
            for n in range(112):
                data += [(n + 144)] * 1
            for n in range(24):
                data += [(n + 256)] * 4
            for n in range(8):
                data += [(n + 280)] * 2
        elif args.deflate_distance:
            # RFC 1951 distance 固定辞書用
            flag_deflate = True
            flag_total = False
            data = [n for n in range(32)]
        elif args.text:
            data = codecs.encode(args.text)
        else:
            if args.FILE is None:
                parser.print_help()
                return
            if args.FILE == '-':
                data = codecs.encode(sys.stdin.read())
            else:
                data = open(args.FILE, 'rb').read()
        huff = Huffman(data, flag_deflate)

        #
        # 結果の出力
        #
        dinf = huff.statistics()

        clen = len('%d' % dinf['max']['code'])
        dlen = len('%d' % dinf['max']['literal'])
        xlen = len('%x' % dinf['max']['literal'])
        slen = dinf['max']['char']
        flen = len('%d' % dinf['max']['freq'])
        blen = len('%d' % dinf['max']['length'])
        plen = dinf['max']['binary']

        fmtstr_dict = {
            'C': '{0:%dd}' % clen,
            'B': '{1:%dd}' % blen,
            'D': '{2:%dd}' % dlen,
            'X': '{2:0%dX}' % xlen,
            'x': '{2:0%dx}' % xlen,
            'F': '{3:%dd}' % flen,
            'P': '{4:<%ds}' % plen,
            'p': '{4:>%ds}' % plen,
            'L': '{5:<%ds}' % slen,
        }

        # 出力形式の解析
        fmtstr = ''
        prefix = False
        for c in line_format:
            if not prefix:
                if c != '%':
                    fmtstr += c
                    continue
                prefix = True
                continue

            prefix = False
            if c in fmtstr_dict:
                fmtstr += fmtstr_dict[c]
                continue
            fmtstr += c

        # 辞書の出力
        squote = '\''
        pchar = args.padding and args.padding[0] or ' '
        for code in sorted(huff.dictionary, key=sort_key, reverse=args.reverse):
            binary = code.binary
            if args.padding:
                binary += (pchar * (plen - len(binary)))
            pass
            print(fmtstr.format(code.code, code.length, code.literal, code.freq, binary, code.char))

        # 合計の出力
        if flag_total:
            total = dinf['total']
            freq = total['freq']
            print('入力: %d バイト (%d ビット)' % (freq, freq * 8))
            print('符号: %d バイト (%d ビット)' % ((total['length'] + 7) >> 3, total['length']))


    main()

#!/usr/bin/env python3

# 辞書
dictionary = (
    (' ', '1110'),
    ('a', '100'),
    ('c', '10100'),
    ('d', '1111'),
    ('e', '000'),
    ('f', '001'),
    ('h', '10101'),
    ('m', '010'),
    ('n', '10110'),
    ('o', '10111'),
    ('p', '11000'),
    ('r', '11001'),
    ('s', '011'),
    ('t', '11010'),
    ('u', '11011'),
)

# 事前準備
code_length_min = min((len(d[1]) for d in dictionary))
code_length_max = max((len(d[1]) for d in dictionary))
code_length_range = range(code_length_min, code_length_max + 1)
code_literal_dict = {code: literal for literal, code in dictionary}
literal_code_dict = {literal: code for literal, code in dictionary}


# 復号
def decode(data):
    output = ''
    while len(data):
        for length in code_length_range:
            code = data[:length]
            if code in code_literal_dict:
                output += code_literal_dict[code]
                data = data[length:]
                break
        else:
            raise Exception('バグってる')
    return output


# 符号化
def encode(data):
    return ''.join(literal_code_dict[literal] for literal in data)


# 例
data = 'huffman compressed data'

# 符号化と復号
enc_data = encode(data)
dec_data = decode(enc_data)

print('文字列: \'%s\'' % data)
print('符号化 %d ビット: %s' % (len(enc_data), enc_data))
print('復号　 %d バイト: \'%s\'' % (len(dec_data), dec_data))
print('検証:', data == dec_data and '正常' or '異常')

#!/usr/bin/env python3

# 「文字と符号長」の一覧から辞書を作る
def make_dictionary(lengths):
    if type(lengths) == dict:
        literals = tuple(literal for literal in lengths)
        lengths = [lengths[literal] for literal in lengths]
    else:
        literals = range(len(lengths))

    def gen_length_code():
        yield 0
        code = 0
        for length in range(1, max(lengths) + 1):
            yield code
            code = (code + lengths.count(length)) << 1

    def gen_dictionary(length_code):
        for index in range(len(lengths)):
            literal = literals[index]
            length = lengths[index]
            code = length_code[length] if length != 0 else None
            length_code[length] += 1
            yield (literal, code, length)

    return (*gen_dictionary([*gen_length_code()]),)


# 辞書の表示
def dump_dictionary(dictionary, fmtstr=None):
    if not fmtstr:
        fmtstr = '\'{0}\' {1:d}:{2}'
    for literal, code, length in dictionary:
        if length != 0:
            binary = ('{0:0%db}' % length).format(code)
            print(fmtstr.format(literal, length, binary))


if __name__ == '__main__':

    print('文字列例の辞書')
    dump_dictionary(make_dictionary({
        ' ': 4, 'a': 3, 'c': 5, 'd': 4, 'e': 3,
        'f': 3, 'h': 5, 'm': 3, 'n': 5, 'o': 5,
        'p': 5, 'r': 5, 's': 3, 't': 5, 'u': 5,
    }))
    print()

    print('符号長の辞書')
    dump_dictionary(make_dictionary((
        0, 0, 0, 2, 2, 1
    )))

文字列例の辞書
' ' 4:1010
'a' 3:000
'c' 5:11000
'd' 4:1011
'e' 3:001
'f' 3:010
'h' 5:11001
'm' 3:011
'n' 5:11010
'o' 5:11011
'p' 5:11100
'r' 5:11101
's' 3:100
't' 5:11110
'u' 5:11111

符号長の辞書
'3' 2:10
'4' 2:11
'5' 1:0

#!/usr/bin/env python3

def make_dictionary(lengths):
    def gen_length_code():
        code = 0
        for length in range(max(lengths) + 1):
            yield code
            code = (code + lengths.count(length)) << 1

    def gen_dictionary(length_code):
        for length in lengths:
            yield (length_code[length], length)
            length_code[length] += 1

    return (*gen_dictionary([*gen_length_code()]),)


def dump_dictionary(dictionary, fmtstr=None):
    if fmtstr is None:
        fmtstr = '{0:3} {1:d}:{2}'
    for literal in range(len(dictionary)):
        code, length = dictionary[literal]
        binary = ('{0:0%db}' % length).format(code)
        print(fmtstr.format(literal, length, binary))
    print()


print('文字（値）の固定辞書')
dump_dictionary(make_dictionary(
    [8]*(144-0) + [9]*(256-144) + [7]*(280-256) + [8]*(288-280)
))

print('前方距離コード用固定辞書')
dump_dictionary(make_dictionary([5]*32))

文字（値）の固定辞書
  0 8:00110000
  1 8:00110001
  2 8:00110010
  3 8:00110011
  4 8:00110100
  5 8:00110101
  6 8:00110110
  7 8:00110111
  8 8:00111000
  9 8:00111001
 10 8:00111010
 11 8:00111011
 12 8:00111100
 13 8:00111101
 14 8:00111110
 15 8:00111111
 16 8:01000000
 17 8:01000001
 18 8:01000010
 19 8:01000011
 20 8:01000100
 21 8:01000101
 22 8:01000110
 23 8:01000111
 24 8:01001000
 25 8:01001001
 26 8:01001010
 27 8:01001011
 28 8:01001100
 29 8:01001101
 30 8:01001110
 31 8:01001111
 32 8:01010000
 33 8:01010001
 34 8:01010010
 35 8:01010011
 36 8:01010100
 37 8:01010101
 38 8:01010110
 39 8:01010111
 40 8:01011000
 41 8:01011001
 42 8:01011010
 43 8:01011011
 44 8:01011100
 45 8:01011101
 46 8:01011110
 47 8:01011111
 48 8:01100000
 49 8:01100001
 50 8:01100010
 51 8:01100011
 52 8:01100100
 53 8:01100101
 54 8:01100110
 55 8:01100111
 56 8:01101000
 57 8:01101001
 58 8:01101010
 59 8:01101011
 60 8:01101100
 61 8:01101101
 62 8:01101110
 63 8:01101111
 64 8:01110000
 65 8:01110001
 66 8:01110010
 67 8:01110011
 68 8:01110100
 69 8:01110101
 70 8:01110110
 71 8:01110111
 72 8:01111000
 73 8:01111001
 74 8:01111010
 75 8:01111011
 76 8:01111100
 77 8:01111101
 78 8:01111110
 79 8:01111111
 80 8:10000000
 81 8:10000001
 82 8:10000010
 83 8:10000011
 84 8:10000100
 85 8:10000101
 86 8:10000110
 87 8:10000111
 88 8:10001000
 89 8:10001001
 90 8:10001010
 91 8:10001011
 92 8:10001100
 93 8:10001101
 94 8:10001110
 95 8:10001111
 96 8:10010000
 97 8:10010001
 98 8:10010010
 99 8:10010011
100 8:10010100
101 8:10010101
102 8:10010110
103 8:10010111
104 8:10011000
105 8:10011001
106 8:10011010
107 8:10011011
108 8:10011100
109 8:10011101
110 8:10011110
111 8:10011111
112 8:10100000
113 8:10100001
114 8:10100010
115 8:10100011
116 8:10100100
117 8:10100101
118 8:10100110
119 8:10100111
120 8:10101000
121 8:10101001
122 8:10101010
123 8:10101011
124 8:10101100
125 8:10101101
126 8:10101110
127 8:10101111
128 8:10110000
129 8:10110001
130 8:10110010
131 8:10110011
132 8:10110100
133 8:10110101
134 8:10110110
135 8:10110111
136 8:10111000
137 8:10111001
138 8:10111010
139 8:10111011
140 8:10111100
141 8:10111101
142 8:10111110
143 8:10111111
144 9:110010000
145 9:110010001
146 9:110010010
147 9:110010011
148 9:110010100
149 9:110010101
150 9:110010110
151 9:110010111
152 9:110011000
153 9:110011001
154 9:110011010
155 9:110011011
156 9:110011100
157 9:110011101
158 9:110011110
159 9:110011111
160 9:110100000
161 9:110100001
162 9:110100010
163 9:110100011
164 9:110100100
165 9:110100101
166 9:110100110
167 9:110100111
168 9:110101000
169 9:110101001
170 9:110101010
171 9:110101011
172 9:110101100
173 9:110101101
174 9:110101110
175 9:110101111
176 9:110110000
177 9:110110001
178 9:110110010
179 9:110110011
180 9:110110100
181 9:110110101
182 9:110110110
183 9:110110111
184 9:110111000
185 9:110111001
186 9:110111010
187 9:110111011
188 9:110111100
189 9:110111101
190 9:110111110
191 9:110111111
192 9:111000000
193 9:111000001
194 9:111000010
195 9:111000011
196 9:111000100
197 9:111000101
198 9:111000110
199 9:111000111
200 9:111001000
201 9:111001001
202 9:111001010
203 9:111001011
204 9:111001100
205 9:111001101
206 9:111001110
207 9:111001111
208 9:111010000
209 9:111010001
210 9:111010010
211 9:111010011
212 9:111010100
213 9:111010101
214 9:111010110
215 9:111010111
216 9:111011000
217 9:111011001
218 9:111011010
219 9:111011011
220 9:111011100
221 9:111011101
222 9:111011110
223 9:111011111
224 9:111100000
225 9:111100001
226 9:111100010
227 9:111100011
228 9:111100100
229 9:111100101
230 9:111100110
231 9:111100111
232 9:111101000
233 9:111101001
234 9:111101010
235 9:111101011
236 9:111101100
237 9:111101101
238 9:111101110
239 9:111101111
240 9:111110000
241 9:111110001
242 9:111110010
243 9:111110011
244 9:111110100
245 9:111110101
246 9:111110110
247 9:111110111
248 9:111111000
249 9:111111001
250 9:111111010
251 9:111111011
252 9:111111100
253 9:111111101
254 9:111111110
255 9:111111111
256 7:0000000
257 7:0000001
258 7:0000010
259 7:0000011
260 7:0000100
261 7:0000101
262 7:0000110
263 7:0000111
264 7:0001000
265 7:0001001
266 7:0001010
267 7:0001011
268 7:0001100
269 7:0001101
270 7:0001110
271 7:0001111
272 7:0010000
273 7:0010001
274 7:0010010
275 7:0010011
276 7:0010100
277 7:0010101
278 7:0010110
279 7:0010111
280 8:11000000
281 8:11000001
282 8:11000010
283 8:11000011
284 8:11000100
285 8:11000101
286 8:11000110
287 8:11000111

前方距離コード用固定辞書
  0 5:00000
  1 5:00001
  2 5:00010
  3 5:00011
  4 5:00100
  5 5:00101
  6 5:00110
  7 5:00111
  8 5:01000
  9 5:01001
 10 5:01010
 11 5:01011
 12 5:01100
 13 5:01101
 14 5:01110
 15 5:01111
 16 5:10000
 17 5:10001
 18 5:10010
 19 5:10011
 20 5:10100
 21 5:10101
 22 5:10110
 23 5:10111
 24 5:11000
 25 5:11001
 26 5:11010
 27 5:11011
 28 5:11100
 29 5:11101
 30 5:11110
 31 5:11111

#!/usr/bin/env python3

import time

####################
#
#   メッセージ処理
#
####################


def noop(*args, **kw): pass  # 何もしない


def print_list(data, prefix=None, indent=0, width=16):
    if prefix:
        msgprint(prefix + ':')
    indent = ' ' * indent
    fmt = '%{0}d'.format(len('%d' % max(data)))
    dlen = len(data)
    for s in range(0, dlen, width):
        line = [fmt % d for d in data[s:min(s + width, dlen)]]
        msgprint('%s%04x: %s' % (indent, s, '  '.join(line)))


def set_verbose_mode():
    global msgprint
    global msgprint_list

    msgprint = print
    msgprint_list = print_list


msgprint = noop
msgprint_list = noop

########################
#
#   チェック・サム
#
########################

#
# Adler-32 チェック・サム
#


class ADLER32:

    @staticmethod
    def adler32(bs):
        return ADLER32(bs).get_value()

    def __init__(self, data=None):
        self.value = 1
        if data != None:
            self.update(data)

    def update(self, data):
        l = self.value & 0xffff
        h = self.value >> 16
        for d in data:
            l = (l + d) % 65521
            h = (h + l) % 65521
        self.value = (h << 16) | l

    def get_value(self):
        return self.value


#
# CRC-32 チェック・サム
#
class CRC32:
    @staticmethod
    def make_table(poly=0xedb88320):
        def f(x): return (x >> 1) ^ (poly if x & 1 else 0)
        return [f(f(f(f(f(f(f(f(n)))))))) for n in range(256)]

    @staticmethod
    def crc32(data):
        return CRC32(data).get_value()

    MASK = 0xffffffff
    TABLE = None

    def __init__(self, data=None):
        if CRC32.TABLE is None:
            CRC32.TABLE = CRC32.make_table()
        self.value = CRC32.MASK
        if data != None:
            self.update(data)

    def update(self, data):
        crc = self.value
        for d in data:
            crc = (crc >> 8) ^ CRC32.TABLE[(crc ^ d) & 0xff]
        self.value = crc

    def get_value(self):
        return self.value ^ CRC32.MASK


################################
#
#   入出力
#
################################

#
# ビット単位での読取り:
#     8 ビットより大きい場合は、リトル・エンディアン形式として扱う.
#
class BitStream:
    def __init__(self, inp):
        self.istream = inp
        self.fetch_data = 0
        self.fetch_bits = 0

    # 指定ビット数を先読み保持から破棄する
    def feed(self, bits):
        self.fetch_data >>= bits
        self.fetch_bits -= bits

    # 指定ビット数を先読みして保持する
    def fetch(self, bits):
        while bits > self.fetch_bits:
            self.fetch_data |= self.readbyte() << self.fetch_bits
            self.fetch_bits += 8
        mask = (1 << bits) - 1
        return (self.fetch_data & mask)

    # 指定ビット数を取り出して進める
    def read(self, bits):
        value = self.fetch(bits)
        self.feed(bits)
        return value

    # バイト境界まで読み出し位置を進める
    def skip_align(self):
        bits = self.fetch_bits & 7
        if bits != 0:
            self.feed(bits)

    # 直接１バイト読み出す
    def readbyte(self):
        return self.istream.read(1)[0]


#
# 解凍データの出力先:
#     全ての解凍データを保持する（手抜き）
#
class OutputStream:
    def __init__(self):
        self.output = []

    # 文字を１つ追加
    def write(self, value):
        self.output.append(value)

    # distance/length による複写追記
    def lzcopy(self, distance, length):
        pos = len(self.output) - distance
        for n in range(length):
            self.output.append(self.output[pos+n])


#
# ハフマン符号の解凍
#
class DecodeHuffman:

    # 符号のビット列を反転する
    #   length が 0 のときは None
    @staticmethod
    def reverse_code(code, length):
        return int(('{0:0%db}' % length).format(code)[::-1], 2) if length != 0 else None

    # 文字に対する符号長の配列で初期化する
    #   入力: lengths[文字] = 符号長
    def __init__(self, lengths):
        # 最大符号長
        self.max_length = max(lengths)

        # 符号長ごとの符号の初期値を作る
        #    length_code[符号長] = 符号の初期値
        def gen_length_code():
            yield 0
            code = 0
            for length in range(1, self.max_length + 1):
                yield code
                code = (code + lengths.count(length)) << 1

        # 文字に対する (反転符号, 符号長) を生成
        def gen_dictionary(length_code):
            for length in lengths:
                yield (DecodeHuffman.reverse_code(length_code[length], length), length)
                length_code[length] += 1

        # 符号化辞書: dictionary[文字] = (反転符号, 符号長)
        dictionary = (*gen_dictionary([*gen_length_code()]),)

        # 復号辞書の生成
        self.decode_table = [None] * (1 << self.max_length)
        for literal in range(len(lengths)):
            code, length = dictionary[literal]
            if length == 0:
                continue
            step = 1 << length
            value = (literal, length)
            while code < len(self.decode_table):
                self.decode_table[code] = value
                code += step

    # ストリームから復号して、文字を１つ取り出す
    #   出力：（文字, 符号長, ビット反転符号）

    def decode(self, bstream):
        code = bstream.fetch(self.max_length)
        literal, length = self.decode_table[code]
        code &= (1 << length) - 1
        if False:
            msgprint(('Huffman: {2:#05x} <- {1:2}:{0:0%db}' % length).
                     format(DecodeHuffman.reverse_code(code, length), length, literal))
        bstream.feed(length)
        return (literal, length, code)


#
# RFC-1951: DEFLATE 圧縮データ形式の解凍
#
class Inflate:
    CL4CL_ORDER = (
        16, 17, 18,
        0, 8,
        7, 9,
        6, 10,
        5, 11,
        4, 12,
        3, 13,
        2, 14,
        1, 15
    )

    LENGTH_BASE = (
        (3, 0), (4, 0), (5, 0), (6, 0),
        (7, 0), (8, 0), (9, 0), (10, 0),
        (11, 1), (13, 1), (15, 1), (17, 1),
        (19, 2), (23, 2), (27, 2), (31, 2),
        (35, 3), (43, 3), (51, 3), (59, 3),
        (67, 4), (83, 4), (99, 4), (115, 4),
        (131, 5), (163, 5), (195, 5), (227, 5),
        (258, 0),
    )

    DISTANCE_BASE = (
        (1,  0), (2,  0),
        (3,  0), (4,  0),
        (5,  1), (7,  1),
        (9,  2), (13,  2),
        (17,  3), (25,  3),
        (33,  4), (49,  4),
        (65,  5), (97,  5),
        (129,  6), (193,  6),
        (257,  7), (385,  7),
        (513,  8), (769,  8),
        (1025,  9), (1537,  9),
        (2049, 10), (3073, 10),
        (4097, 11), (6145, 11),
        (8193, 12), (12289, 12),
        (16385, 13), (24577, 13),
    )

    BTYPE00_LITERAL_LENGTH = [8]*(144-0) + [9]*(256-144) + [7]*(280-256) + [8]*(288-280)
    BTYPE00_DISTANCE_LENGTH = [5]*32

    def __init__(self, bitstream, ostream):
        self.bstream = bitstream
        self.ostream = ostream
        self.code_decoder = None
        self.literal_decoder = None
        self.distance_decoder = None
        self.BFINAL = None
        self.BTYPE = None
        self.HLIT = None
        self.HDIST = None
        self.HCLEN = None
        self.CL4CL = None
        self.CL4LA = None
        self.CL4DA = None

    #
    # ブロックの解凍
    #
    def block(self):
        msgprint('======== BLOCK ========')
        self.BFINAL = self.bstream.read(1)
        self.BTYPE = self.bstream.read(2)

        BT0 = (self.BTYPE >> 0) & 1
        BT1 = (self.BTYPE >> 1) & 1
        msgprint('%8s: %d' % ('BFINAL', self.BFINAL))
        msgprint('%8s: %d%d' % ('BTYPE', BT1, BT0))

        if self.BTYPE == 0:
            self.btype00()
        elif self.BTYPE == 1:
            self.btype01()
        elif self.BTYPE == 2:
            self.btype10()
        elif self.BTYPE == 3:
            raise NotImplemented  # reserved
        return (self.BFINAL == 0)

    #
    # ブロック タイプ 00 : 非圧縮なので複写
    #
    def btype00(self):
        self.bstream.skip_align()
        LEN = self.bstream.read(16)
        NLEN = self.bstream.read(16) ^ 0xffff
        if LEN != NLEN:
            raise Exception('LEN(%#06x) != NLEN(%#06x)' % (LEN, NLEN))
        msgprint('BTYPE00: LEN(%#06x), NLEN(%#06x)' % (LEN, NLEN))

        for n in range(LEN):
            self.ostream.write(self.bstream.read(8))

    #
    # ブロック タイプ 01 : 固定辞書による解凍
    #
    def btype01(self):
        self.literal_decoder = DecodeHuffman(Inflate.BTYPE00_LITERAL_LENGTH)
        self.distance_decoder = DecodeHuffman(Inflate.BTYPE00_DISTANCE_LENGTH)
        self.decode_data()

    #
    # ブロック タイプ 10 : 動的辞書による解凍
    #
    def btype10(self):
        self.btype10_header()
        self.btype10_code_length()
        self.btype10_literal_length()
        self.btype10_distance_length()
        self.decode_data()

    def btype10_header(self):
        HLIT = self.bstream.read(5)
        HDIST = self.bstream.read(5)
        HCLEN = self.bstream.read(4)
        self.HLIT = HLIT + 257
        self.HDIST = HDIST + 1
        self.HCLEN = HCLEN + 4
        msgprint('%8s: %d + 257 = %d' % ('HLIT', HLIT, self.HLIT))
        msgprint('%8s: %d + 1 = %d' % ('HDIST', HDIST, self.HDIST))
        msgprint('%8s: %d + 4 = %d' % ('HCLEN', HCLEN, self.HCLEN))

    # 圧縮された動的辞書の解凍準備
    def btype10_code_length(self):
        CL4CL = []
        for n in range(self.HCLEN):
            CL4CL.append(self.bstream.read(3))

        self.CL4CL = [0] * 19
        for n in range(len(CL4CL)):
            p = Inflate.CL4CL_ORDER[n]
            self.CL4CL[p] = CL4CL[n]
        msgprint_list(CL4CL, '  code length', 4)

        self.code_decoder = DecodeHuffman(self.CL4CL)
        self.HDICT = self.decode_dictionary()

    # literal/length の解凍準備
    def btype10_literal_length(self):
        self.CL4LA = self.HDICT[:self.HLIT]
        msgprint_list(self.CL4LA, '  literal/length code length', 4)
        if self.CL4LA[256] == 0:
            raise Exception('CODE[256] == 0')
        self.literal_decoder = DecodeHuffman(self.CL4LA)

    # distance の解凍準備
    def btype10_distance_length(self):
        self.CL4DA = self.HDICT[self.HLIT:]
        msgprint_list(self.CL4DA, '  distance code length', 4)
        self.distance_decoder = DecodeHuffman(self.CL4DA)

    # literal/length, distance 符号情報の解凍
    def decode_dictionary(self):
        count = self.HLIT + self.HDIST
        clen = []
        while len(clen) < count:
            (code, bits, huff) = self.code_decoder.decode(self.bstream)

            # 0..15 はコードに対する符号のビット数
            if code < 16:
                clen.append(code)
                continue

            c = 0
            n = 0
            if code == 16:
                # 直前の値を複写(3~6)
                #   長さは直後の 2 ビットに 3 を加える
                n = self.bstream.read(2) + 3
                c = clen[-1]
            elif code == 17:
                # ゼロで埋める(3~10)
                #    長さは直後の 3 ビットに 3 を加える
                n = self.bstream.read(3) + 3
            elif code == 18:
                # ゼロで埋める(11~138)
                #    長さは直後の 7 ビットに 11 を加える
                n = self.bstream.read(7) + 11
            else:
                raise Exception('unknown code: %d' % code)
            clen += [c] * n
        return clen

    # 圧縮データの解凍
    def decode_data(self):
        msgprint('COMPRESSED DATA:')
        while True:
            # literal/length の解凍
            (code, bits, huff) = self.literal_decoder.decode(self.bstream)

            # 0..255 は 8 ビットの文字データ(literal)
            if code < 256:
                self.ostream.write(code)
                c = chr(code)
                if not c.isprintable():
                    c = ''
                msgprint('  LITERAL[%#04x]: %s' % (code, c))
                continue

            # 256 はブロックの終わり
            if code == 256:
                msgprint('  END:')
                break

            # 257..285 はデータの複写数情報(length)
            # 以下で、実際の数を求める
            length, b = Inflate.LENGTH_BASE[code - 257]
            if b != 0:
                length += self.bstream.read(b)

            # データの複写開始位置情報(distance)の解凍
            (code, bits, huff) = self.distance_decoder.decode(self.bstream)

            # 以下で、実際の開始位置を求める
            distance, b = Inflate.DISTANCE_BASE[code]
            if b != 0:
                distance += self.bstream.read(b)

            # データの複写
            msgprint('  LENGTH=%d, DISTANCE=%d' % (length, distance))
            self.ostream.lzcopy(distance, length)


#　RFC-1950: ZLIB 圧縮データ形式の解凍
class ZLIBInflate:
    COMPRESSION_ALGORITHM = (
        'fastest',
        'fast',
        'default',
        'slowest',
    )

    def __init__(self, fp):
        self.bstream = BitStream(fp)
        self.ostream = OutputStream()
        self.header_CMF = None
        self.header_FLG = None

    def CMF_CM(self):
        return (self.header_CMF & 0x0f)

    def CMF_CINFO(self):
        return ((self.header_CMF >> 4) & 0x0f)

    def flags_FCHECK(self):
        return (self.header_FLG & 0x1f)

    def flags_FDICT(self):
        return (self.header_FLG & 0x20)

    def flags_FLEVEL(self):
        return ((self.header_FLG >> 6) & 3)

    def inflate_date(self):
        return self.ostream.output

    #
    # 入力ファイルの解凍処理
    #
    def inflate(self):
        # CMF:FLG を調査
        self.header_CMF = self.bstream.read(8)
        self.header_FLG = self.bstream.read(8)
        msgprint('CMF:FLG = %02x:%02x' % (self.header_CMF, self.header_FLG))

        if ((self.header_CMF * 256 + self.header_FLG) % 31) != 0:
            raise Exception('invalid FCHECK')

        cm = self.CMF_CM()
        if cm != 8:
            raise Exception('unknown compression method: %d' % cm)

        cinfo = self.CMF_CINFO()
        if cinfo > 7:
            raise Exception('invalid CINFO')
        # window_size = 1 << (8 + cinfo)

        # FDICT には非対応
        if self.flags_FDICT():
            self.DICTID = self.bstream.readbyte(4)
            raise NotImplemented

        # 圧縮データの解凍
        self.inflate = Inflate(self.bstream, self.ostream)
        while self.inflate.block():
            pass
        self.bstream.skip_align()

        # Adler-32 によるエラー検知
        xadler32 = ADLER32.adler32(self.inflate_date())
        dadler32 = self.read32be()
        msgprint('ADLER32: %#010x (%#010x)' % (dadler32, xadler32))
        if xadler32 != dadler32:
            raise Exception('ADLER32: %#010x != %#010x' % (dadler32, xadler32))

    # ビッグ・エンディアンで 32bit の読み出し
    def read32be(self):
        b0 = self.bstream.read(8)
        b1 = self.bstream.read(8)
        b2 = self.bstream.read(8)
        b3 = self.bstream.read(8)
        return (b0 << 24) | (b1 << 16) | (b2 << 8) | b3


#　RFC-1952: GZIP 圧縮データ形式の解凍
class GZIPInflate:
    OS_NAME = {
        0: 'FAT filesystem (MS-DOS, OS/2, NT/Win32)',
        1: 'Amiga',
        2: 'VMS (or OpenVMS)',
        3: 'Unix',
        4: 'VM/CMS',
        5: 'Atari TOS',
        6: 'HPFS filesystem (OS/2, NT)',
        7: 'Machintosh',
        8: 'Z-System',
        9: 'CP/M',
        10: 'TOPS-20',
        11: 'NTFS filesystem (NT)',
        12: 'QDOS',
        13: 'Acorn RISCOS',
        255: 'unknown',
    }

    XFL_NAME = {
        0: '(default compression)',
        2: 'slowest algorithm (maximum compression)',
        4: 'fastest algorithm',
    }

    def __init__(self, fp):
        self.bstream = BitStream(fp)
        self.ostream = OutputStream()
        self.read_data = []
        self.compression_method = None
        self.flags = None
        self.mtime = None
        self.extra_flags = None
        self.os = None
        self.extra = None
        self.name = None
        self.comment = None
        self.crc16 = None

    def flags_FTEXT(self):
        return (self.flags & 0x01)

    def flags_FHCRC(self):
        return (self.flags & 0x02)

    def flags_FEXTRA(self):
        return (self.flags & 0x04)

    def flags_FNAME(self):
        return (self.flags & 0x08)

    def flags_FCOMMENT(self):
        return (self.flags & 0x10)

    def inflate_date(self):
        return self.ostream.output

    # 入力ファイルから１バイトの読取り
    #   FHCRC 処理に備える
    def readbyte(self, n=1):
        r = 0
        b = 0
        for i in range(n):
            d = self.bstream.readbyte()
            self.read_data.append(d)
            r += d << b
            b += 8
        return r

    #
    # 入力ファイルの解凍処理
    #
    def inflate(self):
        # ID を調査
        self.check_id()

        # ヘッダ部の読み込み
        self.read_header()

        # 圧縮データの解凍
        self.inflate = Inflate(self.bstream, self.ostream)
        while self.inflate.block():
            pass
        self.bstream.skip_align()

        # CRC32 によるエラー検知
        xdata = self.inflate_date()
        xcrc32 = CRC32.crc32(xdata)
        dcrc32 = self.bstream.read(32)
        msgprint('CRC32: %#010x (%#010x)' % (dcrc32, xcrc32))
        if dcrc32 != xcrc32:
            raise Exception('CRC32: %#010x != %#010x' % (dcrc32, xcrc32))

        # 元データとの大きさ比較によるエラー検知
        xsize = len(xdata)
        isize = self.bstream.read(32)
        msgprint('ISIZE: %#010x (%#010x)' % (isize, xsize))
        if isize != xsize:
            raise Exception('ISIZE: %#010x != %#010x' % (isize, xsize))

    # ファイルの先頭が 0x1f, 0x8b か？
    def check_id(self):
        id1 = self.readbyte()
        id2 = self.readbyte()
        magic = 'FILE MAGIC: %#04x,%#04x' % (id1, id2)
        if id1 != 0x1f or id2 != 0x8b:
            raise Exception('Invalid ' + magic)
        msgprint(magic)

    #
    # ヘッダ部の読み込み
    #
    def read_header(self):
        # 必須
        self.read_header_CM()
        self.read_header_FLG()
        self.read_header_MTIME()
        self.read_header_XFL()
        self.read_header_OS()
        # オプション
        self.read_header_EXTRA()
        self.read_header_NAME()
        self.read_header_COMMENT()
        self.read_header_CRC16()

    def read_header_CM(self):
        self.compression_method = self.readbyte()
        msgprint('%8s: %#04x' % ('CM', self.compression_method))
        if self.compression_method != 8:
            raise Exception('unknown compression method: %d' % self.compression_method)

    def read_header_FLG(self):
        self.flags = self.readbyte()
        mflg = ''
        if self.flags_FTEXT():
            mflg += ', FTEXT'
        if self.flags_FHCRC():
            mflg += ', FHCRC'
        if self.flags_FEXTRA():
            mflg += ', FEXTRA'
        if self.flags_FNAME():
            mflg += ', FNAME'
        if self.flags_FCOMMENT():
            mflg += ', FCOMMENT'
        msgprint('%8s: %#04x%s' % ('FLG', self.flags, mflg))

    def read_header_MTIME(self):
        self.mtime = self.readbyte(4)
        msgprint('%8s: %s (%#010x)' % ('MTIME', time.ctime(self.mtime), self.mtime))

    def read_header_XFL(self):
        self.extra_flags = self.readbyte()
        msgprint('%8s: %#04x, %s' % ('XFL', self.extra_flags, GZIPInflate.XFL_NAME[self.extra_flags]))

    def read_header_OS(self):
        self.os = self.readbyte()
        msgprint('%8s: %#04x, %s' % ('OS', self.os, GZIPInflate.OS_NAME[self.os]))

    def read_header_EXTRA(self):
        self.extra = None
        if self.flags_FEXTRA():
            self.read_EXTRA()

    def read_header_NAME(self):
        self.name = None
        if self.flags_FNAME():
            self.name = self.read_CString()
            msgprint('%8s: \'%s\'' % ('NAME', self.name))

    def read_header_COMMENT(self):
        self.comment = None
        if self.flags_FCOMMENT():
            self.comment = self.read_CString()
            msgprint('%8s: %s' % ('COMMENT', self.name))

    def read_header_CRC16(self):
        self.crc16 = None
        if self.flags_FHCRC():
            crc16 = 0xffff & CRC32.crc32(self.read_data)
            self.crc16 = self.readbyte(2)
            msgprint('CRC16: %#06x, %#06x' % self.crc16, crc16)

    # 拡張データの読み込み
    def read_EXTRA(self):
        xlen = self.readbyte(2)
        self.extra = []
        for n in range(xlen):
            self.extra.append(self.readbyte())
        msgprint('%8s: [%d] ...' % ('EXTRA', len(self.extra)))

    # NULL 文字終端の文字列の読み込み
    def read_CString(self):
        s = ''
        while True:
            c = self.readbyte()
            if c == 0:
                break
            s += chr(c)
        return s


# コマンド ライン起動用の関数
def main():
    import argparse
    import codecs
    import sys

    # コマンド ライン引数の解析
    parser = argparse.ArgumentParser()
    parser.add_argument('-v', '--verbose', action='store_true', help='冗長モード')
    parser.add_argument('-o', '--output', metavar='OUTPUT', help='出力ファイル')
    parser.add_argument('INPUT', help='入力ファイル')
    args = parser.parse_args()

    # 冗長モードを設定
    if args.verbose or args.output is None:
        set_verbose_mode()

    # 入力ファイルを開く
    if len(args.INPUT) == 0:
        return parser.print_help()
    if args.INPUT == '-':
        inp = sys.stdin.buffer
    else:
        inp = open(args.INPUT, 'rb')

    # 解凍処理
    gz = GZIPInflate(inp)
    gz.inflate()

    # 解凍データを出力
    if args.output:
        if args.output == '-':
            out = sys.stdout
        else:
            out = open(args.output, 'wb')
        out.write(bytearray(gz.inflate_date()))


if __name__ == '__main__':
    main()