itoa SIMD

Logic:value = ...;
divisors = [ ..., 1000, 100, 10, 1 ];
modulo = [ ..., 10, 10, 10, 10, 10 ];
increment = [ ..., 0x30, 0x30, 0x30, 0x30 ]

sse_divide(value, divisors)
sse_mod(value, modulo)
sse_add(value, increment);

How it works:value = 413;
413 413 413
divide 100 10 1
= 4 41 413
mod 4 1 3
add 0x34 0x31 0x33
Or, first implement unrolled itoa, then implement that with SSE instructions.

Logic:value = ...;
divisors = [ ..., 1000, 100, 10, 1 ];
modulo = [ ..., 10, 10, 10, 10, 10 ];
increment = [ ..., 0x30, 0x30, 0x30, 0x30 ]

sse_divide(value, divisors)
sse_mod(value, modulo)
sse_add(value, increment);

How it works:value = 413;
413 413 413
divide 100 10 1
= 4 41 413
mod 4 1 3
add 0x34 0x31 0x33
Or, first implement unrolled itoa, then implement that with SSE instructions.

Thanks very much for your reply, one quick question is how to implement sse modulo in that case ?


Ive just checked Intel SW Developers Manual Vol2B , could not find ,

but just found something like this : http://think-in-co.d...modulo-mit-sse/

Also I can`t understand how to do flooring with SIMD , since manual modulus operation with SIMD relies on the flooring.

Thanks very much for your reply, one quick question is how to implement sse modulo in that case ?[/quote]

I'm not sure it can be done in a trivial manner. You could start from mod(a,n) = a-n*floor(a/n), but division would likely require switching to floating point.

The solution I gave was about vectorization. I can't think of a way to actually implement it practically, there are too many constraints in instruction sets.

After looking around a bit, here's a method that can be implemented, see remu10 in document linked from there.

int remu10(unsigned n) {
static char table[16] = {0, 1, 2, 2, 3, 3, 4, 5,
5, 6, 7, 7, 8, 8, 9, 0};
n = (0x19999999*n + (n >> 1) + (n >> 3)) >> 28;
return table[n];
}

Actually , for an assignment , I need to use SIMD insructions somehow to implement itoa fully in assembly.

Regarding the original code I have sent , is there anything you would suggest to somehow use SIMD instructions ?



I am strugglnig to do so , but I could not find any yet , for the worst case writing a SIMD itoa from scratch is also ok , ofcourse I would need modulo/floor for this one

Actually , for an assignment , I need to use SIMD insructions somehow to implement itoa fully in assembly.

School assignment? That seems rather poor choice.

It's doable, barely. But most of the work will go into hacking around the limitations of SSE and MMX registers. Itoa is just a poor fit for SSE-based implementation.

Regarding the original code I have sent , is there anything you would suggest to somehow use SIMD instructions ?[/quote]Nope. SIMD algorithm is completely different in every way. It's not something you sprinkle over in the end.

am strugglnig to do so , but I could not find any yet , for the worst case writing a SIMD itoa from scratch is also ok , ofcourse I would need modulo/floor for this one[/quote]The modulo formula is given above, the div/10 can be found in linked article.

But it will still result in a lot of ugly code. There's also impedance mismatch. 32-bit integer will result in sign+9 digits, but SSE prefers multiples of 4 or 16 elements. So regardless of whether working with 32 or 8 bit values, there is no perfect fit. Then there's potential issues with rounding, signedness, whether resulting string is properly aligned.

As said, it's doable, just a lot of effort for, IMHO, no useful gain.

I see your points , actually the method you mentinoed is the only starting point in my hand including the other link for modulo

so i think for the time being the best thing for me is starting to implement , perhaps I can come up with any ideas as I go through



Thanks a lot for information

As things have turned out I learned that I am allowed to change the definition/signature of itoa

So I want to implement a different version of itoa , which will take 4 or 8 integers at a time and return string will be their combined ascii versions.


Yes , the pdf in the link above already supplies all necessary information.


I wan to re-ask my question for this special case because perhaps another approach for that particular case might be suggested.

I have an itoa ASM implementation. I would like to use SIMD for it.

Because converting numbers to strings - presumably so that they can then be written to a file or a console window, which takes far, far more time - is performance-critical? What?

Because converting numbers to strings - presumably so that they can then be written to a file or a console window, which takes far, far more time - is performance-critical? What?

Even though the topic here is about some sort of homework, there is actually a theoretical case - map/reduce. While raw binary dump would be ideal, it gets complicated in heterogeneous environments. A good implementation could approach that of memcpy.

But as said above, it would need to be fairly constrained and SSE opcodes really aren't ideal for this.

BTW a note regarding one of my posts above which is about flooring , just in case someone may look for it in future

I did it by using this : http://msdn.microsoft.com/en-us/library/1h005y6x.aspx