boost/gil/algorithm.hpp

   1 //
   2 // Copyright 2005-2007 Adobe Systems Incorporated
   3 //
   4 // Distributed under the Boost Software License, Version 1.0
   5 // See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt
   7 //
   8 #ifndef BOOST_GIL_ALGORITHM_HPP
   9 #define BOOST_GIL_ALGORITHM_HPP
  10
  11 #include <boost/gil/bit_aligned_pixel_iterator.hpp>
  12 #include <boost/gil/color_base_algorithm.hpp>
  13 #include <boost/gil/concepts.hpp>
  14 #include <boost/gil/image_view.hpp>
  15 #include <boost/gil/image_view_factory.hpp>
  16 #include <boost/gil/detail/mp11.hpp>
  17 #include <boost/gil/detail/type_traits.hpp>
  18
  19 #include <boost/assert.hpp>
  20 #include <boost/config.hpp>
  21
  22 #include <algorithm>
  23 #include <cstddef>
  24 #include <cstring>
  25 #include <iterator>
  26 #include <memory>
  27 #include <type_traits>
  28 #include <typeinfo>
  29
  30 namespace boost { namespace gil {
  31
  32 //forward declarations
  33 template <typename ChannelPtr, typename ColorSpace>
  34 struct planar_pixel_iterator;
  35 template <typename Iterator>
  36 class memory_based_step_iterator;
  37 template <typename StepIterator>
  38 class memory_based_2d_locator;
  39
  40 // a tag denoting incompatible arguments
  41 struct error_t {};
  42
  43 /// \defgroup ImageViewSTLAlgorithms STL-like Algorithms
  44 /// \ingroup ImageViewAlgorithm
  45 /// \brief Image view-equivalents of STL algorithms
  46 ///
  47 /// Image views provide 1D iteration of their pixels via \p begin() and \p end() methods,
  48 /// which makes it possible to use STL algorithms with them. However, using nested loops
  49 /// over X and Y is in many cases more efficient. The algorithms in this section resemble
  50 /// STL algorithms, but they abstract away the nested loops and take views (as opposed to ranges) as input.
  51 ///
  52 /// Most algorithms check whether the image views are 1D-traversable. A 1D-traversable image view has no gaps
  53 /// at the end of the rows. In other words, if an x_iterator of that view is advanced past the last pixel in a row
  54 /// it will move to the first pixel of the next row. When image views are 1D-traversable, the algorithms use
  55 /// a single loop and run more efficiently. If one or more of the input views are not 1D-traversable, the algorithms
  56 /// fall-back to an X-loop nested inside a Y-loop.
  57 ///
  58 /// The algorithms typically delegate the work to their corresponding STL algorithms. For example, \p copy_pixels calls
  59 /// \p std::copy either for each row, or, when the images are 1D-traversable, once for all pixels.
  60 ///
  61 /// In addition, overloads are sometimes provided for the STL algorithms. For example, std::copy for planar iterators
  62 /// is overloaded to perform \p std::copy for each of the planes. \p std::copy over bitwise-copiable pixels results in
  63 /// std::copy over unsigned char, which STL typically implements via \p memmove.
  64 ///
  65 /// As a result \p copy_pixels may result in a single call to \p memmove for interleaved 1D-traversable views,
  66 /// or one per each plane of planar 1D-traversable views, or one per each row of interleaved non-1D-traversable images, etc.
  67
  68 /// \defgroup STLOptimizations  Performance overloads of STL algorithms
  69 /// \ingroup ImageViewAlgorithm
  70 /// \brief overloads of STL algorithms allowing more efficient implementation when used with GIL constructs
  71
  72 /// \brief A generic binary operation on views
  73 /// \ingroup ImageViewSTLAlgorithms
  74 ///
  75 /// Use this class as a convenience superclass when defining an operation for any image views.
  76 /// Many operations have different behavior when the two views are compatible. This class checks
  77 /// for compatibility and invokes apply_compatible(V1,V2) or apply_incompatible(V1,V2) of the subclass.
  78 /// You must provide apply_compatible(V1,V2) method in your subclass, but apply_incompatible(V1,V2)
  79 /// is not required and the default throws std::bad_cast.
  80 template <typename Derived, typename Result=void>
  81 struct binary_operation_obj
  82 {
  83     using result_type = Result;
  84
  85     template <typename V1, typename V2> BOOST_FORCEINLINE
  86     result_type operator()(const std::pair<const V1*,const V2*>& p) const {
  87         return apply(*p.first, *p.second, typename views_are_compatible<V1,V2>::type());
  88     }
  89
  90     template <typename V1, typename V2> BOOST_FORCEINLINE
  91     result_type operator()(const V1& v1, const V2& v2) const {
  92         return apply(v1, v2, typename views_are_compatible<V1,V2>::type());
  93     }
  94
  95     result_type operator()(const error_t&) const { throw std::bad_cast(); }
  96 private:
  97
  98     // dispatch from apply overload to a function with distinct name
  99     template <typename V1, typename V2>
 100     BOOST_FORCEINLINE
 101     result_type apply(V1 const& v1, V2 const& v2, std::false_type) const
 102     {
 103         return ((const Derived*)this)->apply_incompatible(v1, v2);
 104     }
 105
 106     // dispatch from apply overload to a function with distinct name
 107     template <typename V1, typename V2>
 108     BOOST_FORCEINLINE
 109     result_type apply(V1 const& v1, V2 const& v2, std::true_type) const
 110     {
 111         return ((const Derived*)this)->apply_compatible(v1, v2);
 112     }
 113
 114     // function with distinct name - it can be overloaded by subclasses
 115     template <typename V1, typename V2>
 116     BOOST_FORCEINLINE
 117     result_type apply_incompatible(V1 const& /*v1*/, V2 const& /*v2*/) const
 118     {
 119         throw std::bad_cast();
 120     }
 121 };
 122
 123 }}  // namespace boost::gil
 124
 125 //////////////////////////////////////////////////////////////////////////////////////
 126 // std::copy and gil::copy_pixels
 127 //////////////////////////////////////////////////////////////////////////////////////
 128
 129 /// \defgroup ImageViewSTLAlgorithmsCopyPixels copy_pixels
 130 /// \ingroup ImageViewSTLAlgorithms
 131 /// \brief std::copy for image views
 132
 133 namespace std {
 134
 135 /// \ingroup STLOptimizations
 136 /// \brief Copy when both src and dst are interleaved and of the same type can be just memmove
 137 template<typename T, typename CS>
 138 BOOST_FORCEINLINE
 139 auto copy(
 140     boost::gil::pixel<T, CS>* first,
 141     boost::gil::pixel<T, CS>* last,
 142     boost::gil::pixel<T, CS>* dst)
 143     ->  boost::gil::pixel<T, CS>*
 144 {
 145     auto p = std::copy((unsigned char*)first, (unsigned char*)last, (unsigned char*)dst);
 146     return reinterpret_cast<boost::gil::pixel<T, CS>*>(p);
 147 }
 148
 149 /// \ingroup STLOptimizations
 150 /// \brief Copy when both src and dst are interleaved and of the same type can be just memmove
 151 template<typename T, typename CS>
 152 BOOST_FORCEINLINE boost::gil::pixel<T,CS>*
 153 copy(const boost::gil::pixel<T,CS>* first, const boost::gil::pixel<T,CS>* last,
 154      boost::gil::pixel<T,CS>* dst) {
 155     return (boost::gil::pixel<T,CS>*)std::copy((unsigned char*)first,(unsigned char*)last, (unsigned char*)dst);
 156 }
 157 } // namespace std
 158
 159 namespace boost { namespace gil {
 160 namespace detail {
 161 template <typename I, typename O> struct copy_fn {
 162     BOOST_FORCEINLINE I operator()(I first, I last, O dst) const { return std::copy(first,last,dst); }
 163 };
 164 } // namespace detail
 165 } }  // namespace boost::gil
 166
 167 namespace std {
 168 /// \ingroup STLOptimizations
 169 /// \brief Copy when both src and dst are planar pointers is copy for each channel
 170 template<typename CS, typename IC1, typename IC2> BOOST_FORCEINLINE
 171 boost::gil::planar_pixel_iterator<IC2,CS> copy(boost::gil::planar_pixel_iterator<IC1,CS> first, boost::gil::planar_pixel_iterator<IC1,CS> last, boost::gil::planar_pixel_iterator<IC2,CS> dst) {
 172     boost::gil::gil_function_requires<boost::gil::ChannelsCompatibleConcept<typename std::iterator_traits<IC1>::value_type,typename std::iterator_traits<IC2>::value_type>>();
 173     static_for_each(first,last,dst,boost::gil::detail::copy_fn<IC1,IC2>());
 174     return dst+(last-first);
 175 }
 176 } // namespace std
 177
 178 namespace boost { namespace gil {
 179 namespace detail {
 180 /// Does a copy-n. If the inputs contain image iterators, performs a copy at each row using the row iterators
 181 /// \ingroup CopyPixels
 182 template <typename I, typename O>
 183 struct copier_n {
 184     BOOST_FORCEINLINE void operator()(I src, typename std::iterator_traits<I>::difference_type n, O dst) const { std::copy(src,src+n, dst); }
 185 };
 186
 187 /// Source range is delimited by image iterators
 188 template <typename IL, typename O>  // IL Models ConstPixelLocatorConcept, O Models PixelIteratorConcept
 189 struct copier_n<iterator_from_2d<IL>,O> {
 190     using diff_t = typename std::iterator_traits<iterator_from_2d<IL>>::difference_type;
 191     BOOST_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, O dst) const {
 192         gil_function_requires<PixelLocatorConcept<IL>>();
 193         gil_function_requires<MutablePixelIteratorConcept<O>>();
 194         while (n>0) {
 195             diff_t l=src.width()-src.x_pos();
 196             diff_t numToCopy=(n<l ? n:l);
 197             detail::copy_n(src.x(), numToCopy, dst);
 198             dst+=numToCopy;
 199             src+=numToCopy;
 200             n-=numToCopy;
 201         }
 202     }
 203 };
 204
 205 /// Destination range is delimited by image iterators
 206 template <typename I, typename OL> // I Models ConstPixelIteratorConcept, OL Models PixelLocatorConcept
 207 struct copier_n<I,iterator_from_2d<OL>> {
 208     using diff_t = typename std::iterator_traits<I>::difference_type;
 209     BOOST_FORCEINLINE void operator()(I src, diff_t n, iterator_from_2d<OL> dst) const {
 210         gil_function_requires<PixelIteratorConcept<I>>();
 211         gil_function_requires<MutablePixelLocatorConcept<OL>>();
 212         while (n>0) {
 213             diff_t l=dst.width()-dst.x_pos();
 214             diff_t numToCopy=(n<l ? n:l);
 215             detail::copy_n(src, numToCopy, dst.x());
 216             dst+=numToCopy;
 217             src+=numToCopy;
 218             n-=numToCopy;
 219         }
 220     }
 221 };
 222
 223 /// Both source and destination ranges are delimited by image iterators
 224 template <typename IL, typename OL>
 225 struct copier_n<iterator_from_2d<IL>,iterator_from_2d<OL>> {
 226    using diff_t = typename iterator_from_2d<IL>::difference_type;
 227    BOOST_FORCEINLINE void operator()(iterator_from_2d<IL> src, diff_t n, iterator_from_2d<OL> dst) const {
 228         gil_function_requires<PixelLocatorConcept<IL>>();
 229         gil_function_requires<MutablePixelLocatorConcept<OL>>();
 230         if (src.x_pos()!=dst.x_pos() || src.width()!=dst.width()) {
 231             while(n-->0) {
 232                 *dst++=*src++;
 233             }
 234         }
 235         while (n>0) {
 236             diff_t l=dst.width()-dst.x_pos();
 237             diff_t numToCopy=(n<l ? n : l);
 238             detail::copy_n(src.x(), numToCopy, dst.x());
 239             dst+=numToCopy;
 240             src+=numToCopy;
 241             n-=numToCopy;
 242         }
 243     }
 244 };
 245
 246 template <typename SrcIterator, typename DstIterator>
 247 BOOST_FORCEINLINE DstIterator copy_with_2d_iterators(SrcIterator first, SrcIterator last, DstIterator dst) {
 248     using src_x_iterator = typename SrcIterator::x_iterator;
 249     using dst_x_iterator = typename DstIterator::x_iterator;
 250
 251     typename SrcIterator::difference_type n = last - first;
 252
 253     if (first.is_1d_traversable()) {
 254         if (dst.is_1d_traversable())
 255             copier_n<src_x_iterator,dst_x_iterator>()(first.x(),n, dst.x());
 256         else
 257             copier_n<src_x_iterator,DstIterator >()(first.x(),n, dst);
 258     } else {
 259         if (dst.is_1d_traversable())
 260             copier_n<SrcIterator,dst_x_iterator>()(first,n, dst.x());
 261         else
 262             copier_n<SrcIterator,DstIterator>()(first,n,dst);
 263     }
 264     return dst+n;
 265 }
 266 } // namespace detail
 267 } }  // namespace boost::gil
 268
 269 namespace std {
 270 /// \ingroup STLOptimizations
 271 /// \brief  std::copy(I1,I1,I2) with I1 and I2 being a iterator_from_2d
 272 template <typename IL, typename OL>
 273 BOOST_FORCEINLINE boost::gil::iterator_from_2d<OL> copy1(boost::gil::iterator_from_2d<IL> first, boost::gil::iterator_from_2d<IL> last, boost::gil::iterator_from_2d<OL> dst) {
 274     return boost::gil::detail::copy_with_2d_iterators(first,last,dst);
 275 }
 276 } // namespace std
 277
 278 namespace boost { namespace gil {
 279 /// \ingroup ImageViewSTLAlgorithmsCopyPixels
 280 /// \brief std::copy for image views
 281 template <typename View1, typename View2> BOOST_FORCEINLINE
 282 void copy_pixels(const View1& src, const View2& dst)
 283 {
 284     BOOST_ASSERT(src.dimensions() == dst.dimensions());
 285     detail::copy_with_2d_iterators(src.begin(),src.end(),dst.begin());
 286 }
 287
 288 //////////////////////////////////////////////////////////////////////////////////////
 289 // copy_and_convert_pixels
 290 //////////////////////////////////////////////////////////////////////////////////////
 291
 292 /// \defgroup ImageViewSTLAlgorithmsCopyAndConvertPixels copy_and_convert_pixels
 293 /// \ingroup ImageViewSTLAlgorithms
 294 /// \brief copies src view into dst view, color converting if necessary.
 295 ///
 296 /// Versions taking static and runtime views are provided. Versions taking user-defined color convered are provided.
 297
 298 namespace detail {
 299 template <typename CC>
 300 class copy_and_convert_pixels_fn : public binary_operation_obj<copy_and_convert_pixels_fn<CC>>
 301 {
 302 private:
 303     CC _cc;
 304 public:
 305     using result_type = typename binary_operation_obj<copy_and_convert_pixels_fn<default_color_converter>>::result_type;
 306     copy_and_convert_pixels_fn() {}
 307     copy_and_convert_pixels_fn(CC cc_in) : _cc(cc_in) {}
 308    // when the two color spaces are incompatible, a color conversion is performed
 309     template <typename V1, typename V2> BOOST_FORCEINLINE
 310     result_type apply_incompatible(const V1& src, const V2& dst) const {
 311         copy_pixels(color_converted_view<typename V2::value_type>(src,_cc),dst);
 312     }
 313
 314     // If the two color spaces are compatible, copy_and_convert is just copy
 315     template <typename V1, typename V2> BOOST_FORCEINLINE
 316     result_type apply_compatible(const V1& src, const V2& dst) const {
 317          copy_pixels(src,dst);
 318     }
 319 };
 320 } // namespace detail
 321
 322 /// \ingroup ImageViewSTLAlgorithmsCopyAndConvertPixels
 323 template <typename V1, typename V2,typename CC>
 324 BOOST_FORCEINLINE
 325 void copy_and_convert_pixels(const V1& src, const V2& dst,CC cc) {
 326     detail::copy_and_convert_pixels_fn<CC> ccp(cc);
 327     ccp(src,dst);
 328 }
 329
 330 struct default_color_converter;
 331
 332 /// \ingroup ImageViewSTLAlgorithmsCopyAndConvertPixels
 333 template <typename View1, typename View2>
 334 BOOST_FORCEINLINE
 335 void copy_and_convert_pixels(const View1& src, const View2& dst) {
 336     detail::copy_and_convert_pixels_fn<default_color_converter> ccp;
 337     ccp(src,dst);
 338 }
 339 } }  // namespace boost::gil
 340
 341 //////////////////////////////////////////////////////////////////////////////////////
 342 // std::fill and gil::fill_pixels
 343 //////////////////////////////////////////////////////////////////////////////////////
 344
 345 /// \defgroup ImageViewSTLAlgorithmsFillPixels fill_pixels
 346 /// \ingroup ImageViewSTLAlgorithms
 347 /// \brief std::fill for image views
 348
 349 namespace std {
 350 /// \ingroup STLOptimizations
 351 /// \brief std::fill(I,I,V) with I being a iterator_from_2d
 352 ///
 353 /// Invoked when one calls std::fill(I,I,V) with I being a iterator_from_2d (which is
 354 /// a 1D iterator over the pixels in an image). For contiguous images (i.e. images that have
 355 /// no alignment gap at the end of each row) it is more efficient to use the underlying
 356 /// pixel iterator that does not check for the end of rows. For non-contiguous images fill
 357 /// resolves to fill of each row using the underlying pixel iterator, which is still faster
 358 template <typename IL, typename V>
 359 void fill(boost::gil::iterator_from_2d<IL> first, boost::gil::iterator_from_2d<IL> last, const V& val) {
 360     boost::gil::gil_function_requires<boost::gil::MutablePixelLocatorConcept<IL>>();
 361     if (first.is_1d_traversable()) {
 362         std::fill(first.x(), last.x(), val);
 363     } else {
 364         // fill row by row
 365         std::ptrdiff_t n=last-first;
 366         while (n>0) {
 367             std::ptrdiff_t numToDo=std::min<const std::ptrdiff_t>(n,(std::ptrdiff_t)(first.width()-first.x_pos()));
 368             std::fill_n(first.x(), numToDo, val);
 369             first+=numToDo;
 370             n-=numToDo;
 371         }
 372     }
 373 }
 374 } // namespace std
 375
 376 namespace boost { namespace gil {
 377
 378 namespace detail {
 379
 380 /// struct to do std::fill
 381 struct std_fill_t {
 382     template <typename It, typename P>
 383     void operator()(It first, It last, const P& p_in) {
 384         std::fill(first,last,p_in);
 385     }
 386 };
 387
 388 /// std::fill for planar iterators
 389 template <typename It, typename P>
 390 BOOST_FORCEINLINE
 391 void fill_aux(It first, It last, P const& p, std::true_type)
 392 {
 393     static_for_each(first, last, p, std_fill_t());
 394 }
 395
 396 /// std::fill for interleaved iterators
 397 template <typename It, typename P>
 398 BOOST_FORCEINLINE
 399 void fill_aux(It first, It last, P const& p, std::false_type)
 400 {
 401     std::fill(first, last, p);
 402 }
 403
 404 } // namespace detail
 405
 406 /// \ingroup ImageViewSTLAlgorithmsFillPixels
 407 /// \brief std::fill for image views
 408 template <typename View, typename Value>
 409 BOOST_FORCEINLINE
 410 void fill_pixels(View const& view, Value const& value)
 411 {
 412     if (view.is_1d_traversable())
 413     {
 414         detail::fill_aux(
 415             view.begin().x(), view.end().x(), value, is_planar<View>());
 416     }
 417     else
 418     {
 419         for (std::ptrdiff_t y = 0; y < view.height(); ++y)
 420             detail::fill_aux(
 421                 view.row_begin(y), view.row_end(y), value, is_planar<View>());
 422     }
 423 }
 424
 425 //////////////////////////////////////////////////////////////////////////////////////
 426 // destruct_pixels
 427 //////////////////////////////////////////////////////////////////////////////////////
 428
 429 /// \defgroup ImageViewSTLAlgorithmsDestructPixels destruct_pixels
 430 /// \ingroup ImageViewSTLAlgorithms
 431 /// \brief invokes the destructor on every pixel of an image view
 432
 433 namespace detail {
 434 template <typename Iterator>
 435 BOOST_FORCEINLINE
 436 void destruct_range_impl(Iterator first, Iterator last,
 437     typename std::enable_if
 438     <
 439         mp11::mp_and
 440         <
 441             std::is_pointer<Iterator>,
 442             mp11::mp_not
 443             <
 444                 detail::is_trivially_destructible<typename std::iterator_traits<Iterator>::value_type>
 445             >
 446         >::value
 447     >::type* /*ptr*/ = 0)
 448 {
 449     while (first != last)
 450     {
 451         first->~value_t();
 452         ++first;
 453     }
 454 }
 455
 456 template <typename Iterator>
 457 BOOST_FORCEINLINE
 458 void destruct_range_impl(Iterator /*first*/, Iterator /*last*/,
 459     typename std::enable_if
 460     <
 461         mp11::mp_or
 462         <
 463             mp11::mp_not<std::is_pointer<Iterator>>,
 464             detail::is_trivially_destructible<typename std::iterator_traits<Iterator>::value_type>
 465         >::value
 466     >::type* /* ptr */ = nullptr)
 467 {
 468 }
 469
 470 template <typename Iterator>
 471 BOOST_FORCEINLINE
 472 void destruct_range(Iterator first, Iterator last)
 473 {
 474     destruct_range_impl(first, last);
 475 }
 476
 477 struct std_destruct_t
 478 {
 479     template <typename Iterator>
 480     void operator()(Iterator first, Iterator last) const
 481     {
 482         destruct_range(first,last);
 483     }
 484 };
 485
 486 /// destruct for planar iterators
 487 template <typename It>
 488 BOOST_FORCEINLINE
 489 void destruct_aux(It first, It last, std::true_type)
 490 {
 491     static_for_each(first,last,std_destruct_t());
 492 }
 493
 494 /// destruct for interleaved iterators
 495 template <typename It>
 496 BOOST_FORCEINLINE
 497 void destruct_aux(It first, It last, std::false_type)
 498 {
 499     destruct_range(first,last);
 500 }
 501
 502 } // namespace detail
 503
 504 /// \ingroup ImageViewSTLAlgorithmsDestructPixels
 505 /// \brief Invokes the in-place destructor on every pixel of the view
 506 template <typename View>
 507 BOOST_FORCEINLINE
 508 void destruct_pixels(View const& view)
 509 {
 510     if (view.is_1d_traversable())
 511     {
 512         detail::destruct_aux(
 513             view.begin().x(), view.end().x(), is_planar<View>());
 514     }
 515     else
 516     {
 517         for (std::ptrdiff_t y = 0; y < view.height(); ++y)
 518             detail::destruct_aux(
 519                 view.row_begin(y), view.row_end(y), is_planar<View>());
 520     }
 521 }
 522
 523 //////////////////////////////////////////////////////////////////////////////////////
 524 // uninitialized_fill_pixels
 525 //////////////////////////////////////////////////////////////////////////////////////
 526
 527 /// \defgroup ImageViewSTLAlgorithmsUninitializedFillPixels uninitialized_fill_pixels
 528 /// \ingroup ImageViewSTLAlgorithms
 529 /// \brief std::uninitialized_fill for image views
 530
 531 namespace detail {
 532
 533 /// std::uninitialized_fill for planar iterators
 534 /// If an exception is thrown destructs any in-place copy-constructed objects
 535 template <typename It, typename P>
 536 BOOST_FORCEINLINE
 537 void uninitialized_fill_aux(It first, It last, P const& p, std::true_type)
 538 {
 539     int channel = 0;
 540     try
 541     {
 542         using pixel_t = typename std::iterator_traits<It>::value_type;
 543         while (channel < num_channels<pixel_t>::value)
 544         {
 545             std::uninitialized_fill(
 546                 dynamic_at_c(first,channel),
 547                 dynamic_at_c(last,channel),
 548                 dynamic_at_c(p,channel));
 549
 550             ++channel;
 551         }
 552     }
 553     catch (...)
 554     {
 555         for (int c = 0; c < channel; ++c)
 556             destruct_range(dynamic_at_c(first, c), dynamic_at_c(last, c));
 557         throw;
 558     }
 559 }
 560
 561 /// std::uninitialized_fill for interleaved iterators
 562 /// If an exception is thrown destructs any in-place copy-constructed objects
 563 template <typename It, typename P>
 564 BOOST_FORCEINLINE
 565 void uninitialized_fill_aux(It first, It last, P const& p, std::false_type)
 566 {
 567     std::uninitialized_fill(first,last,p);
 568 }
 569
 570 } // namespace detail
 571
 572 /// \ingroup ImageViewSTLAlgorithmsUninitializedFillPixels
 573 /// \brief std::uninitialized_fill for image views.
 574 /// Does not support planar heterogeneous views.
 575 /// If an exception is thrown destructs any in-place copy-constructed pixels
 576 template <typename View, typename Value>
 577 void uninitialized_fill_pixels(const View& view, const Value& val) {
 578     if (view.is_1d_traversable())
 579         detail::uninitialized_fill_aux(view.begin().x(), view.end().x(),
 580                                        val,is_planar<View>());
 581     else {
 582         typename View::y_coord_t y = 0;
 583         try {
 584             for (y=0; y<view.height(); ++y)
 585                 detail::uninitialized_fill_aux(view.row_begin(y),view.row_end(y),
 586                                                val,is_planar<View>());
 587         } catch(...) {
 588             for (typename View::y_coord_t y0=0; y0<y; ++y0)
 589                 detail::destruct_aux(view.row_begin(y0),view.row_end(y0), is_planar<View>());
 590             throw;
 591         }
 592     }
 593 }
 594
 595 //////////////////////////////////////////////////////////////////////////////////////
 596 // default_construct_pixels
 597 //////////////////////////////////////////////////////////////////////////////////////
 598
 599 /// \defgroup ImageViewSTLAlgorithmsDefaultConstructPixels default_construct_pixels
 600 /// \ingroup ImageViewSTLAlgorithms
 601 /// \brief invokes the default constructor on every pixel of an image view
 602
 603 namespace detail {
 604 template <typename It> BOOST_FORCEINLINE
 605 void default_construct_range_impl(It first, It last, std::true_type)
 606 {
 607     It first1 = first;
 608     try
 609     {
 610         using value_t = typename std::iterator_traits<It>::value_type;
 611         while (first != last)
 612         {
 613             new (first) value_t();
 614             ++first;
 615         }
 616     }
 617     catch (...)
 618     {
 619         destruct_range(first1, first);
 620         throw;
 621     }
 622 }
 623
 624 template <typename It>
 625 BOOST_FORCEINLINE
 626 void default_construct_range_impl(It, It, std::false_type) {}
 627
 628 template <typename It>
 629 BOOST_FORCEINLINE
 630 void default_construct_range(It first, It last)
 631 {
 632     default_construct_range_impl(first, last, typename std::is_pointer<It>::type());
 633 }
 634
 635 /// uninitialized_default_construct for planar iterators
 636 template <typename It>
 637 BOOST_FORCEINLINE
 638 void default_construct_aux(It first, It last, std::true_type)
 639 {
 640     int channel = 0;
 641     try
 642     {
 643         using pixel_t = typename std::iterator_traits<It>::value_type;
 644         while (channel < num_channels<pixel_t>::value)
 645         {
 646             default_construct_range(dynamic_at_c(first, channel), dynamic_at_c(last, channel));
 647             ++channel;
 648         }
 649     }
 650     catch (...)
 651     {
 652         for (int c = 0; c < channel; ++c)
 653             destruct_range(dynamic_at_c(first, c), dynamic_at_c(last, c));
 654         throw;
 655     }
 656 }
 657
 658 /// uninitialized_default_construct for interleaved iterators
 659 template <typename It>
 660 BOOST_FORCEINLINE
 661 void default_construct_aux(It first, It last, std::false_type)
 662 {
 663     default_construct_range(first, last);
 664 }
 665
 666 template <typename View, bool IsPlanar>
 667 struct has_trivial_pixel_constructor
 668     : detail::is_trivially_default_constructible<typename View::value_type>
 669 {};
 670
 671 template <typename View>
 672 struct has_trivial_pixel_constructor<View, true>
 673     : detail::is_trivially_default_constructible<typename channel_type<View>::type>
 674 {};
 675
 676 template<typename View, bool IsTriviallyConstructible>
 677 BOOST_FORCEINLINE
 678 void default_construct_pixels_impl(
 679     View const& view,
 680     std::enable_if<!IsTriviallyConstructible>* /*ptr*/ = nullptr)
 681 {
 682     if (view.is_1d_traversable())
 683     {
 684         detail::default_construct_aux(
 685             view.begin().x(), view.end().x(), is_planar<View>());
 686     }
 687     else
 688     {
 689         typename View::y_coord_t y = 0;
 690         try
 691         {
 692             for( y = 0; y < view.height(); ++y )
 693                 detail::default_construct_aux(
 694                     view.row_begin(y), view.row_end(y), is_planar<View>());
 695         }
 696         catch(...)
 697         {
 698             for (typename View::y_coord_t y0 = 0; y0 < y; ++y0 )
 699                 detail::destruct_aux(
 700                     view.row_begin(y0), view.row_end(y0), is_planar<View>());
 701
 702             throw;
 703         }
 704     }
 705 }
 706
 707 } // namespace detail
 708
 709 /// \ingroup ImageViewSTLAlgorithmsDefaultConstructPixels
 710 /// \brief Invokes the in-place default constructor on every pixel of the (uninitialized) view.
 711 /// Does not support planar heterogeneous views.
 712 /// If an exception is thrown destructs any in-place default-constructed pixels
 713 template <typename View>
 714 void default_construct_pixels(View const& view)
 715 {
 716     detail::default_construct_pixels_impl
 717         <
 718             View,
 719             detail::has_trivial_pixel_constructor
 720             <
 721                 View,
 722                 is_planar<View>::value
 723             >::value
 724         >(view);
 725 }
 726
 727 //////////////////////////////////////////////////////////////////////////////////////
 728 // uninitialized_copy_pixels
 729 //////////////////////////////////////////////////////////////////////////////////////
 730
 731 /// \defgroup ImageViewSTLAlgorithmsUninitializedCopyPixels uninitialized_copy_pixels
 732 /// \ingroup ImageViewSTLAlgorithms
 733 /// \brief std::uninitialized_copy for image views
 734
 735 namespace detail {
 736
 737 /// std::uninitialized_copy for pairs of planar iterators
 738 template <typename It1, typename It2>
 739 BOOST_FORCEINLINE
 740 void uninitialized_copy_aux(It1 first1, It1 last1, It2 first2, std::true_type)
 741 {
 742     int channel=0;
 743     try {
 744         using pixel_t = typename std::iterator_traits<It1>::value_type;
 745         while (channel < num_channels<pixel_t>::value)
 746         {
 747             std::uninitialized_copy(
 748                 dynamic_at_c(first1, channel),
 749                 dynamic_at_c(last1, channel),
 750                 dynamic_at_c(first2, channel));
 751             ++channel;
 752         }
 753     }
 754     catch (...)
 755     {
 756         It2 last2 = first2;
 757         std::advance(last2, std::distance(first1, last1));
 758         for (int c = 0; c < channel; ++c)
 759             destruct_range(dynamic_at_c(first2, c), dynamic_at_c(last2, c));
 760         throw;
 761     }
 762 }
 763
 764 /// std::uninitialized_copy for interleaved or mixed iterators
 765 template <typename It1, typename It2>
 766 BOOST_FORCEINLINE
 767 void uninitialized_copy_aux(It1 first1, It1 last1, It2 first2, std::false_type)
 768 {
 769     std::uninitialized_copy(first1, last1, first2);
 770 }
 771 } // namespace detail
 772
 773 /// \ingroup ImageViewSTLAlgorithmsUninitializedCopyPixels
 774 /// \brief std::uninitialized_copy for image views.
 775 /// Does not support planar heterogeneous views.
 776 /// If an exception is thrown destructs any in-place copy-constructed objects
 777 template <typename View1, typename View2>
 778 void uninitialized_copy_pixels(View1 const& view1, View2 const& view2)
 779 {
 780     using is_planar = std::integral_constant<bool, is_planar<View1>::value && is_planar<View2>::value>;
 781     BOOST_ASSERT(view1.dimensions() == view2.dimensions());
 782
 783     if (view1.is_1d_traversable() && view2.is_1d_traversable())
 784     {
 785         detail::uninitialized_copy_aux(
 786             view1.begin().x(), view1.end().x(), view2.begin().x(), is_planar());
 787     }
 788     else
 789     {
 790         typename View1::y_coord_t y = 0;
 791         try
 792         {
 793             for (y = 0; y < view1.height(); ++y)
 794                 detail::uninitialized_copy_aux(
 795                     view1.row_begin(y), view1.row_end(y), view2.row_begin(y), is_planar());
 796         }
 797         catch(...)
 798         {
 799             for (typename View1::y_coord_t y0 = 0; y0 < y; ++y0)
 800                 detail::destruct_aux(view2.row_begin(y0), view2.row_end(y0), is_planar());
 801             throw;
 802         }
 803     }
 804 }
 805
 806 //////////////////////////////////////////////////////////////////////////////////////
 807 // for_each_pixel
 808 //////////////////////////////////////////////////////////////////////////////////////
 809
 810 /// \defgroup ImageViewSTLAlgorithmsForEachPixel for_each_pixel
 811 /// \ingroup ImageViewSTLAlgorithms
 812 /// \brief std::for_each for image views
 813 ///
 814 /// For contiguous images (i.e. images that have no alignment gap at the end of each row) it is
 815 /// more efficient to use the underlying pixel iterator that does not check for the end of rows.
 816 /// For non-contiguous images for_each_pixel resolves to for_each of each row using the underlying
 817 /// pixel iterator, which is still faster
 818
 819 /// \ingroup ImageViewSTLAlgorithmsForEachPixel
 820 template <typename View, typename F>
 821 F for_each_pixel(View const& view, F fun)
 822 {
 823     if (view.is_1d_traversable())
 824     {
 825         return std::for_each(view.begin().x(), view.end().x(), fun);
 826     }
 827     else
 828     {
 829         for (std::ptrdiff_t y = 0; y < view.height(); ++y)
 830             std::for_each(view.row_begin(y), view.row_end(y), fun);
 831         return fun;
 832     }
 833 }
 834
 835 /// \defgroup ImageViewSTLAlgorithmsForEachPixelPosition for_each_pixel_position
 836 /// \ingroup ImageViewSTLAlgorithms
 837 /// \brief adobe::for_each_position for image views (passes locators, instead of pixel references, to the function object)
 838
 839 /// \ingroup ImageViewSTLAlgorithmsForEachPixelPosition
 840 template <typename View, typename F>
 841 F for_each_pixel_position(View const& view, F fun)
 842 {
 843     typename View::xy_locator loc = view.xy_at(0, 0);
 844     for (std::ptrdiff_t y = 0; y < view.height(); ++y)
 845     {
 846         for (std::ptrdiff_t x = 0; x < view.width(); ++x, ++loc.x())
 847             fun(loc);
 848         loc.x() -= view.width(); ++loc.y();
 849     }
 850     return fun;
 851 }
 852
 853 //////////////////////////////////////////////////////////////////////////////////////
 854 // generate_pixels
 855 //////////////////////////////////////////////////////////////////////////////////////
 856
 857 /// \defgroup ImageViewSTLAlgorithmsGeneratePixels generate_pixels
 858 /// \ingroup ImageViewSTLAlgorithms
 859 /// \brief std::generate for image views
 860
 861 /// \ingroup ImageViewSTLAlgorithmsGeneratePixels
 862 /// \brief std::generate for image views
 863 template <typename View, typename F>
 864 void generate_pixels(View const& view, F fun)
 865 {
 866     if (view.is_1d_traversable())
 867     {
 868         std::generate(view.begin().x(), view.end().x(), fun);
 869     }
 870     else
 871     {
 872         for (std::ptrdiff_t y = 0; y < view.height(); ++y)
 873             std::generate(view.row_begin(y), view.row_end(y), fun);
 874     }
 875 }
 876
 877 //////////////////////////////////////////////////////////////////////////////////////
 878 // std::equal and gil::equal_pixels for GIL constructs
 879 //////////////////////////////////////////////////////////////////////////////////////
 880
 881 /// \defgroup ImageViewSTLAlgorithmsEqualPixels equal_pixels
 882 /// \ingroup ImageViewSTLAlgorithms
 883 /// \brief std::equal for image views
 884
 885 template <typename I1, typename I2>
 886 BOOST_FORCEINLINE
 887 bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2);
 888
 889 namespace detail {
 890
 891 template <typename I1, typename I2>
 892 struct equal_n_fn
 893 {
 894     BOOST_FORCEINLINE
 895     bool operator()(I1 i1, std::ptrdiff_t n, I2 i2) const
 896     {
 897         return std::equal(i1, i1 + n, i2);
 898     }
 899 };
 900
 901 /// Equal when both ranges are interleaved and of the same type.
 902 /// GIL pixels are bitwise comparable, so memcmp is used. User-defined pixels that are not bitwise comparable need to provide an overload
 903 template<typename T, typename CS>
 904 struct equal_n_fn<pixel<T, CS> const*, pixel<T, CS> const*>
 905 {
 906     BOOST_FORCEINLINE
 907     bool operator()(pixel<T, CS> const* i1, std::ptrdiff_t n, pixel<T, CS> const* i2) const
 908     {
 909         return memcmp(i1, i2, n * sizeof(pixel<T, CS>)) == 0;
 910     }
 911 };
 912
 913 template<typename T, typename CS>
 914 struct equal_n_fn<pixel<T, CS>*, pixel<T, CS>*>
 915     : equal_n_fn<pixel<T, CS> const*, pixel<T, CS> const*>
 916 {};
 917
 918 /// EqualPixels
 919 /// Equal when both ranges are planar pointers of the same type. memcmp is invoked for each channel plane
 920 ///  User-defined channels that are not bitwise comparable need to provide an overload
 921 template<typename IC, typename CS>
 922 struct equal_n_fn<planar_pixel_iterator<IC, CS>, planar_pixel_iterator<IC, CS>>
 923 {
 924     BOOST_FORCEINLINE
 925     bool operator()(planar_pixel_iterator<IC, CS> const i1, std::ptrdiff_t n, planar_pixel_iterator<IC, CS> const i2) const
 926     {
 927         // FIXME: ptrdiff_t vs size_t
 928         constexpr std::ptrdiff_t byte_size = n * sizeof(typename std::iterator_traits<IC>::value_type);
 929         for (std::ptrdiff_t i = 0; i < mp11::mp_size<CS>::value; ++i)
 930         {
 931             if (memcmp(dynamic_at_c(i1, i), dynamic_at_c(i2, i), byte_size) != 0)
 932                 return false;
 933         }
 934         return true;
 935     }
 936 };
 937
 938 /// Source range is delimited by image iterators
 939 /// \tparam Loc Models ConstPixelLocatorConcept
 940 /// \tparam It Models PixelIteratorConcept
 941 template <typename Loc, typename It>
 942 struct equal_n_fn<boost::gil::iterator_from_2d<Loc>, It>
 943 {
 944     BOOST_FORCEINLINE
 945     bool operator()(boost::gil::iterator_from_2d<Loc> i1, std::ptrdiff_t n, It i2) const
 946     {
 947         gil_function_requires<boost::gil::PixelLocatorConcept<Loc>>();
 948         gil_function_requires<boost::gil::PixelIteratorConcept<It>>();
 949         while (n > 0)
 950         {
 951             std::ptrdiff_t const num = std::min<std::ptrdiff_t>(n, i1.width() - i1.x_pos());
 952             if (!equal_n(i1.x(), num, i2))
 953                 return false;
 954             i1 += num;
 955             i2 += num;
 956             n -= num;
 957         }
 958         return true;
 959     }
 960 };
 961
 962 /// Destination range is delimited by image iterators
 963 /// \tparam It Models PixelIteratorConcept
 964 /// \tparam Loc Models PixelLocatorConcept
 965 template <typename It, typename Loc>
 966 struct equal_n_fn<It, boost::gil::iterator_from_2d<Loc>>
 967 {
 968     BOOST_FORCEINLINE
 969     bool operator()(It i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc> i2) const
 970     {
 971         gil_function_requires<boost::gil::PixelIteratorConcept<It>>();
 972         gil_function_requires<boost::gil::PixelLocatorConcept<Loc>>();
 973         while (n > 0)
 974         {
 975             std::ptrdiff_t const num = std::min<std::ptrdiff_t>(n, i2.width() - i2.x_pos());
 976             if (!equal_n(i1, num, i2.x()))
 977                 return false;
 978             i1 += num;
 979             i2 += num;
 980             n -= num;
 981         }
 982         return true;
 983     }
 984 };
 985
 986 /// Both source and destination ranges are delimited by image iterators
 987 template <typename Loc1, typename Loc2>
 988 struct equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2>> {
 989    BOOST_FORCEINLINE bool operator()(boost::gil::iterator_from_2d<Loc1> i1, std::ptrdiff_t n, boost::gil::iterator_from_2d<Loc2> i2) const {
 990         gil_function_requires<boost::gil::PixelLocatorConcept<Loc1>>();
 991         gil_function_requires<boost::gil::PixelLocatorConcept<Loc2>>();
 992         if (i1.x_pos()!=i2.x_pos() || i1.width()!=i2.width()) {
 993             while(n-->0) {
 994                 if (*i1++!=*i2++) return false;
 995             }
 996         }
 997         while (n>0) {
 998             std::ptrdiff_t num=std::min<const std::ptrdiff_t>(n,i2.width()-i2.x_pos());
 999             if (!equal_n(i1.x(), num, i2.x()))
1000                 return false;
1001             i1+=num;
1002             i2+=num;
1003             n-=num;
1004         }
1005         return true;
1006     }
1007 };
1008 } // namespace detail
1009
1010 template <typename I1, typename I2> BOOST_FORCEINLINE
1011 bool equal_n(I1 i1, std::ptrdiff_t n, I2 i2) {
1012     return detail::equal_n_fn<I1,I2>()(i1,n,i2);
1013 }
1014 } }  // namespace boost::gil
1015
1016 namespace std {
1017 /// \ingroup STLOptimizations
1018 /// \brief  std::equal(I1,I1,I2) with I1 and I2 being a iterator_from_2d
1019 ///
1020 /// Invoked when one calls std::equal(I1,I1,I2) with I1 and I2 being a iterator_from_2d (which is
1021 /// a 1D iterator over the pixels in an image). Attempts to demote the source and destination
1022 /// iterators to simpler/faster types if the corresponding range is contiguous.
1023 /// For contiguous images (i.e. images that have
1024 /// no alignment gap at the end of each row) it is more efficient to use the underlying
1025 /// pixel iterator that does not check for the end of rows. If the underlying pixel iterator
1026 /// happens to be a fundamental planar/interleaved pointer, the call may further resolve
1027 /// to memcmp. Otherwise it resolves to copying each row using the underlying pixel iterator
1028 template <typename Loc1, typename Loc2> BOOST_FORCEINLINE
1029 bool equal(boost::gil::iterator_from_2d<Loc1> first, boost::gil::iterator_from_2d<Loc1> last, boost::gil::iterator_from_2d<Loc2> first2) {
1030     boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc1>>();
1031     boost::gil::gil_function_requires<boost::gil::PixelLocatorConcept<Loc2>>();
1032     std::ptrdiff_t n=last-first;
1033     if (first.is_1d_traversable()) {
1034         if (first2.is_1d_traversable())
1035             return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,typename Loc2::x_iterator>()(first.x(),n, first2.x());
1036         else
1037             return boost::gil::detail::equal_n_fn<typename Loc1::x_iterator,boost::gil::iterator_from_2d<Loc2>>()(first.x(),n, first2);
1038     } else {
1039         if (first2.is_1d_traversable())
1040             return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,typename Loc2::x_iterator>()(first,n, first2.x());
1041         else
1042             return boost::gil::detail::equal_n_fn<boost::gil::iterator_from_2d<Loc1>,boost::gil::iterator_from_2d<Loc2>>()(first,n,first2);
1043     }
1044 }
1045 } // namespace std
1046
1047 namespace boost { namespace gil {
1048 /// \ingroup ImageViewSTLAlgorithmsEqualPixels
1049 /// \brief std::equal for image views
1050 template <typename View1, typename View2> BOOST_FORCEINLINE
1051 bool equal_pixels(const View1& v1, const View2& v2) {
1052     BOOST_ASSERT(v1.dimensions() == v2.dimensions());
1053     return std::equal(v1.begin(),v1.end(),v2.begin()); // std::equal has overloads with GIL iterators for optimal performance
1054 }
1055
1056 //////////////////////////////////////////////////////////////////////////////////////
1057 ///
1058 /// transform_pixels
1059 ///
1060 //////////////////////////////////////////////////////////////////////////////////////
1061
1062 /// \defgroup ImageViewSTLAlgorithmsTransformPixels transform_pixels
1063 /// \ingroup ImageViewSTLAlgorithms
1064 /// \brief std::transform for image views
1065
1066 /// \ingroup ImageViewSTLAlgorithmsTransformPixels
1067 /// \brief std::transform for image views
1068 template <typename View1, typename View2, typename F> BOOST_FORCEINLINE
1069 F transform_pixels(const View1& src,const View2& dst, F fun) {
1070     BOOST_ASSERT(src.dimensions() == dst.dimensions());
1071     for (std::ptrdiff_t y=0; y<src.height(); ++y) {
1072         typename View1::x_iterator srcIt=src.row_begin(y);
1073         typename View2::x_iterator dstIt=dst.row_begin(y);
1074         for (std::ptrdiff_t x=0; x<src.width(); ++x)
1075             dstIt[x]=fun(srcIt[x]);
1076     }
1077     return fun;
1078 }
1079
1080 /// \ingroup ImageViewSTLAlgorithmsTransformPixels
1081 /// \brief transform_pixels with two sources
1082 template <typename View1, typename View2, typename View3, typename F> BOOST_FORCEINLINE
1083 F transform_pixels(const View1& src1, const View2& src2,const View3& dst, F fun) {
1084     for (std::ptrdiff_t y=0; y<dst.height(); ++y) {
1085         typename View1::x_iterator srcIt1=src1.row_begin(y);
1086         typename View2::x_iterator srcIt2=src2.row_begin(y);
1087         typename View3::x_iterator dstIt=dst.row_begin(y);
1088         for (std::ptrdiff_t x=0; x<dst.width(); ++x)
1089             dstIt[x]=fun(srcIt1[x],srcIt2[x]);
1090     }
1091     return fun;
1092 }
1093
1094 /// \defgroup ImageViewSTLAlgorithmsTransformPixelPositions transform_pixel_positions
1095 /// \ingroup ImageViewSTLAlgorithms
1096 /// \brief adobe::transform_positions for image views (passes locators, instead of pixel references, to the function object)
1097
1098 /// \ingroup ImageViewSTLAlgorithmsTransformPixelPositions
1099 /// \brief Like transform_pixels but passes to the function object pixel locators instead of pixel references
1100 template <typename View1, typename View2, typename F> BOOST_FORCEINLINE
1101 F transform_pixel_positions(const View1& src,const View2& dst, F fun) {
1102     BOOST_ASSERT(src.dimensions() == dst.dimensions());
1103     typename View1::xy_locator loc=src.xy_at(0,0);
1104     for (std::ptrdiff_t y=0; y<src.height(); ++y) {
1105         typename View2::x_iterator dstIt=dst.row_begin(y);
1106         for (std::ptrdiff_t x=0; x<src.width(); ++x, ++loc.x())
1107             dstIt[x]=fun(loc);
1108         loc.x()-=src.width(); ++loc.y();
1109     }
1110     return fun;
1111 }
1112
1113 /// \ingroup ImageViewSTLAlgorithmsTransformPixelPositions
1114 /// \brief transform_pixel_positions with two sources
1115 template <typename View1, typename View2, typename View3, typename F> BOOST_FORCEINLINE
1116 F transform_pixel_positions(const View1& src1,const View2& src2,const View3& dst, F fun) {
1117     BOOST_ASSERT(src1.dimensions() == dst.dimensions());
1118     BOOST_ASSERT(src2.dimensions() == dst.dimensions());
1119     typename View1::xy_locator loc1=src1.xy_at(0,0);
1120     typename View2::xy_locator loc2=src2.xy_at(0,0);
1121     for (std::ptrdiff_t y=0; y<src1.height(); ++y) {
1122         typename View3::x_iterator dstIt=dst.row_begin(y);
1123         for (std::ptrdiff_t x=0; x<src1.width(); ++x, ++loc1.x(), ++loc2.x())
1124             dstIt[x]=fun(loc1,loc2);
1125         loc1.x()-=src1.width(); ++loc1.y();
1126         loc2.x()-=src2.width(); ++loc2.y();
1127     }
1128     return fun;
1129 }
1130 } }  // namespace boost::gil
1131
1132 #endif