Right shift vs. divide (really shifts can be useful)

[Karl Tombre]

In article <124000005 at ima.UUCP> johnl at ima.UUCP writes:
>
>Now that we know that right shifting is not the same as division, has 
>anybody ever come up with a plausible reason for computers to have 
>arithmetic shift instructions on twos complement machines (other than that 
>they're easy to implement and poorly educated engineers might have thought 
>they were the same as division)?  

You can use shift instructions for other things than divisions:
In some binary image processing programs (for example thinning), you have to
scan an image (considered as a 2D matrix of bits) in order to find
particular 3x3 window patterns where you can change the central pixel. A
fast way for doing this is the use of a look-up table and of coding in one
word of the neighborhood. Here is the considered neighborhood:

    1 4 7                               ___________________
    2 5 8     which is coded as follows |1|2|3|4|5|6|7|8|9|
    3 6 9                               -------------------

Well, there are 512 possible configurations, I thus can use a look-up table
of 512 entries, where I put a 1 (true) for each interesting configuration.
Now, to scan one line of the image, you use shift instructions the following
way:

typedef PIXEL /*whatever you use to code pixels*/

PIXEL *pl, /*pointer in preceding line*/
      *cl, /*           current line*/
      *fl; /*           following line*/
int window; /*where I code the window configuration*/

/* skip most of the function... I just want to show how you go from one
   point to the next*/

/* window codes one window configuration. When I go to the next point on the
   current line, I do the following : */

window = ( window << 1) | (*pl & 01);   /*preceding line*/
window = ( window << 1) | (*cl & 01);   /*current line*/
window = ( window << 1) | (*fl & 01);   /*following line*/

window &= 0x1ff;  /*to keep only the 9 lowest bits*/

This is just a little example of the usefulness of shift instructions. If
they didn't exist, it wouldn't run quite as fast on the machine.

> Followups to net.arch, please.  
>
>John Levine, ima!johnl

Well, I think this was more a C answer than an architecture answer. I only
wanted to show that I find shifts quite useful. But perhaps you were
thinking of something else...

-- 
--- Karl Tombre @ CRIN (Centre de Recherche en Informatique de Nancy)
UUCP:    ...!vmucnam!crin!tombre  or    ...!inria!crin!tombre
COSAC:   crin/tombre
POST:    Karl Tombre, CRIN, B.P. 239, 54506 VANDOEUVRE CEDEX, France

Les plus desesperes sont les chants les plus beaux,
Et j'en sais d'immortels qui sont de purs sanglots.

       Alfred de Musset.