include/filters/GP_HilbertCurve.h

   1 /*****************************************************************************
   2  * This file is part of gfxprim library.                                     *
   3  *                                                                           *
   4  * Gfxprim is free software; you can redistribute it and/or                  *
   5  * modify it under the terms of the GNU Lesser General Public                *
   6  * License as published by the Free Software Foundation; either              *
   7  * version 2.1 of the License, or (at your option) any later version.        *
   8  *                                                                           *
   9  * Gfxprim is distributed in the hope that it will be useful,                *
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  12  * Lesser General Public License for more details.                           *
  13  *                                                                           *
  14  * You should have received a copy of the GNU Lesser General Public          *
  15  * License along with gfxprim; if not, write to the Free Software            *
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor,                        *
  17  * Boston, MA  02110-1301  USA                                               *
  18  *                                                                           *
  19  * Copyright (C) 2009-2012 Cyril Hrubis <metan@ucw.cz>                       *
  20  *                                                                           *
  21  *****************************************************************************/
  22
  23 /*
  24
  25   Hilbert curve implementation.
  26
  27  */
  28
  29 #ifndef FILTERS_GP_HILBERT_CURVE_H
  30 #define FILTERS_GP_HILBERT_CURVE_H
  31
  32 struct GP_CurveState {
  33         /* half of the number of bits of curve size */
  34         unsigned int n;
  35         /* coordinates */
  36         unsigned int x, y;
  37         /* current curve lenght */
  38         unsigned int s;
  39 };
  40
  41 /*
  42  * Resets curve to initial state i.e. x = 0, y = 0, (length) s = 0.
  43  */
  44 static inline void GP_HilbertCurveInit(struct GP_CurveState *state, int n)
  45 {
  46         state->n = n;
  47         state->s = 0;
  48         state->x = 0;
  49         state->y = 0;
  50 }
  51
  52 /*
  53  * Variant of Lam and Shapiro
  54  */
  55 static inline void GP_HilbertCurveGetXY(struct GP_CurveState *state)
  56 {
  57         int sa, sb;
  58         /*
  59          * Older gcc thinks that x and y are used uninitialized that is not
  60          * true so we silence the warning by initializing them.
  61          */
  62         unsigned int i, temp, x = 0, y = 0;
  63
  64         for (i = 0; i < 2 * state->n; i += 2) {
  65                 sa = (state->s >> (i+1)) & 0x01;
  66                 sb = (state->s >> i)     & 0x01;
  67
  68                 if ((sa ^ sb) == 0) {
  69                         temp = x;
  70                         x = y ^ (-sa);
  71                         y = temp ^ (-sa);
  72                 }
  73
  74                 x = (x >> 1) | (sa << 31);
  75                 y = (y >> 1) | ((sa ^ sb) << 31);
  76         }
  77
  78         state->x = x >> (32 - state->n);
  79         state->y = y >> (32 - state->n);
  80 }
  81
  82
  83 /*
  84  * Finds next X and Y
  85  */
  86 static inline void GP_HilbertCurveNext(struct GP_CurveState *state)
  87 {
  88
  89         /* increment length */
  90         state->s++;
  91         /* get X and Y */
  92         GP_HilbertCurveGetXY(state);
  93 }
  94
  95 /*
  96  * Returns true if we are not at curve endpoint
  97  */
  98 static inline int GP_HilbertCurveContinues(struct GP_CurveState *state)
  99 {
 100         return state->s < (1U<<(2*state->n));
 101 }
 102
 103 #endif /* FILTERS_GP_HILBERT_CURVE_H */