亲爱的汇编/C++ 开发人员,
问题是:即使它有效,在两个 ASM 块之间传播进位(或任何标志)是现实的还是完全疯狂的?
几年前,我开发了一个用于低于 512 位(在编译时)的大型算术的整数库。我当时没有使用 GMP,因为对于这种规模,由于内存分配和二进制表示的模型选择,GMP 变得更慢bench http://comp-phys.org/vli/bench.html.
我必须承认我使用以下命令创建了 ASM(字符串块)BOOST_PP
,它不是很光荣(好奇的看看它vli https://github.com/timocafe/vli)。图书馆运转良好。
然而我注意到此时不可能在两个 ASM 内联块之间传播状态寄存器的进位标志。这是合乎逻辑的,因为对于编译器在两个块之间生成的任何助记符,寄存器都会被重置(除了mov
说明(来自我的汇编知识))。
昨天,我想到了在两个 ASM 块之间传播进位的想法,这有点棘手(使用递归算法)。它正在发挥作用,但我认为我很幸运。
#include <iostream>
#include <array>
#include <cassert>
#include <algorithm>
//forward declaration
template<std::size_t NumBits>
struct integer;
//helper using object function, partial specialization is forbiden on functions
template <std::size_t NumBits, std::size_t W, bool K = W == integer<NumBits>::numwords>
struct helper {
static inline void add(integer<NumBits> &a, const integer<NumBits> &b){
helper<NumBits, integer<NumBits>::numwords>::add(a,b);
}
};
// first addition (call first)
template<std::size_t NumBits, std::size_t W>
struct helper<NumBits, W, 1> {
static inline void add(integer<NumBits> &a, const integer<NumBits> &b){
__asm__ (
"movq %1, %%rax \n"
"addq %%rax, %0 \n"
: "+m"(a[0]) // output
: "m" (b[0]) // input only
: "rax", "cc", "memory");
helper<NumBits,W-1>::add(a,b);
}
};
//second and more propagate the carry (call next)
template<std::size_t NumBits, std::size_t W>
struct helper<NumBits, W, 0> {
static inline void add(integer<NumBits> &a, const integer<NumBits> &b){
__asm__ (
"movq %1, %%rax \n"
"adcq %%rax, %0 \n"
: "+m"(a[integer<NumBits>::numwords-W])
: "m" (b[integer<NumBits>::numwords-W])
: "rax", "cc", "memory");
helper<NumBits,W-1>::add(a,b);
}
};
//nothing end reccursive process (call last)
template<std::size_t NumBits>
struct helper<NumBits, 0, 0> {
static inline void add(integer<NumBits> &a, const integer<NumBits> &b){};
};
// tiny integer class
template<std::size_t NumBits>
struct integer{
typedef uint64_t value_type;
static const std::size_t numbits = NumBits;
static const std::size_t numwords = (NumBits+std::numeric_limits<value_type>::digits-1)/std::numeric_limits<value_type>::digits;
using container = std::array<uint64_t, numwords>;
typedef typename container::iterator iterator;
iterator begin() { return data_.begin();}
iterator end() { return data_.end();}
explicit integer(value_type num = value_type()){
assert( -1l >> 1 == -1l );
std::fill(begin(),end(),value_type());
data_[0] = num;
}
inline value_type& operator[](std::size_t n){ return data_[n];}
inline const value_type& operator[](std::size_t n) const { return data_[n];}
integer& operator+=(const integer& a){
helper<numbits,numwords>::add(*this,a);
return *this;
}
integer& operator~(){
std::transform(begin(),end(),begin(),std::bit_not<value_type>());
return *this;
}
void print_raw(std::ostream& os) const{
os << "(" ;
for(std::size_t i = numwords-1; i > 0; --i)
os << data_[i]<<" ";
os << data_[0];
os << ")";
}
void print(std::ostream& os) const{
assert(false && " TO DO ! \n");
}
private:
container data_;
};
template <std::size_t NumBits>
std::ostream& operator<< (std::ostream& os, integer<NumBits> const& i){
if(os.flags() & std::ios_base::hex)
i.print_raw(os);
else
i.print(os);
return os;
}
int main(int argc, const char * argv[]) {
integer<256> a; // 0
integer<256> b(1);
~a; //all the 0 become 1
std::cout << " a: " << std::hex << a << std::endl;
std::cout << " ref: (ffffffffffffffff ffffffffffffffff ffffffffffffffff ffffffffffffffff) " << std::endl;
a += b; // should propagate the carry
std::cout << " a+=b: " << a << std::endl;
std::cout << " ref: (0 0 0 0) " << std::endl; // it works but ...
return 0;
}
我得到了正确的结果(它必须在版本 -O2 或 -O3 中编译!)并且 ASM 是正确的(在我的 Mac 上使用 clang++:Apple LLVM 版本 9.0.0 (clang-900.0.39.2))
movq -96(%rbp), %rax
addq %rax, -64(%rbp)
## InlineAsm End
## InlineAsm Start
movq -88(%rbp), %rax
adcq %rax, -56(%rbp)
## InlineAsm End
## InlineAsm Start
movq -80(%rbp), %rax
adcq %rax, -48(%rbp)
## InlineAsm End
## InlineAsm Start
movq -72(%rbp), %rax
adcq %rax, -40(%rbp)
我确信它正在工作,因为在优化过程中,编译器删除了 ASM 块之间的所有无用指令(在调试模式下它失败了)。
你怎么认为 ?绝对不安全?编译器人员知道它的稳定性吗?
总而言之:我这样做只是为了好玩:) 是的,GMP 是大型算术的解决方案!