lib/nghttp2_hd.h

   1 /*
   2  * nghttp2 - HTTP/2 C Library
   3  *
   4  * Copyright (c) 2013 Tatsuhiro Tsujikawa
   5  *
   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:
  13  *
  14  * The above copyright notice and this permission notice shall be
  15  * included in all copies or substantial portions of the Software.
  16  *
  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.
  24  */
  25 #ifndef NGHTTP2_HD_H
  26 #define NGHTTP2_HD_H
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include <config.h>
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #include <nghttp2/nghttp2.h>
  33
  34 #include "nghttp2_hd_huffman.h"
  35 #include "nghttp2_buf.h"
  36 #include "nghttp2_mem.h"
  37
  38 #define NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE NGHTTP2_DEFAULT_HEADER_TABLE_SIZE
  39 #define NGHTTP2_HD_ENTRY_OVERHEAD 32
  40
  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
  45
  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)
  50
  51 /* Exported for unit test */
  52 extern const size_t NGHTTP2_STATIC_TABLE_LENGTH;
  53
  54 typedef enum {
  55   NGHTTP2_HD_FLAG_NONE = 0,
  56   /* Indicates name was dynamically allocated and must be freed */
  57   NGHTTP2_HD_FLAG_NAME_ALLOC = 1,
  58   /* Indicates value was dynamically allocated and must be freed */
  59   NGHTTP2_HD_FLAG_VALUE_ALLOC = 1 << 1,
  60   /* Indicates that the name was gifted to the entry and no copying
  61      necessary. */
  62   NGHTTP2_HD_FLAG_NAME_GIFT = 1 << 2,
  63   /* Indicates that the value was gifted to the entry and no copying
  64      necessary. */
  65   NGHTTP2_HD_FLAG_VALUE_GIFT = 1 << 3
  66 } nghttp2_hd_flags;
  67
  68 typedef struct {
  69   nghttp2_nv nv;
  70   uint32_t name_hash;
  71   uint32_t value_hash;
  72   /* Reference count */
  73   uint8_t ref;
  74   uint8_t flags;
  75 } nghttp2_hd_entry;
  76
  77 typedef struct {
  78   nghttp2_hd_entry ent;
  79   size_t index;
  80 } nghttp2_hd_static_entry;
  81
  82 typedef struct {
  83   nghttp2_hd_entry **buffer;
  84   size_t mask;
  85   size_t first;
  86   size_t len;
  87 } nghttp2_hd_ringbuf;
  88
  89 typedef enum {
  90   NGHTTP2_HD_OPCODE_NONE,
  91   NGHTTP2_HD_OPCODE_INDEXED,
  92   NGHTTP2_HD_OPCODE_NEWNAME,
  93   NGHTTP2_HD_OPCODE_INDNAME
  94 } nghttp2_hd_opcode;
  95
  96 typedef enum {
  97   NGHTTP2_HD_STATE_OPCODE,
  98   NGHTTP2_HD_STATE_READ_TABLE_SIZE,
  99   NGHTTP2_HD_STATE_READ_INDEX,
 100   NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN,
 101   NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN,
 102   NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF,
 103   NGHTTP2_HD_STATE_NEWNAME_READ_NAME,
 104   NGHTTP2_HD_STATE_CHECK_VALUELEN,
 105   NGHTTP2_HD_STATE_READ_VALUELEN,
 106   NGHTTP2_HD_STATE_READ_VALUEHUFF,
 107   NGHTTP2_HD_STATE_READ_VALUE
 108 } nghttp2_hd_inflate_state;
 109
 110 typedef struct {
 111   /* dynamic header table */
 112   nghttp2_hd_ringbuf hd_table;
 113   /* Memory allocator */
 114   nghttp2_mem *mem;
 115   /* Abstract buffer size of hd_table as described in the spec. This
 116      is the sum of length of name/value in hd_table +
 117      NGHTTP2_HD_ENTRY_OVERHEAD bytes overhead per each entry. */
 118   size_t hd_table_bufsize;
 119   /* The effective header table size. */
 120   size_t hd_table_bufsize_max;
 121   /* If inflate/deflate error occurred, this value is set to 1 and
 122      further invocation of inflate/deflate will fail with
 123      NGHTTP2_ERR_HEADER_COMP. */
 124   uint8_t bad;
 125 } nghttp2_hd_context;
 126
 127 struct nghttp2_hd_deflater {
 128   nghttp2_hd_context ctx;
 129   /* The upper limit of the header table size the deflater accepts. */
 130   size_t deflate_hd_table_bufsize_max;
 131   /* Minimum header table size notified in the next context update */
 132   size_t min_hd_table_bufsize_max;
 133   /* If nonzero, send header table size using encoding context update
 134      in the next deflate process */
 135   uint8_t notify_table_size_change;
 136 };
 137
 138 struct nghttp2_hd_inflater {
 139   nghttp2_hd_context ctx;
 140   /* header buffer */
 141   nghttp2_bufs nvbufs;
 142   /* Stores current state of huffman decoding */
 143   nghttp2_hd_huff_decode_context huff_decode_ctx;
 144   /* Pointer to the nghttp2_hd_entry which is used current header
 145      emission. This is required because in some cases the
 146      ent_keep->ref == 0 and we have to keep track of it. */
 147   nghttp2_hd_entry *ent_keep;
 148   /* Pointer to the name/value pair buffer which is used in the
 149      current header emission. */
 150   uint8_t *nv_keep;
 151   /* The number of bytes to read */
 152   size_t left;
 153   /* The index in indexed repr or indexed name */
 154   size_t index;
 155   /* The length of new name encoded in literal.  For huffman encoded
 156      string, this is the length after it is decoded. */
 157   size_t newnamelen;
 158   /* The maximum header table size the inflater supports. This is the
 159      same value transmitted in SETTINGS_HEADER_TABLE_SIZE */
 160   size_t settings_hd_table_bufsize_max;
 161   /* The number of next shift to decode integer */
 162   size_t shift;
 163   nghttp2_hd_opcode opcode;
 164   nghttp2_hd_inflate_state state;
 165   /* nonzero if string is huffman encoded */
 166   uint8_t huffman_encoded;
 167   /* nonzero if deflater requires that current entry is indexed */
 168   uint8_t index_required;
 169   /* nonzero if deflater requires that current entry must not be
 170      indexed */
 171   uint8_t no_index;
 172 };
 173
 174 /*
 175  * Initializes the |ent| members. If NGHTTP2_HD_FLAG_NAME_ALLOC bit
 176  * set in the |flags|, the content pointed by the |name| with length
 177  * |namelen| is copied. Likewise, if NGHTTP2_HD_FLAG_VALUE_ALLOC bit
 178  * set in the |flags|, the content pointed by the |value| with length
 179  * |valuelen| is copied.  The |name_hash| and |value_hash| are hash
 180  * value for |name| and |value| respectively.  The hash function is
 181  * defined in nghttp2_hd.c.
 182  *
 183  * This function returns 0 if it succeeds, or one of the following
 184  * negative error codes:
 185  *
 186  * NGHTTP2_ERR_NOMEM
 187  *     Out of memory.
 188  */
 189 int nghttp2_hd_entry_init(nghttp2_hd_entry *ent, uint8_t flags, uint8_t *name,
 190                           size_t namelen, uint8_t *value, size_t valuelen,
 191                           uint32_t name_hash, uint32_t value_hash,
 192                           nghttp2_mem *mem);
 193
 194 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent, nghttp2_mem *mem);
 195
 196 /*
 197  * Initializes |deflater| for deflating name/values pairs.
 198  *
 199  * The encoder only uses up to
 200  * NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE bytes for header table
 201  * even if the larger value is specified later in
 202  * nghttp2_hd_change_table_size().
 203  *
 204  * This function returns 0 if it succeeds, or one of the following
 205  * negative error codes:
 206  *
 207  * NGHTTP2_ERR_NOMEM
 208  *     Out of memory.
 209  */
 210 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem);
 211
 212 /*
 213  * Initializes |deflater| for deflating name/values pairs.
 214  *
 215  * The encoder only uses up to |deflate_hd_table_bufsize_max| bytes
 216  * for header table even if the larger value is specified later in
 217  * nghttp2_hd_change_table_size().
 218  *
 219  * This function returns 0 if it succeeds, or one of the following
 220  * negative error codes:
 221  *
 222  * NGHTTP2_ERR_NOMEM
 223  *     Out of memory.
 224  */
 225 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater,
 226                              size_t deflate_hd_table_bufsize_max,
 227                              nghttp2_mem *mem);
 228
 229 /*
 230  * Deallocates any resources allocated for |deflater|.
 231  */
 232 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater);
 233
 234 /*
 235  * Deflates the |nva|, which has the |nvlen| name/value pairs, into
 236  * the |bufs|.
 237  *
 238  * This function expands |bufs| as necessary to store the result. If
 239  * buffers is full and the process still requires more space, this
 240  * funtion fails and returns NGHTTP2_ERR_HEADER_COMP.
 241  *
 242  * After this function returns, it is safe to delete the |nva|.
 243  *
 244  * This function returns 0 if it succeeds, or one of the following
 245  * negative error codes:
 246  *
 247  * NGHTTP2_ERR_NOMEM
 248  *     Out of memory.
 249  * NGHTTP2_ERR_HEADER_COMP
 250  *     Deflation process has failed.
 251  * NGHTTP2_ERR_BUFFER_ERROR
 252  *     Out of buffer space.
 253  */
 254 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater,
 255                                nghttp2_bufs *bufs, const nghttp2_nv *nva,
 256                                size_t nvlen);
 257
 258 /*
 259  * Initializes |inflater| for inflating name/values pairs.
 260  *
 261  * This function returns 0 if it succeeds, or one of the following
 262  * negative error codes:
 263  *
 264  * :enum:`NGHTTP2_ERR_NOMEM`
 265  *     Out of memory.
 266  */
 267 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem);
 268
 269 /*
 270  * Deallocates any resources allocated for |inflater|.
 271  */
 272 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater);
 273
 274 /* For unittesting purpose */
 275 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t index,
 276                                   nghttp2_nv *nv, int inc_indexing);
 277
 278 /* For unittesting purpose */
 279 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv,
 280                                   int inc_indexing);
 281
 282 /* For unittesting purpose */
 283 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size);
 284
 285 /* For unittesting purpose */
 286 nghttp2_hd_entry *nghttp2_hd_table_get(nghttp2_hd_context *context,
 287                                        size_t index);
 288
 289 /* For unittesting purpose */
 290 ssize_t nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr, int *final,
 291                                  uint32_t initial, size_t shift, uint8_t *in,
 292                                  uint8_t *last, size_t prefix);
 293
 294 /* Huffman encoding/decoding functions */
 295
 296 /*
 297  * Counts the required bytes to encode |src| with length |len|.
 298  *
 299  * This function returns the number of required bytes to encode given
 300  * data, including padding of prefix of terminal symbol code. This
 301  * function always succeeds.
 302  */
 303 size_t nghttp2_hd_huff_encode_count(const uint8_t *src, size_t len);
 304
 305 /*
 306  * Encodes the given data |src| with length |srclen| to the |bufs|.
 307  * This function expands extra buffers in |bufs| if necessary.
 308  *
 309  * This function returns 0 if it succeeds, or one of the following
 310  * negative error codes:
 311  *
 312  * NGHTTP2_ERR_NOMEM
 313  *     Out of memory.
 314  * NGHTTP2_ERR_BUFFER_ERROR
 315  *     Out of buffer space.
 316  */
 317 int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src,
 318                            size_t srclen);
 319
 320 void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx);
 321
 322 /*
 323  * Decodes the given data |src| with length |srclen|. The |ctx| must
 324  * be initialized by nghttp2_hd_huff_decode_context_init(). The result
 325  * will be added to |dest|. This function may expand |dest| as
 326  * needed. The caller is responsible to release the memory of |dest|
 327  * by calling nghttp2_bufs_free() or export its content using
 328  * nghttp2_bufs_remove().
 329  *
 330  * The caller must set the |final| to nonzero if the given input is
 331  * the final block.
 332  *
 333  * This function returns the number of read bytes from the |in|.
 334  *
 335  * If this function fails, it returns one of the following negative
 336  * return codes:
 337  *
 338  * NGHTTP2_ERR_NOMEM
 339  *     Out of memory.
 340  * NGHTTP2_ERR_BUFFER_ERROR
 341  *     Maximum buffer capacity size exceeded.
 342  * NGHTTP2_ERR_HEADER_COMP
 343  *     Decoding process has failed.
 344  */
 345 ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx,
 346                                nghttp2_bufs *bufs, const uint8_t *src,
 347                                size_t srclen, int final);
 348
 349 #endif /* NGHTTP2_HD_H */