ReedSolomon k+1 broken if parity buffer is not zero'ed

[maximelubin]

Stumbled upon this one. Reproduced using the attached mocha test (renamed as .txt for github upload)
rononmon.test.txt

Execution gives out:

$ npm test test/rononmon.test.js

> ecstream@0.1.0 test /home/mlubin/dev/ecstream
> mocha --use_strict --check-leaks --no-exit  "test/rononmon.test.js"



  ✓ Test parity initialization - m=1, initValue=0
  1) Test parity initialization - m=1, initValue=255
  ✓ Test parity initialization - m=2, initValue=0
  ✓ Test parity initialization - m=2, initValue=255

  3 passing (13ms)
  1 failing

  1)  Test parity initialization - m=1, initValue=255:

      Uncaught AssertionError: <Buffer db db db db db db db db> === <Buffer 24 24 24 24 24 24 24 24>
      + expected - actual

       [
      -  219
      -  219
      -  219
      -  219
      -  219
      -  219
      -  219
      -  219
      +  36
      +  36
      +  36
      +  36
      +  36
      +  36
      +  36
      +  36
       ]
      
      at ReedSolomon.encode.err (test/rononmon.test.js:38:36)

Handling of m=1 seems very special. Looking at binding.cc code I found the special code path which directly call dot_xor and do not start with a dot_cpy first:

diff --git a/binding.cc b/binding.cc
index b61ecdd..c323b3e 100644
--- a/binding.cc
+++ b/binding.cc
@@ -705,8 +705,16 @@ void encode(
   ) {
     // Optimization for 1 erasure (i < k + 1), encoding only targets:
     uint8_t* target = shards[flags_first(targets)];
+    int copied = 0;
     for (int i = 0; i < k + 1; i++) {
-      if (sources & (1 << i)) dot_xor(shards[i], target, shardSize);
+      if (sources & (1 << i)) {
+        if (!copied) {
+          dot_cpy(shards[i], target, shardSize);
+          copied = 1;
+        } else {
+          dot_xor(shards[i], target, shardSize);
+        }
+      }
     }
     return;
   }

Can be reproduced in your test by forcing random parity buffers in test.js:

diff --git a/test.js b/test.js
index ef462e9..1c1f902 100644
--- a/test.js
+++ b/test.js
@@ -317,7 +317,7 @@ queue.onData = function(args, end) {
   );
   var buffer = cipher.update(Buffer.alloc(bufferOffset + bufferSize));
   Assert(buffer.length === bufferOffset + bufferSize);
-  var parity = Buffer.alloc(parityOffset + paritySize);
+  var parity = Node.crypto.randomBytes(parityOffset + paritySize);
   if (parityOffset) {
     Assert(
       cipher.update(Buffer.alloc(parityOffset)).copy(parity, 0) === parityOffset

The above patch fixes the issue, at least on the simple test I attached and your tests.

Cheers,
Maxime

[maximelubin]

Created a pull request with aforementioned changes: #5

[jorangreef]

Thanks very much @maximelubin, well spotted!

I made a few comments on your PR.

[jorangreef]

Thanks again @maximelubin, fixed in 6f23d45