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

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.8.0 (Wed Sep 26 2012)