Tag Archives: C

Time Difference

This post is based on a discussion about Progress Bars of Life, where I was foolish enough to claim that printing a text string representing the difference between two times could not be that hard in C. It is not hard, but turned out not to be entirely trivial either.

Pocket Watch

The problem we will consider is; given two tm structs, compute the difference in time between them, in such a way that we can easily format a string that gives a textual representation of it. We want years, months, days, hours, minutes, seconds.

The first idea you might get is to use difftime() to get the difference in seconds between the two times, and then compute the quantities we want by simple arithmetic. So,

You often see something like this in timing code — it works great for showing elapsed time in seconds, minutes, even hours. Do you see any problems with this approach?
Continue reading

Long Division, Part 3

I ended part two of this series with an open question:

And of course I can’t help but wonder if the CLR is compiled with Visual C++, so doing arithmetic on 64-bit numbers in C# and other .NET languages ends up at the same runtime functions?

I don’t have a lot of experience in debugging the CLR myself, so I asked Brian Rasmussen if he might be interested in taking a look at it. He was kind enough to take the time to point me in the right direction.

A little digging showed that the CLR does in fact call some of these functions from the C runtime, but with a twist.
Continue reading

Quoting Command-line Arguments

Raymond Chen recently blogged about the way CommandLineToArgvW treats quotes and backslashes. Parsing the command-line into argv[] is something I have had to fight with as well, so besides pointing to Raymond’s excellent post, I wanted to add a few comments of my own here.

We are examining how command-line arguments with spaces and quotes are handled. Part of the problem comes from the fact that DOS/Windows uses backslash as separator in paths. On systems like Unix, where forward slash is used instead, using backslash to escape special characters is less of a problem. But if you ever put a Windows path in a C string literal, you may have run into LTS — the situation where a string becomes unreadable due to escape characters.

Microsoft fixed this in C# with verbatim string literals. C# also implements a simpler method of escaping a quote inside a quoted string — doubling it — which is used in languages like Pascal and BASIC, and is what Raymond’s second hypothetical set of rules suggest.

The compromise we get for parsing command-line arguments in the C runtime library (and CommandLineToArgvW) is documented on MSDN. What the MSDN documentation does not tell you is that there is a second mechanism for inserting a literal quote in a quoted string — or at least there might be, depending on which version of the C runtime library.
Continue reading

Long Division, Part 2

In part one I talked about the support functions in the C standard libraries of various x86 32-bit compilers that perform arithmetic operations when you use 64-bit integers in your code.

While updating WCRT to work with the latest Visual C++ compilers, I was writing my own implementations of these functions, and naturally I tested them against the versions supplied in the VC CRT to verify they worked.

To my surprise, I found the GCD test I wrote for Long Division ran faster when compiled with WCRT.

This naturally piqued my curiosity.
Continue reading

Long Division

Integer types with at least 64 bits have been a part of the C standard for a while now (they were added in C99, and were a standard extension in many 32-bit compilers before that). But have you ever wondered what exactly happens when you use them?

Consider the following function (substitute long long with __int64 if you are using an older version of Visual C++):

let’s first have a look at what the VC 64-bit compiler gives us:

Pretty much what you would expect, a little setup and an idiv instruction to perform the division. Now let’s try the VC 32-bit compiler:

A little setup and .. a call?
Continue reading

INT_MIN

While adding a few header files to WCRT (a small C runtime library for Visual C++), I stumbled upon something that caught my interest.

INT_MIN in <limits.h> is a macro that expands to the minimum value for an object of type int. In the 32-bit C compilers I have installed at the moment, it is defined as:

So what exactly is wrong with the integer constant -2147483648 ?

Well, firstly it is not an integer constant. Let’s see what the standard says:

“An integer constant begins with a digit, but has no period or exponent part. It may have a prefix that specifies its base and a suffix that specifies its type.”

You will notice there is no mention of a sign. So -2147483648 is in fact a constant expression, consisting of the unary minus operator, and the integer constant 2147483648.

This still does not explain why that expression is not used directly in the macro. To see that, we have to revisit the rules for the type of integer constants.

The type of an unsuffixed integer constant is the first of these in which its value can be represented:

C89 : int, long int, unsigned long int
C99 : int, long int, long long int
C++ : int, long int, long long int

The problem is that 2147483648 cannot be represented in a signed 32-bit integer, so it becomes either an unsigned long int or a long long int.

So we have to resort to a little trickery, and compute -2147483648 as (-2147483647 – 1), which all fit nicely into 32-bit signed integers, and INT_MIN gets the right type and value.

If you happen to look up INT_MIN in the standard you will see:

minimum value for an object of type int

Which brings up the question why isn’t it (-32767 – 1)?

Pretty much any computer available today uses two’s complement to represent signed numbers, but this hasn’t always been the case.

Since C was designed to work efficiently on a variety of architectures, the standard’s limits allow for using other representations as well.

I will end this post with a little (not quite standard conformant) example. Try compiling it with your favorite C compiler, and let us know if something puzzles you.

Padding Trouble

When Intel expanded the 8086 architecture to 32-bit in 1985, they extended the 16-bit registers present to 32-bit registers. ax became eax, but it was still possible to use the low 16 bits of eax as ax just like before. Their choice was that performing operations on the low 16 bits did not change the high 16 bits of the register.

AMD expanded the 32-bit architecture to 64-bit in 2003. This was again a superset of the original, making it backwards compatible. They extended the 32-bit registers to 64-bit, and eax became rax. Again it was possible to to perform operations on the low 32 bits, but doing so clears the high 32 bits of the register.

“Operations that output to a 32-bit subregister are automatically zero-extended to the entire 64-bit register. Operations that output to 8-bit or 16-bit subregisters are not zero-extended (this is compatible x86 behavior).”

Now both choices work as far as backwards compatibility goes, and as long as we as programmers are aware of what happens, neither is a problem.

When building the aPLib compression library, I use Visual C++ to generate assembly listings, which I then perform some changes on with a perl script, before assembling the object files. While working on the recently released 64-bit version, I ran into a problem — the debug build of the library worked fine, but the release build did not.

Bugs like this are often caused by some improper memory usage, so I spent a day trying to track down the problem without much luck. Somehow the contents of a register was corrupted.

Looking through the code in HIEW I finally found the cause; a seemingly random instruction that wrote to the 32-bit part of a register, thereby clearing the high 32 bits. Then it dawned on me.

Visual C++ emits padding macros into assembly listings to align code and improve performance. These macros, npad, are defined in a file called listing.inc which resides in the Visual C++ include folder. But there is no 64-bit version of this file!

Let’s have a look then:

And there we have it. An instruction like mov edi, edi is safe to use as padding in 32-bit code, because moving the register to itself has no effect. But if you insert it in 64-bit code, it all of a sudden has an effect — the high 32 bits of rdi are cleared.

I have reported the problem to Microsoft and they say it will be addressed in a future release.

Loophole in Visual C++, Part 2

Here is a slightly more elaborate example:

This program goes through the entire range of the unsigned int type, performing some action for each. It shows the progress by calling a function to compute the ratio of count to the maximum possible value. Again, count is incremented in each step, and hence will reach the value zero at some point.

The program works as expected on the compilers I tried, except for cl.exe from VC7 and VC71 with the /O2 switch, which stop at 25%. In case you wondered about the starting point of 0x3fffffff, that’s the reason — no need to watch your machine chew it’s way through all integers up to 25%.

Looking at the code generated for the loop:

We see that it fails because the two instructions before the conditional jump have been reversed. Again it looks like the optimizer fails to recognize the importance of the increment to the loop.

Additional Trouble

2 plus 2 is 4, but does that generalize?

What is your immediate reaction to this little program?

If it was something along the lines of ‘depends’ then you’re either a raider of the standard, or you’ve just been around C/C++ for too long like me.

The type of an unsuffixed decimal integer constant is the first type from a list in which its value can be represented:

C89 - int, long int, unsigned long int
C99 - int, long int, long long int
C++ - int, long int

Now, the problem with the little program above is that if the int type is 16-bit, then 20000 + 20000 results in an overflow because the maximum value of a 16-bit int is 32767. We are guaranteed that computations involving unsigned operands cannot overflow, but there is no such guarantee for signed operands. So the addition may leave us in the land of undefined behaviour.

I compiled the above example with three DOS 16-bit compilers; Borland, Open Watcom and Digital Mars. None of the programs gave any output when run. Borland warned about the overflow, Open Watcom warned at -w2, Digital Mars did not warn.

What happens is that in the x86 two’s complement representation, 20000 + 20000 overflows and becomes -25536, which is not equal to 40000.

Writing portable, standard compliant C/C++ is not always easy .. and it can be Hard to C the problems.

Loophole in Visual C++, Part 1

Lets start this post by recalling what the gosp^H^H^H^Hstandard has to say about unsigned arithmetic:

“A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.”

This is from the C89 draft (3.1.2.5p5), statements to the same effect are present in the C99 standard (6.2.5p9) and the C++ standards.

Now consider the following program:

Since count starts at zero and is incremented each time through the loop, the standard tells us it will wrap to zero when it reaches a result that cannot be represented by an unsigned int, making the program terminate. Compiling the program with various compilers gives the expected stream of increasing numbers.

However, if you compile it with cl.exe from Visual C++ using the /O2 switch (maximize speed) you get a somewhat surprising result; a single zero and the program exits. This goes for VC6, VC7 and VC71.

If you initialize count to one instead, the program works fine. So it looks like the optimizer fails to recognize the addition as changing the value of count, and thus optimizes away the loop.

I have not tested the various VC8 betas, so if you have any of them installed, feel free to try it out and post your results (just remember to compile from the command-line using cl.exe and /O2).