"Fossies" - the Fresh Open Source Software Archive

Member "Pound-3.0.2/src/hpack.c" (28 Nov 2021, 26188 Bytes) of package /linux/www/Pound-3.0.2.tgz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hpack.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.0.1_vs_3.0.2.

    1 /*  $OpenBSD$   */
    2 
    3 /*
    4  * Copyright (c) 2019 Reyk Floeter <reyk@openbsd.org>
    5  *
    6  * Permission to use, copy, modify, and distribute this software for any
    7  * purpose with or without fee is hereby granted, provided that the above
    8  * copyright notice and this permission notice appear in all copies.
    9  *
   10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
   12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
   13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
   14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
   15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
   16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
   17  */
   18 
   19 #include <sys/types.h>
   20 
   21 #include <stdio.h>
   22 #include <string.h>
   23 #include <stdlib.h>
   24 #include <limits.h>
   25 #include <math.h>
   26 #include <err.h>
   27 
   28 #define HPACK_INTERNAL
   29 #include "pound.h"
   30 
   31 static const struct hpack_index *
   32          hpack_table_getbyid(long, struct hpack_index *,
   33             struct hpack_table *);
   34 static const struct hpack_index *
   35          hpack_table_getbyheader(struct hpack_header *,
   36             struct hpack_index *, struct hpack_table *);
   37 static int   hpack_table_add(struct hpack_header *,
   38             struct hpack_table *);
   39 static int   hpack_table_evict(long, long, struct hpack_table *);
   40 static int   hpack_table_setsize(long, struct hpack_table *);
   41 
   42 static long  hpack_decode_int(struct hbuf *, unsigned char);
   43 static char *hpack_decode_str(struct hbuf *, unsigned char);
   44 static int   hpack_decode_buf(struct hbuf *, struct hpack_table *);
   45 static long  hpack_decode_index(struct hbuf *, unsigned char,
   46             const struct hpack_index **, struct hpack_table *);
   47 static int   hpack_decode_literal(struct hbuf *, unsigned char,
   48             struct hpack_table *);
   49 static int   hpack_encode_int(struct hbuf *, long, unsigned char,
   50             unsigned char);
   51 static int   hpack_encode_str(struct hbuf *, char *);
   52 
   53 static int   hpack_huffman_init(void);
   54 static struct hpack_huffman_node *
   55          hpack_huffman_new(void);
   56 static void  hpack_huffman_free(struct hpack_huffman_node *);
   57 
   58 static struct hbuf *
   59          hbuf_new(unsigned char *, size_t);
   60 static void  hbuf_free(struct hbuf *);
   61 static int   hbuf_writechar(struct hbuf *, unsigned char);
   62 static int   hbuf_writebuf(struct hbuf *, unsigned char *, size_t);
   63 static unsigned char *
   64          hbuf_release(struct hbuf *, size_t *);
   65 static int   hbuf_readchar(struct hbuf *, unsigned char *);
   66 static int   hbuf_readbuf(struct hbuf *, unsigned char **, size_t);
   67 static int   hbuf_advance(struct hbuf *, size_t);
   68 static size_t    hbuf_left(struct hbuf *);
   69 
   70 static struct hpack  hpack_global;
   71 
   72 #ifdef  __GLIBC__
   73 /* these functions are available on BSD, but not on Linux */
   74 
   75 #include    <stdlib.h>
   76 
   77 void *
   78 recallocarray(void *ptr, size_t oldnmemb, size_t nmemb, size_t size)
   79 {
   80     void    *res;
   81 
   82     if(ptr == NULL)
   83         return calloc(nmemb, size);
   84     /* the code should really be like this, but the Linux reallocarray does not zero correctly the additional memory
   85     if((res = reallocarray(ptr, nmemb, size)) == NULL)
   86         return NULL;
   87     */
   88     if((res = calloc(nmemb, size)) == NULL)
   89         return NULL;
   90     memcpy(res, ptr, size * (nmemb > oldnmemb? oldnmemb: nmemb));
   91     return res;
   92 }
   93 
   94 void
   95 freezero(void *ptr, size_t size)
   96 {
   97     if(ptr == NULL)
   98         return;
   99     free(ptr);
  100     return;
  101 }
  102 
  103 #endif
  104 
  105 int
  106 hpack_init(void)
  107 {
  108     /* Initialize the huffman tree */
  109     if (hpack_huffman_init() == -1)
  110         return (-1);
  111 
  112     return (0);
  113 }
  114 
  115 struct hpack_header *
  116 hpack_header_new(void)
  117 {
  118     return (calloc(1, sizeof(struct hpack_header)));
  119 }
  120 
  121 struct hpack_header *
  122 hpack_header_add(struct hpack_headerblock *hdrs, const char *name,
  123     const char *value, enum hpack_header_index index)
  124 {
  125     struct hpack_header *hdr;
  126 
  127     if ((hdr = hpack_header_new()) == NULL)
  128         return (NULL);
  129     hdr->hdr_name = strdup(name);
  130     hdr->hdr_value = strdup(value);
  131     hdr->hdr_index = index;
  132     if (hdr->hdr_name == NULL || hdr->hdr_value == NULL) {
  133         hpack_header_free(hdr);
  134         return (NULL);
  135     }
  136     TAILQ_INSERT_TAIL(hdrs, hdr, hdr_entry);
  137 
  138     return (hdr);
  139 }
  140 
  141 void
  142 hpack_header_free(struct hpack_header *hdr)
  143 {
  144     if (hdr == NULL)
  145         return;
  146     free(hdr->hdr_name);
  147     free(hdr->hdr_value);
  148     free(hdr);
  149 }
  150 
  151 struct hpack_headerblock *
  152 hpack_headerblock_new(void)
  153 {
  154     struct hpack_headerblock    *hdrs;
  155     if ((hdrs = calloc(1, sizeof(*hdrs))) == NULL)
  156         return (NULL);
  157     TAILQ_INIT(hdrs);
  158     return (hdrs);
  159 }
  160 
  161 void
  162 hpack_headerblock_free(struct hpack_headerblock *hdrs)
  163 {
  164     struct hpack_header *hdr;
  165 
  166     if (hdrs == NULL)
  167         return;
  168     while ((hdr = TAILQ_FIRST(hdrs)) != NULL) {
  169         TAILQ_REMOVE(hdrs, hdr, hdr_entry);
  170         hpack_header_free(hdr);
  171     }
  172 }
  173 
  174 struct hpack_table *
  175 hpack_table_new(size_t max_table_size)
  176 {
  177     struct hpack_table  *hpack;
  178 
  179     if ((hpack = calloc(1, sizeof(*hpack))) == NULL)
  180         return (NULL);
  181     if ((hpack->htb_dynamic = hpack_headerblock_new()) == NULL) {
  182         free(hpack);
  183         return (NULL);
  184     }
  185     hpack->htb_max_table_size = hpack->htb_table_size =
  186         max_table_size == 0 ? HPACK_MAX_TABLE_SIZE : max_table_size;
  187 
  188     return (hpack);
  189 }
  190 
  191 void
  192 hpack_table_free(struct hpack_table *hpack)
  193 {
  194     if (hpack == NULL)
  195         return;
  196     hpack_headerblock_free(hpack->htb_dynamic);
  197     free(hpack);
  198 }
  199 
  200 static const struct hpack_index *
  201 hpack_table_getbyid(long index, struct hpack_index *idbuf,
  202     struct hpack_table *hpack)
  203 {
  204     struct hpack_index      *id = NULL;
  205     struct hpack_header     *hdr;
  206     long                 dynidx = HPACK_STATIC_SIZE;
  207 
  208     if (index < 1 || index > dynidx + (long)hpack->htb_dynamic_size)
  209         return (NULL);
  210 
  211     if (index <= dynidx) {
  212         /* Static table */
  213         id = &static_table[index - 1];
  214         if (id->hpi_id != index)
  215             DPRINTF("corrupted HPACK static table %ld != %ld",
  216                 id->hpi_id, index);
  217     } else {
  218         /* Dynamic table */
  219         TAILQ_FOREACH_REVERSE(hdr, hpack->htb_dynamic,
  220             hpack_headerblock, hdr_entry) {
  221             dynidx++;
  222             if (dynidx == index) {
  223                 idbuf->hpi_id = index;
  224                 idbuf->hpi_name = hdr->hdr_name;
  225                 idbuf->hpi_value = hdr->hdr_value;
  226                 id = idbuf;
  227                 break;
  228             }
  229         }
  230     }
  231 
  232     return (id);
  233 }
  234 
  235 static const struct hpack_index *
  236 hpack_table_getbyheader(struct hpack_header *key, struct hpack_index *idbuf,
  237     struct hpack_table *hpack)
  238 {
  239     struct hpack_index      *id = NULL, *firstid = NULL;
  240     struct hpack_header     *hdr;
  241     size_t               i, dynidx = HPACK_STATIC_SIZE;
  242 
  243     if (key->hdr_name == NULL)
  244         return (NULL);
  245 
  246     /*
  247      * Search the static and dynamic tables for a perfect match
  248      * or the first match that only matches the name.
  249      */
  250 
  251     /* Static table */
  252     for (i = 0; i < dynidx; i++) {
  253         id = &static_table[i];
  254         if (strcasecmp(id->hpi_name, key->hdr_name) != 0)
  255             continue;
  256         if (firstid == NULL) {
  257             memcpy(idbuf, id, sizeof(*id));
  258             idbuf->hpi_value = NULL;
  259             firstid = idbuf;
  260         }
  261         if ((id->hpi_value != NULL && key->hdr_value != NULL) &&
  262             strcasecmp(id->hpi_value, key->hdr_value) == 0)
  263             return (id);
  264     }
  265 
  266     /* Dynamic table */
  267     TAILQ_FOREACH_REVERSE(hdr, hpack->htb_dynamic,
  268         hpack_headerblock, hdr_entry) {
  269         dynidx++;
  270         if (strcasecmp(hdr->hdr_name, key->hdr_name) != 0)
  271             continue;
  272         if (firstid == NULL) {
  273             idbuf->hpi_id = dynidx;
  274             idbuf->hpi_name = hdr->hdr_name;
  275             idbuf->hpi_value = NULL;
  276             firstid = idbuf;
  277         }
  278         if ((hdr->hdr_value != NULL && key->hdr_value != NULL) &&
  279             strcasecmp(hdr->hdr_value, key->hdr_value) == 0) {
  280             idbuf->hpi_id = dynidx;
  281             idbuf->hpi_name = hdr->hdr_name;
  282             idbuf->hpi_value = hdr->hdr_value;
  283             id = idbuf;
  284             return (id);
  285         }
  286     }
  287 
  288     return (firstid);
  289 }
  290 
  291 static int
  292 hpack_table_add(struct hpack_header *hdr, struct hpack_table *hpack)
  293 {
  294     long         newsize;
  295 
  296     if (hdr->hdr_index != HPACK_INDEX)
  297         return (0);
  298 
  299     /*
  300      * Following RFC 7451 section 4.1,
  301      * the additional 32 octets account for an estimated overhead
  302      * associated with an entry.
  303      */
  304     newsize = strlen(hdr->hdr_name) + strlen(hdr->hdr_value) + 32;
  305 
  306     if (newsize > hpack->htb_table_size) {
  307         /*
  308          * An entry larger than the maximum size causes
  309          * the table to be emptied of all existing entries.
  310          */
  311         hpack_table_evict(0, newsize, hpack);
  312         return (0);
  313     } else
  314         hpack_table_evict(hpack->htb_table_size,
  315             newsize, hpack);
  316 
  317     if (hpack_header_add(hpack->htb_dynamic,
  318         hdr->hdr_name, hdr->hdr_value, hdr->hdr_index) == NULL)
  319         return (-1);
  320     hpack->htb_dynamic_entries++;
  321     hpack->htb_dynamic_size += newsize;
  322 
  323     return (0);
  324 }
  325 
  326 static int
  327 hpack_table_evict(long size, long newsize, struct hpack_table *hpack)
  328 {
  329     struct hpack_header *hdr;
  330 
  331     while (size < (hpack->htb_dynamic_size + newsize) &&
  332         (hdr = TAILQ_FIRST(hpack->htb_dynamic)) != NULL) {
  333         TAILQ_REMOVE(hpack->htb_dynamic, hdr, hdr_entry);
  334         hpack->htb_dynamic_entries--;
  335         hpack->htb_dynamic_size -=
  336             strlen(hdr->hdr_name) +
  337             strlen(hdr->hdr_value) +
  338             32;
  339         hpack_header_free(hdr);
  340     }
  341 
  342     if (TAILQ_EMPTY(hpack->htb_dynamic) &&
  343         hpack->htb_dynamic_entries != 0 &&
  344         hpack->htb_dynamic_size != 0)
  345         DPRINTF("corrupted HPACK dynamic table");
  346 
  347     return (0);
  348 }
  349 
  350 static int
  351 hpack_table_setsize(long size, struct hpack_table *hpack)
  352 {
  353     if (size > hpack->htb_max_table_size)
  354         return (-1);
  355 
  356     if (hpack_table_evict(size, 0, hpack) == -1)
  357         return (-1);
  358     hpack->htb_table_size = size;
  359 
  360     return (0);
  361 }
  362 
  363 size_t
  364 hpack_table_size(struct hpack_table *hpack)
  365 {
  366     return ((size_t)hpack->htb_dynamic_size);
  367 }
  368 
  369 struct hpack_headerblock *
  370 hpack_decode(unsigned char *data, size_t len, struct hpack_table *hpack)
  371 {
  372     struct hpack_headerblock    *hdrs = NULL;
  373     struct hbuf         *hbuf = NULL;
  374     struct hpack_table      *ctx = NULL;
  375     int              ret = -1;
  376 
  377     if (len == 0 || len > LONG_MAX)
  378 
  379     if (hpack == NULL && (hpack = ctx = hpack_table_new(0)) == NULL)
  380         goto fail;
  381     if ((hdrs = hpack_headerblock_new()) == NULL)
  382         goto fail;
  383 
  384     hpack->htb_headers = hdrs;
  385     hpack->htb_next = NULL;
  386 
  387     if ((hbuf = hbuf_new(data, len)) == NULL)
  388         goto fail;
  389 
  390     do {
  391         if (hpack_decode_buf(hbuf, hpack) == -1)
  392             goto fail;
  393     } while (hbuf_left(hbuf) > 0);
  394 
  395     ret = 0;
  396  fail:
  397     hbuf_free(hbuf);
  398     if (ret != 0) {
  399         hpack_headerblock_free(hdrs);
  400         hdrs = NULL;
  401     } else
  402         hdrs = hpack->htb_headers;
  403     hpack->htb_headers = NULL;
  404     hpack->htb_next = NULL;
  405 
  406     /* Free the local table (for single invocations) */
  407     hpack_table_free(ctx);
  408 
  409     return (hdrs);
  410 }
  411 
  412 static long
  413 hpack_decode_int(struct hbuf *buf, unsigned char prefix)
  414 {
  415     unsigned long    i = 0;
  416     unsigned char    b = 0, m;
  417 
  418     if (hbuf_left(buf) == 0)
  419         return (-1);
  420 
  421     if (hbuf_readchar(buf, &b) == -1 ||
  422         hbuf_advance(buf, 1) == -1)
  423         return (-1);
  424 
  425     /* Mask and remainder after the prefix of the first octet */
  426     m = ~prefix;
  427     i = b & m;
  428 
  429     if (i >= m) {
  430         m = 0;
  431 
  432         /* Read varint bits while the 0x80 bit is set */
  433         do {
  434             if (i > LONG_MAX)
  435                 return (-1);
  436             if (hbuf_readchar(buf, &b) == -1 ||
  437                 hbuf_advance(buf, 1) == -1)
  438                 return (-1);
  439             i += (b & ~0x80) << m;
  440             m += 7;
  441         } while (b & 0x80);
  442     }
  443 
  444     return ((long)i);
  445 }
  446 
  447 static long
  448 hpack_decode_index(struct hbuf *buf, unsigned char prefix,
  449     const struct hpack_index **idptr, struct hpack_table *hpack)
  450 {
  451     struct hpack_index       idbuf;
  452     struct hpack_header     *hdr = hpack->htb_next;
  453     const struct hpack_index    *id;
  454     long                 i;
  455     int              hasvalue;
  456 
  457     if (idptr != NULL)
  458         *idptr = NULL;
  459 
  460     if ((i = hpack_decode_int(buf, prefix)) == -1)
  461         return (-1);
  462     DPRINTF("%s: index %ld", __func__, i);
  463 
  464     if (i == 0)
  465         return (0);
  466     if ((id = hpack_table_getbyid(i, &idbuf, hpack)) == NULL) {
  467         DPRINTF("index not found: %ld\n", i);
  468         return (-1);
  469     }
  470 
  471     if (hdr == NULL || hdr->hdr_name != NULL || hdr->hdr_value != NULL)
  472         DPRINTF("invalid header");
  473 
  474     if ((hdr->hdr_name = strdup(id->hpi_name)) == NULL)
  475         return (-1);
  476     hasvalue = id->hpi_value == NULL ? 0 : 1;
  477     if (hasvalue &&
  478         (hdr->hdr_value = strdup(id->hpi_value)) == NULL) {
  479         free(hdr->hdr_name);
  480         hdr->hdr_name = NULL;
  481         return (-1);
  482     }
  483 
  484     DPRINTF("%s: index: %ld (%s%s%s)", __func__,
  485         i, id->hpi_name,
  486         hasvalue ? ": " : "",
  487         hasvalue ? id->hpi_value : "");
  488 
  489     if (idptr != NULL)
  490         *idptr = id;
  491 
  492     return (i);
  493 }
  494 
  495 static char *
  496 hpack_decode_str(struct hbuf *buf, unsigned char prefix)
  497 {
  498     long         i;
  499     unsigned char   *ptr, c;
  500     char        *str;
  501 
  502     if (hbuf_readchar(buf, &c) == -1)
  503         return (NULL);
  504     if ((i = hpack_decode_int(buf, prefix)) == -1)
  505         return (NULL);
  506     if (hbuf_readbuf(buf, &ptr, (size_t)i) == -1 ||
  507         hbuf_advance(buf, (size_t)i) == -1)
  508         return (NULL);
  509     if ((c & HPACK_M_LITERAL) == HPACK_F_LITERAL_HUFFMAN) {
  510         DPRINTF("%s: decoding huffman code (size %ld)", __func__, i);
  511         if ((str = hpack_huffman_decode_str(ptr, (size_t)i)) == NULL)
  512             return (NULL);
  513     } else {
  514         if ((str = calloc(1, (size_t)i + 1)) == NULL)
  515             return (NULL);
  516         memcpy(str, ptr, (size_t)i);
  517     }
  518     return (str);
  519 }
  520 
  521 static int
  522 hpack_decode_literal(struct hbuf *buf, unsigned char prefix,
  523     struct hpack_table *hpack)
  524 {
  525     struct hpack_header     *hdr = hpack->htb_next;
  526     const struct hpack_index    *id;
  527     long                 i;
  528     char                *str;
  529 
  530     if ((i = hpack_decode_index(buf, prefix, &id, hpack)) == -1)
  531         return (-1);
  532 
  533     if (i == 0) {
  534         if (hdr == NULL ||
  535             hdr->hdr_name != NULL || hdr->hdr_value != NULL)
  536             DPRINTF("invalid header");
  537 
  538         if ((str = hpack_decode_str(buf,
  539             HPACK_M_LITERAL)) == NULL)
  540             return (-1);
  541         DPRINTF("%s: name: %s", __func__, str);
  542         hdr->hdr_name = str;
  543     }
  544 
  545     /* The index might have set a default value */
  546     if (hdr->hdr_value != NULL) {
  547         free(hdr->hdr_value);
  548         hdr->hdr_value = NULL;
  549     }
  550 
  551     if ((str = hpack_decode_str(buf, HPACK_M_LITERAL)) == NULL)
  552         return (-1);
  553     DPRINTF("%s: value: %s", __func__, str);
  554     hdr->hdr_value = str;
  555 
  556     return (0);
  557 }
  558 
  559 static int
  560 hpack_decode_buf(struct hbuf *buf, struct hpack_table *hpack)
  561 {
  562     struct hpack_header *hdr = NULL;
  563     unsigned char        c;
  564     long             i;
  565 
  566     if (hbuf_readchar(buf, &c) == -1)
  567         goto fail;
  568 
  569     if ((hdr = hpack_header_new()) == NULL)
  570         goto fail;
  571     hdr->hdr_index = HPACK_NO_INDEX;
  572     hpack->htb_next = hdr;
  573 
  574     /* 6.1 Indexed Header Field Representation */
  575     if ((c & HPACK_M_INDEX) == HPACK_F_INDEX) {
  576         DPRINTF("%s: 0x%02x: 6.1 index", __func__, c);
  577 
  578         /* 7 bit index */
  579         if ((i = hpack_decode_index(buf,
  580             HPACK_M_INDEX, NULL, hpack)) == -1)
  581             goto fail;
  582 
  583         /* No value means header with empty value */
  584         if ((hdr->hdr_value == NULL) &&
  585             (hdr->hdr_value = strdup("")) == NULL)
  586             goto fail;
  587     }
  588 
  589     /* 6.2.1. Literal Header Field with Incremental Indexing */
  590     else if ((c & HPACK_M_LITERAL_INDEX) == HPACK_F_LITERAL_INDEX) {
  591         DPRINTF("%s: 0x%02x: 6.2.1 literal indexed", __func__, c);
  592 
  593         /* 6 bit index */
  594         if (hpack_decode_literal(buf,
  595             HPACK_M_LITERAL_INDEX, hpack) == -1)
  596             goto fail;
  597         hdr->hdr_index = HPACK_INDEX;
  598     }
  599 
  600     /* 6.2.2. Literal Header Field without Indexing */
  601     else if ((c & HPACK_M_LITERAL_NO_INDEX) == HPACK_F_LITERAL_NO_INDEX) {
  602         DPRINTF("%s: 0x%02x: 6.2.2 literal", __func__, c);
  603 
  604         /* 4 bit index */
  605         if (hpack_decode_literal(buf,
  606             HPACK_M_LITERAL_NO_INDEX, hpack) == -1)
  607             goto fail;
  608     }
  609 
  610     /* 6.2.3. Literal Header Field Never Indexed */
  611     else if ((c & HPACK_M_LITERAL_NO_INDEX) == HPACK_F_LITERAL_NO_INDEX) {
  612         DPRINTF("%s: 0x%02x: 6.2.3 literal never indexed", __func__, c);
  613 
  614         /* 4 bit index */
  615         if (hpack_decode_literal(buf,
  616             HPACK_M_LITERAL_NO_INDEX, hpack) == -1)
  617             goto fail;
  618         hdr->hdr_index = HPACK_NEVER_INDEX;
  619     }
  620 
  621     /* 6.3. Dynamic Table Size Update */
  622     else if ((c & HPACK_M_TABLE_SIZE_UPDATE) == HPACK_F_TABLE_SIZE_UPDATE) {
  623         DPRINTF("%s: 0x%02x: 6.3 dynamic table update", __func__, c);
  624 
  625         /* 5 bit index */
  626         if ((i = hpack_decode_int(buf,
  627             HPACK_M_TABLE_SIZE_UPDATE)) == -1)
  628             goto fail;
  629 
  630         if (hpack_table_setsize(i, hpack) == -1)
  631             goto fail;
  632 
  633         return (0);
  634     }
  635 
  636     /* unknown index */
  637     else {
  638         DPRINTF("%s: 0x%02x: unknown index", __func__, c);
  639         goto fail;
  640     }
  641 
  642     if (hdr->hdr_name == NULL || hdr->hdr_value == NULL)
  643         goto fail;
  644 
  645     /* Optionally add to index */
  646     if (hpack_table_add(hdr, hpack) == -1)
  647         goto fail;
  648 
  649     /* Add header to the list */
  650     TAILQ_INSERT_TAIL(hpack->htb_headers, hdr, hdr_entry);
  651     hpack->htb_next = NULL;
  652 
  653     return (0);
  654  fail:
  655     DPRINTF("%s: failed", __func__);
  656     hpack_header_free(hdr);
  657     hpack->htb_next = NULL;
  658 
  659     return (-1);
  660 }
  661 
  662 unsigned char *
  663 hpack_encode(struct hpack_headerblock *hdrs, size_t *encoded_len,
  664     struct hpack_table *hpack)
  665 {
  666     const struct hpack_index    *id;
  667     struct hpack_index       idbuf;
  668     struct hpack_table      *ctx = NULL;
  669     struct hpack_header     *hdr;
  670     struct hbuf         *hbuf = NULL;
  671     unsigned char            mask, flag;
  672 
  673     if (hpack == NULL && (hpack = ctx = hpack_table_new(0)) == NULL)
  674         goto fail;
  675 
  676     if ((hbuf = hbuf_new(NULL, BUFSIZ)) == NULL)
  677         goto fail;
  678 
  679     TAILQ_FOREACH(hdr, hdrs, hdr_entry) {
  680         DPRINTF("%s: header %s: %s (index %d)", __func__,
  681             hdr->hdr_name,
  682             hdr->hdr_value == NULL ? "(null)" : hdr->hdr_value,
  683             hdr->hdr_index);
  684 
  685         switch (hdr->hdr_index) {
  686         case HPACK_INDEX:
  687             mask = HPACK_M_LITERAL_INDEX;
  688             flag = HPACK_F_LITERAL_INDEX;
  689             break;
  690         case HPACK_NO_INDEX:
  691             mask = HPACK_M_LITERAL_NO_INDEX;
  692             flag = HPACK_F_LITERAL_NO_INDEX;
  693             break;
  694         case HPACK_NEVER_INDEX:
  695             mask = HPACK_M_LITERAL_NEVER_INDEX;
  696             flag = HPACK_F_LITERAL_NEVER_INDEX;
  697             break;
  698         }
  699 
  700         id = hpack_table_getbyheader(hdr, &idbuf, hpack);
  701 
  702         /* 6.1 Indexed Header Field Representation */
  703         if (id != NULL && id->hpi_value != NULL) {
  704             DPRINTF("%s: index %zu (%s: %s)", __func__,
  705                 id->hpi_id,
  706                 id->hpi_name,
  707                 id->hpi_value == NULL ? "(null)" : id->hpi_value);
  708             if (hpack_encode_int(hbuf, id->hpi_id,
  709                 HPACK_M_INDEX, HPACK_F_INDEX) == -1)
  710                 goto fail;
  711             continue;
  712         }
  713 
  714         /* 6.2 Literal Header Field Representation */
  715         else if (id != NULL) {
  716             DPRINTF("%s: index+name %zu, %s", __func__,
  717                 id->hpi_id,
  718                 hdr->hdr_value);
  719 
  720             if (hpack_encode_int(hbuf, id->hpi_id,
  721                 mask, flag) == -1)
  722                 goto fail;
  723         } else {
  724             DPRINTF("%s: literal %s: %s", __func__,
  725                 hdr->hdr_name,
  726                 hdr->hdr_value);
  727 
  728             if (hpack_encode_int(hbuf, 0, mask, flag) == -1)
  729                 goto fail;
  730 
  731             /* name */
  732             if (hpack_encode_str(hbuf, hdr->hdr_name) == -1)
  733                 goto fail;
  734         }
  735 
  736         /* value */
  737         if (hpack_encode_str(hbuf, hdr->hdr_value) == -1)
  738             goto fail;
  739 
  740         /* Optionally add to index */
  741         if (hpack_table_add(hdr, hpack) == -1)
  742             goto fail;
  743     }
  744 
  745     return (hbuf_release(hbuf, encoded_len));
  746  fail:
  747     hpack_table_free(ctx);
  748     hbuf_free(hbuf);
  749     return (NULL);
  750 }
  751 
  752 static int
  753 hpack_encode_int(struct hbuf *buf, long i, unsigned char prefix,
  754     unsigned char type)
  755 {
  756     unsigned char   b, m;
  757 
  758     if (i < 0)
  759         return (-1);
  760 
  761     /* The first octet encodes up to prefix length bits */
  762     m = ~prefix;
  763     if (i <= m)
  764         b = (i & m) | type;
  765     else
  766         b = m | type;
  767     if (hbuf_writechar(buf, b) == -1)
  768         return (-1);
  769     i -= m;
  770 
  771     /* Encode the remainder as a varint */
  772     for (m = 0x80; i >= m; i /= m) {
  773         b = i % m + m;
  774         /* Set the continuation bit if there are steps left */
  775         if (i >= m)
  776             b |= m;
  777         if (hbuf_writechar(buf, b) == -1)
  778             return (-1);
  779     }
  780     if (i > 0 &&
  781         hbuf_writechar(buf, (unsigned char)i) == -1)
  782         return (-1);
  783 
  784     return (0);
  785 }
  786 
  787 static int
  788 hpack_encode_str(struct hbuf *buf, char *str)
  789 {
  790     unsigned char   *data = NULL;
  791     size_t       len, slen;
  792     int      ret = -1;
  793 
  794     /*
  795      * We have to decide if the string should be encoded with huffman
  796      * encoding or as literal string.  There could be better heuristics
  797      * to do this...
  798      */
  799     slen = strlen(str);
  800     if ((data = hpack_huffman_encode(str, slen, &len)) == NULL)
  801         goto done;
  802     if (len > 0 && len < slen) {
  803         DPRINTF("%s: encoded huffman code (size %ld, from %ld)",
  804             __func__, len, slen);
  805         if (hpack_encode_int(buf, len, HPACK_M_LITERAL,
  806             HPACK_F_LITERAL_HUFFMAN) == -1)
  807             goto done;
  808         if (hbuf_writebuf(buf, data, len) == -1)
  809             goto done;
  810     } else {
  811         if (hpack_encode_int(buf, slen, HPACK_M_LITERAL,
  812             HPACK_F_LITERAL) == -1)
  813             goto done;
  814         if (hbuf_writebuf(buf, str, slen) == -1)
  815             goto done;
  816     }
  817 
  818     ret = 0;
  819  done:
  820     free(data);
  821     return (ret);
  822 }
  823 
  824 static int
  825 hpack_huffman_init(void)
  826 {
  827     struct hpack_huffman        *hph;
  828     struct hpack_huffman_node   *root, *cur, *node;
  829     unsigned int             i, j;
  830 
  831     /* Create new Huffman tree */
  832     if ((root = hpack_huffman_new()) == NULL)
  833         return (-1);
  834 
  835     for (i = 0; i < HPACK_HUFFMAN_SIZE; i++) {
  836         hph = &huffman_table[i];
  837         cur = root;
  838 
  839         /* Create branch for each symbol */
  840         for (j = hph->hph_length; j > 0; j--) {
  841             if ((hph->hph_code >> (j - 1)) & 1) {
  842                 if (cur->hpn_one == NULL) {
  843                     if ((node =
  844                         hpack_huffman_new()) == NULL)
  845                         goto fail;
  846                     cur->hpn_one = node;
  847                 }
  848                 cur = cur->hpn_one;
  849             } else {
  850                 if (cur->hpn_zero == NULL) {
  851                     if ((node =
  852                         hpack_huffman_new()) == NULL)
  853                         goto fail;
  854                     cur->hpn_zero = node;
  855                 }
  856                 cur = cur->hpn_zero;
  857             }
  858         }
  859 
  860         /* The leaf node contains the (8-bit ASCII) symbol */
  861         cur->hpn_sym = i;
  862     }
  863 
  864     hpack_global.hpack_huffman = root;
  865     return (0);
  866  fail:
  867     hpack_huffman_free(root);
  868     hpack_global.hpack_huffman = NULL;
  869     return (-1);
  870 }
  871 
  872 unsigned char *
  873 hpack_huffman_decode(unsigned char *buf, size_t len, size_t *decoded_len)
  874 {
  875     struct hpack_huffman_node   *node, *root;
  876     unsigned int             i, j, code;
  877     struct hbuf         *hbuf = NULL;
  878 
  879     if ((root = node = hpack_global.hpack_huffman) == NULL)
  880         DPRINTF("hpack not initialized");
  881 
  882     if ((hbuf = hbuf_new(NULL, len)) == NULL)
  883         return (NULL);
  884 
  885     for (i = 0; i < len; i++) {
  886         code = buf[i];
  887 
  888         /* Walk the Huffman tree for each bit in the encoded input */
  889         for (j = 8; j > 0; j--) {
  890             if ((code >> (j - 1)) & 1)
  891                 node = node->hpn_one;
  892             else
  893                 node = node->hpn_zero;
  894             if (node->hpn_sym == -1)
  895                 continue;
  896 
  897             /* Leaf node of the next (8-bit ASCII) symbol */
  898             if (hbuf_writechar(hbuf, (unsigned char)node->hpn_sym) == -1) {
  899                 DPRINTF("%s: failed to add '%c'", __func__, node->hpn_sym);
  900                 goto fail;
  901             }
  902             node = root;
  903         }
  904     }
  905 
  906     return (hbuf_release(hbuf, decoded_len));
  907  fail:
  908     *decoded_len = 0;
  909     hbuf_free(hbuf);
  910     return (NULL);
  911 }
  912 
  913 char *
  914 hpack_huffman_decode_str(unsigned char *buf, size_t len)
  915 {
  916     unsigned char   *data;
  917     char        *str;
  918     size_t       data_len;
  919 
  920     if ((data = hpack_huffman_decode(buf, len, &data_len)) == NULL)
  921         return (NULL);
  922 
  923     /* Allocate with an extra NUL character */
  924     if ((str = recallocarray(data, data_len, data_len + 1, 1)) == NULL) {
  925         freezero(data, data_len);
  926         return (NULL);
  927     }
  928 
  929     /* Check if this is an actual string (no matter of the encoding) */
  930     if (strlen(str) != data_len) {
  931         freezero(str, data_len + 1);
  932         str = NULL;
  933     }
  934 
  935     return (str);
  936 }
  937 
  938 unsigned char *
  939 hpack_huffman_encode(unsigned char *data, size_t len, size_t *encoded_len)
  940 {
  941     struct hbuf     *hbuf;
  942     struct hpack_huffman    *hph;
  943     unsigned int         code, i, j;
  944     unsigned char        o, obits;
  945 
  946     if ((hbuf = hbuf_new(NULL, len)) == NULL)
  947         return (NULL);
  948 
  949     for (i = 0, o = 0, obits = 8; i < len; i++) {
  950         /* Get Huffman code for each (8-bit ASCII) symbol */
  951         hph = &huffman_table[data[i]];
  952 
  953         for (code = hph->hph_code, j = hph->hph_length; j > 0;) {
  954             if (j > obits) {
  955                 /* More bits to encode for this symbol */
  956                 j -= obits;
  957                 o |= (code >> j) & 0xff;
  958                 obits = 0;
  959             } else {
  960                 /*
  961                  * Remaining bits to encode for this input
  962                  * symbol.  The current output octet will
  963                  * include bits from the next symbol or padding.
  964                  */
  965                 obits -= j;
  966                 o |= (code << obits) & 0xff;
  967                 j = 0;
  968             }
  969             if (obits == 0) {
  970                 if (hbuf_writechar(hbuf, o) == -1) {
  971                     DPRINTF("%s: failed to add '%c'",
  972                         __func__, o);
  973                     goto fail;
  974                 }
  975                 o = 0;
  976                 obits = 8;
  977             }
  978         }
  979     }
  980 
  981     if (len && obits > 0 && obits < 8) {
  982         /* Pad last octet with ones (EOS) */
  983         o |= (1 << obits) - 1;
  984         if (hbuf_writechar(hbuf, o) == -1) {
  985             DPRINTF("%s: failed to add '%c'", __func__, o);
  986             goto fail;
  987         }
  988     }
  989 
  990     return (hbuf_release(hbuf, encoded_len));
  991  fail:
  992     *encoded_len = 0;
  993     hbuf_free(hbuf);
  994     return (NULL);
  995 }
  996 
  997 static struct hpack_huffman_node *
  998 hpack_huffman_new(void)
  999 {
 1000     struct hpack_huffman_node   *node;
 1001 
 1002     if ((node = calloc(1, sizeof(*node))) == NULL)
 1003         return (NULL);
 1004     node->hpn_sym = -1;
 1005 
 1006     return (node);
 1007 }
 1008 
 1009 static void
 1010 hpack_huffman_free(struct hpack_huffman_node *root)
 1011 {
 1012     if (root == NULL)
 1013         return;
 1014     hpack_huffman_free(root->hpn_zero);
 1015     hpack_huffman_free(root->hpn_one);
 1016     free(root);
 1017 }
 1018 
 1019 static struct hbuf *
 1020 hbuf_new(unsigned char *data, size_t len)
 1021 {
 1022     struct hbuf *buf;
 1023     size_t       size = len;
 1024 
 1025     if ((buf = calloc(1, sizeof(*buf))) == NULL)
 1026         return (NULL);
 1027     size = MAX(HPACK_HUFFMAN_BUFSZ, len);
 1028     if ((buf->data = calloc(1, size)) == NULL) {
 1029         free(buf);
 1030         return (NULL);
 1031     }
 1032     if (data != NULL) {
 1033         memcpy(buf->data, data, len);
 1034         buf->wpos = len;
 1035     }
 1036     buf->size = buf->wbsz = size;
 1037     return (buf);
 1038 }
 1039 
 1040 static void
 1041 hbuf_free(struct hbuf *buf)
 1042 {
 1043     if (buf == NULL)
 1044         return;
 1045     freezero(buf->data, buf->size);
 1046     free(buf);
 1047 }
 1048 
 1049 static int
 1050 hbuf_realloc(struct hbuf *buf, size_t len)
 1051 {
 1052     unsigned char   *ptr;
 1053     size_t       newsize;
 1054 
 1055     /* Allocate a multiple of the initial write buffer size */
 1056     newsize = (buf->size + len + (buf->wbsz - 1)) & ~(buf->wbsz - 1);
 1057 
 1058     DPRINTF("%s: size %zu -> %zu", __func__, buf->size, newsize);
 1059 
 1060     if ((ptr = recallocarray(buf->data, buf->size, newsize, 1)) == NULL)
 1061         return (-1);
 1062     buf->data = ptr;
 1063     buf->size = newsize;
 1064 
 1065     return (0);
 1066 }
 1067 
 1068 static int
 1069 hbuf_writechar(struct hbuf *buf, unsigned char c)
 1070 {
 1071     return (hbuf_writebuf(buf, &c, 1));
 1072 }
 1073 
 1074 static int
 1075 hbuf_writebuf(struct hbuf *buf, unsigned char *data, size_t len)
 1076 {
 1077     if ((buf->wpos + len > buf->size) &&
 1078         hbuf_realloc(buf, len) == -1)
 1079         return (-1);
 1080 
 1081     memcpy(buf->data + buf->wpos, data, len);
 1082     buf->wpos += len;
 1083 
 1084     return (0);
 1085 }
 1086 
 1087 static unsigned char *
 1088 hbuf_release(struct hbuf *buf, size_t *len)
 1089 {
 1090     unsigned char   *data;
 1091 
 1092     /*
 1093      * Adjust (shrink) buffer to the used size.  This allows to
 1094      * safely call recallocarray() or freezero() later.
 1095      */
 1096     if (buf->wpos != buf->size) {
 1097         if ((data = recallocarray(buf->data,
 1098             buf->size, buf->wpos, 1)) == NULL) {
 1099             hbuf_free(buf);
 1100             return (NULL);
 1101         }
 1102         buf->data = data;
 1103     }
 1104 
 1105     *len = buf->wpos;
 1106     data = buf->data;
 1107     free(buf);
 1108 
 1109     return (data);
 1110 }
 1111 
 1112 static int
 1113 hbuf_readchar(struct hbuf *buf, unsigned char *c)
 1114 {
 1115     if (buf->rpos + 1 > buf->size)
 1116         return (-1);
 1117     *c = *(buf->data + buf->rpos);
 1118     return (0);
 1119 }
 1120 
 1121 static int
 1122 hbuf_readbuf(struct hbuf *buf, unsigned char **ptr, size_t len)
 1123 {
 1124     if (buf->rpos + len > buf->size)
 1125         return (-1);
 1126     *ptr = buf->data + buf->rpos;
 1127     return (0);
 1128 }
 1129 
 1130 static int
 1131 hbuf_advance(struct hbuf *buf, size_t len)
 1132 {
 1133     if (buf->rpos + len > buf->size)
 1134         return (-1);
 1135     buf->rpos += len;
 1136     return (0);
 1137 }
 1138 
 1139 static size_t
 1140 hbuf_left(struct hbuf *buf)
 1141 {
 1142     if (buf->rpos >= buf->wpos)
 1143         return (0);
 1144     return (buf->wpos - buf->rpos);
 1145 }