Reversing bit order

[SCV]

Is there a neater way to reverse the bit order?

eg 0000 0001 0010 0011 (0x0123) becomes 1100 0100 1000 0000 (0xC480)

Code Select Expand

CRC_IN.15 = TEMP_CRC.0
CRC_IN.14 = TEMP_CRC.1
CRC_IN.13 = TEMP_CRC.2
CRC_IN.12 = TEMP_CRC.3
CRC_IN.11 = TEMP_CRC.4
CRC_IN.10 = TEMP_CRC.5
CRC_IN.9  = TEMP_CRC.6
CRC_IN.8  = TEMP_CRC.7
CRC_IN.7  = TEMP_CRC.8
CRC_IN.6  = TEMP_CRC.9
CRC_IN.5  = TEMP_CRC.10
CRC_IN.4  = TEMP_CRC.11
CRC_IN.3  = TEMP_CRC.12
CRC_IN.2  = TEMP_CRC.13
CRC_IN.1  = TEMP_CRC.14
CRC_IN.0  = TEMP_CRC.15
Thanks,
Tim

[JonW]

cant you use the @ bitwise reverse

var = var @ 8 etc (if byte)
Page 88 manual

[JonW]

sorry that's not what you requested. 

a loop may also use more codespace.

this should work

             TEMP = %0000111100001111           
             TEMP2 = 0
             For LP = 15 To 0 STEP -1
                If TEMP.0  = 1 Then SetBit TEMP2,LP
                Ror TEMP   
             Next

[JonW]

Simulated it and compiled it and its about 50 bytes less for the loop in a 18F device

[John Drew]

It might be 50 bytes less in a loop but it might be slower as the loop cycles 16 times. I don't know how the bitwise reverse works. Maybe it also has loops. A look at the ASM would sort that question.
John

[JonW]

True John, I guess you have to weigh up what's more efficient

Tim, If you want to call it then you do a procedure

        GoTo        MAIN
       
Proc REVCRC(CRCIN As Word)
            Dim LP As Byte                   
            CRC = 0
            For LP = 15 To 0 Step -1
                If CRCIN.1 = 1 Then SetBit CRC,LP
                Ror CRCIN   
            Next
EndProc       

     
       
MAIN:

             CRC = %0000101000001111
             REVCRC(CRC)
           
End 

[SCV]

Interesting ideas. None seem to be quicker and easier than a bit bash, possibly more elegant, though I do like to keep things simple and de-buggable.

Not sure the bitwise reverse '@' would work, I thought it just inverted (xor) the lowest bits. If it was a bit swap then firstly, the number of bits to be reversed would have to be an even number, and secondly, it would not affect just the lowest bits!

[JonW]

no the @ does not work in your case but the loop and proc does

[trastikata]

http://www.piclist.com/techref/microchip/math/bit/revbits.htm

[JonW]

The above Proc vs original:  The proc loop is approx 8 times  longer in process time (Proteus Sim).  Its slower but more code efficient.

[tumbleweed]

If you're looking for the fastest way then that would be a slight variation on the code in  post #1:

Code Select Expand

TEMP = %0000111100001111          

TEMP2 = 0
If temp.0 = 1 Then temp2.15 = 1
If temp.1 = 1 Then temp2.14 = 1
If temp.2 = 1 Then temp2.13 = 1
If temp.3 = 1 Then temp2.12 = 1
If temp.4 = 1 Then temp2.11 = 1
If temp.5 = 1 Then temp2.10 = 1
If temp.6 = 1 Then temp2.9 = 1
If temp.7 = 1 Then temp2.8 = 1
If temp.8 = 1 Then temp2.7 = 1
If temp.9 = 1 Then temp2.6 = 1
If temp.10 = 1 Then temp2.5 = 1
If temp.11 = 1 Then temp2.4 = 1
If temp.12 = 1 Then temp2.3 = 1
If temp.13 = 1 Then temp2.2 = 1
If temp.14 = 1 Then temp2.1 = 1
If temp.15 = 1 Then temp2.0 = 1

That saves one instruction per bit, so it's also slightly less code (but more code than most of the loops).

[SCV]

Thanks for the link Trastikata.
Intersting idea to xor the bit15 against bit0, bit14 against bit1 etc.

It was a thought provoking question as final code is going into a dsPIC33 with gallons of space and a warp speed clock, so my only concern is that anyone reading my code instantly understands what it does and has no doubts how the procedure works.

[top204]

With the 16-bit devices, loops can be extremely fast because of the mnemonics the devices have, and the linear RAM, and the use of the WREGx SFRs that the compiler allows. Not forgetting the tight assembler code that the compiler produces. For example, the demo below has a procedure to reverse the bit-order of a 16-bit value using a loop and is efficient. It also has an inline coded procedure that is twice as efficient. The efficiency is also because each time a rotate happens, it rotates the full 16-bit variable in a single instruction cycle.

There are more convoluted methods of reversing bits, but the procedures below show the two simpler methods that will work on any device.

Under tests, the looped procedure took approx 5.4us at 32MHz, while the inline procedure took approx 2.4us at 32MHz.

Code Select Expand

'
'   /\\\\\\\\\
'  /\\\///////\\\
'  \/\\\     \/\\\                                                 /\\\          /\\\
'   \/\\\\\\\\\\\/        /\\\\\     /\\\\\\\\\\     /\\\\\\\\   /\\\\\\\\\\\  /\\\\\\\\\\\  /\\\\\\\\\
'    \/\\\//////\\\      /\\\///\\\  \/\\\//////    /\\\/////\\\ \////\\\////  \////\\\////  \////////\\\
'     \/\\\    \//\\\    /\\\  \//\\\ \/\\\\\\\\\\  /\\\\\\\\\\\     \/\\\         \/\\\        /\\\\\\\\\\
'      \/\\\     \//\\\  \//\\\  /\\\  \////////\\\ \//\\///////      \/\\\ /\\     \/\\\ /\\   /\\\/////\\\
'       \/\\\      \//\\\  \///\\\\\/    /\\\\\\\\\\  \//\\\\\\\\\\    \//\\\\\      \//\\\\\   \//\\\\\\\\/\\
'        \///        \///     \/////     \//////////    \//////////      \/////        \/////     \////////\//
'                                  Let's find out together what makes a PIC Tick!
'
' Procedures to reverse the bit-order of a 16-bit variable, using a loop or inline
'
' Written for the Positron16 BASIC compiler by Les Johnson
'  
    Device = 24FJ64GA002
    Declare Xtal = 32
'
' Setup USART1
'   
    Declare Hserial_Baud = 9600
    Declare HRSOut1_Pin = PORTB.14                  ' Select which pin is to be used for TX with USART1
'
' Create some variables for the demo
'   
    Dim WordIn As Word
    Dim Wordout As Word

'----------------------------------------------------------------
' The main program starts here
' Reverse the bit order of a 16-bit variable and display the results on a serial terminal
'
Main:       
    CLKDIV = 0                                      ' CPU peripheral clock ratio set to 1:1
    Write_OSCCONH(%00010000)                        ' Enable the PLL to operate the device at 32MHz
    PPS_Output(cOut_Pin_RP14, cOut_Fn_U1TX)         ' Make Pin RB14 U1TX
'
' Perform the reversing using the looped code procedure
' 
    HRSOutLn "Looped"
    WordIn = %1011111100000001                      ' Load a variable with the value to reverse
    HRSOutLn "Before: ", IBin16 WordIn              ' Transmit the binary value before it is reversed
   
    Wordout = RevBits16(WordIn)                     ' Reverse the value within the variable using the looped code
   
    HRSOutLn "After : ", IBin16 Wordout             ' Transmit the binary value after it is reversed
'
' Perform the reversing using the inline code procedure
'     
    HRSOutLn "Inline"
    WordIn = %1011111100000001                      ' Load a variable with the value to reverse
    HRSOutLn "Before: ", IBin16 WordIn              ' Transmit the binary value before it is reversed
   
    Wordout = Fast_RevBits16(WordIn)                ' Reverse the value within the variable using the inline code
   
    HRSOutLn "After : ", IBin16 Wordout             ' Transmit the binary value after it is reversed
      
'----------------------------------------------------------------
' Reverse the bit-order of a 16-bit value using a loop
' Input     : pValue holds the value to reverse
' Output    : Returns the reversed value
' Notes     : Optimised further by using the WREGx SFRs
'
Proc RevBits16(pValue As WREG0), WREG1
    For WREG2.Byte0 = 15 To 0 Step -1   ' Create a loop for the amount of bits to reverse
        Rol pValue                      ' Rotate the variable Left, into the Carry flag
        Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Next
EndProc

'----------------------------------------------------------------
' Reverse the bit-order of a 16-bit value using inline code
' Input     : pValue holds the value to reverse
' Output    : Returns the reversed value
' Notes     : Optimised further by using the WREGx SFRs
'
Proc Fast_RevBits16(pValue As WREG0), WREG1
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
    Rol pValue                      ' Rotate the variable Left, into the Carry flag
    Ror Result                      ' Rotate the Carry flag into the MSB of Result
EndProc

On the serial terminal, it displays:

Looped
Before: %1011111100000001
After : %1000000011111101
Inline
Before: %1011111100000001
After : %1000000011111101

The assembler code for the looped procedure is shown below:

Code Select Expand

; Proc RevBits16(pValue As WREG0), WREG1
.global RevBits16
RevBits16:
; For WREG2.Byte0 = 15 To 0 Step -1
    mov.b #15,W2
_lbl__2:
; Rol pValue
    rlc.w WREG0
; Ror Result
    rrc.w WREG1
_lbl__4:
; Next
    dec.b WREG2
    bra c,_lbl__2
_lbl__3:
; EndProc
    return

It doesn't get much more optimised!

[JonW]

Slick.. .  of course use carry flag.

[See_Mos]

this was my solution, only tested with the one value $123.  I don't know how efficient it is but space wise only 50 bytes

temp = $123         
temp2 = 0

For index = 0 To 15
temp2 = temp2 << 1
temp2.0  = GetBit temp,index
Next

[atomix]

my experiment code for pic18f

Code Select Expand

Device 18F46K22
Declare Xtal = 64

Dim TEMP As Word
Dim TEMP2 As Word

TEMP = %0000111100001111

TEMP2 = Rev_Fast(TEMP)
TEMP2 = Rev_Other(TEMP)

'-----------------------------------------------------------------------
Proc Rev_Fast(value As Word),Word
    Result.Byte1 = Rev_Fast_Byte(value.Byte0)
    Result.Byte0 = Rev_Fast_Byte(value.Byte1)
EndProc

Proc Rev_Other(value As Word),Word
    Result.Byte1 = Rev_Other_Byte(value.Byte0)
    Result.Byte0 = Rev_Other_Byte(value.Byte1)
EndProc

Proc Rev_Fast_Byte(value As WREG),WREG
    PRODH = value
    Rlncf PRODH,W   :                   WREG = WREG & %00010001  :  PRODL = WREG
    Rrncf PRODH,W   :                   WREG = WREG & %10001000  :  PRODL = PRODL | WREG
    Rlncf PRODH,W   :  Swapf WREG,W  :  WREG = WREG & %01000100  :  PRODL = PRODL | WREG
    Rrncf PRODH,W   :  Swapf WREG,W  :  WREG = WREG & %00100010  :  WREG  = PRODL | WREG
EndProc

Proc Rev_Other_Byte(value As WREG),WREG
    PRODH = value
    Rrncf PRODH,W   :                   WREG = WREG & %01010101  :  PRODL = WREG
    Rlncf PRODH,W   :                   WREG = WREG & %10101010  :  PRODL = PRODL | WREG
    Rrncf PRODL,W   :  Rrncf WREG,W  :  WREG = WREG & %00110011  :  PRODH = WREG
    Rlncf PRODL,W   :  Rlncf WREG,W  :  WREG = WREG & %11001100  :  WREG  = PRODH | WREG
    Swapf WREG,W
EndProc

[top204]

One of the good things about the 16-bit devices is that flash memory is not a problem, and there are some devices that have plenty of it. Also, the mnemonics allow complex processes to be performed with less flash memory usage.

For speed, there is no getting away from the fact that loops are slower, so an inline approach is always better. Whenever I create code that requires speed, I roll out the code so it operates a lot faster. Then, if flash memory is becoming tight, I go through the code and make the sections back into loops if the program is not too reliant on them.

For example, I recently required a fast method of upscaling a 12-bit value to a 16-bit value, so I created the inline code:

Code Select Expand

$define UpScale_12_to_16(pValue, pResult)  '  
    pResult.Word1 = pValue.Word0           '
    pResult.Word0 = $0000                  '  
    pResult.Byte0 = pResult.Byte1          '
    pResult.Byte1 = pResult.Byte2          '
    PRODL = pResult.Byte3                  '
    Ror PRODL                              '
    Ror pResult.Byte1                      '
    Ror pResult.Byte0                      '
    Ror PRODL                              '
    Ror pResult.Byte1                      '
    Ror pResult.Byte0                      '
    Ror PRODL                              '
    Ror pResult.Byte1                      '
    Ror pResult.Byte0                      '
    Ror PRODL                              '
    Ror pResult.Byte1                      '
    Ror pResult.Byte0

It is larger, but a whole lot faster to operate.

[atomix]

my fast method of upscaling a 12-bit value to a 16-bit value (for pic18f):

see info link:

Code Select Expand

Device 18F46K22
Declare Xtal = 64
Dim PROD As PRODL.Word
Dim V As Word
Dim R As Dword

$define MY_12_16(pValue, pResult)          ' 
    PROD = pValue.Byte0 * 16               '
    WREG = pValue.Byte1 & 15               '
    pResult.Byte0 = PRODL | WREG           '
    WREG = pValue.Byte1 << 4               '
    pResult.Byte1 = PRODH | WREG         

V = %111100000000  :  MY_12_16(V, R)


[top204]

That is an excellent piece of coding Atomix!

It's good that the compiler allows single expressions using the "very" volatile WREG SFR isn't it? It seems such a simple thing, and is taken for granted, but I had to go through all the seperate expression codes within the compiler's code when I wrote it, and detect if an 8-bit operand is WREG, and if so, change the code so it does not get altered. It took a while, but I think it was worth it because code can be made so much tighter. Also, some of the expressions get turned into a single assember mnemonic. :-)

I have a project on at the moment that is taking all of my time up, so once it is completed for its testing in a few days, I will get back into the other, possible, anomalies and correct the ones that are valid. Some have already been corrected, but I will add them all to the corrections updater ASAP. I'll send you a link to it first, if you do not mind, so you can check out some of the corrections before I make it public.

[atomix]

ok