Adding upstream version 2.4.38.upstream/2.4.38

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1060 insertions, 0 deletions

diff --git a/modules/http2/h2_push.c b/modules/http2/h2_push.c
new file mode 100644
index 0000000..9a3b19b
--- /dev/null
+++ b/modules/http2/h2_push.c
@@ -0,0 +1,1060 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+ 
+#include <assert.h>
+#include <stdio.h>
+
+#include <apr_lib.h>
+#include <apr_strings.h>
+#include <apr_hash.h>
+#include <apr_time.h>
+
+#ifdef H2_OPENSSL
+#include <openssl/sha.h>
+#endif
+
+#include <httpd.h>
+#include <http_core.h>
+#include <http_log.h>
+
+#include "h2_private.h"
+#include "h2_h2.h"
+#include "h2_util.h"
+#include "h2_push.h"
+#include "h2_request.h"
+#include "h2_headers.h"
+#include "h2_session.h"
+#include "h2_stream.h"
+
+/*******************************************************************************
+ * link header handling 
+ ******************************************************************************/
+
+static const char *policy_str(h2_push_policy policy)
+{
+    switch (policy) {
+        case H2_PUSH_NONE:
+            return "none";
+        case H2_PUSH_FAST_LOAD:
+            return "fast-load";
+        case H2_PUSH_HEAD:
+            return "head";
+        default:
+            return "default";
+    }
+}
+
+typedef struct {
+    const h2_request *req;
+    int push_policy;
+    apr_pool_t *pool;
+    apr_array_header_t *pushes;
+    const char *s;
+    size_t slen;
+    size_t i;
+    
+    const char *link;
+    apr_table_t *params;
+    char b[4096];
+} link_ctx;
+
+static int attr_char(char c) 
+{
+    switch (c) {
+        case '!':
+        case '#':
+        case '$':
+        case '&':
+        case '+':
+        case '-':
+        case '.':
+        case '^':
+        case '_':
+        case '`':
+        case '|':
+        case '~':
+            return 1;
+        default:
+            return apr_isalnum(c);
+    }
+}
+
+static int ptoken_char(char c) 
+{
+    switch (c) {
+        case '!':
+        case '#':
+        case '$':
+        case '&':
+        case '\'':
+        case '(':
+        case ')':
+        case '*':
+        case '+':
+        case '-':
+        case '.':
+        case '/':
+        case ':':
+        case '<':
+        case '=':
+        case '>':
+        case '?':
+        case '@':
+        case '[':
+        case ']':
+        case '^':
+        case '_':
+        case '`':
+        case '{':
+        case '|':
+        case '}':
+        case '~':
+            return 1;
+        default:
+            return apr_isalnum(c);
+    }
+}
+
+static int skip_ws(link_ctx *ctx)
+{
+    char c;
+    while (ctx->i < ctx->slen 
+           && (((c = ctx->s[ctx->i]) == ' ') || (c == '\t'))) {
+        ++ctx->i;
+    }
+    return (ctx->i < ctx->slen);
+}
+
+static int find_chr(link_ctx *ctx, char c, size_t *pidx)
+{
+    size_t j;
+    for (j = ctx->i; j < ctx->slen; ++j) {
+        if (ctx->s[j] == c) {
+            *pidx = j;
+            return 1;
+        }
+    } 
+    return 0;
+}
+
+static int read_chr(link_ctx *ctx, char c)
+{
+    if (ctx->i < ctx->slen && ctx->s[ctx->i] == c) {
+        ++ctx->i;
+        return 1;
+    }
+    return 0;
+}
+
+static char *mk_str(link_ctx *ctx, size_t end) 
+{
+    if (ctx->i < end) {
+        return apr_pstrndup(ctx->pool, ctx->s + ctx->i, end - ctx->i);
+    }
+    return (char*)"";
+}
+
+static int read_qstring(link_ctx *ctx, const char **ps)
+{
+    if (skip_ws(ctx) && read_chr(ctx, '\"')) {
+        size_t end;
+        if (find_chr(ctx, '\"', &end)) {
+            *ps = mk_str(ctx, end);
+            ctx->i = end + 1;
+            return 1;
+        }
+    }
+    return 0;
+}
+
+static int read_ptoken(link_ctx *ctx, const char **ps)
+{
+    if (skip_ws(ctx)) {
+        size_t i;
+        for (i = ctx->i; i < ctx->slen && ptoken_char(ctx->s[i]); ++i) {
+            /* nop */
+        }
+        if (i > ctx->i) {
+            *ps = mk_str(ctx, i);
+            ctx->i = i;
+            return 1;
+        }
+    }
+    return 0;
+}
+
+
+static int read_link(link_ctx *ctx)
+{
+    if (skip_ws(ctx) && read_chr(ctx, '<')) {
+        size_t end;
+        if (find_chr(ctx, '>', &end)) {
+            ctx->link = mk_str(ctx, end);
+            ctx->i = end + 1;
+            return 1;
+        }
+    }
+    return 0;
+}
+
+static int read_pname(link_ctx *ctx, const char **pname)
+{
+    if (skip_ws(ctx)) {
+        size_t i;
+        for (i = ctx->i; i < ctx->slen && attr_char(ctx->s[i]); ++i) {
+            /* nop */
+        }
+        if (i > ctx->i) {
+            *pname = mk_str(ctx, i);
+            ctx->i = i;
+            return 1;
+        }
+    }
+    return 0;
+}
+
+static int read_pvalue(link_ctx *ctx, const char **pvalue)
+{
+    if (skip_ws(ctx) && read_chr(ctx, '=')) {
+        if (read_qstring(ctx, pvalue) || read_ptoken(ctx, pvalue)) {
+            return 1;
+        }
+    }
+    return 0;
+}
+
+static int read_param(link_ctx *ctx)
+{
+    if (skip_ws(ctx) && read_chr(ctx, ';')) {
+        const char *name, *value = "";
+        if (read_pname(ctx, &name)) {
+            read_pvalue(ctx, &value); /* value is optional */
+            apr_table_setn(ctx->params, name, value);
+            return 1;
+        }
+    }
+    return 0;
+}
+
+static int read_sep(link_ctx *ctx)
+{
+    if (skip_ws(ctx) && read_chr(ctx, ',')) {
+        return 1;
+    }
+    return 0;
+}
+
+static void init_params(link_ctx *ctx) 
+{
+    if (!ctx->params) {
+        ctx->params = apr_table_make(ctx->pool, 5);
+    }
+    else {
+        apr_table_clear(ctx->params);
+    }
+}
+
+static int same_authority(const h2_request *req, const apr_uri_t *uri)
+{
+    if (uri->scheme != NULL && strcmp(uri->scheme, req->scheme)) {
+        return 0;
+    }
+    if (uri->hostinfo != NULL && strcmp(uri->hostinfo, req->authority)) {
+        return 0;
+    }
+    return 1;
+}
+
+static int set_push_header(void *ctx, const char *key, const char *value) 
+{
+    size_t klen = strlen(key);
+    if (H2_HD_MATCH_LIT("User-Agent", key, klen)
+        || H2_HD_MATCH_LIT("Accept", key, klen)
+        || H2_HD_MATCH_LIT("Accept-Encoding", key, klen)
+        || H2_HD_MATCH_LIT("Accept-Language", key, klen)
+        || H2_HD_MATCH_LIT("Cache-Control", key, klen)) {
+        apr_table_setn(ctx, key, value);
+    }
+    return 1;
+}
+
+static int has_param(link_ctx *ctx, const char *param)
+{
+    const char *p = apr_table_get(ctx->params, param);
+    return !!p;
+}
+
+static int has_relation(link_ctx *ctx, const char *rel)
+{
+    const char *s, *val = apr_table_get(ctx->params, "rel");
+    if (val) {
+        if (!strcmp(rel, val)) {
+            return 1;
+        }
+        s = ap_strstr_c(val, rel);
+        if (s && (s == val || s[-1] == ' ')) {
+            s += strlen(rel);
+            if (!*s || *s == ' ') {
+                return 1;
+            }
+        }
+    }
+    return 0;
+}
+
+static int add_push(link_ctx *ctx)
+{
+    /* so, we have read a Link header and need to decide
+     * if we transform it into a push.
+     */
+    if (has_relation(ctx, "preload") && !has_param(ctx, "nopush")) {
+        apr_uri_t uri;
+        if (apr_uri_parse(ctx->pool, ctx->link, &uri) == APR_SUCCESS) {
+            if (uri.path && same_authority(ctx->req, &uri)) {
+                char *path;
+                const char *method;
+                apr_table_t *headers;
+                h2_request *req;
+                h2_push *push;
+                
+                /* We only want to generate pushes for resources in the
+                 * same authority than the original request.
+                 * icing: i think that is wise, otherwise we really need to
+                 * check that the vhost/server is available and uses the same
+                 * TLS (if any) parameters.
+                 */
+                path = apr_uri_unparse(ctx->pool, &uri, APR_URI_UNP_OMITSITEPART);
+                push = apr_pcalloc(ctx->pool, sizeof(*push));
+                switch (ctx->push_policy) {
+                    case H2_PUSH_HEAD:
+                        method = "HEAD";
+                        break;
+                    default:
+                        method = "GET";
+                        break;
+                }
+                headers = apr_table_make(ctx->pool, 5);
+                apr_table_do(set_push_header, headers, ctx->req->headers, NULL);
+                req = h2_req_create(0, ctx->pool, method, ctx->req->scheme,
+                                    ctx->req->authority, path, headers,
+                                    ctx->req->serialize);
+                /* atm, we do not push on pushes */
+                h2_request_end_headers(req, ctx->pool, 1, 0);
+                push->req = req;
+                if (has_param(ctx, "critical")) {
+                    h2_priority *prio = apr_pcalloc(ctx->pool, sizeof(*prio));
+                    prio->dependency = H2_DEPENDANT_BEFORE;
+                    push->priority = prio;
+                }
+                if (!ctx->pushes) {
+                    ctx->pushes = apr_array_make(ctx->pool, 5, sizeof(h2_push*));
+                }
+                APR_ARRAY_PUSH(ctx->pushes, h2_push*) = push;
+            }
+        }
+    }
+    return 0;
+}
+
+static void inspect_link(link_ctx *ctx, const char *s, size_t slen)
+{
+    /* RFC 5988 <https://tools.ietf.org/html/rfc5988#section-6.2.1>
+      Link           = "Link" ":" #link-value
+      link-value     = "<" URI-Reference ">" *( ";" link-param )
+      link-param     = ( ( "rel" "=" relation-types )
+                     | ( "anchor" "=" <"> URI-Reference <"> )
+                     | ( "rev" "=" relation-types )
+                     | ( "hreflang" "=" Language-Tag )
+                     | ( "media" "=" ( MediaDesc | ( <"> MediaDesc <"> ) ) )
+                     | ( "title" "=" quoted-string )
+                     | ( "title*" "=" ext-value )
+                     | ( "type" "=" ( media-type | quoted-mt ) )
+                     | ( link-extension ) )
+      link-extension = ( parmname [ "=" ( ptoken | quoted-string ) ] )
+                     | ( ext-name-star "=" ext-value )
+      ext-name-star  = parmname "*" ; reserved for RFC2231-profiled
+                                    ; extensions.  Whitespace NOT
+                                    ; allowed in between.
+      ptoken         = 1*ptokenchar
+      ptokenchar     = "!" | "#" | "$" | "%" | "&" | "'" | "("
+                     | ")" | "*" | "+" | "-" | "." | "/" | DIGIT
+                     | ":" | "<" | "=" | ">" | "?" | "@" | ALPHA
+                     | "[" | "]" | "^" | "_" | "`" | "{" | "|"
+                     | "}" | "~"
+      media-type     = type-name "/" subtype-name
+      quoted-mt      = <"> media-type <">
+      relation-types = relation-type
+                     | <"> relation-type *( 1*SP relation-type ) <">
+      relation-type  = reg-rel-type | ext-rel-type
+      reg-rel-type   = LOALPHA *( LOALPHA | DIGIT | "." | "-" )
+      ext-rel-type   = URI
+      
+      and from <https://tools.ietf.org/html/rfc5987>
+      parmname      = 1*attr-char
+      attr-char     = ALPHA / DIGIT
+                       / "!" / "#" / "$" / "&" / "+" / "-" / "."
+                       / "^" / "_" / "`" / "|" / "~"
+     */
+
+     ctx->s = s;
+     ctx->slen = slen;
+     ctx->i = 0;
+     
+     while (read_link(ctx)) {
+        init_params(ctx);
+        while (read_param(ctx)) {
+            /* nop */
+        }
+        add_push(ctx);
+        if (!read_sep(ctx)) {
+            break;
+        }
+     }
+}
+
+static int head_iter(void *ctx, const char *key, const char *value) 
+{
+    if (!apr_strnatcasecmp("link", key)) {
+        inspect_link(ctx, value, strlen(value));
+    }
+    return 1;
+}
+
+apr_array_header_t *h2_push_collect(apr_pool_t *p, const h2_request *req,
+                                    int push_policy, const h2_headers *res)
+{
+    if (req && push_policy != H2_PUSH_NONE) {
+        /* Collect push candidates from the request/response pair.
+         * 
+         * One source for pushes are "rel=preload" link headers
+         * in the response.
+         * 
+         * TODO: This may be extended in the future by hooks or callbacks
+         * where other modules can provide push information directly.
+         */
+        if (res->headers) {
+            link_ctx ctx;
+            
+            memset(&ctx, 0, sizeof(ctx));
+            ctx.req = req;
+            ctx.push_policy = push_policy;
+            ctx.pool = p;
+            
+            apr_table_do(head_iter, &ctx, res->headers, NULL);
+            if (ctx.pushes) {
+                apr_table_setn(res->headers, "push-policy", 
+                               policy_str(push_policy));
+            }
+            return ctx.pushes;
+        }
+    }
+    return NULL;
+}
+
+/*******************************************************************************
+ * push diary 
+ *
+ * - The push diary keeps track of resources already PUSHed via HTTP/2 on this
+ *   connection. It records a hash value from the absolute URL of the resource
+ *   pushed.
+ * - Lacking openssl, it uses 'apr_hashfunc_default' for the value
+ * - with openssl, it uses SHA256 to calculate the hash value
+ * - whatever the method to generate the hash, the diary keeps a maximum of 64
+ *   bits per hash, limiting the memory consumption to about 
+ *      H2PushDiarySize * 8 
+ *   bytes. Entries are sorted by most recently used and oldest entries are
+ *   forgotten first.
+ * - Clients can initialize/replace the push diary by sending a 'Cache-Digest'
+ *   header. Currently, this is the base64url encoded value of the cache digest
+ *   as specified in https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
+ *   This draft can be expected to evolve and the definition of the header
+ *   will be added there and refined.
+ * - The cache digest header is a Golomb Coded Set of hash values, but it may
+ *   limit the amount of bits per hash value even further. For a good description
+ *   of GCS, read here:
+ *      http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters
+ * - The means that the push diary might be initialized with hash values of much
+ *   less than 64 bits, leading to more false positives, but smaller digest size.
+ ******************************************************************************/
+ 
+ 
+#define GCSLOG_LEVEL   APLOG_TRACE1
+
+typedef struct h2_push_diary_entry {
+    apr_uint64_t hash;
+} h2_push_diary_entry;
+
+
+#ifdef H2_OPENSSL
+static void sha256_update(SHA256_CTX *ctx, const char *s)
+{
+    SHA256_Update(ctx, s, strlen(s));
+}
+
+static void calc_sha256_hash(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push) 
+{
+    SHA256_CTX sha256;
+    apr_uint64_t val;
+    unsigned char hash[SHA256_DIGEST_LENGTH];
+    int i;
+    
+    SHA256_Init(&sha256);
+    sha256_update(&sha256, push->req->scheme);
+    sha256_update(&sha256, "://");
+    sha256_update(&sha256, push->req->authority);
+    sha256_update(&sha256, push->req->path);
+    SHA256_Final(hash, &sha256);
+
+    val = 0;
+    for (i = 0; i != sizeof(val); ++i)
+        val = val * 256 + hash[i];
+    *phash = val >> (64 - diary->mask_bits);
+}
+#endif
+
+
+static unsigned int val_apr_hash(const char *str) 
+{
+    apr_ssize_t len = strlen(str);
+    return apr_hashfunc_default(str, &len);
+}
+
+static void calc_apr_hash(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push) 
+{
+    apr_uint64_t val;
+#if APR_UINT64_MAX > UINT_MAX
+    val = ((apr_uint64_t)(val_apr_hash(push->req->scheme)) << 32);
+    val ^= ((apr_uint64_t)(val_apr_hash(push->req->authority)) << 16);
+    val ^= val_apr_hash(push->req->path);
+#else
+    val = val_apr_hash(push->req->scheme);
+    val ^= val_apr_hash(push->req->authority);
+    val ^= val_apr_hash(push->req->path);
+#endif
+    *phash = val;
+}
+
+static apr_int32_t ceil_power_of_2(apr_int32_t n)
+{
+    if (n <= 2) return 2;
+    --n;
+    n |= n >> 1;
+    n |= n >> 2;
+    n |= n >> 4;
+    n |= n >> 8;
+    n |= n >> 16;
+    return ++n;
+}
+
+static h2_push_diary *diary_create(apr_pool_t *p, h2_push_digest_type dtype, 
+                                   int N)
+{
+    h2_push_diary *diary = NULL;
+    
+    if (N > 0) {
+        diary = apr_pcalloc(p, sizeof(*diary));
+        
+        diary->NMax        = ceil_power_of_2(N);
+        diary->N           = diary->NMax;
+        /* the mask we use in value comparison depends on where we got
+         * the values from. If we calculate them ourselves, we can use
+         * the full 64 bits.
+         * If we set the diary via a compressed golomb set, we have less
+         * relevant bits and need to use a smaller mask. */
+        diary->mask_bits   = 64;
+        /* grows by doubling, start with a power of 2 */
+        diary->entries     = apr_array_make(p, 16, sizeof(h2_push_diary_entry));
+        
+        switch (dtype) {
+#ifdef H2_OPENSSL
+            case H2_PUSH_DIGEST_SHA256:
+                diary->dtype       = H2_PUSH_DIGEST_SHA256;
+                diary->dcalc       = calc_sha256_hash;
+                break;
+#endif /* ifdef H2_OPENSSL */
+            default:
+                diary->dtype       = H2_PUSH_DIGEST_APR_HASH;
+                diary->dcalc       = calc_apr_hash;
+                break;
+        }
+    }
+    
+    return diary;
+}
+
+h2_push_diary *h2_push_diary_create(apr_pool_t *p, int N)
+{
+    return diary_create(p, H2_PUSH_DIGEST_SHA256, N);
+}
+
+static int h2_push_diary_find(h2_push_diary *diary, apr_uint64_t hash)
+{
+    if (diary) {
+        h2_push_diary_entry *e;
+        int i;
+
+        /* search from the end, where the last accessed digests are */
+        for (i = diary->entries->nelts-1; i >= 0; --i) {
+            e = &APR_ARRAY_IDX(diary->entries, i, h2_push_diary_entry);
+            if (e->hash == hash) {
+                return i;
+            }
+        }
+    }
+    return -1;
+}
+
+static h2_push_diary_entry *move_to_last(h2_push_diary *diary, apr_size_t idx)
+{
+    h2_push_diary_entry *entries = (h2_push_diary_entry*)diary->entries->elts;
+    h2_push_diary_entry e;
+    apr_size_t lastidx = diary->entries->nelts-1;
+    
+    /* move entry[idx] to the end */
+    if (idx < lastidx) {
+        e =  entries[idx];
+        memmove(entries+idx, entries+idx+1, sizeof(e) * (lastidx - idx));
+        entries[lastidx] = e;
+    }
+    return &entries[lastidx];
+}
+
+static void h2_push_diary_append(h2_push_diary *diary, h2_push_diary_entry *e)
+{
+    h2_push_diary_entry *ne;
+    
+    if (diary->entries->nelts < diary->N) {
+        /* append a new diary entry at the end */
+        APR_ARRAY_PUSH(diary->entries, h2_push_diary_entry) = *e;
+        ne = &APR_ARRAY_IDX(diary->entries, diary->entries->nelts-1, h2_push_diary_entry);
+    }
+    else {
+        /* replace content with new digest. keeps memory usage constant once diary is full */
+        ne = move_to_last(diary, 0);
+        *ne = *e;
+    }
+    /* Intentional no APLOGNO */
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, diary->entries->pool,
+                  "push_diary_append: %"APR_UINT64_T_HEX_FMT, ne->hash);
+}
+
+apr_array_header_t *h2_push_diary_update(h2_session *session, apr_array_header_t *pushes)
+{
+    apr_array_header_t *npushes = pushes;
+    h2_push_diary_entry e;
+    int i, idx;
+    
+    if (session->push_diary && pushes) {
+        npushes = NULL;
+        
+        for (i = 0; i < pushes->nelts; ++i) {
+            h2_push *push;
+            
+            push = APR_ARRAY_IDX(pushes, i, h2_push*);
+            session->push_diary->dcalc(session->push_diary, &e.hash, push);
+            idx = h2_push_diary_find(session->push_diary, e.hash);
+            if (idx >= 0) {
+                /* Intentional no APLOGNO */
+                ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c,
+                              "push_diary_update: already there PUSH %s", push->req->path);
+                move_to_last(session->push_diary, idx);
+            }
+            else {
+                /* Intentional no APLOGNO */
+                ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c,
+                              "push_diary_update: adding PUSH %s", push->req->path);
+                if (!npushes) {
+                    npushes = apr_array_make(pushes->pool, 5, sizeof(h2_push_diary_entry*));
+                }
+                APR_ARRAY_PUSH(npushes, h2_push*) = push;
+                h2_push_diary_append(session->push_diary, &e);
+            }
+        }
+    }
+    return npushes;
+}
+    
+apr_array_header_t *h2_push_collect_update(h2_stream *stream, 
+                                           const struct h2_request *req, 
+                                           const struct h2_headers *res)
+{
+    h2_session *session = stream->session;
+    const char *cache_digest = apr_table_get(req->headers, "Cache-Digest");
+    apr_array_header_t *pushes;
+    apr_status_t status;
+    
+    if (cache_digest && session->push_diary) {
+        status = h2_push_diary_digest64_set(session->push_diary, req->authority, 
+                                            cache_digest, stream->pool);
+        if (status != APR_SUCCESS) {
+            ap_log_cerror(APLOG_MARK, APLOG_DEBUG, status, session->c,
+                          H2_SSSN_LOG(APLOGNO(03057), session,
+                          "push diary set from Cache-Digest: %s"), cache_digest);
+        }
+    }
+    pushes = h2_push_collect(stream->pool, req, stream->push_policy, res);
+    return h2_push_diary_update(stream->session, pushes);
+}
+
+static apr_int32_t h2_log2inv(unsigned char log2)
+{
+    return log2? (1 << log2) : 1;
+}
+
+
+typedef struct {
+    h2_push_diary *diary;
+    unsigned char log2p;
+    int mask_bits;
+    int delta_bits;
+    int fixed_bits;
+    apr_uint64_t fixed_mask;
+    apr_pool_t *pool;
+    unsigned char *data;
+    apr_size_t datalen;
+    apr_size_t offset;
+    unsigned int bit;
+    apr_uint64_t last;
+} gset_encoder;
+
+static int cmp_puint64(const void *p1, const void *p2)
+{
+    const apr_uint64_t *pu1 = p1, *pu2 = p2;
+    return (*pu1 > *pu2)? 1 : ((*pu1 == *pu2)? 0 : -1);
+}
+
+/* in golomb bit stream encoding, bit 0 is the 8th of the first char, or
+ * more generally: 
+ *      char(bit/8) & cbit_mask[(bit % 8)]
+ */
+static unsigned char cbit_mask[] = {
+    0x80u,
+    0x40u,
+    0x20u,
+    0x10u,
+    0x08u,
+    0x04u,
+    0x02u,
+    0x01u,
+};
+
+static apr_status_t gset_encode_bit(gset_encoder *encoder, int bit)
+{
+    if (++encoder->bit >= 8) {
+        if (++encoder->offset >= encoder->datalen) {
+            apr_size_t nlen = encoder->datalen*2;
+            unsigned char *ndata = apr_pcalloc(encoder->pool, nlen);
+            if (!ndata) {
+                return APR_ENOMEM;
+            }
+            memcpy(ndata, encoder->data, encoder->datalen);
+            encoder->data = ndata;
+            encoder->datalen = nlen;
+        }
+        encoder->bit = 0;
+        encoder->data[encoder->offset] = 0xffu;
+    }
+    if (!bit) {
+        encoder->data[encoder->offset] &= ~cbit_mask[encoder->bit];
+    }
+    return APR_SUCCESS;
+}
+
+static apr_status_t gset_encode_next(gset_encoder *encoder, apr_uint64_t pval)
+{
+    apr_uint64_t delta, flex_bits;
+    apr_status_t status = APR_SUCCESS;
+    int i;
+    
+    delta = pval - encoder->last;
+    encoder->last = pval;
+    flex_bits = (delta >> encoder->fixed_bits);
+    /* Intentional no APLOGNO */
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, encoder->pool,
+                  "h2_push_diary_enc: val=%"APR_UINT64_T_HEX_FMT", delta=%"
+                  APR_UINT64_T_HEX_FMT" flex_bits=%"APR_UINT64_T_FMT", "
+                  ", fixed_bits=%d, fixed_val=%"APR_UINT64_T_HEX_FMT, 
+                  pval, delta, flex_bits, encoder->fixed_bits, delta&encoder->fixed_mask);
+    for (; flex_bits != 0; --flex_bits) {
+        status = gset_encode_bit(encoder, 1);
+        if (status != APR_SUCCESS) {
+            return status;
+        }
+    }
+    status = gset_encode_bit(encoder, 0);
+    if (status != APR_SUCCESS) {
+        return status;
+    }
+
+    for (i = encoder->fixed_bits-1; i >= 0; --i) {
+        status = gset_encode_bit(encoder, (delta >> i) & 1);
+        if (status != APR_SUCCESS) {
+            return status;
+        }
+    }
+    return APR_SUCCESS;
+}
+
+/**
+ * Get a cache digest as described in 
+ * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
+ * from the contents of the push diary.
+ * 
+ * @param diary the diary to calculdate the digest from
+ * @param p the pool to use
+ * @param pdata on successful return, the binary cache digest
+ * @param plen on successful return, the length of the binary data
+ */
+apr_status_t h2_push_diary_digest_get(h2_push_diary *diary, apr_pool_t *pool, 
+                                      int maxP, const char *authority, 
+                                      const char **pdata, apr_size_t *plen)
+{
+    int nelts, N, i;
+    unsigned char log2n, log2pmax;
+    gset_encoder encoder;
+    apr_uint64_t *hashes;
+    apr_size_t hash_count;
+    
+    nelts = diary->entries->nelts;
+    
+    if (nelts > APR_UINT32_MAX) {
+        /* should not happen */
+        return APR_ENOTIMPL;
+    }
+    N = ceil_power_of_2(nelts);
+    log2n = h2_log2(N);
+    
+    /* Now log2p is the max number of relevant bits, so that
+     * log2p + log2n == mask_bits. We can uise a lower log2p
+     * and have a shorter set encoding...
+     */
+    log2pmax = h2_log2(ceil_power_of_2(maxP));
+    
+    memset(&encoder, 0, sizeof(encoder));
+    encoder.diary = diary;
+    encoder.log2p = H2MIN(diary->mask_bits - log2n, log2pmax);
+    encoder.mask_bits = log2n + encoder.log2p;
+    encoder.delta_bits = diary->mask_bits - encoder.mask_bits;
+    encoder.fixed_bits = encoder.log2p;
+    encoder.fixed_mask = 1;
+    encoder.fixed_mask = (encoder.fixed_mask << encoder.fixed_bits) - 1;
+    encoder.pool = pool;
+    encoder.datalen = 512;
+    encoder.data = apr_pcalloc(encoder.pool, encoder.datalen);
+    
+    encoder.data[0] = log2n;
+    encoder.data[1] = encoder.log2p;
+    encoder.offset = 1;
+    encoder.bit = 8;
+    encoder.last = 0;
+    
+    /* Intentional no APLOGNO */
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest_get: %d entries, N=%d, log2n=%d, "
+                  "mask_bits=%d, enc.mask_bits=%d, delta_bits=%d, enc.log2p=%d, authority=%s", 
+                  (int)nelts, (int)N, (int)log2n, diary->mask_bits, 
+                  (int)encoder.mask_bits, (int)encoder.delta_bits, 
+                  (int)encoder.log2p, authority);
+                  
+    if (!authority || !diary->authority 
+        || !strcmp("*", authority) || !strcmp(diary->authority, authority)) {
+        hash_count = diary->entries->nelts;
+        hashes = apr_pcalloc(encoder.pool, hash_count);
+        for (i = 0; i < hash_count; ++i) {
+            hashes[i] = ((&APR_ARRAY_IDX(diary->entries, i, h2_push_diary_entry))->hash 
+                         >> encoder.delta_bits);
+        }
+        
+        qsort(hashes, hash_count, sizeof(apr_uint64_t), cmp_puint64);
+        for (i = 0; i < hash_count; ++i) {
+            if (!i || (hashes[i] != hashes[i-1])) {
+                gset_encode_next(&encoder, hashes[i]);
+            }
+        }
+        /* Intentional no APLOGNO */
+        ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                      "h2_push_diary_digest_get: golomb compressed hashes, %d bytes",
+                      (int)encoder.offset + 1);
+    }
+    *pdata = (const char *)encoder.data;
+    *plen = encoder.offset + 1;
+    
+    return APR_SUCCESS;
+}
+
+typedef struct {
+    h2_push_diary *diary;
+    apr_pool_t *pool;
+    unsigned char log2p;
+    const unsigned char *data;
+    apr_size_t datalen;
+    apr_size_t offset;
+    unsigned int bit;
+    apr_uint64_t last_val;
+} gset_decoder;
+
+static int gset_decode_next_bit(gset_decoder *decoder)
+{
+    if (++decoder->bit >= 8) {
+        if (++decoder->offset >= decoder->datalen) {
+            return -1;
+        }
+        decoder->bit = 0;
+    }
+    return (decoder->data[decoder->offset] & cbit_mask[decoder->bit])? 1 : 0;
+}
+
+static apr_status_t gset_decode_next(gset_decoder *decoder, apr_uint64_t *phash)
+{
+    apr_uint64_t flex = 0, fixed = 0, delta;
+    int i;
+    
+    /* read 1 bits until we encounter 0, then read log2n(diary-P) bits.
+     * On a malformed bit-string, this will not fail, but produce results
+     * which are pbly too large. Luckily, the diary will modulo the hash.
+     */
+    while (1) {
+        int bit = gset_decode_next_bit(decoder);
+        if (bit == -1) {
+            return APR_EINVAL;
+        }
+        if (!bit) {
+            break;
+        }
+        ++flex;
+    }
+    
+    for (i = 0; i < decoder->log2p; ++i) {
+        int bit = gset_decode_next_bit(decoder);
+        if (bit == -1) {
+            return APR_EINVAL;
+        }
+        fixed = (fixed << 1) | bit;
+    }
+    
+    delta = (flex << decoder->log2p) | fixed;
+    *phash = delta + decoder->last_val;
+    decoder->last_val = *phash;
+    
+    /* Intentional no APLOGNO */
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, decoder->pool,
+                  "h2_push_diary_digest_dec: val=%"APR_UINT64_T_HEX_FMT", delta=%"
+                  APR_UINT64_T_HEX_FMT", flex=%d, fixed=%"APR_UINT64_T_HEX_FMT, 
+                  *phash, delta, (int)flex, fixed);
+                  
+    return APR_SUCCESS;
+}
+
+/**
+ * Initialize the push diary by a cache digest as described in 
+ * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
+ * .
+ * @param diary the diary to set the digest into
+ * @param data the binary cache digest
+ * @param len the length of the cache digest
+ * @return APR_EINVAL if digest was not successfully parsed
+ */
+apr_status_t h2_push_diary_digest_set(h2_push_diary *diary, const char *authority, 
+                                      const char *data, apr_size_t len)
+{
+    gset_decoder decoder;
+    unsigned char log2n, log2p;
+    int N, i;
+    apr_pool_t *pool = diary->entries->pool;
+    h2_push_diary_entry e;
+    apr_status_t status = APR_SUCCESS;
+    
+    if (len < 2) {
+        /* at least this should be there */
+        return APR_EINVAL;
+    }
+    log2n = data[0];
+    log2p = data[1];
+    diary->mask_bits = log2n + log2p;
+    if (diary->mask_bits > 64) {
+        /* cannot handle */
+        return APR_ENOTIMPL;
+    }
+    
+    /* whatever is in the digest, it replaces the diary entries */
+    apr_array_clear(diary->entries);
+    if (!authority || !strcmp("*", authority)) {
+        diary->authority = NULL;
+    }
+    else if (!diary->authority || strcmp(diary->authority, authority)) {
+        diary->authority = apr_pstrdup(diary->entries->pool, authority);
+    }
+
+    N = h2_log2inv(log2n + log2p);
+
+    decoder.diary    = diary;
+    decoder.pool     = pool;
+    decoder.log2p    = log2p;
+    decoder.data     = (const unsigned char*)data;
+    decoder.datalen  = len;
+    decoder.offset   = 1;
+    decoder.bit      = 8;
+    decoder.last_val = 0;
+    
+    diary->N = N;
+    /* Determine effective N we use for storage */
+    if (!N) {
+        /* a totally empty cache digest. someone tells us that she has no
+         * entries in the cache at all. Use our own preferences for N+mask 
+         */
+        diary->N = diary->NMax;
+        return APR_SUCCESS;
+    }
+    else if (N > diary->NMax) {
+        /* Store not more than diary is configured to hold. We open us up
+         * to DOS attacks otherwise. */
+        diary->N = diary->NMax;
+    }
+    
+    /* Intentional no APLOGNO */
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest_set: N=%d, log2n=%d, "
+                  "diary->mask_bits=%d, dec.log2p=%d", 
+                  (int)diary->N, (int)log2n, diary->mask_bits, 
+                  (int)decoder.log2p);
+                  
+    for (i = 0; i < diary->N; ++i) {
+        if (gset_decode_next(&decoder, &e.hash) != APR_SUCCESS) {
+            /* the data may have less than N values */
+            break;
+        }
+        h2_push_diary_append(diary, &e);
+    }
+    
+    /* Intentional no APLOGNO */
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest_set: diary now with %d entries, mask_bits=%d", 
+                  (int)diary->entries->nelts, diary->mask_bits);
+    return status;
+}
+
+apr_status_t h2_push_diary_digest64_set(h2_push_diary *diary, const char *authority, 
+                                        const char *data64url, apr_pool_t *pool)
+{
+    const char *data;
+    apr_size_t len = h2_util_base64url_decode(&data, data64url, pool);
+    /* Intentional no APLOGNO */
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest64_set: digest=%s, dlen=%d", 
+                  data64url, (int)len);
+    return h2_push_diary_digest_set(diary, authority, data, len);
+}
+