[FFmpeg-devel] avformat: Add parityfec and ulpfec protocol

Parityfec (RFC 2733) and ulpfec (RFC 5109) generic FEC encoding for RTP streams.

Signed-off-by: Camille Gonnet <camille@sound4.biz>
---
 Changelog                 |   1 +
 doc/general_contents.texi |   1 +
 doc/protocols.texi        | 106 +++++
 libavformat/Makefile      |   1 +
 libavformat/fecrtp.c      | 884 ++++++++++++++++++++++++++++++++++++++
 libavformat/protocols.c   |   1 +
 libavformat/rtpproto.c    |   2 +-
 7 files changed, 995 insertions(+), 1 deletion(-)
 create mode 100644 libavformat/fecrtp.c

I did not have any feedback on this patch.
Thanks,

On April 9, 2021 at 4:08 PM, Camille Gonnet (camille@sound4.biz) wrote:
Parityfec (RFC 2733) and ulpfec (RFC 5109) generic FEC encoding for RTP streams.

Signed-off-by: Camille Gonnet <camille@sound4.biz>
---
 Changelog                 |   1 +
 doc/general_contents.texi |   1 +
 doc/protocols.texi        | 106 +++++
 libavformat/Makefile      |   1 +
 libavformat/fecrtp.c      | 884 ++++++++++++++++++++++++++++++++++++++
 libavformat/protocols.c   |   1 +
 libavformat/rtpproto.c    |   2 +-
 7 files changed, 995 insertions(+), 1 deletion(-)
 create mode 100644 libavformat/fecrtp.c

diff --git a/Changelog b/Changelog
index a96e350e09..e83ec2c60d 100644
--- a/Changelog
+++ b/Changelog
@@ -83,6 +83,7 @@ version <next>:
 - msad video filter
 - gophers protocol
 - RIST protocol via librist
+- FEC RTP (RFC5109+RFC2733) protocol (encoding only)
 
 
 version 4.3:
diff --git a/doc/general_contents.texi b/doc/general_contents.texi
index 33ece6e884..2b70dfb2ad 100644
--- a/doc/general_contents.texi
+++ b/doc/general_contents.texi
@@ -1368,6 +1368,7 @@ performance on systems without hardware floating point support).
 @multitable @columnfractions .4 .1
 @item Name         @tab Support
 @item AMQP         @tab E
+@item FECRTP       @tab X
 @item file         @tab X
 @item FTP          @tab X
 @item Gopher       @tab X
diff --git a/doc/protocols.texi b/doc/protocols.texi
index d3f6cbefcf..403e7b415d 100644
--- a/doc/protocols.texi
+++ b/doc/protocols.texi
@@ -243,6 +243,112 @@ For example, to convert a GIF file given inline with @command{ffmpeg}:
 ffmpeg -i "data:image/gif;base64,R0lGODdhCAAIAMIEAAAAAAAA//8AAP//AP///////////////ywAAAAACAAIAAADF0gEDLojDgdGiJdJqUX02iB4E8Q9jUMkADs=" smiley.png
 @end example
 
+@section fecrtp
+
+FEC for RTP Protocol. Supports ULP FEC (RFC 5109) and Parity FEC (RFC 2733)
+
+The FEC is a generic parity-check forward error correction mechanism
+for RTP Streams.
+
+This protocol must be used in conjunction with the @code{rtp} protocol.
+
+The required syntax is:
+@example
+-fec fecrtp=@var{option}=@var{val}... rtp://@var{hostname}:@var{port}
+@end example
+
+This protocol accepts the following options:
+@table @option
+
+@item payload_type=@var{n}
+Specify RTP payload type for FEC packets (0-127).
+Default value is 98.
+
+@item port=@var{n}
+Specify RTP port for FEC packets (0-127).
+Default value is (RTP port + 2).
+
+@item host=@var{destination}
+Specify RTP destination for FEC packets.
+If not provided, use same as RTP.
+
+@item kind=@var{kind}
+Set the kind of FEC to use. Default is @code{ulpfec}
+Accepts the following options:
+@table @samp
+@item parityfec
+parityfec (RFC 2733)
+@item ulpfec
+ulpfec (RFC 5109)
+@end table
+
+@item length=@var{n}
+Length of recovery, or 0 for full. (0-1472)
+For @code{kind=ulpfec} only.
+Default value is 0 (full).
+
+@item algorithm=@var{algorithm}
+Set the covered packets algorithm. Default is @code{simple}
+Accepts the following options:
+@table @samp
+@item simple
+Simple usage using @code{span},@code{every} and @code{delay},
+@item rotate
+Combine @code{span-1} packets in the last @code{span} packets in every way.@*
+With span=4 and packets a,b,c,d, will produce (a,b,c) (a,b,d) (a,c,d) (b,c,d).
+@item 1d
+Put the packets in a matrix and compute columns FEC (similar to ProMPEG).
+Use @code{col} and @code{row}.
+@end table
+
+@item span=@var{n}
+The number of RTP packets covered by each FEC packet.
+For @code{algorithm=simple} and @code{algorithm=rotate}.
+Default value is 2.
+
+@item every=@var{n}
+How often we add a FEC packet after a RTP packet (1-20).
+This must be a divider of span.
+For @code{algorithm=simple}.
+Default value is 2.
+
+@item delay=@var{n}
+How many RTP packet we should delay the sending of our FEC packet
+when it is ready (0-20)
+For @code{algorithm=simple}.
+Default value is 0.
+
+@item col=@var{n}
+Number of columns in the matrix.
+For @code{algorithm=1d}.
+Default value is 4.
+
+@item row=@var{n}
+Number of rows in the matrix.
+For @code{algorithm=1d}.
+Default value is 4.
+
+@end table
+
+Example usage:
+@itemize @bullet
+@item
+For 1/4 recovery, 25% overhead
+@example
+-fec fecrtp=span=4:every=4 rtp://@var{hostname}:@var{port}
+@end example
+@item
+For 1/10 recovery, 10% overhead in ulpfec
+@example
+-fec fecrtp=kind=ulpfec,span=10:every=10 rtp://@var{hostname}:@var{port}
+@end example
+@item
+For 1d fec with 4 rows and 4 columns
+@example
+-fec fecrtp=algorithm=1d:col=4:row=4 rtp://@var{hostname}:@var{port}
+@end example
+@end itemize
+
 @section file
 
 File access protocol.
diff --git a/libavformat/Makefile b/libavformat/Makefile
index 0f340f74a0..f393ce14ca 100644
--- a/libavformat/Makefile
+++ b/libavformat/Makefile
@@ -618,6 +618,7 @@ OBJS-$(CONFIG_CRYPTO_PROTOCOL)           += crypto.o
 OBJS-$(CONFIG_DATA_PROTOCOL)             += data_uri.o
 OBJS-$(CONFIG_FFRTMPCRYPT_PROTOCOL)      += rtmpcrypt.o rtmpdigest.o rtmpdh.o
 OBJS-$(CONFIG_FFRTMPHTTP_PROTOCOL)       += rtmphttp.o
+OBJS-$(CONFIG_FECRTP_PROTOCOL)           += fecrtp.o
 OBJS-$(CONFIG_FILE_PROTOCOL)             += file.o
 OBJS-$(CONFIG_FTP_PROTOCOL)              += ftp.o urldecode.o
 OBJS-$(CONFIG_GOPHER_PROTOCOL)           += gopher.o
diff --git a/libavformat/fecrtp.c b/libavformat/fecrtp.c
new file mode 100644
index 0000000000..7e4de1b267
--- /dev/null
+++ b/libavformat/fecrtp.c
@@ -0,0 +1,884 @@
+/*
+ * FEC for RTP - RFC 5109 and RFC 2733
+ * Copyright (c) 2021 SOUND4, France (http://www.sound4.com)
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * FEC for RTP - RFC 5109 and RFC 2733
+ * @author Camille Gonnet <camille@sound4.biz>
+ */
+
+/*
+ * Note: see also prompeg.c which use a derivative of the RFC 2733.
+ *
+ * Algorithm:
+ * Those FEC compute parity of previous RTP frames, but choice of frame is open.
+ * Here 3 algorithm can be used:
+ *   + Simple
+ *     Uses 3 parameters: span, every and delay
+ *     It computes the parity of 'span' sequential packets and output a FEC packet
+ *     every 'every' RTP packets, delaying the send by 'delay' packets when all
+ *     have been send.
+ *   + Rotate
+ *     Uses 1 parameter: span
+ *     It computes parity of 'span'-1 packets over the last 'span' packets, by
+ *     rotating the missing packet in every way.
+ *     With span=4 and packets a,b,c,d, will produce (a,b,c) (a,b,d) (a,c,d) (b,c,d).
+ *   + 1d
+ *     Uses 2 parameters: col,row
+ *     Put the packets in a matrix and compute columns FEC (similar to ProMPEG)
+ *
+ * A typical set is for instance :
+ *   span=5, every=5, delay=0
+ *     which recovers one packet loss over 5 packets with 20% overhead and 5 delay.
+ *
+ * Reminder:
+
+ [RFC 3550] RTP header
+
+    0                   1                   2                   3
+    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |V=2|P|X|  CC   |M|     PT      |       sequence number         |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                           timestamp                           |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |           synchronization source (SSRC) identifier             |
+   +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
+   |            contributing source (CSRC) identifiers              |
+   |                             ....                              |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ [RFC 2733] FEC Packet Structure
+
+    0                   1                   2                   3
+    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                         RTP Header                            |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                         FEC Header                            |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                         FEC Payload                           |
+   |                                                               |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ [RFC 2733] Parity Header Format
+
+    0                   1                   2                   3
+    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |      SN base                  |        length recovery        |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |E| PT recovery |                 mask                          |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                          TS recovery                          |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ [RFC 5109] FEC Packet Structure
+
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                RTP Header (12 octets or more)                 |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                    FEC Header (10 octets)                     |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                      FEC Level 0 Header                       |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                     FEC Level 0 Payload                       |
+   |                                                               |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                      FEC Level 1 Header                       |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                     FEC Level 1 Payload                       |
+   |                                                               |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                            Cont.                              |
+   |                                                               |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ [RFC 5109] FEC Header Format
+
+    0                   1                   2                   3
+    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |E|L|P|X|  CC   |M| PT recovery |            SN base            |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |                          TS recovery                          |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |        length recovery        |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+
+ [RFC 5109] ULP Level Header Format
+
+    0                   1                   2                   3
+    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |       Protection Length       |             mask              |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+   |              mask cont. (present only when L = 1)             |
+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+  */
+
+#include "libavutil/avstring.h"
+#include "libavutil/intreadwrite.h"
+#include "libavutil/opt.h"
+#include "libavutil/parseutils.h"
+#include "libavutil/random_seed.h"
+#include "avformat.h"
+#include "config.h"
+#include "url.h"
+
+typedef struct Fecrtp {
+    uint16_t sn;
+    uint32_t ssrc;
+    uint16_t length_recovery;
+    int size;           // size of the bitstring, so the bigger input packet size
+    uint8_t *bitstring; // We will store the xor of the full packets including RTP header.
+} Fecrtp;
+
+enum {
+    FECRTP_5109                   = 1,
+    FECRTP_2733                   = 2,
+};
+enum {
+    FECRTP_ALGO_SIMPLE            = 1,
+    FECRTP_ALGO_1D                = 2,
+    FECRTP_ALGO_ROTATE            = 3,
+};
+typedef struct FecrtpContext {
+    const AVClass *class;
+
+    int kind;
+    int algorithm;
+
+    int ttl;
+    uint8_t pt;
+    const char *host;
+    uint8_t port;
+    int span, every, delay;
+    int protection_length;
+    int col, row;
+
+    int mask_length;    // in bits
+    int long_header;    // if mask_length>16 (L==1) RFC5109 only
+    URLContext *fec_hd;
+    int fec_arr_len;
+    uint64_t mask;
+
+    Fecrtp **fec_arr;
+    uint8_t *rtp_buf;
+    uint16_t rtp_sn;
+    int packet_idx, packet_idx_max;
+    int bitstring_size;
+    int rtp_buf_size;
+    int init;
+    int first;
+    int last_idx;
+} FecrtpContext;
+
+#define OFFSET(x) offsetof(FecrtpContext, x)
+#define E AV_OPT_FLAG_ENCODING_PARAM
+
+static const AVOption options[] = {
+    { "ttl",   "Time to live (in milliseconds, multicast only)", OFFSET(ttl),
+        AV_OPT_TYPE_INT, { .i64 = -1 }, -1, INT_MAX, .flags = E },
+    { "payload_type", "Specify RTP payload type for FEC packets", OFFSET(pt),
+        AV_OPT_TYPE_INT, { .i64 = 98 }, 0, 127, .flags = E },
+    { "port", "Specify RTP port. Default is RTP port + 2", OFFSET(port),
+        AV_OPT_TYPE_INT, { .i64 = 0 }, 0, 127, .flags = E },
+    { "host", "Specify destination host. Default is same as RTP", OFFSET(host),
+        AV_OPT_TYPE_STRING, { .str = NULL }, 0, 0, .flags = E },
+    { "kind", "Set the FEC kind",
+      OFFSET(kind), AV_OPT_TYPE_INT, { .i64 = FECRTP_5109 }, 1, 2, E, "kind" },
+        { "parityfec", "parityfec (RFC 2733)",
+          0, AV_OPT_TYPE_CONST, { .i64 = FECRTP_2733 }, 1, 2, E, "kind" },
+        { "ulpfec", "ulpfec (RFC 5109)",
+          0, AV_OPT_TYPE_CONST, { .i64 = FECRTP_5109 }, 1, 2, E, "kind" },
+    { "algorithm", "Set the covered packets algorithm",
+      OFFSET(algorithm), AV_OPT_TYPE_INT, { .i64 = FECRTP_ALGO_SIMPLE }, 1, 3, E, "algorithm" },
+        { "simple", "Simple: use span/every/delay",
+          0, AV_OPT_TYPE_CONST, { .i64 = FECRTP_ALGO_SIMPLE }, 1, 3, E, "algorithm" },
+        { "rotate", "Rotating: combine (span-1) packets in the last (span) packets in every way.",
+          0, AV_OPT_TYPE_CONST, { .i64 = FECRTP_ALGO_ROTATE }, 1, 3, E, "algorithm" },
+        { "1d", "1D: column mode (similar to ST2022-1). Use col/row",
+          0, AV_OPT_TYPE_CONST, { .i64 = FECRTP_ALGO_1D }, 1, 3, E, "algorithm" },
+    { "span",  "Number of packets covered each time (algorithm=simple,rotate)", OFFSET(span),
+        AV_OPT_TYPE_INT, { .i64 =  2 }, 2, 24, .flags = E },
+    { "every", "Insert a FEC packet every # RTP packets (algorithm=simple)", OFFSET(every),
+        AV_OPT_TYPE_INT, { .i64 =  2 }, 1, 24, .flags = E },
+    { "delay", "Send FEC packet # packets after last covered (algorithm=simple)", OFFSET(delay),
+        AV_OPT_TYPE_INT, { .i64 =  0 }, 0, 24, .flags = E },
+    { "col", "Number of matrix column (algorithm=1d)", OFFSET(col),
+        AV_OPT_TYPE_INT, { .i64 =  4 }, 2, 24, .flags = E },
+    { "row", "Number of matrix row (algorithm=1d)", OFFSET(row),
+        AV_OPT_TYPE_INT, { .i64 =  4 }, 2, 24, .flags = E },
+
+    { NULL }
+};
+
+static const AVClass fecrtp_class = {
+    .class_name = "fecrtp",
+    .item_name  = av_default_item_name,
+    .option     = options,
+    .version    = LIBAVUTIL_VERSION_INT,
+};
+
+static void xor_fast(const uint8_t *in1, int size1, const uint8_t *in2, int size2, uint8_t *out, int size) {
+    int i, n, s, sizemin;
+#if HAVE_FAST_64BIT
+    uint64_t v1, v2;
+#else
+    uint32_t v1, v2;
+#endif
+
+    size = FFMAX(size1, size2);
+    sizemin = FFMIN(size1, size2);
+
+    // Do the XOR where both have data
+#if HAVE_FAST_64BIT
+    n = sizemin / sizeof (uint64_t);
+    s = n * sizeof (uint64_t);
+
+    for (i = 0; i < n; i++) {
+        v1 = AV_RN64A(in1);
+        v2 = AV_RN64A(in2);
+        AV_WN64A(out, v1 ^ v2);
+        in1 += 8;
+        in2 += 8;
+        out += 8;
+    }
+#else
+    n = sizemin / sizeof (uint32_t);
+    s = n * sizeof (uint32_t);
+
+    for (i = 0; i < n; i++) {
+        v1 = AV_RN32A(in1);
+        v2 = AV_RN32A(in2);
+        AV_WN32A(out, v1 ^ v2);
+        in1 += 4;
+        in2 += 4;
+        out += 4;
+    }
+#endif
+
+    n = sizemin - s;
+
+    for (i = 0; i < n; i++) {
+        out[i] = in1[i] ^ in2[i];
+    }
+    s += n;
+
+    // Compute the part where only one has data (padding 0)
+    n = size - s;
+    if (n > 0) {
+        if (size1 >= size2) {
+            memcpy(out,in1, n);
+        } else {
+            memcpy(out,in2, n);
+        }
+    }
+}
+
+static uint16_t bitrev16(uint16_t x)
+{
+       x = (((x & 0xaaaa) >> 1) | ((x & 0x5555) << 1));
+       x = (((x & 0xcccc) >> 2) | ((x & 0x3333) << 2));
+       x = (((x & 0xf0f0) >> 4) | ((x & 0x0f0f) << 4));
+       return((x >> 8) | (x << 8));
+}
+
+static uint32_t bitrev32(uint32_t x)
+{
+       x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
+       x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
+       x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
+       x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
+    return((x >> 16) | (x << 16));
+}
+
+static int fecrtp_init_fecpacket(URLContext *h, const uint8_t *buf, int size) {
+    FecrtpContext *s = h->priv_data;
+    int idx;
+
+    s->last_idx++;
+    if (s->last_idx == s->fec_arr_len)
+        s->last_idx = 0;
+    idx = s->last_idx;
+
+    // sanity check only, should not happen if algorithm are handled properly.
+    if (s->fec_arr[idx]->size>0) {
+        av_log(h, AV_LOG_ERROR, "Internal error, buffer already used (%d)\n", idx);
+        return AVERROR(EINVAL);
+    }
+
+    s->fec_arr[idx]->sn = AV_RB16(buf + 2);
+    // The SSRC value will generally be the same as the SSRC value of the media stream it protects
+    // It MAY be different if the FEC stream is being demultiplexed via the SSRC
+    s->fec_arr[idx]->ssrc = AV_RB32(buf + 8);
+    // Initialize it with the content
+    memcpy(s->fec_arr[idx]->bitstring, buf, size);
+    s->fec_arr[idx]->size = size;
+    s->fec_arr[idx]->length_recovery = (size-12);
+
+    //av_log(h, AV_LOG_DEBUG, "Starting new FEC[%d] SN=%hu SSRC=%X size=%d (packet idx %d)\n",
+        //idx, s->fec_arr[idx]->sn, s->fec_arr[idx]->ssrc, s->fec_arr[idx]->size, s->packet_idx);
+    return 0;
+}
+
+static int fecrtp_add_fecpacket(URLContext *h, int idx, const uint8_t *buf, int size) {
+    FecrtpContext *s = h->priv_data;
+
+    if (s->fec_arr[idx]->size>0) {
+        //av_log(h, AV_LOG_DEBUG, "Adding to FEC[%d] (packet idx %d)\n", idx, s->packet_idx);
+
+        xor_fast(s->fec_arr[idx]->bitstring, s->fec_arr[idx]->size,
+            buf, size,
+            s->fec_arr[idx]->bitstring, FFMAX(size, s->fec_arr[idx]->size));
+        s->fec_arr[idx]->length_recovery ^= (size-12);
+        if (s->fec_arr[idx]->size < size) {
+            s->fec_arr[idx]->size = size;
+        }
+    }
+    return 0;
+}
+
+static int fecrtp_write_fec2733(URLContext *h, Fecrtp *fec, uint32_t ts_current, uint64_t mask) {
+    FecrtpContext *s = h->priv_data;
+    uint8_t *buf = s->rtp_buf; // zero-filled
+    uint8_t *b = fec->bitstring;
+    uint16_t sn;
+    int ret;
+
+    sn = ++s->rtp_sn;
+
+    // RTP Header (12 bytes)
+    // V=2, P=xor, X=xor, CC=xor
+    buf[0] = 0x80| (b[0] & 0x3f);
+    // M=xor, PT=fixed
+    buf[1] = (b[1] & 0x80) | s->pt;
+    // SN=ours
+    AV_WB16(buf + 2, sn);
+    // TS=current
+    AV_WB32(buf + 4, ts_current);
+    // SSRC=original
+    AV_WB32(buf + 8, fec->ssrc);
+    // no CSRC or extension, even if bits X or E are set.
+
+    // FEC Header (12 bytes)
+    // SN:original first
+    AV_WB16(buf + 12, fec->sn);
+    // length recovery:xor
+    AV_WB16(buf + 14, fec->length_recovery);
+    // E=0, PT=xor
+    buf[16]=(b[1] & 0X7f);
+    // MASK:MASK (MSb First)
+    AV_WB24(buf + 17, mask);
+    // TS:xor
+    memcpy(buf + 20, b + 4, 4);
+
+    // Payload : part after basic RTP header (12 bytes) of all frames
+    memcpy(buf + 24, b + 12, fec->size-12);
+
+    ret = ffurl_write(s->fec_hd, buf, 24 + fec->size - 12);
+    return ret;
+}
+
+static int fecrtp_write_fec5109(URLContext *h, Fecrtp *fec, uint32_t ts_current, uint64_t mask) {
+    FecrtpContext *s = h->priv_data;
+    uint8_t *buf = s->rtp_buf; // zero-filled
+    uint8_t *b = fec->bitstring;
+    uint16_t sn;
+    int ret;
+    int headerlen;
+
+    sn = ++s->rtp_sn;
+
+    // RTP Header (12 bytes)
+    // V=2, P=0, X=0, CC=0
+    buf[0] = 0x80;
+    // M=0, PT=fixed
+    buf[1] = s->pt;
+    // SN=ours
+    AV_WB16(buf + 2, sn);
+    // TS=current
+    AV_WB32(buf + 4, ts_current);
+    // SSRC=original
+    AV_WB32(buf + 8, fec->ssrc);
+    // no CSRC
+
+    // FEC Header (10 bytes)
+    // E=0, L=0|1, P,X,CC:xor
+    buf[12] = (s->long_header<<6) | (b[0] & 0x3F);
+    // M,PT:xor
+    buf[13] = b[1];
+    // SN:original first
+    AV_WB16(buf + 14, fec->sn);
+    // TS:xor
+    memcpy(buf + 16, b + 4, 4);
+    // length:xor
+    AV_WB16(buf + 20, fec->length_recovery);
+
+    // FEC Level 0 Header
+    // Protection Length: note clear in RFC, guess this is the level payload length
+    AV_WB16(buf + 22, fec->size-12);
+    // Mask : (LSb First)
+    AV_WB16(buf + 24, bitrev16(mask));
+    headerlen = 24+2;
+    if (s->long_header) {
+        mask >>= 16;
+        AV_WB32(buf + 26, bitrev32(mask));
+        headerlen += 4;
+    }
+    // Payload : part after basic RTP header (12 bytes) of all frames
+    memcpy(buf + headerlen, b + 12, fec->size-12);
+
+    ret = ffurl_write(s->fec_hd, buf, headerlen + fec->size - 12);
+    return ret;
+}
+
+static int fecrtp_send_fecpacket(URLContext *h, int idx, const uint8_t *buf, uint64_t mask) {
+    FecrtpContext *s = h->priv_data;
+    uint32_t ts_current;
+    int ret = 0;
+
+    // Sanity check, should not happen if algorithm are handled properly.
+    if (!s->fec_arr[idx]->size) {
+        av_log(h, AV_LOG_ERROR, "Internal error, want to send uninitialized buffer (%d)\n", idx);
+        return AVERROR(EINVAL);
+    }
+
+    // The timestamp MUST be set to the value of the media
+    // RTP clock at the instant the FEC packet is transmitted
+    ts_current = AV_RB32(buf + 4);
+    switch (s->kind) {
+    case FECRTP_2733:
+        if ((ret = fecrtp_write_fec2733(h, s->fec_arr[idx], ts_current, mask)) < 0)
+            goto end;
+        break;
+    case FECRTP_5109:
+        if ((ret = fecrtp_write_fec5109(h, s->fec_arr[idx], ts_current, mask)) < 0)
+            goto end;
+        break;
+    };
+    // mark packet as free for reuse (internal check)
+    s->fec_arr[idx]->size = 0;
+
+end:
+    return ret;
+}
+
+static int fecrtp_open(URLContext *h, const char *uri, int flags) {
+    FecrtpContext *s = h->priv_data;
+    AVDictionary *udp_opts = NULL;
+    int rtp_port, fec_port;
+    char rtp_hostname[256];
+    const char *hostname;
+    char buf[1024];
+
+    s->fec_hd = NULL;
+
+    av_url_split(NULL, 0, NULL, 0, rtp_hostname, sizeof (rtp_hostname), &rtp_port,
+            NULL, 0, uri);
+
+    if (s->port) {
+        fec_port = s->port;
+    } else {
+        if (rtp_port < 1 || rtp_port > UINT16_MAX - 2) {
+            av_log(h, AV_LOG_ERROR, "Invalid RTP base port %d\n", rtp_port);
+            return AVERROR(EINVAL);
+        }
+        fec_port = rtp_port + 2;
+    }
+    if (s->host) {
+        hostname = s->host;
+    } else {
+        hostname = rtp_hostname;
+    }
+
+    if (s->ttl > 0) {
+        av_dict_set_int(&udp_opts, "ttl", s->ttl, 0);
+    }
+
+    ff_url_join(buf, sizeof (buf), "udp", NULL, hostname, fec_port, NULL);
+    if (ffurl_open_whitelist(&s->fec_hd, buf, flags, &h->interrupt_callback,
+            &udp_opts, h->protocol_whitelist, h->protocol_blacklist, h) < 0)
+        goto fail;
+
+    h->max_packet_size = s->fec_hd->max_packet_size;
+    s->init = 1;
+
+    av_dict_free(&udp_opts);
+    return 0;
+
+fail:
+    ffurl_closep(&s->fec_hd);
+    av_dict_free(&udp_opts);
+    return AVERROR(EIO);
+}
+
+static int fecrtp_init(URLContext *h, const uint8_t *buf, int size) {
+    FecrtpContext *s = h->priv_data;
+    uint32_t seed;
+    int i;
+    uint64_t mask_bit;
+
+    s->fec_arr = NULL;
+    s->rtp_buf = NULL;
+
+    if (size < 12 || size > UINT16_MAX + 12) {
+        av_log(h, AV_LOG_ERROR, "Invalid RTP packet size\n");
+        return AVERROR_INVALIDDATA;
+    }
+
+    switch (s->algorithm) {
+    case FECRTP_ALGO_SIMPLE:
+        if ( (s->span < s->every) || (s->span % s->every)!=0 ) {
+            av_log(h, AV_LOG_ERROR, "'span' must be a multiple of 'every'\n");
+            return AVERROR_INVALIDDATA;
+        }
+        s->mask_length = s->span;
+        break;
+    case FECRTP_ALGO_ROTATE:
+        s->mask_length = s->span - 1;
+        break;
+    case FECRTP_ALGO_1D:
+        s->span = s->row * s->col;
+        s->mask_length = s->row * s->col;
+        break;
+    };
+
+    switch (s->kind) {
+    case FECRTP_2733:
+        if (s->mask_length > 24) {
+            av_log(h, AV_LOG_ERROR, "Invalid FEC parameters: maximum mask is 24 bits\n");
+            return AVERROR_INVALIDDATA;
+        }
+        break;
+    case FECRTP_5109:
+        s->long_header = (s->mask_length > 16)? 1 : 0;
+        if (s->mask_length > 48) {
+            av_log(h, AV_LOG_ERROR, "Invalid FEC parameters: maximum mask is 48 bits\n");
+            return AVERROR_INVALIDDATA;
+        }
+        break;
+    };
+    s->mask=0;
+    mask_bit=1;
+    switch (s->algorithm) {
+    case FECRTP_ALGO_SIMPLE:
+        for (i=0;i<s->span;i++) {
+            s->mask |= mask_bit;
+            mask_bit <<= 1;
+        }
+        s->fec_arr_len = s->span / s->every + s->delay;
+        // Round up packet index to a multiple of fec_arr_len
+        s->packet_idx_max = INT_MAX - (INT_MAX % s->fec_arr_len);
+        break;
+    case FECRTP_ALGO_ROTATE:
+        // mask will change each time, by removing 1 bit
+        s->mask = (1<<s->span) -1;
+        s->fec_arr_len = s->span;
+        // Round up packet index to a multiple of fec_arr_len
+        s->packet_idx_max = INT_MAX - (INT_MAX % s->fec_arr_len);
+        break;
+    case FECRTP_ALGO_1D:
+        for (i=0;i< s->row;i++) {
+            s->mask |= mask_bit;
+            mask_bit <<= s->col;
+        }
+        s->fec_arr_len = s->col * 2;
+        // Round up packet index to a multiple of fec_arr_len
+        s->packet_idx_max = INT_MAX - (INT_MAX % (s->col * s->row));
+        break;
+    };
+
+    s->packet_idx = 0;
+    if (h->flags & AVFMT_FLAG_BITEXACT) {
+        s->rtp_sn = 0;
+    } else {
+        seed = av_get_random_seed();
+        s->rtp_sn = seed & 0x0fff;
+    }
+
+    if (s->kind == FECRTP_2733) {
+        s->rtp_buf_size = 24 + h->max_packet_size; // 12 + 12: RTP + FEC headers
+        s->bitstring_size = 10 + h->max_packet_size; // 10: P, X, CC, M, PT, SN, TS, Length
+    } else /* if (s->kind == FECRTP_5109) */ {
+        s->rtp_buf_size = 28 + (s->protection_length?s->protection_length:h->max_packet_size); // 12 + 16: RTP + FEC headers
+        s->bitstring_size = 10 + (s->protection_length?s->protection_length:h->max_packet_size); // 10: P, X, CC, M, PT, SN, TS, Length
+    }
+
+    s->fec_arr = av_malloc_array(s->fec_arr_len, sizeof (Fecrtp*));
+    if (!s->fec_arr) {
+        goto fail;
+    }
+    for (i = 0; i < s->fec_arr_len; i++) {
+        s->fec_arr[i] = av_malloc(sizeof (Fecrtp));
+        if (!s->fec_arr[i]) {
+            goto fail;
+        }
+        s->fec_arr[i]->size=0;
+        s->fec_arr[i]->bitstring = av_malloc_array(s->bitstring_size, sizeof (uint8_t));
+        if (!s->fec_arr[i]->bitstring) {
+            av_freep(&s->fec_arr[i]);
+            goto fail;
+        }
+    }
+    // Simplifying: first one will be 0 in array
+    s->last_idx = s->fec_arr_len-1;
+
+    s->rtp_buf = av_malloc_array(s->rtp_buf_size, sizeof (uint8_t));
+    if (!s->rtp_buf) {
+        goto fail;
+    }
+    memset(s->rtp_buf, 0, s->rtp_buf_size);
+
+    s->init = 0;
+    switch (s->algorithm) {
+    case FECRTP_ALGO_SIMPLE:
+        s->first = s->span + s->delay - 1;
+        av_log(h, AV_LOG_INFO, "FEC: %s algorithm simple, span=%d every=%d delay=%d\n",
+            s->kind==FECRTP_5109?"ulpfec":"parityfec", s->span, s->every, s->delay);
+        break;
+    case FECRTP_ALGO_ROTATE:
+        s->first = 0;
+        av_log(h, AV_LOG_INFO, "FEC: %s algorithm rotate, span=%d\n",
+            s->kind==FECRTP_5109?"ulpfec":"parityfec", s->span);
+        break;
+    case FECRTP_ALGO_1D:
+        s->first = s->col * s->row;
+        av_log(h, AV_LOG_INFO, "FEC: %s algorithm 1d, col=%d, row=%d\n",
+            s->kind==FECRTP_5109?"ulpfec":"parityfec", s->col, s->row);
+        break;
+    };
+
+    return 0;
+
+fail:
+    av_log(h, AV_LOG_ERROR, "Failed to allocate the FEC buffer\n");
+    return AVERROR(ENOMEM);
+}
+
+static int fecrtp_write(URLContext *h, const uint8_t *buf, int size) {
+    FecrtpContext *s = h->priv_data;
+    int idx, first_is_new=0;
+    int ret = 0;
+    int protected_size = size;
+    uint64_t mask_clear;
+    int cur_row, cur_col;
+
+    if (s->kind == FECRTP_5109) {
+        // if protection_length is set, forget all after
+        if (s->protection_length > 0 && protected_size > s->protection_length)
+            protected_size = s->protection_length;
+    }
+
+    if (s->init && ((ret = fecrtp_init(h, buf, protected_size)) < 0))
+        goto end;
+
+    if (protected_size > s->bitstring_size) {
+        av_log(h, AV_LOG_ERROR, "The RTP packet size exceed the max_packet_size\n");
+        return AVERROR(EINVAL);
+    }
+
+    idx = s->last_idx;
+    // Create/Update needed FEC packets
+    switch (s->algorithm) {
+    case FECRTP_ALGO_SIMPLE:
+        if (s->packet_idx % s->every == 0) {
+            if ((ret = fecrtp_init_fecpacket(h, buf, protected_size)) <0)
+                goto end;
+
+            // Do not xor this one
+            first_is_new = 1;
+        }
+        // One RTP packet will be used in (span/every) FEC packets
+        for (int n=0; n < s->span/s->every; n++) {
+            if (first_is_new) {
+                first_is_new--;
+            } else {
+                // next one to process
+                if (!idx)
+                    idx = s->fec_arr_len;
+                idx--;
+                if ((ret=fecrtp_add_fecpacket(h, idx, buf, protected_size)) < 0)
+                    goto end;
+            }
+        }
+        break;
+    case FECRTP_ALGO_ROTATE:
+        // comments for case span==4
+        if (s->packet_idx % s->span == 0) {
+            // create all but last (a,b,c) (a,b,d) (a,c,d)
+            for (int n=0; n < s->span-1; n++) {
+                if ((ret = fecrtp_init_fecpacket(h, buf, protected_size)) <0)
+                    goto end;
+            }
+            // idx is on last
+        } else if (s->packet_idx % s->span == 1) {
+            // create last now (b,c,d)
+            if ((ret = fecrtp_init_fecpacket(h, buf, protected_size)) <0)
+                goto end;
+            // And XOR all but two last (last just created)
+            for (int n=0; n < s->span-2; n++) {
+                // Add the xor to all but
+                idx=s->last_idx+1+n;
+                if (idx >= s->fec_arr_len)
+                    idx -= s->fec_arr_len;
+                if ((ret=fecrtp_add_fecpacket(h, idx, buf, protected_size)) < 0)
+                    goto end;
+            }
+            // idx is on last-1
+        } else {
+            // XOR all but last-packet_idx
+            for (int n=0; n < s->span; n++) {
+                idx=s->last_idx+1+n;
+                if (idx >= s->fec_arr_len)
+                    idx -= s->fec_arr_len;
+                if (n != (s->span - 1 - (s->packet_idx % s->span))) {
+                    if ((ret=fecrtp_add_fecpacket(h, idx, buf, protected_size)) < 0)
+                        goto end;
+                }
+            }
+        }
+        break;
+    case FECRTP_ALGO_1D:
+        // Where are we in matrix
+        cur_col = s->packet_idx % s->col;
+        cur_row = (s->packet_idx / s->col ) % s->row;
+        if (!cur_row) {
+            // First row, we create the FEC at each column
+            if ((ret = fecrtp_init_fecpacket(h, buf, protected_size)) <0)
+                goto end;
+        } else {
+            // we process current column
+            idx = (s->last_idx - s->col + 1) + cur_col;
+            if (idx >= s->fec_arr_len)
+                idx -= s->fec_arr_len;
+            if ((ret=fecrtp_add_fecpacket(h, idx, buf, protected_size)) < 0)
+                goto end;
+        }
+        break;
+    };
+
+    // Send needed FEC packets
+    if (s->first) {
+        // Not enough data to send
+        //av_log(h, AV_LOG_DEBUG, "not sending (first=%d)\n", s->first);
+        s->first--;
+    } else {
+        switch (s->algorithm) {
+        case FECRTP_ALGO_SIMPLE:
+            // Should we send now ?
+            if ((s->packet_idx - (s->span-1) - s->delay) % s->every == 0) {
+                // Skip the delay if needed
+                idx-=s->delay+1;
+                if (idx < 0)
+                    idx += s->fec_arr_len;
+                if ((ret=fecrtp_send_fecpacket(h, idx, buf, s->mask)) < 0)
+                    goto end;
+            }
+            break;
+        case FECRTP_ALGO_ROTATE:
+            // comments for case span==4
+            if (s->packet_idx % s->span == s->span - 2) {
+                // Send first one at one before last
+                mask_clear=1<<(s->span-1);  // This one is not in the xor
+                idx=s->last_idx+1;  // circular -> go first
+                if (idx >= s->fec_arr_len)
+                    idx -= s->fec_arr_len;
+                if ((ret=fecrtp_send_fecpacket(h, idx, buf, s->mask & (~mask_clear))) < 0)
+                    goto end;
+            } else if (s->packet_idx % s->span == s->span - 1) {
+                // Send all others on last
+                for (int n=1; n < s->span; n++) {
+                    mask_clear=1<<(s->span-1-n);  // This one is not in the xor
+                    // For the last one, we started one later, so clear MSB
+                    if (n == s->span-1)
+                        mask_clear=1<<(s->span-1);
+                    idx=s->last_idx+1+n;
+                    if (idx >= s->fec_arr_len)
+                        idx -= s->fec_arr_len;
+                    if ((ret=fecrtp_send_fecpacket(h, idx, buf, s->mask & (~mask_clear))) < 0)
+                        goto end;
+                }
+            }
+            break;
+        case FECRTP_ALGO_1D:
+            // cur_col and cur_row already set to where we are in matrix
+            // evenly space them, starting of 1st of matrix
+            // we have s->col to send in s->col*s->row packets
+            if ((cur_col+cur_row*s->col)%s->row == 0) {
+                // Find index of first of previous matrix
+                if (!cur_row) {
+                    // only cur_col has been added for new matrix
+                    idx = (s->last_idx - cur_col + s->col);
+                } else {
+                    // all have been added  for new matrix
+                    idx = (s->last_idx  + 1);
+                }
+                idx += (cur_col+cur_row*s->col)/s->row;
+                idx %= s->fec_arr_len;
+                if ((ret=fecrtp_send_fecpacket(h, idx, buf, s->mask)) < 0)
+                    goto end;
+            }
+            break;
+        };
+    }
+
+    // prepare for next packet
+    s->packet_idx++;
+    if (s->packet_idx == s->packet_idx_max)
+        s->packet_idx = 0;
+
+    ret = protected_size;
+
+end:
+    return ret;
+}
+
+static int fecrtp_close(URLContext *h) {
+    FecrtpContext *s = h->priv_data;
+    int i;
+
+    ffurl_closep(&s->fec_hd);
+
+    if (s->fec_arr) {
+        for (i = 0; i < s->fec_arr_len; i++) {
+            av_free(s->fec_arr[i]->bitstring);
+            av_freep(&s->fec_arr[i]);
+        }
+        av_freep(&s->fec_arr);
+    }
+    av_freep(&s->rtp_buf);
+
+    return 0;
+}
+
+const URLProtocol ff_fecrtp_protocol = {
+    .name                      = "fecrtp",
+    .url_open                  = fecrtp_open,
+    .url_write                 = fecrtp_write,
+    .url_close                 = fecrtp_close,
+    .priv_data_size            = sizeof(FecrtpContext),
+    .flags                     = URL_PROTOCOL_FLAG_NETWORK,
+    .priv_data_class           = &fecrtp_class,
+};
diff --git a/libavformat/protocols.c b/libavformat/protocols.c
index fb6fabdce5..af16313fdb 100644
--- a/libavformat/protocols.c
+++ b/libavformat/protocols.c
@@ -31,6 +31,7 @@ extern const URLProtocol ff_crypto_protocol;
 extern const URLProtocol ff_data_protocol;
 extern const URLProtocol ff_ffrtmpcrypt_protocol;
 extern const URLProtocol ff_ffrtmphttp_protocol;
+extern const URLProtocol ff_fecrtp_protocol;
 extern const URLProtocol ff_file_protocol;
 extern const URLProtocol ff_ftp_protocol;
 extern const URLProtocol ff_gopher_protocol;
diff --git a/libavformat/rtpproto.c b/libavformat/rtpproto.c
index 7dd6042158..a58472d684 100644
--- a/libavformat/rtpproto.c
+++ b/libavformat/rtpproto.c
@@ -295,7 +295,7 @@ static int rtp_open(URLContext *h, const char *uri, int flags)
             av_log(h, AV_LOG_ERROR, "Failed to parse the FEC protocol value\n");
             goto fail;
         }
-        if (strcmp(fec_protocol, "prompeg")) {
+        if (strcmp(fec_protocol, "prompeg") && strcmp(fec_protocol, "fecrtp")) {
             av_log(h, AV_LOG_ERROR, "Unsupported FEC protocol %s\n", fec_protocol);
             goto fail;
         }
--
2.25.1

Hi,

On Fri, 9 Apr 2021, Camille Gonnet wrote:

> Parityfec (RFC 2733) and ulpfec (RFC 5109) generic FEC encoding for RTP streams.
>
> Signed-off-by: Camille Gonnet <camille@sound4.biz>
> ---
> Changelog                 |   1 +
> doc/general_contents.texi |   1 +
> doc/protocols.texi        | 106 +++++
> libavformat/Makefile      |   1 +
> libavformat/fecrtp.c      | 884 ++++++++++++++++++++++++++++++++++++++
> libavformat/protocols.c   |   1 +
> libavformat/rtpproto.c    |   2 +-
> 7 files changed, 995 insertions(+), 1 deletion(-)
> create mode 100644 libavformat/fecrtp.c

I had a brief look at this... I'm not familiar with how fec protocols are 
hooked up and all that, but it does seem to follow the existing practice 
for the prompg protocol.

Stylistically, the code could adhere a bit more to the ffmpeg style (it 
misses space around operators in many places, random example:

+                mask_clear=1<<(s->span-1);  // This one is not in the xor
+                idx=s->last_idx+1;  // circular -> go first

The bitrev16/32 functions have incorrect indentation and odd spacing 
("return((x >> 8 ..."). I wonder if we have any existing function that do 
the same - as av_bswap* only swap bytes - maybe not...

The code uses a number of commented out av_log calls, which isn't 
stylistically great... As they already are added with a low enough debug 
level (AV_LOG_DEBUG) couldn't they be left in the code (so that they end 
up compiled and syntax checked)?

I didn't try following the whole algorithm, but I had a peek at some 
comments which I didn't quite understand, e.g. this one:

+    int size;           // size of the bitstring, so the bigger input packet size

Is that a typo in the comment, or just something I'd understand if I'd 
read the code more thoroughly?

// Martin