[Freeciv-Dev] Re: (PR#1180) [PATCH] cleanup to canvas_pos_to_map_pos

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

It at least recognizes the positive denominator :-).

But try this as a way to overcome the "%" anti-pattern bias ...

/*
 * DIVIDE() divide and round down (== more negative), rather than just
 *   divide (round toward 0).  It is assumed the divisor is positive.
 *   Arguments are used multiple times, so must not have side effects.
 * The full case would be ...
 * DIVIDE_GENERIC(n, d)  ( (d) < 0 ? DIVIDE(-(n), -(d)) : DIVIDE((n), (d)) )
 */
#define DIVIDE(n, d) \
  ( (n) < 0 ? ((n) - (d) + 1) / (d) : (n) / (d) )
  -- or --
  ( (n) < 0 ? ((n) + 1) / (d) - 1 : (n) / (d) )

There is absolutely never a need for % operations which are *very* 
expensive. The first form may actually be faster if the two adds 
are handled by an indexing instruction, but the second will never
be more than a single clock behind if the terminal dec is the long
pole of the pipeline. In the positive case, you just lose the extra
conditional and branch over a simple divide which is about optimal.

These are still bad in that they evaluate the arguments 2 or 3 times
though the compiler will hopefully catch this in many cases. It is 
then only the side-effect problem that becomes an issue.

The only real solution for side effects that still retains things as 
expressions is to use static storage to hold the intermediates. Note
that most optimizing compilers will never use the intermediates, as
things will be done in registers and never referenced afterwards.

static int _FC_DIVIDE_N, _FC_DIVIDE_D;

#define DIVIDE(n, d) \
  ( _FC_DIVIDE_N = (n), _FC_DIVIDE_D = (d),    \
    ( _FC_DIVIDE_N) < 0                        \
    ? ((_FC_DIVIDE_N) + 1)/(_FC_DIVIDE_D) - 1  \
    : (_FC_DIVIDE_N) / (_FC_DIVIDE_D) )

One could use alloca() to get local memory to hold the intermediates
but this is not a real (== portable) solution in many cases. One could
also use asm instructions to use regs instead of variables as temps
but again with the non-portability issues.

The moral is, if you do low-level instruction fixes like this, then
take the time to do them right. After that, forget about them :-).

Cheers,
RossW
=====

>+/*
>+ * DIVIDE() divides and rounds down, rather than just divides and
>+ * rounds toward 0.  It is assumed that the divisor is positive.
>+ */
>+#define DIVIDE(n, d) \
>+    ( (n) / (d) - ( (n) < 0 && (n) % (d) < 0 ) )


At 05:27 AM 02/11/21 -0800, Gregory Berkolaiko via RT wrote:
>
>
>Same patch but with even uglier DIVIDE.
>
>G.
>
>
>On Tue, 19 Nov 2002, Jason Short via RT wrote:
>
>> 
>> [glip - Tue Nov 19 20:56:43 2002]:
>> 
>> > So, skipping N_T_ stuff and cancelling the common factors, the
>> > transformation is
>> > 
>> > x_map = [ x / W + y / H]
>> > y_map = [ y / H - x / W]
>> 
>> Here's a new patch.  It still has what Ross calls the "DIVIDE ugliness",
>> but the operations are made atomic and described as a whole.  It refers
>> the your diagram by its URL right here in RT - alternately the diagram
>> could be put into CVS (in /doc) or onto the main freeciv web site.
>> 
>> jason
>> 
>> 
>
>Index: client/citydlg_common.c
>===================================================================
>RCS file: /home/freeciv/CVS/freeciv/client/citydlg_common.c,v
>retrieving revision 1.11
>diff -u -r1.11 citydlg_common.c
>--- client/citydlg_common.c    2002/11/14 09:14:50     1.11
>+++ client/citydlg_common.c    2002/11/21 13:22:08
>@@ -55,35 +55,30 @@
> **************************************************************************/
> void canvas_pos_to_city_pos(int canvas_x, int canvas_y, int *map_x, int
*map_y)
> {
>+  int orig_canvas_x = canvas_x, orig_canvas_y = canvas_y;
>+
>   if (is_isometric) {
>-    *map_x = -2;
>-    *map_y = 2;
>+    const int W = NORMAL_TILE_WIDTH, H = NORMAL_TILE_HEIGHT;
> 
>-    /* first find an equivalent position on the left side of the screen. */
>-    *map_x += canvas_x / NORMAL_TILE_WIDTH;
>-    *map_y -= canvas_x / NORMAL_TILE_WIDTH;
>-    canvas_x %= NORMAL_TILE_WIDTH;
>+    /* Shift the tile right so the top corner of tile (-2,2) is at
>+       canvas position (0,0). */
>+    canvas_y += H / 2;
> 
>-    /* Then move op to the top corner. */
>-    *map_x += canvas_y / NORMAL_TILE_HEIGHT;
>-    *map_y += canvas_y / NORMAL_TILE_HEIGHT;
>-    canvas_y %= NORMAL_TILE_HEIGHT;
>+    /* Perform a pi/4 rotation, with scaling.  See canvas_pos_to_map_pos
>+       for a full explanation. */
>+    *map_x = DIVIDE(canvas_x * H + canvas_y * W, W * H);
>+    *map_y = DIVIDE(canvas_y * W - canvas_x * H, W * H);
> 
>-    assert(NORMAL_TILE_WIDTH == 2 * NORMAL_TILE_HEIGHT);
>-    canvas_y *= 2;            /* now we have a square. */
>-    if (canvas_x + canvas_y > NORMAL_TILE_WIDTH / 2)
>-      (*map_x)++;
>-    if (canvas_x + canvas_y > 3 * NORMAL_TILE_WIDTH / 2)
>-      (*map_x)++;
>-    if (canvas_x - canvas_y > NORMAL_TILE_WIDTH / 2)
>-      (*map_y)--;
>-    if (canvas_y - canvas_x > NORMAL_TILE_WIDTH / 2)
>-      (*map_y)++;
>+    /* Add on the offset of the top-left corner to get the final
>+       coordinates (like in canvas_pos_to_map_pos). */
>+    *map_x -= 2;
>+    *map_y += 2;
>   } else {
>     *map_x = canvas_x / NORMAL_TILE_WIDTH;
>     *map_y = canvas_y / NORMAL_TILE_HEIGHT;
>   }
>-  freelog(LOG_DEBUG, "canvas_pos_to_city_pos(pos=(%d,%d))=(%d,%d)",
canvas_x, canvas_y, *map_x, *map_y);
>+  freelog(LOG_DEBUG, "canvas_pos_to_city_pos(pos=(%d,%d))=(%d,%d)",
>+        orig_canvas_x, orig_canvas_y, *map_x, *map_y);
> }
> 
> /**************************************************************************
>Index: client/mapview_common.c
>===================================================================
>RCS file: /home/freeciv/CVS/freeciv/client/mapview_common.c,v
>retrieving revision 1.15
>diff -u -r1.15 mapview_common.c
>--- client/mapview_common.c    2002/11/19 20:13:38     1.15
>+++ client/mapview_common.c    2002/11/21 13:22:08
>@@ -187,34 +187,42 @@
>                                 int map_view_topleft_map_y)
> {
>   if (is_isometric) {
>-    *map_x = map_view_topleft_map_x;
>-    *map_y = map_view_topleft_map_y;
>+    /* The basic operation here is a simple pi/4 rotation; however, we
>+     * have to first scale because the tiles have different width and
>+     * height.  Mathematically, this looks like
>+     *   | 1/W  1/H | |x|    |x`|
>+     *   |          | | | -> |  |
>+     *   |-1/W  1/H | |y|    |y`|
>+     *
>+     * Where W is the tile width and H the height.
>+     *
>+     * In simple terms, this is
>+     *   map_x = [   x / W + y / H ]
>+     *   map_y = [ - x / W + y / H ]
>+     * where [q] stands for integer part of q.
>+     *
>+     * Here the division is proper mathematical floating point division.
>+     *
>+     * A picture demonstrating this can be seen at
>+     * http://rt.freeciv.org/Ticket/Attachment/16782/9982/grid1.png.
>+     *
>+     * The calculation is complicated somewhat because of two things: we
>+     * only use integer math, and C integer division rounds toward zero
>+     * instead of rounding down.
>+     *
>+     * For another example of this math, see canvas_pos_to_city_pos().
>+     */
>+    const int W = NORMAL_TILE_WIDTH, H = NORMAL_TILE_HEIGHT;
> 
>-    /* first find an equivalent position on the left side of the screen. */
>-    *map_x += canvas_x / NORMAL_TILE_WIDTH;
>-    *map_y -= canvas_x / NORMAL_TILE_WIDTH;
>-    canvas_x %= NORMAL_TILE_WIDTH;
>-
>-    /* Then move op to the top corner. */
>-    *map_x += canvas_y / NORMAL_TILE_HEIGHT;
>-    *map_y += canvas_y / NORMAL_TILE_HEIGHT;
>-    canvas_y %= NORMAL_TILE_HEIGHT;
>-
>-    /* We are inside a rectangle, with 2 half tiles starting in the
>-       corner, and two tiles further out. Draw a grid to see how this
>-       works :). */
>-    assert(NORMAL_TILE_WIDTH == 2 * NORMAL_TILE_HEIGHT);
>-    canvas_y *= 2;            /* now we have a square. */
>-    if (canvas_x > canvas_y) {
>-      *map_y -= 1;
>-    }
>-    if (canvas_x + canvas_y > NORMAL_TILE_WIDTH) {
>-      *map_x += 1;
>-    }
>+    *map_x = DIVIDE(canvas_x * H + canvas_y * W, W * H);
>+    *map_y = DIVIDE(canvas_y * W - canvas_x * H, W * H);
>   } else {                    /* is_isometric */
>-    *map_x = map_view_topleft_map_x + canvas_x / NORMAL_TILE_WIDTH;
>-    *map_y = map_view_topleft_map_y + canvas_y / NORMAL_TILE_HEIGHT;
>+    *map_x = canvas_x / NORMAL_TILE_WIDTH;
>+    *map_y = canvas_y / NORMAL_TILE_HEIGHT;
>   }
>+
>+  *map_x += map_view_topleft_map_x;
>+  *map_y += map_view_topleft_map_y;
> 
>   /*
>    * If we are outside the map find the nearest tile, with distance as
>Index: common/shared.h
>===================================================================
>RCS file: /home/freeciv/CVS/freeciv/common/shared.h,v
>retrieving revision 1.105
>diff -u -r1.105 shared.h
>--- common/shared.h    2002/11/13 19:44:25     1.105
>+++ common/shared.h    2002/11/21 13:22:08
>@@ -65,6 +65,13 @@
> 
> #define BOOL_VAL(x) ((x)!=0)
> 
>+/*
>+ * DIVIDE() divides and rounds down, rather than just divides and
>+ * rounds toward 0.  It is assumed that the divisor is positive.
>+ */
>+#define DIVIDE(n, d) \
>+    ( (n) / (d) - ( (n) < 0 && (n) % (d) < 0 ) )
>+
> /* Deletes bit no in val,
>    moves all bits larger than no one down,
>    and inserts a zero at the top. */
>