Fast int<-->float conversion routines?

D619d95cddb1edb227f51ef539d15cdc
0
Nautilus 103 Jun 24, 2007 at 22:34

Greetings,
I’m looking for conversion routines [int <–> float] faster
than the standard cast ops int() and float().

I can write my own in C++, but I need to best the standard
cast ops. Instead I barely match them.

Looking for material, the best I’ve found is Agner Fog’s
“float to int” rounding routines, but I’m interested in
truncation, not rounding.
And there’s no “int to float” conversion anyway.

Other links I’ve found either point me to libraries to license,
or quick explanations about why the standard cast ops
should be avoided when performance is of importance, and
not a line of usable code.

Please, do you have any valid link?

Ciao ciao : )

24 Replies

Please log in or register to post a reply.

C4b4ac681e11772d2e07ed9a84cffe3f
0
kusma 101 Jun 24, 2007 at 22:55

http://www.xyzw.de/c190.html has some float->int stuff.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jun 25, 2007 at 09:17

@Nautilus

Greetings,
I’m looking for conversion routines [int <–> float] faster
than the standard cast ops int() and float().

I can write my own in C++, but I need to best the standard
cast ops. Instead I barely match them.

Looking for material, the best I’ve found is Agner Fog’s
“float to int” rounding routines, but I’m interested in
truncation, not rounding.
And there’s no “int to float” conversion anyway.

Other links I’ve found either point me to libraries to license,
or quick explanations about why the standard cast ops
should be avoided when performance is of importance, and
not a line of usable code.

Please, do you have any valid link?

Ciao ciao : )

If I remember correctly the cast ops are slow because they actually result in a function call to ftol. Simply write a piece of assembly code that pops the float you want from the floating point stack. That will atuomatically truncate it. I can post a piece of code when I’m home from work in a few hours or so.

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Jun 25, 2007 at 12:07

This one might be interesting for you as well:

http://www.stereopsis.com/FPU.html

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Jun 25, 2007 at 12:12

Also, if you know the range of the integer you want to convert, you can do this directly: this is a little example to convert from float to int assuming that the float is >=0 && < 256:

unsigned char flt_to_byte (float a)
{
  float x = a + 256.0f;
  return ((*(int*)&x)&0x7fffff)>>15;
}
F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jun 25, 2007 at 16:00

Well… I have nothing to add to that :)

D619d95cddb1edb227f51ef539d15cdc
0
Nautilus 103 Jun 25, 2007 at 16:49

Thanks for the links, Kusma and Nils.
I’ll use Google’s cache to read the pages.
IE and Mozilla fail to open them directly =/

Hi Anubis,@anubis

If I remember correctly the cast ops are slow because they actually result in a function call to ftol.

Correct.
More precisely, with _ftol two FPU state changes happen.
First the FPU current rounding mode is changed, then the
desired bitmask is built, and finally the FPU rounding mode
is set back to the original state.
This is done to guarantee taht the ANSI C standard is fully
respected, no matter the platform, because there’s no
dedicated asm instruction***.
[edit]
*** maybe due to the fact that the IEEE 754 is still under
R&D, and may change in future. Just a wild guess…
[/edit]

These state changes stall the FPU twice per each cast.
Collaterally, the designated CPU pipe has to sit and rot
while waiting for the FPU to finish.
To add insult to injury, the state changes are unnecessary
in most cases anyway.
@anubis

Simply write a piece of assembly code that pops the float you want from the floating point stack. That will atuomatically truncate it. I can post a piece of code when I’m home from work in a few hours or so.

I didn’t mention that I know little to no asm.
I recognize jumps, and some basic instructions.
I know that the count of “push” and “pop” must always
match.
But that’s all.

As far as my job is concerned, I don’t need to know assembly.
Yet game programming is my 2nd hobby, and I’ll have to
buy a good book someday.
Examining the asm produced by the compiler isn’t enough.

Kind regards everyone,
Ciao ciao : )

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 25, 2007 at 16:53

You can do Nils’ trick safely for any float up to (but not including) 16777216. If you want a full positive int, use a double

unsigned ftoi(double d)
{
    d += 4503599627370496.0;  // 1 << 52
    return (unsigned &)d;
}
46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Jun 25, 2007 at 17:49

More fun: :)

int FloatToInt(float x)
{
    unsigned e = (0x7F + 31) - ((* (unsigned*) &x & 0x7F800000) >> 23);
    unsigned m = 0x80000000 | (* (unsigned*) &x << 8);
    return int((m >> e) & -(e < 32));
}

Any reason why the values has to be truncated? Rounding is faster, and this SSE2 snippet performs quite well:

#include <intrin.h>
int FloatToInt_SSE(float x)
{
    return _mm_cvt_ss2si( _mm_load_ss(&x) );
}
E26922d4cc36f855832c335fe7a7e8af
0
t0rakka 101 Jun 25, 2007 at 18:16

While we’re on the topic, any fast/efficient way to do:

  1. float[4] -> *unsigned* int [4] conversion from SSE xmm(n) (to anywhere, xmm register would be fine ;)

  2. float[4] -> unsigned char [4] (normalized) conversion from SSE xmm(n) to anywhere, xmm, mm, 32 bit ALU register, .. memory (!)

The case 1 is easy for signed, but for unsigned have to swizzle, crackle and pop the values in multiple parts through mm registers. Likewise for case 2, am I missing something vital or is “unsigned” a second class citizen with SSE? (SSE2, SSE3, ..)

// example of case 2
__m128 c = …;
__m64 frag = _mm_cvtps_pi16(c);
uint32 v = _mm_cvtsi64_si32(_mm_packs_pu16(frag,frag));

FWIW, there is a better sequence for what I actually use this for (mantissa extraction) but it’s not so good with the case 1, so I came wondering while bumping into this thread.. my bad. :O

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 25, 2007 at 18:37

I wonder why everyone uses the *(type*)&x notation while (type&)x works just fine. Must be old C remnants ;)

D619d95cddb1edb227f51ef539d15cdc
0
Nautilus 103 Jun 25, 2007 at 20:17

@.oisyn

I wonder why everyone uses the *(type*)&x notation while (type&)x works just fine. Must be old C remnants :)

Ciao .oysin,
(type&)x is prettier but less secure than *(type*)&x.
Indeed both produce the same result, but consider the case:

float f = 1.0f;

// Forget the &, and the compiler may not complain.
// In this case it won't.
DWORD d = (DWORD &) f;

float f = 1.0f;

// Forget either a * or the &, and the compiler will catch
// the error.
DWORD d = *(DWORD*) &f;

Also (DWORD &) f at first glance looks like a plain cast to DWORD.
Using *(DWORD*) &f instead you hardly get fooled, even if quickly skimming through the code.

Ciao ciao : )

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 25, 2007 at 20:20

If that’s your reasoning, you should use reinterpret_cast anyway.

D619d95cddb1edb227f51ef539d15cdc
0
Nautilus 103 Jun 25, 2007 at 20:42

You kidding? reinterpret_cast<> is too long and boring to
type every time, and even uglier than *(type*)&x
I prefer the old style casts, thanks \^_\^

Ciao ciao : )

E26922d4cc36f855832c335fe7a7e8af
0
t0rakka 101 Jun 25, 2007 at 20:48

reinterpret_cast is great! The whole point is that when you’re casting, you *should* sweat your a** off! The less you cast the better you are off (meaning: you chose your types wisely yada yada..)

But when Man Gotta Cast, Man Gotta Cast.. *_cast<> ! FAP!

And a worn-out cliche: “and you can grep _cast…”

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Jun 25, 2007 at 20:51

@.oisyn

I wonder why everyone uses the *(type*)&x notation while (type&)x works just fine. Must be old C remnants :)

Neither of them are secure since they break the type aliasing rule. The only secure way to do it is to put float and int into a union and access them as needed. Most compilers will sort such little float to int hacks without any overhead these days.

Btw oisyn,

Nice little code snippet! I knew there is a general purpose way to do this cast conversion, but I never had the time to do it. I always write these kind of quick-casts on purpose, hand-tailored for the special case I need (sometimes it’s fixed point, sometimes not).

Anyways, I’d like to note that these casts work in reverse just as well. Construct your float from an integer, add he correct exponent and subtract some magic float from it. Once you’ve understood the float format it becomes second nature.

Nils

D619d95cddb1edb227f51ef539d15cdc
0
Nautilus 103 Jun 25, 2007 at 21:15

@ Nils:
You are quite right, as usual.
And I forgot my manners by not saying “thanks” to .oysin, for the snippet you just mentioned.

@ .oysin:
Thank you : )

@ Kenneth:
Thank you too.
I need truncation because I often cast to int from floats with fractional parts and the truncation of float() is handy.
Rounding has its uses too, of course.
I think I now have enough material to go on.
But if any of you has more to share, feel free to do so!

@ t0rakka:
I’ve read an article, once, where the author was complaining about the triad of the _cast<> operators.
He said that they are meant to substitute the old C style casts.
C++ programmers should always resort to such _cast<> and forget about the old C way.
On the other hand -and here I’ll repeat part of what you said- casts are evil and should be avoided.
And that’s why when they had to decide on syntax and names of the new C++ _cast<> operators, they chose such long and inelegant names. Kind of to discourage their use.

The article concluded saying that the _cast<> ops were superfluous and were adding nothing -in terms of functionality- to the existing language.
I don’t remember the link anymore, sorry.

IIRC the article’s title had the words “Why I hate [+something else]” in it.
It was one of several articles on C++.
The site is still up for sure.

Regards,
Ciao ciao : )

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 25, 2007 at 23:01

@Nautilus

You kidding? reinterpret_cast<> is too long and boring to

Look, either you want to be safe from mistakes, or you wat to type something short. If you want to be safe, you should use the C++ style casts (with reinterpret_cast you express what you mean and you can’t accidentally cast away cv qualifiers - A C style cast could do pointer conversions if the types are related) :)

I prefer the old style casts, thanks ;)

Which is perfectly fine, as long as you keep in mind they’re not that safe as C++ style casts.
@Nils Pipenbrinck

Neither of them are secure since they break the type aliasing rule. The only secure way to do it is to put float and int into a union and access them as needed. Most compilers will sort such little float to int hacks without any overhead these days.

What kind of security are you talking about exactly? I fail to see the difference between a union and reinterpret_cast, since from the standard’s point of view, you’re only allowed to read the member from a union you have previously written (so technically writing to the float in the union and then reading the int yields undefined behaviour, just as with reading an int from a float reference - the compiler can make the same set of assumptions in both cases)

D4481ead2260c58a7ffda0a64c5f52aa
0
EDWYN 101 Mar 22, 2010 at 05:49

@Nils Pipenbrinck

This one might be interesting for you as well: http://www.stereopsis.com/FPU.html

yes, its really very much interesting and very informative piece of work.

A99eff0d24ebaf420caf351c810d5503
0
GloW 101 Apr 05, 2012 at 15:17

Hello

i’ve suceeded into using Kenneth Godring code, but i’ve not fully understood how this work.

I try to modify the code of FloatToInt into DoubleToUnsignedShort, if someone can give me a Hand.

int FloatToInt(float x)
{
        unsigned e = (0x7F + 31) - ((* (unsigned*) &x & 0x7F800000) >> 23);
        unsigned m = 0x80000000 | (* (unsigned*) &x << 8);
        return int((m >> e) & -(e < 32));
}

Anyway i would like to understand :
- The first line extract the exponent, all right but why 0x7f + 31 at the beginning?
- The second line extract the mantissa , all rigth but why addinf a forced to 1 MSB?
- The third line confuse me

Thanks for Help

6eaf0e08fe36b2c23ca096562dd7a8b7
0
__________Smile_ 101 Apr 05, 2012 at 19:13

First line computes 31 - exponent.
Second computes 2\^31 * mantissa (0x80000000 comes from omitted 1 in mantissa).
-(e < 32) is -1 (or 0xFFFFFFFF) if exponent >=0 and 0 if exponent < 0.
So third line computes (2\^31 * mantissa) >> (31 - exponent) = mantissa * 2\^exponent if exponent >= 0 and zero otherwise.

For double it will be something like

uint64_t double_to_uint64(double x)
{
    uint64_t y =  *(uint64_t *)&x;
    uint64_t e = 0x3FF + 63 - (y >> 52);
    uint64_t m = 1 << 63 | y << 11;
    return m >> e & -(e < 64);
}

Personally I prefer more black magic:

int32_t fast_round(float x)
{
    x += 12582912;
    return (*(int32_t *)&x ^ 0x4B000000) - 0x00400000;
}

but my tests show that simple (int)x will be fastest (at least under g++).

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Apr 06, 2012 at 10:22

Note that 12582912 is just 0xc00000. But why 0xc00000? I always did something like

int fast_round(float x)
{
        x += (1 << 23);
        return (int&)x & ((1 << 23) - 1);
}

I don’t get the XOR either. Your method breaks down at 0x400001, mine at 0x800000. The code by GloW works for the full (positive) int range. Above method is easily explained - since floats always store their value as 1.mantissa * 2\^exponent, where mantissa is 23 bits wide, adding 1 << 23 for numbers smaller than 1 << 23 makes sure that the exponent is always 23 and your number is directly encoded in the mantissa bits; no shift needed, and you can simply AND the exponent part out of the float.

Anyway, the reason that (int)x can be slow in many implementations is because it may call an implementation function that ensures the FPU rounding mode is set to truncate before the FIST(P) instruction is executed. FIST(P) isn’t that slow nowadays - certainly not compared to writing a float to memory and then loading it into an int register to process some stuff. Doing bitmagic is mostly ideal when the float is already in memory, or when you’re able to manipulate the bits directly in float registers such as in SSE (which has a fast convert-to-int-with-rounding-mode instruction anyway so that’s a moot point, SSE3 even introduces the FPU instruction FISTTP which always truncates, regardless of FPU rounding mode)

6eaf0e08fe36b2c23ca096562dd7a8b7
0
__________Smile_ 101 Apr 06, 2012 at 13:34

My method works for signed numbers, so accepted dynamic range is of the same size, [-0x400000; 0x400000] instead of [0; 0x800000].

And I think any decent compiler (with right flags set) nowadays uses SSEn for floating-point computations, so (int)x will be fastest.

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Apr 07, 2012 at 16:07

@.oisyn

What kind of security are you talking about exactly?

IIRC, the only safe way to do such a cast according to C++ standard is memcpy() (or cast to char and copy byte-by-byte). You could implement raw_cast<>() using memcpy if you want to be C++ standard pedantic and have nice looking code for such casts, e.g. int x=raw_cast<int>(1.0f);

template<typename T, typename U>
T raw_cast(U v_)
{
  // some static assert here to ensure sizeof(T)==sizeof(U) and that you use only non-class types for T & U
  T v;
  memcpy(&v, &v_, sizeof(T));
  return v;
}
B20d81438814b6ba7da7ff8eb502d039
0
Vilem_Otte 117 Apr 10, 2012 at 00:25

Casts are evil and should be avoided … especially when you’re using haskell :D … okay end of joke…

# #23 }:+()___ (Smile) - you’re right and all today compilers should produce SSE code (and if they don’t, you’re either using really old version, or don’t using good optimize flags). So you can actually be happy with (int)value. Doing bit-magic trickery is outdated - it will be outperformed by SSE (or AVX).

Similarly to performing min/max - one can use black magic here, but SSE will heavily outperform it (same for this case, and probably for all black-magic cases today)