Faster and simpler.
Add load of pre-stored operation vectors.

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

Fix division problem and unit tests.

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

Replace Octet lookup tables with a version without the check for zero.

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

Fix an error by increasing the lookup table size by one.
Improve performance by change type from uint16_t to uint8_t.

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

Both counting non-zeroes and finding non-zero values. Great performance gain
when decoding. The same gain is also for the encoder when not using the
operation vector.

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

The operation vector is fast but the number of combinations (hole-locations and
repair-symbols) result in to many cache misses for all but the smallest block
sizes.
Testing with randomized hole-locations and repair-symbols show that caching the
matrix created in the gen-step is faster for a block-size of 26 and up. Another
benefit is that the key-size is smaller.

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

The rows and columns are swapped when creating the sparse Eigen matrix in
phase 3. This improve overall performance a few percent, but the main benefit
is when decoding fails before phase 3.

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

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>