说在前面
????????这篇文章的内容主要源于个人在学习基于ARM架构的cos开发时所碰到的问题，因此，所涉及的东西是一些在ARM架构下进行开发的初学者应知的注意事项或技巧。但这篇文章会由浅入深，从工程实现中会考虑的问题出发，来逐一介绍这些技巧，让一个初学者写出更优秀的C程序。（本人也是初学者，个人在学习时的参考资料是《ARM System Developer's Guide》）
? ? ? ? 这篇文章如有幸被某位读者发现，并找到了其中的不足，欢迎您随时与我沟通讨论。
????????在开始读这篇文章前，我假设读者对ARM的一些基本汇编指令已经有所了解。接下来，我会从变量类型，有无符号类型，如何写好一个循环体等方面进行介绍。在以后的文章中，我将使用我接下来提到的技巧去实现一些密码算法，比如一些国际上常用的对称或非对称密码算法，如RSA，ECC, AES，DES, SHA等，和一些国密算法，如SM2，SM3，SM4，SM9等。当然，这些实现不只是包含功能，我还会向读者介绍怎么去实现安全的密码算法以及这些密码算法的安全调用。
1. 局部变量类型
? ? ? ? 因为大多数的ARM处理器的数据操作都仅限于32位，因此，哪怕当前在操作8位或者16位值，也应尽可能的将局部变量定义为32-bit数据类型，如int或者long。除非你想要一种模运算，如255+1=0，此时应该使用char类型的局部变量。为了更直观的了解为什么要这么做，我们举下面这样一个例子。
int check(int *data)
{
char i;
int sum = 0;
for (i = 0; i < 64; i++)
{
sum += data[i];
}
return sum;
}? ? ? ? 我们注意到上面的代码对于i的定义我们使用了char类型。通常在编写程序时，会考虑占用更小的寄存器空间和栈空间而选择char类型，但在ARM中，这种考虑是错误的。上面的代码编译后循环体部分是这样的：
check_loop
LDR r3,[r2,r1,LSL #2] ; r3 = data[i]
ADD r1,r1,#1 ; r1 = i+1
AND r1,r1,#0xff ; i = (char)r1
CMP r1,#0x40 ; compare i, 64
ADD r0,r3,r0 ; sum += r3
BCC check_loop ; if (i<64) loop
MOV pc,r14 ; return sum? ? ? ? 我们很容易发现，上面有一个步骤是 i = (char) r1。这一步是在 i 和64比较前，对 i 进行强制类型转换。但如果将 i 定义为int类型，就可以免除这一步骤，在一个循环中能减少一条指令是有很大的性能提升的，特别是对于比较重要和经常使用的循环体。同样，假设data所指向的数据是16-bit类型，并且我们最后想获得一个16-bit的checksum的话，有的人会这么写：（下面的循环体中不使用sum+=data[i]是因为这样做可能会产生一个warning）
short check(short *data)
{
unsigned int i;
short sum = 0;
for (i = 0; i < 64; i++)
{
sum = (short)(sum + data[i]);
}
return sum;
}? ? ? ? 它的编译结果是这样的：
check_loop
ADD r3,r2,r1,LSL #1 ; r3 = &data[i]，这里多一步
LDRH r3,[r3,#0] ; r3 = data[i]
ADD r1,r1,#1 ; i++
CMP r1,#0x40 ; compare i, 64
ADD r0,r3,r0 ; r0 = sum + r3
MOV r0,r0,LSL #16
MOV r0,r0,ASR #16 ; sum = (short)r0, 这里多两步
BCC check_loop ; if (i<64) goto loop
MOV pc,r14 ; return sum? ? ? ? 这比起直接使用int类型，多了足足三条指令，原因是：1）LDRH指令不支持地址偏移，无法像LDR那样直接读取data；2）将求和结果转换为short需要两个mov指令，用两个mov指令是为了实现符号扩展。但是，这样额外的指令是完全可以避免的。
? ? ? ? 为了解决上面两个问题，我们可以这么做：对于第二点，将sum定义为int类型，只在最后返回（short）sum。而对于第一个问题，由于ARM的所有load和store指令都支持后增量寻址，因此，我们只需要将sum = (short)(sum + data[i])更改为sum += *(data++)即可。当然，你也可以写成sum += *data，data++。
2. 函数参数类型
????????第一节中描述的对局部变量定义使用int所带来的好处，这一点在函数参数类型定义上也同样适用。但是我们还是来看看下面这样的情况：
short add(short a, short b)
{
return a + (b>>1);
}????????对于上面的代码，armcc的编译结果是这样的：
ADD r0,r0,r1,ASR #1 ; r0 = (int)a + ((int)b >> 1)
MOV r0,r0,LSL #16
MOV r0,r0,ASR #16 ; r0 = (short)r0
MOV pc,r14 ; return r0? ? ? ? gcc的编译结果是这样的：
MOV r0, r0, LSL #16
MOV r1, r1, LSL #16
MOV r1, r1, ASR #17 ; r1 = (int)b >> 1
ADD r1, r1, r0, ASR #16 ; r1 += (int)a
MOV r1, r1, LSL #16
MOV r0, r1, ASR #16 ; r0 = (short)r1
MOV pc, lr ; return r0? ? ? ? 这里可以看出，armcc在输出前将结果转换为short类型，gcc在计算前和输出前都进行了类型转换。于是，我们可以很容易得出结论，尽可能的使用(unsigned) int定义函数参数类型和返回值，这样可以减小代码量以提高效率。
3. 有符号和无符号类型
? ? ? ? 对于加减乘三种运算，有符号运算和无符号运算在效率上并没有差异，但是除法不然。我们还是举例说明问题，下面是一个求平均值的小方法：
int average(int a, int b)
{
return (a+b)/2;
}? ? ? ? 它的编译结果是：
average
ADD r0,r0,r1 ; r0 = a + b
ADD r0,r0,r0,LSR #31 ; if (r0<0) r0++
MOV r0,r0,ASR #1 ; r0 = r0 >> 1
MOV pc,r14 ; return r0? ? ? ? ? 汇编代码显示，编译器在对加法结果右移前，先对其进行了是否为负判断并加1的过程，即将除以2的过程替换为了：
(x<0) ? ((x+1) >> 1): (x >> 1)之所以这么做，是因为a是有符号数，对于负数，除以2并不能只使用简单的右移操作来完成，比如，-3>>1 = -2，但是-3/2 = -1。因此，使用无符号数除法会更有效率。
? ? ? ? 这里给出一些总结性的建议：1）尽量使用32-bit数据类型定义函数参数，局部变量以及函数返回值，即使当前参数值会很小。但对于全局变量，尽量使用小的数据类型，这样可以节省内存；2）尽量使用指针叠加来遍历数组，例如前面使用的*(data++)，避免使用data[i]这种地址加偏移的方式来遍历；3）尽量避免数据类型转换；4）当函数参数大于4个时，使用结构体指针传参，因为ARM用于传参的寄存器只有R0-R3，第5个参数开始，会有入栈出栈过程。
?4. C语言的循环结构
? ? ? ? ?这一小节，我会讲到如何让for和while循环更加有效率(基于ARM)，整个过程会拆分成几块来讲述，以便于更深刻的理解。
4.1 固定循环次数的循环结构
? ? ? ? 首先，我们关注具有固定循环次数的循环结构和如何写好一个ARM上的for循环。我们回到第一节中给出的check函数这一案例，在之前的讨论中，我们知道这一方法最好的实现方式是这样的：
int check(int *data)
{
unsigned int i;
int sum=0;
for (i=0; i<64; i++)
{
sum += *(data++);
}
return sum;
}? ? ? ? 它的完整的编译结果是：
check
MOV r2,r0 ; r2 = data
MOV r0,#0 ; sum = 0
MOV r1,#0 ; i = 0
check_loop
LDR r3,[r2],#4 ; r3 = *(data++)
ADD r1,r1,#1 ; i++
CMP r1,#0x40 ; compare i, 64
ADD r0,r3,r0 ; sum += r3
BCC checks_loop ; if (i<64) goto loop
MOV pc,r14 ; return sum????????该函数的循环结构（抛开循环体）可以看做三个步骤：1）i 的递增；2）比较64与i；3）执行分支。但在ARM中，这三个步骤可以缩减为两个步骤来完成：1）i 递减和设置标志位；2）执行分支。代码如下：
int check(int *data)
{
unsigned int i;
int sum=0;
for (i=64; i!=0; i--)
{
sum += *(data++);
}
return sum;
}????????该代码的编译结果如下：
check
MOV r2,r0 ; r2 = data
MOV r0,#0 ; sum = 0
MOV r1,#0x40 ; i = 64
check_loop
LDR r3,[r2],#4 ; r3 = *(data++)
SUBS r1,r1,#1 ; i-- and set flags
ADD r0,r3,r0 ; sum += r3
BNE check_loop ; if (i!=0) goto loop
MOV pc,r14 ; return sum????????我们可以看到，将计数器 i 由递增判断更改为递减判断后，代码的编译结果中少了比较 i 和64这一步骤。原因是，SUBS会在做完减法后设置标志位，类似于将计算结果保存起来了，BNE直接查看这一结果（检验标志位）是否为0来判断是否继续执行循环。在ARM中，支撑一个循环结构的指令数最优情况就是两条，在程序的性能评估时，也会将循环结构视作2条指令，4个cycle来计算。
????????除此之外，我们还注意到了，进行终止判断的代码是 i!=0，而不是i>0，这一点也十分重要。对于无符号数 i 来说，这两种不同的终止条件判断方法没有什么不同，但是对于有符号数就有所区别了。理想中，当使用有符号计数值 i 时，编译结果会是SUBS+BGT两条指令，代码整体的指令数目不会发生变化，但这是错误的。真实的编译结果是SUB+CMP+BGT这三条指令来支撑整个循环结构。而对于SUB+CMP+BGT这样的指令顺序，会导致一个问题，当 i = -0x80000000时，由于先减1再比较，会导致 i-1 = +0x7fffffff，i大于0然后继续循环。尽管这种情况出现的概率很小，但是还是建议尽可能的使用unsigned int来定义计数器并递减计数，并且将i>0这样的终止判断改写为i！=0。
4.2?不定循环次数的循环结构
? ? ? ? 对于不定循环次数的循环结构，即循环次数由一个变量来确定，我们能想到的实现方法大概和之前相同。不过我们不再需要计数器 i 了。现在假设check函数有另外一个决定循环次数的参数N，我们首先根据之前提及的技巧来实现这一函数：
int check(int *data, unsigned int N)
{
int sum=0;
for (; N!=0; N--)
{
sum += *(data++);
}
return sum;
}它的编译结果是：
check
MOV r2,#0 ; sum = 0
CMP r1,#0 ; compare N, 0
BEQ check_end ; if (N==0) goto end
check_loop
LDR r3,[r0],#4 ; r3 = *(data++)
SUBS r1,r1,#1 ; N-- and set flags
ADD r2,r3,r2 ; sum += r3
BNE check_loop ; if (N!=0) goto loop
check_end
MOV r0,r2 ; r0 = sum
MOV pc,r14 ; return r0? ? ? ? 不难看到，在进入循环之前，编译器会先检验N是否非0来判断是否要执行循环体。但大多数情况，这一步骤都有些多余，特别是你在确定N一定不为0时。如果确定循环体一定会被执行，便可以将for循环替换为do-while循环来优化代码。替换为while循环后的代码如下：
int check(int *data, unsigned int N)
{
int sum=0;
do
{
sum += *(data++);
} while (--N!=0);
return sum;
}????????现在的编译结果如下：
check
MOV r2,#0 ; sum = 0
check_loop
LDR r3,[r0],#4 ; r3 = *(data++)
SUBS r1,r1,#1 ; N-- and set flags
ADD r2,r3,r2 ; sum += r3
BNE check_loop ; if (N!=0) goto loop
MOV r0,r2 ; r0 = sum
MOV pc,r14 ; return r0????????这样一来，我们又节省了两个cycle。
4.3 循环扩展
????????在ARM7或ARM9中，支撑循环的两个指令SUBS和BNE分别需要1cycle和3cycles。在实际的工程实现中，可以使用循环扩展这一方法来优化代码。循环扩展通过降低在整个循环执行的过程中SUBS和BNE指令的占比来提高效率，即重复结构体，比如在check函数中，将sum += *(data++)多复制几次。现在我们给出优化后的代码和对应的编译结果。
int checksum_v9(int *data, unsigned int N)
{
int sum=0;
do
{
sum += *(data++);
sum += *(data++);
sum += *(data++);
sum += *(data++);
N -= 4;
} while ( N!=0);
return sum;
}check
MOV r2,#0 ; sum = 0
check_loop
LDR r3,[r0],#4 ; r3 = *(data++)
SUBS r1,r1,#4 ; N -= 4 & set flags
ADD r2,r3,r2 ; sum += r3
LDR r3,[r0],#4 ; r3 = *(data++)
ADD r2,r3,r2 ; sum += r3
LDR r3,[r0],#4 ; r3 = *(data++)
ADD r2,r3,r2 ; sum += r3
LDR r3,[r0],#4 ; r3 = *(data++)
ADD r2,r3,r2 ; sum += r3
BNE check_loop ; if (N!=0) goto loop
MOV r0,r2 ; r0 = sum
MOV pc,r14 ; return r0????????上面的例子中，我们将循环次数减少为之前的1/4，整个循环结构需要的开销由8cycles变为20cycles。20/4与8相比，我们几乎将性能提升了一倍，而代价只是增加了少量代码。并且我计算的前提是对于ARM7内核，对于ARM9以及之后的核，提升只会更大。但是，要这么做我们必须考虑两个问题：1）循环体扩展次数如何确定？2）如果N不是我要拆成的数目的倍数怎么办？
? ? ? ? 对于第一个问题，在工程实现中一般是这么考量的：尽管循环扩展能提高效率，但是它会导致代码量增大，如果所有的循环都是用循环扩展来提高效率，可能会导致效率不升反降。于是，我们只对那些对于整个工程来说比较重要的循环体实施循环扩展。用数据来说明，假设某一个循环结构对整个工程来说十分重要或者被经常使用，比如，在整个工程中占比30%。再假设你将这个循环结构整体展开到了512字节，也就是128条指令。那么整个循环中SUBS+BNE两条指令的开销占比大概就是3/128，也就是说，这两条指令在整个工程中占比为1/128，不到百分之1。通常来说，当收益小于百分之1时，就已经不值得再实施循环扩展了。
? ? ? ? 对于第二个问题，通常在工程实施起初，就应该设置data这样的数组的大小为2，4或者8的倍数方便以后进行扩展，如果做不到这一点，那就只能增加一部分代码来处理去掉倍数余下的部分。但是要注意，如果采用额外的代码来处理余下的部分，意味着你不能再使用do-while循环了，因为我们采用do-while循环的原因是，我们确定循环结构至少会执行一次。当然，我们还有一些其他场景会强制采用do-while循环来实施，比如，我希望某个循环至少要被执行一次，以防御一些恶意的注错攻击，此时我们不以效率为目的，而应以程序的安全实现为目的。提及这一点的原因是当具体实施时，我们还应该考虑别的因素，这些内容留在之后的算法实现中再详细说明。
? ? ? ? 现在我们来进行总结：1）循环结构的计数器应该为unsigned int类型，倒序递减计数并且循环中断条件应该设置为 i!=0而不是i>0；2)如果你确定循环至少会执行一次，那么就是用do-while循环替换for循环；3）对重要的循环体进行循环扩展，同时避免过度展开；4）尽量在工程实施之初就设置某些数组的长度为2，4或者8的倍数，方便以后进行扩展。
5. 除法
? ? ? ? ARM中并没有专门的除法指令，而是依靠调用C库来实现。C库提供的标准除法需要20到100个cycle，因此，我们如果可以使用偏移来完成某个除法操作，就绝不使用标准除法。当然，取余操作本（%）身也是很快的，它比乘法要快，比加法慢，但是，有一些操作还是能够被优化的。本小节，我们就来介绍如何使用乘法替代除法以及最小化除法调用次数，从而达到优化除法的效果。我们直接举例：
x = (x + y) % z; //x<z, y>=z ? ? ? ? 上面这段代码的场景是很常见，对于一个小于z的数x，现在要加上一个大于z的数y并对结果取余。它实际上可以被优化成以下代码：
想办法让 y<z, 然后执行
x += y;
if (x>=z)
{
x-= z;
}虽然第一段代码相当简洁，但实际上它需要几乎50个cycle，而第二段代码只需要几个cycle，这是相当大的提升。如果你没办法像上面的方法一样避免使用除法，那就尽可能的使用两个无符号数的除法，因为对于有符号数，编译器会先对操作数取绝对值再运算。
? ? ? ? 对于同时对相同分母进行除法和取余操作，如x = a/b, y = a%b。这是两个操作，但是在ARM中，这两个运算是同时进行的，因为c库中的除法操作本身会同时返回商和余数，此时我们不需要对除法或取余进行优化，当你尝试优化时反倒会使得效率降低。
? ? ? ? 接下来我们来分情况讨论几种具体的优化方法。
5.1 除法转换为乘法
? ? ? ? 如果你对结论的推导过程不感兴趣，可以直接跳转到本小节的末尾，查看黑体加粗的结论。
? ? ? ? 首先，对于a/b这样的除法运算（注意，a/b的意思是a除以b然后向下取整），我们往往可以预估b的逆然后在进行乘法运算，一个能较为准确的预估出b的逆大小的方法是计算。于是a/b可以转换为：
? ? ? ? ? 但是，如果我们使用上面的方法会产生两个问题：1）2的32次方的计算，unsigned int类型已经不再适用，我们需要long long类型；2）当b恰好是1时，2的32次方除以b也同样不再适合unsigned int类型。
? ? ? ? 上面的两个问题是这样解决的，并且在实际的工程实现中也是这么做的，我们估计b的逆的值用采用的是。而这个式子一定对于某个可以使用unsigned int类型定义的s满足：
上面的等式意味着我们使用s代替除以b向下取整的结果，即
。并且因为我们已知a和b，所以可以很轻松的计算得到(as)>>32。现在，我们将已知的(as)>>32记做 q 。
? ? ? ? ?由于 q 和之间本身会有一个差值，记为
。我们将其展开并替换掉公式中的 s ：
????????于是，我们得出结论，应该是a/b或者a/b-1这两个值中的某一个值与 q 相等。实际上，我们很容易就能找出是哪个值，只需要计算a-qb，然后判断结果是否大于d就行了。若小于d，则为前者，若大于等于d，为后者。有人或许有疑问，我的计算步骤中不是为了得到 s 使用了一次除法，何来将除法转换为乘法一说。那么现在，我将我们推理的成果用代码展示出来，如下 ：
/**
* @brief 除法
* @param [out] dest 计算结果的输出地址
* @param [in] src 被除数数组
* @param [in] d 除数
* @param [in] N 被除数的长度
*/
void scale(unsigned int *dest, unsigned int *src, unsigned int d, unsigned int N)
{
unsigned int s = 0xFFFFFFFFu / d;
do
{
unsigned int n, q, r;
n = *(src++);
q = (unsigned int)(((unsigned long long)n * s) >> 32);
r = n-q * d;
if (r >= d)
{
q++;
}
*(dest++) = q;
} while (--N);
}????????这里已经可以看到，我们通常考虑的是大数的除法，被除数可能是一个数组。对于上面的32-bit数据搭配循环体内的64-bit乘法，这样的运算快了很多，因为循环结构体中没有除法操作并且ARM中的64位乘法（UMULL指令）是相当快速的。不过要注意，在使用上面的方法时，如果你是16-bit数据那就搭配32-bit乘法计算q，如果是64-bit数据，那就搭配128-bit乘法计算q。s也可以与之对应选择更小的值。总之，选择当下适用且最小的尺寸就行了。
5.2?除数为常数的除法
????????5.1小节中我们讲了一种通用的除法?，但对于除数为常数的除法，还有更快的方法。
? ? ? ? 对于无符号除法：首先找到一个整数 k 满足，，并计算
，我们会得到
? ? ? ? 而对于有符号数除法（我们假设d是正数，因为d的符号完全可以放在运算之外去处理）：
? ? ? ? 我们给出上面优化方案对应的代码：首先找到一个整数 k 满足，，并计算
，最后，我们会得到
?
? ? ? ? ?这两中的情况在《ARM System Developer's Guide》的5.10.3和5.10.4章节中有相关证明，这里不进行赘述。下面我们直接给出这两种情况的代码实现：
unsigned int udiv_by_const(unsigned int a, unsigned int b)
{
unsigned int s,k,q;
/* We assume b!=0 */
/* first find k such that (1 << k) <= b < (1<<(k+1)) */
for (k=0; b/2>=(1u << k); k++);
if (b==1u << k)
{
/* we can implement the divide with a shift */
return a >> k;
}
/* b is in the range (1 << k) < b < (1<<(k+1)) */
s = (unsigned int)(((1ull << (32+k))+(1ull << k))/b);
if ((unsigned long long)s*b >= (1ull << (32+k)))
{
/* a/d = (a*s) >> (32+k) */
q = (unsigned int)(((unsigned long long)a*s) >> 32);
return q >> k;
}
/* a/b = (a*s+s) >> (32+k) */
q = (unsigned int)(((unsigned long long)a*s + s) >> 32);
return q >> k;
}? ? ? ? 上面的代码是第一种情况的实现代码，注意到 N 的值是32，因此这个方法是对32-bit无符号数的除法运算。下面给出有符号数的情况，它的 N 为31：
int sdiv_by_const(int a, int b)
{
int s,k,q;
unsigned int D;
/* set D to be the absolute value of b, we assume b!=0 */
if (d>0)
{
D=(unsigned int)d; /* 1 <= D <= 0x7FFFFFFF */
}
else
{
D=(unsigned int) - d; /* 1 <= D <= 0x80000000 */
}
/* first find k such that (1 << k) <= D < (1<<(k+1)) */
for (k=0; D/2>=(1u << k); k++);
if (D==1u << k)
{
/* we can implement the divide with a shift */
q = a >> 31; /* 0 if a>0, -1 if a<0 */
q = a + ((unsigned)q >> (32-k)); /* insert rounding */
q = q >> k; /* divide */
if (b < 0)
{
q = -q; /* correct sign */
}
return q;
}
/* Next find s in the range 0<=s<=0xFFFFFFFF */
/* Note that k here is one smaller than the k in the equation */
s = (int)(((1ull << (31+(k+1)))+(1ull << (k+1)))/D);
if (s>=0)
{
q = (int)(((signed long long)a*s) >> 32);
}
else
{
/* (unsigned)s = (signed)s + (1 << 32) */
q = a + (int)(((signed long long)a*s) >> 32);
}
q = q >> k;
/* if a<0 then the formula requires us to add one */
q += (unsigned)a >> 31;
/* if b was negative we must correct the sign */
if (b<0)
{
q = -q;
}
return q;
}? ? ? ? 同样的给出总结性的建议：1）尽量避免除法运算，特别是在循环体内；2）如果不能避免除法运算，将具有相同除数的求余操作和求商操作放在一起；3）尽可能的将除法转换为乘法；4）除以某个确定常数的除法，使用上面提及的快速算法。
最后
? ? ? ? 至此，一些重要的技巧和注意事项已经介绍完了，在之后的文章中，我们开始使用这些技巧来实现密码算法，但在实现这些算法前，我需要先完成大数运算，例如加法，乘法，模逆等运算的实现。在这些实现中，我会尝试开始提及如何实现安全的算法，以及讲解这么实现的原因。感谢您的阅览，再次，如果您发现了什么不足和错误的地方，欢迎随时与我沟通讨论。