Long shift register [Archive] - MEL PICBASIC Forum

Joe Rocci

- 15th April 2009, 15:33

I need to make a long shift register with 1000 taps or so. I'd like to be able to clock bits into it at a minimum 10 khz rate. I know how I'd do it in assembler, but I'd really like to implement it in PBP if feasable. Are there any tricks to streamline this process?

Joe

Jerson

- 15th April 2009, 18:34

How about inline assembly enclosed by ASM....ENDASM statements?

Joe Rocci

- 15th April 2009, 18:37

How about inline assembly enclosed by ASM....ENDASM statements?

That would defeat my goal. I wanted to see if I could do it all (or mostly) in PBP.

Thanks

Joe

Chris Barron

- 16th April 2009, 18:27

That would defeat my goal. I wanted to see if I could do it all (or mostly) in PBP.

Thanks

Joe

Are the picbasic commands 'shiftin' and 'shiftout' too slow for you ?

Joe Rocci

- 16th April 2009, 18:48

Are the picbasic commands 'shiftin' and 'shiftout' too slow for you ?

Chris

SHIFTOUT is an I/O function that toggles an output port with the bitwise contents of a data variable. SHIFTIN does the same thing in the other I/O direction.

What I want to do is set up a 'virtual' 1000 tap shift-register in the PIC's memory and be able to clock data through it. It's basically a digital delay line in memory, commonly used for digital signal processing applications. I need to clock it at a well-defined rate and also be able to read any of the 1000 tap points at any time.

It's quite straightforward in assembler, but I wanted to try to incorporate it into an existing PBP program using PBP's ">>" (shift right) and or "<<" (shift left) instructions instead of using assembler. I was hopng someone would tell me there are secret PBP system variables that capture the bits that are shifted OUT of an array variable so they can be shifted back IN to the next variable in the array. This way, a 63-word array could be set up as the 1000-bit shift-register, and bits could be clocked through the 1000 bits as though it were one long shift-register.

Joe

Byte_Butcher

- 16th April 2009, 20:57

Charles Linquis

- 16th April 2009, 21:24

18F parts let you have arrays as large as memory.

Joe Rocci

- 16th April 2009, 21:44

well, I guess that you can only have bit arrays up to 256 elements, but I was thinking something like this..

bigarray var bit[256] 'Large array to hold data
newdata var bit 'newest bit to be shifted in
index var byte

for 0 to 255
bigarray[index] = bigarray[index +1]
next index

bigarray[255] = newdata 'put the newest data bit into the array

Maybe with 4 big arrays you could shift through 1024 steps?
Or have I missed the point entirely...

Byte_Butcher,

I hadn't thought about a bit array. My thinking was stuck on word arrays, ">>" functions, and being able to get the bit that falls out the end of one word and automatically put it into the input of the next word in the array. In assembler. this is almost trivial.

Your idea seems very doable, except that every bit has to be handled individually. I'm concerned about time, since I want to shift all 1000 bits in 100usec or less. Actually, I'd like to do 2000 bits in that time if I could.

Joe

Chris Barron

- 17th April 2009, 18:01

Byte_Butcher,

I hadn't thought about a bit array. My thinking was stuck on word arrays, ">>" functions, and being able to get the bit that falls out the end of one word and automatically put it into the input of the next word in the array. In assembler. this is almost trivial.

Your idea seems very doable, except that every bit has to be handled individually. I'm concerned about time, since I want to shift all 1000 bits in 100usec or less. Actually, I'd like to do 2000 bits in that time if I could.

Joe

Perhaps if you gave a few more clearer details other than you want to make a 1000 byte long virtual bit array. Some explanation about how many of the bits you need to read, how often, if you need to skip any chunks (as in filtering and the application of maths series) It seems that you might not be clear enough answers because yoiur application isn't obvious.

If you can do it in assembler you should, regardless of what esoteric reason you might have for not wanting to do it, life is too short sometimes !

Joe Rocci

- 17th April 2009, 18:32

Perhaps if you gave a few more clearer details other than you want to make a 1000 byte long virtual bit array. Some explanation about how many of the bits you need to read, how often, if you need to skip any chunks (as in filtering and the application of maths series) It seems that you might not be clear enough answers because yoiur application isn't obvious.

-----------------

Actually Chris......

I really don't know what else I can proactively offer in the way of explanation, but if you'd like to help out, feel free to ask questions.

If you re-read the thread, I think you'll find pretty clear explanations of what I'm trying to do:
1) I need a 1000 tap shift register for a DSP-like application
2) I need to be able to read the state of any or all bits
3) I want to clock things into it at about a 10 khz rate
4) I'm looking for one of the PBP experts in the group to tell me whether the "<<" shift operation results in setting any system variables that can be clocked into the next word in an array.

BTW, I really got a kick out of this part:

"If you can do it in assembler you should, regardless of what esoteric reason you might have for not wanting to do it, life is too short sometimes !" Sort reminds me of the old sales cliche that says "If you can find it cheaper somewhere else, buy it!" Oh yeah...uhhh, sure. Thanks

Joe

Bruce

- 17th April 2009, 19:15

Pretty much anything you can do in assembler you can do with PBP, but a little more
information of what you're trying to do really would help.

I.E. are you loading a word var with a 16-bit value, then trying to shift this up x number of
bits into your array, or are you 'clocking' bits into an I/O-pin, and trying to stash these into
your array?

I see a boat load of options for something like this, but I'm not getting a very clear picture
of exactly what you need on this one.

If you post the simple assembler example you have working, I'll bet we can come up with a
simple PBP BASIC equivalent.

I can't say if a PBP example can beat your assembler example without seeing your .asm
version as for timing, but I suspect it would be easier to read...;o}

Joe Rocci

- 17th April 2009, 19:25

Bruce,

Here's a 'brute force' implementation of a long shift register in assembler for a 16F628A:

; Move shift register contents left one
;
bcf STATUS,C ; Clear Carry bit to prevent any carry in
rlf SR8,f ;
rlf SR16,f ;
rlf SR24,f ;
rlf SR32,f ;
rlf SR40,f ;
rlf SR48,f ;
rlf SR56,f ;
rlf SR64,f ;
rlf SR72,f ;
rlf SR80,f ;
rlf SR88,f
rlf SR96,f
rlf SR104,f
rlf SR112,f
rlf SR120,f
rlf SR128,f
rlf SR136,f
rlf SR144,f
rlf SR152,f
rlf SR160,f
rlf SR168,f
rlf SR176,f
rlf SR184,f
rlf SR192,f
rlf SR200,f
rlf SR208,f
rlf SR216,f
rlf SR224,f
rlf SR232,f
rlf SR240,f
rlf SR248,f
rlf SR256,f
rlf SR264,f
rlf SR272,f
rlf SR280,f
rlf SR288,f
rlf SR296,f
rlf SR304,f
rlf SR312,f
rlf SR320,f
rlf SR328,f
rlf SR336,f
rlf SR344,f
rlf SR352,f
rlf SR360,f
rlf SR368,f
rlf SR376,f
rlf SR384,f
rlf SR392,f
rlf SR400,f
rlf SR408,f
rlf SR416,f
rlf SR424,f
rlf SR432,f
rlf SR440,f
rlf SR448,f
rlf SR456,f
rlf SR464,f
rlf SR472,f
rlf SR480,f ;
rlf SR488,f ;
rlf SR496,f ;
rlf SR504,f ;

Bank1 ; 65 Switch to next set of registers in Bank1

; btfsc STATUS,C
; bsf SR512,0
rlf SR512,f ; 66
rlf SR520,f
rlf SR528,f
rlf SR536,f
rlf SR544,f
rlf SR552,f
rlf SR560,f
rlf SR568,f
rlf SR576,f
rlf SR584,f
rlf SR592,f
rlf SR600,f
rlf SR608,f
rlf SR616,f
rlf SR624,f
rlf SR632,f
rlf SR640,f
rlf SR648,f
rlf SR656,f
rlf SR664,f
rlf SR672,f
rlf SR680,f
rlf SR688,f
rlf SR696,f
rlf SR704,f
rlf SR712,f
rlf SR720,f
rlf SR728,f
rlf SR736,f
rlf SR744,f
rlf SR752,f
rlf SR760,f
rlf SR768,f
rlf SR776,f
rlf SR784,f
rlf SR792,f
rlf SR800,f
rlf SR808,f
rlf SR816,f
rlf SR824,f
rlf SR832,f
rlf SR840,f
rlf SR848,f
rlf SR856,f
rlf SR864,f
rlf SR872,f
rlf SR880,f
rlf SR888,f
rlf SR896,f
rlf SR904,f
rlf SR912,f
rlf SR920,f
rlf SR928,f
rlf SR936,f
rlf SR944,f
rlf SR952,f
rlf SR960,f
rlf SR968,f
rlf SR976,f
rlf SR984,f ;
rlf SR992,f ;
rlf SR1000,f ;127
Bank0 ;9 Back to Bank 0
return ; Back to calling routine

Thanks
Joe

Joe Rocci

- 17th April 2009, 19:54

....I should have explained that the routine is entered with the current input bit in SR8, bit 0.
Joe

Chris Barron

- 17th April 2009, 21:14

....I should have explained that the routine is entered with the current input bit in SR8, bit 0.
Joe

no need Joe, that bit was very obvious.

Can I ask you again (at the risk of receiving more needless sarcasm ?), how many bits do you need to access, and how often ? Is your only interest in the first and last bit, or just even the last bit which is being output. Or when you specified a 1000 tap shifter was it because you need random access to the contents of every tap at all times ? I can think of as many times I would need access to all bits, as I can think of times I might only be interested in every 100th bit (sample rate dependent)

How many program variables will you need to do your processing with (do you have enough if you have all those bytes tied up us a shift register ? As has been pointed out, the 18F parts are much more user friendly where memory addressing is concerned, and you can write program space and use your data space for program variables. If you aren't going to do any processing within the pic but just have it rotate a 1,000 bit buffer endlessly yoiu probably have enough memory and have probably written the near ideal solution (in terms of processing time at least )already.

Good luck
Chris

Joe Rocci

- 17th April 2009, 21:39

Chris Barron

- 17th April 2009, 22:26

Chris,

For now, I only need to compare the first and last bits each time I update the SR. In the future, I might wat to look at intermediate bits. I can pick a PIC (say that a dozen times!!) with as much memory as I need, even an 18F part if that's what it takes, so no prob there. I think the primary limitation on how much other processing I can do will ultimately be determined by how much throughput is left (time). There are a few other tasks having to do with data acquisition (input)and disposal of the results (output), but they're minor as of now. Of course, the more horsepower that is left after the important job is done, the more 'feature creep' I can build in.

FYI, the application is a 'stabilizer' for a voltage controlled oscillator, similar to a PLL. It works by sampling the instantaneous oscillator state with a precise time base, and comparing the present state with the state "n" samples ago. The result of the sampling and comparison process is used to pump the oscillator fine-tuning voltage up or down until the oscillator locks onto the nearest 'comb' point. The spacing of comb points is determined by the sampling rate and the number of samples stored in the SR. It has the advantages of fine tuning resolution combined with fast acquisition and tracking speed, parameters that are usually mutually exclusive in a PLL synthesizer.

Thanks

Jjoe

That sounds very very cool !

Just a look at the processing time......(your minimum execution time assembly example)

2000 bits = 250bytes = 250 RLF's = 250 clock cycles

At 4MHz (crystal) , clock cycles = 1MHz, shift frequency = 4kHz (1MHz/250)

(There's an obvious connection here between shift frequency and crystal frequency due to the nice numbers), therefore a 10kHz shift frequency requires a 10MHz crystal.
20MHz crystal = 20kHz shift frequency

Okay, now to prove myself wrong that you had already written the quickest routine !

Moving one bit at a time is consuming 250 clock cycles (8 bits = 2000 clock cycles) , and because you only need the first and last bits why not move the in between registers 1 byte at a time, but still shift in the first bit and out the last bit by using a pair of end buffers

Data moving from left to right....
(Every iteration, 2 shifts)
SHIFTS: ] --8.bit input buffer-- + --8.bit output buffer--

After every 8 shifts, move bytes in between buffers
MOVES: ] [SR1000>output_buffer][sr992>SR1000].....[input_buffer>SR8]

iteration 1 : 2 shifts + 4 loop counter maintenance
iteration 2: ditto
.
.
.
.
.
iteration 8: 252 MOVFF's + 2 shifts + 4 loop counter maintenance

Estimated overhead for 8 bits = (7 * 6) + (252 +2 + 4) = 300 clock cycles

Using the first method you have a fixed length execution time of 250 clocks per iteration, and using the second method you have one long execution cycle in every 8 (but it has a much lower processing overhead), and averages about 32 cycles per iteration , leaves more time for processing.

Chris

Now, for each iteration you have 6 clock cycles for shifts, and 250/8 MOVEs, which if yoiu use a PIC 18F and the MOVFF command (1 clock cycle) completes in about 50 clock cycles average (excluding loop counter overehad)

iteration 1 : 2 shifts + 4 loop counter maintenance
iteration 2: ditto
.
.
.
.
.
iteration 8:

Darrel Taylor

- 17th April 2009, 22:53

I think it would be easier to create a "Circular" buffer of bits, much like you would for a byte sized serial buffer.

Nothing actually shifts, only the pointers to the data change.

Joe Rocci

- 18th April 2009, 00:47

Darrel,

Can you post an example of how you'd implement that in PBP?

Thanks

Joe

Joe Rocci

- 18th April 2009, 01:04

That sounds very very cool !

Just a look at the processing time......(your minimum execution time assembly example)

2000 bits = 250bytes = 250 RLF's = 250 clock cycles

At 4MHz (crystal) , clock cycles = 1MHz, shift frequency = 4kHz (1MHz/250)

Chris,

I'm using a 20mhz crystal, so cycle time is 200nsec. My ~260 cycle assembler SR should thus take about 52 usec, if my math is correct. I was planning to use the crystal to run a Timer1 timer to generate prescise 100usec interrupts. If I sample at 100usec (10khz), that leaves about 48usec to do 'other things'. That would do it in the assembler version.

The big question, is there a PBP alternative that would be fast enough, and in fact leave a little time for other things?? I suspect not, and that I'll end up with a hybrid solution, using assembler for the SR, and PBP for the 'other things'.

Joe

Joe

Darrel Taylor

- 18th April 2009, 05:13

Darrel,
Can you post an example of how you'd implement that in PBP?
Thanks
Joe

I can.

First let me say that ASM is a very BIG part of PicBasic Pro.
It's the Glue that binds everything together.

Ignoring ASM, and pretending it's not part of PBP simply deprives you of the easiest ways to do exactly what you want, without having to find some basackwards way to get around your problems.

OK, now that the commercials over ...<hr>
20uS shift @ 40Mhz. With 18F's ONLY!
Using a large Circular buffer.
Variable length Shift up to 2032 bits.

Basic Language ONLY ...

'************************************************* **************************
'* Name : 1000Bits.pbp *
'* Author : Darrel Taylor *
'* Date : 4/17/2009 *
'* Version : 1.1 *
'* Notes : Requires an 18F *
'* : 20uS ~shift at 40Mhz, 40uS @ 20Mhz *
'************************************************* **************************
@ __CONFIG _CONFIG1H, _OSCS_OFF_1H & _HSPLL_OSC_1H
DEFINE OSC 40

CLEAR

BufferBits CON 1000 ; max 2032
BufferBytes CON BufferBits / 8 + 1 ; number of BYTEs required for buffer
Buffer VAR BYTE[BufferBytes] ; The Buffer Array
ShiftSize VAR WORD ; Variable sized Shift at run-time
INptr VAR WORD ; Points to the IN bit of the array
OUTptr VAR WORD ; Points to the OUT bit of the array
BuffPtr VAR BYTE ; Points to the BYTE in the buffer
BitPtr VAR BYTE ; Points to the BIT in the byte
TempB VAR BYTE ; temporary byte variable
BITin VAR PORTB.0 ; The BIT being shifted IN
BITout VAR PORTB.1 ; The BIT being shifted OUT

ShiftSize = 800 ; Any Size - up to BufferBits
GOSUB ResizeBuffer ; setup the Pointers
GOSUB ClearBuffer ; Set buffer to all 0's
INPUT BITin ; Input pin
LOW BITout ; Output pin

;---------------------------------------------------------------------------
Main:
GOSUB ShiftBits
PAUSEUS 80
GOTO Main

;---------------------------------------------------------------------------
ShiftBits:
INptr = INptr + 1 ; Increment IN pointer
IF INptr.LowByte = ShiftSize.LowByte Then ; IF past end of buffer?
IF INptr.HighByte = ShiftSize.HighByte Then
INptr = 0 ; Wrap to beginning
ENDIF
ENDIF
OUTptr = OUTptr + 1 ; Increment OUT pointer
IF OUTptr.LowByte = ShiftSize.LowByte Then ; IF past end of buffer?
IF OUTptr.HighByte = ShiftSize.HighByte Then
OUTptr = 0 ; Wrap to beginning
ENDIF
ENDIF

; --- Put new BIT into the Buffer ------------
BuffPtr = INptr >> 3 ; Which BYTE in the buffer
BitPtr = INptr & %111 ; Which BIT in the byte
TempB = Buffer(BuffPtr) ; retrieve the byte
TempB.0(BitPtr) = BITin ; store the bit
Buffer(BuffPtr) = TempB ; put byte back in buffer

; --- Get old BIT from the Buffer ------------
BuffPtr = OUTptr >> 3 ; Which BYTE in the buffer
BitPtr = OUTptr & %111 ; Which BIT in the byte
TempB = Buffer(BuffPtr) ; retrieve the byte
BITout = TempB.0(BitPtr) ; output the BIT
RETURN

;---------------------------------------------------------------------------
ResizeBuffer:
ShiftSize = ShiftSize MIN BufferBits ; limit to buffer size
INptr = ShiftSize - 1 ; buffer starting point
OUTptr = 0 ; out bit starts at 0
RETURN

;---------------------------------------------------------------------------
ClearBuffer:
FOR TempB = 0 to BufferBytes - 1
Buffer(TempB) = 0
NEXT TempB
RETURN

Chris Barron

- 18th April 2009, 19:14

Chris,

I'm using a 20mhz crystal, so cycle time is 200nsec. My ~260 cycle assembler SR should thus take about 52 usec, if my math is correct. I was planning to use the crystal to run a Timer1 timer to generate prescise 100usec interrupts. If I sample at 100usec (10khz), that leaves about 48usec to do 'other things'. That would do it in the assembler version.

The big question, is there a PBP alternative that would be fast enough, and in fact leave a little time for other things?? I suspect not, and that I'll end up with a hybrid solution, using assembler for the SR, and PBP for the 'other things'.

Joe

Joe

I would go for the 100uS interrupt and do the basic shifting in the ISR. every 8th bitshift do a single byte pointer reallocation. That would be the circular buffer. You could trim it down to 10 clock cycles per interrupt, and every 8th interrupt 20 clock cycles.

Picbasic, like C, and most other high level languages, are macro systems for assembler, of particular flavours depending on the main application. I consider myself lucky that I learned assembler first before any other langauge (with the exception of the file handler friendly OPL on Psion PDA's)