AtlatestRepositorysigil-http3
sigil-http3 / tree / scriptsgenerate-qpack-tables.mjs
1
// Run on Linux. Generate protocol constants from the published RFCs.2
import { mkdirSync, writeFileSync } from 'node:fs';3
import { createHash } from 'node:crypto';5
const urls = [6
'https://www.rfc-editor.org/rfc/rfc9204.xml',7
'https://www.rfc-editor.org/rfc/rfc7541.txt',8
];9
const sources = await Promise.all(urls.map(async url => {10
const response = await fetch(url, { signal: AbortSignal.timeout(20000) });11
if (!response.ok) throw new Error(`${url}: ${response.status}`);12
return response.text();13
}));14
const plain = text => text.replace(/<[^>]*>/g, '').replace(/&#(x[0-9a-f]+|[0-9]+);/gi,15
(_, value) => String.fromCodePoint(value[0] === 'x' ? parseInt(value.slice(1), 16) : +value))16
.replace(/</g, '<').replace(/>/g, '>').replace(/"/g, '"')17
.replace(/'/g, "'").replace(/&/g, '&').replace(/\s+/g, ' ').trim();18
const fields = [];19
for (const match of sources[0].matchAll(/<tr\b[^>]*>([\s\S]*?)<\/tr>/g)) {20
const cells = [...match[1].matchAll(/<td\b[^>]*?\/>|<td\b[^>]*>([\s\S]*?)<\/td>/g)]21
.map(cell => plain(cell[1] ?? ''));22
if (cells.length === 3 && /^\d+$/.test(cells[0])) fields.push(cells);23
}24
if (fields.length !== 99 || fields.some((field, index) => +field[0] !== index)) {25
throw new Error(`RFC 9204 table is not exactly 99 ordered entries: ${fields.length}`);26
}27
if (fields[25][1] !== ':status' || fields[25][2] !== '200' || fields[98][1] !== 'x-frame-options') {28
throw new Error('RFC 9204 table anchor checks failed');29
}31
const codes = [];32
for (const match of sources[1].matchAll(/\(\s*(\d+)\)\s+\|[01|]+\s+([0-9a-f]+)\s+\[\s*(\d+)\]/g)) {33
const [, symbol, hex, width] = match;34
if (+symbol !== codes.length) throw new Error('Huffman symbol order differs from RFC 7541');35
codes.push([parseInt(hex, 16), +width]);36
}37
if (codes.length !== 257 || codes[256][0] !== 0x3fffffff || codes[256][1] !== 30) {38
throw new Error(`RFC 7541 Huffman table is not exactly 257 codes: ${codes.length}`);39
}40
const nodes = [[-1, -1, -1]];41
for (const [symbol, [code, width]] of codes.entries()) {42
let node = 0;43
for (let shift = width - 1; shift >= 0; shift--) {44
if (nodes[node][2] !== -1) throw new Error('Huffman prefix collision');45
const bit = Math.floor(code / 2 ** shift) % 2;46
if (nodes[node][bit] === -1) {47
nodes[node][bit] = nodes.length;48
nodes.push([-1, -1, -1]);49
}50
node = nodes[node][bit];51
}52
if (nodes[node].some(value => value !== -1)) throw new Error('Huffman duplicate or prefix');53
nodes[node][2] = symbol;54
}55
const octets = text => `#u8(${[...Buffer.from(text, 'utf8')].join(' ')})`;56
const output = `;;; Generated from RFC 9204 Appendix A and RFC 7541 Appendix B.57
;;; Reproduce on Linux: node scripts/generate-qpack-tables.mjs58
;;; Protocol constants; see the RFCs' IETF Trust notices.59
(define-library (sigil http3 qpack tables)60
(export qpack-static-table qpack-huffman-tree)61
(begin62
(define qpack-static-table63
'#(64
${fields.map(([, name, value]) => ` (${octets(name)} . ${octets(value)})`).join('\n')}))65
(define qpack-huffman-tree66
'#(67
${nodes.map(node => ` #(${node.join(' ')})`).join('\n')}))))68
`;69
mkdirSync('src/sigil/http3/qpack', { recursive: true });70
mkdirSync('build', { recursive: true });71
writeFileSync('src/sigil/http3/qpack/tables.sgl', output);72
const receipt = urls.map((url, index) => `${url} sha256=${createHash('sha256').update(sources[index]).digest('hex')}`);73
receipt.push(`RESULT qpack-static-entries=${fields.length} huffman-symbols=${codes.length} trie-nodes=${nodes.length}`);74
writeFileSync('build/qpack-table-sources.txt', receipt.join('\n') + '\n');75
console.log(receipt.join('\n'));