Searching \ for '[PIC]: Better way to rotate?' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/devices.htm?key=pic
Search entire site for: 'Better way to rotate?'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: Better way to rotate?'
2000\07\17@172634 by Chris Eddy

flavicon
face
Folks, I have a very long data string that I want to shift in, to the
tune of 90 or more bits.  I want to shift the data in (or if possible
use a pointer to a bit with increment) in C.  (You assy folks sit back
down, I know it is fairly easy).  I can implement longs and use the left
shift operator, but how can I avoid carrying the one bit with a pack of
code just for that purpose?  If I just do a bunch of rotates, I think C
will start with a 0 in carry for the roll operation every time.

Any grand ideas?

Chris Eddy

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]: PIC only [EE]: engineering [OT]: off topic [AD]: advertisements

2000\07\17@183025 by Mark Willis

flavicon
face
Could shift it in in 8-bit or so wide, smaller chunks, then combine them
when done shifting in - all this basically does is move where you do the
shifting, though.

Or could make a struct and stuff each bit into a bit array then when
done read out the equivalent packed struct;  your compiler of choice may
not do this, in which case you might have to use some "nasty" pointer
accessing of the data, but less shifting.

 Mark

Chris Eddy wrote:
{Quote hidden}

--
I re-ship for small US & overseas businesses, world-wide.
(For private individuals at cost; ask.)

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]: PIC only [EE]: engineering [OT]: off topic [AD]: advertisements

2000\07\18@093740 by Scott Dattalo

face
flavicon
face
On Mon, 17 Jul 2000, Chris Eddy wrote:

> Folks, I have a very long data string that I want to shift in, to the
> tune of 90 or more bits.  I want to shift the data in (or if possible
> use a pointer to a bit with increment) in C.  (You assy folks sit back
> down, I know it is fairly easy).  I can implement longs and use the left
> shift operator, but how can I avoid carrying the one bit with a pack of
> code just for that purpose?  If I just do a bunch of rotates, I think C
> will start with a 0 in carry for the roll operation every time.
>
> Any grand ideas?
>
> Chris Eddy

The assembly version is just too easy. For 90 bits, you can do it in 12
instructions without resorting to optimization from Dmitry.


The C version is harder. But here is something for bit indexing that is more
generic.


void set_bit(unsigned char *bit_array, char bit_position, char new_state)
{


 if(new_state)
   bit_array[bit_position >> 3] |= ( 1 << (bit_position & 7) );
 else
   bit_array[bit_position >> 3] ^= ~( 1 << (bit_position & 7) );

}

I bet the compiler generates more than 12 instructions for this!


but I reckon you can do it in assembly like so:

set_bit:

 ;Get a pointer to the byte containing the bit we want:

   rrf   bit_position,w
   movwf fsr

   rrf   fsr,f
   rrf   fsr,w
   andlw BIT_ARRAY_MASK
   addlw bit_array
   movwf fsr

 ; find 1<<(bit_position&7) [note, this could be made 2-cycles
 ;                           shorter]

   movlw  0101b
   btfsc  bit_position,0
    movlw 1010b

   movwf  mask

   movlw  0011b
   btfsc  bit_position,1
    movlw 1100b

   andwf  mask,f

   btfsc  bit_position,2
    swapf mask,f

 ; now set or clear the bit

   movf   mask,w
   iorwf  indf,f         ; Assume we're setting.
   btfss  new_state,0
    xorwf mask,w         ; assumption was wrong


Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@112842 by Michael Rigby-Jones

flavicon
face
{Quote hidden}

Should the bit clear not be:

bit_array[bit_position >> 3] &= ~(1 << (bit_position & 7));

or am I missing something?

Anyway, as written this compiles to 55 words using HiTech, not including the
return and compiled for a 16F84.  By butchering the routine a bit to make it
less general i.e. removing the bit_array pointer and by breaking down the
maths into separate chunks I managed to get this down to 38 words, at the
cost of a couple of temp variables.


void set_bit(unsigned char bit_position, unsigned char new_state)
{
       unsigned char bitmask;
       unsigned char byteptr;

       byteptr = bit_position >> 3;
       bitmask = 1 << (bit_position & 7);

       if(new_state)
       {
               bitarray[byteptr] |= bitmask;
       }
       else
       {
               bitarray[byteptr] &= ~bitmask;
       }
}

Cheers

Mike

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@114713 by Michael Rigby-Jones

flavicon
face
Just a thought, if you don't need random access when filling the array, then
the following might work.  You will have to reset the bitmask and byteptr
before shifting in each chunk of bits.  23 words in Hitech.

unsigned char bitmask = 0x01;
unsigned char byteptr = 0x00;

void set_bit(unsigned char new_state)
{

       if(new_state)
               bitarray[byteptr] |= bitmask;
       else
               bitarray[byteptr] &= ~bitmask;

       if(bitmask && 0x80){
               bitmask = 0x01;
               byteptr++;}
       else
               bitmask << 1;
}

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@120620 by Scott Dattalo

face
flavicon
face
On Tue, 18 Jul 2000, Michael Rigby-Jones wrote:

> > void set_bit(unsigned char *bit_array, char bit_position, char new_state)
> > {
> >
> >
> >   if(new_state)
> >     bit_array[bit_position >> 3] |= ( 1 << (bit_position & 7) );
> >   else
> >     bit_array[bit_position >> 3] ^= ~( 1 << (bit_position & 7) );
> >
> > }
> >
> > I bet the compiler generates more than 12 instructions for this!
> >
> Should the bit clear not be:
>
> bit_array[bit_position >> 3] &= ~(1 << (bit_position & 7));
>
> or am I missing something?

Only that it had been two hours since my last cup of coffee. You're right, it
should be `&' instead of `^'.


{Quote hidden}

The unoptimized assembly version was 21 cycles/words. (but it's a tad more
difficult to understand). Does the C version have a loop for the << and >>
operators?

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@123757 by David Kott

flavicon
face
> Just a thought, if you don't need random access when filling the array,
then
{Quote hidden}

24 words in CCS PCM for the 'F84.

-d

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@134707 by Scott Dattalo

face
flavicon
face
On Tue, 18 Jul 2000, David Kott wrote:

{Quote hidden}

set_bit:

    movf   bitmask,w

    iorwf  indf,f
    btfsc  new_state,0
     xorwf indf,f

    clrc
    rlf    bitmask,w
    rlf    bitmask,f

    btfsc  bitmask,0
     incf  fsr,f


9 words/cycles in assembly, with the same caveats as the above routine
(i.e. byteptr, which is fsr, and bitmask both need pre-initialization).

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@135229 by Chris Eddy

flavicon
face
These answers are great.  I will do the idea by Michael, since I do not need
random access.  Thanks everyone for the ideas.

Chris Eddy

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@162951 by Peter L. Peres

picon face
>shift in 90 bits

I think that you could use a vector of shift registers (actually chars).
(I assume this is a 8 bit micro). Then you would have code like:

uchar data[NUM_BYTES];

p = data - 1;
for(i=NUM_BITS;i>0;--i) {
 if( !(i%8)) // actually: (i & 0x07) == 0
   ++p;
 *p = (*p * 2) + read_bit();
}

imho for 90 bits you should unroll the outer loop unless there is a code
size problem, or write it in assembly. 90 bits ~= 11 bytes of storage.

The loop above can be rewritten in assembly very efficiently (using fsr
for p and rotate for *2) and can even be isochronous). Like:

 movlw         (VECTOR_BASE-1)
 movwf         FSR

 movlw         NUM_BITS
 movwf         Fi

loop: ; loop period is 8T+overhead to read input bit
 movlw         H'07'
 andwf         Fi,w
 btfsc         STATUS,Z
 incf          FSR,f

 ; input bit into STATUS.C here

 rlf           INDF,f

 decfsz        Fi,f
 goto          loop

The same method (assembly) can be used on larger processors (i386) and it
works to transmit and to receive synchronous data and sound (;-)).

The bit stream must not be tranmitted off chip, it can be fed to another
register as required.

To rotate the whole register use something like:

c0 = input_carry;
for(i=LENGTH;i>0;--i) {
 *p++ = ((c1 = (*p & 0x80)) << 1) + c0;
 c0 = c1;
}

Which can be turned into assembly like:

 rlf           Vector_Top,w
 rlf           Fscratch,f

 movlw         VECTOR_SIZE
 movwf         Fi

 movlw         Vector_Base
 movwf         FSR

loop:
 rrf           Fscratch,f
 rlf           INDF,f
 rlf           Fscratch,f

 incf          FSR,f

 decfsz        Fi,f
 goto          loop

Fscratch will have its lowest and highest bits changed at the end.

I hope that this answers your question.

Peter

PS: Did the C compiler beat me to this ? ;-) ;-) ;-)

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@170115 by Scott Dattalo

face
flavicon
face
On Tue, 18 Jul 2000, Peter L. Peres wrote:

> >shift in 90 bits
>
> I think that you could use a vector of shift registers (actually chars).
> (I assume this is a 8 bit micro). Then you would have code like:
>
> uchar data[NUM_BYTES];
>
> p = data - 1;
> for(i=NUM_BITS;i>0;--i) {
>   if( !(i%8)) // actually: (i & 0x07) == 0
>     ++p;
>   *p = (*p * 2) + read_bit();
> }

this works

> c0 = input_carry;
> for(i=LENGTH;i>0;--i) {
>   *p++ = ((c1 = (*p & 0x80)) << 1) + c0;
>   c0 = c1;
> }

this doesn't. It looks like this'll only write one bit to each byte.

btw, I'm not sure what Chris's application is, but I once had a similar
requirement. For me, I needed to sample a stream as fast as possible. For an
arbitrary length (but constrained by the PIC's memory) arrary of bits, you can
do something like:


    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,0
    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,1
    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,2
    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,3
    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,4
    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,5
    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,6
    btfsc   BIT_PORT,THE_BIT
     bsf    byte0,7


    btfsc   BIT_PORT,THE_BIT
     bsf    byte1,0
 etc, for byte1, byte2

This'll give 2-cycle sampling per bit. There's a way to improve this to 1-cycle
resolution, but you're limited to 15 bits. Anyone care to guess how?

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@172344 by Dmitry Kiryashov

flavicon
face
part 0 44 bytes
his is a multi-part message in MIME format.
part 1 2210 bytes content-type:text/plain; charset=us-ascii (decoded 7bit)

Hi Scott and Piclisters. ;)

I feel like it's time to make a break, put endless
coffee aside and add one more two cent from me too ;)

Scott Dattalo wrote:
{Quote hidden}

Probably it would be better to pre allocate bit position value in cell
shifted by one bit to left, like xxxx.yyyz where xxxx is byte offset
and yyy bit offset. It let us write more tight code for this case.

       swapf   bit_position,W
       andlw   0x0F
       addlw   bit_array
       movwf   FSR



{Quote hidden}

Ok, using the same bit_position allocation approach. (xxxx.yyyz)

       movlw   1
       btfsc   bit_position,2  ;y.1
       movlw   4
       movwf   mask

       btfsc   bit_position,1  ;y.0
       addwf   mask,F

       btfsc   bit_position,3  ;y.2
       swapf   mask,F



>   ; now set or clear the bit
>
>     movf   mask,w
>     iorwf  indf,f         ; Assume we're setting.
>     btfss  new_state,0
>      xorwf mask,w         ; assumption was wrong


This point I'm admiring with Scott trick. (I guess it has been grown
from vertical math ? ;) Only one correction, final xorwf should be done
to indf as well I guess.

       movfw   mask
       iorwf   INDF,F
       btfss   bit_position,0  ;we can use z for this why not?
       xorwf   INDF,F

WBR Dmitry.

PS. Last time we have played with vertical math I've done small table
   for myself to discover bool operation combinations. Here it is.
   Use it as is probably it has errors inside.

-----

part 2 909 bytes content-type:text/plain; charset=us-ascii;
(decoded 7bit)

A=!a , B=!b

;1.(a|b)^b=a&B
;2.(a^b)|b=a|b
;3.(a&b)^b=A&b
;4.(a^b)&b=A&b
;5.(a|b)&b=b
;6.(a&b)|b=b

;7.(A|b)^b=/(a|b)=A&B
;8.(A^b)|b=A|b
;9.(A&b)^b=a&b
;A.(A^b)&b=a&b
;B.(A|b)&b=b
;C.(A&b)|b=b

;D.(A|b)^a=A|B
;E.(A^b)|a=a|B
;F.(A&b)^a=a|b
;G.(A^b)&a=a&b
;H.(A|b)&a=a&b
;I.(A&b)|a=a|b

;J.(a|b)^A=a|B
;K.(a^b)|A=A|B
;L.(a&b)^A=A|b
;M.(a^b)&A=A&b
;N.(a|b)&A=A&b
;O.(a&b)|A=A|b

+--+---+------+-+---------+------+------+
|ab||&^|123456|A|[7"8]9ABC|DEFGHI|JKLMNO|
+--+---+------+-+---------+------+------+
|00|000|000000|1|111100000|110000|111001|
|01|101|011111|1|100110011|101001|011111|
|10|101|110000|0|000000000|111001|110000|
|11|110|010011|0|101101111|011111|101001|
+--+----------+-+---------+------+------+

[=/a|b
"=/a^b=/(a^b)
]=/a&b
<=/a|b


part 3 142 bytes
--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@173458 by H.P. de Vries

flavicon
face
This is not related to the thread, but I'd still like to know :-)

Why do u use
       swapf   bit_position,w
in stead of
       movf    bit_position,w          ?

just wondering....

Hans

{Quote hidden}

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@173910 by Dmitry Kiryashov

flavicon
face
Scott Dattalo wrote:

> This'll give 2-cycle sampling per bit. There's a way to improve this to 1-cycle
> resolution, but you're limited to 15 bits. Anyone care to guess how?
>
> Scott

If I suggest it right way it will make all the port unusable for other
purposes ;)
Source is located in bit.0 for instance. tris.0 is input others for
output.
Probably will not work on very fast speed (Scenix?)

       rlf     port,F  ;do it 7 times

       rlf     port,W  ;get 8 samples into W

       rlf     port,F  ;do it 8 times
                       ;will have one more 8 samples
                       ;in carry,port.7..1

Why 15 ? ;)

WBR Dmitry.

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@174448 by Dmitry Kiryashov

flavicon
face
Cause it's easy to change bit position like

       movlw   offset<<1
       addwf   bit_position,F  ;or sub from it

instead of having deal with two separate variables.

WBR Dmitry.


"H.P. de Vries" wrote:
{Quote hidden}

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@175041 by Scott Dattalo

face
flavicon
face
On Wed, 19 Jul 2000, Dmitry Kiryashov wrote:

{Quote hidden}

You're right. I forgot about that damn carry bit again.

BTW, you can get more bits by tying the input to more than one I/O port. But
this is big waste of I/O pins...

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@181557 by Effect Ulit

flavicon
face
Scott Dattalo <scottspamKILLspamDATTALO.COM> said:

> > >shift in 90 bits

<++++++++++++++++++++++++++++++++++>

> btw, I'm not sure what Chris's application is, but I once had a similar
> requirement. For me, I needed to sample a stream as fast as possible. For an
> arbitrary length (but constrained by the PIC's memory) arrary of bits, you
can
{Quote hidden}

cycle
> resolution, but you're limited to 15 bits. Anyone care to guess how?
>
> Scott


 Ill take a guess, but I havent tried this myself, I would guess because a
16bit timer (such as a 16F876 TMR1) has its high and low bytes linked that
possibly shifting bits into it using rrf/rlf (while your signal to be sampled
is being input to the T1CKI input) would enable you to get a 1 cycle sampling
resolution. But I would have thought you could get 16 samples still, how did
you figure only 15?

Dean  [Effect]

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\18@182811 by Dmitry Kiryashov

flavicon
face
Agreed. Too expensive serial shift register ;)

> BTW, you can get more bits by tying the input to more than one I/O port. But
> this is big waste of I/O pins...

WBR Dmitry.

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

2000\07\19@031933 by Ries van Twisk

flavicon
face
Hi,

sometimes the bestway to rotate is just don't rotato but instead using pointers or a index to the right byte in a array and then bitmask it out. This is a fearly simple technique at pritty fast. Depenind on the type of application ofcourse.
You have to excuse me if I'm totally off, I didn't follow the thread from the beginning


Ries

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

2000\07\19@042047 by Michael Rigby-Jones

flavicon
face
{Quote hidden}

Superb, I wish my brain worked that well.  I never seem to consider using
XOR, I have OR and AND far to firmly embedded into my boolean logic lobe :o)

Just one thing, I think the btfsc should really be a btfss (you wish to
perform the xor if new_state is zero).

This is one of those tricky functions that seems very hard to optimize in C.
Very timely thread though, I need to do something very similar in a project
I'm working on the moment.

Regards

Mike

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

2000\07\19@043122 by Michael Rigby-Jones

flavicon
face
I tried to use Scotts code as inline asm in HiTech, but you need to do some
dubious bodging to make it work due to the way to compiler passes single
chars.  However, this "hybrid" compiles down to 20 words including return.


void set_bit(unsigned char new_state)
{
       bitarray[byteptr] |= bitmask;
       if(new_state)
               bitarray[byteptr] ^= bitmask;

#asm
       clrc
       rlf     _bitmask,w
       rlf     _bitmask,f
       btfsc   _bitmask,0
       incf    _byteptr
#endasm

}


Cheers

Mike
> {Original Message removed}

2000\07\19@163727 by Peter L. Peres

picon face
>> c0 = input_carry;
>> for(i=LENGTH;i>0;--i) {
>>   *p++ = ((c1 = (*p & 0x80)) << 1) + c0;
>>   c0 = c1;
>> }
>
>this doesn't. It looks like this'll only write one bit to each byte.

I think that it works ;-), excepting for the oops with c1 inside the
assignment. Ought to be:

c0 = input_carry;
for(i=LENGTH;i>0;--i) {
 c1 = *p & 0x80;
 *p++ = (*p << 1) + c0;
 c0 = c1;
}

It rotates the shift register stored in the vector up by 1 bit (left).

I gave 2 solutions because 'rotating' is ambiguous in meaning. It could be
rotating bits, a matrix, or some other usual target (like serial data).

Peter

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

2000\07\19@173359 by Dmitry Kiryashov

flavicon
face
Can you illustrate your suggestion with code?
Looks very sophisticated but unrealizable for me.
It has to be _1_clock_ per sample of course.

Dmitry.

Effect Ulit wrote:
{Quote hidden}

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

2000\07\19@174019 by Peter L. Peres

picon face
>15 bit fast sampler (1T/cyc)

Ok, how ? 2T/cyc is easy, but 1T/cyc ? What artifice are you using ?

The only 1T know is the hard wired rotate on a byte when all the other
bits are unused, storing 9 bits. Like:

rrf     PORTA,w
rrf     PORTA,f
rrf     PORTA,f
...

assuming the input is in PORTA.0 and all the other PORTA bits are unused
and wired as outputs, and that they are implemented of course.

Is this what you meant ? ;-)

Peter

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

More... (looser matching)
- Last day of these posts
- In 2000 , 2001 only
- Today
- New search...