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