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

Exact match. Not showing close matches.
PICList Thread
'[PIC]: brain teaser'
2003\06\09@224833 by Mike Hord

picon face
Right after finished my embedded systems class in college, a friend of mine
was taking it from a different prof.  The professor gave them a challenge:

In the shortest possible time, reverse the order of the bits in a random
data register.  Assume this is the time critical element of the application,
and nothing about the application is as important as getting the order of
these bits reversed as quickly as possible.

Assume the processor is a 16F876.

My friend came up with the fastest possible means I've yet seen.  What
say you all?

Mike H.

_________________________________________________________________
Add photos to your e-mail with MSN 8. Get 2 months FREE*.
http://join.msn.com/?page=features/featuredemail

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

2003\06\09@225914 by M. Adam Davis

flavicon
face
Does it beat all of the options here:
http://www.piclist.com/techref/microchip/math/bit/revbits.htm

The fastest one takes 4 instruction cycles (lookup table).
The shortest is 5 instructions long. (rotate left into c, rotate right
from c, in a loop)
The one which seems to be both fast and small is 12 instructions and
takes 12 cycles to execute

-Adam

Mike Hord wrote:

{Quote hidden}

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

2003\06\09@230327 by Tal

flavicon
face
Hi Mike,

When do this homework due ?  ;-)

My bet would be overclocking the PIC and liquid cooling it.

If this is not acceptable, how about a lookup talbe ?

Tal

> {Original Message removed}

2003\06\09@231341 by Scott Dattalo

face
flavicon
face
On Mon, 9 Jun 2003, Mike Hord wrote:

> Right after finished my embedded systems class in college, a friend of mine
> was taking it from a different prof.  The professor gave them a challenge:
>
> In the shortest possible time, reverse the order of the bits in a random
> data register.  Assume this is the time critical element of the application,
> and nothing about the application is as important as getting the order of
> these bits reversed as quickly as possible.
>
> Assume the processor is a 16F876.
>
> My friend came up with the fastest possible means I've yet seen.  What
> say you all?


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

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

2003\06\09@231755 by Ben Jackson

flavicon
face
On Mon, Jun 09, 2003 at 09:47:44PM -0500, Mike Hord wrote:
> In the shortest possible time, reverse the order of the bits in a random
> data register.  Assume this is the time critical element of the application,
> and nothing about the application is as important as getting the order of
> these bits reversed as quickly as possible.

Crosswire two ports, write to one, read from the other.

In a real application you could probably arrange for the bits to be
reversed as part of some other operation (eg at input time).

--
Ben Jackson
<EraseMEbenspam_OUTspamTakeThisOuTben.com>
http://www.ben.com/

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

2003\06\10@011109 by Marc Nicholas

flavicon
face
The fastest possible solution would be to utilize quantum mechanics, whereby
all possible solutions would be computed in near instantaneous time and with
all possible permutations. ;-)



-marc

On 9/6/03 22:47, "Mike Hord" <@spam@gaidinmdKILLspamspamHOTMAIL.COM> wrote:

{Quote hidden}

--------------------------------------------------
Marc Nicholas Geekythings Inc. C/416.543.4896
UNIX, Database, Security and Networking Consulting

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestTakeThisOuTspammitvma.mit.edu>

2003\06\10@011950 by Mike Poulton

flavicon
face
Marc Nicholas wrote:
> The fastest possible solution would be to utilize quantum mechanics, whereby
> all possible solutions would be computed in near instantaneous time and with
> all possible permutations. ;-)

Is that an undocumented feature of the 16F876? :)

--

Mike Poulton
spamBeGonempoultonspamBeGonespammtptech.com
MTP Technologies
KC0LLX

--
http://www.piclist.com hint: To leave the PICList
TakeThisOuTpiclist-unsubscribe-requestEraseMEspamspam_OUTmitvma.mit.edu>

2003\06\10@012343 by David VanHorn

flavicon
face
>
>> My friend came up with the fastest possible means I've yet seen.  What
>> say you all?

This sounds like a trick question, but off the top of my head, 16 clocks in an AVR, very straightforward.

Input in TEMP register, output in TEMP2 register

ROL TEMP
ROR TEMP2
(repeat 8X)

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestspamTakeThisOuTmitvma.mit.edu>

2003\06\10@012631 by Marc Nicholas

flavicon
face
On 10/6/03 01:18, "Mike Poulton" <mpoultonEraseMEspam.....MTPTECH.COM> wrote:

> Marc Nicholas wrote:
>> The fastest possible solution would be to utilize quantum mechanics, whereby
>> all possible solutions would be computed in near instantaneous time and with
>> all possible permutations. ;-)
>
> Is that an undocumented feature of the 16F876? :)

Well, technically anything that can move electrons around *could* do it ;-)

Funny thing about quantum computing: if you could do it, you could compute
all possible moves in a chess game. Believe it or not, that actually defies
the laws of physics.


-marc

--
http://www.piclist.com hint: To leave the PICList
EraseMEpiclist-unsubscribe-requestspammitvma.mit.edu>

2003\06\10@034253 by Wouter van Ooijen

face picon face
> In the shortest possible time, reverse the order of the bits
> in a random
> data register.  Assume this is the time critical element of
> the application,
> and nothing about the application is as important as getting
> the order of
> these bits reversed as quickly as possible.

1. Random? You want the reverse of random? I will give you 0b_0000_0000,
now you prove me wrong!

2. Write to a port, read back from another port with appropriate wiring
between the ports

3. hardware tricks are not allowed? I did not hear you say so! But you
could always use a RETLW table.

4. Bugger, it must be a small amout of code too? Better get your specs
right next time, and ask Scott to do it in 3.5 instructions.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestEraseMEspamEraseMEmitvma.mit.edu>

2003\06\10@035518 by hael Rigby-Jones

picon face
> -----Original Message-----
> From: M. Adam Davis [SMTP:RemoveMEadampicspam_OUTspamKILLspamUBASICS.COM]
> Sent: Tuesday, June 10, 2003 3:59 AM
> To:   RemoveMEPICLISTTakeThisOuTspamspamMITVMA.MIT.EDU
> Subject:      Re: [PIC]: brain teaser
>
> Does it beat all of the options here:
> http://www.piclist.com/techref/microchip/math/bit/revbits.htm
>
> The fastest one takes 4 instruction cycles (lookup table).
>
I make that 8 cycles (REG being the randomly chosen register):

       movf    REG,w           ; one cycle
       call            reverse         ; two cycles
       movwf   REG             ; one cycle

reverse:
       addwf   PCL,f           ; two cycles
       retlw   0x00            ; two cycles
       retlw   0x80
       retlw   0x40


Cross-wiring two ports gives a 4 cycle solution:

       movf    REG,w           ; one cycle
       movwf   PORTB           ; one cycle
       movf    PORTC,w ; one cycle
       movwf   REG             ; one cycle


Regards

Mike


=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
Any questions about Bookham's E-Mail service should be directed to EraseMEpostmasterspamspamspamBeGonebookham.com.

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestKILLspamspammitvma.mit.edu>

2003\06\10@061753 by Jim Robertson

flavicon
face
{Quote hidden}

Now to the real world.  The above example assumes that:

1) The Addwf PCL,f  is one address location before a Mod 256 address.
2) That PCLATH is "magically" addressing the right 256 byte page
3) That the PIC involved is not a PIC18 core type.

Regards,

Jim

--
http://www.piclist.com hint: To leave the PICList
KILLspampiclist-unsubscribe-requestspamBeGonespammitvma.mit.edu>

2003\06\10@070730 by hael Rigby-Jones

picon face
{Quote hidden}

Indeed.  I ignored these as this was a "best case" scenario.  A "bit
reverser" would be trivial to implement in silicon, I wonder if MChip have
ever considered including one as this topic has come up quite a few times.

Mike

Mike


=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
Any questions about Bookham's E-Mail service should be directed to .....postmasterspam_OUTspambookham.com.

--
http://www.piclist.com hint: To leave the PICList
TakeThisOuTpiclist-unsubscribe-request.....spamTakeThisOuTmitvma.mit.edu>

2003\06\10@081626 by

flavicon
face
Or, on the 18-series :

Cross-wiring two ports gives a 4 cycle solution:

       movff   REG,PORTB       ; two cycles
       movff   PORTC,REG       ; two cycles

Same code space, same # of cycles, but just two
instruction...

Jan-Erik.

Michael Rigby-Jones wrote:

> Cross-wiring two ports gives a 4 cycle solution:
>
>        movf    REG,w           ; one cycle
>        movwf   PORTB           ; one cycle
>        movf    PORTC,w ; one cycle
>        movwf   REG             ; one cycle

--
http://www.piclist.com hint: To leave the PICList
TakeThisOuTpiclist-unsubscribe-requestKILLspamspamspammitvma.mit.edu>

2003\06\10@082908 by M. Adam Davis

flavicon
face
Marc Nicholas wrote:

>Well, technically anything that can move electrons around *could* do it ;-)
>
>Funny thing about quantum computing: if you could do it, you could compute
>all possible moves in a chess game. Believe it or not, that actually defies
>the laws of physics.
>
>
Only if you believe that we could not come up with a representation of
something which takes more than all the known atoms in the universe to
represent.

The nice thing about the quantum computer, however, is that you wouldn't
need to compute all possible chess game moves.  Just build the computer
to compute the best move given a certian board configuration.  If it has
to run through all possible moves in order to compute it, so be it, but
it never actually has to store any board configuration beyond the
current one for more than an instant.

-Adam

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestspamRemoveMEmitvma.mit.edu>

2003\06\10@090957 by Olin Lathrop

face picon face
> Right after finished my embedded systems class in college, a friend of
> mine was taking it from a different prof.  The professor gave them a
> challenge:
>
> In the shortest possible time, reverse the order of the bits in a random
> data register.  Assume this is the time critical element of the
> application, and nothing about the application is as important as
> getting the order of these bits reversed as quickly as possible.
>
> Assume the processor is a 16F876.
>
> My friend came up with the fastest possible means I've yet seen.  What
> say you all?

OK, here's the ugly brute force approach:


;   Subroutine to flip the bits in REG0 and return them in W.
;
    glbsub  flipit, noregs

    movlw   high table      ;set high address of table entry
    movwf   pclath
    movf    reg0, w         ;get the byte value to flip
    movwf   pcl             ;jump to selected table entry, returns from
FLIPIT

table code   <some multiple of 256 in same page as FLIPIT>


However, I think there are far more elegant methods making clever use of
SWAP, XOR, etc.

<soapbox>
In a normal application where this isn't a critical function, I would
prefer the clearest and most undestandable approach.  Usually a few extra
instructions are cheaper in the long run if they decrease the chance that
some green programmer three years later long after you've moved on doesn't
mess it up and spend two days trying to figure out why something obscure
broke.  University professors don't usually appreciate this.  While these
kinds of brain teasers can be good mental exercises and help you think
about using the instruction set in different ways, they also create the
false impression that this sort of programming is valuable or even a good
idea.  Most of the time it's neither.
</soapbox>

That said, my first knee jerk reaction would be to shift one register one
bit at a time into C, then shift the other one in from the same direction.
Yes, I'm quite sure there are faster and smaller methods, but this method
is both cheap to write and maintain.  I can probably write this loop
(including comments of course) or the unrolled version in under a minute.
Most of the time it wouldn't be in my customer's interest to spend 5
minutes creating an optimized version.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestspamspamBeGonemitvma.mit.edu>

2003\06\10@091211 by Olin Lathrop

face picon face
M. Adam Davis wrote:
> The fastest one takes 4 instruction cycles (lookup table).

Unlikely after you add up all the true costs.  I challange you to show the
code.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

--
http://www.piclist.com hint: To leave the PICList
spamBeGonepiclist-unsubscribe-request@spam@spamspam_OUTmitvma.mit.edu>

2003\06\10@092449 by Olin Lathrop

face picon face
> Indeed.  I ignored these as this was a "best case" scenario.  A "bit
> reverser" would be trivial to implement in silicon, I wonder if MChip
> have
> ever considered including one as this topic has come up quite a few
> times.

A few times as a brain challange, but I don't remember a single serious
case.  In dozens of PIC projects I only remember needing to do this once.
No, I'd rather not have Microchip waste $$ on this problem.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

--
http://www.piclist.com hint: To leave the PICList
TakeThisOuTpiclist-unsubscribe-requestspamspammitvma.mit.edu>

2003\06\10@093448 by hael Rigby-Jones

picon face
> -----Original Message-----
> From: Olin Lathrop [SMTP:olin_piclistEraseMEspamEMBEDINC.COM]
> Sent: Tuesday, June 10, 2003 2:25 PM
> To:   RemoveMEPICLISTEraseMEspamspam_OUTMITVMA.MIT.EDU
> Subject:      Re: [PIC]: brain teaser
>
> > Indeed.  I ignored these as this was a "best case" scenario.  A "bit
> > reverser" would be trivial to implement in silicon, I wonder if MChip
> > have
> > ever considered including one as this topic has come up quite a few
> > times.
>
> A few times as a brain challange, but I don't remember a single serious
> case.  In dozens of PIC projects I only remember needing to do this once.
> No, I'd rather not have Microchip waste $$ on this problem.
>
An application that I have used was interfacing to a non standard SPI-like
bus that transmitted data LSB first.  I can't imagine that this would
increase silicon cost, although it would use one or maybe two SFR addresses.

Mike



=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
Any questions about Bookham's E-Mail service should be directed to @spam@postmasterRemoveMEspamEraseMEbookham.com.

--
http://www.piclist.com hint: To leave the PICList
EraseMEpiclist-unsubscribe-requestspam@spam@mitvma.mit.edu>

2003\06\10@125421 by Mike Singer

picon face
Someone wrote:
> A few times as a brain challange, but I don't remember a single
> serious case.
.
> Unlikely after you add up all the true costs.  I challange
> you to show the code.

Could anybody explain me is "challange" just misspelling of
"challenge" word or it's like "color" vs "colour" or "thru"
vs "through" American usage of English?

Thank you.

Mike.
Trying to improve my poor English.

--
http://www.piclist.com hint: To leave the PICList
@spam@piclist-unsubscribe-requestspam_OUTspam.....mitvma.mit.edu>

2003\06\10@131831 by David VanHorn

flavicon
face
>
>That said, my first knee jerk reaction would be to shift one register one
>bit at a time into C, then shift the other one in from the same direction.
>Yes, I'm quite sure there are faster and smaller methods, but this method
>is both cheap to write and maintain.  I can probably write this loop
>(including comments of course) or the unrolled version in under a minute.
>Most of the time it wouldn't be in my customer's interest to spend 5
>minutes creating an optimized version.

That's what I hit on, in my AVR version. :)
I agree with you 100% on the reasoning. I also like to be able to debug my own code when I meet it again, a couple years later.

--
http://www.piclist.com hint: To leave the PICList
spamBeGonepiclist-unsubscribe-requestEraseMEspammitvma.mit.edu>

2003\06\10@132030 by David Minkler

flavicon
face
Mike,

It's just a misspelling.

Dave

Mike Singer wrote:
> Could anybody explain me is "challange" just misspelling of
> "challenge" word or it's like "color" vs "colour" or "thru"
> vs "through" American usage of English?
>
> Thank you.
>
> Mike.

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestspamBeGonespammitvma.mit.edu>

2003\06\10@153437 by Dale Botkin

flavicon
face
On Tue, 10 Jun 2003, Olin Lathrop wrote:

> A few times as a brain challange, but I don't remember a single serious
> case.  In dozens of PIC projects I only remember needing to do this once.
> No, I'd rather not have Microchip waste $$ on this problem.

Me too, but I did actually have occasion recently to reverse the order of
two bits in a register, with minimum words of program memory (and no use
of ports) as the only requirement.  It's in a 12F675 with no code space to
spare and all pins used.

Dale
--
It's a thankless job, but I've got a lot of Karma to burn off.
Get a PicoKeyer: http://www.hamgadgets.com

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-request@spam@spamspamBeGonemitvma.mit.edu>

2003\06\10@160350 by Olin Lathrop

face picon face
> Could anybody explain me is "challange" just misspelling of
> "challenge"

Yup, just a typo on my part.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-request@spam@spamEraseMEmitvma.mit.edu>

2003\06\10@170401 by Mike Singer

picon face
Olin Lathrop wrote:
> A few times as a brain challange, but I don't remember
> a single serious case.  In dozens of PIC projects I
> only remember needing to do this once. No, I'd rather
> not have Microchip waste $$ on this problem.

Dale Botkin wrote:
> Me too, but I did actually have occasion recently to
> reverse the order of two bits in a register, with
> minimum words of program memory (and no use of ports)
> as the only requirement.  It's in a 12F675 with no code
> space to spare and all pins used.


Hmm, if there were sorta Xilinx chip that one could load
with some CPU core (PIC, AVR, MSP...) into built-in flash,
configure built-in analog modules and I/O's. If this bloody
creature would be priced as low as PIC.
To reverse the order of bits in one 100MHz cycle just load
extended CPU core command set...

Who can swear this wouldn't be done in few years?

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

Mike.

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestRemoveMEspammitvma.mit.edu>

2003\06\10@172111 by Dale Botkin

flavicon
face
On Wed, 11 Jun 2003, Mike Singer wrote:

> Hmm, if there were sorta Xilinx chip that one could load
> with some CPU core (PIC, AVR, MSP...) into built-in flash,
> configure built-in analog modules and I/O's. If this bloody
> creature would be priced as low as PIC.

And be available in an 8-pin DIP package, and sleep at .005uA, and cost
under two bucks in small quantities -- all of which are important for
*this particular* project, though this is one isolated case of course.

> Who can swear this wouldn't be done in few years?

You're right, but by then it won't matter (at least to me).  Heck, a
12F629 with 1.5 or 2K or program memory and maybe a pullup on GP3 would be
just peachy right now, but Microchip doesn't make one at the moment, so we
make do with what's available.

Dale
--
It's a thankless job, but I've got a lot of Karma to burn off.
Get a PicoKeyer: http://www.hamgadgets.com

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestSTOPspamspam@spam@mitvma.mit.edu>

2003\06\10@173352 by Dal Wheeler

flavicon
face
You mean like a Atmel AT94K?  *Not* $2 ea. in small qtys though... :(
Still, it's fairly cheap to put out a pic + xilinx xc9500xl series if you
need it (at least compared to 5 years ago...).
-Dal
{Original Message removed}

2003\06\10@182009 by Mike Hord

picon face
I haven't read all the responses, but I have so far seen two that came up
with
my friend's fastest method:  two crosswired I/O ports.

(Quoted from Wouter)

>2. Write to a port, read back from another port with appropriate wiring
>between the ports

>3. hardware tricks are not allowed? I did not hear you say so! But you
>could always use a RETLW table.

That's why I didn't specify they aren't allowed!  I just think it's an
interesting
example of "thinking outside the box".  I did specify the PIC, because that
trick
won't work (at least, not as easily) on a lower pinout package.

Mike H.

_________________________________________________________________
The new MSN 8: advanced junk mail protection and 2 months FREE*
http://join.msn.com/?page=features/junkmail

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestEraseMEspam@spam@mitvma.mit.edu>

2003\06\10@191802 by William Chops Westfield

face picon face
People have been designing clever bit-reversal algorithms since the 60s, (do
a net search for "hakmem and Schroeppel" for some nasty code that reverses 6
or 7 bits in 3 instructions, or 8 bits in 4 instructions (involves 36 bit
multiplications and divisions!))  I have a hard time believing that it's
ever important enough to build special purpose hardware within a processor
to do it.  I mean, the only time the actual order of the bits is relevant is
when doing math, and doing math and logical-bit operations on the same
numbers is pretty rare.  It's always easier to simply make your external
shift registers shift the other direction, or re-think the problem.  I think
I used a bit-reversal algorithm in a graphics hack once, but only because I
wanted the leftmost bits on the printer to match the leftmost bits in the
memory; and that was quite arbitrary; there's no reason that the MSB of a
word has to be thought of as being "on the left."

BillW

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestspamspamBeGonemitvma.mit.edu>

2003\06\10@230439 by Dwayne Reid

flavicon
face
At 04:14 PM 6/10/03 -0700, William Chops Westfield wrote:

>I think I used a bit-reversal algorithm in a graphics hack once, but only
>because I
>wanted the leftmost bits on the printer to match the leftmost bits in the
>memory; and that was quite arbitrary; there's no reason that the MSB of a
>word has to be thought of as being "on the left."

Just like it doesn't matter how you wire up the data lines or even the low
order address lines on static ram chips (small embedded systems using 805x
or 68xx micros).  Since the same wire connections are being used to write
and read the data, the actual order doesn't matter.  Do the same to the ROM
chips and confuse the heck out of someone trying to reverse-engineer your
product.

Some people used to have a real problem with that concept.  But it sure
made it easier to lay out PCBs <grin>.

dwayne

--
Dwayne Reid   <spamBeGonedwaynerKILLspamspam@spam@planet.eon.net>
Trinity Electronics Systems Ltd    Edmonton, AB, CANADA
(780) 489-3199 voice          (780) 487-6397 fax

Celebrating 19 years of Engineering Innovation (1984 - 2003)
 .-.   .-.   .-.   .-.   .-.   .-.   .-.   .-.   .-.   .-
    `-'   `-'   `-'   `-'   `-'   `-'   `-'   `-'   `-'
Do NOT send unsolicited commercial email to this email address.
This message neither grants consent to receive unsolicited
commercial email nor is intended to solicit commercial email.

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestspam_OUTspam@spam@mitvma.mit.edu>

2003\06\11@012417 by William Chops Westfield

face picon face
   Do the same to the ROM chips and confuse the heck out of someone
   trying to reverse-engineer your product.

Heh.  IIRC, the cisco CSC/2 processor card got laid out a bit wrong,
with the data lines reversed (I *think* this was accidental, rather
than an attempt at security.)  So the prom-downloading softwarfe was
another place we ended up putting some bit reversal code (but it
didn't have to be small or fast.)

BillW

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@013721 by David VanHorn

flavicon
face
>
>Heh.  IIRC, the cisco CSC/2 processor card got laid out a bit wrong,
>with the data lines reversed (I *think* this was accidental, rather
>than an attempt at security.)  So the prom-downloading softwarfe was
>another place we ended up putting some bit reversal code (but it
>didn't have to be small or fast.)

We used to scramble the address and data lines all the time, just to make the board route easier.  All it takes is a wire-wrapped adaptor when you burn the master rom, then you just copy.  No problem.  Of course ram doesn't care at all.

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@034907 by Alan B. Pearce

face picon face
>Just like it doesn't matter how you wire up the data lines or even the low
>order address lines on static ram chips (small embedded systems using 805x
>or 68xx micros).  Since the same wire connections are being used to write
>and read the data, the actual order doesn't matter.  Do the same to the ROM
>chips and confuse the heck out of someone trying to reverse-engineer your
>product.
>
>Some people used to have a real problem with that concept.  But it sure
>made it easier to lay out PCBs <grin>.

I believe I have heard of this being done to make reverse engineering a
product somewhat harder to do also. Remove the ROM and dump it into a
disassembler and the code looks like nothing sensible - Huh? Well you did
assume that the LSB of the processor went to the ROM pin labelled LSB, but
it doesn't really.

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@101806 by Morgan Olsson

flavicon
face
Hej QAC. Tack för ditt meddelande 14:15 2003-06-10 enligt nedan:
>Or, on the 18-series :
>
>Cross-wiring two ports gives a 4 cycle solution:

No, 2 cycle:

>       movff   REG,PORTB       ; two cycles

Stop here; DONE!  -the result *is* acessible in regster PORTC now!  :)

>        movff   PORTC,REG       ; two cycles

only if you need a copy of it elswhere

/Morgan

--
Morgan Olsson, Kivik, Sweden

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@102426 by hael Rigby-Jones

picon face
{Quote hidden}

within an arbitrary register.  The second instruction *is* required in order
to achieve this.

Regards

Mike


=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
Any questions about Bookham's E-Mail service should be directed to spamBeGonepostmasterspam_OUTspamRemoveMEbookham.com.

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@121737 by Dmitriy A. Kiryashov

picon face
Excellent idea!

Nultiplying by constant in such way what every original bit from A
being transferred into reversed position in result's high register.
Since multiple positions resulted divison is used at the end.
Can be implemented on PIC's with hardware multiplication as
well I think. I like the way Gosper and Freiberg thought. ;)

Add/sub operations are capable to shift bits simultaneously to
the same distance while mul/div can move each bit differently.
Interesting...


WBR Dmitry.


William Chops Westfield wrote:
{Quote hidden}

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@122412 by Hazelwood Lyle

flavicon
face
{Quote hidden}

OK, but I believe that a NOP between the two MOVFF
instructions may be necessary to allow I/O settling.

I'm not ready to wire one up and test, but the
possibility of reading the second MOVFF before the
outputs are stable in their new state seems a possibility.

Just theorizing,
Lyle

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@123435 by David VanHorn

flavicon
face
Just for chagrins, isn't a page register change needed between IO port read and write operations?

That would put the two instruction version at four instructions, without accounting for moving the data to be reversed into W and back out.

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@124853 by hael Rigby-Jones

picon face
> -----Original Message-----
> From: David VanHorn [SMTP:dvanhornspam@spam@CEDAR.NET]
> Sent: Wednesday, June 11, 2003 5:32 PM
> To:   EraseMEPICLISTRemoveMEspamSTOPspamMITVMA.MIT.EDU
> Subject:      Re: [PIC]: brain teaser
>
> Just for chagrins, isn't a page register change needed between IO port
> read and write operations?
>
> That would put the two instruction version at four instructions, without
> accounting for moving the data to be reversed into W and back out.
>
Only on a 12/14 bit core and only if REG is not in bank 1.

Regards

Mike


=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
Any questions about Bookham's E-Mail service should be directed to RemoveMEpostmasterKILLspamspamTakeThisOuTbookham.com.

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@135150 by Peter L. Peres

picon face
On 10/6/03 01:18, "Mike Poulton" <spamBeGonempoultonspam@spam@MTPTECH.COM> wrote:

> Funny thing about quantum computing: if you could do it, you could
> compute all possible moves in a chess game. Believe it or not, that
> actually defies the laws of physics.

Why does it defy the laws of physics ? The number of states the board can
be in is finite and computable. That would be the total number of
positions in any game. Neglecting the rules of playing you have 16 pieces
on 64 squares = C(64,16), then 15 on 64, C(64,15) etc. The sum is a simple
computation and the real number of possible positions will be a subset of
it (the covering number would be used to plan the computer for enough
capacity and speed so you do not have to grow old while watching it work).

Peter

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\11@141051 by Olin Lathrop

face picon face
David VanHorn wrote:
> Just for chagrins, isn't a page register change needed between IO port
> read and write operations?

No.

First, pages have nothing to do with register access.  Second, since the
read and write access are to the same address, there is no need for a bank
change either.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads

2003\06\12@034842 by o-8859-1?Q?Tony_K=FCbek?=

flavicon
face
Hi,
Dmitry wrote:
>Nultiplying by constant in such way what every original bit from A
>being transferred into reversed position in result's high register.
>Since multiple positions resulted divison is used at the end.
>Can be implemented on PIC's with hardware multiplication as
>well I think. I like the way Gosper and Freiberg thought. ;)
>
>Add/sub operations are capable to shift bits simultaneously to
>the same distance while mul/div can move each bit differently.
>Interesting...

Yes interesting indeed, last time this came up I spent a few minutes
trying to use the multiplier on the 18xx chips, I only got 'halfway'
though. In about 6 cycles (I think?) I got the following:

Input: b7b6b5b4b3b2b1b0
..
6 cycles :)
..
Output: b1b0b3b2b5b4b7b6

But it had me stumped there, lacking time (and brainpower :) ) I had
to leave it at that state. Of cource it's 'easy' to correct it but
the number of cycles it took seemed ineffective, I feel there has to be an
better way (gut feeling). I think with the limited multiplier (8x8) it's hard to reach an substancial
improvement over the 'brute force' method (shift->carry).
Anyway this is a brain teaser indeed.

/Tony

--
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

2003\06\13@192535 by Scott Dattalo

face
flavicon
face
On Thu, 12 Jun 2003, Tony K|bek wrote:

{Quote hidden}

Tony,

why not do this:


 ; copied from Dmitry's solution

   swapf   X,W     ;efghabcd
   xorwf   X,W     ;efghabcd
                   ;abcdefgh
   andlw   0x66    ;.fg..bc.
                   ;.bc..fg.
   xorwf   X,F     ;afgdebch

 ; then take advantage of the 18f instructions:

   rlncf   X,W     ;fgdebcha
   rrncf   X,F     ;hafgdebc
   xorwf   X,W     ;hafgdebc
                   ;fgdebcha
   andlw   0x55    ;0a0g0e0c
                   ;0g0e0c0a
   xorwf   X,F     ;hgfedcba

Actually, I think you can save 2-cycles off Dmitry's solution for the
mid-range parts:

   swapf   X,W     ;efghabcd
   xorwf   X,W     ;efghabcd
                   ;abcdefgh
   andlw   0x66    ;.fg..bc.
                   ;.bc..fg.
   xorwf   X,F     ;afgdebch

 ; then take advantage of the 18f instructions:

   rlf     X,W     ;fgdebch?
   rlf     X,W     ;fgdebcha
   rrf     X,F     ;aafgdebc
   xorwf   X,W     ;aafgdebc
                   ;fgdebcha
   andlw   0x55    ;0a0g0e0c
                   ;0g0e0c0a
   xorwf   X,F     ;hgfedcba

If I didn't make a mistake, then the mystical 12-cycle algorithm axiom has
finally been proven false!

Scott

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

2003\06\13@231749 by Scott Dattalo

face
flavicon
face
On Fri, 13 Jun 2003, Scott Dattalo wrote:

{Quote hidden}

Tested and works...

{Quote hidden}

Tested and doesn't work. damn. The upper bit of X is messed up in the last
rrf instruction.

Scott

--
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 2003 , 2004 only
- Today
- New search...