DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (07eb2cc7e1c3)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
# This script exists to auto-generate Http2HuffmanIncoming.h from the table
# contained in the HPACK spec. It's pretty simple to run:
#   python make_incoming_tables.py < http2_huffman_table.txt > Http2HuffmanIncoming.h
# where huff_incoming.txt is copy/pasted text from the latest version of the
# HPACK spec, with all non-relevant lines removed (the most recent version
# of huff_incoming.txt also lives in this directory as an example).
import sys

def char_cmp(x, y):
    rv = cmp(x['nbits'], y['nbits'])
    if not rv:
        rv = cmp(x['bpat'], y['bpat'])
    if not rv:
        rv = cmp(x['ascii'], y['ascii'])
    return rv

characters = []

for line in sys.stdin:
    line = line.rstrip()
    obracket = line.rfind('[')
    nbits = int(line[obracket + 1:-1])

    oparen = line.find(' (')
    ascii = int(line[oparen + 2:oparen + 5].strip())

    bar = line.find('|', oparen)
    space = line.find(' ', bar)
    bpat = line[bar + 1:space].strip().rstrip('|')

    characters.append({'ascii': ascii, 'nbits': nbits, 'bpat': bpat})

characters.sort(cmp=char_cmp)
raw_entries = []
for c in characters:
    raw_entries.append((c['ascii'], c['bpat']))

class DefaultList(list):
    def __init__(self, default=None):
        self.__default = default

    def __ensure_size(self, sz):
        while sz > len(self):
            self.append(self.__default)

    def __getitem__(self, idx):
        self.__ensure_size(idx + 1)
        rv = super(DefaultList, self).__getitem__(idx)
        return rv

    def __setitem__(self, idx, val):
        self.__ensure_size(idx + 1)
        super(DefaultList, self).__setitem__(idx, val)

def expand_to_8bit(bstr):
    while len(bstr) < 8:
        bstr += '0'
    return int(bstr, 2)

table = DefaultList()
for r in raw_entries:
    ascii, bpat = r
    ascii = int(ascii)
    bstrs = bpat.split('|')
    curr_table = table
    while len(bstrs) > 1:
        idx = expand_to_8bit(bstrs[0])
        if curr_table[idx] is None:
            curr_table[idx] = DefaultList()
        curr_table = curr_table[idx]
        bstrs.pop(0)

    idx = expand_to_8bit(bstrs[0])
    curr_table[idx] = {'prefix_len': len(bstrs[0]),
                        'mask': int(bstrs[0], 2),
                        'value': ascii}


def output_table(table, name_suffix=''):
    max_prefix_len = 0
    for i, t in enumerate(table):
        if isinstance(t, dict):
            if t['prefix_len'] > max_prefix_len:
                max_prefix_len = t['prefix_len']
        elif t is not None:
            output_table(t, '%s_%s' % (name_suffix, i))

    tablename = 'HuffmanIncoming%s' % (name_suffix if name_suffix else 'Root',)
    entriestable = tablename.replace('HuffmanIncoming', 'HuffmanIncomingEntries')
    nexttable = tablename.replace('HuffmanIncoming', 'HuffmanIncomingNextTables')
    sys.stdout.write('static const HuffmanIncomingEntry %s[] = {\n' %
                     (entriestable,))
    prefix_len = 0
    value = 0
    i = 0
    while i < 256:
        t = table[i]
        if isinstance(t, dict):
            value = t['value']
            prefix_len = t['prefix_len']
        elif t is not None:
            break

        sys.stdout.write('  { %s, %s }' %
                         (value, prefix_len))
        sys.stdout.write(',\n')
        i += 1

    indexOfFirstNextTable = i
    if i < 256:
        sys.stdout.write('};\n')
        sys.stdout.write('\n')
        sys.stdout.write('static const HuffmanIncomingTable* %s[] = {\n' %
                         (nexttable,))
        while i < 256:
            subtable = '%s_%s' % (name_suffix, i)
            ptr = '&HuffmanIncoming%s' % (subtable,)
            sys.stdout.write('  %s' %
                             (ptr))
            sys.stdout.write(',\n')
            i += 1
    else:
        nexttable = 'nullptr'

    sys.stdout.write('};\n')
    sys.stdout.write('\n')
    sys.stdout.write('static const HuffmanIncomingTable %s = {\n' % (tablename,))
    sys.stdout.write('  %s,\n' % (entriestable,))
    sys.stdout.write('  %s,\n' % (nexttable,))
    sys.stdout.write('  %s,\n' % (indexOfFirstNextTable,))
    sys.stdout.write('  %s\n' % (max_prefix_len,))
    sys.stdout.write('};\n')
    sys.stdout.write('\n')

sys.stdout.write('''/*
 * THIS FILE IS AUTO-GENERATED. DO NOT EDIT!
 */
#ifndef mozilla__net__Http2HuffmanIncoming_h
#define mozilla__net__Http2HuffmanIncoming_h

namespace mozilla {
namespace net {

struct HuffmanIncomingTable;

struct HuffmanIncomingEntry {
  uint16_t mValue:9;      // 9 bits so it can hold 0..256
  uint16_t mPrefixLen:7;  // only holds 1..8
};

// The data members are public only so they can be statically constructed. All
// accesses should be done through the functions.
struct HuffmanIncomingTable {
  // The normal entries, for indices in the range 0..(mNumEntries-1).
  const HuffmanIncomingEntry* const mEntries;

  // The next tables, for indices in the range mNumEntries..255. Must be
  // |nullptr| if mIndexOfFirstNextTable is 256.
  const HuffmanIncomingTable** const mNextTables;

  // The index of the first next table (equal to the number of entries in
  // mEntries). This cannot be a uint8_t because it can have the value 256,
  // in which case there are no next tables and mNextTables must be |nullptr|.
  const uint16_t mIndexOfFirstNextTable;

  const uint8_t mPrefixLen;

  bool IndexHasANextTable(uint8_t aIndex) const
  {
    return aIndex >= mIndexOfFirstNextTable;
  }

  const HuffmanIncomingEntry* Entry(uint8_t aIndex) const
  {
    MOZ_ASSERT(aIndex < mIndexOfFirstNextTable);
    return &mEntries[aIndex];
  }

  const HuffmanIncomingTable* NextTable(uint8_t aIndex) const
  {
    MOZ_ASSERT(aIndex >= mIndexOfFirstNextTable);
    return mNextTables[aIndex - mIndexOfFirstNextTable];
  }
};

''')

output_table(table)

sys.stdout.write('''} // namespace net
} // namespace mozilla

#endif // mozilla__net__Http2HuffmanIncoming_h
''')