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