Efficient n-bit barrel shifter in C or BASIC

Discussion in 'Embedded Systems and Microcontrollers' started by thatoneguy, Feb 9, 2012.

  1. thatoneguy

    Thread Starter AAC Fanatic!

    Feb 19, 2009
    6,357
    718
    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?
     
  2. codehead

    Member

    Nov 28, 2011
    56
    11
    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).
     
  3. joeyd999

    AAC Fanatic!

    Jun 6, 2011
    2,677
    2,729
    I don't do C on PICs, but here is how I'd do it in asm:

    Code ( (Unknown Language)):
    1.  
    2. ;four bit barrel roller
    3. ;  input:
    4. ;    barreg: barrel roller register
    5. ;    flags:  flag register.  Flags.0 = 0 if roll right, 1 if roll left
    6. ;    wreg:  number of shifts
    7. ;
    8. ;  output:
    9. ;     barreg: rotated value
    10. ;
    11. ;   uses:
    12. ;     bitcnt
    13.  
    14. barroll movwf   bitcnt      ;save number of shifts
    15.  
    16.     bcf status,c    ;ensure 0 shifted in
    17.  
    18. brloop  btfsc   flags,0     ;roll right?
    19.     goto    brleft      ;no, left.
    20.  
    21. brright rrf barreg,f    ;shift right
    22.     btfsc   status,c    ;bit roll out?
    23.     bsf barreg,3    ;yes, set high bit
    24.  
    25.     goto    brcont      ;continue with loop
    26.  
    27. brleft  rlf barreg,f    ;shift left
    28.     btfsc   barreg,4    ;1 roll out if bit 3?
    29.     bsf barreg,0    ;yes, set bit 0
    30.     bcf barreg,4    ;and clear bit 4
    31.    
    32. brcont  decfsz  bitcnt,f    ;decrement counter
    33.     goto    brloop      ;do for all bits
    34.  
    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.
     
  4. ErnieM

    AAC Fanatic!

    Apr 24, 2011
    7,386
    1,605
    Quickest way to get an answer in C would be to read back an array holding the result:

    Code ( (Unknown Language)):
    1.  
    2. static Shifted = {0x0, 0x4, 0x8, 0xC,
    3.                   0x1, 0x5, 0x9, 0xD,
    4.                   0x2, 0x6, 0xA, 0xE,
    5.                   0x3, 0x7, 0xB, 0xF}
    6.  
    7. ....
    8.  
    9.    y = shifted[x];
    10.  
    hint: check my math, I did it in notepad. :D
     
  5. joeyd999

    AAC Fanatic!

    Jun 6, 2011
    2,677
    2,729
    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...
     
  6. ErnieM

    AAC Fanatic!

    Apr 24, 2011
    7,386
    1,605
    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.)
     
  7. joeyd999

    AAC Fanatic!

    Jun 6, 2011
    2,677
    2,729
    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... :)
     
  8. codehead

    Member

    Nov 28, 2011
    56
    11
    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.
     
  9. joeyd999

    AAC Fanatic!

    Jun 6, 2011
    2,677
    2,729
    Don't care what it's called. Gave him what he asked for.
     
  10. codehead

    Member

    Nov 28, 2011
    56
    11
    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. ;-)
     
  11. codehead

    Member

    Nov 28, 2011
    56
    11
    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:

    Code ( (Unknown Language)):
    1.  
    2. void shifty(char *target, bool directionRight, char bits) {
    3.   if (directionRight)
    4.     bits = 4 - bits;
    5.   *target <<= bits;
    6.   *target = (*target | (*target >> 4)) & 0x0f;
    7. }
    8.  
    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:

    Code ( (Unknown Language)):
    1.  
    2. void shifty(char *target, char bits) {
    3.   if (bits < 0)
    4.     bits = 4 + bits;
    5.   *target <<= bits;
    6.   *target = (*target | (*target >> 4)) & 0x0f;
    7. }
    8.  
     
  12. thatoneguy

    Thread Starter AAC Fanatic!

    Feb 19, 2009
    6,357
    718
    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.
     
  13. codehead

    Member

    Nov 28, 2011
    56
    11
    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:

    Code ( (Unknown Language)):
    1.  
    2.     static const char shiftLeft[] = {
    3.         0, 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15,  // rol 1
    4.         0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15,  // rol 2
    5.         0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15   // rol 3
    6.     };
    7.     if (bits < 0)
    8.         bits += 4;
    9.     if ((bits <= 0) || (bits > 3))
    10.         return;
    11.     *target = shiftLeft[*target * (bits - 1)];
    12.  
    13.  
    14.     // example of optimized constant "rol 2", inline
    15.     static const char rol2[] = {
    16.         0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15  // << 2
    17.     };
    18.     // ...somewhere in your code...
    19.     val = rol2[val];
    20.  
    21.  
    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.
     
Loading...