0
\$\begingroup\$

My original question was:

I've a 8 bit data with only 3 bit used, for example:

0110 0001

Where 0 indicate unused bit that are always set to 0 and 1 indicate bits that change.

I want to convert this 0110 0001 8 bit to 3 bit that indicate this 3 used bits.

For example

0110 0001 --> 111

0010 0001 --> 011

0000 0000 --> 000

0100 0001 --> 101

How I can do that with minimal operations?

I had this answer:

a = 0110 0001;

data = ((a >> 4) & 6) | (a & 1)

But before this answer I used this method:

a = 0110 0001;

if(a&0x01)
 data = data + 1;
if(a&0x20)
 data = data + 2;    
if(a&0x40)
 data = data + 4;

I want to ask which is more efficient for a MCU an require less clock cycle to perform. (I know that depend on MCU, but I'm asking in general way)

\$\endgroup\$
  • \$\begingroup\$ "I know that depend on MCU, but I'm asking in general way" ehrm, what? \$\endgroup\$ – PlasmaHH Feb 24 '15 at 10:19
  • 3
    \$\begingroup\$ You'll have to see the actual machine code emitted to make your decision. No matter how hard you think your compiler may surprise you. \$\endgroup\$ – sharptooth Feb 24 '15 at 10:24
  • \$\begingroup\$ On an FPGA, this is trivial to do in one clock cycle. Difficult to get more minimal than that. \$\endgroup\$ – Brian Drummond Feb 24 '15 at 13:17
4
\$\begingroup\$

As @sharptooth mentions - the compiler really does have the final say. It also depends heavily on the architecture you're compiling for - what instructions it has available.

For instance, compiling your first snippet for MIPS results in:

sra v1,v0,0x4
andi    v1,v1,0x6
andi    v0,v0,0x1
or  v0,v1,v0

And your second results in:

andi    v1,v0,0x1
beqz    v1,func+0x20
andi    v1,v0,0x20
lbu v1,-32760(gp)
addiu   v1,v1,1
sb  v1,-32760(gp)
andi    v1,v0,0x20
beqz    v1,func+0x34
andi    v0,v0,0x40
lbu v1,-32760(gp)
addiu   v1,v1,2
sb  v1,-32760(gp)
beqz    v0,func+0x44
lbu v0,-32760(gp)
addiu   v0,v0,4
sb  v0,-32760(gp)

So undoubtedly in this situation your first snippet is the more code efficient. The same may not always be true though for a different architecture or a different compiler.

There's also some other caveats to note with your second snippet. Chiefly, what is "data" at the start? You have to remember to always zero "data" out before doing your calculations, or you'll end up accumulating successive values. The same is not true for the first snippet.

\$\endgroup\$
1
\$\begingroup\$

As others have correctly said, "it depends".

On a Cortex M0, with the variables in memory, for your one-liner I get

 // data = ((a >> 4) & 6) | (a & 1)
 ldrb   r1, [r2]
 ldrb   r3, [r2]
 mov    r2, #1
 lsr    r1, r1, #4
 and    r1, r4
 and    r2, r3
 mov    r3, r1
 orr    r3, r2
 strb   r3, [r5]

for your second code

 // if's 
 mov    r3, sp
 ldrb   r1, [r2]
 add    r3, r3, #6
 lsl    r1, r1, #31
 bpl    .L2
 ldrb   r1, [r3]
 add    r1, r1, #1
 uxtb   r1, r1
 strb   r1, [r3]
.L2:
 ldrb   r1, [r2]
 lsl    r1, r1, #26
 bpl    .L3
 ldrb   r1, [r3]
 add    r1, r1, #2
 uxtb   r1, r1
 strb   r1, [r3]
.L3:
 ldrb   r1, [r2]
 lsl    r1, r1, #25
 bpl    .L4
 ldrb   r1, [r3]
 add    r1, r1, #4
 uxtb   r1, r1
 strb   r1, [r3]
.L4:

Yuk, that's ugly, isn't it? But on an architecture that has skip instructions (PIC) or conditional instructions (ARM) it might look much better.

My attempt would be

data = ((a >> 4 ) | a ) & 0x0F;

ldrb    r2, [r3, #7]
ldrb    r1, [r3, #7]
lsr r2, r2, #4
orr r2, r1
mov r1, #15
and r2, r1
strb    r2, [r3, #6]

Which turns out marginally better than your one-liner on this version of this compiler for this target and with this optimization settings.

I think I could even leave out the final "& 0x0F" which would save 2 instructions.

\$\endgroup\$
0
\$\begingroup\$

On the Microchip PIC, testing individual bits is generally the fastest approach if the source or destination are in the same bank, or if at least one of them is an unbanked region. On those machines, each conditional bit set operation will take two instructions (one for the "if", and one for the "bit set"). On the 8051, the fastest approach if source and destination are in bit-addressable memory will be to use "mov bit,C" and "mov C,bit" instructions.

On the ARM, the fastest "general" approach is apt to be using a combination of either RORS or ROLS and ADC. Such an approach can be used to permute bits in arbitrary fashion among registers and a cost of two cycles per bit. If, for example, one wanted to assemble a register R2 using (in LSB-first order) bits R0.3, R1.4, R0.8, and R1.7, the sequence would be something like:

rors r1,r1,#7 ; Move bit 7 to bit 0
ands r2,r1,#1  ; May need to split this into two instructions on some machines
rors r0,r0,#9 ; Move bit 8 into carry and bit 31
adcs r2,r2,r2
rors r1,r1,#30 ; Bit 4 had been at 29, so move it to carry and bit 31
adcs r2,r2,r2
rors r0,r0,#27 ; Bit 3 had been at 26; so move it to carry and bit 31
adcs r2,r2,r2

Unfortunately, I don't know any nice way to convince a C compiler to generate something like the above, but the assembly code isn't complicated. The RORS instruction does a circular rotate right, copying the last shifted bit into carry register. The ADCS instruction adds a register to itself (effectively shifting it left one place) but adds one if the previous operation set the carry flag.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.