Update to 2.0.0 tree from current Fremantle build
[opencv] / include / opencv / cxmisc.h
1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 //  By downloading, copying, installing or using the software you agree to this license.
6 //  If you do not agree to this license, do not download, install,
7 //  copy or use the software.
8 //
9 //
10 //                           License Agreement
11 //                For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
14 // Copyright (C) 2009, Willow Garage Inc., all rights reserved.
15 // Third party copyrights are property of their respective owners.
16 //
17 // Redistribution and use in source and binary forms, with or without modification,
18 // are permitted provided that the following conditions are met:
19 //
20 //   * Redistribution's of source code must retain the above copyright notice,
21 //     this list of conditions and the following disclaimer.
22 //
23 //   * Redistribution's in binary form must reproduce the above copyright notice,
24 //     this list of conditions and the following disclaimer in the documentation
25 //     and/or other materials provided with the distribution.
26 //
27 //   * The name of the copyright holders may not be used to endorse or promote products
28 //     derived from this software without specific prior written permission.
29 //
30 // This software is provided by the copyright holders and contributors "as is" and
31 // any express or implied warranties, including, but not limited to, the implied
32 // warranties of merchantability and fitness for a particular purpose are disclaimed.
33 // In no event shall the Intel Corporation or contributors be liable for any direct,
34 // indirect, incidental, special, exemplary, or consequential damages
35 // (including, but not limited to, procurement of substitute goods or services;
36 // loss of use, data, or profits; or business interruption) however caused
37 // and on any theory of liability, whether in contract, strict liability,
38 // or tort (including negligence or otherwise) arising in any way out of
39 // the use of this software, even if advised of the possibility of such damage.
40 //
41 //M*/
42
43 /* The header is mostly for internal use and it is likely to change.
44    It contains some macro definitions that are used in cxcore, cv, cvaux
45    and, probably, other libraries. If you need some of this functionality,
46    the safe way is to copy it into your code and rename the macros.
47 */
48 #ifndef _CXCORE_MISC_H_
49 #define _CXCORE_MISC_H_
50
51 #ifdef HAVE_CONFIG_H
52     #include "cvconfig.h"
53 #endif
54
55 #include <limits.h>
56 #ifdef _OPENMP
57 #include "omp.h"
58 #endif
59
60 /****************************************************************************************\
61 *                              Compile-time tuning parameters                            *
62 \****************************************************************************************/
63
64 /* maximal size of vector to run matrix operations on it inline (i.e. w/o ipp calls) */
65 #define  CV_MAX_INLINE_MAT_OP_SIZE  10
66
67 /* maximal linear size of matrix to allocate it on stack. */
68 #define  CV_MAX_LOCAL_MAT_SIZE  32
69
70 /* maximal size of local memory storage */
71 #define  CV_MAX_LOCAL_SIZE  \
72     (CV_MAX_LOCAL_MAT_SIZE*CV_MAX_LOCAL_MAT_SIZE*(int)sizeof(double))
73
74 /* default image row align (in bytes) */
75 #define  CV_DEFAULT_IMAGE_ROW_ALIGN  4
76
77 /* matrices are continuous by default */
78 #define  CV_DEFAULT_MAT_ROW_ALIGN  1
79
80 /* maximum size of dynamic memory buffer.
81    cvAlloc reports an error if a larger block is requested. */
82 #define  CV_MAX_ALLOC_SIZE    (((size_t)1 << (sizeof(size_t)*8-2)))
83
84 /* the alignment of all the allocated buffers */
85 #define  CV_MALLOC_ALIGN    16
86
87 /* default alignment for dynamic data strucutures, resided in storages. */
88 #define  CV_STRUCT_ALIGN    ((int)sizeof(double))
89
90 /* default storage block size */
91 #define  CV_STORAGE_BLOCK_SIZE   ((1<<16) - 128)
92
93 /* default memory block for sparse array elements */
94 #define  CV_SPARSE_MAT_BLOCK    (1<<12)
95
96 /* initial hash table size */
97 #define  CV_SPARSE_HASH_SIZE0    (1<<10)
98
99 /* maximal average node_count/hash_size ratio beyond which hash table is resized */
100 #define  CV_SPARSE_HASH_RATIO    3
101
102 /* max length of strings */
103 #define  CV_MAX_STRLEN  1024
104
105 /* maximum possible number of threads in parallel implementations */
106 #ifdef _OPENMP
107 #define CV_MAX_THREADS 128
108 #else
109 #define CV_MAX_THREADS 1
110 #endif
111
112 #if 0 /*def  CV_CHECK_FOR_NANS*/
113     #define CV_CHECK_NANS( arr ) cvCheckArray((arr))
114 #else
115     #define CV_CHECK_NANS( arr )
116 #endif
117
118 /****************************************************************************************\
119 *                                  Common declarations                                   *
120 \****************************************************************************************/
121
122 /* get alloca declaration */
123 #ifdef __GNUC__
124     #undef alloca
125     #define alloca __builtin_alloca
126 #elif defined WIN32 || defined _WIN32 || defined WIN64 || defined _WIN64 || \
127       defined WINCE || defined _MSC_VER || defined __BORLANDC__
128     #include <malloc.h>
129 #elif defined HAVE_ALLOCA_H
130     #include <alloca.h>
131 #elif defined HAVE_ALLOCA
132     #include <stdlib.h>
133 #else
134     #error "No alloca!"
135 #endif
136
137 #ifdef __GNUC__
138 #define CV_DECL_ALIGNED(x) __attribute__ ((aligned (x)))
139 #elif defined _MSC_VER
140 #define CV_DECL_ALIGNED(x) __declspec(align(x))
141 #else
142 #define CV_DECL_ALIGNED(x)
143 #endif
144
145 /* ! DO NOT make it an inline function */
146 #define cvStackAlloc(size) cvAlignPtr( alloca((size) + CV_MALLOC_ALIGN), CV_MALLOC_ALIGN )
147
148 #if defined _MSC_VER || defined __BORLANDC__
149     #define CV_BIG_INT(n)   n##I64
150     #define CV_BIG_UINT(n)  n##UI64
151 #else
152     #define CV_BIG_INT(n)   n##LL
153     #define CV_BIG_UINT(n)  n##ULL
154 #endif
155
156 #define CV_IMPL CV_EXTERN_C
157
158 #define CV_DBG_BREAK() { volatile int* crashMe = 0; *crashMe = 0; }
159
160 /* default step, set in case of continuous data
161    to work around checks for valid step in some ipp functions */
162 #define  CV_STUB_STEP     (1 << 30)
163
164 #define  CV_SIZEOF_FLOAT ((int)sizeof(float))
165 #define  CV_SIZEOF_SHORT ((int)sizeof(short))
166
167 #define  CV_ORIGIN_TL  0
168 #define  CV_ORIGIN_BL  1
169
170 /* IEEE754 constants and macros */
171 #define  CV_POS_INF       0x7f800000
172 #define  CV_NEG_INF       0x807fffff /* CV_TOGGLE_FLT(0xff800000) */
173 #define  CV_1F            0x3f800000
174 #define  CV_TOGGLE_FLT(x) ((x)^((int)(x) < 0 ? 0x7fffffff : 0))
175 #define  CV_TOGGLE_DBL(x) \
176     ((x)^((int64)(x) < 0 ? CV_BIG_INT(0x7fffffffffffffff) : 0))
177
178 #define  CV_NOP(a)      (a)
179 #define  CV_ADD(a, b)   ((a) + (b))
180 #define  CV_SUB(a, b)   ((a) - (b))
181 #define  CV_MUL(a, b)   ((a) * (b))
182 #define  CV_AND(a, b)   ((a) & (b))
183 #define  CV_OR(a, b)    ((a) | (b))
184 #define  CV_XOR(a, b)   ((a) ^ (b))
185 #define  CV_ANDN(a, b)  (~(a) & (b))
186 #define  CV_ORN(a, b)   (~(a) | (b))
187 #define  CV_SQR(a)      ((a) * (a))
188
189 #define  CV_LT(a, b)    ((a) < (b))
190 #define  CV_LE(a, b)    ((a) <= (b))
191 #define  CV_EQ(a, b)    ((a) == (b))
192 #define  CV_NE(a, b)    ((a) != (b))
193 #define  CV_GT(a, b)    ((a) > (b))
194 #define  CV_GE(a, b)    ((a) >= (b))
195
196 #define  CV_NONZERO(a)      ((a) != 0)
197 #define  CV_NONZERO_FLT(a)  (((a)+(a)) != 0)
198
199 /* general-purpose saturation macros */
200 #define  CV_CAST_8U(t)  (uchar)(!((t) & ~255) ? (t) : (t) > 0 ? 255 : 0)
201 #define  CV_CAST_8S(t)  (schar)(!(((t)+128) & ~255) ? (t) : (t) > 0 ? 127 : -128)
202 #define  CV_CAST_16U(t) (ushort)(!((t) & ~65535) ? (t) : (t) > 0 ? 65535 : 0)
203 #define  CV_CAST_16S(t) (short)(!(((t)+32768) & ~65535) ? (t) : (t) > 0 ? 32767 : -32768)
204 #define  CV_CAST_32S(t) (int)(t)
205 #define  CV_CAST_64S(t) (int64)(t)
206 #define  CV_CAST_32F(t) (float)(t)
207 #define  CV_CAST_64F(t) (double)(t)
208
209 #define  CV_PASTE2(a,b) a##b
210 #define  CV_PASTE(a,b)  CV_PASTE2(a,b)
211
212 #define  CV_EMPTY
213 #define  CV_MAKE_STR(a) #a
214
215 #define  CV_ZERO_OBJ(x) memset((x), 0, sizeof(*(x)))
216
217 #define  CV_DIM(static_array) ((int)(sizeof(static_array)/sizeof((static_array)[0])))
218
219 #define  cvUnsupportedFormat "Unsupported format"
220
221 CV_INLINE void* cvAlignPtr( const void* ptr, int align CV_DEFAULT(32) )
222 {
223     assert( (align & (align-1)) == 0 );
224     return (void*)( ((size_t)ptr + align - 1) & ~(size_t)(align-1) );
225 }
226
227 CV_INLINE int cvAlign( int size, int align )
228 {
229     assert( (align & (align-1)) == 0 && size < INT_MAX );
230     return (size + align - 1) & -align;
231 }
232
233 CV_INLINE  CvSize  cvGetMatSize( const CvMat* mat )
234 {
235     CvSize size;
236     size.width = mat->cols;
237     size.height = mat->rows;
238     return size;
239 }
240
241 #define  CV_DESCALE(x,n)     (((x) + (1 << ((n)-1))) >> (n))
242 #define  CV_FLT_TO_FIX(x,n)  cvRound((x)*(1<<(n)))
243
244 /****************************************************************************************\
245
246   Generic implementation of QuickSort algorithm.
247   ----------------------------------------------
248   Using this macro user can declare customized sort function that can be much faster
249   than built-in qsort function because of lower overhead on elements
250   comparison and exchange. The macro takes less_than (or LT) argument - a macro or function
251   that takes 2 arguments returns non-zero if the first argument should be before the second
252   one in the sorted sequence and zero otherwise.
253
254   Example:
255
256     Suppose that the task is to sort points by ascending of y coordinates and if
257     y's are equal x's should ascend.
258
259     The code is:
260     ------------------------------------------------------------------------------
261            #define cmp_pts( pt1, pt2 ) \
262                ((pt1).y < (pt2).y || ((pt1).y < (pt2).y && (pt1).x < (pt2).x))
263
264            [static] CV_IMPLEMENT_QSORT( icvSortPoints, CvPoint, cmp_pts )
265     ------------------------------------------------------------------------------
266
267     After that the function "void icvSortPoints( CvPoint* array, size_t total, int aux );"
268     is available to user.
269
270   aux is an additional parameter, which can be used when comparing elements.
271   The current implementation was derived from *BSD system qsort():
272
273     * Copyright (c) 1992, 1993
274     *  The Regents of the University of California.  All rights reserved.
275     *
276     * Redistribution and use in source and binary forms, with or without
277     * modification, are permitted provided that the following conditions
278     * are met:
279     * 1. Redistributions of source code must retain the above copyright
280     *    notice, this list of conditions and the following disclaimer.
281     * 2. Redistributions in binary form must reproduce the above copyright
282     *    notice, this list of conditions and the following disclaimer in the
283     *    documentation and/or other materials provided with the distribution.
284     * 3. All advertising materials mentioning features or use of this software
285     *    must display the following acknowledgement:
286     *  This product includes software developed by the University of
287     *  California, Berkeley and its contributors.
288     * 4. Neither the name of the University nor the names of its contributors
289     *    may be used to endorse or promote products derived from this software
290     *    without specific prior written permission.
291     *
292     * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
293     * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
294     * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
295     * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
296     * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
297     * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
298     * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
299     * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
300     * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
301     * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
302     * SUCH DAMAGE.
303
304 \****************************************************************************************/
305
306 #define CV_IMPLEMENT_QSORT_EX( func_name, T, LT, user_data_type )                   \
307 void func_name( T *array, size_t total, user_data_type aux )                        \
308 {                                                                                   \
309     int isort_thresh = 7;                                                           \
310     T t;                                                                            \
311     int sp = 0;                                                                     \
312                                                                                     \
313     struct                                                                          \
314     {                                                                               \
315         T *lb;                                                                      \
316         T *ub;                                                                      \
317     }                                                                               \
318     stack[48];                                                                      \
319                                                                                     \
320     aux = aux;                                                                      \
321                                                                                     \
322     if( total <= 1 )                                                                \
323         return;                                                                     \
324                                                                                     \
325     stack[0].lb = array;                                                            \
326     stack[0].ub = array + (total - 1);                                              \
327                                                                                     \
328     while( sp >= 0 )                                                                \
329     {                                                                               \
330         T* left = stack[sp].lb;                                                     \
331         T* right = stack[sp--].ub;                                                  \
332                                                                                     \
333         for(;;)                                                                     \
334         {                                                                           \
335             int i, n = (int)(right - left) + 1, m;                                  \
336             T* ptr;                                                                 \
337             T* ptr2;                                                                \
338                                                                                     \
339             if( n <= isort_thresh )                                                 \
340             {                                                                       \
341             insert_sort:                                                            \
342                 for( ptr = left + 1; ptr <= right; ptr++ )                          \
343                 {                                                                   \
344                     for( ptr2 = ptr; ptr2 > left && LT(ptr2[0],ptr2[-1]); ptr2--)   \
345                         CV_SWAP( ptr2[0], ptr2[-1], t );                            \
346                 }                                                                   \
347                 break;                                                              \
348             }                                                                       \
349             else                                                                    \
350             {                                                                       \
351                 T* left0;                                                           \
352                 T* left1;                                                           \
353                 T* right0;                                                          \
354                 T* right1;                                                          \
355                 T* pivot;                                                           \
356                 T* a;                                                               \
357                 T* b;                                                               \
358                 T* c;                                                               \
359                 int swap_cnt = 0;                                                   \
360                                                                                     \
361                 left0 = left;                                                       \
362                 right0 = right;                                                     \
363                 pivot = left + (n/2);                                               \
364                                                                                     \
365                 if( n > 40 )                                                        \
366                 {                                                                   \
367                     int d = n / 8;                                                  \
368                     a = left, b = left + d, c = left + 2*d;                         \
369                     left = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))     \
370                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));    \
371                                                                                     \
372                     a = pivot - d, b = pivot, c = pivot + d;                        \
373                     pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))    \
374                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));    \
375                                                                                     \
376                     a = right - 2*d, b = right - d, c = right;                      \
377                     right = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))    \
378                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));    \
379                 }                                                                   \
380                                                                                     \
381                 a = left, b = pivot, c = right;                                     \
382                 pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))        \
383                                    : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));       \
384                 if( pivot != left0 )                                                \
385                 {                                                                   \
386                     CV_SWAP( *pivot, *left0, t );                                   \
387                     pivot = left0;                                                  \
388                 }                                                                   \
389                 left = left1 = left0 + 1;                                           \
390                 right = right1 = right0;                                            \
391                                                                                     \
392                 for(;;)                                                             \
393                 {                                                                   \
394                     while( left <= right && !LT(*pivot, *left) )                    \
395                     {                                                               \
396                         if( !LT(*left, *pivot) )                                    \
397                         {                                                           \
398                             if( left > left1 )                                      \
399                                 CV_SWAP( *left1, *left, t );                        \
400                             swap_cnt = 1;                                           \
401                             left1++;                                                \
402                         }                                                           \
403                         left++;                                                     \
404                     }                                                               \
405                                                                                     \
406                     while( left <= right && !LT(*right, *pivot) )                   \
407                     {                                                               \
408                         if( !LT(*pivot, *right) )                                   \
409                         {                                                           \
410                             if( right < right1 )                                    \
411                                 CV_SWAP( *right1, *right, t );                      \
412                             swap_cnt = 1;                                           \
413                             right1--;                                               \
414                         }                                                           \
415                         right--;                                                    \
416                     }                                                               \
417                                                                                     \
418                     if( left > right )                                              \
419                         break;                                                      \
420                     CV_SWAP( *left, *right, t );                                    \
421                     swap_cnt = 1;                                                   \
422                     left++;                                                         \
423                     right--;                                                        \
424                 }                                                                   \
425                                                                                     \
426                 if( swap_cnt == 0 )                                                 \
427                 {                                                                   \
428                     left = left0, right = right0;                                   \
429                     goto insert_sort;                                               \
430                 }                                                                   \
431                                                                                     \
432                 n = MIN( (int)(left1 - left0), (int)(left - left1) );               \
433                 for( i = 0; i < n; i++ )                                            \
434                     CV_SWAP( left0[i], left[i-n], t );                              \
435                                                                                     \
436                 n = MIN( (int)(right0 - right1), (int)(right1 - right) );           \
437                 for( i = 0; i < n; i++ )                                            \
438                     CV_SWAP( left[i], right0[i-n+1], t );                           \
439                 n = (int)(left - left1);                                            \
440                 m = (int)(right1 - right);                                          \
441                 if( n > 1 )                                                         \
442                 {                                                                   \
443                     if( m > 1 )                                                     \
444                     {                                                               \
445                         if( n > m )                                                 \
446                         {                                                           \
447                             stack[++sp].lb = left0;                                 \
448                             stack[sp].ub = left0 + n - 1;                           \
449                             left = right0 - m + 1, right = right0;                  \
450                         }                                                           \
451                         else                                                        \
452                         {                                                           \
453                             stack[++sp].lb = right0 - m + 1;                        \
454                             stack[sp].ub = right0;                                  \
455                             left = left0, right = left0 + n - 1;                    \
456                         }                                                           \
457                     }                                                               \
458                     else                                                            \
459                         left = left0, right = left0 + n - 1;                        \
460                 }                                                                   \
461                 else if( m > 1 )                                                    \
462                     left = right0 - m + 1, right = right0;                          \
463                 else                                                                \
464                     break;                                                          \
465             }                                                                       \
466         }                                                                           \
467     }                                                                               \
468 }
469
470 #define CV_IMPLEMENT_QSORT( func_name, T, cmp )  \
471     CV_IMPLEMENT_QSORT_EX( func_name, T, cmp, int )
472
473 /****************************************************************************************\
474 *                     Structures and macros for integration with IPP                     *
475 \****************************************************************************************/
476
477 /* IPP-compatible return codes */
478 typedef enum CvStatus
479 {
480     CV_BADMEMBLOCK_ERR          = -113,
481     CV_INPLACE_NOT_SUPPORTED_ERR= -112,
482     CV_UNMATCHED_ROI_ERR        = -111,
483     CV_NOTFOUND_ERR             = -110,
484     CV_BADCONVERGENCE_ERR       = -109,
485
486     CV_BADDEPTH_ERR             = -107,
487     CV_BADROI_ERR               = -106,
488     CV_BADHEADER_ERR            = -105,
489     CV_UNMATCHED_FORMATS_ERR    = -104,
490     CV_UNSUPPORTED_COI_ERR      = -103,
491     CV_UNSUPPORTED_CHANNELS_ERR = -102,
492     CV_UNSUPPORTED_DEPTH_ERR    = -101,
493     CV_UNSUPPORTED_FORMAT_ERR   = -100,
494
495     CV_BADARG_ERR      = -49,  //ipp comp
496     CV_NOTDEFINED_ERR  = -48,  //ipp comp
497
498     CV_BADCHANNELS_ERR = -47,  //ipp comp
499     CV_BADRANGE_ERR    = -44,  //ipp comp
500     CV_BADSTEP_ERR     = -29,  //ipp comp
501
502     CV_BADFLAG_ERR     =  -12,
503     CV_DIV_BY_ZERO_ERR =  -11, //ipp comp
504     CV_BADCOEF_ERR     =  -10,
505
506     CV_BADFACTOR_ERR   =  -7,
507     CV_BADPOINT_ERR    =  -6,
508     CV_BADSCALE_ERR    =  -4,
509     CV_OUTOFMEM_ERR    =  -3,
510     CV_NULLPTR_ERR     =  -2,
511     CV_BADSIZE_ERR     =  -1,
512     CV_NO_ERR          =   0,
513     CV_OK              =   CV_NO_ERR
514 }
515 CvStatus;
516
517 #define IPPI_CALL(stmt) CV_Assert((stmt) >= 0)
518
519 #define CV_NOTHROW throw()
520
521 typedef struct CvFuncTable
522 {
523     void*   fn_2d[CV_DEPTH_MAX];
524 }
525 CvFuncTable;
526
527 typedef struct CvBigFuncTable
528 {
529     void*   fn_2d[CV_DEPTH_MAX*CV_CN_MAX];
530 }
531 CvBigFuncTable;
532
533 #define CV_INIT_FUNC_TAB( tab, FUNCNAME, FLAG )         \
534     (tab).fn_2d[CV_8U] = (void*)FUNCNAME##_8u##FLAG;    \
535     (tab).fn_2d[CV_8S] = 0;                             \
536     (tab).fn_2d[CV_16U] = (void*)FUNCNAME##_16u##FLAG;  \
537     (tab).fn_2d[CV_16S] = (void*)FUNCNAME##_16s##FLAG;  \
538     (tab).fn_2d[CV_32S] = (void*)FUNCNAME##_32s##FLAG;  \
539     (tab).fn_2d[CV_32F] = (void*)FUNCNAME##_32f##FLAG;  \
540     (tab).fn_2d[CV_64F] = (void*)FUNCNAME##_64f##FLAG
541
542 #endif /*_CXCORE_MISC_H_*/