public inbox for devel@edk2.groups.io
 help / color / mirror / Atom feed
From: "Laszlo Ersek" <lersek@redhat.com>
To: edk2-devel-groups-io <devel@edk2.groups.io>
Cc: "Liming Gao" <liming.gao@intel.com>,
	"Marvin Häuser" <mhaeuser@outlook.de>,
	"Michael D Kinney" <michael.d.kinney@intel.com>,
	"Philippe Mathieu-Daudé" <philmd@redhat.com>,
	"Zhichao Gao" <zhichao.gao@intel.com>
Subject: [PATCH 2/3] MdePkg/BaseLib: rewrite Base64Decode()
Date: Tue,  2 Jul 2019 12:28:35 +0200	[thread overview]
Message-ID: <20190702102836.27589-3-lersek@redhat.com> (raw)
In-Reply-To: <20190702102836.27589-1-lersek@redhat.com>

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.

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.
+    //
+    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;
 }
 
 /**
-- 
2.19.1.3.g30247aa5d201



  parent reply	other threads:[~2019-07-02 10:29 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-07-02 10:28 [PATCH 0/3] MdePkg, OvmfPkg: rewrite Base64Decode(), clean up call site Laszlo Ersek
2019-07-02 10:28 ` [PATCH 1/3] MdePkg/BaseLib: re-specify Base64Decode(), and add temporary stub impl Laszlo Ersek
2019-07-16  8:38   ` Philippe Mathieu-Daudé
2019-07-16  9:41     ` Philippe Mathieu-Daudé
2019-07-16 14:14       ` Laszlo Ersek
2019-07-16 14:59         ` Philippe Mathieu-Daudé
2019-07-16 18:53           ` [edk2-devel] " Laszlo Ersek
2019-07-16 10:49   ` Laszlo Ersek
2019-07-16 14:56     ` Liming Gao
2019-07-16 17:15       ` Laszlo Ersek
2019-07-02 10:28 ` Laszlo Ersek [this message]
2019-07-12  2:31   ` [edk2-devel] [PATCH 2/3] MdePkg/BaseLib: rewrite Base64Decode() Gao, Zhichao
2019-07-12 19:31     ` Laszlo Ersek
2019-07-15 15:22       ` Liming Gao
2019-07-15 21:56         ` Laszlo Ersek
2019-07-16  1:18           ` Gao, Zhichao
2019-07-16 10:48             ` Laszlo Ersek
2019-07-15 18:44   ` mhaeuser
2019-07-16  0:45     ` Laszlo Ersek
2019-07-16 10:05   ` Philippe Mathieu-Daudé
2019-07-16 14:17     ` Laszlo Ersek
2019-07-02 10:28 ` [PATCH 3/3] OvmfPkg/EnrollDefaultKeys: clean up Base64Decode() retval handling Laszlo Ersek
2019-07-15 21:58   ` [edk2-devel] " Laszlo Ersek
2019-07-16  8:36     ` Philippe Mathieu-Daudé
2019-07-10  9:20 ` [edk2-devel] [PATCH 0/3] MdePkg, OvmfPkg: rewrite Base64Decode(), clean up call site Laszlo Ersek
2019-07-16 22:02 ` Laszlo Ersek

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-list from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190702102836.27589-3-lersek@redhat.com \
    --to=devel@edk2.groups.io \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox