Searching \ for '[PIC]: yet another algorithm challange' 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: 'yet another algorithm challange'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: yet another algorithm challange'
2001\01\10@131911 by Dave Bell

flavicon
face
I've really enjoyed the challanges posted lately, and picked up some good
coding ideas from them. Here is one I had almost decided to do in external
hardware. Maybe some of the gurus here can help me find an efficient way
of doing it in software!

I have a PIC (16F873 or 7) generating a synchronous (clock + data) data
stream through the on-board USART. There are two odd formats I need to
support in feeding out the variable data: Given an input byte, I need to
"stretch" the data bits by 2X or 6X, producing 2 or 6 bytes of output.

For example, in 2X mode, '0xA1' would translate to '0xCC 0x03', or in
6X mode, to '0xFC 0x0F 0xC0 0x00 0x00 0x3F'. I planned on implementing the
conversion so that it output the bytes to a software FIFO that I would
manage, as I pulled bytes out to transmit.

Obviously, a full byte-in, bytes-out lookup table would be horrendously
big and inefficient of RAM or ROM. Bit-by-bit seems like a little slow,
even in ASM (mainly coding in C, but inline ASM or functions where
needed). Possibly a hybrid lookup of bit pairs or quads, but I was getting
all tied up in trying to handle the loops and differential shifting...

I'd very much appreciate any suggestions!

Dave Bell

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email spam_OUTlistservTakeThisOuTspammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@133338 by Drew Vassallo

picon face
>For example, in 2X mode, '0xA1' would translate to '0xCC 0x03', or in
>6X mode, to '0xFC 0x0F 0xC0 0x00 0x00 0x3F'. I planned on implementing the
>Obviously, a full byte-in, bytes-out lookup table would be horrendously
>big and inefficient of RAM or ROM.

Interesting, because a lookup table would be only 15 lines by my
calculations for 2x mode.  1 byte returned for each nibble 0-F.  6x is
another story, 3 bytes per nibble, but maybe that could be simplified.
Maybe using the 2x table in a clever way could get you what you need for the
6x mode.  It is a neat problem.

--Andrew


_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email .....listservKILLspamspam@spam@mitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@142440 by Bob Ammerman

picon face
Simple idea for 6x mode:

   movlw  0                ; start output byte 6
   btfsc    inval,0
   iorlw    0x3F

   btfsc    inval,1
   iorlw    0xC0
   movwf  out6

   movlw  0                ; start output byte 5
   btfsc    inval,1
   iorlw    0x0F

   btfsc    inval,2
   iorlw    0xF0
   movwf out6

   etc.
   etc.

Rather long, but quite fast and quite simple.

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservspamKILLspammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@145841 by Drew Vassallo

picon face
> >Interesting, because a lookup table would be only 15 lines by my
> >calculations for 2x mode.  1 byte returned for each nibble 0-F.  6x is
> >another story, 3 bytes per nibble, but maybe that could be simplified.
>
>How would that look, in code? I've seen the PIC idiom for lookup table
>that has a branch at the start, and N occurrances of RETLW xxx, but
>can't find an example at hand. Is this what you mean?

For 2x, this would be (and yes, it could probably be more elegant):

;;Result of 2x original byte is in Converted_Number (LSB)
;; and Converted_Number + 1 (MSB)
CBLOCK 0x0C
 Base_Number
 Converted_Number:2
ENDC

 movf Base_Number, w    ; in your example, "0xA1" moves to W
 swapf Base_Number, f   ; force "A" to lower nibble
 andlw 0x0F             ; Mask off the upper nibble
 call Get_2x_Conversion
 movwf Converted_Number ; dump off lower byte
 movf Base_Number, w
 andlw 0x0F             ; mask off the upper nibble
 call Get_2x_Conversion
 movwf Converted_Number + 1  ; dump off upper byte

Get_2x_Conversion
;; Conversion is 0->0, 1->3, 2->C, 3->F for each bit pair
;; Make sure you watch PCLATH and compensate accordingly
  addwf PCL
dt 0x00, 0x03, 0x0C, 0x0F, 0x30, 0x33, 0x3C, 0x3F, 0xC0, 0xC3, 0xCC
dt 0xCF, 0xF0, 0xF3, 0xFC, 0xFF


Actually, now that I did this table on paper, it's obvious that you can just
use bit pairs for lookups (ie., 0, 3, C, and F).  Mask off the unused bits
and send the remaining bit pair to the lower nibble.  This reduces your
table to only 4 lines, but increases your code length.  I'd say you could do
this pretty easily.

--Andrew
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email .....listservKILLspamspam.....mitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@160308 by Drew Vassallo

picon face
>Actually, now that I did this table on paper, it's obvious that you can
>just
>use bit pairs for lookups (ie., 0, 3, C, and F).  Mask off the unused bits
>and send the remaining bit pair to the lower nibble.  This reduces your
>table to only 4 lines, but increases your code length.  I'd say you could
>do
>this pretty easily.

Ok, I had some free time.  This should work, but it's untested.

;;Result of 2x original byte is in Converted_Number (LSB)
;; and Converted_Number + 1 (MSB)
;;Result of 6x original byte is in Converted_Number (LSB), etc...
CBLOCK 0x0C
   Count
   Base_Number
   Converted_Number:6
ENDC

2x_Convert
   movf Base_Number, w    ; in your example, "0xA1" moves to W
   swapf Base_Number, f   ; force "A" to lower nibble
   andlw 0x0F             ; Mask off the upper nibble
   call Get_2x_Conversion
   movwf Converted_Number ; dump off lower byte
   movf Base_Number, w
   andlw 0x0F             ; mask off the upper nibble
   call Get_2x_Conversion
   movwf Converted_Number + 1  ; dump off upper byte

Get_2x_Conversion
;; Conversion is 0->0, 1->3, 2->C, 3->F for each bit pair
;; Make sure you watch PCLATH and compensate accordingly
   addwf PCL
dt 0x00, 0x03, 0x0C, 0x0F, 0x30, 0x33, 0x3C, 0x3F, 0xC0, 0xC3, 0xCC
dt 0xCF, 0xF0, 0xF3, 0xFC, 0xFF

6x_Convert
;; This is a little more difficult, requiring 3 nibbles per bit pair
;; or 3 bytes per original nibble (6 bytes total per original byte).
;; You could keep these 2 methods different, or convert the 2x method to
;; this bit-pair method.
;; 00->000, 01->03F, 10->FC0, 11->FFF
   clrw
   clrf Converted_Number
   clrf Converted_Number+1
   clrf Converted_Number+2
   clrf Converted_Number+3
   clrf Converted_Number+4
   clrf Converted_Number+5
   clrc
   rlf Base_Number
   btfss STATUS, C
   goto Check_6
   movlw 0xFC
   addwf Converted_Number + 5
Check_6
   rlf Base_Number
   btfss STATUS, C
   goto Check_5
   movlw 0x03
   addwf Converted_Number + 5
   movlw 0xF0
   addwf Converted_Number + 4
Check_5
   rlf Base_Number
   btfss STATUS, C
   goto Check_4
   movlw 0x0F
   addwf Converted_Number + 4
   movlw 0xC0
   addwf Converted_Number + 3
Check_4
   rlf Base_Number
   btfss STATUS, C
   goto Check_3
   movlw 0x3F
   addwf Converted_Number + 3
etc... repeat for lower nibble.

I haven't tried this, so you're on your own :)

--Andrew

_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email EraseMElistservspam_OUTspamTakeThisOuTmitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@161556 by Drew Vassallo

picon face
Of course, this could be simplified slightly:

    btfss Base_Number, 7
instead of:
>    rlf Base_Number
>    btfss STATUS, C

>    goto Check_6
>    movlw 0xFC
>    addwf Converted_Number + 5
>Check_6

    btfss Base_Number, 6
Instead of:
>    rlf Base_Number
>    btfss STATUS, C

etc...

I was going to put it into a loop, hence the "rlf", but it never worked out.

--Andrew

_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservspamspam_OUTmitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@170404 by Scott Dattalo

face
flavicon
face
On Wed, 10 Jan 2001, Bob Ammerman wrote:

{Quote hidden}

Another approach that is rather short, but quite slow and complex yet versatile
is to maintain three counters:

  cBitExp   - bit expansion counter
  cBitSnd   - bit in byte to be sent
  cBitCnt   - bit in byte that we are expanding

The idea is that the bytes to be sent are built up a bit-at-a-time.
Here's some sample code off of the top of my head:

init:

   movlw 8          ;8bits/byte
   movwf cBitSnd
   movlw 1
   movwf cBitCnt

   movf  bit_expansion_factor  ;e.g. 2,3, or 6 whatever
   movwf cBitExp

   call  get_next_byte_to_send
   movwf next_byte   ; save a copy here

   return

expand:

   decfsz cBitSnd        ;If we've built up 8 bits
    goto  l1

   movf   next_byte,w    ; then send them out
   call   send_a_byte
   bsf    cBitCnt,3      ;set count to 8 (#bits/byte)

l1:
   clrc                  ;Get the next bit that we
   rlf    byte_to_send   ;want to send by copying the
   btfsc  next_byte,7    ;msb of the source byte into
    bsf   byte_to_send,0 ;the lsb of the destination
                         ;Note that we could bit-bang
                         ;an I/O port right here instead.

   decfsz cBitExp        ;If the expansion counter has
    goto  l2             ;terminated then
                         ;reload it and shift the source
                         ;byte one position

   movf   bit_expansion_factor
   movwf  cBitExp

   rlf    next_byte,f

l2:
   decfsz cBitCnt        ;If we've gone through all 8-bits
    goto  l3             ;of the source
                         ;then get the next byte.
   call   get_next_byte_to_send
   movwf  next_byte      ; save a copy here

   bsf    cBitCnt,3      ;8-bits per byte

l3:
   return                ; or make this a loop

This routine assumes a UART, but could easily be adapted to bit-banging (since
the bytes to send are built a bit-at-a-time). Also, this code works for any
sized expansion - you could even make it one-to-one (or one-to-256).

Scott

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email @spam@listservKILLspamspammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@171621 by Dave Bell

flavicon
face
Thanks to Andrew Vassallo and Bob Ammerman for some quick and detailed
help on my "bit stretcher" algorithms!

Here's what I ended up with for the 6X routine:

//
int   OUT[6];

#byte Out1 = OUT
#byte Out2 = OUT+1
#byte Out3 = OUT+2
#byte Out4 = OUT+3
#byte Out5 = OUT+4
#byte Out6 = OUT+5

int   inval;

void X6(int v)
{
#asm
  movwf    inval

  movlw    0                 // start output byte 6
  btfsc    inval,0
  iorlw    0x3F

  btfsc    inval,1
  iorlw    0xC0
  movwf    Out6

  movlw    0                 // start output byte 5
  btfsc    inval,1
  iorlw    0x0F

  btfsc    inval,2
  iorlw    0xF0
  movwf    Out5

  movlw    0                 // start output byte 4
  btfsc    inval,2
  iorlw    0x03

  btfsc    inval,3
  iorlw    0xFC
  movwf    Out4

// now, repeat for (bit+4) and (byte-3)
  movlw    0                 // start output byte 3
  btfsc    inval,4
  iorlw    0x3F

  btfsc    inval,5
  iorlw    0xC0
  movwf    Out3

  movlw    0                 // start output byte 2
  btfsc    inval,5
  iorlw    0x0F

  btfsc    inval,6
  iorlw    0xF0
  movwf    Out2

  movlw    0                 // start output byte 1
  btfsc    inval,6
  iorlw    0x03

  btfsc    inval,7
  iorlw    0xFC
  movwf    Out1
#endasm
}


Fast (enough), clean (very), and (I think) isochronous to boot...

Dave Bell

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email KILLspamlistservKILLspamspammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@174714 by Drew Vassallo

picon face
>Thanks to Andrew Vassallo and Bob Ammerman for some quick and detailed
>help on my "bit stretcher" algorithms!

You're welcome.

Hmm, I'm assuming that your "Out1" is the MSByte.  If not, you've got things
reversed.  I just never saw the convention "OUT+5" to indicate the LSByte in
a hex long word.  Forgive me if you've got it right, but it just looks odd.

{Quote hidden}

_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email RemoveMElistservTakeThisOuTspammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@180339 by Dave Bell

flavicon
face
Andrew Vassallo wrote:

>Hmm, I'm assuming that your "Out1" is the MSByte.  If not, you've got
>things reversed.  I just never saw the convention "OUT+5" to indicate the
>LSByte in a hex long word.  Forgive me if you've got it right, but it
>just looks odd.

 Actually, I agree; I posted the code as I expanded it from Bob
Ammerman's suggestion. I guess it's a big- vs. little-endian thing.
I may end up reversing it, but it works. I used the same structure to
create a bit doubler, by the way. Not much longer than the lookup table
method, and there's some advantage in readability, to using the same
algorithm for both! I might make a tripler, and compare size/time between
the 6X code and (2X * 3X)... Gut feeling is that 6X is shorter, faster.

Dave Bell

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email spamBeGonelistservspamBeGonespammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@181753 by Bob Ammerman

picon face
----- Original Message -----
From: Dave Bell <TakeThisOuTdbellEraseMEspamspam_OUTTHEBELLS.NET>
To: <RemoveMEPICLISTspamTakeThisOuTMITVMA.MIT.EDU>
Sent: Wednesday, January 10, 2001 5:16 PM
Subject: Re: [PIC]: yet another algorithm challange


{Quote hidden}

You're not likely to find faster.
It is very simple to follow and 'clean'.
It isn't too long.
And yes, it is isochronous.

Sometimes the obvious is what makes the most sense.

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservEraseMEspam.....mitvma.mit.edu with SET PICList DIGEST in the body


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