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 :             CachedTile tmp = std::move(m_aCachedTiles[i]);
     240        6068 :             for (int j = i; j >= 1; --j)
     241        4072 :                 m_aCachedTiles[j] = std::move(m_aCachedTiles[j - 1]);
     242        1996 :             m_aCachedTiles[0] = std::move(tmp);
     243        1996 :             return true;
     244             :         }
     245             :     }
     246         213 :     if (!LoadTile(nTileX, nTileY))
     247             :     {
     248           0 :         return false;
     249             :     }
     250         213 :     m_aCachedTiles[0].m_data[nYInTile * TILE_SIZE + nXInTile] = val;
     251         213 :     m_aCachedTiles[0].m_bModified = true;
     252         213 :     return true;
     253             : }
     254             : 
     255             : /************************************************************************/
     256             : /*                             FlushCache()                             */
     257             : /************************************************************************/
     258             : 
     259             : /** Flush content of modified tiles and drop caches
     260             :  *
     261             :  * @return true if success
     262             :  */
     263             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     264          36 : bool GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::FlushCache()
     265             : {
     266          36 :     bool bRet = true;
     267         202 :     for (int i = 0; i < m_nCachedTileCount; ++i)
     268             :     {
     269         166 :         if (!FlushTile(i))
     270           0 :             bRet = false;
     271         166 :         m_aCachedTiles[i].m_nTileX = -1;
     272         166 :         m_aCachedTiles[i].m_nTileY = -1;
     273             :     }
     274          36 :     return bRet;
     275             : }
     276             : 
     277             : /************************************************************************/
     278             : /*                         ResetModifiedFlag()                          */
     279             : /************************************************************************/
     280             : 
     281             : /** Reset the modified flag for cached tiles.
     282             :  */
     283             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     284          10 : void GDALCachedPixelAccessor<Type, TILE_SIZE,
     285             :                              CACHED_TILE_COUNT>::ResetModifiedFlag()
     286             : {
     287          68 :     for (int i = 0; i < m_nCachedTileCount; ++i)
     288             :     {
     289          58 :         m_aCachedTiles[i].m_bModified = false;
     290             :     }
     291          10 : }
     292             : 
     293             : /************************************************************************/
     294             : /*                  GDALCachedPixelAccessorGetDataType                  */
     295             : /************************************************************************/
     296             : 
     297             : /*! @cond Doxygen_Suppress */
     298             : template <class T> struct GDALCachedPixelAccessorGetDataType
     299             : {
     300             : };
     301             : 
     302             : template <> struct GDALCachedPixelAccessorGetDataType<GByte>
     303             : {
     304             :     static constexpr GDALDataType DataType = GDT_Byte;
     305             : };
     306             : 
     307             : template <> struct GDALCachedPixelAccessorGetDataType<GInt8>
     308             : {
     309             :     static constexpr GDALDataType DataType = GDT_Int8;
     310             : };
     311             : 
     312             : template <> struct GDALCachedPixelAccessorGetDataType<GUInt16>
     313             : {
     314             :     static constexpr GDALDataType DataType = GDT_UInt16;
     315             : };
     316             : 
     317             : template <> struct GDALCachedPixelAccessorGetDataType<GInt16>
     318             : {
     319             :     static constexpr GDALDataType DataType = GDT_Int16;
     320             : };
     321             : 
     322             : template <> struct GDALCachedPixelAccessorGetDataType<GUInt32>
     323             : {
     324             :     static constexpr GDALDataType DataType = GDT_UInt32;
     325             : };
     326             : 
     327             : template <> struct GDALCachedPixelAccessorGetDataType<GInt32>
     328             : {
     329             :     static constexpr GDALDataType DataType = GDT_Int32;
     330             : };
     331             : #if SIZEOF_UNSIGNED_LONG == 8
     332             : // std::uint64_t on Linux 64-bit resolves as unsigned long
     333             : template <> struct GDALCachedPixelAccessorGetDataType<unsigned long>
     334             : {
     335             :     static constexpr GDALDataType DataType = GDT_UInt64;
     336             : };
     337             : 
     338             : template <> struct GDALCachedPixelAccessorGetDataType<long>
     339             : {
     340             :     static constexpr GDALDataType DataType = GDT_Int64;
     341             : };
     342             : #endif
     343             : template <> struct GDALCachedPixelAccessorGetDataType<GUInt64>
     344             : {
     345             :     static constexpr GDALDataType DataType = GDT_UInt64;
     346             : };
     347             : 
     348             : template <> struct GDALCachedPixelAccessorGetDataType<GInt64>
     349             : {
     350             :     static constexpr GDALDataType DataType = GDT_Int64;
     351             : };
     352             : 
     353             : template <> struct GDALCachedPixelAccessorGetDataType<GFloat16>
     354             : {
     355             :     static constexpr GDALDataType DataType = GDT_Float16;
     356             : };
     357             : 
     358             : template <> struct GDALCachedPixelAccessorGetDataType<float>
     359             : {
     360             :     static constexpr GDALDataType DataType = GDT_Float32;
     361             : };
     362             : 
     363             : template <> struct GDALCachedPixelAccessorGetDataType<double>
     364             : {
     365             :     static constexpr GDALDataType DataType = GDT_Float64;
     366             : };
     367             : 
     368             : /*! @endcond */
     369             : 
     370             : /************************************************************************/
     371             : /*                              LoadTile()                              */
     372             : /************************************************************************/
     373             : 
     374             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     375         454 : bool GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::LoadTile(
     376             :     int nTileX, int nTileY)
     377             : {
     378         454 :     if (m_nCachedTileCount == CACHED_TILE_COUNT)
     379             :     {
     380         352 :         if (!FlushTile(CACHED_TILE_COUNT - 1))
     381           0 :             return false;
     382         704 :         CachedTile tmp = std::move(m_aCachedTiles[CACHED_TILE_COUNT - 1]);
     383        1408 :         for (int i = CACHED_TILE_COUNT - 1; i >= 1; --i)
     384        1056 :             m_aCachedTiles[i] = std::move(m_aCachedTiles[i - 1]);
     385         352 :         m_aCachedTiles[0] = std::move(tmp);
     386             :     }
     387             :     else
     388             :     {
     389         102 :         if (m_nCachedTileCount > 0)
     390          81 :             std::swap(m_aCachedTiles[0], m_aCachedTiles[m_nCachedTileCount]);
     391         102 :         m_aCachedTiles[0].m_data.resize(TILE_SIZE * TILE_SIZE);
     392         102 :         m_nCachedTileCount++;
     393             :     }
     394             : 
     395             : #if 0
     396             :     CPLDebug("GDAL", "Load tile(%d, %d) of band %d of dataset %s",
     397             :               nTileX, nTileY, m_poBand->GetBand(),
     398             :               m_poBand->GetDataset() ? m_poBand->GetDataset()->GetDescription() : "(unknown)");
     399             : #endif
     400         454 :     CPLAssert(!m_aCachedTiles[0].m_bModified);
     401         454 :     const int nXOff = nTileX * TILE_SIZE;
     402         454 :     const int nYOff = nTileY * TILE_SIZE;
     403         454 :     const int nReqXSize = std::min(m_poBand->GetXSize() - nXOff, TILE_SIZE);
     404         454 :     const int nReqYSize = std::min(m_poBand->GetYSize() - nYOff, TILE_SIZE);
     405         908 :     if (m_poBand->RasterIO(
     406             :             GF_Read, nXOff, nYOff, nReqXSize, nReqYSize,
     407         454 :             m_aCachedTiles[0].m_data.data(), nReqXSize, nReqYSize,
     408             :             GDALCachedPixelAccessorGetDataType<Type>::DataType, sizeof(Type),
     409         454 :             TILE_SIZE * sizeof(Type), nullptr) != CE_None)
     410             :     {
     411           0 :         m_aCachedTiles[0].m_nTileX = -1;
     412           0 :         m_aCachedTiles[0].m_nTileY = -1;
     413           0 :         return false;
     414             :     }
     415         454 :     m_aCachedTiles[0].m_nTileX = nTileX;
     416         454 :     m_aCachedTiles[0].m_nTileY = nTileY;
     417         454 :     return true;
     418             : }
     419             : 
     420             : /************************************************************************/
     421             : /*                             FlushTile()                              */
     422             : /************************************************************************/
     423             : 
     424             : template <class Type, int TILE_SIZE, int CACHED_TILE_COUNT>
     425         518 : bool GDALCachedPixelAccessor<Type, TILE_SIZE, CACHED_TILE_COUNT>::FlushTile(
     426             :     int iSlot)
     427             : {
     428         518 :     if (!m_aCachedTiles[iSlot].m_bModified)
     429         300 :         return true;
     430             : 
     431         218 :     m_aCachedTiles[iSlot].m_bModified = false;
     432         218 :     const int nXOff = m_aCachedTiles[iSlot].m_nTileX * TILE_SIZE;
     433         218 :     const int nYOff = m_aCachedTiles[iSlot].m_nTileY * TILE_SIZE;
     434         218 :     const int nReqXSize = std::min(m_poBand->GetXSize() - nXOff, TILE_SIZE);
     435         218 :     const int nReqYSize = std::min(m_poBand->GetYSize() - nYOff, TILE_SIZE);
     436         218 :     return m_poBand->RasterIO(
     437             :                GF_Write, nXOff, nYOff, nReqXSize, nReqYSize,
     438         218 :                m_aCachedTiles[iSlot].m_data.data(), nReqXSize, nReqYSize,
     439             :                GDALCachedPixelAccessorGetDataType<Type>::DataType, sizeof(Type),
     440         218 :                TILE_SIZE * sizeof(Type), nullptr) == CE_None;
     441             : }
     442             : 
     443             : #endif  // GDAL_PIXEL_ACCESSOR_INCLUDED