2 * nghttp2 - HTTP/2 C Library
4 * Copyright (c) 2013 Tatsuhiro Tsujikawa
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30 #endif /* HAVE_CONFIG_H */
32 #include <nghttp2/nghttp2.h>
34 #include "nghttp2_hd_huffman.h"
35 #include "nghttp2_buf.h"
36 #include "nghttp2_mem.h"
38 #define NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE NGHTTP2_DEFAULT_HEADER_TABLE_SIZE
39 #define NGHTTP2_HD_ENTRY_OVERHEAD 32
41 /* The maximum length of one name/value pair. This is the sum of the
42 length of name and value. This is not specified by the spec. We
43 just chose the arbitrary size */
44 #define NGHTTP2_HD_MAX_NV 65536
46 /* Default size of maximum table buffer size for encoder. Even if
47 remote decoder notifies larger buffer size for its decoding,
48 encoder only uses the memory up to this value. */
49 #define NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE (1 << 12)
51 /* Exported for unit test */
52 #define NGHTTP2_STATIC_TABLE_LENGTH 61
54 /* Generated by genlibtokenlookup.py */
56 NGHTTP2_TOKEN__AUTHORITY = 0,
57 NGHTTP2_TOKEN__METHOD = 1,
58 NGHTTP2_TOKEN__PATH = 3,
59 NGHTTP2_TOKEN__SCHEME = 5,
60 NGHTTP2_TOKEN__STATUS = 7,
61 NGHTTP2_TOKEN_ACCEPT_CHARSET = 14,
62 NGHTTP2_TOKEN_ACCEPT_ENCODING = 15,
63 NGHTTP2_TOKEN_ACCEPT_LANGUAGE = 16,
64 NGHTTP2_TOKEN_ACCEPT_RANGES = 17,
65 NGHTTP2_TOKEN_ACCEPT = 18,
66 NGHTTP2_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN = 19,
67 NGHTTP2_TOKEN_AGE = 20,
68 NGHTTP2_TOKEN_ALLOW = 21,
69 NGHTTP2_TOKEN_AUTHORIZATION = 22,
70 NGHTTP2_TOKEN_CACHE_CONTROL = 23,
71 NGHTTP2_TOKEN_CONTENT_DISPOSITION = 24,
72 NGHTTP2_TOKEN_CONTENT_ENCODING = 25,
73 NGHTTP2_TOKEN_CONTENT_LANGUAGE = 26,
74 NGHTTP2_TOKEN_CONTENT_LENGTH = 27,
75 NGHTTP2_TOKEN_CONTENT_LOCATION = 28,
76 NGHTTP2_TOKEN_CONTENT_RANGE = 29,
77 NGHTTP2_TOKEN_CONTENT_TYPE = 30,
78 NGHTTP2_TOKEN_COOKIE = 31,
79 NGHTTP2_TOKEN_DATE = 32,
80 NGHTTP2_TOKEN_ETAG = 33,
81 NGHTTP2_TOKEN_EXPECT = 34,
82 NGHTTP2_TOKEN_EXPIRES = 35,
83 NGHTTP2_TOKEN_FROM = 36,
84 NGHTTP2_TOKEN_HOST = 37,
85 NGHTTP2_TOKEN_IF_MATCH = 38,
86 NGHTTP2_TOKEN_IF_MODIFIED_SINCE = 39,
87 NGHTTP2_TOKEN_IF_NONE_MATCH = 40,
88 NGHTTP2_TOKEN_IF_RANGE = 41,
89 NGHTTP2_TOKEN_IF_UNMODIFIED_SINCE = 42,
90 NGHTTP2_TOKEN_LAST_MODIFIED = 43,
91 NGHTTP2_TOKEN_LINK = 44,
92 NGHTTP2_TOKEN_LOCATION = 45,
93 NGHTTP2_TOKEN_MAX_FORWARDS = 46,
94 NGHTTP2_TOKEN_PROXY_AUTHENTICATE = 47,
95 NGHTTP2_TOKEN_PROXY_AUTHORIZATION = 48,
96 NGHTTP2_TOKEN_RANGE = 49,
97 NGHTTP2_TOKEN_REFERER = 50,
98 NGHTTP2_TOKEN_REFRESH = 51,
99 NGHTTP2_TOKEN_RETRY_AFTER = 52,
100 NGHTTP2_TOKEN_SERVER = 53,
101 NGHTTP2_TOKEN_SET_COOKIE = 54,
102 NGHTTP2_TOKEN_STRICT_TRANSPORT_SECURITY = 55,
103 NGHTTP2_TOKEN_TRANSFER_ENCODING = 56,
104 NGHTTP2_TOKEN_USER_AGENT = 57,
105 NGHTTP2_TOKEN_VARY = 58,
106 NGHTTP2_TOKEN_VIA = 59,
107 NGHTTP2_TOKEN_WWW_AUTHENTICATE = 60,
109 NGHTTP2_TOKEN_CONNECTION,
110 NGHTTP2_TOKEN_KEEP_ALIVE,
111 NGHTTP2_TOKEN_PROXY_CONNECTION,
112 NGHTTP2_TOKEN_UPGRADE
116 NGHTTP2_HD_FLAG_NONE = 0,
117 /* Indicates name was dynamically allocated and must be freed */
118 NGHTTP2_HD_FLAG_NAME_ALLOC = 1,
119 /* Indicates value was dynamically allocated and must be freed */
120 NGHTTP2_HD_FLAG_VALUE_ALLOC = 1 << 1,
121 /* Indicates that the name was gifted to the entry and no copying
123 NGHTTP2_HD_FLAG_NAME_GIFT = 1 << 2,
124 /* Indicates that the value was gifted to the entry and no copying
126 NGHTTP2_HD_FLAG_VALUE_GIFT = 1 << 3
131 /* nghttp2_token value for nv.name. It could be -1 if we have no
132 token for that header field name. */
134 /* Reference count */
140 nghttp2_hd_entry **buffer;
144 } nghttp2_hd_ringbuf;
147 NGHTTP2_HD_OPCODE_NONE,
148 NGHTTP2_HD_OPCODE_INDEXED,
149 NGHTTP2_HD_OPCODE_NEWNAME,
150 NGHTTP2_HD_OPCODE_INDNAME
154 NGHTTP2_HD_STATE_OPCODE,
155 NGHTTP2_HD_STATE_READ_TABLE_SIZE,
156 NGHTTP2_HD_STATE_READ_INDEX,
157 NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN,
158 NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN,
159 NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF,
160 NGHTTP2_HD_STATE_NEWNAME_READ_NAME,
161 NGHTTP2_HD_STATE_CHECK_VALUELEN,
162 NGHTTP2_HD_STATE_READ_VALUELEN,
163 NGHTTP2_HD_STATE_READ_VALUEHUFF,
164 NGHTTP2_HD_STATE_READ_VALUE
165 } nghttp2_hd_inflate_state;
168 NGHTTP2_HD_WITH_INDEXING,
169 NGHTTP2_HD_WITHOUT_INDEXING,
170 NGHTTP2_HD_NEVER_INDEXING
171 } nghttp2_hd_indexing_mode;
174 /* dynamic header table */
175 nghttp2_hd_ringbuf hd_table;
176 /* Memory allocator */
178 /* Abstract buffer size of hd_table as described in the spec. This
179 is the sum of length of name/value in hd_table +
180 NGHTTP2_HD_ENTRY_OVERHEAD bytes overhead per each entry. */
181 size_t hd_table_bufsize;
182 /* The effective header table size. */
183 size_t hd_table_bufsize_max;
184 /* If inflate/deflate error occurred, this value is set to 1 and
185 further invocation of inflate/deflate will fail with
186 NGHTTP2_ERR_HEADER_COMP. */
188 } nghttp2_hd_context;
190 struct nghttp2_hd_deflater {
191 nghttp2_hd_context ctx;
192 /* The upper limit of the header table size the deflater accepts. */
193 size_t deflate_hd_table_bufsize_max;
194 /* Minimum header table size notified in the next context update */
195 size_t min_hd_table_bufsize_max;
196 /* If nonzero, send header table size using encoding context update
197 in the next deflate process */
198 uint8_t notify_table_size_change;
201 struct nghttp2_hd_inflater {
202 nghttp2_hd_context ctx;
205 /* Stores current state of huffman decoding */
206 nghttp2_hd_huff_decode_context huff_decode_ctx;
207 /* Pointer to the nghttp2_hd_entry which is used current header
208 emission. This is required because in some cases the
209 ent_keep->ref == 0 and we have to keep track of it. */
210 nghttp2_hd_entry *ent_keep;
211 /* Pointer to the name/value pair buffer which is used in the
212 current header emission. */
214 /* The number of bytes to read */
216 /* The index in indexed repr or indexed name */
218 /* The length of new name encoded in literal. For huffman encoded
219 string, this is the length after it is decoded. */
221 /* The maximum header table size the inflater supports. This is the
222 same value transmitted in SETTINGS_HEADER_TABLE_SIZE */
223 size_t settings_hd_table_bufsize_max;
224 /* The number of next shift to decode integer */
226 nghttp2_hd_opcode opcode;
227 nghttp2_hd_inflate_state state;
228 /* nonzero if string is huffman encoded */
229 uint8_t huffman_encoded;
230 /* nonzero if deflater requires that current entry is indexed */
231 uint8_t index_required;
232 /* nonzero if deflater requires that current entry must not be
238 * Initializes the |ent| members. If NGHTTP2_HD_FLAG_NAME_ALLOC bit
239 * set in the |flags|, the content pointed by the |name| with length
240 * |namelen| is copied. Likewise, if NGHTTP2_HD_FLAG_VALUE_ALLOC bit
241 * set in the |flags|, the content pointed by the |value| with length
242 * |valuelen| is copied. The |token| is enum number looked up by
243 * |name|. It could be -1 if we don't have that enum value.
245 * This function returns 0 if it succeeds, or one of the following
246 * negative error codes:
251 int nghttp2_hd_entry_init(nghttp2_hd_entry *ent, uint8_t flags, uint8_t *name,
252 size_t namelen, uint8_t *value, size_t valuelen,
253 int token, nghttp2_mem *mem);
255 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent, nghttp2_mem *mem);
258 * Initializes |deflater| for deflating name/values pairs.
260 * The encoder only uses up to
261 * NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE bytes for header table
262 * even if the larger value is specified later in
263 * nghttp2_hd_change_table_size().
265 * This function returns 0 if it succeeds, or one of the following
266 * negative error codes:
271 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem);
274 * Initializes |deflater| for deflating name/values pairs.
276 * The encoder only uses up to |deflate_hd_table_bufsize_max| bytes
277 * for header table even if the larger value is specified later in
278 * nghttp2_hd_change_table_size().
280 * This function returns 0 if it succeeds, or one of the following
281 * negative error codes:
286 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater,
287 size_t deflate_hd_table_bufsize_max,
291 * Deallocates any resources allocated for |deflater|.
293 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater);
296 * Deflates the |nva|, which has the |nvlen| name/value pairs, into
299 * This function expands |bufs| as necessary to store the result. If
300 * buffers is full and the process still requires more space, this
301 * funtion fails and returns NGHTTP2_ERR_HEADER_COMP.
303 * After this function returns, it is safe to delete the |nva|.
305 * This function returns 0 if it succeeds, or one of the following
306 * negative error codes:
310 * NGHTTP2_ERR_HEADER_COMP
311 * Deflation process has failed.
312 * NGHTTP2_ERR_BUFFER_ERROR
313 * Out of buffer space.
315 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater,
316 nghttp2_bufs *bufs, const nghttp2_nv *nva,
320 * Initializes |inflater| for inflating name/values pairs.
322 * This function returns 0 if it succeeds, or one of the following
323 * negative error codes:
325 * :enum:`NGHTTP2_ERR_NOMEM`
328 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem);
331 * Deallocates any resources allocated for |inflater|.
333 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater);
336 * Similar to nghttp2_hd_inflate_hd(), but this takes additional
337 * output parameter |token|. On successful header emission, it
338 * contains nghttp2_token value for nv_out->name. It could be -1 if
339 * we don't have enum value for the name. Other than that return
340 * values and semantics are the same as nghttp2_hd_inflate_hd().
342 ssize_t nghttp2_hd_inflate_hd2(nghttp2_hd_inflater *inflater,
343 nghttp2_nv *nv_out, int *inflate_flags,
344 int *token, uint8_t *in, size_t inlen,
347 /* For unittesting purpose */
348 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t index,
349 nghttp2_nv *nv, int indexing_mode);
351 /* For unittesting purpose */
352 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv,
355 /* For unittesting purpose */
356 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size);
358 /* For unittesting purpose */
359 nghttp2_hd_entry *nghttp2_hd_table_get(nghttp2_hd_context *context,
362 /* For unittesting purpose */
363 ssize_t nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr, int *final,
364 uint32_t initial, size_t shift, uint8_t *in,
365 uint8_t *last, size_t prefix);
367 /* Huffman encoding/decoding functions */
370 * Counts the required bytes to encode |src| with length |len|.
372 * This function returns the number of required bytes to encode given
373 * data, including padding of prefix of terminal symbol code. This
374 * function always succeeds.
376 size_t nghttp2_hd_huff_encode_count(const uint8_t *src, size_t len);
379 * Encodes the given data |src| with length |srclen| to the |bufs|.
380 * This function expands extra buffers in |bufs| if necessary.
382 * This function returns 0 if it succeeds, or one of the following
383 * negative error codes:
387 * NGHTTP2_ERR_BUFFER_ERROR
388 * Out of buffer space.
390 int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src,
393 void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx);
396 * Decodes the given data |src| with length |srclen|. The |ctx| must
397 * be initialized by nghttp2_hd_huff_decode_context_init(). The result
398 * will be added to |dest|. This function may expand |dest| as
399 * needed. The caller is responsible to release the memory of |dest|
400 * by calling nghttp2_bufs_free().
402 * The caller must set the |final| to nonzero if the given input is
405 * This function returns the number of read bytes from the |in|.
407 * If this function fails, it returns one of the following negative
412 * NGHTTP2_ERR_BUFFER_ERROR
413 * Maximum buffer capacity size exceeded.
414 * NGHTTP2_ERR_HEADER_COMP
415 * Decoding process has failed.
417 ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx,
418 nghttp2_bufs *bufs, const uint8_t *src,
419 size_t srclen, int final);
421 #endif /* NGHTTP2_HD_H */