Efficient n-bit barrel shifter in C or BASIC

Thread Starter

thatoneguy

Joined Feb 19, 2009
6,359
Son is working on a effects idea with a PICAXE.

Need a rll and rlr assembly commands (RoLlLeft, RolLRight).

example, 4 bits, barrel shifted left by 2 places:
before: 0110
after: 1001
or
before: 0011
after: 1100

That is Roll Left, 2 bits

With the 20M, which doesn't have << or >> commands, to make a 1 bit roll, he just multiplied by 2, if result was > 8, set result to 1. This worked fine.

Now he wants to jump 2 steps, since he got the PICAXE 20X2, and now has the << and >> operators (in addition to a ton more memory).

I'm thinking (4 bit barrel shift left):

x=0b00001100
x=x<<2 ;Shift left 2
y=x & f0 ;Get high nybble
x= x | y>>4 ; put LSB back to far right side


Is there a way to make this more efficient?

In C a function could be made for this, but it would only deal with char length digits (*char, bool dir, char bits)

Input?
 

codehead

Joined Nov 28, 2011
57
First, it appears that the thread title is wrong—I think that you are asking for a rotate (wrapping around high and low bits), correct? A barrel shifter is something completely different (it's usually done in hardware—it allows multiple bit shifts in a single cycle instead of one at a time).
 

joeyd999

Joined Jun 6, 2011
4,432
I don't do C on PICs, but here is how I'd do it in asm:

Rich (BB code):
;four bit barrel roller
;  input:
;    barreg: barrel roller register
;    flags:  flag register.  Flags.0 = 0 if roll right, 1 if roll left
;    wreg:  number of shifts
;
;  output:
;     barreg: rotated value
;
;   uses:
;     bitcnt

barroll	movwf	bitcnt		;save number of shifts

	bcf	status,c	;ensure 0 shifted in

brloop	btfsc	flags,0		;roll right?
	goto	brleft		;no, left.

brright	rrf	barreg,f	;shift right
	btfsc	status,c	;bit roll out?
	bsf	barreg,3	;yes, set high bit

	goto	brcont		;continue with loop

brleft	rlf	barreg,f	;shift left
	btfsc	barreg,4	;1 roll out if bit 3?
	bsf	barreg,0	;yes, set bit 0
	bcf	barreg,4	;and clear bit 4
	
brcont	decfsz	bitcnt,f	;decrement counter
	goto	brloop		;do for all bits
Two things of import:

1) I assume you want to keep the high nibble b'0000'. I've included code to ensure that.

2) I didn't run this through the simulator...your mileage may vary!

I wouldn't know how to code this in any particular C implementation to get similar asm code. Sorry.
 

ErnieM

Joined Apr 24, 2011
8,058
Quickest way to get an answer in C would be to read back an array holding the result:

Rich (BB code):
static Shifted = {0x0, 0x4, 0x8, 0xC, 
                  0x1, 0x5, 0x9, 0xD, 
                  0x2, 0x6, 0xA, 0xE, 
                  0x3, 0x7, 0xB, 0xF}

....

   y = shifted[x];
hint: check my math, I did it in notepad. :D
 

joeyd999

Joined Jun 6, 2011
4,432
Quickest way to get an answer in C would be to read back an array holding the result:

Rich (BB code):
static Shifted = {0x0, 0x4, 0x8, 0xC, 
                  0x1, 0x5, 0x9, 0xD, 
                  0x2, 0x6, 0xA, 0xE, 
                  0x3, 0x7, 0xB, 0xF}

....

   y = shifted[x];
hint: check my math, I did it in notepad. :D
I think he wanted a variable number of shifts, both left and right. Regardless, your array method would work, faster than mine, and it would do well in asm too...
 

ErnieM

Joined Apr 24, 2011
8,058
Wow, you mean I wrote some C that is faster then assembly?

Thank you sir, that is no small compliment. :)

(Of course, the same algorithm written in assembler would be faster still.)
 

joeyd999

Joined Jun 6, 2011
4,432
Wow, you mean I wrote some C that is faster then assembly?

Thank you sir, that is no small compliment. :)

(Of course, the same algorithm written in assembler would be faster still.)
Somehow you guys got the idea that I am not appreciative of good code, regardless of language, unless I wrote it. I hope this shows, at least to a small extent, that that's not entirely true... :)
 

codehead

Joined Nov 28, 2011
57
Guys, these aren't barrel shifters. That's why I asked the OP to clarify what he was asking for. Yes, barrel shifters shift multiple bits. But shifting multiple bits doesn't mean it's a barrel shifter.
 

joeyd999

Joined Jun 6, 2011
4,432
Guys, these aren't barrel shifters. That's why I asked the OP to clarify what he was asking for. Yes, barrel shifters shift multiple bits. But shifting multiple bits doesn't mean it's a barrel shifter.
Don't care what it's called. Gave him what he asked for.
 

codehead

Joined Nov 28, 2011
57
Don't care what it's called. Gave him what he asked for.
OK, but your code called it a "barrel roller" as well—just making a point that that's not what it is. Not trying to make it a big deal, but some things are called certain names for a reason. I'll shut up now. ;-)
 

codehead

Joined Nov 28, 2011
57
...I'm thinking (4 bit barrel shift left):

x=0b00001100
x=x<<2 ;Shift left 2
y=x & f0 ;Get high nybble
x= x | y>>4 ; put LSB back to far right side


Is there a way to make this more efficient?

In C a function could be made for this, but it would only deal with char length digits (*char, bool dir, char bits)

Input?
Your idea is pretty good, but note that you can delete that "& f0" to the next line—you don't need to mask it for y, since the least significant bits will roll into the bit bucket anyway. And you'll need to add a mask the next line with "& 0f" to clear the high nibble, if that's required. (That is, you can replace the last two lines with something like "x = (x&0f) | x>>4;")

For the C function, note that you could ditch the direction boolean and use a negative "bits" value for right shift, if you prefer. It might well be quicker to copy the value to a register variable, but I'll leave out that kind of optimizing, and make it simple with no new variables or declarations:

Rich (BB code):
void shifty(char *target, bool directionRight, char bits) {
  if (directionRight)
    bits = 4 - bits;
  *target <<= bits;
  *target = (*target | (*target >> 4)) & 0x0f;
}
Of course, you could have done a shift right instead of subtracting from 4, and moved the shift left into an else, but that's an added branch, and also it sets up the other form I mentioned..if you use negative bits for right shifts:

Rich (BB code):
void shifty(char *target, char bits) {
  if (bits < 0)
    bits = 4 + bits;
  *target <<= bits;
  *target = (*target | (*target >> 4)) & 0x0f;
}
 

Thread Starter

thatoneguy

Joined Feb 19, 2009
6,359
Thanks for the shortening, the code he started with came out rather huge in assembly, so I'm thinking about just inlining the assembly shown by jody above, or the lookup array, not sure which.

I know barrel shifter isn't the exact term, but many realize what I'm talking about if they haven't worked on systems with the roll left and roll right (both through carry) instructions, which PIC16 doesn't have.

I try to let my kid figure out most stuff, and nudge him in better directions when he has ideas, but in this case, my "better way" ended up way bigger than I thought, but was more flexible.

He has been programming for a couple years is all and still tends toward spaghetti code when trying out an idea, then doesn't optimize it later. His solution whas a bunch of case|select statements, but after seeing the lookup table, that is a cool way of doing it as well.

He is trying to write athe Basic Stamp & PICAXE Instructions as a C library, using C functions that can take arguments to be more useful. It might turn into something kind of cool, and it might not, he's having fun trying.
 

codehead

Joined Nov 28, 2011
57
...His solution whas a bunch of case|select statements, but after seeing the lookup table, that is a cool way of doing it as well.

He is trying to write athe Basic Stamp & PICAXE Instructions as a C library, using C functions that can take arguments to be more useful. It might turn into something kind of cool, and it might not, he's having fun trying.
That's great. I've long told people who've asked me how to learn programming that it's best if they have something they're trying to do (learning the language by figuring out how it can get them where they're trying to go, as opposed to learning syntax aimlessly).

Solving something by computation vs lookup tables is always a fun exercise—caching can always be big factor on the more sophisticated processors. Here's a full solution for looking up a nibble-shift (untested), with negative bits for right shift—the second "if" statement can be deleted if you make sure to call it with shift of plus/minus 1-3, constant shifts could be broken up to access a line, etc., so I'm including this mostly for the table:

Rich (BB code):
    static const char shiftLeft[] = {
        0, 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15,  // rol 1
        0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15,  // rol 2
        0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15   // rol 3
    };
    if (bits < 0)
        bits += 4;
    if ((bits <= 0) || (bits > 3))
        return;
    *target = shiftLeft[*target * (bits - 1)];


    // example of optimized constant "rol 2", inline
    static const char rol2[] = {
        0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15  // << 2
    };
    // ...somewhere in your code...
    val = rol2[val];
BTW, I wasn't trying to be the technology police (barrel shifters)—I was truly confused about what you were asking for till I came back the next day and re-read your post.
 
Top