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