Types and Number Representation

GNU C

The GNU C Compiler, more commonly referred to as gcc, almost completely implements the C99 standard. However it also implements a range of extensions to the standard which programmers will often use to gain extra functionality, at the expense of portability to another compiler. These extensions are usually related to very low level code and are much more common in the system programming field; the most common extension being used in this area being inline assembly code. Programmers should read the gcc documentation and understand when they may be using features that diverge from the standard.

gcc can be directed to adhere strictly to the standard (the -std=c99 flag for example) and warn or create an error when certain things are done that are not in the standard. This is obviously appropriate if you need to ensure that you can move your code easily to another compiler.

64 bit

One area that causes confusion is the introduction of 64 bit computing. This means that the processor can handle addresses 64 bits in length (specifically the registers are 64 bits wide; a topic we discuss in the next week).

This firstly means that all pointers are required to be a 64 bits wide so they can represent any possible address in the system. However, system implementors must then make decisions about the size of the other types. Two common models are widely used, as shown below.

You can see that in the LP64 (long-pointer 64) model long values are defined to be 64 bits wide. This is different to the 32 bit model we showed previously. The LP64 model is widely used on UNIX systems.

In the other model, long remains a 32 bit value. This maintains maximum compatibility with 32 code. This model is in use with 64 bit Windows.

There are good reasons why the size of int was not increased to 64 bits in either model. Consider that if the size of int is increased to 64 bits you leave programmers no way to obtain a 32 bit variable. The only possibly is redefining shorts to be a larger 32 bit type.

A 64 bit variable is so large that it is not generally required to represent many variables. For example, loops very rarely repeat more times than would fit in a 32 bit variable (4294967296 times!). Images usually are usually represented with 8 bits for each of a red, green and blue value and an extra 8 bits for extra (alpha channel) information; a total of 32 bits. Consequently for many cases, using a 64 bit variable will be wasting at least the top 32 bits (if not more). Not only this, but the size of an integer array has now doubled too. This means programs take up more system memory (and thus more cache; discussed in detail next week) for no real improvement. For the same reason Windows elected to keep their long values as 32 bits; since much of the Windows API was originally written to use long variables on a 32 bit system and hence does not require the extra bits this saves considerable wasted space in the system without having to re-write all the API.

If we consider the proposed alternative where short was redefined to be a 32 bit variable; programmers working on a 64 bit system could use it for variables they know are bounded to smaller values. However, when moving back to a 32 bit system their same short variable would now be only 16 bits long, a value which is much more realistically overflowed (65536).

By making a programmer request larger variables when they know they will be needed strikes a balance with respect to portability concerns and wasting space in binaries.

Type qualifiers

The C standard also talks about some qualifiers for variable types. For example const means that a variable will never be modified from its original value and volatile suggests to the compiler that this value might change outside program execution flow so the compiler must be careful not to re-order access to it in any way.

signed and unsigned are probably the two most important qualifiers; and they say if a variable can take on a negative value or not. We examine this in more detail below.

Qualifiers are all intended to pass extra information about how the variable will be used to the compiler. This means two things; the compiler can check if you are violating your own rules (e.g. writing to a const value) and it can make optimisations based upon the extra knowledge (examined in later weeks).

Standard Types

C99 realises that all these rules, sizes and portability concerns can become very confusing very quickly. To help, it provides a series of special types which can specify the exact properties of a variable. These are defined in <stdint.h> and have the form qtypes_t where q is a qualifier, type is the base type, s is the width in bits and _t is an extension so you know you are using the C99 defined types.

So for example uint8_t is an unsigned integer exactly 8 bits wide. Many other types are defined; the complete list is detailed in C99 17.8 or (more cryptically) in the header file. [1]

It is up to the system implementing the C99 standard to provide these types for you by mapping them to appropriate sized types on the target system; on Linux these headers are provided by the system libraries.

Types in action

Below we see an example of how types place restrictions on what operations are valid for a variable, and how the compiler can use this information to warn when variables are used in an incorrect fashion. In this code, we firstly assign an integer value into a char variable. Since the char variable is smaller, we loose the correct value of the integer. Further down, we attempt to assign a pointer to a char to memory we designated as aninteger. This operation can be done; but it is not safe. The first example is run on a 32-bit Pentium machine, and the correct value is returned. However, as shown in the second example, on a 64-bit Itanium machine a pointer is 64 bits (8 bytes) long, but an integer is only 4 bytes long. Clearly, 8 bytes can not fit into 4! We can attempt to "fool" the compiler by casting the value before assigning it; note that in this case we have shot ourselves in the foot by doing this cast and ignoring the compiler warning since the smaller variable can not hold all the information from the pointer and we end up with an invalid address.

$ cat types.c
#include <stdio.h>
#include <stdint.h>

int main(void)
{
        char *c;
        int i;

        i = c;
        i = (int)c;

        return 0;
}

$ uname -m
i686

$ gcc -Wall -o types types.c
types.c: In function 'main':
types.c:19: warning: assignment makes integer from pointer without a cast

$ ./types
i is 52
p is 0x80484e8
p is 0x80484e8

$ uname -m
ia64

$ gcc -Wall  -o types types.c
types.c: In function 'main':
types.c:19: warning: assignment makes integer from pointer without a cast
types.c:21: warning: cast from pointer to integer of different size
types.c:22: warning: cast to pointer from integer of different size

$ ./types
i is 52
p is 0x40000000000009e0
p is 0x9e0

Negative Values

With our modern base 10 numeral system we indicate a negative number by placing a minus (-) sign in front of it. When using binary we need to use a different system to indicate negative numbers.

There is only one scheme in common use on modern hardware, but C99 defines three acceptable methods for negative value representation.

Floating Point

So far we have only discussed integer or whole numbers; the class of numbers that can represent decimal values is called floating point.

To create a decimal number, we require some way to represent the concept of the decimal place in binary. The most common scheme for this is known as the IEEE-754 floating point standard because the standard is published by the Institute of Electric and Electronics Engineers. The scheme is conceptually quite simple and is somewhat analogous to "scientific notation".

In scientific notation the value 123.45 might commonly be represented as 1.2345x10². We call 1.2345 the mantissa or significand, 10 is the radix and 2 is the exponent.

In the IEEE floating point model, we break up the available bits to represent the sign, mantissa and exponent of a decimal number. A decimal number is represented by sign × significand × 2^^exponent.

The sign bit equates to either 1 or -1. Since we are working in binary, we always have the implied radix of 2.

There are differing widths for a floating point value -- we examine below at only a 32 bit value. More bits allows greater precision.

The other important factor is bias of the exponent. The exponent needs to be able to represent both positive and negative values, thus an implied value of 127 is subtracted from the exponent. For example, an exponent of 0 has an exponent field of 127, 128 would represent 1 and 126 would represent -1.

Each bit of the significand adds a little more precision to the values we can represent. Consider the scientific notation representation of the value 198765. We could write this as 1.98765x10⁶, which corresponds to a representation below

Each additional digit allows a greater range of decimal values we can represent. In base 10, each digit after the decimal place increases the precision of our number by 10 times. For example, we can represent 0.0 through 0.9 (10 values) with one digit of decimal place, 0.00 through 0.99 (100 values) with two digits, and so on. In binary, rather than each additional digit giving us 10 times the precision, we only get two times the precision, as illustrated in the table below. This means that our binary representation does not always map in a straight-forward manner to a decimal representation.

With only one bit of precision, our fractional precision is not very big; we can only say that the fraction is either 0 or 0.5. If we add another bit of precision, we can now say that the decimal value is one of either 0,0.25,0.5,0.75. With another bit of precision we can now represent the values 0,0.125,0.25,0.375,0.5,0.625,0.75,0.875.

Increasing the number of bits therefore allows us greater and greater precision. However, since the range of possible numbers is infinite we will never have enough bits to represent any possible value.

For example, if we only have two bits of precision and need to represent the value 0.3 we can only say that it is closest to 0.25; obviously this is insufficient for most any application. With 22 bits of significand we have a much finer resolution, but it is still not enough for most applications. A double value increases the number of significand bits to 52 (it also increases the range of exponent values too). Some hardware has an 84-bit float, with a full 64 bits of significand. 64 bits allows a tremendous precision and should be suitable for all but the most demanding of applications (XXX is this sufficient to represent a length to less than the size of an atom?)

$ cat float.c
#include <stdio.h>

int main(void)
{
        float a = 0.45;
        float b = 8.0;

        double ad = 0.45;
        double bd = 8.0;

        printf("float+float, 6dp    : %f\n", a+b);
        printf("double+double, 6dp  : %f\n", ad+bd);
        printf("float+float, 20dp   : %10.20f\n", a+b);
        printf("dobule+double, 20dp : %10.20f\n", ad+bd);

        return 0;
}

$ gcc -o float float.c

$ ./float
float+float, 6dp    : 8.450000
double+double, 6dp  : 8.450000
float+float, 20dp   : 8.44999998807907104492
dobule+double, 20dp : 8.44999999999999928946

$ python
Python 2.4.4 (#2, Oct 20 2006, 00:23:25)
[GCC 4.1.2 20061015 (prerelease) (Debian 4.1.1-16.1)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 8.0 + 0.45
8.4499999999999993

A practical example is illustrated above. Notice that for the default 6 decimal places of precision given by printf both answers are the same, since they are rounded up correctly. However, when asked to give the results to a larger precision, in this case 20 decimal places, we can see the results start to diverge. The code using doubles has a more accurate result, but it is still not exactly correct. We can also see that programmers not explicitly dealing with float values still have problems with precision of variables!

    #include <stdio.h>
    
    int main(void)
    {
  5 	//  in binary = 1000 0000 0000 0000
    	//  bit num     5432 1098 7654 3210
    	int i = 0x8000;
    	int count = 0;
    	while ( !(i & 0x1) ) {
 10 		count ++;
    		i = i >> 1;
    	}
    	printf("First non-zero (slow) is %d\n", count);
    
 15 	// this value is normalised when it is loaded
    	long double d = 0x8000UL;
    	long exp;
    
    	// Itanium "get floating point exponent" instruction
 20 	asm ("getf.exp %0=%1" : "=r"(exp) : "f"(d));
    
    	// note exponent include bias
    	printf("The first non-zero (fast) is %d\n", exp - 65535);
    
 25 };

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
  5 /* return 2^n */
    int two_to_pos(int n)
    {
    	if (n == 0)
    		return 1;
 10 	return 2 * two_to_pos(n - 1);
    }
    
    double two_to_neg(int n)
    {
 15 	if (n == 0)
    		return 1;
    	return 1.0 / (two_to_pos(abs(n)));
    }
    
 20 double two_to(int n)
    {
    	if (n >= 0)
    		return two_to_pos(n);
    	if (n < 0)
 25 		return two_to_neg(n);
    	return 0;
    }
    
    /* Go through some memory "m" which is the 24 bit significand of a
 30    floating point number.  We work "backwards" from the bits
       furthest on the right, for no particular reason. */
    double calc_float(int m, int bit)
    {
    	/* 23 bits; this terminates recursion */
 35 	if (bit > 23)
    		return 0;
    
    	/* if the bit is set, it represents the value 1/2^bit */
    	if ((m >> bit) & 1)
 40 		return 1.0L/two_to(23 - bit) + calc_float(m, bit + 1);
    
    	/* otherwise go to the next bit */
    	return calc_float(m, bit + 1);
    }
 45 
    int main(int argc, char *argv[])
    {
    	float f;
    	int m,i,sign,exponent,significand;
 50 
    	if (argc != 2)
    	{
    		printf("usage: float 123.456\n");
    		exit(1);
 55 	}
    
    	if (sscanf(argv[1], "%f", &f) != 1)
    	{
    		printf("invalid input\n");
 60 		exit(1);
    	}
    
    	/* We need to "fool" the compiler, as if we start to use casts
    	   (e.g. (int)f) it will actually do a conversion for us.  We
 65 	   want access to the raw bits, so we just copy it into a same
    	   sized variable. */
    	memcpy(&m, &f, 4);
    
    	/* The sign bit is the first bit */
 70 	sign = (m >> 31) & 0x1;
    
    	/* Exponent is 8 bits following the sign bit */
    	exponent = ((m >> 23) & 0xFF) - 127;
    
 75 	/* Significand fills out the float, the first bit is implied
    	   to be 1, hence the 24 bit OR value below. */
    	significand = (m & 0x7FFFFF) | 0x800000;
    
    	/* print out a power representation */
 80 	printf("%f = %d * (", f, sign ? -1 : 1);
    	for(i = 23 ; i >= 0 ; i--)
    	{
    		if ((significand >> i) & 1)
    			printf("%s1/2^%d", (i == 23) ? "" : " + ",
 85 			       23-i);
    	}
    	printf(") * 2^%d\n", exponent);
    
    	/* print out a fractional representation */
 90 	printf("%f = %d * (", f, sign ? -1 : 1);
    	for(i = 23 ; i >= 0 ; i--)
    	{
    		if ((significand >> i) & 1)
    			printf("%s1/%d", (i == 23) ? "" : " + ",
 95 			       (int)two_to(23-i));
    	}
    	printf(") * 2^%d\n", exponent);
    
    	/* convert this into decimal and print it out */
100 	printf("%f = %d * %.12g * %f\n",
    	       f,
    	       (sign ? -1 : 1),
    	       calc_float(significand, 0),
    	       two_to(exponent));
105 
    	/* do the math this time */
    	printf("%f = %.12g\n",
    	       f,
    	       (sign ? -1 : 1) *
110 	       calc_float(significand, 0) *
    	       two_to(exponent)
    		);
    
    	return 0;
115 };

$ ./float 8.45
8.450000 = 1 * (1/2^0 + 1/2^5 + 1/2^6 + 1/2^7 + 1/2^10 + 1/2^11 + 1/2^14 + 1/2^15 + 1/2^18 + 1/2^19 + 1/2^22 + 1/2^23) * 2^3
8.450000 = 1 * (1/1 + 1/32 + 1/64 + 1/128 + 1/1024 + 1/2048 + 1/16384 + 1/32768 + 1/262144 + 1/524288 + 1/4194304 + 1/8388608) * 2^3
8.450000 = 1 * 1.05624997616 * 8.000000
8.450000 = 8.44999980927