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

algorithm.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 2010-2011 by Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35
36 #ifndef VIGRA_ALGORITHM_HXX
37 #define VIGRA_ALGORITHM_HXX
38
39 #include "sized_int.hxx"
40 #include "numerictraits.hxx"
41 #include "inspector_passes.hxx"
42 #include <algorithm>
43 #include <functional>
44 #include <iterator>
45
46 namespace vigra {
47
48 /** \addtogroup MathFunctions
49 */
50 //@{
51 /** \brief Find the minimum element in a sequence.
52
53 The function returns the iterator referring to the minimum element.
54 This is identical to the function <tt>std::min_element()</tt>.
55
56 <b>Required Interface:</b>
57
58 \code
59 Iterator is a standard forward iterator.
60
61 bool f = *first < NumericTraits<typename std::iterator_traits<Iterator>::value_type>::max();
62 \endcode
63
64 <b>\#include</b> <vigra/algorithm.hxx><br>
65 Namespace: vigra
66 */
67 template <class Iterator>
68 Iterator argMin(Iterator first, Iterator last)
69 {
70 if(first == last)
71 return last;
72 Iterator best = first;
73 for(++first; first != last; ++first)
74 if(*first < *best)
75 best = first;
76 return best;
77 }
78
79 /** \brief Find the maximum element in a sequence.
80
81 The function returns the iterator referring to the maximum element.
82 This is identical to the function <tt>std::max_element()</tt>.
83
84 <b>Required Interface:</b>
85
86 \code
87 Iterator is a standard forward iterator.
88
89 bool f = NumericTraits<typename std::iterator_traits<Iterator>::value_type>::min() < *first;
90 \endcode
91
92 <b>\#include</b> <vigra/algorithm.hxx><br>
93 Namespace: vigra
94 */
95 template <class Iterator>
96 Iterator argMax(Iterator first, Iterator last)
97 {
98 if(first == last)
99 return last;
100 Iterator best = first;
101 for(++first; first != last; ++first)
102 if(*best < *first)
103 best = first;
104 return best;
105 }
106
107 /** \brief Find the minimum element in a sequence conforming to a condition.
108
109 The function returns the iterator referring to the minimum element,
110 where only elements conforming to the condition (i.e. where
111 <tt>condition(*iterator)</tt> evaluates to <tt>true</tt>) are considered.
112 If no element conforms to the condition, or the sequence is empty,
113 the end iterator \a last is returned.
114
115 <b>Required Interface:</b>
116
117 \code
118 Iterator is a standard forward iterator.
119
120 bool c = condition(*first);
121
122 bool f = *first < NumericTraits<typename std::iterator_traits<Iterator>::value_type>::max();
123 \endcode
124
125 <b>\#include</b> <vigra/algorithm.hxx><br>
126 Namespace: vigra
127 */
128 template <class Iterator, class UnaryFunctor>
129 Iterator argMinIf(Iterator first, Iterator last, UnaryFunctor condition)
130 {
131 for(; first != last; ++first)
132 if(condition(*first))
133 break;
134 if(first == last)
135 return last;
136 Iterator best = first;
137 for(++first; first != last; ++first)
138 if(condition(*first) && *first < *best)
139 best = first;
140 return best;
141 }
142
143 /** \brief Find the maximum element in a sequence conforming to a condition.
144
145 The function returns the iterator referring to the maximum element,
146 where only elements conforming to the condition (i.e. where
147 <tt>condition(*iterator)</tt> evaluates to <tt>true</tt>) are considered.
148 If no element conforms to the condition, or the sequence is empty,
149 the end iterator \a last is returned.
150
151 <b>Required Interface:</b>
152
153 \code
154 Iterator is a standard forward iterator.
155
156 bool c = condition(*first);
157
158 bool f = NumericTraits<typename std::iterator_traits<Iterator>::value_type>::min() < *first;
159 \endcode
160
161 <b>\#include</b> <vigra/algorithm.hxx><br>
162 Namespace: vigra
163 */
164 template <class Iterator, class UnaryFunctor>
165 Iterator argMaxIf(Iterator first, Iterator last, UnaryFunctor condition)
166 {
167 for(; first != last; ++first)
168 if(condition(*first))
169 break;
170 if(first == last)
171 return last;
172 Iterator best = first;
173 for(++first; first != last; ++first)
174 if(condition(*first) && *best < *first)
175 best = first;
176 return best;
177 }
178
179 /** \brief Fill an array with a sequence of numbers.
180
181 The sequence starts at \a start and is incremented with \a step. Default start
182 and stepsize are 0 and 1 respectively.
183
184 <b> Declaration:</b>
185
186 \code
187 namespace vigra {
188 template <class Iterator, class Value>
189 void linearSequence(Iterator first, Iterator last,
190 Value const & start = 0, Value const & step = 1);
191 }
192 \endcode
193
194 <b>Required Interface:</b>
195
196 \code
197 Iterator is a standard forward iterator.
198
199 *first = start;
200 start += step;
201 \endcode
202
203 <b>\#include</b> <vigra/algorithm.hxx><br>
204 Namespace: vigra
205 */
206 template <class Iterator, class Value>
207 void linearSequence(Iterator first, Iterator last, Value start, Value step)
208 {
209 for(; first != last; ++first, start += step)
210 *first = start;
211 }
212
213 template <class Iterator, class Value>
214 void linearSequence(Iterator first, Iterator last, Value start)
215 {
216 for(; first != last; ++first, ++start)
217 *first = start;
218 }
219
220 template <class Iterator>
221 void linearSequence(Iterator first, Iterator last)
222 {
223 typedef typename std::iterator_traits<Iterator>::value_type Value;
224
225 linearSequence(first, last, NumericTraits<Value>::zero());
226 }
227
228 /** \brief Call an analyzing functor at every element of a sequence.
229
230 This function can be used to collect statistics of the sequence
231 <tt>[first, last)</tt> defined by these two input interators.
232 The results must be stored in the functor, which serves as a return
233 value.
234
235 <b> Declarations:</b>
236
237 \code
238 namespace vigra {
239 template <class InputIterator, class Functor>
240 void
241 inspectSequence(InputIterator first, InputIterator last, Functor & f);
242 }
243 \endcode
244
245 <b> Usage:</b>
246
247 <b>\#include</b> <vigra/algorithm.hxx><br>
248 Namespace: vigra
249
250 \code
251 std::vector array(100);
252
253 // init functor
254 vigra::FindMinMax<int> minmax;
255
256 vigra::inspectSequence(array.begin(), array.end(), minmax);
257
258 cout << "Min: " << minmax.min << " Max: " << minmax.max;
259
260 \endcode
261
262 */
263 doxygen_overloaded_function(template <...> void inspectSequence)
264
265 namespace detail {
266
267 template <class InputIterator>
268 struct inspectSequence_binder
269 {
270 InputIterator first;
271 InputIterator last;
272 inspectSequence_binder(InputIterator first_, InputIterator last_)
273 : first(first_), last(last_) {}
274 template <class Functor>
275 void operator()(Functor & f)
276 {
277 for (InputIterator i = first; i != last; ++i)
278 f(*i);
279 }
280 };
281
282 } // namespace detail
283
284 template <class InputIterator, class Functor>
285 inline void
286 inspectSequence(InputIterator first, InputIterator last, Functor & f)
287 {
288 detail::inspectSequence_binder<InputIterator> g(first, last);
289 detail::extra_passes_select(g, f);
290 }
291
292 namespace detail {
293
294 template <class Iterator, class Compare>
295 struct IndexCompare
296 {
297 Iterator i_;
298 Compare c_;
299
300 IndexCompare(Iterator i, Compare c)
301 : i_(i),
302 c_(c)
303 {}
304
305 template <class Index>
306 bool operator()(Index const & l, Index const & r) const
307 {
308 return c_(i_[l], i_[r]);
309 }
310 };
311
312 } // namespace detail
313
314 /** \brief Return the index permutation that would sort the input array.
315
316 To actually sort an array according to the ordering thus determined, use
317 \ref applyPermutation().
318
319 <b> Declarations:</b>
320
321 \code
322 namespace vigra {
323 // compare using std::less
324 template <class Iterator, class IndexIterator>
325 void indexSort(Iterator first, Iterator last, IndexIterator index_first);
326
327 // compare using functor Compare
328 template <class Iterator, class IndexIterator, class Compare>
329 void indexSort(Iterator first, Iterator last, IndexIterator index_first, Compare compare);
330 }
331 \endcode
332
333 <b>Required Interface:</b>
334
335 \code
336 Iterator and IndexIterators are random access iterators.
337
338 bool res = compare(first[*index_first], first[*index_first]);
339 \endcode
340
341 <b>\#include</b> <vigra/algorithm.hxx><br>
342 Namespace: vigra
343 */
344 template <class Iterator, class IndexIterator, class Compare>
345 void indexSort(Iterator first, Iterator last, IndexIterator index_first, Compare c)
346 {
347 int size = last - first;
348 linearSequence(index_first, index_first+size);
349 std::sort(index_first, index_first+size,
350 detail::IndexCompare<Iterator, Compare>(first, c));
351 }
352
353 template <class Iterator, class IndexIterator>
354 void indexSort(Iterator first, Iterator last, IndexIterator index_first)
355 {
356 typedef typename std::iterator_traits<Iterator>::value_type Value;
357 indexSort(first, last, index_first, std::less<Value>());
358 }
359
360 /** \brief Sort an array according to the given index permutation.
361
362 The iterators \a in and \a out may not refer to the same array, as
363 this would overwrite the input prematurely.
364
365 <b> Declaration:</b>
366
367 \code
368 namespace vigra {
369 template <class IndexIterator, class InIterator, class OutIterator>
370 void applyPermutation(IndexIterator index_first, IndexIterator index_last,
371 InIterator in, OutIterator out);
372 }
373 \endcode
374
375 <b>Required Interface:</b>
376
377 \code
378 OutIterator and IndexIterators are forward iterators.
379 InIterator is a random access iterator.
380
381 *out = in[*index_first];
382 \endcode
383
384 <b>\#include</b> <vigra/algorithm.hxx><br>
385 Namespace: vigra
386 */
387 template <class IndexIterator, class InIterator, class OutIterator>
388 void applyPermutation(IndexIterator index_first, IndexIterator index_last,
389 InIterator in, OutIterator out)
390 {
391 for(; index_first != index_last; ++index_first, ++out)
392 *out = in[*index_first];
393 }
394
395
396 /** \brief Compute the inverse of a given permutation.
397
398 This is just another name for \ref indexSort(), referring to
399 another semantics.
400
401 <b> Declaration:</b>
402
403 \code
404 namespace vigra {
405 template <class InIterator, class OutIterator>
406 void inversePermutation(InIterator first, InIterator last,
407 OutIterator out);
408 }
409 \endcode
410
411 <b>Required Interface:</b>
412
413 \code
414 InIterator and OutIterator are random access iterators.
415
416 *out = in[*index_first];
417 \endcode
418
419 <b>\#include</b> <vigra/algorithm.hxx><br>
420 Namespace: vigra
421 */
422 template <class InIterator, class OutIterator>
423 void inversePermutation(InIterator first, InIterator last,
424 OutIterator out)
425 {
426 indexSort(first, last, out);
427 }
428
429 namespace detail {
430
431 static bool isLittleEndian()
432 {
433 static const UIntBiggest testint = 0x01;
434 return ((UInt8 *)&testint)[0] == 0x01;
435 }
436
437 template <class INT>
438 struct ChecksumImpl
439 {
440 static UInt32 table0[256];
441 static UInt32 table1[256];
442 static UInt32 table2[256];
443 static UInt32 table3[256];
444
445 template <class InIterator>
446 static UInt32 exec(InIterator i, unsigned int size, UInt32 crc = 0xFFFFFFFF);
447 };
448
449 template <class INT>
450 UInt32 ChecksumImpl<INT>::table0[256] = {
451 0x0U, 0x77073096U, 0xee0e612cU, 0x990951baU, 0x76dc419U, 0x706af48fU,
452 0xe963a535U, 0x9e6495a3U, 0xedb8832U, 0x79dcb8a4U, 0xe0d5e91eU, 0x97d2d988U,
453 0x9b64c2bU, 0x7eb17cbdU, 0xe7b82d07U, 0x90bf1d91U, 0x1db71064U, 0x6ab020f2U,
454 0xf3b97148U, 0x84be41deU, 0x1adad47dU, 0x6ddde4ebU, 0xf4d4b551U, 0x83d385c7U,
455 0x136c9856U, 0x646ba8c0U, 0xfd62f97aU, 0x8a65c9ecU, 0x14015c4fU, 0x63066cd9U,
456 0xfa0f3d63U, 0x8d080df5U, 0x3b6e20c8U, 0x4c69105eU, 0xd56041e4U, 0xa2677172U,
457 0x3c03e4d1U, 0x4b04d447U, 0xd20d85fdU, 0xa50ab56bU, 0x35b5a8faU, 0x42b2986cU,
458 0xdbbbc9d6U, 0xacbcf940U, 0x32d86ce3U, 0x45df5c75U, 0xdcd60dcfU, 0xabd13d59U,
459 0x26d930acU, 0x51de003aU, 0xc8d75180U, 0xbfd06116U, 0x21b4f4b5U, 0x56b3c423U,
460 0xcfba9599U, 0xb8bda50fU, 0x2802b89eU, 0x5f058808U, 0xc60cd9b2U, 0xb10be924U,
461 0x2f6f7c87U, 0x58684c11U, 0xc1611dabU, 0xb6662d3dU, 0x76dc4190U, 0x1db7106U,
462 0x98d220bcU, 0xefd5102aU, 0x71b18589U, 0x6b6b51fU, 0x9fbfe4a5U, 0xe8b8d433U,
463 0x7807c9a2U, 0xf00f934U, 0x9609a88eU, 0xe10e9818U, 0x7f6a0dbbU, 0x86d3d2dU,
464 0x91646c97U, 0xe6635c01U, 0x6b6b51f4U, 0x1c6c6162U, 0x856530d8U, 0xf262004eU,
465 0x6c0695edU, 0x1b01a57bU, 0x8208f4c1U, 0xf50fc457U, 0x65b0d9c6U, 0x12b7e950U,
466 0x8bbeb8eaU, 0xfcb9887cU, 0x62dd1ddfU, 0x15da2d49U, 0x8cd37cf3U, 0xfbd44c65U,
467 0x4db26158U, 0x3ab551ceU, 0xa3bc0074U, 0xd4bb30e2U, 0x4adfa541U, 0x3dd895d7U,
468 0xa4d1c46dU, 0xd3d6f4fbU, 0x4369e96aU, 0x346ed9fcU, 0xad678846U, 0xda60b8d0U,
469 0x44042d73U, 0x33031de5U, 0xaa0a4c5fU, 0xdd0d7cc9U, 0x5005713cU, 0x270241aaU,
470 0xbe0b1010U, 0xc90c2086U, 0x5768b525U, 0x206f85b3U, 0xb966d409U, 0xce61e49fU,
471 0x5edef90eU, 0x29d9c998U, 0xb0d09822U, 0xc7d7a8b4U, 0x59b33d17U, 0x2eb40d81U,
472 0xb7bd5c3bU, 0xc0ba6cadU, 0xedb88320U, 0x9abfb3b6U, 0x3b6e20cU, 0x74b1d29aU,
473 0xead54739U, 0x9dd277afU, 0x4db2615U, 0x73dc1683U, 0xe3630b12U, 0x94643b84U,
474 0xd6d6a3eU, 0x7a6a5aa8U, 0xe40ecf0bU, 0x9309ff9dU, 0xa00ae27U, 0x7d079eb1U,
475 0xf00f9344U, 0x8708a3d2U, 0x1e01f268U, 0x6906c2feU, 0xf762575dU, 0x806567cbU,
476 0x196c3671U, 0x6e6b06e7U, 0xfed41b76U, 0x89d32be0U, 0x10da7a5aU, 0x67dd4accU,
477 0xf9b9df6fU, 0x8ebeeff9U, 0x17b7be43U, 0x60b08ed5U, 0xd6d6a3e8U, 0xa1d1937eU,
478 0x38d8c2c4U, 0x4fdff252U, 0xd1bb67f1U, 0xa6bc5767U, 0x3fb506ddU, 0x48b2364bU,
479 0xd80d2bdaU, 0xaf0a1b4cU, 0x36034af6U, 0x41047a60U, 0xdf60efc3U, 0xa867df55U,
480 0x316e8eefU, 0x4669be79U, 0xcb61b38cU, 0xbc66831aU, 0x256fd2a0U, 0x5268e236U,
481 0xcc0c7795U, 0xbb0b4703U, 0x220216b9U, 0x5505262fU, 0xc5ba3bbeU, 0xb2bd0b28U,
482 0x2bb45a92U, 0x5cb36a04U, 0xc2d7ffa7U, 0xb5d0cf31U, 0x2cd99e8bU, 0x5bdeae1dU,
483 0x9b64c2b0U, 0xec63f226U, 0x756aa39cU, 0x26d930aU, 0x9c0906a9U, 0xeb0e363fU,
484 0x72076785U, 0x5005713U, 0x95bf4a82U, 0xe2b87a14U, 0x7bb12baeU, 0xcb61b38U,
485 0x92d28e9bU, 0xe5d5be0dU, 0x7cdcefb7U, 0xbdbdf21U, 0x86d3d2d4U, 0xf1d4e242U,
486 0x68ddb3f8U, 0x1fda836eU, 0x81be16cdU, 0xf6b9265bU, 0x6fb077e1U, 0x18b74777U,
487 0x88085ae6U, 0xff0f6a70U, 0x66063bcaU, 0x11010b5cU, 0x8f659effU, 0xf862ae69U,
488 0x616bffd3U, 0x166ccf45U, 0xa00ae278U, 0xd70dd2eeU, 0x4e048354U, 0x3903b3c2U,
489 0xa7672661U, 0xd06016f7U, 0x4969474dU, 0x3e6e77dbU, 0xaed16a4aU, 0xd9d65adcU,
490 0x40df0b66U, 0x37d83bf0U, 0xa9bcae53U, 0xdebb9ec5U, 0x47b2cf7fU, 0x30b5ffe9U,
491 0xbdbdf21cU, 0xcabac28aU, 0x53b39330U, 0x24b4a3a6U, 0xbad03605U, 0xcdd70693U,
492 0x54de5729U, 0x23d967bfU, 0xb3667a2eU, 0xc4614ab8U, 0x5d681b02U, 0x2a6f2b94U,
493 0xb40bbe37U, 0xc30c8ea1U, 0x5a05df1bU, 0x2d02ef8dU };
494
495 template <class INT>
496 UInt32 ChecksumImpl<INT>::table1[256] = {
497 0x00000000U, 0x191b3141U, 0x32366282U, 0x2b2d53c3U, 0x646cc504U,
498 0x7d77f445U, 0x565aa786U, 0x4f4196c7U, 0xc8d98a08U, 0xd1c2bb49U,
499 0xfaefe88aU, 0xe3f4d9cbU, 0xacb54f0cU, 0xb5ae7e4dU, 0x9e832d8eU,
500 0x87981ccfU, 0x4ac21251U, 0x53d92310U, 0x78f470d3U, 0x61ef4192U,
501 0x2eaed755U, 0x37b5e614U, 0x1c98b5d7U, 0x05838496U, 0x821b9859U,
502 0x9b00a918U, 0xb02dfadbU, 0xa936cb9aU, 0xe6775d5dU, 0xff6c6c1cU,
503 0xd4413fdfU, 0xcd5a0e9eU, 0x958424a2U, 0x8c9f15e3U, 0xa7b24620U,
504 0xbea97761U, 0xf1e8e1a6U, 0xe8f3d0e7U, 0xc3de8324U, 0xdac5b265U,
505 0x5d5daeaaU, 0x44469febU, 0x6f6bcc28U, 0x7670fd69U, 0x39316baeU,
506 0x202a5aefU, 0x0b07092cU, 0x121c386dU, 0xdf4636f3U, 0xc65d07b2U,
507 0xed705471U, 0xf46b6530U, 0xbb2af3f7U, 0xa231c2b6U, 0x891c9175U,
508 0x9007a034U, 0x179fbcfbU, 0x0e848dbaU, 0x25a9de79U, 0x3cb2ef38U,
509 0x73f379ffU, 0x6ae848beU, 0x41c51b7dU, 0x58de2a3cU, 0xf0794f05U,
510 0xe9627e44U, 0xc24f2d87U, 0xdb541cc6U, 0x94158a01U, 0x8d0ebb40U,
511 0xa623e883U, 0xbf38d9c2U, 0x38a0c50dU, 0x21bbf44cU, 0x0a96a78fU,
512 0x138d96ceU, 0x5ccc0009U, 0x45d73148U, 0x6efa628bU, 0x77e153caU,
513 0xbabb5d54U, 0xa3a06c15U, 0x888d3fd6U, 0x91960e97U, 0xded79850U,
514 0xc7cca911U, 0xece1fad2U, 0xf5facb93U, 0x7262d75cU, 0x6b79e61dU,
515 0x4054b5deU, 0x594f849fU, 0x160e1258U, 0x0f152319U, 0x243870daU,
516 0x3d23419bU, 0x65fd6ba7U, 0x7ce65ae6U, 0x57cb0925U, 0x4ed03864U,
517 0x0191aea3U, 0x188a9fe2U, 0x33a7cc21U, 0x2abcfd60U, 0xad24e1afU,
518 0xb43fd0eeU, 0x9f12832dU, 0x8609b26cU, 0xc94824abU, 0xd05315eaU,
519 0xfb7e4629U, 0xe2657768U, 0x2f3f79f6U, 0x362448b7U, 0x1d091b74U,
520 0x04122a35U, 0x4b53bcf2U, 0x52488db3U, 0x7965de70U, 0x607eef31U,
521 0xe7e6f3feU, 0xfefdc2bfU, 0xd5d0917cU, 0xcccba03dU, 0x838a36faU,
522 0x9a9107bbU, 0xb1bc5478U, 0xa8a76539U, 0x3b83984bU, 0x2298a90aU,
523 0x09b5fac9U, 0x10aecb88U, 0x5fef5d4fU, 0x46f46c0eU, 0x6dd93fcdU,
524 0x74c20e8cU, 0xf35a1243U, 0xea412302U, 0xc16c70c1U, 0xd8774180U,
525 0x9736d747U, 0x8e2de606U, 0xa500b5c5U, 0xbc1b8484U, 0x71418a1aU,
526 0x685abb5bU, 0x4377e898U, 0x5a6cd9d9U, 0x152d4f1eU, 0x0c367e5fU,
527 0x271b2d9cU, 0x3e001cddU, 0xb9980012U, 0xa0833153U, 0x8bae6290U,
528 0x92b553d1U, 0xddf4c516U, 0xc4eff457U, 0xefc2a794U, 0xf6d996d5U,
529 0xae07bce9U, 0xb71c8da8U, 0x9c31de6bU, 0x852aef2aU, 0xca6b79edU,
530 0xd37048acU, 0xf85d1b6fU, 0xe1462a2eU, 0x66de36e1U, 0x7fc507a0U,
531 0x54e85463U, 0x4df36522U, 0x02b2f3e5U, 0x1ba9c2a4U, 0x30849167U,
532 0x299fa026U, 0xe4c5aeb8U, 0xfdde9ff9U, 0xd6f3cc3aU, 0xcfe8fd7bU,
533 0x80a96bbcU, 0x99b25afdU, 0xb29f093eU, 0xab84387fU, 0x2c1c24b0U,
534 0x350715f1U, 0x1e2a4632U, 0x07317773U, 0x4870e1b4U, 0x516bd0f5U,
535 0x7a468336U, 0x635db277U, 0xcbfad74eU, 0xd2e1e60fU, 0xf9ccb5ccU,
536 0xe0d7848dU, 0xaf96124aU, 0xb68d230bU, 0x9da070c8U, 0x84bb4189U,
537 0x03235d46U, 0x1a386c07U, 0x31153fc4U, 0x280e0e85U, 0x674f9842U,
538 0x7e54a903U, 0x5579fac0U, 0x4c62cb81U, 0x8138c51fU, 0x9823f45eU,
539 0xb30ea79dU, 0xaa1596dcU, 0xe554001bU, 0xfc4f315aU, 0xd7626299U,
540 0xce7953d8U, 0x49e14f17U, 0x50fa7e56U, 0x7bd72d95U, 0x62cc1cd4U,
541 0x2d8d8a13U, 0x3496bb52U, 0x1fbbe891U, 0x06a0d9d0U, 0x5e7ef3ecU,
542 0x4765c2adU, 0x6c48916eU, 0x7553a02fU, 0x3a1236e8U, 0x230907a9U,
543 0x0824546aU, 0x113f652bU, 0x96a779e4U, 0x8fbc48a5U, 0xa4911b66U,
544 0xbd8a2a27U, 0xf2cbbce0U, 0xebd08da1U, 0xc0fdde62U, 0xd9e6ef23U,
545 0x14bce1bdU, 0x0da7d0fcU, 0x268a833fU, 0x3f91b27eU, 0x70d024b9U,
546 0x69cb15f8U, 0x42e6463bU, 0x5bfd777aU, 0xdc656bb5U, 0xc57e5af4U,
547 0xee530937U, 0xf7483876U, 0xb809aeb1U, 0xa1129ff0U, 0x8a3fcc33U,
548 0x9324fd72U };
549
550 template <class INT>
551 UInt32 ChecksumImpl<INT>::table2[256] = {
552 0x00000000U, 0x01c26a37U, 0x0384d46eU, 0x0246be59U, 0x0709a8dcU,
553 0x06cbc2ebU, 0x048d7cb2U, 0x054f1685U, 0x0e1351b8U, 0x0fd13b8fU,
554 0x0d9785d6U, 0x0c55efe1U, 0x091af964U, 0x08d89353U, 0x0a9e2d0aU,
555 0x0b5c473dU, 0x1c26a370U, 0x1de4c947U, 0x1fa2771eU, 0x1e601d29U,
556 0x1b2f0bacU, 0x1aed619bU, 0x18abdfc2U, 0x1969b5f5U, 0x1235f2c8U,
557 0x13f798ffU, 0x11b126a6U, 0x10734c91U, 0x153c5a14U, 0x14fe3023U,
558 0x16b88e7aU, 0x177ae44dU, 0x384d46e0U, 0x398f2cd7U, 0x3bc9928eU,
559 0x3a0bf8b9U, 0x3f44ee3cU, 0x3e86840bU, 0x3cc03a52U, 0x3d025065U,
560 0x365e1758U, 0x379c7d6fU, 0x35dac336U, 0x3418a901U, 0x3157bf84U,
561 0x3095d5b3U, 0x32d36beaU, 0x331101ddU, 0x246be590U, 0x25a98fa7U,
562 0x27ef31feU, 0x262d5bc9U, 0x23624d4cU, 0x22a0277bU, 0x20e69922U,
563 0x2124f315U, 0x2a78b428U, 0x2bbade1fU, 0x29fc6046U, 0x283e0a71U,
564 0x2d711cf4U, 0x2cb376c3U, 0x2ef5c89aU, 0x2f37a2adU, 0x709a8dc0U,
565 0x7158e7f7U, 0x731e59aeU, 0x72dc3399U, 0x7793251cU, 0x76514f2bU,
566 0x7417f172U, 0x75d59b45U, 0x7e89dc78U, 0x7f4bb64fU, 0x7d0d0816U,
567 0x7ccf6221U, 0x798074a4U, 0x78421e93U, 0x7a04a0caU, 0x7bc6cafdU,
568 0x6cbc2eb0U, 0x6d7e4487U, 0x6f38fadeU, 0x6efa90e9U, 0x6bb5866cU,
569 0x6a77ec5bU, 0x68315202U, 0x69f33835U, 0x62af7f08U, 0x636d153fU,
570 0x612bab66U, 0x60e9c151U, 0x65a6d7d4U, 0x6464bde3U, 0x662203baU,
571 0x67e0698dU, 0x48d7cb20U, 0x4915a117U, 0x4b531f4eU, 0x4a917579U,
572 0x4fde63fcU, 0x4e1c09cbU, 0x4c5ab792U, 0x4d98dda5U, 0x46c49a98U,
573 0x4706f0afU, 0x45404ef6U, 0x448224c1U, 0x41cd3244U, 0x400f5873U,
574 0x4249e62aU, 0x438b8c1dU, 0x54f16850U, 0x55330267U, 0x5775bc3eU,
575 0x56b7d609U, 0x53f8c08cU, 0x523aaabbU, 0x507c14e2U, 0x51be7ed5U,
576 0x5ae239e8U, 0x5b2053dfU, 0x5966ed86U, 0x58a487b1U, 0x5deb9134U,
577 0x5c29fb03U, 0x5e6f455aU, 0x5fad2f6dU, 0xe1351b80U, 0xe0f771b7U,
578 0xe2b1cfeeU, 0xe373a5d9U, 0xe63cb35cU, 0xe7fed96bU, 0xe5b86732U,
579 0xe47a0d05U, 0xef264a38U, 0xeee4200fU, 0xeca29e56U, 0xed60f461U,
580 0xe82fe2e4U, 0xe9ed88d3U, 0xebab368aU, 0xea695cbdU, 0xfd13b8f0U,
581 0xfcd1d2c7U, 0xfe976c9eU, 0xff5506a9U, 0xfa1a102cU, 0xfbd87a1bU,
582 0xf99ec442U, 0xf85cae75U, 0xf300e948U, 0xf2c2837fU, 0xf0843d26U,
583 0xf1465711U, 0xf4094194U, 0xf5cb2ba3U, 0xf78d95faU, 0xf64fffcdU,
584 0xd9785d60U, 0xd8ba3757U, 0xdafc890eU, 0xdb3ee339U, 0xde71f5bcU,
585 0xdfb39f8bU, 0xddf521d2U, 0xdc374be5U, 0xd76b0cd8U, 0xd6a966efU,
586 0xd4efd8b6U, 0xd52db281U, 0xd062a404U, 0xd1a0ce33U, 0xd3e6706aU,
587 0xd2241a5dU, 0xc55efe10U, 0xc49c9427U, 0xc6da2a7eU, 0xc7184049U,
588 0xc25756ccU, 0xc3953cfbU, 0xc1d382a2U, 0xc011e895U, 0xcb4dafa8U,
589 0xca8fc59fU, 0xc8c97bc6U, 0xc90b11f1U, 0xcc440774U, 0xcd866d43U,
590 0xcfc0d31aU, 0xce02b92dU, 0x91af9640U, 0x906dfc77U, 0x922b422eU,
591 0x93e92819U, 0x96a63e9cU, 0x976454abU, 0x9522eaf2U, 0x94e080c5U,
592 0x9fbcc7f8U, 0x9e7eadcfU, 0x9c381396U, 0x9dfa79a1U, 0x98b56f24U,
593 0x99770513U, 0x9b31bb4aU, 0x9af3d17dU, 0x8d893530U, 0x8c4b5f07U,
594 0x8e0de15eU, 0x8fcf8b69U, 0x8a809decU, 0x8b42f7dbU, 0x89044982U,
595 0x88c623b5U, 0x839a6488U, 0x82580ebfU, 0x801eb0e6U, 0x81dcdad1U,
596 0x8493cc54U, 0x8551a663U, 0x8717183aU, 0x86d5720dU, 0xa9e2d0a0U,
597 0xa820ba97U, 0xaa6604ceU, 0xaba46ef9U, 0xaeeb787cU, 0xaf29124bU,
598 0xad6fac12U, 0xacadc625U, 0xa7f18118U, 0xa633eb2fU, 0xa4755576U,
599 0xa5b73f41U, 0xa0f829c4U, 0xa13a43f3U, 0xa37cfdaaU, 0xa2be979dU,
600 0xb5c473d0U, 0xb40619e7U, 0xb640a7beU, 0xb782cd89U, 0xb2cddb0cU,
601 0xb30fb13bU, 0xb1490f62U, 0xb08b6555U, 0xbbd72268U, 0xba15485fU,
602 0xb853f606U, 0xb9919c31U, 0xbcde8ab4U, 0xbd1ce083U, 0xbf5a5edaU,
603 0xbe9834edU };
604
605 template <class INT>
606 UInt32 ChecksumImpl<INT>::table3[256] = {
607 0x00000000U, 0xb8bc6765U, 0xaa09c88bU, 0x12b5afeeU, 0x8f629757U,
608 0x37def032U, 0x256b5fdcU, 0x9dd738b9U, 0xc5b428efU, 0x7d084f8aU,
609 0x6fbde064U, 0xd7018701U, 0x4ad6bfb8U, 0xf26ad8ddU, 0xe0df7733U,
610 0x58631056U, 0x5019579fU, 0xe8a530faU, 0xfa109f14U, 0x42acf871U,
611 0xdf7bc0c8U, 0x67c7a7adU, 0x75720843U, 0xcdce6f26U, 0x95ad7f70U,
612 0x2d111815U, 0x3fa4b7fbU, 0x8718d09eU, 0x1acfe827U, 0xa2738f42U,
613 0xb0c620acU, 0x087a47c9U, 0xa032af3eU, 0x188ec85bU, 0x0a3b67b5U,
614 0xb28700d0U, 0x2f503869U, 0x97ec5f0cU, 0x8559f0e2U, 0x3de59787U,
615 0x658687d1U, 0xdd3ae0b4U, 0xcf8f4f5aU, 0x7733283fU, 0xeae41086U,
616 0x525877e3U, 0x40edd80dU, 0xf851bf68U, 0xf02bf8a1U, 0x48979fc4U,
617 0x5a22302aU, 0xe29e574fU, 0x7f496ff6U, 0xc7f50893U, 0xd540a77dU,
618 0x6dfcc018U, 0x359fd04eU, 0x8d23b72bU, 0x9f9618c5U, 0x272a7fa0U,
619 0xbafd4719U, 0x0241207cU, 0x10f48f92U, 0xa848e8f7U, 0x9b14583dU,
620 0x23a83f58U, 0x311d90b6U, 0x89a1f7d3U, 0x1476cf6aU, 0xaccaa80fU,
621 0xbe7f07e1U, 0x06c36084U, 0x5ea070d2U, 0xe61c17b7U, 0xf4a9b859U,
622 0x4c15df3cU, 0xd1c2e785U, 0x697e80e0U, 0x7bcb2f0eU, 0xc377486bU,
623 0xcb0d0fa2U, 0x73b168c7U, 0x6104c729U, 0xd9b8a04cU, 0x446f98f5U,
624 0xfcd3ff90U, 0xee66507eU, 0x56da371bU, 0x0eb9274dU, 0xb6054028U,
625 0xa4b0efc6U, 0x1c0c88a3U, 0x81dbb01aU, 0x3967d77fU, 0x2bd27891U,
626 0x936e1ff4U, 0x3b26f703U, 0x839a9066U, 0x912f3f88U, 0x299358edU,
627 0xb4446054U, 0x0cf80731U, 0x1e4da8dfU, 0xa6f1cfbaU, 0xfe92dfecU,
628 0x462eb889U, 0x549b1767U, 0xec277002U, 0x71f048bbU, 0xc94c2fdeU,
629 0xdbf98030U, 0x6345e755U, 0x6b3fa09cU, 0xd383c7f9U, 0xc1366817U,
630 0x798a0f72U, 0xe45d37cbU, 0x5ce150aeU, 0x4e54ff40U, 0xf6e89825U,
631 0xae8b8873U, 0x1637ef16U, 0x048240f8U, 0xbc3e279dU, 0x21e91f24U,
632 0x99557841U, 0x8be0d7afU, 0x335cb0caU, 0xed59b63bU, 0x55e5d15eU,
633 0x47507eb0U, 0xffec19d5U, 0x623b216cU, 0xda874609U, 0xc832e9e7U,
634 0x708e8e82U, 0x28ed9ed4U, 0x9051f9b1U, 0x82e4565fU, 0x3a58313aU,
635 0xa78f0983U, 0x1f336ee6U, 0x0d86c108U, 0xb53aa66dU, 0xbd40e1a4U,
636 0x05fc86c1U, 0x1749292fU, 0xaff54e4aU, 0x322276f3U, 0x8a9e1196U,
637 0x982bbe78U, 0x2097d91dU, 0x78f4c94bU, 0xc048ae2eU, 0xd2fd01c0U,
638 0x6a4166a5U, 0xf7965e1cU, 0x4f2a3979U, 0x5d9f9697U, 0xe523f1f2U,
639 0x4d6b1905U, 0xf5d77e60U, 0xe762d18eU, 0x5fdeb6ebU, 0xc2098e52U,
640 0x7ab5e937U, 0x680046d9U, 0xd0bc21bcU, 0x88df31eaU, 0x3063568fU,
641 0x22d6f961U, 0x9a6a9e04U, 0x07bda6bdU, 0xbf01c1d8U, 0xadb46e36U,
642 0x15080953U, 0x1d724e9aU, 0xa5ce29ffU, 0xb77b8611U, 0x0fc7e174U,
643 0x9210d9cdU, 0x2aacbea8U, 0x38191146U, 0x80a57623U, 0xd8c66675U,
644 0x607a0110U, 0x72cfaefeU, 0xca73c99bU, 0x57a4f122U, 0xef189647U,
645 0xfdad39a9U, 0x45115eccU, 0x764dee06U, 0xcef18963U, 0xdc44268dU,
646 0x64f841e8U, 0xf92f7951U, 0x41931e34U, 0x5326b1daU, 0xeb9ad6bfU,
647 0xb3f9c6e9U, 0x0b45a18cU, 0x19f00e62U, 0xa14c6907U, 0x3c9b51beU,
648 0x842736dbU, 0x96929935U, 0x2e2efe50U, 0x2654b999U, 0x9ee8defcU,
649 0x8c5d7112U, 0x34e11677U, 0xa9362eceU, 0x118a49abU, 0x033fe645U,
650 0xbb838120U, 0xe3e09176U, 0x5b5cf613U, 0x49e959fdU, 0xf1553e98U,
651 0x6c820621U, 0xd43e6144U, 0xc68bceaaU, 0x7e37a9cfU, 0xd67f4138U,
652 0x6ec3265dU, 0x7c7689b3U, 0xc4caeed6U, 0x591dd66fU, 0xe1a1b10aU,
653 0xf3141ee4U, 0x4ba87981U, 0x13cb69d7U, 0xab770eb2U, 0xb9c2a15cU,
654 0x017ec639U, 0x9ca9fe80U, 0x241599e5U, 0x36a0360bU, 0x8e1c516eU,
655 0x866616a7U, 0x3eda71c2U, 0x2c6fde2cU, 0x94d3b949U, 0x090481f0U,
656 0xb1b8e695U, 0xa30d497bU, 0x1bb12e1eU, 0x43d23e48U, 0xfb6e592dU,
657 0xe9dbf6c3U, 0x516791a6U, 0xccb0a91fU, 0x740cce7aU, 0x66b96194U,
658 0xde0506f1U };
659
660
661 template <class INT>
662 template <class InIterator>
663 UInt32 ChecksumImpl<INT>::exec(InIterator i, unsigned int size, UInt32 crc)
664 {
665 InIterator end = i + size;
666
667 if(isLittleEndian() && size > 3)
668 {
669 // take care of alignment
670 for(; (std::size_t)i % 4 != 0; ++i)
671 {
672 crc = (crc >> 8) ^ table0[(crc ^ *i) & 0xFF];
673 }
674 for(; i < end-3; i+=4)
675 {
676 crc ^= *((UInt32 *)i);
677 crc = table3[crc & 0xFF] ^
678 table2[(crc >> 8) & 0xFF] ^
679 table1[(crc >> 16) & 0xFF] ^
680 table0[crc >> 24];
681 }
682 }
683 for(; i < end; ++i)
684 {
685 crc = (crc >> 8) ^ table0[(crc ^ *i) & 0xFF];
686 }
687 return ~crc;
688 }
689
690 } // namespace detail
691
692 /** \brief Compute the CRC-32 checksum of a byte array.
693
694 Implementation note: This function is slower on big-endian machines
695 because the "4 bytes at a time" optimization is only implemented for
696 little-endian.
697 */
698 inline UInt32 checksum(const char * data, unsigned int size)
699 {
700 return detail::ChecksumImpl<UInt32>::exec(data, size);
701 }
702
703 /** Concatenate a byte array to an existing CRC-32 checksum.
704 */
705 inline UInt32 concatenateChecksum(UInt32 checksum, const char * data, unsigned int size)
706 {
707
708 return detail::ChecksumImpl<UInt32>::exec(data, size, ~checksum);
709 }
710
711 template <class T>
712 void updateMin(T & x, const T & y)
713 {
714 using std::min;
715 x = min(x, y);
716 }
717
718 template <class T>
719 void updateMax(T & x, const T & y)
720 {
721 using std::max;
722 x = max(x, y);
723 }
724
725
726 //@}
727
728 } // namespace vigra
729
730 #endif /* VIGRA_ALGORITHM_HXX */
vigra::applyPermutation
void applyPermutation(IndexIterator index_first, IndexIterator index_last, InIterator in, OutIterator out)
Sort an array according to the given index permutation.
Definition: algorithm.hxx:388
vigra::argMinIf
Iterator argMinIf(Iterator first, Iterator last, UnaryFunctor condition)
Find the minimum element in a sequence conforming to a condition.
Definition: algorithm.hxx:129
vigra::indexSort
void indexSort(Iterator first, Iterator last, IndexIterator index_first, Compare c)
Return the index permutation that would sort the input array.
Definition: algorithm.hxx:345
vigra::UInt8
detail::SelectIntegerType< 8, detail::UnsignedIntTypes >::type UInt8
8-bit unsigned int
Definition: sized_int.hxx:179
vigra::linearSequence
void linearSequence(Iterator first, Iterator last, Value start, Value step)
Fill an array with a sequence of numbers.
Definition: algorithm.hxx:207
vigra
Definition: accessor.hxx:43
vigra::UIntBiggest
detail::SelectBiggestIntegerType< detail::UnsignedIntTypes >::type UIntBiggest
the biggest unsigned integer type of the system
Definition: sized_int.hxx:190
vigra::concatenateChecksum
UInt32 concatenateChecksum(UInt32 checksum, const char *data, unsigned int size)
Definition: algorithm.hxx:705
vigra::argMax
Iterator argMax(Iterator first, Iterator last)
Find the maximum element in a sequence.
Definition: algorithm.hxx:96
vigra::argMaxIf
Iterator argMaxIf(Iterator first, Iterator last, UnaryFunctor condition)
Find the maximum element in a sequence conforming to a condition.
Definition: algorithm.hxx:165
vigra::UInt32
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition: sized_int.hxx:183
vigra::argMin
Iterator argMin(Iterator first, Iterator last)
Find the minimum element in a sequence.
Definition: algorithm.hxx:68
vigra::inspectSequence
void inspectSequence(...)
Call an analyzing functor at every element of a sequence.
vigra::inversePermutation
void inversePermutation(InIterator first, InIterator last, OutIterator out)
Compute the inverse of a given permutation.
Definition: algorithm.hxx:423
vigra::checksum
UInt32 checksum(const char *data, unsigned int size)
Compute the CRC-32 checksum of a byte array.
Definition: algorithm.hxx:698

© 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.10.0