1

I writing a fast "8 bit reverse"-routine for an avr-project with an ATmega2560 processor. I'm using

  • GNU C (WinAVR 20100110) version 4.3.3 (avr) / compiled by GNU C version 3.4.5 (mingw-vista special r3), GMP version 4.2.3, MPFR version 2.4.1.

First I created a global lookup-table of reversed bytes (size: 0x100):

uint8_t BitReverseTable[]
        __attribute__((__progmem__, aligned(0x100))) = {
    0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,
    0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
    [...]
    0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF
};

This works as expected. That is the macro I intend to use, which should cost me only 5 cylces:

#define BITREVERSE(x) (__extension__({                                        \
    register uint8_t b=(uint8_t)x;                                            \
    __asm__ __volatile__ (                                                    \
        "ldi r31, hi8(table)"                                          "\n\t" \
        "mov r30, ioRegister"                                          "\n\t" \
        "lpm ioRegister, z"                                            "\n\t" \
        :[ioRegister] "+r" (b)                                                \
        :[table] "g" (BitReverseTable)                                        \
        :"r30", "r31"                                                         \
    );                                                                        \
}))

The code to get it compiled (or not).

int main() /// Test for bitreverse
{
    BITREVERSE(25);
    return 0;
}

That's the error I get from the compiler:

c:/winavr-20100110/bin/../lib/gcc/avr/4.3.3/../../../../avr/bin/as.exe -mmcu=atmega2560 -o bitreverse.o C:\Users\xxx\AppData\Local\Temp/ccCefE75.s
C:\Users\xxx\AppData\Local\Temp/ccCefE75.s: Assembler messages:
C:\Users\xxx\AppData\Local\Temp/ccCefE75.s:349: Error: constant value required
C:\Users\xxx\AppData\Local\Temp/ccCefE75.s:350: Error: constant value required

I guess the problem is here:

    :[table] "g" (BitReverseTable)                                        \

From my point of view BitReverseTable is the memory position of the array, which is fixed and known at compile time. Therefor it is constant. Maybe I need to cast BitReverseTable into something (i tried anything I could think of). Maybe I need another constraint ("g" was my last test). I'm sure I used anything possible and impossible. I coded an assembler version, which works fine, but instead of being an inline assembly code, this is a proper function which adds another 6 cycles (for call and ret).

Any advice or suggestions are very welcome!

Full source of bitreverse.c on pastebin. Verbose compiler output also on pastebin

4

1 回答 1

1

以下似乎确实适用于 avr-gcc (GCC) 4.8.2，但它确实对我有明显的 hacky 回味。

编辑以解决 OP (Thomas) 在评论中指出的问题：

  • Z寄存器的高字节是r31（我有r30并r31交换过）
  • 较新的 AVR 也支持 ATmega2560 lpm r,Z（仅限较旧的 AVR lpm r0,Z）

感谢您的修复，托马斯！我确实有一块 ATmega2560 板，但我更喜欢 Teensies（部分是因为原生 USB），所以我只编译测试了代码，没有运行它来验证。我应该提到这一点；道歉。

const unsigned char reverse_bits_table[256] __attribute__((progmem, aligned (256))) = {
      0, 128,  64, 192,  32, 160,  96, 224,  16, 144,  80, 208,  48, 176, 112, 240,
      8, 136,  72, 200,  40, 168, 104, 232,  24, 152,  88, 216,  56, 184, 120, 248,
      4, 132,  68, 196,  36, 164, 100, 228,  20, 148,  84, 212,  52, 180, 116, 244,
     12, 140,  76, 204,  44, 172, 108, 236,  28, 156,  92, 220,  60, 188, 124, 252,
      2, 130,  66, 194,  34, 162,  98, 226,  18, 146,  82, 210,  50, 178, 114, 242,
     10, 138,  74, 202,  42, 170, 106, 234,  26, 154,  90, 218,  58, 186, 122, 250,
      6, 134,  70, 198,  38, 166, 102, 230,  22, 150,  86, 214,  54, 182, 118, 246,
     14, 142,  78, 206,  46, 174, 110, 238,  30, 158,  94, 222,  62, 190, 126, 254,
      1, 129,  65, 193,  33, 161,  97, 225,  17, 145,  81, 209,  49, 177, 113, 241,
      9, 137,  73, 201,  41, 169, 105, 233,  25, 153,  89, 217,  57, 185, 121, 249,
      5, 133,  69, 197,  37, 165, 101, 229,  21, 149,  85, 213,  53, 181, 117, 245,
     13, 141,  77, 205,  45, 173, 109, 237,  29, 157,  93, 221,  61, 189, 125, 253,
      3, 131,  67, 195,  35, 163,  99, 227,  19, 147,  83, 211,  51, 179, 115, 243,
     11, 139,  75, 203,  43, 171, 107, 235,  27, 155,  91, 219,  59, 187, 123, 251,
      7, 135,  71, 199,  39, 167, 103, 231,  23, 151,  87, 215,  55, 183, 119, 247,
     15, 143,  79, 207,  47, 175, 111, 239,  31, 159,  95, 223,  63, 191, 127, 255,
};

#define USING_REVERSE_BITS \
    register unsigned char r31 asm("r31"); \
    asm volatile ( "ldi r31,hi8(reverse_bits_table)\n\t" : [r31] "=d" (r31) )

#define REVERSE_BITS(v) \
    ({ register unsigned char r30 asm("r30") = v; \
       register unsigned char ret; \
       asm volatile ( "lpm %[ret],Z\n\t" : [ret] "=r" (ret) : [r30] "d" (r30), [r31] "d" (r31) ); \
       ret; })

unsigned char reverse_bits(const unsigned char value)
{
    USING_REVERSE_BITS;
    return REVERSE_BITS(value);
}

void reverse_bits_in(unsigned char *string, unsigned char length)
{
    USING_REVERSE_BITS;

    while (length-->0) {
        *string = REVERSE_BITS(*string);
        string++;
    }
}

对于仅支持的旧 AVR lpm r0,Z，请使用

#define REVERSE_BITS(v) \
    ({ register unsigned char r30 asm("r30") = v; \
       register unsigned char ret asm("r0"); \
       asm volatile ( "lpm %[ret],Z\n\t" : [ret] "=t" (ret) : [r30] "d" (r30), [r31] "d" (r31) ); \
       ret; })

这个想法是我们使用本地 reg var r31来保留Z寄存器对的高字节。宏在USING_REVERSE_BITS;当前范围内定义它，使用内联汇编有两个目的：避免将表地址的低部分不必要地加载到寄存器中，并确保 GCC 知道我们已经在其中存储了一个值（因为它是一个输出操作数），而没有任何方式知道该值应该是什么，因此希望在整个范围内保留它。

宏产生结果REVERSE_BITS()，告诉编译器它需要 register 中的参数，以及inr30设置的表地址高字节。USING_REVERSE_BITS;r31

听起来有点复杂，但那只是因为我不知道如何更好地解释它。这真的很简单。

编译上面avr-gcc-4.8.2 -O2 -fomit-frame-pointer -mmcu=atmega2560 -S的代码会产生汇编源代码。（我确实建议使用-O2 -fomit-frame-pointer。）省略注释和正常指令：

    .text

reverse_bits:
    ldi r31,hi8(reverse_bits_table)
    mov r30,r24
    lpm r24,Z
    ret

reverse_bits_in:
    mov r26,r24
    mov r27,r25
    ldi r31,hi8(reverse_bits_table)
    ldi r24,lo8(-1)
    add r24,r22
    tst r22
    breq .L2
.L8:
    ld r30,X
    lpm r30,Z
    st X+,r30
    subi r24,1
    brcc .L8
.L2:
    ret

    .section    .progmem.data,"a",@progbits
    .p2align    8
reverse_bits_table:
    .byte    0
    .byte    -128
    ; Rest of data omitted for brevity

如果您想知道，在 ATmega2560 上，GCC 将第一个 8 位参数和 8 位函数结果都放在 register 中r24。

据我所知，第一个功能是最佳的。（在仅支持 的旧 AVR 上lpm r0,Z，您可以将结果从 复制r0到r24。）

对于第二个函数，设置部分可能不是完全最佳的（对于一个，你可以做tst r22 breq .L2第一件事来加速零长度数组检查），但我不确定我是否可以写一个更快/更短的我; 我当然可以接受。

第二个函数中的循环对我来说是最优的。它的使用方式一开始r30我觉得奇怪和可怕，但后来我意识到它非常有意义——使用的寄存器更少，并且重用r30这种方式没有害处（即使它也是Z寄存器的低部分），因为它会从string下一次迭代开始时加载一个新值。

请注意，在我之前的编辑中，我提到交换函数参数的顺序会产生更好的代码，但随着 Thomas 的添加，情况不再如此。寄存器变了，就是这样。

如果您确定始终提供大于零的值length，请使用

void reverse_bits_in(unsigned char *string, unsigned char length)
{
    USING_REVERSE_BITS;
    do {
        *string = REVERSE_BITS(*string);
        string++;
    } while (--length);
}

产量

reverse_bits_in:
    mov r26,r24                      ; 1 cycle
    mov r27,r25                      ; 1 cycle
    ldi r31,hi8(reverse_bits_table)  ; 2 cycles
.L4:
    ld r30,X                         ; 2 cycles
    lpm r30,Z                        ; 3 cycles
    st X+,r30                        ; 2 cycles
    subi r22,lo8(-(-1))              ; 1 cycle
    brne .L4                         ; 2 cycles
    ret                              ; 4 cycles

这开始让我印象深刻：每个字节十个周期，四个周期用于设置，三个周期清理（brne如果没有跳转只需要一个周期）。我在脑海中列出了循环计数，因此它们中可能存在小错误（这里或那里的循环）。r26:r27是X，函数的第一个指针参数在 中提供r24:r25，长度在 中r22。

位于reverse_bits_table正确的部分，并且正确对齐。（.p2align 8确实对齐到 256 个字节；它指定了低 8 位为零的对齐方式。）

尽管 GCC 因多余的寄存器移动而臭名昭著，但我真的很喜欢它上面生成的代码。当然，总是有技巧的空间。对于重要的代码序列，我建议尝试不同的变体，甚至更改函数参数的顺序（或在本地范围内声明循环变量）等等，然后编译使用-S以查看生成的代码。AVR指令时序很简单，因此很容易比较代码序列，看看是否明显更好。我喜欢先删除指令和评论；它使阅读程序集更容易。

hacky 回味的原因是GCC 文档明确指出“定义这样的寄存器变量不会保留寄存器；它仍然可用于流控制确定变量值不存在的地方的其他用途”，我只是不不要相信这对 GCC 开发人员的意义与对我的意义相同。即使现在这样做了，将来也可能不会；这里没有标准的 GCC 开发人员应该遵守，因为这是 GCC 特有的特性。

另一方面，我只依赖于上面记录的 GCC 行为，虽然“hacky”，但它确实从简单的 C 代码生成有效的汇编。

就个人而言，我建议在更新 avr-gcc 时重新编译上述测试代码，并查看生成的程序集（也许使用 sed 去除注释和标签，并与已知的好版本进行比较？）。

问题？

于 2014-09-05T18:21:57.707 回答