在C ++中进行基本的128位整数计算的有效方式？ [英] An efficient way to do basic 128 bit integer calculations in C++?
问题描述
128位整数。
现在我有同样的问题，但是这次我需要在不支持任何一种128位的32位嵌入式系统（Intel Edison）上运行一些基本的128位算术（sum，bitshifts和乘法） 。但是，直接支持64位整数（unsigned long long int）。
我在天真地尝试使用上次在CPU上回答的asm代码，但是我收到了一大堆错误。我真的没有体验过asm，所以：最有效的方式是什么，拥有64位整数，在128位中实现加法，乘法和位移？
谢谢你非常
更新：由于OP尚未接受答案< hint> ;< hint>，我附加了一些代码。
使用上面讨论的库可能是一个好主意。虽然您今天可能只需要几个功能，但最终您可能会发现还需要一个功能。然后再一次。直到最终你最终编写，调试和维护自己的128位数学库。这是浪费你的时间和精力。
说。如果你决定自己滚动：
1）你以前提出的cuda问题已经有c代码的乘法。有没有一些问题？
2）这个转移可能不会从使用asm中获益，所以一个c解决方案对我来说也是有道理的。 尽管如果性能在这里真的是一个问题，我会看看爱迪生是否支持SHLD / SHRD，这可能使得这个更快。否则，m 可能是这样的方法？
my_uint128_t lshift_uint128（const my_uint128_t a，int b）
{
my_uint128_t res;
if（b< 32）{
res.x = a.x< b;
res.y =（a.y<< b）| （a.x>（32-b））;
res.z =（a.z
} elseif（b< 64）{
...
}
return res;
}
更新：由于Edison可能会支持SHLD / SHRD，这是一个替代方案，其中可能比上面的'c'代码更有效。与所有代码一样，您应该测试它。
inline
unsigned int __shld（unsigned int into ，unsigned int from，unsigned int c）
{
unsigned int res;
if（__builtin_constant_p（into）&&
__builtin_constant_p（from）&&b $ b __builtin_constant_p（c））
{
res = （< c）| （从>（32-c））;
}
else
{
asm（shld％b3，％2，％0
：= rm（res）
： 0（into），r（from），ic（c）
：cc）;
}
return res;
}
inline
unsigned int __shrd（unsigned int into，unsigned int from，unsigned int c）
{
unsigned int res;
if（__builtin_constant_p（into）&&
__builtin_constant_p（from）&&b $ b __builtin_constant_p（c））
{
res = （进入>> c）| （从<（32-c））;
}
else
{
asm（shrd％b3，％2，％0
：= rm（res）
： 0（into），r（from），ic（c）
：cc）;
}
return res;
}
my_uint128_t lshift_uint128（const my_uint128_t a，unsigned int b）
{
my_uint128_t res;
if（b< 32）{
res.x = a.x<< b;
res.y = __shld（a.y，a.x，b）;
res.z = __shld（a.z，a.y，b）;
res.w = __shld（a.w，a.z，b）;
} else if（b< 64）{
res.x = 0;
res.y = a.x<<< （b-32）;
res.z = __shld（a.y，a.x，b - 32）;
res.w = __shld（a.z，a.y，b - 32）;
} else if（b& 96）{
res.x = 0;
res.y = 0;
res.z = a.x<< （b-64）;
res.w = __shld（a.y，a.x，b - 64）;
} else if（b< 128）{
res.x = 0;
res.y = 0;
res.z = 0;
res.w = a.x<<< （b - 96）;
} else {
memset（& res，0，sizeof（res））;
}
return res;
}
my_uint128_t rshift_uint128（const my_uint128_t a，unsigned int b）
{
my_uint128_t res;
if（b< 32）{
res.x = __shrd（a.x，a.y，b）;
res.y = __shrd（a.y，a.z，b）;
res.z = __shrd（a.z，a.w，b）;
res.w = a.w>> b;
} else if（b< 64）{
res.x = __shrd（a.y，a.z，b - 32）;
res.y = __shrd（a.z，a.w，b - 32）;
res.z = a.w>> （b-32）;
res.w = 0;
} else if（b& 96）{
res.x = __shrd（a.z，a.w，b - 64）;
res.y = a.w>> （b-64）;
res.z = 0;
res.w = 0;
} else if（b< 128）{
res.x = a.w>> （b - 96）;
res.y = 0;
res.z = 0;
res.w = 0;
} else {
memset（& res，0，sizeof（res））;
}
return res;
}
3）添加可能受益于asm。你可以试试这个：
struct my_uint128_t
{
unsigned int x;
unsigned int y;
unsigned int z;
unsigned int w;
};
my_uint128_t add_uint128（const my_uint128_t a，const my_uint128_t b）
{
my_uint128_t res;
asm（addl％5，％[resx] \\\
\t
adcl％7，％[resy] \\\
\t
adcl％9，％[resz] \\\
\t
adcl％11，％[resw] \\\
\t
：[resx]=& r （res.x），[resy]=& r（res.y），
[resz]=& r（res.z），[resw]=& r（
：％0（ax），irm（bx），
％1（ay），irm（by），
％2 （az），irm（bz），
％3（aw），irm（bw）
：cc）;
return res;
}
我刚刚打破了这一切，所以使用自己的风险。我没有爱迪生，但是这可以与x86一起使用。
更新：如果你只是在积累（认为 to + = from 而不是上面的代码是 c = a + b ），此代码可能会更好地为您服务：
inline
void addto_uint128（my_uint128_t * to，const my_uint128_t from）
{
asm（addl ％[fromx]，％[tox] \\\
\t
adcl％[fromy]，％[toy] \\\
\t
adcl％[fromz]，％ [toz] \\\
\t
adcl％[fromw]，％[tow] \\\
\t
：[tox]+& r（〜> ; x），[玩具]+& r（至> y），
[toz]+& r（→z），[tow]+& （to> w）
：[fromx]irm（from.x），[fromy]irm（from.y），
[fromz]irm z），[fromw]irm（from.w）
：cc）;
}
Some years ago I needed a way to do some basic 128 bit integer math with Cuda: 128 bit integer on cuda?. Now I am having the same problem, but this time I need to run some basic 128 bit arithmetics (sums, bitshifts and multiplications) on a 32 bit embedded system (Intel Edison) that does not support 128 bits of any kind. There are, however, 64 bit integers supported directly (unsigned long long int).
I tried naively to use the asm code that was answered to me last time on the CPU, but I got a bunch of errors. I am really not experienced with asm, so: what is the most efficient way, having 64 bit integers, to implement additions, multiplications and bit shifting in 128 bits?
Thank you very much
Update: Since the OP hasn't accepted an answer yet <hint><hint>, I've attached a bit more code.
Using the libraries discussed above is probably a good idea. While you might only need a few functions today, eventually you may find that you need one more. Then one more after that. Until eventually you end up writing, debugging and maintaining your own 128bit math library. Which is a waste of your time and effort.
That said. If you are determined to roll your own:
1) The cuda question you asked previously already has c code for multiplication. Was there some problem with it?
2) The shift probably won't benefit from using asm, so a c solution makes sense to me here as well. Although if performance is really an issue here, I'd see if the Edison supports SHLD/SHRD, which might make this a bit faster. Otherwise, m Maybe an approach like this?
my_uint128_t lshift_uint128 (const my_uint128_t a, int b)
{
my_uint128_t res;
if (b < 32) {
res.x = a.x << b;
res.y = (a.y << b) | (a.x >> (32 - b));
res.z = (a.z << b) | (a.y >> (32 - b));
res.w = (a.w << b) | (a.z >> (32 - b));
} elseif (b < 64) {
...
}
return res;
}
Update: Since it appears that the Edison may support SHLD/SHRD, here's an alternative which might be more performant than the 'c' code above. As with all code purporting to be faster, you should test it.
inline
unsigned int __shld(unsigned int into, unsigned int from, unsigned int c)
{
unsigned int res;
if (__builtin_constant_p(into) &&
__builtin_constant_p(from) &&
__builtin_constant_p(c))
{
res = (into << c) | (from >> (32 - c));
}
else
{
asm("shld %b3, %2, %0"
: "=rm" (res)
: "0" (into), "r" (from), "ic" (c)
: "cc");
}
return res;
}
inline
unsigned int __shrd(unsigned int into, unsigned int from, unsigned int c)
{
unsigned int res;
if (__builtin_constant_p(into) &&
__builtin_constant_p(from) &&
__builtin_constant_p(c))
{
res = (into >> c) | (from << (32 - c));
}
else
{
asm("shrd %b3, %2, %0"
: "=rm" (res)
: "0" (into), "r" (from), "ic" (c)
: "cc");
}
return res;
}
my_uint128_t lshift_uint128 (const my_uint128_t a, unsigned int b)
{
my_uint128_t res;
if (b < 32) {
res.x = a.x << b;
res.y = __shld(a.y, a.x, b);
res.z = __shld(a.z, a.y, b);
res.w = __shld(a.w, a.z, b);
} else if (b < 64) {
res.x = 0;
res.y = a.x << (b - 32);
res.z = __shld(a.y, a.x, b - 32);
res.w = __shld(a.z, a.y, b - 32);
} else if (b < 96) {
res.x = 0;
res.y = 0;
res.z = a.x << (b - 64);
res.w = __shld(a.y, a.x, b - 64);
} else if (b < 128) {
res.x = 0;
res.y = 0;
res.z = 0;
res.w = a.x << (b - 96);
} else {
memset(&res, 0, sizeof(res));
}
return res;
}
my_uint128_t rshift_uint128 (const my_uint128_t a, unsigned int b)
{
my_uint128_t res;
if (b < 32) {
res.x = __shrd(a.x, a.y, b);
res.y = __shrd(a.y, a.z, b);
res.z = __shrd(a.z, a.w, b);
res.w = a.w >> b;
} else if (b < 64) {
res.x = __shrd(a.y, a.z, b - 32);
res.y = __shrd(a.z, a.w, b - 32);
res.z = a.w >> (b - 32);
res.w = 0;
} else if (b < 96) {
res.x = __shrd(a.z, a.w, b - 64);
res.y = a.w >> (b - 64);
res.z = 0;
res.w = 0;
} else if (b < 128) {
res.x = a.w >> (b - 96);
res.y = 0;
res.z = 0;
res.w = 0;
} else {
memset(&res, 0, sizeof(res));
}
return res;
}
3) The addition may benefit from asm. You could try this:
struct my_uint128_t
{
unsigned int x;
unsigned int y;
unsigned int z;
unsigned int w;
};
my_uint128_t add_uint128 (const my_uint128_t a, const my_uint128_t b)
{
my_uint128_t res;
asm ("addl %5, %[resx]\n\t"
"adcl %7, %[resy]\n\t"
"adcl %9, %[resz]\n\t"
"adcl %11, %[resw]\n\t"
: [resx] "=&r" (res.x), [resy] "=&r" (res.y),
[resz] "=&r" (res.z), [resw] "=&r" (res.w)
: "%0"(a.x), "irm"(b.x),
"%1"(a.y), "irm"(b.y),
"%2"(a.z), "irm"(b.z),
"%3"(a.w), "irm"(b.w)
: "cc");
return res;
}
I just dashed this off, so use at your own risk. I don't have an Edison, but this works with x86.
Update: If you are just doing accumulation (think to += from instead of the code above which is c = a + b), this code might serve you better:
inline
void addto_uint128 (my_uint128_t *to, const my_uint128_t from)
{
asm ("addl %[fromx], %[tox]\n\t"
"adcl %[fromy], %[toy]\n\t"
"adcl %[fromz], %[toz]\n\t"
"adcl %[fromw], %[tow]\n\t"
: [tox] "+&r"(to->x), [toy] "+&r"(to->y),
[toz] "+&r"(to->z), [tow] "+&r"(to->w)
: [fromx] "irm"(from.x), [fromy] "irm"(from.y),
[fromz] "irm"(from.z), [fromw] "irm"(from.w)
: "cc");
}
这篇关于在C ++中进行基本的128位整数计算的有效方式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
