{

for (unsigned i = 0; i < SiameseDecoderStats_Count; ++i) {

Counts[i] = 0;

}

{

RecoveryPackets.TheAllocator = &TheAllocator;

RecoveryPackets.CheckedRegion = &CheckedRegion;

Window.TheAllocator = &TheAllocator;

Window.Stats = &Stats;

Window.CheckedRegion = &CheckedRegion;

Window.RecoveryPackets = &RecoveryPackets;

Window.RecoveryMatrix = &RecoveryMatrix;

RecoveryMatrix.TheAllocator = &TheAllocator;

RecoveryMatrix.Window = &Window;

RecoveryMatrix.CheckedRegion = &CheckedRegion;

CheckedRegion.RecoveryMatrix = &RecoveryMatrix;

{

// Note: Keep this in sync with Encoder::Get

if (Window.EmergencyDisabled) {

return Siamese_Disabled;

}

// Note: This also works when Count == 0

const unsigned element = Window.ColumnToElement(packetOut.PacketNum);

if (Window.InvalidElement(element))

{

// Set default return value

packetOut.Data = nullptr;

packetOut.DataBytes = 0;

return Siamese_NeedMoreData;

}

// Return the packet data

OriginalPacket* original = Window.GetWindowElement(element);

if (original->Buffer.Bytes <= 0)

{

packetOut.Data = nullptr;

packetOut.DataBytes = 0;

return Siamese_NeedMoreData;

}

const unsigned headerBytes = original->HeaderBytes;

SIAMESE_DEBUG_ASSERT(headerBytes > 0 && original->Buffer.Bytes > headerBytes);

const unsigned length = original->Buffer.Bytes - headerBytes;

#ifdef SIAMESE_DEBUG

// Check: Deserialize length from the front

unsigned lengthCheck;

int headerBytesCheck = DeserializeHeader_PacketLength(

original->Buffer.Data,

original->Buffer.Bytes,

lengthCheck);

if (lengthCheck != length || (int)headerBytes != headerBytesCheck ||

headerBytesCheck < 1 || lengthCheck == 0 ||

lengthCheck + headerBytesCheck != original->Buffer.Bytes)

{

SIAMESE_DEBUG_BREAK(); // Invalid input

Window.EmergencyDisabled = true;

return Siamese_Disabled;

}

#endif // SIAMESE_DEBUG

packetOut.Data = original->Buffer.Data + headerBytes;

packetOut.DataBytes = length;

return Siamese_Success;

uint8_t* buffer,

unsigned byteLimit,

unsigned& usedBytesOut)

{

if (Window.EmergencyDisabled) {

return Siamese_Disabled;

}

SIAMESE_DEBUG_ASSERT(byteLimit >= SIAMESE_ACK_MIN_BYTES);

std::ostringstream* pDebugMsg = nullptr;

// If we have no data yet:

const unsigned windowCount = Window.Count;

if (windowCount == 0)

{

// This should only happen before we receive any data at all.

// After we receive some data we keep a window of data around to decode FEC packets

SIAMESE_DEBUG_ASSERT(Window.ColumnStart == 0);

usedBytesOut = 0;

return Siamese_NeedMoreData;

}

const uint8_t* bufferStart = buffer;

// Calculate next column we expect to receive

const unsigned nextElementExpected = Window.NextExpectedElement;

SIAMESE_DEBUG_ASSERT(nextElementExpected <= windowCount);

const unsigned nextColumnExpected = Window.ElementToColumn(nextElementExpected);

unsigned headerBytes = SerializeHeader_PacketNum(nextColumnExpected, buffer);

buffer += headerBytes, byteLimit -= headerBytes;

// If there is no missing data:

if (Window.InvalidElement(nextElementExpected))

{

// Write used bytes

usedBytesOut = (unsigned)(uintptr_t)(buffer - bufferStart);

Stats.Counts[SiameseDecoderStats_AckCount]++;

Stats.Counts[SiameseDecoderStats_AckBytes] += usedBytesOut;

return Siamese_Success;

}

SIAMESE_DEBUG_ASSERT(Window.GetWindowElement(nextElementExpected)->Buffer.Bytes == 0);

// Start searching for the next set bit at the next after the next expected element

unsigned rangeOffset = nextElementExpected;

if (Logger.ShouldLog(logger::Level::Debug))

{

delete pDebugMsg;

pDebugMsg = new std::ostringstream();

*pDebugMsg << "Building ack from nextExpectedColumn=" << nextColumnExpected << " : NACKs = {";

}

// While there is room for another maximum-length loss range:

while (byteLimit >= kMaxLossRangeFieldBytes)

{

const unsigned rangeStart = Window.FindNextLostElement(rangeOffset);

if (rangeStart >= windowCount)

{

SIAMESE_DEBUG_ASSERT(rangeStart == windowCount);

if (pDebugMsg)

*pDebugMsg << " next:" << AddColumns(Window.ColumnStart, rangeStart);

// Noticed this can happen somehow

if (windowCount >= rangeOffset)

{

// Take range start relative to the range offset

const unsigned relativeStart = windowCount - rangeOffset;

// Serialize this NACK loss range into the buffer

const unsigned encodedBytes = SerializeHeader_NACKLossRange(relativeStart, 0, buffer);

buffer += encodedBytes;

}

break;

}

SIAMESE_DEBUG_ASSERT(rangeStart >= rangeOffset);

unsigned rangeEnd = Window.FindNextGotElement(rangeStart + 1);

SIAMESE_DEBUG_ASSERT(rangeEnd > rangeStart);

SIAMESE_DEBUG_ASSERT(rangeEnd <= windowCount);

unsigned lossCountM1 = rangeEnd - rangeStart - 1; // Loss count minus 1

if (pDebugMsg)

{

if (lossCountM1 > 0) {

*pDebugMsg << " " << AddColumns(Window.ColumnStart, rangeStart)

<< "-" << Window.ElementToColumn(rangeEnd - 1);

}

else {

*pDebugMsg << " " << AddColumns(Window.ColumnStart, rangeStart);

}

}

// Take range start relative to the range offset

SIAMESE_DEBUG_ASSERT(rangeStart >= rangeOffset);

const unsigned relativeStart = rangeStart - rangeOffset;

// Serialize this NACK loss range into the buffer

const unsigned encodedBytes = SerializeHeader_NACKLossRange(relativeStart, lossCountM1, buffer);

// Range end is one beyond the end of the loss region.

// The next loss cannot be before one after the range end, since we

// either found a received packet id there, or we hit end of range.

// This is also where we should start searching for losses again

rangeOffset = rangeEnd + 1;

// Advance buffer write pointer

buffer += encodedBytes;

byteLimit -= encodedBytes;

}

// Note that the loss range list may have been truncated due to the buffer space constraint

if (pDebugMsg)

{

*pDebugMsg << " }";

Logger.Debug(pDebugMsg->str());

}

// Write used bytes

usedBytesOut = (unsigned)(uintptr_t)(buffer - bufferStart);

Stats.Counts[SiameseDecoderStats_AckCount]++;

Stats.Counts[SiameseDecoderStats_AckBytes] += usedBytesOut;

return Siamese_Success;

{

if (Window.EmergencyDisabled) {

return Siamese_Disabled;

}

// Deserialize the recovery metadata from the front of the packet

RecoveryMetadata metadata;

int footerSize = DeserializeFooter_RecoveryMetadata(packet.Data, packet.DataBytes, metadata);

if (footerSize < 0)

{

Window.EmergencyDisabled = true;

Logger.Error("AddRecovery: Corrupt recovery metadata");

SIAMESE_DEBUG_BREAK(); // Should never happen

return Siamese_Disabled;

}

Stats.Counts[SiameseDecoderStats_RecoveryCount]++;

Stats.Counts[SiameseDecoderStats_RecoveryBytes] += packet.DataBytes;

// Check if recovery packet was received out of order

bool outOfOrder = IsColumnDeltaNegative(metadata.ColumnStart + metadata.SumCount - LatestColumn);

if (!outOfOrder) {

// Update the latest received column

LatestColumn = (metadata.ColumnStart + metadata.SumCount) % kColumnPeriod;

}

#if 0 /* Siamese correctly handles data received out of order */

if (outOfOrder)

{

Logger.Warning("Ignoring recovery packet received out of order");

Stats.Counts[SiameseDecoderStats_DupedRecoveryCount]++;

return Siamese_Success; // This packet cannot be used for recovery

}

#endif

unsigned elementStart, elementEnd;

// Check if we need this recovery packet:

if (Window.Count <= 0)

{

if (outOfOrder)

{

Logger.Warning("Recovery packet cannot be used because it was received by an empty window out of order");

Stats.Counts[SiameseDecoderStats_DupedRecoveryCount]++;

return Siamese_Success; // This packet cannot be used for recovery

}

Logger.Info("Got first recovery packet: ColumnStart=", metadata.ColumnStart, " SumCount=", metadata.SumCount, " LDPC_Count=", metadata.LDPCCount, " Row=", metadata.Row);

Window.ColumnStart = metadata.ColumnStart;

if (!Window.GrowWindow(metadata.SumCount))

{

Window.EmergencyDisabled = true;

Logger.Error("AddRecovery.GrowWindow: OOM");

return Siamese_Disabled;

}

elementEnd = metadata.SumCount;

elementStart = elementEnd - metadata.LDPCCount;

// This should only happen at the start if we get recovery first before data

SIAMESE_DEBUG_ASSERT(Window.NextExpectedElement == 0);

}

else

{

Logger.Info("Got recovery packet: ColumnStart=", metadata.ColumnStart, " SumCount=", metadata.SumCount, " LDPC_Count=", metadata.LDPCCount, " Row=", metadata.Row);

elementEnd = Window.ColumnToElement(metadata.ColumnStart + metadata.SumCount);

// Ignore data from too long ago

if (IsColumnDeltaNegative(elementEnd))

{

Logger.Info("Packet cannot be used because it ends before the window starts");

Stats.Counts[SiameseDecoderStats_DupedRecoveryCount]++;

return Siamese_Success;

}

// If we clipped the LDPC region already out of the window:

if (elementEnd < metadata.LDPCCount)

{

Logger.Warning("Recovery packet cannot be used because we clipped its LDPC region already: Received too far out of order?");

Stats.Counts[SiameseDecoderStats_DupedRecoveryCount]++;

return Siamese_Success; // This packet cannot be used for recovery

}

elementStart = elementEnd - metadata.LDPCCount;

// Ignore data we already have

if (elementEnd <= Window.NextExpectedElement)

{

if (outOfOrder)

{

Logger.Warning("Recovery packet does not contain new data and is out of order, so ignoring it");

Stats.Counts[SiameseDecoderStats_DupedRecoveryCount]++;

return Siamese_Success; // This packet cannot be used for recovery

}

Logger.Debug("Ignoring unnecessary recovery packet for data we received successfully");

if (elementStart >= kDecoderRemoveThreshold)

{

const unsigned recoveryBytes = packet.DataBytes - footerSize;

// Update the last received recovery metadata

RecoveryPackets.LastRecoveryMetadata = metadata;

RecoveryPackets.LastRecoveryBytes = recoveryBytes;

Window.RemoveElements();

}

Stats.Counts[SiameseDecoderStats_DupedRecoveryCount]++;

return Siamese_Success;

}

// Ignore sums that include data we have removed already

#ifdef SIAMESE_ENABLE_CAUCHY

// If it is a Siamese sum row:

if (metadata.SumCount > SIAMESE_CAUCHY_THRESHOLD)

#endif

{

// If there is no running sum or it does not match the new one:

if (Window.SumColumnCount == 0 || Window.SumColumnStart != metadata.ColumnStart)

{

// Then we need to have all the data in the sum at hand or it is useless.

const unsigned elementSumStart = Window.ColumnToElement(metadata.ColumnStart);

if (Window.InvalidElement(elementSumStart))

{

Logger.Info("Recovery packet cannot be used because we clipped its Sum region already : " \

"Received too far out of order: Window.SumColumnStart = ",

Window.SumColumnStart, ", Window.SumColumnCount = ", Window.SumColumnCount,

", metadata.ColumnStart = ", metadata.ColumnStart);

Stats.Counts[SiameseDecoderStats_DupedRecoveryCount]++;

return Siamese_Success;

}

}

}

// Grow the original packet window to cover all the packets this one protects

if (!Window.GrowWindow(elementEnd))

{

Window.EmergencyDisabled = true;

Logger.Error("AddRecovery.GrowWindow2: OOM");

return Siamese_Disabled;

}

}

// If this is a single (duplicate) packet:

if (metadata.SumCount == 1)

{

if (!AddSingleRecovery(packet, metadata, footerSize))

{

Window.EmergencyDisabled = true;

Logger.Error("AddRecovery.AddSingleRecovery failed");

return Siamese_Disabled;

}

return Siamese_Success;

}

// Allocate a packet object

RecoveryPacket* recovery = (RecoveryPacket*)TheAllocator.Construct<RecoveryPacket>();

if (!recovery)

{

Window.EmergencyDisabled = true;

Logger.Error("AddRecovery.Construct OOM");

return Siamese_Disabled;

}

SIAMESE_DEBUG_ASSERT((unsigned)footerSize < packet.DataBytes);

const unsigned recoveryBytes = packet.DataBytes - footerSize;

SIAMESE_DEBUG_ASSERT(recoveryBytes > 0);

if (!recovery->Buffer.Initialize(&TheAllocator, recoveryBytes))

{

TheAllocator.Destruct(recovery);

Window.EmergencyDisabled = true;

Logger.Error("AddRecovery.Initialize OOM");

return Siamese_Disabled;

}

// Fill in the packet object

memcpy(recovery->Buffer.Data, packet.Data, recoveryBytes);

recovery->Metadata = metadata;

recovery->ElementStart = elementStart;

recovery->ElementEnd = elementEnd;

// Insert it into the sorted packet list

RecoveryPackets.Insert(recovery, outOfOrder);

// Remove elements from the front if possible

if (elementStart >= kDecoderRemoveThreshold) {

Window.RemoveElements();

}

return Siamese_Success;

{

const unsigned element = Window.ColumnToElement(metadata.ColumnStart);

if (Window.InvalidElement(element)) {

SIAMESE_DEBUG_BREAK(); // Should never happen

return false;

}

// Note: In this case the length is already prefixed to the data

SIAMESE_DEBUG_ASSERT(metadata.LDPCCount == 1 && metadata.Row == 0);

OriginalPacket* windowOriginal = Window.GetWindowElement(element);

// Ignore duplicate data

if (windowOriginal->Buffer.Bytes != 0) {

return true;

}

// Check: Deserialize length from the front

SIAMESE_DEBUG_ASSERT(packet.DataBytes > (unsigned)footerSize);

const unsigned lengthPlusDataBytes = packet.DataBytes - footerSize;

unsigned lengthCheck;

int headerBytes = DeserializeHeader_PacketLength(packet.Data, lengthPlusDataBytes, lengthCheck);

if (headerBytes < 1 || lengthCheck == 0 ||

lengthCheck + headerBytes != lengthPlusDataBytes)

{

SIAMESE_DEBUG_BREAK(); // Invalid input

return false;

}

SiameseOriginalPacket original;

SIAMESE_DEBUG_ASSERT((int)packet.DataBytes > footerSize + headerBytes);

original.DataBytes = packet.DataBytes - footerSize - headerBytes;

original.Data = packet.Data + headerBytes;

original.PacketNum = metadata.ColumnStart;

unsigned newHeaderBytes = windowOriginal->Initialize(&TheAllocator, original);

SIAMESE_DEBUG_ASSERT(newHeaderBytes == (unsigned)headerBytes);

if (0 == newHeaderBytes) {

SIAMESE_DEBUG_BREAK(); // Invalid input

return false;

}

SIAMESE_DEBUG_ASSERT(windowOriginal->Buffer.Bytes > 1);

if (!Window.HasRecoveredPackets)

{

Window.HasRecoveredPackets = true;

Window.RecoveredPackets.Clear();

}

original.Data = windowOriginal->Buffer.Data + newHeaderBytes;

SIAMESE_DEBUG_ASSERT(original.DataBytes == windowOriginal->Buffer.Bytes - headerBytes);

if (!Window.RecoveredPackets.Append(original)) {

SIAMESE_DEBUG_BREAK(); // OOM

return false;

}

if (!Window.RecoveredColumns.Append(metadata.ColumnStart)) {

SIAMESE_DEBUG_BREAK(); // OOM

return false;

}

// If the added element is somewhere inside the previously checked region:

if (element >= CheckedRegion.ElementStart &&

element < CheckedRegion.NextCheckStart)

{

CheckedRegion.Reset();

}

// If this was the next expected element:

if (Window.MarkGotColumn(metadata.ColumnStart))

{

SIAMESE_DEBUG_ASSERT(element == Window.NextExpectedElement);

// Iterate the next expected element beyond the recovery region

Window.IterateNextExpectedElement(element + 1);

Logger.Debug("AddSingleRecovery: Deleting recovery packets before element ", Window.NextExpectedElement, " column = ", (Window.NextExpectedElement + Window.ColumnStart));

RecoveryPackets.DeletePacketsBefore(Window.NextExpectedElement);

if (CheckedRegion.NextCheckStart >= kDecoderRemoveThreshold) {

Window.RemoveElements();

}

}

return true;

{

if (Window.EmergencyDisabled) {

return false;

}

RecoveryPacket* recovery;

unsigned nextCheckStart, recoveryCount, lostCount;

// If we just started checking again:

if (!CheckedRegion.LastRecovery)

{

recovery = RecoveryPackets.Head;

if (!recovery) {

return false; // No recovery data

}

CheckedRegion.FirstRecovery = recovery;

CheckedRegion.ElementStart = recovery->ElementStart;

#ifdef SIAMESE_DEBUG

const unsigned lostPacketsBeforeLDPC = Window.RangeLostPackets(0, recovery->ElementStart);

SIAMESE_DEBUG_ASSERT(0 == lostPacketsBeforeLDPC);

#endif

recoveryCount = 1;

nextCheckStart = recovery->ElementEnd;

lostCount = Window.RangeLostPackets(recovery->ElementStart, nextCheckStart);

CheckedRegion.SolveFailed = false;

// Keep track of how many losses this recovery packet is facing

recovery->LostCount = lostCount;

}

else

{

recoveryCount = CheckedRegion.RecoveryCount;

lostCount = CheckedRegion.LostCount;

if (recoveryCount >= lostCount && !CheckedRegion.SolveFailed)

{

// If maximum loss recovery count is exceeded:

if (lostCount > kMaximumLossRecoveryCount) {

return false; // Limit was hit

}

return true; // It is already possible

}

recovery = CheckedRegion.LastRecovery;

nextCheckStart = CheckedRegion.NextCheckStart;

}

SIAMESE_DEBUG_ASSERT(lostCount > 0);

// While we do not have enough recovery data:

while ((recoveryCount < lostCount || CheckedRegion.SolveFailed) &&

(recovery->Next != nullptr))

{

recovery = recovery->Next;

++recoveryCount;

// Accumulate losses within the range of this recovery packet, skipping

// losses we've already accumulated into the checked region

unsigned elementEnd = recovery->ElementEnd;

if (elementEnd < nextCheckStart) {

elementEnd = nextCheckStart; // This can happen when interleaved with Cauchy packets

}

Logger.Debug("RecoveryPossible? Searching between ", nextCheckStart, " and ", elementEnd);

lostCount += Window.RangeLostPackets(nextCheckStart, elementEnd);

SIAMESE_DEBUG_ASSERT(lostCount > 0);

nextCheckStart = elementEnd;

// Keep track of how many losses this recovery packet is facing

recovery->LostCount = lostCount;

CheckedRegion.SolveFailed = false;

}

// Remember state for the next time around

CheckedRegion.LastRecovery = recovery;

CheckedRegion.RecoveryCount = recoveryCount;

CheckedRegion.LostCount = lostCount;

CheckedRegion.NextCheckStart = nextCheckStart;

Logger.Debug("RecoveryPossible? LostCount=", CheckedRegion.LostCount, " RecoveryCount=", CheckedRegion.RecoveryCount);

// If maximum loss recovery count is exceeded:

if (lostCount > kMaximumLossRecoveryCount) {

return false; // Limit was hit

}

return recoveryCount >= lostCount && !CheckedRegion.SolveFailed;

{

if (Window.EmergencyDisabled) {

return Siamese_Disabled;

}

// If there are already recovered packets to report:

if (Window.HasRecoveredPackets)

{

Window.HasRecoveredPackets = false;

SIAMESE_DEBUG_ASSERT(Window.RecoveredPackets.GetSize() != 0);

if (packetsPtrOut)

{

*packetsPtrOut = Window.RecoveredPackets.GetPtr(0);

*countOut = Window.RecoveredPackets.GetSize();

}

return Siamese_Success;

}

// Default return on failure

if (packetsPtrOut)

{

*packetsPtrOut = nullptr;

*countOut = 0;

}

/*

// Advance the checked region to the first possible solution

if (!CheckRecoveryPossible()) {

return Siamese_NeedMoreData;

}

RecoveryPacket* recovery = CheckedRegion.LastRecovery;

unsigned nextCheckStart = CheckedRegion.NextCheckStart;

unsigned recoveryCount = CheckedRegion.RecoveryCount;

unsigned lostCount = CheckedRegion.LostCount;

SIAMESE_DEBUG_ASSERT(recovery != nullptr && nextCheckStart > CheckedRegion.ElementStart);

SIAMESE_DEBUG_ASSERT(lostCount > 0 && lostCount <= recoveryCount);

for (;;)

{

if (recoveryCount >= lostCount)

{

SiameseResult result = DecodeCheckedRegion();

// Pass error or success up; continue on decode failure

if (result == Siamese_Success)

{

if (packetsPtrOut)

{

*packetsPtrOut = Window.RecoveredPackets.GetPtr(0);

*countOut = Window.RecoveredPackets.GetSize();

}

return Siamese_Success;

}

if (result != Siamese_NeedMoreData) {

return result;

}

}

if (recovery->Next == nullptr) {

break;

}

recovery = recovery->Next;

++recoveryCount;

// Accumulate losses within the range of this recovery packet, skipping

// losses we've already accumulated into the checked region

unsigned elementEnd = recovery->ElementEnd;

if (elementEnd < nextCheckStart) {

elementEnd = nextCheckStart; // This can happen when interleaved with Cauchy packets

}

lostCount += Window.RangeLostPackets(nextCheckStart, elementEnd);

// Keep track of how many lost packets this recovery packet is facing

recovery->LostCount = lostCount;

nextCheckStart = elementEnd;

}

// Remember state for the next time around

CheckedRegion.LastRecovery = recovery;

CheckedRegion.NextCheckStart = nextCheckStart;

CheckedRegion.RecoveryCount = recoveryCount;

CheckedRegion.LostCount = lostCount;

return Siamese_NeedMoreData;

{

Logger.Debug("Attempting decode...");

#ifdef SIAMESE_DECODER_DUMP_SOLVER_PERF

bool skipLog = CheckedRegion.LostCount <= 1;

if (!skipLog)

Logger.Debug("For ", CheckedRegion.LostCount, " losses:");

uint64_t t0 = GetTimeUsec();

#endif

// Generate updated recovery matrix

if (!RecoveryMatrix.GenerateMatrix())

{

Window.EmergencyDisabled = true;

Logger.Error("DecodeCheckedRegion.GenerateMatrix failed");

return Siamese_Disabled;

}

#ifdef SIAMESE_DECODER_DUMP_SOLVER_PERF

uint64_t t1 = GetTimeUsec();

#endif

// Attempt to solve the linear system

if (!RecoveryMatrix.GaussianElimination())

{

CheckedRegion.SolveFailed = true;

Stats.Counts[SiameseDecoderStats_SolveFailCount]++;

return Siamese_NeedMoreData;

}

#ifdef SIAMESE_DECODER_DUMP_SOLVER_PERF

uint64_t t2 = GetTimeUsec();

#endif

if (!EliminateOriginalData())

{

Window.EmergencyDisabled = true;

Logger.Error("DecodeCheckedRegion.EliminateOriginalData failed");

return Siamese_Disabled;

}

#ifdef SIAMESE_DECODER_DUMP_SOLVER_PERF

uint64_t t3 = GetTimeUsec();

#endif

if (!MultiplyLowerTriangle())

{

Window.EmergencyDisabled = true;

Logger.Error("DecodeCheckedRegion.MultiplyLowerTriangle failed");

return Siamese_Disabled;

}

#ifdef SIAMESE_DECODER_DUMP_SOLVER_PERF

uint64_t t4 = GetTimeUsec();

#endif

SiameseResult solveResult = BackSubstitution();

#ifdef SIAMESE_DECODER_DUMP_SOLVER_PERF

uint64_t t5 = GetTimeUsec();

#endif

CheckedRegion.Reset();

#ifdef SIAMESE_DECODER_DUMP_SOLVER_PERF

uint64_t t6 = GetTimeUsec();

if (!skipLog)

{

Logger.Info("RecoveryMatrix.GenerateMatrix: ", (t1 - t0), " usec");

Logger.Info("RecoveryMatrix.GaussianElimination: ", (t2 - t1), " usec");

Logger.Info("EliminateOriginalData: ", (t3 - t2), " usec");

Logger.Info("MultiplyLowerTriangle: ", (t4 - t3), " usec");

Logger.Info("BackSubstitution: ", (t5 - t4), " usec");

Logger.Info("Cleanup: ", (t6 - t5), " usec");

}

#endif

return solveResult;

{

SIAMESE_DEBUG_ASSERT(CheckedRegion.LostCount == RecoveryMatrix.Columns.GetSize());

std::ostringstream* pDebugMsg = nullptr;

// Note: This is done because the Siamese sums need to be accumulated from

// left to right in the same order that the encoder generated them.

// This step tends to be slow because there is a lot of data that was

// successfully received that we need to eliminate from the recovery sums

const unsigned rows = CheckedRegion.RecoveryCount;

SIAMESE_DEBUG_ASSERT(CheckedRegion.RecoveryCount == RecoveryMatrix.Rows.GetSize());

// Eliminate data in sorted row order regardless of pivot order:

for (unsigned matrixRowIndex = 0; matrixRowIndex < rows; ++matrixRowIndex)

{

if (!RecoveryMatrix.Rows.GetRef(matrixRowIndex).UsedForSolution) {

continue;

}

RecoveryPacket* recovery = RecoveryMatrix.Rows.GetRef(matrixRowIndex).Recovery;

const RecoveryMetadata metadata = recovery->Metadata;

const unsigned elementStart = recovery->ElementStart;

const unsigned elementEnd = recovery->ElementEnd;

GrowingAlignedDataBuffer& recoveryBuffer = recovery->Buffer;

SIAMESE_DEBUG_ASSERT(recoveryBuffer.Data && recoveryBuffer.Bytes > 0);

#ifdef SIAMESE_ENABLE_CAUCHY

// If it is a Cauchy or parity row:

if (metadata.SumCount <= SIAMESE_CAUCHY_THRESHOLD)

{

// If this is a parity row:

if (metadata.Row == 0)

{

// Fill columns from left for new rows:

for (unsigned j = elementStart; j < elementEnd; ++j)

{

OriginalPacket* original = Window.GetWindowElement(j);

unsigned addBytes = original->Buffer.Bytes;

if (addBytes > 0)

{

if (addBytes > recoveryBuffer.Bytes) {

SIAMESE_DEBUG_BREAK(); // Should never happen

addBytes = recoveryBuffer.Bytes;

}

gf256_add_mem(recoveryBuffer.Data, original->Buffer.Data, addBytes);

}

}

}

else // This is a Cauchy row:

{

// Fill columns from left for new rows:

for (unsigned j = elementStart; j < elementEnd; ++j)

{

OriginalPacket* original = Window.GetWindowElement(j);

unsigned addBytes = original->Buffer.Bytes;

if (addBytes > 0)

{

const uint8_t y = CauchyElement(metadata.Row - 1, original->Column % kCauchyMaxColumns);

if (addBytes > recoveryBuffer.Bytes) {

SIAMESE_DEBUG_BREAK(); // Should never happen

addBytes = recoveryBuffer.Bytes;

}

gf256_muladd_mem(recoveryBuffer.Data, y, original->Buffer.Data, addBytes);

}

}

}

continue;

}

#endif // SIAMESE_ENABLE_CAUCHY

// Zero the product sum

const unsigned recoveryBytes = recoveryBuffer.Bytes;

if (!ProductSum.Initialize(&TheAllocator, recoveryBytes)) {

return false;

}

memset(ProductSum.Data, 0, recoveryBytes);

Logger.Debug("Starting sums for row=", recovery->Metadata.Row, " start=", recovery->Metadata.ColumnStart, " count=", recovery->Metadata.SumCount);

// Convert column start to window element.

// If some of the summed elements have fallen out of the window,

// then start it at the first element in the window (0).

unsigned sumElementStart = Window.ColumnToElement(recovery->Metadata.ColumnStart);

/*

if (metadata.ColumnStart != Window.SumColumnStart ||

metadata.SumCount < Window.SumColumnCount)

{

// If we have to restart the sums but the data is not available:

if (Window.InvalidElement(sumElementStart)) {

// This should never happen. The code that decides when to

// remove data from the window should have kept this data.

SIAMESE_DEBUG_BREAK();

return false;

}

Window.ResetSums(sumElementStart);

Window.SumColumnStart = metadata.ColumnStart;

}

else

{

if (Window.InvalidElement(sumElementStart)) {

sumElementStart = 0;

}

// Prepare any lane sums that have not accumulated data yet to

// receive data, since we are about to start accumulaing into

// some of these running sums.

if (!Window.StartSums(sumElementStart, recoveryBytes)) {

return false;

}

}

Window.SumColumnCount = metadata.SumCount;

// Eliminate dense recovery data outside of matrix:

for (unsigned laneIndex = 0; laneIndex < kColumnLaneCount; ++laneIndex)

{

const unsigned opcode = GetRowOpcode(laneIndex, metadata.Row);

// For summations into the RecoveryPacket buffer:

unsigned mask = 1;

for (unsigned sumIndex = 0; sumIndex < kColumnSumCount; ++sumIndex)

{

if (opcode & mask)

{

const GrowingAlignedDataBuffer* sum = Window.GetSum(laneIndex, sumIndex, elementEnd);

SIAMESE_DEBUG_ASSERT(elementEnd + kColumnLaneCount >= Window.Lanes[laneIndex].Sums[sumIndex].ElementEnd);

unsigned addBytes = sum->Bytes;

if (addBytes > 0)

{

if (addBytes > recoveryBytes) {

addBytes = recoveryBytes;

}

gf256_add_mem(recoveryBuffer.Data, sum->Data, addBytes);

}

}

mask <<= 1;

}

// For summations into the ProductWorkspace buffer:

for (unsigned sumIndex = 0; sumIndex < kColumnSumCount; ++sumIndex)

{

if (opcode & mask)

{

const GrowingAlignedDataBuffer* sum = Window.GetSum(laneIndex, sumIndex, elementEnd);

SIAMESE_DEBUG_ASSERT(elementEnd + kColumnLaneCount >= Window.Lanes[laneIndex].Sums[sumIndex].ElementEnd);

unsigned addBytes = sum->Bytes;

if (addBytes > 0)

{

if (addBytes > recoveryBytes)

addBytes = recoveryBytes;

gf256_add_mem(ProductSum.Data, sum->Data, addBytes);

}

}

mask <<= 1;

}

}

// Eliminate light recovery data outside of matrix:

PCGRandom prng;

prng.Seed(metadata.Row, metadata.LDPCCount);

SIAMESE_DEBUG_ASSERT(metadata.SumCount >= metadata.LDPCCount);

if (Logger.ShouldLog(logger::Level::Debug))