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