Line data    Source code

       1             : /*
       2             : Copyright 2016-2017 Esri
       3             : Licensed under the Apache License, Version 2.0 (the "License");
       4             : you may not use this file except in compliance with the License.
       5             : You may obtain a copy of the License at
       6             : http://www.apache.org/licenses/LICENSE-2.0
       7             : Unless required by applicable law or agreed to in writing, software
       8             : distributed under the License is distributed on an "AS IS" BASIS,
       9             : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      10             : See the License for the specific language governing permissions and
      11             : limitations under the License.
      12             : 
      13             : Contributors:  Lucian Plesea
      14             : */
      15             : 
      16             : /*
      17             : 
      18             : A 2D bitmask stored in 4x4 or 8x8 units
      19             : While it is a template over unit type, the only valid types are
      20             : unsigned 16bit and unsigned 64bit
      21             : 
      22             : Obviously not thread safe while any bit gets modified
      23             : 
      24             : */
      25             : #if !defined(BITMASK2D_H)
      26             : #define BITMASK2D_H
      27             : #include <vector>
      28             : #include <stdexcept>
      29             : 
      30             : // For CPL_MSB and swap functions
      31             : #include "cpl_port.h"
      32             : 
      33             : #include "marfa.h"
      34             : #if defined(PACKER)
      35             : #include "Packer.h"
      36             : #endif
      37             : 
      38             : NAMESPACE_MRF_START
      39             : 
      40             : // integer sqrt at compile time
      41             : // N is the number, M is the number of refining iterations
      42             : template <int N, int M = 4> struct Sqrt
      43             : {
      44             :     static const int value =
      45             :         (Sqrt<N, M - 1>::value + N / Sqrt<N, M - 1>::value) / 2;
      46             : };
      47             : 
      48             : // End condition
      49             : template <int N> struct Sqrt<N, 0>
      50             : {
      51             :     static const int value = N / 2;
      52             : };
      53             : 
      54             : // Round up division by N
      55          60 : template <unsigned int N> static int Chunks(int x)
      56             : {
      57          60 :     return 1 + (x - 1) / N;
      58             : }
      59             : 
      60             : //// These exist in C++11, so we name them with upper case
      61             : // template < typename T1, typename T2 > struct Is_Same {
      62             : //     enum { value = false }; // is_same represents a bool.
      63             : //     typedef Is_Same<T1, T2> type; // to qualify as a metafunction.
      64             : // };
      65             : //
      66             : //
      67             : ////// Specialization
      68             : // template < typename T > struct Is_Same<T,T> {
      69             : //     enum { value = true };
      70             : //     typedef Is_Same<T, T> type;
      71             : // };
      72             : //
      73             : 
      74             : // linear size of storage unit, 4 or 8
      75             : #define TGSIZE Sqrt<sizeof(T) * 8>::value
      76             : 
      77             : template <typename T = unsigned long long> class BitMap2D
      78             : {
      79             :   public:
      80             :     // Initialized to all bits set
      81          20 :     BitMap2D(unsigned int width, unsigned int height) : _w(width), _h(height)
      82             :     {
      83             :         // Prevent creation of bitmasks using any other types
      84             : 
      85             :         // Uncomment these statements to enforce only 64 and 16 bit units
      86             :         // They work but generate warnings on some compilers
      87             :         // Is_Same<T, unsigned long long>::type a;
      88             :         // Is_Same<T, unsigned short>::type b;
      89             :         // if (!(a.value || b.value))
      90             :         //   throw std::out_of_range("Only bitmap units of unsigned 16 and 64
      91             :         //   bits work");
      92             : 
      93             :         // Precalculate row size in storage units, for speed
      94          20 :         _lw = Chunks<TGSIZE>(_w);
      95             :         // Defaults to all set
      96          20 :         init(~(T)0);
      97             : #if defined(PACKER)
      98          20 :         _packer = nullptr;
      99             : #endif
     100          20 :     }
     101             : 
     102          20 :     int getWidth() const
     103             :     {
     104          20 :         return _w;
     105             :     }
     106             : 
     107          20 :     int getHeight() const
     108             :     {
     109          20 :         return _h;
     110             :     }
     111             : 
     112             :     // Size in bytes
     113          32 :     size_t size() const
     114             :     {
     115          32 :         return _bits.size() * sizeof(T);
     116             :     }
     117             : 
     118             :     // Returns the condition of a specific bit
     119     2097150 :     bool isSet(int x, int y) const
     120             :     {
     121     2097150 :         return 0 != (_bits[_idx(x, y)] & _bitmask(x, y));
     122             :     }
     123             : 
     124             :     void set(int x, int y)
     125             :     {
     126             :         _bits[_idx(x, y)] |= _bitmask(x, y);
     127             :     }
     128             : 
     129     2340860 :     void clear(int x, int y)
     130             :     {
     131     2340860 :         _bits[_idx(x, y)] &= ~_bitmask(x, y);
     132     2340860 :     }
     133             : 
     134             :     // Set a location bit to true or false
     135             :     void assign(int x, int y, bool val = true)
     136             :     {
     137             :         if (val)
     138             :             set(x, y);
     139             :         else
     140             :             clear(x, y);
     141             :     }
     142             : 
     143             :     // Flip a bit
     144             :     void flip(int x, int y)
     145             :     {
     146             :         _bits[_idx(x, y)] ^= _bitmask(x, y);
     147             :     }
     148             : 
     149             :     // Set all units to same bit pattern by unit
     150             :     // Use init(~(T)0)) for all set
     151          20 :     void init(T val)
     152             :     {
     153          40 :         _bits.assign(
     154          20 :             static_cast<size_t>(Chunks<TGSIZE>(_w)) * Chunks<TGSIZE>(_h), val);
     155          20 :     }
     156             : 
     157             :     // Support for store and load
     158             : #if defined(PACKER)
     159             : 
     160          20 :     void set_packer(Packer *packer)
     161             :     {
     162          20 :         _packer = packer;
     163          20 :     }
     164             : 
     165          12 :     int store(storage_manager *dst)
     166             :     {
     167             :         int result;
     168          12 :         storage_manager src = {reinterpret_cast<char *>(&_bits[0]), size()};
     169             :         // Store the bytes in little endian format
     170          12 :         swab();
     171          12 :         if (_packer)
     172          12 :             result = _packer->store(&src, dst);
     173             :         else
     174           0 :             result = Packer().store(&src, dst);
     175          12 :         swab();
     176          12 :         return result;
     177             :     }
     178             : 
     179           8 :     int load(storage_manager *src)
     180             :     {
     181             :         int result;
     182           8 :         storage_manager dst = {reinterpret_cast<char *>(&_bits[0]), size()};
     183           8 :         if (_packer)
     184           8 :             result = _packer->load(src, &dst);
     185             :         else
     186           0 :             result = Packer().load(src, &dst);
     187           8 :         swab();
     188           8 :         return result;
     189             :     }
     190             : #endif
     191             : 
     192             :   private:
     193             :     // unit index
     194     4438020 :     unsigned int _idx(int x, int y) const
     195             :     {
     196     4438020 :         return _lw * (y / TGSIZE) + x / TGSIZE;
     197             :     }
     198             : 
     199             :     // one bit mask within a unit
     200     4438020 :     static T _bitmask(int x, int y)
     201             :     {
     202     4438020 :         return static_cast<T>(1) << (TGSIZE * (y % TGSIZE) + x % TGSIZE);
     203             :     }
     204             : 
     205             : #if defined(PACKER)
     206             : // Swap bytes of storage units within the bitmap to low endian
     207             : #if defined(CPL_LSB)
     208          32 :     static void swab()
     209             :     {
     210          32 :     }
     211             : #else
     212             :     void swab()
     213             :     {
     214             :         for (size_t i = 0; i < _bits.size(); i++)
     215             :         {
     216             :             if (sizeof(T) == sizeof(GUIntBig))
     217             :             {
     218             :                 CPL_SWAP64PTR(reinterpret_cast<GUIntBig *>(&_bits[i]));
     219             :             }
     220             :             else
     221             :             {
     222             :                 CPL_SWAP16PTR(reinterpret_cast<GUInt16 *>(&_bits[i]));
     223             :             }
     224             :         }
     225             :     }
     226             : #endif
     227             : 
     228             :     // Class that provides export and import capabilities, not owned
     229             :     Packer *_packer;
     230             : #endif
     231             : 
     232             :     // bit storage vector
     233             :     std::vector<T> _bits;
     234             :     // width and height of bitmap
     235             :     unsigned int _w, _h;
     236             :     // Line size in linear chunks
     237             :     unsigned int _lw;
     238             : };
     239             : 
     240             : #undef TGSIZE
     241             : NAMESPACE_MRF_END
     242             : #endif