views:

157

answers:

9

I created a structure to represent a fixed-point positive number. I want the numbers in both sides of the decimal point to consist 2 bytes.

typedef struct Fixed_t {
    unsigned short floor; //left side of the decimal point
    unsigned short fraction; //right side of the decimal point
} Fixed;

Now I want to add two fixed point numbers, Fixed x and Fixed y. To do so I treat them like integers and add.

(Fixed) ( (int)x + (int)y );

But as my visual studio 2010 compiler says, I cannot convert between Fixed and int.

What's the right way to do this?

EDIT: I'm not committed to the {short floor, short fraction} implementation of Fixed.

+2  A: 

This is not possible portably, as the compiler does not guarantee a Fixed will use the same amount of space as an int. The right way is to define a function Fixed add(Fixed a, Fixed b).

larsmans
I agree. But I was actually asking about the implementation of the add function. I want the Fixed addition function to be as fast as int addition. That's why I decided to convert the fixed-point number to an integer for the addition.
snakile
+5  A: 

If you have to you can use a union but beware of endian issues. You might find the arithmetic doesn't work and certainly is not portable.

typedef struct Fixed_t {
   union { 
        struct { unsigned short floor; unsigned short fraction }; 
        unsigned int whole;
         };
} Fixed;

which is more likely (I think) to work big-endian (which Windows/Intel isn't).

CashCow
+1 for pointing out endian issues and not portable.
Anders Abel
`__attribute__ ((__packed__))` should be added to struct so the compiler doesn't try to optimize byte alignment.
Till Backhaus
@Till: Thanks. Where in the struct should I add that __attribute__((__packed__)) thing?
snakile
@snakile `struct { unsigned short floor; unsigned short fraction }__attribute__ ((__packed__));`
Till Backhaus
You should not use `__attribute__((__packed__))`. This code works perfectly well without nonstandard packing options on any real-world ABI.
R..
@R.. aren't there compilers that align struct members on 4 byte boundaries? Maybe when optimizations are switched on?
Till Backhaus
These issues are also why it is not considered portable to set one member of a union then read another one, which is what you would be doing here. That doesn't mean you should never ever do it, because there may be highly performance-critical situations where it works best for the situation, usually something very low-level.
CashCow
@Till: As far as I know, no. It would make no sense. I think you're confused about the nature and purpose of alignment if you think it would affect this structure. Keep in mind such alignment would have to be structure-specific and without purpose, since a type can never have alignment requirements larger than its size or which do not divide its size evenly (if you don't see why think of arrays).
R..
A: 

Try this:

typedef union {
    struct Fixed_t {
        unsigned short floor; //left side of the decimal point
        unsigned short fraction; //right side of the decimal point
    } Fixed;
    int Fixed_int;
}
Bernd
See my answer which removes the endian-dependency.
R..
+1  A: 

Just add the pieces separately. You need to know the value of the fraction that means "1" - here I'm calling that FRAC_MAX:

 // c = a + b
 void fixed_add( Fixed* a, Fixed* b, Fixed* c){
     unsigned short carry = 0;
     if((int)(a->floor) + (int)(b->floor) > FRAC_MAX){
         carry = 1;
         c->fraction = a->floor + b->floor - FRAC_MAX; 
     }
     c->floor = a->floor + b->floor + carry;
 }

Alternatively, if you're just setting the fixed point as being at the 2 byte boundary you can do something like:

void fixed_add( Fixed* a, Fixed *b, Fixed *c){
    int ia = a->floor << 16 + a->fraction;
    int ib = b->floor << 16 + b->fraction;
    int ic = ia + ib;
    c->floor = ic >> 16;
    c->fraction = ic - c->floor;
}
Mark E
This pretty much defeats the whole purpose of a fixed-point type...
R..
A: 

If your compiler puts the two short on 4 bytes, then you can use memcpy to copy your int in your struct, but as said in another answer, this is not portable... and quite ugly.

Do you really care adding separately each field in a separate method? Do you want to keep the integer for performance reason?

Benoit Thiery
+6  A: 

You could attempt a nasty hack, but there's a problem here with endian-ness. Whatever you do to convert, how is the compiler supposed to know that you want floor to be the most significant part of the result, and fraction the less significant part? Any solution that relies on re-interpreting memory is going to work for one endian-ness but not another.

You should either:

(1) define the conversion explicitly. Assuming short is 16 bits:

unsigned int val = (x.floor << 16) + x.fraction;

(2) change Fixed so that it has an int member instead of two shorts, and then decompose when required, rather than composing when required.

If you want addition to be fast, then (2) is the thing to do. If you have a 64 bit type, then you can also do multiplication without decomposing: unsigned int result = (((uint64_t)x) * y) >> 16.

The nasty hack, by the way, would be this:

unsigned int val;
assert(sizeof(Fixed) == sizeof(unsigned int))              // could be a static test
assert(2 * sizeof(unsigned short) == sizeof(unsigned int)) // could be a static test
memcpy(&val, &x, sizeof(unsigned int));

That would work on a big-endian system, where Fixed has no padding (and the integer types have no padding bits). On a little-endian system you'd need the members of Fixed to be in the other order, which is why it's nasty. Sometimes casting through memcpy is the right thing to do (in which case it's a "trick" rather than a "nasty hack"). This just isn't one of those times.

Steve Jessop
+1 for "This just isn't one of those times."
larsmans
See my answer which should be portable to any system with fixed-size integer types and no mixed-endianness insanity.
R..
if x.floor is 16 bits then shifting it left will overflow all the bits, so you'd need to cast to a 32-bit unsigned int first.
CashCow
@CashCow: no, the shift operators perform integer promotions on their operands. Try it. The overflow would only occur if `int` is 16 bits, but the question is implicitly assuming that it isn't.
Steve Jessop
A: 
// add two Fixed 
Fixed operator+( Fixed a, Fixed b ) 
{   
...
}

//add Fixed and int
Fixed operator+( Fixed a, int b ) 
{   
...
}
Andy
This is C, not C++.
Mark E
A: 

You may cast any addressable type to another one by using:

*(newtype *)&var
Vovanium
Actually you cannot. This is explicitly undefined behavior as per the aliasing rules.
R..
This is undefined behavior but nobody can restrict you from doing this. :) And behavior that is undefined by standard may be defined by implementation.
Vovanium
+3  A: 

Some magic:

typedef union Fixed {
    uint16_t w[2];
    uint32_t d;
} Fixed;
#define Floor w[((Fixed){1}).d==1]
#define Fraction w[((Fixed){1}).d!=1]

Key points:

  • I use fixed-size integer types so you're not depending on short being 16-bit and int being 32-bit.
  • The macros for Floor and Fraction (capitalized to avoid clashing with floor() function) access the two parts in an endian-independent way, as foo.Floor and foo.Fraction.

Edit: At OP's request, an explanation of the macros:

Unions are a way of declaring an object consisting of several different overlapping types. Here we have uint16_t w[2]; overlapping uint32_t d;, making it possible to access the value as 2 16-bit units or 1 32-bit unit.

(Fixed){1} is a compound literal, and could be written more verbosely as (Fixed){{1,0}}. Its first element (uint16_t w[2];) gets initialized with {1,0}. The expression ((Fixed){1}).d then evaluates to the 32-bit integer whose first 16-bit half is 1 and whose second 16-bit half is 0. On a little-endian system, this value is 1, so ((Fixed){1}).d==1 evaluates to 1 (true) and ((Fixed){1}).d!=1 evaluates to 0 (false). On a big-endian system, it'll be the other way around.

Thus, on a little-endian system, Floor is w[1] and Fraction is w[0]. On a big-endian system, Floor is w[0] and Fraction is w[1]. Either way, you end up storing/accessing the correct half of the 32-bit value for the endian-ness of your platform.

In theory, a hypothetical system could use a completely different representation for 16-bit and 32-bit values (for instance interleaving the bits of the two halves), breaking these macros. In practice, that's not going to happen. :-)

R..
I know it's silly, but AFAIK nothing in the standard prevents `uint32_t` from being middle-endian. Personally I've seen middle-endian 64-bit types, but never middle-endian 32-bit types. Even then, you'd very strongly expect the endian-ness within the halves of `uint32_t` to match that of `uint16_t`, so I don't dispute that this works on any sane implementation.
Steve Jessop
@Steve: Yep, that was my thought exactly.
R..
@R.. : Could you please explain how the Floor and Fraction macros work? I don't understand what's going on in there.
snakile
Explanations added.
R..
@R.. pretty clever
snakile
By the way, if you ever encounter a legacy compiler that doesn't support compound literals, you could simply define `Floor` and `Fraction` to `w[1]` and `w[0]` or vice versa depending on the endian-ness of the platform with the broken compiler.
R..
@R. I'm not sure C89 is "broken", but it certainly is legacy.
Steve Jessop
@Steve: My thought was that the only non-C99 compiler OP is likely to encounter with code that's almost certianly for gaming is MSVC, and that MSVC is broken (for many reasons other than lack of C99 support).
R..