string_decoder: rewrite implementation

This commit provides a rewrite of StringDecoder that both improves
performance (for non-single-byte encodings) and understandability.

Additionally, StringDecoder instantiation performance has increased
considerably due to inlinability and more efficient encoding name
checking.

PR-URL: https://github.com/nodejs/node/pull/6777
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Anna Henningsen <anna@addaleax.net>
Reviewed-By: Ben Noordhuis <info@bnoordhuis.nl>

1 files changed, 193 insertions, 183 deletions

diff --git a/lib/string_decoder.js b/lib/string_decoder.js
index 4047489e6c..aaadfd8934 100644
--- a/lib/string_decoder.js
+++ b/lib/string_decoder.js
@@ -2,224 +2,234 @@
 
 const Buffer = require('buffer').Buffer;
 
-function assertEncoding(encoding) {
-  // Do not cache `Buffer.isEncoding`, some modules monkey-patch it to support
-  // additional encodings
-  if (encoding && !Buffer.isEncoding(encoding)) {
-    throw new Error('Unknown encoding: ' + encoding);
+// Do not cache `Buffer.isEncoding` when checking encoding names as some
+// modules monkey-patch it to support additional encodings
+function normalizeEncoding(enc) {
+  if (!enc) return 'utf8';
+  var low;
+  for (;;) {
+    switch (enc) {
+      case 'utf8':
+      case 'utf-8':
+        return 'utf8';
+      case 'ucs2':
+      case 'utf16le':
+      case 'ucs-2':
+      case 'utf-16le':
+        return 'utf16le';
+      case 'base64':
+      case 'ascii':
+      case 'binary':
+      case 'hex':
+        return enc;
+      default:
+        if (low) {
+          if (!Buffer.isEncoding(enc))
+            throw new Error('Unknown encoding: ' + enc);
+          return enc;
+        }
+        low = true;
+        enc = ('' + enc).toLowerCase();
+    }
   }
 }
 
 // StringDecoder provides an interface for efficiently splitting a series of
 // buffers into a series of JS strings without breaking apart multi-byte
-// characters. CESU-8 is handled as part of the UTF-8 encoding.
-//
-// @TODO Handling all encodings inside a single object makes it very difficult
-// to reason about this code, so it should be split up in the future.
-// @TODO There should be a utf8-strict encoding that rejects invalid UTF-8 code
-// points as used by CESU-8.
-const StringDecoder = exports.StringDecoder = function(encoding) {
-  this.encoding = (encoding || 'utf8').toLowerCase().replace(/[-_]/, '');
-  assertEncoding(encoding);
+// characters.
+exports.StringDecoder = StringDecoder;
+function StringDecoder(encoding) {
+  this.encoding = normalizeEncoding(encoding);
+  var nb;
   switch (this.encoding) {
-    case 'utf8':
-      // CESU-8 represents each of Surrogate Pair by 3-bytes
-      this.surrogateSize = 3;
-      break;
-    case 'ucs2':
     case 'utf16le':
-      // UTF-16 represents each of Surrogate Pair by 2-bytes
-      this.surrogateSize = 2;
-      this.detectIncompleteChar = utf16DetectIncompleteChar;
+      this.text = utf16Text;
+      this.end = utf16End;
+      // fall through
+    case 'utf8':
+      nb = 4;
       break;
     case 'base64':
-      // Base-64 stores 3 bytes in 4 chars, and pads the remainder.
-      this.surrogateSize = 3;
-      this.detectIncompleteChar = base64DetectIncompleteChar;
+      this.text = base64Text;
+      this.end = base64End;
+      nb = 3;
       break;
     default:
-      this.write = passThroughWrite;
+      this.write = simpleWrite;
+      this.end = simpleEnd;
       return;
   }
+  this.lastNeed = 0;
+  this.lastTotal = 0;
+  this.lastChar = Buffer.allocUnsafe(nb);
+}
 
-  // Enough space to store all bytes of a single character. UTF-8 needs 4
-  // bytes, but CESU-8 may require up to 6 (3 bytes per surrogate).
-  this.charBuffer = Buffer.allocUnsafe(6);
-  // Number of bytes received for the current incomplete multi-byte character.
-  this.charReceived = 0;
-  // Number of bytes expected for the current incomplete multi-byte character.
-  this.charLength = 0;
-};
-
-
-// write decodes the given buffer and returns it as JS string that is
-// guaranteed to not contain any partial multi-byte characters. Any partial
-// character found at the end of the buffer is buffered up, and will be
-// returned when calling write again with the remaining bytes.
-//
-// Note: Converting a Buffer containing an orphan surrogate to a String
-// currently works, but converting a String to a Buffer (via `Buffer.from()`,
-// or Buffer#write) will replace incomplete surrogates with the unicode
-// replacement character. See https://codereview.chromium.org/121173009/ .
-StringDecoder.prototype.write = function(buffer) {
-  var charStr = '';
-  var buflen = buffer.length;
-  var charBuffer = this.charBuffer;
-  var charLength = this.charLength;
-  var charReceived = this.charReceived;
-  var surrogateSize = this.surrogateSize;
-  var encoding = this.encoding;
-  var charCode;
-  // if our last write ended with an incomplete multibyte character
-  while (charLength) {
-    // determine how many remaining bytes this buffer has to offer for this char
-    var diff = charLength - charReceived;
-    var available = (buflen >= diff) ? diff : buflen;
-
-    // add the new bytes to the char buffer
-    buffer.copy(charBuffer, charReceived, 0, available);
-    charReceived += available;
-
-    if (charReceived < charLength) {
-      // still not enough chars in this buffer? wait for more ...
-
-      this.charLength = charLength;
-      this.charReceived = charReceived;
-
+StringDecoder.prototype.write = function(buf) {
+  if (buf.length === 0)
+    return '';
+  var r;
+  var i;
+  if (this.lastNeed) {
+    r = this.fillLast(buf);
+    if (r === undefined)
       return '';
-    }
-
-    // remove bytes belonging to the current character from the buffer
-    buffer = buffer.slice(available, buflen);
-    buflen = buffer.length;
-
-    // get the character that was split
-    charStr = charBuffer.toString(encoding, 0, charLength);
+    i = this.lastNeed;
+    this.lastNeed = 0;
+  } else {
+    i = 0;
+  }
+  if (i < buf.length)
+    return (r ? r + this.text(buf, i) : this.text(buf, i));
+  return r || '';
+};
 
-    // CESU-8: lead surrogate (D800-DBFF) is also the incomplete character
-    charCode = charStr.charCodeAt(charStr.length - 1);
-    if (charCode >= 0xD800 && charCode <= 0xDBFF) {
-      charLength += surrogateSize;
-      charStr = '';
-      continue;
-    }
-    charReceived = charLength = 0;
+StringDecoder.prototype.end = utf8End;
 
-    // if there are no more bytes in this buffer, just emit our char
-    if (buflen === 0) {
-      this.charLength = charLength;
-      this.charReceived = charReceived;
+// Returns only complete characters in a Buffer
+StringDecoder.prototype.text = utf8Text;
 
-      return charStr;
-    }
+// Attempts to complete a partial character using bytes from a Buffer
+StringDecoder.prototype.fillLast = function(buf) {
+  if (this.lastNeed <= buf.length) {
+    buf.copy(this.lastChar, this.lastTotal - this.lastNeed, 0, this.lastNeed);
+    return this.lastChar.toString(this.encoding, 0, this.lastTotal);
   }
+  buf.copy(this.lastChar, this.lastTotal - this.lastNeed, 0, buf.length);
+  this.lastNeed -= buf.length;
+};
 
-  // determine and set charLength / charReceived
-  if (this.detectIncompleteChar(buffer))
-    charLength = this.charLength;
-  charReceived = this.charReceived;
+// Checks the type of a UTF-8 byte, whether it's ASCII, a leading byte, or a
+// continuation byte.
+function utf8CheckByte(byte) {
+  if (byte <= 0x7F)
+    return 0;
+  else if (byte >> 5 === 0x06)
+    return 2;
+  else if (byte >> 4 === 0x0E)
+    return 3;
+  else if (byte >> 3 === 0x1E)
+    return 4;
+  return -1;
+}
 
-  var end = buflen;
-  if (charLength) {
-    // buffer the incomplete character bytes we got
-    buffer.copy(charBuffer, 0, buflen - charReceived, end);
-    end -= charReceived;
+// Checks at most the last 3 bytes of a Buffer for an incomplete UTF-8
+// character, returning the total number of bytes needed to complete the partial
+// character (if applicable).
+function utf8CheckIncomplete(self, buf, i) {
+  var j = buf.length - 1;
+  if (j < i)
+    return 0;
+  var nb = utf8CheckByte(buf[j--]);
+  if (nb >= 0) {
+    if (nb > 0)
+      self.lastNeed = nb + 1 - (buf.length - j);
+    return nb;
   }
-
-  this.charLength = charLength;
-  charStr += buffer.toString(encoding, 0, end);
-
-  end = charStr.length - 1;
-  charCode = charStr.charCodeAt(end);
-  // CESU-8: lead surrogate (D800-DBFF) is also the incomplete character
-  if (charCode >= 0xD800 && charCode <= 0xDBFF) {
-    charLength += surrogateSize;
-    charReceived += surrogateSize;
-    charBuffer.copy(charBuffer, surrogateSize, 0, surrogateSize);
-    buffer.copy(charBuffer, 0, 0, surrogateSize);
-
-    this.charLength = charLength;
-    this.charReceived = charReceived;
-
-    return charStr.substring(0, end);
+  if (j < i)
+    return 0;
+  nb = utf8CheckByte(buf[j--]);
+  if (nb >= 0) {
+    if (nb > 0)
+      self.lastNeed = nb + 1 - (buf.length - j);
+    return nb;
   }
+  if (j < i)
+    return 0;
+  nb = utf8CheckByte(buf[j--]);
+  if (nb >= 0) {
+    if (nb > 0)
+      self.lastNeed = nb + 1 - (buf.length - j);
+    return nb;
+  }
+  return 0;
+}
 
-  // or just emit the charStr
-  return charStr;
-};
-
-// detectIncompleteChar determines if there is an incomplete UTF-8 character at
-// the end of the given buffer. If so, it sets this.charLength to the byte
-// length that character, and sets this.charReceived to the number of bytes
-// that are available for this character.
-StringDecoder.prototype.detectIncompleteChar = function(buffer) {
-  var buflen = buffer.length;
-  // determine how many bytes we have to check at the end of this buffer
-  var i = (buflen >= 3) ? 3 : buflen;
-  var newlen = false;
-
-  // Figure out if one of the last i bytes of our buffer announces an
-  // incomplete char.
-  for (; i > 0; i--) {
-    var c = buffer[buflen - i];
-
-    // See http://en.wikipedia.org/wiki/UTF-8#Description
-
-    // 110XXXXX
-    if (i === 1 && c >> 5 === 0x06) {
-      this.charLength = 2;
-      newlen = true;
-      break;
-    }
+// Returns all complete UTF-8 characters in a Buffer. If the Buffer ended on a
+// partial character, the character's bytes are buffered until the required
+// number of bytes are available.
+function utf8Text(buf, i) {
+  const total = utf8CheckIncomplete(this, buf, i);
+  if (!this.lastNeed)
+    return buf.toString('utf8', i);
+  this.lastTotal = total;
+  const end = buf.length - (total - this.lastNeed);
+  buf.copy(this.lastChar, 0, end);
+  return buf.toString('utf8', i, end);
+}
 
-    // 1110XXXX
-    if (i <= 2 && c >> 4 === 0x0E) {
-      this.charLength = 3;
-      newlen = true;
-      break;
-    }
+// For UTF-8, a replacement character for each buffered byte of a (partial)
+// character needs to be added to the output.
+function utf8End(buf) {
+  const r = (buf && buf.length ? this.write(buf) : '');
+  if (this.lastNeed)
+    return r + '\ufffd'.repeat(this.lastTotal - this.lastNeed);
+  return r;
+}
 
-    // 11110XXX
-    if (i <= 3 && c >> 3 === 0x1E) {
-      this.charLength = 4;
-      newlen = true;
-      break;
+// UTF-16LE typically needs two bytes per character, but even if we have an even
+// number of bytes available, we need to check if we end on a leading/high
+// surrogate. In that case, we need to wait for the next two bytes in order to
+// decode the last character properly.
+function utf16Text(buf, i) {
+  if ((buf.length - i) % 2 === 0) {
+    const r = buf.toString('utf16le', i);
+    if (r) {
+      const c = r.charCodeAt(r.length - 1);
+      if (c >= 0xD800 && c <= 0xDBFF) {
+        this.lastNeed = 2;
+        this.lastTotal = 4;
+        this.lastChar[0] = buf[buf.length - 2];
+        this.lastChar[1] = buf[buf.length - 1];
+        return r.slice(0, -1);
+      }
     }
+    return r;
   }
+  this.lastNeed = 1;
+  this.lastTotal = 2;
+  this.lastChar[0] = buf[buf.length - 1];
+  return buf.toString('utf16le', i, buf.length - 1);
+}
 
-  this.charReceived = i;
-
-  return newlen;
-};
+// For UTF-16LE we do not explicitly append special replacement characters if we
+// end on a partial character, we simply let v8 handle that.
+function utf16End(buf) {
+  const r = (buf && buf.length ? this.write(buf) : '');
+  if (this.lastNeed) {
+    const end = this.lastTotal - this.lastNeed;
+    return r + this.lastChar.toString('utf16le', 0, end);
+  }
+  return r;
+}
 
-StringDecoder.prototype.end = function(buffer) {
-  var res = '';
-  if (buffer && buffer.length)
-    res = this.write(buffer);
-
-  var charReceived = this.charReceived;
-  if (charReceived) {
-    var cr = charReceived;
-    var buf = this.charBuffer;
-    var enc = this.encoding;
-    res += buf.toString(enc, 0, cr);
+function base64Text(buf, i) {
+  const n = (buf.length - i) % 3;
+  if (n === 0)
+    return buf.toString('base64', i);
+  this.lastNeed = 3 - n;
+  this.lastTotal = 3;
+  if (n === 1) {
+    this.lastChar[0] = buf[buf.length - 1];
+  } else {
+    this.lastChar[0] = buf[buf.length - 2];
+    this.lastChar[1] = buf[buf.length - 1];
   }
+  return buf.toString('base64', i, buf.length - n);
+}
 
-  return res;
-};
 
-function passThroughWrite(buffer) {
-  return buffer.toString(this.encoding);
+function base64End(buf) {
+  const r = (buf && buf.length ? this.write(buf) : '');
+  if (this.lastNeed)
+    return r + this.lastChar.toString('base64', 0, 3 - this.lastNeed);
+  return r;
 }
 
-function utf16DetectIncompleteChar(buffer) {
-  var charReceived = this.charReceived = buffer.length % 2;
-  this.charLength = charReceived ? 2 : 0;
-  return true;
+// Pass bytes on through for single-byte encodings (e.g. ascii, binary, hex)
+function simpleWrite(buf) {
+  return buf.toString(this.encoding);
 }
 
-function base64DetectIncompleteChar(buffer) {
-  var charReceived = this.charReceived = buffer.length % 3;
-  this.charLength = charReceived ? 3 : 0;
-  return true;
+function simpleEnd(buf) {
+  return (buf && buf.length ? this.write(buf) : '');
 }