Re: [avr-gcc-list] [avr-libc]: Smarter parity implementation

[Paulo Marques]

Georg-Johann Lay wrote:
> The current implementation of parity in avr-libc compiles
> 
> #include <stdint.h>
> #include <util/parity.h>
> 
> uint8_t pari1 (uint8_t val)
> {
>     return parity_even_bit (val);
> }
> 
> with -Os to
> 
> pari1:
> /* #APP */
>     mov __tmp_reg__,r24
>     swap r24
>     eor r24,__tmp_reg__
>     mov __tmp_reg__,r24
>     lsr r24
>     lsr r24
>     eor r24,__tmp_reg__
> /* #NOAPP */
>     ldi r25,lo8(0)
>     adiw r24,1
>     asr r25
>     ror r24
>     andi r24,lo8(1)
>     ret
> 
> which are 12 instructions, 13 ticks and 2 regs.
> 
> Parity can be implemented with 9 instructions
> and 9 ticks and one reg. Instead of r24 any d-reg
> can be used:
> 
> ;; r24 = parity8 (r24)
> ;; clobbers: __tmp_reg__
> parity8:
>     ;; parity is in r24[0..7]
>     mov  __tmp_reg__, r24
>     swap __tmp_reg__
>     eor  r24, __tmp_reg__
>     ;; parity is in r24[0..3]
>     subi r24, -4
>     andi r24, -5
>     subi r24, -6
>     ;; parity is in r24[0,3]
>     sbrc r24, 3
>     inc  r24
>     ;; parity is in r24[0]
>     andi r24, 1
> 
> An implementation similar to the original avr-libc
> using one instruction/tick more is
> 
>     mov __tmp_reg__,r24
>     swap r24
>     eor r24,__tmp_reg__
>     mov __tmp_reg__,r24
>     lsr r24
>     lsr r24
>     eor r24,__tmp_reg__
>     lsr r24
>     sbci r24,0
>     andi r24,1

IIRC you're required to clear r25 even if the return type is uint8_t,
i.e., the return type needs to be upgraded to "int".

I think this happens because, since most expressions are upgraded to int
anyway, it is cheaper to do it in one place than in all call sites.

-- 
Paulo Marques
Software Development Department - Grupo PIE, S.A.
Phone: +351 252 290600, Fax: +351 252 290601
Web: www.grupopie.com

"Very funny Scotty. Now beam up my clothes."