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..8554ed0ded873e9cd5cf45e700934ff3af6d6450
--- /dev/null
+++ b/lib/src/hex/decoder.dart
@@ -0,0 +1,115 @@
+// 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

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

Maybe mention that this is RFC 4648 base-16 encoding.

[nweiz, 2015/09/23 22:04:20]

Done, in the HexCodec documentation.

+/// 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("Expected an even-length hexadecimal string, "
+          "was odd.");

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

Add ", string, string.length" as arguments to FormatException.
Maybe reduce text to "Invalid input length, must be even".

[nweiz, 2015/09/23 22:04:21]

Done.

+    }
+
+    var bytes = new Uint8List(string.length ~/ 2);
+    _decode(string.runes, bytes, 0);

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

Use string.codeUnits instead. It's more efficient and any >255 value is an error
in either case.

[nweiz, 2015/09/23 22:04:20]

Done.

+    return bytes;
+  }
+
+  StringConversionSink startChunkedConversion(Sink<List<int>> sink) =>
+      new _HexDecoderSink(sink);
+}
+
+/// A sink for chunked hexadecimal decoding.

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

A conversion sink for ...
("A sink" is too generic, and it's not the Sink class).

[nweiz, 2015/09/23 22:04:21]

Done.

+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) {

[Lasse Reichstein Nielsen, 2015/09/23 08:32:03]

Maybe use:
  end = RangeError.checkValidRange(start, end, string.length);
It also checks that start >= 0 and end <= string.length.

This allows end to be null. If that's not OK, check for that first (and drop the
assignment).

[nweiz, 2015/09/23 22:04:21]

Done, although I'm not checking for null explicitly because that's not the usual
style.

+    if (start > end) {
+      throw new ArgumentError(
+          "start $start must be less than or equal to end $end.");
+    }
+
+    var bytes;
+    var bytesStart;
+    if (_lastDigit == null) {

[Lasse Reichstein Nielsen, 2015/09/23 08:32:03]

dart2js would probably prefer if the variable always contains integers, so maybe
use -1 instead of null to represent "no carry".

[nweiz, 2015/09/23 22:04:20]

I really don't like using magic numbers to indicate "no value" when we have a
null value that's explicitly for that case and fails more gracefully if it's
mis-used. Unless we have concrete data that "null" makes the code size or speed
substantially worse, I'd prefer to leave it in.

Also, it's at least plausible that dart2js can figure out that _lastDigit's only
use is guarded by an if statement that guarantees it won't be null.

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

True. This is definitely speculative, so keep it as is.

+      bytes = new Uint8List((end - start) ~/ 2);
+      bytesStart = 0;
+    } else {
+      start++;
+      bytes = new Uint8List(1 + (end - start) ~/ 2);
+      bytes[0] = _lastDigit + _digitForCodeUnit(string.codeUnitAt(start - 1));

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

Slightly confusing to increment start first and then subtract one here.
Maybe do it as:
  var firstChar = string.codeUnitAt(start);
  start++;
  bytes = ...;
  bytes[0] = _lastDigit + _digitsForCodeUnit(firstChar);
or 
  bytes = new Uint8List((end - start + 1) ~/ 2);
  bytes[0] = _lastDigit + _digitForCodeUnit(string.codeUnitAt(start - 1));
  start++;

[nweiz, 2015/09/23 22:04:20]

Done.

+      bytesStart = 1;
+    }
+
+    var runes = string.runes.skip(start).take(end);

[Lasse Reichstein Nielsen, 2015/09/23 08:32:03]

Should have be either .take(end).skip(start) or .skip(start).take(end - start).
We should have .getRange(start, end) on Iterable that does this for you.

But avoid doing this at all and just work directly on the codeUnits, not the
runes.
If you really want to report invalid code points (aka runes), you only need to
do it in the error handling, you can still parse the code units because the
first surrogate will be invalid anyway.

[nweiz, 2015/09/23 22:04:21]

Changed to use codeUnits, although I'm still using take/skip. to get at the
correct sublist.

+    _lastDigit = _decode(runes, bytes, bytesStart);
+
+    _sink.add(bytes);
+    if (isLast) close();
+  }
+
+  void close() {
+    if (_lastDigit != null) {
+      throw new FormatException("Expected an even-length hexadecimal string, "
+          "was odd.");

[Lasse Reichstein Nielsen, 2015/09/23 08:32:03]

Same message as above (if you changed it there). 
It's sad that we don't have an input/index to report here, but it's kind of
unavoidable.

[nweiz, 2015/09/23 22:04:20]

Done.

+    }
+
+    _sink.close();
+  }

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

Consider extending with asUtf8Sink because you can still use _decode for utf-8
input.

[nweiz, 2015/09/23 22:04:20]

Done.

+}
+
+/// Decodes [runes] and writes the result into [destination].
+///
+/// This begins writing into destination at the index [start].
+int _decode(Iterable<int> runes, List<int> destination, int start) {

[Lasse Reichstein Nielsen, 2015/09/23 08:32:03]

Make it: _decode(List<int> codeUnits, int start, int end, List<int> destination,
int destIndex)
Then you don't have to wrap the argument in skip/take, and you can index it as a
list instead of using it only as an iterator.

[nweiz, 2015/09/23 22:04:21]

Is that going to be substantially more efficient? It makes the signature more
complex and changes a lot of the implementation to be math-y instead of using
semantic method calls.

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

Most likely yes.
This is the inner loop of the transformation. The more code you put in here, the
slower everything gets. An Iterable, in this case a SubListIterable on top of a
CodeUnits list on top of a String, will have more overhead than doing
.codeUnitAt(index) directly. I don't think any of our compilers are smart enough
to avoid it.
You say "math-y" as if it's a bad thing :)

And it's very much in line with most other methods that take a string in taking
start,end too. 
It's a bad design that requires us to do it - we should have an efficient slice
operator on String that returns a CharSequence (not a string, but similar
interface) so we didn't have to pass around "string, start, end" manually, but
alas, we didn't do that.

It's not like the code is unreadable either:

int _decode(List<int> input, int start, int end, List<int> output, int outIndex)
{
  for (int i = start; i + 1 < end; i++) {
    var firstDigit = _digitForCodeUnit(input, i);
    var secondDigit = _digitForCodeUnit(input, i + 1);
    output[outIndex++] = firstDigit * 16 + secondDigit;
  }
  int length = end - start;
  if (length.isOdd) return _digitForCodeUnit(input, end - 1) * 16;
  return null;
}

int _digitForCodeUnit(List<int> codeUnits, int index) {
  int codeUnit = codeUnits[index];
  ... decode as usual ...
  throw new FormatException("Not hexadecimal digit", 
                new String.fromCodeUnits(codeUnits), index);
}

... and this even makes the input and index available at the point of error.
It would be even easier if you just passed the string around and did
.codeUnitAt, but then you need different code for the asUtf8Sink sink.

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

Done.

+  var iterator = runes.iterator;
+  for (var i = start; true; i++) {

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

remove the "true". An omitted condition in a for statement is true by default,
and parts that are not used are traditionally omitted.

Or just use a while(true) loop and increment i as  destination[i++]=...  below.

[nweiz, 2015/09/23 22:04:21]

Done.

+    if (!iterator.moveNext()) return null;
+    var firstDigit = _digitForCodeUnit(iterator.current) * 16;
+
+    if (!iterator.moveNext()) return firstDigit;
+    var secondDigit = _digitForCodeUnit(iterator.current);
+
+    destination[i] = firstDigit + secondDigit;
+  }
+}
+
+/// 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;
+

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

Consider optimizing this to:

int digit = codeUnit ^ $0;
if (codeUnit <= 9) {  // Only one branch for 10 of 16 cases.
  return digit;
}
int ucLetter = codeUnit & ~0x20;  // Upper-case if letter.
if (ucLetter <= $Z && ucLetter >= $A) {
  return ucLetter - ($A - 10);
}
throw new FormatException(...)

It would be great if the FormatException could contain the input string and
index, but it's harder when you don't pass the string and index down here.
Returning -1 for error is possible, but it introduces an extra check in the
inner loop (which can be delayed if necessary).

[nweiz, 2015/09/23 22:04:21]

If this is worth heavily optimizing, would it be better to just use a switch
statement? Couldn't that be compiled to a single jump or something clever like
that?

Also, it looks like your code won't catch negative code units, which could come
from a misuse of the UTF-8 converter.
Passing down the string would add a lot of complexity with the UTF-8 decoder,
and passing back up an error value would add complexity regardless. One somewhat
cleaner possibility would be to just pass in the index, and then have a
try/catch that rethrows the exception with the original source in whatever
format.

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

It's executed twice in the inner loop of the transformation, so it's a good idea
to keep it small and reduce the number of unpredictable branches.
I'd use either this or a table.
Of course, having a benchmark would be even better :)
It could, but it likely isn't. I wouldn't trust switch statements, and in this
case (where there is no special code for any case) a simple table would be a
more direct way to get get the result with a single indirection.
And it avoids branches. You will need a branch to ensure that the input is in
the range of the table, but that should be a predictable branch (always true,
otherwise we have an error anyway). 

 
That is true. For that you will need the >= 0 check:

int digit = codeUnit ^ $0;
if (digit <= 9) {
  if (digit >= 0) return digit;  // Predictable branch.
} else {
  int letter = codeUnit & ~0x20;
  if ($A <= letter && letter <= $Z) return letter - ($A - 10);
}
throw ...

That check is predictable for correct input, so it shouldn't cost.
Really, the only unpredictable branch is the first "<= 9".
Or, if you pass around a list and an index, you can do the index operation
inside the _digitForCodeUnit function.

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

Done.

+  throw new FormatException("Invalid hexadecimal code point "
+      "U+${codeUnit.toRadixString(16)}.");

[Lasse Reichstein Nielsen, 2015/09/23 08:32:04]

code point -> code unit
add: .padLeft(4, '0') so the hex is always four digits.

[nweiz, 2015/09/23 22:04:21]

Done.
Done.

+}