lib/nghttp2_hd.c

   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 #include "nghttp2_hd.h"
  26
  27 #include <string.h>
  28 #include <assert.h>
  29 #include <stdio.h>
  30
  31 #include "nghttp2_helper.h"
  32 #include "nghttp2_int.h"
  33
  34 #define STATIC_TABLE_LENGTH 61
  35
  36 /* Make scalar initialization form of nghttp2_nv */
  37 #define MAKE_STATIC_ENT(I, N, V, NH, VH)                                       \
  38   {                                                                            \
  39     {                                                                          \
  40       { (uint8_t *) N, (uint8_t *)V, sizeof(N) - 1, sizeof(V) - 1, 0 }         \
  41       , NH, VH, 1, NGHTTP2_HD_FLAG_NONE                                        \
  42     }                                                                          \
  43     , I                                                                        \
  44   }
  45
  46 /* Generated by mkstatictbl.py */
  47 /* Sorted by hash(name) and its table index */
  48 static nghttp2_hd_static_entry static_table[] = {
  49     MAKE_STATIC_ENT(20, "age", "", 96511u, 0u),
  50     MAKE_STATIC_ENT(59, "via", "", 116750u, 0u),
  51     MAKE_STATIC_ENT(32, "date", "", 3076014u, 0u),
  52     MAKE_STATIC_ENT(33, "etag", "", 3123477u, 0u),
  53     MAKE_STATIC_ENT(36, "from", "", 3151786u, 0u),
  54     MAKE_STATIC_ENT(37, "host", "", 3208616u, 0u),
  55     MAKE_STATIC_ENT(44, "link", "", 3321850u, 0u),
  56     MAKE_STATIC_ENT(58, "vary", "", 3612210u, 0u),
  57     MAKE_STATIC_ENT(38, "if-match", "", 34533653u, 0u),
  58     MAKE_STATIC_ENT(41, "if-range", "", 39145613u, 0u),
  59     MAKE_STATIC_ENT(3, ":path", "/", 56997727u, 47u),
  60     MAKE_STATIC_ENT(4, ":path", "/index.html", 56997727u, 2144181430u),
  61     MAKE_STATIC_ENT(21, "allow", "", 92906313u, 0u),
  62     MAKE_STATIC_ENT(49, "range", "", 108280125u, 0u),
  63     MAKE_STATIC_ENT(14, "accept-charset", "", 124285319u, 0u),
  64     MAKE_STATIC_ENT(43, "last-modified", "", 150043680u, 0u),
  65     MAKE_STATIC_ENT(48, "proxy-authorization", "", 329532250u, 0u),
  66     MAKE_STATIC_ENT(57, "user-agent", "", 486342275u, 0u),
  67     MAKE_STATIC_ENT(40, "if-none-match", "", 646073760u, 0u),
  68     MAKE_STATIC_ENT(30, "content-type", "", 785670158u, 0u),
  69     MAKE_STATIC_ENT(16, "accept-language", "", 802785917u, 0u),
  70     MAKE_STATIC_ENT(50, "referer", "", 1085069613u, 0u),
  71     MAKE_STATIC_ENT(51, "refresh", "", 1085444827u, 0u),
  72     MAKE_STATIC_ENT(55, "strict-transport-security", "", 1153852136u, 0u),
  73     MAKE_STATIC_ENT(54, "set-cookie", "", 1237214767u, 0u),
  74     MAKE_STATIC_ENT(56, "transfer-encoding", "", 1274458357u, 0u),
  75     MAKE_STATIC_ENT(17, "accept-ranges", "", 1397189435u, 0u),
  76     MAKE_STATIC_ENT(42, "if-unmodified-since", "", 1454068927u, 0u),
  77     MAKE_STATIC_ENT(46, "max-forwards", "", 1619948695u, 0u),
  78     MAKE_STATIC_ENT(45, "location", "", 1901043637u, 0u),
  79     MAKE_STATIC_ENT(52, "retry-after", "", 1933352567u, 0u),
  80     MAKE_STATIC_ENT(25, "content-encoding", "", 2095084583u, 0u),
  81     MAKE_STATIC_ENT(28, "content-location", "", 2284906121u, 0u),
  82     MAKE_STATIC_ENT(39, "if-modified-since", "", 2302095846u, 0u),
  83     MAKE_STATIC_ENT(18, "accept", "", 2871506184u, 0u),
  84     MAKE_STATIC_ENT(29, "content-range", "", 2878374633u, 0u),
  85     MAKE_STATIC_ENT(22, "authorization", "", 2909397113u, 0u),
  86     MAKE_STATIC_ENT(31, "cookie", "", 2940209764u, 0u),
  87     MAKE_STATIC_ENT(0, ":authority", "", 2962729033u, 0u),
  88     MAKE_STATIC_ENT(35, "expires", "", 2985731892u, 0u),
  89     MAKE_STATIC_ENT(34, "expect", "", 3005803609u, 0u),
  90     MAKE_STATIC_ENT(24, "content-disposition", "", 3027699811u, 0u),
  91     MAKE_STATIC_ENT(26, "content-language", "", 3065240108u, 0u),
  92     MAKE_STATIC_ENT(1, ":method", "GET", 3153018267u, 70454u),
  93     MAKE_STATIC_ENT(2, ":method", "POST", 3153018267u, 2461856u),
  94     MAKE_STATIC_ENT(27, "content-length", "", 3162187450u, 0u),
  95     MAKE_STATIC_ENT(19, "access-control-allow-origin", "", 3297999203u, 0u),
  96     MAKE_STATIC_ENT(5, ":scheme", "http", 3322585695u, 3213448u),
  97     MAKE_STATIC_ENT(6, ":scheme", "https", 3322585695u, 99617003u),
  98     MAKE_STATIC_ENT(7, ":status", "200", 3338091692u, 49586u),
  99     MAKE_STATIC_ENT(8, ":status", "204", 3338091692u, 49590u),
 100     MAKE_STATIC_ENT(9, ":status", "206", 3338091692u, 49592u),
 101     MAKE_STATIC_ENT(10, ":status", "304", 3338091692u, 50551u),
 102     MAKE_STATIC_ENT(11, ":status", "400", 3338091692u, 51508u),
 103     MAKE_STATIC_ENT(12, ":status", "404", 3338091692u, 51512u),
 104     MAKE_STATIC_ENT(13, ":status", "500", 3338091692u, 52469u),
 105     MAKE_STATIC_ENT(53, "server", "", 3389140803u, 0u),
 106     MAKE_STATIC_ENT(47, "proxy-authenticate", "", 3993199572u, 0u),
 107     MAKE_STATIC_ENT(60, "www-authenticate", "", 4051929931u, 0u),
 108     MAKE_STATIC_ENT(23, "cache-control", "", 4086191634u, 0u),
 109     MAKE_STATIC_ENT(15, "accept-encoding", "gzip, deflate", 4127597688u,
 110                     1733326877u),
 111 };
 112
 113 /* Index to the position in static_table */
 114 const size_t static_table_index[] = {
 115     38, 43, 44, 10, 11, 47, 48, 49, 50, 51, 52, 53, 54, 55, 14, 60,
 116     20, 26, 34, 46, 0,  12, 36, 59, 41, 31, 42, 45, 32, 35, 19, 37,
 117     2,  3,  40, 39, 4,  5,  8,  33, 18, 9,  27, 15, 6,  29, 28, 57,
 118     16, 13, 21, 22, 30, 56, 24, 23, 25, 17, 7,  1,  58};
 119
 120 const size_t NGHTTP2_STATIC_TABLE_LENGTH =
 121     sizeof(static_table) / sizeof(static_table[0]);
 122
 123 static int memeq(const void *s1, const void *s2, size_t n) {
 124   const uint8_t *a = (const uint8_t *)s1, *b = (const uint8_t *)s2;
 125   uint8_t c = 0;
 126   while (n > 0) {
 127     c |= (*a++) ^ (*b++);
 128     --n;
 129   }
 130   return c == 0;
 131 }
 132
 133 static uint32_t hash(const uint8_t *s, size_t n) {
 134   uint32_t h = 0;
 135   while (n > 0) {
 136     h = h * 31 + *s++;
 137     --n;
 138   }
 139   return h;
 140 }
 141
 142 int nghttp2_hd_entry_init(nghttp2_hd_entry *ent, uint8_t flags, uint8_t *name,
 143                           size_t namelen, uint8_t *value, size_t valuelen,
 144                           uint32_t name_hash, uint32_t value_hash,
 145                           nghttp2_mem *mem) {
 146   int rv = 0;
 147
 148   /* Since nghttp2_hd_entry is used for indexing, ent->nv.flags always
 149      NGHTTP2_NV_FLAG_NONE */
 150   ent->nv.flags = NGHTTP2_NV_FLAG_NONE;
 151
 152   if ((flags & NGHTTP2_HD_FLAG_NAME_ALLOC) &&
 153       (flags & NGHTTP2_HD_FLAG_NAME_GIFT) == 0) {
 154     if (namelen == 0) {
 155       /* We should not allow empty header field name */
 156       ent->nv.name = NULL;
 157     } else {
 158       ent->nv.name = nghttp2_memdup(name, namelen, mem);
 159       if (ent->nv.name == NULL) {
 160         rv = NGHTTP2_ERR_NOMEM;
 161         goto fail;
 162       }
 163     }
 164   } else {
 165     ent->nv.name = name;
 166   }
 167   if ((flags & NGHTTP2_HD_FLAG_VALUE_ALLOC) &&
 168       (flags & NGHTTP2_HD_FLAG_VALUE_GIFT) == 0) {
 169     if (valuelen == 0) {
 170       ent->nv.value = NULL;
 171     } else {
 172       ent->nv.value = nghttp2_memdup(value, valuelen, mem);
 173       if (ent->nv.value == NULL) {
 174         rv = NGHTTP2_ERR_NOMEM;
 175         goto fail2;
 176       }
 177     }
 178   } else {
 179     ent->nv.value = value;
 180   }
 181   ent->nv.namelen = namelen;
 182   ent->nv.valuelen = valuelen;
 183   ent->ref = 1;
 184   ent->flags = flags;
 185
 186   ent->name_hash = name_hash;
 187   ent->value_hash = value_hash;
 188
 189   return 0;
 190
 191 fail2:
 192   if (flags & NGHTTP2_HD_FLAG_NAME_ALLOC) {
 193     nghttp2_mem_free(mem, ent->nv.name);
 194   }
 195 fail:
 196   return rv;
 197 }
 198
 199 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent, nghttp2_mem *mem) {
 200   assert(ent->ref == 0);
 201   if (ent->flags & NGHTTP2_HD_FLAG_NAME_ALLOC) {
 202     nghttp2_mem_free(mem, ent->nv.name);
 203   }
 204   if (ent->flags & NGHTTP2_HD_FLAG_VALUE_ALLOC) {
 205     nghttp2_mem_free(mem, ent->nv.value);
 206   }
 207 }
 208
 209 static int hd_ringbuf_init(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
 210                            nghttp2_mem *mem) {
 211   size_t size;
 212   for (size = 1; size < bufsize; size <<= 1)
 213     ;
 214   ringbuf->buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
 215   if (ringbuf->buffer == NULL) {
 216     return NGHTTP2_ERR_NOMEM;
 217   }
 218   ringbuf->mask = size - 1;
 219   ringbuf->first = 0;
 220   ringbuf->len = 0;
 221   return 0;
 222 }
 223
 224 static nghttp2_hd_entry *hd_ringbuf_get(nghttp2_hd_ringbuf *ringbuf,
 225                                         size_t idx) {
 226   assert(idx < ringbuf->len);
 227   return ringbuf->buffer[(ringbuf->first + idx) & ringbuf->mask];
 228 }
 229
 230 static int hd_ringbuf_reserve(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
 231                               nghttp2_mem *mem) {
 232   size_t i;
 233   size_t size;
 234   nghttp2_hd_entry **buffer;
 235
 236   if (ringbuf->mask + 1 >= bufsize) {
 237     return 0;
 238   }
 239   for (size = 1; size < bufsize; size <<= 1)
 240     ;
 241   buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
 242   if (buffer == NULL) {
 243     return NGHTTP2_ERR_NOMEM;
 244   }
 245   for (i = 0; i < ringbuf->len; ++i) {
 246     buffer[i] = hd_ringbuf_get(ringbuf, i);
 247   }
 248   nghttp2_mem_free(mem, ringbuf->buffer);
 249   ringbuf->buffer = buffer;
 250   ringbuf->mask = size - 1;
 251   ringbuf->first = 0;
 252   return 0;
 253 }
 254
 255 static void hd_ringbuf_free(nghttp2_hd_ringbuf *ringbuf, nghttp2_mem *mem) {
 256   size_t i;
 257   if (ringbuf == NULL) {
 258     return;
 259   }
 260   for (i = 0; i < ringbuf->len; ++i) {
 261     nghttp2_hd_entry *ent = hd_ringbuf_get(ringbuf, i);
 262     --ent->ref;
 263     nghttp2_hd_entry_free(ent, mem);
 264     nghttp2_mem_free(mem, ent);
 265   }
 266   nghttp2_mem_free(mem, ringbuf->buffer);
 267 }
 268
 269 static int hd_ringbuf_push_front(nghttp2_hd_ringbuf *ringbuf,
 270                                  nghttp2_hd_entry *ent, nghttp2_mem *mem) {
 271   int rv;
 272
 273   rv = hd_ringbuf_reserve(ringbuf, ringbuf->len + 1, mem);
 274
 275   if (rv != 0) {
 276     return rv;
 277   }
 278
 279   ringbuf->buffer[--ringbuf->first & ringbuf->mask] = ent;
 280   ++ringbuf->len;
 281
 282   return 0;
 283 }
 284
 285 static void hd_ringbuf_pop_back(nghttp2_hd_ringbuf *ringbuf) {
 286   assert(ringbuf->len > 0);
 287   --ringbuf->len;
 288 }
 289
 290 static int hd_context_init(nghttp2_hd_context *context, nghttp2_mem *mem) {
 291   int rv;
 292   context->mem = mem;
 293   context->bad = 0;
 294   context->hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
 295   rv = hd_ringbuf_init(&context->hd_table, context->hd_table_bufsize_max /
 296                                                NGHTTP2_HD_ENTRY_OVERHEAD,
 297                        mem);
 298   if (rv != 0) {
 299     return rv;
 300   }
 301
 302   context->hd_table_bufsize = 0;
 303   return 0;
 304 }
 305
 306 static void hd_context_free(nghttp2_hd_context *context) {
 307   hd_ringbuf_free(&context->hd_table, context->mem);
 308 }
 309
 310 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem) {
 311   return nghttp2_hd_deflate_init2(
 312       deflater, NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE, mem);
 313 }
 314
 315 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater,
 316                              size_t deflate_hd_table_bufsize_max,
 317                              nghttp2_mem *mem) {
 318   int rv;
 319   rv = hd_context_init(&deflater->ctx, mem);
 320   if (rv != 0) {
 321     return rv;
 322   }
 323
 324   if (deflate_hd_table_bufsize_max < NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE) {
 325     deflater->notify_table_size_change = 1;
 326     deflater->ctx.hd_table_bufsize_max = deflate_hd_table_bufsize_max;
 327   } else {
 328     deflater->notify_table_size_change = 0;
 329   }
 330
 331   deflater->deflate_hd_table_bufsize_max = deflate_hd_table_bufsize_max;
 332   deflater->min_hd_table_bufsize_max = UINT32_MAX;
 333
 334   return 0;
 335 }
 336
 337 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem) {
 338   int rv;
 339
 340   rv = hd_context_init(&inflater->ctx, mem);
 341   if (rv != 0) {
 342     goto fail;
 343   }
 344
 345   inflater->settings_hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
 346
 347   inflater->ent_keep = NULL;
 348   inflater->nv_keep = NULL;
 349
 350   inflater->opcode = NGHTTP2_HD_OPCODE_NONE;
 351   inflater->state = NGHTTP2_HD_STATE_OPCODE;
 352
 353   rv = nghttp2_bufs_init3(&inflater->nvbufs, NGHTTP2_HD_MAX_NV / 8, 8, 1, 0,
 354                           mem);
 355
 356   if (rv != 0) {
 357     goto nvbufs_fail;
 358   }
 359
 360   inflater->huffman_encoded = 0;
 361   inflater->index = 0;
 362   inflater->left = 0;
 363   inflater->shift = 0;
 364   inflater->newnamelen = 0;
 365   inflater->index_required = 0;
 366   inflater->no_index = 0;
 367
 368   return 0;
 369
 370 nvbufs_fail:
 371   hd_context_free(&inflater->ctx);
 372 fail:
 373   return rv;
 374 }
 375
 376 static void hd_inflate_keep_free(nghttp2_hd_inflater *inflater) {
 377   nghttp2_mem *mem;
 378
 379   mem = inflater->ctx.mem;
 380   if (inflater->ent_keep) {
 381     if (inflater->ent_keep->ref == 0) {
 382       nghttp2_hd_entry_free(inflater->ent_keep, mem);
 383       nghttp2_mem_free(mem, inflater->ent_keep);
 384     }
 385     inflater->ent_keep = NULL;
 386   }
 387
 388   nghttp2_mem_free(mem, inflater->nv_keep);
 389   inflater->nv_keep = NULL;
 390 }
 391
 392 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater) {
 393   hd_context_free(&deflater->ctx);
 394 }
 395
 396 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater) {
 397   hd_inflate_keep_free(inflater);
 398   nghttp2_bufs_free(&inflater->nvbufs);
 399   hd_context_free(&inflater->ctx);
 400 }
 401
 402 static size_t entry_room(size_t namelen, size_t valuelen) {
 403   return NGHTTP2_HD_ENTRY_OVERHEAD + namelen + valuelen;
 404 }
 405
 406 static int emit_indexed_header(nghttp2_nv *nv_out, nghttp2_hd_entry *ent) {
 407   DEBUGF(fprintf(stderr, "inflatehd: header emission: "));
 408   DEBUGF(fwrite(ent->nv.name, ent->nv.namelen, 1, stderr));
 409   DEBUGF(fprintf(stderr, ": "));
 410   DEBUGF(fwrite(ent->nv.value, ent->nv.valuelen, 1, stderr));
 411   DEBUGF(fprintf(stderr, "\n"));
 412   /* ent->ref may be 0. This happens if the encoder emits literal
 413      block larger than header table capacity with indexing. */
 414   *nv_out = ent->nv;
 415   return 0;
 416 }
 417
 418 static int emit_literal_header(nghttp2_nv *nv_out, nghttp2_nv *nv) {
 419   DEBUGF(fprintf(stderr, "inflatehd: header emission: "));
 420   DEBUGF(fwrite(nv->name, nv->namelen, 1, stderr));
 421   DEBUGF(fprintf(stderr, ": "));
 422   DEBUGF(fwrite(nv->value, nv->valuelen, 1, stderr));
 423   DEBUGF(fprintf(stderr, "\n"));
 424   *nv_out = *nv;
 425   return 0;
 426 }
 427
 428 static size_t count_encoded_length(size_t n, size_t prefix) {
 429   size_t k = (1 << prefix) - 1;
 430   size_t len = 0;
 431
 432   if (n < k) {
 433     return 1;
 434   }
 435
 436   n -= k;
 437   ++len;
 438
 439   for (; n >= 128; n >>= 7, ++len)
 440     ;
 441
 442   return len + 1;
 443 }
 444
 445 static size_t encode_length(uint8_t *buf, size_t n, size_t prefix) {
 446   size_t k = (1 << prefix) - 1;
 447   uint8_t *begin = buf;
 448
 449   *buf &= ~k;
 450
 451   if (n < k) {
 452     *buf |= n;
 453     return 1;
 454   }
 455
 456   *buf++ |= k;
 457   n -= k;
 458
 459   for (; n >= 128; n >>= 7) {
 460     *buf++ = (1 << 7) | (n & 0x7f);
 461   }
 462
 463   *buf++ = (uint8_t)n;
 464
 465   return (size_t)(buf - begin);
 466 }
 467
 468 /*
 469  * Decodes |prefix| prefixed integer stored from |in|.  The |last|
 470  * represents the 1 beyond the last of the valid contiguous memory
 471  * region from |in|.  The decoded integer must be less than or equal
 472  * to UINT32_MAX.
 473  *
 474  * If the |initial| is nonzero, it is used as a initial value, this
 475  * function assumes the |in| starts with intermediate data.
 476  *
 477  * An entire integer is decoded successfully, decoded, the |*final| is
 478  * set to nonzero.
 479  *
 480  * This function stores the decoded integer in |*res| if it succeed,
 481  * including partial decoding (in this case, number of shift to make
 482  * in the next call will be stored in |*shift_ptr|) and returns number
 483  * of bytes processed, or returns -1, indicating decoding error.
 484  */
 485 static ssize_t decode_length(uint32_t *res, size_t *shift_ptr, int *final,
 486                              uint32_t initial, size_t shift, uint8_t *in,
 487                              uint8_t *last, size_t prefix) {
 488   uint32_t k = (1 << prefix) - 1;
 489   uint32_t n = initial;
 490   uint8_t *start = in;
 491
 492   *shift_ptr = 0;
 493   *final = 0;
 494
 495   if (n == 0) {
 496     if ((*in & k) != k) {
 497       *res = (*in) & k;
 498       *final = 1;
 499       return 1;
 500     }
 501
 502     n = k;
 503
 504     if (++in == last) {
 505       *res = n;
 506       return (ssize_t)(in - start);
 507     }
 508   }
 509
 510   for (; in != last; ++in, shift += 7) {
 511     uint32_t add = *in & 0x7f;
 512
 513     if ((UINT32_MAX >> shift) < add) {
 514       DEBUGF(fprintf(stderr, "inflate: integer overflow on shift\n"));
 515       return -1;
 516     }
 517
 518     add <<= shift;
 519
 520     if (UINT32_MAX - add < n) {
 521       DEBUGF(fprintf(stderr, "inflate: integer overflow on addition\n"));
 522       return -1;
 523     }
 524
 525     n += add;
 526
 527     if ((*in & (1 << 7)) == 0) {
 528       break;
 529     }
 530   }
 531
 532   *shift_ptr = shift;
 533
 534   if (in == last) {
 535     *res = n;
 536     return (ssize_t)(in - start);
 537   }
 538
 539   *res = n;
 540   *final = 1;
 541   return (ssize_t)(in + 1 - start);
 542 }
 543
 544 static int emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
 545   int rv;
 546   uint8_t *bufp;
 547   size_t blocklen;
 548   uint8_t sb[16];
 549
 550   DEBUGF(fprintf(stderr, "deflatehd: emit table_size=%zu\n", table_size));
 551
 552   blocklen = count_encoded_length(table_size, 5);
 553
 554   if (sizeof(sb) < blocklen) {
 555     return NGHTTP2_ERR_HEADER_COMP;
 556   }
 557
 558   bufp = sb;
 559
 560   *bufp = 0x20u;
 561
 562   encode_length(bufp, table_size, 5);
 563
 564   rv = nghttp2_bufs_add(bufs, sb, blocklen);
 565   if (rv != 0) {
 566     return rv;
 567   }
 568
 569   return 0;
 570 }
 571
 572 static int emit_indexed_block(nghttp2_bufs *bufs, size_t idx) {
 573   int rv;
 574   size_t blocklen;
 575   uint8_t sb[16];
 576   uint8_t *bufp;
 577
 578   blocklen = count_encoded_length(idx + 1, 7);
 579
 580   DEBUGF(fprintf(stderr, "deflatehd: emit indexed index=%zu, %zu bytes\n", idx,
 581                  blocklen));
 582
 583   if (sizeof(sb) < blocklen) {
 584     return NGHTTP2_ERR_HEADER_COMP;
 585   }
 586
 587   bufp = sb;
 588   *bufp = 0x80u;
 589   encode_length(bufp, idx + 1, 7);
 590
 591   rv = nghttp2_bufs_add(bufs, sb, blocklen);
 592   if (rv != 0) {
 593     return rv;
 594   }
 595
 596   return 0;
 597 }
 598
 599 static int emit_string(nghttp2_bufs *bufs, const uint8_t *str, size_t len) {
 600   int rv;
 601   uint8_t sb[16];
 602   uint8_t *bufp;
 603   size_t blocklen;
 604   size_t enclen;
 605   int huffman = 0;
 606
 607   enclen = nghttp2_hd_huff_encode_count(str, len);
 608
 609   if (enclen < len) {
 610     huffman = 1;
 611   } else {
 612     enclen = len;
 613   }
 614
 615   blocklen = count_encoded_length(enclen, 7);
 616
 617   DEBUGF(fprintf(stderr, "deflatehd: emit string str="));
 618   DEBUGF(fwrite(str, len, 1, stderr));
 619   DEBUGF(fprintf(stderr, ", length=%zu, huffman=%d, encoded_length=%zu\n", len,
 620                  huffman, enclen));
 621
 622   if (sizeof(sb) < blocklen) {
 623     return NGHTTP2_ERR_HEADER_COMP;
 624   }
 625
 626   bufp = sb;
 627   *bufp = huffman ? 1 << 7 : 0;
 628   encode_length(bufp, enclen, 7);
 629
 630   rv = nghttp2_bufs_add(bufs, sb, blocklen);
 631   if (rv != 0) {
 632     return rv;
 633   }
 634
 635   if (huffman) {
 636     rv = nghttp2_hd_huff_encode(bufs, str, len);
 637   } else {
 638     assert(enclen == len);
 639     rv = nghttp2_bufs_add(bufs, str, len);
 640   }
 641
 642   return rv;
 643 }
 644
 645 static uint8_t pack_first_byte(int inc_indexing, int no_index) {
 646   if (inc_indexing) {
 647     return 0x40u;
 648   }
 649
 650   if (no_index) {
 651     return 0x10u;
 652   }
 653
 654   return 0;
 655 }
 656
 657 static int emit_indname_block(nghttp2_bufs *bufs, size_t idx,
 658                               const nghttp2_nv *nv, int inc_indexing) {
 659   int rv;
 660   uint8_t *bufp;
 661   size_t blocklen;
 662   uint8_t sb[16];
 663   size_t prefixlen;
 664   int no_index;
 665
 666   no_index = (nv->flags & NGHTTP2_NV_FLAG_NO_INDEX) != 0;
 667
 668   if (inc_indexing) {
 669     prefixlen = 6;
 670   } else {
 671     prefixlen = 4;
 672   }
 673
 674   DEBUGF(fprintf(stderr, "deflatehd: emit indname index=%zu, valuelen=%zu, "
 675                          "indexing=%d, no_index=%d\n",
 676                  idx, nv->valuelen, inc_indexing, no_index));
 677
 678   blocklen = count_encoded_length(idx + 1, prefixlen);
 679
 680   if (sizeof(sb) < blocklen) {
 681     return NGHTTP2_ERR_HEADER_COMP;
 682   }
 683
 684   bufp = sb;
 685
 686   *bufp = pack_first_byte(inc_indexing, no_index);
 687
 688   encode_length(bufp, idx + 1, prefixlen);
 689
 690   rv = nghttp2_bufs_add(bufs, sb, blocklen);
 691   if (rv != 0) {
 692     return rv;
 693   }
 694
 695   rv = emit_string(bufs, nv->value, nv->valuelen);
 696   if (rv != 0) {
 697     return rv;
 698   }
 699
 700   return 0;
 701 }
 702
 703 static int emit_newname_block(nghttp2_bufs *bufs, const nghttp2_nv *nv,
 704                               int inc_indexing) {
 705   int rv;
 706   int no_index;
 707
 708   no_index = (nv->flags & NGHTTP2_NV_FLAG_NO_INDEX) != 0;
 709
 710   DEBUGF(fprintf(stderr, "deflatehd: emit newname namelen=%zu, valuelen=%zu, "
 711                          "indexing=%d, no_index=%d\n",
 712                  nv->namelen, nv->valuelen, inc_indexing, no_index));
 713
 714   rv = nghttp2_bufs_addb(bufs, pack_first_byte(inc_indexing, no_index));
 715   if (rv != 0) {
 716     return rv;
 717   }
 718
 719   rv = emit_string(bufs, nv->name, nv->namelen);
 720   if (rv != 0) {
 721     return rv;
 722   }
 723
 724   rv = emit_string(bufs, nv->value, nv->valuelen);
 725   if (rv != 0) {
 726     return rv;
 727   }
 728
 729   return 0;
 730 }
 731
 732 static nghttp2_hd_entry *add_hd_table_incremental(nghttp2_hd_context *context,
 733                                                   const nghttp2_nv *nv,
 734                                                   uint32_t name_hash,
 735                                                   uint32_t value_hash,
 736                                                   uint8_t entry_flags) {
 737   int rv;
 738   nghttp2_hd_entry *new_ent;
 739   size_t room;
 740   nghttp2_mem *mem;
 741
 742   mem = context->mem;
 743   room = entry_room(nv->namelen, nv->valuelen);
 744
 745   while (context->hd_table_bufsize + room > context->hd_table_bufsize_max &&
 746          context->hd_table.len > 0) {
 747
 748     size_t idx = context->hd_table.len - 1;
 749     nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);
 750
 751     context->hd_table_bufsize -= entry_room(ent->nv.namelen, ent->nv.valuelen);
 752
 753     DEBUGF(fprintf(stderr, "hpack: remove item from header table: "));
 754     DEBUGF(fwrite(ent->nv.name, ent->nv.namelen, 1, stderr));
 755     DEBUGF(fprintf(stderr, ": "));
 756     DEBUGF(fwrite(ent->nv.value, ent->nv.valuelen, 1, stderr));
 757     DEBUGF(fprintf(stderr, "\n"));
 758     hd_ringbuf_pop_back(&context->hd_table);
 759     if (--ent->ref == 0) {
 760       nghttp2_hd_entry_free(ent, mem);
 761       nghttp2_mem_free(mem, ent);
 762     }
 763   }
 764
 765   new_ent = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry));
 766   if (new_ent == NULL) {
 767     return NULL;
 768   }
 769
 770   rv = nghttp2_hd_entry_init(new_ent, entry_flags, nv->name, nv->namelen,
 771                              nv->value, nv->valuelen, name_hash, value_hash,
 772                              mem);
 773   if (rv != 0) {
 774     nghttp2_mem_free(mem, new_ent);
 775     return NULL;
 776   }
 777
 778   if (room > context->hd_table_bufsize_max) {
 779     /* The entry taking more than NGHTTP2_HD_MAX_BUFFER_SIZE is
 780        immediately evicted. */
 781     --new_ent->ref;
 782   } else {
 783     rv = hd_ringbuf_push_front(&context->hd_table, new_ent, mem);
 784
 785     if (rv != 0) {
 786       --new_ent->ref;
 787
 788       if ((entry_flags & NGHTTP2_HD_FLAG_NAME_ALLOC) &&
 789           (entry_flags & NGHTTP2_HD_FLAG_NAME_GIFT)) {
 790         /* nv->name are managed by caller. */
 791         new_ent->nv.name = NULL;
 792         new_ent->nv.namelen = 0;
 793       }
 794       if ((entry_flags & NGHTTP2_HD_FLAG_VALUE_ALLOC) &&
 795           (entry_flags & NGHTTP2_HD_FLAG_VALUE_GIFT)) {
 796         /* nv->value are managed by caller. */
 797         new_ent->nv.value = NULL;
 798         new_ent->nv.valuelen = 0;
 799       }
 800
 801       nghttp2_hd_entry_free(new_ent, mem);
 802       nghttp2_mem_free(mem, new_ent);
 803
 804       return NULL;
 805     }
 806
 807     context->hd_table_bufsize += room;
 808   }
 809   return new_ent;
 810 }
 811
 812 static int name_eq(const nghttp2_nv *a, const nghttp2_nv *b) {
 813   return a->namelen == b->namelen && memeq(a->name, b->name, a->namelen);
 814 }
 815
 816 static int value_eq(const nghttp2_nv *a, const nghttp2_nv *b) {
 817   return a->valuelen == b->valuelen && memeq(a->value, b->value, a->valuelen);
 818 }
 819
 820 typedef struct {
 821   ssize_t index;
 822   /* Nonzero if both name and value are matched. */
 823   uint8_t name_value_match;
 824 } search_result;
 825
 826 static search_result search_hd_table(nghttp2_hd_context *context,
 827                                      const nghttp2_nv *nv, uint32_t name_hash,
 828                                      uint32_t value_hash) {
 829   ssize_t left = -1, right = (ssize_t)STATIC_TABLE_LENGTH;
 830   search_result res = {-1, 0};
 831   size_t i;
 832   int use_index = (nv->flags & NGHTTP2_NV_FLAG_NO_INDEX) == 0;
 833
 834   /* Search dynamic table first, so that we can find recently used
 835      entry first */
 836   if (use_index) {
 837     for (i = 0; i < context->hd_table.len; ++i) {
 838       nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, i);
 839       if (ent->name_hash != name_hash || !name_eq(&ent->nv, nv)) {
 840         continue;
 841       }
 842
 843       if (res.index == -1) {
 844         res.index = (ssize_t)(i + NGHTTP2_STATIC_TABLE_LENGTH);
 845       }
 846
 847       if (ent->value_hash == value_hash && value_eq(&ent->nv, nv)) {
 848         res.index = (ssize_t)(i + NGHTTP2_STATIC_TABLE_LENGTH);
 849         res.name_value_match = 1;
 850         return res;
 851       }
 852     }
 853   }
 854
 855   while (right - left > 1) {
 856     ssize_t mid = (left + right) / 2;
 857     nghttp2_hd_entry *ent = &static_table[mid].ent;
 858     if (ent->name_hash < name_hash) {
 859       left = mid;
 860     } else {
 861       right = mid;
 862     }
 863   }
 864
 865   for (i = right; i < STATIC_TABLE_LENGTH; ++i) {
 866     nghttp2_hd_entry *ent = &static_table[i].ent;
 867     if (ent->name_hash != name_hash) {
 868       break;
 869     }
 870
 871     if (name_eq(&ent->nv, nv)) {
 872       if (res.index == -1) {
 873         res.index = (ssize_t)(static_table[i].index);
 874       }
 875       if (use_index && ent->value_hash == value_hash &&
 876           value_eq(&ent->nv, nv)) {
 877         res.index = (ssize_t)(static_table[i].index);
 878         res.name_value_match = 1;
 879         return res;
 880       }
 881     }
 882   }
 883
 884   return res;
 885 }
 886
 887 static void hd_context_shrink_table_size(nghttp2_hd_context *context) {
 888   nghttp2_mem *mem;
 889
 890   mem = context->mem;
 891
 892   while (context->hd_table_bufsize > context->hd_table_bufsize_max &&
 893          context->hd_table.len > 0) {
 894     size_t idx = context->hd_table.len - 1;
 895     nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);
 896     context->hd_table_bufsize -= entry_room(ent->nv.namelen, ent->nv.valuelen);
 897     hd_ringbuf_pop_back(&context->hd_table);
 898     if (--ent->ref == 0) {
 899       nghttp2_hd_entry_free(ent, mem);
 900       nghttp2_mem_free(mem, ent);
 901     }
 902   }
 903 }
 904
 905 int nghttp2_hd_deflate_change_table_size(nghttp2_hd_deflater *deflater,
 906                                          size_t settings_hd_table_bufsize_max) {
 907   size_t next_bufsize = nghttp2_min(settings_hd_table_bufsize_max,
 908                                     deflater->deflate_hd_table_bufsize_max);
 909
 910   deflater->ctx.hd_table_bufsize_max = next_bufsize;
 911
 912   deflater->min_hd_table_bufsize_max =
 913       nghttp2_min(deflater->min_hd_table_bufsize_max, next_bufsize);
 914
 915   deflater->notify_table_size_change = 1;
 916
 917   hd_context_shrink_table_size(&deflater->ctx);
 918   return 0;
 919 }
 920
 921 int nghttp2_hd_inflate_change_table_size(nghttp2_hd_inflater *inflater,
 922                                          size_t settings_hd_table_bufsize_max) {
 923   inflater->settings_hd_table_bufsize_max = settings_hd_table_bufsize_max;
 924   inflater->ctx.hd_table_bufsize_max = settings_hd_table_bufsize_max;
 925   hd_context_shrink_table_size(&inflater->ctx);
 926   return 0;
 927 }
 928
 929 #define INDEX_RANGE_VALID(context, idx)                                        \
 930   ((idx) < (context)->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH)
 931
 932 static size_t get_max_index(nghttp2_hd_context *context) {
 933   return context->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH - 1;
 934 }
 935
 936 nghttp2_hd_entry *nghttp2_hd_table_get(nghttp2_hd_context *context,
 937                                        size_t idx) {
 938   assert(INDEX_RANGE_VALID(context, idx));
 939   if (idx >= NGHTTP2_STATIC_TABLE_LENGTH) {
 940     return hd_ringbuf_get(&context->hd_table,
 941                           idx - NGHTTP2_STATIC_TABLE_LENGTH);
 942   } else {
 943     return &static_table[static_table_index[idx]].ent;
 944   }
 945 }
 946
 947 #define name_match(NV, NAME)                                                   \
 948   (nv->namelen == sizeof(NAME) - 1 && memeq(nv->name, NAME, sizeof(NAME) - 1))
 949
 950 static int hd_deflate_should_indexing(nghttp2_hd_deflater *deflater,
 951                                       const nghttp2_nv *nv) {
 952   if ((nv->flags & NGHTTP2_NV_FLAG_NO_INDEX) ||
 953       entry_room(nv->namelen, nv->valuelen) >
 954           deflater->ctx.hd_table_bufsize_max * 3 / 4) {
 955     return 0;
 956   }
 957 #ifdef NGHTTP2_XHD
 958   return !name_match(nv, NGHTTP2_XHD);
 959 #else  /* !NGHTTP2_XHD */
 960   return !name_match(nv, ":path") && !name_match(nv, "content-length") &&
 961          !name_match(nv, "set-cookie") && !name_match(nv, "etag") &&
 962          !name_match(nv, "if-modified-since") &&
 963          !name_match(nv, "if-none-match") && !name_match(nv, "location") &&
 964          !name_match(nv, "age");
 965 #endif /* !NGHTTP2_XHD */
 966 }
 967
 968 static int deflate_nv(nghttp2_hd_deflater *deflater, nghttp2_bufs *bufs,
 969                       const nghttp2_nv *nv) {
 970   int rv;
 971   search_result res;
 972   ssize_t idx;
 973   int incidx = 0;
 974   uint32_t name_hash = hash(nv->name, nv->namelen);
 975   uint32_t value_hash = hash(nv->value, nv->valuelen);
 976   nghttp2_mem *mem;
 977
 978   DEBUGF(fprintf(stderr, "deflatehd: deflating "));
 979   DEBUGF(fwrite(nv->name, nv->namelen, 1, stderr));
 980   DEBUGF(fprintf(stderr, ": "));
 981   DEBUGF(fwrite(nv->value, nv->valuelen, 1, stderr));
 982   DEBUGF(fprintf(stderr, "\n"));
 983
 984   mem = deflater->ctx.mem;
 985
 986   res = search_hd_table(&deflater->ctx, nv, name_hash, value_hash);
 987
 988   idx = res.index;
 989
 990   if (res.name_value_match) {
 991
 992     DEBUGF(fprintf(stderr, "deflatehd: name/value match index=%zd\n", idx));
 993
 994     rv = emit_indexed_block(bufs, idx);
 995     if (rv != 0) {
 996       return rv;
 997     }
 998
 999     return 0;
1000   }
1001
1002   if (res.index != -1) {
1003     DEBUGF(fprintf(stderr, "deflatehd: name match index=%zd\n", res.index));
1004   }
1005
1006   if (hd_deflate_should_indexing(deflater, nv)) {
1007     nghttp2_hd_entry *new_ent;
1008     if (idx != -1 && idx < (ssize_t)NGHTTP2_STATIC_TABLE_LENGTH) {
1009       nghttp2_nv nv_indname;
1010       nv_indname = *nv;
1011       nv_indname.name = nghttp2_hd_table_get(&deflater->ctx, idx)->nv.name;
1012       new_ent =
1013           add_hd_table_incremental(&deflater->ctx, &nv_indname, name_hash,
1014                                    value_hash, NGHTTP2_HD_FLAG_VALUE_ALLOC);
1015     } else {
1016       new_ent = add_hd_table_incremental(
1017           &deflater->ctx, nv, name_hash, value_hash,
1018           NGHTTP2_HD_FLAG_NAME_ALLOC | NGHTTP2_HD_FLAG_VALUE_ALLOC);
1019     }
1020     if (!new_ent) {
1021       return NGHTTP2_ERR_HEADER_COMP;
1022     }
1023     if (new_ent->ref == 0) {
1024       nghttp2_hd_entry_free(new_ent, mem);
1025       nghttp2_mem_free(mem, new_ent);
1026     }
1027     incidx = 1;
1028   }
1029   if (idx == -1) {
1030     rv = emit_newname_block(bufs, nv, incidx);
1031   } else {
1032     rv = emit_indname_block(bufs, idx, nv, incidx);
1033   }
1034   if (rv != 0) {
1035     return rv;
1036   }
1037
1038   return 0;
1039 }
1040
1041 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater,
1042                                nghttp2_bufs *bufs, const nghttp2_nv *nv,
1043                                size_t nvlen) {
1044   size_t i;
1045   int rv = 0;
1046
1047   if (deflater->ctx.bad) {
1048     return NGHTTP2_ERR_HEADER_COMP;
1049   }
1050
1051   if (deflater->notify_table_size_change) {
1052     size_t min_hd_table_bufsize_max;
1053
1054     min_hd_table_bufsize_max = deflater->min_hd_table_bufsize_max;
1055
1056     deflater->notify_table_size_change = 0;
1057     deflater->min_hd_table_bufsize_max = UINT32_MAX;
1058
1059     if (deflater->ctx.hd_table_bufsize_max > min_hd_table_bufsize_max) {
1060
1061       rv = emit_table_size(bufs, min_hd_table_bufsize_max);
1062
1063       if (rv != 0) {
1064         goto fail;
1065       }
1066     }
1067
1068     rv = emit_table_size(bufs, deflater->ctx.hd_table_bufsize_max);
1069
1070     if (rv != 0) {
1071       goto fail;
1072     }
1073   }
1074
1075   for (i = 0; i < nvlen; ++i) {
1076     rv = deflate_nv(deflater, bufs, &nv[i]);
1077     if (rv != 0) {
1078       goto fail;
1079     }
1080   }
1081
1082   DEBUGF(
1083       fprintf(stderr, "deflatehd: all input name/value pairs were deflated\n"));
1084
1085   return 0;
1086 fail:
1087   DEBUGF(fprintf(stderr, "deflatehd: error return %d\n", rv));
1088
1089   deflater->ctx.bad = 1;
1090   return rv;
1091 }
1092
1093 ssize_t nghttp2_hd_deflate_hd(nghttp2_hd_deflater *deflater, uint8_t *buf,
1094                               size_t buflen, const nghttp2_nv *nv,
1095                               size_t nvlen) {
1096   nghttp2_bufs bufs;
1097   int rv;
1098   nghttp2_mem *mem;
1099
1100   mem = deflater->ctx.mem;
1101
1102   rv = nghttp2_bufs_wrap_init(&bufs, buf, buflen, mem);
1103
1104   if (rv != 0) {
1105     return rv;
1106   }
1107
1108   rv = nghttp2_hd_deflate_hd_bufs(deflater, &bufs, nv, nvlen);
1109
1110   buflen = nghttp2_bufs_len(&bufs);
1111
1112   nghttp2_bufs_wrap_free(&bufs);
1113
1114   if (rv == NGHTTP2_ERR_BUFFER_ERROR) {
1115     return NGHTTP2_ERR_INSUFF_BUFSIZE;
1116   }
1117
1118   if (rv != 0) {
1119     return rv;
1120   }
1121
1122   return (ssize_t)buflen;
1123 }
1124
1125 size_t nghttp2_hd_deflate_bound(nghttp2_hd_deflater *deflater _U_,
1126                                 const nghttp2_nv *nva, size_t nvlen) {
1127   size_t n = 0;
1128   size_t i;
1129
1130   /* Possible Maximum Header Table Size Change.  Encoding (1u << 31) -
1131      1 using 4 bit prefix requires 6 bytes.  We may emit this at most
1132      twice. */
1133   n += 12;
1134
1135   /* Use Literal Header Field without indexing - New Name, since it is
1136      most space consuming format.  Also we choose the less one between
1137      non-huffman and huffman, so using literal byte count is
1138      sufficient for upper bound.
1139
1140      Encoding (1u << 31) - 1 using 7 bit prefix requires 6 bytes.  We
1141      need 2 of this for |nvlen| header fields. */
1142   n += 6 * 2 * nvlen;
1143
1144   for (i = 0; i < nvlen; ++i) {
1145     n += nva[i].namelen + nva[i].valuelen;
1146   }
1147
1148   return n;
1149 }
1150
1151 int nghttp2_hd_deflate_new(nghttp2_hd_deflater **deflater_ptr,
1152                            size_t deflate_hd_table_bufsize_max) {
1153   return nghttp2_hd_deflate_new2(deflater_ptr, deflate_hd_table_bufsize_max,
1154                                  NULL);
1155 }
1156
1157 int nghttp2_hd_deflate_new2(nghttp2_hd_deflater **deflater_ptr,
1158                             size_t deflate_hd_table_bufsize_max,
1159                             nghttp2_mem *mem) {
1160   int rv;
1161   nghttp2_hd_deflater *deflater;
1162
1163   if (mem == NULL) {
1164     mem = nghttp2_mem_default();
1165   }
1166
1167   deflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_deflater));
1168
1169   if (deflater == NULL) {
1170     return NGHTTP2_ERR_NOMEM;
1171   }
1172
1173   rv = nghttp2_hd_deflate_init2(deflater, deflate_hd_table_bufsize_max, mem);
1174
1175   if (rv != 0) {
1176     nghttp2_mem_free(mem, deflater);
1177
1178     return rv;
1179   }
1180
1181   *deflater_ptr = deflater;
1182
1183   return 0;
1184 }
1185
1186 void nghttp2_hd_deflate_del(nghttp2_hd_deflater *deflater) {
1187   nghttp2_mem *mem;
1188
1189   mem = deflater->ctx.mem;
1190
1191   nghttp2_hd_deflate_free(deflater);
1192
1193   nghttp2_mem_free(mem, deflater);
1194 }
1195
1196 static void hd_inflate_set_huffman_encoded(nghttp2_hd_inflater *inflater,
1197                                            const uint8_t *in) {
1198   inflater->huffman_encoded = (*in & (1 << 7)) != 0;
1199 }
1200
1201 /*
1202  * Decodes the integer from the range [in, last).  The result is
1203  * assigned to |inflater->left|.  If the |inflater->left| is 0, then
1204  * it performs variable integer decoding from scratch. Otherwise, it
1205  * uses the |inflater->left| as the initial value and continues to
1206  * decode assuming that [in, last) begins with intermediary sequence.
1207  *
1208  * This function returns the number of bytes read if it succeeds, or
1209  * one of the following negative error codes:
1210  *
1211  * NGHTTP2_ERR_HEADER_COMP
1212  *   Integer decoding failed
1213  */
1214 static ssize_t hd_inflate_read_len(nghttp2_hd_inflater *inflater, int *rfin,
1215                                    uint8_t *in, uint8_t *last, size_t prefix,
1216                                    size_t maxlen) {
1217   ssize_t rv;
1218   uint32_t out;
1219
1220   *rfin = 0;
1221
1222   rv = decode_length(&out, &inflater->shift, rfin, (uint32_t)inflater->left,
1223                      inflater->shift, in, last, prefix);
1224
1225   if (rv == -1) {
1226     DEBUGF(fprintf(stderr, "inflatehd: integer decoding failed\n"));
1227     return NGHTTP2_ERR_HEADER_COMP;
1228   }
1229
1230   if (out > maxlen) {
1231     DEBUGF(fprintf(
1232         stderr, "inflatehd: integer exceeded the maximum value %zu\n", maxlen));
1233     return NGHTTP2_ERR_HEADER_COMP;
1234   }
1235
1236   inflater->left = out;
1237
1238   DEBUGF(fprintf(stderr, "inflatehd: decoded integer is %u\n", out));
1239
1240   return rv;
1241 }
1242
1243 /*
1244  * Reads |inflater->left| bytes from the range [in, last) and performs
1245  * huffman decoding against them and pushes the result into the
1246  * |buffer|.
1247  *
1248  * This function returns the number of bytes read if it succeeds, or
1249  * one of the following negative error codes:
1250  *
1251  * NGHTTP2_ERR_NOMEM
1252  *   Out of memory
1253  * NGHTTP2_ERR_HEADER_COMP
1254  *   Huffman decoding failed
1255  * NGHTTP2_ERR_BUFFER_ERROR
1256  *     Out of buffer space.
1257  */
1258 static ssize_t hd_inflate_read_huff(nghttp2_hd_inflater *inflater,
1259                                     nghttp2_bufs *bufs, uint8_t *in,
1260                                     uint8_t *last) {
1261   ssize_t readlen;
1262   int final = 0;
1263   if ((size_t)(last - in) >= inflater->left) {
1264     last = in + inflater->left;
1265     final = 1;
1266   }
1267   readlen = nghttp2_hd_huff_decode(&inflater->huff_decode_ctx, bufs, in,
1268                                    last - in, final);
1269
1270   if (readlen < 0) {
1271     DEBUGF(fprintf(stderr, "inflatehd: huffman decoding failed\n"));
1272     return readlen;
1273   }
1274   inflater->left -= (size_t)readlen;
1275   return readlen;
1276 }
1277
1278 /*
1279  * Reads |inflater->left| bytes from the range [in, last) and copies
1280  * them into the |buffer|.
1281  *
1282  * This function returns the number of bytes read if it succeeds, or
1283  * one of the following negative error codes:
1284  *
1285  * NGHTTP2_ERR_NOMEM
1286  *   Out of memory
1287  * NGHTTP2_ERR_HEADER_COMP
1288  *   Header decompression failed
1289  * NGHTTP2_ERR_BUFFER_ERROR
1290  *     Out of buffer space.
1291  */
1292 static ssize_t hd_inflate_read(nghttp2_hd_inflater *inflater,
1293                                nghttp2_bufs *bufs, uint8_t *in, uint8_t *last) {
1294   int rv;
1295   size_t len = nghttp2_min((size_t)(last - in), inflater->left);
1296   rv = nghttp2_bufs_add(bufs, in, len);
1297   if (rv != 0) {
1298     return rv;
1299   }
1300   inflater->left -= len;
1301   return (ssize_t)len;
1302 }
1303
1304 /*
1305  * Finalize indexed header representation reception. If header is
1306  * emitted, |*nv_out| is filled with that value and 0 is returned. If
1307  * no header is emitted, 1 is returned.
1308  *
1309  * This function returns either 0 or 1 if it succeeds, or one of the
1310  * following negative error codes:
1311  *
1312  * NGHTTP2_ERR_NOMEM
1313  *   Out of memory
1314  */
1315 static int hd_inflate_commit_indexed(nghttp2_hd_inflater *inflater,
1316                                      nghttp2_nv *nv_out) {
1317   nghttp2_hd_entry *ent = nghttp2_hd_table_get(&inflater->ctx, inflater->index);
1318
1319   emit_indexed_header(nv_out, ent);
1320
1321   return 0;
1322 }
1323
1324 static int hd_inflate_remove_bufs(nghttp2_hd_inflater *inflater, nghttp2_nv *nv,
1325                                   int value_only) {
1326   ssize_t rv;
1327   size_t buflen;
1328   uint8_t *buf;
1329   nghttp2_buf *pbuf;
1330
1331   if (inflater->index_required ||
1332       inflater->nvbufs.head != inflater->nvbufs.cur) {
1333
1334     rv = nghttp2_bufs_remove(&inflater->nvbufs, &buf);
1335
1336     if (rv < 0) {
1337       return NGHTTP2_ERR_NOMEM;
1338     }
1339
1340     buflen = rv;
1341
1342     if (value_only) {
1343       nv->name = NULL;
1344       nv->namelen = 0;
1345     } else {
1346       nv->name = buf;
1347       nv->namelen = inflater->newnamelen;
1348     }
1349
1350     nv->value = buf + nv->namelen;
1351     nv->valuelen = buflen - nv->namelen;
1352
1353     return 0;
1354   }
1355
1356   /* If we are not going to store header in header table and
1357      name/value are in first chunk, we just refer them from nv,
1358      instead of mallocing another memory. */
1359
1360   pbuf = &inflater->nvbufs.head->buf;
1361
1362   if (value_only) {
1363     nv->name = NULL;
1364     nv->namelen = 0;
1365   } else {
1366     nv->name = pbuf->pos;
1367     nv->namelen = inflater->newnamelen;
1368   }
1369
1370   nv->value = pbuf->pos + nv->namelen;
1371   nv->valuelen = nghttp2_buf_len(pbuf) - nv->namelen;
1372
1373   /* Resetting does not change the content of first buffer */
1374   nghttp2_bufs_reset(&inflater->nvbufs);
1375
1376   return 0;
1377 }
1378
1379 /*
1380  * Finalize literal header representation - new name- reception. If
1381  * header is emitted, |*nv_out| is filled with that value and 0 is
1382  * returned.
1383  *
1384  * This function returns 0 if it succeeds, or one of the following
1385  * negative error codes:
1386  *
1387  * NGHTTP2_ERR_NOMEM
1388  *   Out of memory
1389  */
1390 static int hd_inflate_commit_newname(nghttp2_hd_inflater *inflater,
1391                                      nghttp2_nv *nv_out) {
1392   int rv;
1393   nghttp2_nv nv;
1394   nghttp2_mem *mem;
1395
1396   mem = inflater->ctx.mem;
1397
1398   rv = hd_inflate_remove_bufs(inflater, &nv, 0 /* name and value */);
1399   if (rv != 0) {
1400     return NGHTTP2_ERR_NOMEM;
1401   }
1402
1403   if (inflater->no_index) {
1404     nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
1405   } else {
1406     nv.flags = NGHTTP2_NV_FLAG_NONE;
1407   }
1408
1409   if (inflater->index_required) {
1410     nghttp2_hd_entry *new_ent;
1411     uint8_t ent_flags;
1412
1413     /* nv->value points to the middle of the buffer pointed by
1414        nv->name.  So we just need to keep track of nv->name for memory
1415        management. */
1416     ent_flags = NGHTTP2_HD_FLAG_NAME_ALLOC | NGHTTP2_HD_FLAG_NAME_GIFT;
1417
1418     new_ent =
1419         add_hd_table_incremental(&inflater->ctx, &nv, hash(nv.name, nv.namelen),
1420                                  hash(nv.value, nv.valuelen), ent_flags);
1421
1422     if (new_ent) {
1423       emit_indexed_header(nv_out, new_ent);
1424       inflater->ent_keep = new_ent;
1425
1426       return 0;
1427     }
1428
1429     nghttp2_mem_free(mem, nv.name);
1430
1431     return NGHTTP2_ERR_NOMEM;
1432   }
1433
1434   emit_literal_header(nv_out, &nv);
1435
1436   if (nv.name != inflater->nvbufs.head->buf.pos) {
1437     inflater->nv_keep = nv.name;
1438   }
1439
1440   return 0;
1441 }
1442
1443 /*
1444  * Finalize literal header representation - indexed name-
1445  * reception. If header is emitted, |*nv_out| is filled with that
1446  * value and 0 is returned.
1447  *
1448  * This function returns 0 if it succeeds, or one of the following
1449  * negative error codes:
1450  *
1451  * NGHTTP2_ERR_NOMEM
1452  *   Out of memory
1453  */
1454 static int hd_inflate_commit_indname(nghttp2_hd_inflater *inflater,
1455                                      nghttp2_nv *nv_out) {
1456   int rv;
1457   nghttp2_nv nv;
1458   nghttp2_hd_entry *ent_name;
1459   nghttp2_mem *mem;
1460
1461   mem = inflater->ctx.mem;
1462
1463   rv = hd_inflate_remove_bufs(inflater, &nv, 1 /* value only */);
1464   if (rv != 0) {
1465     return NGHTTP2_ERR_NOMEM;
1466   }
1467
1468   if (inflater->no_index) {
1469     nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
1470   } else {
1471     nv.flags = NGHTTP2_NV_FLAG_NONE;
1472   }
1473
1474   ent_name = nghttp2_hd_table_get(&inflater->ctx, inflater->index);
1475
1476   nv.name = ent_name->nv.name;
1477   nv.namelen = ent_name->nv.namelen;
1478
1479   if (inflater->index_required) {
1480     nghttp2_hd_entry *new_ent;
1481     uint8_t ent_flags;
1482     int static_name;
1483
1484     ent_flags = NGHTTP2_HD_FLAG_VALUE_ALLOC | NGHTTP2_HD_FLAG_VALUE_GIFT;
1485     static_name = inflater->index < NGHTTP2_STATIC_TABLE_LENGTH;
1486
1487     if (!static_name) {
1488       ent_flags |= NGHTTP2_HD_FLAG_NAME_ALLOC;
1489       /* For entry in static table, we must not touch ref, because it
1490          is shared by threads */
1491       ++ent_name->ref;
1492     }
1493
1494     new_ent = add_hd_table_incremental(&inflater->ctx, &nv, ent_name->name_hash,
1495                                        hash(nv.value, nv.valuelen), ent_flags);
1496
1497     if (!static_name && --ent_name->ref == 0) {
1498       nghttp2_hd_entry_free(ent_name, mem);
1499       nghttp2_mem_free(mem, ent_name);
1500     }
1501
1502     if (new_ent) {
1503       emit_indexed_header(nv_out, new_ent);
1504
1505       inflater->ent_keep = new_ent;
1506
1507       return 0;
1508     }
1509
1510     nghttp2_mem_free(mem, nv.value);
1511
1512     return NGHTTP2_ERR_NOMEM;
1513   }
1514
1515   emit_literal_header(nv_out, &nv);
1516
1517   if (nv.value != inflater->nvbufs.head->buf.pos) {
1518     inflater->nv_keep = nv.value;
1519   }
1520
1521   return 0;
1522 }
1523
1524 ssize_t nghttp2_hd_inflate_hd(nghttp2_hd_inflater *inflater, nghttp2_nv *nv_out,
1525                               int *inflate_flags, uint8_t *in, size_t inlen,
1526                               int in_final) {
1527   ssize_t rv = 0;
1528   uint8_t *first = in;
1529   uint8_t *last = in + inlen;
1530   int rfin = 0;
1531
1532   if (inflater->ctx.bad) {
1533     return NGHTTP2_ERR_HEADER_COMP;
1534   }
1535
1536   DEBUGF(fprintf(stderr, "inflatehd: start state=%d\n", inflater->state));
1537   hd_inflate_keep_free(inflater);
1538   *inflate_flags = NGHTTP2_HD_INFLATE_NONE;
1539   for (; in != last;) {
1540     switch (inflater->state) {
1541     case NGHTTP2_HD_STATE_OPCODE:
1542       if ((*in & 0xe0u) == 0x20u) {
1543         DEBUGF(fprintf(stderr, "inflatehd: header table size change\n"));
1544         inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
1545         inflater->state = NGHTTP2_HD_STATE_READ_TABLE_SIZE;
1546       } else if (*in & 0x80u) {
1547         DEBUGF(fprintf(stderr, "inflatehd: indexed repr\n"));
1548         inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
1549         inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
1550       } else {
1551         if (*in == 0x40u || *in == 0 || *in == 0x10u) {
1552           DEBUGF(
1553               fprintf(stderr, "inflatehd: literal header repr - new name\n"));
1554           inflater->opcode = NGHTTP2_HD_OPCODE_NEWNAME;
1555           inflater->state = NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN;
1556         } else {
1557           DEBUGF(fprintf(stderr,
1558                          "inflatehd: literal header repr - indexed name\n"));
1559           inflater->opcode = NGHTTP2_HD_OPCODE_INDNAME;
1560           inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
1561         }
1562         inflater->index_required = (*in & 0x40) != 0;
1563         inflater->no_index = (*in & 0xf0u) == 0x10u;
1564         DEBUGF(fprintf(stderr, "inflatehd: indexing required=%d, no_index=%d\n",
1565                        inflater->index_required, inflater->no_index));
1566         if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
1567           ++in;
1568         }
1569       }
1570       inflater->left = 0;
1571       inflater->shift = 0;
1572       break;
1573     case NGHTTP2_HD_STATE_READ_TABLE_SIZE:
1574       rfin = 0;
1575       rv = hd_inflate_read_len(inflater, &rfin, in, last, 5,
1576                                inflater->settings_hd_table_bufsize_max);
1577       if (rv < 0) {
1578         goto fail;
1579       }
1580       in += rv;
1581       if (!rfin) {
1582         goto almost_ok;
1583       }
1584       DEBUGF(fprintf(stderr, "inflatehd: table_size=%zu\n", inflater->left));
1585       inflater->ctx.hd_table_bufsize_max = inflater->left;
1586       hd_context_shrink_table_size(&inflater->ctx);
1587       inflater->state = NGHTTP2_HD_STATE_OPCODE;
1588       break;
1589     case NGHTTP2_HD_STATE_READ_INDEX: {
1590       size_t prefixlen;
1591
1592       if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
1593         prefixlen = 7;
1594       } else if (inflater->index_required) {
1595         prefixlen = 6;
1596       } else {
1597         prefixlen = 4;
1598       }
1599
1600       rfin = 0;
1601       rv = hd_inflate_read_len(inflater, &rfin, in, last, prefixlen,
1602                                get_max_index(&inflater->ctx) + 1);
1603       if (rv < 0) {
1604         goto fail;
1605       }
1606
1607       in += rv;
1608
1609       if (!rfin) {
1610         goto almost_ok;
1611       }
1612
1613       if (inflater->left == 0) {
1614         rv = NGHTTP2_ERR_HEADER_COMP;
1615         goto fail;
1616       }
1617
1618       DEBUGF(fprintf(stderr, "inflatehd: index=%zu\n", inflater->left));
1619       if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
1620         inflater->index = inflater->left;
1621         --inflater->index;
1622
1623         rv = hd_inflate_commit_indexed(inflater, nv_out);
1624         if (rv < 0) {
1625           goto fail;
1626         }
1627         inflater->state = NGHTTP2_HD_STATE_OPCODE;
1628         /* If rv == 1, no header was emitted */
1629         if (rv == 0) {
1630           *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
1631           return (ssize_t)(in - first);
1632         }
1633       } else {
1634         inflater->index = inflater->left;
1635         --inflater->index;
1636
1637         inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
1638       }
1639       break;
1640     }
1641     case NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN:
1642       hd_inflate_set_huffman_encoded(inflater, in);
1643       inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN;
1644       inflater->left = 0;
1645       inflater->shift = 0;
1646       DEBUGF(fprintf(stderr, "inflatehd: huffman encoded=%d\n",
1647                      inflater->huffman_encoded != 0));
1648     /* Fall through */
1649     case NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN:
1650       rfin = 0;
1651       rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
1652       if (rv < 0) {
1653         goto fail;
1654       }
1655       in += rv;
1656       if (!rfin) {
1657         DEBUGF(fprintf(stderr,
1658                        "inflatehd: integer not fully decoded. current=%zu\n",
1659                        inflater->left));
1660
1661         goto almost_ok;
1662       }
1663
1664       if (inflater->huffman_encoded) {
1665         nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);
1666
1667         inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF;
1668       } else {
1669         inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAME;
1670       }
1671       break;
1672     case NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF:
1673       rv = hd_inflate_read_huff(inflater, &inflater->nvbufs, in, last);
1674       if (rv < 0) {
1675         goto fail;
1676       }
1677
1678       in += rv;
1679
1680       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
1681
1682       if (inflater->left) {
1683         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
1684                        inflater->left));
1685
1686         goto almost_ok;
1687       }
1688
1689       inflater->newnamelen = nghttp2_bufs_len(&inflater->nvbufs);
1690
1691       inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
1692
1693       break;
1694     case NGHTTP2_HD_STATE_NEWNAME_READ_NAME:
1695       rv = hd_inflate_read(inflater, &inflater->nvbufs, in, last);
1696       if (rv < 0) {
1697         goto fail;
1698       }
1699
1700       in += rv;
1701
1702       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
1703       if (inflater->left) {
1704         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
1705                        inflater->left));
1706
1707         goto almost_ok;
1708       }
1709
1710       inflater->newnamelen = nghttp2_bufs_len(&inflater->nvbufs);
1711
1712       inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
1713
1714       break;
1715     case NGHTTP2_HD_STATE_CHECK_VALUELEN:
1716       hd_inflate_set_huffman_encoded(inflater, in);
1717       inflater->state = NGHTTP2_HD_STATE_READ_VALUELEN;
1718       inflater->left = 0;
1719       inflater->shift = 0;
1720       DEBUGF(fprintf(stderr, "inflatehd: huffman encoded=%d\n",
1721                      inflater->huffman_encoded != 0));
1722     /* Fall through */
1723     case NGHTTP2_HD_STATE_READ_VALUELEN:
1724       rfin = 0;
1725       rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
1726       if (rv < 0) {
1727         goto fail;
1728       }
1729
1730       in += rv;
1731
1732       if (!rfin) {
1733         goto almost_ok;
1734       }
1735
1736       DEBUGF(fprintf(stderr, "inflatehd: valuelen=%zu\n", inflater->left));
1737       if (inflater->left == 0) {
1738         if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
1739           rv = hd_inflate_commit_newname(inflater, nv_out);
1740         } else {
1741           rv = hd_inflate_commit_indname(inflater, nv_out);
1742         }
1743         if (rv != 0) {
1744           goto fail;
1745         }
1746         inflater->state = NGHTTP2_HD_STATE_OPCODE;
1747         *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
1748         return (ssize_t)(in - first);
1749       }
1750
1751       if (inflater->huffman_encoded) {
1752         nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);
1753
1754         inflater->state = NGHTTP2_HD_STATE_READ_VALUEHUFF;
1755       } else {
1756         inflater->state = NGHTTP2_HD_STATE_READ_VALUE;
1757       }
1758       break;
1759     case NGHTTP2_HD_STATE_READ_VALUEHUFF:
1760       rv = hd_inflate_read_huff(inflater, &inflater->nvbufs, in, last);
1761       if (rv < 0) {
1762         goto fail;
1763       }
1764
1765       in += rv;
1766
1767       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
1768
1769       if (inflater->left) {
1770         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
1771                        inflater->left));
1772
1773         goto almost_ok;
1774       }
1775
1776       if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
1777         rv = hd_inflate_commit_newname(inflater, nv_out);
1778       } else {
1779         rv = hd_inflate_commit_indname(inflater, nv_out);
1780       }
1781
1782       if (rv != 0) {
1783         goto fail;
1784       }
1785
1786       inflater->state = NGHTTP2_HD_STATE_OPCODE;
1787       *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
1788
1789       return (ssize_t)(in - first);
1790     case NGHTTP2_HD_STATE_READ_VALUE:
1791       rv = hd_inflate_read(inflater, &inflater->nvbufs, in, last);
1792       if (rv < 0) {
1793         DEBUGF(fprintf(stderr, "inflatehd: value read failure %zd: %s\n", rv,
1794                        nghttp2_strerror((int)rv)));
1795         goto fail;
1796       }
1797
1798       in += rv;
1799
1800       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
1801
1802       if (inflater->left) {
1803         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
1804                        inflater->left));
1805         goto almost_ok;
1806       }
1807
1808       if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
1809         rv = hd_inflate_commit_newname(inflater, nv_out);
1810       } else {
1811         rv = hd_inflate_commit_indname(inflater, nv_out);
1812       }
1813
1814       if (rv != 0) {
1815         goto fail;
1816       }
1817
1818       inflater->state = NGHTTP2_HD_STATE_OPCODE;
1819       *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
1820
1821       return (ssize_t)(in - first);
1822     }
1823   }
1824
1825   assert(in == last);
1826
1827   DEBUGF(fprintf(stderr, "inflatehd: all input bytes were processed\n"));
1828
1829   if (in_final) {
1830     DEBUGF(fprintf(stderr, "inflatehd: in_final set\n"));
1831
1832     if (inflater->state != NGHTTP2_HD_STATE_OPCODE) {
1833       DEBUGF(fprintf(stderr, "inflatehd: unacceptable state=%d\n",
1834                      inflater->state));
1835       rv = NGHTTP2_ERR_HEADER_COMP;
1836
1837       goto fail;
1838     }
1839     *inflate_flags |= NGHTTP2_HD_INFLATE_FINAL;
1840   }
1841   return (ssize_t)(in - first);
1842
1843 almost_ok:
1844   if (in_final && inflater->state != NGHTTP2_HD_STATE_OPCODE) {
1845     DEBUGF(fprintf(stderr, "inflatehd: input ended prematurely\n"));
1846
1847     rv = NGHTTP2_ERR_HEADER_COMP;
1848
1849     goto fail;
1850   }
1851   return (ssize_t)(in - first);
1852
1853 fail:
1854   DEBUGF(fprintf(stderr, "inflatehd: error return %zd\n", rv));
1855
1856   inflater->ctx.bad = 1;
1857   return rv;
1858 }
1859
1860 int nghttp2_hd_inflate_end_headers(nghttp2_hd_inflater *inflater) {
1861   hd_inflate_keep_free(inflater);
1862   return 0;
1863 }
1864
1865 int nghttp2_hd_inflate_new(nghttp2_hd_inflater **inflater_ptr) {
1866   return nghttp2_hd_inflate_new2(inflater_ptr, NULL);
1867 }
1868
1869 int nghttp2_hd_inflate_new2(nghttp2_hd_inflater **inflater_ptr,
1870                             nghttp2_mem *mem) {
1871   int rv;
1872   nghttp2_hd_inflater *inflater;
1873
1874   if (mem == NULL) {
1875     mem = nghttp2_mem_default();
1876   }
1877
1878   inflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_inflater));
1879
1880   if (inflater == NULL) {
1881     return NGHTTP2_ERR_NOMEM;
1882   }
1883
1884   rv = nghttp2_hd_inflate_init(inflater, mem);
1885
1886   if (rv != 0) {
1887     nghttp2_mem_free(mem, inflater);
1888
1889     return rv;
1890   }
1891
1892   *inflater_ptr = inflater;
1893
1894   return 0;
1895 }
1896
1897 void nghttp2_hd_inflate_del(nghttp2_hd_inflater *inflater) {
1898   nghttp2_mem *mem;
1899
1900   mem = inflater->ctx.mem;
1901   nghttp2_hd_inflate_free(inflater);
1902
1903   nghttp2_mem_free(mem, inflater);
1904 }
1905
1906 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t idx,
1907                                   nghttp2_nv *nv, int inc_indexing) {
1908
1909   return emit_indname_block(bufs, idx, nv, inc_indexing);
1910 }
1911
1912 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv,
1913                                   int inc_indexing) {
1914   return emit_newname_block(bufs, nv, inc_indexing);
1915 }
1916
1917 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
1918   return emit_table_size(bufs, table_size);
1919 }
1920
1921 ssize_t nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr, int *final,
1922                                  uint32_t initial, size_t shift, uint8_t *in,
1923                                  uint8_t *last, size_t prefix) {
1924   return decode_length(res, shift_ptr, final, initial, shift, in, last, prefix);
1925 }