lsquic_parse_gquic_be.c revision c51ce338 
1/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_parse_gquic_be.c -- Parsing functions specific to big-endian
4 *                              (Q039 and higher) GQUIC.
5 */
6
7#include <assert.h>
8#include <inttypes.h>
9#include <errno.h>
10#include <stdlib.h>
11#include <string.h>
12#include <sys/queue.h>
13#include <sys/types.h>
14
15#include "lsquic_types.h"
16#include "lsquic_alarmset.h"
17#include "lsquic_packet_common.h"
18#include "lsquic_packet_in.h"
19#include "lsquic_parse.h"
20#include "lsquic_rechist.h"
21#include "lsquic_sfcw.h"
22#include "lsquic_stream.h"
23#include "lsquic_mm.h"
24#include "lsquic_malo.h"
25#include "lsquic_version.h"
26#include "lsquic.h"
27#include "lsquic_parse_gquic_be.h"  /* Include to catch mismatches */
28
29#define LSQUIC_LOGGER_MODULE LSQLM_PARSE
30#include "lsquic_logger.h"
31
32
33/* read 16 bits(2 bytes) time, unit: us */
34uint64_t
35gquic_be_read_float_time16 (const void *mem)
36{
37    uint16_t val;
38    READ_UINT(val, 16, mem, 2);
39    uint64_t temp = val;
40    uint16_t exp = (temp >> 11) & 0x1F;
41    if (0 == exp)
42        return temp;
43    else
44    {
45        --exp;
46        temp &= 0x7FF;
47        temp |= 0x800;
48        return temp << exp;
49    }
50}
51
52
53void
54gquic_be_write_float_time16 (lsquic_time_t time_us, void *mem)
55{
56    uint16_t ret = 0;
57    uint16_t high, i;
58
59    if (time_us < ((uint64_t)1 << 11))
60        ret = time_us;
61    else if(time_us > 0x3FFC0000000)
62        ret = 0xFFFF;
63    else
64    {
65        high = 0;
66        for (i = 16; i > 0; i /= 2)
67        {
68            if (time_us >= (uint64_t)1 << (11 + i))
69            {
70                high |= i;
71                time_us >>= i;
72            }
73        }
74        ret = time_us + (high << 11);
75    }
76#if __BYTE_ORDER == __LITTLE_ENDIAN
77    ret = bswap_16(ret);
78#endif
79    memcpy(mem, (void *)&ret, 2);
80}
81
82
83/* Parse out packet number */
84void
85gquic_be_parse_packet_in_finish (lsquic_packet_in_t *packet_in,
86                                            struct packin_parse_state *state)
87{
88    lsquic_packno_t packno;
89    if (state->pps_nbytes)
90    {
91        READ_UINT(packno, 64, state->pps_p, state->pps_nbytes);
92        packet_in->pi_packno = packno;
93    }
94}
95
96
97int
98gquic_be_gen_ver_nego_pkt (unsigned char *buf, size_t bufsz, uint64_t conn_id,
99                  unsigned version_bitmask)
100{
101    int sz;
102    unsigned char *p = buf;
103    unsigned char *const pend = p + bufsz;
104
105    CHECK_SPACE(1, p, pend);
106    *p = PACKET_PUBLIC_FLAGS_VERSION | PACKET_PUBLIC_FLAGS_8BYTE_CONNECTION_ID;
107    ++p;
108
109    CHECK_SPACE(8, p, pend);
110    memcpy(p, &conn_id, 8);
111    p += 8;
112
113    sz = gen_ver_tags(p, pend - p, version_bitmask);
114    if (sz < 0)
115        return -1;
116
117    return p + sz - buf;
118}
119
120
121int
122gquic_be_gen_reg_pkt_header (unsigned char *buf, size_t bufsz, const lsquic_cid_t *conn_id,
123                    const lsquic_ver_tag_t *ver, const unsigned char *nonce,
124                    lsquic_packno_t packno, enum lsquic_packno_bits bits)
125{
126    unsigned packnum_len, header_len;
127    unsigned char *p;
128
129    packnum_len = packno_bits2len(bits);
130
131    header_len = 1 + (!!conn_id << 3) + (!!ver << 2) + ((!!nonce) << 5)
132               + packnum_len;
133    if (header_len > bufsz)
134    {
135        errno = ENOBUFS;
136        return -1;
137    }
138
139    p =  buf;
140
141    *p = (!!conn_id << 3)
142       | (bits << 4)
143       | ((!!nonce) << 2)
144       | !!ver;
145    ++p;
146
147    if (conn_id)
148    {
149        memcpy(p, conn_id , sizeof(*conn_id));
150        p += sizeof(*conn_id);
151    }
152
153    if (ver)
154    {
155        memcpy(p, ver, 4);
156        p += 4;
157    }
158
159    if (nonce)
160    {
161        memcpy(p, nonce , 32);
162        p += 32;
163    }
164
165#if __BYTE_ORDER == __LITTLE_ENDIAN
166    packno = bswap_64(packno);
167#endif
168    memcpy(p, (unsigned char *) &packno + 8 - packnum_len, packnum_len);
169    p += packnum_len;
170
171    assert(p - buf == (intptr_t) header_len);
172
173    return header_len;
174}
175
176
177int
178gquic_be_gen_stream_frame (unsigned char *buf, size_t buf_len, uint32_t stream_id,
179                  uint64_t offset, gsf_fin_f gsf_fin, gsf_size_f gsf_size,
180                  gsf_read_f gsf_read, void *stream)
181{
182    /* 1fdoooss */
183    unsigned slen, olen, dlen;
184    unsigned char *p = buf + 1;
185    int fin;
186
187    /* ss: Stream ID length: 1, 2, 3, or 4 bytes */
188    slen = (stream_id > 0x0000FF)
189         + (stream_id > 0x00FFFF)
190         + (stream_id > 0xFFFFFF)
191         + 1;
192
193    /* ooo: Offset length: 0, 2, 3, 4, 5, 6, 7, or 8 bytes */
194    olen = (offset >= (1ULL << 56))
195         + (offset >= (1ULL << 48))
196         + (offset >= (1ULL << 40))
197         + (offset >= (1ULL << 32))
198         + (offset >= (1ULL << 24))
199         + (offset >= (1ULL << 16))
200         + ((offset > 0) << 1);
201
202    fin = gsf_fin(stream);
203    if (!fin)
204    {
205        unsigned size, n_avail;
206        uint16_t nr;
207
208        size = gsf_size(stream);
209        n_avail = buf_len - (p + slen + olen - buf);
210
211        /* If we cannot fill remaining buffer, we need to include data
212         * length.
213         */
214        dlen = (size < n_avail) << 1;
215        n_avail -= dlen;
216
217        CHECK_SPACE(1 + olen + slen + dlen +
218            + 1 /* We need to write at least 1 byte */, buf, buf + buf_len);
219
220#if __BYTE_ORDER == __LITTLE_ENDIAN
221        stream_id = bswap_32(stream_id);
222#endif
223        memcpy(p, (unsigned char *) &stream_id + 4 - slen, slen);
224        p += slen;
225
226#if __BYTE_ORDER == __LITTLE_ENDIAN
227        offset = bswap_64(offset);
228#endif
229        memcpy(p, (unsigned char *) &offset + 8 - olen, olen);
230        p += olen;
231
232        /* Read as much as we can */
233        nr = gsf_read(stream, p + dlen, n_avail, &fin);
234        assert(nr != 0);
235
236        if (dlen)
237        {
238            uint16_t nr_copy = nr;
239#if __BYTE_ORDER == __LITTLE_ENDIAN
240            nr_copy = bswap_16(nr_copy);
241#endif
242            memcpy(p, &nr_copy, 2);
243        }
244
245        p += dlen + nr;
246    }
247    else
248    {
249        dlen = 2;
250        CHECK_SPACE(1 + slen + olen + 2, buf, buf + buf_len);
251#if __BYTE_ORDER == __LITTLE_ENDIAN
252        stream_id = bswap_32(stream_id);
253#endif
254        memcpy(p, (unsigned char *) &stream_id + 4 - slen, slen);
255        p += slen;
256#if __BYTE_ORDER == __LITTLE_ENDIAN
257        offset = bswap_64(offset);
258#endif
259        memcpy(p, (unsigned char *) &offset + 8 - olen, olen);
260        p += olen;
261        memset(p, 0, 2);
262        p += 2;
263    }
264
265    /* Convert slen to bit representation: 0 - 3: */
266    slen -= 1;
267    assert(slen <= 3);
268
269    /* Convert olen to bit representation: 0 - 7: */
270    olen += !olen;
271    olen -= 1;
272    assert(olen <= 7);
273
274    buf[0] = 0x80
275           | (fin << 6)
276           | (dlen << 4)
277           | (olen << 2)
278           | slen
279           ;
280    return p - buf;
281}
282
283
284/* return parsed (used) buffer length */
285int
286gquic_be_parse_stream_frame (const unsigned char *buf, size_t rem_packet_sz,
287                       stream_frame_t *stream_frame)
288{
289    /* 1fdoooss */
290    const unsigned char *p = buf;
291    const unsigned char *const pend = p + rem_packet_sz;
292
293    CHECK_SPACE(1, p, pend);
294    const char type = *p++;
295
296    const unsigned data_len   = (type >> 4) & 2;
297    const unsigned offset_len = ((type >> 2) & 7) + 1 - !((type >> 2) & 7);
298    const unsigned stream_id_len = 1 + (type & 3);
299    const unsigned need = data_len + offset_len + stream_id_len;
300    CHECK_SPACE(need, p, pend);
301
302    memset(stream_frame, 0, sizeof(*stream_frame));
303
304    stream_frame->data_frame.df_fin = (type >> 6) & 1;
305
306    memcpy((unsigned char *) &stream_frame->stream_id + 4 - stream_id_len, p,
307                                                                stream_id_len);
308
309#if __BYTE_ORDER == __LITTLE_ENDIAN
310    stream_frame->stream_id = bswap_32(stream_frame->stream_id);
311#endif
312    p += stream_id_len;
313
314    memcpy((unsigned char *) &stream_frame->data_frame.df_offset
315                                            + 8 - offset_len, p, offset_len);
316#if __BYTE_ORDER == __LITTLE_ENDIAN
317    stream_frame->data_frame.df_offset =
318                                bswap_64(stream_frame->data_frame.df_offset);
319#endif
320    p += offset_len;
321
322    if (data_len)
323    {
324        memcpy(&stream_frame->data_frame.df_size, p, data_len);
325#if __BYTE_ORDER == __LITTLE_ENDIAN
326        stream_frame->data_frame.df_size =
327                                bswap_16(stream_frame->data_frame.df_size);
328#endif
329        p += data_len;
330        CHECK_SPACE(stream_frame->data_frame.df_size, p, pend);
331        stream_frame->data_frame.df_data = p;
332        p += stream_frame->data_frame.df_size;
333    }
334    else
335    {
336        stream_frame->data_frame.df_size = pend - p;
337        stream_frame->data_frame.df_data = p;
338        p = pend;
339    }
340
341    /* From the spec: "A stream frame must always have either non-zero
342     * data length or the FIN bit set.'
343     */
344    if (!(stream_frame->data_frame.df_size ||
345                                        stream_frame->data_frame.df_fin))
346        return -1;
347
348    assert(p <= pend);
349
350    return p - (unsigned char *) buf;
351}
352
353
354/* This is a special function: it is used to extract the largest observed
355 * packet number from ACK frame that we ourselves generated.  This allows
356 * us to skip some checks.
357 */
358lsquic_packno_t
359gquic_be_parse_ack_high (const unsigned char *buf, size_t buf_len)
360{
361    unsigned char type;
362    unsigned largest_obs_len;
363    lsquic_packno_t packno;
364
365    type = buf[0];
366    largest_obs_len = twobit_to_1246((type >> 2) & 3);
367    assert(parse_frame_type_gquic_Q035_thru_Q039(type) == QUIC_FRAME_ACK);
368    assert(buf_len >= 1 + largest_obs_len);
369    READ_UINT(packno, 64, buf + 1, largest_obs_len);
370    return packno;
371}
372
373
374/* Return parsed (used) buffer length.
375 * If parsing failed, negative value is returned.
376 */
377int
378gquic_be_parse_ack_frame (const unsigned char *buf, size_t buf_len, ack_info_t *ack)
379{
380    /* 01nullmm */
381    lsquic_packno_t tmp_packno;
382    const unsigned char type = buf[0];
383    const unsigned char *p = buf + 1;
384    const unsigned char *const pend = buf + buf_len;
385
386    assert((type & 0xC0) == 0x40);      /* We're passed correct frame type */
387
388    const int ack_block_len   = twobit_to_1246(type & 3);        /* mm */
389    const int largest_obs_len = twobit_to_1246((type >> 2) & 3); /* ll */
390
391    CHECK_SPACE(largest_obs_len, p , pend);
392
393    READ_UINT(ack->ranges[0].high, 64, p, largest_obs_len);
394    p += largest_obs_len;
395
396    CHECK_SPACE(2, p , pend);
397    ack->lack_delta = gquic_be_read_float_time16(p);
398    p += 2;
399
400    unsigned n_blocks;
401    if (type & 0x20)
402    {
403        CHECK_SPACE(1, p , pend);
404        n_blocks = *p;
405        ++p;
406    }
407    else
408        n_blocks = 0;
409
410    CHECK_SPACE(ack_block_len, p , pend);
411    READ_UINT(tmp_packno, 64, p, ack_block_len);
412    ack->ranges[0].low = ack->ranges[0].high - tmp_packno + 1;
413    p += ack_block_len;
414
415    if (n_blocks)
416    {
417        CHECK_SPACE((ack_block_len + 1) * n_blocks, p , pend);
418        unsigned i, n, gap;
419        for (i = 0, n = 1, gap = 0; i < n_blocks; ++i)
420        {
421            uint64_t length;
422            gap += *p;
423            READ_UINT(length, 64, p + 1, ack_block_len);
424            p += 1 + ack_block_len;
425            if (length)
426            {
427                ack->ranges[n].high = ack->ranges[n - 1].low - gap - 1;
428                ack->ranges[n].low  = ack->ranges[n].high - length + 1;
429                ++n;
430                gap = 0;
431            }
432        }
433        ack->n_ranges = n;
434    }
435    else
436        ack->n_ranges = 1;
437
438    CHECK_SPACE(1, p , pend);
439    ack->n_timestamps = *p;
440    ++p;
441
442    if (ack->n_timestamps)
443    {
444#if LSQUIC_PARSE_ACK_TIMESTAMPS
445        CHECK_SPACE(5, p , pend);
446        ack->timestamps[0].packet_delta = *p++;
447        memcpy(&ack->timestamps[0].delta_usec, p, 4);
448        p += 4;
449        unsigned i;
450        for (i = 1; i < ack->n_timestamps; ++i)
451        {
452            CHECK_SPACE(3, p , pend);
453            ack->timestamps[i].packet_delta = *p++;
454            uint64_t delta_time = read_float_time16(p);
455            p += 2;
456            ack->timestamps[i].delta_usec =
457                ack->timestamps[i - 1].delta_usec + delta_time;
458        }
459#else
460        unsigned timestamps_size = 5 + 3 * (ack->n_timestamps - 1);
461        CHECK_SPACE(timestamps_size, p, pend);
462        p += timestamps_size;
463#endif
464    }
465
466    assert(p <= pend);
467
468    return p - (unsigned char *) buf;
469}
470
471
472int
473gquic_be_gen_stop_waiting_frame(unsigned char *buf, size_t buf_len,
474                lsquic_packno_t cur_packno, enum lsquic_packno_bits bits,
475                lsquic_packno_t least_unacked_packno)
476{
477    lsquic_packno_t delta;
478    unsigned packnum_len = packno_bits2len(bits);
479
480    if (buf_len >= 1 + packnum_len)
481    {
482        *buf = 0x06;
483        delta = cur_packno - least_unacked_packno;
484#if __BYTE_ORDER == __LITTLE_ENDIAN
485        delta = bswap_64(delta);
486#endif
487        memcpy(buf + 1, (unsigned char *) &delta + 8 - packnum_len,
488                                                            packnum_len);
489        return 1 + packnum_len;
490    }
491    else
492        return -1;
493}
494
495
496int
497gquic_be_parse_stop_waiting_frame (const unsigned char *buf, size_t buf_len,
498                 lsquic_packno_t cur_packno, enum lsquic_packno_bits bits,
499                 lsquic_packno_t *least_unacked)
500{
501    lsquic_packno_t delta;
502    unsigned packnum_len = packno_bits2len(bits);
503
504    if (buf_len >= 1 + packnum_len)
505    {
506        READ_UINT(delta, 64, buf + 1, packnum_len);
507        *least_unacked = cur_packno - delta;
508        return 1 + packnum_len;
509    }
510    else
511        return -1;
512}
513
514
515int
516gquic_be_skip_stop_waiting_frame (size_t buf_len, enum lsquic_packno_bits bits)
517{
518    unsigned packnum_len = packno_bits2len(bits);
519    if (buf_len >= 1 + packnum_len)
520        return 1 + packnum_len;
521    else
522        return -1;
523}
524
525
526int
527gquic_be_gen_window_update_frame (unsigned char *buf, int buf_len, uint32_t stream_id,
528                         uint64_t offset)
529{
530    if (buf_len < QUIC_WUF_SZ)
531        return -1;
532
533    *buf = 0x04;
534#if __BYTE_ORDER == __LITTLE_ENDIAN
535    stream_id = bswap_32(stream_id);
536#endif
537    memcpy(buf + 1, (unsigned char *) &stream_id, 4);
538#if __BYTE_ORDER == __LITTLE_ENDIAN
539    offset = bswap_64(offset);
540#endif
541    memcpy(buf + 1 + 4, (unsigned char *) &offset, 8);
542    return QUIC_WUF_SZ;
543}
544
545
546int
547gquic_be_parse_window_update_frame (const unsigned char *buf, size_t buf_len,
548                              uint32_t *stream_id, uint64_t *offset)
549{
550    if (buf_len < QUIC_WUF_SZ)
551        return -1;
552
553    READ_UINT(*stream_id, 32, buf + 1, 4);
554    READ_UINT(*offset, 64, buf + 1 + 4, 8);
555    return QUIC_WUF_SZ;
556}
557
558
559int
560gquic_be_gen_blocked_frame (unsigned char *buf, size_t buf_len, uint32_t stream_id)
561{
562    if (buf_len < QUIC_BLOCKED_FRAME_SZ)
563        return -1;
564
565    *buf = 0x05;
566#if __BYTE_ORDER == __LITTLE_ENDIAN
567    stream_id = bswap_32(stream_id);
568#endif
569    memcpy(buf + 1, &stream_id, 4);
570    return QUIC_BLOCKED_FRAME_SZ;
571}
572
573
574int
575gquic_be_parse_blocked_frame (const unsigned char *buf, size_t buf_len,
576                                                    uint32_t *stream_id)
577{
578    if (buf_len < QUIC_BLOCKED_FRAME_SZ)
579        return -1;
580
581    READ_UINT(*stream_id, 32, buf + 1, 4);
582    return QUIC_BLOCKED_FRAME_SZ;
583}
584
585
586int
587gquic_be_gen_rst_frame (unsigned char *buf, size_t buf_len, uint32_t stream_id,
588                    uint64_t offset, uint32_t error_code)
589{
590    unsigned char *p = buf;
591    if (buf_len < QUIC_RST_STREAM_SZ)
592        return -1;
593
594    *p = 0x01;
595    ++p;
596#if __BYTE_ORDER == __LITTLE_ENDIAN
597    stream_id = bswap_32(stream_id);
598#endif
599    memcpy(p, &stream_id, 4);
600    p += 4;
601#if __BYTE_ORDER == __LITTLE_ENDIAN
602    offset = bswap_64(offset);
603#endif
604    memcpy(p, &offset, 8);
605    p += 8;
606#if __BYTE_ORDER == __LITTLE_ENDIAN
607    error_code = bswap_32(error_code);
608#endif
609    memcpy(p, &error_code, 4);
610    p += 4;
611    return p - buf;
612}
613
614
615int
616gquic_be_parse_rst_frame (const unsigned char *buf, size_t buf_len, uint32_t *stream_id,
617                    uint64_t *offset, uint32_t *error_code)
618{
619    if (buf_len < QUIC_RST_STREAM_SZ)
620        return -1;
621
622    READ_UINT(*stream_id, 32, buf + 1, 4);
623    READ_UINT(*offset, 64, buf + 1 + 4, 8);
624    READ_UINT(*error_code, 32, buf + 1 + 4 + 8, 4);
625    return QUIC_RST_STREAM_SZ;
626}
627
628
629int
630gquic_be_gen_ping_frame (unsigned char *buf, int buf_len)
631{
632    if (buf_len > 0)
633    {
634        buf[0] = 0x07;
635        return 1;
636    }
637    else
638        return -1;
639}
640
641
642int
643gquic_be_gen_connect_close_frame (unsigned char *buf, int buf_len, uint32_t error_code,
644                            const char *reason, int reason_len)
645{
646    unsigned char *p = buf;
647    if (buf_len < 7)
648        return -1;
649
650    *p = 0x02;
651    ++p;
652#if __BYTE_ORDER == __LITTLE_ENDIAN
653    error_code = bswap_32(error_code);
654#endif
655    memcpy(p, &error_code, 4);
656    p += 4;
657#if __BYTE_ORDER == __LITTLE_ENDIAN
658    const uint16_t copy = bswap_16(reason_len);
659    memcpy(p, &copy, 2);
660#else
661    memcpy(p, &reason_len, 2);
662#endif
663    p += 2;
664    memcpy(p, reason, reason_len);
665    p += reason_len;
666    if (buf_len < p - buf)
667        return -2;
668
669    return p - buf;
670}
671
672
673int
674gquic_be_parse_connect_close_frame (const unsigned char *buf, size_t buf_len,
675        uint32_t *error_code, uint16_t *reason_len, uint8_t *reason_offset)
676{
677    if (buf_len < 7)
678        return -1;
679
680    READ_UINT(*error_code, 32, buf + 1, 4);
681    READ_UINT(*reason_len, 16, buf + 1 + 4, 2);
682    *reason_offset = 7;
683    if (buf_len < 7u + *reason_len)
684        return -2;
685
686    return 7 + *reason_len;
687}
688
689
690int
691gquic_be_gen_goaway_frame(unsigned char *buf, size_t buf_len, uint32_t error_code,
692                     uint32_t last_good_stream_id, const char *reason,
693                     size_t reason_len)
694{
695    unsigned char *p = buf;
696    if (buf_len < QUIC_GOAWAY_FRAME_SZ + reason_len)
697        return -1;
698
699    *p = 0x03;
700    ++p;
701#if __BYTE_ORDER == __LITTLE_ENDIAN
702    error_code = bswap_32(error_code);
703#endif
704    memcpy(p, &error_code, 4);
705    p += 4;
706#if __BYTE_ORDER == __LITTLE_ENDIAN
707    last_good_stream_id = bswap_32(last_good_stream_id);
708#endif
709    memcpy(p, &last_good_stream_id, 4);
710    p += 4;
711#if __BYTE_ORDER == __LITTLE_ENDIAN
712    uint16_t copy = bswap_16(reason_len);
713    memcpy(p, &copy, 2);
714#else
715    memcpy(p, &reason_len, 2);
716#endif
717    p += 2;
718    if (reason_len)
719    {
720        memcpy(p, reason, reason_len);
721        p += reason_len;
722    }
723
724    return p - buf;
725}
726
727
728/* the reason is buf + *reason_offset, length is *reason_length */
729int
730gquic_be_parse_goaway_frame (const unsigned char *buf, size_t buf_len,
731                       uint32_t *error_code, uint32_t *last_good_stream_id,
732                       uint16_t *reason_length, const char **reason)
733{
734    if (buf_len < QUIC_GOAWAY_FRAME_SZ)
735        return -1;
736
737    READ_UINT(*error_code,          32, buf + 1,         4);
738    READ_UINT(*last_good_stream_id, 32, buf + 1 + 4,     4);
739    READ_UINT(*reason_length,       16, buf + 1 + 4 + 4, 2);
740    if (*reason_length)
741    {
742        if ((int)buf_len < QUIC_GOAWAY_FRAME_SZ + *reason_length)
743            return -2;
744        *reason = (const char *) buf + QUIC_GOAWAY_FRAME_SZ;
745    }
746    else
747        *reason = NULL;
748
749    return QUIC_GOAWAY_FRAME_SZ + *reason_length;
750}
751
752
753/* Returns number of bytes written or -1 on failure */
754/* This function makes an assumption that there is at least one range */
755int
756gquic_be_gen_ack_frame (unsigned char *outbuf, size_t outbuf_sz,
757        gaf_rechist_first_f rechist_first, gaf_rechist_next_f rechist_next,
758        gaf_rechist_largest_recv_f rechist_largest_recv,
759        void *rechist, lsquic_time_t now, int *has_missing)
760{
761    lsquic_packno_t tmp_packno;
762    const struct lsquic_packno_range *const first = rechist_first(rechist);
763    if (!first)
764    {
765        errno = EINVAL;
766        return -1;
767    }
768
769    /* Copy values from the first range, because the memory the pointer
770     * points to may change:
771     */
772    const lsquic_packno_t first_low = first->low, first_high = first->high;
773
774    unsigned char *p = outbuf;
775    unsigned char *const type = p;
776    unsigned char *const end = p + outbuf_sz;
777
778#define AVAIL() (end - p)
779
780#define CHECKOUT(sz) do {                                               \
781    if ((intptr_t) (sz) > AVAIL()) {                                    \
782        errno = ENOBUFS;                                                \
783        return -1;                                                      \
784    }                                                                   \
785} while (0)
786
787    CHECKOUT(1);
788    ++p;
789
790    /* 01nullmm */
791    *type = 0x40;
792
793    unsigned largest_acked_len, ack_block_len, bits;
794
795    /* Calculate largest ACKed len and set `ll' bits: */
796    const lsquic_packno_t maxno = first_high;
797    bits = (maxno >= (1ULL <<  8))
798         + (maxno >= (1ULL << 16))
799         + (maxno >= (1ULL << 32));
800    largest_acked_len = (1 << bits) - ((maxno >= (1ULL << 32)) << 1);
801    *type |= bits << 2;
802
803    /* Calculate largest ACK block length and set `mm' bits: */
804    unsigned n_ranges = 0;
805    lsquic_packno_t maxdiff = 0;
806    const struct lsquic_packno_range *range;
807    for (range = rechist_first(rechist); range; range = rechist_next(rechist))
808    {
809        ++n_ranges;
810        const lsquic_packno_t diff = range->high - range->low + 1;
811        if (diff > maxdiff)
812            maxdiff = diff;
813    }
814    bits = (maxdiff >= (1ULL <<  8))
815         + (maxdiff >= (1ULL << 16))
816         + (maxdiff >= (1ULL << 32));
817    ack_block_len = (1 << bits) - ((maxdiff >= (1ULL << 32)) << 1);
818    *type |= bits;
819
820    CHECKOUT(largest_acked_len);
821    tmp_packno = maxno;
822#if __BYTE_ORDER == __LITTLE_ENDIAN
823    tmp_packno = bswap_64(maxno);
824#endif
825    memcpy(p, (unsigned char *) &tmp_packno + 8 - largest_acked_len,
826                                                            largest_acked_len);
827    p += largest_acked_len;
828
829    CHECKOUT(2);
830    lsquic_time_t diff = now - rechist_largest_recv(rechist);
831    gquic_be_write_float_time16(diff, p);
832    LSQ_DEBUG("%s: diff: %"PRIu64"; encoded: 0x%04X", __func__, diff,
833                                                            *(uint16_t*)p);
834    p += 2;
835
836    if (n_ranges > 1)
837    {
838        *has_missing = 1;
839        *type |= 0x20;
840        /* We need to write out at least one range */
841        CHECKOUT(2 * (1 + ack_block_len));
842        unsigned char *const n_ranges_p = p;             /* Set this later */
843        lsquic_packno_t diff = maxno - first_low + 1;
844#if __BYTE_ORDER == __LITTLE_ENDIAN
845        diff = bswap_64(diff);
846#endif
847        memcpy(p + 1, (unsigned char *) &diff + 8 - ack_block_len,
848                                                            ack_block_len);
849        p += ack_block_len + 1;
850        /* Write out ack blocks until one of the following occurs:
851         *  1. We run out of intervals.
852         *  2. We run out of room.
853         *  3. We run out of highest possible number of ACK blocks (0xFF).
854         */
855        range = rechist_first(rechist);
856        lsquic_packno_t gap = 0;
857        n_ranges = 0;
858        do {
859            if (0 == gap)
860            {
861                const lsquic_packno_t prev_low = range->low;
862                range = rechist_next(rechist);
863                if (!range)
864                    break;
865                gap = prev_low - range->high - 1;
866            }
867            if (gap >= 0x100)
868            {
869                *p = 0xFF;
870                gap -= 0xFF;
871                memset(p + 1, 0, ack_block_len);
872            }
873            else
874            {
875                *p = gap;
876                gap = 0;
877                diff = range->high - range->low + 1;
878#if __BYTE_ORDER == __LITTLE_ENDIAN
879                diff = bswap_64(diff);
880#endif
881                memcpy(p + 1, (unsigned char *) &diff + 8 - ack_block_len,
882                                                                ack_block_len);
883            }
884            p += ack_block_len + 1;
885            ++n_ranges;
886        } while (n_ranges < 0xFF &&
887                 AVAIL() >= (intptr_t) ack_block_len + 1 + 1 /* timestamp byte */);
888        *n_ranges_p = n_ranges;
889    }
890    else
891    {
892        *has_missing = 0;
893        CHECKOUT(ack_block_len);
894        lsquic_packno_t diff = maxno - first_low + 1;
895#if __BYTE_ORDER == __LITTLE_ENDIAN
896        diff = bswap_64(diff);
897#endif
898        memcpy(p, (unsigned char *) &diff + 8 - ack_block_len, ack_block_len);
899        p += ack_block_len;
900    }
901
902    /* We do not generate timestamp list because the reference implementation
903     * does not use them.  When that changes, we will start sending timestamps
904     * over.
905     */
906    CHECKOUT(1);
907    *p = 0;
908    ++p;
909
910    return p - (unsigned char *) outbuf;
911
912#undef CHECKOUT
913}
914
915
916const struct parse_funcs lsquic_parse_funcs_gquic_Q039 =
917{
918    .pf_gen_ver_nego_pkt              =  gquic_be_gen_ver_nego_pkt,
919    .pf_gen_reg_pkt_header            =  gquic_be_gen_reg_pkt_header,
920    .pf_parse_packet_in_finish        =  gquic_be_parse_packet_in_finish,
921    .pf_gen_stream_frame              =  gquic_be_gen_stream_frame,
922    .pf_calc_stream_frame_header_sz   =  calc_stream_frame_header_sz_gquic,
923    .pf_parse_stream_frame_header_sz  =  parse_stream_frame_header_sz_gquic,
924    .pf_parse_stream_frame            =  gquic_be_parse_stream_frame,
925    .pf_parse_ack_frame               =  gquic_be_parse_ack_frame,
926    .pf_parse_ack_high                =  gquic_be_parse_ack_high,
927    .pf_gen_ack_frame                 =  gquic_be_gen_ack_frame,
928    .pf_gen_stop_waiting_frame        =  gquic_be_gen_stop_waiting_frame,
929    .pf_parse_stop_waiting_frame      =  gquic_be_parse_stop_waiting_frame,
930    .pf_skip_stop_waiting_frame       =  gquic_be_skip_stop_waiting_frame,
931    .pf_gen_window_update_frame       =  gquic_be_gen_window_update_frame,
932    .pf_parse_window_update_frame     =  gquic_be_parse_window_update_frame,
933    .pf_gen_blocked_frame             =  gquic_be_gen_blocked_frame,
934    .pf_parse_blocked_frame           =  gquic_be_parse_blocked_frame,
935    .pf_gen_rst_frame                 =  gquic_be_gen_rst_frame,
936    .pf_parse_rst_frame               =  gquic_be_parse_rst_frame,
937    .pf_gen_connect_close_frame       =  gquic_be_gen_connect_close_frame,
938    .pf_parse_connect_close_frame     =  gquic_be_parse_connect_close_frame,
939    .pf_gen_goaway_frame              =  gquic_be_gen_goaway_frame,
940    .pf_parse_goaway_frame            =  gquic_be_parse_goaway_frame,
941    .pf_gen_ping_frame                =  gquic_be_gen_ping_frame,
942#ifndef NDEBUG
943    .pf_write_float_time16            =  gquic_be_write_float_time16,
944    .pf_read_float_time16             =  gquic_be_read_float_time16,
945#endif
946    .pf_parse_frame_type              =  parse_frame_type_gquic_Q035_thru_Q039,
947    .pf_turn_on_fin                   =  lsquic_turn_on_fin_Q035_thru_Q039,
948};
949