Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

reed-solomon

Package Overview
Dependencies
Maintainers
1
Versions
24
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

reed-solomon - npm Package Compare versions

Comparing version 2.0.0 to 3.0.1

queue-stream.js

239

benchmark.js

@@ -0,84 +1,175 @@

var ram = 268435456;
var cpus = require('os').cpus();
var cpu = cpus[0].model;
var cores = cpus.length;
// Using more cores increases throughput.
// Using more than 1/2 available cores can increase latency.
var concurrency = Math.max(2, Math.round(cores / 2));
process['UV_THREADPOOL_SIZE'] = cores;
var QueueStream = require('./queue-stream.js');
var ReedSolomon = require('./index.js');
// Create shards:
var dataShards = 17;
var parityShards = 3;
var totalShards = dataShards + parityShards;
var shardSize = (1024 * 1024 * 8);
var now = Date.now();
var shards = new Array(totalShards);
for (var index = 0; index < totalShards; index++) {
if (index < dataShards) {
shards[index] = new Buffer(shardSize);
var Execute = {};
Execute.Encode = function(binding, vector, end) {
binding.encode(
vector.buffer,
vector.bufferOffset,
vector.bufferSize,
vector.shardLength,
vector.shardOffset,
vector.shardSize,
end
);
};
Execute.Decode = function(binding, vector, end) {
var targets = 0;
targets |= (1 << 0);
targets |= (1 << 1);
targets |= (1 << (totalShards - 1));
binding.decode(
vector.buffer,
vector.bufferOffset,
vector.bufferSize,
vector.shardLength,
vector.shardOffset,
vector.shardSize,
targets,
end
);
};
var dataShards = 10;
var parityShards = 4;
var totalShards = 14;
var binding = {
'Javascript': new ReedSolomon(
dataShards,
parityShards,
ReedSolomon.binding.javascript
),
'Native': new ReedSolomon(
dataShards,
parityShards,
ReedSolomon.binding.native
)
};
function benchmark(type, vectors, name, binding, end) {
if (name == 'Native') {
var queueConcurrency = concurrency;
} else {
shards[index] = new Buffer(shardSize);
shards[index].fill(0);
var queueConcurrency = 1;
}
var now = Date.now();
var sum = 0;
var time = 0;
var count = 0;
var queue = new QueueStream(queueConcurrency);
queue.onData = function(vector, end) {
var hrtime = process.hrtime();
Execute[type](binding, vector,
function(error) {
if (error) return end(error);
var difference = process.hrtime(hrtime);
var ns = (difference[0] * 1e9) + difference[1];
// Count the number of data bytes that can be processed per second:
sum += vector.shardLength * dataShards;
time += ns;
count++;
end();
}
);
};
queue.onEnd = function(error) {
if (error) return end(error);
var elapsed = Date.now() - now;
var latency = (time / count) / 1000000;
var throughput = sum / elapsed / 1000;
display([
name + ':',
'Latency:',
latency.toFixed(3) + 'ms',
'Throughput:',
throughput.toFixed(2) + ' MB/s'
]);
// Rest between benchmarks to leave room for GC:
setTimeout(end, 100);
};
queue.push(vectors);
queue.end();
}
console.log('\nReedSolomon(' + dataShards + ', ' + parityShards + '):');
function display(columns) {
var string = columns[0];
while (string.length < 15) string = ' ' + string;
string += ' ' + columns.slice(1).join(' ');
console.log(string);
}
console.log('');
display([ 'CPU:', cpu ]);
display([ 'Cores:', cores ]);
display([ 'Threads:', concurrency ]);
var bindings = [];
if (ReedSolomon.bindingNative) bindings.push(ReedSolomon.bindingNative);
bindings.push(ReedSolomon.bindingJS);
bindings.forEach(
function(binding) {
if (binding === undefined) throw new Error('Binding not defined.');
if (binding === ReedSolomon.bindingNative) {
var bindingName = 'Native';
} else {
var bindingName = 'Javascript';
}
console.log('Binding: ' + bindingName);
var queue = new QueueStream();
queue.onData = function(type, end) {
console.log('');
console.log('============================================================');
var queue = new QueueStream();
queue.onData = function(shardLength, end) {
var vectors = [];
var length = Math.min(10000, Math.round(ram / 2 / shardLength));
console.log('');
var encodingResults = [];
var decodingResults = [];
// Benchmark several runs of encoding and decoding.
var times = 5;
while (times--) {
// Encode:
var now = Date.now();
var reedSolomon = new ReedSolomon(dataShards, parityShards, binding);
reedSolomon.encode(shards, 0, shardSize);
var elapsed = (Date.now() - now) / 1000;
var encoded = dataShards * shardSize / (1024* 1024);
var rate = 1 / elapsed * encoded;
encodingResults.push('Encode: ' + rate.toFixed(2) + ' MB/s');
// Decode:
var now = Date.now();
var reedSolomon = new ReedSolomon(dataShards, parityShards, binding);
var shardsPresent = new Array(totalShards);
var length = totalShards;
while (length--) shardsPresent[length] = true;
shards[0] = new Buffer(shardSize);
shardsPresent[0] = false;
shards[1] = new Buffer(shardSize);
shardsPresent[1] = false;
shards[totalShards - 1] = new Buffer(shardSize);
shardsPresent[totalShards - 1] = false;
reedSolomon.decode(shards, 0, shardSize, shardsPresent);
var elapsed = (Date.now() - now) / 1000;
var decoded = dataShards * shardSize / (1024* 1024);
var rate = 1 / elapsed * decoded;
decodingResults.push('Decode: ' + rate.toFixed(2) + ' MB/s');
var parameters = [
'Data=' + dataShards,
'Parity=' + parityShards,
'Shard=' + shardLength
];
display([
type + ':',
length + ' x (' + parameters.join(' ') + ')'
]);
while (length--) {
vectors.push({
buffer: Buffer.alloc(totalShards * shardLength),
bufferOffset: 0,
bufferSize: totalShards * shardLength,
shardLength: shardLength,
shardOffset: 0,
shardSize: shardLength
});
}
// Group the encoding and decoding results:
encodingResults.forEach(
function(encodingResult) {
console.log(encodingResult);
}
);
console.log('');
decodingResults.forEach(
function(decodingResult) {
console.log(decodingResult);
}
);
console.log('');
}
);
var queue = new QueueStream();
queue.onData = function(name, end) {
benchmark(type, vectors, name, binding[name], end);
};
queue.onEnd = end;
queue.push([
'Javascript',
'Native'
]);
queue.end();
};
queue.onEnd = end;
queue.push([
256,
1024,
4096,
65536,
131072,
1048576
]);
queue.end();
};
queue.onEnd = function(error) {
if (error) throw error;
console.log('');
};
queue.push([
'Encode',
'Decode'
]);
queue.end();

883

index.js

@@ -20,341 +20,532 @@ 'use strict';

var self = this;
self.binding = binding || ReedSolomon.bindingNative || ReedSolomon.bindingJS;
self.binding = (
binding || ReedSolomon.binding.native || ReedSolomon.binding.javascript
);
self.dataShards = dataShards;
self.parityShards = parityShards;
self.totalShards = self.dataShards + self.parityShards;
if (self.totalShards > 256) {
if (typeof self.binding != 'object') {
throw new Error('binding must be provided');
}
if (typeof self.binding.encode != 'function') {
throw new Error('binding must have an encode method');
}
ReedSolomon.assertInteger('dataShards', self.dataShards);
ReedSolomon.assertInteger('parityShards', self.parityShards);
ReedSolomon.assertInteger('totalShards', self.totalShards);
if (self.dataShards === 0) throw new Error('dataShards must be > 0');
if (self.parityShards === 0) throw new Error('parityShards must be > 0');
if (self.totalShards === 0) throw new Error('totalShards must be > 0');
if (self.dataShards > 30) throw new Error('dataShards must be <= 30');
if (self.parityShards > 30) throw new Error('parityShards must be <= 30');
if (self.totalShards > 31) {
// The Vandermonde matrix is guaranteed for 256 rows.
throw new Error('Data and parity shards must be at most 256 shards.');
// We use a 31-bit integer to represent sources and targets.
// This is more efficient in Javascript than a 32-bit integer or Array.
// After the 256 shard limit, this imposes a 31 shard limit.
// ReedSolomon on 20+ shards is slow and not to be encouraged.
throw new Error('dataShards + parityShards must be at most 31 shards');
}
self.matrix = ReedSolomon.matrix(self.dataShards, self.totalShards);
self.parityRows = new Array(self.parityShards);
self.parityRows = Buffer.alloc(self.dataShards * self.parityShards);
for (var index = 0; index < self.parityShards; index++) {
self.parityRows[index] = self.matrix.getRow(self.dataShards + index);
var row = self.matrix.getRow(self.dataShards + index);
row.copy(self.parityRows, index * row.length);
}
self.rowSize = self.dataShards;
};
// Checks the consistency of arguments passed to public methods.
ReedSolomon.prototype.check = function(shards, offset, size) {
ReedSolomon.prototype.checkArguments = function(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
targets,
end
) {
var self = this;
// The number of buffers should be equal to the number of
// data shards plus the number of parity shards.
if (shards.length != self.totalShards) {
throw new Error('Wrong number of shards: ' + shards.length);
if (!Buffer.isBuffer(buffer)) {
throw new Error('buffer must be a buffer');
}
// All of the shards should be buffers.
// All of the shards should be the same length.
var shardLength = shards[0].length;
for (var index = 0; index < shards.length; index++) {
var shard = shards[index];
if (!Buffer.isBuffer(shard)) throw new Error('Shards must all be buffers.');
if (shard.length != shardLength) {
throw new Error('Shards are different sizes.');
}
ReedSolomon.assertInteger('bufferOffset', bufferOffset);
ReedSolomon.assertInteger('bufferSize', bufferSize);
ReedSolomon.assertInteger(
'bufferOffset + bufferSize',
bufferOffset + bufferSize
);
ReedSolomon.assertInteger('shardLength', shardLength);
ReedSolomon.assertInteger('shardOffset', shardOffset);
ReedSolomon.assertInteger('shardSize', shardSize);
ReedSolomon.assertInteger(
'shardOffset + shardSize',
shardOffset + shardSize
);
ReedSolomon.assertBits('targets' + targets, targets);
if (typeof end != 'function') {
throw new Error('callback must be a function');
}
if (!ReedSolomon.integer(offset)) {
throw new Error('Argument offset must be a positive integer.');
if (bufferOffset + bufferSize > buffer.length) {
throw new Error(
'bufferOffset=' + bufferOffset + ' + bufferSize=' + bufferSize +
' > buffer.length=' + buffer.length
);
}
if (!ReedSolomon.integer(size)) {
throw new Error('Argument size must be a positive integer.');
if (bufferSize !== (shardLength * self.totalShards)) {
throw new Error(
'bufferSize must be the product of shardLength and totalShards'
);
}
if (shardLength < offset + size) {
throw new Error('Overflow with offset=' + offset + ', size=' + size + '.');
if (shardOffset + shardSize > shardLength) {
throw new Error(
'shardOffset=' + shardOffset + ' + shardSize=' + shardSize +
' > shardLength=' + shardLength
);
}
if (ReedSolomon.indexMSB(targets) + 1 > self.totalShards) {
throw new Error('targets > totalShards');
}
if (ReedSolomon.countBits(targets) > self.parityShards) {
throw new Error('not enough shards present to recover data');
}
};
// Multiplies a subset of rows from a coding matrix by a full set of
// input shards to produce some output shards, and checks that the
// the data in those shards matches what is expected.
ReedSolomon.prototype.checkSomeShards = function(
matrixRows, sources, sourcesLength, targets, targetsLength, offset, size, temp
// Given a list of shards, some of which contain data, fills in the shards which
// do not contain data. Returns quickly if all the shards are present.
ReedSolomon.prototype.decode = function(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
targets,
end
) {
var self = this;
var table = ReedSolomon.Galois.MULTIPLY_TABLE;
for (var targetsIndex = 0; targetsIndex < targetsLength; targetsIndex++) {
var target = targets[targetsIndex];
var matrixRow = matrixRows[targetsIndex];
for (var sourcesIndex = 0; sourcesIndex < sourcesLength; sourcesIndex++) {
var source = sources[sourcesIndex];
var multTableRow = table[matrixRow[sourcesIndex]];
if (sourcesIndex === 0) {
for (var index = offset; index < offset + size; index++) {
temp[index] = multTableRow[source[index]];
self.checkArguments(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
targets,
end
);
if (targets === 0) return end();
function decodeDataShards() {
// If no data shards need to be decoded then we can move on:
var dataShardsMissing = 0;
for (var shardIndex = 0; shardIndex < self.dataShards; shardIndex++) {
if (targets & (1 << shardIndex)) dataShardsMissing++;
}
if (dataShardsMissing === 0) return decodeParityShards();
// Pull out the rows of the matrix that correspond to the shards that we
// have and build a square matrix:
var subMatrix = new ReedSolomon.Matrix(self.dataShards, self.dataShards);
// Pull out an array holding just the shards that correspond to the rows of
// the submatrix. These shards will be the input to the decoding process
// that recreates the missing data shards.
var dataSources = 0;
var count = 0;
var shardIndex = 0;
while (shardIndex < self.totalShards && count < self.dataShards) {
if (!(targets & (1 << shardIndex))) {
// Shard is present and does not need to be decoded.
dataSources |= (1 << shardIndex);
for (var column = 0; column < self.dataShards; column++) {
subMatrix.set(
count,
column,
self.matrix.get(shardIndex, column)
);
}
} else {
for (var index = offset; index < offset + size; index++) {
temp[index] ^= multTableRow[source[index]];
}
count++;
}
shardIndex++;
}
for (var index = offset; index < offset + size; index++) {
if (temp[index] != target[index]) return false;
// Invert the matrix, so that we can go from the encoded shards back to the
// original data. Then pull out the row that generates the shard that we
// want to decode. Note that since this matrix maps back to the orginal
// data, it can be used to create a data shard, but not a parity shard.
var dataMatrix = subMatrix.invert();
// Recreate any data shards that were missing. The inputs to the coding are
// the shards we actually have, and the outputs are the missing data shards.
// The computation is done using the special decode matrix we just built.
var rows = Buffer.alloc(dataShardsMissing * self.dataShards);
var rowsOffset = 0;
var dataTargets = 0;
for (var shardIndex = 0; shardIndex < self.dataShards; shardIndex++) {
if (targets & (1 << shardIndex)) {
// Shard is not present and needs to be decoded.
dataTargets |= (1 << shardIndex);
dataMatrix.getRow(shardIndex).copy(rows, rowsOffset);
rowsOffset += self.rowSize;
}
}
}
return true;
};
// Multiplies a subset of rows from a coding matrix by a full set of
// input shards to produce some output shards.
ReedSolomon.prototype.codeSomeShards = function(
matrixRows, sources, sourcesLength, targets, targetsLength, offset, size
) {
var self = this;
var table = ReedSolomon.Galois.MULTIPLY_TABLE;
for (var targetsIndex = 0; targetsIndex < targetsLength; targetsIndex++) {
var target = targets[targetsIndex];
var matrixRow = matrixRows[targetsIndex];
self.binding.mset(
table[matrixRow[0]],
sources[0],
target,
offset,
offset + size
if (ReedSolomon.countBits(dataTargets) > self.parityShards) {
throw new Error('dataTargets > parityShards');
}
self.binding.encode(
ReedSolomon.Galois.TABLE,
rows,
self.rowSize,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
dataSources,
dataTargets,
decodeParityShards
);
for (var sourcesIndex = 1; sourcesIndex < sourcesLength; sourcesIndex++) {
self.binding.mxor(
table[matrixRow[sourcesIndex]],
sources[sourcesIndex],
target,
offset,
offset + size
);
}
}
};
ReedSolomon.prototype.copy = function(src, srcPos, dst, dstPos, size) {
var self = this;
while (size--) dst[dstPos++] = src[srcPos++];
};
// Given a list of shards, some of which contain data, fills in the shards which
// do not contain data. Returns quickly if all the shards are present.
ReedSolomon.prototype.decode = function(shards, offset, size, present) {
var self = this;
self.check(shards, offset, size);
// Are the shards all present? If so, there is nothing to be done further.
if (!present || present.constructor !== Array) {
throw new Error('Present argument should be an array.');
}
if (present.length !== self.totalShards) {
throw new Error('Present array should have the same length as shards.');
}
var numberPresent = 0;
for (var index = 0; index < self.totalShards; index++) {
if (typeof present[index] !== 'boolean') {
throw new Error('Present array elements should be booleans.');
function decodeParityShards(error) {
if (error) return end(error);
// If no parity shards need to be decoded then we are done:
var parityShardsMissing = 0;
var shardIndex = self.dataShards;
while (shardIndex < self.totalShards) {
if (targets & (1 << shardIndex)) parityShardsMissing++;
shardIndex++;
}
if (present[index]) numberPresent += 1;
}
if (numberPresent == self.totalShards) return;
if (numberPresent < self.dataShards) {
// There is not enough redundant data to recover the missing data.
throw new Error('Not enough shards present to recover data.');
}
// Pull out the rows of the matrix that correspond to the shards that we have
// and build a square matrix.
var subMatrix = new ReedSolomon.Matrix(
self.dataShards,
self.dataShards
);
// Pull out an array holding just the shards that correspond to the rows of
// the submatrix. These shards will be the input to the decoding process that
// recreates the missing data shards.
var subShards = new Array(self.dataShards);
var subMatrixRow = 0;
var matrixRow = 0;
while (matrixRow < self.totalShards && subMatrixRow < self.dataShards) {
if (present[matrixRow]) {
for (var column = 0; column < self.dataShards; column++) {
subMatrix.set(subMatrixRow, column, self.matrix.get(matrixRow, column));
if (parityShardsMissing === 0) return end();
// Now that we have all of the data shards intact, we can compute any of the
// parity shards that are missing. The inputs to the coding are all of the
// data shards, including any that we have just calculated. The outputs are
// all the parity shards which were missing.
var rows = Buffer.alloc(parityShardsMissing * self.dataShards);
var rowsOffset = 0;
var paritySources = Math.pow(2, self.dataShards) - 1;
var parityTargets = 0;
var shardIndex = self.dataShards;
while (shardIndex < self.totalShards) {
if (targets & (1 << shardIndex)) {
parityTargets |= (1 << shardIndex);
self.parityRows.copy(
rows,
rowsOffset,
(shardIndex - self.dataShards) * self.rowSize,
(shardIndex - self.dataShards + 1) * self.rowSize
);
rowsOffset += self.rowSize;
}
subShards[subMatrixRow] = shards[matrixRow];
subMatrixRow += 1;
shardIndex++;
}
matrixRow++;
}
// Invert the matrix, so that we can go from the encoded shards back to the
// original data. Then pull out the row that generates the shard that we want
// to decode. Note that since this matrix maps back to the orginal data, it
// can be used to create a data shard, but not a parity shard.
var dataDecodeMatrix = subMatrix.invert();
// Recreate any data shards that were missing. The inputs to the coding are
// the shards we actually have, and the outputs are the missing data shards.
// The computation is done using the special decode matrix we just built.
var outputs = new Array(self.parityShards);
var matrixRows = new Array(self.parityShards);
var outputCount = 0;
var shardsIndex = 0;
var shardsLength = self.dataShards;
while (shardsIndex < self.dataShards) {
if (!present[shardsIndex]) {
outputs[outputCount] = shards[shardsIndex];
matrixRows[outputCount] = dataDecodeMatrix.getRow(shardsIndex);
outputCount += 1;
if (ReedSolomon.countBits(parityTargets) > self.parityShards) {
throw new Error('parityTargets > parityShards');
}
shardsIndex++;
self.binding.encode(
ReedSolomon.Galois.TABLE,
rows,
self.rowSize,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
paritySources,
parityTargets,
end
);
}
self.codeSomeShards(
matrixRows,
subShards,
self.dataShards,
outputs,
outputCount,
offset,
size
);
// Now that we have all of the data shards intact, we can compute any of the
// parity shards that are missing. The inputs to the coding are all of the
// data shards, including any that we have just calculated. The outputs are
// all the parity shards which were missing.
outputCount = 0;
var shardsIndex = self.dataShards;
var shardsLength = self.totalShards;
while (shardsIndex < self.totalShards) {
if (!present[shardsIndex]) {
outputs[outputCount] = shards[shardsIndex];
matrixRows[outputCount] = self.parityRows[shardsIndex - self.dataShards];
outputCount += 1;
}
shardsIndex++;
}
self.codeSomeShards(
matrixRows,
shards,
self.dataShards,
outputs,
outputCount,
offset,
size
);
decodeDataShards();
};
// Encodes the parity shards for a set of data shards.
// All shards (including parity shards) must be initialized as buffers.
// All shards must be the same size.
// offset: The index of the first byte in each shard to encode.
// size: The number of bytes to encode in each shard.
ReedSolomon.prototype.encode = function(shards, offset, size) {
ReedSolomon.prototype.encode = function(
buffer, bufferOffset, bufferSize, shardLength, shardOffset, shardSize, end
) {
var self = this;
self.check(shards, offset, size);
var outputs = new Array(self.parityShards);
self.copy(shards, self.dataShards, outputs, 0, self.parityShards);
self.codeSomeShards(
self.checkArguments(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
0,
end
);
// Use all data shards as sources:
var sources = Math.pow(2, self.dataShards) - 1;
// Use all parity shards as targets:
var targets = Math.pow(2, self.totalShards) - 1 - sources;
ReedSolomon.assertBits('sources', sources);
ReedSolomon.assertBits('targets', targets);
self.binding.encode(
ReedSolomon.Galois.TABLE,
self.parityRows,
shards,
self.dataShards,
outputs,
self.parityShards,
offset,
size
self.rowSize,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
sources,
targets,
end
);
};
// Returns true if the parity shards contain the right data.
ReedSolomon.prototype.isParityCorrect = function(shards, offset, size, temp) {
var self = this;
self.check(shards, offset, size);
if (!temp) {
throw new Error('Temp buffer should be provided.');
ReedSolomon.assertBits = function(key, value) {
ReedSolomon.assertInteger(key, value);
if (value > 2147483647) {
throw new Error(key + ' > 31 shards: ' + value);
}
if (!Buffer.isBuffer(temp)) {
throw new Error('Temp buffer must be a Buffer.');
};
ReedSolomon.assertBuffer = function(key, value) {
if (!Buffer.isBuffer(value)) {
throw new Error(key + ' must be a buffer');
}
// Temp buffer must be at least the same size as shards.
if (temp.length < shards[0].length) {
throw new Error('Temp buffer is too small.');
};
ReedSolomon.assertInteger = function(key, value) {
if (typeof value != 'number') {
throw new Error(key + ' must be a number');
}
var toCheck = new Array(self.parityShards);
self.copy(shards, self.dataShards, toCheck, 0, self.parityShards);
return self.checkSomeShards(
self.parityRows,
shards,
self.dataShards,
toCheck,
self.parityShards,
offset,
size,
temp
);
if (value < 0) {
throw new Error(key + ' must be positive: ' + value);
}
if (Math.floor(value) !== value) {
throw new Error(key + ' must be an integer: ' + value);
}
if (value > 4294967295) {
throw new Error(key + ' must be a 32-bit integer: ' + value);
}
};
ReedSolomon.bindingJS = {
mset: function(mtable, source, target, offset, length) {
ReedSolomon.binding = {};
ReedSolomon.binding.javascript = {
checkArguments: function(
tables,
rows,
rowSize,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
sources,
targets,
end
) {
ReedSolomon.assertBuffer('tables', tables);
ReedSolomon.assertBuffer('rows', rows);
ReedSolomon.assertInteger('rowSize', rowSize);
ReedSolomon.assertBuffer('buffer', buffer);
ReedSolomon.assertInteger('bufferOffset', bufferOffset);
ReedSolomon.assertInteger('bufferSize', bufferSize);
ReedSolomon.assertInteger('shardLength', shardLength);
ReedSolomon.assertInteger('shardOffset', shardOffset);
ReedSolomon.assertInteger('shardSize', shardSize);
ReedSolomon.assertBits('sources', sources);
ReedSolomon.assertBits('targets', targets);
if (typeof end != 'function') {
throw new Error('callback must be a function');
}
if (tables.length != 65536) {
throw new Error('tables length != 256 x 256');
}
if (bufferOffset + bufferSize > buffer.length) {
throw new Error('bufferOffset + bufferSize > buffer.length');
}
if (shardLength > 0 && (bufferSize % shardLength) !== 0) {
throw new Error('bufferSize must be a multiple of shardLength');
}
if (shardLength === 0 && bufferSize !== 0) {
throw new Error('shardLength === 0 && bufferSize !== 0');
}
if (shardOffset + shardSize > shardLength) {
throw new Error('shardOffset + shardSize > shardLength');
}
if (sources === 0) {
throw new Error('sources == 0 shards');
}
if (targets === 0) {
throw new Error('targets == 0 shards');
}
if (sources > 2147483647) {
throw new Error('sources > 31 shards');
}
if (targets > 2147483647) {
throw new Error('targets > 31 shards');
}
if ((sources & targets) !== 0) {
throw new Error('sources cannot be targets');
}
if (
(ReedSolomon.indexMSB(sources) * shardLength) + shardLength > bufferSize
) {
throw new Error('buffer would overflow (too many sources)');
}
if (
(ReedSolomon.indexMSB(targets) * shardLength) + shardLength > bufferSize
) {
throw new Error('buffer would overflow (too many targets)');
}
if (rows.length != ReedSolomon.countBits(targets) * rowSize) {
throw new Error('rows length != number of targets * rowSize');
}
if (rowSize != ReedSolomon.countBits(sources)) {
throw new Error('rowSize != number of sources');
}
},
encode: function(
tables,
rows,
rowSize,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
sources,
targets,
end
) {
var self = this;
self.checkArguments(
tables,
rows,
rowSize,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
sources,
targets,
end
);
var targetCount = 0;
for (var targetIndex = 0; targetIndex < 31; targetIndex++) {
if (targets & (1 << targetIndex)) {
var rowOffset = targetCount * rowSize;
var targetOffset = bufferOffset + (targetIndex * shardLength);
var target = buffer.slice(targetOffset, targetOffset + shardLength);
var sourceCount = 0;
for (var sourceIndex = 0; sourceIndex < 31; sourceIndex++) {
if (sources & (1 << sourceIndex)) {
var tablesOffset = rows[rowOffset + sourceCount] * 256;
var table = tables.slice(tablesOffset, tablesOffset + 256);
var sourceOffset = bufferOffset + (sourceIndex * shardLength);
var source = buffer.slice(sourceOffset, sourceOffset + shardLength);
if (sourceCount === 0) {
self.mset(
table,
source,
target,
shardOffset,
shardOffset + shardSize
);
} else {
self.mxor(
table,
source,
target,
shardOffset,
shardOffset + shardSize
);
}
sourceCount++;
}
}
targetCount++;
}
}
end();
},
mset: function(table, source, target, offset, length) {
var blocks = Math.floor((length - offset) / 32);
while (blocks--) {
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = mtable[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
target[offset] = table[source[offset++]];
}
while (offset < length) {
target[offset] = mtable[source[offset++]];
target[offset] = table[source[offset++]];
}
},
mxor: function(mtable, source, target, offset, length) {
mxor: function(table, source, target, offset, length) {
var blocks = Math.floor((length - offset) / 32);
while (blocks--) {
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= mtable[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
target[offset] ^= table[source[offset++]];
}
while (offset < length) {
target[offset] ^= mtable[source[offset++]];
target[offset] ^= table[source[offset++]];
}

@@ -365,14 +556,26 @@ }

try {
ReedSolomon.bindingNative = require('./build/Release/binding');
ReedSolomon.binding.native = require('./build/Release/binding.node');
} catch (exception) {
// We use the Javascript binding if the native binding has not been compiled.
ReedSolomon.bindingNative = undefined;
}
ReedSolomon.integer = function(value) {
if (typeof value != 'number') return false;
if (value < 0 || Math.floor(value) !== value) return false;
return true;
ReedSolomon.countBits = function(bits) {
// Count the number of bits set.
ReedSolomon.assertBits('bits', bits);
for (var count = 0; bits; count++) {
bits &= bits - 1;
}
return count;
};
ReedSolomon.indexMSB = function(bits) {
// Find the index of the most significant bit.
ReedSolomon.assertBits('bits', bits);
var index = 31;
while (index--) {
if (bits & (1 << index)) return index;
}
return -1;
};
// Create the matrix to use for encoding, given the number of data shards and

@@ -382,8 +585,4 @@ // the number of total shards. The top square of the matrix should be an

ReedSolomon.matrix = function(dataShards, totalShards) {
if (!ReedSolomon.integer(dataShards)) {
throw new Error('Argument dataShards must be a positive integer.');
}
if (!ReedSolomon.integer(totalShards)) {
throw new Error('Argument totalShards must be a positive integer.');
}
ReedSolomon.assertInteger('dataShards', dataShards);
ReedSolomon.assertInteger('totalShards', totalShards);
// Start with a Vandermonde matrix. This matrix would work in theory, but does

@@ -402,8 +601,4 @@ // not have the property that the data shards are unchanged after encoding.

ReedSolomon.vandermonde = function(rows, columns) {
if (!ReedSolomon.integer(rows)) {
throw new Error('Argument rows must be a positive integer.');
}
if (!ReedSolomon.integer(columns)) {
throw new Error('Argument columns must be a positive integer.');
}
ReedSolomon.assertInteger('rows', rows);
ReedSolomon.assertInteger('columns', columns);
var result = new ReedSolomon.Matrix(rows, columns);

@@ -423,3 +618,3 @@ for (var row = 0; row < rows; row++) {

// field. There is no entry for 255 because the highest log is 254.
ReedSolomon.Galois.EXP_TABLE = new Buffer([
ReedSolomon.Galois.EXP_TABLE = Buffer.from([
1, 2, 4, 8, 16, 32, 64, 128,

@@ -504,3 +699,3 @@ 29, 58, 116, 232, 205, 135, 19, 38,

// index 0 is never used because there is no log of 0.
ReedSolomon.Galois.LOG_TABLE = new Buffer([
ReedSolomon.Galois.LOG_TABLE = Buffer.from([
0, 0, 1, 25, 2, 50, 26, 198,

@@ -548,3 +743,3 @@ 3, 223, 51, 238, 27, 104, 199, 75,

if (a === 0) return 0;
if (b === 0) throw new Error('Divisor cannot be 0.');
if (b === 0) throw new Error('divisor cannot be 0');
var logA = ReedSolomon.Galois.LOG_TABLE[a];

@@ -586,4 +781,3 @@ var logB = ReedSolomon.Galois.LOG_TABLE[b];

ReedSolomon.Galois.generateExpTable = function(logTable) {
var result = new Buffer(ReedSolomon.Galois.FIELD_SIZE * 2 - 2);
result.fill(0);
var result = Buffer.alloc(ReedSolomon.Galois.FIELD_SIZE * 2 - 2);
for (var i = 1; i < ReedSolomon.Galois.FIELD_SIZE; i++) {

@@ -599,4 +793,3 @@ var log = logTable[i];

ReedSolomon.Galois.generateLogTable = function(polynomial) {
var result = new Buffer(ReedSolomon.Galois.FIELD_SIZE);
result.fill(0);
var result = Buffer.alloc(ReedSolomon.Galois.FIELD_SIZE);
var b = 1;

@@ -617,12 +810,12 @@ for (var log = 0; log < ReedSolomon.Galois.FIELD_SIZE - 1; log++) {

// Generates the multiplication table.
ReedSolomon.Galois.generateMultiplyTable = function() {
ReedSolomon.Galois.generateMultiplicationTable = function() {
var size = ReedSolomon.Galois.FIELD_SIZE;
var result = new Array(size);
var table = Buffer.alloc(size * size);
var offset = 0;
for (var a = 0; a < size; a++) {
result[a] = new Buffer(size);
for (var b = 0; b < size; b++) {
result[a][b] = ReedSolomon.Galois.multiply(a, b);
table[offset++] = ReedSolomon.Galois.multiply(a, b);
}
}
return result;
return table;
};

@@ -632,3 +825,3 @@

// using the multiply() method, which is implemented with log/exp table lookups.
ReedSolomon.Galois.MULTIPLY_TABLE = ReedSolomon.Galois.generateMultiplyTable();
ReedSolomon.Galois.TABLE = ReedSolomon.Galois.generateMultiplicationTable();

@@ -641,8 +834,4 @@ // Matrix algebra over an 8-bit Galois field.

// Initialize a matrix of zeroes.
if (!ReedSolomon.integer(initRows)) {
throw new Error('Argument initRows must be a positive integer.');
}
if (!ReedSolomon.integer(initColumns)) {
throw new Error('Argument initColumns must be a positive integer.');
}
ReedSolomon.assertInteger('initRows', initRows);
ReedSolomon.assertInteger('initColumns', initColumns);
self.rows = initRows;

@@ -655,4 +844,4 @@ self.columns = initColumns;

for (var row = 0; row < self.rows; row++) {
self.data[row] = new Buffer(self.columns);
self.data[row].fill(0); // The matrix must be a matrix of zeroes.
// The matrix must be a matrix of zeroes.
self.data[row] = Buffer.alloc(self.columns);
}

@@ -663,3 +852,3 @@ } else {

if (!initData || initData.constructor !== Array) {
throw new Error('Argument initData must be an Array.');
throw new Error('initData must be an Array');
}

@@ -669,3 +858,3 @@ self.rows = initData.length;

if (!Buffer.isBuffer(initData[row])) {
throw new Error('All rows must be Buffers.');
throw new Error('all rows must be Buffers');
}

@@ -677,5 +866,5 @@ }

if (initData[row].length != self.columns) {
throw new Error('All rows must have the same number of columns.');
throw new Error('all rows must have the same number of columns');
}
self.data[row] = new Buffer(self.columns);
self.data[row] = Buffer.alloc(self.columns);
for (var column = 0; column < self.columns; column++) {

@@ -692,3 +881,3 @@ self.data[row][column] = initData[row][column];

if (self.rows != right.rows) {
throw new Error('Matrices do not have the same number of rows.');
throw new Error('matrices do not have the same number of rows');
}

@@ -725,3 +914,3 @@ var result = new ReedSolomon.Matrix(self.rows, self.columns + right.columns);

if (self.data[row][row] === 0) {
throw new Error('Matrix is singular.');
throw new Error('matrix is singular');
}

@@ -771,7 +960,9 @@ // Scale to 1.

var self = this;
if (!ReedSolomon.integer(row) || self.rows <= row) {
throw new Error('Row index is out of range: ' + row);
ReedSolomon.assertInteger('row', row);
ReedSolomon.assertInteger('column', column);
if (self.rows <= row) {
throw new Error('row index is out of range: ' + row);
}
if (!ReedSolomon.integer(column) || self.columns <= column) {
throw new Error('Column index is out of range: ' + column);
if (self.columns <= column) {
throw new Error('column index is out of range: ' + column);
}

@@ -784,3 +975,3 @@ return self.data[row][column];

var self = this;
var result = new Buffer(self.columns);
var result = Buffer.alloc(self.columns);
for (var column = 0; column < self.columns; column++) {

@@ -796,3 +987,3 @@ result[column] = self.get(row, column);

if (self.rows != self.columns) {
throw new Error('Only square matrices can be inverted.');
throw new Error('only square matrices can be inverted');
}

@@ -810,7 +1001,9 @@ // Create a working matrix by augmenting with an identity matrix on the right.

var self = this;
if (!ReedSolomon.integer(row) || self.rows <= row) {
throw new Error('Row index is out of range: ' + row);
ReedSolomon.assertInteger('row', row);
ReedSolomon.assertInteger('column', column);
if (self.rows <= row) {
throw new Error('row index is out of range: ' + row);
}
if (!ReedSolomon.integer(column) || self.columns <= column) {
throw new Error('Column index is out of range: ' + column);
if (self.columns <= column) {
throw new Error('column index is out of range: ' + column);
}

@@ -835,7 +1028,9 @@ self.data[row][column] = value;

var self = this;
if (!ReedSolomon.integer(row1) || row1 >= self.rows) {
throw new Error('Row index 1 is out of range.');
ReedSolomon.assertInteger('row1', row1);
ReedSolomon.assertInteger('row2', row2);
if (row1 >= self.rows) {
throw new Error('row index 1 is out of range');
}
if (!ReedSolomon.integer(row2) || row2 >= self.rows) {
throw new Error('Row index 2 is out of range.');
if (row2 >= self.rows) {
throw new Error('row index 2 is out of range');
}

@@ -901,1 +1096,3 @@ var temp = self.data[row1];

module.exports = ReedSolomon;
// S.D.G.

2

package.json
{
"name": "reed-solomon",
"version": "2.0.0",
"version": "3.0.1",
"description": "Reed-Solomon erasure coding in pure Javascript",

@@ -5,0 +5,0 @@ "main": "index.js",

186

README.md
# reed-solomon
Reed-Solomon erasure coding in pure Javascript. A Javascript port of the [JavaReedSolomon](https://github.com/Backblaze/JavaReedSolomon) library released by [Backblaze](http://backblaze.com). For an introduction to erasure coding, see the post by Brian Beach on the [Backblaze blog](https://www.backblaze.com/blog/reed-solomon/). Special thanks to [Backblaze](http://backblaze.com).
Reed-Solomon erasure coding in pure Javascript with an optional C++ binding for multi-core throughput. A port of the [JavaReedSolomon](https://github.com/Backblaze/JavaReedSolomon) library released by [Backblaze](http://backblaze.com). For an introduction to erasure coding, see the post by Brian Beach on the [Backblaze blog](https://www.backblaze.com/blog/reed-solomon/). Special thanks to [Backblaze](http://backblaze.com).

@@ -20,18 +20,62 @@ ## License

## Efficiency
Data redundancy is typically achieved through mirroring or replication at a cost of 3x the original data. With Reed-Solomon erasure codes, you can achieve better redundancy at a cost of only 1.5x the original data, for example. Various storage efficiencies of 1.4x and 1.18x are also possible. You can trade storage efficiency, redundancy and recovery time by fine-tuning the number of data shards and parity shards you use.
Data redundancy is typically achieved through mirroring or replication at a cost of 3x the original data. With Reed-Solomon erasure codes, you can achieve better redundancy at a cost of only 1.5x the original data. Various storage efficiencies of 1.4x and 1.18x are also possible. You can trade storage efficiency, redundancy and recovery time by fine-tuning the number of data shards and parity shards you use.
## Performance
`reed-solomon` includes a Javascript binding as well as an optional native binding:
`reed-solomon` includes a Javascript binding as well as an optional native binding. The native binding executes asynchronously in Node's threadpool for multi-core throughput and scalability without blocking the event loop:
```
ReedSolomon(17, 3) [1,8 GHz Intel Core i5]:
CPU: Intel(R) Xeon(R) CPU E3-1230 V2 @ 3.30GHz
Cores: 8
Threads: 4
Binding: Native
============================================================
Encode: 400.00 MB/s
Decode: 369.57 MB/s
Encode: 10000 x (Data=10 Parity=4 Shard=256)
Javascript: Latency: 0.028ms Throughput: 88.89 MB/s
Native: Latency: 0.044ms Throughput: 224.56 MB/s
Binding: Javascript
Encode: 10000 x (Data=10 Parity=4 Shard=1024)
Javascript: Latency: 0.064ms Throughput: 159.75 MB/s
Native: Latency: 0.054ms Throughput: 747.45 MB/s
Encode: 195.68 MB/s
Decode: 193.18 MB/s
Encode: 10000 x (Data=10 Parity=4 Shard=4096)
Javascript: Latency: 0.207ms Throughput: 197.02 MB/s
Native: Latency: 0.124ms Throughput: 1312.82 MB/s
Encode: 2048 x (Data=10 Parity=4 Shard=65536)
Javascript: Latency: 3.099ms Throughput: 211.43 MB/s
Native: Latency: 1.637ms Throughput: 1597.83 MB/s
Encode: 1024 x (Data=10 Parity=4 Shard=131072)
Javascript: Latency: 6.202ms Throughput: 211.27 MB/s
Native: Latency: 3.357ms Throughput: 1558.86 MB/s
Encode: 128 x (Data=10 Parity=4 Shard=1048576)
Javascript: Latency: 51.338ms Throughput: 204.23 MB/s
Native: Latency: 26.021ms Throughput: 1595.93 MB/s
============================================================
Decode: 10000 x (Data=10 Parity=4 Shard=256)
Javascript: Latency: 0.068ms Throughput: 37.10 MB/s
Native: Latency: 0.246ms Throughput: 41.36 MB/s
Decode: 10000 x (Data=10 Parity=4 Shard=1024)
Javascript: Latency: 0.095ms Throughput: 107.56 MB/s
Native: Latency: 0.271ms Throughput: 150.59 MB/s
Decode: 10000 x (Data=10 Parity=4 Shard=4096)
Javascript: Latency: 0.196ms Throughput: 208.13 MB/s
Native: Latency: 0.264ms Throughput: 618.73 MB/s
Decode: 2048 x (Data=10 Parity=4 Shard=65536)
Javascript: Latency: 2.390ms Throughput: 274.03 MB/s
Native: Latency: 1.397ms Throughput: 1871.93 MB/s
Decode: 1024 x (Data=10 Parity=4 Shard=131072)
Javascript: Latency: 4.656ms Throughput: 281.32 MB/s
Native: Latency: 2.683ms Throughput: 1950.84 MB/s
Decode: 128 x (Data=10 Parity=4 Shard=1048576)
Javascript: Latency: 36.400ms Throughput: 288.02 MB/s
Native: Latency: 24.051ms Throughput: 1711.96 MB/s
```

@@ -50,56 +94,96 @@

## Usage
Divide a single `Buffer` into an `Array` of fixed-size data shards, then use `reed-solomon` to compute as many parity shards as you need. If you lose some data shards or some parity shards (no more than the number of parity shards you added), you can use `reed-solomon` to reconstruct the missing data and parity shards.
#### Encoding
#### Encoding Parity Shards
```
var ReedSolomon = require('reed-solomon');
// Specify the number of data shards (<=31):
var dataShards = 6;
var parityShards = 3;
var shardSize = 1024 * 1024;
var shards = [
// Data shards (containing user data):
<Buffer (shardSize) >,
<Buffer (shardSize) >,
<Buffer (shardSize) >,
<Buffer (shardSize) >,
<Buffer (shardSize) >,
<Buffer (shardSize) >,
// Specify the number of parity shards (<=31):
var parityShards = 3; // Protect against loss of any 3 data or parity shards.
var totalShards = dataShards + parityShards;
// Specify the total length of each shard in bytes:
var shardLength = 1024 * 1024;
var buffer = Buffer.concat([
// Non-ReedSolomon header data:
<Buffer (16)>,
// Data shards:
<Buffer (shardLength)>,
<Buffer (shardLength)>,
<Buffer (shardLength)>,
<Buffer (shardLength)>,
<Buffer (shardLength)>,
<Buffer (shardLength)>,
// Parity shards:
new Buffer(shardSize),
new Buffer(shardSize),
new Buffer(shardSize)
];
<Buffer (shardLength)>,
<Buffer (shardLength)>,
<Buffer (shardLength)>,
// Non-ReedSolomon footer data:
<Buffer (...)>
]);
// Specify the offset into the buffer at which shards begin:
// This allows you to include non-ReedSolomon header data in the buffer.
var bufferOffset = 16;
// Specify the size after this offset of all shards:
// This allows you to include non-ReedSolomon footer data in the buffer.
var bufferSize = shardLength * totalShards;
// Specify the offset into each shard from which to encode/decode:
// This allows you to include non-ReedSolomon header data in each shard.
var shardOffset = 0;
// Specify the size after this offset:
// This allows you to include non-ReedSolomon footer data in each shard.
var shardSize = shardLength - shardOffset;
// Instantiate a ReedSolomon instance:
// This can be used concurrently across many `encode()`/`decode()` calls.
var rs = new ReedSolomon(dataShards, parityShards);
var offset = 0; // The offset of each shard within each buffer.
var size = shardSize; // The size of each shard within each buffer.
rs.encode(shards, offset, size);
// Parity shards now contain parity data.
// Encode all parity shards:
rs.encode(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
function(error) {
if (error) throw error;
// Parity shards now contain parity data.
}
);
```
#### Verifying Parity Shards
```
rs.isParityCorrect(shards, offset, size); // true/false
```
#### Decoding Corrupted Shards
```
// Corrupt a data shard:
shards[0] = new Buffer(shardSize);
buffer[0] = 255;
// Corrupt a parity shard:
shards[shards.length - 1] = new Buffer(shardSize);
buffer[dataShards + parityShards - 1] = 255;
// We still have enough parity to corrupt another shard.
// Specify each corrupted shard according to its index in the array:
// If a corrupted shard is not specified, the result will be wrong.
var targets = 0;
targets |= (1 << 0); // Data shard at index 0 needs to be decoded.
targets |= (1 << 8); // Parity shard at index 8 needs to be decoded.
// Decode the corrupted data and parity shards:
var present = [
false, // We indicate that shard 1/9 is corrupt. This is a data shard.
true,
true,
true,
true,
true,
true,
true,
false // We indicate that shard 9/9 is corrupt. This is a parity shard.
];
rs.decode(shards, offset, size, present);
// Shards 1 and 9 have been repaired.
rs.decode(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
targets,
function(error) {
if (error) throw error;
// Data shard at index 0 has been repaired.
// Parity shard at index 8 has been repaired.
}
);
```

@@ -106,0 +190,0 @@

882

test.js

@@ -0,3 +1,5 @@

var Node = { crypto: require('crypto') };
var QueueStream = require('./queue-stream.js');
var ReedSolomon = require('./index.js');
var Node = { crypto: require('crypto') };
var Test = {};

@@ -30,53 +32,62 @@

var rs = new ReedSolomon(2, 1);
var shards = [
new Buffer(0),
new Buffer(0),
new Buffer(0)
];
rs.encode(shards, 0, 0);
Test.equal(shards.length, 3, 'ReedSolomon', 'zero encode shards.length');
Test.equal(shards[0].length, 0, 'ReedSolomon', 'zero encode shards[0].length');
Test.equal(shards[1].length, 0, 'ReedSolomon', 'zero encode shards[1].length');
Test.equal(shards[2].length, 0, 'ReedSolomon', 'zero encode shards[2].length');
function CheckParity(
dataShards,
parityShards,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize
) {
var totalShards = dataShards + parityShards;
var matrix = ReedSolomon.matrix(dataShards, totalShards);
var matrixRows = [];
for (var index = 0; index < parityShards; index++) {
matrixRows.push(matrix.getRow(dataShards + index));
}
if (shardOffset + shardSize > shardLength) {
throw new Error('shard overflow');
}
var shards = [];
for (var index = 0; index < totalShards; index++) {
if (bufferOffset + shardLength > buffer.length) {
throw new Error('buffer overflow');
}
var shard = buffer.slice(bufferOffset, bufferOffset += shardLength);
shards.push(shard.slice(shardOffset, shardOffset + shardSize));
}
var sources = shards.slice(0, dataShards);
var targets = shards.slice(dataShards);
if (targets.length !== parityShards) {
throw new Error('targets.length !== parityShards');
}
var temp = Buffer.alloc(shardSize);
var table = ReedSolomon.Galois.TABLE;
var targetsLength = targets.length;
var sourcesLength = sources.length;
for (var targetsIndex = 0; targetsIndex < targetsLength; targetsIndex++) {
var target = targets[targetsIndex];
var matrixRow = matrixRows[targetsIndex];
for (var sourcesIndex = 0; sourcesIndex < sourcesLength; sourcesIndex++) {
var source = sources[sourcesIndex];
var tableOffset = matrixRow[sourcesIndex] * 256;
var tableRow = table.slice(tableOffset, tableOffset + 256);
if (sourcesIndex === 0) {
for (var index = 0; index < shardSize; index++) {
temp[index] = tableRow[source[index]];
}
} else {
for (var index = 0; index < shardSize; index++) {
temp[index] ^= tableRow[source[index]];
}
}
}
for (var index = 0; index < shardSize; index++) {
if (temp[index] != target[index]) return false;
}
}
return true;
}
var rs = new ReedSolomon(5, 5);
var shards = [
new Buffer([0, 1]),
new Buffer([4, 5]),
new Buffer([2, 3]),
new Buffer([6, 7]),
new Buffer([8, 9]),
new Buffer([0, 0]),
new Buffer([0, 0]),
new Buffer([0, 0]),
new Buffer([0, 0]),
new Buffer([0, 0])
];
rs.encode(shards, 0, 2);
Test.equal(shards[0], new Buffer([0, 1]), 'ReedSolomon', 'shard 0');
Test.equal(shards[1], new Buffer([4, 5]), 'ReedSolomon', 'shard 1');
Test.equal(shards[2], new Buffer([2, 3]), 'ReedSolomon', 'shard 2');
Test.equal(shards[3], new Buffer([6, 7]), 'ReedSolomon', 'shard 3');
Test.equal(shards[4], new Buffer([8, 9]), 'ReedSolomon', 'shard 4');
Test.equal(shards[5], new Buffer([12, 13]), 'ReedSolomon', 'shard 5');
Test.equal(shards[6], new Buffer([10, 11]), 'ReedSolomon', 'shard 6');
Test.equal(shards[7], new Buffer([14, 15]), 'ReedSolomon', 'shard 7');
Test.equal(shards[8], new Buffer([90, 91]), 'ReedSolomon', 'shard 8');
Test.equal(shards[9], new Buffer([94, 95]), 'ReedSolomon', 'shard 9');
var temp = new Buffer([0, 0]);
Test.equal(
rs.isParityCorrect(shards, 0, 2, temp),
true,
'ReedSolomon',
'isParityCorrect'
);
shards[8][0] += 1;
Test.equal(
rs.isParityCorrect(shards, 0, 2, temp),
false,
'ReedSolomon',
'isParityCorrect'
);
var actual = ReedSolomon.Matrix.identity(3).toString();

@@ -87,8 +98,8 @@ var expect = '[[1, 0, 0], [0, 1, 0], [0, 0, 1]]';

var m1 = new ReedSolomon.Matrix([
new Buffer([1, 2]),
new Buffer([3, 4])
Buffer.from([1, 2]),
Buffer.from([3, 4])
]);
var m2 = new ReedSolomon.Matrix([
new Buffer([5, 6]),
new Buffer([7, 8])
Buffer.from([5, 6]),
Buffer.from([7, 8])
]);

@@ -100,5 +111,5 @@ var actual = m1.times(m2).toString();

var m = new ReedSolomon.Matrix([
new Buffer([56, 23, 98]),
new Buffer([3, 100, 200]),
new Buffer([45, 201, 123])
Buffer.from([56, 23, 98]),
Buffer.from([3, 100, 200]),
Buffer.from([45, 201, 123])
]);

@@ -119,7 +130,7 @@ Test.equal(

var m = new ReedSolomon.Matrix([
new Buffer([1, 0, 0, 0, 0]),
new Buffer([0, 1, 0, 0, 0]),
new Buffer([0, 0, 0, 1, 0]),
new Buffer([0, 0, 0, 0, 1]),
new Buffer([7, 7, 6, 6, 1])
Buffer.from([1, 0, 0, 0, 0]),
Buffer.from([0, 1, 0, 0, 0]),
Buffer.from([0, 0, 0, 1, 0]),
Buffer.from([0, 0, 0, 0, 1]),
Buffer.from([7, 7, 6, 6, 1])
]);

@@ -168,131 +179,136 @@ var expected = '[' + [

// Test associativity:
for (var a = 0; a < 256; a++) {
for (var b = 0; b < 256; b++) {
for (var c = 0; c < 256; c++) {
assertEquals(
ReedSolomon.Galois.add(a, ReedSolomon.Galois.add(b, c)),
ReedSolomon.Galois.add(ReedSolomon.Galois.add(a, b), c),
'Galois',
'associativity',
2000000
);
assertEquals(
ReedSolomon.Galois.multiply(a, ReedSolomon.Galois.multiply(b, c)),
ReedSolomon.Galois.multiply(ReedSolomon.Galois.multiply(a, b), c),
'Galois',
'associativity',
2000000
);
}
}
}
// // Test associativity:
// for (var a = 0; a < 256; a++) {
// for (var b = 0; b < 256; b++) {
// for (var c = 0; c < 256; c++) {
// assertEquals(
// ReedSolomon.Galois.add(a, ReedSolomon.Galois.add(b, c)),
// ReedSolomon.Galois.add(ReedSolomon.Galois.add(a, b), c),
// 'Galois',
// 'associativity',
// 2000000
// );
// assertEquals(
// ReedSolomon.Galois.multiply(a, ReedSolomon.Galois.multiply(b, c)),
// ReedSolomon.Galois.multiply(ReedSolomon.Galois.multiply(a, b), c),
// 'Galois',
// 'associativity',
// 2000000
// );
// }
// }
// }
//
// // Test identity:
// for (var a = 0; a < 256; a++) {
// assertEquals(a, ReedSolomon.Galois.add(a, 0), 'Galois', 'identity', 32);
// assertEquals(a, ReedSolomon.Galois.multiply(a, 1), 'Galois', 'identity', 32);
// }
//
// // Test inverse:
// for (var a = 0; a < 256; a++) {
// var b = ReedSolomon.Galois.subtract(0, a);
// assertEquals(0, ReedSolomon.Galois.add(a, b), 'Galois', 'inverse', 64);
// if (a !== 0) {
// var b = ReedSolomon.Galois.divide(1, a);
// assertEquals(1, ReedSolomon.Galois.multiply(a, b), 'Galois', 'inverse', 13);
// }
// }
//
// // Test commutativity:
// for (var a = 0; a < 256; a++) {
// for (var b = 0; b < 256; b++) {
// assertEquals(
// ReedSolomon.Galois.add(a, b),
// ReedSolomon.Galois.add(b, a),
// 'Galois',
// 'commutativity',
// 8192
// );
// assertEquals(
// ReedSolomon.Galois.multiply(a, b),
// ReedSolomon.Galois.multiply(b, a),
// 'Galois',
// 'commutativity',
// 8192
// );
// }
// }
//
// // Test distributivity:
// for (var a = 0; a < 256; a++) {
// for (var b = 0; b < 256; b++) {
// for (var c = 0; c < 256; c++) {
// assertEquals(
// ReedSolomon.Galois.multiply(a, ReedSolomon.Galois.add(b, c)),
// ReedSolomon.Galois.add(
// ReedSolomon.Galois.multiply(a, b),
// ReedSolomon.Galois.multiply(a, c)
// ),
// 'Galois',
// 'distributivity',
// 2000000
// );
// }
// }
// }
//
// // Test exp:
// for (var a = 0; a < 256; a++) {
// var power = 1;
// for (var j = 0; j < 256; j++) {
// assertEquals(
// power,
// ReedSolomon.Galois.exp(a, j),
// 'Galois',
// 'exp',
// 4000
// );
// power = ReedSolomon.Galois.multiply(power, a);
// }
// }
//
// // Test log table generation:
// var logTable = ReedSolomon.Galois.generateLogTable(
// ReedSolomon.Galois.GENERATING_POLYNOMIAL
// );
// assertArrayEquals(
// ReedSolomon.Galois.LOG_TABLE,
// logTable,
// 'Galois',
// 'log table'
// );
//
// // Test exp table generation:
// var expTable = ReedSolomon.Galois.generateExpTable(logTable);
// assertArrayEquals(
// ReedSolomon.Galois.EXP_TABLE,
// expTable,
// 'Galois',
// 'exp table'
// );
//
// // Test multiply table:
// var table = ReedSolomon.Galois.TABLE;
// for (var a = 0; a < 256; a++) {
// for (var b = 0; b < 256; b++) {
// assertEquals(
// ReedSolomon.Galois.multiply(a, b),
// table[(a * 256) + b],
// 'Galois',
// 'table',
// 4000
// );
// }
// }
// Test identity:
for (var a = 0; a < 256; a++) {
assertEquals(a, ReedSolomon.Galois.add(a, 0), 'Galois', 'identity', 32);
assertEquals(a, ReedSolomon.Galois.multiply(a, 1), 'Galois', 'identity', 32);
}
// Test inverse:
for (var a = 0; a < 256; a++) {
var b = ReedSolomon.Galois.subtract(0, a);
assertEquals(0, ReedSolomon.Galois.add(a, b), 'Galois', 'inverse', 64);
if (a !== 0) {
var b = ReedSolomon.Galois.divide(1, a);
assertEquals(1, ReedSolomon.Galois.multiply(a, b), 'Galois', 'inverse', 13);
}
}
// Test commutativity:
for (var a = 0; a < 256; a++) {
for (var b = 0; b < 256; b++) {
assertEquals(
ReedSolomon.Galois.add(a, b),
ReedSolomon.Galois.add(b, a),
'Galois',
'commutativity',
8192
);
assertEquals(
ReedSolomon.Galois.multiply(a, b),
ReedSolomon.Galois.multiply(b, a),
'Galois',
'commutativity',
8192
);
}
}
// Test distributivity:
for (var a = 0; a < 256; a++) {
for (var b = 0; b < 256; b++) {
for (var c = 0; c < 256; c++) {
assertEquals(
ReedSolomon.Galois.multiply(a, ReedSolomon.Galois.add(b, c)),
ReedSolomon.Galois.add(
ReedSolomon.Galois.multiply(a, b),
ReedSolomon.Galois.multiply(a, c)
),
'Galois',
'distributivity',
2000000
);
}
}
}
// Test exp:
for (var a = 0; a < 256; a++) {
var power = 1;
for (var j = 0; j < 256; j++) {
assertEquals(
power,
ReedSolomon.Galois.exp(a, j),
'Galois',
'exp',
4000
);
power = ReedSolomon.Galois.multiply(power, a);
}
}
// Test log table generation:
var logTable = ReedSolomon.Galois.generateLogTable(
ReedSolomon.Galois.GENERATING_POLYNOMIAL
);
assertArrayEquals(
ReedSolomon.Galois.LOG_TABLE,
logTable,
'Galois',
'log table'
);
// Test exp table generation:
var expTable = ReedSolomon.Galois.generateExpTable(logTable);
assertArrayEquals(
ReedSolomon.Galois.EXP_TABLE,
expTable,
'Galois',
'exp table'
);
// Test multiply table:
var table = ReedSolomon.Galois.MULTIPLY_TABLE;
for (var a = 0; a < 256; a++) {
for (var b = 0; b < 256; b++) {
assertEquals(
ReedSolomon.Galois.multiply(a, b),
table[a & 0xFF][b & 0xFF],
'Galois',
'mtable',
4000
);
}
}
// Test reference values:
Test.equal(12, ReedSolomon.Galois.multiply(3, 4), 'Galois', 'multiply(3, 4)');
Test.equal(21, ReedSolomon.Galois.multiply(7, 7), 'Galois', 'multiply(7, 7)');
Test.equal(41, ReedSolomon.Galois.multiply(23, 45), 'Galois', 'multiply(23, 45)');
Test.equal(
41,
ReedSolomon.Galois.multiply(23, 45),
'Galois',
'multiply(23, 45)'
);
Test.equal(4, ReedSolomon.Galois.exp(2, 2), 'Galois', 'exp(2, 2)');

@@ -304,37 +320,34 @@ Test.equal(235, ReedSolomon.Galois.exp(5, 20), 'Galois', 'exp(5, 20)');

var generateShard = function(shardSize) {
var buffer = new Buffer(shardSize);
var length = shardSize;
if (random() < 0.05) {
while (length--) buffer[length] = 0;
} else if (random() < 0.05) {
while (length--) buffer[length] = 255;
} else {
while (length--) buffer[length] = Math.round(random() * 255);
}
return buffer;
var sliceShard = function(buffer, bufferOffset, shardIndex, shardLength) {
var shardOffset = shardIndex * shardLength;
return buffer.slice(
bufferOffset + shardOffset,
bufferOffset + shardOffset + shardLength
);
};
var hashShard = function(buffer) {
var hash = Node.crypto.createHash('SHA256');
hash.update(buffer);
return hash.digest('hex').slice(0, 128 / 8 * 2); // Truncate hash to 128 bits.
};
var corruptShard = function(shard, offset, size) {
var corruptShard = function(
buffer,
bufferOffset,
shardIndex,
shardLength,
shardOffset,
shardSize
) {
var shard = sliceShard(buffer, bufferOffset, shardIndex, shardLength);
var seen = {};
var times = Math.min(
size,
shardSize,
Math.max(
1,
Math.round(random() * Math.min(10, size))
Math.round(random() * Math.min(10, shardSize))
)
);
while (times) {
var position = Math.min(size - 1, Math.round(random() * size));
var position = Math.min(shardSize - 1, Math.round(random() * shardSize));
if (seen.hasOwnProperty(position)) continue;
var source = shard[offset + position];
var source = shard[shardOffset + position];
var target = (source + Math.floor(random() * 256)) & 255;
if (target !== source) {
shard[offset + position] = target;
shard[shardOffset + position] = target;
seen[position] = true;

@@ -346,2 +359,12 @@ times--;

var generateShard = function(shardLength) {
return Buffer.alloc(shardLength, Math.floor(random() * 256));
};
var hashShard = function(buffer, bufferOffset, shardIndex, shardLength) {
var hash = Node.crypto.createHash('SHA256');
hash.update(sliceShard(buffer, bufferOffset, shardIndex, shardLength));
return hash.digest('hex').slice(0, 128 / 8 * 2); // Truncate hash to 128 bits.
};
var reinstantiateInstance = function(rs, dataShards, parityShards, binding) {

@@ -353,6 +376,6 @@ if (random() < 0.8) return rs;

var fuzz = function(maxShards, maxShardSize, binding) {
var fuzz = function(binding, parameters, end) {
var minShards = 1;
var minShardSize = 1;
if (binding === ReedSolomon.bindingNative) {
var minShardLength = 0;
if (binding === ReedSolomon.binding.native) {
var bindingType = 'Native';

@@ -366,3 +389,3 @@ } else {

minShards + 1,
Math.round(random() * maxShards)
Math.round(random() * parameters.maxShards)
);

@@ -381,3 +404,3 @@ var dataShards = Math.max(

Test.equal(
dataShards >= 1,
dataShards >= 1 && dataShards <= 31,
true,

@@ -388,3 +411,3 @@ 'ReedSolomon',

Test.equal(
parityShards >= 1,
parityShards >= 1 && dataShards <= 31,
true,

@@ -395,169 +418,334 @@ 'ReedSolomon',

if (random() < 0.01) {
var shardSize = minShardSize;
var shardLength = minShardLength;
} else {
var shardSize = Math.max(
minShardSize,
Math.round(random() * maxShardSize)
var shardLength = Math.max(
minShardLength,
Math.round(random() * parameters.maxShardLength)
);
}
Test.equal(
shardSize >= minShardSize && shardSize <= maxShardSize,
shardLength >= minShardLength && shardLength <= parameters.maxShardLength,
true,
'ReedSolomon',
'shardSize=' + shardSize
'shardLength=' + shardLength
);
if (random() < 0.2) {
var offset = 0;
if (random() < 0.5) {
var shardOffset = 0;
} else {
var offset = Math.min(shardSize - 1, Math.round(random() * shardSize));
var shardOffset = Math.min(
Math.max(0, shardLength - 1),
Math.round(random() * shardLength)
);
}
Test.equal(
offset >= 0 && offset < shardSize,
!(shardOffset < 0 || shardOffset > shardLength),
true,
'ReedSolomon',
'offset=' + offset
'shardOffset=' + shardOffset
);
var remaining = shardSize - offset;
var remaining = shardLength - shardOffset;
if (random() < 0.2) {
var size = remaining;
var shardSize = remaining;
} else {
var size = Math.min(remaining, Math.round(random() * remaining));
if (size < 1) size = 1;
var shardSize = Math.min(remaining, Math.round(random() * remaining));
}
Test.equal(
size > 0 && offset + size <= shardSize,
!(shardSize < 0 || (shardOffset + shardSize) > shardLength),
true,
'ReedSolomon',
'size=' + size
'shardSize=' + shardSize
);
// Create data shards, initialize parity shards and hash data shards:
var shards = new Array(totalShards);
var hashes = new Array(totalShards);
for (var index = 0; index < dataShards; index++) {
shards[index] = generateShard(shardSize); // Data shard.
hashes[index] = hashShard(shards[index]);
}
for (var index = dataShards; index < totalShards; index++) {
shards[index] = generateShard(shardSize); // Parity shard.
}
var rs = new ReedSolomon(dataShards, parityShards, binding);
// Encode parity shards:
rs.encode(shards, offset, size);
// Check that shards were not corrupted by encode():
for (var index = 0; index < dataShards; index++) {
Test.equal(
hashShard(shards[index]),
hashes[index],
'ReedSolomon',
'shard ' + (index + 1) + '/' + totalShards + ' after encoding'
);
}
// Capture parity hashes:
for (var index = dataShards; index < totalShards; index++) {
hashes[index] = hashShard(shards[index]);
}
// Occasionally switch to a new instance:
rs = reinstantiateInstance(rs, dataShards, parityShards, binding);
// Check isParityCorrect() is working for valid shards:
var parityTemp = new Buffer(shardSize);
var bufferOffset = Math.floor(random() * shardLength * 2);
var bufferSize = totalShards * shardLength;
var bufferTail = Math.floor(random() * shardLength * 2);
var buffer = Buffer.alloc(bufferOffset + bufferSize + bufferTail);
Test.equal(
rs.isParityCorrect(shards, offset, size, parityTemp),
true,
true,
'ReedSolomon',
'isParityCorrect'
'bufferOffset=' + bufferOffset
);
// Check that shards were not corrupted by isParityCorrect():
for (var index = 0; index < totalShards; index++) {
Test.equal(
hashShard(shards[index]),
hashes[index],
'ReedSolomon',
'shard ' + (index + 1) + '/' + totalShards + ' after checking parity'
);
}
// Decide how many shards to corrupt:
var corruptShardsCount = Math.max(1, Math.round(random() * parityShards));
Test.equal(
corruptShardsCount >= 1 && corruptShardsCount <= parityShards,
true,
true,
'ReedSolomon',
'corruptShardsCount=' + corruptShardsCount
'bufferSize=' + bufferSize
);
// Choose these shards randomly from data and parity shards:
var corruptShards = new Array(totalShards);
for (var index = 0; index < totalShards; index++) {
corruptShards[index] = index;
var hashes = new Array(totalShards);
for (var index = 0; index < dataShards; index++) {
// Data shard:
var shard = generateShard(shardLength);
shard.copy(buffer, bufferOffset + (index * shardLength));
hashes[index] = hashShard(buffer, bufferOffset, index, shardLength);
}
var order = {};
corruptShards.sort(
function(a, b) {
var key = a < b ? (a + '.' + b) : (b + '.' + a);
if (!order.hasOwnProperty(key)) {
order[key] = random() < 0.5 ? -1 : 1;
for (var index = dataShards; index < totalShards; index++) {
// Parity shard:
var shard = generateShard(shardLength);
shard.copy(buffer, bufferOffset + (index * shardLength));
}
var rs = new ReedSolomon(dataShards, parityShards, binding);
// Encode parity shards:
rs.encode(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
function(error) {
if (error) return end(error);
// Check that shards were not corrupted by encode():
for (var index = 0; index < dataShards; index++) {
Test.equal(
hashShard(buffer, bufferOffset, index, shardLength),
hashes[index],
'ReedSolomon',
'shard ' + (index + 1) + '/' + totalShards + ' after encoding'
);
}
return order[key];
// Capture parity hashes:
for (var index = dataShards; index < totalShards; index++) {
hashes[index] = hashShard(buffer, bufferOffset, index, shardLength);
Test.equal(
hashes[index],
hashes[index],
'ReedSolomon',
'shard ' + (index + 1) + '/' + totalShards + ' after encoding'
);
}
// Check parity shards:
Test.equal(
CheckParity(
dataShards,
parityShards,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize
),
true,
'ReedSolomon',
'parity correct'
);
// Check that shards were not corrupted by checking parity:
for (var index = 0; index < totalShards; index++) {
Test.equal(
hashShard(buffer, bufferOffset, index, shardLength),
hashes[index],
'ReedSolomon',
'shard ' + (index + 1) + '/' + totalShards + ' after checking parity'
);
}
// Occasionally switch to a new instance:
rs = reinstantiateInstance(rs, dataShards, parityShards, binding);
// Decide how many shards to corrupt:
if (shardSize === 0) {
var corruptShardsCount = 0;
} else {
var corruptShardsCount = Math.round(random() * parityShards);
}
Test.equal(
corruptShardsCount >= 0 && corruptShardsCount <= parityShards,
true,
'ReedSolomon',
'corruptShardsCount=' + corruptShardsCount
);
// Choose these shards randomly from data and parity shards:
var corruptShards = new Array(totalShards);
for (var index = 0; index < totalShards; index++) {
corruptShards[index] = index;
}
var order = {};
corruptShards.sort(
function(a, b) {
var key = a < b ? (a + '.' + b) : (b + '.' + a);
if (!order.hasOwnProperty(key)) {
order[key] = random() < 0.5 ? -1 : 1;
}
return order[key];
}
);
var corrupt = {};
for (var index = 0; index < corruptShardsCount; index++) {
corrupt[corruptShards[index]] = true;
}
// Corrupt shards and update targets:
var targets = 0;
for (var index = 0; index < totalShards; index++) {
if (corrupt.hasOwnProperty(index)) {
targets |= (1 << index);
corruptShard(
buffer,
bufferOffset,
index,
shardLength,
shardOffset,
shardSize
);
}
}
// Occasionally switch to a new instance:
rs = reinstantiateInstance(rs, dataShards, parityShards, binding);
// Check parity shards (should now be false):
Test.equal(
CheckParity(
dataShards,
parityShards,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize
),
corruptShardsCount === 0,
'ReedSolomon',
'parity correct'
);
// Decode corrupted shards:
rs.decode(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
targets,
function(error) {
if (error) return end(error);
// Check that shards are all correct:
for (var index = 0; index < totalShards; index++) {
Test.equal(
hashShard(buffer, bufferOffset, index, shardLength),
hashes[index],
'ReedSolomon',
'shard ' + (index + 1) + '/' + totalShards + ' after decoding'
);
}
end();
}
);
}
);
var corrupt = {};
for (var index = 0; index < corruptShardsCount; index++) {
corrupt[corruptShards[index]] = true;
}
// Corrupt shards and update present array:
var present = new Array(totalShards);
for (var index = 0; index < totalShards; index++) {
if (corrupt.hasOwnProperty(index)) {
present[index] = false;
corruptShard(shards[index], offset, size);
} else {
present[index] = true;
}
}
// Occasionally switch to a new instance:
rs = reinstantiateInstance(rs, dataShards, parityShards, binding);
// Check isParityCorrect() is working for corrupt shards:
Test.equal(
rs.isParityCorrect(shards, offset, size, parityTemp),
false,
'ReedSolomon',
'isParityCorrect'
);
// Decode corrupted shards:
rs.decode(shards, offset, size, present);
// Check that shards were not corrupted by isParityCorrect():
for (var index = 0; index < totalShards; index++) {
Test.equal(
hashShard(shards[index]),
hashes[index],
'ReedSolomon',
'shard ' + (index + 1) + '/' + totalShards + ' after decoding'
);
}
// Check isParityCorrect() is working for valid shards:
Test.equal(
rs.isParityCorrect(shards, offset, size, parityTemp),
true,
'ReedSolomon',
'isParityCorrect'
);
};
var bindings = [ReedSolomon.bindingJS];
var bindings = [ReedSolomon.binding.javascript];
var bindingNames = ['Javascript'];
if (ReedSolomon.bindingNative) {
bindings.push(ReedSolomon.bindingNative);
if (ReedSolomon.binding.native) {
bindings.push(ReedSolomon.binding.native);
bindingNames.push('Native');
}
bindings.forEach(
function(binding) {
// Do many small tests:
var tests = 100;
while (tests--) fuzz(256, 1024, binding); // (maxShards, maxShardSize)
// Do some large tests:
var tests = 10;
while (tests--) fuzz(32, 1024 * 1024, binding); // (maxShards, maxShardSize)
}
);
console.log('Bindings Tested: ' + bindingNames.join(', '));
console.log('================');
console.log('ALL TESTS PASSED');
console.log('================');
var queue = new QueueStream();
queue.onData = function(binding, end) {
var queue = new QueueStream();
queue.onData = function(parameters, end) {
fuzz(binding, parameters, end);
};
queue.onEnd = function(error) {
if (error) return end(error);
// Fixed vector test:
Test.equal(
true,
true,
'ReedSolomon',
'fixed vector'
);
var dataShards = 5;
var parityShards = 5;
var rs = new ReedSolomon(dataShards, parityShards, binding);
var buffer = Buffer.concat([
Buffer.from([0, 1]),
Buffer.from([4, 5]),
Buffer.from([2, 3]),
Buffer.from([6, 7]),
Buffer.from([8, 9]),
Buffer.from([0, 0]),
Buffer.from([0, 0]),
Buffer.from([0, 0]),
Buffer.from([0, 0]),
Buffer.from([0, 0])
]);
var bufferOffset = 0;
var bufferSize = buffer.length;
var shardLength = 2;
var shardOffset = 0;
var shardSize = shardLength;
rs.encode(
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize,
function(error) {
if (error) return end(error);
function shard(index) {
var offset = index * 2;
return buffer.slice(offset, offset + 2);
}
Test.equal(shard(0), Buffer.from([0, 1]), 'ReedSolomon', 'shard 0');
Test.equal(shard(1), Buffer.from([4, 5]), 'ReedSolomon', 'shard 1');
Test.equal(shard(2), Buffer.from([2, 3]), 'ReedSolomon', 'shard 2');
Test.equal(shard(3), Buffer.from([6, 7]), 'ReedSolomon', 'shard 3');
Test.equal(shard(4), Buffer.from([8, 9]), 'ReedSolomon', 'shard 4');
Test.equal(shard(5), Buffer.from([12, 13]), 'ReedSolomon', 'shard 5');
Test.equal(shard(6), Buffer.from([10, 11]), 'ReedSolomon', 'shard 6');
Test.equal(shard(7), Buffer.from([14, 15]), 'ReedSolomon', 'shard 7');
Test.equal(shard(8), Buffer.from([90, 91]), 'ReedSolomon', 'shard 8');
Test.equal(shard(9), Buffer.from([94, 95]), 'ReedSolomon', 'shard 9');
Test.equal(
CheckParity(
dataShards,
parityShards,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize
),
true,
'ReedSolomon',
'fixed vector parity correct'
);
buffer[0] = 255;
Test.equal(
CheckParity(
dataShards,
parityShards,
buffer,
bufferOffset,
bufferSize,
shardLength,
shardOffset,
shardSize
),
false,
'ReedSolomon',
'fixed vector parity correct'
);
end();
}
);
};
// Do many small tests:
var tests = 1000;
while (tests--) queue.push({ maxShards: 31, maxShardLength: 32 });
// Do some large tests:
var tests = 100;
while (tests--) queue.push({ maxShards: 31, maxShardLength: 256 * 1024 });
queue.end();
};
queue.onEnd = function(error) {
if (error) throw error;
console.log('Bindings Tested: ' + bindingNames.join(', '));
console.log('================');
console.log('ALL TESTS PASSED');
console.log('================');
};
queue.push(bindings);
queue.end();
binding.cc

Sorry, the diff of this file is not supported yet

binding.gyp

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc