String encoding utility methods and tests for Unicode, UTF-8, -16 and -32.

utils/string_encoding/Utf8_impl.dart

Index: utils/string_encoding/Utf8_impl.dart
diff --git a/utils/string_encoding/Utf8_impl.dart b/utils/string_encoding/Utf8_impl.dart
new file mode 100644
index 0000000000000000000000000000000000000000..9512ae85fdb61be1fe6d2f042f11214fde11261d
--- /dev/null
+++ b/utils/string_encoding/Utf8_impl.dart
@@ -0,0 +1,197 @@
+// Copyright (c) 2012, 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.
+
+final int _UTF8_ONE_BYTE_MAX = 0x7f;
+final int _UTF8_TWO_BYTE_MAX = 0x7ff;
+final int _UTF8_THREE_BYTE_MAX = 0xffff;
+
+final int _UTF8_LO_SIX_BIT_MASK = 0x3f;
+
+final int _UTF8_FIRST_BYTE_OF_TWO_BASE = 0xc0;
+final int _UTF8_FIRST_BYTE_OF_THREE_BASE = 0xe0;
+final int _UTF8_FIRST_BYTE_OF_FOUR_BASE = 0xf0;
+final int _UTF8_FIRST_BYTE_OF_FIVE_BASE = 0xf8;
+final int _UTF8_FIRST_BYTE_OF_SIX_BASE = 0xfc;
+
+final int _UTF8_FIRST_BYTE_OF_TWO_MASK = 0x1f;
+final int _UTF8_FIRST_BYTE_OF_THREE_MASK = 0xf;
+final int _UTF8_FIRST_BYTE_OF_FOUR_MASK = 0x7;
+
+final int _UTF8_FIRST_BYTE_BOUND_EXCL = 0xfe;
+final int _UTF8_SUBSEQUENT_BYTE_BASE = 0x80;
+
+final List<int> _UTF8_REPLACEMENT_CHARACTER = const <int>[0xef, 0xbf, 0xbd];
+
+/**
+ * Produce a sequence of UTF8 encoded bytes from the provided string.
+ */
+List<int> encodeAsUtf8(String str) =>
+  _codepointsToUtf8(stringToCodepoints(str));
+
+/**
+ * Produce a String from a sequence of UTF8 encoded bytes.
+ */
+String decodeFromUtf8(List<int> bytes) =>

[Søren Gjesse, 2012/02/01 11:25:25]

Should we perhaps have an optional offset and length field here. We do in a lot
of places where byte Lists are passed. In some cases you might like to decode
parts of a network buffer received.

[Søren Gjesse, 2012/02/01 11:25:25]

Should there be optional arguments for:

1. Specifying an alternative "replacement character"
2. Requesting an Exception instead of decoding to the "replacement character".

[dcarlson, 2012/02/01 22:18:46]

Done.

[dcarlson, 2012/02/01 22:18:46]

Done.

+    codepointsToString(_utf8ToCodepoints(bytes, 0, bytes.length));

[Søren Gjesse, 2012/02/01 11:25:25]

Consider having both _utf8ToCodepoints and _utf8ToString where _utf8ToString
fills characters directly into a StringBuffer and returns a string. That avoids
allocating the code points array.

[dcarlson, 2012/02/01 22:18:46]

I don't think this buys us much. The StringBuffer is a List (of strings, but we
are adding a character at a time, so no real win). If we can figure the length
ahead of time, we could allocate a ByteArray to perhaps reduce the # of objects
allocated at any one time.

+
+int _addToEncoding(int start, int bytes, int value, List<int> buffer) {
+  while(bytes > 0) {
+    buffer[start + bytes] = _UTF8_SUBSEQUENT_BYTE_BASE |
+        (value & _UTF8_LO_SIX_BIT_MASK);
+    value = value >> 6;
+    bytes--;
+  }
+  return value;
+}
+
+/**
+ * Encode code points as UTF8 code units.
+ */
+List<int> _codepointsToUtf8(List<int> codepoints,
+    [int start = 0, int length = null]) {
+  if (!(start >= 0)) {
+    throw new IllegalArgumentException("start");
+  }
+
+  if (!(length == null || length >= 0)) {
+    throw new IllegalArgumentException("length");
+  }
+
+  int end = length != null ?
+      Math.min(codepoints.length, start + length) :
+      codepoints.length;
+
+  int encodedLength = 0;
+  for (int i = start; i < end; i++) {
+    int value = codepoints[i];
+    if (value < 0 || value > UNICODE_VALID_RANGE_MAX) {
+      encodedLength += 3;
+    } else if (value <= _UTF8_ONE_BYTE_MAX) {
+      encodedLength++;
+    } else if (value <= _UTF8_TWO_BYTE_MAX) {
+      encodedLength += 2;
+    } else if (value <= _UTF8_THREE_BYTE_MAX) {
+      encodedLength += 3;
+    } else if (value <= UNICODE_VALID_RANGE_MAX) {
+      encodedLength += 4;
+    }
+  }
+
+  List<int> encoded = new List<int>(encodedLength);
+  int insertAt = 0;
+  for (int i = start; i < end; i++) {
+    int value = codepoints[i];
+    if (value < 0 || value > UNICODE_VALID_RANGE_MAX) {
+      encoded.setRange(insertAt, 3, [0xef, 0xbf, 0xbd]);
+      insertAt += 3;
+    } else if (value <= _UTF8_ONE_BYTE_MAX) {
+      encoded[insertAt] = value;
+      insertAt++;
+    } else if (value <= _UTF8_TWO_BYTE_MAX) {
+      encoded[insertAt] = _UTF8_FIRST_BYTE_OF_TWO_BASE | (
+          _UTF8_FIRST_BYTE_OF_TWO_MASK &
+          _addToEncoding(insertAt, 1, value, encoded));
+      insertAt += 2;
+    } else if (value <= _UTF8_THREE_BYTE_MAX) {
+      encoded[insertAt] = _UTF8_FIRST_BYTE_OF_THREE_BASE | (
+          _UTF8_FIRST_BYTE_OF_THREE_MASK &
+          _addToEncoding(insertAt, 2, value, encoded));
+      insertAt += 3;
+    } else if (value <= UNICODE_VALID_RANGE_MAX) {
+      encoded[insertAt] = _UTF8_FIRST_BYTE_OF_FOUR_BASE | (
+          _UTF8_FIRST_BYTE_OF_FOUR_MASK &
+          _addToEncoding(insertAt, 3, value, encoded));
+      insertAt += 4;
+    }
+  }
+  return encoded;
+}
+
+ // Because UTF-8 specifies byte order, we do not have to follow the pattern
+ // used by UTF-16 & -32 regarding byte order.
+List<int> _utf8ToCodepoints(List<int> utf8EncodedBytes,
+    [int start = 0, int length = null]) {

[Søren Gjesse, 2012/02/01 11:25:25]

I think corelib normally uses the name offset instead of start.

[dcarlson, 2012/02/01 22:18:46]

Done.

+  if (!(start >= 0)) {
+    throw new IllegalArgumentException("start");
+  }
+
+  if (!(length == null || length >= 0)) {
+    throw new IllegalArgumentException("length");
+  }
+
+  int end = length != null ?
+      Math.min(utf8EncodedBytes.length, start + length) :
+      utf8EncodedBytes.length;
+
+  List<int> codepointBuffer = <int>[];

[Søren Gjesse, 2012/02/01 11:25:25]

Have you thought about having an initial scan for calculating the number of
decoded codepoints first (like you calculate encodedLength above)?

[dcarlson, 2012/02/01 22:18:46]

Done.

+  int i = start;
+  while (i < end) {
+    int value = utf8EncodedBytes[i++];
+    if (value >= 0) {
+      if (value <= _UTF8_ONE_BYTE_MAX) {
+        codepointBuffer.add(value);
+      } else if (value < _UTF8_FIRST_BYTE_OF_TWO_BASE) {
+        codepointBuffer.add(UNICODE_REPLACEMENT_CHARACTER_CODEPOINT);
+        continue;
+      } else {
+        int additionalBytes = 0;
+        if (value < _UTF8_FIRST_BYTE_OF_THREE_BASE) {
+          value -= _UTF8_FIRST_BYTE_OF_TWO_BASE;
+          additionalBytes = 1;
+        } else if (value < _UTF8_FIRST_BYTE_OF_FOUR_BASE) {
+          value -= _UTF8_FIRST_BYTE_OF_THREE_BASE;
+          additionalBytes = 2;
+        } else if (value < _UTF8_FIRST_BYTE_OF_FIVE_BASE) {
+          value -= _UTF8_FIRST_BYTE_OF_FOUR_BASE;
+          additionalBytes = 3;

[Søren Gjesse, 2012/02/01 11:25:25]

Do we ever want to decode more than 4 bytes. There are no defined codepoints
that require more AFAIK.

[dcarlson, 2012/02/01 22:18:46]

No valid codepoints, but the spec defines decodings out to 6 bytes -- I wanted
to keep these because although will treat it as an invalid character, we don't
want to get out of sync.

+        } else if (value < _UTF8_FIRST_BYTE_OF_SIX_BASE) {
+          value -= _UTF8_FIRST_BYTE_OF_FIVE_BASE;
+          additionalBytes = 4;
+        } else if (value < _UTF8_FIRST_BYTE_BOUND_EXCL) {
+          value -= _UTF8_FIRST_BYTE_OF_SIX_BASE;
+          additionalBytes = 5;
+        } else {
+          codepointBuffer.add(UNICODE_REPLACEMENT_CHARACTER_CODEPOINT);
+          continue;
+        }
+        int j = 0;
+        while (j < additionalBytes && i < end) {
+          int nextValue = utf8EncodedBytes[i++];
+          if (nextValue > _UTF8_ONE_BYTE_MAX &&
+              nextValue < _UTF8_FIRST_BYTE_OF_TWO_BASE) {
+            value = (value << 6) | (nextValue & _UTF8_LO_SIX_BIT_MASK);
+          } else {
+            // if sequence-starting code unit, reposition cursor to start here
+            if (nextValue >= _UTF8_FIRST_BYTE_OF_TWO_BASE) {
+              i--;
+            }
+            break;
+          }
+          j++;
+        }
+        if (j == additionalBytes && (
+            value < UNICODE_UTF16_RESERVED_LO || 
+            value > UNICODE_UTF16_RESERVED_HI)) {
+          if (additionalBytes == 1 && value > _UTF8_ONE_BYTE_MAX) {
+            codepointBuffer.add(value);
+          } else if (additionalBytes == 2 && value > _UTF8_TWO_BYTE_MAX) {
+            codepointBuffer.add(value);
+          } else if (additionalBytes == 3 && value > _UTF8_THREE_BYTE_MAX &&
+              value <= UNICODE_VALID_RANGE_MAX) {
+            codepointBuffer.add(value);
+          } else {
+            codepointBuffer.add(UNICODE_REPLACEMENT_CHARACTER_CODEPOINT);
+          }
+        } else {
+          codepointBuffer.add(UNICODE_REPLACEMENT_CHARACTER_CODEPOINT);
+          continue;
+        }
+      }
+    } else {
+      codepointBuffer.add(UNICODE_REPLACEMENT_CHARACTER_CODEPOINT);
+      continue;
+    }
+  }
+  return codepointBuffer;
+}