20
\$\begingroup\$

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. UTF8 model


#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
        }
    }

}
\$\endgroup\$
  • 3
    \$\begingroup\$ See stackoverflow.com/a/148766/5987 for a function to convert from wchar_t to UTF-8, quickly and easily. \$\endgroup\$ – Mark Ransom May 18 at 18:45
  • 2
    \$\begingroup\$ I have to do it on my own. It's for a university task... \$\endgroup\$ – lettomobile May 18 at 19:36
  • 2
    \$\begingroup\$ You might look at it for ideas then. \$\endgroup\$ – Mark Ransom May 18 at 20:00
22
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Are you really saying that the overhead of some extra function calls (not kernel calls) will be nontrivial in a hopefully IO limited program? That seems unlikely to me. \$\endgroup\$ – Voo May 18 at 11:27
  • \$\begingroup\$ @Voo: Is it I/O limited? That really depends on your hardware configuration. And even if you are I/O limited, wasting more CPU cycles than necessary wastes energy (important if your device runs off a battery), and if other processes are running in parallel, they will have less CPU cycles to spend. Also, it's not just the overhead of doing a function call, but also fread() having to do checks to see if the requested data is already in the internal buffer or not, and so on. Doing that every time to read just a few bytes adds up. \$\endgroup\$ – G. Sliepen May 18 at 12:20
  • 21
    \$\begingroup\$ Running some benchmarks on a AMD Ryzen 9 3900X and a Samsung 950 PRO NVMe drive and a 4 GB input file, I get on average 42.9 seconds for the unoptimized code, and on average 3.6 seconds for code which does fread() and fwrite() in 64 kiB blocks. According to hdparm, the throughput of the drive is 2.5 GB/s, so the optimized code is approximately I/O bound, whereas the unoptimized code is about 12 times slower. \$\endgroup\$ – G. Sliepen May 18 at 15:10
  • 2
    \$\begingroup\$ @MarkRansom: setvbuf()? It's C89. \$\endgroup\$ – G. Sliepen May 18 at 18:55
  • 1
    \$\begingroup\$ With glibc, at least, f* function calls have overhead in the form of virtual function dispatch (because FILE structures don't have to refer to real files), locking (because multiple threads could perform file operations at the same time), bookkeeping (to adjust structure offsets, buffer pointers, allocations), and so on. They can be remarkably expensive function calls - to the point where you can probably beat them with careful use of write... \$\endgroup\$ – nneonneo May 20 at 18:19
21
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ How can I transform it into a loop? Can you give me an example? I'm an if-else fan but I'm curious how to do it with a loop. \$\endgroup\$ – lettomobile May 19 at 22:41
  • \$\begingroup\$ You could even use a loop instead of the succession of if ... else if ... tests. And probably shift the codepoint after outputting each of the bytes. \$\endgroup\$ – jcaron May 20 at 21:57
11
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ UTF-32LE is used in linux sometimes, but BE I've never encountered. \$\endgroup\$ – Mooing Duck May 19 at 17:09
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Could you explain why your solution is better inside the answer? \$\endgroup\$ – pacmaninbw May 18 at 22:33
7
\$\begingroup\$

Code fails to detect invalid code points

There are 1,112,064 valid unicode code points, not 232.

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You're absolutely right about having to check if the bytes are being read correctly. I simply do not do it because this task is not worth so much so I avoid such checks that should be done in a more serious converter. About the UTF8 version, I edited showing which model my program is based on. \$\endgroup\$ – lettomobile May 19 at 19:56

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.