From d23b7d2656dc25f6a33bcd436e15e9fd84aabc27 Mon Sep 17 00:00:00 2001 From: Brian White Date: Sun, 15 May 2016 14:53:08 -0400 Subject: 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 Reviewed-By: Anna Henningsen Reviewed-By: Ben Noordhuis --- lib/string_decoder.js | 376 ++++++++++++++++++++++++++------------------------ 1 file changed, 193 insertions(+), 183 deletions(-) (limited to 'lib/string_decoder.js') 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) : ''); } -- cgit v1.2.3