6
\$\begingroup\$

I'm doing some recreational programming in C (after spending some time in C++, but professionally using only PHP/JavaScript).

I wrote a UTF8 to UTF32 converter and just wanted to know if I made some obvious mistakes. (For example, is it a big no-no to malloc inside a function (because of possible memory leaks) – and if yes – how would you rather do it?)

#include <stdlib.h>
#include <stdint.h>

size_t utf8_strlen(uint8_t* text) {
    size_t i = 0;
    size_t num_chars = 0;

    while (text[i] != 0) {
        num_chars++;

        if ((text[i] & 0b10000000) == 0) {
            // 1 byte code point, ASCII
            i += 1;
        }
        else if ((text[i] & 0b11100000) == 0b11000000) {
            // 2 byte code point
            i += 2;
        }
        else if ((text[i] & 0b11110000) == 0b11100000) {
            // 3 byte code point
            i += 3;
        }
        else {
            // 4 byte code point
            i += 4;
        }
    }

    return num_chars;
}

uint32_t* utf8_to_utf32(uint8_t* text) {
    size_t num_chars = utf8_strlen(text);
    uint32_t* c = malloc(sizeof(uint32_t) * num_chars);
    size_t i = 0;

    for (size_t n = 0; n < num_chars; n++) {
        if ((text[i] & 0b10000000) == 0) {
            // 1 byte code point, ASCII
            c[n] = (text[i] & 0b01111111);
            i += 1;
        }
        else if ((text[i] & 0b11100000) == 0b11000000) {
            // 2 byte code point
            c[n] = (text[i] & 0b00011111) << 6 | (text[i + 1] & 0b00111111);
            i += 2;
        }
        else if ((text[i] & 0b11110000) == 0b11100000) {
            // 3 byte code point
            c[n] = (text[i] & 0b00001111) << 12 | (text[i + 1] & 0b00111111) << 6 | (text[i + 2] & 0b00111111);
            i += 3;
        }
        else {
            // 4 byte code point
            c[n] = (text[i] & 0b00000111) << 18 | (text[i + 1] & 0b00111111) << 12 | (text[i + 2] & 0b00111111) << 6 | (text[i + 3] & 0b00111111);
            i += 4;
        }
    }

    return c;
}

Edit:

I've posted an updated version of the code to GitHub for anyone that is interested: https://github.com/s22h/cutils/blob/master/include/s22h/unicode.h

\$\endgroup\$
  • 1
    \$\begingroup\$ I just realised that I'm missing the null terminator at the end of the UTF32 string. \$\endgroup\$ – S22h Jun 30 '18 at 16:24
5
\$\begingroup\$

There are two main things to talk about: checking the input, and buffer handling (your malloc question).

It's a very bad idea to do things like array[i + 1], unless you're absolutely, 100% sure that this refers to memory that is both allocated and part of the string. If it's not allocated, your program is begging for a crash; if it's not part of the string, it's a vulnerability issue and every script kiddie will be able to read your process' memory.

Checking the input

Unless you're absolutely, 100% sure that your user will be supplying you with a valid, NULL-terminated UTF-8 string, you definitely need to do some checking. Note that when I say "user", I mean the developer who will be using your functions.

When writing APIs, it really helps to write, or at least think about, some usage code first, in order to get an idea of what developers would need and how your code will be used. This will help again later, when discussing your malloc question.

Now, think about your general use cases. The developer gets some input through a socket, file, hardware device, form field, whatever. Sockets, files and hardware are prone to losing some bytes due to many different reasons. Forms are generally safe, but you will come across a library that will leave off bytes of the last UTF-8 character when you give it a too small buffer, or not null-terminate the string when the last character fits exactly in the buffer (some C standard lib functions are guilty of the latter). Malicious users may also try to exploit the form input field.

Out of all these, only the form field will be naturally NULL-terminated (probably). With all the others, you get a stream of data that simply ends at some point. So you're forcing the user to manually add the NULL byte, which could possibly lead to reallocation... you can see it's not a good idea.

The developer, however, knows exactly how many bytes he got. Why not exploit this? Rewrite your utf8_strlen function like this:

size_t utf8_strlen(uint8_t* text, size_t nb_text, size_t* nb_valid);

Do pretty much the same thing you were doing, however:

  1. Do not blindly increment i without testing whether i + NUM_BYTES_IN_NEXT_CHAR <= nb_text
  2. Stop immediately if that fails
  3. Stop immediately at a null byte, even if you've used less than nb_text bytes
  4. Stop when you've used nb_text bytes
  5. You may check that every single byte conforms to the UTF-8 standard. Depends on how thorough you want to be. Best to do it anyways.
  6. In short, only increment i when you're sure that you've got enough bytes left for the next character, and all bytes of the next character are valid UTF-8. Don't increment i at the terminating null byte and immediately stop.
  7. In the end, set *nb_valid = i. This allows the user to check how many bytes were valid UTF-8. Note that text + *nb_valid would point to the byte immediately after the last valid UTF-8 character. If the string ended with a null byte, text + *nb_valid would point to it instead.
  8. Be nice, and allow nb_valid to be a NULL pointer if the developer doesn't care about this information.
  9. Return the number of valid characters parsed.

Now that you're sure you're only going through valid UTF-8, your utf8_to_utf32 can remain the same. Just add the needed parameters:

uint32_t* utf8_to_utf32(uint8_t* text, size_t nb_text, size_t* nb_valid) {
    size_t num_chars = utf8_strlen(text, nb_text, nb_valid);
    /* ... rest is the same ... */
}

... but do consider what the previous answers mentioned, especially the portability issue of left-shifts, if you plan to program arduinos or other microcontrollers.

Buffer handling

is the reason C is hard. But again, let's think about the use cases. At first, allocating the buffer for the user may seem very helpful, but actually it's rarely something that the user wants. Besides, it burdens them with freeing the buffer, which sucks.

  1. Let's say I'm reading a file or some socket line by line. I'd actually want to allocate just one buffer, and re-use it for each line (reallocating or doing partial reads if I get a very long line). Thus, I'd like for utf8_to_utf32 to write to a particular buffer that I give it. Much better than having many, many allocations and deallocations.
  2. Let's say I'm updating some user input. In most cases I'd already have a UTF-32 buffer where the old user input is stored, and I want to update it. Again, I'd like for utf8_to_utf32 to write to a particular buffer.
  3. I may wish to concatenate or append text. Again, writing to a particular buffer.

So it seems you don't want to actually allocate the buffer, which is just dandy, since the best memory management is none at all. (Side note: the more experienced a C developer, the less you'll see them messing around with memory and allocations, for example see Casey Muratori [1] [2] [3], a very experienced C developer).

The function signature changes to:

void utf8_to_utf32(uint8_t* text, size_t nb_text, uint32_t* out_buf, size_t* nb_valid) {
    /* don't allocate c, replace c with out_buf */
}

Great, but how will you ensure that there's enough space in out_buf? Two options, each with its pros and cons.

A. Let the user worry about it

You're already providing a function - utf8_strlen, that will let the developer know how many characters to allocate for the buffer (plus one more for the NULL-terminator). If they don't, then that's their problem. Many standard lib functions operate like this: for example mbstowcs.

B. You worry about it

Add another parameter to the function that tells you the size of out_buf. You should never write more than this number of characters. This is a bit safer, though the programmer can of course still lie. This will make your code a bit more complicated, and will allow for partial conversions, though this usually falls under the YAGNI principle. Again, many standard lib functions operate like this too: for example strncpy, snprintf

Pick your poison and keep it consistent

People are familiar with both styles, so choose whatever you prefer and keep it consistent if you decide to add more functions later.

Now the only question that remains is what to do with the return value, which is currently void. Looking at the standard lib functions, you'll see that they would usually return the number of characters written to out_buf.

Another reasonable thing to do would be to return 1 or 0, based on whether the input UTF-8 string was valid all the way through, or there was some invalid data. I'm suggesting it because the check would be

is_utf8_valid = (nb_text == *nb_valid) || (text[*nb_valid] == '\0');

which is something you don't want to bother the user with getting right.

\$\endgroup\$
  • 3
    \$\begingroup\$ A small note about strncpy. Please be careful when using it. It does not always \0 terminate. It's not meant for C strings, but for "fixed length, \0 padded, possibly not terminated" strings. \$\endgroup\$ – domen Sep 5 '18 at 15:16
4
\$\begingroup\$

Welcome back to C

Binary constants are not part of standard C - yet

// 0b10000000
0x80

Lack of error detection

i += 2;, i += 3 or i += 4 in utf8_strlen() assumes the characters skipped over are of the proper form 0b10......

Instead test for that. utf8_strlen() then needs some way to convey an error. Perhaps utf8_string_size(), which includes the space needs for a null character. Then a return of 0 implies error.

Allocation error / missing null character

uint32_t* c = malloc(sizeof(uint32_t) * num_chars); does not allocate enough for a terminating null character to make a string.

Rather than allocate to the size of a type, use the size of the referenced object. It is easier to code right, review and maintain.

// uint32_t* c = malloc(sizeof(uint32_t) * num_chars);
uint32_t* c = malloc(sizeof *c * (num_chars + 1));
if (c == NULL) {
  // TBD Handle out of memory somehow.
  return NULL;
}
...
c[n] = '\0';

Bug with 16 bit int/unsigned

Avoid assuming 32 bit int. text[i] & 0b00000111) << 18 is undefined behavior with 16-bit int. Further better to use unsigned types with shifting/masking.

#include <stdint.h>

// (text[i] & 0b00000111) << 18
(text[i] & UINT32_C(0x07)) << 18

Use const

Using const allows const strings to be processed and conveys to the user of utf8_strlen() that. Recall a user of code may only see the header. It can allows for some optimizations too.

// size_t utf8_strlen(uint8_t* text) {
size_t utf8_strlen(const uint8_t* text) {
\$\endgroup\$
  • \$\begingroup\$ Also, binary numbers are very long. I cannot look at the source code and determine that 0b10000000 is the constant that I think it should be. With 0x80, that's something I can read. \$\endgroup\$ – gnasher729 Jun 30 '18 at 20:19
  • \$\begingroup\$ @gnasher729 True. I look forward to constants that allow a tick like 1'234'567, 0x89AB'CDEF, 0b0100'0010 - maybe in the next standard update? \$\endgroup\$ – chux - Reinstate Monica Jun 30 '18 at 21:00
4
\$\begingroup\$

Portability

In calculations like

c[n] = (text[i] & 0b00000111) << 18 | (text[i + 1] & 0b00111111) << 12 | (text[i + 2] & 0b00111111) << 6 | (text[i + 3] & 0b00111111);

all operands are promoted to int. That is a 32-bit integer on most platforms, but the C standard only requires that int has at least 16 bits, which means that the left-shift can overflow.

Better convert all bytes to uint32_t explicitly before shifting them:

c[n] = ((uint32_t)text[i] & 0b00000111) << 18
        | ((uint32_t)text[i + 1] & 0b00111111) << 12
        | ((uint32_t)text[i + 2] & 0b00111111) << 6
        | ((uint32_t)text[i + 3] & 0b00111111);

or, more verbosely:

uint32_t b0 = text[i]     & 0b00000111;
uint32_t b1 = text[i + 1] & 0b00111111;
uint32_t b2 = text[i + 2] & 0b00111111;
uint32_t b3 = text[i + 3] & 0b00111111;
c[n] = (b0 << 18) | (b1 << 12) | (b2 << 6) | b3;
\$\endgroup\$
  • \$\begingroup\$ "truly portable" would not assume optional types like uint32_t exist - yet that is only a very small exception. "truly portable" would not use compiler extensions like binary constants. \$\endgroup\$ – chux - Reinstate Monica Jun 30 '18 at 19:06
  • \$\begingroup\$ @chux: You are right (but those problems would be caught by the compiler and not go unnoticed). I have removed the phrase “truly portable” – thank you for the feedback. \$\endgroup\$ – Martin R Jun 30 '18 at 19:21
4
\$\begingroup\$

Magic numbers

The implementation uses them a lot. While the bit-notation helps with indicating what is happening, it doesn't show the intention. What reads clearer:

if((text[i] & 0b1000000) == 0)

or

if((text[i] & UTF8_ONE_BYTE_MASK) == UTF8_ONE_BYTE_COUNT)

Error handling

It isn't guaranteed that only valid UTF8 strings will be given to this code. I don't see any error signaling for those cases.

Code duplication

All those checks for how many UTF8 bytes encode one UTF32 byte are repeated in both function. These could easily be extracted into one function.

Missing null-terminator on UTF32 string

As you realized in a comment, the UTF32 string doesn't have a null terminator. This is easily fixable, though

Possible rewritten code

#include <stdlib.h>
#include <stdint.h>

#define UTF8_ONE_BYTE_MASK 0b10000000
#define UTF8_ONE_BYTE_COUNT 0

#define UTF8_TWO_BYTE_MASK 0b11100000
#define UTF8_TWO_BYTE_COUNT 0b11000000

#define UTF8_THREE_BYTE_MASK 0b11110000
#define UTF8_THREE_BYTE_COUNT 0b11100000

#define UTF8_FOUR_BYTE_MASK 0b11111000
#define UTF8_FOUR_BYTE_COUNT 0b11110000

// This one could use a better name, I just don't know a better one (yet?)
#define UTF8_OTHER_MASK 0b00111111

size_t utf8_codepoint_size(uint8_t text) {
    if((text & UTF8_ONE_BYTE_MASK) == UTF8_ONE_BYTE_COUNT) {
        return 1;
    }

    if((text & UTF8_TWO_BYTE_MASK) == UTF8_TWO_BYTE_COUNT) {
        return 2;
    }

    if((text & UTF8_THREE_BYTE_MASK) == UTF8_THREE_BYTE_COUNT) {
        return 3;
    }

    // TODO: what should happen if a byte with prefix 0b10xxxxxx is passed?
    return 4;
}

size_t utf8_strlen(uint8_t* text) {
    size_t i = 0;
    size_t num_chars = 0;

    while (text[i] != 0) {
        num_chars++;

        // TODO: error handling?
        i += utf8_codepoint_size(text[i]);
    }

    return num_chars;
}

uint32_t* utf8_to_utf32(uint8_t* text) {
    size_t num_chars = utf8_strlen(text) + 1;
    uint32_t* c = malloc(sizeof(uint32_t) * num_chars);
    size_t i = 0;

    for (size_t n = 0; n < num_chars; n++) {
        size_t byte_count = utf8_codepoint_size(text[i]);

        switch(byte_count) {
        case 1:
            c[n] = (text[i] & ~UTF8_ONE_BYTE_MASK);
            break;

        case 2:
            c[n] = (text[i] & ~UTF8_TWO_BYTE_MASK) << 6 | (text[i + 1] & UTF8_OTHER_MASK);
            break;

        case 3:
            c[n] = (text[i] & ~UTF8_THREE_BYTE_MASK) << 12 | (text[i + 1] & UTF8_OTHER_MASK) << 6 | (text[i + 2] & UTF8_OTHER_MASK);
            break;

        case 4:
            c[n] = (text[i] & ~UTF8_FOUR_BYTE_MASK) << 18 | (text[i + 1] & UTF8_OTHER_MASK) << 12 | (text[i + 2] & UTF8_OTHER_MASK) << 6 | (text[i + 3] & UTF8_OTHER_MASK);
            break;

        // TODO: error handling?
        }

        i += byte_count;
    }

    return c;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ In this case, I wouldn't call it "magic numbers", it's numbers that are inherent part of the Unicode standard and cannot be any different. \$\endgroup\$ – gnasher729 Jun 30 '18 at 20:18
  • 3
    \$\begingroup\$ @gnasher729: "Cannot be any different" - I don't see how that makes any difference. As far as I understand it, every directly used literal (string, number, ...) in code whose meaning isn't immediately obvious at a first glance is a magic number, and thus should have a name. Plus it reduces the number of places for value-changing typos. \$\endgroup\$ – hoffmale Jun 30 '18 at 20:44
  • 1
    \$\begingroup\$ What about (static) constants instead of macro definitions? \$\endgroup\$ – Martin R Jun 30 '18 at 21:28
2
\$\begingroup\$

You're right to be concerned about allocating memory in the function. One obvious problem is that malloc() can return a null pointer, so we need to check for that before we think about using it:

uint32_t* c = malloc(sizeof *c * num_chars);
if (!c) { return c; }

Making two passes over the input can be problematic, as then we have two pieces of code which need to agree closely, even for malformed input. You might consider a single pass with occasional realloc(), to avoid overrunning the buffer.

Returning allocated memory can be inconvenient for the caller, and result in extra copying. For example, the user may have a memory-mapped file, and would like the converted string to be written directly to that file, instead of receiving allocated memory which needs to be copied. For this reason, I recommend an interface that allows the user to specify where to write the output, and how big that output space is (consider snprintf() as a possible model).

\$\endgroup\$
  • 1
    \$\begingroup\$ Actually, the first count can be sloppy, as long as it doesn't under-count. The first approximation of one codepoint per codeunit might even be enough. So, at most one reallocation at the end to disown excess space. \$\endgroup\$ – Deduplicator Jun 4 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.