文档章节

用x64汇编语言编写384位无符号整数乘法(上)

safedead
 safedead
发布于 2015/02/06 15:55
字数 1257
阅读 60
收藏 0
点赞 0
评论 0

一、用GCC生成汇编模板

1、编写C语言头文件mul384.h,内容就下面一行
uint64_t mul384(uint64_t c[12], uint64_t a[6], uint64_t b[6]);//c = a * b
2、编写相应C程序文件mul384.c,写个空函数就行了
#include <stdint.h>
#include "mul384.h"
uint64_t mul384(uint64_t c[12], uint64_t a[6], uint64_t b[6])
{
    return 0;
}
3、用GCC编译C程序文件生成汇编文件mul384.s,生成汇编模板文件
gcc -Wall -O2 mul384.c -S

这是mul384.s的全部内容

    .file    "mul384.c"
    .text
    .p2align 4,,15
.globl mul384
    .type    mul384, @function
mul384:
.LFB0:
    .cfi_startproc
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size    mul384, .-mul384
    .ident    "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-11)"
    .section    .note.GNU-stack,"",@progbits

这个mul384.s文件之所以被称为汇编模板,是因为后面编写的汇编代码需要填入下面两句之间

    .cfi_startproc
    .cfi_endproc

替换原先的这两条指令

    xorl    %eax, %eax
    ret

二、算法选择与汇编程序设计

1、C函数接口设计

在x64平台上,无符号整数位宽为64位,一个384位无符号整数需要6个64位无符号整数构成,两个384位无符号整数相乘,其结果需要不超过768位的存储空间,占用12个64位无符号整数空间,故此设计C函数声明为:

uint64_t mul384(uint64_t c[12], uint64_t a[6], uint64_t b[6]);//c = a * b

uint64_t的定义在头文件stdint.h中,因此应用中编译C程序时要包含此头文件。

2、汇编程序输入输出设计

为了提高代码性能,采用“一次输入,一次输出”的内存访问策略,除了最初的输入和最后的输出外,整个运算过程中不访问内存,过程数据全部缓存于SSE寄存器中,为此CPU必须支持SSE42指令集,本文代码只适用于用户态程序,不能用于内核态(不清楚内核态和用户态编程区别的读者请无视这句话)。另外就是调用者传给函数用于输入输出的数组指针a[]、b[]和c[]必须满足16字节对齐要求,否则必将触发CPU错误导致进程崩溃。

3、乘法算法选择

384位乘法在大数运算中属于短位长运算,FFT乘法神马的就别想了,还不够折腾的,Karatsuba算法也不用考虑,对于常用x64处理器来讲,若将基本64位加法指令 addq 耗时设定为1单位,那么带进位64位加法指令 adcq 耗时为2单位,64位无符号乘法指令 mulq 耗时为4单位,综合考虑得失后,采用最基本的分治乘法算法作为本文使用的算法,详细如下:

|====|====|====|====|====|====|====|====|====|====|=====|=====|
|c[0]|c[1]|c[2]|c[3]|c[4]|c[5]|c[6]|c[7]|c[8]|c[9]|c[10]|c[11]|
|====|====|====|====|====|====|====|====|====|====|=====|=====|
|a[0]*b[0]|    |    |    |    |    |    |    |    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |a[0]*b[1]|    |    |    |    |    |    |    |     |     |
|    |a[1]*b[0]|    |    |    |    |    |    |    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |a[0]*b[2]|    |    |    |    |    |    |     |     |
|    |    |a[1]*b[1]|    |    |    |    |    |    |     |     |
|    |    |a[2]*b[0]|    |    |    |    |    |    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |a[0]*b[3]|    |    |    |    |    |     |     |
|    |    |    |a[1]*b[2]|    |    |    |    |    |     |     |
|    |    |    |a[2]*b[1]|    |    |    |    |    |     |     |
|    |    |    |a[3]*b[0]|    |    |    |    |    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |    |a[0]*b[4]|    |    |    |    |     |     |
|    |    |    |    |a[1]*b[3]|    |    |    |    |     |     |
|    |    |    |    |a[2]*b[2]|    |    |    |    |     |     |
|    |    |    |    |a[3]*b[1]|    |    |    |    |     |     |
|    |    |    |    |a[4]*b[0]|    |    |    |    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |    |    |a[0]*b[5]|    |    |    |     |     |
|    |    |    |    |    |a[1]*b[4]|    |    |    |     |     |
|    |    |    |    |    |a[2]*b[3]|    |    |    |     |     |
|    |    |    |    |    |a[3]*b[2]|    |    |    |     |     |
|    |    |    |    |    |a[4]*b[1]|    |    |    |     |     |
|    |    |    |    |    |a[5]*b[0]|    |    |    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |    |    |    |a[1]*b[5]|    |    |     |     |
|    |    |    |    |    |    |a[2]*b[4]|    |    |     |     |
|    |    |    |    |    |    |a[3]*b[3]|    |    |     |     |
|    |    |    |    |    |    |a[4]*b[2]|    |    |     |     |
|    |    |    |    |    |    |a[5]*b[1]|    |    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |    |    |    |    |a[2]*b[5]|    |     |     |
|    |    |    |    |    |    |    |a[3]*b[4]|    |     |     |
|    |    |    |    |    |    |    |a[4]*b[3]|    |     |     |
|    |    |    |    |    |    |    |a[5]*b[2]|    |     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |    |    |    |    |    |a[3]*b[5]|     |     |
|    |    |    |    |    |    |    |    |a[4]*b[4]|     |     |
|    |    |    |    |    |    |    |    |a[5]*b[3]|     |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |    |    |    |    |    |    |a[4]*b[5] |     |
|    |    |    |    |    |    |    |    |    |a[5]*b[4] |     |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |    |    |    |    |    |    |    |    |    | a[5]*b[5] |
|====|====|====|====|====|====|====|====|====|====|=====|=====|
4、寄存器规划

以高性能运算为目的的汇编语言编程设计中,寄存器规划是重中之重,还好384位乘法对x64处理器来讲只是入门级小菜,所以我用了两周时间完成了寄存器规划,详细使用规划如下:

(1).rdi是输出数据c[]的首地址,rsi是输入数据a[]的首地址,rdx是输入数据b[]的首地址

(2).xmm0 ~ xmm5这个6个SSE寄存器用于缓存运算过程与结果数据
|---------|---------|---------|---------|---------|-----------|
|  %xmm0  |  %xmm1  |  %xmm2  |  %xmm3  |  %xmm4  |  %xmm5    |
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|c[0]|c[1]|c[2]|c[3]|c[4]|c[5]|c[6]|c[7]|c[8]|c[9]|c[10]|c[11]|
|----|----|----|----|----|----|----|----|----|----|-----|-----|

(3).xmm6 ~ xmm8这个6个SSE寄存器用于输入数据a和b
|---------|---------|---------|---------|---------|---------|
|  %xmm6  |  %xmm7  |  %xmm8  |  %xmm6  |  %xmm7  |  %xmm8  |
|----|----|----|----|----|----|----|----|----|----|----|----|
|a[0]|a[1]|a[2]|a[3]|a[4]|a[5]|b[0]|b[1]|b[2]|b[3]|b[4]|b[5]|
|----|----|----|----|----|----|----|----|----|----|----|----|

(4).xmm14和xmm15用于r12 ~ r15的备份与恢复
|---------|---------|
| %xmm14  | %xmm15  |
|----|----|----|----|
|%r12|%r13|%r14|%r15|
|----|----|----|----|

(5).r10 ~ r15用于乘法指令mulq的操作数,其数值固定
|----|----|----|----|----|----|
|%r10|%r11|%r12|%r13|%r14|%r15|
|----|----|----|----|----|----|
|a[1]|a[3]|a[5]|b[1]|b[3]|b[5]|
|----|----|----|----|----|----|

(6).r8, r9, rsi三个通用寄存器用于累加过程,循环使用
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|c[0]|c[1]|c[2]|c[3]|c[4]|c[5]|c[6]|c[7]|c[8]|c[9]|c[10]|c[11]|
|----|----|----|----|----|----|----|----|----|----|-----|-----|
|    |%r8 |%r9 |%rsi|%r8 |%r9 |%rsi|%r8 |%r9 |%rsi|%r8  |%r9  |
|----|----|----|----|----|----|----|----|----|----|-----|-----|


© 著作权归作者所有

共有 人打赏支持
safedead
粉丝 2
博文 19
码字总数 16374
作品 0
海淀
高精度乘法程序设计汇编语言版-课程设计

一段尘封已久的代码,当年的课程设计!高精度乘法程序设计汇编语言版 1.1 课程设计题目 高精度乘法程序设计 1.2 课程设计目的 1. 巩固和加深课堂所学知识 2. 将课本上的理论知识和实际应用有...

城邑耕夫 ⋅ 2012/04/14 ⋅ 0

汇编总结:无符号除法,有符号除法,取余,无符号乘法,有符号乘法指令

本文分为3个模块。 示例---该指令的示例 解释---为指令不好理解的地方 练习---为了更熟悉该指令 1.1 有符号除法指令及取余example: 在c语言里要完成 8 / 2的汇编指令如下: 在c语言里要完成 ...

guonaihong ⋅ 2015/10/07 ⋅ 0

php 位移运算符(>右移)

位移运算符 << 位左移 左移运算的实质是将对应的数据的二进制值逐位左移若干位,并在空出的位置上填0,最高位溢出并舍弃。例 如 $a=10; $b=$a<<2; 则$b=40,根据手册描述可以看出位运算可以看...

happy_limit ⋅ 2013/05/31 ⋅ 1

《深入理解计算机系统》2——信息编码

计算机中数字的主要表示方式有无符号数,补码数和浮点数三种。计算机中最小可寻址单位为8位的块,或者称为字节。机器级程序将存储器视为一个非常大的字节数组,称为虚拟存储器,虚拟存储器中...

曹越 ⋅ 2012/04/10 ⋅ 0

从奔腾I的VCD播放到AI区块链播放器——程序优化的魔法

从上个世纪本腾I电脑播放VCD,通过巧妙的算法优化,可以在损失部分效果的情况下在低性能的电脑上播放VCD。时至今日,硬件性能大幅飙升,许多算法近乎“失传”了。但对于充满好奇心的程序员,...

LiveVideoStack ⋅ 04/23 ⋅ 0

汇编语言指令英文全称

1.通用数据传送指令 MOV----> move MOV dest,src;dest←src MOV指令把一个字节或字的操作数从源地址src传送至目的地址dest。 MOVSX---->extended move with sign data MOVZX---->extended mo......

伽罗kapple ⋅ 2015/10/24 ⋅ 0

【原创翻译】数值(number)

Go有很多种表示数值的类型。通常来说,我们将数值分成两类:整数和浮点数。 整数 整数——跟数学意义上的整数一样——没有小数部分(...,-3,-2,-1,-,1,2,3,...)。但不像我们用10进制表示整数...

zingscript ⋅ 2014/01/20 ⋅ 0

C#数据类型 什么是有符号的64位整数和无符号的64位整数

C#中,数据类型中存在 有字符和无字符类型整数,eg:什么是有符号的64位整数和无符号的64位整数 Short:代表有符号的16位整数,范围从-32768 ~ 32767 ushort:代表无符号的16位整数,范围从-...

心路独舞 ⋅ 2015/12/16 ⋅ 3

OpenRTMFP/Cumulus Primer(9)AMF解析之BinaryReader/Writer

OpenRTMFP/Cumulus Primer(9)AMF解析之BinaryReader/Writer Author: 柳大·Poechant(钟超) Email: zhongchao.ustc#gmail.com (#->@) Blog: Blog.CSDN.net/Poechant Date: April 24th, 20......

晨曦之光 ⋅ 2012/04/24 ⋅ 0

Java程序员从笨鸟到菜鸟之(九十六)深入java虚拟机(五)——java本地接口JNI详解

对于java程序员来说,java语言的好处和优点,我想不用我说了,大家自然会说出很多一套套的。但虽然我们作为java程序员,但我们不得不承认java语言也有一些它本身的缺点。比如在性能、和底层打...

长平狐 ⋅ 2012/11/12 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

笔试题之Java基础部分【简】【一】

基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语法,集合的语法,io 的语法,虚拟机方面的语法,其他 1.length、length()和size() length针对...

anlve ⋅ 13分钟前 ⋅ 1

table eg

user_id user_name full_name 1 zhangsan 张三 2 lisi 李四 `` ™ [========] 2018-06-18 09:42:06 星期一½ gdsgagagagdsgasgagadsgdasgagsa...

qwfys ⋅ 37分钟前 ⋅ 0

一个有趣的Java问题

先来看看源码: public class TestDemo { public static void main(String[] args) { Integer a = 10; Integer b = 20; swap(a, b); System.out......

linxyz ⋅ 42分钟前 ⋅ 0

十五周二次课

十五周二次课 17.1mysql主从介绍 17.2准备工作 17.3配置主 17.4配置从 17.5测试主从同步 17.1mysql主从介绍 MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主...

河图再现 ⋅ 今天 ⋅ 0

docker安装snmp rrdtool环境

以Ubuntu16:04作为基础版本 docker pull ubuntu:16.04 启动一个容器 docker run -d -i -t --name flow_mete ubuntu:16.04 bash 进入容器 docker exec -it flow_mete bash cd ~ 安装基本软件 ......

messud4312 ⋅ 今天 ⋅ 0

OSChina 周一乱弹 —— 快别开心了,你还没有女友呢。

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享吴彤的单曲《好春光》 《好春光》- 吴彤 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :小萝莉街上乱跑,误把我认错成...

小小编辑 ⋅ 今天 ⋅ 8

Java 开发者不容错过的 12 种高效工具

Java 开发者常常都会想办法如何更快地编写 Java 代码,让编程变得更加轻松。目前,市面上涌现出越来越多的高效编程工具。所以,以下总结了一系列工具列表,其中包含了大多数开发人员已经使用...

jason_kiss ⋅ 昨天 ⋅ 0

Linux下php访问远程ms sqlserver

1、安装freetds(略,安装在/opt/local/freetds 下) 2、cd /path/to/php-5.6.36/ 进入PHP源码目录 3、cd ext/mssql进入MSSQL模块源码目录 4、/opt/php/bin/phpize生成编译配置文件 5、 . ./...

wangxuwei ⋅ 昨天 ⋅ 0

如何成为技术专家

文章来源于 -- 时间的朋友 拥有良好的心态。首先要有空杯心态,用欣赏的眼光发现并学习别人的长处,包括但不限于工具的使用,工作方法,解决问题以及规划未来的能力等。向别人学习的同时要注...

长安一梦 ⋅ 昨天 ⋅ 0

Linux vmstat命令实战详解

vmstat命令是最常见的Linux/Unix监控工具,可以展现给定时间间隔的服务器的状态值,包括服务器的CPU使用率,内存使用,虚拟内存交换情况,IO读写情况。这个命令是我查看Linux/Unix最喜爱的命令...

刘祖鹏 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部