Firstly, we must understand that Unicode inputs (whether in UTF-8, UTF-16 or UTF-32) can be correct or not. For example, the 4-byte sequence \xFF\xFF\xFF\xFF is not valid UTF-8. The sequence \x80\x80\x80 is also invalid UTF-8.

When transcoding inputs that we expect to be proper Unicode strings (e.g., from UTF-8 to UTF-16), we proceed in two steps:

1. A fast scan through the data determines the expected size of the transcoded output. This makes it possible for the user to allocate the necessary memory or to check that they have enough memory. Importantly, we do not need to validate the input at this stage: we only need to allocate enough memory so that we have enough of an output buffer. They key condition is that if the input is valid, then the computed output must be the exact output size needed.
2. In the second step, we actually transcode... usually with validation. We load the data and write it out transcoded. We can either transcode optimistically and report an error at the end, or we can constantly check for error, and stop early... as this gives up the ability to pinpoint the location of the error (useful for string debugging purposes).

One characteristic of this process is that it is non-allocating. The user allocates memory, we don't. That's important because the client might have its own needs in terms of memory allocation.

For example, given \xFF\xFF\xFF\xFF, the first step in a UTF-8 to UTF-16 transcoder, could (for example) determine that 16 bytes of output are required. Keep in mind that this first step is non-validating, so it might not detect. Similarly, the first step might decide that byte sequence \x80\x80\x80 as UTF-8 should produce zero bytes of output. The second step would detect an error. (I am giving these results as examples... In simdutf, the utf16_length_from_utf8 function (first step) generally counts 1 for each leading byte (so any byte that is not of the form 0b10xxxxxx), and an extra 1 for any byte with value greater or equal than 240.

The transcoding with replacement problem is different. What it does is that it can take any input string, including one that is not valid unicode. According to ISO 10646-1:2000, sections D.7 and 2.3c, malformed sequences (sequences that do not conform to the UTF-8 encoding standard) should be handled in the same manner as characters that are not part of the character set the device supports. Unsupported characters (those outside the device's adopted character subset) must be visibly indicated to the user by the device. In practice, malformed sequences are replaced with a replacement character, which is often U+FFFD. This character typically looks like a diamond with a question mark inside it (�) or a similar symbol, alerting the user that the original character could not be properly displayed.

You represent U+FFFD in UTF-32 as the 4-byte value 0x0000FFFD, in UTF-16 as the 2-byte value 0xFFFD, and in UTF-8 as the three-byte sequence 0xEF 0xBF 0xBD. This needs to be inserted everywhere you find an 'invalid sequence'. It is unclear exactly what 'invalid sequence' means (that is, it is underspecified in the standard as far as I can tell). However, an error in the input should lead at least one replacement character.

It is unclear whether the replacement character should be fixed, or whether it needs to provided as a parameter.

In any case, given \x80\x80\x80 as an UTF-8, we need to output... possibly 0xFFFD 0xFFFD 0xFFFD as UTF-16.

So how do we transcode with replacement efficiently?

One possible strategy goes as follows.

1. We make the first step validating. What it does is that it scans the input identify the errors, and computes the output size with replacement.
2. We then transcode as before.

But wait! In step 1, we have are validating. So we know where the errors happen, and how many there are. Or, at least, we can compute it. Do we repeat again the validation in step 2? That seems wasteful.

We could, in the new step 1, locate the errors and somehow save this information to some buffer. But that might require dynamic allocation. This breaks the model that we are non-allocating.

What else might we do?

Instead, we could try the following model.

1. Scan up to the first error in the input buffer. Record enough statistics so that you can compute the output buffer size if you were to transcode up to that point. The .NET library (C#) has such a function called GetPointerToFirstInvalidByte and accelerated it with SIMD in C#, see https://github.com/simdutf/SimdUnicode.
2. Ask the user to provide enough memory to decode up to this point.
3. Do the transcoding up to the first error, but this time use non-validating transcoding. You don't need to validate because you did it in step 1. We are using the memory provided by the user.
4. Investigate the error and output as many replacement characters as you need, asking the user to provide the necessary memory.
5. Go back to step 1 if you are not at the end.

That's complicated because we have a back and forth with the user.

For obvious reasons, we want to get the right high-level design before starting the implementation of the low-level functionality.

To transcode from UTF-8 to UTF-16 with replacement, ICU offers a low approach whereas you first provide a buffer and if it is not large enough, you will get a buffer overflow error and then you are expected to try again:

     /* convert the string from UTF-8 to UTF-16 */
    u_strFromUTF8(b1,b1Capacity,&b1Len,src,srcLength,status);
    if(*status == U_BUFFER_OVERFLOW_ERROR){
        /* reset the status */
        *status = U_ZERO_ERROR;
        b1 = (UChar*) malloc(b1Len * U_SIZEOF_UCHAR);
        b1Capacity = b1Len;
        u_strFromUTF8(b1, b1Capacity, &b1Len, src, srcLength, status);
    }

You can find its documentation online at

https://github.com/unicode-org/icu/blob/5b45e5c64b7487ded927759ad73637bab5184451/icu4c/source/common/unicode/ustring.h#L1290

Here is how Node.js used to do it...

ICU has also a high level approach which returns a string instance (ICU has its own string class):

auto str =
        U_ICU_NAMESPACE::UnicodeString::fromUTF8(std::string_view(data, size));

In the latter case, ICU handles the memory allocation for us. It is the most convenient approach, but it may require a copy of the data to the real destination.

The source code is online:

https://github.com/unicode-org/icu/blob/5b45e5c64b7487ded927759ad73637bab5184451/icu4c/source/common/unistr.cpp#L484

https://github.com/unicode-org/icu/blob/5b45e5c64b7487ded927759ad73637bab5184451/icu4c/source/common/unicode/unistr.h#L3641

The standard library iconv will convert as much as possible, incrementing the input and output buffer. It returns the number of replacements. When there is no enough space, errno is set to E2BIG. So you are expected to reallocate the output buffer on your own, or provide a generous buffer to begin with.

       #include <iconv.h>

       size_t iconv(iconv_t cd,
                    char **restrict inbuf, size_t *restrict inbytesleft,
                    char **restrict outbuf, size_t *restrict outbytesleft);