Introduce per group slice sizes.
authorAndre Noll <maan@systemlinux.org>
Sat, 7 Aug 2010 16:36:45 +0000 (18:36 +0200)
committerAndre Noll <maan@systemlinux.org>
Sun, 31 Oct 2010 11:06:58 +0000 (12:06 +0100)
While the FEC parameters k and n are fixed, the size of a FEC slice may
be different for each FEC group. This patch exploits this freedom and
implements variable sized FEC slices for the DCCP and UDP transports.

Two new functions, compute_group_size() and compute_slice_size(),
are introduced which try to compute an optimal size for the entire
FEC group and the slice size of the group respectively.

The group size is chosen such that the group duration is approximately
150ms. Larger values cause too much latency while smaller groups use
the available bandwidth ineffectively. Several contraints such as
the maximal packet size are taken into account when computing the
group size.

Once the group size is known, a suitable slice size is chosen. It
should be as small as possible to avoid unnecessary FEC calculations
but must be large enough to guarantee that the k data slices suffice
to encode the header (if needed) and the data chunk(s).

vss.c

diff --git a/vss.c b/vss.c
index 2e952eb..3405d5a 100644 (file)
--- a/vss.c
+++ b/vss.c
@@ -129,6 +129,8 @@ struct fec_group {
        struct timeval slice_duration;
        /** Group contains the audio file header that occupies that many slices. */
        uint8_t num_header_slices;
+       /** Number of bytes per slice for this group. */
+       uint16_t slice_bytes;
 };
 
 enum fec_client_state {
@@ -209,7 +211,7 @@ static void write_fec_header(struct fec_client *fc, struct vss_task *vsst)
        write_u32(buf + 14, g->bytes);
 
        write_u8(buf + 18, fc->current_slice_num);
-       write_u16(buf + 20, fc->mps - FEC_HEADER_SIZE);
+       write_u16(buf + 20, g->slice_bytes);
        write_u8(buf + 22, g->first_chunk? 0 : 1);
        write_u8(buf + 23, vsst->header_len? 1 : 0);
        memset(buf + 24, 0, 7);
@@ -231,14 +233,13 @@ static bool need_audio_header(struct fec_client *fc, struct vss_task *vsst)
        return true;
 }
 
-static int num_slices(long unsigned bytes, int mps, int rs)
+static int num_slices(long unsigned bytes, int max_payload, int rs)
 {
-       int m = mps - FEC_HEADER_SIZE;
        int ret;
 
-       assert(m > 0);
+       assert(max_payload > 0);
        assert(rs > 0);
-       ret = DIV_ROUND_UP(bytes, m);
+       ret = DIV_ROUND_UP(bytes, max_payload);
        if (ret + rs > 255)
                return -E_BAD_CT;
        return ret;
@@ -258,7 +259,7 @@ static void set_group_timing(struct fec_client *fc, struct fec_group *g)
 
 static int initialize_fec_client(struct fec_client *fc, struct vss_task *vsst)
 {
-       int k, n, ret, mps;
+       int k, n, ret;
        int hs, ds, rs; /* header/data/redundant slices */
        struct fec_client_parms *fcp = fc->fcp;
 
@@ -272,40 +273,36 @@ static int initialize_fec_client(struct fec_client *fc, struct vss_task *vsst)
                ret = fcp->init_fec(fc->sc);
                if (ret < 0)
                        return ret;
-               mps = ret;
+               fc->mps = ret;
        } else
-               mps = generic_max_transport_msg_size(fc->sc->fd);
-       if (mps <= FEC_HEADER_SIZE)
+               fc->mps = generic_max_transport_msg_size(fc->sc->fd);
+       if (fc->mps <= FEC_HEADER_SIZE)
                return -ERRNO_TO_PARA_ERROR(EINVAL);
 
        rs = fc->fcp->slices_per_group - fc->fcp->data_slices_per_group;
-       ret = num_slices(vsst->header_len, mps, rs);
+       ret = num_slices(vsst->header_len, fc->mps - FEC_HEADER_SIZE, rs);
        if (ret < 0)
                goto err;
        hs = ret;
-       ret = num_slices(mmd->afd.max_chunk_size, mps, rs);
+       ret = num_slices(mmd->afd.max_chunk_size, fc->mps - FEC_HEADER_SIZE, rs);
        if (ret < 0)
                goto err;
        ds = ret;
-       k = ret + ds;
+       k = hs + ds;
        if (k < fc->fcp->data_slices_per_group)
                k = fc->fcp->data_slices_per_group;
+       fc->num_extra_slices = k - fc->fcp->data_slices_per_group;
        n = k + rs;
-       PARA_CRIT_LOG("hs: %d, ds: %d, rs: %d, k: %d, n: %d\n", hs, ds, rs, k, n);
        fec_free(fc->parms);
        ret = fec_new(k, n, &fc->parms);
        if (ret < 0)
                return ret;
-       fc->num_extra_slices = k - fc->fcp->data_slices_per_group;
-       PARA_NOTICE_LOG("fec parms %d:%d:%d (%d extra slices)\n",
-               mps, k, n, fc->num_extra_slices);
+       PARA_INFO_LOG("mps: %d, k: %d, n: %d, extra slices: %d\n",
+               fc->mps, k, n, fc->num_extra_slices);
        fc->src_data = para_realloc(fc->src_data, k * sizeof(char *));
-       fc->enc_buf = para_realloc(fc->enc_buf, mps);
-       memset(fc->enc_buf, 0, mps);
-       fc->extra_src_buf = para_realloc(fc->extra_src_buf, mps);
-       memset(fc->extra_src_buf, 0, mps);
+       fc->enc_buf = para_realloc(fc->enc_buf, fc->mps);
+       fc->extra_src_buf = para_realloc(fc->extra_src_buf, fc->mps);
 
-       fc->mps = mps;
        fc->state = FEC_STATE_READY_TO_RUN;
        fc->next_header_time.tv_sec = 0;
        fc->stream_start = *now;
@@ -316,14 +313,145 @@ err:
        return ret;
 }
 
+static void compute_group_size(struct vss_task *vsst, struct fec_group *g,
+               int max_bytes)
+{
+       int i, max_chunks = PARA_MAX(1LU, 150 / tv2ms(vss_chunk_time()));
+
+       g->num_chunks = 0;
+       g->bytes = 0;
+       /*
+        * Include chunks into the group until the group duration is at least
+        * 150ms.  For ogg and wma, a single chunk's duration (ogg page/wma
+        * super frame) is already larger than 150ms, so a FEC group consists
+        * of exactly one chunk for these audio formats.
+        */
+       for (i = 0;; i++) {
+               const char *buf;
+               size_t len;
+               int chunk_num = g->first_chunk + i;
+
+               if (g->bytes > 0 && i >= max_chunks) /* duration limit */
+                       break;
+               if (chunk_num >= mmd->afd.afhi.chunks_total) /* eof */
+                       break;
+               afh_get_chunk(chunk_num, &mmd->afd.afhi, vsst->map, &buf, &len);
+               if (g->bytes + len > max_bytes)
+                       break;
+               /* Include this chunk */
+               g->bytes += len;
+               g->num_chunks++;
+       }
+       assert(g->num_chunks);
+}
+
+/*
+ * Compute the slice size of the next group.
+ *
+ * The FEC parameters n and k are fixed but the slice size varies per
+ * FEC group.  We'd like to choose slices as small as possible to avoid
+ * unnecessary FEC calculations but large enough to guarantee that the
+ * k data slices suffice to encode the header (if needed) and the data
+ * chunk(s).
+ *
+ * Once we know the payload of the next group, we define the number s
+ * of bytes per slice for this group by
+ *
+ *     s = ceil(payload / k)
+ *
+ * However, for header streams, computing s is more complicated since no
+ * overlapping of header and data slices is possible. Hence we have k >=
+ * 2 and s must satisfy
+ *
+ * (*) ceil(h / s) + ceil(d / s) <= k
+ *
+ * where h and d are payload of the header and the data chunk(s)
+ * respectively. In general there is no value for s such that (*)
+ * becomes an equality, for example if h = 4000, d = 5000 and k = 10.
+ *
+ * We use the following approach for computing a suitable value for s:
+ *
+ * Let
+ *     k1 := ceil(k * min(h, d) / (h + d)),
+ *     k2 := k - k1.
+ *
+ * Note that k >= 2 implies k1 > 0 and k2 > 0, so
+ *
+ *     s := max(ceil(min(h, d) / k1), ceil(max(h, d) / k2))
+ *
+ * is well-defined. Inequality (*) holds for this value of s since k1
+ * slices suffice to store min(h, d) while k2 slices suffice to store
+ * max(h, d), i.e. the first addent of (*) is bounded by k1 and the
+ * second by k2.
+ *
+ * For the above example we obtain
+ *
+ *     k1 = ceil(10 * 4000 / 9000) = 5, k2 = 5,
+ *     s = max(4000 / 5, 5000 / 5) = 1000,
+ *
+ * which is optimal since a slice size of 999 bytes would already require
+ * 11 slices.
+ */
+static int compute_slice_size(struct fec_client *fc, struct vss_task *vsst)
+{
+       struct fec_group *g = &fc->group;
+       int k = fc->fcp->data_slices_per_group + fc->num_extra_slices;
+       int n = fc->fcp->slices_per_group + fc->num_extra_slices;
+       int ret, k1, k2, h, d, min, max, sum;
+       int max_slice_bytes = fc->mps - FEC_HEADER_SIZE;
+       int max_group_bytes;
+
+       if (!need_audio_header(fc, vsst)) {
+               max_group_bytes = k * max_slice_bytes;
+               g->num_header_slices = 0;
+               compute_group_size(vsst, g, max_group_bytes);
+               g->slice_bytes = DIV_ROUND_UP(g->bytes, k);
+               if (g->slice_bytes == 0)
+                       g->slice_bytes = 1;
+               return 1;
+       }
+       h = vsst->header_len;
+       max_group_bytes = (k - num_slices(h, max_slice_bytes, n - k))
+               * max_slice_bytes;
+       compute_group_size(vsst, g, max_group_bytes);
+       d = g->bytes;
+       if (d == 0) {
+               g->slice_bytes = DIV_ROUND_UP(h, k);
+               ret = num_slices(vsst->header_len, g->slice_bytes, n - k);
+               if (ret < 0)
+                       return ret;
+               g->num_header_slices = ret;
+               return 1;
+       }
+       min = PARA_MIN(h, d);
+       max = PARA_MAX(h, d);
+       sum = h + d;
+       k1 = DIV_ROUND_UP(k * min, sum);
+       k2 = k - k1;
+       assert(k1 > 0);
+       assert(k2 > 0);
+
+       g->slice_bytes = PARA_MAX(DIV_ROUND_UP(min, k1), DIV_ROUND_UP(max, k2));
+       /*
+        * This value of s := g->slice_bytes satisfies inequality (*) above,
+        * but it might be larger than max_slice_bytes. However, we know that
+        * max_slice_bytes are sufficient to store header and data, so:
+        */
+       g->slice_bytes = PARA_MIN((int)g->slice_bytes, max_slice_bytes);
+
+       ret = num_slices(vsst->header_len, g->slice_bytes, n - k);
+       if (ret < 0)
+               return ret;
+       g->num_header_slices = ret;
+       return 1;
+}
+
 static int setup_next_fec_group(struct fec_client *fc, struct vss_task *vsst)
 {
        int ret, i, k, n, data_slices;
        size_t len;
-       const char *buf, *start_buf;
+       const char *buf;
        struct fec_group *g = &fc->group;
-       unsigned slice_bytes;
-       uint32_t max_data_size;
 
        if (fc->state == FEC_STATE_NONE) {
                ret = initialize_fec_client(fc, vsst);
@@ -332,7 +460,6 @@ static int setup_next_fec_group(struct fec_client *fc, struct vss_task *vsst)
                g->first_chunk = mmd->current_chunk;
                g->num = 0;
                g->start = *now;
-               
        } else {
                struct timeval tmp;
                if (g->first_chunk + g->num_chunks >= mmd->afd.afhi.chunks_total)
@@ -347,32 +474,16 @@ static int setup_next_fec_group(struct fec_client *fc, struct vss_task *vsst)
                g->first_chunk += g->num_chunks;
                g->num++;
        }
-       slice_bytes = fc->mps - FEC_HEADER_SIZE;
-       PARA_CRIT_LOG("slice_bytes: %d\n", slice_bytes);
        k = fc->fcp->data_slices_per_group + fc->num_extra_slices;
        n = fc->fcp->slices_per_group + fc->num_extra_slices;
-       PARA_CRIT_LOG("k: %d, n: %d\n", k, n);
-       if (need_audio_header(fc, vsst)) {
-               ret = num_slices(vsst->header_len, slice_bytes, n - k);
-               if (ret < 0)
-                       return ret;
-               g->num_header_slices = ret;
-       } else
-               g->num_header_slices = 0;
-       afh_get_chunk(g->first_chunk, &mmd->afd.afhi, vsst->map, &start_buf,
-               &len);
-       data_slices = k - g->num_header_slices;
-       assert(data_slices);
-       max_data_size = slice_bytes * data_slices;
-       g->bytes = 0;
-       for (i = g->first_chunk; i < mmd->afd.afhi.chunks_total; i++) {
-               afh_get_chunk(i, &mmd->afd.afhi, vsst->map, &buf, &len);
-               if (g->bytes + len > max_data_size)
-                       break;
-               g->bytes += len;
-       }
-       g->num_chunks = i - g->first_chunk;
-       assert(g->num_chunks);
+
+       compute_slice_size(fc, vsst);
+       assert(g->slice_bytes > 0);
+       ret = num_slices(g->bytes, g->slice_bytes, n - k);
+       if (ret < 0)
+               return ret;
+       data_slices = ret;
+       assert(g->num_header_slices + data_slices <= k);
        fc->current_slice_num = 0;
        if (g->num == 0)
                set_group_timing(fc, g);
@@ -381,37 +492,42 @@ static int setup_next_fec_group(struct fec_client *fc, struct vss_task *vsst)
        buf = vsst->header_buf;
        for (i = 0; i < g->num_header_slices; i++) {
                fc->src_data[i] = (const unsigned char *)buf;
-               buf += slice_bytes;
+               buf += g->slice_bytes;
        }
 
        /* setup data slices */
-       buf = start_buf;
-       for (i = g->num_header_slices; i < k; i++) {
-               if (buf + slice_bytes > vsst->map + mmd->size)
+       afh_get_chunk(g->first_chunk, &mmd->afd.afhi, vsst->map, &buf, &len);
+       for (; i < g->num_header_slices + data_slices; i++) {
+               if (buf + g->slice_bytes > vsst->map + mmd->size) {
                        /*
                         * Can not use the memory mapped audio file for this
                         * slice as it goes beyond the map. This slice will not
                         * be fully used.
                         */
+                       uint32_t payload_size = vsst->map + mmd->size - buf;
+                       memcpy(fc->extra_src_buf, buf, payload_size);
+                       if (payload_size < g->slice_bytes)
+                               memset(fc->extra_src_buf + payload_size, 0,
+                                       g->slice_bytes - payload_size);
+                       fc->src_data[i] = fc->extra_src_buf;
+                       i++;
                        break;
+               }
                fc->src_data[i] = (const unsigned char *)buf;
-               buf += slice_bytes;
+               buf += g->slice_bytes;
        }
        if (i < k) {
-               uint32_t payload_size = vsst->map + mmd->size - buf;
-               memcpy(fc->extra_src_buf, buf, payload_size);
-               fc->src_data[i] = fc->extra_src_buf;
-               i++;
                /* use arbitrary data for all remaining slices */
                buf = vsst->map;
                for (; i < k; i++)
                        fc->src_data[i] = (const unsigned char *)buf;
        }
-       PARA_DEBUG_LOG("FEC group %d: %d chunks (%d - %d), "
-               "%d header slices, %d data slices\n",
+       PARA_DEBUG_LOG("FEC group %d: %d chunks (%d - %d), %d bytes\n",
                g->num, g->num_chunks, g->first_chunk,
-               g->first_chunk + g->num_chunks - 1,
-               g->num_header_slices, data_slices
+               g->first_chunk + g->num_chunks - 1, g->bytes
+       );
+       PARA_DEBUG_LOG("slice_bytes: %d, %d header slices, %d data slices\n",
+               g->slice_bytes, g->num_header_slices, data_slices
        );
        return 1;
 }
@@ -432,7 +548,7 @@ static int compute_next_fec_slice(struct fec_client *fc, struct vss_task *vsst)
        }
        write_fec_header(fc, vsst);
        fec_encode(fc->parms, fc->src_data, fc->enc_buf + FEC_HEADER_SIZE,
-               fc->current_slice_num, fc->mps - FEC_HEADER_SIZE);
+               fc->current_slice_num, fc->group.slice_bytes);
        return 1;
 }
 
@@ -883,8 +999,9 @@ static void vss_send(struct vss_task *vsst)
                if (compute_next_fec_slice(fc, vsst) <= 0)
                        continue;
                PARA_DEBUG_LOG("sending %d:%d (%u bytes)\n", fc->group.num,
-                       fc->current_slice_num, fc->mps);
-               fc->fcp->send_fec(fc->sc, (char *)fc->enc_buf, fc->mps);
+                       fc->current_slice_num, fc->group.slice_bytes);
+               fc->fcp->send_fec(fc->sc, (char *)fc->enc_buf,
+                       fc->group.slice_bytes + FEC_HEADER_SIZE);
                fc->current_slice_num++;
                fec_active = 1;
        }