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         unsigned int i, temp, x, y;
  59
  60         for (i = 0; i < 2 * state->n; i += 2) {
  61                 sa = (state->s >> (i+1)) & 0x01;
  62                 sb = (state->s >> i)     & 0x01;
  63
  64                 if ((sa ^ sb) == 0) {
  65                         temp = x;
  66                         x = y ^ (-sa);
  67                         y = temp ^ (-sa);
  68                 }
  69
  70                 x = (x >> 1) | (sa << 31);
  71                 y = (y >> 1) | ((sa ^ sb) << 31);
  72         }
  73
  74         state->x = x >> (32 - state->n);
  75         state->y = y >> (32 - state->n);
  76 }
  77
  78
  79 /*
  80  * Finds next X and Y
  81  */
  82 static inline void GP_HilbertCurveNext(struct GP_CurveState *state)
  83 {
  84
  85         /* increment length */
  86         state->s++;
  87         /* get X and Y */
  88         GP_HilbertCurveGetXY(state);
  89 }
  90
  91 /*
  92  * Returns true if we are not at curve endpoint
  93  */
  94 static inline int GP_HilbertCurveContinues(struct GP_CurveState *state)
  95 {
  96         return state->s < (1U<<(2*state->n));
  97 }
  98
  99 #endif /* FILTERS_GP_HILBERT_CURVE_H */