Can I slim this UTF8-encoding program?

Question

Below is my entire program. You can read what it does thanks to the comments and specifications in particular.

My question is: can it be improved? Would it be possible, for example, to avoid writing a fwrite() inside each if? Is there a good pattern that can be implemented somewhere in this code?

---

The entire program is base on this UTF8 model and also studies the case in which a bit occurs in the 32nd position.

---

#include <stdio.h>
#include <math.h>
#include <stdint.h>

double log(double a);

/*
* This program reads 4 byte codepoints (in BIG ENDIAN) from a file strictly called "input.data" and creates another file called "ENCODED.data" with the relative encoding in UTF8.
* 
* In order to compile this file, in Unix, you need to add the -lm clause because the library math.h function log() requires it.
* For example: gcc encoding.c -o encoding -lm
*/
int main() {

    unsigned char bufferCP[4]; //Buffer used to store the codepoints
    unsigned char bufferOut[6]; //Buffer used to store the UTF8-encoded codepoints

    FILE *ptr, *out;
    ptr = fopen("input.data", "rb"); //r for read, b for bynary
    out = fopen("ENCODED.data", "wb");

    int elem = 0, bytesRead = 0;
    unsigned char mask = 0x3F; //Mask used to keep bits interesting for analysis
    uint32_t codepoint = 0; //A codepoint must be an unsigned 32 bit integer

    //--------------------File-Reading--------------------
    while ((elem = fgetc(ptr)) != EOF) {
        //Stores the character in the buffer
        bufferCP[bytesRead++] = (unsigned char) elem;

        if (bytesRead == 4) { //A codepoint is ready to be managed              

            //Builds a codepoint from the buffer. Reads it in BIG ENDIAN.
            for(int j=3; j>=0; j--) {
                    codepoint <<= 8;
                    codepoint |= bufferCP[j];
            }
            //Searches the position of the most significant bit
            double logRes = (log(codepoint)/log(2)) + 1;
            int bitPos = (int) logRes;

            //--------------------UTF8-Encoding--------------------
            if (bitPos <= 7) {
                bufferOut[0] = (unsigned char) codepoint; //No need to manage this codepoint
                fwrite(bufferOut, 1, 1, out);

            } else if (bitPos <= 11) {
                bufferOut[0] = (codepoint >> 6) | 0xC0;
                bufferOut[1] = (codepoint & mask) | 0x80;
                fwrite(bufferOut, 1, 2, out); 

            } else if (bitPos <= 16) {
                bufferOut[0] = (codepoint >> 12) | 0xE0; 
                for(int i=1; i<3; i++)
                    bufferOut[i] = ((codepoint >> 6*(2-i)) & mask) | 0x80;
                fwrite(bufferOut, 1, 3, out);

            } else if (bitPos <= 21) {
                bufferOut[0] = (codepoint >> 18) | 0xF0; 
                for(int i=1; i<4; i++)
                    bufferOut[i] = ((codepoint >> 6*(3-i)) & mask) | 0x80;
                fwrite(bufferOut, 1, 4, out);

            } else if (bitPos <= 26) {
                bufferOut[0] = (codepoint >> 24) | 0xF8;
                for(int i=1; i<5; i++)
                    bufferOut[i] = ((codepoint >> 6*(4-i)) & mask) | 0x80;
                fwrite(bufferOut, 1, 5, out);

            } else if (bitPos <= 32) {
                if (bitPos == 32)
                    bufferOut[0] = (codepoint >> 30) | 0xFE; //UTF8-encoding first byte would be: 11111111?
                else
                    bufferOut[0] = (codepoint >> 30) | 0xFC;

                for(int i=1; i<6; i++)
                    bufferOut[i] = ((codepoint >> 6*(5-i)) & mask) | 0x80;
                fwrite(bufferOut, 1, 6, out);
            }

            bytesRead = 0; //Variable reset
        }
    }

}

Answer 1

Efficient file I/O

By default, files opened with fopen() are buffered, meaning that not every call to fread() or fwrite() will result in a system call. Instead, the C library has an internal buffer and will try to read and write larger chunks at a time. However, you are still paying for the overhead of a regular function call each time you call fread() and fwrite(). To avoid this, it is best that you read and write in large chunks in your own code as well.

While you could try to read in the whole file at once, or even use technique like mmap() to memory map the file, you can already get very good performance by reading and writing blocks of say 64 kilobytes at a time. This avoids using a lot of memory. Of course, you have to handle the last block not being exactly 64 kilobytes large, but that is quite easy to deal with.

Furthermore, fread() and fwrite() allow you to specify the size of an element and the number of elements you want to read, this comes in handy to ensure you read in a whole number of 4-byte codepoints.

I would structure your code like so:

uint32_t bufferIn[16384]; // 16384 4-byte code points = 64 kB
char bufferOut[65536];

size_t countIn;

while ((countIn = fread(bufferIn, sizeof *bufferIn, sizeof bufferIn / sizeof *bufferIn, ptr)) > 0) {
    // There are countIn codepoints in the buffer
    for (size_t i = 0; i < countIn; i++) {
         uint32_t codepoint = ...; // Convert bufferIn[i] to native endian here.

         // Write UTF-8 to bufferOut here.
         // If bufferOut is almost full, fwrite() it and start writing to it from the start.
    }
}

// Flush the remaining bytes in bufferOut here.

Don't use floating point math for integer problems

Avoid using floating point math when you are dealing with integers. It is hard to get it right, and converting int to double, doing some math operation, and then converting back again can be quite slow.

There are several ways to get the highest set bit in an integer. If you want a portable one, I recommend using one of the bit twiddling hacks. Sometimes compilers will even recognize such a bit twiddling hack and convert it to a single CPU instruction if possible.

Answer 2

• log is already declared in <math.h>. You don't need to declare it yourself. In fact, it could be harmful.

• As stated in another answer, do not use floating point math.

  In fact, you don't need to know the exact position of the leftmost bit. For your purposes, the value of codepoint is enough. For example, bitPos <= 7 is equivalent to codepoint < (1 << 8).

• I strongly recommend to separate the I/O from the conversion logic. Consider

  while (read_four_bytes(input_fp, bufferCP) == 4) {
      size_t utf_char_size = convert_to_utf(bufferCP, bufferOut);
      write_utf_char(bufferOut, utf_char_size);
  }
  

• DRY. All the conversion clauses look very similar. Consider refactoring them into a function, along the lines of

  convert_codepoint(uint32_t codepoint, int utf_char_size, char * bufferOut) {
      for (int i = 0; i < utf_char_size; i++) {
          bufferOut[i] = ((codepoint >> 6 * (utf_char_size - i)) & mask) | 0x80;
      }
      bufferOut[0] |= special_mask[utf_char_size];
  }
  

  and use it as

  if (codepoint < (1 << 8)) {
      convert_codepoint(codepoint, 1, bufferOut);
  else if (codepoint < (1 << 12)) {
      convert_codepoint(codepoint, 2, bufferOut);
  } ....
  

  The resulting cascade of if/elses may also be transformed into a loop.

Answer 3

• This program reads 4 byte codepoints (in BIG ENDIAN) from a file strictly called "input.data" and creates another file called "ENCODED.data" with the relative encoding in UTF8.

Needless to say, that's a weird way of storing code points. I know UTF-16, but UTF-32BE (just the code point in big endian form) is not widely used, although Python seems to use it to encode strings internally. Now that you know what this encoding is called, I wonder if you need to code this yourself or that you could have used a library.

* This program reads 4 byte codepoints (in BIG ENDIAN) from a file strictly called "input.data" and creates another file called "ENCODED.data" with the relative encoding in UTF8.

That it reads 4 bytes at a time is really an implementation detail. Generally we don't create conversion applications that restrict themselves to specific files (or even files, to be honest).

unsigned char bufferCP[4]; //Buffer used to store the codepoints

If you have to spell out what a variable means, then you're generally better off spelling it out in the variable name: utf32be_buffer would be a good variable name.

The value 4 doesn't have a meaning, which becomes a problem once you split the main method into functions (as you should).

unsigned char bufferOut[6]

What about utf8_buffer?

int elem = 0, bytesRead = 0;

Split the variable declaration to different lines. elem is also directly assigned, so assigning zero to it is completely unnecessary.

unsigned char mask = 0x3F; //Mask used to keep bits interesting for analysis

This comment really begs the question of the reader: which bits are "interesting"?

uint32_t codepoint = 0; //A codepoint must be an unsigned 32 bit integer

Utterly unnecessary comment. "must be" also begs the question: for this program or according to some kind of standard?

//--------------------File-Reading--------------------

What about read_into_buffer instead of a comment?

if (bytesRead == 4) { //A codepoint is ready to be managed              

Repeat of a literal, while utf32be_buffer is already assigned a size. Use that.

Again a comment that reads as if a method should be introduced. You can almost hear yourself defining them.

Finally, what happens if the file doesn't contain a multiple of 4 bytes? It seems like you're just removing the last bytes without warning or error.

//Builds a codepoint from the buffer. Reads it in BIG ENDIAN.

There is the name, although I would simply use convert_code_point().

for(int j=3; j>=0; j--) {

Another repeat of the same literal 4, but now disguised as a 3, i.e. 4 - 1. Great.

codepoint <<= 8;

I actually use a constant (Byte.SIZE) in Java for this, but you can be excused for using 8 here, especially since this code should perform well.

//Searches the position of the most significant bit
double logRes = (log(codepoint)/log(2)) + 1;
int bitPos = (int) logRes;

As already indicated, use bit ops for this. And a method please, here is an answer on StackOverflow for that.

bufferOut[0] = (unsigned char) codepoint; //No need to manage this codepoint   

What is "managing" a code point? When I first read the comment I was afraid you were going to skip it. Fortunately, that's not the case.

fwrite(bufferOut, 1, 1, out);

Just keep a variable of the number of bytes in the buffer and then write those in the end.

} else if (bitPos <= 32) {

We use zero based indexing in C-style languages. What is the chance that a significant bit is at position 32 according to you?

bytesRead = 0; //Variable reset

Would never have guessed that without the comment, I admit. It also shows that the name of the variable is wrong: it represents the number of bytes in the buffer, not the bytes read from the file.

Answer 4

regarding:

ptr = fopen("input.data", "rb"); 
out = fopen("ENCODED.data", "wb"); 

always check (!=NULL) the returned value to assure the operation was successful. If not successful (==NULL) then call:

perror( "your error message" ); 

to output both your error message and the text reason the system thinks the error occurred to stderr.

Answer 5

As others have said, don't use floating point math, but in some sense that's reviewing the wrong layer. The real issue behind that is that you don't need to be branching on a derived quantity, the number of bits. Instead branch on the codepoint value ranges (original input). For example (excerpt from my implementation):

} else if ((unsigned)wc < 0x800) {
    *s++ = 0xc0 | (wc>>6);
    *s = 0x80 | (wc&0x3f);
    return 2;
}

Not only is branching directly on the input quantity simpler than computing a derived quantity like number of bits; for the problem at hand (UTF-8) it's necessary in order to do proper error handling. Boundaries that are not exact numbers of bits (between D800 and DFFF, above 10FFFF) correspond erroneous inputs that should not be output as malformed UTF-8 but rejected in some manner.

Answer 6

Code fails to detect invalid code points

There are 1,112,064 valid unicode code points, not 2³².

The valid range is [0x0 - 0x10FFFF] except the sub-range of [0xD800 - 0xDFFF]. This later sub-range is for surrogates.

UTF-8 is not defined for 4-byte values outside this range. Code should not attempt to create a six-byte "UTF-8" unless it is calling it an obsolete 1993 version of UTF-8.

Better code would detect invalid sequences.

Code silently discard extra bytes

Should code read an extra final 1, 2 or 3 bytes, no error indication is provided.