vigra - vigra/algorithm.hxx Source File

[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

vigra/algorithm.hxx |

    00001 /************************************************************************/
    00002 /*                                                                      */
    00003 /*               Copyright 2010-2011 by Ullrich Koethe                  */
    00004 /*                                                                      */
    00005 /*    This file is part of the VIGRA computer vision library.           */
    00006 /*    The VIGRA Website is                                              */
    00007 /*        http://hci.iwr.uni-heidelberg.de/vigra/                       */
    00008 /*    Please direct questions, bug reports, and contributions to        */
    00009 /*        ullrich.koethe@iwr.uni-heidelberg.de    or                    */
    00010 /*        vigra@informatik.uni-hamburg.de                               */
    00011 /*                                                                      */
    00012 /*    Permission is hereby granted, free of charge, to any person       */
    00013 /*    obtaining a copy of this software and associated documentation    */
    00014 /*    files (the "Software"), to deal in the Software without           */
    00015 /*    restriction, including without limitation the rights to use,      */
    00016 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
    00017 /*    sell copies of the Software, and to permit persons to whom the    */
    00018 /*    Software is furnished to do so, subject to the following          */
    00019 /*    conditions:                                                       */
    00020 /*                                                                      */
    00021 /*    The above copyright notice and this permission notice shall be    */
    00022 /*    included in all copies or substantial portions of the             */
    00023 /*    Software.                                                         */
    00024 /*                                                                      */
    00025 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
    00026 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
    00027 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
    00028 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
    00029 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
    00030 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
    00031 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
    00032 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */
    00033 /*                                                                      */
    00034 /************************************************************************/
    00035
    00036 #ifndef VIGRA_ALGORITHM_HXX
    00037 #define VIGRA_ALGORITHM_HXX
    00038
    00039 #include "sized_int.hxx"
    00040 #include "numerictraits.hxx"
    00041 #include "inspector_passes.hxx"
    00042 #include <algorithm>
    00043 #include <functional>
    00044 #include <iterator>
    00045
    00046 namespace vigra {
    00047
    00048 /** \addtogroup MathFunctions
    00049 */
    00050 //@{
    00051     /*! Find the minimum element in a sequence.
    00052
    00053         The function returns the iterator referring to the minimum element.
    00054         This is identical to the function <tt>std::min_element()</tt>.
    00055
    00056         <b>Required Interface:</b>
    00057
    00058         \code
    00059         Iterator is a standard forward iterator.
    00060
    00061         bool f = *first < NumericTraits<typename std::iterator_traits<Iterator>::value_type>::max();
    00062         \endcode
    00063
    00064         <b>\#include</b> <vigra/algorithm.hxx><br>
    00065         Namespace: vigra
    00066     */
    00067 template <class Iterator>
    00068 Iterator argMin(Iterator first, Iterator last)
    00069 {
    00070     if(first == last)
    00071         return last;
    00072     Iterator best = first;
    00073     for(++first; first != last; ++first)
    00074         if(*first < *best)
    00075             best = first;
    00076     return best;
    00077 }
    00078
    00079     /*! Find the maximum element in a sequence.
    00080
    00081         The function returns the iterator referring to the maximum element.
    00082         This is identical to the function <tt>std::max_element()</tt>.
    00083
    00084         <b>Required Interface:</b>
    00085
    00086         \code
    00087         Iterator is a standard forward iterator.
    00088
    00089         bool f = NumericTraits<typename std::iterator_traits<Iterator>::value_type>::min() < *first;
    00090         \endcode
    00091
    00092         <b>\#include</b> <vigra/algorithm.hxx><br>
    00093         Namespace: vigra
    00094     */
    00095 template <class Iterator>
    00096 Iterator argMax(Iterator first, Iterator last)
    00097 {
    00098     if(first == last)
    00099         return last;
    00100     Iterator best = first;
    00101     for(++first; first != last; ++first)
    00102         if(*best < *first)
    00103             best = first;
    00104     return best;
    00105 }
    00106
    00107     /*! Find the minimum element in a sequence conforming to a condition.
    00108
    00109         The function returns the iterator referring to the minimum element,
    00110         where only elements conforming to the condition (i.e. where
    00111         <tt>condition(*iterator)</tt> evaluates to <tt>true</tt>) are considered.
    00112         If no element conforms to the condition, or the sequence is empty,
    00113         the end iterator \a last is returned.
    00114
    00115         <b>Required Interface:</b>
    00116
    00117         \code
    00118         Iterator is a standard forward iterator.
    00119
    00120         bool c = condition(*first);
    00121
    00122         bool f = *first < NumericTraits<typename std::iterator_traits<Iterator>::value_type>::max();
    00123         \endcode
    00124
    00125         <b>\#include</b> <vigra/algorithm.hxx><br>
    00126         Namespace: vigra
    00127     */
    00128 template <class Iterator, class UnaryFunctor>
    00129 Iterator argMinIf(Iterator first, Iterator last, UnaryFunctor condition)
    00130 {
    00131     for(; first != last; ++first)
    00132         if(condition(*first))
    00133             break;
    00134     if(first == last)
    00135         return last;
    00136     Iterator best = first;
    00137     for(++first; first != last; ++first)
    00138         if(condition(*first) && *first < *best)
    00139             best = first;
    00140     return best;
    00141 }
    00142
    00143     /*! Find the maximum element in a sequence conforming to a condition.
    00144
    00145         The function returns the iterator referring to the maximum element,
    00146         where only elements conforming to the condition (i.e. where
    00147         <tt>condition(*iterator)</tt> evaluates to <tt>true</tt>) are considered.
    00148         If no element conforms to the condition, or the sequence is empty,
    00149         the end iterator \a last is returned.
    00150
    00151         <b>Required Interface:</b>
    00152
    00153         \code
    00154         Iterator is a standard forward iterator.
    00155
    00156         bool c = condition(*first);
    00157
    00158         bool f = NumericTraits<typename std::iterator_traits<Iterator>::value_type>::min() < *first;
    00159         \endcode
    00160
    00161         <b>\#include</b> <vigra/algorithm.hxx><br>
    00162         Namespace: vigra
    00163     */
    00164 template <class Iterator, class UnaryFunctor>
    00165 Iterator argMaxIf(Iterator first, Iterator last, UnaryFunctor condition)
    00166 {
    00167     for(; first != last; ++first)
    00168         if(condition(*first))
    00169             break;
    00170     if(first == last)
    00171         return last;
    00172     Iterator best = first;
    00173     for(++first; first != last; ++first)
    00174         if(condition(*first) && *best < *first)
    00175             best = first;
    00176     return best;
    00177 }
    00178
    00179     /*! Fill an array with a sequence of numbers.
    00180
    00181         The sequence starts at \a start and is incremented with \a step. Default start
    00182         and stepsize are 0 and 1 respectively.
    00183
    00184         <b> Declaration:</b>
    00185
    00186         \code
    00187         namespace vigra {
    00188             template <class Iterator, class Value>
    00189             void linearSequence(Iterator first, Iterator last,
    00190                           Value const & start = 0, Value const & step = 1);
    00191         }
    00192         \endcode
    00193
    00194         <b>Required Interface:</b>
    00195
    00196         \code
    00197         Iterator is a standard forward iterator.
    00198
    00199         *first = start;
    00200         start += step;
    00201         \endcode
    00202
    00203         <b>\#include</b> <vigra/algorithm.hxx><br>
    00204         Namespace: vigra
    00205     */
    00206 template <class Iterator, class Value>
    00207 void linearSequence(Iterator first, Iterator last, Value start, Value step)
    00208 {
    00209     for(; first != last; ++first, start += step)
    00210         *first = start;
    00211 }
    00212
    00213 template <class Iterator, class Value>
    00214 void linearSequence(Iterator first, Iterator last, Value start)
    00215 {
    00216     for(; first != last; ++first, ++start)
    00217         *first = start;
    00218 }
    00219
    00220 template <class Iterator>
    00221 void linearSequence(Iterator first, Iterator last)
    00222 {
    00223     typedef typename std::iterator_traits<Iterator>::value_type Value;
    00224
    00225     linearSequence(first, last, NumericTraits<Value>::zero());
    00226 }
    00227
    00228 /** \brief Call an analyzing functor at every element of a sequence.
    00229
    00230     This function can be used to collect statistics of the sequence
    00231     <tt>[first, last)</tt> defined by these two input interators.
    00232     The results must be stored in the functor, which serves as a return
    00233     value.
    00234
    00235     <b> Declarations:</b>
    00236
    00237     \code
    00238     namespace vigra {
    00239         template <class InputIterator, class Functor>
    00240         void
    00241         inspectSequence(InputIterator first, InputIterator last, Functor & f);
    00242     }
    00243     \endcode
    00244
    00245     <b> Usage:</b>
    00246
    00247     <b>\#include</b> <vigra/algorithm.hxx><br>
    00248     Namespace: vigra
    00249
    00250     \code
    00251     std::vector array(100);
    00252
    00253     // init functor
    00254     vigra::FindMinMax<int> minmax;
    00255
    00256     vigra::inspectSequence(array.begin(), array.end(), minmax);
    00257
    00258     cout << "Min: " << minmax.min << " Max: " << minmax.max;
    00259
    00260     \endcode
    00261
    00262 */
    00263 doxygen_overloaded_function(template <...> void inspectSequence)
    00264
    00265 namespace detail {
    00266
    00267 template <class InputIterator>
    00268 struct inspectSequence_binder
    00269 {
    00270     InputIterator first;
    00271     InputIterator last;
    00272     inspectSequence_binder(InputIterator first_, InputIterator last_)
    00273         : first(first_), last(last_) {}
    00274     template <class Functor>
    00275     void operator()(Functor & f)
    00276     {
    00277         for (InputIterator i = first; i != last; ++i)
    00278             f(*i);
    00279     }
    00280 };
    00281
    00282 } // namespace detail
    00283
    00284 template <class InputIterator, class Functor>
    00285 inline void
    00286 inspectSequence(InputIterator first, InputIterator last, Functor & f)
    00287 {
    00288     detail::inspectSequence_binder<InputIterator> g(first, last);
    00289     detail::extra_passes_select(g, f);
    00290 }
    00291
    00292 namespace detail {
    00293
    00294 template <class Iterator, class Compare>
    00295 struct IndexCompare
    00296 {
    00297     Iterator i_;
    00298     Compare c_;
    00299
    00300     IndexCompare(Iterator i, Compare c)
    00301     : i_(i),
    00302       c_(c)
    00303     {}
    00304
    00305     template <class Index>
    00306     bool operator()(Index const & l, Index const & r) const
    00307     {
    00308         return c_(i_[l], i_[r]);
    00309     }
    00310 };
    00311
    00312 } // namespace detail
    00313
    00314     /*! Return the index permutation that would sort the input array.
    00315
    00316         To actually sort an array according to the ordering thus determined, use
    00317         \ref applyPermutation().
    00318
    00319         <b> Declarations:</b>
    00320
    00321         \code
    00322         namespace vigra {
    00323             // compare using std::less
    00324             template <class Iterator, class IndexIterator>
    00325             void indexSort(Iterator first, Iterator last, IndexIterator index_first);
    00326
    00327             // compare using functor Compare
    00328             template <class Iterator, class IndexIterator, class Compare>
    00329             void indexSort(Iterator first, Iterator last, IndexIterator index_first, Compare compare);
    00330         }
    00331         \endcode
    00332
    00333         <b>Required Interface:</b>
    00334
    00335         \code
    00336         Iterator and IndexIterators are random access iterators.
    00337
    00338         bool res = compare(first[*index_first], first[*index_first]);
    00339         \endcode
    00340
    00341         <b>\#include</b> <vigra/algorithm.hxx><br>
    00342         Namespace: vigra
    00343     */
    00344 template <class Iterator, class IndexIterator, class Compare>
    00345 void indexSort(Iterator first, Iterator last, IndexIterator index_first, Compare c)
    00346 {
    00347     int size = last - first;
    00348     linearSequence(index_first, index_first+size);
    00349     std::sort(index_first, index_first+size,
    00350               detail::IndexCompare<Iterator, Compare>(first, c));
    00351 }
    00352
    00353 template <class Iterator, class IndexIterator>
    00354 void indexSort(Iterator first, Iterator last, IndexIterator index_first)
    00355 {
    00356     typedef typename std::iterator_traits<Iterator>::value_type Value;
    00357     indexSort(first, last, index_first, std::less<Value>());
    00358 }
    00359
    00360     /*! Sort an array according to the given index permutation.
    00361
    00362         The iterators \a in and \a out may not refer to the same array, as
    00363         this would overwrite the input prematurely.
    00364
    00365         <b> Declaration:</b>
    00366
    00367         \code
    00368         namespace vigra {
    00369             template <class IndexIterator, class InIterator, class OutIterator>
    00370             void applyPermutation(IndexIterator index_first, IndexIterator index_last,
    00371                                   InIterator in, OutIterator out);
    00372         }
    00373         \endcode
    00374
    00375         <b>Required Interface:</b>
    00376
    00377         \code
    00378         OutIterator and IndexIterators are forward iterators.
    00379         InIterator is a random access iterator.
    00380
    00381         *out = in[*index_first];
    00382         \endcode
    00383
    00384         <b>\#include</b> <vigra/algorithm.hxx><br>
    00385         Namespace: vigra
    00386     */
    00387 template <class IndexIterator, class InIterator, class OutIterator>
    00388 void applyPermutation(IndexIterator index_first, IndexIterator index_last,
    00389                       InIterator in, OutIterator out)
    00390 {
    00391     for(; index_first != index_last; ++index_first, ++out)
    00392         *out = in[*index_first];
    00393 }
    00394
    00395
    00396     /*! Compute the inverse of a given permutation.
    00397
    00398         This is just another name for \ref indexSort(), referring to
    00399         another semantics.
    00400
    00401         <b> Declaration:</b>
    00402
    00403         \code
    00404         namespace vigra {
    00405             template <class InIterator, class OutIterator>
    00406             void inversePermutation(InIterator first, InIterator last,
    00407                                     OutIterator out);
    00408         }
    00409         \endcode
    00410
    00411         <b>Required Interface:</b>
    00412
    00413         \code
    00414         InIterator and OutIterator are random access iterators.
    00415
    00416         *out = in[*index_first];
    00417         \endcode
    00418
    00419         <b>\#include</b> <vigra/algorithm.hxx><br>
    00420         Namespace: vigra
    00421     */
    00422 template <class InIterator, class OutIterator>
    00423 void inversePermutation(InIterator first, InIterator last,
    00424                         OutIterator out)
    00425 {
    00426     indexSort(first, last, out);
    00427 }
    00428
    00429 namespace detail {
    00430
    00431 static bool isLittleEndian()
    00432 {
    00433     static const UIntBiggest testint = 0x01;
    00434     return ((UInt8 *)&testint)[0] == 0x01;
    00435 }
    00436
    00437 template <class InIterator>
    00438 UInt32 checksumImpl(InIterator i, unsigned int size, UInt32 crc = 0xFFFFFFFF)
    00439 {
    00440     static const UInt32 table[256] = {
    00441         0x0U, 0x77073096U, 0xee0e612cU, 0x990951baU, 0x76dc419U, 0x706af48fU,
    00442         0xe963a535U, 0x9e6495a3U, 0xedb8832U, 0x79dcb8a4U, 0xe0d5e91eU, 0x97d2d988U,
    00443         0x9b64c2bU, 0x7eb17cbdU, 0xe7b82d07U, 0x90bf1d91U, 0x1db71064U, 0x6ab020f2U,
    00444         0xf3b97148U, 0x84be41deU, 0x1adad47dU, 0x6ddde4ebU, 0xf4d4b551U, 0x83d385c7U,
    00445         0x136c9856U, 0x646ba8c0U, 0xfd62f97aU, 0x8a65c9ecU, 0x14015c4fU, 0x63066cd9U,
    00446         0xfa0f3d63U, 0x8d080df5U, 0x3b6e20c8U, 0x4c69105eU, 0xd56041e4U, 0xa2677172U,
    00447         0x3c03e4d1U, 0x4b04d447U, 0xd20d85fdU, 0xa50ab56bU, 0x35b5a8faU, 0x42b2986cU,
    00448         0xdbbbc9d6U, 0xacbcf940U, 0x32d86ce3U, 0x45df5c75U, 0xdcd60dcfU, 0xabd13d59U,
    00449         0x26d930acU, 0x51de003aU, 0xc8d75180U, 0xbfd06116U, 0x21b4f4b5U, 0x56b3c423U,
    00450         0xcfba9599U, 0xb8bda50fU, 0x2802b89eU, 0x5f058808U, 0xc60cd9b2U, 0xb10be924U,
    00451         0x2f6f7c87U, 0x58684c11U, 0xc1611dabU, 0xb6662d3dU, 0x76dc4190U, 0x1db7106U,
    00452         0x98d220bcU, 0xefd5102aU, 0x71b18589U, 0x6b6b51fU, 0x9fbfe4a5U, 0xe8b8d433U,
    00453         0x7807c9a2U, 0xf00f934U, 0x9609a88eU, 0xe10e9818U, 0x7f6a0dbbU, 0x86d3d2dU,
    00454         0x91646c97U, 0xe6635c01U, 0x6b6b51f4U, 0x1c6c6162U, 0x856530d8U, 0xf262004eU,
    00455         0x6c0695edU, 0x1b01a57bU, 0x8208f4c1U, 0xf50fc457U, 0x65b0d9c6U, 0x12b7e950U,
    00456         0x8bbeb8eaU, 0xfcb9887cU, 0x62dd1ddfU, 0x15da2d49U, 0x8cd37cf3U, 0xfbd44c65U,
    00457         0x4db26158U, 0x3ab551ceU, 0xa3bc0074U, 0xd4bb30e2U, 0x4adfa541U, 0x3dd895d7U,
    00458         0xa4d1c46dU, 0xd3d6f4fbU, 0x4369e96aU, 0x346ed9fcU, 0xad678846U, 0xda60b8d0U,
    00459         0x44042d73U, 0x33031de5U, 0xaa0a4c5fU, 0xdd0d7cc9U, 0x5005713cU, 0x270241aaU,
    00460         0xbe0b1010U, 0xc90c2086U, 0x5768b525U, 0x206f85b3U, 0xb966d409U, 0xce61e49fU,
    00461         0x5edef90eU, 0x29d9c998U, 0xb0d09822U, 0xc7d7a8b4U, 0x59b33d17U, 0x2eb40d81U,
    00462         0xb7bd5c3bU, 0xc0ba6cadU, 0xedb88320U, 0x9abfb3b6U, 0x3b6e20cU, 0x74b1d29aU,
    00463         0xead54739U, 0x9dd277afU, 0x4db2615U, 0x73dc1683U, 0xe3630b12U, 0x94643b84U,
    00464         0xd6d6a3eU, 0x7a6a5aa8U, 0xe40ecf0bU, 0x9309ff9dU, 0xa00ae27U, 0x7d079eb1U,
    00465         0xf00f9344U, 0x8708a3d2U, 0x1e01f268U, 0x6906c2feU, 0xf762575dU, 0x806567cbU,
    00466         0x196c3671U, 0x6e6b06e7U, 0xfed41b76U, 0x89d32be0U, 0x10da7a5aU, 0x67dd4accU,
    00467         0xf9b9df6fU, 0x8ebeeff9U, 0x17b7be43U, 0x60b08ed5U, 0xd6d6a3e8U, 0xa1d1937eU,
    00468         0x38d8c2c4U, 0x4fdff252U, 0xd1bb67f1U, 0xa6bc5767U, 0x3fb506ddU, 0x48b2364bU,
    00469         0xd80d2bdaU, 0xaf0a1b4cU, 0x36034af6U, 0x41047a60U, 0xdf60efc3U, 0xa867df55U,
    00470         0x316e8eefU, 0x4669be79U, 0xcb61b38cU, 0xbc66831aU, 0x256fd2a0U, 0x5268e236U,
    00471         0xcc0c7795U, 0xbb0b4703U, 0x220216b9U, 0x5505262fU, 0xc5ba3bbeU, 0xb2bd0b28U,
    00472         0x2bb45a92U, 0x5cb36a04U, 0xc2d7ffa7U, 0xb5d0cf31U, 0x2cd99e8bU, 0x5bdeae1dU,
    00473         0x9b64c2b0U, 0xec63f226U, 0x756aa39cU, 0x26d930aU, 0x9c0906a9U, 0xeb0e363fU,
    00474         0x72076785U, 0x5005713U, 0x95bf4a82U, 0xe2b87a14U, 0x7bb12baeU, 0xcb61b38U,
    00475         0x92d28e9bU, 0xe5d5be0dU, 0x7cdcefb7U, 0xbdbdf21U, 0x86d3d2d4U, 0xf1d4e242U,
    00476         0x68ddb3f8U, 0x1fda836eU, 0x81be16cdU, 0xf6b9265bU, 0x6fb077e1U, 0x18b74777U,
    00477         0x88085ae6U, 0xff0f6a70U, 0x66063bcaU, 0x11010b5cU, 0x8f659effU, 0xf862ae69U,
    00478         0x616bffd3U, 0x166ccf45U, 0xa00ae278U, 0xd70dd2eeU, 0x4e048354U, 0x3903b3c2U,
    00479         0xa7672661U, 0xd06016f7U, 0x4969474dU, 0x3e6e77dbU, 0xaed16a4aU, 0xd9d65adcU,
    00480         0x40df0b66U, 0x37d83bf0U, 0xa9bcae53U, 0xdebb9ec5U, 0x47b2cf7fU, 0x30b5ffe9U,
    00481         0xbdbdf21cU, 0xcabac28aU, 0x53b39330U, 0x24b4a3a6U, 0xbad03605U, 0xcdd70693U,
    00482         0x54de5729U, 0x23d967bfU, 0xb3667a2eU, 0xc4614ab8U, 0x5d681b02U, 0x2a6f2b94U,
    00483         0xb40bbe37U, 0xc30c8ea1U, 0x5a05df1bU, 0x2d02ef8dU };
    00484
    00485     static const UInt32 table1[256] = {
    00486         0x00000000U, 0x191b3141U, 0x32366282U, 0x2b2d53c3U, 0x646cc504U,
    00487         0x7d77f445U, 0x565aa786U, 0x4f4196c7U, 0xc8d98a08U, 0xd1c2bb49U,
    00488         0xfaefe88aU, 0xe3f4d9cbU, 0xacb54f0cU, 0xb5ae7e4dU, 0x9e832d8eU,
    00489         0x87981ccfU, 0x4ac21251U, 0x53d92310U, 0x78f470d3U, 0x61ef4192U,
    00490         0x2eaed755U, 0x37b5e614U, 0x1c98b5d7U, 0x05838496U, 0x821b9859U,
    00491         0x9b00a918U, 0xb02dfadbU, 0xa936cb9aU, 0xe6775d5dU, 0xff6c6c1cU,
    00492         0xd4413fdfU, 0xcd5a0e9eU, 0x958424a2U, 0x8c9f15e3U, 0xa7b24620U,
    00493         0xbea97761U, 0xf1e8e1a6U, 0xe8f3d0e7U, 0xc3de8324U, 0xdac5b265U,
    00494         0x5d5daeaaU, 0x44469febU, 0x6f6bcc28U, 0x7670fd69U, 0x39316baeU,
    00495         0x202a5aefU, 0x0b07092cU, 0x121c386dU, 0xdf4636f3U, 0xc65d07b2U,
    00496         0xed705471U, 0xf46b6530U, 0xbb2af3f7U, 0xa231c2b6U, 0x891c9175U,
    00497         0x9007a034U, 0x179fbcfbU, 0x0e848dbaU, 0x25a9de79U, 0x3cb2ef38U,
    00498         0x73f379ffU, 0x6ae848beU, 0x41c51b7dU, 0x58de2a3cU, 0xf0794f05U,
    00499         0xe9627e44U, 0xc24f2d87U, 0xdb541cc6U, 0x94158a01U, 0x8d0ebb40U,
    00500         0xa623e883U, 0xbf38d9c2U, 0x38a0c50dU, 0x21bbf44cU, 0x0a96a78fU,
    00501         0x138d96ceU, 0x5ccc0009U, 0x45d73148U, 0x6efa628bU, 0x77e153caU,
    00502         0xbabb5d54U, 0xa3a06c15U, 0x888d3fd6U, 0x91960e97U, 0xded79850U,
    00503         0xc7cca911U, 0xece1fad2U, 0xf5facb93U, 0x7262d75cU, 0x6b79e61dU,
    00504         0x4054b5deU, 0x594f849fU, 0x160e1258U, 0x0f152319U, 0x243870daU,
    00505         0x3d23419bU, 0x65fd6ba7U, 0x7ce65ae6U, 0x57cb0925U, 0x4ed03864U,
    00506         0x0191aea3U, 0x188a9fe2U, 0x33a7cc21U, 0x2abcfd60U, 0xad24e1afU,
    00507         0xb43fd0eeU, 0x9f12832dU, 0x8609b26cU, 0xc94824abU, 0xd05315eaU,
    00508         0xfb7e4629U, 0xe2657768U, 0x2f3f79f6U, 0x362448b7U, 0x1d091b74U,
    00509         0x04122a35U, 0x4b53bcf2U, 0x52488db3U, 0x7965de70U, 0x607eef31U,
    00510         0xe7e6f3feU, 0xfefdc2bfU, 0xd5d0917cU, 0xcccba03dU, 0x838a36faU,
    00511         0x9a9107bbU, 0xb1bc5478U, 0xa8a76539U, 0x3b83984bU, 0x2298a90aU,
    00512         0x09b5fac9U, 0x10aecb88U, 0x5fef5d4fU, 0x46f46c0eU, 0x6dd93fcdU,
    00513         0x74c20e8cU, 0xf35a1243U, 0xea412302U, 0xc16c70c1U, 0xd8774180U,
    00514         0x9736d747U, 0x8e2de606U, 0xa500b5c5U, 0xbc1b8484U, 0x71418a1aU,
    00515         0x685abb5bU, 0x4377e898U, 0x5a6cd9d9U, 0x152d4f1eU, 0x0c367e5fU,
    00516         0x271b2d9cU, 0x3e001cddU, 0xb9980012U, 0xa0833153U, 0x8bae6290U,
    00517         0x92b553d1U, 0xddf4c516U, 0xc4eff457U, 0xefc2a794U, 0xf6d996d5U,
    00518         0xae07bce9U, 0xb71c8da8U, 0x9c31de6bU, 0x852aef2aU, 0xca6b79edU,
    00519         0xd37048acU, 0xf85d1b6fU, 0xe1462a2eU, 0x66de36e1U, 0x7fc507a0U,
    00520         0x54e85463U, 0x4df36522U, 0x02b2f3e5U, 0x1ba9c2a4U, 0x30849167U,
    00521         0x299fa026U, 0xe4c5aeb8U, 0xfdde9ff9U, 0xd6f3cc3aU, 0xcfe8fd7bU,
    00522         0x80a96bbcU, 0x99b25afdU, 0xb29f093eU, 0xab84387fU, 0x2c1c24b0U,
    00523         0x350715f1U, 0x1e2a4632U, 0x07317773U, 0x4870e1b4U, 0x516bd0f5U,
    00524         0x7a468336U, 0x635db277U, 0xcbfad74eU, 0xd2e1e60fU, 0xf9ccb5ccU,
    00525         0xe0d7848dU, 0xaf96124aU, 0xb68d230bU, 0x9da070c8U, 0x84bb4189U,
    00526         0x03235d46U, 0x1a386c07U, 0x31153fc4U, 0x280e0e85U, 0x674f9842U,
    00527         0x7e54a903U, 0x5579fac0U, 0x4c62cb81U, 0x8138c51fU, 0x9823f45eU,
    00528         0xb30ea79dU, 0xaa1596dcU, 0xe554001bU, 0xfc4f315aU, 0xd7626299U,
    00529         0xce7953d8U, 0x49e14f17U, 0x50fa7e56U, 0x7bd72d95U, 0x62cc1cd4U,
    00530         0x2d8d8a13U, 0x3496bb52U, 0x1fbbe891U, 0x06a0d9d0U, 0x5e7ef3ecU,
    00531         0x4765c2adU, 0x6c48916eU, 0x7553a02fU, 0x3a1236e8U, 0x230907a9U,
    00532         0x0824546aU, 0x113f652bU, 0x96a779e4U, 0x8fbc48a5U, 0xa4911b66U,
    00533         0xbd8a2a27U, 0xf2cbbce0U, 0xebd08da1U, 0xc0fdde62U, 0xd9e6ef23U,
    00534         0x14bce1bdU, 0x0da7d0fcU, 0x268a833fU, 0x3f91b27eU, 0x70d024b9U,
    00535         0x69cb15f8U, 0x42e6463bU, 0x5bfd777aU, 0xdc656bb5U, 0xc57e5af4U,
    00536         0xee530937U, 0xf7483876U, 0xb809aeb1U, 0xa1129ff0U, 0x8a3fcc33U,
    00537         0x9324fd72U };
    00538
    00539     static const UInt32 table2[256] = {
    00540         0x00000000U, 0x01c26a37U, 0x0384d46eU, 0x0246be59U, 0x0709a8dcU,
    00541         0x06cbc2ebU, 0x048d7cb2U, 0x054f1685U, 0x0e1351b8U, 0x0fd13b8fU,
    00542         0x0d9785d6U, 0x0c55efe1U, 0x091af964U, 0x08d89353U, 0x0a9e2d0aU,
    00543         0x0b5c473dU, 0x1c26a370U, 0x1de4c947U, 0x1fa2771eU, 0x1e601d29U,
    00544         0x1b2f0bacU, 0x1aed619bU, 0x18abdfc2U, 0x1969b5f5U, 0x1235f2c8U,
    00545         0x13f798ffU, 0x11b126a6U, 0x10734c91U, 0x153c5a14U, 0x14fe3023U,
    00546         0x16b88e7aU, 0x177ae44dU, 0x384d46e0U, 0x398f2cd7U, 0x3bc9928eU,
    00547         0x3a0bf8b9U, 0x3f44ee3cU, 0x3e86840bU, 0x3cc03a52U, 0x3d025065U,
    00548         0x365e1758U, 0x379c7d6fU, 0x35dac336U, 0x3418a901U, 0x3157bf84U,
    00549         0x3095d5b3U, 0x32d36beaU, 0x331101ddU, 0x246be590U, 0x25a98fa7U,
    00550         0x27ef31feU, 0x262d5bc9U, 0x23624d4cU, 0x22a0277bU, 0x20e69922U,
    00551         0x2124f315U, 0x2a78b428U, 0x2bbade1fU, 0x29fc6046U, 0x283e0a71U,
    00552         0x2d711cf4U, 0x2cb376c3U, 0x2ef5c89aU, 0x2f37a2adU, 0x709a8dc0U,
    00553         0x7158e7f7U, 0x731e59aeU, 0x72dc3399U, 0x7793251cU, 0x76514f2bU,
    00554         0x7417f172U, 0x75d59b45U, 0x7e89dc78U, 0x7f4bb64fU, 0x7d0d0816U,
    00555         0x7ccf6221U, 0x798074a4U, 0x78421e93U, 0x7a04a0caU, 0x7bc6cafdU,
    00556         0x6cbc2eb0U, 0x6d7e4487U, 0x6f38fadeU, 0x6efa90e9U, 0x6bb5866cU,
    00557         0x6a77ec5bU, 0x68315202U, 0x69f33835U, 0x62af7f08U, 0x636d153fU,
    00558         0x612bab66U, 0x60e9c151U, 0x65a6d7d4U, 0x6464bde3U, 0x662203baU,
    00559         0x67e0698dU, 0x48d7cb20U, 0x4915a117U, 0x4b531f4eU, 0x4a917579U,
    00560         0x4fde63fcU, 0x4e1c09cbU, 0x4c5ab792U, 0x4d98dda5U, 0x46c49a98U,
    00561         0x4706f0afU, 0x45404ef6U, 0x448224c1U, 0x41cd3244U, 0x400f5873U,
    00562         0x4249e62aU, 0x438b8c1dU, 0x54f16850U, 0x55330267U, 0x5775bc3eU,
    00563         0x56b7d609U, 0x53f8c08cU, 0x523aaabbU, 0x507c14e2U, 0x51be7ed5U,
    00564         0x5ae239e8U, 0x5b2053dfU, 0x5966ed86U, 0x58a487b1U, 0x5deb9134U,
    00565         0x5c29fb03U, 0x5e6f455aU, 0x5fad2f6dU, 0xe1351b80U, 0xe0f771b7U,
    00566         0xe2b1cfeeU, 0xe373a5d9U, 0xe63cb35cU, 0xe7fed96bU, 0xe5b86732U,
    00567         0xe47a0d05U, 0xef264a38U, 0xeee4200fU, 0xeca29e56U, 0xed60f461U,
    00568         0xe82fe2e4U, 0xe9ed88d3U, 0xebab368aU, 0xea695cbdU, 0xfd13b8f0U,
    00569         0xfcd1d2c7U, 0xfe976c9eU, 0xff5506a9U, 0xfa1a102cU, 0xfbd87a1bU,
    00570         0xf99ec442U, 0xf85cae75U, 0xf300e948U, 0xf2c2837fU, 0xf0843d26U,
    00571         0xf1465711U, 0xf4094194U, 0xf5cb2ba3U, 0xf78d95faU, 0xf64fffcdU,
    00572         0xd9785d60U, 0xd8ba3757U, 0xdafc890eU, 0xdb3ee339U, 0xde71f5bcU,
    00573         0xdfb39f8bU, 0xddf521d2U, 0xdc374be5U, 0xd76b0cd8U, 0xd6a966efU,
    00574         0xd4efd8b6U, 0xd52db281U, 0xd062a404U, 0xd1a0ce33U, 0xd3e6706aU,
    00575         0xd2241a5dU, 0xc55efe10U, 0xc49c9427U, 0xc6da2a7eU, 0xc7184049U,
    00576         0xc25756ccU, 0xc3953cfbU, 0xc1d382a2U, 0xc011e895U, 0xcb4dafa8U,
    00577         0xca8fc59fU, 0xc8c97bc6U, 0xc90b11f1U, 0xcc440774U, 0xcd866d43U,
    00578         0xcfc0d31aU, 0xce02b92dU, 0x91af9640U, 0x906dfc77U, 0x922b422eU,
    00579         0x93e92819U, 0x96a63e9cU, 0x976454abU, 0x9522eaf2U, 0x94e080c5U,
    00580         0x9fbcc7f8U, 0x9e7eadcfU, 0x9c381396U, 0x9dfa79a1U, 0x98b56f24U,
    00581         0x99770513U, 0x9b31bb4aU, 0x9af3d17dU, 0x8d893530U, 0x8c4b5f07U,
    00582         0x8e0de15eU, 0x8fcf8b69U, 0x8a809decU, 0x8b42f7dbU, 0x89044982U,
    00583         0x88c623b5U, 0x839a6488U, 0x82580ebfU, 0x801eb0e6U, 0x81dcdad1U,
    00584         0x8493cc54U, 0x8551a663U, 0x8717183aU, 0x86d5720dU, 0xa9e2d0a0U,
    00585         0xa820ba97U, 0xaa6604ceU, 0xaba46ef9U, 0xaeeb787cU, 0xaf29124bU,
    00586         0xad6fac12U, 0xacadc625U, 0xa7f18118U, 0xa633eb2fU, 0xa4755576U,
    00587         0xa5b73f41U, 0xa0f829c4U, 0xa13a43f3U, 0xa37cfdaaU, 0xa2be979dU,
    00588         0xb5c473d0U, 0xb40619e7U, 0xb640a7beU, 0xb782cd89U, 0xb2cddb0cU,
    00589         0xb30fb13bU, 0xb1490f62U, 0xb08b6555U, 0xbbd72268U, 0xba15485fU,
    00590         0xb853f606U, 0xb9919c31U, 0xbcde8ab4U, 0xbd1ce083U, 0xbf5a5edaU,
    00591         0xbe9834edU };
    00592
    00593     static const UInt32 table3[256] = {
    00594         0x00000000U, 0xb8bc6765U, 0xaa09c88bU, 0x12b5afeeU, 0x8f629757U,
    00595         0x37def032U, 0x256b5fdcU, 0x9dd738b9U, 0xc5b428efU, 0x7d084f8aU,
    00596         0x6fbde064U, 0xd7018701U, 0x4ad6bfb8U, 0xf26ad8ddU, 0xe0df7733U,
    00597         0x58631056U, 0x5019579fU, 0xe8a530faU, 0xfa109f14U, 0x42acf871U,
    00598         0xdf7bc0c8U, 0x67c7a7adU, 0x75720843U, 0xcdce6f26U, 0x95ad7f70U,
    00599         0x2d111815U, 0x3fa4b7fbU, 0x8718d09eU, 0x1acfe827U, 0xa2738f42U,
    00600         0xb0c620acU, 0x087a47c9U, 0xa032af3eU, 0x188ec85bU, 0x0a3b67b5U,
    00601         0xb28700d0U, 0x2f503869U, 0x97ec5f0cU, 0x8559f0e2U, 0x3de59787U,
    00602         0x658687d1U, 0xdd3ae0b4U, 0xcf8f4f5aU, 0x7733283fU, 0xeae41086U,
    00603         0x525877e3U, 0x40edd80dU, 0xf851bf68U, 0xf02bf8a1U, 0x48979fc4U,
    00604         0x5a22302aU, 0xe29e574fU, 0x7f496ff6U, 0xc7f50893U, 0xd540a77dU,
    00605         0x6dfcc018U, 0x359fd04eU, 0x8d23b72bU, 0x9f9618c5U, 0x272a7fa0U,
    00606         0xbafd4719U, 0x0241207cU, 0x10f48f92U, 0xa848e8f7U, 0x9b14583dU,
    00607         0x23a83f58U, 0x311d90b6U, 0x89a1f7d3U, 0x1476cf6aU, 0xaccaa80fU,
    00608         0xbe7f07e1U, 0x06c36084U, 0x5ea070d2U, 0xe61c17b7U, 0xf4a9b859U,
    00609         0x4c15df3cU, 0xd1c2e785U, 0x697e80e0U, 0x7bcb2f0eU, 0xc377486bU,
    00610         0xcb0d0fa2U, 0x73b168c7U, 0x6104c729U, 0xd9b8a04cU, 0x446f98f5U,
    00611         0xfcd3ff90U, 0xee66507eU, 0x56da371bU, 0x0eb9274dU, 0xb6054028U,
    00612         0xa4b0efc6U, 0x1c0c88a3U, 0x81dbb01aU, 0x3967d77fU, 0x2bd27891U,
    00613         0x936e1ff4U, 0x3b26f703U, 0x839a9066U, 0x912f3f88U, 0x299358edU,
    00614         0xb4446054U, 0x0cf80731U, 0x1e4da8dfU, 0xa6f1cfbaU, 0xfe92dfecU,
    00615         0x462eb889U, 0x549b1767U, 0xec277002U, 0x71f048bbU, 0xc94c2fdeU,
    00616         0xdbf98030U, 0x6345e755U, 0x6b3fa09cU, 0xd383c7f9U, 0xc1366817U,
    00617         0x798a0f72U, 0xe45d37cbU, 0x5ce150aeU, 0x4e54ff40U, 0xf6e89825U,
    00618         0xae8b8873U, 0x1637ef16U, 0x048240f8U, 0xbc3e279dU, 0x21e91f24U,
    00619         0x99557841U, 0x8be0d7afU, 0x335cb0caU, 0xed59b63bU, 0x55e5d15eU,
    00620         0x47507eb0U, 0xffec19d5U, 0x623b216cU, 0xda874609U, 0xc832e9e7U,
    00621         0x708e8e82U, 0x28ed9ed4U, 0x9051f9b1U, 0x82e4565fU, 0x3a58313aU,
    00622         0xa78f0983U, 0x1f336ee6U, 0x0d86c108U, 0xb53aa66dU, 0xbd40e1a4U,
    00623         0x05fc86c1U, 0x1749292fU, 0xaff54e4aU, 0x322276f3U, 0x8a9e1196U,
    00624         0x982bbe78U, 0x2097d91dU, 0x78f4c94bU, 0xc048ae2eU, 0xd2fd01c0U,
    00625         0x6a4166a5U, 0xf7965e1cU, 0x4f2a3979U, 0x5d9f9697U, 0xe523f1f2U,
    00626         0x4d6b1905U, 0xf5d77e60U, 0xe762d18eU, 0x5fdeb6ebU, 0xc2098e52U,
    00627         0x7ab5e937U, 0x680046d9U, 0xd0bc21bcU, 0x88df31eaU, 0x3063568fU,
    00628         0x22d6f961U, 0x9a6a9e04U, 0x07bda6bdU, 0xbf01c1d8U, 0xadb46e36U,
    00629         0x15080953U, 0x1d724e9aU, 0xa5ce29ffU, 0xb77b8611U, 0x0fc7e174U,
    00630         0x9210d9cdU, 0x2aacbea8U, 0x38191146U, 0x80a57623U, 0xd8c66675U,
    00631         0x607a0110U, 0x72cfaefeU, 0xca73c99bU, 0x57a4f122U, 0xef189647U,
    00632         0xfdad39a9U, 0x45115eccU, 0x764dee06U, 0xcef18963U, 0xdc44268dU,
    00633         0x64f841e8U, 0xf92f7951U, 0x41931e34U, 0x5326b1daU, 0xeb9ad6bfU,
    00634         0xb3f9c6e9U, 0x0b45a18cU, 0x19f00e62U, 0xa14c6907U, 0x3c9b51beU,
    00635         0x842736dbU, 0x96929935U, 0x2e2efe50U, 0x2654b999U, 0x9ee8defcU,
    00636         0x8c5d7112U, 0x34e11677U, 0xa9362eceU, 0x118a49abU, 0x033fe645U,
    00637         0xbb838120U, 0xe3e09176U, 0x5b5cf613U, 0x49e959fdU, 0xf1553e98U,
    00638         0x6c820621U, 0xd43e6144U, 0xc68bceaaU, 0x7e37a9cfU, 0xd67f4138U,
    00639         0x6ec3265dU, 0x7c7689b3U, 0xc4caeed6U, 0x591dd66fU, 0xe1a1b10aU,
    00640         0xf3141ee4U, 0x4ba87981U, 0x13cb69d7U, 0xab770eb2U, 0xb9c2a15cU,
    00641         0x017ec639U, 0x9ca9fe80U, 0x241599e5U, 0x36a0360bU, 0x8e1c516eU,
    00642         0x866616a7U, 0x3eda71c2U, 0x2c6fde2cU, 0x94d3b949U, 0x090481f0U,
    00643         0xb1b8e695U, 0xa30d497bU, 0x1bb12e1eU, 0x43d23e48U, 0xfb6e592dU,
    00644         0xe9dbf6c3U, 0x516791a6U, 0xccb0a91fU, 0x740cce7aU, 0x66b96194U,
    00645         0xde0506f1U };
    00646
    00647     InIterator end = i + size;
    00648
    00649     if(isLittleEndian() && size > 3)
    00650     {
    00651         // take care of alignment
    00652         for(; (std::size_t)i % 4 != 0; ++i)
    00653         {
    00654             crc = (crc >> 8) ^ table[(crc ^ *i) & 0xFF];
    00655         }
    00656         for(; i < end-3; i+=4)
    00657         {
    00658             crc ^= *((UInt32 *)i);
    00659             crc = table3[crc & 0xFF] ^
    00660                   table2[(crc >> 8) & 0xFF] ^
    00661                   table1[(crc >> 16) & 0xFF] ^
    00662                   table[crc >> 24];
    00663         }
    00664     }
    00665     for(; i < end; ++i)
    00666     {
    00667         crc = (crc >> 8) ^ table[(crc ^ *i) & 0xFF];
    00668     }
    00669     return ~crc;
    00670 }
    00671
    00672 } // namespace detail
    00673
    00674     /*! Compute the CRC-32 checksum of a byte array.
    00675
    00676         Implementation note: This function is slower on big-endian machines
    00677         because the "4 bytes at a time" optimization is only implemented for
    00678         little-endian.
    00679     */
    00680 inline UInt32 checksum(const char * data, unsigned int size)
    00681 {
    00682     return detail::checksumImpl(data, size);
    00683 }
    00684
    00685     /*! Concatenate a byte array to an existing CRC-32 checksum.
    00686     */
    00687 inline UInt32 concatenateChecksum(UInt32 checksum, const char * data, unsigned int size)
    00688 {
    00689
    00690     return detail::checksumImpl(data, size, ~checksum);
    00691 }
    00692
    00693 template <class T>
    00694 void updateMin(T & x, const T & y)
    00695 {
    00696     using std::min;
    00697     x = min(x, y);
    00698 }
    00699
    00700 template <class T>
    00701 void updateMax(T & x, const T & y)
    00702 {
    00703     using std::max;
    00704     x = max(x, y);
    00705 }
    00706
    00707
    00708 //@}
    00709
    00710 } // namespace vigra
    00711
    00712 #endif /* VIGRA_ALGORITHM_HXX */

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.9.0 (Tue Nov 6 2012)