Line data    Source code

       1             : /******************************************************************************
       2             :  *
       3             :  * Project:  GDAL
       4             :  * Purpose:  Fast access to individual pixels in a GDALRasterBand
       5             :  * Author:   Even Rouault <even dot rouault at spatialys.com>
       6             :  *
       7             :  ******************************************************************************
       8             :  * Copyright (c) 2022, Planet Labs
       9             :  *
      10             :  * SPDX-License-Identifier: MIT
      11             :  ****************************************************************************/
      12             : 
      13             : #ifndef GDAL_CACHED_PIXEL_ACCESSOR_INCLUDED
      14             : #define GDAL_CACHED_PIXEL_ACCESSOR_INCLUDED
      15             : 
      16             : #include "gdal_priv.h"
      17             : #include "cpl_error.h"
      18             : #include "cpl_float.h"
      19             : 
      20             : #include <algorithm>
      21             : #include <array>
      22             : #include <vector>
      23             : 
      24             : /************************************************************************/
      25             : /*                       GDALCachedPixelAccessor                        */
      26             : /************************************************************************/
      27             : 
      28             : /** Class to have reasonably fast random pixel access to a raster band, when
      29             :  * accessing multiple pixels that are close to each other.
      30             :  *
      31             :  * This gives faster access than using GDALRasterBand::RasterIO() with
      32             :  * a 1x1 window.
      33             :  *
      34             :  * @since GDAL 3.5
      35             :  */
      36             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT = 4>
      37             : class GDALCachedPixelAccessor
      38             : {
      39             :     GDALRasterBand *m_poBand = nullptr;
      40             : 
      41             :     struct CachedTile
      42             :     {
      43             :         std::vector<Type> m_data{};
      44             :         int m_nTileX = -1;
      45             :         int m_nTileY = -1;
      46             :         bool m_bModified = false;
      47             :     };
      48             : 
      49             :     int m_nCachedTileCount = 0;
      50             :     std::array<CachedTile, static_cast<size_t>(CACHED_TILE_COUNT)>
      51             :         m_aCachedTiles{};
      52             : 
      53             :     bool LoadTile(int nTileX, int nTileY);
      54             :     bool FlushTile(int iSlot);
      55             : 
      56             :     Type GetSlowPath(int nTileX, int nTileY, int nXInTile, int nYInTile,
      57             :                      bool *pbSuccess);
      58             :     bool SetSlowPath(int nTileX, int nTileY, int nXInTile, int nYInTile,
      59             :                      Type val);
      60             : 
      61             :     GDALCachedPixelAccessor(const GDALCachedPixelAccessor &) = delete;
      62             :     GDALCachedPixelAccessor &
      63             :     operator=(const GDALCachedPixelAccessor &) = delete;
      64             : 
      65             :   public:
      66             :     explicit GDALCachedPixelAccessor(GDALRasterBand *poBand);
      67             :     ~GDALCachedPixelAccessor();
      68             : 
      69             :     /** Assign the raster band if not known at construction time. */
      70          10 :     void SetBand(GDALRasterBand *poBand)
      71             :     {
      72          10 :         m_poBand = poBand;
      73          10 :     }
      74             : 
      75             :     Type Get(int nX, int nY, bool *pbSuccess = nullptr);
      76             :     bool Set(int nX, int nY, Type val);
      77             : 
      78             :     bool FlushCache();
      79             :     void ResetModifiedFlag();
      80             : };
      81             : 
      82             : /************************************************************************/
      83             : /*                      GDALCachedPixelAccessor()                       */
      84             : /************************************************************************/
      85             : 
      86             : /** Constructor.
      87             :  *
      88             :  * The template accepts the following parameters:
      89             :  * - Type: should be one of GByte, GUInt16, GInt16, GUInt32, GInt32, GUInt64,
      90             :  * GInt64, float or double
      91             :  * - TILE_SIZE: the tile size for the cache of GDALCachedPixelAccessor.
      92             :  *              Use a power of two for faster computation.
      93             :  *              It doesn't need to be the same of the underlying raster
      94             :  * - CACHED_TILE_COUNT: number of tiles to cache. Should be >= 1. Defaults to 4.
      95             :  *
      96             :  * @param poBand Raster band.
      97             :  */
      98             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
      99          21 : GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::
     100             :     GDALCachedPixelAccessor(GDALRasterBand *poBand)
     101          21 :     : m_poBand(poBand)
     102             : {
     103          21 : }
     104             : 
     105             : /************************************************************************/
     106             : /*                      ~GDALCachedPixelAccessor()                      */
     107             : /************************************************************************/
     108             : 
     109             : /** Destructor.
     110             :  *
     111             :  * Will call FlushCache()
     112             :  */
     113             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     114          21 : GDALCachedPixelAccessor<Type, TILE_SIZE,
     115             :                         CACHED_TILE_COUNT>::~GDALCachedPixelAccessor()
     116             : {
     117          21 :     FlushCache();
     118          21 : }
     119             : 
     120             : /************************************************************************/
     121             : /*                                Get()                                 */
     122             : /************************************************************************/
     123             : 
     124             : /** Get the value of a pixel.
     125             :  *
     126             :  * No bound checking of nX, nY is done.
     127             :  *
     128             :  * @param nX X coordinate (between 0 and GetXSize()-1)
     129             :  * @param nY Y coordinate (between 0 and GetYSize()-1)
     130             :  * @param[out] pbSuccess Optional pointer to a success flag
     131             :  * @return the pixel value
     132             :  */
     133             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     134    16223013 : inline Type GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::Get(
     135             :     int nX, int nY, bool *pbSuccess)
     136             : {
     137    16223013 :     const int nTileX = nX / TILE_SIZE;
     138    16223013 :     const int nTileY = nY / TILE_SIZE;
     139    16223013 :     const int nXInTile = nX % TILE_SIZE;
     140    16223013 :     const int nYInTile = nY % TILE_SIZE;
     141    32424607 :     if (m_aCachedTiles[0].m_nTileX == nTileX &&
     142    16201584 :         m_aCachedTiles[0].m_nTileY == nTileY)
     143             :     {
     144    16186884 :         if (pbSuccess)
     145           0 :             *pbSuccess = true;
     146    16186884 :         return m_aCachedTiles[0].m_data[nYInTile * TILE_SIZE + nXInTile];
     147             :     }
     148       36118 :     return GetSlowPath(nTileX, nTileY, nXInTile, nYInTile, pbSuccess);
     149             : }
     150             : 
     151             : /************************************************************************/
     152             : /*                            GetSlowPath()                             */
     153             : /************************************************************************/
     154             : 
     155             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     156       36118 : Type GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::GetSlowPath(
     157             :     int nTileX, int nTileY, int nXInTile, int nYInTile, bool *pbSuccess)
     158             : {
     159       50580 :     for (int i = 1; i < m_nCachedTileCount; ++i)
     160             :     {
     161       50339 :         const auto &cachedTile = m_aCachedTiles[i];
     162       50339 :         if (cachedTile.m_nTileX == nTileX && cachedTile.m_nTileY == nTileY)
     163             :         {
     164       35877 :             const auto ret = cachedTile.m_data[nYInTile * TILE_SIZE + nXInTile];
     165       35877 :             CachedTile tmp = std::move(m_aCachedTiles[i]);
     166       85442 :             for (int j = i; j >= 1; --j)
     167       49565 :                 m_aCachedTiles[j] = std::move(m_aCachedTiles[j - 1]);
     168       35877 :             m_aCachedTiles[0] = std::move(tmp);
     169       35877 :             if (pbSuccess)
     170           0 :                 *pbSuccess = true;
     171       35877 :             return ret;
     172             :         }
     173             :     }
     174         241 :     if (!LoadTile(nTileX, nTileY))
     175             :     {
     176           0 :         if (pbSuccess)
     177           0 :             *pbSuccess = false;
     178           0 :         return 0;
     179             :     }
     180         241 :     if (pbSuccess)
     181           0 :         *pbSuccess = true;
     182         241 :     return m_aCachedTiles[0].m_data[nYInTile * TILE_SIZE + nXInTile];
     183             : }
     184             : 
     185             : /************************************************************************/
     186             : /*                                Set()                                 */
     187             : /************************************************************************/
     188             : 
     189             : /** Set the value of a pixel.
     190             :  *
     191             :  * The actual modification of the underlying raster is deferred until the tile
     192             :  * is implicit flushed while loading a new tile, or an explicit call to
     193             :  * FlushCache().
     194             :  *
     195             :  * The destructor of GDALCachedPixelAccessor will take care of calling
     196             :  * FlushCache(), if the user hasn't done it explicitly.
     197             :  *
     198             :  * No bound checking of nX, nY is done.
     199             :  *
     200             :  * @param nX X coordinate (between 0 and GetXSize()-1)
     201             :  * @param nY Y coordinate (between 0 and GetYSize()-1)
     202             :  * @param val pixel value
     203             :  * @return true if success
     204             :  */
     205             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     206             : inline bool
     207     1475403 : GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::Set(int nX, int nY,
     208             :                                                                  Type val)
     209             : {
     210     1475403 :     const int nTileX = nX / TILE_SIZE;
     211     1475403 :     const int nTileY = nY / TILE_SIZE;
     212     1475403 :     const int nXInTile = nX % TILE_SIZE;
     213     1475403 :     const int nYInTile = nY % TILE_SIZE;
     214     2948607 :     if (m_aCachedTiles[0].m_nTileX == nTileX &&
     215     1473194 :         m_aCachedTiles[0].m_nTileY == nTileY)
     216             :     {
     217     1473194 :         m_aCachedTiles[0].m_data[nYInTile * TILE_SIZE + nXInTile] = val;
     218     1473194 :         m_aCachedTiles[0].m_bModified = true;
     219     1473194 :         return true;
     220             :     }
     221        2209 :     return SetSlowPath(nTileX, nTileY, nXInTile, nYInTile, val);
     222             : }
     223             : 
     224             : /************************************************************************/
     225             : /*                            SetSlowPath()                             */
     226             : /************************************************************************/
     227             : 
     228             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     229        2209 : bool GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::SetSlowPath(
     230             :     int nTileX, int nTileY, int nXInTile, int nYInTile, Type val)
     231             : {
     232        4792 :     for (int i = 1; i < m_nCachedTileCount; ++i)
     233             :     {
     234        4579 :         auto &cachedTile = m_aCachedTiles[i];
     235        4579 :         if (cachedTile.m_nTileX == nTileX && cachedTile.m_nTileY == nTileY)
     236             :         {
     237        1996 :             cachedTile.m_data[nYInTile * TILE_SIZE + nXInTile] = val;
     238        1996 :             cachedTile.m_bModified = true;
     239        1996 :             if (i > 0)
     240             :             {
     241        3992 :                 CachedTile tmp = std::move(m_aCachedTiles[i]);
     242        6068 :                 for (int j = i; j >= 1; --j)
     243        4072 :                     m_aCachedTiles[j] = std::move(m_aCachedTiles[j - 1]);
     244        1996 :                 m_aCachedTiles[0] = std::move(tmp);
     245             :             }
     246        1996 :             return true;
     247             :         }
     248             :     }
     249         213 :     if (!LoadTile(nTileX, nTileY))
     250             :     {
     251           0 :         return false;
     252             :     }
     253         213 :     m_aCachedTiles[0].m_data[nYInTile * TILE_SIZE + nXInTile] = val;
     254         213 :     m_aCachedTiles[0].m_bModified = true;
     255         213 :     return true;
     256             : }
     257             : 
     258             : /************************************************************************/
     259             : /*                             FlushCache()                             */
     260             : /************************************************************************/
     261             : 
     262             : /** Flush content of modified tiles and drop caches
     263             :  *
     264             :  * @return true if success
     265             :  */
     266             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     267          36 : bool GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::FlushCache()
     268             : {
     269          36 :     bool bRet = true;
     270         202 :     for (int i = 0; i < m_nCachedTileCount; ++i)
     271             :     {
     272         166 :         if (!FlushTile(i))
     273           0 :             bRet = false;
     274         166 :         m_aCachedTiles[i].m_nTileX = -1;
     275         166 :         m_aCachedTiles[i].m_nTileY = -1;
     276             :     }
     277          36 :     return bRet;
     278             : }
     279             : 
     280             : /************************************************************************/
     281             : /*                         ResetModifiedFlag()                          */
     282             : /************************************************************************/
     283             : 
     284             : /** Reset the modified flag for cached tiles.
     285             :  */
     286             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     287          10 : void GDALCachedPixelAccessor<Type, TILE_SIZE,
     288             :                              CACHED_TILE_COUNT>::ResetModifiedFlag()
     289             : {
     290          68 :     for (int i = 0; i < m_nCachedTileCount; ++i)
     291             :     {
     292          58 :         m_aCachedTiles[i].m_bModified = false;
     293             :     }
     294          10 : }
     295             : 
     296             : /************************************************************************/
     297             : /*                  GDALCachedPixelAccessorGetDataType                  */
     298             : /************************************************************************/
     299             : 
     300             : /*! @cond Doxygen_Suppress */
     301             : template <class T> struct GDALCachedPixelAccessorGetDataType
     302             : {
     303             : };
     304             : 
     305             : template <> struct GDALCachedPixelAccessorGetDataType<GByte>
     306             : {
     307             :     static constexpr GDALDataType DataType = GDT_Byte;
     308             : };
     309             : 
     310             : template <> struct GDALCachedPixelAccessorGetDataType<GInt8>
     311             : {
     312             :     static constexpr GDALDataType DataType = GDT_Int8;
     313             : };
     314             : 
     315             : template <> struct GDALCachedPixelAccessorGetDataType<GUInt16>
     316             : {
     317             :     static constexpr GDALDataType DataType = GDT_UInt16;
     318             : };
     319             : 
     320             : template <> struct GDALCachedPixelAccessorGetDataType<GInt16>
     321             : {
     322             :     static constexpr GDALDataType DataType = GDT_Int16;
     323             : };
     324             : 
     325             : template <> struct GDALCachedPixelAccessorGetDataType<GUInt32>
     326             : {
     327             :     static constexpr GDALDataType DataType = GDT_UInt32;
     328             : };
     329             : 
     330             : template <> struct GDALCachedPixelAccessorGetDataType<GInt32>
     331             : {
     332             :     static constexpr GDALDataType DataType = GDT_Int32;
     333             : };
     334             : #if SIZEOF_UNSIGNED_LONG == 8
     335             : // std::uint64_t on Linux 64-bit resolves as unsigned long
     336             : template <> struct GDALCachedPixelAccessorGetDataType<unsigned long>
     337             : {
     338             :     static constexpr GDALDataType DataType = GDT_UInt64;
     339             : };
     340             : 
     341             : template <> struct GDALCachedPixelAccessorGetDataType<long>
     342             : {
     343             :     static constexpr GDALDataType DataType = GDT_Int64;
     344             : };
     345             : #endif
     346             : template <> struct GDALCachedPixelAccessorGetDataType<GUInt64>
     347             : {
     348             :     static constexpr GDALDataType DataType = GDT_UInt64;
     349             : };
     350             : 
     351             : template <> struct GDALCachedPixelAccessorGetDataType<GInt64>
     352             : {
     353             :     static constexpr GDALDataType DataType = GDT_Int64;
     354             : };
     355             : 
     356             : template <> struct GDALCachedPixelAccessorGetDataType<GFloat16>
     357             : {
     358             :     static constexpr GDALDataType DataType = GDT_Float16;
     359             : };
     360             : 
     361             : template <> struct GDALCachedPixelAccessorGetDataType<float>
     362             : {
     363             :     static constexpr GDALDataType DataType = GDT_Float32;
     364             : };
     365             : 
     366             : template <> struct GDALCachedPixelAccessorGetDataType<double>
     367             : {
     368             :     static constexpr GDALDataType DataType = GDT_Float64;
     369             : };
     370             : 
     371             : /*! @endcond */
     372             : 
     373             : /************************************************************************/
     374             : /*                              LoadTile()                              */
     375             : /************************************************************************/
     376             : 
     377             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     378         454 : bool GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::LoadTile(
     379             :     int nTileX, int nTileY)
     380             : {
     381         454 :     if (m_nCachedTileCount == CACHED_TILE_COUNT)
     382             :     {
     383         352 :         if (!FlushTile(CACHED_TILE_COUNT - 1))
     384           0 :             return false;
     385         704 :         CachedTile tmp = std::move(m_aCachedTiles[CACHED_TILE_COUNT - 1]);
     386        1408 :         for (int i = CACHED_TILE_COUNT - 1; i >= 1; --i)
     387        1056 :             m_aCachedTiles[i] = std::move(m_aCachedTiles[i - 1]);
     388         352 :         m_aCachedTiles[0] = std::move(tmp);
     389             :     }
     390             :     else
     391             :     {
     392         102 :         if (m_nCachedTileCount > 0)
     393          81 :             std::swap(m_aCachedTiles[0], m_aCachedTiles[m_nCachedTileCount]);
     394         102 :         m_aCachedTiles[0].m_data.resize(TILE_SIZE * TILE_SIZE);
     395         102 :         m_nCachedTileCount++;
     396             :     }
     397             : 
     398             : #if 0
     399             :     CPLDebug("GDAL", "Load tile(%d, %d) of band %d of dataset %s",
     400             :               nTileX, nTileY, m_poBand->GetBand(),
     401             :               m_poBand->GetDataset() ? m_poBand->GetDataset()->GetDescription() : "(unknown)");
     402             : #endif
     403         454 :     CPLAssert(!m_aCachedTiles[0].m_bModified);
     404         454 :     const int nXOff = nTileX * TILE_SIZE;
     405         454 :     const int nYOff = nTileY * TILE_SIZE;
     406         454 :     const int nReqXSize = std::min(m_poBand->GetXSize() - nXOff, TILE_SIZE);
     407         454 :     const int nReqYSize = std::min(m_poBand->GetYSize() - nYOff, TILE_SIZE);
     408         908 :     if (m_poBand->RasterIO(
     409             :             GF_Read, nXOff, nYOff, nReqXSize, nReqYSize,
     410         454 :             m_aCachedTiles[0].m_data.data(), nReqXSize, nReqYSize,
     411             :             GDALCachedPixelAccessorGetDataType<Type>::DataType, sizeof(Type),
     412         454 :             TILE_SIZE * sizeof(Type), nullptr) != CE_None)
     413             :     {
     414           0 :         m_aCachedTiles[0].m_nTileX = -1;
     415           0 :         m_aCachedTiles[0].m_nTileY = -1;
     416           0 :         return false;
     417             :     }
     418         454 :     m_aCachedTiles[0].m_nTileX = nTileX;
     419         454 :     m_aCachedTiles[0].m_nTileY = nTileY;
     420         454 :     return true;
     421             : }
     422             : 
     423             : /************************************************************************/
     424             : /*                             FlushTile()                              */
     425             : /************************************************************************/
     426             : 
     427             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     428         518 : bool GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::FlushTile(
     429             :     int iSlot)
     430             : {
     431         518 :     if (!m_aCachedTiles[iSlot].m_bModified)
     432         300 :         return true;
     433             : 
     434         218 :     m_aCachedTiles[iSlot].m_bModified = false;
     435         218 :     const int nXOff = m_aCachedTiles[iSlot].m_nTileX * TILE_SIZE;
     436         218 :     const int nYOff = m_aCachedTiles[iSlot].m_nTileY * TILE_SIZE;
     437         218 :     const int nReqXSize = std::min(m_poBand->GetXSize() - nXOff, TILE_SIZE);
     438         218 :     const int nReqYSize = std::min(m_poBand->GetYSize() - nYOff, TILE_SIZE);
     439         218 :     return m_poBand->RasterIO(
     440             :                GF_Write, nXOff, nYOff, nReqXSize, nReqYSize,
     441         218 :                m_aCachedTiles[iSlot].m_data.data(), nReqXSize, nReqYSize,
     442             :                GDALCachedPixelAccessorGetDataType<Type>::DataType, sizeof(Type),
     443         218 :                TILE_SIZE * sizeof(Type), nullptr) == CE_None;
     444             : }
     445             : 
     446             : #endif  // GDAL_PIXEL_ACCESSOR_INCLUDED