迭代与。将整数打印到字符的递归 LCD/OLED 显示

Iteration Vs. Recursion for Printing Integer Numbers to a Character LCD/OLED Display

问题

我正在寻找一些关于如何优化打印整数数字的输入,比如 uint32_t num = 1234567890;,使用 Arduino UNO 进行字符显示。 要考虑的主要指标是内存使用情况和合规大小。显示速度太慢,速度上的任何改进都没有意义,最小代码长度虽然不错,但不是必需的。

目前,我正在使用 num%10 提取最低有效数字,然后通过 num/10 删除该数字,依此类推,直到提取出 num 的所有数字。使用递归,我可以反转打印顺序,因此只需很少的操作(作为显式代码行)即可按正确顺序打印数字。使用 for 循环,我需要找到用于写入数字的字符数,然后存储它们,然后才能以正确的顺序打印它们,需要一个数组和 3 个 for 循环。

根据 Arduino IDE,当打印各种有符号和无符号整数时,递归使用 2010/33 字节的 storage/memory,而迭代当使用扩展 class [=23= 的 Adafruit_CharacterOLED 库时,使用 2200/33 字节而不是 2474/52 字节].

有没有比我在下面使用递归和迭代编写的函数更好地实现它的方法?如果不是,您更喜欢哪个,为什么? 我觉得可能有更好的方法用更少的资源来做到这一点——但也许我是唐吉诃德与风车搏斗,代码已经足够好了。

背景

我正在使用 NHD-0420DZW 字符 OLED 显示器,并使用 Newhaven 数据表和 LiquidCrystal 库作为编写我自己的库的指南,显示器运行良好。然而,为了尽量减少代码膨胀,我选择不让我的显示库成为 Print 的子 class,它是 Arduino 核心库的一部分。这样做,已经实现了存储 space(~400 字节)和内存(~19 字节)的显着节省(ATmega328P 具有 32k 存储和 2k RAM,因此资源稀缺)。


递归

如果我使用递归,打印方法相当优雅。该数字除以 10,直到达到零的基本情况。然后打印最小数字的最低有效位(MSD of num),以及下一个最小数字的LSD(second MSD of num)等等,导致最终打印顺序颠倒。这纠正了使用 %10/10 操作的相反顺序的数字提取。

// print integer type literals to display (base-10 representation) 
void NewhavenDZW::print(int8_t num) {print(static_cast<int32_t>(num));}
void NewhavenDZW::print(uint8_t num) {print(static_cast<uint32_t>(num));}
void NewhavenDZW::print(int16_t num) {print(static_cast<int32_t>(num));}
void NewhavenDZW::print(uint16_t num) {print(static_cast<uint32_t>(num));}
void NewhavenDZW::print(int32_t num) {
    if(num < 0) {         // print negative sign if present
        send('-', HIGH);  // and make num positive
        print(static_cast<uint32_t>(-num));
    } else
        print(static_cast<uint32_t>(num));
}
void NewhavenDZW::print(uint32_t num) {
    if(num < 10) {  // print single digit numbers directly
        send(num + '0', HIGH);
        return;
    } else                    // use recursion to print nums with more
        recursivePrint(num);  // than two digits in the correct order
}
// recursive method for printing a number "backwards"
// used to correct the reversed order of digit extraction
void NewhavenDZW::recursivePrint(uint32_t num) {
    if(num) {  // true if num>0, false if num==0
        recursivePrint(num/10);    // maximum of 11 recursive steps
        send(num%10 + '0', HIGH);  // for a 10 digit number
    }
}

迭代

由于数字提取方法从 LSD 开始,而不是 MSD,提取的数字不能直接打印,除非我移动光标并告诉显示器从右到左打印。所以我必须在提取数字时存储它们,然后才能以正确的顺序将它们写入显示器。

void NewhavenDZW::print(uint32_t num) {
    if(num < 10) {
        send(num + '0', HIGH);
        return;
    }
    uint8_t length = 0;
    for(uint32_t i=num; i>0; i/=10)  // determine number of characters 
        ++length;                    // needed to represent number
    char text[length];
    for(uint8_t i=length; num>0; num/=10, --i)
        text[i-1] = num%10 + '0';    // map each numerical digit to 
    for(uint8_t i=0; i<length; i++)  // its char value and fix ordering
        send(text[i], HIGH);         // before printing result
}

更新

最终,递归占用的存储空间最少 space,但可能使用的内存最多。

在查看了 Igor G 和 darune 友情提供的代码,以及查看了 godbolt 上列出的指令数量后(正如 darune 和 old_timer 所讨论的)我相信 Igor G 的解决方案总体上是最好的。对于 darune 的函数,它编译为 2076 字节与 2096 字节(使用 if 语句停止前导零并能够打印0) 在测试期间。当添加必要的 if 语句时,它还需要比 darune 的 (273) 更少的指令 (88)。

使用指针变量

void NewhavenDZW::print(uint32_t num) {
    char buffer[10];
    char* p = buffer;
    do {
        *p++ = num%10 + '0';
        num /= 10;
    } while (num);
    while (p != buffer)
        send(*--p, HIGH);
}

使用索引变量

这就是我原来的 for 循环试图做的事情,但是是以一种天真的方式。正如 Igor G 指出的那样,尝试最小化缓冲区数组的大小确实没有意义。

void NewhavenDZW::print(uint32_t num) {
    char text[10];  // signed/unsigned 32-bit ints are <= 10 digits
    uint8_t i = sizeof(text) - 1;  // set index to end of char array
    do {
        text[i--] = num%10 + '0';  // store each numerical digit as 
        num /= 10;                 // its associated char value
    } while (num);
    while (i < sizeof(text))
        send(text[i++], HIGH);     // print num in the correct order
}

另类

这里是添加了 if 语句的 darune 函数,供那些不想浏览评论的人使用。条件 pow10 == 100pow10 == 1 相同,但在具有相同编译大小的同时保存了两次循环迭代以打印零。

void NewhavenDZW::print(uint32_t num) {
    for (uint32_t pow10 = 1000000000; pow10 != 0; pow10 /= 10)
        if (num >= pow10 || (num == 0 && pow10 == 100))
            send((num/pow10)%10 + '0', HIGH);
}

试试这个。我的avr-gcc-5.4.0 + readelf告诉函数体只有138字节。

void Send(uint8_t);

void OptimizedPrintf(uint32_t val)
{
    uint8_t         buffer[sizeof(val) * CHAR_BIT / 3 + 1];
    uint8_t*        p = buffer;
    do
    {
        *p++ = (val % 10) + '0';
        val /= 10;
    } while (val);
    while (p != buffer)
        Send(*--p);
}

对于较小的占用空间,您可以使用类似这样的东西:

void Send(unsigned char);

void SmallPrintf(unsigned long val)
{
    static_assert(sizeof(decltype(val)) == 4, "expected '10 digit type'");
   for (unsigned long digit_pow10{1000000000}; digit_pow10 != 0; digit_pow10 /= 10)
    {
        Send((val / digit_pow10 % 10) + '0');
    }
}

这会产生大约 70 条指令 - 比使用缓冲区并在之后迭代缓冲区少大约 14 条指令。 (而且代码也简单很多)

Link 到 godbolt.

如果不需要前导零,那么 if 子句可以避免这种相当简单的情况 - 类似于:

    if (val >= digit_pow10) {
        Send((val / digit_pow10 % 10) + '0');
    }

但是它会花费一些额外的指令 (~9) - 但是总数仍然低于缓冲示例。

有趣的实验。

unsigned long fun ( unsigned long x )
{
    return(x/10);
}
unsigned long fun2 ( unsigned long x )
{
    return(x%10);
}
int main ( void )
{
   return(0);
}

does/can 提供 apt-got 工具链:

00000000 <fun>:
   0:   2a e0           ldi r18, 0x0A   ; 10
   2:   30 e0           ldi r19, 0x00   ; 0
   4:   40 e0           ldi r20, 0x00   ; 0
   6:   50 e0           ldi r21, 0x00   ; 0
   8:   0e d0           rcall   .+28        ; 0x26 <__udivmodsi4>
   a:   95 2f           mov r25, r21
   c:   84 2f           mov r24, r20
   e:   73 2f           mov r23, r19
  10:   62 2f           mov r22, r18
  12:   08 95           ret

00000014 <fun2>:
  14:   2a e0           ldi r18, 0x0A   ; 10
  16:   30 e0           ldi r19, 0x00   ; 0
  18:   40 e0           ldi r20, 0x00   ; 0
  1a:   50 e0           ldi r21, 0x00   ; 0
  1c:   04 d0           rcall   .+8         ; 0x26 <__udivmodsi4>
  1e:   08 95           ret

00000020 <main>:
  20:   80 e0           ldi r24, 0x00   ; 0
  22:   90 e0           ldi r25, 0x00   ; 0
  24:   08 95           ret

00000026 <__udivmodsi4>:
  26:   a1 e2           ldi r26, 0x21   ; 33
  28:   1a 2e           mov r1, r26
  2a:   aa 1b           sub r26, r26
  2c:   bb 1b           sub r27, r27
  2e:   ea 2f           mov r30, r26
  30:   fb 2f           mov r31, r27
  32:   0d c0           rjmp    .+26        ; 0x4e <__udivmodsi4_ep>

00000034 <__udivmodsi4_loop>:
  34:   aa 1f           adc r26, r26
  36:   bb 1f           adc r27, r27
  38:   ee 1f           adc r30, r30
  3a:   ff 1f           adc r31, r31
  3c:   a2 17           cp  r26, r18
  3e:   b3 07           cpc r27, r19
  40:   e4 07           cpc r30, r20
  42:   f5 07           cpc r31, r21
  44:   20 f0           brcs    .+8         ; 0x4e <__udivmodsi4_ep>
  46:   a2 1b           sub r26, r18
  48:   b3 0b           sbc r27, r19
  4a:   e4 0b           sbc r30, r20
  4c:   f5 0b           sbc r31, r21

0000004e <__udivmodsi4_ep>:
  4e:   66 1f           adc r22, r22
  50:   77 1f           adc r23, r23
  52:   88 1f           adc r24, r24
  54:   99 1f           adc r25, r25
  56:   1a 94           dec r1
  58:   69 f7           brne    .-38        ; 0x34 <__udivmodsi4_loop>
  5a:   60 95           com r22
  5c:   70 95           com r23
  5e:   80 95           com r24
  60:   90 95           com r25
  62:   26 2f           mov r18, r22
  64:   37 2f           mov r19, r23
  66:   48 2f           mov r20, r24
  68:   59 2f           mov r21, r25
  6a:   6a 2f           mov r22, r26
  6c:   7b 2f           mov r23, r27
  6e:   8e 2f           mov r24, r30
  70:   9f 2f           mov r25, r31
  72:   08 95           ret

回答了我的一个问题,除法函数的78个指令。此外,它 returns 分子和分母都在一个调用中,如果绝望,可以利用它。

unsigned int fun ( unsigned int x )
{
    return(x/10);
}
unsigned int fun2 ( unsigned int x )
{
    return(x%10);
}
int main ( void )
{
   return(0);
}

给予

00000000 <fun>:
   0:   6a e0           ldi r22, 0x0A   ; 10
   2:   70 e0           ldi r23, 0x00   ; 0
   4:   0a d0           rcall   .+20        ; 0x1a <__udivmodhi4>
   6:   86 2f           mov r24, r22
   8:   97 2f           mov r25, r23
   a:   08 95           ret

0000000c <fun2>:
   c:   6a e0           ldi r22, 0x0A   ; 10
   e:   70 e0           ldi r23, 0x00   ; 0
  10:   04 d0           rcall   .+8         ; 0x1a <__udivmodhi4>
  12:   08 95           ret

00000014 <main>:
  14:   80 e0           ldi r24, 0x00   ; 0
  16:   90 e0           ldi r25, 0x00   ; 0
  18:   08 95           ret

0000001a <__udivmodhi4>:
  1a:   aa 1b           sub r26, r26
  1c:   bb 1b           sub r27, r27
  1e:   51 e1           ldi r21, 0x11   ; 17
  20:   07 c0           rjmp    .+14        ; 0x30 <__udivmodhi4_ep>

00000022 <__udivmodhi4_loop>:
  22:   aa 1f           adc r26, r26
  24:   bb 1f           adc r27, r27
  26:   a6 17           cp  r26, r22
  28:   b7 07           cpc r27, r23
  2a:   10 f0           brcs    .+4         ; 0x30 <__udivmodhi4_ep>
  2c:   a6 1b           sub r26, r22
  2e:   b7 0b           sbc r27, r23

00000030 <__udivmodhi4_ep>:
  30:   88 1f           adc r24, r24
  32:   99 1f           adc r25, r25
  34:   5a 95           dec r21
  36:   a9 f7           brne    .-22        ; 0x22 <__udivmodhi4_loop>
  38:   80 95           com r24
  3a:   90 95           com r25
  3c:   68 2f           mov r22, r24
  3e:   79 2f           mov r23, r25
  40:   8a 2f           mov r24, r26
  42:   9b 2f           mov r25, r27
  44:   08 95           ret

22 行,44 个字节用于划分。也很有趣。可能在 C++ 级别被利用来保存 space(如果此显示循环是您执行 divide/modulo 的唯一位置)。

优化器当然知道库函数会同时计算结果和余数:

unsigned long fun ( unsigned long x )
{
    unsigned long res;
    unsigned long rem;

    res=x/10;
    rem=x&10;

    res&=0xFFFF;
    rem&=0xFFFF;
    return((res<<16)|rem);
}
int main ( void )
{
   return(0);
}


00000000 <fun>:
   0:   cf 92           push    r12
   2:   df 92           push    r13
   4:   ef 92           push    r14
   6:   ff 92           push    r15
   8:   c6 2e           mov r12, r22
   a:   d7 2e           mov r13, r23
   c:   e8 2e           mov r14, r24
   e:   f9 2e           mov r15, r25
  10:   2a e0           ldi r18, 0x0A   ; 10
  12:   30 e0           ldi r19, 0x00   ; 0
  14:   40 e0           ldi r20, 0x00   ; 0
  16:   50 e0           ldi r21, 0x00   ; 0
  18:   19 d0           rcall   .+50        ; 0x4c <__udivmodsi4>
  1a:   a2 2f           mov r26, r18
  1c:   b3 2f           mov r27, r19
  1e:   99 27           eor r25, r25
  20:   88 27           eor r24, r24
  22:   2a e0           ldi r18, 0x0A   ; 10
  24:   c2 22           and r12, r18
  26:   dd 24           eor r13, r13
  28:   ee 24           eor r14, r14
  2a:   ff 24           eor r15, r15
  2c:   68 2f           mov r22, r24
  2e:   79 2f           mov r23, r25
  30:   8a 2f           mov r24, r26
  32:   9b 2f           mov r25, r27
  34:   6c 29           or  r22, r12
  36:   7d 29           or  r23, r13
  38:   8e 29           or  r24, r14
  3a:   9f 29           or  r25, r15
  3c:   ff 90           pop r15
  3e:   ef 90           pop r14
  40:   df 90           pop r13
  42:   cf 90           pop r12
  44:   08 95           ret

00000046 <main>:
  46:   80 e0           ldi r24, 0x00   ; 0
  48:   90 e0           ldi r25, 0x00   ; 0
  4a:   08 95           ret

0000004c <__udivmodsi4>:
  4c:   a1 e2           ldi r26, 0x21   ; 33
  4e:   1a 2e           mov r1, r26
  50:   aa 1b           sub r26, r26
  52:   bb 1b           sub r27, r27
  54:   ea 2f           mov r30, r26
  56:   fb 2f           mov r31, r27
  58:   0d c0           rjmp    .+26        ; 0x74 <__udivmodsi4_ep>

0000005a <__udivmodsi4_loop>:
  5a:   aa 1f           adc r26, r26
  5c:   bb 1f           adc r27, r27
  5e:   ee 1f           adc r30, r30
  60:   ff 1f           adc r31, r31
  62:   a2 17           cp  r26, r18
  64:   b3 07           cpc r27, r19
  66:   e4 07           cpc r30, r20
  68:   f5 07           cpc r31, r21
  6a:   20 f0           brcs    .+8         ; 0x74 <__udivmodsi4_ep>
  6c:   a2 1b           sub r26, r18
  6e:   b3 0b           sbc r27, r19
  70:   e4 0b           sbc r30, r20
  72:   f5 0b           sbc r31, r21

00000074 <__udivmodsi4_ep>:
  74:   66 1f           adc r22, r22
  76:   77 1f           adc r23, r23
  78:   88 1f           adc r24, r24
  7a:   99 1f           adc r25, r25
  7c:   1a 94           dec r1
  7e:   69 f7           brne    .-38        ; 0x5a <__udivmodsi4_loop>
  80:   60 95           com r22
  82:   70 95           com r23
  84:   80 95           com r24
  86:   90 95           com r25
  88:   26 2f           mov r18, r22
  8a:   37 2f           mov r19, r23
  8c:   48 2f           mov r20, r24
  8e:   59 2f           mov r21, r25
  90:   6a 2f           mov r22, r26
  92:   7b 2f           mov r23, r27
  94:   8e 2f           mov r24, r30
  96:   9f 2f           mov r25, r31
  98:   08 95           ret

抱歉使用这个 space 来享受这个练习,看看编译器如何处理这个问题。尝试使用 16 位除法开始爆炸寄存器使用,烧毁保存的 34 条指令。

由于分母是固定的,而且这是一个 8 位处理器,您可以使用编译器玩优化游戏,但您可能会沿着一条不可读的路径走下去。

仍然很确定这可以在不使用除法库函数的情况下完成得更紧密,并且知道这是一个 AVR。虽然移位很残酷,很多寄存器,但一旦溢出,函数的大小也会爆炸。很细腻。

您可以用一个 uno 的价格购买一把蓝色药丸,里面的东西更多,包括 32 位寄存器和将除以 10 变成几条指令的乘法。仍然可以使用 arduino 沙箱,并且运行速度更快。 (更多闪存,更多内存,编译器友好的指令集,可能不再需要计算字节数,应该尝试为该目标编译您的项目并查看使用了多少闪存)。