headers
Ed Sutton | 8 May 17:57

[PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Are there other ways to implement a divide by a 14 constant other than 
cycle-chewing subtraction loops?

I want to use the PIC16F flash consisting of 14-bit words to store 8-bit 
data.  I can implement the multiply-by-8 as a shift.  The crux of the 
problem is basically the divide by a constant of 14.

Pseudo Code ( actual code will likely be assembly )

wordOffset = 8*byteOffset / 14;          // The integer result 
wordBitOffset = 8*byteOffset % 14;   // The remainder result

Patterns:

The 14-bit words and 8-bit data have a common multiple of 56.
The wordBitOffset pattern { 0,8,2,10,4,12,6 } repeats every 7-bytes.
I can't see a solution but it is an interesting puzzle.

Thanks in advance for any tips or suggestions,

-Ed

--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
Gordon Williams | 8 May 18:23

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access8-bit data in PIC16F flash )

Did you look at:

http://www.piclist.com/techref/piclist/codegen/constdivmul.htm

It works quite well.

Regards,

Gordon Williams

----- Original Message ----- 
From: "Ed Sutton" <esutton <at> engius.com>
To: <piclist <at> mit.edu>
Sent: Thursday, May 08, 2008 11:59 AM
Subject: [PIC] - Need fast divide by 14 constant routine? ( Random
access8-bit data in PIC16F flash )

: Are there other ways to implement a divide by a 14 constant other than
: cycle-chewing subtraction loops?
:
: I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
: data.  I can implement the multiply-by-8 as a shift.  The crux of the
: problem is basically the divide by a constant of 14.
:
: Pseudo Code ( actual code will likely be assembly )
:
: wordOffset = 8*byteOffset / 14;          // The integer result
: wordBitOffset = 8*byteOffset % 14;   // The remainder result
:
:
(Continue reading)

Permalink | Reply |
headers
Tamas Rudnai | 8 May 18:34

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Hi Ed,

Could you explain a bit more what you are trying to do? 14 bit words means
each address addresses 14bit words, other words you do not need division or
whatever to pick up one byte. Or you are trying to split up the bytes to bit
streams to compress the data (and reading the flash with eeprom reading
method)?

Tamas

On Thu, May 8, 2008 at 4:59 PM, Ed Sutton <esutton <at> engius.com> wrote:

> Are there other ways to implement a divide by a 14 constant other than
> cycle-chewing subtraction loops?
>
> I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
> data.  I can implement the multiply-by-8 as a shift.  The crux of the
> problem is basically the divide by a constant of 14.
>
> Pseudo Code ( actual code will likely be assembly )
>
> wordOffset = 8*byteOffset / 14;          // The integer result
> wordBitOffset = 8*byteOffset % 14;   // The remainder result
>
>
> Patterns:
>
> The 14-bit words and 8-bit data have a common multiple of 56.
> The wordBitOffset pattern { 0,8,2,10,4,12,6 } repeats every 7-bytes.
> I can't see a solution but it is an interesting puzzle.
(Continue reading)

Permalink | Reply |
headers
David VanHorn | 8 May 19:06

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Multiply by 9, then divide by 128?  (close..)

It's not really apparent what you're trying to optimize.
I had a problem once where I was trying to do bearing calculations,
and I did NOT want to do 16 bit math, and I was able to do it in 8
bit, forsaking degrees for "dilberts" where there are 256 dilberts of
angle in a circle
--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
Mark Scoville | 8 May 20:31

RE: [PIC] - Need fast divide by 14 constant routine? ( Random access8-bit data in PIC16F flash )

Or mult by 18, then divide by 256. Will not be any more accurate than
*9/128, but Divide by 256 is simply dropping the least sig byte.

<Mumbling to self> now I gotta buy a new calculator that has "dilberts" :-)

-- Mark

> -----Original Message-----
> From: piclist-bounces <at> mit.edu [mailto:piclist-bounces <at> mit.edu]On Behalf
> Of David VanHorn
> Sent: Thursday, May 08, 2008 12:06 PM
> To: Microcontroller discussion list - Public.
> Subject: Re: [PIC] - Need fast divide by 14 constant routine? ( Random
> access8-bit data in PIC16F flash )
>
>
> Multiply by 9, then divide by 128?  (close..)
>
> It's not really apparent what you're trying to optimize.
> I had a problem once where I was trying to do bearing calculations,
> and I did NOT want to do 16 bit math, and I was able to do it in 8
> bit, forsaking degrees for "dilberts" where there are 256 dilberts of
> angle in a circle
> --
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>
>
(Continue reading)

Permalink | Reply |
headers
William "Chops" Westfield | 9 May 01:42

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access8-bit data in PIC16F flash )


On May 8, 2008, at 11:31 AM, Mark Scoville wrote:
> Or mult by 18, then divide by 256. Will not be any more accurate than
> *9/128, but Divide by 256 is simply dropping the least sig byte.
>>
>> Multiply by 9, then divide by 128?  (close..)

Not close enough.  Fails about 50 times over the range of 1..256, and is
off by more than 1 by starting at 910.

BillW

--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
Spehro Pefhany | 8 May 19:10

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Quoting Ed Sutton <esutton <at> engius.com>:

> Are there other ways to implement a divide by a 14 constant other than
> cycle-chewing subtraction loops?
>
> I want to use the PIC16F flash consisting of 14-bit words to store 8-bit
> data.  I can implement the multiply-by-8 as a shift.  The crux of the
> problem is basically the divide by a constant of 14.
>
> Pseudo Code ( actual code will likely be assembly )
>
> wordOffset = 8*byteOffset / 14;          // The integer result
> wordBitOffset = 8*byteOffset % 14;   // The remainder result

Since you need both the quotient and the remainder, and cannot tolerate
any error in either, I think a conventional shift-and-subtract  
division routine
will work pretty well and will generate both numbers at once. Did you  
check the PICLIST code library?

Best regards,
Spehro Pefhany
-- 
"it's the network..."                          "The Journey is the reward"
s...@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
(Continue reading)

Permalink | Reply |
headers
Jinx | 8 May 23:40

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Ed, I have an 16F877 application that **has** to be accurate. Much
of program memory plus external flash is bit-mapped in a chance game

I had a look at some shift-type routines, but found that the remainder
was not always accurate, even with a 0.5 test. Perhaps not quite true,
but the more bits you use for the division, the more bits are in the
remainder fraction, and by the time you work through those it would
sometimes have been quicker to do the division the by subtraction

Can't describe the game itself in detail, but basically there are three
very large bit tables, all the same length. To access a number in each
eg 9,473 => 9473/14 => 676 whole bytes, remainder indicates the
position in the 677th byte

So, anyway, this isn't fast, but it's accurate. I'm sure it could be made
a little faster but it's sufficient for my application as is

Hope it helps (you or someone)

;================================================
;        Divide by subtraction, 
;        Slow but guaranteed accurate remainder
;================================================

div14    bank0
         bcf     res_eq0      ;result=0 flag
         movlw   0x0e         ;divisor
         movwf   dsorl
         clrf    dsorm
         clrf    dsorh
(Continue reading)

Permalink | Reply |
headers
"Ruben =?iso-8859-1?q?J=F6nsson=22?= | 9 May 09:16

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

> 
> Can't describe the game itself in detail, but basically there are three
> very large bit tables, all the same length. To access a number in each
> eg 9,473 => 9473/14 => 676 whole bytes, remainder indicates the
> position in the 677th byte
> 
> So, anyway, this isn't fast, but it's accurate. I'm sure it could be made
> a little faster but it's sufficient for my application as is
> 

A shift-subtract division is also accurate. Always.

In your case you can multiply the dividend with 256 (just one more byte of 
0's), run the shift-subtract division until you got 3 bits in the quotient 
fraction part, right shift the 3 upper bits 5 times (to get them to the 3 lower 
bits) and then you have the byte position in the integer quotient part and the 
bit offset in the shifted fraction remainder part.

/Ruben
<http://www.rjjournal.net>
==============================
Ruben Jönsson
AB Liros Electronic
Box 9124, 200 39 Malmö, Sweden
TEL INT +46 40142078
FAX INT +46 40947388
ruben <at> pp.sbbs.se
==============================

--

--
(Continue reading)

Permalink | Reply |
headers
Jinx | 10 May 01:29

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access8-bit data in PIC16F flash )

> A shift-subtract division is also accurate. Always.

I have no doubt you're right Ruben, you have to be. Whether it
was the method I chose, I did something wrong or what, don't
know, but I did get results that I couldn't be confident in (and
more importantly should not happen in front of the client). These
days I *would* make shift-subtract division work. At the time,
the /14 was an important, but small, part of a quite large project
and the push was on to get it up and running, so you go with
what works first, even if it ain't pretty

--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
Harold Hallikainen | 9 May 21:39

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

There's a nice code generator for multiply and divide by a constant at
http://www.piclist.com/techref/piclist/codegen/constdivmul.htm .

Harold

-- 
FCC Rules Updated Daily at http://www.hallikainen.com - Advertising
opportunities available!
--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
William "Chops" Westfield | 10 May 02:14

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )


On May 9, 2008, at 12:39 PM, Harold Hallikainen wrote:
> There's a nice code generator for multiply and divide by a constant at
> http://www.piclist.com/techref/piclist/codegen/constdivmul.htm .

The algorithm it produces does not seem to work very well in this  
case, even if I use extra bits to produce less error in intermediate  
steps.
I'm having trouble grasping why not :-(

It says:

; ALGORITHM:
; Clear accumulator
; Add input / 16 to accumulator
; Add input / 128 to accumulator
; Add input / 1024 to accumulator
; Add input / 8192 to accumulator
; Add input / 65536 to accumulator

The first error is at 14.  (ALL the factors are obviously zero.)
Even if I do:

	(i/2 + i/16 + i/128 + i/1024 + i/8192) / 8

The first error is still at 14.

Going at it backwards isn't going to work either:
	x/14 = x/8 - x/32 - x/64 - x/256...
(Continue reading)

Permalink | Reply |
headers
John Coppens | 10 May 03:27

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

On Fri, 9 May 2008 17:14:47 -0700
"William \"Chops\" Westfield" <westfw <at> mac.com> wrote:

> 
> On May 9, 2008, at 12:39 PM, Harold Hallikainen wrote:
> > There's a nice code generator for multiply and divide by a constant at
> > http://www.piclist.com/techref/piclist/codegen/constdivmul.htm .
> 
> The algorithm it produces does not seem to work very well in this  
> case, even if I use extra bits to produce less error in intermediate  
> steps.
> I'm having trouble grasping why not :-(
> 
> It says:
> 
> ; ALGORITHM:
> ; Clear accumulator
> ; Add input / 16 to accumulator
> ; Add input / 128 to accumulator
> ; Add input / 1024 to accumulator
> ; Add input / 8192 to accumulator
> ; Add input / 65536 to accumulator
> 

Hi Bill...

I believe this is not a precise division. What is being done is multiply
really by 1/14 in decimal, or 0.071...  You selected a precision of 16
bits (?), so the error will probably be in the order of 1. It's quite
probable that the first one fails.
(Continue reading)

Permalink | Reply |
headers
John Coppens | 10 May 03:44

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

On Fri, 9 May 2008 22:27:26 -0300
John Coppens <john <at> jcoppens.com> wrote:

> You selected a precision of 16
> bits (?), so the error will probably be in the order of 1. It's quite
> probable that the first one fails.

That didn't come out right.

The error will always be +/- 1, but if you selected 16 bit precision,
that means only an error of 1 in 4000 or so (65536/14). Which, if you
look to replace fractional division by a simple algorithm, is quite good.

As stated in the other message, the division won't necessarily work for
you if you need exact results.

The 0.071... is approximated by

1/16		0.0625 +
1/128		0.0078125 +
1/1024		0.0009765625 +
etc

John
--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
(Continue reading)

Permalink | Reply |
headers
William "Chops" Westfield | 10 May 06:05

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )


On May 9, 2008, at 6:27 PM, John Coppens wrote:
> I believe this is not a precise division. What is being done is  
> multiply
> really by 1/14 in decimal, or 0.071...  You selected a precision of 16
> bits (?), so the error will probably be in the order of 1. It's quite
> probable that the first one fails.

Right, that's PART of it.  But multiplying (floatingpoint) by
	(1.0/16 + 1.0/128 + 1.0/1024 + 1.0/8192 + 1.0/65536)

over the input range (1..65535) gives only 1/3 the number of errors  
(about 7000) as adding the set of integer divisions. Note that this  
point is about as far as it makes sense to take the binary fractions;  
for the 16bit input, anything smaller than i/65536 is going to be  
zero anyway; that's one of the factors that led me to expect better  
results.  :-(

> The error will always be +/- 1, but if you selected 16 bit precision,
> that means only an error of 1 in 4000 or so (65536/14). Which, if you
> look to replace fractional division by a simple algorithm, is quite  
> good.

Sounds good, doesn't it?  But 14/14 = 0 is 100% error !

It seems like a similar algorithm ought to be able to do better.

BillW

--

--
(Continue reading)

Permalink | Reply |
headers
John Coppens | 11 May 02:26

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

On Fri, 9 May 2008 21:05:46 -0700
"William \"Chops\" Westfield" <westfw <at> mac.com> wrote:

> Sounds good, doesn't it?  But 14/14 = 0 is 100% error !

Ok... But the _range_ of the output is 0-4000 (approx), so 14/14 = 0 is
only an error of 1 in 4000 (if you implement the 16-bit algorithm). That's
like blaming a DVM when you're measuring on the 4.000 volt range for
changing the last digit (1mV).

It's probable that if you divide 14.01 by 14, you'd get 1. In fact, I'm
sure, as the approximation the algorithm does is really dividing by
14.00042726, not 14.

> over the input range (1..65535) gives only 1/3 the number of errors  
> (about 7000) as adding the set of integer divisions. 

Note that you may be seeing approximation errors in the floating point
values wherever you're simulating.

John
--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
Michael Rigby-Jones | 12 May 14:31

RE: [PIC] - Need fast divide by 14 constant routine? ( Random access8-bit data in PIC16F flash )


> -----Original Message-----
> From: piclist-bounces <at> mit.edu [mailto:piclist-bounces <at> mit.edu] On
Behalf
> Of William "Chops" Westfield
> Sent: 10 May 2008 01:15
> To: Microcontroller discussion list - Public.
> Subject: Re: [PIC] - Need fast divide by 14 constant routine? ( Random
> access8-bit data in PIC16F flash )
> 
> 
> On May 9, 2008, at 12:39 PM, Harold Hallikainen wrote:
> > There's a nice code generator for multiply and divide by a constant
at
> > http://www.piclist.com/techref/piclist/codegen/constdivmul.htm .
> 
> The algorithm it produces does not seem to work very well in this
> case, even if I use extra bits to produce less error in intermediate
> steps.
> I'm having trouble grasping why not :-(
> 
> It says:
> 
> ; ALGORITHM:
> ; Clear accumulator
> ; Add input / 16 to accumulator
> ; Add input / 128 to accumulator
> ; Add input / 1024 to accumulator
> ; Add input / 8192 to accumulator
> ; Add input / 65536 to accumulator
(Continue reading)

Permalink | Reply |
headers
sergio masci | 10 May 02:15

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Ok, so you need an array of bits stored in code space.

How big is this array?

For an array of upto 3584 bits you could encode the bit positions 
differently to give you better performance.

e.g.

word_offset = (8 * byte_offset) & 0xff;
bit_offset  = (8 * byte_offset) >> 8;

so you use:
bit 0 if word 0 for bit_arr[0]
bit 0 if word 1 for bit_arr[1]
bit 0 if word 2 for bit_arr[2]
.
.
.
bit 0 if word 255 for bit_arr[255]
bit 1 if word 0   for bit_arr[256]
bit 1 if word 1   for bit_arr[257]
bit 1 if word 2   for bit_arr[258]
.
.
.
bit 1 if word 255 for bit_arr[511]
bit 2 if word 0   for bit_arr[512]
bit 2 if word 1   for bit_arr[513]
bit 2 if word 2   for bit_arr[514]
(Continue reading)

Permalink | Reply |
headers
Forrest Christian | 10 May 11:53

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Have you considered storing this in some sort of word-aligned manner...

I.E. let's assume you want to store 500 8 bit bytes...

Store the first 286 as bits 0...7 bits of each word (8 bits).
Store the next 143 as bits 8..11 of each word, but spread across 2 words.
Store the final 71 as bits 12 & 13 of eac word, and spread across 4 words.

Then your algorithm looks like (semi pseudo-code, in c ...  That is, 
don't shoot me if I mangled something like & versus && or >>'d the wrong 
way or too few/too many bits- I've had too long of a day today so I 
might have messed up and I don't feel like looking it up.)

uint8 retrievebyte (uint16 address)
{
  if (address<286)
  {
     return flash[address]&&0xff;
  }
  else if (address<(143+286))
  {
     //return bits 8.11 of address*2 in lower 4 bits, and 8.11 of 
address*2+1 in higher 4 bits;
     return (   (flash[address*2]>>8) && 0x0f) +
                   (flash[address*2+1]>>4&&0xf0)
               );
  }
  else if (address<(71+143+286))
  {
     return (   (flash[address*2]>>12) && 0x03) +
(Continue reading)

Permalink | Reply |
headers
Dario Greggio | 10 May 14:08

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Forrest Christian wrote:
>      return flash[address]&&0xff;

hmmm, those (and following) "&&" are wrong - "&" is what you meant I guess.

-- 
Ciao, Dario
--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
Forrest Christian | 10 May 21:40

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Dario Greggio wrote:
> Forrest Christian wrote:
>   
>>      return flash[address]&&0xff;
>>     
>
> hmmm, those (and following) "&&" are wrong - "&" is what you meant I guess.
>
>   
Yes... I meant bitwise &...

-forrest

--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
sergio masci | 11 May 03:08

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )


Hi Forrest,

I started looking at this but things don't quite look right.

Could you have a look at your numbers again (8 bits is 256 not 286).

is the address the bit address or the byte address?

If it is the bit address then

>   if (address<286)
>   {
>      return flash[address]&&0xff;
>   }

should be

>   if (address<256)
>   {
>      return flash[address >> 3] & 0xff;
>   }

if it is the byte address then there are 8 * 256 = 4k bits available in 
256 bytes (much more than 500)

Also if the requirement of the OP is to return a single bit then you don't 
need relatively complicated extraction and packing.

Maybe you could have another look and clarify things a bit :-)
(Continue reading)

Permalink | Reply |
headers
Forrest W Christian | 11 May 06:21

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Let me see if I can re-explain.  And fix a bug.

Instead of storing the bytes something like the following  (where the # 
is which byte that bit belongs to, and note that for convienience I've 
swapped LSB/MSB left-to-right just for visual purposes):

LSb                     MSb
0 0 0 0 0 0 0 0 1 1 1 1 1 1    (Word 0)
1 1 2 2 2 2 2 2 2 2 3 3 3 3    (Word 1)
3 3 3 3 4 4 4 4 4 4 4 4 5 5    (Word 2)
5 5 5 5 5 5 6 6 6 6 6 6 6 6    (Word 3)

I'm advocating something like this:

0 0 0 0 0 0 0 0 4 4 4 4 6 6   (Word 0)
1 1 1 1 1 1 1 1 4 4 4 4 6 6   (Word 1)
2 2 2 2 2 2 2 2 5 5 5 5 6 6   (Word 2)
3 3 3 3 3 3 3 3 5 5 5 5 6 6   (Word 3)

So the algorithm is:

if (address<4)  // Bytes 0..3 are in 8 LSb of words 0..3.
{
   return flash[address]&0xff;
}
elsif (address<6) // bytes 4..5 are in bits 8..11 of words 0..3
{
   return flash[ (address-4)/2 ]>>8) & 0b00001111
        | flash[ (address-4)/2+1 ]>>6 ) &0b11110000;
}
(Continue reading)

Permalink | Reply |
headers
Timothy J. Weber | 11 May 14:25

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Forrest W Christian wrote:
> Let me see if I can re-explain.  And fix a bug.
> 
> Instead of storing the bytes something like the following  (where the # 
> is which byte that bit belongs to, and note that for convienience I've 
> swapped LSB/MSB left-to-right just for visual purposes):
> 
> LSb                     MSb
> 0 0 0 0 0 0 0 0 1 1 1 1 1 1    (Word 0)
> 1 1 2 2 2 2 2 2 2 2 3 3 3 3    (Word 1)
> 3 3 3 3 4 4 4 4 4 4 4 4 5 5    (Word 2)
> 5 5 5 5 5 5 6 6 6 6 6 6 6 6    (Word 3)
> 
> I'm advocating something like this:
> 
> 0 0 0 0 0 0 0 0 4 4 4 4 6 6   (Word 0)
> 1 1 1 1 1 1 1 1 4 4 4 4 6 6   (Word 1)
> 2 2 2 2 2 2 2 2 5 5 5 5 6 6   (Word 2)
> 3 3 3 3 3 3 3 3 5 5 5 5 6 6   (Word 3)

I haven't really been paying attention... maybe it would be simpler like 
this?

  0  1  2  3  4  5  6  7  8  9 10 11 12 13   (Word 0)
  0  1  2  3  4  5  6  7  8  9 10 11 12 13
  0  1  2  3  4  5  6  7  8  9 10 11 12 13
  0  1  2  3  4  5  6  7  8  9 10 11 12 13
  0  1  2  3  4  5  6  7  8  9 10 11 12 13
  0  1  2  3  4  5  6  7  8  9 10 11 12 13
  0  1  2  3  4  5  6  7  8  9 10 11 12 13
(Continue reading)

Permalink | Reply |
headers
Forrest Christian | 11 May 23:34

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

The original poster was looking for a fast way to divide by 14 so he 
could locate the appropriate byte.

The best scenario for the original poster was to do a multiply by 8 
(shift by 3), do a divide by 14, do a modulus, and then for the 
retrieval, do two bitwise shifts (total length of shift depending on 
exact position), and two ands, and two ors.  I probably missed something...

My initial glance at your code looks like it still requires the divide 
by 14, and the multiply by 8, just in opposite directions.   (Divide by 
14 to get which "block", then multiply by 8 to get the starting address 
of the block).  The retrieval seems worse, though since it requries 8 
bitwise shifts, 8 ands, and 8 ors.

My solution requires the following:

When storing 7 words:
For the first 4 words:  One compare, and one bitwise and.
For the next 2 words: Two compares, two multibit shifts, two bitwise 
ands, and one or.
For the final word:  Three compares, four multibit shifts, four bitwise 
ands, and three ors.

-forrest

Timothy J. Weber wrote:
> I haven't really been paying attention... maybe it would be simpler 
> like this?
>   0  1  2  3  4  5  6  7  8  9 10 11 12 13   (Word 0)
>   0  1  2  3  4  5  6  7  8  9 10 11 12 13
(Continue reading)

Permalink | Reply |
headers
Timothy J. Weber | 12 May 02:25

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Forrest Christian wrote:
> My initial glance at your code looks like it still requires the divide 
> by 14, and the multiply by 8, just in opposite directions.   (Divide by 
> 14 to get which "block", then multiply by 8 to get the starting address 
> of the block).  The retrieval seems worse, though since it requries 8 
> bitwise shifts, 8 ands, and 8 ors.

Yup, I think you're right.
-- 
Timothy J. Weber
http://timothyweber.org
--

-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
Permalink | Reply |
headers
Tamas Rudnai | 12 May 13:37

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Actually I was thinking of an alternative method, where we are still going
to loose some space but much less than storing 8 bits on 14 bits, and also
relatively easy to calculate addresses:

We store the first 7 bits of each bytes in a way of:

0 0 0 0 0 0 0 1 1 1 1 1 1 1  (word 0)
2 2 2 2 2 2 2 3 3 3 3 3 3 3  (word 1)
4 4 4 4 4 4 4 5 5 5 5 5 5 5  (word 2)
6 6 6 6 6 6 6 7 7 7 7 7 7 7  (word 3)

If we are going to store 7 bit data stream like pure ascii, then we are
already fine, but if we need the 8th bit, then we store it in a separated
area:

xx xx xx xx xx xx 00 01 02 03 04 05 06 07 (word 0)
xx xx xx xx xx xx 08 09 10 11 12 13 14 15 (word 1)
xx xx xx xx xx xx 16 17 18 19 20 21 22 23 (word 2)

Se here we are loosing 6 bit/8bytes, but its much easier to divide by 8
here, and by 2 when calculating for the address of the first 7 bits.
Also the remainder is fairly easy with a single ANDLW instruction...

With these 8th bits we can use RETLW as well as it could be faster to do so
than eeprom reading. Alternatively it could be shared with a table of 6 bits
of data array.

What do you recon?

Tamas
(Continue reading)

Permalink | Reply |
headers
Ed Sutton | 12 May 19:10

Re: [PIC] - Need fast divide by 14 constant routine? ( Random access 8-bit data in PIC16F flash )

Thank you all for the thoughtful feedback.  Sorry, it took so long to 
reply.  I took me a while to find the archive where I could read the 
replies.  Last time our IT guy whined when about mail traffic when I 
signed up for PICList so this time a signed up for daily digest format.

Basically I am trying to replace a byte addressable serial EEPROM with 
the large flash memory space found in the newer PIC16F parts.  I had not 
thought about word-aligning as suggested by Forrest.  This would 
certainly make it easier for the math challenged (this includes myself); 
8-bit align in 14-bit words till end of memory space, then 4-bit align 
in the upper part of the 6-bits till end of memory space,  then 2-bit 
align in the remaining 2-bits of the upper 6-bits.  Performance would 
likely be faster than a math routine to calculate byte and bit offset.  
At least for the byte and nibble aligned address space; getting four 
2-bit chunks from four words might be as slow as a math routing.

I am still digesting the math routine ideas....

Thanks for the great input!

-Ed

Ed Sutton wrote:
> Are there other ways to implement a divide by a 14 constant other than 
> cycle-chewing subtraction loops?
>
> I want to use the PIC16F flash consisting of 14-bit words to store 
> 8-bit data.  I can implement the multiply-by-8 as a shift.  The crux 
> of the problem is basically the divide by a constant of 14.
>
(Continue reading)

Permalink | Reply |

Gmane