| /* |
| * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. |
| * |
| * Use of this source code is governed by a BSD-style license |
| * that can be found in the LICENSE file in the root of the source |
| * tree. An additional intellectual property rights grant can be found |
| * in the file PATENTS. All contributing project authors may |
| * be found in the AUTHORS file in the root of the source tree. |
| */ |
| |
| #include "forward_error_correction_internal.h" |
| #include "fec_private_tables.h" |
| |
| #include <cassert> |
| #include <cstring> |
| |
| namespace { |
| |
| // Allow for different modes of protection for packets in UEP case. |
| enum ProtectionMode |
| { |
| kModeNoOverlap, |
| kModeOverlap, |
| kModeBiasFirstPacket, |
| }; |
| |
| /** |
| * Fits an input mask (subMask) to an output mask. |
| * The mask is a matrix where the rows are the FEC packets, |
| * and the columns are the source packets the FEC is applied to. |
| * Each row of the mask is represented by a number of mask bytes. |
| * |
| * \param[in] numMaskBytes The number of mask bytes of output mask. |
| * \param[in] numSubMaskBytes The number of mask bytes of input mask. |
| * \param[in] numRows The number of rows of the input mask. |
| * \param[in] subMask A pointer to hold the input mask, of size |
| * [0, numRows * numSubMaskBytes] |
| * \param[out] packetMask A pointer to hold the output mask, of size |
| * [0, x * numMaskBytes], where x >= numRows. |
| */ |
| void FitSubMask(WebRtc_UWord16 numMaskBytes, |
| WebRtc_UWord16 numSubMaskBytes, |
| WebRtc_UWord16 numRows, |
| const WebRtc_UWord8* subMask, |
| WebRtc_UWord8* packetMask) |
| { |
| if (numMaskBytes == numSubMaskBytes) |
| { |
| memcpy(packetMask,subMask, |
| numRows * numSubMaskBytes); |
| } |
| else |
| { |
| for (WebRtc_UWord32 i = 0; i < numRows; i++) |
| { |
| WebRtc_UWord32 pktMaskIdx = i * numMaskBytes; |
| WebRtc_UWord32 pktMaskIdx2 = i * numSubMaskBytes; |
| for (WebRtc_UWord32 j = 0; j < numSubMaskBytes; j++) |
| { |
| packetMask[pktMaskIdx] = subMask[pktMaskIdx2]; |
| pktMaskIdx++; |
| pktMaskIdx2++; |
| } |
| } |
| } |
| } |
| |
| /** |
| * Shifts a mask by number of columns (bits), and fits it to an output mask. |
| * The mask is a matrix where the rows are the FEC packets, |
| * and the columns are the source packets the FEC is applied to. |
| * Each row of the mask is represented by a number of mask bytes. |
| * |
| * \param[in] numMaskBytes The number of mask bytes of output mask. |
| * \param[in] numSubMaskBytes The number of mask bytes of input mask. |
| * \param[in] numColumnShift The number columns to be shifted, and |
| * the starting row for the output mask. |
| * \param[in] endRow The ending row for the output mask. |
| * \param[in] subMask A pointer to hold the input mask, of size |
| * [0, (endRowFEC - startRowFec) * numSubMaskBytes] |
| * \param[out] packetMask A pointer to hold the output mask, of size |
| * [0, x * numMaskBytes], where x >= endRowFEC. |
| */ |
| // TODO (marpan): This function is doing three things at the same time: |
| // shift within a byte, byte shift and resizing. |
| // Split up into subroutines. |
| void ShiftFitSubMask(WebRtc_UWord16 numMaskBytes, |
| WebRtc_UWord16 resMaskBytes, |
| WebRtc_UWord16 numColumnShift, |
| WebRtc_UWord16 endRow, |
| const WebRtc_UWord8* subMask, |
| WebRtc_UWord8* packetMask) |
| { |
| |
| // Number of bit shifts within a byte |
| const WebRtc_UWord8 numBitShifts = (numColumnShift % 8); |
| const WebRtc_UWord8 numByteShifts = numColumnShift >> 3; |
| |
| // Modify new mask with sub-mask21. |
| |
| // Loop over the remaining FEC packets. |
| for (WebRtc_UWord32 i = numColumnShift; i < endRow; i++) |
| { |
| // Byte index of new mask, for row i and column resMaskBytes, |
| // offset by the number of bytes shifts |
| WebRtc_UWord32 pktMaskIdx = i * numMaskBytes + resMaskBytes - 1 |
| + numByteShifts; |
| // Byte index of subMask, for row i and column resMaskBytes |
| WebRtc_UWord32 pktMaskIdx2 = |
| (i - numColumnShift) * resMaskBytes + resMaskBytes - 1; |
| |
| WebRtc_UWord8 shiftRightCurrByte = 0; |
| WebRtc_UWord8 shiftLeftPrevByte = 0; |
| WebRtc_UWord8 combNewByte = 0; |
| |
| // Handle case of numMaskBytes > resMaskBytes: |
| // For a given row, copy the rightmost "numBitShifts" bits |
| // of the last byte of subMask into output mask. |
| if (numMaskBytes > resMaskBytes) |
| { |
| shiftLeftPrevByte = |
| (subMask[pktMaskIdx2] << (8 - numBitShifts)); |
| packetMask[pktMaskIdx + 1] = shiftLeftPrevByte; |
| } |
| |
| // For each row i (FEC packet), shift the bit-mask of the subMask. |
| // Each row of the mask contains "resMaskBytes" of bytes. |
| // We start from the last byte of the subMask and move to first one. |
| for (WebRtc_Word32 j = resMaskBytes - 1; j > 0; j--) |
| { |
| // Shift current byte of sub21 to the right by "numBitShifts". |
| shiftRightCurrByte = |
| subMask[pktMaskIdx2] >> numBitShifts; |
| |
| // Fill in shifted bits with bits from the previous (left) byte: |
| // First shift the previous byte to the left by "8-numBitShifts". |
| shiftLeftPrevByte = |
| (subMask[pktMaskIdx2 - 1] << (8 - numBitShifts)); |
| |
| // Then combine both shifted bytes into new mask byte. |
| combNewByte = shiftRightCurrByte | shiftLeftPrevByte; |
| |
| // Assign to new mask. |
| packetMask[pktMaskIdx] = combNewByte; |
| pktMaskIdx--; |
| pktMaskIdx2--; |
| } |
| // For the first byte in the row (j=0 case). |
| shiftRightCurrByte = subMask[pktMaskIdx2] >> numBitShifts; |
| packetMask[pktMaskIdx] = shiftRightCurrByte; |
| |
| } |
| } |
| |
| } //namespace |
| |
| namespace webrtc { |
| namespace internal { |
| |
| // Remaining protection after important (first partition) packet protection |
| void RemainingPacketProtection(WebRtc_UWord16 numMediaPackets, |
| WebRtc_UWord16 numFecRemaining, |
| WebRtc_UWord16 numFecForImpPackets, |
| WebRtc_UWord16 numMaskBytes, |
| ProtectionMode mode, |
| WebRtc_UWord8* packetMask) |
| { |
| if (mode == kModeNoOverlap) |
| { |
| // subMask21 |
| |
| const WebRtc_UWord8 lBit = |
| (numMediaPackets - numFecForImpPackets) > 16 ? 1 : 0; |
| |
| const WebRtc_UWord16 resMaskBytes = |
| (lBit == 1)? kMaskSizeLBitSet : kMaskSizeLBitClear; |
| |
| const WebRtc_UWord8* packetMaskSub21 = |
| packetMaskTbl[numMediaPackets - numFecForImpPackets - 1] |
| [numFecRemaining - 1]; |
| |
| ShiftFitSubMask(numMaskBytes, resMaskBytes, numFecForImpPackets, |
| (numFecForImpPackets + numFecRemaining), |
| packetMaskSub21, packetMask); |
| |
| } |
| else if (mode == kModeOverlap || mode == kModeBiasFirstPacket) |
| { |
| // subMask22 |
| |
| const WebRtc_UWord8* packetMaskSub22 = |
| packetMaskTbl[numMediaPackets - 1][numFecRemaining - 1]; |
| |
| FitSubMask(numMaskBytes, numMaskBytes, numFecRemaining, packetMaskSub22, |
| &packetMask[numFecForImpPackets * numMaskBytes]); |
| |
| if (mode == kModeBiasFirstPacket) |
| { |
| for (WebRtc_UWord32 i = 0; i < numFecRemaining; i++) |
| { |
| WebRtc_UWord32 pktMaskIdx = i * numMaskBytes; |
| packetMask[pktMaskIdx] = packetMask[pktMaskIdx] | (1 << 7); |
| } |
| } |
| } |
| else |
| { |
| assert(false); |
| } |
| |
| } |
| |
| // Protection for important (first partition) packets |
| void ImportantPacketProtection(WebRtc_UWord16 numFecForImpPackets, |
| WebRtc_UWord16 numImpPackets, |
| WebRtc_UWord16 numMaskBytes, |
| WebRtc_UWord8* packetMask) |
| { |
| const WebRtc_UWord8 lBit = numImpPackets > 16 ? 1 : 0; |
| const WebRtc_UWord16 numImpMaskBytes = |
| (lBit == 1)? kMaskSizeLBitSet : kMaskSizeLBitClear; |
| |
| |
| // Get subMask1 from table |
| const WebRtc_UWord8* packetMaskSub1 = |
| packetMaskTbl[numImpPackets - 1][numFecForImpPackets - 1]; |
| |
| FitSubMask(numMaskBytes, numImpMaskBytes, |
| numFecForImpPackets, packetMaskSub1, packetMask); |
| |
| } |
| |
| // This function sets the protection allocation: i.e., how many FEC packets |
| // to use for numImp (1st partition) packets, given the: number of media |
| // packets, number of FEC packets, and number of 1st partition packets. |
| WebRtc_UWord32 SetProtectionAllocation(const WebRtc_UWord16 numMediaPackets, |
| const WebRtc_UWord16 numFecPackets, |
| const WebRtc_UWord16 numImpPackets) |
| { |
| |
| // TODO (marpan): test different cases for protection allocation: |
| |
| // Use at most (allocPar * numFecPackets) for important packets. |
| float allocPar = 0.5; |
| WebRtc_UWord16 maxNumFecForImp = static_cast<WebRtc_UWord16> |
| (allocPar * numFecPackets); |
| |
| WebRtc_UWord16 numFecForImpPackets = (numImpPackets < maxNumFecForImp) ? |
| numImpPackets : maxNumFecForImp; |
| |
| // Fall back to equal protection in this case |
| if (numFecPackets == 1 && (numMediaPackets > 2 * numImpPackets)) |
| { |
| numFecForImpPackets = 0; |
| } |
| |
| return numFecForImpPackets; |
| } |
| |
| // Modification for UEP: reuse the off-line tables for the packet masks. |
| // Note: these masks were designed for equal packet protection case, |
| // assuming random packet loss. |
| |
| // Current version has 3 modes (options) to build UEP mask from existing ones. |
| // Various other combinations may be added in future versions. |
| // Longer-term, we may add another set of tables specifically for UEP cases. |
| // TODO (marpan): also consider modification of masks for bursty loss cases. |
| |
| // Mask is characterized as (#packets_to_protect, #fec_for_protection). |
| // Protection factor defined as: (#fec_for_protection / #packets_to_protect). |
| |
| // Let k=numMediaPackets, n=total#packets, (n-k)=numFecPackets, m=numImpPackets. |
| |
| // For ProtectionMode 0 and 1: |
| // one mask (subMask1) is used for 1st partition packets, |
| // the other mask (subMask21/22, for 0/1) is for the remaining FEC packets. |
| |
| // In both mode 0 and 1, the packets of 1st partition (numImpPackets) are |
| // treated equally important, and are afforded more protection than the |
| // residual partition packets. |
| |
| // For numImpPackets: |
| // subMask1 = (m, t): protection = t/(m), where t=F(k,n-k,m). |
| // t=F(k,n-k,m) is the number of packets used to protect first partition in |
| // subMask1. This is determined from the function SetProtectionAllocation(). |
| |
| // For the left-over protection: |
| // Mode 0: subMask21 = (k-m,n-k-t): protection = (n-k-t)/(k-m) |
| // mode 0 has no protection overlap between the two partitions. |
| // For mode 0, we would typically set t = min(m, n-k). |
| |
| |
| // Mode 1: subMask22 = (k, n-k-t), with protection (n-k-t)/(k) |
| // mode 1 has protection overlap between the two partitions (preferred). |
| |
| // For ProtectionMode 2: |
| // This gives 1st packet of list (which is 1st packet of 1st partition) more |
| // protection. In mode 2, the equal protection mask (which is obtained from |
| // mode 1 for t=0) is modified (more "1s" added in 1st column of packet mask) |
| // to bias higher protection for the 1st source packet. |
| |
| // Protection Mode 2 may be extended for a sort of sliding protection |
| // (i.e., vary the number/density of "1s" across columns) across packets. |
| |
| void UnequalProtectionMask(const WebRtc_UWord16 numMediaPackets, |
| const WebRtc_UWord16 numFecPackets, |
| const WebRtc_UWord16 numImpPackets, |
| const WebRtc_UWord16 numMaskBytes, |
| WebRtc_UWord8* packetMask) |
| { |
| |
| // Set Protection type and allocation |
| // TODO (marpan): test/update for best mode and some combinations thereof. |
| |
| ProtectionMode mode = kModeOverlap; |
| WebRtc_UWord16 numFecForImpPackets = 0; |
| |
| if (mode != kModeBiasFirstPacket) |
| { |
| numFecForImpPackets = SetProtectionAllocation(numMediaPackets, |
| numFecPackets, |
| numImpPackets); |
| } |
| |
| WebRtc_UWord16 numFecRemaining = numFecPackets - numFecForImpPackets; |
| // Done with setting protection type and allocation |
| |
| // |
| // Generate subMask1 |
| // |
| if (numFecForImpPackets > 0) |
| { |
| ImportantPacketProtection(numFecForImpPackets, numImpPackets, |
| numMaskBytes, packetMask); |
| } |
| |
| // |
| // Generate subMask2 |
| // |
| if (numFecRemaining > 0) |
| { |
| RemainingPacketProtection(numMediaPackets, numFecRemaining, |
| numFecForImpPackets, numMaskBytes, |
| mode, packetMask); |
| } |
| |
| } |
| |
| void GeneratePacketMasks(int numMediaPackets, |
| int numFecPackets, |
| int numImpPackets, |
| bool useUnequalProtection, |
| WebRtc_UWord8* packetMask) |
| { |
| assert(numMediaPackets <= static_cast<int>(sizeof(packetMaskTbl) / |
| sizeof(*packetMaskTbl))); |
| assert(numMediaPackets > 0); |
| assert(numFecPackets <= numMediaPackets && numFecPackets > 0); |
| assert(numImpPackets <= numMediaPackets && numImpPackets >= 0); |
| |
| WebRtc_UWord8 lBit = numMediaPackets > 16 ? 1 : 0; |
| const WebRtc_UWord16 numMaskBytes = |
| (lBit == 1)? kMaskSizeLBitSet : kMaskSizeLBitClear; |
| |
| // Equal-protection for these cases |
| if (!useUnequalProtection || numImpPackets == 0) |
| { |
| // Retrieve corresponding mask table directly:for equal-protection case. |
| // Mask = (k,n-k), with protection factor = (n-k)/k, |
| // where k = numMediaPackets, n=total#packets, (n-k)=numFecPackets. |
| memcpy(packetMask, packetMaskTbl[numMediaPackets - 1][numFecPackets - 1], |
| numFecPackets * numMaskBytes); |
| } |
| else //UEP case |
| { |
| UnequalProtectionMask(numMediaPackets, numFecPackets, numImpPackets, |
| numMaskBytes, packetMask); |
| |
| } // End of UEP modification |
| |
| } //End of GetPacketMasks |
| |
| } // namespace internal |
| } // namespace webrtc |
