Electronics & Programming

develissimo

Open Source electronics development and programming

  • You are not logged in.
  • Root
  • » AVR-GCC
  • » [avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ? [RSS Feed]

#1 Nov. 4, 2005 05:37:18

Vincent T.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


Hello list,

I just ran into a weird problem that I hardly expected.
I wrote a trivial routine that takes a 32bit unsigned int, which holds a
memory address, and shifts the lower 19 bits, out to a port pin (this
feeds cascaded shift registers, that in turn drive the 19 address lines
of a memory chip).
The 19th/MSbit is shifted first, so this is the bit I actually test.
But when I timed the routine, I discovered with much surprise and
horror, that instead of being very quick, it's massively slow to
execute ! About 3ms/3,000 cycles ! This makes it useless in the case at
hand sadly.
I looked at the disassembler output and discovered that instead of
testing directly the required (19th) bit of the address/integer, it
shifted the number 18 times to bring said bit on the far right, and then
only, test it.
So the routine takes about 20 times more time to execute than it should,
hence the 3ms horror figure I measured :-/
I tried various optimisation flags (-O, -Os, -O3) but all of them use
the same method, none of them manages to test the bit directly/quickly.
Looking at the AVR instruction set, there exist instructions by the
names of SBRC and SBRS, which should be able to test whatever bit in a
register, which is what is needed here: test the third bit of the third
byte of this 4 byte integer.

How should I re-word my bit test statement/expression, to cause the
compiler to use these lovely SBRS/C instructions at last ?



Regards,


--
Vince, puzzled...


static void log_address_set( uint32_t address )
{
...
...
if (address & 0x00040000)
PORTB |= LOG_SDA;
else
PORTB &= ~LOG_SDA;
...
}


static void log_address_set( uint32_t address )
{
...
...
if (address & 0x00040000)
24ec: da 01 movw r26, r20
24ee: c9 01 movw r24, r18
24f0: 72 e1 ldi r23, 0x12 ; 18
24f2: b6 95 lsr r27
24f4: a7 95 ror r26
24f6: 97 95 ror r25
24f8: 87 95 ror r24
24fa: 7a 95 dec r23
24fc: d1 f7 brne .-12 ; 0x24f2
24fe: 81 70 andi r24, 0x01 ; 1
2500: 90 70 andi r25, 0x00 ; 0
2502: 89 2b or r24, r25
2504: 11 f0 breq .+4 ; 0x250a
PORTB |= LOG_SDA;
2506: c0 9a sbi 0x18, 0 ; 24
2508: 01 c0 rjmp .+2 ; 0x250c
else
PORTB &= ~LOG_SDA;
250a: c0 98 cbi 0x18, 0 ; 24




_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#2 Nov. 4, 2005 06:11:15

Vincent T.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


> How should I re-word my bit test statement/expression, to cause the
> compiler to use these lovely SBRS/C instructions at last ?

Sorry for the noise :-/
Why is it always AFTER I hit the 'send' button, that I suddenly get the
bright idea that stops me pulling my hair ??

I replaced the '&' operator with the more appropriate '&&' one.... works
much better... 5 instructions instead of 115 (3 + 6*18 + 4) for the
previous code.
So that's indeed about 20 times faster. Although I still don't get why
it can't just use one single SBRC/S instruction instead of these 4 cp or
cpc instructions... I guess I am still missing something in the bit test
department...

--
Vince

if (address && 0x00040000)
24ec: 21 15 cp r18, r1
24ee: 31 05 cpc r19, r1
24f0: 41 05 cpc r20, r1
24f2: 51 05 cpc r21, r1
24f4: 11 f0 breq .+4 ; 0x24fa



> if (address & 0x00040000)
> 24ec: da 01 movw r26, r20
> 24ee: c9 01 movw r24, r18
> 24f0: 72 e1 ldi r23, 0x12 ; 18
> 24f2: b6 95 lsr r27
> 24f4: a7 95 ror r26
> 24f6: 97 95 ror r25
> 24f8: 87 95 ror r24
> 24fa: 7a 95 dec r23
> 24fc: d1 f7 brne .-12 ; 0x24f2
> 24fe: 81 70 andi r24, 0x01 ; 1
> 2500: 90 70 andi r25, 0x00 ; 0
> 2502: 89 2b or r24, r25
> 2504: 11 f0 breq .+4 ; 0x250a 114



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#3 Nov. 4, 2005 06:34:05

Royce P.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


hI,On Fri, 04 Nov 2005 11:41:35 +0530, Vincent Trouilliez<> wrote:So that's indeed about 20 times faster. Although I still don't get why
it can't just use one single SBRC/S instruction instead of these 4 cp or--------------------------

Have you tried creating a structure of single bit variables like:

typedef unsigned word
typedef unsigned char byte
//Above is for my conenienience only..

typedef volatile union //reserve 2 bytes to be used as flags.
{
word asword;

struct
{
byte B0: 1;
byte B1: 1;
byte B2 : 1;
byte B3 : 1;
byte B4 : 1;
byte B5 : 1;
byte B6 : 1;
byte B7 : 1;
byte B8 : 1;
byte B9 : 1;
byte B10 : 1;
byte B11 : 1;
//etc...
}bits;
}flags;

flags flg0; //, flg1;
//=============================
#define flg_test flg0.bits.B9 //for example
//------------
int main(void)
{
if(flg_test)
{
//do something..
}

return 0;

}
//============================

I believe this will generate the sbrs/sbrc instructions

--Royce.
--
Using Opera's revolutionary e-mail client:http://www.opera.com/mail/_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#4 Nov. 4, 2005 07:07:07

Vincent T.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


> I replaced the '&' operator with the more appropriate '&&' one.... works
> much better... 5 instructions instead of 115 (3 + 6*18 + 4) for the
> previous code.
> So that's indeed about 20 times faster. Although I still don't get why
> it can't just use one single SBRC/S instruction instead of these 4 cp or
> cpc instructions... I guess I am still missing something in the bit test
> department...
>

> if (address && 0x00040000)
> 24ec: 21 15 cp r18, r1
> 24ee: 31 05 cpc r19, r1
> 24f0: 41 05 cpc r20, r1
> 24f2: 51 05 cpc r21, r1
> 24f4: 11 f0 breq .+4 ; 0x24fa



Hmmm, '&&' might give much tighter code than '&', but my program no
longer works ! So it's still not the proper way to test a bit then,
dear... :o(((


--
Vince



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#5 Nov. 4, 2005 07:39:46

Ian C.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


Hi Vince,All your new code is doing is checking that address is non-zero as it isa logical AND with a non-zero number, which would get optimised out.I haven't tried this, but it might be better:

unsigned char temp;

temp = (address >> 16) & 0xFF;

if(temp & 0x04)
{
/* Your code */
}

This is just off the top of my head...hope it works for you.

regards,

Ian Caddy



Vincent Trouilliez wrote:I replaced the '&' operator with the more appropriate '&&' one.... works
much better... 5 instructions instead of 115 (3 + 6*18 + 4) for the
previous code.
So that's indeed about 20 times faster. Although I still don't get why
it can't just use one single SBRC/S instruction instead of these 4 cp or
cpc instructions... I guess I am still missing something in the bit test
department...if (address && 0x00040000)
24ec: 21 15 cp r18, r1
24ee: 31 05 cpc r19, r1
24f0: 41 05 cpc r20, r1
24f2: 51 05 cpc r21, r1
24f4: 11 f0 breq .+4 ; 0x24faHmmm, '&&' might give much tighter code than '&', but my program no
longer works ! So it's still not the proper way to test a bit then,
dear... :o(((


--
Vince



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-l***@*ongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list--
Ian Caddy
Goanna Technologies Pty Ltd
+61 8 9221 1860



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#6 Nov. 4, 2005 08:43:00

Vincent T.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


On Fri, 2005-11-04 at 15:20 +0800, Ian Caddy wrote:
> Hi Vince,
>
> All your new code is doing is checking that address is non-zero as it is
> a logical AND with a non-zero number, which would get optimised out.
>
> I haven't tried this, but it might be better:
>
> unsigned char temp;
>
> temp = (address >> 16) & 0xFF;
>
> if(temp & 0x04)


Thank you very much Ian, your code is highly efficient, and does work
perfectly, unlike && or &. :o) I am in heaven :

temp = (address >> 16) & 0xFF;
28bc: ca 01 movw r24, r20
28be: aa 27 eor r26, r26
28c0: bb 27 eor r27, r27
if (temp & 0x04)
28c2: 82 ff sbrs r24, 2
28c4: 02 c0 rjmp .+4 ; 0x28ca

can't get any better than that really :o)))


Thanks again


--
Vince



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#7 Nov. 4, 2005 09:33:47

Alex W.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


Him

Vincent Trouilliez schrieb:
> Thank you very much Ian, your code is highly efficient, and does work
> perfectly, unlike && or &. :o) I am in heaven :
>
> temp = (address >> 16) & 0xFF;
> 28bc: ca 01 movw r24, r20
> 28be: aa 27 eor r26, r26
> 28c0: bb 27 eor r27, r27
> if (temp & 0x04)
> 28c2: 82 ff sbrs r24, 2
> 28c4: 02 c0 rjmp .+4 ; 0x28ca
>
> can't get any better than that really :o)))

if you make temp unsigned char, it should be even better.

-Blueloop


_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#8 Nov. 4, 2005 12:14:31

Vincent T.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


On Fri, 2005-11-04 at 10:17 +0100, Alex Wenger wrote:
> Him
>
> Vincent Trouilliez schrieb:
> > Thank you very much Ian, your code is highly efficient, and does work
> > perfectly, unlike && or &. :o) I am in heaven :
> >
> > temp = (address >> 16) & 0xFF;
> > 28bc: ca 01 movw r24, r20
> > 28be: aa 27 eor r26, r26
> > 28c0: bb 27 eor r27, r27
> > if (temp & 0x04)
> > 28c2: 82 ff sbrs r24, 2
> > 28c4: 02 c0 rjmp .+4 ; 0x28ca
> >
> > can't get any better than that really :o)))
>
> if you make temp unsigned char, it should be even better.


Yes I see what you mean, the two 'eor' instructions that clear the two
upper bytes.... The problem is that 'temp' IS declared as uint8_t, and I
have no idea why the compiler insists on clearing the upper bytes as if
it were casting it into a 32bit integer (then what about the second byte
in this case, should get cleared as well ?!). It's only testing a bit in
the first (and only) byte, r24, so I don't understand why it care for
upper bytes at all. I tried to reword the statement a bit:

temp = (uint8_t) (address >> 16) 0xFF;

,as well as change optimisation flags, but it really insists on clearing
these two bytes. God knows why. I guess it's doing something very subtle
that escapes me...


--
Vince



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#9 Nov. 4, 2005 12:50:37

Bernard F.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


Vincent Trouilliez wrote:I replaced the '&' operator with the more appropriate '&&' one.... works
much better... 5 instructions instead of 115 (3 + 6*18 + 4) for the
previous code.Unfortunately, '&&' and '&' are very different. '&' is the correct bitoperator to use, '&&' will check the result of an expression. Soif ( address && 0x00040000)

is always true if address is not null.The assembly output is much smaller since the optimizer took away '&&0x00040000' since this part is always true! I gess that if you look atthe full assembly, you'll see 'address' being loaded in r18-r21. So thecompiler just checks that 'address' is not null... (r1 is always at zerofor avr-gcc).Now your problem with 'address & 0x00040000' is a real one: avr-gcc isnot yet very good with 32 bits operators (BTW what version of avr-gcc doyou use?).To solve such speed problems, you have to tell the compiler that youwant to perform just a 8 bit operation. So use something like:----
union {
uint32_t my_ulong;;
struct {
uint8_t a;
uint8_t b;
uint8_t c;
uint8_t d;
} my_bytes;
} value;

value.my_ulong=address;
if(value.my_bytes.c & 0x40)

----

This is very dirty:- it is not portable since it relies on the endieness of the target andcompiler (note that it may be value.my_bytes.b to test to have the codereally working, I did not test!)- It's a pain to maintain since some other people will look at this codein a few weeks/months/years and think that the person who wrote it wasnut unless it is very well documented.- In a later version of the compiler it can have the opposite effect andbe less efficient than to have the compiler do correctly its job.Now it solves your problem today, so it's up to you to decide to use itor not.Bernard



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

#10 Nov. 4, 2005 13:30:34

Vincent T.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ?


> Now your problem with 'address & 0x00040000' is a real one: avr-gcc is
> not yet very good with 32 bits operators

Well, this way we have nice things to be looking forward to, for
upcoming releases of gcc.... :-)

> (BTW what version of avr-gcc do you use?).

I compiled 3.4.3 ... does 3.4.4 or 4.0 do a better job at it ?


> To solve such speed problems, you have to tell the compiler that you
> want to perform just a 8 bit operation. So use something like:
> ----
> union {
> uint32_t my_ulong;;
> struct {
> uint8_t a;
> uint8_t b;
> uint8_t c;
> uint8_t d;
> } my_bytes;
> } value;
>
> value.my_ulong=address;
> if(value.my_bytes.c & 0x40)
>
> ----
>
> This is very dirty:
>
> Now it solves your problem today, so it's up to you to decide to use it
> or not.
>
> Bernard


Well, as we saw earlier today:

uint8_t temp;

temp = (address >> 16) & 0xFF;
if (temp & 0x04)

works perfectly, much simpler and cleaner than all the union stuff ! :o)
I am not sure if it's anymore portable (does the >> operator shift left
in systems where MSB is stored first ?) but my program won't ever be
ported, it's only a prototype/one-off for my personal use... and
although I do intend to "upgrade" it in the coming years, with a
graphical LCD module instead of a text module, and some basic data
processing and graphing functionality, I think/guess AVR chips should
still be up to the job, when clocked at 16MHz.


--
Vince



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@nongnu.orghttp://lists.nongnu.org/mailman/listinfo/avr-gcc-list

Offline

  • Root
  • » AVR-GCC
  • » [avr-gcc-list] How to (efficeiently !!!) test a bit within a multi-byte integer ? [RSS Feed]

Board footer

Moderator control

Enjoy the 18th of November
PoweredBy

The Forums are managed by develissimo stuff members, if you find any issues or misplaced content please help us to fix it. Thank you! Tell us via Contact Options
Leave a Message
Welcome to Develissimo Live Support