This will improve perfomance when decoding fails.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

 - The precomputed matrix was created from the operation vector.
 - The operation vector scale much better with problem size than matrix
   multiplication.
 - Storing an operation vector for block size 347 takes less than half of the
   space of storing a precomputed matrix.
 - Creating encoded symbols for block size 347 is 100x faster with an
   operations vector using SSSE3 than using a precomputed matrix. Note that
   other parts also take time so the overall performance increase is around 40x
   for block size 347.
 - The performance gains also apply to decoding.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

Add SIMD for row operations add, div and multiply-add.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

This is a pre-step for adding SIMD row-operations.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

Matrices A and X in phase three are both sparse in their structure. Sparse
matrix multiplication is both faster and scale a lot better with block size
(symbols per block).

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

Much faster than before, a cache of 100 MiB runs fast. The solution is built
with a map and a deque. The map is used for key based lookup and the deque is
used for keeping order (which keys are accessed the most). The key is stored
twice and the map take up some extra space so there is an increased overhead.

Add and get is logarithmic time. There might be a need to remove a couple of
items before add, if that is the case each removal will be logarithmic.
Resize is either constant (if size is increased) or n * logarithmic where n is
the number of items that need to be removed.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

 - Fix storage space calculations.
 - Reverse sorting order, largest value first.
 - Add unit tests.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

Validate GF256 multiplication.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

Generate hasn't been executed in case there is a cache-miss.
Generate hasn't been executed before call to intermediate if precode is off.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

The documentation is in place and updated
even for the RAW API. a bit more testing
and we are done with v1

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Also: set the default thread number for concurrency
decoding of the RAW decoder to 1 (no concurrency)

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

De_Interleaver was not properly calculating
when to stop, and the decode_bytes was working with
old assumptions on de_interleaver.

fixed both

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Parts of it were not usable, other parts could
have been better

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

The linked version was not usable, and there were
inconsistencies. much better not, probably
still work to do.

The same will be done on the RFC wrappers

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Due to the wrking threads we can not really move
the RAW of RFC decoders.

We *can* move the wrappers, and *_void however.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

encode() was still expecting the symbol in
host endianness. the iterator was calling it
with the host endianness, too, so we did not notice.

The funny thing? The stable version was patched
correctly, and does not have this problem...

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Work for ticket #23



Get an RFC packet and add it to the decoder.
Not really tested :P

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Lots of bugs made any data taken from this binary
pretty useless. Now everything seems a bit more plausible.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

RAW API should be complete up to the C++ decoder
not included

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

block_size() optimistically reported the block size
as extracted from the partitioning. The problem
is that the last block is not always full, so the
last block had the wrong size.

report the right size

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

also a couple of other tests in there, but nothing
noteworthy, really

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Fixes #24



Sometimes it makes sense to have incomplete data.
This way we both de-interleave the incomplete data
and we give a std::vector<bool> of which bytes were
transmitted correctly and which were zeroed out.

Accessible through the end_of_input() calls, as it is the
only call that makes sense for this, since we need to
also ignore any other repair symbol.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Small optimization taken from OpenRQ.
Do not compute something that will not be
read again.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Things are much more stable and tested.
Documentation is still missing.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

The de_interleaver was still following the
raw esi (max_esi == extended_esi) instead of the
real number of symbols in the block.

Also a minor bugfix that probably does not change
anything in precode_solver

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Nothing of real value here

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

And I only found it by using this in an other project
..I really need some comprehensive tests...

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

2 bugs found in phase1

* wrong row tracking
* did not account for non_zero == 1

After looking at that code again, I think it needs a
small rewrite, some things could be a bit more efficient...

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Anders Martinsson authored Mar 15, 2018 and Luker committed Mar 16, 2018

Loop from 'i' to 'M' instead of 'i' to 'L' during Gaussian elimination in the
second phase.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>

This probably comes from a ill-fated idea to optimize and stop after the
triangular matrix is parsed, but that prevented us from parsing
other repair symbols. Which is really wrong.

Good work for ticket #21



Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

This table is used to generate random values
so this should help a lot towards fixing #20



Thanks to Anders Martinsson for reporting.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

We were doing really bad stuff.
* we were not using the correct block size, but instead
  creating something completely out-of standard
  This surely means that we were not compatible with
  OpenRQ (Ticket #20), and possibly a reason for which
  decoding fails too ofter (Ticket #21).
* We used the wrong ESI number, which should skip
  the padding numbers (#23, #20

)
* we did not expose the real block size to the user
  of the RFC namespace (RFC iterators)

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

We only report the number of symbols used in a block,
but you might want to know the size of the matrix we
use internally.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

The OTI fields and the symbol id are all in big endian.
We used the host endianness instead. fix that.

Ticket #22

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

update docs: a variable was renamed to keep the
C and C++ versions in sync

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

...which brings some API breakage :(

notable things:

* C and C++ names for structs and variables are now in sync
* common.hpp is much easier to read
* added "trcked by" "tracks ..." to know that some things
  are to be kept in synch between C and C++
* "RaptorQ_Dec_Result" name was too similar to
  "RaptorQ_Decoder_Result". The C++ version calls it
  "Decoder_wait_res", let's go with that, at least it
  is more different and actually more to the point.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>

Just using wait() on the future does not give the
same semantic meaning as decode_once, which can sometimes
be needed.

Also, the C++ API exposes that, so the C API should really
track it.

Signed-off-by: Luca Fulchir <luker@fenrirproject.org>