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