Intel includes in its recent processors a powerful set of instructions
capable of processing 512-bit registers with a single instruction (AVX-512).
Some of these instructions have no equivalent in earlier instruction sets.
We leverage these instructions to efficiently transcode strings between the most
common formats: UTF-8 and UTF-16.
With our novel algorithms, we are often twice as fast as the previous best solutions.
For example, we transcode Chinese text from UTF-8 to UTF-16 at more than
5 using fewer
than 2 CPU instructions per character.
To ensure reproducibility, we make our software freely available as an open source library. Our library is part of the popular Node.js JavaScript runtime.

§ INTRODUCTION

Computers store strings of text as arrays of bytes. Unicode is a standard for representing text as a sequence of universal characters represented by code points. Code points are stored as short sequences of bytes according to a given unicode transformation format (UTF), the most popular being UTF-8 and UTF-16.
Not all sequence of bytes are valid UTF-8 or UTF-16 strings [Keiser and Lemire, 2021].
Validation is required to detect incorrectly encoded or corrupted text before it is processed.

We often need to transcode strings between the two formats.
For example, a database might store data in UTF-16 and yet the
programmer might need to produce UTF-8 strings for a web site.
Thankfully, transcoding is relatively efficient.
Conventional transcoders often achieve a throughput between 0.51.5 on commodity processors [Lemire and Muła, 2022] (cf.  <ref>).[The speed is measured by taking the size of the input and dividing by the time elapsed.] Yet this falls far below the sequential-read speed of a fast disk (e.g., 5) or the throughput of a fast network connection.

IBM mainframes based on z/Architecture provide special-purposes instructions named “convert utf-8 to utf-16” and “convert utf-16 to utf-8” for translation between the two encodings [zpo, 2022].
By virtue of being implemented in hardware, these exceed 10 processing speed for typical inputs.
While commodity processors currently lack such dedicated instructions, they can benefit from single-instruction-multiple-data (SIMD) instructions.
Unlike conventional instructions which operate on a single machine word (e. g. 64 bits), these SIMD instructions operate on larger registers (128 bits, 256 bits, …) representing vectors of numbers.
A single SIMD instruction may add eight pairs of 16-bit words at once.
We can transcode gigabytes of text per second [Lemire and Muła, 2022] by a deliberate use  of conventional SIMD instructions (e.g., ARM NEON, SSE, AVX2).

In recent years, Intel introduced new SIMD instruction sets operating over registers as wide as 512 bits.
If Intel had merely doubled the width of the registers, there would be little need for further work on our part.
However, our experience suggests that to fully benefit from AVX-512 instructions, we need to use adapted algorithms [Muła and Lemire, 2020].
Indeed, while AVX-512 instructions benefit from wider registers, Intel has also added many more instructions than what is typically found in SIMD instruction sets.
There is also a slightly different model: AVX-512 instruction may consume or generate masks in mask registers which have no equivalent in prior commodity instruction sets. In AVX-512, a mask is conceptually an array of 8, 16, 32, or 64 bits corresponding to vectors of 8, 16, 32, or 64 elements.

We present novel transcoding functions using AVX-512 instructions. On average, we are roughly twice as fast as the previous fastest functions [Lemire and Muła, 2022] on commodity processors.

[Bit-by-bit correspondence between UTF-16 and UTF-8 encodings in the four possible cases. The bits are named  to  starting at the least significant bits with $\mathtt{0vuts}=\mathtt{WVUTS}-1$.]

case   UTF-16   UTF-8

ASCII   000000000GFEDCBA   0GFEDCBA

2-byte   00000LKJHGFEDCBA   110LKJHG10FEDCBA

3-byte   RQPNMLKJHGFEDCBA   1110RQPN10MLKJHG10FEDCBA

4-byte   110110vutsRQPNML   11110WVU10TSRQPN10MLKJHG10FEDCBA

[Examples of matched code-point values in UTF-32, UTF-16LE and UTF-8. For 10000 and 10FFFF, UTF-16 requires a surrogate pair. ]

codepoint   UTF-16   UTF-8

0   0000000000000000   00000000

7F    0000000001111111   01111111

80   0000000010000000   1100001010000000

7FF   0000011111111111   1101111110111111

800   0000100000000000   111000001010000010000000

FFFF   1111111111111111   111011111011111110111111

10000   1101100000000000   11110000100100001000000010000000

10FFFF   1101101111111111   11110100100011111011111110111111

Correspondence between UTF-16 and UTF-8. Format-specific prescribed bits (tag bits) are underlined.

§ UNICODE AND ITS ENCODINGS

Unicode is a standard based on the Universal Character Set (UCS).
An extension to ASCII, UCS is a character set whose characters (called universal characters) have code points numbered from 0[ followed by a hexadecimal number is notation for a universal character's code point.] to 10FFFF (decimal 1114111).
These code points are organized into 17 planes of 65536 characters each, with the first plane 0000ffff being called the Basic Multilingual Plane (BMP).

Code points in the range – are reserved for surrogates used in the UTF-16 encoding and do not represent universal characters.

Unlike simpler character sets like ASCII, universal characters are seldomly stored directly as integers, as such a storage format is wasteful and incompatible to existing byte-oriented environments.
Instead, several Unicode Transformation Formats (UTF) are employed to store and process universal characters, depending on the use case at hand.

A Unicode Transformation Format transforms each universal character into a sequence of integers, with the size of the integer being dependent on the format.
Popular Unicode Transformation Formats include:

UTF-32 representing each universal character as a 32-bit integer.  Mainly used as an internal representation.

UTF-16 representing each universal character as one or two 16-bit integers [Hoffman and Yergeau, 2000].  All code-point values up to FFFF are stored as 2-byte integer values directly. Otherwise we use surrogate pairs: two consecutive 2-byte values, each storing 10 bits of the codepoint.  Used by Java, Windows NT, databases, binary protocols, and others.

UTF-8 representing each universal character as 1–4 bytes [Yergeau, 2003].  An extension to ASCII, UTF-8 is by far the most popular text encoding on the World Wide Web.

Though our software work covers many cases (from UTF-8 to UTF-16 or UTF-32, from UTF-16 to UTF-8 or UTF-32, and so forth), we study the two most difficult  cases: from UTF-8 to UTF-16 and back.

Multi-byte words in computers representing numerical
values can be stored in either
little-endian format or big-endian format, depending on whether the first byte is the least significant or the most significant.
Unicode Transformation Formats representing characters in units larger than bytes are subject to endianess.
If the endianess is not known from the context[Big endian is the prescribed default byte order [Hoffman and Yergeau, 2000], although it is less common.], it can be given by adding a LE or BE suffix to the name of the Unicode Transformation Format, giving e. g. UTF-16BE or UTF-32LE.
We can reverse the order of the bytes—between big and little endian—at high speed: e.g., using one instruction per 64 bytes.
For simplicity, we  present our results on UTF-8 and UTF-16LE.

§.§ UTF-16

When the Universal Character Set was initially defined, it was meant to be a 16-bit character set with UTF-16 being its natural encoding, representing each universal character in one 16-bit word.
It was later realized that 65536 code points are insufficient to represent the writing systems of the world's many cultures, especially when having to account for over 50000 Chinese, Japanese, and Korean ideographs.
UCS was therefore extended past the Basic Multilingual Plane to code points up to 10FFFF and UTF-16 retrofitted with a surrogate mechanism to permit representation of these newly added characters.

UTF-16 is a versatile Unicode Transformation Format as it permits (absent surrogates) easy processing of text in many popular languages, while not being as memory-hungry as UTF-32.
It is widely used in databases and binary file formats and is the preferred internal text representation on Windows NT.
Nevertheless, with the advent and growing popularity of universal characters outside of the Basic Multilingual Plane, UTF-16 has been steadily declining in use.

Despite big-endian byte order being prescribed for UTF-16, the little-endian variant UTF-16LE is more commonly encountered under the influence of x86's little-endian orientation.
A common convention to deal with this ambiguity is to prefix UTF-16 encoded documents with the byte order mark (BOM) FEFF.[FEFF only has this function as the first character of a document.  In other positions, it should be treated as an ordinary universal character and must not be stripped or altered.]
Its byte-swapped counterpart FFFE is a reserved “uncharacter” and should not occur in Unicode text.
If a UTF-16 encoded document begins with FFFE, it can thus be assumed to be in wrong byte order, permitting automatic byte-order detection in many situations.
Our algorithms do not make use of this convention and strictly assume UTF-16LE throughout.
A BOM is neither generated, nor checked for, nor stripped.

As illustrated in the “UTF-16” column of Fig. <ref>, code points in the Basic Multilingual Plane are represented as themselves.
Code points outside of this plane have  subtracted from them (the surrogate plane shift), yielding a 20-bit number.
This number is split into two 10-bit halves.
The high half is tagged with , yielding a high surrogate.
Likewise, the low half is tagged with , yielding a low surrogate.
The character is then encoded by giving its high surrogate, directly followed by its low surrogate.
It is for this purpose that code points in the range – do not represent universal characters.

Decoding UTF-16 is a matter of joining the bits of surrogate pairs, leaving Basic-Multilingual-Plane characters unchanged.
Care must be taken to validate that each high surrogate is succeeded by a low surrogate and vice versa.
With this sequencing requirement ensured, all UTF-16 sequences are valid and have a 1:1 mapping to code points.

Types of UTF-8 bytes with tag bits underlined.

type   range   pattern

ASCII lead byte   –

continuation byte   –

2-byte lead byte   –

3-byte lead byte   –

4-byte lead byte   –

§.§ UTF-8

The most popular Unicode Transformation Format is UTF-8, representing each universal character as a sequence of 1–4 bytes.
Replacing the earlier UTF-1, the format was designed to be backwards-compatible to ASCII while also being safe for use in UNIX file names, and comes with many other desirable features.
Under many circumstances, UTF-8 text can be processed as if it was a conventional ASCII-based 8-bit encoding like those of the ISO-8859 family.
This includes common applications like concatenation, substring search, field-splitting (with ASCII characters or UTF-8 strings for separators), and collation, rendering it the most popular UTF.

UTF-8 can be seen as an extension to ASCII, where each ASCII character (007F) is represented as itself with other characters being represented by sequences of bytes in the range – (cf. Table <ref>).
Such sequences start with a lead byte ([ and  would introduce 2-byte sequences corresponding to ASCII characters, which are encoded as single bytes instead.]–) indicating the length of the sequence in its tag bits, followed by 1–3 continuation bytes (–), making the encoding stateless, and self-synchronizing.

The details are summarized in the “UTF-8” column of Fig. <ref>:
The bits of the code point are numbered – starting at the least significant bit.
For each of the four possible cases (the ASCII/1-byte case, the 2-byte case, the 3-byte case, and the 4-byte case[the 1–3-byte cases represent Basic-Multilingual-Plane characters, the 4-byte case corresponds to characters represented as surrogate pairs in UTF-16.]), the bits of the code point are copied into the lead and continuation bytes as indicated in the figure.
Tag bits are applied (underlined in Fig. <ref>) to distinguish ASCII, lead, and continuation bytes.

For many universal characters, more than one encoding seems to be possible according to the figure.
However, only the shortest possible encoding for each character is permitted to ensure uniqueness of the encoding.
While 4-byte sequences could encode code points in excess of 10FFFF, such sequences are not legal either.
The bytes , , and – are thus not used by UTF-8.

Decoding UTF-8 begins by looking at the tag bits to tell the start and length of each sequence.
Then, the code point is assembled from the payload of these bytes.
A critical part in decoding UTF-8 is validation, especially against overly-long sequences and illegal code points (surrogates, code points greater than ).
In the algorithm presented in  <ref> we demonstrate how decoding UTF-8 with comprehensive validation and then reencoding it into UTF-16 can be implemented efficiently, leveraging AVX-512 instructions.

Summary of notation

expression     description
$\lnot a$   bitwise complement of $a$

$\ctz(a)$   number of trailing zeroes in $a$

$\width(a)$   number of bits needed to represent $a$

$\popcount(a)$   number of bits set in $a$

$\pext(a,b)$   the bits given in $a$ extracted from $b$

$\pdep(a,b)$   $b$ deposited into the bits given in $a$

$\compress(m, v)$   vector $v$ compressed by mask $m$

$a+b$   sum of $a$ and $b$

$a\ll b$   $a$ logically shifted to the left by $b$ places

$a\gg b$   $a$ logically shifted to the right by $b$ places

$a=b$   mask indicating elements of $a$ equal to those of $b$

$a\land b$   bitwise and of $a$ and $b$

$a\lor b$   bitwise or of $a$ and $b$

$a\oplus b$   bitwise exclusive-or of $a$ and $b$

$a\mathrel ?b:c$   ternary operator; equal to $a\land b\lor\lnot a\land c$

§ RELATED WORK

There are relatively few academic publications on Unicode string processing using SIMD instructions.
Cameron [Cameron, 2008] proposed a  UTF-8 to UTF-16 transcoder using SIMD instruction using bit streams. A bit stream is a transposition on the character inputs. For example, from 128 bytes of data, we produce eight 128-bit registers with the first register containing the most significant bits of each input byte, and the last register containing the least significant bit of each input byte. The transcoding from UTF-8 to UTF-16 is done in this bit stream form with a final phase where unused bytes are removed.  Inoue et al. [Inoue et al., 2008] presented a limited UTF-8 to UTF-16 transcoder which lacked validation and could not handle 4-byte UTF-8 characters. They rely on a 105 lookup table.

Lemire and Muła [Lemire and Muła, 2022] presented a generic approach that does full UTF-8 to UTF-16 and UTF-16 to UTF-8 transcoding, with validation. Their UTF-8 to UTF-16 transcoding function is similar in principle to the strategy used by Inoue et al. [Inoue et al., 2008] in that they
rely on the presence of instructions to quickly permute bytes within a register in an arbitrary manner, based on a lookup table.
The  accelerated  UTF-8 to UTF-16 transcoding algorithm  processes up to 12 input UTF-8 bytes at a time. Given the input bytes, it finds beginning of each character, forming a 12-bit word which is used as a key in a 1024-entry table. Each entry in the table contains the number of UTF-8 bytes to consume and an index into another table where we find shuffle masks. The tables use about 11.
The shuffle masks are applied to the 12 input bytes to form a vector register that can be transformed efficiently. This 12-byte routine works within
64-byte blocks. The 64-byte blocks are validated using a fast technique [Keiser and Lemire, 2021].
Their UTF-16 to UTF-8 algorithm iteratively reads a block of input bytes in a SIMD register.
Depending of the values of 16-bit words, the algorithm uses one of several paths. E.g., if all 16-bit words are in the range 000007ff, the 16-bit words are converted to 32-bit words to ultimately produce 1-byte, 2-byte or 3-byte characters. A series of lookup tables allow the efficient permutations, using a total of 8.5.

Gatilov [Gatilov, 2012] produced one of the best and most complete software library for Unicode transcoding (utf8lut). It is similar in spirit to the work of Lemire and Muła [Lemire and Muła, 2022], but utf8lut requires larger tables: 2 for the UTF-8 to UTF-16 transcoder and 16 for the UTF-16 to UTF-8 transcoder.

Unlike this prior work, our proposals do not require lookup tables. This is possible through the use of novel compression instructions introduced with AVX-512VBMI2 (see  <ref>, Tbl. <ref>), allowing us to move bytes to the right places within registers entirely in hardware, without in-memory tables.

§ NOTATIONAL CONVENTIONS

In the algorithms described below, all logical symbols refer to bitwise logic.
Comparisons are performed between corresponding elements of vectors, yielding a bit mask of those elements for which the comparison holds.
All arithmetic operations, shifts, and comparisons are performed on unsigned numbers.
The width of the number depends on the vector used.

As a general convention, scalars, vectors of bytes, and masks derived from them are indicated with lowercase letters.
Vectors of 16- or 32-bit words are indicated with uppercase letters.[The convention attempts to underline that byte vectors correspond to UTF-8 whereas word vectors correspond to UTF-16.]
The symbol $n$ is number of bytes in a vector; for AVX-512 it is
This convention permits us to explain the algorithms in terms of AVX-512 instructions while giving generic formulæ potentially applicable to other future instruction sets.

The operator precedence follows C precedence rules with

\begin{equation*}
a+b\ll c=d\land e\lor f
\end{equation*}

being parsed as

\begin{equation*}
((((a+b)\ll c)=d)\land e)\lor f.
\end{equation*}

Table <ref> gives a list of symbols used in decreasing order of precedence.

§.§ Mask Operations

Masks are conceptually arrays of bits—containing between 8 and 64 bits—meant
to be used in conjunction with vectors having the same number of elements.
For example, byte masks (noted $m_1, m_{234},\ldots$) may contain 64 bits if  they correspond
to vectors of 64 bytes. We also have word masks (e.g., $M_3$) containing 16 bits when they corresponding to 512-bit vectors of 32-bit values. See Appendices <ref> and <ref> for detailed lists of our masks and other variables.
We operate on masks as if they were unsigned integer values: $m_{+3}=m_4\ll3$ means that the whole mask $m_4$ is shifted to the left by three places to give $m_{+3}$; the 64 individual mask bits are always either 0 or 1.  The logical operations
or ($\lor$),  and ($\land$) and not ($\lnot$) are applied bitwise. We have that $m=0$ sets all bits to zero whereas $m=\lnot0$ sets all bits to one.

In practice, the processor has several instructions dedicated to AVX-512 mask registers (e. g., , , ).  Mask registers can be converted back and forth to general-purpose registers as needed—with the caveat that the conversion from mask registers to general-purpose registers may have a high latency (e. g., 3 cycles).

§.§ Vector Operations

When operating on vectors, equations have to be read as “SIMD formulæ” applying element-by-element.
For example, we write

\begin{equation*}
\end{equation*}

to mean “each element of $w$ is set to the sum of the corresponding elements in $a$ and $b$ if the corresponding bit is set in $m$ or to $c$ otherwise.”
With an explicit index $i=0\ldots n-1$, the previous expression could be written as

\begin{equation*}
w[i]=m\land1\ll i\mathrel ?a[i]+b[i]:c[i]\quad\mbox{for }i=0,1,\ldots,n-1.
\end{equation*}

We believe that the presentation as “SIMD formulæ” is easier to understand and prefer it where possible.
Explicit indices are only used when permutations are involved.
For example, we write

\begin{equation*}
\end{equation*}

to mean “$w$ is $v$ permuted by the index vector $p$.”

Conversions from one element size to another are not explicitly written out; watch the letter case of the variables used to see when this happens.
All such conversions are zero-extensions or truncations.

The conventional binary notation presents the least significant bits last. When working with masks and vectors, these least significant bits correspond to the first elements of the vectors. This discrepancy in the order is a source of confusion, but it is difficult to avoid. Intel intrinsic functions reflect this confusion by providing two sets of functions to create new vectors:
and  depending on the prefered order [Intel Corporation, 2023].

§.§ Special Functions

We use several special bit-manipulation functions corresponding to instructions available on contemporary x86 computers:

ctz The count trailing zeroes operation $\ctz(a)$ counts the number of trailing (least significant) zero bits in $a$, i. e. how often $a$ can be divided by $2$ until leaving an odd number.
It corresponds to the / instructions of the x86 instruction set.
Our algorithms never invoke $\ctz(0)$.

The bit width operation $\width(a)$ counts the number of bits needed to represent $a$.
It is

\begin{equation}
\width(a)=(a\ne0)\mathrel?\lfloor\log_2a\rfloor+1:0.
\end{equation}

This operation is efficiently implemented on many architectures through the count leading zeroes operation (x86 instruction /).
Our algorithms never invoke $\width(0)$.

popcount The population count operation $\popcount(a)$ computes the number of bits set in $a$.
This can also be understood as the sum of the bits of $a$.
It corresponds to the  instruction of the x86 instruction set.

pext The parallel extract operation $\pext(a,b)$ takes a bit mask $a$ indicating a possibly non-consecutive bit field and extracts those bits from $b$, packing them into  $\popcount(a)$ bits.
This corresponds to the  instruction on recent x86 processors.
The operation is perhaps best understood with a diagram:

\begin{equation}
\begin{tabular}{rl}
$a$         &\texttt{1010111011000100}\\
$b$         &\texttt{1000101011110001}\\
bit field   &\texttt{1-0-101-11-{}-{}-0-{}-}\\
\end{tabular}
\end{equation}

pdep The parallel deposit operation $\pdep(a,b)$ takes a bit mask $a$ indicating a possibly non-consecutive bit field and deposits the bits from $b$ into this field.
It performs the opposite operation to $\pext$ and corresponds to the  instruction on recent x86 processors.
We can likewise visualize its operation through a diagram:

\begin{equation}
\begin{tabular}{rl}
$a$         &\texttt{1010111011000100}\\
bit field   &\texttt{1-0-101-11-{}-{}-0-{}-}\\
\end{tabular}
\end{equation}

compress The compress vector operation $\compress(m, v)$ is the only vector operation among our special functions.
It performs the same operation as the parallel extract operation $\pext$,
but instead of extracting bits from a bit field, it extracts elements from a vector.
This corresponds to the  instruction on recent x86 processors.
For the visualization, we have given the mask $m=\texttt{0xcd}$ with the least significant bit on the left to make the operation easier to see.
The least significant mask bit decides whether to keep the first vector element and so on until the most significant mask bit decides whether to keep the last vector element:

\begin{equation}
\def\0{\hphantom0}
\begin{tabular}{rl}
$m$            &\texttt{\01\,\00\,\01\,\01\,\00\,\00\,\01\,\01}\\
$v$            &\texttt{12\,34\,56\,78\,9a\,bc\,de\,f0}\\
kept elements  &\texttt{12\,-{}-\,56\,78\,-{}-\,-{}-\,de\,f0}\\
\end{tabular}
\end{equation}

Observe how we reversed the bit order of the mask $m$ to match the natural vector order: its usual binary representation is .

Selected AVX-512 instructions.

instruction     -1emextension-1em     description

BW   move byte/word/dword vector

BW/F   blend words/dwords with mask

F   broadcast dword/qword to vector

DQ   extract 256-byte word from vector

BW/F   zero-extend byte to word or word to dword

BW   add bytes/words/dwords

BW   subtract bytes/words/dwords

BW   compare unsigned bytes/words

F   logic on 3 operands by given truth table

F   bitwise and dwords

F   bitwise and-not dwords

BW/F   logically shift words/dwords left by immediate

BW/F   logically shift words/dwords right by immediate

F   right-shift elements between operands

VBMI   shift bytes within qword, see  <ref>

VBMI2   compress byte vector, see  <ref>

VBMI   permute byte vector by byte index vector

BW   move 32/64-bit mask

BW   bitwise or 32/64-bit mask

BW   bitwise and-not 32/64-bit mask

BW   bitwise complement 32/64-bit mask

BW   logically shift 32/64-bit mask right by imm.

BW   test bitwise and/and-not of masks for all-zero

BW   test bitwise or of masks for all-zero/all-one

§ AVX-512

Our algorithms are based on the AVX-512 family of instruction-set extensions to the Intel 64[The 64 bit variant of the x86 (IA-32) instruction-set architecture, also known as amd64, x86-64, em64t, and IA-32e.] instruction-set architecture [sdm, 2022].
An extension to the AVX family of instruction-set extensions, AVX-512 provides a comprehensive set of SIMD instructions for operation on vectors of 16, 32, or 64 bytes organized into bytes or words of 16, 32, or 64 bits.  A register file of 32 vector registers – complemented by 8 mask registers – is provided.

AVX-512 instructions are generally non-destructive, writing their output into a separate operand from their inputs.
In most AVX-512 instructions, one operand is permitted to be a memory operand with the remaining operands being register or immediate operands.
This is usually the first input operand, but for some instructions it may also be the output operand.

The AVX-512 instruction set is split into a set of extensions.
Each extension adds new instructions to the Intel 64 architecture, enhancing the capabilities of AVX-512.
Depending on the microarchitecture used, not all AVX-512 extensions might be available.
Table <ref> gives a list of AVX-512 instructions used and the extension they hail from.
In the following, we list those AVX-512 extensions needed to execute the algorithms described in this paper:

AVX-512F The foundation extension implements the basic AVX-512 instruction set on 64-byte vectors.
Every AVX-512 implementation must support AVX-512F.

AVX-512BW The byte/word extension extends the AVX-512F instructions to vectors of bytes and 16-bit words.

AVX-512DQ The dword/qword extension provides additional instructions on 32- and 64-bit words.

AVX-512VBMI The vector byte manipulation instructions extension adds instructions to permute and manipulate bytes.

AVX-512VBMI2 The vector byte manipulation instructions 2 extension adds compress/expand support and double-width shifts for bytes and 16-bit words.

The first generation of Intel 64 processors supporting all required AVX-512 extensions are those code named Icelake, based on the microarchitecture code named Sunny Cove.
By emulating  through other instructions, it is likely possible to adapt the algorithms to processors as early as the generation code named Cannon Lake, albeit at significant reduction in performance.

§.§ Masking

The output of most vector instructions is subject to masking, a novel feature of AVX-512.
A mask register –[Mask register  cannot be used for masking, but remains available for logic on masks.] is applied to the output operand, specifying either merge masking or zero masking.
With merge masking, only those vector elements indicated by bits set in the mask register are modified in the output operand.
The other vector elements remain unchanged.
With zero masking, vector elements for which the bits in the mask register are clear are zeroed out.

For example, the merge and zero masking instructions

\begin{equation*}
\begin{tabular}{ll}
\texttt{vpaddb zmm0\string{k1\string}, zmm2, zmm3}&(merge masking), and\\
\texttt{vpaddb zmm4\string{k5\string}\string{z\string}, zmm6, zmm7}&(zero masking)\\
\end{tabular}
\end{equation*}

perform a packed addition of bytes, giving

\begin{align*}
\texttt{zmm0}&=\texttt{k1}\mathrel?\texttt{zmm2}+\texttt{zmm3}:\texttt{zmm0}\quad\mbox{and}\\
\texttt{zmm4}&=\texttt{k5}\mathrel?\texttt{zmm6}+\texttt{zmm7}:0.
\end{align*}

Masking on register operands is free for most instructions, though merge masking introduces an input dependency on the old value of the output operand.

Masking on memory operands enables memory fault suppression for most instructions.
This means that the CPU does not signal memory faults for masked-out vector elements, permitting masked out elements to extend into unmapped or non-writable pages.
This suppression affects both input and output memory operands.

§.§ Microarchitectural Details

To simplify the implementation of AVX-512 on microarchitectures designed to execute the older SSE and AVX families of instruction-set extensions, most SIMD instructions operate within lanes of 16 bytes.
That is, in many ways, it is as if the 64-byte vector registers were made of four nearly independent 16-byte subregisters.
Instructions that process data across lanes (such as  or ) exist, but can typically execute on less execution units and take longer to execute in comparison to instructions that do not.
We thus want to avoid cross-lane operations if feasible.

On current Intel microarchitectures including Sunny Cove (Icelake), Cypress Cove (Rocket Lake), and Willow Cove (Tiger Lake), most AVX-512 instructions[assuming no memory operands] can execute on execution ports 0, 1, and 5.
Instructions that do not cross lanes usually execute in a single cycle, instructions that do take 3 or more cycles.
Some instructions are restricted in the ports they can execute on: shifts can only execute on ports 0/1, permutations and other cross-lane instructions, as well as comparisons into masks can only execute on port 5.
Instructions operating on masks (i. e. those whose mnemonics start with ) are restricted to one of ports 0 or port 5, depending on the instruction [Fog, 2022, Abel and Reineke, 2019].

In addition to these restrictions, ports 0 and 1 support a vector length of only 32 bytes while port 5 supports the whole 64 bytes.
Instructions operating on a vector length of 64 bytes are executed either on port 5 or on ports 0/1 joined together, occupying both ports for one cycle simultaneously.
Thus, there are effectively only two ports available to execute instructions with a 64-byte vector length.
While 32-byte vectors are processed at 3 vectors of 32 bytes (i. e. 6 lanes) per cycle, 64-byte vectors are processed at only 2 vectors of 64 bytes (or 8 lanes) per cycle, leading to a theoretical speedup by a factor of $4/3$ or $33\,\%$ of 64-byte vectors over 32-byte vectors for an otherwise identical algorithm.
This stands in contrast to the factor $2$ or $100\,\%$ speedup one would naïvely expect from doubling the vector length.

It is vital for the performance of AVX-512 code to keep track of which ports instructions execute on, rearranging or editing the code such that both port 0/1 and port 5 can execute instructions at the same time [Fog, 2022].
Through the use of microarchitectural simulation [Abel and Reineke, 2022] in the design of the algorithms, good port utilization has been ensured.

§ TRANSCODING FROM UTF-8 TO UTF-16

We transcode UTF-8 to UTF-16 by gathering the bytes that make up each character from the last byte of each character to its first byte.
This exploits the similarity in bit arrangement between the four cases (ASCII, 2-byte, 3-byte, and 4-byte) highlighted in Fig. <ref>.
The bytes of each UTF-8 sequence are isolated from the input string, liberated of their tag bits, shifted into position, and finally summed up into a code point.

Using the exact correspondence between 4-byte UTF-8 characters and characters represented as surrogate pairs in UTF-16, we treat 4-byte characters as an overlapping pair of a 3-byte sequences and a 2-byte sequence that is later fixed up into a high and a low surrogate.
This saves us extra code for extracting the fourth-last byte of each sequence and avoids the costly use of 32-bit words for intermediate results.

To illustrate this idea, consider the following example, translating the Unicode characters 40 (@), A7 (), 2208 ($\in$), and 1D4AA ($\mathcal O$) from UTF-8 to UTF-16:

\begin{equation}
\setlength\tabcolsep{2pt}
\begin{tabular}{cccccccccc}
@&\multicolumn{2}{c}{\S}&\multicolumn{3}{c}{$\in$}&\multicolumn{4}{c}{$\mathcal O$}\\
\texttt{40}&\texttt{C2}&\texttt{A7}&\texttt{E2}&\texttt{88}&\texttt{88}&\texttt{F0}&\texttt{9D}&\texttt{92}&\texttt{AA}\\
\midrule
\texttt{40}&&&&&&&&&\\
\midrule
\multicolumn{2}{c}{\texttt{0040}}&\multicolumn{2}{c}{\texttt{00A7}}&\multicolumn{2}{c}{\texttt{2208}}&\multicolumn{2}{c}{\texttt{D835}}&\multicolumn{2}{c}{\texttt{DCAA}}\\
\end{tabular}
\end{equation}

These four characters demonstrate the behavior of the algorithm on the four UTF-8 cases, representing ASCII, 2-byte, 3-byte, and 4-byte respectively.
Observe especially how the code sequence  for $\mathcal O$ is split into two overlapping sequences  and .
The first of these two is translated into the high surrogate  with the second one becoming the low surrogate .

The algorithm can be roughly described with the following plan of attack:

* Read a vector of 64 bytes.

* Classify each byte according to whether it is an ASCII byte, continuation byte, 2-byte lead byte, 3-byte lead byte, or 4-byte lead byte.

* Construct a mask indicating the last byte of each UTF-8 sequence.  For 4-byte characters, the third byte is indicated, too, treating them as a 3-byte sequence for the high surrogate and a 2-byte sequence for the low surrogate.

* Use the mask to gather the last, $2^{\mathrm{nd}}$ last, and $3^{\mathrm{rd}}$ last byte of each sequence.

* Strip tag bits, shift bits into place and or them into UTF-16 words.

* Postprocess surrogates by shifting their bits into place, and applying tag bits and surrogate plane shift.

* Write the resulting bytes to the output, incrementing the input and output pointers by the number of bytes consumed/generated.

* Repeat until the end of input or an encoding error are encountered.

Apart from this general plan, there are also fast paths for the cases (a) ASCII characters only, (b) ASCII,  and 2-byte sequences only, and (c) 1–3-byte sequences only.

Validation is performed throughout the transcoding process, as explained in  <ref>.
In comparison to previous algorithms, it is simplified by advancing the input only by complete UTF-8 sequences;
if the input is correct UTF-8, each vector of input thus begins with a complete sequence.

§.§ Classification and Masks

After reading a vector of bytes from the input buffer, the characters in it are classified according to the range they fall into.  Various masks are then built from this classification.  In the following explanations, we follow the convention from  <ref> where names of the form $m_{\ldots}$ refer to masks about the input vector $w_{\mathrm{in}}$ while names of the form $M_{\ldots}$ refer to masks about the output vector.

These two kinds of masks are connected through the $\pext$ and $\pdep$ operations, relating the end bytes of the decoded UTF-8 sequences to the UTF-16 words they correspond to and vice versa.

The first set of masks is derived directly from $w_{\mathrm{in}}$, classifying the input into ASCII

\begin{equation}
m_1=(w_{\mathrm{in}}<\texttt{0x80}), \label{8to16:m1}
\end{equation}

2/3/4-byte sequence lead bytes

\begin{equation}
m_{234}=(\texttt{0xc0}\le w_{\mathrm{in}}), \label{8to16:m234}
\end{equation}

3/4-byte sequence lead bytes

\begin{equation}
m_{34}=(\texttt{0xe0}\le w_{\mathrm{in}}) \label{8to16:m34}
\end{equation}

and 4-byte sequence lead bytes

\begin{equation}
m_4=(\texttt{0xf0}\le w_{\mathrm{in}}). \label{8to16:m4}
\end{equation}

From these we then derive a mask

\begin{equation}
m_{1234}=m_1\lor m_{234} \label{8to16:m1234}
\end{equation}

indicating the presence of any kind of lead byte.
All other bytes ($\lnot m_{1234}$) are continuation bytes.

Then we construct the important mask $m_{\mathrm{end}}$ identifying the last bytes of each sequence to be decoded.
These are the last bytes of each UTF-8 sequence as well as the third byte of each 4-byte sequence.
Working backwards from these last bytes, we later use this mask to gather the last, second-last and third-last bytes of each sequence.

The key insight in constructing $m_{\mathrm{end}}$ is that as each UTF-8 sequence is followed by another UTF-8 sequence, we can find the positions of the last bytes as those preceding the lead bytes of the next sequence ($m_{1234}\gg1$).
The third byte of each 4-byte sequence is added by first computing the fourth byte of each sequence

\begin{equation}
m_{+3}=m_4\ll3 \label{8to16:mplus3}
\end{equation}

and then shifting the result to the right to obtain the last third bytes

\begin{align}
m_{\mathrm{end}}=(m_{+3}\lor m_{1234})\gg1\lor m_{+3}.\label{8to16:mend}
\end{align}

An unfortunate consequence of defining $m_{\mathrm{end}}$ by going backwards from the lead bytes of the next characters is that we only catch the last character of the vector when it is followed by an incomplete character whose lead byte we can shift to the right.
For 4-byte sequences right at the end of the vector, this leads to us only detecting the third last byte in the character.
Oring in $m_{+3}$ at the end fixes this problem for the 4-byte case.

For the other cases, the only effect of this process is that if $w_{\mathrm{in}}$ does not end in a partial character, decodes to no more than 32 words of UTF-16, and the last character is not a 4-byte sequence, we process one less character in the current iteration than possible.
However, the minor performance impact of hitting this edge case is more than outweighed by not spending extra time computing the mask correctly.[
If a perfect mask is desired, you can instead use

\begin{equation*}
m'_{\mathrm{end}}=(m_1\lor m_2\ll 1\lor m_{34}\ll2\lor m_4\ll3)\land\lnot\bigl(m_4\ll2\land 1\ll(n-1)\bigr), \label{8to16:mendperfect}
\end{equation*}

where $m_2=m_{234}\land\lnot m_{34}$ indicates 2-byte sequence lead bytes.
The first byte of each sequence is shifted to the position of its last byte (and the third byte of a 4-byte sequence).
The mask is then post-processed by clearing the third byte of a 4-byte sequence starting in the third-last byte of $w_{\mathrm{in}}$, as only complete sequences can be processed.]

To visualize the various masks, consider the strings “x$\nabla\mathfrak P$” and “$\varepsilon{\le}{\pm}1$” with a vector length of $n=8$ bytes:

\begin{equation}
\setlength\tabcolsep{2pt}
\begin{tabular}{rlccccccccclcccccccc}
&&&x&\multicolumn{3}{c}{$\nabla$}&\multicolumn{4}{c}{$\mathfrak P$}&&\multicolumn{2}{c}{$\varepsilon$}&\multicolumn{3}{c}{$\le$}&\multicolumn{2}{c}{$\pm$}&$1$\\
\midrule
$m_1$     &$\!=w_{\mathrm{in}}<\texttt{0x80}$   &&1&0&0&0&0&0&0&0&&0&0&0&0&0&0&0&1\\
$m_{234}$ &$\!=\texttt{0xc0}\le w_{\mathrm{in}}$&&0&1&0&0&1&0&0&0&&1&0&1&0&0&1&0&0\\
$m_{34}$  &$\!=\texttt{0xe0}\le w_{\mathrm{in}}$&&0&1&0&0&1&0&0&0&&0&0&1&0&0&0&0&0\\
$m_4$     &$\!=\texttt{0xf0}\le w_{\mathrm{in}}$&&0&0&0&0&1&0&0&0&&0&0&0&0&0&0&0&0\\
$m_{1234}$&$\!=m_1\lor m_{234}$                 &&1&1&0&0&1&0&0&0&&1&0&1&0&0&1&0&1\\
$m_{+3}$  &$\!=m_4\ll3$                         &&0&0&0&0&0&0&0&1&&0&0&0&0&0&0&0&0\\
$m_{\mathrm{end}}$&$\!=(m_{+3}\lor m_{1234})\gg1\lor m_{+3}$&&1&0&0&1&0&0&1&1&&0&1&0&0&1&0&1&0\\
\end{tabular}
\end{equation}

In this example, masks are arrays of eight bits corresponding to eight-byte sequences: in our actual implementation, we use 64-bit masks.
Note in particular how $m_{\mathrm{end}}$ accounts for the last character in the left string (being a 4-byte character), but not in the right string, where it is an ASCII character.
Also note how the character $\mathfrak P$ has two end bits, being treated as a 3-byte sequence overlapping a 2-byte sequence.

§.§ Assembling Characters

With these masks in hand, we can strip off the tag bits and assemble characters.
The UTF-8 tag bits are stripped off by clearing the most significant two bit of each non-ASCII byte in $w_{\mathrm{in}}$, giving

\begin{equation}
w_{\mathrm{stripped}}=m_1\mathrel ? w_{\mathrm{in}}:w_{\mathrm{in}}\land\texttt{0x3f}. \label{8to16:wstripped}
\end{equation}

The tag bits of 3/4-byte lead bytes are not completely removed by this step;
this is sufficient for our purposes as these tag bits  get shifted out later on.

Characters are assembled by selecting from $w_{\mathrm{stripped}}$ the last ($W_{\mathrm{end}}$), second-last ($W_{-1}$) and third-last bytes ($W_{-2}$) of each sequence, zero-extending them to 16 bits and joining their bits into a UTF-16 word.
We do this by first preparing a permutation vector $P$ that holds for each word in the output vector, the index of the last byte of the corresponding sequence.
This vector is prepared by compressing () a byte vector holding an identity permutation $(0,1,\ldots,63)$ subject to $m_{\mathrm{end}}$.  The compressed vector is then zero-extended () to 16-bit words, keeping its first $n/2$ elements:

\begin{equation}
P=\compress\bigl(m_{\mathrm{end}}, (0,1,\ldots,n-1)\bigr). \label{8to16:P}
\end{equation}

We only generate one vector of UTF-16 words per iteration representing at most 32 characters. When the input contains ASCII characters, it might be possible for $m_{\mathrm{end}}$ to contain more than 32 set bits. Bits set in $m_{\mathrm{end}}$ past the 32$^\mathrm{nd}$ bit are discarded during the processing: $P$ contains only $n/2$ (or 32) elements.
With $P$ in hand, we can load the last byte of each sequence

\begin{equation}
W_{\mathrm{end}}[i]=w_{\mathrm{stripped}}\bigl[P[i]\bigr] \label{8to16:Wend}
\end{equation}

with a single permutation instruction ().[as  permutes each byte, we zero-mask its result with  to only permute into the less significant byte of each 16-bit word, zero-extending for free.]

By decrementing the entries of $P$, we produce index vectors corresponding to the second-last and third-last bytes of each sequence.
To avoid loading the third-last byte of a 1/2-byte sequence or the second-last byte of an ASCII sequence, we mask $w_{\mathrm{stripped}}$ with masks

\begin{align}
m_{-1}&=\lnot m_1\gg 1\quad\mbox{and} \label{8to16:mminus1} \\
m_{-2}&=m_{34}\land\lnot0\gg2 \label{8to16:mminus2}
\end{align}

to clear out bytes before ASCII characters resp. those that do not start a 3/4-byte sequence, accounting for possible wrap around.[$P[i]-1$ and $P[i]-2$ may yield negative numbers; we assume that in a permutation, such indices either wrap around to the end of the vector or produce $0$ as an output. If negative permutation indices yield zeroes, the term $\lnot0\gg2$, serving as wraparound protection, can be omitted from $m_{-2}$.]
We then obtain our vectors

\begin{align}
W_{-1}[i]&=\bigl(m_{-1}\mathrel?w_{\mathrm{stripped}}:0\bigr)\bigl[P[i]-1\bigr]\quad\mbox{and} \label{8to16:Wminus1}\\
W_{-2}[i]&=\bigl(m_{-2}\mathrel?w_{\mathrm{stripped}}:0\bigr)\bigl[P[i]-2\bigr] \label{8to16:Wminus2}
\end{align}

as desired.
The last, second-last, and third-last bytes are shifted into place and ored such that the bits –
are contiguous, giving

\begin{equation}
W_{\mathrm{sum}}=W_{-2}\ll12\lor W_{-1}\ll6\lor W_{\mathrm{end}}.  \label{8to16:Wsum}
\end{equation}

The value of $W_{\mathrm{sum}}$ depending on the case taken can be visualized as follows:

\begin{equation}
\begin{tabular}{rcc}
\emph{case}&\emph{byte sequence}&$W_{\mathrm{sum}}$\\
\midrule
ASCII   &\texttt{\hphantom{XXXX\,XXXX\;XXXX\,XXXX\;XXXX\,XXXX\;}0GFE\,DCBA}&\texttt{0000\,0000\,0GFE\,DCBA}\\
2 byte  &\texttt{\hphantom{XXXX\,XXXX\;XXXX\,XXXX\;}110L\,KJHG\;10FE\,DCBA}&\texttt{0000\,0LKJ\,HGFE\,DCBA}\\
3 byte  &\texttt{\hphantom{XXXX\,XXXX\;}1110\,RQPN\;10ML\,KJHG\;10FE\,DCBA}&\texttt{RQPN\,MLKJ\,HGFE\,DCBA}\\
hi surr &\texttt{1111\,0WVU\;10TS\,RQPN\;10ML\,KJHG\hphantom{\;XXXX\,XXXX}}&\texttt{0WVU\,TSRQ\,PNML\,KJHG}\\
lo surr &\texttt{\hphantom{XXXX\,XXXX\;XXXX\,XXXX\;}10ML\,KJHG\;10FE\,DCBA}&\texttt{0000\,MLKJ\,HGFE\,DCBA}\\
\end{tabular}
\end{equation}

This representation is close to UTF-16LE format with only the surrogate cases diverging.
To address this difference, we first identify the locations of surrogates in $W_{\mathrm{out}}$.
Sequences in $w_{\mathrm{in}}$ corresponding to low surrogates end at the fourth bytes of 4-byte sequences.
By extracting the locations of these through $m_{\mathrm{end}}$ into the space of $W_{\mathrm{out}}$, we obtain the locations of low surrogates

\begin{equation}
M_{\mathrm{lo}}=\pext(m_{\mathrm{end}}, m_{+3}) \label{8to16:Mlo}
\end{equation}

in $W_{\mathrm{out}}$.
High surrogates

\begin{equation}
M_{\mathrm{hi}}=M_{\mathrm{lo}}\gg1 \label{8to16:Mhi}
\end{equation}

always precede low surrogates.

Surrogates are fixed up by shifting high surrogates into position and applying surrogate plane shift and tag bits,[Adding $\texttt{0xd7c0}=\texttt{0xd800}-\texttt{0x0020}$ applies the tag bits and the surrogate plane shift in one step.] giving

\begin{equation}
\begin{cases}
(W_{\mathrm{sum}}\gg4)+\texttt{0xd7c0}&\mbox{if $M_{\mathrm{hi}}$}\\
W_{\mathrm{sum}}\lor \texttt{0xdc00}&\mbox{if $M_{\mathrm{lo}}$}\\
\end{cases} \label{8to16:Wout}
\end{equation}

The operation of Eq. <ref> can be visualized as follows, where $\texttt{0vuts}=\texttt{WVUTS}-1$:

\begin{equation}
\begin{tabular}{rcc}
\emph{case}&$W_{\mathrm{sum}}$&$W_{\mathrm{out}}$\\
\midrule
high surrogate&\texttt{0WVU\,TSRQ\,PNML\,KJHG}&\texttt{1101\,10vu\,tsRQ\,PNML}\\
low surrogate&\texttt{0000\,MLKJ\,HGFE\,DCBA}&\texttt{1101\,11KJ\,HGFE\,DCBA}\\
\end{tabular}
\end{equation}

For illustration purposes, we provide C code implementing
equation Eq. <ref> using Intel intrinsic functions: see Fig. <ref>.

__m512i mask_d7c0d7c0 = _mm512_set1_epi32(0xd7c0d7c0);
__m512i mask_dc00dc00 = _mm512_set1_epi32(0xdc00dc00);
// Mlo, Mhi and Wsum have been computed, we compute Wout.
__m512i lo_surr_mask = _mm512_maskz_mov_epi16(Mlo, mask_dc00dc00);
__m512i shifted4_Wsum = _mm512_srli_epi16(Wsum, 4);
__m512i tagged_lo_surrogates = _mm512_or_si512(Wsum, lo_surr_mask);
__m512i Wout = _mm512_mask_add_epi16(tagged_lo_surrogates, Mhi,
shifted4_Wsum, mask_d7c0d7c0);

C code using Intel intrinsic functions equivalent to Eq. <ref>.

The vector $W_{\mathrm{out}}$ holds the UTF-16LE encoded characters we want to write out.
There is a final issue: the 64 bytes of UTF-8 data in the input may correspond to anywhere from 21 to 64 words of output, of which the first up to 32 words are processed.[Input data corresponding to the remaining words (if any) is reprocessed in the next iteration.]
If a surrogate pair happened to straddle the end of $W_{\mathrm{out}}$, we would discard the corresponding low surrogate and produce an incorrect result.
So once again, special care must be taken to omit the $32^{\mathrm{nd}}$ word of output if it is a high surrogate.
We do so by computing a mask

\begin{equation}
M_{\mathrm{out}}=\lnot\bigl(M_{\mathrm{hi}}\land 1\ll(n/2-1)\bigr) \label{8to16:Mout}
\end{equation}

of the elements of $W_{\mathrm{out}}$ excluding the last element if it happens to be a high surrogate.
We introduce a variable $b$ which is set to all ones  ($b=\lnot0$) except at the end of the input (cf.  <ref>).
By depositing the mask $M_{\mathrm{out}}$ into the last bytes of each sequence, we obtain a mask

\begin{equation}
m_{\mathrm{processed}}=\pdep(b\land m_{\mathrm{end}}, M_{\mathrm{out}}) \label{8to16:mprocessed}
\end{equation}

holding the locations of the last byte of each sequence that has been processed into a word in $W_{\mathrm{out}}$.

With this mask, we can compute the number of bytes of input processed

\begin{equation}
n_{\mathrm{in}}=\width(m_{\mathrm{processed}}) \label{8to16:nin}
\end{equation}

and the number of words of output produced

\begin{equation}
n_{\mathrm{out}}=\popcount(m_{\mathrm{processed}}). \label{8to16:nout}
\end{equation}

The first $n_{\mathrm{out}}$ bytes of the output vector are then deposited into the output buffer, input and output buffers are advanced by $n_{\mathrm{in}}$ and $n_{\mathrm{out}}$ and we continue with the next iteration.

To visualize the generation of $m_{\mathrm{processed}}$, consider the example string “$\pm1{=}\mathcal O$” with a vector length of $n=8$ bytes:

\begin{equation}
\setlength\tabcolsep{2pt}
\begin{tabular}{rcccccccc}
&\multicolumn{2}{c}{$\pm$}&1&=&\multicolumn{4}{c}{$\mathcal O$}\\
\end{tabular}
\end{equation}

As the character  straddles the end of the vector, it cannot be processed in the current iteration:

\begin{equation}
\setlength\tabcolsep{2pt}
\begin{tabular}{rccccc}
&$\pm$&1&=&\multicolumn{2}{c}{$\mathcal O$\hphantom{()}}\\
\end{tabular}
\end{equation}

Depositing the bits of $M_{\mathrm{out}}$ through $m_{\mathrm{end}}$, we then obtain

\begin{equation}
\setlength\tabcolsep{2pt}
\begin{tabular}{rcccccccc}
bytes processed&\texttt{C2}&\texttt{B1}&\texttt{31}&\texttt{3D}&\texttt{-{}-}&\texttt{-{}-}&\texttt{-{}-}&\texttt{-{}-}\\
words produced&\multicolumn{2}{c}{\texttt{00B1}}&\multicolumn{2}{c}{\texttt{0031}}&\multicolumn{2}{c}{\texttt{003D}}&\multicolumn{2}{c}{\texttt\dash}\\
\end{tabular}
\end{equation}

and advance buffers by $n_{\mathrm{in}}=4$ bytes and $n_{\mathrm{out}}=3$ words respectively.
The bytes corresponding to $\mathcal O$ will be processed again in the next iteration.

§.§ Processing the Tail

The final bit of input with less than 64 characters remaining (tail) is handled through the variable $b$.
This variable holds a mask of those bytes in $w_{\mathrm{in}}$ we are permitted to process.
Initially we set $b=\lnot0$, permitting all bytes to be processed.
When the end of the input with $\ell<n$ bytes remaining to be processed is reached, we set $b$ to a mask of the first $\ell$ bytes of $w_{\mathrm{in}}$, giving

\begin{equation}
b=(1\ll\ell)-1. \label{8to16:b}
\end{equation}

The tail of input is read zero-masked by $b$, padding it with nul bytes.
Then, a final iteration of the main loop is performed, processing only the bytes accounted for in $b$.

§.§ Input Validation

Throughout the transcoding process, we check the input for encoding errors and abort transcoding if any such error occurs.
Aborting is done by determining the location of the encoding error and setting the remaining input length $\ell$ to the number of bytes preceding the first error.
We then clear all input bytes starting at the first erroneous byte and jump to the tail-handling code from  <ref>, effectively restarting the current iteration as “final” iteration.

Having talked about how to continue after an error has occurred, we shall now direct our attention to the kinds of errors we have to check for.
A UTF-8 encoded document must conform to the following rules:

* Bytes – must not occur.

* Lead and continuation bytes must match: each byte in  to  must be followed by one continuation byte, each byte from  to  by two continuation bytes and each byte from  to  by three continuation bytes.

* Continuation bytes may not otherwise occur.

* The decoded character must be larger than 7F for 2-byte sequences, larger than 7FF for 3-byte sequences, and larger than FFFF for 4-byte sequences.

* The character must be no greater than 10FFFF.

* The character must not be in the range D800DFFF.

We check for these rules throughout the algorithm, mostly reusing masks we already have to compute for other steps of the code.
Three checks are performed in total:

Overlong 2-byte sequences
Right at the beginning, we check whether any of the bytes  or  occur.
Presence of these bytes indicates a 2-byte sequence that encodes a code point below 80, violating condition 4.
The first invalid input byte is the first  or  byte found:

\begin{equation}
\mbox{valid if}\quad\bigl(m_{234}\land(w_{\mathrm{in}}<\texttt{0xc2})\bigr)=0.\label{8to16:fail1}
\end{equation}

Mismatched continuation bytes
After computing the various classification masks, we check if conditions 2 and 3 hold.
As each byte of UTF-8 is either a lead or continuation byte, we check this by computing where continuation bytes should be ($m_c$)
and comparing this with where lead bytes are not:

\begin{equation}
\mbox{valid if}\quad m_c=\lnot m_{1234}.\label{8to16:fail2}
\end{equation}

We compute $m_c$ from the location of the second ($m_{+1}$), third ($m_{+2}$), and fourth byte ($m_{+3}$, see Eq. <ref>) of each sequence:

\begin{align}
m_{+1}&=m_{234}\ll1, \label{8to16:mplus1} \\
m_{+2}&=m_{34}\ll2, \label{8to16:mplus2} \\
m_c&=m_{+1}\lor m_{+2}\lor m_{+3}. \label{8to16:mc}
\end{align}

Conveniently, this check also fails on the input if it starts with continuation bytes, violating the invariant established earlier.
We do not catch a UTF-8 sequence straddling the end of the vector; such a sequence is checked properly in the next iteration once additional bytes have been fed in.

If this check fails, we must distinguish two cases to determine the location of the first encoding error:
If the first mismatch of $m_c$ and $m_{1234}$ is due to a continuation byte present where there should not be one, the first invalid byte is that byte, giving

\begin{equation}
\ell=\ctz(m_c\oplus\lnot m_{1234}).\label{8to16:l1}
\end{equation}

Otherwise a continuation byte is missing where there should be one and the corresponding lead byte is the first invalid byte.
This byte can be found by masking $m_{1234}$ to all bits preceding the mismatch

\begin{equation}
m_{\mathrm{pre}}=\bigl(1\ll\ctz(m_c\oplus\lnot m_{1234})\bigr)-1 \label{8to16:mpre}
\end{equation}

and then finding the last (most significant) bit in it, corresponding to the lead byte that is missing a continuation byte.  This gives

\begin{equation}
\ell=\width(m_{1234}\land m_{\mathrm{pre}})-1.\label{8to16:l2}
\end{equation}

Encodings out of range
Finally, we check if the codepoints encoded by 3- and 4-byte sequences are in range (conditions 4 and 5) and that 3-byte sequences do not encode surrogates (condition 6).
The algorithm treats input bytes in the range – as lead bytes of 4-byte sequences.
Such sequences encode code points well in excess of 110000, allowing us to verify condition 1 as a side effect with no extra code.

We augment our existing mask set with a mask

\begin{equation}
m_3=m_{34}\land\lnot m_4 \label{8to16:m3}
\end{equation}

indicating the location of 3-byte sequence start bytes in $w_{\mathrm{in}}$.
Shifting the mask to indicate the last byte of each 3-byte sequence, extracting through $m_{\mathrm{end}}$, and truncating to $n/2$ bits, we obtain a mask

\begin{equation}
M_3=\pext(m_{\mathrm{end}}, m_3\ll2) \label{8to16:M3}
\end{equation}

indicating which words in $W_{\mathrm{out}}$ correspond to 3-byte sequences.
We then use $M_3$ to check if any 3-byte sequences encode codepoints below 800,

\begin{equation}
M_{<\codepoint{800}}=M_3\land(W_{\mathrm{out}}<\texttt{0x800}) \label{8to16:M800}
\end{equation}

indicating violations of condition 4.

Then we check for surrogates: words in $M_3$ must not encode surrogates, words in $M_{\mathrm{hi}}$ must encode high surrogates (condition 6).[by construction, words produced from 1- and 2-byte sequences never produce surrogates and $M_{\mathrm{lo}}$ always produces low surrogates; we do not need to validate these.]
A word in $M_{\mathrm{hi}}$ produces a high surrogate if and only if the code point it encodes is in range 1000010ffff (conditions 1, 4, and 5).
The masks

\begin{align}
M_{3s}&=M_3\land(\texttt{0xd800}\le W_{\mathrm{out}}<\texttt{0xe000}) \nonumber\\
&=M_3\land(W_{\mathrm{out}}-\texttt{0xd800}<\texttt{0x0800}) \label{8to16:M3s}
\end{align}

\begin{align}
M_{4s}&=M_{\mathrm{hi}}\land\lnot(\texttt{0xd800}\le W_{\mathrm{out}}<\texttt{0xdc00}) \nonumber\\
&=M_{\mathrm{hi}}\land(W_{\mathrm{out}}-\texttt{0xd800}\ge\texttt{0x0400}) \label{8to16:M4s}
\end{align}

indicate violations of these conditions.[As all comparisons are unsigned (), one comparison for each range check suffices.]
The check succeeds if no offending words are found:

\begin{equation}
\mbox{valid if}\quad M_{<\codepoint{800}}\lor M_{3s}\lor M_{4s}=0.\label{8to16:fail3}
\end{equation}

If an offending word is found, the first invalid byte is the start byte of the corresponding sequence.
As the error can never occur in a low surrogate, we can find its location by projecting its location back onto the locations of the first and fourth bytes of every sequence:

\begin{equation}
\ell=\ctz\bigl(\pdep(m_{+3}\lor m_{1234},\;M_{<\codepoint{800}}\lor M_{3s}\lor M_{4s})\bigr).\label{8to16:l3}
\end{equation}

§.§ Fast Paths

Three fast paths are provided, speeding up common cases.  The first two are programmed such that they cannot be triggered in the “final” iterations for the tail or in case of an encoding error, allowing us to omit the handling of $b$ in their length computations for a further performance increase.

ASCII only
If the first 32 bytes of input are all ASCII bytes, we process these by  zero-extension () of the first 32 bytes to 16-bit words.
The number of processed bytes is always 32, the number of words written out always 32, shortening the dependency chain to the next iteration.  No validation is needed in this case as ASCII bytes are always valid.

Only the first 32 bytes are considered before embarking on the fast path as the default path does not process more than 32 characters in any case.
Hence, while checking for all 64 bytes to be ASCII would allow for slightly faster processing in the all-ASCII case, performance for documents with short runs of ASCII characters amidst other characters (e. g. HTML documents) suffers significantly, outweighing the benefits of the other case.

1/2 byte only
In the absence of 3- and 4-byte sequences ($m_{34}=0$), we employ a simplified variant of the algorithm.
While following the same operating principles as the main algorithm, we can take some shortcuts in the proven absence of 3- and 4-byte sequences.
First, the computation of some masks is greatly simplified, with most masks being entirely irrelevant for this path:

\begin{align}
m_2&=m_{234}, \label{8to16:12b:m2}\\
m_{\mathrm{end}}&=\lnot m_2,\quad\mbox{and} \label{8to16:12b:mend}\\
M_{\mathrm{out}}&=\pdep\bigl(m_{\mathrm{end}}, (1\ll n/2)-1\bigr). \label{8to16:12b:mout}
\end{align}

We then employ a simplified scheme to compute $W_{\mathrm{out}}$:
Instead of masking out tag bits, we subtract  from the lead byte of each two-byte sequence to cancel out the tag bits of both lead and continuation byte, giving

\begin{equation}
w_{-\texttt{0xc2}}=m_1\mathrel?0:w_{\mathrm{in}}-\texttt{0xc2}. \label{8to16:wc2}
\end{equation}

Instead of first building a permutation vector $P$ and then using it to permute the input bytes into place, we directly compress the bytes into position () and then zero extend to 16-bit words (), giving

\begin{align}
W_{\mathrm{end}}&=\compress(m_{\mathrm{end}}, w_{\mathrm{in}})\quad\mbox{and} \label{8to16:12b:Wend}\\
W_{-1}&=\compress(m_{1234}, w_{-\texttt{0xc2}}). \label{8to16:12b:Wminus1}
\end{align}

Vectors $W_{\mathrm{end}}$ and $W_{-1}$ must be merged by addition instead of bitwise or to correctly cancel out tag bits, giving

\begin{equation}
W_{\mathrm{out}}=(W_{-1}\ll6)+W_{\mathrm{end}}. \label{8to16:12b:Wout}
\end{equation}

The operation on 2-byte characters can be visualized as follows;  is subtracted separately to illustrate the idea:

\begin{equation}
\begin{tabular}{rll}
\midrule
\end{tabular}
\end{equation}

We want to increment the input pointer quickly—without a long chain of operations. We find it advantageous to always process half a vector (32 bytes or 33 bytes to include a final continuation byte) of input data per iteration like in the ASCII-only fast path.
While this approach usually processes less data than first determining the maximum number of input bytes we can process, being able to load the next data quicker is more important.  We avoid
accessing the SIMD masks to determine whether we advance
by 32 bytes or 33 bytes.

Thus we have

\begin{equation}
n/2+1&\mbox{if $\texttt{0x80}\le w_{\mathrm{in}}[n/2]<\texttt{0xc0}$}\\
\end{cases}
\end{equation}

processing 32 bytes per iteration unless a 2-byte sequence straddles the middle of the vector[i. e. unless the byte at position $n/2$ is a continuation byte], in which case we process that extra byte, too.

The output buffer is advanced by the number of characters starting in the first 32 bytes, giving

\begin{equation}
n_{\mathrm{out}}=\popcount\bigl(m_{1234} \land (1\ll n/2)-1\bigr).
\end{equation}

As for validation, the checks for “encodings out of range” are omitted.  The check for “mismatched continuation bytes” is simplified to

\begin{equation}
\mbox{valid if}\quad m_2\ll1=\lnot m_{1234} \label{8to16:12b:fail2}
\end{equation}

as continuation bytes must always directly follow 2-byte sequence lead bytes.
The combination of all these simplifications yields a code path of roughly half the latency of the standard code path.

1/2/3 byte only
In the absence of 4-byte sequences ($m_{4}=0$),
all characters are in the Basic Multilingual Plane. In this common case,
we can slightly simplify the main routine. We have
that $m_{+3}=m_4\ll3$ is zero. Consequently,
we can simplify the definitions of $m_c$ and $m_{\mathrm{end}}$ to

\begin{align}
m_c&=m_{+1}\lor m_{+2}\quad\mbox{and}\\
\end{align}

The computation of $W_{\mathrm{out}}$ and $M_\mathrm{out}$ is eliminated. As no surrogates are present, we can omit the surrogate post-processing and don't need to account for surrogate pairs straddling the end of the vector.
Instead, we directly get

\begin{align}
\end{align}

Finally, the validation check for out-of-range encoding is slightly simpler: as surrogates cannot occur, we can drop the $M_{4s}$ term off Eq. <ref>.

§ TRANSCODING FROM UTF-16 TO UTF-8

As explained in  <ref>, UTF-16 encodes characters in the Basic Multilingual Plane (0000ffff) in one 16-bit word and all others in two words as surrogate pairs.
To encode a code point as a surrogate pair,  is subtracted from the character code to obtain a 20-bit binary number.
The most significant 10 bits are added to  to form a high surrogate, which is followed by the less significant 10 bits added to , producing the corresponding low surrogate.

UTF-8 encodes Unicode characters in the range 0000007F in one byte, characters in the range 008007FF in two bytes, characters in the range 0800FFFF in three bytes and the other characters in four bytes.
Characters encoded in one UTF-16 word thus correspond to characters encoded in 1–3 bytes of UTF-8 and characters encoded in two UTF-16 words correspond to characters encoded in 4 bytes of UTF-8.
This suggests the following plan of attack for transcoding UTF-16 to UTF-8:

* Read a vector of 16-bit words.

* Classify the input words into ASCII (0000007F), 2-byte (008007FF), high surrogate (D800DBFF), low surrogate (DC00DFFF), and 3-byte (0800FFFF).

* Zero extend each 16-bit word to a 32-bit word and join low and high surrogates.

* Shuffle the bits within each 32-bit word into the right positions and apply tag bits according to the type of character, producing UTF-8 sequences padded with null bytes.

* Compress this vector, squeezing out the padding bytes.

* Write the byte string to the output buffer and proceed to the next iteration.

Apart from this general plan, we also have fast code paths for the three cases of (a) ASCII characters only, (b) all in 000007FF, and (c) no surrogates, complementing the default code path (d) surrogates present.
Which code path to take is decided based on the characters in the current 62-byte chunk of input.
We expect that  most text inputs would consistently rely on the same code paths. Thus branches corresponding to the various fast paths are easy to predict, and we expect that they may provide a significant performance boost.

We would now like to explain the steps in the plan of attack in detail.  The steps are interlinked with information produced in each step being reused for the subsequent steps.  Additionally, the classification masks are reused for input validation.

First, 32 words (i. e. 64 bytes) of input are loaded from memory into $W_{\mathrm{in}}$.  Of these words, 31 words are encoded in the iteration with the last word serving as a look ahead for surrogate processing ( <ref>).  The mask

\begin{equation}
L=1\ll n/2-1 \label{16to8:L}
\end{equation}

indicates the position of the lookahead word in $W_{\mathrm{in}}$.

§.§ Classification and Fast Paths

We first need to find out what UTF-8 cases the characters in our input correspond to.
Comparing the 16-bit words in the input vector with  and , we produce the

\begin{align}
M_{234}&=(\texttt{0x0080}\le W_{\mathrm{in}})\land\lnot L\quad\mbox{and} \label{16to8:M234}\\
M_{12}&=(\texttt{0x0800}> W_{\mathrm{in}}) \label{16to8:M12}
\end{align}

telling us if non-ASCII (i. e. 2-, 3-, or 4-byte) characters and ASCII or 2-byte characters are present.
ASCII characters in the lookahead are ignored to simplify some later bits of the algorithm.
Based on this information, we can then embark on a code path suitable for this chunk of input.

ASCII only If all input words represent ASCII characters ($M_{234}=0$), we handle the input in an ASCII-only fast path: the vector is truncated to bytes () and deposited into the output buffer, advancing it by 31 bytes. Though we could advance by 32 bytes,  we want the the algorithm to proceed with a constant stride through memory irrespective of the content.

Default path If some 3- or 4-byte characters are present ($M_{12}\lor L\ne\lnot0$), we check for surrogates. We do this by masking the words with  and then checking if the result is equal to  (high surrogate, $M_{\mathrm{hi}}$) or  (low surrogate, $M_{\mathrm{lo}}$), giving

\begin{align}
M_{\mathrm{hi}}&=(\texttt{0xd800}\le W_{\mathrm{in}}<\texttt{0xdc00})\land\lnot L\notag\\
&=(W_{\mathrm{in}}\land\texttt{0xfc00}=\texttt{0xd800})\land\lnot L\quad\mbox{and} \label{16to8:Mhi}\\
M_{\mathrm{lo}}&=(\texttt{0xdc00}\le W_{\mathrm{in}}<\texttt{0xe000})\notag\\
&=(W_{\mathrm{in}}\land\texttt{0xfc00}=\texttt{0xdc00}). \label{16to8:Mlo}
\end{align}

If surrogates are found to be present ($M_{\mathrm{hi}}\lor M_{\mathrm{lo}}\ne0$), we proceed to  <ref> to handle them.[Low surrogates in the lookahead are registered to permit detection of sequencing errors.]  Otherwise we skip that step, set $W_{\mathrm{joined}}=W_{\mathrm{in}}$ zero-extended from 16-bit to 32-bit (vpmovzxwd), and directly go to  <ref>.

1/2 byte only In the third and final case, we know that the input is a mix of ASCII and 2-byte characters.
We process this case by shuffling the bits of two-byte characters into position.[As we are on a little-endian architecture, the lead byte is the less-significant of the two.]
The most significant two bits of each byte are cleared and tag bits are applied.  Through this whole process, ASCII characters are left unchanged, giving us

\begin{equation}
W_{\mathrm{out}}=M_{234}\mathrel?(W_{\mathrm{in}}\ll8\lor W_{\mathrm{in}}\gg6)\land\texttt{0x3f3f}\lor\texttt{0x80c0}\mathrel:W_{\mathrm{in}}. \label{16to8:12b:Wout}
\end{equation}

We illustrate this equation in the 2-byte case:

\begin{equation}
\begin{tabular}{rl}
$W_{\mathrm{in}}\ll8\lor W_{\mathrm{in}}\gg6$&\texttt{HGFE\,DCBA\;000L\,KJHG}\\
\end{tabular}
\end{equation}

The words of $W_{\mathrm{out}}$ before the lookahead are then bytewise compared with [a constant we have already loaded into a register; any other constant with high-byte in range – and low byte 0 works.] producing a mask

\begin{equation}
m_{\mathrm{keep}}=W_{\mathrm{out}}\ge_{\mathrm{byte}}(L\mathrel?\texttt{0xffff}\mathrel:\texttt{0x0800}) \label{16to8:12b:mkeep}
\end{equation}

holding binary 01 for ASCII characters, 11 for 2-byte characters, and 00 for the lookahead.
With this mask, we finally compress $W_{\mathrm{out}}$ into a UTF-8 stream

\begin{equation}
w_{\mathrm{out}}=\compress(m_{\mathrm{keep}}, W_{\mathrm{out}}) \label{16to8:12b:woutsimpl}
\end{equation}

and write it to the output.

The output buffer pointer is advanced by the number of bytes of output produced, which is one byte for each word of input (sans lookahead) and another byte for each 2-byte character.

\begin{equation}
n_{\mathrm{out}}=\popcount(M_{234})+n/2-1. \label{16to8:12b:nout}
\end{equation}

§.§ Surrogates

When surrogates are present in the input, the bits of low surrogate have to be merged into those of the corresponding high surrogate, yielding the code point of the character to be encoded.

First, $W_{\mathrm{in}}$ is zero extended to 32 bits per element.[From here on, each vector holds $2n$ bytes of data.  These can be implemented as pairs of $n$-byte vectors.]  A vector $W_{\mathrm{lo}}$, holding for each high surrogate in $W_{\mathrm{in}}$ its corresponding low surrogate, is produced by rotating $W_{\mathrm{in}}$ to the right by one element.

Then, the surrogates are joined by subtracting the tag bits ( for the high surrogate,  for the low surrogate), undoing the surrogate plane shift for the high surrogate, shifting the bits of the high surrogate into place and then adding the two together.
By pulling out the constants representing the tag bits and the plane shift, these additions and subtractions can be combined into one using 32-bit unsigned arithmetic.
This gives us

\begin{align}
W_{\mathrm{joined}}&=M_{\mathrm{hi}}\mathrel?\bigl((W_{\mathrm{in}}-\texttt{0xd800}+\texttt{0x0040})\ll10\bigr)+(W_{\mathrm{lo}}-\texttt{0xdc00}):W_{\mathrm{in}}\nonumber \\
&=M_{\mathrm{hi}}\mathrel?(W_{\mathrm{in}}\ll10)+W_{\mathrm{lo}}+\texttt{0xfca02400}:W_{\mathrm{in}}. \label{16to8:Wjoined}
\end{align}

With the surrogate pairs decoded, we can then proceed to  <ref> to encode into UTF-8.  The vector elements corresponding to low surrogates are ignored for the rest of the algorithm.

§.§ Encoding into UTF-8

When we reach this step, we have transformed $W_{\mathrm{in}}$ into a vector $W_{\mathrm{joined}}$ of 32-bit integers, holding the code points of the characters in the input.[In the presence of surrogates, some of these elements are ignored.]  We would now like to encode these code points into UTF-8, producing 1–4 bytes of output per code point.

Consider Fig. <ref>: for the 2-, 3- and 4-byte case, the bits – making up the code point always appear in the same position.
This suggests using the same encoding procedure for the 2-, 3-, and 4-byte case with merely different tag bits applied at the end.
ASCII characters are handled with a  shift into position.

The encoding procedure is based on the  instruction introduced with the VBMI instruction set extension.  Given a vector of 64-bit words and for each such word a vector of eight bytes, the instruction uses the byte vectors as indices to pick eight 8-bit chunks of data (8 consecutive bits) from the corresponding source words.
By choosing these indices such that they do not cross a 32-bit boundary, we can effectively use the instruction to select four 8-bit chunks out of each 32-bit word.

Applying the index vector $(18,12,6,0)$ to each 32-bit word[i. e. the index vector $(18,12,6,0,50,44,38,32)$ applied to each 64-bit word] of $W_{\mathrm{joined}}$, we obtain $W_{\mathrm{shifted}}$ with each bit shifted into the right position with some bits left over:

\begin{equation} \label{16to8:Wshifted}
\begin{tabular}{rl}
\midrule
index          18&\texttt{\hphantom{0000\,00}00\;000w\,vu}\\
index          12&\texttt{\hphantom{0000\,0000\;0000\,}vuts\;RQPN\,    \;    \,    }\\
index \hphantom06&\texttt{\hphantom{0000\,0000\;0000\,0000\;00}PN\,MLKJ\;HG  \,    }\\
index \hphantom00&\texttt{\hphantom{0000\,0000\;0000\,0000\;0000\,0000\;}HGFE\,DCBA}\\
\midrule
\end{tabular}
\end{equation}

To fix up the left-over bits, we mask with , reusing the mask from the 2-byte fast path.
Then, appropriate tag bits $W_{\mathrm{tag}}$ are applied:

\begin{equation} \label{16to8:Wtag}
\begin{tabular}{ccc}
\emph{case}&\emph{$W_{\mathrm{shifted}}$ masked with \texttt{\upshape0x3f3f3f3f}}&\emph{tag bits}\\
\midrule
\end{tabular}
\end{equation}

Finally, the ASCII case is handled by just shifting the ASCII words into position and
merging these shifted characters into the output of the other cases, giving us

\begin{equation}
W_{\mathrm{out}}=M_{234}\mathrel?W_{\mathrm{shifted}}\land\texttt{0x3f3f3f3f}\lor W_{\mathrm{tag}}\mathrel:W_{\mathrm{in}}\ll24. \label{16to8:Wout}
\end{equation}

We end up with UTF-8 encoded characters in $W_{\mathrm{out}}$.  Each character occupies a 32-bit word and is padded with  bytes to 4 bytes.
Input words corresponding to low surrogates have been passed through, being decoded into junk content.
We get rid of the padding and the low surrogate junk by preparing a mask of bytes we want to keep and compressing out the unwanted bytes using the  instruction.

In the mask, we want to keep the most significant byte of each 32-bit word and all non-zero bytes—except for processed low surrogates.
These seemingly complex requirements can be negotiated in two steps by first building a comparison mask and then taking all bytes that are not lower than the mask.
For low surrogate bytes and the lookahead, the mask is  which cannot occur in $w_{\mathrm{out}}$.[The byte value  is not possible in valid UTF-8 (cf. Table <ref>).  It could be generated through invalid sequencing of surrogates, but we catch such an error when validating the content.]
For the most significant byte of all other words, it is  which admits every byte.
For other bytes, it is , admitting only nonzero bytes.
Thus we have

\begin{align}
W_{\mathrm{keep}}&=M_{\mathrm{lo}}\lor L\mathrel?\texttt{0xffffffff}\mathrel:\texttt{0x00010101},\quad\mbox{building} \label{16to8:Wkeep}\\
m_{\mathrm{keep}}&=(W_{\mathrm{out}}\ge_{\mathrm{byte}}W_{\mathrm{keep}}) \label{16to8:mkeep}.
\end{align}

With this mask, we compress $W_{\mathrm{out}}$ into

\begin{equation}
w_{\mathrm{out}}=\compress(m_{\mathrm{keep}}, W_{\mathrm{out}}), \label{16to8:wout}
\end{equation}

write it to the output buffer and advance the output by

\begin{equation}
n_{\mathrm{out}}=\popcount(m_{\mathrm{keep}}) \label{16to8:nout}
\end{equation}

Due to the little-endian orientation of the x64 architecture, the bytes of each UTF-8 sequence end up in the right order: within each 32-bit word, they are written from the least significant byte to the most significant byte.

§.§ Validation

In contrast to the UTF-8 to UTF-16 procedure, validation of UTF-16 input is less involved.
We merely have to check for the correct sequencing of surrogates: every high surrogate must be followed by a low surrogate and vice versa.
As this validation only pertains surrogates, it is skipped in their absence, i. e. in all fast paths;
input strings without surrogates are always valid.

To aid in this process, we only process 31 words of input in each iteration, permitting a “look ahead” into the first word of the next iteration.
We also keep track of a surrogate carry $c$ indicating if the first word in $W_{\mathrm{in}}$ was preceded by a high surrogate.
This carry allows us to decide if a low surrogate in $W[0]$ is to be ignored ($c=1$) or is a sequencing error ($c=0$).[When $W[0]$ is not a low surrogate, $c$ is guaranteed to be clear.]

Correct sequencing is checked for by concatenating $M_{\mathrm{hi}}$ with $c$ and shifting it to the position of the corresponding low surrogates $M_{\mathrm{lo}}$.
The input is valid if each high surrogate corresponds to a low surrogate:

\begin{equation} \label{16to8:valsur}
\mbox{valid if}\quad (M_{\mathrm{hi}}\ll1\lor c)=M_{\mathrm{lo}}.
\end{equation}

The carry for the next iteration is computed as the presence of a high surrogate in the vector element right before the lookahead, giving

\begin{equation}
c_{\mathrm{out}}=M_{\mathrm{hi}}\gg(n/2-2)\land1. \label{16to8:cout}
\end{equation}

In the absence of surrogates, i. e. in the fast paths, the carry is  cleared ($c_{\mathrm{out}}=0$).

If validation fails, we find the location of the first mismatched surrogate to transcode the words preceding the encoding error and then terminate.
This is done by setting the number of remaining input words $\ell$ to the number of words preceding the encoding error and then jumping to the tail handling code  <ref>.

Computing the location requires more work than Eq. <ref>; for a high surrogate not followed by a low surrogate, that equation indicates the missing low surrogate as the first erroneous word when it should really be the unmatched high surrogate.
So we proceed more carefully and first compute the sets of high surrogates not followed by low surrogates

\begin{equation}
M_{\mathrm{hi-lo}}=M_{\mathrm{hi}}\land\lnot(M_{\mathrm{lo}}\gg1) \label{16to8:Mhilo}
\end{equation}

and the set of low surrogates not preceded by high surrogates

\begin{equation}
M_{\mathrm{lo-hi}}=M_{\mathrm{lo}}\land\lnot(M_{\mathrm{hi}}\ll1\lor c). \label{16to8:Mlohi}
\end{equation}

The number of valid bytes is then the longest prefix not found in either of these masks:

\begin{equation}
\ell=\ctz(M_{\mathrm{lo-hi}}\lor M_{\mathrm{hi-lo}}). \label{16to8:l}
\end{equation}

§.§ Decoding Failure and Tail Handling

At the end of the input, there might be some UTF-16 words left to process, but not enough to load a whole 64-byte vector.
We deal with this remaining input in a manner similar to the UTF-8 to UTF-16 case, cf.  <ref>.

When $\ell<n/2$ words of input remain to be processed, we compute a mask

\begin{equation}
B=(1\ll\ell)-1 \label{16to8:B}
\end{equation}

of input words left to be processed.
We then load the remaining input zero-masked with $B$,[Or in case of an encoding
error, mask the already loaded vector.] giving us the input tail padded with 0000.
This remaining input is then processed in a final iteration of the main loop.

As each null byte translates into a single byte of output, this leads to an output that is precisely $n/2-1-\ell$ bytes longer than the true output length.
We compensate for this by adjusting the output length reported to the caller accordingly.

In contrast to the other direction, this approach may write past the end of the output buffer if it is just long enough to hold the decoded string.
We avoid this problem by performing masked stores instead of potentially storing null bytes past the end of the output.

§ EXPERIMENTS

Our initial implementation of the algorithms was written in Intel 64 assembly for systems following the System V ABI [Matz et al., 2012].
Hand-tuned assembly can slightly surpass optimizing
compilers due to better instruction scheduling and register allocation.
For the measurements and comparison with competitive libraries, we have translated the code to C++ using intrinsic functions [Intel Corporation, 2023] to access AVX-512 instructions and integrated it into our simdutf library[<https://github.com/simdutf/simdutf>] as the AVX-512 kernel.
This library is freely available.
Despite a slight loss of performance in comparison to the assembly implementation, we believe that this approach facilitates better portability and integration into existing software.

Our library is organized in different kernels that are automatically selected at runtime based on the features of the CPU, a process sometimes called runtime dispatching.
During benchmarking, we can manually select the different kernels.
As the names suggest,  the AVX2 kernel relies on AVX2 instructions (32-byte vector length) while the AVX-512 kernel using our new functions relies on AVX-512 instructions with a 64-byte vector length.
Our new functions are part of the AVX-512 kernel, and the AVX2 kernel represents results presented by Lemire and Muła [Lemire and Muła, 2022].

For benchmarking, we use Ubuntu 22.04 on a non-virtual (metal) server from Amazon Web Services ().
These servers have 32-core Intel Xeon 8375C (Ice Lake) processors with 41 of L3 memory, with 48 of L1 data cache memory and 1.25 of L2 cache memory per core.
The base clock frequency is 2.9, with a maximal frequency of 3.5.
They have 256 of main memory (DDR4, 3200).
The benchmarks are single-threaded and we exclude disk and network accesses from our tests.
The software is written in C++ and compiled with the Clang 14 C++ compiler from the LLVM project using the default  setting for a release build: .

We could use several threads.
For example, we could split the input into segments,
and compute the expected transcoded size
of the segments, before transcoding each segment in
its own thread.
However, merely joining a thread under Linux can require tens of microseconds of waiting from the main thread. With the high speed of our functions,
this penalty is equivalent to the time required to process hundreds of kilobytes of data. We could
use faster synchronization techniques (e.g., spin locks and thread pools), but at the expense of complexity and power efficiency. We expect
that multicore parallelism is only warranted for large inputs, in the megabytes or gigabytes range. Future work might consider such cases.

§.§ Setup

We benchmark the transcoding of data files between UTF-8 and UTF-16 in memory.
We repeat the task 10000 times, measuring the time of each conversion: the C++ library reports a precision of 1 for the  measures on our test system [Najafi et al., 2021].
The distribution of timings has a long tail akin to a log-normal distribution:
most values are close to the minimum.
We verify automatically that the difference between the minimum and the average timing is small (less than $1\,\%$).

AVX-512 capable Intel processors prior to the Ice Lake and Rocket Lake families
would systematically reduce their frequency when using 512-bit instructions,
a process that Intel referred to as licensing. Such 512-bit licensing
is no longer present in the more recent processors [Downs, 2020].
However,  the processor frequency may fluctuate based on power consumption
and heat production as is generally the case with Intel processors. We expect
512-bit instructions to use more power, and thus to run at a slightly lower frequency.
Irrespective of power usage,  Intel processors execute 512-bit instructions at a
reduced speed  initially (e.g., $4\times$ slower)—for a few microseconds.
We assume that our functions with 512-bit instructions are part of a binary executable
compiled with optimizations for 512-bit capable processors so that this temporary
effect is uncommon, maybe occurring only once.

We are interested in the steady-state performance of our functions: we
therefore always  benchmark our functions twice: once to intuitively warm
the processor so that 512-bit instructions always execute at full speed and
so that the processor has had a chance to decode the instructions.
Furthermore, we may sometimes benchmark a function relying on 512-bit instructions,
followed by a conventional function: to ensure that the latter is not penalized
by the power usage of the first function, we pause for a millisecond when switching
the benchmarked function.

We report performance results in characters per second. A given string has the same
number of characters irrespective of the format (UTF-8, UTF-16). We also report speeds in gigabytes per second by taking the size of the input and dividing by the time elapsed. We focus on little-endian
UTF-16, but our software supports big-endian UTF-16, at little cost.

We compare our work with the following competitors:

* We use the  library [Cameron, 2008] (last released in 2007).

* We use the  library [Gatilov, 2012] (last modified April 19, 2020).
We require full validation of input ().

* We use the C++ component from International Components for Unicode (ICU) [Unicode, Inc., 2010].

* We use the transcoding functions of the LLVM project, they were originally produced by  the Unicode Consortium.

* We use the  library, which is part of the C library (GNU C Library 2.35).

We use automatically generated (lipsum) text in Arabic, Chinese, Hebrew, Hindi, Japanese, Korean, Latin
and Russian, as well as a list of emojis (henceforth Emoji).[<https://github.com/rusticstuff/simdutf8>]
When formatted as UTF-16, they range in size between 11 and
The Chinese, Hindi, Japanese and Korean files have a high fraction of 3-byte UTF-8 characters.
The Arabic, Hebrew and Russian files have a high fraction of 2-byte UTF-8 characters.
Except for the Emoji file, none of the file contain 4-byte UTF-8 characters.
We  make our files freely available.[<https://github.com/lemire/unicode_lipsum>]

[UTF-8 to UTF-16 transcoding]

[UTF-16 to UTF-8 transcoding]

Transcoding speeds in gigabytes of input data per second for various test files. We compare against the ICU library.
The simdutf library provides both  AVX2 and AVX-512  functions.

Validating transcoding speeds (gigacharacters per second) over the lipsum datasets, last row is the harmonic mean of the column.  The last column (AVX-512) presents the results from our new algorithms.
[UTF-8 to UTF-16]    llvm     iconv     ICU     u8u16     utf8lut     AVX2     AVX-512
Arabic     0.17     0.39     0.80     0.87     0.92     1.3     4.3

Chinese     0.22     0.26     0.50     0.45     0.63     1.2     1.8

Emoji     0.18     0.19     0.22     0.31     0.18     0.40     1.0

Hebrew     0.17     0.39     0.80     0.87     0.92     1.3     4.3

Hindi     0.16     0.21     0.43     0.49     0.72     0.84     1.7

Japanese     0.21     0.26     0.51     0.46     0.64     1.2     1.7

Korean     0.13     0.30     0.62     0.54     0.72     0.89     1.8

Latin     0.35     0.56     1.5     13.     1.0     22.     20.

Russian     0.17     0.29     0.46     0.86     0.92     1.3     4.2

harm. mean     0.18    0.29    0.50    0.60    0.57    1.0    2.3

[UTF-16 to UTF-8]    llvm     iconv     ICU     utf8lut     AVX2     AVX-512
Arabic     0.38     0.30     0.67     2.4     4.8     11.

Chinese     0.38     0.28     0.36     2.4     2.6     3.9

Emoji     0.29     0.20     0.27     0.37     0.38     1.6

Hebrew     0.48     0.32     0.68     2.3     4.8     11.

Hindi     0.31     0.21     0.21     2.4     2.6     3.8

Japanese     0.38     0.26     0.37     2.3     2.7     3.8

Korean     0.43     0.30     0.37     2.3     2.7     3.8

Latin     0.58     0.56     0.91     2.3     18.     20.

Russian     0.28     0.23     0.23     2.4     4.8     11.

harm. mean     0.37    0.27    0.36    1.5    1.9    4.5

Validating transcoding speeds in gigabytes of input per second over the lipsum datasets, last row is the harmonic mean of the column. The last column (AVX-512) presents the results from our new algorithms.
[UTF-8 to UTF-16]    llvm     iconv     ICU     u8u16     utf8lut     AVX2     AVX-512
Arabic     0.31     0.70     1.4     1.5     1.6     2.3     7.6

Chinese     0.66     0.77     1.5     1.3     1.9     3.7     5.4

Emoji     0.72     0.78     0.87     1.2     0.70     1.6     4.2

Hebrew     0.31     0.70     1.4     1.6     1.6     2.3     7.7

Hindi     0.43     0.56     1.2     1.3     1.9     2.3     4.6

Japanese     0.60     0.74     1.5     1.3     1.9     3.5     5.0

Korean     0.32     0.73     1.5     1.3     1.8     2.2     4.5

Latin     0.35     0.56     1.5     13.     1.0     22.     20.

Russian     0.31     0.52     0.83     1.6     1.7     2.4     7.7

harm. mean     0.40    0.66    1.2    1.5    1.4    2.6    6.0

[UTF-16 to UTF-8]    llvm     iconv     ICU     utf8lut     AVX2     AVX-512
Arabic     0.76     0.61     1.3     4.7     9.6     21.

Chinese     0.76     0.57     0.73     4.7     5.3     7.7

Emoji     1.2     0.82     1.1     1.5     1.5     6.5

Hebrew     0.96     0.63     1.3     4.7     9.6     21.

Hindi     0.63     0.42     0.41     4.7     5.3     7.7

Japanese     0.77     0.52     0.74     4.7     5.3     7.6

Korean     0.86     0.60     0.73     4.7     5.4     7.6

Latin     1.2     1.1     1.8     4.7     37.     40.

Russian     0.56     0.45     0.46     4.7     9.6     21.

harm. mean     0.80    0.59    0.77    3.8    5.1    11.

§.§ Results

We present speed results in gigacharacters per second regarding the validating UTF-8 to UTF-16 transcoding functions on the lipsum files in Table <ref>.
The AVX2 and AVX-512 columns correspond to our own code, in the simdutf library (version 2.0.9, git tag ).
As the AVX2 kernels are implemented with a 32-byte vector length compared to the 64-byte vector length of the AVX-512 kernels, we expect a $33\,\%$ higher throughput just from using longer vectors (see  <ref>).

On the Latin file, the new AVX-512 kernel fails to improve on the earlier AVX2 kernel: the Latin dataset is made almost entirely of ASCII inputs which the AVX-512 kernel processes 32 bytes at a time, just like the AVX2 kernel.
On the Emoji file, the new AVX-512 kernel achieves one gigacharacter per second when transcoding from UTF-8, which is more than twice as fast as any competitor.
When transcoding from UTF-16, the new kernel transcode the Emoji file at 1.6 gigacharacters per second, which is more than four times as fast as any competitor. Whether transcoding from UTF-8 or UTF-16, the new kernel does well when transcoding inputs dominated by 2-byte UTF-8 sequences (Arabic, Hebrew and Russian): it is twice as fast as any competitor. For inputs dominated by 3-byte UTF-8 sequences (Chinese, Hindi, Japanese and Korean), the gain compared to the earlier AVX2 kernel is of the order of 50%.

Fig. <ref> and Table <ref> present the speed results in gigabytes of inputs per second.
Whereas the speeds of the AVX-512 function in gigacharacters per second vary by multiples (from 4.3 with Arabic to 1.0 with Emoji), the gaps are much less significant in gigabytes per second (from 7.6 with Arabic to 4.2 with Emoji).

Table <ref> presents the number of instructions retired per character,
measured using the hardware performance counters provided by Intel.[Under Linux, the performance counters are made available by the operating system. A C program can query them using the
functions defined in the  header.]
In the worst case (for the Emoji files), the new AVX-512 kernel still requires fewer than 6 instructions per character to transcode in either direction.
Except for  the Latin files, the new AVX-512 kernel requires far fewer than half the number of instructions than the AVX2 kernel when transcoding from UTF-8.
For example, we reduce the number of instructions by a factor of three for the Arabic file.

Table <ref> provides the number of instructions per cycle. We find that the AVX-512 kernel is associated with a lower number of instructions retired per cycle—especially so when transcoding from UTF-8. Correspondingly, we expect a lower number of 64-byte instructions being retired per cycle compared to 32-byte instructions due to the microarchitectures of the Intel CPUs ( <ref>).

The  library, when transcoding from UTF-8, requires fewer instructions than our AVX-2 kernel, but it is associated with few instructions per cycle. Hence, the  library is generally slower than our AVX-2 kernel despite relying on the same instruction set. The  library relies on a 2 table for UTF-8 to UTF-16 transcoding as opposed to a small table (11) for our AVX-2 kernel, and no table at all for our AVX-512 kernel. A large table may cause the CPU to wait for loads to complete and increases overall cache pressure.

CPU instructions retired per character when transcoding with validation.  The last column (AVX-512) presents the results from our new algorithms.
[UTF-8 to UTF-16]    llvm     iconv     ICU     u8u16     utf8lut     AVX2     AVX-512
Arabic     65.     52.     27.     15.     5.3     7.4     2.3

Chinese     82.     78.     38.     31.     8.4     11.     3.2

Emoji     100     100     93.     45.     95.     29.     5.4

Hebrew     65.     51.     27.     15.     5.3     7.4     2.3

Hindi     80.     71.     34.     28.     7.3     12.     3.0

Japanese     81.     76.     37.     30.     8.2     11.     3.2

Korean     75.     66.     31.     25.     6.9     12.     2.7

Latin     56.     35.     11.     0.65     5.3     0.35     0.24

Russian     66.     52.     27.     16.     5.3     7.2     2.3

[UTF-16 to UTF-8]    llvm     iconv     ICU     utf8lut     AVX2     AVX-512
Arabic     37.     53.     27.     6.3     2.6     1.1

Chinese     48.     67.     41.     6.3     4.5     2.2

Emoji     62.     90.     67.     51.     48.     5.4

Hebrew     37.     53.     27.     6.3     2.6     1.1

Hindi     45.     62.     38.     6.3     4.5     2.2

Japanese     47.     65.     40.     6.3     4.5     2.2

Korean     43.     58.     35.     6.3     4.5     2.2

Latin     31.     34.     19.     6.3     0.69     0.55

Russian     37.     53.     27.     6.3     2.6     1.1

CPU instructions retired per cycle when transcoding with validation.  The last column (AVX-512) presents the results from our new algorithms.
[UTF-8 to UTF-16]    llvm     iconv     ICU     u8u16     utf8lut     AVX2     AVX-512
Arabic     3.3     5.8     6.1     3.8     1.4     2.7     2.9

Chinese     5.2     5.7     5.3     4.0     1.5     3.9     1.7

Emoji     5.1     5.8     5.8     3.9     4.8     3.3     1.6

Hebrew     3.2     5.8     6.1     3.8     1.4     2.7     2.9

Hindi     3.7     4.3     4.2     3.9     1.5     2.9     1.5

Japanese     4.8     5.5     5.4     3.9     1.5     3.9     1.6

Korean     2.8     5.6     5.4     3.9     1.4     3.1     1.5

Latin     5.6     5.6     4.6     2.4     1.6     2.2     1.4

Russian     3.2     4.3     3.6     3.9     1.4     2.7     2.9

harm. mean      3.9    5.3    5.0    3.6    1.6    3.0    1.8

[UTF-16 to UTF-8]    llvm     iconv     ICU     utf8lut     AVX2     AVX-512
Arabic     4.0     4.6     5.2     4.2     3.5     3.3

Chinese     5.2     5.4     4.8     4.2     3.4     2.5

Emoji     5.2     5.3     5.2     5.3     5.1     2.6

Hebrew     5.1     4.8     5.2     4.2     3.5     3.3

Hindi     4.1     3.7     2.6     4.2     3.4     2.5

Japanese     5.2     4.9     4.7     4.2     3.4     2.5

Korean     5.3     5.0     4.5     4.2     3.4     2.5

Latin     5.2     5.5     5.0     4.2     3.6     3.2

Russian     3.0     3.4     2.1     4.2     3.5     3.3

harm. mean     4.5    4.6    3.9    4.3    3.6    2.8

n,	speed
32,	0.951197
39,	1.16102
47,	1.39607
54,	1.60503
62,	1.84659
69,	1.95555
77,	2.18223
84,	2.38121
92,	2.60398
99,	2.62049
107,	2.8329
114,	3.02393
122,	3.2365
129,	3.19037
137,	3.37401
144,	3.55409
152,	3.75092
159,	3.68273
167,	3.861
174,	4.04357
182,	4.22419
189,	4.16042
197,	4.33344
204,	4.48201
212,	4.66805
219,	4.59355
227,	4.74386
234,	4.89729
242,	5.05574
249,	4.95764
257,	5.12146
264,	5.26179
272,	5.41618
279,	5.56447
287,	5.44836
294,	5.6014
302,	5.73652
309,	5.87652
317,	5.74412
324,	5.86319
332,	6.01983
339,	6.12953
347,	5.98417
354,	6.09916
362,	6.24462
719,	6.71269
1077,	8.57128
1434,	8.90774
1792,	9.49984
2149,	9.80102
2507,	10.0811
2864,	10.1974
3222,	10.1628
3579,	10.319
3937,	10.4894
4294,	10.5914
4652,	10.625
5009,	10.7524
5367,	10.7828
5724,	10.964
6082,	11.0458
6439,	11.0313
6797,	10.9503
7154,	11.1511
7512,	11.1793
7869,	11.2161
8227,	11.2279
8584,	11.3021
8942,	11.307
9299,	11.3159
9657,	11.3669
10014,	11.3247
10372,	11.3559
10729,	11.3268
11087,	11.4733
11444,	11.454
11802,	11.382
12159,	11.3041
12517,	11.1416
12874,	10.8953
13232,	10.6868
13589,	10.5224
13947,	10.341
14304,	10.2438
14662,	10.2312
15019,	10.2226
15377,	10.239
15734,	10.2527
16092,	10.2573
16449,	10.2854
16807,	10.2787
17164,	10.3005
17522,	10.3039
17879,	10.3186
18237,	10.3245
18594,	10.3363
18952,	10.3359
19309,	10.36
19667,	10.3638
20024,	10.3736
20382,	10.3725
20739,	10.3811
21097,	10.3587
21454,	10.3556
21812,	10.3727
22169,	10.3703
22527,	10.3895
22884,	10.3805
23242,	10.4029
23599,	10.3876
23957,	10.4142
24314,	10.4161
24672,	10.4304
25029,	10.4241
25387,	10.4375
25744,	10.4327
26102,	10.4439
26459,	10.4438
26817,	10.4369
27174,	10.4527
27532,	10.4468
27889,	10.4542
28247,	10.4625
28604,	10.4652
28962,	10.4657
29319,	10.477
29677,	10.474
30034,	10.4828
30392,	10.4857
30749,	10.4885
31107,	10.4824
31464,	10.4853
31822,	10.4551
32179,	10.4258
32537,	10.4288
32894,	10.4262
33252,	10.4369
33609,	10.4348
33967,	10.4452
34324,	10.4475
34682,	10.4567
35039,	10.4472
35397,	10.4429
35754,	10.4445
36112,	10.4556
36469,	10.4604
36827,	10.4674
37184,	10.4625
37542,	10.4676
37899,	10.4757
38257,	10.4775
38614,	10.4842
38972,	10.487
39329,	10.4921
39687,	10.4734
40044,	10.4923
40402,	10.4905
40759,	10.4957
41117,	10.4921
41474,	10.499
41832,	10.4953
42189,	10.5071
42547,	10.4997
42904,	10.5056
43262,	10.504
43619,	10.5057
43977,	10.5093
44334,	10.5029
44692,	10.5154
45049,	10.5094
45407,	10.5133
45764,	10.5121

n,	speed
35,	1.05079
42,	1.25808
49,	1.46967
56,	1.49823
64,	1.70709
71,	1.49101
78,	1.87193
85,	2.02731
92,	2.01586
100,	2.18308
108,	1.93092
115,	2.30885
122,	2.44803
129,	2.39303
137,	2.54254
144,	2.24648
152,	2.62179
159,	2.33064
166,	2.66871
173,	2.77592
181,	2.50054
188,	2.83461
196,	2.95296
203,	2.88281
210,	2.98521
217,	2.90133
224,	2.99251
232,	3.10455
240,	3.0344
247,	3.11889
254,	3.04092
261,	3.12273
268,	3.20269
275,	3.13562
284,	3.23743
291,	3.17273
298,	3.24428
306,	2.99927
312,	3.25761
319,	3.32608
326,	3.25907
334,	3.336
342,	3.10124
349,	3.34984
355,	3.41068
363,	3.35272
720,	3.85995
1080,	3.97679
1439,	4.06532
1795,	4.15386
2151,	4.18032
2509,	4.18781
2865,	4.14589
3222,	4.24032
3581,	4.25217
3940,	4.23926
4298,	4.28598
4655,	4.28406
5012,	4.26577
5368,	4.30099
5725,	4.29914
6082,	4.25564
6442,	4.27285
6800,	4.2741
7157,	4.25887
7513,	4.28688
7871,	4.28696
8227,	4.28617
8584,	4.29981
8942,	4.30086
9301,	4.29804
9660,	4.30753
10016,	4.30849
10373,	4.31722
10730,	4.31513
11086,	4.31195
11444,	4.29918
11803,	4.30954
12161,	4.30707
12518,	4.31344
12874,	4.30062
13232,	4.28818
13587,	4.28588
13946,	4.27843
14303,	4.26544
14662,	4.27208
15022,	4.26688
15378,	4.25889
15735,	4.27467
16092,	4.26931
16448,	4.26311
16805,	4.27552
17165,	4.27493
17523,	4.26894
17879,	4.27687
18236,	4.27581
18594,	4.27721
18950,	4.27577
19308,	4.27666
19665,	4.28167
20024,	4.28183
20383,	4.282
20739,	4.28316
21097,	4.29259
21454,	4.2746
21809,	4.28273
22167,	4.28435
22525,	4.27576
22884,	4.28735
23242,	4.28524
23598,	4.27556
23956,	4.2877
24311,	4.28545
24669,	4.27995
25027,	4.27943
25386,	4.26958
25744,	4.26229
26100,	4.27114
26459,	4.2706
26815,	4.27275
27171,	4.27126
27529,	4.27415
27888,	4.27303
28246,	4.27591
28604,	4.27613
28960,	4.27757
29318,	4.27504
29672,	4.27779
30030,	4.27823
30388,	4.27846
30746,	4.27917
31106,	4.28322
31462,	4.28164
31820,	4.28373
32176,	4.2826
32533,	4.28223
32890,	4.27863
33249,	4.28468
33607,	4.28306
33965,	4.28547
34322,	4.28517
34679,	4.2851
35034,	4.28664
35392,	4.28626
35750,	4.28744
36109,	4.28905
36467,	4.28949
36824,	4.28884
37181,	4.28988
37538,	4.29044
37894,	4.287
38251,	4.29213
38610,	4.29333
38968,	4.28924
39327,	4.29451
39683,	4.29341
40041,	4.29463
40395,	4.2942
40754,	4.29356
41111,	4.29074
41471,	4.29488
41829,	4.29451
42185,	4.29647
42542,	4.29665
42899,	4.29288
43256,	4.29612
43613,	4.2856
43971,	4.25358
44331,	4.24709
44688,	4.25055
45045,	4.24627
45402,	4.25208
45758,	4.25228

In Fig. <ref>, we present the measured transcoding speed for various small prefixes of the Arabic files. We find that as long as the input has hundreds of characters, we can reach and exceed a billion characters decoded per second.

mark = none,
axis x line*=bottom,
axis y line*=left,
ylabel=billions of characters per second,
xlabel=number of characters (prefix),
legend pos=south east]
[black!30!blue, ultra thick] table [x=n, y=speed, col sep=comma] arabicutf16.dat;
UTF-16 to UTF-8;
[black!30!red, ultra thick] table [x=n, y=speed, col sep=comma] arabicutf8.dat;
UTF-8 to UTF-16;

Validating transcoding speed in billions of characters per second for prefixes of various lengths of the Arabic files using our techniques.

Historically, some processors could only read and write data when the memory address was a multiple of the data size. Older Intel processors could read and write at any address, but with a severe penalty for  unaligned memory addresses.
On recent processors (e.g., Intel's  Sandy Bridge microarchitecture launched in 2011), there is reportedly no measurable performance penalty for reading or writing misaligned memory operands [Fog, 2022]. However, there might be indirect penalties (e.g., accessing more cache lines).
In the hope of achieving better performance, we could require that our memory buffers start at an address divisible by 512 bits. However, we expect that the performance of the transcoding functions is generally unaffected by memory alignment on our test system.
Thus our benchmarking code does not align the memory in any particular manner, relying instead on the default behavior of the memory allocator.
To test the effect of the memory alignment of the input, we  transcoded the same data, but shifted by 0 to 512 bytes inside a buffer. Using one of our UTF-8 file (Arabic), we measured a difference of 2% between the fastest and slowest alignment when using our fast (AVX-512) transcoder.
We get a similar result if we transcode from a fixed input to offsetted locations inside a destination buffer. Our results suggest that memory alignment is likely not a significant factor.

§ CONCLUSION

It is not a priori obvious that character transcoding is amenable
to SIMD processing.

Earlier work achieved
high speeds but it required kilobytes of lookup tables [Lemire and Muła, 2022].
Our work indicates that the AVX-512 instruction-set extensions enables high speed for
tasks such as character transcoding—without lookup tables and using few instructions.
It suggests that some features of the AVX-512 instruction-set extensions
might serve as a reference for future instruction-set extensions. In particular, we find masked SIMD instructions (move, load, store, compress) with byte-level granularity useful.

Both Intel and AMD support AVX-512 instructions. They also both offer specialized compilers, tuned for their processors. Future work could compare the performance of our routines on more varied Intel and AMD  processors (e.g., Intel Rocket Lake and Sapphire Rapids, AMD Zen 4), using specialized compilers (e.g., from Intel and AMD) and hand-tuned assembly.
We could extend our benchmarks to cover a wider range of string.

§ ACKNOWLEDGEMENTS

We thank W. Muła who produced an early UTF-8 to UTF-16 transcoder using AVX-512
instructions. The version presented in this manuscript follows a different
design but Muła's work provided a crucial motivation.
We thank N. Boyer for his technical work on our software library, benchmarks,
and tests.

[Keiser and Lemire, 2021]
Keiser J, Lemire D.
Validating UTF-8 in less than one instruction per byte.
Software: Practice and Experience 2021;51(5).

[Lemire and Muła, 2022]
Lemire D, Muła W.
Transcoding billions of Unicode characters per second with SIMD
Software: Practice and Experience 2022;52(2):555–575.

[zpo, 2022]
z/Architecture Principles of Operation.
International Business Machines Corporation, fourteenth ed.; 2022,
document SA22-7832-13.

[Muła and Lemire, 2020]
Muła W, Lemire D.
Base64 encoding and decoding at almost the speed of a memory copy.
Software: Practice and Experience 2020;50(2):89–97.

[Hoffman and Yergeau, 2000]
Hoffman P, Yergeau F, UTF-16, an encoding of ISO 10646; 2000.
Internet Engineering Task Force, Request for Comments: 3629.
<https://tools.ietf.org/html/rfc2781> [last checked July 2021].

[Yergeau, 2003]
Yergeau F, UTF-8, a transformation format of ISO 10646; 2003.
Internet Engineering Task Force, Request for Comments: 3629.
<https://tools.ietf.org/html/rfc3629> [last checked July 2021].

[Cameron, 2008]
Cameron RD.
A case study in SIMD text processing with parallel bit streams:
UTF-8 to UTF-16 transcoding.
In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and
practice of parallel programming ACM; 2008. p. 91–98.

[Inoue et al., 2008]
Inoue H, Komatsu H, Nakatani T.
Accelerating UTF-8 Decoding Using SIMD Instructions (in Japanese).
Information Processing Society of Japan Transactions on Programming

[Gatilov, 2012]
Gatilov S, utf8lut: Vectorized UTF-8 converter; 2012.
<https://bit.ly/3qI7BVQ> [last checked October 2022].

[Intel Corporation, 2023]
Intel Intrinsics Guide; 2023.
[last checked June 2023].

[sdm, 2022]
Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2.
Intel Corporation; 2022, order number 325383-077US.

[Fog, 2022]
Fog A.
Instruction tables: Lists of instruction latencies, throughputs and
micro-operation breakdowns for Intel, AMD and VIA CPUs.
In: Optimization Manuals, vol. 4 published online at
<https://agner.org/optimize>; 2022.

[Abel and Reineke, 2019]
Abel A, Reineke J.
uops.info: Characterizing Latency, Throughput, and Port Usage of
Instructions on Intel Microarchitectures.
In: ASPLOS ASPLOS '19, New York, NY, USA: ACM; 2019. p. 673–686.

[Fog, 2022]
Fog A.
The microarchitecture of Intel, AMD and VIA CPUs: An
optimization guide for assembly programmers and compiler makers.
In: Optimization Manuals, vol. 3 published online at
<https://agner.org/optimize>; 2022.

[Abel and Reineke, 2022]
Abel A, Reineke J.
uiCA: Accurate Throughput Prediction of Basic Blocks on Recent
Intel Microarchitectures.
In: Rauchwerger L, Cameron K, Nikolopoulos DS, Pnevmatikatos D,
editors. ICS '22: 2022 International Conference on Supercomputing, Virtual
Event, USA, June 27-30, 2022 ICS '22, ACM; 2022. p. 1–12.

[Matz et al., 2012]
Matz M, Hubička J, Jaeger A, Mitchell M, System V Application Binary
Interface AMD64 Architecture Processor Supplement; 2012.
Draft Version 0.99.6.

[Najafi et al., 2021]
Najafi A, Tai A, Wei M.
Systems Research is Running out of Time.
In: Proceedings of the Workshop on Hot Topics in Operating Systems
HotOS '21, New York, NY, USA: Association for Computing Machinery; 2021. p.

[Downs, 2020]
Downs T, Ice Lake AVX-512 Downclocking; 2020.
[last checked July 2022].

[Unicode, Inc., 2010]
International Components for Unicode (ICU); 2010.
<http://site.icu-project.org> [last checked July 2021].

§ UTF-8 TO UTF-16: SUMMARY OF VARIABLES

\begin{equation*}
\begin{tabular}{ccp{0.535\textwidth}c}
\toprule
\emph{symbol}&\emph{type}&\emph{description}&\emph{Eq.}\\
\midrule
$w_{\mathrm{in}}$&byte vector&input vector&---\\
$m_1$&byte mask&1-byte sequence lead bytes in~$w_{\mathrm{in}}$&(\ref{8to16:m1})\\
$m_{234}$&byte mask&2/3/4-byte sequence lead bytes in~$w_{\mathrm{in}}$&(\ref{8to16:m234})\\
$m_2$&byte mask&2-byte sequence lead bytes in~$w_{\mathrm{in}}$&---\\
$m_{34}$&byte mask&3/4-byte sequence lead bytes in~$w_{\mathrm{in}}$&(\ref{8to16:m34})\\
$m_3$&byte mask&3-byte sequence lead bytes in~$w_{\mathrm{in}}$&(\ref{8to16:m3})\\
$m_4$&byte mask&4-byte sequence lead bytes in~$w_{\mathrm{in}}$&(\ref{8to16:m4})\\
$m_{1234}$&byte mask&lead bytes in~$w_{\mathrm{in}}$&(\ref{8to16:m1234})\\
$m_{+1}$&byte mask&second byte of each sequence in~$w_{\mathrm{in}}$&(\ref{8to16:mplus1})\\
$m_{+2}$&byte mask&third byte of each sequence in~$w_{\mathrm{in}}$&(\ref{8to16:mplus2})\\
$m_{+3}$&byte mask&fourth byte of each sequence in~$w_{\mathrm{in}}$&(\ref{8to16:mplus3})\\
$m_{\mathrm{end}}$&byte mask&last byte of each sequence in~$w_{\mathrm{in}}$&(\ref{8to16:mend})\\
$M_3$&word mask&3-byte characters in~$W_{\mathrm{out}}$&(\ref{8to16:M3})\\
$M_{\mathrm{hi}}$&word mask&high surrogates in~$W_{\mathrm{out}}$&(\ref{8to16:Mhi})\\
$M_{\mathrm{lo}}$&word mask&low surrogates in~$W_{\mathrm{out}}$&(\ref{8to16:Mlo})\\
$w_{\mathrm{stripped}}$&byte vector&$w_{\mathrm{in}}$ with tag bits stripped off&(\ref{8to16:wstripped})\\
$P$&word vector&indices of last-in-sequence bytes in~$w_{\mathrm{in}}$&(\ref{8to16:P})\\
$m_{-1}$&byte mask&mask to admit only $2^{\mathrm{nd}}$-last bytes of~$w_{\mathrm{in}}$&(\ref{8to16:mminus1})\\
$m_{-2}$&byte mask&mask to admit only $3^{\mathrm{rd}}$-last bytes of~$w_{\mathrm{in}}$&(\ref{8to16:mminus2})\\
$W_{\mathrm{end}}$&word vector&last byte of each sequence in~$w_{\mathrm{in}}$&(\ref{8to16:Wend})\\
$W_{-1}$&word vector&second-last byte of each sequence in~$w_{\mathrm{in}}$&(\ref{8to16:Wminus1})\\
$W_{-2}$&word vector&third-last byte of each sequence in~$w_{\mathrm{in}}$&(\ref{8to16:Wminus2})\\
$W_{\mathrm{sum}}$&word vector&$W_{\mathrm{end}}$, $W_{-1}$, and~$W_{-2}$ bits assembled&(\ref{8to16:Wsum})\\
$W_{\mathrm{out}}$&word vector&$W_{\mathrm{end}}$ with surrogates fixed up&(\ref{8to16:Wout})\\
$M_{\mathrm{out}}$&word mask&valid words in~$W_{\mathrm{out}}$&(\ref{8to16:Mout})\\
$m_{\mathrm{processed}}$&byte mask&last byte of each sequence in~$M_{\mathrm{out}}$&(\ref{8to16:mprocessed})\\
$n_{\mathrm{in}}$&integer&number of $w_{\mathrm{in}}$~bytes processed&(\ref{8to16:nin})\\
$n_{\mathrm{out}}$&integer&number of words written out&(\ref{8to16:nout})\\
$\ell$&integer&number of input bytes left to process&---\\
$b$&byte mask&input bytes left to process&(\ref{8to16:b})\\
$m_c$&byte mask&where continuation bytes should be in~$w_{\mathrm{in}}$&(\ref{8to16:mc})\\
$m_{\mathrm{pre}}$&byte mask&$w_{\mathrm{in}}$ bytes preceding first mismatch&(\ref{8to16:mpre})\\
$M_{<\codepoint{800}}$&word mask&overlong 3-byte characters in~$W_{\mathrm{out}}$&(\ref{8to16:M800})\\
$M_{3s}$&word mask&3-byte characters encoding surr. in~$W_{\mathrm{out}}$&(\ref{8to16:M3s})\\
$M_{4s}$&word mask&surrogates not encoding surr. in~$W_{\mathrm{out}}$&(\ref{8to16:M4s})\\
\bottomrule
\end{tabular}
\end{equation*}

Variables pertaining to the fast paths are not listed.

§ UTF-16 TO UTF-8: SUMMARY OF VARIABLES

\begin{equation*}
\begin{tabular}{ccp{0.54\textwidth}c}
\toprule
\emph{symbol}&\emph{type}&\emph{description}&\emph{Eq.}\\
\midrule
$W_{\mathrm{in}}$&word vector&input vector&---\\
$L$&word mask&position of lookahead word&(\ref{16to8:L})\\
$M_{234}$&word mask&words that are 2--4-byte characters&(\ref{16to8:M234})\\
$M_{12}$&word mask&words that are 1- and 2-byte characters&(\ref{16to8:M12})\\
$M_{\mathrm{hi}}$&word mask&words that are high surrogates&(\ref{16to8:Mhi})\\
$M_{\mathrm{lo}}$&word mask&words that are low surrogates&(\ref{16to8:Mlo})\\
$W_{\mathrm{lo}}$&dword vector&$W_{\mathrm{in}}$ shifted to the right by one element&---\\
$W_{\mathrm{joined}}$&dword vector&$W_{\mathrm{in}}$ with high and low surrogates joined&(\ref{16to8:Wjoined})\\
$W_{\mathrm{shifted}}$&dword vector&$W_{\mathrm{joined}}$ bits shifted with \texttt{vpmultishiftqb}&(\ref{16to8:Wshifted})\\
$W_{\mathrm{tag}}$&dword vector&UTF-8 tag bits for $W_{\mathrm{out}}$&(\ref{16to8:Wtag})\\
$W_{\mathrm{out}}$&dword vector&$W_{\mathrm{in}}$ transcoded to UTF-8 with padding&(\ref{16to8:Wout})\\
$W_{\mathrm{keep}}$&dword vector&magic constant for which bytes to keep&(\ref{16to8:Wkeep})\\
$m_{\mathrm{keep}}$&byte mask&mask of $W_{\mathrm{out}}$ bytes we want to keep&(\ref{16to8:mkeep})\\
$w_{\mathrm{out}}$&byte vector&output string without padding&(\ref{16to8:wout})\\
$n_{\mathrm{out}}$&integer&length of $w_{\mathrm{out}}$&(\ref{16to8:nout})\\
$c$&integer&surrogate carry (in)&---\\
$c_{\mathrm{out}}$&integer&surrogate carry out&(\ref{16to8:cout})\\

$M_{\mathrm{hi-lo}}$&word mask&high surrogates not followed by low surr.&(\ref{16to8:Mhilo})\\
$M_{\mathrm{lo-hi}}$&word mask&low surrogates not preceded by high surr.&(\ref{16to8:Mlohi})\\
$\ell$&integer&number of input words left to process&(\ref{16to8:l})\\
$B$&word mask&input words left to process&(\ref{16to8:B})\\
\bottomrule
\end{tabular}
\end{equation*}

§ UTF-8 TO UTF-16: LISTING

The function uses the amd64 SysV calling convention.
Register  holds a pointer to the output buffer,
holds a pointer to the input buffer,
holds the length of the input buffer in bytes,
and  holds a pointer to a 64-bit variable to which the number of 16-bit words produced is written.
The function returns in  the number of input bytes consumed.

As an extension to Intel syntax, we write e. g.

\begin{equation*}
\mbox{vpbroadcastd\quad zmm30, =\texttt{0xc0c0c0c}}
\end{equation*}

to indicate that the operand is the address of a constant  placed somewhere in static storage.

Equations that implement an equation have that equation mentioned in a comment on the right.

v̄pmultishiftqb z̄mm26, zmm26, zmm26,  utf8_to_utf16le:

vpbroadcastdzmm30, =

vpaddbzmm31, zmm30, zmm30

vpbroadcastdzmm28, =

vpaddbzmm29, zmm38, zmm38

vpbroadcastdzmm20, =

vmovdqu8zmm27, $=(0, 1, \ldots, 63)$

vpternlogdzmm26, zmm26, zmm26,

vpbroadcastdzmm24, =

vpbroadcastdzmm21, =

vpbroadcastdzmm2, zmm22, =

vpaddwzmm23, zmm21, zmm21

vpaddwzmm25, zmm22, zmm21

kmovqk7, rax

kmovqk0, rax

cmprdx, 64

vmovdqu8zmm0, [rsi]

vpcmpltubk1, zmm0, zmm31(<ref>)

kortestdk1, k1

; 1-byte fast path

vpmovzxbwzmm1, ymm0

vmovdqu16[rdi], zmm1

addrsi, 32

subrdx, 32

addrdi, 64

cmprdx, 64

vpcmpnltubk2, zmm0, zmm30(<ref>)

vpcmpnltubk3, zmm0, zmm29(<ref>)

vpcmpltubk5{k2}, zmm0, zmm20(<ref>)

ktestqk5, k5(<ref>)

kmovqr12, k2

ktestqk3, k3

; 1/2-byte fast path

movecx, ebx(<ref>)

pdeprcx, rcx, r12(<ref>)

lzcntrcx, rcx

vpsubbzmm2{k2}{z}, zmm0, zmm20(<ref>)

korqk5, k2, k1(<ref>)

knotqk6, k2(<ref>)

vpcompressbzmm2{k2}{z}, zmm2(<ref>)

vpmovzxbwzmm2, ymm2(<ref>)

vpcompressbzmm1{k6}{z}, zmm0(<ref>)

vpmovzxbwzmm1, ymm1(<ref>)

vpsllwzmm2, zmm2, 6(<ref>)

vpaddwzmm1, zmm1, zmm2(<ref>)

vmovdqu16[rdi], zmm1

adcr12, r12(<ref>)

cmpr8, r12(<ref>)

addrsi, 64

subrsi, rcx

leardx, $\mathrm{[rdx+rcx-64]}$

addrdi, 64

cmprdx, 64

; default path

vpcmpnltubk4, zmm0, zmm28(<ref>)

kmovqr8, k1

kmovqr11, k4

kmovqr9, k3

orr8, r12(<ref>)

learax, $\mathrm{[r8+r11\times8]}$(<ref>)

andnr10, r11, r9(<ref>)

shrrax, 1(<ref>)

shlr11, 3(<ref>)

orrax, r11(<ref>)

knotqk5, k1(<ref>)

kmovqk6, rax

vpcompressbzmm7{k6}{z}, zmm27(<ref>)

vpmovzxbwzmm7, ymm7(<ref>)

vmovdqu8zmm6{k5}{z}, zmm30(<ref>)

vpandndzmm0, zmm6, zmm0(<ref>)

vpermbzmm1{k7}{z}, zmm7, zmm0(<ref>)

shlr9, 2(<ref>)

addr12, r12(<ref>)

orr9, r11(<ref>)

orr12, r9(<ref>)

cmpr8, r12(<ref>)

pextrcx, r11, rax(<ref>)

kmovdk2, ecx

shrrcx, 1(<ref>)

kmovdk1, ecx

kshiftrqk5, k5, 1(<ref>)

vpaddwzmm7, zmm7, zmm26(<ref>)

vmovdqu8zmm6{k5}{z}, zmm0(<ref>)

vpermbzmm2{k7}{z}, zmm7, zmm6(<ref>)

vpsllwzmm2, zmm2, 6(<ref>)

vpaddwzmm2, zmm1, zmm2(<ref>)

kandqk3, k3, k0(<ref>)

vpaddwzmm7, zmm7, zmm26(<ref>)

vmovdqu8zmm6{k3}{z}, zmm0(<ref>)

vpermbzmm3{k7}{z}, zmm6(<ref>)

vpsllwzmm3, zmm3, 12(<ref>)

vpaddwzmm1, zmm2, zmm3(<ref>)

movr9, rax(<ref>)

andecx, (<ref>)

andr9, rbx(<ref>)

pdepr9, rcx, r9(<ref>)

lzcntrcx, r9(<ref>)

addrsi, 64(<ref>)

subrsi, rcx(<ref>)

leardx, $\mathrm{[rdx+rcx-64]}$(<ref>)

popcntr9, r9(<ref>)

kmovdk4, r8d

vmovdqu16zmm2{k2}{z}, zmm25(<ref>)

vpsrlwzmm3, zmm1, 4(<ref>)

vpordzmm1, zmm2, zmm1(<ref>)

vpaddwzmm1{k1}, zmm3, zmm24(<ref>)

bzhir8d, ebx, r9d

vmovdqu16[rdi]{k4}, zmm1

leardi, $\mathrm{[rdi+r9\times2]}$

shlr10, 2(<ref>)

pextr10, r10, rax(<ref>)

kmovdk6, r10d

vpcmpltuwk4{k6}, zmm1, zmm23(<ref>)

vpsubwzmm2, zmm1, zmm22(<ref>)

vpcmpltuwk2{k6}, zmm2, zmm23(<ref>)

kordk2, k2, k4(<ref>)

vpcmpnltuwk4{k1}, zmm2, zmm21(<ref>)

kortestdk2, k4(<ref>)

cmprdx, 64

testrdx, rdx

; compute lengths and exit

subrsi, r8

subrdi, r9

shrrdi, 1

movrax, rsi

mov[rcx], rdi

; handle remaining tail bytes

bzhirbx, rbx, rbx(<ref>)

kmovqk1, rbx

vmovdqu8zmm0{k1}{z}, [rsi]

vpcmpltubk1, zmm0, zmm31(<ref>)

vpcmpnltubk2, zmm0, zmm30(<ref>)

vpcmpnltubk3, zmm0, zmm29(<ref>)

vpcmpltubk5{k2}, zmm0, zmm20(<ref>)

ktestqk5, k5(<ref>)

kmovqr12, k2

; bytes ,  present

kmovqrdx, k5

tzcntrdx, rdx

; lead and continuation bytes mismatched

xorr12, r8(<ref>)

tzcntrdx, r12(<ref>)

btr8, rdx

bzhirax, r8, rdx(<ref>)

movedx, 64(<ref>)

lzcntrax, rax(<ref>)

subedx, eax(<ref>)

; overlong encoding/sequence or surrogate

subrdi, r9

subrdi, r9

learsi, $\mathrm{[rsi+rcx-64]}$

kordk2, k2, k4(<ref>)

kmovdedx, k2

adcrax, rax(<ref>)

pdeprdx, rdx, rax(<ref>)

tzcntrdx, rdx(<ref>)

§ UTF-16 TO UTF-8: LISTING

The function uses the amd64 SysV calling convention.
Register  holds a pointer to the output buffer,
holds a pointer to the input buffer,
holds the length of the input buffer in 16-bit words,
and  holds a pointer to a 64-bit variable to which the number of bytes produced is written.
The function returns in  the number of input words consumed.

As an extension to Intel syntax, we write for example

\begin{equation*}
\mbox{vpbroadcastd\quad zmm30, =\texttt{0xc0c0c0c}}
\end{equation*}

to indicate that the operand is the address of a constant  placed somewhere in static storage.

Equations that implement an equation have that equation mentioned in a comment on the right.

v̄pmultishiftqb z̄mm26, zmm26, zmm26,  utf16le_to_utf8:

vpbroadcastdzmm31, =

vpslldzmm30, zmm31, 4

vpbroadcastdzmm29, =

vpbroadcastdzmm28, =

vpbroadcastdzmm27, =

vpbroadcastdzmm26, =

vpbroadcastdzmm25, =

vpternlogdzmm20, zmm20, zmm20,

kmovdk1, eax

movr8, rdi

xorr9, r9

xoreax, eax

cmprdx, 32

movdqu16zmm0, [rsi]

subrdx, 31

addrsi, 62

vpcmpnltuwk2{k1}, zmm0, zmm31(<ref>)

ktestdk2, k2

; 1-byte fast path

vpmovwb[rdi]{k1}, zmm0

addrdi, 31

xoreax, eax

cmprdx, 32

vpcmpltuwk3, zmm0, zmm30(<ref>)

ktestdk3, k1

; 1/2-byte fast path

kmovdeax, k2

vpsrlwzmm1, zmm0, 6(<ref>)

vpsllwzmm2, zmm0, 8(<ref>)

vpternlogdzmm1, zmm2, zmm29, (<ref>)

vpaddwzmm0{k2}, zmm1, zmm28(<ref>)

popcnteax, eax(<ref>)

vpblendmwzmm1{k1}, zmm20, zmm30(<ref>)

vpcmpnltubk3, zmm0, zmm1(<ref>)

vpcompressbzmm1{k1}{z}, zmm0(<ref>)

kmovqr10, k3

pextr10, r10, r10

kmovqk3, r10

vmovdqu8[rdi]{k3}, zmm1

leardi, $\mathrm{[rdi+rax+31]}$(<ref>)

xoreax, eax

cmprdx, 32

vpbroadcastqzmm23, $=(18, 12, 6, 0, 50, 44, 38, 32)$

vpbroadcastdzmm16, =(<ref>)

vmovdqa32zmm17, zmm16(<ref>)

vpanddzmm3, zmm0, zmm27

vpcmpequwk4{k1}, zmm3, zmm26(<ref>)

vpcmpequwk5, zmm3, zmm25(<ref>)

vextracti32x8ymm2, zmm0, 1

vpmovzxwdzmm1, ymm0

vpmovzxwdzmm2, yzmm2

kortestdk5, k4

; surrogate processing

valigndzmm3, zmm2, zmm1, 1

valigndzmm4, zmm1, zmm2, 1

kshiftrdk6, k4, 16

vmovdqa32zmm16{k4}, zmm22(<ref>)

vmovdqa32zmm17{k6}, zmm22(<ref>)

vpslldzmm1{k4}, zmm1, 10(<ref>)

vpslldzmm2{k6}, zmm2, 10(<ref>)

vpadddzmm3, zmm3, zmm24(<ref>)

vpadddzmm4, zmm4, zmm24(<ref>)

vpadddzmm1{k4}, zmm1, zmm3(<ref>)

vpadddzmm2{k6}, zmm2, zmm4(<ref>)

kmovdr10d, k4

kmovdr11d, k5

addeax, r10d(<ref>)

addeax, r10d(<ref>)

xoreax, r11d(<ref>)

shrr10d, 30(<ref>)

vpmultishiftqbzmm3, zmm23, zmm1(<ref>)

vpmultishiftqbzmm4, zmm23, zmm2(<ref>)

vpbroadcastdzmm21, =

knotdk2, k2

kandndk5, k5, k1

kshiftrdk7, k3, 16

kshiftrdk6, k2, 16

kshiftrdk4, k5, 16

vpslldzmm16{k3}, zmm28, 16(<ref>)

vpslldzmm17{k7}, zmm28, 16(<ref>)

vpblendmdzmm5{k5}, zmm20, zmm21(<ref>)

vpblendmdzmm6{k4}, zmm20, zmm21(<ref>)

vpternlogdzmm3, zmm29, zmm16, (<ref>)

vpternlogdzmm4, zmm29, zmm17, (<ref>)

vpslldzmm3{k2}, zmm1, 24(<ref>)

vpslldzmm4{k6}, zmm2, 24(<ref>)

vpcmpnltubk2, zmm3, zmm5(<ref>)

vpcmpnltubk3, zmm4, zmm6(<ref>)

kmovqr10, k2

kmovqr11, k3

vpcompressbzmm3{k2}{z}, zmm3(<ref>)

vpcompressbzmm4{k3}{z}, zmm4(<ref>)

pextrbx, r10, r10

popcntr10, r10(<ref>)

kmovqk2, rbx

pextrbx, r11, r11

popcntr11, r11(<ref>)

kmovqk3, rbx

vmovdqu8[rdi]{k2}, zmm3

vmovdqu8$\mathrm{[rdi+r10]}${k3}, zmm4

addrdi, r10

addrdi, r11

cmprdx, 32

subrdi, r9

testedx, edx

addrdi, r9

subrsi, rax

sarrsi, 1

learax, $\mathrm{[rsi+r9]}$

subrdi, r8

mov[rcx], rdi

movr9d, (<ref>)

bzhir9d, r9d, rdx(<ref>)

kmovdk1, r9d

vmovdqu16zmm0{k1}{z}, [rsi]

lear9, $\mathrm{[rdx-31]}$

xoredx, edx

; mismatched/lone surrogate found

xoreax, r11d

andneax, eax, r11d(<ref>)

shrr11d, 1(<ref>)

andnr11d, r11d, r11d(<ref>)

oreax, r11d(<ref>)

tzcntedx, eax(<ref>)

moveax, (<ref>)

bzhieax, eax, edx(<ref>)

kmovdk1, eax

kmovdeax, k5

andeax, 1

vmovdqu16zmm0{k1}{z}, zmm0

lear9, $\mathrm{[rdx-31]}$

xoredx, edx