httlib_hpack/encoder/mod.rs
1//! Provides an implementation of the [HPACK] encoder.
2//!
3//! The encoder performs the task of data compression. It converts the data from
4//! its original readable form into an optimized byte sequence by applying the
5//! rules defined in the [HPACK] specification.
6//!
7//! The HPACK encoding has specific rules for representing integer and string
8//! primitive types.
9//!
10//! * [Integer representation] defines the rules for encoding integer numbers.
11//! Integers are used to represent name indexes, header field indexes, or
12//! character string lengths.
13//!
14//! * [String literal representation] defines the rules for encoding string
15//! literals. With these, we encode the header name and value literals. The
16//! content of these rules can be written in plain text format or encoded with
17//! the [Huffman algorithm].
18//!
19//! With these basic rules, HPACK defines the binary formats for the
20//! representation of the actual headers.
21//!
22//! * [Indexed header field representation] represents fully indexed headers.
23//! These are the headers that are stored in the indexing table under specific
24//! index numbers. Since both the header name and value are stored in the
25//! indexing table, only this index number is encoded. Such headers are really
26//! minimal and therefore optimal in terms of performance.
27//!
28//! * [Literal header field representation] defines headers that are not or
29//! only partially indexed. If the header field name matches the header field
30//! name of an entry stored in the static or dynamic table, the header field
31//! name can be displayed using the index of this entry. Otherwise, the header
32//! field name is displayed as a string literal. Header values are always
33//! displayed as a string literal. Such headers can be marked as "index", "do
34//! not index" or "never index". The latter tells us that the data is
35//! sensitive and that the entity should handle it with some restrictions
36//! (e.g.: protect it with a password).
37//!
38//! HPACK is designed as a single-standing mechanism that can also be used
39//! outside the HTTP/2 protocol. For this reason, the specification provides a
40//! rule for signaling changes related to the allowed size of the dynamic table.
41//!
42//! * [Dynamic table size update] defines the rule for signaling changes in the
43//! size of the dynamic table. Such a change is signaled by the encoder, while
44//! the limit must be less than or equal to the limit determined by the protocol
45//! using HPACK. In HTTP/2 this limit is the last value of the
46//! [SETTINGS_HEADER_TABLE_SIZE] received by the decoder and acknowledged by the
47//! encoder. Encoder and decoder use the HTTP/2 protocol to communicate the
48//! change in table size and if the change is accepted at both ends, the encoder
49//! applies the change and reports it to the decoder using the HPACK mechanism.
50//!
51//! These five rules, with some additional conditional rules described by the
52//! HPACK specification, define the HPACK encoder.
53//!
54//! [HPACK]: https://tools.ietf.org/html/rfc7541
55//! [HTTP/2]: https://tools.ietf.org/html/rfc7540
56//! [Integer representation]: https://tools.ietf.org/html/rfc7541#section-5.1
57//! [String literal representation]: https://tools.ietf.org/html/rfc7541#section-5.2
58//! [Indexed header field representation]: https://tools.ietf.org/html/rfc7541#section-6.1
59//! [Literal header field representation]: https://tools.ietf.org/html/rfc7541#section-6.2
60//! [Dynamic table size update]: https://tools.ietf.org/html/rfc7541#section-6.3
61//! [SETTINGS_HEADER_TABLE_SIZE]: https://tools.ietf.org/html/rfc7540#section-6.5.2
62//! [Huffman algorithm]: https://dev.to/xpepermint/hpack-huffman-encoder-3i7c
63
64mod error;
65mod input;
66mod primitives;
67
68pub use error::*;
69pub use input::*;
70use primitives::*;
71use crate::table::Table;
72
73/// Provides the encoding engine for HTTP/2 headers.
74///
75/// Since headers in HPACK can be encoded in multiple ways, the encoder provides
76/// multiple methods for encoding headers. A developer is responsible to
77/// carefully choose between them to achieve the best encoding performance.
78#[derive(Debug)]
79pub struct Encoder<'a> {
80 /// A store for the static and the dynamic headers.
81 table: Table<'a>,
82}
83
84impl<'a> Encoder<'a> {
85 /// A flag indicating to encode header name with Huffman algorithm (`0x1`).
86 pub const HUFFMAN_NAME: u8 = 0x1;
87
88 /// A flag indicating to encode header value with Huffman algorithm (`0x2`).
89 pub const HUFFMAN_VALUE: u8 = 0x2;
90
91 /// A flag indicating to index literal header field (`0x4`).
92 pub const WITH_INDEXING: u8 = 0x4;
93
94 /// A flag indicating to never index literal header field (`0x8`).
95 pub const NEVER_INDEXED: u8 = 0x8;
96
97 /// A flag indicating to find the best literal representation by searching
98 /// the indexing table (`0x10`).
99 pub const BEST_FORMAT: u8 = 0x10;
100
101 /// Returns a new encoder instance with the provided maximum allowed size of
102 /// the dynamic table.
103 pub fn with_dynamic_size(max_dynamic_size: u32) -> Self {
104 Self {
105 table: Table::with_dynamic_size(max_dynamic_size),
106 }
107 }
108
109 /// Returns the maximum allowed size of the dynamic table.
110 pub fn max_dynamic_size(&mut self) -> u32 {
111 self.table.max_dynamic_size()
112 }
113
114 /// Encodes headers into the HPACK's header field representation format.
115 ///
116 /// By default headers are represented without indexing and Huffman encoding
117 /// is not enabled for literals. We can configure the encoder by providing
118 /// byte `flags`:
119 ///
120 /// * `0x1`: Use Huffman to encode header name.
121 /// * `0x2`: Use Huffman to encode header value.
122 /// * `0x4`: Literal header field with incremental indexing ([6.2.1.]).
123 /// * `0x8`: Literal header field never indexed ([6.2.3.]).
124 /// * `0x10`: Encode literal as the best representation.
125 ///
126 /// **Example:**
127 ///
128 /// ```rust
129 /// use httlib_hpack::Encoder;
130 ///
131 /// let mut encoder = Encoder::default();
132 /// let mut dst = Vec::new();
133 /// let name = b":method".to_vec();
134 /// let value = b"PATCH".to_vec();
135 /// let flags = 0x2 | 0x4 | 0x10;
136 /// encoder.encode((name, value, flags), &mut dst).unwrap();
137 /// ```
138 ///
139 /// [6.2.1.]: https://tools.ietf.org/html/rfc7541#section-6.2.1
140 /// [6.2.3.]: https://tools.ietf.org/html/rfc7541#section-6.2.3
141 pub fn encode<F>(
142 &mut self,
143 field: F,
144 dst: &mut Vec<u8>,
145 ) -> Result<(), EncoderError>
146 where
147 F: Into<EncoderInput>,
148 {
149 match field.into() {
150 EncoderInput::Indexed(index) => {
151 self.encode_indexed(index, dst)
152 },
153 EncoderInput::IndexedName(index, value, flags) => {
154 self.encode_indexed_name(index, value, flags, dst)
155 },
156 EncoderInput::Literal(name, value, flags) => {
157 if flags & 0x10 == 0x10 {
158 match self.table.find(&name, &value) {
159 Some((index, true)) => {
160 self.encode_indexed(index as u32, dst)
161 },
162 Some((index, false)) => {
163 self.encode_indexed_name(index as u32, value, flags, dst)
164 },
165 None => {
166 self.encode_literal(name, value, flags, dst)
167 },
168 }
169 } else {
170 self.encode_literal(name, value, flags, dst)
171 }
172 },
173 }
174 }
175
176 /// Encodes a header that exists at `index` in the indexing table.
177 ///
178 /// The function converts the header index into HPACK's indexed header field
179 /// representation and writes it into the `dst` buffer.
180 ///
181 /// **Indexed header field representation ([6.1.], figure 5):**
182 ///
183 /// ```txt
184 /// 0 1 2 3 4 5 6 7
185 /// +---+---+---+---+---+---+---+---+
186 /// | 1 | Index (7+) |
187 /// +---+---------------------------+
188 /// ```
189 ///
190 /// [6.1.]: https://tools.ietf.org/html/rfc7541#section-6.1
191 pub fn encode_indexed(
192 &self,
193 index: u32,
194 dst: &mut Vec<u8>,
195 ) -> Result<(), EncoderError> {
196
197 if self.table.get(index).is_none() {
198 return Err(EncoderError::InvalidIndex);
199 }
200
201 encode_integer(index, 0x80, 7, dst)
202 }
203
204 /// Encodes a header where its name is represented with an `index` from the
205 /// indexing table and the `value` is provided in bytes.
206 ///
207 /// This function converts the header into HPACK's literal header field
208 /// representation and writes it into the `dst` buffer.
209 ///
210 /// **Literal header field with incremental indexing ([6.2.1.], figure 6):**
211 ///
212 /// ```txt
213 /// 0 1 2 3 4 5 6 7
214 /// +---+---+---+---+---+---+---+---+
215 /// | 0 | 1 | Index (6+) |
216 /// +---+---+-----------------------+
217 /// | H | Value Length (7+) |
218 /// +---+---------------------------+
219 /// | Value String (Length octets) |
220 /// +-------------------------------+
221 /// ```
222 ///
223 /// **Literal header field without indexing ([6.2.2.], figure 8):**
224 ///
225 /// ```txt
226 /// 0 1 2 3 4 5 6 7
227 /// +---+---+---+---+---+---+---+---+
228 /// | 0 | 0 | 0 | 0 | Index (4+) |
229 /// +---+---+-----------------------+
230 /// | H | Value Length (7+) |
231 /// +---+---------------------------+
232 /// | Value String (Length octets) |
233 /// +-------------------------------+
234 /// ```
235 ///
236 /// **Literal header field never indexed ([6.2.3.], figure 10):**
237 ///
238 /// ```txt
239 /// 0 1 2 3 4 5 6 7
240 /// +---+---+---+---+---+---+---+---+
241 /// | 0 | 0 | 0 | 1 | Index (4+) |
242 /// +---+---+-----------------------+
243 /// | H | Value Length (7+) |
244 /// +---+---------------------------+
245 /// | Value String (Length octets) |
246 /// +-------------------------------+
247 /// ```
248 ///
249 /// By default headers are represented as literals without indexing and
250 /// header's value is encoded as a string. We can configure the encoder by
251 /// providing byte `flags`:
252 ///
253 /// * `0x2`: Use Huffman to encode header value.
254 /// * `0x4`: Literal header field with incremental indexing ([6.2.1.]).
255 /// * `0x8`: Literal header field never indexed ([6.2.3.]).
256 ///
257 /// [6.2.1.]: https://tools.ietf.org/html/rfc7541#section-6.2.1
258 /// [6.2.2.]: https://tools.ietf.org/html/rfc7541#section-6.2.2
259 /// [6.2.3.]: https://tools.ietf.org/html/rfc7541#section-6.2.3
260 pub fn encode_indexed_name(
261 &mut self,
262 index: u32,
263 value: Vec<u8>,
264 flags: u8,
265 dst: &mut Vec<u8>,
266 ) -> Result<(), EncoderError> {
267
268 let name = if let Some(entry) = self.table.get(index) {
269 entry.0.to_vec()
270 } else {
271 return Err(EncoderError::InvalidIndex);
272 };
273
274 if flags & 0x4 == 0x4 {
275 self.table.insert(name, value.clone());
276 encode_integer(index, 0x40, 6, dst)?;
277 } else if flags & 0x8 == 0x8 {
278 encode_integer(index, 0b00010000, 4, dst)?;
279 } else { // without indexing
280 encode_integer(index, 0x0, 4, dst)?;
281 }
282
283 encode_string(value, flags & 0x2 == 0x2, dst)
284 }
285
286 /// Encodes a header where its name and value are provided in bytes.
287 ///
288 /// This function converts the header into HPACK's literal header field
289 /// representation and writes it into the `dst` buffer.
290 ///
291 /// **Literal header field with incremental indexing ([6.2.1.], figure 7):**
292 ///
293 /// ```txt
294 /// 0 1 2 3 4 5 6 7
295 /// +---+---+---+---+---+---+---+---+
296 /// | 0 | 1 | 0 |
297 /// +---+---+-----------------------+
298 /// | H | Name Length (7+) |
299 /// +---+---------------------------+
300 /// | Name String (Length octets) |
301 /// +---+---------------------------+
302 /// | H | Value Length (7+) |
303 /// +---+---------------------------+
304 /// | Value String (Length octets) |
305 /// +-------------------------------+
306 /// ```
307 ///
308 /// **Literal header field without indexing ([6.2.2.], figure 9):**
309 ///
310 /// ```txt
311 /// 0 1 2 3 4 5 6 7
312 /// +---+---+---+---+---+---+---+---+
313 /// | 0 | 0 | 0 | 0 | 0 |
314 /// +---+---+-----------------------+
315 /// | H | Name Length (7+) |
316 /// +---+---------------------------+
317 /// | Name String (Length octets) |
318 /// +---+---------------------------+
319 /// | H | Value Length (7+) |
320 /// +---+---------------------------+
321 /// | Value String (Length octets) |
322 /// +-------------------------------+
323 /// ```
324 ///
325 /// **Literal header field never indexed ([6.2.3.], figure 11):**
326 ///
327 /// ```txt
328 /// 0 1 2 3 4 5 6 7
329 /// +---+---+---+---+---+---+---+---+
330 /// | 0 | 0 | 0 | 1 | 0 |
331 /// +---+---+-----------------------+
332 /// | H | Name Length (7+) |
333 /// +---+---------------------------+
334 /// | Name String (Length octets) |
335 /// +---+---------------------------+
336 /// | H | Value Length (7+) |
337 /// +---+---------------------------+
338 /// | Value String (Length octets) |
339 /// +-------------------------------+
340 /// ```
341 ///
342 /// By default headers are represented as literals without indexing. Heder's
343 /// name and value are encoded as a string. We can configure the encoder by
344 /// providing byte `flags`:
345 ///
346 /// * `0x1`: Use Huffman to encode header name.
347 /// * `0x2`: Use Huffman to encode header value.
348 /// * `0x4`: Literal header field with incremental indexing ([6.2.1.]).
349 /// * `0x8`: Literal header field never indexed ([6.2.3.]).
350 ///
351 /// [6.2.1.]: https://tools.ietf.org/html/rfc7541#section-6.2.1
352 /// [6.2.2.]: https://tools.ietf.org/html/rfc7541#section-6.2.2
353 /// [6.2.3.]: https://tools.ietf.org/html/rfc7541#section-6.2.3
354 pub fn encode_literal(
355 &mut self,
356 name: Vec<u8>,
357 value: Vec<u8>,
358 flags: u8,
359 dst: &mut Vec<u8>,
360 ) -> Result<(), EncoderError> {
361
362 if flags & 0x4 == 0x4 {
363 dst.push(0x40);
364 self.table.insert(name.clone(), value.clone());
365 } else if flags & 0x8 == 0x8 {
366 dst.push(0b00010000);
367 } else { // without indexing
368 dst.push(0x0);
369 }
370
371 encode_string(name, flags & 0x1 == 0x1, dst)?;
372 encode_string(value, flags & 0x2 == 0x2, dst)
373 }
374
375 /// Updates the maximum size of the dynamic table and encodes the new size
376 /// into a dynamic table size signal.
377 ///
378 /// The new maximum size MUST be lower than or equal to the limit determined
379 /// by the protocol using HPACK. In HTTP/2, this limit is the last value of
380 /// the `SETTINGS_HEADER_TABLE_SIZE` received from the decoder and
381 /// acknowledged by the encoder.
382 ///
383 /// **Maximum Dynamic table size change ([6.3.], figure 12):**
384 ///
385 /// ```txt
386 /// 0 1 2 3 4 5 6 7
387 /// +---+---+---+---+---+---+---+---+
388 /// | 0 | 0 | 1 | Max size (5+) |
389 /// +---+---------------------------+
390 /// ```
391 ///
392 /// [6.3]: https://tools.ietf.org/html/rfc7541#section-6.3
393 pub fn update_max_dynamic_size(
394 &mut self,
395 size: u32,
396 dst: &mut Vec<u8>,
397 ) -> Result<(), EncoderError> {
398 self.table.update_max_dynamic_size(size);
399 encode_integer(size, 0b00100000, 5, dst)
400 }
401}
402
403impl<'a> Default for Encoder<'a> {
404 fn default() -> Self {
405 Self {
406 table: Table::default(),
407 }
408 }
409}
410
411#[cfg(test)]
412mod test {
413 use super::*;
414
415 /// Should encode a header that exists in the indexing table into HPACK's
416 /// indexed header field representation ([6.1.], figure 5).
417 ///
418 /// [6.1.]: https://tools.ietf.org/html/rfc7541#section-6.1
419 #[test]
420 fn encodes_indexed() {
421 let mut encoder = Encoder::default();
422 encoder.table.insert(b"name62".to_vec(), b"value62".to_vec()); // add dynamic header
423 let fields = vec![
424 (2, vec![0x80 | 2]), // (:method, GET)
425 (3, vec![0x80 | 3]), // (:method, POST)
426 (14, vec![0x80 | 14]), // (:status, 500)
427 (62, vec![0x80 | 62]), // (name62, value62)
428 ];
429 for (index, res) in fields {
430 let mut dst = Vec::new();
431 encoder.encode(index, &mut dst).unwrap();
432 assert_eq!(dst, res);
433 }
434 assert_eq!(encoder.table.len(), 62); // only one header in dynamic table
435 }
436
437 /// Should encode a header, where its name is represented with an index and
438 /// the value is provided in bytes, into a literal header field
439 /// representation with incremental indexing ([6.2.1.], figure 6).
440 ///
441 /// [6.2.1.]: https://tools.ietf.org/html/rfc7541#section-6.2.1
442 #[test]
443 fn encodes_indexed_name_with_indexing() {
444 let mut encoder = Encoder::default();
445 let mut dst = Vec::new();
446 let field = (
447 2, // index
448 b"PATCH".to_vec(),
449 0x2 | 0x4,
450 );
451 encoder.encode(field, &mut dst).unwrap(); // (:method, PATCH), Huffman
452 assert_eq!(dst[0] & 0b01000000, 64); // with incremental indexing
453 assert_eq!(dst[1] & 0b10000000, 128); // value encoded with Huffman
454 assert_eq!(&dst[2..], vec![215, 14, 251, 216, 255]); // value as huffman sequence
455 assert_eq!(encoder.table.len(), 62); // inserted into indexing table
456 let entry = encoder.table.get(62).unwrap();
457 assert_eq!(entry.0, b":method"); // indexed name
458 assert_eq!(entry.1, b"PATCH"); // indexed value
459 }
460
461 /// Should encode a header, where its name and value are provided in bytes,
462 /// into a literal header field representation with incremental indexing
463 /// ([6.2.1.], figure 7).
464 ///
465 /// [6.2.1.]: https://tools.ietf.org/html/rfc7541#section-6.2.1
466 #[test]
467 fn encodes_literal_with_indexing() {
468 let mut encoder = Encoder::default();
469 let mut dst = Vec::new();
470 let field = (
471 b"foo".to_vec(),
472 b"bar".to_vec(),
473 0x4 | 0x1 | 0x2,
474 );
475 encoder.encode(field, &mut dst).unwrap(); // (huffman(foo), huffman(bar))
476 assert_eq!(dst[0], 0b01000000); // with incremental indexing
477 assert_eq!(&dst[1..4], vec![130, 148, 231]); // name as huffman sequence
478 assert_eq!(&dst[4..], vec![131, 140, 118, 127]); // value as huffman sequence
479 assert_eq!(encoder.table.len(), 62); // inserted into indexing table
480 let entry = encoder.table.get(62).unwrap();
481 assert_eq!(entry.0, b"foo"); // indexed name
482 assert_eq!(entry.1, b"bar"); // indexed value
483 }
484
485 /// Should encode a header, where its name is represented with an index and
486 /// the value is provided in bytes, into a literal header field
487 /// representation without indexing ([6.2.2.], figure 8). The indexing table
488 /// should not be altered.
489 ///
490 /// [6.2.2.]: https://tools.ietf.org/html/rfc7541#section-6.2.2
491 #[test]
492 fn encodes_indexed_name_without_indexing() {
493 let mut encoder = Encoder::default();
494 let mut dst = Vec::new();
495 let field = (13, b"PATCH".to_vec(), 0x0);
496 encoder.encode(field, &mut dst).unwrap(); // (:status, PATCH)
497 assert_eq!(dst[0], 13); // without indexing (matches index value)
498 assert_eq!(&dst[1..], vec![5, 80, 65, 84, 67, 72]); // value as string
499 assert_eq!(encoder.table.len(), 61); // table not altered
500 }
501
502 /// Should encode a header, where its name and value are provided in bytes,
503 /// into a literal header field representation without indexing ([6.2.2.],
504 /// figure 9). The indexing table should not be altered.
505 ///
506 /// [6.2.2.]: https://tools.ietf.org/html/rfc7541#section-6.2.2
507 #[test]
508 fn encodes_literal_without_indexing() {
509 let mut encoder = Encoder::default();
510 let mut dst = Vec::new();
511 let field = (b"foo".to_vec(), b"bar".to_vec(), 0x1);
512 encoder.encode(field, &mut dst).unwrap(); // (huffman(foo), bar)
513 assert_eq!(dst[0], 0); // without indexing
514 assert_eq!(&dst[2..4], vec![148, 231]); // name as string
515 assert_eq!(&dst[4..], vec![3, 98, 97, 114]); // value as string
516 assert_eq!(encoder.table.len(), 61); // table not altered
517 }
518
519 /// Should encode a header, where its name is represented with an index and
520 /// the value is provided in bytes, into a never indexed literal header
521 /// field representation ([6.2.3.], figure 10). The indexing table should
522 /// not be altered.
523 ///
524 /// [6.2.3.]: https://tools.ietf.org/html/rfc7541#section-6.2.3
525 #[test]
526 fn encodes_indexed_name_never_indexed() {
527 let mut encoder = Encoder::default();
528 let mut dst = Vec::new();
529 let field = (13, b"PATCH".to_vec(), 0x8);
530 encoder.encode(field, &mut dst).unwrap(); // (:status, 501)
531 assert_eq!(dst[0] & 0b00010000, 16); // never indexed
532 assert_eq!(&dst[1..], vec![5, 80, 65, 84, 67, 72]); // value as string
533 assert_eq!(encoder.table.len(), 61); // table not altered
534 }
535
536 /// Should encode a header, where its name and value are provided in bytes,
537 /// into a never indexed literal header field representation ([6.2.3.],
538 /// figure 11). The indexing table should not be altered.
539 ///
540 /// [6.2.3.]: https://tools.ietf.org/html/rfc7541#section-6.2.3
541 #[test]
542 fn encodes_literal_never_indexed() {
543 let mut encoder = Encoder::default();
544 let mut dst = Vec::new();
545 let field = (b"foo".to_vec(), b"bar".to_vec(), 0x8);
546 encoder.encode(field, &mut dst).unwrap(); // (foo, bar)
547 assert_eq!(dst[0], 0b00010000); // never indexed
548 assert_eq!(&dst[1..5], vec![3, 102, 111, 111]); // name as string
549 assert_eq!(&dst[5..], vec![3, 98, 97, 114]); // value as string
550 assert_eq!(encoder.table.len(), 61); // table not altered
551 }
552
553 /// Should encode a header, where its name and value are provided in bytes,
554 /// into the best header field representation.
555 #[test]
556 fn encodes_literal_automatically() {
557 let mut encoder = Encoder::default();
558 let fields = vec![
559 ((b":method".to_vec(), b"GET".to_vec(), 0x10), vec![130]), // (:method, GET) => index(2)
560 ((b":method".to_vec(), b"DELETE".to_vec(), 0x10 | 0x4), vec![66, 6, 68, 69, 76, 69, 84, 69]), // (:method, DELETE) => (index(2), DELETE)
561 ((b"a".to_vec(), b"b".to_vec(), 0x10 | 0x1), vec![0, 129, 31, 1, 98]), // (a, b) => (huffman(a), b)
562 ];
563 for (field, res) in fields {
564 let mut dst = Vec::new();
565 encoder.encode(field, &mut dst).unwrap();
566 assert_eq!(dst, res);
567 }
568 assert_eq!(encoder.table.len(), 62); // table altered only once
569 }
570
571 /// Should encode a dynamic table size update signal.
572 #[test]
573 fn updates_max_dynamic_size() {
574 let mut encoder = Encoder::with_dynamic_size(70);
575 encoder.table.insert(b"a".to_vec(), b"a".to_vec()); // size: +34
576 encoder.table.insert(b"b".to_vec(), b"b".to_vec()); // size: +34
577 let mut dst = Vec::new();
578 encoder.update_max_dynamic_size(50, &mut dst).unwrap();
579 assert_eq!(dst[0] & 0b00100000, 32); // size update
580 assert_eq!(dst, vec![63, 19]); // encoded size
581 assert_eq!(encoder.table.dynamic_len(), 1); // 1 header evicted
582 }
583}