Saturday, August 11, 2012

Multibyte and wide character strings in C (addendum)

Last time I wrote about multibyte character strings in C, and said that the easiest way to deal with them is to convert them to wide character strings. Unfortunately, there is an issue with the wide character wchar_t type; it just so happens that its size is 32 bits on UNIX (and alike) platforms, while it is only 16 bits wide on the Windows platform. On UNIX mbstowcs() converts to a UTF-32 string, and on Windows mbstowcs() converts to a UTF-16 string. What this means is that everything I talked about in last week's post is quite alright on UNIX and not so cool on Windows. I'm a UNIX programmer and I don't work on Windows, but I do care about portability across platforms, and the wchar_t is hopelessly broken across platforms.

So, what is going on? The C standard actually says that the size of wchar_t is compiler dependent, and that portable code should not use wchar_t. Oddly enough, C does provide a complete set of functions for handling wide character strings (!). Since wchar_t is not defined as a portable type, then a) how are we supposed to work with strings and unicode, and b) what is it doing in the standard in the first place.
The origin of the problem stems from the fact that Unicode started out with just 16 bits code points, but later realized they were going to need a few bits more. Hence the jump to 32 bits. By that time, Microsoft was long happily using a 16 bits wchar_t. When others started supporting unicode, they implemented wchar_t as a 32 bits value so it could hold a single UTF-32 character. Portability ended right there.
Consequently, wchar_t was a good idea that turned out as a failure.

Today, if you want to work around this problem, you are going to have to work with uint32_t for characters and roll your own string functions, including your own UTF-8 encoding and decoding functions. It's pretty sad. There is a bit of good news on the horizon; the proposed ISO C11 standard includes two new data types: char16_t and char32_t and associated conversion functions. Missing however are string handling functions for these types. Basically, it is discouraged that you use strings in their UTF-32 form.
There is no compiler today that implements C11. These new character types are also present in C++11, and recent versions of the g++ and clang++ compilers do support them.

Tuesday, August 7, 2012

Multibyte and wide character strings in C

Over a century ago, man transmitted messages over a wire using a four bit character encoding scheme. Much later, the ASCII table became the standard for encoding characters, using seven bits per character. ASCII is nice for representing English text but it can't work well for other languages, so nowadays we have unicode. Unicode defines code points (numbers) for characters and symbols of every language there is, or was. Documents aren't written in raw unicode; we use UTF-8 encoding.

UTF-8 encoding is a variable length encoding and uses one to four bytes to encode characters. This means some characters (like the ones in the English alphabet) will be represented by a single byte, while others may take up to two, three, or four bytes.
For C programmers using char pointers this means:
  • strlen() does not return the number of characters in a string;
  • strlen() does return the number of bytes in the string (minus terminating nul character)
  • buf[pos] does not address a character;
  • buf[pos] addresses a byte in the UTF-8 stream
  • buf[32] does not reserve space for 31 characters;
  • buf[32] might reserve space for only 7 characters ...
  • strchr() really searches for a byte rather than a character
If you want to be able to address and manipulate individual characters in multibyte character strings, the best thing you can do is converting the string to wide character format and work with that. A wide character is a 32-bit character.

The operating system is configured to work with a native character encoding set (which is often UTF-8, but could be something else). All I/O should be done using that encoding. So if you do a printf(), print the multibyte character string.

During initialization of your program (like in main()), set the locale. If you forget to do this, the string conversion may not work properly.
setlocale(LC_ALL, "");
Converting a multibyte character string to a wide character string:
mbstowcs(wstr, str, n);
Converting a wide character string back to a multibyte character string:
wcstombs(str, wstr, n);
One problem with these functions is estimating the buffer size. Either play it safe and assume each character takes four bytes, or write a dedicated routine that correctly calculates the needed size.

It's fun seeing your program being able to handle Chinese, Japanese, etcetera. For more on the subject, these two pages are highly recommended:

Monday, July 30, 2012

oolib: link with -loo

Just when it started to look like July was becoming the ‘month of Go’, I made a dramatic shift to C++. I don't even like C++ very much, but in fact Go made me go back to defeat an old enemy. Once upon a time I decided that programming in C and C++ should be easier [than it is] and set out to develop a library that allows you to have safe strings, automatically growing and bounds checking arrays, and dictionaries (associative arrays) in C. The holy grail of programming: the simplicity of Python but with the power of C. It turned out to be harder than I imagined, and resulted in thousands of lines of library code that were never actually meaningfully used. At some point I realized that such a beast is better implemented in C++ than C, and continued the holy mission, only to fail. And then came the intermezzo with Go.

Go is a funny language. There is just something about it that makes you think differently about programming. Go doesn't care about object orientation, it only matters if a class (or struct) implements the right functions to adhere to a protocol. Another thing Go does right is multithreading and communication using channels. It makes things easy. A lot of things in Go are easy, yet powerful.
It does have its quirks, I don't find Go code as easy to read as it should be. Go code typically has a lot of typecasts (or type conversions) because of its strict typing. And not totally unimportant, my colleagues don't like Go because they don't know it and stubbornly don't want to know it. That may be their problem, but it's also a problem of Go.

Back to libobjects, which now had three implementations in plain C and two others in C++. But something was wrong with it, and that something was the complexity of loose typing. The whole library leaned on the Objective-Cish idea that everything is a reference counted Object, and that arrays and dictionaries would be able to hold any type, just like they do in Python and in Objective-C. But looking at Go, it seems you can do perfectly without loose typing. In Go, arrays, maps, channels all are defined explicitly for a single type. And that's okay, things only get better with strict typing.

I took the golden advice of a co-worker that the library should be implemented using STL. I don't like writing large programs using STL, but it's chockfull of convenient standard templates perfectly fit for the job.
So for oolib, the new incarnation of the object library, I settled with C++'s template syntax: Array<int> is an array of integers and Dict<String> is a dictionary of strings. Add the Python string interface and stir in a bit of goroutines and channels, and oolib looks pretty nice. Just build with a C++ compiler and link with -loo.

Behind the scenes, oolib leans heavily on shared_ptr. The shared_ptr is a shortcut for having reference counted objects, but what's really strange is that you can't write efficient C++ code without it. Now consider that shared_ptr did not exist when C++ first entered the scene.
A consequence is that when you assign an array variable to another array, they both point at the same backing store. That's exactly what happens in Python too, so for now I'll leave it that way.

Performance-wise, oolib delivers what you expect it to: it's faster than Python, more fast than Go, and a fraction slower than pure C code.

A snippet of oolib code (that shows only a few features):
#include "oolib.h"

using namespace oo;

int main(int argc, char *argv[]) {
    if (argc <= 1) {
        print("usage: listdir [directory]");
        return 1;
    }

    Array<String> a;

    if (listdir(argv[1], a) < 0) {
        perror("listdir");
        return -1;
    }

    print("%v", &a);

    foreach(i, a)
        print("%v", &a[i]);

    return 0;
}
Finally, it begs the question whether this lib will be meaningfully used. Only time will tell, there are probably a zillion of personal libs like this one out there, and I'm glad to have mine. Mission accomplished.

Sunday, July 15, 2012

Go channels in good old C

Last week I wrote about goroutines and channels, and said that you could do the same thing in C by using pthreads and pipes. That's not exactly true. Although a pipe is well-suited for sending data from one thread to another, like in a parent-and-child-process situation, it's not going to work with multiple readers and writers. Well, how about a socketpair? No (!), same problem here. To implement something like a Go channel in C, you have to put in some extra effort.

The Go channel is a queue of items. Multiple threads may access the queue, and it is guaranteed that the concurrent access is safe and free of race conditions. In C you would implement such a queue as an array and include a mutex lock for doing mutual exclusion.
typedef struct {
    size_t max_items, num_items, item_size;
    void *items;
    pthread_mutex_t mutex;
    pthread_cond_t cv;
} chan_t;

chan_t *make_chan(size_t item_size, size_t max_items);
void read_chan(chan_t *c, void *restrict item);
void write_chan(chan_t *c, const void *item);
void close_chan(chan_t *c);
A channel can be initialized to hold any type. In standard C, "any type" means using a void pointer. Mind that because of this, the interface is not fully type-safe. It is up to the programmer to use the channel in the correct way. In C++ you would use a template and have type-safe code.

The items pointer points at an array of items for a buffered channel. For an unbuffered channel, set max_items to one. The mutex and the condition variable work together to take care of the locking. Reading from the channel will wait on the condition, while a write to the channel will signal the condition. Since C does not do automatic garbage collection, close_chan() will deallocate the channel. Certainly, close_chan() should be called in one thread only.

The full code is only like a hundred lines. Not too big, but too big to include here. With this code you can have threads easily communicate just like goroutines communicate over channels in Go. Having channels in C is nice. The main program code, the code that really matters, is so much easier to understand with channels as there are no mutex locks cluttering the code anymore. Now it's also possible to use Go idioms like waiting for all threads to finish using a channel (by writing a value of true to a chan bool named done).

You can write anything you like in C. Still, channels in Go are more powerful than what I presented here. In Go, you can select on channels. Mimicking Go's select in C is not easy ... (grinds teeth). But why bother with C anyway...? It's time to Go.