Failed decode using only repair symbols due to rq->max_esi check

[osresearch]

Originally posted by @sleepybishop in #11

Fountain codes like RaptorQ can be used as a systematic code if the original symbols are used in addition to repair packets, or you can use it as a non-systematic code by using all repair symbols.

I tried to modify encode.c to only generate repair symbols to simulate 100% packet loss on the original symbols:

diff --git a/encode.c b/encode.c
index 15c017b..80e86e2 100644
--- a/encode.c
+++ b/encode.c
@@ -30,6 +30,7 @@ void dump_block(nanorq *rq, struct ioctx *myio, FILE *oh, uint8_t sbn) {
 
   uint32_t num_esi = nanorq_block_symbols(rq, sbn);
   int num_dropped = 0, num_rep = 0;
+#if 0
   for (uint32_t esi = 0; esi < num_esi; esi++) {
     float dropped = ((float)(rand()) / (float)RAND_MAX) * (float)100.0;
     float drop_prob = expected_loss;
@@ -39,6 +40,9 @@ void dump_block(nanorq *rq, struct ioctx *myio, FILE *oh, uint8_t sbn) {
       dump_esi(rq, myio, oh, sbn, esi);
     }
   }
+#else
+  num_dropped = num_esi;
+#endif
   for (uint32_t esi = num_esi; esi < num_esi + num_dropped + overhead; esi++) {
     dump_esi(rq, myio, oh, sbn, esi);
     num_rep++;

This causes decoding to fail:

./encode war_and_peace.txt 1280
block 0 is 165 packets, dropped 165, created 170 repair
block 1 is 164 packets, dropped 164, created 169 repair
block 2 is 164 packets, dropped 164, created 169 repair
block 3 is 164 packets, dropped 164, created 169 repair
block 4 is 164 packets, dropped 164, created 169 repair
block 5 is 164 packets, dropped 164, created 169 repair
block 6 is 164 packets, dropped 164, created 169 repair
block 7 is 164 packets, dropped 164, created 169 repair
block 8 is 164 packets, dropped 164, created 169 repair
block 9 is 164 packets, dropped 164, created 169 repair
block 10 is 164 packets, dropped 164, created 169 repair
block 11 is 164 packets, dropped 164, created 169 repair
block 12 is 164 packets, dropped 164, created 169 repair
block 13 is 164 packets, dropped 164, created 169 repair
block 14 is 164 packets, dropped 164, created 169 repair
block 15 is 164 packets, dropped 164, created 169 repair
./decode peace_and_war.txt
adding symbol 333 failed.
make[1]: *** [example.make:11: peace_and_war.txt] Aborted (core dumped)

Tracing through nanorq_decoder_add_symbol(), it appears that rq->max_esi is 332 (which is set to 2 * rq->P.Kprime in nanorq_decoder_new()), while esi goes up to 334 (165 + 170 - 1). I'm not certain what the correct value should be, but if I comment out the check in lib/nanorq.c line 485 the decode works correctly.

[sleepybishop]

Hi, i don't remember the project I was working on when I added that, but the gist of it was that there is a design flaw in this implementation where memory is allocated internally to contain the entire destination object and large esi's would cause really large allocations, so as a workaround I added the concept of a max esi that the application could set to depending on the use case (via nanorq_set_max_esi. The current value has no meaning beyond it was something that worked for me at the time. I've since deferred such details to the application but I've yet to make those changes here.