granicus.if.org Git - esp-idf/blob - components/nghttp/library/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 /* Make scalar initialization form of nghttp2_hd_entry */
  35 #define MAKE_STATIC_ENT(N, V, T, H)                                            \
  36   {                                                                            \
  37     { NULL, NULL, (uint8_t *)(N), sizeof((N)) - 1, -1 }                        \
  38     , {NULL, NULL, (uint8_t *)(V), sizeof((V)) - 1, -1},                       \
  39         {(uint8_t *)(N), (uint8_t *)(V), sizeof((N)) - 1, sizeof((V)) - 1, 0}, \
  40         T, H                                                                   \
  41   }
  42
  43 /* Generated by mkstatictbl.py */
  44 /* 3rd parameter is nghttp2_token value for header field name.  We use
  45    first enum value if same header names are repeated (e.g.,
  46    :status). */
  47 static nghttp2_hd_static_entry static_table[] = {
  48     MAKE_STATIC_ENT(":authority", "", 0, 3153725150u),
  49     MAKE_STATIC_ENT(":method", "GET", 1, 695666056u),
  50     MAKE_STATIC_ENT(":method", "POST", 1, 695666056u),
  51     MAKE_STATIC_ENT(":path", "/", 3, 3292848686u),
  52     MAKE_STATIC_ENT(":path", "/index.html", 3, 3292848686u),
  53     MAKE_STATIC_ENT(":scheme", "http", 5, 2510477674u),
  54     MAKE_STATIC_ENT(":scheme", "https", 5, 2510477674u),
  55     MAKE_STATIC_ENT(":status", "200", 7, 4000288983u),
  56     MAKE_STATIC_ENT(":status", "204", 7, 4000288983u),
  57     MAKE_STATIC_ENT(":status", "206", 7, 4000288983u),
  58     MAKE_STATIC_ENT(":status", "304", 7, 4000288983u),
  59     MAKE_STATIC_ENT(":status", "400", 7, 4000288983u),
  60     MAKE_STATIC_ENT(":status", "404", 7, 4000288983u),
  61     MAKE_STATIC_ENT(":status", "500", 7, 4000288983u),
  62     MAKE_STATIC_ENT("accept-charset", "", 14, 3664010344u),
  63     MAKE_STATIC_ENT("accept-encoding", "gzip, deflate", 15, 3379649177u),
  64     MAKE_STATIC_ENT("accept-language", "", 16, 1979086614u),
  65     MAKE_STATIC_ENT("accept-ranges", "", 17, 1713753958u),
  66     MAKE_STATIC_ENT("accept", "", 18, 136609321u),
  67     MAKE_STATIC_ENT("access-control-allow-origin", "", 19, 2710797292u),
  68     MAKE_STATIC_ENT("age", "", 20, 742476188u),
  69     MAKE_STATIC_ENT("allow", "", 21, 2930878514u),
  70     MAKE_STATIC_ENT("authorization", "", 22, 2436257726u),
  71     MAKE_STATIC_ENT("cache-control", "", 23, 1355326669u),
  72     MAKE_STATIC_ENT("content-disposition", "", 24, 3889184348u),
  73     MAKE_STATIC_ENT("content-encoding", "", 25, 65203592u),
  74     MAKE_STATIC_ENT("content-language", "", 26, 24973587u),
  75     MAKE_STATIC_ENT("content-length", "", 27, 1308181789u),
  76     MAKE_STATIC_ENT("content-location", "", 28, 2302364718u),
  77     MAKE_STATIC_ENT("content-range", "", 29, 3555523146u),
  78     MAKE_STATIC_ENT("content-type", "", 30, 4244048277u),
  79     MAKE_STATIC_ENT("cookie", "", 31, 2007449791u),
  80     MAKE_STATIC_ENT("date", "", 32, 3564297305u),
  81     MAKE_STATIC_ENT("etag", "", 33, 113792960u),
  82     MAKE_STATIC_ENT("expect", "", 34, 2530896728u),
  83     MAKE_STATIC_ENT("expires", "", 35, 1049544579u),
  84     MAKE_STATIC_ENT("from", "", 36, 2513272949u),
  85     MAKE_STATIC_ENT("host", "", 37, 2952701295u),
  86     MAKE_STATIC_ENT("if-match", "", 38, 3597694698u),
  87     MAKE_STATIC_ENT("if-modified-since", "", 39, 2213050793u),
  88     MAKE_STATIC_ENT("if-none-match", "", 40, 2536202615u),
  89     MAKE_STATIC_ENT("if-range", "", 41, 2340978238u),
  90     MAKE_STATIC_ENT("if-unmodified-since", "", 42, 3794814858u),
  91     MAKE_STATIC_ENT("last-modified", "", 43, 3226950251u),
  92     MAKE_STATIC_ENT("link", "", 44, 232457833u),
  93     MAKE_STATIC_ENT("location", "", 45, 200649126u),
  94     MAKE_STATIC_ENT("max-forwards", "", 46, 1826162134u),
  95     MAKE_STATIC_ENT("proxy-authenticate", "", 47, 2709445359u),
  96     MAKE_STATIC_ENT("proxy-authorization", "", 48, 2686392507u),
  97     MAKE_STATIC_ENT("range", "", 49, 4208725202u),
  98     MAKE_STATIC_ENT("referer", "", 50, 3969579366u),
  99     MAKE_STATIC_ENT("refresh", "", 51, 3572655668u),
 100     MAKE_STATIC_ENT("retry-after", "", 52, 3336180598u),
 101     MAKE_STATIC_ENT("server", "", 53, 1085029842u),
 102     MAKE_STATIC_ENT("set-cookie", "", 54, 1848371000u),
 103     MAKE_STATIC_ENT("strict-transport-security", "", 55, 4138147361u),
 104     MAKE_STATIC_ENT("transfer-encoding", "", 56, 3719590988u),
 105     MAKE_STATIC_ENT("user-agent", "", 57, 606444526u),
 106     MAKE_STATIC_ENT("vary", "", 58, 1085005381u),
 107     MAKE_STATIC_ENT("via", "", 59, 1762798611u),
 108     MAKE_STATIC_ENT("www-authenticate", "", 60, 779865858u),
 109 };
 110
 111 static int memeq(const void *s1, const void *s2, size_t n) {
 112   return memcmp(s1, s2, n) == 0;
 113 }
 114
 115 /*
 116  * This function was generated by genlibtokenlookup.py.  Inspired by
 117  * h2o header lookup.  https://github.com/h2o/h2o
 118  */
 119 static int32_t lookup_token(const uint8_t *name, size_t namelen) {
 120   switch (namelen) {
 121   case 2:
 122     switch (name[1]) {
 123     case 'e':
 124       if (lstreq("t", name, 1)) {
 125         return NGHTTP2_TOKEN_TE;
 126       }
 127       break;
 128     }
 129     break;
 130   case 3:
 131     switch (name[2]) {
 132     case 'a':
 133       if (lstreq("vi", name, 2)) {
 134         return NGHTTP2_TOKEN_VIA;
 135       }
 136       break;
 137     case 'e':
 138       if (lstreq("ag", name, 2)) {
 139         return NGHTTP2_TOKEN_AGE;
 140       }
 141       break;
 142     }
 143     break;
 144   case 4:
 145     switch (name[3]) {
 146     case 'e':
 147       if (lstreq("dat", name, 3)) {
 148         return NGHTTP2_TOKEN_DATE;
 149       }
 150       break;
 151     case 'g':
 152       if (lstreq("eta", name, 3)) {
 153         return NGHTTP2_TOKEN_ETAG;
 154       }
 155       break;
 156     case 'k':
 157       if (lstreq("lin", name, 3)) {
 158         return NGHTTP2_TOKEN_LINK;
 159       }
 160       break;
 161     case 'm':
 162       if (lstreq("fro", name, 3)) {
 163         return NGHTTP2_TOKEN_FROM;
 164       }
 165       break;
 166     case 't':
 167       if (lstreq("hos", name, 3)) {
 168         return NGHTTP2_TOKEN_HOST;
 169       }
 170       break;
 171     case 'y':
 172       if (lstreq("var", name, 3)) {
 173         return NGHTTP2_TOKEN_VARY;
 174       }
 175       break;
 176     }
 177     break;
 178   case 5:
 179     switch (name[4]) {
 180     case 'e':
 181       if (lstreq("rang", name, 4)) {
 182         return NGHTTP2_TOKEN_RANGE;
 183       }
 184       break;
 185     case 'h':
 186       if (lstreq(":pat", name, 4)) {
 187         return NGHTTP2_TOKEN__PATH;
 188       }
 189       break;
 190     case 'w':
 191       if (lstreq("allo", name, 4)) {
 192         return NGHTTP2_TOKEN_ALLOW;
 193       }
 194       break;
 195     }
 196     break;
 197   case 6:
 198     switch (name[5]) {
 199     case 'e':
 200       if (lstreq("cooki", name, 5)) {
 201         return NGHTTP2_TOKEN_COOKIE;
 202       }
 203       break;
 204     case 'r':
 205       if (lstreq("serve", name, 5)) {
 206         return NGHTTP2_TOKEN_SERVER;
 207       }
 208       break;
 209     case 't':
 210       if (lstreq("accep", name, 5)) {
 211         return NGHTTP2_TOKEN_ACCEPT;
 212       }
 213       if (lstreq("expec", name, 5)) {
 214         return NGHTTP2_TOKEN_EXPECT;
 215       }
 216       break;
 217     }
 218     break;
 219   case 7:
 220     switch (name[6]) {
 221     case 'd':
 222       if (lstreq(":metho", name, 6)) {
 223         return NGHTTP2_TOKEN__METHOD;
 224       }
 225       break;
 226     case 'e':
 227       if (lstreq(":schem", name, 6)) {
 228         return NGHTTP2_TOKEN__SCHEME;
 229       }
 230       if (lstreq("upgrad", name, 6)) {
 231         return NGHTTP2_TOKEN_UPGRADE;
 232       }
 233       break;
 234     case 'h':
 235       if (lstreq("refres", name, 6)) {
 236         return NGHTTP2_TOKEN_REFRESH;
 237       }
 238       break;
 239     case 'r':
 240       if (lstreq("refere", name, 6)) {
 241         return NGHTTP2_TOKEN_REFERER;
 242       }
 243       break;
 244     case 's':
 245       if (lstreq(":statu", name, 6)) {
 246         return NGHTTP2_TOKEN__STATUS;
 247       }
 248       if (lstreq("expire", name, 6)) {
 249         return NGHTTP2_TOKEN_EXPIRES;
 250       }
 251       break;
 252     }
 253     break;
 254   case 8:
 255     switch (name[7]) {
 256     case 'e':
 257       if (lstreq("if-rang", name, 7)) {
 258         return NGHTTP2_TOKEN_IF_RANGE;
 259       }
 260       break;
 261     case 'h':
 262       if (lstreq("if-matc", name, 7)) {
 263         return NGHTTP2_TOKEN_IF_MATCH;
 264       }
 265       break;
 266     case 'n':
 267       if (lstreq("locatio", name, 7)) {
 268         return NGHTTP2_TOKEN_LOCATION;
 269       }
 270       break;
 271     }
 272     break;
 273   case 10:
 274     switch (name[9]) {
 275     case 'e':
 276       if (lstreq("keep-aliv", name, 9)) {
 277         return NGHTTP2_TOKEN_KEEP_ALIVE;
 278       }
 279       if (lstreq("set-cooki", name, 9)) {
 280         return NGHTTP2_TOKEN_SET_COOKIE;
 281       }
 282       break;
 283     case 'n':
 284       if (lstreq("connectio", name, 9)) {
 285         return NGHTTP2_TOKEN_CONNECTION;
 286       }
 287       break;
 288     case 't':
 289       if (lstreq("user-agen", name, 9)) {
 290         return NGHTTP2_TOKEN_USER_AGENT;
 291       }
 292       break;
 293     case 'y':
 294       if (lstreq(":authorit", name, 9)) {
 295         return NGHTTP2_TOKEN__AUTHORITY;
 296       }
 297       break;
 298     }
 299     break;
 300   case 11:
 301     switch (name[10]) {
 302     case 'r':
 303       if (lstreq("retry-afte", name, 10)) {
 304         return NGHTTP2_TOKEN_RETRY_AFTER;
 305       }
 306       break;
 307     }
 308     break;
 309   case 12:
 310     switch (name[11]) {
 311     case 'e':
 312       if (lstreq("content-typ", name, 11)) {
 313         return NGHTTP2_TOKEN_CONTENT_TYPE;
 314       }
 315       break;
 316     case 's':
 317       if (lstreq("max-forward", name, 11)) {
 318         return NGHTTP2_TOKEN_MAX_FORWARDS;
 319       }
 320       break;
 321     }
 322     break;
 323   case 13:
 324     switch (name[12]) {
 325     case 'd':
 326       if (lstreq("last-modifie", name, 12)) {
 327         return NGHTTP2_TOKEN_LAST_MODIFIED;
 328       }
 329       break;
 330     case 'e':
 331       if (lstreq("content-rang", name, 12)) {
 332         return NGHTTP2_TOKEN_CONTENT_RANGE;
 333       }
 334       break;
 335     case 'h':
 336       if (lstreq("if-none-matc", name, 12)) {
 337         return NGHTTP2_TOKEN_IF_NONE_MATCH;
 338       }
 339       break;
 340     case 'l':
 341       if (lstreq("cache-contro", name, 12)) {
 342         return NGHTTP2_TOKEN_CACHE_CONTROL;
 343       }
 344       break;
 345     case 'n':
 346       if (lstreq("authorizatio", name, 12)) {
 347         return NGHTTP2_TOKEN_AUTHORIZATION;
 348       }
 349       break;
 350     case 's':
 351       if (lstreq("accept-range", name, 12)) {
 352         return NGHTTP2_TOKEN_ACCEPT_RANGES;
 353       }
 354       break;
 355     }
 356     break;
 357   case 14:
 358     switch (name[13]) {
 359     case 'h':
 360       if (lstreq("content-lengt", name, 13)) {
 361         return NGHTTP2_TOKEN_CONTENT_LENGTH;
 362       }
 363       break;
 364     case 't':
 365       if (lstreq("accept-charse", name, 13)) {
 366         return NGHTTP2_TOKEN_ACCEPT_CHARSET;
 367       }
 368       break;
 369     }
 370     break;
 371   case 15:
 372     switch (name[14]) {
 373     case 'e':
 374       if (lstreq("accept-languag", name, 14)) {
 375         return NGHTTP2_TOKEN_ACCEPT_LANGUAGE;
 376       }
 377       break;
 378     case 'g':
 379       if (lstreq("accept-encodin", name, 14)) {
 380         return NGHTTP2_TOKEN_ACCEPT_ENCODING;
 381       }
 382       break;
 383     }
 384     break;
 385   case 16:
 386     switch (name[15]) {
 387     case 'e':
 388       if (lstreq("content-languag", name, 15)) {
 389         return NGHTTP2_TOKEN_CONTENT_LANGUAGE;
 390       }
 391       if (lstreq("www-authenticat", name, 15)) {
 392         return NGHTTP2_TOKEN_WWW_AUTHENTICATE;
 393       }
 394       break;
 395     case 'g':
 396       if (lstreq("content-encodin", name, 15)) {
 397         return NGHTTP2_TOKEN_CONTENT_ENCODING;
 398       }
 399       break;
 400     case 'n':
 401       if (lstreq("content-locatio", name, 15)) {
 402         return NGHTTP2_TOKEN_CONTENT_LOCATION;
 403       }
 404       if (lstreq("proxy-connectio", name, 15)) {
 405         return NGHTTP2_TOKEN_PROXY_CONNECTION;
 406       }
 407       break;
 408     }
 409     break;
 410   case 17:
 411     switch (name[16]) {
 412     case 'e':
 413       if (lstreq("if-modified-sinc", name, 16)) {
 414         return NGHTTP2_TOKEN_IF_MODIFIED_SINCE;
 415       }
 416       break;
 417     case 'g':
 418       if (lstreq("transfer-encodin", name, 16)) {
 419         return NGHTTP2_TOKEN_TRANSFER_ENCODING;
 420       }
 421       break;
 422     }
 423     break;
 424   case 18:
 425     switch (name[17]) {
 426     case 'e':
 427       if (lstreq("proxy-authenticat", name, 17)) {
 428         return NGHTTP2_TOKEN_PROXY_AUTHENTICATE;
 429       }
 430       break;
 431     }
 432     break;
 433   case 19:
 434     switch (name[18]) {
 435     case 'e':
 436       if (lstreq("if-unmodified-sinc", name, 18)) {
 437         return NGHTTP2_TOKEN_IF_UNMODIFIED_SINCE;
 438       }
 439       break;
 440     case 'n':
 441       if (lstreq("content-dispositio", name, 18)) {
 442         return NGHTTP2_TOKEN_CONTENT_DISPOSITION;
 443       }
 444       if (lstreq("proxy-authorizatio", name, 18)) {
 445         return NGHTTP2_TOKEN_PROXY_AUTHORIZATION;
 446       }
 447       break;
 448     }
 449     break;
 450   case 25:
 451     switch (name[24]) {
 452     case 'y':
 453       if (lstreq("strict-transport-securit", name, 24)) {
 454         return NGHTTP2_TOKEN_STRICT_TRANSPORT_SECURITY;
 455       }
 456       break;
 457     }
 458     break;
 459   case 27:
 460     switch (name[26]) {
 461     case 'n':
 462       if (lstreq("access-control-allow-origi", name, 26)) {
 463         return NGHTTP2_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN;
 464       }
 465       break;
 466     }
 467     break;
 468   }
 469   return -1;
 470 }
 471
 472 void nghttp2_hd_entry_init(nghttp2_hd_entry *ent, nghttp2_hd_nv *nv) {
 473   ent->nv = *nv;
 474   ent->cnv.name = nv->name->base;
 475   ent->cnv.namelen = nv->name->len;
 476   ent->cnv.value = nv->value->base;
 477   ent->cnv.valuelen = nv->value->len;
 478   ent->cnv.flags = nv->flags;
 479   ent->next = NULL;
 480   ent->hash = 0;
 481
 482   nghttp2_rcbuf_incref(ent->nv.name);
 483   nghttp2_rcbuf_incref(ent->nv.value);
 484 }
 485
 486 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent) {
 487   nghttp2_rcbuf_decref(ent->nv.value);
 488   nghttp2_rcbuf_decref(ent->nv.name);
 489 }
 490
 491 static int name_eq(const nghttp2_hd_nv *a, const nghttp2_nv *b) {
 492   return a->name->len == b->namelen &&
 493          memeq(a->name->base, b->name, b->namelen);
 494 }
 495
 496 static int value_eq(const nghttp2_hd_nv *a, const nghttp2_nv *b) {
 497   return a->value->len == b->valuelen &&
 498          memeq(a->value->base, b->value, b->valuelen);
 499 }
 500
 501 static uint32_t name_hash(const nghttp2_nv *nv) {
 502   /* 32 bit FNV-1a: http://isthe.com/chongo/tech/comp/fnv/ */
 503   uint32_t h = 2166136261u;
 504   size_t i;
 505
 506   for (i = 0; i < nv->namelen; ++i) {
 507     h ^= nv->name[i];
 508     h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
 509   }
 510
 511   return h;
 512 }
 513
 514 static void hd_map_init(nghttp2_hd_map *map) {
 515   memset(map, 0, sizeof(nghttp2_hd_map));
 516 }
 517
 518 static void hd_map_insert(nghttp2_hd_map *map, nghttp2_hd_entry *ent) {
 519   nghttp2_hd_entry **bucket;
 520
 521   bucket = &map->table[ent->hash & (HD_MAP_SIZE - 1)];
 522
 523   if (*bucket == NULL) {
 524     *bucket = ent;
 525     return;
 526   }
 527
 528   /* lower index is linked near the root */
 529   ent->next = *bucket;
 530   *bucket = ent;
 531 }
 532
 533 static nghttp2_hd_entry *hd_map_find(nghttp2_hd_map *map, int *exact_match,
 534                                      const nghttp2_nv *nv, int32_t token,
 535                                      uint32_t hash, int name_only) {
 536   nghttp2_hd_entry *p;
 537   nghttp2_hd_entry *res = NULL;
 538
 539   *exact_match = 0;
 540
 541   for (p = map->table[hash & (HD_MAP_SIZE - 1)]; p; p = p->next) {
 542     if (token != p->nv.token ||
 543         (token == -1 && (hash != p->hash || !name_eq(&p->nv, nv)))) {
 544       continue;
 545     }
 546     if (!res) {
 547       res = p;
 548       if (name_only) {
 549         break;
 550       }
 551     }
 552     if (value_eq(&p->nv, nv)) {
 553       res = p;
 554       *exact_match = 1;
 555       break;
 556     }
 557   }
 558
 559   return res;
 560 }
 561
 562 static void hd_map_remove(nghttp2_hd_map *map, nghttp2_hd_entry *ent) {
 563   nghttp2_hd_entry **dst;
 564
 565   dst = &map->table[ent->hash & (HD_MAP_SIZE - 1)];
 566
 567   for (; *dst; dst = &(*dst)->next) {
 568     if (*dst != ent) {
 569       continue;
 570     }
 571
 572     *dst = ent->next;
 573     ent->next = NULL;
 574     return;
 575   }
 576 }
 577
 578 static int hd_ringbuf_init(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
 579                            nghttp2_mem *mem) {
 580   size_t size;
 581   for (size = 1; size < bufsize; size <<= 1)
 582     ;
 583   ringbuf->buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
 584   if (ringbuf->buffer == NULL) {
 585     return NGHTTP2_ERR_NOMEM;
 586   }
 587   ringbuf->mask = size - 1;
 588   ringbuf->first = 0;
 589   ringbuf->len = 0;
 590   return 0;
 591 }
 592
 593 static nghttp2_hd_entry *hd_ringbuf_get(nghttp2_hd_ringbuf *ringbuf,
 594                                         size_t idx) {
 595   assert(idx < ringbuf->len);
 596   return ringbuf->buffer[(ringbuf->first + idx) & ringbuf->mask];
 597 }
 598
 599 static int hd_ringbuf_reserve(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
 600                               nghttp2_mem *mem) {
 601   size_t i;
 602   size_t size;
 603   nghttp2_hd_entry **buffer;
 604
 605   if (ringbuf->mask + 1 >= bufsize) {
 606     return 0;
 607   }
 608   for (size = 1; size < bufsize; size <<= 1)
 609     ;
 610   buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
 611   if (buffer == NULL) {
 612     return NGHTTP2_ERR_NOMEM;
 613   }
 614   for (i = 0; i < ringbuf->len; ++i) {
 615     buffer[i] = hd_ringbuf_get(ringbuf, i);
 616   }
 617   nghttp2_mem_free(mem, ringbuf->buffer);
 618   ringbuf->buffer = buffer;
 619   ringbuf->mask = size - 1;
 620   ringbuf->first = 0;
 621   return 0;
 622 }
 623
 624 static void hd_ringbuf_free(nghttp2_hd_ringbuf *ringbuf, nghttp2_mem *mem) {
 625   size_t i;
 626   if (ringbuf == NULL) {
 627     return;
 628   }
 629   for (i = 0; i < ringbuf->len; ++i) {
 630     nghttp2_hd_entry *ent = hd_ringbuf_get(ringbuf, i);
 631
 632     nghttp2_hd_entry_free(ent);
 633     nghttp2_mem_free(mem, ent);
 634   }
 635   nghttp2_mem_free(mem, ringbuf->buffer);
 636 }
 637
 638 static int hd_ringbuf_push_front(nghttp2_hd_ringbuf *ringbuf,
 639                                  nghttp2_hd_entry *ent, nghttp2_mem *mem) {
 640   int rv;
 641
 642   rv = hd_ringbuf_reserve(ringbuf, ringbuf->len + 1, mem);
 643
 644   if (rv != 0) {
 645     return rv;
 646   }
 647
 648   ringbuf->buffer[--ringbuf->first & ringbuf->mask] = ent;
 649   ++ringbuf->len;
 650
 651   return 0;
 652 }
 653
 654 static void hd_ringbuf_pop_back(nghttp2_hd_ringbuf *ringbuf) {
 655   assert(ringbuf->len > 0);
 656   --ringbuf->len;
 657 }
 658
 659 static int hd_context_init(nghttp2_hd_context *context, nghttp2_mem *mem) {
 660   int rv;
 661   context->mem = mem;
 662   context->bad = 0;
 663   context->hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
 664   rv = hd_ringbuf_init(&context->hd_table, context->hd_table_bufsize_max /
 665                                                NGHTTP2_HD_ENTRY_OVERHEAD,
 666                        mem);
 667   if (rv != 0) {
 668     return rv;
 669   }
 670
 671   context->hd_table_bufsize = 0;
 672   context->next_seq = 0;
 673
 674   return 0;
 675 }
 676
 677 static void hd_context_free(nghttp2_hd_context *context) {
 678   hd_ringbuf_free(&context->hd_table, context->mem);
 679 }
 680
 681 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem) {
 682   return nghttp2_hd_deflate_init2(
 683       deflater, NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE, mem);
 684 }
 685
 686 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater,
 687                              size_t deflate_hd_table_bufsize_max,
 688                              nghttp2_mem *mem) {
 689   int rv;
 690   rv = hd_context_init(&deflater->ctx, mem);
 691   if (rv != 0) {
 692     return rv;
 693   }
 694
 695   hd_map_init(&deflater->map);
 696
 697   if (deflate_hd_table_bufsize_max < NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE) {
 698     deflater->notify_table_size_change = 1;
 699     deflater->ctx.hd_table_bufsize_max = deflate_hd_table_bufsize_max;
 700   } else {
 701     deflater->notify_table_size_change = 0;
 702   }
 703
 704   deflater->deflate_hd_table_bufsize_max = deflate_hd_table_bufsize_max;
 705   deflater->min_hd_table_bufsize_max = UINT32_MAX;
 706
 707   return 0;
 708 }
 709
 710 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem) {
 711   int rv;
 712
 713   rv = hd_context_init(&inflater->ctx, mem);
 714   if (rv != 0) {
 715     goto fail;
 716   }
 717
 718   inflater->settings_hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
 719   inflater->min_hd_table_bufsize_max = UINT32_MAX;
 720
 721   inflater->nv_name_keep = NULL;
 722   inflater->nv_value_keep = NULL;
 723
 724   inflater->opcode = NGHTTP2_HD_OPCODE_NONE;
 725   inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
 726
 727   nghttp2_buf_init(&inflater->namebuf);
 728   nghttp2_buf_init(&inflater->valuebuf);
 729
 730   inflater->namercbuf = NULL;
 731   inflater->valuercbuf = NULL;
 732
 733   inflater->huffman_encoded = 0;
 734   inflater->index = 0;
 735   inflater->left = 0;
 736   inflater->shift = 0;
 737   inflater->index_required = 0;
 738   inflater->no_index = 0;
 739
 740   return 0;
 741
 742 fail:
 743   return rv;
 744 }
 745
 746 static void hd_inflate_keep_free(nghttp2_hd_inflater *inflater) {
 747   nghttp2_rcbuf_decref(inflater->nv_value_keep);
 748   nghttp2_rcbuf_decref(inflater->nv_name_keep);
 749
 750   inflater->nv_value_keep = NULL;
 751   inflater->nv_name_keep = NULL;
 752 }
 753
 754 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater) {
 755   hd_context_free(&deflater->ctx);
 756 }
 757
 758 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater) {
 759   hd_inflate_keep_free(inflater);
 760
 761   nghttp2_rcbuf_decref(inflater->valuercbuf);
 762   nghttp2_rcbuf_decref(inflater->namercbuf);
 763
 764   hd_context_free(&inflater->ctx);
 765 }
 766
 767 static size_t entry_room(size_t namelen, size_t valuelen) {
 768   return NGHTTP2_HD_ENTRY_OVERHEAD + namelen + valuelen;
 769 }
 770
 771 static int emit_header(nghttp2_hd_nv *nv_out, nghttp2_hd_nv *nv) {
 772   DEBUGF(fprintf(stderr, "inflatehd: header emission: %s: %s\n", nv->name->base,
 773                  nv->value->base));
 774   /* ent->ref may be 0. This happens if the encoder emits literal
 775      block larger than header table capacity with indexing. */
 776   *nv_out = *nv;
 777
 778   return 0;
 779 }
 780
 781 static size_t count_encoded_length(size_t n, size_t prefix) {
 782   size_t k = (size_t)((1 << prefix) - 1);
 783   size_t len = 0;
 784
 785   if (n < k) {
 786     return 1;
 787   }
 788
 789   n -= k;
 790   ++len;
 791
 792   for (; n >= 128; n >>= 7, ++len)
 793     ;
 794
 795   return len + 1;
 796 }
 797
 798 static size_t encode_length(uint8_t *buf, size_t n, size_t prefix) {
 799   size_t k = (size_t)((1 << prefix) - 1);
 800   uint8_t *begin = buf;
 801
 802   *buf = (uint8_t)(*buf & ~k);
 803
 804   if (n < k) {
 805     *buf = (uint8_t)(*buf | n);
 806     return 1;
 807   }
 808
 809   *buf = (uint8_t)(*buf | k);
 810   ++buf;
 811
 812   n -= k;
 813
 814   for (; n >= 128; n >>= 7) {
 815     *buf++ = (uint8_t)((1 << 7) | (n & 0x7f));
 816   }
 817
 818   *buf++ = (uint8_t)n;
 819
 820   return (size_t)(buf - begin);
 821 }
 822
 823 /*
 824  * Decodes |prefix| prefixed integer stored from |in|.  The |last|
 825  * represents the 1 beyond the last of the valid contiguous memory
 826  * region from |in|.  The decoded integer must be less than or equal
 827  * to UINT32_MAX.
 828  *
 829  * If the |initial| is nonzero, it is used as a initial value, this
 830  * function assumes the |in| starts with intermediate data.
 831  *
 832  * An entire integer is decoded successfully, decoded, the |*final| is
 833  * set to nonzero.
 834  *
 835  * This function stores the decoded integer in |*res| if it succeed,
 836  * including partial decoding (in this case, number of shift to make
 837  * in the next call will be stored in |*shift_ptr|) and returns number
 838  * of bytes processed, or returns -1, indicating decoding error.
 839  */
 840 static ssize_t decode_length(uint32_t *res, size_t *shift_ptr, int *final,
 841                              uint32_t initial, size_t shift, const uint8_t *in,
 842                              const uint8_t *last, size_t prefix) {
 843   uint32_t k = (uint8_t)((1 << prefix) - 1);
 844   uint32_t n = initial;
 845   const uint8_t *start = in;
 846
 847   *shift_ptr = 0;
 848   *final = 0;
 849
 850   if (n == 0) {
 851     if ((*in & k) != k) {
 852       *res = (*in) & k;
 853       *final = 1;
 854       return 1;
 855     }
 856
 857     n = k;
 858
 859     if (++in == last) {
 860       *res = n;
 861       return (ssize_t)(in - start);
 862     }
 863   }
 864
 865   for (; in != last; ++in, shift += 7) {
 866     uint32_t add = *in & 0x7f;
 867
 868     if ((UINT32_MAX >> shift) < add) {
 869       DEBUGF(fprintf(stderr, "inflate: integer overflow on shift\n"));
 870       return -1;
 871     }
 872
 873     add <<= shift;
 874
 875     if (UINT32_MAX - add < n) {
 876       DEBUGF(fprintf(stderr, "inflate: integer overflow on addition\n"));
 877       return -1;
 878     }
 879
 880     n += add;
 881
 882     if ((*in & (1 << 7)) == 0) {
 883       break;
 884     }
 885   }
 886
 887   *shift_ptr = shift;
 888
 889   if (in == last) {
 890     *res = n;
 891     return (ssize_t)(in - start);
 892   }
 893
 894   *res = n;
 895   *final = 1;
 896   return (ssize_t)(in + 1 - start);
 897 }
 898
 899 static int emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
 900   int rv;
 901   uint8_t *bufp;
 902   size_t blocklen;
 903   uint8_t sb[16];
 904
 905   DEBUGF(fprintf(stderr, "deflatehd: emit table_size=%zu\n", table_size));
 906
 907   blocklen = count_encoded_length(table_size, 5);
 908
 909   if (sizeof(sb) < blocklen) {
 910     return NGHTTP2_ERR_HEADER_COMP;
 911   }
 912
 913   bufp = sb;
 914
 915   *bufp = 0x20u;
 916
 917   encode_length(bufp, table_size, 5);
 918
 919   rv = nghttp2_bufs_add(bufs, sb, blocklen);
 920   if (rv != 0) {
 921     return rv;
 922   }
 923
 924   return 0;
 925 }
 926
 927 static int emit_indexed_block(nghttp2_bufs *bufs, size_t idx) {
 928   int rv;
 929   size_t blocklen;
 930   uint8_t sb[16];
 931   uint8_t *bufp;
 932
 933   blocklen = count_encoded_length(idx + 1, 7);
 934
 935   DEBUGF(fprintf(stderr, "deflatehd: emit indexed index=%zu, %zu bytes\n", idx,
 936                  blocklen));
 937
 938   if (sizeof(sb) < blocklen) {
 939     return NGHTTP2_ERR_HEADER_COMP;
 940   }
 941
 942   bufp = sb;
 943   *bufp = 0x80u;
 944   encode_length(bufp, idx + 1, 7);
 945
 946   rv = nghttp2_bufs_add(bufs, sb, blocklen);
 947   if (rv != 0) {
 948     return rv;
 949   }
 950
 951   return 0;
 952 }
 953
 954 static int emit_string(nghttp2_bufs *bufs, const uint8_t *str, size_t len) {
 955   int rv;
 956   uint8_t sb[16];
 957   uint8_t *bufp;
 958   size_t blocklen;
 959   size_t enclen;
 960   int huffman = 0;
 961
 962   enclen = nghttp2_hd_huff_encode_count(str, len);
 963
 964   if (enclen < len) {
 965     huffman = 1;
 966   } else {
 967     enclen = len;
 968   }
 969
 970   blocklen = count_encoded_length(enclen, 7);
 971
 972   DEBUGF(fprintf(stderr, "deflatehd: emit string str="));
 973   DEBUGF(fwrite(str, 1, len, stderr));
 974   DEBUGF(fprintf(stderr, ", length=%zu, huffman=%d, encoded_length=%zu\n", len,
 975                  huffman, enclen));
 976
 977   if (sizeof(sb) < blocklen) {
 978     return NGHTTP2_ERR_HEADER_COMP;
 979   }
 980
 981   bufp = sb;
 982   *bufp = huffman ? 1 << 7 : 0;
 983   encode_length(bufp, enclen, 7);
 984
 985   rv = nghttp2_bufs_add(bufs, sb, blocklen);
 986   if (rv != 0) {
 987     return rv;
 988   }
 989
 990   if (huffman) {
 991     rv = nghttp2_hd_huff_encode(bufs, str, len);
 992   } else {
 993     assert(enclen == len);
 994     rv = nghttp2_bufs_add(bufs, str, len);
 995   }
 996
 997   return rv;
 998 }
 999
1000 static uint8_t pack_first_byte(int indexing_mode) {
1001   switch (indexing_mode) {
1002   case NGHTTP2_HD_WITH_INDEXING:
1003     return 0x40u;
1004   case NGHTTP2_HD_WITHOUT_INDEXING:
1005     return 0;
1006   case NGHTTP2_HD_NEVER_INDEXING:
1007     return 0x10u;
1008   default:
1009     assert(0);
1010   }
1011   /* This is required to compile with android NDK r10d +
1012      --enable-werror */
1013   return 0;
1014 }
1015
1016 static int emit_indname_block(nghttp2_bufs *bufs, size_t idx,
1017                               const nghttp2_nv *nv, int indexing_mode) {
1018   int rv;
1019   uint8_t *bufp;
1020   size_t blocklen;
1021   uint8_t sb[16];
1022   size_t prefixlen;
1023
1024   if (indexing_mode == NGHTTP2_HD_WITH_INDEXING) {
1025     prefixlen = 6;
1026   } else {
1027     prefixlen = 4;
1028   }
1029
1030   DEBUGF(fprintf(stderr, "deflatehd: emit indname index=%zu, valuelen=%zu, "
1031                          "indexing_mode=%d\n",
1032                  idx, nv->valuelen, indexing_mode));
1033
1034   blocklen = count_encoded_length(idx + 1, prefixlen);
1035
1036   if (sizeof(sb) < blocklen) {
1037     return NGHTTP2_ERR_HEADER_COMP;
1038   }
1039
1040   bufp = sb;
1041
1042   *bufp = pack_first_byte(indexing_mode);
1043
1044   encode_length(bufp, idx + 1, prefixlen);
1045
1046   rv = nghttp2_bufs_add(bufs, sb, blocklen);
1047   if (rv != 0) {
1048     return rv;
1049   }
1050
1051   rv = emit_string(bufs, nv->value, nv->valuelen);
1052   if (rv != 0) {
1053     return rv;
1054   }
1055
1056   return 0;
1057 }
1058
1059 static int emit_newname_block(nghttp2_bufs *bufs, const nghttp2_nv *nv,
1060                               int indexing_mode) {
1061   int rv;
1062
1063   DEBUGF(fprintf(stderr, "deflatehd: emit newname namelen=%zu, valuelen=%zu, "
1064                          "indexing_mode=%d\n",
1065                  nv->namelen, nv->valuelen, indexing_mode));
1066
1067   rv = nghttp2_bufs_addb(bufs, pack_first_byte(indexing_mode));
1068   if (rv != 0) {
1069     return rv;
1070   }
1071
1072   rv = emit_string(bufs, nv->name, nv->namelen);
1073   if (rv != 0) {
1074     return rv;
1075   }
1076
1077   rv = emit_string(bufs, nv->value, nv->valuelen);
1078   if (rv != 0) {
1079     return rv;
1080   }
1081
1082   return 0;
1083 }
1084
1085 static int add_hd_table_incremental(nghttp2_hd_context *context,
1086                                     nghttp2_hd_nv *nv, nghttp2_hd_map *map,
1087                                     uint32_t hash) {
1088   int rv;
1089   nghttp2_hd_entry *new_ent;
1090   size_t room;
1091   nghttp2_mem *mem;
1092
1093   mem = context->mem;
1094   room = entry_room(nv->name->len, nv->value->len);
1095
1096   while (context->hd_table_bufsize + room > context->hd_table_bufsize_max &&
1097          context->hd_table.len > 0) {
1098
1099     size_t idx = context->hd_table.len - 1;
1100     nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);
1101
1102     context->hd_table_bufsize -=
1103         entry_room(ent->nv.name->len, ent->nv.value->len);
1104
1105     DEBUGF(fprintf(stderr, "hpack: remove item from header table: %s: %s\n",
1106                    (char *)ent->nv.name->base, (char *)ent->nv.value->base));
1107
1108     hd_ringbuf_pop_back(&context->hd_table);
1109     if (map) {
1110       hd_map_remove(map, ent);
1111     }
1112
1113     nghttp2_hd_entry_free(ent);
1114     nghttp2_mem_free(mem, ent);
1115   }
1116
1117   if (room > context->hd_table_bufsize_max) {
1118     /* The entry taking more than NGHTTP2_HD_MAX_BUFFER_SIZE is
1119        immediately evicted.  So we don't allocate memory for it. */
1120     return 0;
1121   }
1122
1123   new_ent = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry));
1124   if (new_ent == NULL) {
1125     return NGHTTP2_ERR_NOMEM;
1126   }
1127
1128   nghttp2_hd_entry_init(new_ent, nv);
1129
1130   rv = hd_ringbuf_push_front(&context->hd_table, new_ent, mem);
1131
1132   if (rv != 0) {
1133     nghttp2_hd_entry_free(new_ent);
1134     nghttp2_mem_free(mem, new_ent);
1135
1136     return rv;
1137   }
1138
1139   new_ent->seq = context->next_seq++;
1140   new_ent->hash = hash;
1141
1142   if (map) {
1143     hd_map_insert(map, new_ent);
1144   }
1145
1146   context->hd_table_bufsize += room;
1147
1148   return 0;
1149 }
1150
1151 typedef struct {
1152   ssize_t index;
1153   /* Nonzero if both name and value are matched. */
1154   int name_value_match;
1155 } search_result;
1156
1157 static search_result search_static_table(const nghttp2_nv *nv, int32_t token,
1158                                          int name_only) {
1159   search_result res = {token, 0};
1160   int i;
1161   nghttp2_hd_static_entry *ent;
1162
1163   if (name_only) {
1164     return res;
1165   }
1166
1167   for (i = token;
1168        i <= NGHTTP2_TOKEN_WWW_AUTHENTICATE && static_table[i].token == token;
1169        ++i) {
1170     ent = &static_table[i];
1171     if (ent->value.len == nv->valuelen &&
1172         memcmp(ent->value.base, nv->value, nv->valuelen) == 0) {
1173       res.index = i;
1174       res.name_value_match = 1;
1175       return res;
1176     }
1177   }
1178   return res;
1179 }
1180
1181 static search_result search_hd_table(nghttp2_hd_context *context,
1182                                      const nghttp2_nv *nv, int32_t token,
1183                                      int indexing_mode, nghttp2_hd_map *map,
1184                                      uint32_t hash) {
1185   search_result res = {-1, 0};
1186   nghttp2_hd_entry *ent;
1187   int exact_match;
1188   int name_only = indexing_mode == NGHTTP2_HD_NEVER_INDEXING;
1189
1190   exact_match = 0;
1191   ent = hd_map_find(map, &exact_match, nv, token, hash, name_only);
1192
1193   if (!exact_match && token >= 0 && token <= NGHTTP2_TOKEN_WWW_AUTHENTICATE) {
1194     return search_static_table(nv, token, name_only);
1195   }
1196
1197   if (ent == NULL) {
1198     return res;
1199   }
1200
1201   res.index =
1202       (ssize_t)(context->next_seq - 1 - ent->seq + NGHTTP2_STATIC_TABLE_LENGTH);
1203   res.name_value_match = exact_match;
1204
1205   return res;
1206 }
1207
1208 static void hd_context_shrink_table_size(nghttp2_hd_context *context,
1209                                          nghttp2_hd_map *map) {
1210   nghttp2_mem *mem;
1211
1212   mem = context->mem;
1213
1214   while (context->hd_table_bufsize > context->hd_table_bufsize_max &&
1215          context->hd_table.len > 0) {
1216     size_t idx = context->hd_table.len - 1;
1217     nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);
1218     context->hd_table_bufsize -=
1219         entry_room(ent->nv.name->len, ent->nv.value->len);
1220     hd_ringbuf_pop_back(&context->hd_table);
1221     if (map) {
1222       hd_map_remove(map, ent);
1223     }
1224
1225     nghttp2_hd_entry_free(ent);
1226     nghttp2_mem_free(mem, ent);
1227   }
1228 }
1229
1230 int nghttp2_hd_deflate_change_table_size(nghttp2_hd_deflater *deflater,
1231                                          size_t settings_hd_table_bufsize_max) {
1232   size_t next_bufsize = nghttp2_min(settings_hd_table_bufsize_max,
1233                                     deflater->deflate_hd_table_bufsize_max);
1234
1235   deflater->ctx.hd_table_bufsize_max = next_bufsize;
1236
1237   deflater->min_hd_table_bufsize_max =
1238       nghttp2_min(deflater->min_hd_table_bufsize_max, next_bufsize);
1239
1240   deflater->notify_table_size_change = 1;
1241
1242   hd_context_shrink_table_size(&deflater->ctx, &deflater->map);
1243   return 0;
1244 }
1245
1246 int nghttp2_hd_inflate_change_table_size(nghttp2_hd_inflater *inflater,
1247                                          size_t settings_hd_table_bufsize_max) {
1248   switch (inflater->state) {
1249   case NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE:
1250   case NGHTTP2_HD_STATE_INFLATE_START:
1251     break;
1252   default:
1253     return NGHTTP2_ERR_INVALID_STATE;
1254   }
1255
1256   /* It seems that encoder is not required to send dynamic table size
1257      update if the table size is not changed after applying
1258      SETTINGS_HEADER_TABLE_SIZE.  RFC 7541 is ambiguous here, but this
1259      is the intention of the editor.  If new maximum table size is
1260      strictly smaller than the current negotiated maximum size,
1261      encoder must send dynamic table size update.  In other cases, we
1262      cannot expect it to do so. */
1263   if (inflater->ctx.hd_table_bufsize_max > settings_hd_table_bufsize_max) {
1264     inflater->state = NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE;
1265     /* Remember minimum value, and validate that encoder sends the
1266        value less than or equal to this. */
1267     inflater->min_hd_table_bufsize_max = settings_hd_table_bufsize_max;
1268   }
1269
1270   inflater->settings_hd_table_bufsize_max = settings_hd_table_bufsize_max;
1271
1272   inflater->ctx.hd_table_bufsize_max = settings_hd_table_bufsize_max;
1273
1274   hd_context_shrink_table_size(&inflater->ctx, NULL);
1275   return 0;
1276 }
1277
1278 #define INDEX_RANGE_VALID(context, idx)                                        \
1279   ((idx) < (context)->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH)
1280
1281 static size_t get_max_index(nghttp2_hd_context *context) {
1282   return context->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH;
1283 }
1284
1285 nghttp2_hd_nv nghttp2_hd_table_get(nghttp2_hd_context *context, size_t idx) {
1286   assert(INDEX_RANGE_VALID(context, idx));
1287   if (idx >= NGHTTP2_STATIC_TABLE_LENGTH) {
1288     return hd_ringbuf_get(&context->hd_table, idx - NGHTTP2_STATIC_TABLE_LENGTH)
1289         ->nv;
1290   } else {
1291     nghttp2_hd_static_entry *ent = &static_table[idx];
1292     nghttp2_hd_nv nv = {&ent->name, &ent->value, ent->token,
1293                         NGHTTP2_NV_FLAG_NONE};
1294     return nv;
1295   }
1296 }
1297
1298 static const nghttp2_nv *nghttp2_hd_table_get2(nghttp2_hd_context *context,
1299                                                size_t idx) {
1300   assert(INDEX_RANGE_VALID(context, idx));
1301   if (idx >= NGHTTP2_STATIC_TABLE_LENGTH) {
1302     return &hd_ringbuf_get(&context->hd_table,
1303                            idx - NGHTTP2_STATIC_TABLE_LENGTH)->cnv;
1304   }
1305
1306   return &static_table[idx].cnv;
1307 }
1308
1309 static int hd_deflate_decide_indexing(nghttp2_hd_deflater *deflater,
1310                                       const nghttp2_nv *nv, int32_t token) {
1311   if (token == NGHTTP2_TOKEN__PATH || token == NGHTTP2_TOKEN_AGE ||
1312       token == NGHTTP2_TOKEN_CONTENT_LENGTH || token == NGHTTP2_TOKEN_ETAG ||
1313       token == NGHTTP2_TOKEN_IF_MODIFIED_SINCE ||
1314       token == NGHTTP2_TOKEN_IF_NONE_MATCH || token == NGHTTP2_TOKEN_LOCATION ||
1315       token == NGHTTP2_TOKEN_SET_COOKIE ||
1316       entry_room(nv->namelen, nv->valuelen) >
1317           deflater->ctx.hd_table_bufsize_max * 3 / 4) {
1318     return NGHTTP2_HD_WITHOUT_INDEXING;
1319   }
1320
1321   return NGHTTP2_HD_WITH_INDEXING;
1322 }
1323
1324 static int deflate_nv(nghttp2_hd_deflater *deflater, nghttp2_bufs *bufs,
1325                       const nghttp2_nv *nv) {
1326   int rv;
1327   search_result res;
1328   ssize_t idx;
1329   int indexing_mode;
1330   int32_t token;
1331   nghttp2_mem *mem;
1332   uint32_t hash = 0;
1333
1334   DEBUGF(fprintf(stderr, "deflatehd: deflating %.*s: %.*s\n", (int)nv->namelen,
1335                  nv->name, (int)nv->valuelen, nv->value));
1336
1337   mem = deflater->ctx.mem;
1338
1339   token = lookup_token(nv->name, nv->namelen);
1340   if (token == -1) {
1341     hash = name_hash(nv);
1342   } else if (token <= NGHTTP2_TOKEN_WWW_AUTHENTICATE) {
1343     hash = static_table[token].hash;
1344   }
1345
1346   /* Don't index authorization header field since it may contain low
1347      entropy secret data (e.g., id/password).  Also cookie header
1348      field with less than 20 bytes value is also never indexed.  This
1349      is the same criteria used in Firefox codebase. */
1350   indexing_mode =
1351       token == NGHTTP2_TOKEN_AUTHORIZATION ||
1352               (token == NGHTTP2_TOKEN_COOKIE && nv->valuelen < 20) ||
1353               (nv->flags & NGHTTP2_NV_FLAG_NO_INDEX)
1354           ? NGHTTP2_HD_NEVER_INDEXING
1355           : hd_deflate_decide_indexing(deflater, nv, token);
1356
1357   res = search_hd_table(&deflater->ctx, nv, token, indexing_mode,
1358                         &deflater->map, hash);
1359
1360   idx = res.index;
1361
1362   if (res.name_value_match) {
1363
1364     DEBUGF(fprintf(stderr, "deflatehd: name/value match index=%zd\n", idx));
1365
1366     rv = emit_indexed_block(bufs, (size_t)idx);
1367     if (rv != 0) {
1368       return rv;
1369     }
1370
1371     return 0;
1372   }
1373
1374   if (res.index != -1) {
1375     DEBUGF(fprintf(stderr, "deflatehd: name match index=%zd\n", res.index));
1376   }
1377
1378   if (indexing_mode == NGHTTP2_HD_WITH_INDEXING) {
1379     nghttp2_hd_nv hd_nv;
1380
1381     if (idx != -1 && idx < (ssize_t)NGHTTP2_STATIC_TABLE_LENGTH) {
1382       hd_nv.name = nghttp2_hd_table_get(&deflater->ctx, (size_t)idx).name;
1383       nghttp2_rcbuf_incref(hd_nv.name);
1384     } else {
1385       rv = nghttp2_rcbuf_new2(&hd_nv.name, nv->name, nv->namelen, mem);
1386       if (rv != 0) {
1387         return rv;
1388       }
1389     }
1390
1391     rv = nghttp2_rcbuf_new2(&hd_nv.value, nv->value, nv->valuelen, mem);
1392
1393     if (rv != 0) {
1394       nghttp2_rcbuf_decref(hd_nv.name);
1395       return rv;
1396     }
1397
1398     hd_nv.token = token;
1399     hd_nv.flags = NGHTTP2_NV_FLAG_NONE;
1400
1401     rv = add_hd_table_incremental(&deflater->ctx, &hd_nv, &deflater->map, hash);
1402
1403     nghttp2_rcbuf_decref(hd_nv.value);
1404     nghttp2_rcbuf_decref(hd_nv.name);
1405
1406     if (rv != 0) {
1407       return NGHTTP2_ERR_HEADER_COMP;
1408     }
1409   }
1410   if (idx == -1) {
1411     rv = emit_newname_block(bufs, nv, indexing_mode);
1412   } else {
1413     rv = emit_indname_block(bufs, (size_t)idx, nv, indexing_mode);
1414   }
1415   if (rv != 0) {
1416     return rv;
1417   }
1418
1419   return 0;
1420 }
1421
1422 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater,
1423                                nghttp2_bufs *bufs, const nghttp2_nv *nv,
1424                                size_t nvlen) {
1425   size_t i;
1426   int rv = 0;
1427
1428   if (deflater->ctx.bad) {
1429     return NGHTTP2_ERR_HEADER_COMP;
1430   }
1431
1432   if (deflater->notify_table_size_change) {
1433     size_t min_hd_table_bufsize_max;
1434
1435     min_hd_table_bufsize_max = deflater->min_hd_table_bufsize_max;
1436
1437     deflater->notify_table_size_change = 0;
1438     deflater->min_hd_table_bufsize_max = UINT32_MAX;
1439
1440     if (deflater->ctx.hd_table_bufsize_max > min_hd_table_bufsize_max) {
1441
1442       rv = emit_table_size(bufs, min_hd_table_bufsize_max);
1443
1444       if (rv != 0) {
1445         goto fail;
1446       }
1447     }
1448
1449     rv = emit_table_size(bufs, deflater->ctx.hd_table_bufsize_max);
1450
1451     if (rv != 0) {
1452       goto fail;
1453     }
1454   }
1455
1456   for (i = 0; i < nvlen; ++i) {
1457     rv = deflate_nv(deflater, bufs, &nv[i]);
1458     if (rv != 0) {
1459       goto fail;
1460     }
1461   }
1462
1463   DEBUGF(
1464       fprintf(stderr, "deflatehd: all input name/value pairs were deflated\n"));
1465
1466   return 0;
1467 fail:
1468   DEBUGF(fprintf(stderr, "deflatehd: error return %d\n", rv));
1469
1470   deflater->ctx.bad = 1;
1471   return rv;
1472 }
1473
1474 ssize_t nghttp2_hd_deflate_hd(nghttp2_hd_deflater *deflater, uint8_t *buf,
1475                               size_t buflen, const nghttp2_nv *nv,
1476                               size_t nvlen) {
1477   nghttp2_bufs bufs;
1478   int rv;
1479   nghttp2_mem *mem;
1480
1481   mem = deflater->ctx.mem;
1482
1483   rv = nghttp2_bufs_wrap_init(&bufs, buf, buflen, mem);
1484
1485   if (rv != 0) {
1486     return rv;
1487   }
1488
1489   rv = nghttp2_hd_deflate_hd_bufs(deflater, &bufs, nv, nvlen);
1490
1491   buflen = nghttp2_bufs_len(&bufs);
1492
1493   nghttp2_bufs_wrap_free(&bufs);
1494
1495   if (rv == NGHTTP2_ERR_BUFFER_ERROR) {
1496     return NGHTTP2_ERR_INSUFF_BUFSIZE;
1497   }
1498
1499   if (rv != 0) {
1500     return rv;
1501   }
1502
1503   return (ssize_t)buflen;
1504 }
1505
1506 size_t nghttp2_hd_deflate_bound(nghttp2_hd_deflater *deflater _U_,
1507                                 const nghttp2_nv *nva, size_t nvlen) {
1508   size_t n = 0;
1509   size_t i;
1510
1511   /* Possible Maximum Header Table Size Change.  Encoding (1u << 31) -
1512      1 using 4 bit prefix requires 6 bytes.  We may emit this at most
1513      twice. */
1514   n += 12;
1515
1516   /* Use Literal Header Field without indexing - New Name, since it is
1517      most space consuming format.  Also we choose the less one between
1518      non-huffman and huffman, so using literal byte count is
1519      sufficient for upper bound.
1520
1521      Encoding (1u << 31) - 1 using 7 bit prefix requires 6 bytes.  We
1522      need 2 of this for |nvlen| header fields. */
1523   n += 6 * 2 * nvlen;
1524
1525   for (i = 0; i < nvlen; ++i) {
1526     n += nva[i].namelen + nva[i].valuelen;
1527   }
1528
1529   return n;
1530 }
1531
1532 int nghttp2_hd_deflate_new(nghttp2_hd_deflater **deflater_ptr,
1533                            size_t deflate_hd_table_bufsize_max) {
1534   return nghttp2_hd_deflate_new2(deflater_ptr, deflate_hd_table_bufsize_max,
1535                                  NULL);
1536 }
1537
1538 int nghttp2_hd_deflate_new2(nghttp2_hd_deflater **deflater_ptr,
1539                             size_t deflate_hd_table_bufsize_max,
1540                             nghttp2_mem *mem) {
1541   int rv;
1542   nghttp2_hd_deflater *deflater;
1543
1544   if (mem == NULL) {
1545     mem = nghttp2_mem_default();
1546   }
1547
1548   deflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_deflater));
1549
1550   if (deflater == NULL) {
1551     return NGHTTP2_ERR_NOMEM;
1552   }
1553
1554   rv = nghttp2_hd_deflate_init2(deflater, deflate_hd_table_bufsize_max, mem);
1555
1556   if (rv != 0) {
1557     nghttp2_mem_free(mem, deflater);
1558
1559     return rv;
1560   }
1561
1562   *deflater_ptr = deflater;
1563
1564   return 0;
1565 }
1566
1567 void nghttp2_hd_deflate_del(nghttp2_hd_deflater *deflater) {
1568   nghttp2_mem *mem;
1569
1570   mem = deflater->ctx.mem;
1571
1572   nghttp2_hd_deflate_free(deflater);
1573
1574   nghttp2_mem_free(mem, deflater);
1575 }
1576
1577 static void hd_inflate_set_huffman_encoded(nghttp2_hd_inflater *inflater,
1578                                            const uint8_t *in) {
1579   inflater->huffman_encoded = (*in & (1 << 7)) != 0;
1580 }
1581
1582 /*
1583  * Decodes the integer from the range [in, last).  The result is
1584  * assigned to |inflater->left|.  If the |inflater->left| is 0, then
1585  * it performs variable integer decoding from scratch. Otherwise, it
1586  * uses the |inflater->left| as the initial value and continues to
1587  * decode assuming that [in, last) begins with intermediary sequence.
1588  *
1589  * This function returns the number of bytes read if it succeeds, or
1590  * one of the following negative error codes:
1591  *
1592  * NGHTTP2_ERR_HEADER_COMP
1593  *   Integer decoding failed
1594  */
1595 static ssize_t hd_inflate_read_len(nghttp2_hd_inflater *inflater, int *rfin,
1596                                    const uint8_t *in, const uint8_t *last,
1597                                    size_t prefix, size_t maxlen) {
1598   ssize_t rv;
1599   uint32_t out;
1600
1601   *rfin = 0;
1602
1603   rv = decode_length(&out, &inflater->shift, rfin, (uint32_t)inflater->left,
1604                      inflater->shift, in, last, prefix);
1605
1606   if (rv == -1) {
1607     DEBUGF(fprintf(stderr, "inflatehd: integer decoding failed\n"));
1608     return NGHTTP2_ERR_HEADER_COMP;
1609   }
1610
1611   if (out > maxlen) {
1612     DEBUGF(fprintf(
1613         stderr, "inflatehd: integer exceeded the maximum value %zu\n", maxlen));
1614     return NGHTTP2_ERR_HEADER_COMP;
1615   }
1616
1617   inflater->left = out;
1618
1619   DEBUGF(fprintf(stderr, "inflatehd: decoded integer is %u\n", out));
1620
1621   return rv;
1622 }
1623
1624 /*
1625  * Reads |inflater->left| bytes from the range [in, last) and performs
1626  * huffman decoding against them and pushes the result into the
1627  * |buffer|.
1628  *
1629  * This function returns the number of bytes read if it succeeds, or
1630  * one of the following negative error codes:
1631  *
1632  * NGHTTP2_ERR_NOMEM
1633  *   Out of memory
1634  * NGHTTP2_ERR_HEADER_COMP
1635  *   Huffman decoding failed
1636  */
1637 static ssize_t hd_inflate_read_huff(nghttp2_hd_inflater *inflater,
1638                                     nghttp2_buf *buf, const uint8_t *in,
1639                                     const uint8_t *last) {
1640   ssize_t readlen;
1641   int final = 0;
1642   if ((size_t)(last - in) >= inflater->left) {
1643     last = in + inflater->left;
1644     final = 1;
1645   }
1646   readlen = nghttp2_hd_huff_decode(&inflater->huff_decode_ctx, buf, in,
1647                                    (size_t)(last - in), final);
1648
1649   if (readlen < 0) {
1650     DEBUGF(fprintf(stderr, "inflatehd: huffman decoding failed\n"));
1651     return readlen;
1652   }
1653   inflater->left -= (size_t)readlen;
1654   return readlen;
1655 }
1656
1657 /*
1658  * Reads |inflater->left| bytes from the range [in, last) and copies
1659  * them into the |buffer|.
1660  *
1661  * This function returns the number of bytes read if it succeeds, or
1662  * one of the following negative error codes:
1663  *
1664  * NGHTTP2_ERR_NOMEM
1665  *   Out of memory
1666  * NGHTTP2_ERR_HEADER_COMP
1667  *   Header decompression failed
1668  */
1669 static ssize_t hd_inflate_read(nghttp2_hd_inflater *inflater, nghttp2_buf *buf,
1670                                const uint8_t *in, const uint8_t *last) {
1671   size_t len = nghttp2_min((size_t)(last - in), inflater->left);
1672
1673   buf->last = nghttp2_cpymem(buf->last, in, len);
1674
1675   inflater->left -= len;
1676   return (ssize_t)len;
1677 }
1678
1679 /*
1680  * Finalize indexed header representation reception. If header is
1681  * emitted, |*nv_out| is filled with that value and 0 is returned. If
1682  * no header is emitted, 1 is returned.
1683  *
1684  * This function returns either 0 or 1 if it succeeds, or one of the
1685  * following negative error codes:
1686  *
1687  * NGHTTP2_ERR_NOMEM
1688  *   Out of memory
1689  */
1690 static int hd_inflate_commit_indexed(nghttp2_hd_inflater *inflater,
1691                                      nghttp2_hd_nv *nv_out) {
1692   nghttp2_hd_nv nv = nghttp2_hd_table_get(&inflater->ctx, inflater->index);
1693
1694   emit_header(nv_out, &nv);
1695
1696   return 0;
1697 }
1698
1699 /*
1700  * Finalize literal header representation - new name- reception. If
1701  * header is emitted, |*nv_out| is filled with that value and 0 is
1702  * returned.
1703  *
1704  * This function returns 0 if it succeeds, or one of the following
1705  * negative error codes:
1706  *
1707  * NGHTTP2_ERR_NOMEM
1708  *   Out of memory
1709  */
1710 static int hd_inflate_commit_newname(nghttp2_hd_inflater *inflater,
1711                                      nghttp2_hd_nv *nv_out) {
1712   nghttp2_hd_nv nv;
1713   int rv;
1714
1715   if (inflater->no_index) {
1716     nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
1717   } else {
1718     nv.flags = NGHTTP2_NV_FLAG_NONE;
1719   }
1720
1721   nv.name = inflater->namercbuf;
1722   nv.value = inflater->valuercbuf;
1723   nv.token = lookup_token(inflater->namercbuf->base, inflater->namercbuf->len);
1724
1725   if (inflater->index_required) {
1726     rv = add_hd_table_incremental(&inflater->ctx, &nv, NULL, 0);
1727
1728     if (rv != 0) {
1729       return rv;
1730     }
1731   }
1732
1733   emit_header(nv_out, &nv);
1734
1735   inflater->nv_name_keep = nv.name;
1736   inflater->nv_value_keep = nv.value;
1737
1738   inflater->namercbuf = NULL;
1739   inflater->valuercbuf = NULL;
1740
1741   return 0;
1742 }
1743
1744 /*
1745  * Finalize literal header representation - indexed name-
1746  * reception. If header is emitted, |*nv_out| is filled with that
1747  * value and 0 is returned.
1748  *
1749  * This function returns 0 if it succeeds, or one of the following
1750  * negative error codes:
1751  *
1752  * NGHTTP2_ERR_NOMEM
1753  *   Out of memory
1754  */
1755 static int hd_inflate_commit_indname(nghttp2_hd_inflater *inflater,
1756                                      nghttp2_hd_nv *nv_out) {
1757   nghttp2_hd_nv nv;
1758   int rv;
1759
1760   nv = nghttp2_hd_table_get(&inflater->ctx, inflater->index);
1761
1762   if (inflater->no_index) {
1763     nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
1764   } else {
1765     nv.flags = NGHTTP2_NV_FLAG_NONE;
1766   }
1767
1768   nghttp2_rcbuf_incref(nv.name);
1769
1770   nv.value = inflater->valuercbuf;
1771
1772   if (inflater->index_required) {
1773     rv = add_hd_table_incremental(&inflater->ctx, &nv, NULL, 0);
1774     if (rv != 0) {
1775       nghttp2_rcbuf_decref(nv.name);
1776       return NGHTTP2_ERR_NOMEM;
1777     }
1778   }
1779
1780   emit_header(nv_out, &nv);
1781
1782   inflater->nv_name_keep = nv.name;
1783   inflater->nv_value_keep = nv.value;
1784
1785   inflater->valuercbuf = NULL;
1786
1787   return 0;
1788 }
1789
1790 ssize_t nghttp2_hd_inflate_hd(nghttp2_hd_inflater *inflater, nghttp2_nv *nv_out,
1791                               int *inflate_flags, uint8_t *in, size_t inlen,
1792                               int in_final) {
1793   return nghttp2_hd_inflate_hd2(inflater, nv_out, inflate_flags, in, inlen,
1794                                 in_final);
1795 }
1796
1797 ssize_t nghttp2_hd_inflate_hd2(nghttp2_hd_inflater *inflater,
1798                                nghttp2_nv *nv_out, int *inflate_flags,
1799                                const uint8_t *in, size_t inlen, int in_final) {
1800   ssize_t rv;
1801   nghttp2_hd_nv hd_nv;
1802
1803   rv = nghttp2_hd_inflate_hd_nv(inflater, &hd_nv, inflate_flags, in, inlen,
1804                                 in_final);
1805
1806   if (rv < 0) {
1807     return rv;
1808   }
1809
1810   if (*inflate_flags & NGHTTP2_HD_INFLATE_EMIT) {
1811     nv_out->name = hd_nv.name->base;
1812     nv_out->namelen = hd_nv.name->len;
1813
1814     nv_out->value = hd_nv.value->base;
1815     nv_out->valuelen = hd_nv.value->len;
1816
1817     nv_out->flags = hd_nv.flags;
1818   }
1819
1820   return rv;
1821 }
1822
1823 ssize_t nghttp2_hd_inflate_hd_nv(nghttp2_hd_inflater *inflater,
1824                                  nghttp2_hd_nv *nv_out, int *inflate_flags,
1825                                  const uint8_t *in, size_t inlen,
1826                                  int in_final) {
1827   ssize_t rv = 0;
1828   const uint8_t *first = in;
1829   const uint8_t *last = in + inlen;
1830   int rfin = 0;
1831   int busy = 0;
1832   nghttp2_mem *mem;
1833
1834   mem = inflater->ctx.mem;
1835
1836   if (inflater->ctx.bad) {
1837     return NGHTTP2_ERR_HEADER_COMP;
1838   }
1839
1840   DEBUGF(fprintf(stderr, "inflatehd: start state=%d\n", inflater->state));
1841   hd_inflate_keep_free(inflater);
1842   *inflate_flags = NGHTTP2_HD_INFLATE_NONE;
1843   for (; in != last || busy;) {
1844     busy = 0;
1845     switch (inflater->state) {
1846     case NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE:
1847       if ((*in & 0xe0u) != 0x20u) {
1848         DEBUGF(fprintf(stderr, "inflatehd: header table size change was "
1849                                "expected, but saw 0x%02x as first byte",
1850                        *in));
1851         rv = NGHTTP2_ERR_HEADER_COMP;
1852         goto fail;
1853       }
1854     /* fall through */
1855     case NGHTTP2_HD_STATE_INFLATE_START:
1856     case NGHTTP2_HD_STATE_OPCODE:
1857       if ((*in & 0xe0u) == 0x20u) {
1858         DEBUGF(fprintf(stderr, "inflatehd: header table size change\n"));
1859         if (inflater->state == NGHTTP2_HD_STATE_OPCODE) {
1860           DEBUGF(fprintf(stderr, "inflatehd: header table size change must "
1861                                  "appear at the head of header block\n"));
1862           rv = NGHTTP2_ERR_HEADER_COMP;
1863           goto fail;
1864         }
1865         inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
1866         inflater->state = NGHTTP2_HD_STATE_READ_TABLE_SIZE;
1867       } else if (*in & 0x80u) {
1868         DEBUGF(fprintf(stderr, "inflatehd: indexed repr\n"));
1869         inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
1870         inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
1871       } else {
1872         if (*in == 0x40u || *in == 0 || *in == 0x10u) {
1873           DEBUGF(
1874               fprintf(stderr, "inflatehd: literal header repr - new name\n"));
1875           inflater->opcode = NGHTTP2_HD_OPCODE_NEWNAME;
1876           inflater->state = NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN;
1877         } else {
1878           DEBUGF(fprintf(stderr,
1879                          "inflatehd: literal header repr - indexed name\n"));
1880           inflater->opcode = NGHTTP2_HD_OPCODE_INDNAME;
1881           inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
1882         }
1883         inflater->index_required = (*in & 0x40) != 0;
1884         inflater->no_index = (*in & 0xf0u) == 0x10u;
1885         DEBUGF(fprintf(stderr, "inflatehd: indexing required=%d, no_index=%d\n",
1886                        inflater->index_required, inflater->no_index));
1887         if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
1888           ++in;
1889         }
1890       }
1891       inflater->left = 0;
1892       inflater->shift = 0;
1893       break;
1894     case NGHTTP2_HD_STATE_READ_TABLE_SIZE:
1895       rfin = 0;
1896       rv = hd_inflate_read_len(
1897           inflater, &rfin, in, last, 5,
1898           nghttp2_min(inflater->min_hd_table_bufsize_max,
1899                       inflater->settings_hd_table_bufsize_max));
1900       if (rv < 0) {
1901         goto fail;
1902       }
1903       in += rv;
1904       if (!rfin) {
1905         goto almost_ok;
1906       }
1907       DEBUGF(fprintf(stderr, "inflatehd: table_size=%zu\n", inflater->left));
1908       inflater->min_hd_table_bufsize_max = UINT32_MAX;
1909       inflater->ctx.hd_table_bufsize_max = inflater->left;
1910       hd_context_shrink_table_size(&inflater->ctx, NULL);
1911       inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
1912       break;
1913     case NGHTTP2_HD_STATE_READ_INDEX: {
1914       size_t prefixlen;
1915
1916       if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
1917         prefixlen = 7;
1918       } else if (inflater->index_required) {
1919         prefixlen = 6;
1920       } else {
1921         prefixlen = 4;
1922       }
1923
1924       rfin = 0;
1925       rv = hd_inflate_read_len(inflater, &rfin, in, last, prefixlen,
1926                                get_max_index(&inflater->ctx));
1927       if (rv < 0) {
1928         goto fail;
1929       }
1930
1931       in += rv;
1932
1933       if (!rfin) {
1934         goto almost_ok;
1935       }
1936
1937       if (inflater->left == 0) {
1938         rv = NGHTTP2_ERR_HEADER_COMP;
1939         goto fail;
1940       }
1941
1942       DEBUGF(fprintf(stderr, "inflatehd: index=%zu\n", inflater->left));
1943       if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
1944         inflater->index = inflater->left;
1945         --inflater->index;
1946
1947         rv = hd_inflate_commit_indexed(inflater, nv_out);
1948         if (rv < 0) {
1949           goto fail;
1950         }
1951         inflater->state = NGHTTP2_HD_STATE_OPCODE;
1952         /* If rv == 1, no header was emitted */
1953         if (rv == 0) {
1954           *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
1955           return (ssize_t)(in - first);
1956         }
1957       } else {
1958         inflater->index = inflater->left;
1959         --inflater->index;
1960
1961         inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
1962       }
1963       break;
1964     }
1965     case NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN:
1966       hd_inflate_set_huffman_encoded(inflater, in);
1967       inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN;
1968       inflater->left = 0;
1969       inflater->shift = 0;
1970       DEBUGF(fprintf(stderr, "inflatehd: huffman encoded=%d\n",
1971                      inflater->huffman_encoded != 0));
1972     /* Fall through */
1973     case NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN:
1974       rfin = 0;
1975       rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
1976       if (rv < 0) {
1977         goto fail;
1978       }
1979       in += rv;
1980       if (!rfin) {
1981         DEBUGF(fprintf(stderr,
1982                        "inflatehd: integer not fully decoded. current=%zu\n",
1983                        inflater->left));
1984
1985         goto almost_ok;
1986       }
1987
1988       if (inflater->huffman_encoded) {
1989         nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);
1990
1991         inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF;
1992
1993         rv = nghttp2_rcbuf_new(&inflater->namercbuf, inflater->left * 2 + 1,
1994                                mem);
1995       } else {
1996         inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAME;
1997         rv = nghttp2_rcbuf_new(&inflater->namercbuf, inflater->left + 1, mem);
1998       }
1999
2000       if (rv != 0) {
2001         goto fail;
2002       }
2003
2004       nghttp2_buf_wrap_init(&inflater->namebuf, inflater->namercbuf->base,
2005                             inflater->namercbuf->len);
2006
2007       break;
2008     case NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF:
2009       rv = hd_inflate_read_huff(inflater, &inflater->namebuf, in, last);
2010       if (rv < 0) {
2011         goto fail;
2012       }
2013
2014       in += rv;
2015
2016       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
2017
2018       if (inflater->left) {
2019         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
2020                        inflater->left));
2021
2022         goto almost_ok;
2023       }
2024
2025       *inflater->namebuf.last = '\0';
2026       inflater->namercbuf->len = nghttp2_buf_len(&inflater->namebuf);
2027
2028       inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
2029
2030       break;
2031     case NGHTTP2_HD_STATE_NEWNAME_READ_NAME:
2032       rv = hd_inflate_read(inflater, &inflater->namebuf, in, last);
2033       if (rv < 0) {
2034         goto fail;
2035       }
2036
2037       in += rv;
2038
2039       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
2040       if (inflater->left) {
2041         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
2042                        inflater->left));
2043
2044         goto almost_ok;
2045       }
2046
2047       *inflater->namebuf.last = '\0';
2048       inflater->namercbuf->len = nghttp2_buf_len(&inflater->namebuf);
2049
2050       inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
2051
2052       break;
2053     case NGHTTP2_HD_STATE_CHECK_VALUELEN:
2054       hd_inflate_set_huffman_encoded(inflater, in);
2055       inflater->state = NGHTTP2_HD_STATE_READ_VALUELEN;
2056       inflater->left = 0;
2057       inflater->shift = 0;
2058       DEBUGF(fprintf(stderr, "inflatehd: huffman encoded=%d\n",
2059                      inflater->huffman_encoded != 0));
2060     /* Fall through */
2061     case NGHTTP2_HD_STATE_READ_VALUELEN:
2062       rfin = 0;
2063       rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
2064       if (rv < 0) {
2065         goto fail;
2066       }
2067
2068       in += rv;
2069
2070       if (!rfin) {
2071         goto almost_ok;
2072       }
2073
2074       DEBUGF(fprintf(stderr, "inflatehd: valuelen=%zu\n", inflater->left));
2075
2076       if (inflater->huffman_encoded) {
2077         nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);
2078
2079         inflater->state = NGHTTP2_HD_STATE_READ_VALUEHUFF;
2080
2081         rv = nghttp2_rcbuf_new(&inflater->valuercbuf, inflater->left * 2 + 1,
2082                                mem);
2083       } else {
2084         inflater->state = NGHTTP2_HD_STATE_READ_VALUE;
2085
2086         rv = nghttp2_rcbuf_new(&inflater->valuercbuf, inflater->left + 1, mem);
2087       }
2088
2089       if (rv != 0) {
2090         goto fail;
2091       }
2092
2093       nghttp2_buf_wrap_init(&inflater->valuebuf, inflater->valuercbuf->base,
2094                             inflater->valuercbuf->len);
2095
2096       busy = 1;
2097
2098       break;
2099     case NGHTTP2_HD_STATE_READ_VALUEHUFF:
2100       rv = hd_inflate_read_huff(inflater, &inflater->valuebuf, in, last);
2101       if (rv < 0) {
2102         goto fail;
2103       }
2104
2105       in += rv;
2106
2107       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
2108
2109       if (inflater->left) {
2110         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
2111                        inflater->left));
2112
2113         goto almost_ok;
2114       }
2115
2116       *inflater->valuebuf.last = '\0';
2117       inflater->valuercbuf->len = nghttp2_buf_len(&inflater->valuebuf);
2118
2119       if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
2120         rv = hd_inflate_commit_newname(inflater, nv_out);
2121       } else {
2122         rv = hd_inflate_commit_indname(inflater, nv_out);
2123       }
2124
2125       if (rv != 0) {
2126         goto fail;
2127       }
2128
2129       inflater->state = NGHTTP2_HD_STATE_OPCODE;
2130       *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
2131
2132       return (ssize_t)(in - first);
2133     case NGHTTP2_HD_STATE_READ_VALUE:
2134       rv = hd_inflate_read(inflater, &inflater->valuebuf, in, last);
2135       if (rv < 0) {
2136         DEBUGF(fprintf(stderr, "inflatehd: value read failure %zd: %s\n", rv,
2137                        nghttp2_strerror((int)rv)));
2138         goto fail;
2139       }
2140
2141       in += rv;
2142
2143       DEBUGF(fprintf(stderr, "inflatehd: %zd bytes read\n", rv));
2144
2145       if (inflater->left) {
2146         DEBUGF(fprintf(stderr, "inflatehd: still %zu bytes to go\n",
2147                        inflater->left));
2148         goto almost_ok;
2149       }
2150
2151       *inflater->valuebuf.last = '\0';
2152       inflater->valuercbuf->len = nghttp2_buf_len(&inflater->valuebuf);
2153
2154       if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
2155         rv = hd_inflate_commit_newname(inflater, nv_out);
2156       } else {
2157         rv = hd_inflate_commit_indname(inflater, nv_out);
2158       }
2159
2160       if (rv != 0) {
2161         goto fail;
2162       }
2163
2164       inflater->state = NGHTTP2_HD_STATE_OPCODE;
2165       *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
2166
2167       return (ssize_t)(in - first);
2168     }
2169   }
2170
2171   assert(in == last);
2172
2173   DEBUGF(fprintf(stderr, "inflatehd: all input bytes were processed\n"));
2174
2175   if (in_final) {
2176     DEBUGF(fprintf(stderr, "inflatehd: in_final set\n"));
2177
2178     if (inflater->state != NGHTTP2_HD_STATE_OPCODE &&
2179         inflater->state != NGHTTP2_HD_STATE_INFLATE_START) {
2180       DEBUGF(fprintf(stderr, "inflatehd: unacceptable state=%d\n",
2181                      inflater->state));
2182       rv = NGHTTP2_ERR_HEADER_COMP;
2183
2184       goto fail;
2185     }
2186     *inflate_flags |= NGHTTP2_HD_INFLATE_FINAL;
2187   }
2188   return (ssize_t)(in - first);
2189
2190 almost_ok:
2191   if (in_final) {
2192     DEBUGF(fprintf(stderr, "inflatehd: input ended prematurely\n"));
2193
2194     rv = NGHTTP2_ERR_HEADER_COMP;
2195
2196     goto fail;
2197   }
2198   return (ssize_t)(in - first);
2199
2200 fail:
2201   DEBUGF(fprintf(stderr, "inflatehd: error return %zd\n", rv));
2202
2203   inflater->ctx.bad = 1;
2204   return rv;
2205 }
2206
2207 int nghttp2_hd_inflate_end_headers(nghttp2_hd_inflater *inflater) {
2208   hd_inflate_keep_free(inflater);
2209   inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
2210   return 0;
2211 }
2212
2213 int nghttp2_hd_inflate_new(nghttp2_hd_inflater **inflater_ptr) {
2214   return nghttp2_hd_inflate_new2(inflater_ptr, NULL);
2215 }
2216
2217 int nghttp2_hd_inflate_new2(nghttp2_hd_inflater **inflater_ptr,
2218                             nghttp2_mem *mem) {
2219   int rv;
2220   nghttp2_hd_inflater *inflater;
2221
2222   if (mem == NULL) {
2223     mem = nghttp2_mem_default();
2224   }
2225
2226   inflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_inflater));
2227
2228   if (inflater == NULL) {
2229     return NGHTTP2_ERR_NOMEM;
2230   }
2231
2232   rv = nghttp2_hd_inflate_init(inflater, mem);
2233
2234   if (rv != 0) {
2235     nghttp2_mem_free(mem, inflater);
2236
2237     return rv;
2238   }
2239
2240   *inflater_ptr = inflater;
2241
2242   return 0;
2243 }
2244
2245 void nghttp2_hd_inflate_del(nghttp2_hd_inflater *inflater) {
2246   nghttp2_mem *mem;
2247
2248   mem = inflater->ctx.mem;
2249   nghttp2_hd_inflate_free(inflater);
2250
2251   nghttp2_mem_free(mem, inflater);
2252 }
2253
2254 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t idx,
2255                                   nghttp2_nv *nv, int indexing_mode) {
2256
2257   return emit_indname_block(bufs, idx, nv, indexing_mode);
2258 }
2259
2260 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv,
2261                                   int indexing_mode) {
2262   return emit_newname_block(bufs, nv, indexing_mode);
2263 }
2264
2265 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
2266   return emit_table_size(bufs, table_size);
2267 }
2268
2269 ssize_t nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr, int *final,
2270                                  uint32_t initial, size_t shift, uint8_t *in,
2271                                  uint8_t *last, size_t prefix) {
2272   return decode_length(res, shift_ptr, final, initial, shift, in, last, prefix);
2273 }
2274
2275 static size_t hd_get_num_table_entries(nghttp2_hd_context *context) {
2276   return context->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH;
2277 }
2278
2279 static const nghttp2_nv *hd_get_table_entry(nghttp2_hd_context *context,
2280                                             size_t idx) {
2281   if (idx == 0) {
2282     return NULL;
2283   }
2284
2285   --idx;
2286
2287   if (!INDEX_RANGE_VALID(context, idx)) {
2288     return NULL;
2289   }
2290
2291   return nghttp2_hd_table_get2(context, idx);
2292 }
2293
2294 size_t nghttp2_hd_deflate_get_num_table_entries(nghttp2_hd_deflater *deflater) {
2295   return hd_get_num_table_entries(&deflater->ctx);
2296 }
2297
2298 const nghttp2_nv *
2299 nghttp2_hd_deflate_get_table_entry(nghttp2_hd_deflater *deflater, size_t idx) {
2300   return hd_get_table_entry(&deflater->ctx, idx);
2301 }
2302
2303 size_t
2304 nghttp2_hd_deflate_get_dynamic_table_size(nghttp2_hd_deflater *deflater) {
2305   return deflater->ctx.hd_table_bufsize;
2306 }
2307
2308 size_t
2309 nghttp2_hd_deflate_get_max_dynamic_table_size(nghttp2_hd_deflater *deflater) {
2310   return deflater->ctx.hd_table_bufsize_max;
2311 }
2312
2313 size_t nghttp2_hd_inflate_get_num_table_entries(nghttp2_hd_inflater *inflater) {
2314   return hd_get_num_table_entries(&inflater->ctx);
2315 }
2316
2317 const nghttp2_nv *
2318 nghttp2_hd_inflate_get_table_entry(nghttp2_hd_inflater *inflater, size_t idx) {
2319   return hd_get_table_entry(&inflater->ctx, idx);
2320 }
2321
2322 size_t
2323 nghttp2_hd_inflate_get_dynamic_table_size(nghttp2_hd_inflater *inflater) {
2324   return inflater->ctx.hd_table_bufsize;
2325 }
2326
2327 size_t
2328 nghttp2_hd_inflate_get_max_dynamic_table_size(nghttp2_hd_inflater *inflater) {
2329   return inflater->ctx.hd_table_bufsize_max;
2330 }