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

vigra/algorithm.hxx VIGRA

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)