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

algorithm.hxx VIGRA

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 */
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
Iterator argMinIf(Iterator first, Iterator last, UnaryFunctor condition)
Find the minimum element in a sequence conforming to a condition.
Definition: algorithm.hxx:129
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
detail::SelectIntegerType< 8, detail::UnsignedIntTypes >::type UInt8
8-bit unsigned int
Definition: sized_int.hxx:179
void linearSequence(Iterator first, Iterator last, Value start, Value step)
Fill an array with a sequence of numbers.
Definition: algorithm.hxx:207
detail::SelectBiggestIntegerType< detail::UnsignedIntTypes >::type UIntBiggest
the biggest unsigned integer type of the system
Definition: sized_int.hxx:190
UInt32 concatenateChecksum(UInt32 checksum, const char *data, unsigned int size)
Definition: algorithm.hxx:705
Iterator argMax(Iterator first, Iterator last)
Find the maximum element in a sequence.
Definition: algorithm.hxx:96
Iterator argMaxIf(Iterator first, Iterator last, UnaryFunctor condition)
Find the maximum element in a sequence conforming to a condition.
Definition: algorithm.hxx:165
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition: sized_int.hxx:183
Iterator argMin(Iterator first, Iterator last)
Find the minimum element in a sequence.
Definition: algorithm.hxx:68
void inspectSequence(...)
Call an analyzing functor at every element of a sequence.
void inversePermutation(InIterator first, InIterator last, OutIterator out)
Compute the inverse of a given permutation.
Definition: algorithm.hxx:423
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 (Tue Dec 31 2013)