1use crate::{Error, Result, http1::Header};
3#[path = "huffman_table.rs"]
4mod huffman_table;
5use huffman_table::CODES;
6const STATIC: [(&str, &str); 61] = [
7 (":authority", ""),
8 (":method", "GET"),
9 (":method", "POST"),
10 (":path", "/"),
11 (":path", "/index.html"),
12 (":scheme", "http"),
13 (":scheme", "https"),
14 (":status", "200"),
15 (":status", "204"),
16 (":status", "206"),
17 (":status", "304"),
18 (":status", "400"),
19 (":status", "404"),
20 (":status", "500"),
21 ("accept-charset", ""),
22 ("accept-encoding", "gzip, deflate"),
23 ("accept-language", ""),
24 ("accept-ranges", ""),
25 ("accept", ""),
26 ("access-control-allow-origin", ""),
27 ("age", ""),
28 ("allow", ""),
29 ("authorization", ""),
30 ("cache-control", ""),
31 ("content-disposition", ""),
32 ("content-encoding", ""),
33 ("content-language", ""),
34 ("content-length", ""),
35 ("content-location", ""),
36 ("content-range", ""),
37 ("content-type", ""),
38 ("cookie", ""),
39 ("date", ""),
40 ("etag", ""),
41 ("expect", ""),
42 ("expires", ""),
43 ("from", ""),
44 ("host", ""),
45 ("if-match", ""),
46 ("if-modified-since", ""),
47 ("if-none-match", ""),
48 ("if-range", ""),
49 ("if-unmodified-since", ""),
50 ("last-modified", ""),
51 ("link", ""),
52 ("location", ""),
53 ("max-forwards", ""),
54 ("proxy-authenticate", ""),
55 ("proxy-authorization", ""),
56 ("range", ""),
57 ("referer", ""),
58 ("refresh", ""),
59 ("retry-after", ""),
60 ("server", ""),
61 ("set-cookie", ""),
62 ("strict-transport-security", ""),
63 ("transfer-encoding", ""),
64 ("user-agent", ""),
65 ("vary", ""),
66 ("via", ""),
67 ("www-authenticate", ""),
68];
69fn bad() -> Error {
70 Error::new("COMPRESSION_ERROR", "invalid HPACK block")
71}
72pub fn encode_integer(mut value: usize, bits: u8, prefix: u8, out: &mut Vec<u8>) {
73 let mask = (1usize << bits) - 1;
74 if value < mask {
75 out.push(prefix | value as u8);
76 return;
77 }
78 out.push(prefix | mask as u8);
79 value -= mask;
80 while value >= 128 {
81 out.push((value as u8 & 127) | 128);
82 value >>= 7;
83 }
84 out.push(value as u8);
85}
86fn integer(input: &[u8], pos: &mut usize, bits: u8) -> Result<usize> {
87 let mask = (1usize << bits) - 1;
88 let mut n = (*input.get(*pos).ok_or_else(bad)? as usize) & mask;
89 *pos += 1;
90 if n < mask {
91 return Ok(n);
92 }
93 let mut shift = 0;
94 loop {
95 let b = *input.get(*pos).ok_or_else(bad)?;
96 *pos += 1;
97 if shift >= usize::BITS || (b as usize & 127) > (usize::MAX >> shift) {
98 return Err(bad());
99 }
100 n = n.checked_add((b as usize & 127) << shift).ok_or_else(bad)?;
101 if b & 128 == 0 {
102 return Ok(n);
103 }
104 shift += 7;
105 }
106}
107pub fn huffman_encode(input: &[u8], out: &mut Vec<u8>) {
108 let mut acc = 0u64;
109 let mut bits = 0u8;
110 for b in input {
111 let (code, len) = CODES[*b as usize];
112 acc = (acc << len) | code as u64;
113 bits += len;
114 while bits >= 8 {
115 bits -= 8;
116 out.push((acc >> bits) as u8);
117 }
118 acc &= (1u64 << bits) - 1;
119 }
120 if bits > 0 {
121 out.push(((acc << (8 - bits)) | ((1 << (8 - bits)) - 1)) as u8);
122 }
123}
124#[derive(Clone, Copy)]
125struct Node {
126 child: [usize; 2],
127 symbol: Option<u16>,
128}
129fn trie() -> &'static [Node] {
130 static TREE: std::sync::OnceLock<Vec<Node>> = std::sync::OnceLock::new();
131 TREE.get_or_init(|| {
132 let mut nodes = vec![Node {
133 child: [0; 2],
134 symbol: None,
135 }];
136 for (symbol, (code, len)) in CODES.iter().enumerate() {
137 let mut node = 0;
138 for shift in (0..*len).rev() {
139 let bit = ((code >> shift) & 1) as usize;
140 if nodes[node].child[bit] == 0 {
141 nodes[node].child[bit] = nodes.len();
142 nodes.push(Node {
143 child: [0; 2],
144 symbol: None,
145 });
146 }
147 node = nodes[node].child[bit];
148 }
149 nodes[node].symbol = Some(symbol as u16);
150 }
151 nodes
152 })
153}
154pub fn huffman_decode(input: &[u8], out: &mut Vec<u8>, limit: usize) -> Result<()> {
155 let nodes = trie();
156 let mut node = 0;
157 let mut pending = 0;
158 let mut ones = true;
159 for b in input {
160 for bit in (0..8).rev() {
161 let value = ((b >> bit) & 1) as usize;
162 node = nodes[node].child[value];
163 if node == 0 {
164 return Err(bad());
165 }
166 pending += 1;
167 ones &= value == 1;
168 if let Some(symbol) = nodes[node].symbol {
169 if symbol == 256 || out.len() >= limit {
170 return Err(bad());
171 }
172 out.push(symbol as u8);
173 node = 0;
174 pending = 0;
175 ones = true;
176 }
177 }
178 }
179 if pending > 7 || !ones {
180 return Err(bad());
181 }
182 Ok(())
183}
184fn string(input: &[u8], pos: &mut usize, limit: usize) -> Result<Vec<u8>> {
185 let huffman = *input.get(*pos).ok_or_else(bad)? & 128 != 0;
186 let n = integer(input, pos, 7)?;
187 let end = pos.checked_add(n).ok_or_else(bad)?;
188 let raw = input.get(*pos..end).ok_or_else(bad)?;
189 *pos = end;
190 let mut out = Vec::new();
191 if huffman {
192 huffman_decode(raw, &mut out, limit)?;
193 } else {
194 if n > limit {
195 return Err(bad());
196 }
197 out.extend_from_slice(raw);
198 }
199 Ok(out)
200}
201fn emit_string(value: &[u8], out: &mut Vec<u8>) {
202 let bits: usize = value.iter().map(|b| CODES[*b as usize].1 as usize).sum();
203 let n = bits.div_ceil(8);
204 if n < value.len() {
205 encode_integer(n, 7, 128, out);
206 huffman_encode(value, out);
207 } else {
208 encode_integer(value.len(), 7, 0, out);
209 out.extend_from_slice(value);
210 }
211}
212#[derive(Debug)]
213struct Table {
214 slots: Vec<Header>,
215 used: usize,
216 bytes: usize,
217 max: usize,
218}
219impl Table {
220 fn new(max: usize) -> Self {
221 Self {
222 slots: Vec::new(),
223 used: 0,
224 bytes: 0,
225 max,
226 }
227 }
228 fn resize(&mut self, max: usize) {
229 self.max = max;
230 while self.bytes > max {
231 self.evict();
232 }
233 }
234 fn evict(&mut self) {
235 self.used -= 1;
236 let h = &self.slots[self.used];
237 self.bytes -= h.name.len() + h.value.len() + 32;
238 }
239 fn add(&mut self, name: &str, value: &[u8]) {
240 let size = name.len() + value.len() + 32;
241 if size > self.max {
242 self.used = 0;
243 self.bytes = 0;
244 return;
245 }
246 while self.bytes + size > self.max {
247 self.evict();
248 }
249 if self.used == self.slots.len() {
250 self.slots.push(Header::new("", []));
251 }
252 let h = &mut self.slots[self.used];
253 h.name.clear();
254 h.name.push_str(name);
255 h.value.clear();
256 h.value.extend_from_slice(value);
257 self.used += 1;
258 self.slots[..self.used].rotate_right(1);
259 self.bytes += size;
260 }
261 fn get(&self, index: usize) -> Result<(&str, &[u8])> {
262 if index == 0 {
263 return Err(bad());
264 }
265 if index <= 61 {
266 let (n, v) = STATIC[index - 1];
267 Ok((n, v.as_bytes()))
268 } else {
269 self.slots
270 .get(index - 62)
271 .filter(|_| index - 62 < self.used)
272 .map(|h| (h.name.as_str(), h.value.as_slice()))
273 .ok_or_else(bad)
274 }
275 }
276 fn find(&self, name: &str, value: Option<&[u8]>) -> Option<usize> {
277 (1..=61 + self.used).find(|i| {
278 let (n, v) = self.get(*i).unwrap();
279 n == name && value.is_none_or(|x| x == v)
280 })
281 }
282}
283pub struct Decoder {
284 table: Table,
285 allowed: usize,
286 pub max_list_size: usize,
287 failed: bool,
288}
289impl Decoder {
290 pub fn new(table_size: usize, max_list_size: usize) -> Self {
291 Self {
292 table: Table::new(table_size),
293 allowed: table_size,
294 max_list_size,
295 failed: false,
296 }
297 }
298 pub fn set_allowed(&mut self, size: usize) {
301 self.allowed = size;
302 }
303 pub fn decode(&mut self, input: &[u8], out: &mut Vec<Header>) -> Result<()> {
304 if self.failed {
305 return Err(bad());
306 }
307 let result = self.decode_inner(input, out);
308 if result.is_err() {
309 self.failed = true;
310 }
311 result
312 }
313 fn decode_inner(&mut self, input: &[u8], out: &mut Vec<Header>) -> Result<()> {
314 out.clear();
315 let mut pos = 0;
316 let mut size = 0;
317 let mut fields = false;
318 while pos < input.len() {
319 let b = input[pos];
320 if b & 0xe0 == 0x20 {
321 if fields {
322 return Err(bad());
323 }
324 let n = integer(input, &mut pos, 5)?;
325 if n > self.allowed {
326 return Err(bad());
327 }
328 self.table.resize(n);
329 continue;
330 }
331 fields = true;
332 let header = if b & 128 != 0 {
333 let index = integer(input, &mut pos, 7)?;
334 let (n, v) = self.table.get(index)?;
335 Header {
336 name: n.to_string(),
337 value: v.to_vec(),
338 }
339 } else {
340 let indexed = b & 64 != 0;
341 let index = integer(input, &mut pos, if indexed { 6 } else { 4 })?;
342 let name = if index == 0 {
343 String::from_utf8(string(
344 input,
345 &mut pos,
346 self.max_list_size.saturating_sub(size),
347 )?)
348 .map_err(|_| bad())?
349 } else {
350 self.table.get(index)?.0.to_string()
351 };
352 let value = string(
353 input,
354 &mut pos,
355 self.max_list_size.saturating_sub(size + name.len()),
356 )?;
357 if indexed {
358 self.table.add(&name, &value);
359 }
360 Header { name, value }
361 };
362 size = size
363 .checked_add(header.name.len() + header.value.len() + 32)
364 .ok_or_else(bad)?;
365 if size > self.max_list_size {
366 return Err(Error::new("ENHANCE_YOUR_CALM", "header list limit"));
367 }
368 out.push(header);
369 }
370 Ok(())
371 }
372}
373pub struct Encoder {
374 table: Table,
375 pending: Option<(usize, usize)>,
376}
377impl Encoder {
378 pub fn new(table_size: usize) -> Self {
379 Self {
380 table: Table::new(table_size),
381 pending: None,
382 }
383 }
384 pub fn set_table_size(&mut self, size: usize) {
385 self.table.resize(size);
386 self.pending = Some((self.pending.map_or(size, |(min, _)| min.min(size)), size));
387 }
388 pub fn encode(&mut self, headers: &[Header], out: &mut Vec<u8>) {
389 if let Some((min, last)) = self.pending.take() {
390 encode_integer(min, 5, 0x20, out);
391 if last != min {
392 encode_integer(last, 5, 0x20, out);
393 }
394 }
395 for h in headers {
396 let sensitive = matches!(
397 h.name.as_str(),
398 "authorization" | "proxy-authorization" | "cookie" | "set-cookie"
399 );
400 if !sensitive && let Some(index) = self.table.find(&h.name, Some(&h.value)) {
401 encode_integer(index, 7, 128, out);
402 continue;
403 }
404 let index = self.table.find(&h.name, None).unwrap_or(0);
405 encode_integer(
406 index,
407 if sensitive { 4 } else { 6 },
408 if sensitive { 16 } else { 64 },
409 out,
410 );
411 if index == 0 {
412 emit_string(h.name.as_bytes(), out);
413 }
414 emit_string(&h.value, out);
415 if !sensitive {
416 self.table.add(&h.name, &h.value);
417 }
418 }
419 }
420}