4

I'm working with an old C module that was originally ran on Power PC architecture and compiled with gnu 3.0.6

I'm porting it to run in a VS2012 project on Intel hardware.

The module creates a 3D model of a storm cloud based on a bitmap file and other IO.

I keep seeing signed magnitudes (x- and y-coords, -differentials) being multiplied by 1024*1024 and I don't see why. These quantities are stored in signed ints.

Whenever one of these quantities is output from the module, it's right-shifted by 20, which apparently cancels the multiplication by 1024*1024.

Does anyone know what's going on here?

Thanks

EDIT: One case is where x- and y-differentials of a line embedded in a 256x256 grid are used to iterate across it. Here we have a ray defined by some angle theta and a given starting point (x,y) within the grid. The starting point coordinates are products of 1024*1024, as well

#define KINT 1024*1024

float x_disp, y_disp;
int x, y, dx, dy;

//initializing code    

x = (int)(KINT*x_disp); 
y = (int)(KINT*y_disp); 

//as theta ranges across [-pi/2, pi/2], itheta ranges over [0, 720]

dx = (int)(KINT*sin_table[itheta]);  
dy = (int)(KINT*cos_table[itheta]);  

Come to think of it, I'm not sure why there isn't a (-1) in front of sin_table(itheta).

The line embedded inside the 256x256 grid is traversed by computing the coordinates as follows:

for (int i = 0; i < 256; i++)
{
   int posx = (x>>20);
   int posy = (y>>20);
   if((posx|posy)&0xffffff00 == 0)
   {
        char val = grid[x][y];
        //do something with val
   }

   x += dx;
   y += dy;
} 
  • 1
    Without knowing the source code, there is no way for us to tell. – BobDalgleish Dec 4 '19 at 18:42
  • 6
    Does the code perform calculations on the left-shifted values? If yes, this might be a crude implementation of fixed point math, presumably to increase speed by relying on integer operations instead of floating point, even though the PowerPC wasn't too bad at floats. – Hans-Martin Mosner Dec 4 '19 at 22:28
  • This is just a wild guess, but 1024*1024 is 1MB., which incidentally was the size of the PowerPC's L2 cache. It could be an optimization that forced the values to be within that high-speed area on the CPU. – Berin Loritsch Dec 11 '19 at 21:28
  • @BerinLoritsch might that be possible? – Sam Dec 14 '19 at 1:09
  • 1
    One reminder to everyone: in fixed-point arithmetic implementations, the scaling factor does not have to look nice. In other words, there is no requirement that the scaling factor be divisible by 2 or 10. The main performance come from CPU's processing performance discrepancy between integers and floating-point values. The final "unscaling" do not suffer from the slow speed of floating-point division because floating-point division by a constant (scaling factor) can be equivalently implemented by a multiplication with the reciprocal of the constant (scaling factor). – rwong Mar 21 at 21:49
13

It's difficult to be (at all) certain without looking at the code, but it kind of sounds like it's implementing fixed-point arithmetic, with 12 bits before the decimal point, and 20 bits after.

When/if you multiply two of these together, you need to do a right shift to get the result back to the right representation. That is, each input is a total of 32 bits, so when you multiply them, the result will obviously be 64 bits, and you want to keep 32 bits of that. But you need to keep the correct 32 bits. Since you started with 20 bits of fraction and 12 bits of mantissa in the inputs, you'll get 40 bits of fraction and 24 bits of mantissa in the result. So you right shift by 20, and then keep the bottom 32 bits to get a 12:20 formatted result (and the more significant bits in the result had better be zero, or you've just overflowed what the result can represent).

Many people find it easier to think in terms of decimal. So let's consider a decimal representation where we can handle (say) -999.999 to +999.999, but store and manipulate them as integers.

So, to store a number, we start by multiplying it by 1000, so if we had (say) 123.456, we get 123'456. Now, if we add numbers like this, we don't have to do anything special. So, if we add 123'456 to 234'567, we get 358'023, which represents 358.023 (which is the right answer).

But if we multiply two of these numbers together, our result is a not what we'd want. For example, let's consider 2.2 x 2.3. In our format, that becomes 2'200 x 2'300. When we multiply those, we get 5'060'000, which converts to 5'060.000. Our result is too high by a factor of 1'000 (the same factor we're applying to a value to get it into our notation). So, to get the right answer following a multiplication, we need to shift it to the right by 3 decimal places, so we get 5'060, which converts to 5.06.

It sounds like the code you're looking at does pretty much the same thing, but instead of using a multiplier that's nice and even in decimal, it uses a multiplier that's nice and even in binary. That makes it easy for a binary computer to "fix" the result after a multiplication, by simply doing a right shift (whereas, dividing by a power of 10 would be relatively slow).

Looking a step further: why would they do this? I can see two obvious possibilities. The first and most obvious is sheer speed. Especially on a lot of older processors, it was fairly common for integer math to be substantially faster than floating point math.

The second possibility would be predictability. With fixed-point, you'd fundamentally doing integer math. Integer math is fairly simple and understandable. By contrast, if you use floating point math instead, you get into an area many people find somewhat mysterious. When people start out, they tend to think of floating point is being like a Real number in mathematics--but they quickly learn that the two aren't really the same, and the differences can be difficult to understand and often difficult for a beginner in the area to predict. By using fixed point (scaled integers) they can simply avoid that stuff that's unpredictable and hard to understand.

| improve this answer | |
4

The fact that this shift is done one way and then in reverse later suggests that this is perhaps a hack to provide use extra bandwidth in these values. That is, the 20 low-order bits are being used to hold some other information. This is my best guess.

Another option is that this is an goofy way to clear high-order bits. This seems unlikely but I would be concerned about this possibly happening especially when moving from one architecture to another.

You are going to trace through the code to be sure but you should definitely verify that the int size on the new architecture is at least as large as the old.

| improve this answer | |
0

Another reason for the shifting --

Some data systems left-align data in a field instead of the classic right-aligned. A 10-bit analog-to-digital converter -- for example -- typically gives options for left-align or right-align the 10-bit readings in a 16-bit field. This capability exists in the Atmega32u4 chip used in some Arduino devices -- see datasheet page 313, ADLAR bit in ADMUX register.

Left-aligned data is essentially the same as the system described by Jerry Coffin above if you always have the fractional part as zero.

One big impetus behind these kinds of fixed-point systems is when a processor has no floating-point unit and you know ahead of time how many digits of precision you need after the decimal point. Since 2^10 is roughly 10^3, every ten bits left-shift approximately moves the decimal point right three positions. You can do integer math on numbers that are of the form X.yyy and when you display the result you just insert the decimal point in the proper location after converting to decimal digits.

| improve this answer | |

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.