码创造者

这个屌丝很懒，什么也没留下！

热门标签

ARM 上的C语言开发_arm的c语言

作者：码创造者 | 2024-06-25 07:02:55

踩

arm的c语言

说在前面

这篇文章会由浅入深，从工程实现角度出发，来一些如何写出优秀的基于ARM指令集的C程序的技巧。（参考资料是《ARM System Developer's Guide》）

在开始读这篇文章前，我假设读者对ARM的一些基本汇编指令已经有所了解。接下来，我会从变量类型，有无符号类型，如何写好一个循环体等方面展开介绍。

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 check(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的逆大小的方法是计算 $2^{32}/b$ 。于是a/b可以转换为：

$\left ( a\left ( 2^{32}/b \right ) \right )/2^{32}$

但是，如果我们使用上面的方法会产生两个问题：1）2的32次方的计算，unsigned int类型已经不再适用，我们需要long long类型；2）当b恰好是1时，2的32次方除以b也同样不再适合unsigned int类型。

上面的两个问题是这样解决的，并且在实际的工程实现中也是这么做的，我们估计b的逆的值用采用的是 $\left ( 2^{32} - 1 \right )/b$ 。而这个式子一定对于某个可以使用unsigned int类型定义的s满足：

$\\2^{32} - 1 = sb + t, 0\leqslant t< d \\ \\\Rightarrow s = \frac{2^{32}}{b} - \frac{1+t}{b}, 0< \frac{1+t}{b} = \epsilon \leqslant 1$

上面的等式意味着我们使用s代替 $2^{32} - 1$ 除以b向下取整的结果，即 $s = (2^{32} - 1)/b$ 。并且因为我们已知a和b，所以可以很轻松的计算得到(as)>>32。现在，我们将已知的(as)>>32记做 q 。

由于 q 和 $as2^{-32}$ 之间本身会有一个差值，记为 $\varepsilon$ 。我们将其展开并替换掉公式中的 s ：

$\\q = \frac{a}{b} - a\epsilon 2^{-32} - \varepsilon, \\ \\ 0\leq a\epsilon 2^{-32} + \varepsilon < \epsilon + \varepsilon <2, \\ \\ \Rightarrow a/b-2 < q \leqslant a/b$

于是，我们得出结论，应该是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 满足， $2^{k}< b\leqslant 2^{k+1}$ ，并计算 $s = \left ( 2^{N+k}+2^{k} \right )/b$ ，我们会得到

$\\ a/b = (bs\geq 2^{N+k} ) \ ? \ ((as) >> (N + k)): ((as+s) >> (N + k))$

而对于有符号数除法（我们假设d是正数，因为d的符号完全可以放在运算之外去处理）：首先找到一个整数 k 满足， $2^{k-1}\leq b< 2^{k}$ ，并计算 $s = \left ( 2^{N+k}+2^{k} \right )/b$ ，最后，我们会得到

$\\ a/b = (a\geq 0 ) \ ? \ ((as) >> (N + k)): ((as+s) >> (N + k))+1$

这两中的情况在《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）除以某个确定常数的除法，使用上面提及的快速算法。

最后

至此，一些重要的技巧和注意事项已经介绍完了，在之后的文章中，我们开始使用这些技巧来实现密码算法，但在实现这些算法前，我需要先完成大数运算，例如加法，乘法，模逆等运算的实现。在这些实现中，我会尝试开始提及如何实现安全的算法，以及讲解这么实现的原因。感谢您的阅览，再次，如果您发现了什么不足和错误的地方，欢迎随时与我沟通讨论。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/755440