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>

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>

Silence compiler warnings

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>

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

Add delegates to external (MIT-license)

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>

Generate hasn't been executed before call to intermediate if precode is off.

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

Generate hasn't been executed in case there is a cache-miss.

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>

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

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>

Validate GF256 multiplication.

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>

Version 3.3.4 is the latest stable release.

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

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>

From is a void** not a void*

Copy-paste is as bad as ever, I guess...

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

I forgot to delete and set the ptr to nullptr
for the RaptorQ_ptr

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

marginlabels were improperly used instead of
subsubsections

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

Ticket #8

Finally move the documentation to track the
RFC6330 namespace for both C and C++ APIs

fixes are related to the documentation
* decode_symbol was forgotten
* future_state uniformed between RAW and RFC
* renamed a couple of RaptorQ__v1 in RFC6330__v1

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

For Ticket #19

 C examples are needed, too.
Apparently the test/ directory is a bit complicated.

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

symbol++ did not work.
also: we don't use the default second parameter anymore

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

Update the readme with the long term key, updated the versions
to show we are in alpha.

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

Renamed Decoder_aligned_res in Decoder_written

It's really the same, just that the RFC forces the
sizes of the memebers, while in the RAW API we can
keep size_t

also: bump up to 1.0.0-alpha1, things are much better
and consistent now

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

The rfc API still used that "void* &"
switch to void** which makes more sense for the C interface.
Also, that's what we use on the RAW api

While we are at it, force the template to specify both
input *and* output typenames, so that it is easier
to switch between the linked library and the header-only

inline the template so that it can be reincluded
multiple times without redeinitions

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

The flags "complete" and "no_pool" are actually
perfectly compatible.

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

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

Using a struct makes it more portable for C,
and we avoid some first/second which nobody ever
understand/remeber the meaning

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

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

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