Friday, August 30, 2013

Interesting problems with bit arithmetic (Part 1)

During the implementation of code generators, you can run into all kind of interesting numeric problems. Normally you would not encounter those as you would use the same bit width most of the time. Probably the arithmetic with those types is also well defined. But when you develop a code generator, or interpreter with arbitrary precision, you have to take care of all of this.

In this blog entry I discuss the simple arithmetic problems that I had to reason about during. In the next blog I will discuss the difficulties of implementing a cast operation. The last blog entry will then be about the pains of implementing shift operations.

Definition of arithmetic rules

When you perform arithmetic with two numbers it really doesn't matter whether a number is signed or not. The ALU always performs it the same way. What differs is the resulting interpretation. Let's take a look at a very simple C example:

uint32_t a0=4;
uint32_t b0=5;
uint32_t diff0=a0-b0;
int32_t diffInt0=diff0;
printf("%d-%d=%5d 0x%08x %5d 0x%08x %u\n", a0, b0, diff0, diff0, diffInt0, diffInt0, diffInt0);

uint16_t a1=4;
uint16_t b1=5;
uint16_t diff1=a1-b1;
int16_t diffInt1=diff1;
printf("%d-%d=%5d 0x%08x %5d 0x%08x %u\n", a1, b1, diff1, diff1, diffInt1, diffInt1, diffInt1);

Upon execution you will see the following results:

4-5=   -1 0xffffffff    -1 0xffffffff 4294967295
4-5=65535 0x0000ffff    -1 0xffffffff 4294967295

The reason for the difference between the display of diff0 and diff1 is that the printf function interprets those values as signed 32 bit for the %d option. The %x and %u does not care about the signedness of the value and just dumps the bits.

But what happens when one operand is signed and the other is not? Lets take a look at multiplication:

uint16_t a0=0xFFFF;
uint8_t  b0=-5;
uint16_t prod0=a0*b0;
int16_t  prodInt0=prod0;
printf("%d*%d=%5d 0x%08x %5d 0x%08x %u\n", a0, b0, prod0, prod0, prodInt0, prodInt0, prodInt0);

uint16_t a1=0xFFFF;
int8_t   b1=-5;
uint16_t prod1=a1*b1;
int16_t  prodInt1=prod1;
printf("%d*%d=%6d 0x%08x %5d 0x%08x %u\n", a1, b1, prod1, prod1, prodInt1, prodInt1, prodInt1);

This produces:

65535*251=65285 0x0000ff05  -251 0xffffff05 4294967045
65535*-5=     5 0x00000005     5 0x00000005 5

What is going on here? Lets take a look at first printf. As b0 is unsigned, assigning -5 is just a strange way of writing 0xFB. So the operation that takes place is 0xFFFF * 0xFB which is 0xFAFF05. As the assignment target is 16 bit and the result is 32 bit, the first 2 bytes are cut off.

But what about the second printf? Well, now b1 is a signed type and gets assigned a signed value. This forces the multiplication in prod1 to become a fully signed operation. The 0xFFFFF is a disguised -1 for a 16 bit values. Interpreted as int16_t this becomes a -1 which is then multiplied with -5 which is 5. Or written in hex the multiplication is 0xFFFF * 0xFFFB which is 0xFFFA0005, truncated to 16 bit you have 5.

This leads to the following rules in PSHDL for the arithmetic operations (+,-,*,/,%):

  • If one operand is signed, both operands are treated as signed.
  • Both operands are sized to the bigger size operand.
  • A literal always adopts the size of the other operand. If this leads to a loss in information in the literal, a warning is generated.
  • Arithmetic with bit types is not allowed.

Unfortunately PSHDL does not just have a hand full of bit-width to deal with but can be arbitrary. Lets take a look at the following PSHDL code:

uint<16> a=0xFFFF;
int<16>  b=-5;
uint<32> p=a*b;

In C the result is 5. But is that really the intend of the programmer? One might argue that the programmer actually assumes that he is multiplying something big with a negative number, so the result should be something big that is negative. Even though it would be quite easy to simply add one bit on each operand, I decided to be compatible with C and do not perform such an extension. The result in PSHDL is thus the same as in most C based languages: 5.

No comments:

Post a Comment