mkhufftbl.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3
   4 # This script reads Huffman Code table [1] and generates symbol table
   5 # and decoding tables in C language.  The resulting code is used in
   6 # lib/nghttp2_hd_huffman.h and lib/nghttp2_hd_huffman_data.c
   7 #
   8 # [1] http://http2.github.io/http2-spec/compression.html
   9
  10 from __future__ import unicode_literals
  11 import re
  12 import sys
  13
  14 class Node:
  15     def __init__(self, term = None):
  16         self.term = term
  17         self.left = None
  18         self.right = None
  19         self.trans = []
  20         self.id = None
  21         self.accept = False
  22
  23 def to_bin(s):
  24     res = []
  25     for i in range(0, len(s), 8):
  26         x = s[i:i+8]
  27         x += '0'*(8 - len(x))
  28         a = 0
  29         for j in range(8):
  30             a *= 2
  31             a += ord(x[j]) - ord('0')
  32         res.append(a) #chr(a))
  33     return res
  34
  35 nodes = []
  36
  37 def insert(node, sym, bits):
  38     if len(bits) == 0:
  39         node.term = sym
  40         return
  41     else:
  42         if bits[0] == '0':
  43             if node.left is None:
  44                 node.left = Node()
  45             child = node.left
  46         else:
  47             if node.right is None:
  48                 node.right = Node()
  49             child = node.right
  50         insert(child, sym, bits[1:])
  51
  52 def traverse(node, bits, syms, start_node, root, depth):
  53     if depth == 4:
  54         if 256 in syms:
  55             syms = []
  56             node = None
  57         start_node.trans.append((node, bits, syms))
  58         return
  59
  60     if node.term is not None:
  61         node = root
  62
  63     def go(node, bit):
  64         nbits = list(bits)
  65         nbits.append(bit)
  66         nsyms = list(syms)
  67         if node.term is not None:
  68             nsyms.append(node.term)
  69         traverse(node, nbits, nsyms, start_node, root, depth + 1)
  70
  71     go(node.left, 0)
  72     go(node.right, 1)
  73
  74 idseed = 0
  75
  76 def dfs_setid(node, prefix):
  77     if node.term is not None:
  78         return
  79     if len(prefix) <= 7 and [1] * len(prefix) == prefix:
  80         node.accept = True
  81     global idseed
  82     node.id = idseed
  83     idseed += 1
  84     dfs_setid(node.left, prefix + [0])
  85     dfs_setid(node.right, prefix + [1])
  86
  87 def dfs(node, root):
  88     if node is None:
  89         return
  90     traverse(node, [], [], node, root, 0)
  91     dfs(node.left, root)
  92     dfs(node.right, root)
  93
  94 NGHTTP2_HUFF_ACCEPTED = 1
  95 NGHTTP2_HUFF_SYM = 1 << 1
  96 NGHTTP2_HUFF_FAIL = 1 << 2
  97
  98 def dfs_print(node):
  99     if node.term is not None:
 100         return
 101     print '/* {} */'.format(node.id)
 102     print '{'
 103     for nd, bits, syms in node.trans:
 104         outlen = len(syms)
 105         flags = 0
 106         if outlen == 0:
 107             out = 0
 108         else:
 109             assert(outlen == 1)
 110             out = syms[0]
 111             flags |= NGHTTP2_HUFF_SYM
 112         if nd is None:
 113             id = 0
 114             flags |= NGHTTP2_HUFF_FAIL
 115         else:
 116             id = nd.id
 117             if id is None:
 118                 # if nd.id is None, it is a leaf node
 119                 id = 0
 120                 flags |= NGHTTP2_HUFF_ACCEPTED
 121             elif nd.accept:
 122                 flags |= NGHTTP2_HUFF_ACCEPTED
 123         print '  {{{}, 0x{:02x}, {}}},'.format(id, flags, out)
 124     print '},'
 125     dfs_print(node.left)
 126     dfs_print(node.right)
 127
 128 symbol_tbl = [(None, 0) for i in range(257)]
 129 tables = {}
 130
 131 root = Node()
 132
 133 for line in sys.stdin:
 134     m = re.match(r'.*\(\s*(\d+)\)\s+([|01]+)\s+(\S+)\s+\[\s*(\d+)\].*', line)
 135     if m:
 136         #print m.group(1), m.group(2), m.group(4)
 137         if len(m.group(3)) > 8:
 138             raise Error('Code is more than 4 bytes long')
 139         sym = int(m.group(1))
 140         bits = re.sub(r'\|', '', m.group(2))
 141         nbits = int(m.group(4))
 142         assert(len(bits) == nbits)
 143         binpat = to_bin(bits)
 144         assert(len(binpat) == (nbits+7)/8)
 145         symbol_tbl[sym] = (binpat, nbits, m.group(3))
 146         #print "Inserting", sym
 147         insert(root, sym, bits)
 148
 149 dfs_setid(root, [])
 150 dfs(root, root)
 151
 152 print '''\
 153 typedef struct {
 154   uint32_t nbits;
 155   uint32_t code;
 156 } nghttp2_huff_sym;
 157 '''
 158
 159 print '''\
 160 const nghttp2_huff_sym huff_sym_table[] = {'''
 161 for i in range(257):
 162     pat = list(symbol_tbl[i][0])
 163     pat += [0]*(4 - len(pat))
 164     print '''\
 165   {{ {}, 0x{}u }}{}\
 166 '''.format(symbol_tbl[i][1], symbol_tbl[i][2], ',' if i < 256 else '')
 167 print '};'
 168 print ''
 169
 170 print '''\
 171 enum {{
 172   NGHTTP2_HUFF_ACCEPTED = {},
 173   NGHTTP2_HUFF_SYM = {},
 174   NGHTTP2_HUFF_FAIL = {},
 175 }} nghttp2_huff_decode_flag;
 176 '''.format(NGHTTP2_HUFF_ACCEPTED, NGHTTP2_HUFF_SYM, NGHTTP2_HUFF_FAIL)
 177
 178 print '''\
 179 typedef struct {
 180   uint8_t state;
 181   uint8_t flags;
 182   uint8_t sym;
 183 } nghttp2_huff_decode;
 184 '''
 185
 186 print '''\
 187 const nghttp2_huff_decode huff_decode_table[][16] = {'''
 188 dfs_print(root)
 189 print '};'