[ 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) |
html generated using doxygen and Python
|