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.

Tuesday, August 20, 2013

REST API

After quite some while I finally found the time to fully document the REST API of PSHDL, but maybe it you might want to know why I but such a high emphasis on having a REST API vs. investing time in a command line compiler. Don't worry though, a follow up on how to use the command line (which already exists in some pieces) will follow soon.

To make one thing very clear: I will not use, publish or sell the code that is on my server. I put some effort into the fact that you can not extract the user name or eMail of a workspace, also the workspace is not exposed in such a way that a crawler might find it, unless you post a link to it somewhere. I might take a look at the code if I find that it creates some undesirable behavior (takes unusual long to compile, crashes the compiler, consumes large amount of disk space or is harming the server in some other way). I also might take a look at the interaction with the compiler to learn from it. One particular example I have in mind is: How many edits does it take until the user recovers from a compile error.

You can find the documentation online at the API URL. Unfortunately swagger, the framework that I am using for creating the API documentation, has some issues with correctly filling the forms. So don't be surprised if the sand-box functionality does not work correctly. I hope this will be fixed in a not too future version.

Motivation

There are good reasons for not using the REST API, especially when you are not just toying around anymore, but are producing something more serious. But most other users can actually benefit from it.

Frequent releases

One of the hardest things about designing a language is to predict what people are going to try to do with your language. In a text based language with a fixed grammar some constructs are accepted by the grammar although they don't make any sense on a semantic level. Finding all those strange ways people intend to use your language is difficult for someone who knows the language very well. So occasionally some creative way of doing something can lead to problems that I did not cover well. In the best case they crash the compiler, in the worst case they produce code that is not correct.

My fear when handing out a command line version is that people are trying to solve a problem with PSHDL and fail, either because the compiler crashed, the documentation sucked, the warning wasn't clear enough or they were not using the latest version of the compiler. In a web environment the compiler and the documentation is always the latest version, also crash logs are collected so that I can take a look at them and hopefully fix them. When people are using it on their command line, the chances that they are going to report a bug is quite low, especially on the very crucial first few minutes of toying around with a new language.

Collaborative editing

With an online API it is very simple to share your code with others. If you run into a problem, you can simply send them a link to your source and they can then take a look at it. Or maybe you're working with someone else and want to work together on the same code base at the same time. This is quite easy to accomplish with the REST API. Especially when you start to make use of the streaming API which brings us to the next point.

Interface extensions

In the future I will add the ability to add your own extensions to the web ui. For this a streaming API has been added. The streaming API is essentially a publish subscribe API realized with atmosphere, a web-socket/comet framework. You open a connection to the streaming API and get event notifications for most actions, like adding a file, compiling the workspace etc. In addition to that you can also publish your own messages.

With this API it is possible to create web pages that can react to events on the workspace. For example a local application might automatically download and synthesize your code whenever you hit compile in the workspace. You could also implement some sort of chat facility to discuss the code that you are working on. So far you can not directly hook in to the ui itself, but I am working on that.

New applications

Think of the possibilities: Let's say you want to build an interactive tutorial for learning how to program FPGAs. You could provide code snippets, which upon the press of a button, are converted into JavaScript which you can then use to let the user not just run, but also interact with the example and play around a bit.

Also a REST API is not bound to a particular language. In some circumstances it might not be desirable or even possible to run the Java version of the compiler (think of mobile handsets/tablets). With the REST API this is not much of an issue.

Zero installation

In order to get started with programming in PSHDL all you need is curl/wget or any other http client. No need to install (m)any tools.