Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!mailrus!iuvax!rutgers!rochester!pt.cs.cmu.edu!sei!sei.cmu.edu!firth
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.arch
Subject: Re: RISC v. CISC --more misconceptions
Message-ID: <7575@aw.sei.cmu.edu>
Date: 2 Nov 88 14:41:53 GMT
References: <156@gloom.UUCP> <18931@apple.Apple.COM> <40@sopwith.UUCP> <998@l.cc.purdue.edu>
Sender: netnews@sei.cmu.edu
Reply-To: firth@bd.sei.cmu.edu (Robert Firth)
Organization: Carnegie-Mellon University, SEI, Pgh, Pa
Lines: 16

In article <998@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes:
>There are many other operations which are cheap in hardware and expensive in
>software...I will toss in a few for starters.

>	Find the distance to the next one in a bit stream FAST.  It would
>be good to have an exception handler if one is not found.  I am considering
>algorithms not worth implementing if the operation is slow.

This is implemented in hardware on the MC68020 by the 'BFFFO' instruction.
It takes 18 cycles to find the first bit in a 32-bit register, and upto
32 cycles to find the first bit in a 32-bit bitfield in memory.

I find it hard to believe that a software algorithm on a RISC machine
would do worse.  In the register case, for instance, a simple binary
chop takes at most 5 steps, and each step is just (and-immediate-with-mask;
branch if result zero).  One can get more cunning, but that gives you
the answer in about 12 cycles.