Add support for decoding URL-safe encoded base64.

sdk/lib/convert/base64.dart

 // Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart.convert;
 
 /**
  * An instance of [Base64Codec].
  *
  * This instance provides a convenient access to
@@ skipping 292 matching lines @@
 // ------------------------------------------------------------------------
 // Decoder
 // ------------------------------------------------------------------------
 
 class Base64Decoder extends Converter<String, List<int>> {
   const Base64Decoder();
 
   List<int> convert(String input) {
     if (input.isEmpty) return new Uint8List(0);
     int length = input.length;
-    if (length % 4 != 0) {
-      throw new FormatException("Invalid length, must be multiple of four",
-                                input, length);
-    }
     var decoder = new _Base64Decoder();
     Uint8List buffer = decoder.decode(input, 0, input.length);
     decoder.close(input, input.length);
     return buffer;
   }
 
   StringConversionSink startChunkedConversion(Sink<List<int>> sink) {
     return new _Base64DecoderSink(sink);
   }
 }
@@ skipping 16 matching lines @@
 
   // Shorthands to make the table more readable.
   static const int __ = _invalid;
   static const int _p = _padding;
 
   /**
    * Mapping from ASCII characters to their index in the base64 alphabet.
    *
    * Uses [_invalid] for invalid indices and [_padding] for the padding
    * character.
+   *
+   * Accepts the "URL-safe" alphabet as well (`-` and `_` are the
+   * 62nd and 63rd alphabet characters), and considers `%` a padding
+   * character which mush be followed by `3D`, the percent-escape
+   * for `=`.
    */
   static final List<int> _inverseAlphabet = new Int8List.fromList([
     __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __,
     __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __,
-    __, __, __, __, __, __, __, __, __, __, __, 62, __, __, __, 63,
+    __, __, __, __, __, _p, __, __, __, __, __, 62, __, 62, __, 63,
     52, 53, 54, 55, 56, 57, 58, 59, 60, 61, __, __, __, _p, __, __,
     __,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
-    15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, __, __, __, __, __,
+    15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, __, __, __, __, 63,
     __, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
     41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, __, __, __, __, __,
   ]);
 
+  // Character constants.
+  static const int _char_percent = 0x25;  // '%'.
+  static const int _char_3       = 0x33;  // '3'.
+  static const int _char_d       = 0x64;  // 'd'.
+
   /**
    * Maintains the intermediate state of a partly-decoded input.
    *
    * BASE-64 is decoded in chunks of four characters. If a chunk does not
    * contain a full block, the decoded bits (six per character) of the
    * available characters are stored in [_state] until the next call to
    * [_decode] or [_close].
    *
    * If no padding has been seen, the value is
    *   `numberOfCharactersSeen | (decodedBits << 2)`
@@ skipping 116 matching lines @@
         count = (count + 1) & 3;
         if (count == 0) {
           assert(outIndex + 3 <= output.length);
           output[outIndex++] = (bits >> 16) & eightBitMask;
           output[outIndex++] = (bits >> 8) & eightBitMask;
           output[outIndex++] = bits & eightBitMask;
           bits = 0;
         }
         continue;
       } else if (code == _padding && count > 1) {
+        if (charOr < 0 || charOr > asciiMax) break;
         if (count == 3) {
           if ((bits & 0x03) != 0) {
             throw new FormatException(
                 "Invalid encoding before padding", input, i);
           }
           output[outIndex++] = bits >> 10;
           output[outIndex++] = bits >> 2;
         } else {
           if ((bits & 0x0F) != 0) {
             throw new FormatException(
                 "Invalid encoding before padding", input, i);
           }
           output[outIndex++] = bits >> 4;
         }
-        int expectedPadding = 3 - count;
+        // Expected padding is the number of expected padding characters,
+        // where `=` counts as three and `%3D` counts as one per character.
+        //
+        // Expect either zero or one padding depending on count (2 or 3),
+        // plus two more characters if the code was `%` (a partial padding).
+        int expectedPadding = (3 - count) * 3;
+        if (char == _char_percent) expectedPadding += 2;
         state = _encodePaddingState(expectedPadding);
         return _checkPadding(input, i + 1, end, state);
       }
       throw new FormatException("Invalid character", input, i);
     }
     if (charOr >= 0 && charOr <= asciiMax) {
       return _encodeCharacterState(count, bits);
     }
     // There is an invalid (non-ASCII) character in the input.
     int i;
     for (i = start; i < end; i++) {
       int char = input.codeUnitAt(i);
       if (char < 0 || char > asciiMax) break;
     }
     throw new FormatException("Invalid character", input, i);
   }
 
   /**
    * Allocates a buffer with room for the decoding of a substring of [input].
    *
    * Includes room for the characters in [state], and handles padding correctly.
    */
   static Uint8List _allocateBuffer(String input, int start, int end,
                                    int state) {
     assert(state >= 0);
-    int padding = 0;
-    int length = _stateCount(state) + (end - start);
-    if (end > start && input.codeUnitAt(end - 1) == _paddingChar) {
-      padding++;
-      if (end - 1 > start && input.codeUnitAt(end - 2) == _paddingChar) {
-        padding++;
-      }
-    }
+    int paddingStart = _trimPaddingChars(input, start, end);
+    int length = _stateCount(state) + (paddingStart - start);
     // Three bytes per full four bytes in the input.
     int bufferLength = (length >> 2) * 3;
-    // If padding was seen, then remove the padding if it was counter, or
-    // add the last partial chunk it it wasn't counted.
+    // If padding was seen, then this is the last chunk, and the final partial
+    // chunk should be decoded too.
     int remainderLength = length & 3;
-    if (remainderLength == 0) {
-      bufferLength -= padding;
-    } else if (padding != 0 && remainderLength - padding > 1) {
-      bufferLength += remainderLength - 1 - padding;
+    if (remainderLength != 0 && paddingStart < end) {
+      bufferLength += remainderLength - 1;
     }
     if (bufferLength > 0) return new Uint8List(bufferLength);
-    // If the input plus state is less than four characters, no buffer
-    // is needed.
+    // If the input plus state is less than four characters, and it's not
+    // at the end of input, no buffer is needed.
     return null;
   }
 
   /**
+   * Returns the position of the start of padding at the end of the input.
+   *
+   * This is used to ensure that the decoding buffer has the exact size
+   * it needs when input is valid, and at least enough bytes reach the error

[nweiz, 2015/10/22 20:14:30]

"bytes reach" -> "bytes to reach"

[Lasse Reichstein Nielsen, 2015/10/23 11:03:35]

Done.

+   * when input is invalid.
+   *
+   * Never count more than two padding sequences since any more than that
+   * will raise an error anyway, and we only care about being precise for
+   * successful conversions.
+   */
+  static int _trimPaddingChars(String input, int start, int end) {
+    // This may count '%=' as two paddings. That's ok, it will err later,
+    // but the buffer will be large enough to reach the error.
+    int padding = 0;
+    int index = end;
+    int newEnd = end;
+    while (index > start && padding < 2) {
+      index--;
+      int char = input.codeUnitAt(index);
+      if (char == _paddingChar) {
+        padding++;
+        newEnd = index;
+        continue;
+      }
+      if ((char | 0x20) == _char_d) {
+        if (index == start) break;
+        index--;
+        char = input.codeUnitAt(index);
+      }
+      if (char == _char_3) {
+        if (index == start) break;
+        index--;
+        char = input.codeUnitAt(index);
+      }
+      if (char == _char_percent) {
+        padding++;
+        newEnd = index;
+        continue;
+      }
+      break;
+    }
+    return newEnd;
+  }
+
+  /**
    * Check that the remainder of the string is valid padding.
    *
    * That means zero or one padding character (depending on [_state])

[nweiz, 2015/10/22 20:14:30]

Aren't two padding characters also valid?

[Lasse Reichstein Nielsen, 2015/10/23 11:03:35]

Yes, but we only get here after seeing the first one.
This text should be updated, because now we also get here after seeing the first
"%", so there is 1 2/3 padding left.
I've rewritten it completely.

    * and nothing else.
    */
   static int _checkPadding(String input, int start, int end, int state) {
     assert(_hasSeenPadding(state));
     if (start == end) return state;
     int expectedPadding = _statePadding(state);
-    if (expectedPadding > 0) {
-      int firstChar = input.codeUnitAt(start);
-      if (firstChar != _paddingChar) {
-        throw new FormatException("Missing padding character", input, start);
+    assert(expectedPadding >= 0);
+    assert(expectedPadding < 6);
+    while (expectedPadding > 0) {
+      int char = input.codeUnitAt(start);
+      if (expectedPadding == 3) {
+        if (char == _paddingChar) {
+          expectedPadding -= 3;
+          start++;
+          break;
+        }
+        if (char == _char_percent) {
+          expectedPadding--;
+          start++;
+          if (start == end) break;
+          char = input.codeUnitAt(start);
+        } else {
+          break;
+        }
       }
-      state = _encodePaddingState(0);
+      // Partial padding means we have seen part of a "%3D" escape.
+      int expectedPartialPadding = expectedPadding;
+      if (expectedPartialPadding > 3) expectedPartialPadding -= 3;
+      if (expectedPartialPadding == 2) {
+        // Expects '3'
+        if (char != _char_3) break;
+        start++;
+        expectedPadding--;
+        if (start == end) break;
+        char = input.codeUnitAt(start);
+      }
+      // Expects 'D' or 'd'.
+      if ((char | 0x20) != _char_d) break;
       start++;
+      expectedPadding--;
+      if (start == end) break;
     }
     if (start != end) {
-      throw new FormatException("Invalid character after padding",
+      throw new FormatException("Invalid padding character",
                                 input, start);
     }
-    return state;
+    return _encodePaddingState(expectedPadding);
   }
 }
 
 class _Base64DecoderSink extends StringConversionSinkBase {
   /** Output sink */
   final ChunkedConversionSink<List<int>> _sink;
   final _Base64Decoder _decoder = new _Base64Decoder();
 
   _Base64DecoderSink(this._sink);
 
@@ skipping 12 matching lines @@
     end = RangeError.checkValidRange(start, end, string.length);
     if (start == end) return;
     Uint8List buffer = _decoder.decode(string, start, end);
     if (buffer != null) _sink.add(buffer);
     if (isLast) {
       _decoder.close(string, end);
       _sink.close();
     }
   }
 }