Re: [PATCH 2/3] MdePkg/BaseLib: rewrite Base64Decode()

["Philippe Mathieu-Daudé" <philmd@redhat.com>]

Hi Laszlo,

On 7/2/19 12:28 PM, Laszlo Ersek wrote:
> Rewrite Base64Decode() from scratch, due to reasons listed in the second
> reference below.
> 
> Implement Base64Decode() according to the specification added in the
> previous patch. The decoder scans the input buffer once, it has no inner
> loop(s), and it spills each output byte as soon as the output byte is
> complete.

Sorry it took me so long, I was reluctant to review this at first,
because reimplementing a piece of code to fix a bug often introduce new
bugs. However your implementation is very clean to follow (well
described) and certainly safer.

> Cc: Liming Gao <liming.gao@intel.com>
> Cc: Marvin Häuser <mhaeuser@outlook.de>
> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Cc: Zhichao Gao <zhichao.gao@intel.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=1891
> Ref: http://mid.mail-archive.com/c495bd0b-ea4d-7206-8a4f-a7149760d19a@redhat.com
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> ---
>  MdePkg/Library/BaseLib/String.c | 249 +++++++++++++++++++-
>  1 file changed, 247 insertions(+), 2 deletions(-)
> 
> diff --git a/MdePkg/Library/BaseLib/String.c b/MdePkg/Library/BaseLib/String.c
> index f8397035c32a..6198ccbc9672 100644
> --- a/MdePkg/Library/BaseLib/String.c
> +++ b/MdePkg/Library/BaseLib/String.c
> @@ -1973,8 +1973,253 @@ Base64Decode (
>    IN OUT UINTN       *DestinationSize
>    )
>  {
> -  ASSERT (FALSE);
> -  return RETURN_INVALID_PARAMETER;
> +  BOOLEAN PaddingMode;
> +  UINTN   SixBitGroupsConsumed;
> +  UINT32  Accumulator;
> +  UINTN   OriginalDestinationSize;
> +  UINTN   SourceIndex;
> +
> +  if (DestinationSize == NULL) {
> +    return RETURN_INVALID_PARAMETER;
> +  }
> +
> +  //
> +  // Check Source array validity.
> +  //
> +  if (Source == NULL) {
> +    if (SourceSize > 0) {
> +      //
> +      // At least one CHAR8 element at NULL Source.
> +      //
> +      return RETURN_INVALID_PARAMETER;
> +    }
> +  } else if (SourceSize > MAX_ADDRESS - (UINTN)Source) {
> +    //
> +    // Non-NULL Source, but it wraps around.

You might want to add a comment in the commit description from your
reply to Marvin regarding keeping MAX_ADDRESS, mostly "The original code
included similar MAX_ADDRESS checks".

No more comments :)
Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>

> +    //
> +    return RETURN_INVALID_PARAMETER;
> +  }
> +
> +  //
> +  // Check Destination array validity.
> +  //
> +  if (Destination == NULL) {
> +    if (*DestinationSize > 0) {
> +      //
> +      // At least one UINT8 element at NULL Destination.
> +      //
> +      return RETURN_INVALID_PARAMETER;
> +    }
> +  } else if (*DestinationSize > MAX_ADDRESS - (UINTN)Destination) {
> +    //
> +    // Non-NULL Destination, but it wraps around.
> +    //
> +    return RETURN_INVALID_PARAMETER;
> +  }
> +
> +  //
> +  // Check for overlap.
> +  //
> +  if (Source != NULL && Destination != NULL) {
> +    //
> +    // Both arrays have been provided, and we know from earlier that each array
> +    // is valid in itself.
> +    //
> +    if ((UINTN)Source + SourceSize <= (UINTN)Destination) {
> +      //
> +      // Source array precedes Destination array, OK.
> +      //
> +    } else if ((UINTN)Destination + *DestinationSize <= (UINTN)Source) {
> +      //
> +      // Destination array precedes Source array, OK.
> +      //
> +    } else {
> +      //
> +      // Overlap.
> +      //
> +      return RETURN_INVALID_PARAMETER;
> +    }
> +  }
> +
> +  //
> +  // Decoding loop setup.
> +  //
> +  PaddingMode             = FALSE;
> +  SixBitGroupsConsumed    = 0;
> +  Accumulator             = 0;
> +  OriginalDestinationSize = *DestinationSize;
> +  *DestinationSize        = 0;
> +
> +  //
> +  // Decoding loop.
> +  //
> +  for (SourceIndex = 0; SourceIndex < SourceSize; SourceIndex++) {
> +    CHAR8  SourceChar;
> +    UINT32 Base64Value;
> +    UINT8  DestinationOctet;
> +
> +    SourceChar = Source[SourceIndex];
> +
> +    //
> +    // Whitespace is ignored at all positions (regardless of padding mode).
> +    //
> +    if (SourceChar == '\t' || SourceChar == '\n' || SourceChar == '\v' ||
> +        SourceChar == '\f' || SourceChar == '\r' || SourceChar == ' ') {
> +      continue;
> +    }
> +
> +    //
> +    // If we're in padding mode, accept another padding character, as long as
> +    // that padding character completes the quantum. This completes case (2)
> +    // from RFC4648, Chapter 4. "Base 64 Encoding":
> +    //
> +    // (2) The final quantum of encoding input is exactly 8 bits; here, the
> +    //     final unit of encoded output will be two characters followed by two
> +    //     "=" padding characters.
> +    //
> +    if (PaddingMode) {
> +      if (SourceChar == '=' && SixBitGroupsConsumed == 3) {
> +        SixBitGroupsConsumed = 0;
> +        continue;
> +      }
> +      return RETURN_INVALID_PARAMETER;
> +    }
> +
> +    //
> +    // When not in padding mode, decode Base64Value based on RFC4648, "Table 1:
> +    // The Base 64 Alphabet".
> +    //
> +    if ('A' <= SourceChar && SourceChar <= 'Z') {
> +      Base64Value = SourceChar - 'A';
> +    } else if ('a' <= SourceChar && SourceChar <= 'z') {
> +      Base64Value = 26 + (SourceChar - 'a');
> +    } else if ('0' <= SourceChar && SourceChar <= '9') {
> +      Base64Value = 52 + (SourceChar - '0');
> +    } else if (SourceChar == '+') {
> +      Base64Value = 62;
> +    } else if (SourceChar == '/') {
> +      Base64Value = 63;
> +    } else if (SourceChar == '=') {
> +      //
> +      // Enter padding mode.
> +      //
> +      PaddingMode = TRUE;
> +
> +      if (SixBitGroupsConsumed == 2) {
> +        //
> +        // If we have consumed two 6-bit groups from the current quantum before
> +        // encountering the first padding character, then this is case (2) from
> +        // RFC4648, Chapter 4. "Base 64 Encoding". Bump SixBitGroupsConsumed,
> +        // and we'll enforce another padding character.
> +        //
> +        SixBitGroupsConsumed = 3;
> +      } else if (SixBitGroupsConsumed == 3) {
> +        //
> +        // If we have consumed three 6-bit groups from the current quantum
> +        // before encountering the first padding character, then this is case
> +        // (3) from RFC4648, Chapter 4. "Base 64 Encoding". The quantum is now
> +        // complete.
> +        //
> +        SixBitGroupsConsumed = 0;
> +      } else {
> +        //
> +        // Padding characters are not allowed at the first two positions of a
> +        // quantum.
> +        //
> +        return RETURN_INVALID_PARAMETER;
> +      }
> +
> +      //
> +      // Wherever in a quantum we enter padding mode, we enforce the padding
> +      // bits pending in the accumulator -- from the last 6-bit group just
> +      // preceding the padding character -- to be zero. Refer to RFC4648,
> +      // Chapter 3.5. "Canonical Encoding".
> +      //
> +      if (Accumulator != 0) {
> +        return RETURN_INVALID_PARAMETER;
> +      }
> +
> +      //
> +      // Advance to the next source character.
> +      //
> +      continue;
> +    } else {
> +      //
> +      // Other characters outside of the encoding alphabet are rejected.
> +      //
> +      return RETURN_INVALID_PARAMETER;
> +    }
> +
> +    //
> +    // Feed the bits of the current 6-bit group of the quantum to the
> +    // accumulator.
> +    //
> +    Accumulator = (Accumulator << 6) | Base64Value;
> +    SixBitGroupsConsumed++;
> +    switch (SixBitGroupsConsumed) {
> +    case 1:
> +      //
> +      // No octet to spill after consuming the first 6-bit group of the
> +      // quantum; advance to the next source character.
> +      //
> +      continue;
> +    case 2:
> +      //
> +      // 12 bits accumulated (6 pending + 6 new); prepare for spilling an
> +      // octet. 4 bits remain pending.
> +      //
> +      DestinationOctet = (UINT8)(Accumulator >> 4);
> +      Accumulator &= 0xF;
> +      break;
> +    case 3:
> +      //
> +      // 10 bits accumulated (4 pending + 6 new); prepare for spilling an
> +      // octet. 2 bits remain pending.
> +      //
> +      DestinationOctet = (UINT8)(Accumulator >> 2);
> +      Accumulator &= 0x3;
> +      break;
> +    default:
> +      ASSERT (SixBitGroupsConsumed == 4);
> +      //
> +      // 8 bits accumulated (2 pending + 6 new); prepare for spilling an octet.
> +      // The quantum is complete, 0 bits remain pending.
> +      //
> +      DestinationOctet = (UINT8)Accumulator;
> +      Accumulator = 0;
> +      SixBitGroupsConsumed = 0;
> +      break;
> +    }
> +
> +    //
> +    // Store the decoded octet if there's room left. Increment
> +    // (*DestinationSize) unconditionally.
> +    //
> +    if (*DestinationSize < OriginalDestinationSize) {
> +      ASSERT (Destination != NULL);
> +      Destination[*DestinationSize] = DestinationOctet;
> +    }
> +    (*DestinationSize)++;
> +
> +    //
> +    // Advance to the next source character.
> +    //
> +  }
> +
> +  //
> +  // If Source terminates mid-quantum, then Source is invalid.
> +  //
> +  if (SixBitGroupsConsumed != 0) {
> +    return RETURN_INVALID_PARAMETER;
> +  }
> +
> +  //
> +  // Done.
> +  //
> +  if (*DestinationSize <= OriginalDestinationSize) {
> +    return RETURN_SUCCESS;
> +  }
> +  return RETURN_BUFFER_TOO_SMALL;
>  }
>  
>  /**
>