UTF decode benchmark

main.swift

import Foundation

public func runDecode<Codec : _UnicodeCodec>(codec: Codec.Type, encode: (String) -> [Codec.CodeUnit]) -> NSTimeInterval {
	// 1-byte sequences
	// This test case is the longest as it's the most performance sensitive.
	let ascii = "Swift is a multi-paradigm, compiled programming language created for iOS, OS X, watchOS, tvOS and Linux development by Apple Inc. Swift is designed to work with Apple's Cocoa and Cocoa Touch frameworks and the large body of existing Objective-C code written for Apple products. Swift is intended to be more resilient to erroneous code (\"safer\") than Objective-C and also more concise. It is built with the LLVM compiler framework included in Xcode 6 and later and uses the Objective-C runtime, which allows C, Objective-C, C++ and Swift code to run within a single program."
	// 2-byte sequences
	let russian = "Ру́сский язы́к один из восточнославянских языков, национальный язык русского народа."
	// 3-byte sequences
	let japanese = "日本語（にほんご、にっぽんご）は、主に日本国内や日本人同士の間で使われている言語である。"
	// 4-byte sequences
	// Most commonly emoji, which are usually mixed with other text.
	let emoji = "Panda 🐼, Dog 🐶, Cat 🐱, Mouse 🐭."

//	let strings = [ encode(ascii) ]
	let strings = [ encode(ascii), encode(russian), encode(japanese), encode(emoji) ]

	func isEmpty(_ result: _UnicodeDecodingResult) -> Bool {
		switch result {
		case .emptyInput: return true
		default: return false
		}
	}

	let start = NSDate()
	for _ in 1...10_000 {
		for string in strings {
			var it = string.makeIterator()
			var codec = Codec()
			while !isEmpty(codec.decode(&it)) { }
		}
	}
	let dt = NSDate().timeIntervalSince(start)

	return dt
}

func testUTF8() {
	var total: Double = 0
	let n = 50
	for _ in 0..<n {
		let t0 = runDecode(codec: OldUTF8.self, encode: { Array($0.utf8) })
		let t1 = runDecode(codec: NewUTF8.self, encode: { Array($0.utf8) })
		total += (t0/t1)
	}
	print("UTF-8:\t\(total/Double(n))")
}

func testUTF16() {
	var total: Double = 0
	let n = 50
	for _ in 0..<n {
		let t0 = runDecode(codec: OldUTF16.self, encode: { Array($0.utf16) })
		let t1 = runDecode(codec: NewUTF16.self, encode: { Array($0.utf16) })
		total += (t0/t1)
	}
	print("UTF-16:\t\(total/Double(n))")
}

func testUTF32() {
	var total: Double = 0
	let n = 50
	for _ in 0..<n {

		let t0 = runDecode(codec: OldUTF32.self, encode: { Array($0.unicodeScalars.map { $0.value }) })
		let t1 = runDecode(codec: NewUTF32.self, encode: { Array($0.unicodeScalars.map { $0.value }) })

		total += (t0/t1)
	}
	print("UTF-32:\t\(total/Double(n))")
}

testUTF8()
testUTF16()
//testUTF32()

NewUTF.swift

/// A codec for translating between Unicode scalar values and UTF-8 code
/// units.
public struct NewUTF8 : _UnicodeCodec {
	// See Unicode 8.0.0, Ch 3.9, UTF-8.
	// http://www.unicode.org/versions/Unicode8.0.0/ch03.pdf

	/// A type that can hold code unit values for this encoding.
	public typealias CodeUnit = UInt8

	/// Creates an instance of the UTF-8 codec.
	public init() {}

	/// Lookahead buffer used for UTF-8 decoding.  New bytes are inserted at MSB,
	/// and bytes are read at LSB.  Note that we need to use a buffer, because
	/// in case of invalid subsequences we sometimes don't know whether we should
	/// consume a certain byte before looking at it.
	internal var _decodeBuffer: UInt32 = 0

	/// The number of bits in `_decodeBuffer` that are current filled.
	internal var _bitsInBuffer: UInt8 = 0

	/// Starts or continues decoding a UTF-8 sequence.
	///
	/// To decode a code unit sequence completely, call this method repeatedly
	/// until it returns `UnicodeDecodingResult.emptyInput`. Checking that the
	/// iterator was exhausted is not sufficient, because the decoder can store
	/// buffered data from the input iterator.
	///
	/// Because of buffering, it is impossible to find the corresponding position
	/// in the iterator for a given returned `UnicodeScalar` or an error.
	///
	/// The following example decodes the UTF-8 encoded bytes of a string into an
	/// array of `UnicodeScalar` instances. This is a demonstration only---if
	/// you need the Unicode scalar representation of a string, use its
	/// `unicodeScalars` view.
	///
	///     let str = "✨Unicode✨"
	///     print(Array(str.utf8))
	///     // Prints "[226, 156, 168, 85, 110, 105, 99, 111, 100, 101, 226, 156, 168]"
	///
	///     var bytesIterator = str.utf8.makeIterator()
	///     var scalars: [UnicodeScalar] = []
	///     var utf8Decoder = UTF8()
	///     Decode: while true {
	///         switch utf8Decoder.decode(&bytesIterator) {
	///         case .scalarValue(let v): scalars.append(v)
	///         case .emptyInput: break Decode
	///         case .error:
	///             print("Decoding error")
	///             break Decode
	///         }
	///     }
	///     print(scalars)
	///     // Prints "["\u{2728}", "U", "n", "i", "c", "o", "d", "e", "\u{2728}"]"
	///
	/// - Parameter next: An iterator of code units to be decoded. `next` must be
	///   the same iterator instance in repeated calls to this method. Do not
	///   advance the iterator or any copies of the iterator outside this
	///   method.
	/// - Returns: A `UnicodeDecodingResult` instance, representing the next
	///   Unicode scalar, an indication of an error, or an indication that the
	///   UTF sequence has been fully decoded.
	public mutating func decode<
		I : IteratorProtocol where I.Element == CodeUnit
  >(_ input: inout I) -> _UnicodeDecodingResult {

		// Bufferless ASCII fastpath.
		if _fastPath(_bitsInBuffer == 0) {
			guard let codeUnit = input.next() else { return .emptyInput }
			// ASCII, return immediately.
			if codeUnit & 0x80 == 0 {
				return .scalarValue(_UnicodeScalar(_unchecked: UInt32(codeUnit)))
			}
			// Non-ASCII, proceed to buffering mode.
			_decodeBuffer = UInt32(codeUnit)
			_bitsInBuffer = 8
		} else if (_decodeBuffer & 0x80 == 0) {
			// ASCII in buffer.  We don't refill the buffer so we can return
			// to bufferless mode once we've exhausted it.
			let codeUnit = _decodeBuffer & 0xff
			_decodeBuffer >>= 8
			_bitsInBuffer = _bitsInBuffer &- 8
			return .scalarValue(_UnicodeScalar(_unchecked: codeUnit))
		}
		// Buffering mode.
		// Fill buffer back to 4 bytes (or as many as are left in the iterator).
		_sanityCheck(_bitsInBuffer < 32)
		repeat {
			if let codeUnit = input.next() {
				// We know _bitsInBuffer < 32 so we use `& 0x1f` (31) to make the
				// compiler omit a bounds check branch for the bitshift.
				_decodeBuffer |= (UInt32(codeUnit) << UInt32(_bitsInBuffer & 0x1f))
				_bitsInBuffer = _bitsInBuffer &+ 8
			} else {
				if _bitsInBuffer == 0 { return .emptyInput }
				break // We still have some bytes left in our buffer.
			}
		} while _bitsInBuffer < 32

		// Decode one unicode scalar.
		// Note our empty bytes are always 0x00, which is required for this call.
		let (result, length) = UTF8._decodeOne(_decodeBuffer)

		// Consume the decoded bytes (or maximal subpart of ill-formed sequence).
		let bitsConsumed = 8 &* length
		_sanityCheck(1...4 ~= length && bitsConsumed <= _bitsInBuffer)
		// Swift doesn't allow shifts greater than or equal to the type width.
		// _decodeBuffer >>= UInt32(bitsConsumed) // >>= 32 crashes.
		// Mask with 0x3f (63) to let the compiler omit the '>= 64' bounds check.
		_decodeBuffer = UInt32(truncatingBitPattern:
			UInt64(_decodeBuffer) >> (UInt64(bitsConsumed) & 0x3f))
		_bitsInBuffer = _bitsInBuffer &- bitsConsumed

		guard _fastPath(result != nil) else { return .error }
		return .scalarValue(_UnicodeScalar(_unchecked: result!))
	}

	/// Attempts to decode a single UTF-8 code unit sequence starting at the LSB
	/// of `buffer`.
	///
	/// - Returns:
	///   - result: The decoded code point if the code unit sequence is
	///     well-formed; `nil` otherwise.
	///   - length: The length of the code unit sequence in bytes if it is
	///     well-formed; otherwise the *maximal subpart of the ill-formed
	///     sequence* (Unicode 8.0.0, Ch 3.9, D93b), i.e. the number of leading
	///     code units that were valid or 1 in case none were valid.  Unicode
	///     recommends to skip these bytes and replace them by a single
	///     replacement character (U+FFFD).
	///
	/// - Requires: There is at least one used byte in `buffer`, and the unused
	///   space in `buffer` is filled with some value not matching the UTF-8
	///   continuation byte form (`0b10xxxxxx`).
	public // @testable
	static func _decodeOne(_ buffer: UInt32) -> (result: UInt32?, length: UInt8) {
		// Note the buffer is read least significant byte first: [ #3 #2 #1 #0 ].

		if buffer & 0x80 == 0 { // 1-byte sequence (ASCII), buffer: [ … … … CU0 ].
			let value = buffer & 0xff
			return (value, 1)
		}

		// Determine sequence length using high 5 bits of 1st byte.  We use a
		// look-up table to branch less.  1-byte sequences are handled above.
		//
		//  case | pattern | description
		// ----------------------------
		//   00  |  110xx  | 2-byte sequence
		//   01  |  1110x  | 3-byte sequence
		//   10  |  11110  | 4-byte sequence
		//   11  |  other  | invalid
		//
		//                     11xxx      10xxx      01xxx      00xxx
		let lut0: UInt32 = 0b1011_0000__1111_1111__1111_1111__1111_1111
		let lut1: UInt32 = 0b1100_0000__1111_1111__1111_1111__1111_1111

		let index = (buffer >> 3) & 0x1f
		let bit0 = (lut0 >> index) & 1
		let bit1 = (lut1 >> index) & 1

		switch (bit1, bit0) {
		case (0, 0): // 2-byte sequence, buffer: [ … … CU1 CU0 ].
			// Require 10xx xxxx  110x xxxx.
			if _slowPath(buffer & 0xc0e0 != 0x80c0) { return (nil, 1) }
			// Disallow xxxx xxxx  xxx0 000x (<= 7 bits case).
			if _slowPath(buffer & 0x001e == 0x0000) { return (nil, 1) }
			// Extract data bits.
			let value = (buffer & 0x3f00) >> 8
				| (buffer & 0x001f) << 6
			return (value, 2)

		case (0, 1): // 3-byte sequence, buffer: [ … CU2 CU1 CU0 ].
			// Disallow xxxx xxxx  xx0x xxxx  xxxx 0000 (<= 11 bits case).
			if _slowPath(buffer & 0x00200f == 0x000000) { return (nil, 1) }
			// Disallow xxxx xxxx  xx1x xxxx  xxxx 1101 (surrogate code points).
			if _slowPath(buffer & 0x00200f == 0x00200d) { return (nil, 1) }
			// Require 10xx xxxx  10xx xxxx  1110 xxxx.
			if _slowPath(buffer & 0xc0c0f0 != 0x8080e0) {
				if buffer & 0x00c000 != 0x008000 { return (nil, 1) }
				return (nil, 2) // All checks on CU0 & CU1 passed.
			}
			// Extract data bits.
			let value = (buffer & 0x3f0000) >> 16
				| (buffer & 0x003f00) >> 2
				| (buffer & 0x00000f) << 12
			return (value, 3)

		case (1, 0): // 4-byte sequence, buffer: [ CU3 CU2 CU1 CU0 ].
			// Disallow xxxx xxxx  xxxx xxxx  xx00 xxxx  xxxx x000 (<= 16 bits case).
			if _slowPath(buffer & 0x00003007 == 0x00000000) { return (nil, 1) }
			// If xxxx xxxx  xxxx xxxx  xxxx xxxx  xxxx x1xx.
			if buffer & 0x00000004 == 0x00000004 {
				// Require xxxx xxxx  xxxx xxxx  xx00 xxxx  xxxx xx00 (<= 0x10FFFF).
				if _slowPath(buffer & 0x00003003 != 0x00000000) { return (nil, 1) }
			}
			// Require 10xx xxxx  10xx xxxx  10xx xxxx  1111 0xxx.
			if _slowPath(buffer & 0xc0c0c0f8 != 0x808080f0) {
				if buffer & 0x0000c000 != 0x00008000 { return (nil, 1) }
				// All other checks on CU0, CU1 & CU2 passed.
				if buffer & 0x00c00000 != 0x00800000 { return (nil, 2) }
				return (nil, 3)
			}
			// Extract data bits.
			let value = (buffer & 0x3f000000) >> 24
				| (buffer & 0x003f0000) >> 10
				| (buffer & 0x00003f00) << 4
				| (buffer & 0x00000007) << 18
			return (value, 4)

		default: // Invalid sequence (CU0 invalid).
			return (nil, 1)
		}
	}
}

/// A codec for translating between Unicode scalar values and UTF-16 code
/// units.
public struct NewUTF16 : _UnicodeCodec {
	/// A type that can hold code unit values for this encoding.
	public typealias CodeUnit = UInt16

	/// Creates an instance of the UTF-16 codec.
	public init() {}

	/// A lookahead buffer for one UTF-16 code unit.
	internal var _decodeLookahead: UInt16?

	/// Starts or continues decoding a UTF-16 sequence.
	///
	/// To decode a code unit sequence completely, call this method repeatedly
	/// until it returns `UnicodeDecodingResult.emptyInput`. Checking that the
	/// iterator was exhausted is not sufficient, because the decoder can store
	/// buffered data from the input iterator.
	///
	/// Because of buffering, it is impossible to find the corresponding position
	/// in the iterator for a given returned `UnicodeScalar` or an error.
	///
	/// The following example decodes the UTF-16 encoded bytes of a string into an
	/// array of `UnicodeScalar` instances. This is a demonstration only---if
	/// you need the Unicode scalar representation of a string, use its
	/// `unicodeScalars` view.
	///
	///     let str = "✨Unicode✨"
	///     print(Array(str.utf16))
	///     // Prints "[10024, 85, 110, 105, 99, 111, 100, 101, 10024]"
	///
	///     var codeUnitIterator = str.utf16.makeIterator()
	///     var scalars: [UnicodeScalar] = []
	///     var utf16Decoder = UTF16()
	///     Decode: while true {
	///         switch utf16Decoder.decode(&codeUnitIterator) {
	///         case .scalarValue(let v): scalars.append(v)
	///         case .emptyInput: break Decode
	///         case .error:
	///             print("Decoding error")
	///             break Decode
	///         }
	///     }
	///     print(scalars)
	///     // Prints "["\u{2728}", "U", "n", "i", "c", "o", "d", "e", "\u{2728}"]"
	///
	/// - Parameter next: An iterator of code units to be decoded. `next` must be
	///   the same iterator instance in repeated calls to this method. Do not
	///   advance the iterator or any copies of the iterator outside this
	///   method.
	/// - Returns: A `UnicodeDecodingResult` instance, representing the next
	///   Unicode scalar, an indication of an error, or an indication that the
	///   UTF sequence has been fully decoded.
	public mutating func decode<
		I : IteratorProtocol where I.Element == CodeUnit
  >(_ input: inout I) -> _UnicodeDecodingResult {
		// Note: maximal subpart of ill-formed sequence for UTF-16 can only have
		// length 1.  Length 0 does not make sense.  Neither does length 2 -- in
		// that case the sequence is valid.

		let unit0: UInt16
		if _fastPath(_decodeLookahead == nil) {
			guard let next = input.next() else { return .emptyInput }
			unit0 = next
		} else { // Consume lookahead first.
			unit0 = _decodeLookahead!
			_decodeLookahead = nil
		}

		// A well-formed pair of surrogates looks like this:
		//     high-surrogate        low-surrogate
		// [1101 10xx xxxx xxxx] [1101 11xx xxxx xxxx]

		// Common case first, non-surrogate -- just a sequence of 1 code unit.
		if _fastPath((unit0 >> 11) != 0b1101_1) {
			return .scalarValue(_UnicodeScalar(_unchecked: UInt32(unit0)))
		}

		// Ensure `unit0` is a high-surrogate.
		guard _fastPath((unit0 >> 10) == 0b1101_10) else { return .error }

		// We already have a high-surrogate, so there should be a next code unit.
		guard let unit1 = input.next() else { return .error }

		// `unit0` is a high-surrogate, so `unit1` should be a low-surrogate.
		guard _fastPath((unit1 >> 10) == 0b1101_11) else {
			// Invalid sequence, discard `unit0` and store `unit1` for the next call.
			_decodeLookahead = unit1
			return .error
		}

		// We have a well-formed surrogate pair, decode it.
		let result = 0x10000 + ((UInt32(unit0 & 0x03ff) << 10) | UInt32(unit1 & 0x03ff))
		return .scalarValue(_UnicodeScalar(_unchecked: result))
	}
}

/// A codec for translating between Unicode scalar values and UTF-32 code
/// units.
public struct NewUTF32 : _UnicodeCodec {
	/// A type that can hold code unit values for this encoding.
	public typealias CodeUnit = UInt32

	/// Creates an instance of the UTF-32 codec.
	public init() {}

	/// Starts or continues decoding a UTF-32 sequence.
	///
	/// To decode a code unit sequence completely, call this method repeatedly
	/// until it returns `UnicodeDecodingResult.emptyInput`. Checking that the
	/// iterator was exhausted is not sufficient, because the decoder can store
	/// buffered data from the input iterator.
	///
	/// Because of buffering, it is impossible to find the corresponding position
	/// in the iterator for a given returned `UnicodeScalar` or an error.
	///
	/// The following example decodes the UTF-16 encoded bytes of a string
	/// into an array of `UnicodeScalar` instances. This is a demonstration
	/// only---if you need the Unicode scalar representation of a string, use
	/// its `unicodeScalars` view.
	///
	///     // UTF-32 representation of "✨Unicode✨"
	///     let codeUnits: [UTF32.CodeUnit] =
	///             [10024, 85, 110, 105, 99, 111, 100, 101, 10024]
	///
	///     var codeUnitIterator = codeUnits.makeIterator()
	///     var scalars: [UnicodeSca lar] = []
	///     var utf32Decoder = UTF32()
	///     Decode: while true {
	///         switch utf32Decoder.decode(&codeUnitIterator) {
	///         case .scalarValue(let v): scalars.append(v)
	///         case .emptyInput: break Decode
	///         case .error:
	///             print("Decoding error")
	///             break Decode
	///         }
	///     }
	///     print(scalars)
	///     // Prints "["\u{2728}", "U", "n", "i", "c", "o", "d", "e", "\u{2728}"]"
	///
	/// - Parameter next: An iterator of code units to be decoded. `next` must be
	///   the same iterator instance in repeated calls to this method. Do not
	///   advance the iterator or any copies of the iterator outside this
	///   method.
	/// - Returns: A `UnicodeDecodingResult` instance, representing the next
	///   Unicode scalar, an indication of an error, or an indication that the
	///   UTF sequence has been fully decoded.
	public mutating func decode<
		I : IteratorProtocol where I.Element == CodeUnit
  >(_ input: inout I) -> _UnicodeDecodingResult {
		return NewUTF32._decode(&input)
	}

	internal static func _decode<
		I : IteratorProtocol where I.Element == CodeUnit
  >(_ input: inout I) -> _UnicodeDecodingResult {
		guard let x = input.next() else { return .emptyInput }
		// Check code unit is valid: not surrogate-reserved and within range.
		guard _fastPath((x >> 11) != 0b1101_1 && x <= 0x10ffff)
			else { return .error }
		// x is a valid scalar.
		return .scalarValue(_UnicodeScalar(_unchecked: x))
	}
}

// Unchecked init to avoid precondition branches in hot code paths where we
// already know the value is a valid unicode scalar.
extension _UnicodeScalar {
	/// Create an instance with numeric value `value`, bypassing the regular
	/// precondition checks for code point validity.
	internal init(_unchecked value: UInt32) {
		_sanityCheck(value < 0xD800 || value > 0xDFFF,
		             "high- and low-surrogate code points are not valid Unicode scalar values")
		_sanityCheck(value <= 0x10FFFF, "value is outside of Unicode codespace")

		_value = value
	}
}

OldUTF.swift

/// A codec for translating between Unicode scalar values and UTF-8 code
/// units.
public struct OldUTF8 : _UnicodeCodec {
	// See Unicode 8.0.0, Ch 3.9, UTF-8.
	// http://www.unicode.org/versions/Unicode8.0.0/ch03.pdf

	/// A type that can hold code unit values for this encoding.
	public typealias CodeUnit = UInt8

	/// Creates an instance of the UTF-8 codec.
	public init() {}

	/// Lookahead buffer used for UTF-8 decoding.  New bytes are inserted at MSB,
	/// and bytes are read at LSB.  Note that we need to use a buffer, because
	/// in case of invalid subsequences we sometimes don't know whether we should
	/// consume a certain byte before looking at it.
	internal var _decodeBuffer: UInt32 = 0

	/// The number of bits in `_decodeBuffer` that are current filled.
	internal var _bitsInBuffer: UInt8 = 0

	/// Whether we have exhausted the iterator.  Note that this doesn't mean
	/// we are done decoding, as there might still be bytes left in the buffer.
	internal var _didExhaustIterator: Bool = false

	/// Starts or continues decoding a UTF-8 sequence.
	///
	/// To decode a code unit sequence completely, call this method repeatedly
	/// until it returns `UnicodeDecodingResult.emptyInput`. Checking that the
	/// iterator was exhausted is not sufficient, because the decoder can store
	/// buffered data from the input iterator.
	///
	/// Because of buffering, it is impossible to find the corresponding position
	/// in the iterator for a given returned `UnicodeScalar` or an error.
	///
	/// The following example decodes the UTF-8 encoded bytes of a string into an
	/// array of `UnicodeScalar` instances. This is a demonstration only---if
	/// you need the Unicode scalar representation of a string, use its
	/// `unicodeScalars` view.
	///
	///     let str = "✨Unicode✨"
	///     print(Array(str.utf8))
	///     // Prints "[226, 156, 168, 85, 110, 105, 99, 111, 100, 101, 226, 156, 168]"
	///
	///     var bytesIterator = str.utf8.makeIterator()
	///     var scalars: [UnicodeScalar] = []
	///     var utf8Decoder = UTF8()
	///     Decode: while true {
	///         switch utf8Decoder.decode(&bytesIterator) {
	///         case .scalarValue(let v): scalars.append(v)
	///         case .emptyInput: break Decode
	///         case .error:
	///             print("Decoding error")
	///             break Decode
	///         }
	///     }
	///     print(scalars)
	///     // Prints "["\u{2728}", "U", "n", "i", "c", "o", "d", "e", "\u{2728}"]"
	///
	/// - Parameter next: An iterator of code units to be decoded. `next` must be
	///   the same iterator instance in repeated calls to this method. Do not
	///   advance the iterator or any copies of the iterator outside this
	///   method.
	/// - Returns: A `UnicodeDecodingResult` instance, representing the next
	///   Unicode scalar, an indication of an error, or an indication that the
	///   UTF sequence has been fully decoded.
	public mutating func decode<
		I : IteratorProtocol where I.Element == CodeUnit
  >(_ next: inout I) -> _UnicodeDecodingResult {

		refillBuffer: if !_didExhaustIterator {
			// Bufferless ASCII fastpath.
			if _fastPath(_bitsInBuffer == 0) {
				if let codeUnit = next.next() {
					if codeUnit & 0x80 == 0 {
						return .scalarValue(_UnicodeScalar(_unchecked: UInt32(codeUnit)))
					}
					// Non-ASCII, proceed to buffering mode.
					_decodeBuffer = UInt32(codeUnit)
					_bitsInBuffer = 8
				} else {
					_didExhaustIterator = true
					return .emptyInput
				}
			} else if (_decodeBuffer & 0x80 == 0) {
				// ASCII in buffer.  We don't refill the buffer so we can return
				// to bufferless mode once we've exhausted it.
				break refillBuffer
			}
			// Buffering mode.
			// Fill buffer back to 4 bytes (or as many as are left in the iterator).
			_sanityCheck(_bitsInBuffer < 32)
			repeat {
				if let codeUnit = next.next() {
					// We use & 0x1f to make the compiler omit a bounds check branch.
					_decodeBuffer |= (UInt32(codeUnit) << UInt32(_bitsInBuffer & 0x1f))
					_bitsInBuffer = _bitsInBuffer &+ 8
				} else {
					_didExhaustIterator = true
					if _bitsInBuffer == 0 { return .emptyInput }
					break // We still have some bytes left in our buffer.
				}
			} while _bitsInBuffer < 32
		} else if _bitsInBuffer == 0 {
			return .emptyInput
		}

		// Decode one unicode scalar.
		// Note our empty bytes are always 0x00, which is required for this call.
		let (result, length) = UTF8._decodeOne(_decodeBuffer)

		// Consume the decoded bytes (or maximal subpart of ill-formed sequence).
		let bitsConsumed = 8 &* length
		_sanityCheck(1...4 ~= length && bitsConsumed <= _bitsInBuffer)
		// Swift doesn't allow shifts greater than or equal to the type width.
		// _decodeBuffer >>= UInt32(bitsConsumed) // >>= 32 crashes.
		// Mask with 0x3f to let the compiler omit the '>= 64' bounds check.
		_decodeBuffer = UInt32(truncatingBitPattern:
			UInt64(_decodeBuffer) >> (UInt64(bitsConsumed) & 0x3f))
		_bitsInBuffer = _bitsInBuffer &- bitsConsumed

		if _fastPath(result != nil) {
			return .scalarValue(_UnicodeScalar(_unchecked: result!))
		} else {
			return .error // Ill-formed UTF-8 code unit sequence.
		}
	}

	/// Attempts to decode a single UTF-8 code unit sequence starting at the LSB
	/// of `buffer`.
	///
	/// - Returns:
	///   - result: The decoded code point if the code unit sequence is
	///     well-formed; `nil` otherwise.
	///   - length: The length of the code unit sequence in bytes if it is
	///     well-formed; otherwise the *maximal subpart of the ill-formed
	///     sequence* (Unicode 8.0.0, Ch 3.9, D93b), i.e. the number of leading
	///     code units that were valid or 1 in case none were valid.  Unicode
	///     recommends to skip these bytes and replace them by a single
	///     replacement character (U+FFFD).
	///
	/// - Requires: There is at least one used byte in `buffer`, and the unused
	///   space in `buffer` is filled with some value not matching the UTF-8
	///   continuation byte form (`0b10xxxxxx`).
	public // @testable
	static func _decodeOne(_ buffer: UInt32) -> (result: UInt32?, length: UInt8) {
		// Note the buffer is read least significant byte first: [ #3 #2 #1 #0 ].

		if buffer & 0x80 == 0 { // 1-byte sequence (ASCII), buffer: [ … … … CU0 ].
			let value = buffer & 0xff
			return (value, 1)
		}

		// Determine sequence length using high 5 bits of 1st byte.  We use a
		// look-up table to branch less.  1-byte sequences are handled above.
		//
		//  case | pattern | description
		// ----------------------------
		//   00  |  110xx  | 2-byte sequence
		//   01  |  1110x  | 3-byte sequence
		//   10  |  11110  | 4-byte sequence
		//   11  |  other  | invalid
		//
		//                     11xxx      10xxx      01xxx      00xxx
		let lut0: UInt32 = 0b1011_0000__1111_1111__1111_1111__1111_1111
		let lut1: UInt32 = 0b1100_0000__1111_1111__1111_1111__1111_1111

		let index = (buffer >> 3) & 0x1f
		let bit0 = (lut0 >> index) & 1
		let bit1 = (lut1 >> index) & 1

		switch (bit1, bit0) {
		case (0, 0): // 2-byte sequence, buffer: [ … … CU1 CU0 ].
			// Require 10xx xxxx  110x xxxx.
			if _slowPath(buffer & 0xc0e0 != 0x80c0) { return (nil, 1) }
			// Disallow xxxx xxxx  xxx0 000x (<= 7 bits case).
			if _slowPath(buffer & 0x001e == 0x0000) { return (nil, 1) }
			// Extract data bits.
			let value = (buffer & 0x3f00) >> 8
				| (buffer & 0x001f) << 6
			return (value, 2)

		case (0, 1): // 3-byte sequence, buffer: [ … CU2 CU1 CU0 ].
			// Disallow xxxx xxxx  xx0x xxxx  xxxx 0000 (<= 11 bits case).
			if _slowPath(buffer & 0x00200f == 0x000000) { return (nil, 1) }
			// Disallow xxxx xxxx  xx1x xxxx  xxxx 1101 (surrogate code points).
			if _slowPath(buffer & 0x00200f == 0x00200d) { return (nil, 1) }
			// Require 10xx xxxx  10xx xxxx  1110 xxxx.
			if _slowPath(buffer & 0xc0c0f0 != 0x8080e0) {
				if buffer & 0x00c000 != 0x008000 { return (nil, 1) }
				return (nil, 2) // All checks on CU0 & CU1 passed.
			}
			// Extract data bits.
			let value = (buffer & 0x3f0000) >> 16
				| (buffer & 0x003f00) >> 2
				| (buffer & 0x00000f) << 12
			return (value, 3)

		case (1, 0): // 4-byte sequence, buffer: [ CU3 CU2 CU1 CU0 ].
			// Disallow xxxx xxxx  xxxx xxxx  xx00 xxxx  xxxx x000 (<= 16 bits case).
			if _slowPath(buffer & 0x00003007 == 0x00000000) { return (nil, 1) }
			// If xxxx xxxx  xxxx xxxx  xxxx xxxx  xxxx x1xx.
			if buffer & 0x00000004 == 0x00000004 {
				// Require xxxx xxxx  xxxx xxxx  xx00 xxxx  xxxx xx00 (<= 0x10FFFF).
				if _slowPath(buffer & 0x00003003 != 0x00000000) { return (nil, 1) }
			}
			// Require 10xx xxxx  10xx xxxx  10xx xxxx  1111 0xxx.
			if _slowPath(buffer & 0xc0c0c0f8 != 0x808080f0) {
				if buffer & 0x0000c000 != 0x00008000 { return (nil, 1) }
				// All other checks on CU0, CU1 & CU2 passed.
				if buffer & 0x00c00000 != 0x00800000 { return (nil, 2) }
				return (nil, 3)
			}
			// Extract data bits.
			let value = (buffer & 0x3f000000) >> 24
				| (buffer & 0x003f0000) >> 10
				| (buffer & 0x00003f00) << 4
				| (buffer & 0x00000007) << 18
			return (value, 4)

		default: // Invalid sequence (CU0 invalid).
			return (nil, 1)
		}
	}
}

/// A codec for translating between Unicode scalar values and UTF-16 code
/// units.
public struct OldUTF16 : _UnicodeCodec {
	/// A type that can hold code unit values for this encoding.
	public typealias CodeUnit = UInt16

	/// Creates an instance of the UTF-16 codec.
	public init() {}

	/// A lookahead buffer for one UTF-16 code unit.
	internal var _decodeLookahead: UInt32 = 0

	/// Flags with layout: `0b0000_00xy`.
	///
	/// `y` is the EOF flag.
	///
	/// `x` is set when `_decodeLookahead` contains a code unit.
	internal var _lookaheadFlags: UInt8 = 0

	/// Starts or continues decoding a UTF-16 sequence.
	///
	/// To decode a code unit sequence completely, call this method repeatedly
	/// until it returns `UnicodeDecodingResult.emptyInput`. Checking that the
	/// iterator was exhausted is not sufficient, because the decoder can store
	/// buffered data from the input iterator.
	///
	/// Because of buffering, it is impossible to find the corresponding position
	/// in the iterator for a given returned `UnicodeScalar` or an error.
	///
	/// The following example decodes the UTF-16 encoded bytes of a string into an
	/// array of `UnicodeScalar` instances. This is a demonstration only---if
	/// you need the Unicode scalar representation of a string, use its
	/// `unicodeScalars` view.
	///
	///     let str = "✨Unicode✨"
	///     print(Array(str.utf16))
	///     // Prints "[10024, 85, 110, 105, 99, 111, 100, 101, 10024]"
	///
	///     var codeUnitIterator = str.utf16.makeIterator()
	///     var scalars: [UnicodeScalar] = []
	///     var utf16Decoder = UTF16()
	///     Decode: while true {
	///         switch utf16Decoder.decode(&codeUnitIterator) {
	///         case .scalarValue(let v): scalars.append(v)
	///         case .emptyInput: break Decode
	///         case .error:
	///             print("Decoding error")
	///             break Decode
	///         }
	///     }
	///     print(scalars)
	///     // Prints "["\u{2728}", "U", "n", "i", "c", "o", "d", "e", "\u{2728}"]"
	///
	/// - Parameter next: An iterator of code units to be decoded. `next` must be
	///   the same iterator instance in repeated calls to this method. Do not
	///   advance the iterator or any copies of the iterator outside this
	///   method.
	/// - Returns: A `UnicodeDecodingResult` instance, representing the next
	///   Unicode scalar, an indication of an error, or an indication that the
	///   UTF sequence has been fully decoded.
	public mutating func decode<
		I : IteratorProtocol where I.Element == CodeUnit
  >(_ input: inout I) -> _UnicodeDecodingResult {
		if _lookaheadFlags & 0b01 != 0 {
			return .emptyInput
		}

		// Note: maximal subpart of ill-formed sequence for UTF-16 can only have
		// length 1.  Length 0 does not make sense.  Neither does length 2 -- in
		// that case the sequence is valid.

		var unit0: UInt32
		if _fastPath(_lookaheadFlags & 0b10 == 0) {
			if let first = input.next() {
				unit0 = UInt32(first)
			} else {
				// Set EOF flag.
				_lookaheadFlags |= 0b01
				return .emptyInput
			}
		} else {
			// Fetch code unit from the lookahead buffer and note this fact in flags.
			unit0 = _decodeLookahead
			_lookaheadFlags &= 0b01
		}

		// A well-formed pair of surrogates looks like this:
		// [1101 10ww wwxx xxxx] [1101 11xx xxxx xxxx]

		if _fastPath((unit0 >> 11) != 0b1101_1) {
			// Neither high-surrogate, nor low-surrogate -- sequence of 1 code unit,
			// decoding is trivial.
			return .scalarValue(_UnicodeScalar(unit0))
		}

		if _slowPath((unit0 >> 10) == 0b1101_11) {
			// `unit0` is a low-surrogate.  We have an ill-formed sequence.
			return .error
		}

		// At this point we know that `unit0` is a high-surrogate.

		var unit1: UInt32
		if let second = input.next() {
			unit1 = UInt32(second)
		} else {
			// EOF reached.  Set EOF flag.
			_lookaheadFlags |= 0b01

			// We have seen a high-surrogate and EOF, so we have an ill-formed
			// sequence.
			return .error
		}

		if _fastPath((unit1 >> 10) == 0b1101_11) {
			// `unit1` is a low-surrogate.  We have a well-formed surrogate pair.

			let result = 0x10000 + (((unit0 & 0x03ff) << 10) | (unit1 & 0x03ff))
			return .scalarValue(_UnicodeScalar(result))
		}

		// Otherwise, we have an ill-formed sequence.  These are the possible
		// cases:
		//
		// * `unit1` is a high-surrogate, so we have a pair of two high-surrogates.
		//
		// * `unit1` is not a surrogate.  We have an ill-formed sequence:
		//   high-surrogate followed by a non-surrogate.

		// Save the second code unit in the lookahead buffer.
		_decodeLookahead = unit1
		_lookaheadFlags |= 0b10
		return .error
	}
}

/// A codec for translating between Unicode scalar values and UTF-32 code
/// units.
public struct OldUTF32 : _UnicodeCodec {
  /// A type that can hold code unit values for this encoding.
  public typealias CodeUnit = UInt32

  /// Creates an instance of the UTF-32 codec.
  public init() {}

  /// Starts or continues decoding a UTF-32 sequence.
  ///
  /// To decode a code unit sequence completely, call this method repeatedly
  /// until it returns `UnicodeDecodingResult.emptyInput`. Checking that the
  /// iterator was exhausted is not sufficient, because the decoder can store
  /// buffered data from the input iterator.
  ///
  /// Because of buffering, it is impossible to find the corresponding position
  /// in the iterator for a given returned `UnicodeScalar` or an error.
  ///
  /// The following example decodes the UTF-16 encoded bytes of a string
  /// into an array of `UnicodeScalar` instances. This is a demonstration
  /// only---if you need the Unicode scalar representation of a string, use
  /// its `unicodeScalars` view.
  ///
  ///     // UTF-32 representation of "✨Unicode✨"
  ///     let codeUnits: [UTF32.CodeUnit] =
  ///             [10024, 85, 110, 105, 99, 111, 100, 101, 10024]
  ///
  ///     var codeUnitIterator = codeUnits.makeIterator()
  ///     var scalars: [UnicodeScalar] = []
  ///     var utf32Decoder = UTF32()
  ///     Decode: while true {
  ///         switch utf32Decoder.decode(&codeUnitIterator) {
  ///         case .scalarValue(let v): scalars.append(v)
  ///         case .emptyInput: break Decode
  ///         case .error:
  ///             print("Decoding error")
  ///             break Decode
  ///         }
  ///     }
  ///     print(scalars)
  ///     // Prints "["\u{2728}", "U", "n", "i", "c", "o", "d", "e", "\u{2728}"]"
  ///
  /// - Parameter next: An iterator of code units to be decoded. `next` must be
  ///   the same iterator instance in repeated calls to this method. Do not
  ///   advance the iterator or any copies of the iterator outside this
  ///   method.
  /// - Returns: A `UnicodeDecodingResult` instance, representing the next
  ///   Unicode scalar, an indication of an error, or an indication that the
  ///   UTF sequence has been fully decoded.
  public mutating func decode<I : IteratorProtocol>(
    _ input: inout I
  ) -> _UnicodeDecodingResult where I.Element == CodeUnit {
    return OldUTF32._decode(&input)
  }

  internal static func _decode<I : IteratorProtocol>(
    _ input: inout I
  ) -> _UnicodeDecodingResult where I.Element == CodeUnit {
    guard let x = input.next() else { return .emptyInput }
    if _fastPath((x >> 11) != 0b1101_1 && x <= 0x10ffff) {
      return .scalarValue(_UnicodeScalar(x))
    } else {
      return .error
    }
  }
}

UnicodeCodec.swift

// Conversions between different Unicode encodings.  Note that UTF-16 and
// UTF-32 decoding are *not* currently resilient to erroneous data.

/// The result of one Unicode decoding step.
///
/// Each `UnicodeDecodingResult` instance can represent a Unicode scalar value,
/// an indication that no more Unicode scalars are available, or an indication
/// of a decoding error.
///
/// - SeeAlso: `UnicodeCodec.decode(next:)`
public enum _UnicodeDecodingResult : Equatable {
	/// A decoded Unicode scalar value.
	case scalarValue(_UnicodeScalar)

	/// An indication that no more Unicode scalars are available in the input.
	case emptyInput

	/// An indication of a decoding error.
	case error
}

public func == (
	lhs: _UnicodeDecodingResult,
	rhs: _UnicodeDecodingResult
	) -> Bool {
	switch (lhs, rhs) {
	case (.scalarValue(let lhsScalar), .scalarValue(let rhsScalar)):
		return lhsScalar == rhsScalar
	case (.emptyInput, .emptyInput):
		return true
	case (.error, .error):
		return true
	default:
		return false
	}
}

/// A Unicode encoding form that translates between Unicode scalar values and
/// form-specific code units.
///
/// The `UnicodeCodec` protocol declares methods that decode code unit
/// sequences into Unicode scalar values and encode Unicode scalar values
/// into code unit sequences. The standard library implements codecs for the
/// UTF-8, UTF-16, and UTF-32 encoding schemes as the `UTF8`, `UTF16`, and
/// `UTF32` types, respectively. Use the `UnicodeScalar` type to work with
/// decoded Unicode scalar values.
///
/// - SeeAlso: `UTF8`, `UTF16`, `UTF32`, `UnicodeScalar`
public protocol _UnicodeCodec {

	/// A type that can hold code unit values for this encoding.
	associatedtype CodeUnit

	/// Creates an instance of the codec.
	init()

	/// Starts or continues decoding a code unit sequence into Unicode scalar
	/// values.
	///
	/// To decode a code unit sequence completely, call this method repeatedly
	/// until it returns `UnicodeDecodingResult.emptyInput`. Checking that the
	/// iterator was exhausted is not sufficient, because the decoder can store
	/// buffered data from the input iterator.
	///
	/// Because of buffering, it is impossible to find the corresponding position
	/// in the iterator for a given returned `UnicodeScalar` or an error.
	///
	/// The following example decodes the UTF-8 encoded bytes of a string into an
	/// array of `UnicodeScalar` instances:
	///
	///     let str = "✨Unicode✨"
	///     print(Array(str.utf8))
	///     // Prints "[226, 156, 168, 85, 110, 105, 99, 111, 100, 101, 226, 156, 168]"
	///
	///     var bytesIterator = str.utf8.makeIterator()
	///     var scalars: [UnicodeScalar] = []
	///     var utf8Decoder = UTF8()
	///     Decode: while true {
	///         switch utf8Decoder.decode(&bytesIterator) {
	///         case .scalarValue(let v): scalars.append(v)
	///         case .emptyInput: break Decode
	///         case .error:
	///             print("Decoding error")
	///             break Decode
	///         }
	///     }
	///     print(scalars)
	///     // Prints "["\u{2728}", "U", "n", "i", "c", "o", "d", "e", "\u{2728}"]"
	///
	/// - Parameter next: An iterator of code units to be decoded. `next` must be
	///   the same iterator instance in repeated calls to this method. Do not
	///   advance the iterator or any copies of the iterator outside this
	///   method.
	/// - Returns: A `UnicodeDecodingResult` instance, representing the next
	///   Unicode scalar, an indication of an error, or an indication that the
	///   UTF sequence has been fully decoded.
	mutating func decode<I : IteratorProtocol>(
		_ next: inout I
  ) -> _UnicodeDecodingResult where I.Element == CodeUnit
}

UnicodeScalar.swift

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// UnicodeScalar Type
//===----------------------------------------------------------------------===//

/// A Unicode scalar value.
///
/// The `UnicodeScalar` type, representing a single Unicode scalar value, is
/// the element type of a string's `unicodeScalars` collection.
///
/// You can create a `UnicodeScalar` instance by using a string literal that
/// contains a single character representing exactly one Unicode scalar value.
///
///     let letterK: UnicodeScalar = "K"
///     let kim: UnicodeScalar = "김"
///     print(letterK, kim)
///     // Prints "K 김"
///
/// You can also create Unicode scalar values directly from their numeric
/// representation.
///
///     let airplane = UnicodeScalar(9992)
///     print(airplane)
///     // Prints "✈︎"
@_fixed_layout
public struct _UnicodeScalar {

	var _value: UInt32

	/// A numeric representation of the Unicode scalar.
	public var value: UInt32 { return _value }

	/// Creates a Unicode scalar with the specified value.
	///
	/// Do not call this initializer directly. It may be used by the compiler
	/// when you use a string literal to initialize a `UnicodeScalar` instance.
	///
	///     let letterK: UnicodeScalar = "K"
	///     print(letterK)
	///     // Prints "K"
	///
	/// In this example, the assignment to the `letterK` constant is handled by
	/// this initializer behind the scenes.
	@_transparent
	public init(unicodeScalarLiteral value: _UnicodeScalar) {
		self = value
	}

	/// Creates a Unicode scalar with the specified numeric value.
	///
	/// For example, the following code sample creates a `UnicodeScalar` instance
	/// with a value of an emoji character:
	///
	///     let codepoint: UInt32 = 127881
	///     let emoji = UnicodeScalar(codepoint)
	///     print(emoji)
	///     // Prints "🎉"
	///
	/// - Parameter v: The Unicode code point to use for the scalar. `v` must be
	///   a valid Unicode scalar value, in the range `0...0xD7FF` or
	///   `0xE000...0x10FFFF`.
	public init(_ v: UInt32) {
		// Unicode 6.3.0:
		//
		//     D9.  Unicode codespace: A range of integers from 0 to 10FFFF.
		//
		//     D76. Unicode scalar value: Any Unicode code point except
		//     high-surrogate and low-surrogate code points.
		//
		//     * As a result of this definition, the set of Unicode scalar values
		//     consists of the ranges 0 to D7FF and E000 to 10FFFF, inclusive.

		_precondition(v < 0xD800 || v > 0xDFFF,
		              "high- and low-surrogate code points are not valid Unicode scalar values")
		_precondition(v <= 0x10FFFF, "value is outside of Unicode codespace")

		self._value = v
	}

	/// Creates a Unicode scalar with the specified numeric value.
	///
	/// For example, the following code sample creates a `UnicodeScalar` instance
	/// with a value of `밥`, the Korean word for rice:
	///
	///     let codepoint: UInt16 = 48165
	///     let bap = UnicodeScalar(codepoint)
	///     print(bap)
	///     // Prints "밥"
	///
	/// - Parameter v: The Unicode code point to use for the scalar. `v` must be
	///   a valid Unicode scalar value, in the range `0...0xD7FF` or
	///   `0xE000...0xFFFF`.
	public init(_ v: UInt16) {
		self = _UnicodeScalar(UInt32(v))
	}

	/// Creates a Unicode scalar with the specified numeric value.
	///
	/// For example, the following code sample creates a `UnicodeScalar` instance
	/// with a value of `7`:
	///
	///     let codepoint: UInt8 = 55
	///     let seven = UnicodeScalar(codepoint)
	///     print(seven)
	///     // Prints "7"
	///
	/// - Parameter v: The code point to use for the scalar.
	public init(_ v: UInt8) {
		self = _UnicodeScalar(UInt32(v))
	}

	/// Creates a duplicate of the given Unicode scalar.
	public init(_ v: _UnicodeScalar) {
		// This constructor allows one to provide necessary type context to
		// disambiguate between function overloads on 'String' and 'UnicodeScalar'.
		self = v
	}
}

extension _UnicodeScalar : Hashable {
	/// The Unicode scalar's hash value.
	///
	/// Hash values are not guaranteed to be equal across different executions of
	/// your program. Do not save hash values to use during a future execution.
	public var hashValue: Int {
		return Int(self.value)
	}
}

extension _UnicodeScalar {
	/// Creates a Unicode scalar with the specified numeric value.
	///
	/// For example, the following code sample creates a `UnicodeScalar` instance
	/// with a value of an emoji character:
	///
	///     let codepoint = 127881
	///     let emoji = UnicodeScalar(codepoint)
	///     print(emoji)
	///     // Prints "🎉"
	///
	/// - Parameter v: The Unicode code point to use for the scalar. `v` must be
	///   a valid Unicode scalar value, in the ranges `0...0xD7FF` or
	///   `0xE000...0x10FFFF`.
	public init(_ v: Int) {
		self = _UnicodeScalar(UInt32(v))
	}
}

extension UInt8 {
	/// Construct with value `v.value`.
	///
	/// - Precondition: `v.value` can be represented as ASCII (0..<128).
	public init(ascii v: _UnicodeScalar) {
		_precondition(v.value < 128,
		              "Code point value does not fit into ASCII")
		self = UInt8(v.value)
	}
}
extension UInt32 {
	/// Construct with value `v.value`.
	///
	/// - Precondition: `v.value` can be represented as UInt32.
	public init(_ v: _UnicodeScalar) {
		self = v.value
	}
}
extension UInt64 {
	/// Construct with value `v.value`.
	///
	/// - Precondition: `v.value` can be represented as UInt64.
	public init(_ v: _UnicodeScalar) {
		self = UInt64(v.value)
	}
}

extension _UnicodeScalar : Comparable, Equatable {
}

public func ==(lhs: _UnicodeScalar, rhs: _UnicodeScalar) -> Bool {
	return lhs.value == rhs.value
}

public func <(lhs: _UnicodeScalar, rhs: _UnicodeScalar) -> Bool {
	return lhs.value < rhs.value
}

extension _UnicodeScalar {
	struct UTF16View {
		var value: _UnicodeScalar
	}

	var utf16: UTF16View {
		return UTF16View(value: self)
	}
}