Add a hexadecimal codec.

lib/src/hex/decoder.dart

Index: lib/src/hex/decoder.dart
diff --git a/lib/src/hex/decoder.dart b/lib/src/hex/decoder.dart
new file mode 100644
index 0000000000000000000000000000000000000000..b12fdd09bbbbc6de3237c74e5878439450603c01
--- /dev/null
+++ b/lib/src/hex/decoder.dart
@@ -0,0 +1,164 @@
+// 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.
+
+library convert.hex.decoder;
+
+import 'dart:convert';
+import 'dart:typed_data';
+
+import 'package:charcode/ascii.dart';
+
+/// The canonical instance of [HexDecoder].
+const hexDecoder = const HexDecoder._();
+
+/// A converter that decodes hexadecimal strings into byte arrays.
+///
+/// Because two hexadecimal digits correspond to a single byte, this will throw
+/// a [FormatException] if given an odd-length string. It will also throw a
+/// [FormatException] if given a string containing non-hexadecimal code units.
+class HexDecoder extends Converter<String, List<int>> {
+  const HexDecoder._();
+
+  List<int> convert(String string) {
+    if (!string.length.isEven) {
+      throw new FormatException("Invalid input length, must be even.",
+          string, string.length);
+    }
+
+    var bytes = new Uint8List(string.length ~/ 2);
+    _decode(string.codeUnits, bytes, 0);
+    return bytes;
+  }
+
+  StringConversionSink startChunkedConversion(Sink<List<int>> sink) =>
+      new _HexDecoderSink(sink);
+}
+
+/// A conversion sink for chunked hexadecimal decoding.
+class _HexDecoderSink extends StringConversionSinkBase {
+  /// The underlying sink to which decoded byte arrays will be passed.
+  final Sink<List<int>> _sink;
+
+  /// The trailing digit from the previous string.
+  ///
+  /// This will be non-`null` if the most recent string had an odd number of
+  /// hexadecimal digits. Since it's the most significant digit, it's always a
+  /// multiple of 16.
+  int _lastDigit;
+
+  _HexDecoderSink(this._sink);
+
+  void addSlice(String string, int start, int end, bool isLast) {
+    RangeError.checkValidRange(start, end, string.length);

[Lasse Reichstein Nielsen, 2015/09/24 08:07:02]

Maybe do
  end = RangeError.checkValidRange(...);
Then a "null" end will be treated as string.length instead of failing somewhere
below.

[nweiz, 2015/09/24 23:23:42]

StringConversionSink.addSlice's documentation doesn't describe [end] as being
nullable, so I'd rather not add support for it here.

+
+    var bytes;
+    var bytesStart;
+    if (_lastDigit == null) {
+      bytes = new Uint8List((end - start) ~/ 2);
+      bytesStart = 0;
+    } else {
+      var hexPairs = (end - start - 1) ~/ 2;
+      bytes = new Uint8List(1 + hexPairs);
+      bytes[0] = _lastDigit + _digitForCodeUnit(string.codeUnitAt(start));
+      start++;
+      bytesStart = 1;
+    }
+
+    var codeUnits = string.codeUnits.take(end).skip(start);

[Lasse Reichstein Nielsen, 2015/09/24 08:07:02]

I want to add getRange(start, end) to Iterable, but they won't let me add more
to Iterable any more :(

[Lasse Reichstein Nielsen, 2015/09/24 11:37:39]

However, since codeUnits is a list, you *can* write:
   string.codeUnits.getRange(start, end)

[sra1, 2015/09/24 18:39:35]

On dart2js it is going to be very much better to pass the (codeUnits,start,end)
to _decode and use indexing in _decode.

+    _lastDigit = _decode(codeUnits, bytes, bytesStart);
+
+    _sink.add(bytes);
+    if (isLast) close();
+  }
+
+  ByteConversionSink asUtf8Sink(bool allowMalformed) =>
+      new _HexDecoderByteSink(_sink);
+
+  void close() {
+    if (_lastDigit != null) {
+      throw new FormatException("Invalid input length, must be even.");
+    }
+
+    _sink.close();
+  }
+}
+
+/// A conversion sink for chunked hexadecimal decoding from UTF-8 bytes.
+class _HexDecoderByteSink extends ByteConversionSinkBase {
+  /// The underlying sink to which decoded byte arrays will be passed.
+  final Sink<List<int>> _sink;
+
+  /// The trailing digit from the previous string.
+  ///
+  /// This will be non-`null` if the most recent string had an odd number of
+  /// hexadecimal digits. Since it's the most significant digit, it's always a
+  /// multiple of 16.
+  int _lastDigit;
+
+  _HexDecoderByteSink(this._sink);
+
+  void add(List<int> chunk) => addSlice(chunk, 0, chunk.length, false);
+
+  void addSlice(List<int> chunk, int start, int end, bool isLast) {
+    RangeError.checkValidRange(start, end, chunk.length);
+

[Lasse Reichstein Nielsen, 2015/09/24 08:07:02]

You need to handle the case where start==end somehow.
Probably just wrap everything until if(isLast)  in  if (start < end) {...}

[nweiz, 2015/09/24 23:23:42]

Done.

+    var bytes;
+    var bytesStart;
+    if (_lastDigit == null) {
+      bytes = new Uint8List((end - start) ~/ 2);
+      bytesStart = 0;
+    } else {
+      var hexPairs = (end - start - 1) ~/ 2;

[Lasse Reichstein Nielsen, 2015/09/24 08:07:02]

Maybe declare
  var length = end - start;
Consider writing it as:

  var hexPairs = (length + 1) ~/ 2;
  bytes = new Uint8List(hexPairs);
instead of needing the 1+ below.

[nweiz, 2015/09/24 23:23:42]

I like how the current writing makes hexPairs the number of *pairs* in the
chunk, and then adds one to that for the extra carry-over byte.

[Lasse Reichstein Nielsen, 2015/09/25 06:40:33]

I guess that's just a difference in perspective. I was seeing it as the number
of pairs being output, which includes the carry-over byte

+      bytes = new Uint8List(1 + hexPairs);
+      bytes[0] = _lastDigit + _digitForCodeUnit(chunk[start]);
+      start++;
+      bytesStart = 1;
+    }
+
+    var codeUnits = chunk.take(end).skip(start);
+    _lastDigit = _decode(codeUnits, bytes, bytesStart);

[Lasse Reichstein Nielsen, 2015/09/24 08:07:02]

I still think using a list+start+end is more efficient than in iterator (and
personally I think it's more readable too - it *is* a list, and reducing it to
an iterator is just throwing away useful information).

+
+    _sink.add(bytes);
+    if (isLast) close();
+  }
+
+  void close() {
+    if (_lastDigit != null) {
+      throw new FormatException("Invalid input length, must be even.");
+    }
+
+    _sink.close();
+  }
+}
+
+/// Decodes [codeUnits] and writes the result into [destination].
+///
+/// This begins writing into destination at the index [start]. It returns the
+/// leftover digit from the end of [codeUnits], if any.
+int _decode(Iterable<int> codeUnits, List<int> destination, int start) {
+  var iterator = codeUnits.iterator;
+  for (var i = start;; i++) {
+    if (!iterator.moveNext()) return null;
+    var firstDigit = _digitForCodeUnit(iterator.current) * 16;

[sra1, 2015/09/24 18:39:35]

It really helps dart2js to have the constant first.  That looks nasty for
expressions like `0 > n` but reads fine for `16 *
_digitForCodeUnit(iterator.current)`.

[nweiz, 2015/09/24 23:23:42]

Done.

+
+    if (!iterator.moveNext()) return firstDigit;
+    var secondDigit = _digitForCodeUnit(iterator.current);

[sra1, 2015/09/24 18:39:35]

dart2js thinks iterator.current can be null (because all iterators have a null
.current at the end) so will generate type checks in the comparison arithmetic
below.

It is even worse, though.

Since the iterable is a skip/take, which is used from many other places, dart2js
will be confused about the type of .current and will believe _digitForCodeUnit
is called with anything.  The result is code for 'codeUnit >= $0' that would
work for any type (codeUnit might be a Duration!).  The cost of the dynamic
dispatch to do this will dwarf the concerns about the number of correctly
predicted branches.

+
+    destination[i] = firstDigit + secondDigit;

[sra1, 2015/09/24 18:39:35]

nit: it feels wrong to call both of these xxxDigit when one is scaled and the
other is not.

[nweiz, 2015/09/24 23:23:42]

Done.

+  }
+}
+
+/// Returns the digit (0 through 15) corresponding to the hexadecimal code unit
+/// [codeUnit].
+///
+/// If [codeUnit] isn't a valid hexadecimal code unit, throws a
+/// [FormatException].
+int _digitForCodeUnit(int codeUnit) {
+  if (codeUnit >= $0 && codeUnit <= $9) return codeUnit - $0;
+  if (codeUnit >= $a && codeUnit <= $f) return codeUnit - $a + 10;
+  if (codeUnit >= $A && codeUnit <= $F) return codeUnit - $A + 10;
+
+  throw new FormatException("Invalid hexadecimal code unit "
+      "U+${codeUnit.toRadixString(16).padLeft(4, '0')}.");
+}