00001 /*M/////////////////////////////////////////////////////////////////////////////////////// 00002 // 00003 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 00004 // 00005 // By downloading, copying, installing or using the software you agree to this license. 00006 // If you do not agree to this license, do not download, install, 00007 // copy or use the software. 00008 // 00009 // 00010 // License Agreement 00011 // For Open Source Computer Vision Library 00012 // 00013 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved. 00014 // Copyright (C) 2009, Willow Garage Inc., all rights reserved. 00015 // Third party copyrights are property of their respective owners. 00016 // 00017 // Redistribution and use in source and binary forms, with or without modification, 00018 // are permitted provided that the following conditions are met: 00019 // 00020 // * Redistribution's of source code must retain the above copyright notice, 00021 // this list of conditions and the following disclaimer. 00022 // 00023 // * Redistribution's in binary form must reproduce the above copyright notice, 00024 // this list of conditions and the following disclaimer in the documentation 00025 // and/or other materials provided with the distribution. 00026 // 00027 // * The name of the copyright holders may not be used to endorse or promote products 00028 // derived from this software without specific prior written permission. 00029 // 00030 // This software is provided by the copyright holders and contributors "as is" and 00031 // any express or implied warranties, including, but not limited to, the implied 00032 // warranties of merchantability and fitness for a particular purpose are disclaimed. 00033 // In no event shall the Intel Corporation or contributors be liable for any direct, 00034 // indirect, incidental, special, exemplary, or consequential damages 00035 // (including, but not limited to, procurement of substitute goods or services; 00036 // loss of use, data, or profits; or business interruption) however caused 00037 // and on any theory of liability, whether in contract, strict liability, 00038 // or tort (including negligence or otherwise) arising in any way out of 00039 // the use of this software, even if advised of the possibility of such damage. 00040 // 00041 //M*/ 00042 00043 /* The header is mostly for internal use and it is likely to change. 00044 It contains some macro definitions that are used in cxcore, cv, cvaux 00045 and, probably, other libraries. If you need some of this functionality, 00046 the safe way is to copy it into your code and rename the macros. 00047 */ 00048 #ifndef __OPENCV_MISC_H__ 00049 #define __OPENCV_MISC_H__ 00050 00051 #include <limits.h> 00052 00053 /****************************************************************************************\ 00054 * Compile-time tuning parameters * 00055 \****************************************************************************************/ 00056 00057 /* maximal size of vector to run matrix operations on it inline (i.e. w/o ipp calls) */ 00058 #define CV_MAX_INLINE_MAT_OP_SIZE 10 00059 00060 /* maximal linear size of matrix to allocate it on stack. */ 00061 #define CV_MAX_LOCAL_MAT_SIZE 32 00062 00063 /* maximal size of local memory storage */ 00064 #define CV_MAX_LOCAL_SIZE \ 00065 (CV_MAX_LOCAL_MAT_SIZE*CV_MAX_LOCAL_MAT_SIZE*(int)sizeof(double)) 00066 00067 /* default image row align (in bytes) */ 00068 #define CV_DEFAULT_IMAGE_ROW_ALIGN 4 00069 00070 /* matrices are continuous by default */ 00071 #define CV_DEFAULT_MAT_ROW_ALIGN 1 00072 00073 /* maximum size of dynamic memory buffer. 00074 cvAlloc reports an error if a larger block is requested. */ 00075 #define CV_MAX_ALLOC_SIZE (((size_t)1 << (sizeof(size_t)*8-2))) 00076 00077 /* the alignment of all the allocated buffers */ 00078 #define CV_MALLOC_ALIGN 16 00079 00080 /* default alignment for dynamic data strucutures, resided in storages. */ 00081 #define CV_STRUCT_ALIGN ((int)sizeof(double)) 00082 00083 /* default storage block size */ 00084 #define CV_STORAGE_BLOCK_SIZE ((1<<16) - 128) 00085 00086 /* default memory block for sparse array elements */ 00087 #define CV_SPARSE_MAT_BLOCK (1<<12) 00088 00089 /* initial hash table size */ 00090 #define CV_SPARSE_HASH_SIZE0 (1<<10) 00091 00092 /* maximal average node_count/hash_size ratio beyond which hash table is resized */ 00093 #define CV_SPARSE_HASH_RATIO 3 00094 00095 /* max length of strings */ 00096 #define CV_MAX_STRLEN 1024 00097 00098 /* maximum possible number of threads in parallel implementations */ 00099 #ifdef _OPENMP 00100 #define CV_MAX_THREADS 128 00101 #else 00102 #define CV_MAX_THREADS 1 00103 #endif 00104 00105 #if 0 /*def CV_CHECK_FOR_NANS*/ 00106 #define CV_CHECK_NANS( arr ) cvCheckArray((arr)) 00107 #else 00108 #define CV_CHECK_NANS( arr ) 00109 #endif 00110 00111 /****************************************************************************************\ 00112 * Common declarations * 00113 \****************************************************************************************/ 00114 00115 /* get alloca declaration */ 00116 #ifdef __GNUC__ 00117 #undef alloca 00118 #define alloca __builtin_alloca 00119 #elif defined WIN32 || defined _WIN32 || defined WIN64 || defined _WIN64 || \ 00120 defined WINCE || defined _MSC_VER || defined __BORLANDC__ 00121 #include <malloc.h> 00122 #elif defined HAVE_ALLOCA_H 00123 #include <alloca.h> 00124 #elif defined HAVE_ALLOCA 00125 #include <stdlib.h> 00126 #else 00127 #error "No alloca!" 00128 #endif 00129 00130 #ifdef __GNUC__ 00131 #define CV_DECL_ALIGNED(x) __attribute__ ((aligned (x))) 00132 #elif defined _MSC_VER 00133 #define CV_DECL_ALIGNED(x) __declspec(align(x)) 00134 #else 00135 #define CV_DECL_ALIGNED(x) 00136 #endif 00137 00138 /* ! DO NOT make it an inline function */ 00139 #define cvStackAlloc(size) cvAlignPtr( alloca((size) + CV_MALLOC_ALIGN), CV_MALLOC_ALIGN ) 00140 00141 #if defined _MSC_VER || defined __BORLANDC__ 00142 #define CV_BIG_INT(n) n##I64 00143 #define CV_BIG_UINT(n) n##UI64 00144 #else 00145 #define CV_BIG_INT(n) n##LL 00146 #define CV_BIG_UINT(n) n##ULL 00147 #endif 00148 00149 #define CV_IMPL CV_EXTERN_C 00150 00151 #define CV_DBG_BREAK() { volatile int* crashMe = 0; *crashMe = 0; } 00152 00153 /* default step, set in case of continuous data 00154 to work around checks for valid step in some ipp functions */ 00155 #define CV_STUB_STEP (1 << 30) 00156 00157 #define CV_SIZEOF_FLOAT ((int)sizeof(float)) 00158 #define CV_SIZEOF_SHORT ((int)sizeof(short)) 00159 00160 #define CV_ORIGIN_TL 0 00161 #define CV_ORIGIN_BL 1 00162 00163 /* IEEE754 constants and macros */ 00164 #define CV_POS_INF 0x7f800000 00165 #define CV_NEG_INF 0x807fffff /* CV_TOGGLE_FLT(0xff800000) */ 00166 #define CV_1F 0x3f800000 00167 #define CV_TOGGLE_FLT(x) ((x)^((int)(x) < 0 ? 0x7fffffff : 0)) 00168 #define CV_TOGGLE_DBL(x) \ 00169 ((x)^((int64)(x) < 0 ? CV_BIG_INT(0x7fffffffffffffff) : 0)) 00170 00171 #define CV_NOP(a) (a) 00172 #define CV_ADD(a, b) ((a) + (b)) 00173 #define CV_SUB(a, b) ((a) - (b)) 00174 #define CV_MUL(a, b) ((a) * (b)) 00175 #define CV_AND(a, b) ((a) & (b)) 00176 #define CV_OR(a, b) ((a) | (b)) 00177 #define CV_XOR(a, b) ((a) ^ (b)) 00178 #define CV_ANDN(a, b) (~(a) & (b)) 00179 #define CV_ORN(a, b) (~(a) | (b)) 00180 #define CV_SQR(a) ((a) * (a)) 00181 00182 #define CV_LT(a, b) ((a) < (b)) 00183 #define CV_LE(a, b) ((a) <= (b)) 00184 #define CV_EQ(a, b) ((a) == (b)) 00185 #define CV_NE(a, b) ((a) != (b)) 00186 #define CV_GT(a, b) ((a) > (b)) 00187 #define CV_GE(a, b) ((a) >= (b)) 00188 00189 #define CV_NONZERO(a) ((a) != 0) 00190 #define CV_NONZERO_FLT(a) (((a)+(a)) != 0) 00191 00192 /* general-purpose saturation macros */ 00193 #define CV_CAST_8U(t) (uchar)(!((t) & ~255) ? (t) : (t) > 0 ? 255 : 0) 00194 #define CV_CAST_8S(t) (schar)(!(((t)+128) & ~255) ? (t) : (t) > 0 ? 127 : -128) 00195 #define CV_CAST_16U(t) (ushort)(!((t) & ~65535) ? (t) : (t) > 0 ? 65535 : 0) 00196 #define CV_CAST_16S(t) (short)(!(((t)+32768) & ~65535) ? (t) : (t) > 0 ? 32767 : -32768) 00197 #define CV_CAST_32S(t) (int)(t) 00198 #define CV_CAST_64S(t) (int64)(t) 00199 #define CV_CAST_32F(t) (float)(t) 00200 #define CV_CAST_64F(t) (double)(t) 00201 00202 #define CV_PASTE2(a,b) a##b 00203 #define CV_PASTE(a,b) CV_PASTE2(a,b) 00204 00205 #define CV_EMPTY 00206 #define CV_MAKE_STR(a) #a 00207 00208 #define CV_ZERO_OBJ(x) memset((x), 0, sizeof(*(x))) 00209 00210 #define CV_DIM(static_array) ((int)(sizeof(static_array)/sizeof((static_array)[0]))) 00211 00212 #define cvUnsupportedFormat "Unsupported format" 00213 00214 CV_INLINE void* cvAlignPtr( const void* ptr, int align CV_DEFAULT(32) ) 00215 { 00216 assert( (align & (align-1)) == 0 ); 00217 return (void*)( ((size_t)ptr + align - 1) & ~(size_t)(align-1) ); 00218 } 00219 00220 CV_INLINE int cvAlign( int size, int align ) 00221 { 00222 assert( (align & (align-1)) == 0 && size < INT_MAX ); 00223 return (size + align - 1) & -align; 00224 } 00225 00226 CV_INLINE CvSize cvGetMatSize( const CvMat* mat ) 00227 { 00228 CvSize size; 00229 size.width = mat->cols; 00230 size.height = mat->rows; 00231 return size; 00232 } 00233 00234 #define CV_DESCALE(x,n) (((x) + (1 << ((n)-1))) >> (n)) 00235 #define CV_FLT_TO_FIX(x,n) cvRound((x)*(1<<(n))) 00236 00237 /****************************************************************************************\ 00238 00239 Generic implementation of QuickSort algorithm. 00240 ---------------------------------------------- 00241 Using this macro user can declare customized sort function that can be much faster 00242 than built-in qsort function because of lower overhead on elements 00243 comparison and exchange. The macro takes less_than (or LT) argument - a macro or function 00244 that takes 2 arguments returns non-zero if the first argument should be before the second 00245 one in the sorted sequence and zero otherwise. 00246 00247 Example: 00248 00249 Suppose that the task is to sort points by ascending of y coordinates and if 00250 y's are equal x's should ascend. 00251 00252 The code is: 00253 ------------------------------------------------------------------------------ 00254 #define cmp_pts( pt1, pt2 ) \ 00255 ((pt1).y < (pt2).y || ((pt1).y < (pt2).y && (pt1).x < (pt2).x)) 00256 00257 [static] CV_IMPLEMENT_QSORT( icvSortPoints, CvPoint, cmp_pts ) 00258 ------------------------------------------------------------------------------ 00259 00260 After that the function "void icvSortPoints( CvPoint* array, size_t total, int aux );" 00261 is available to user. 00262 00263 aux is an additional parameter, which can be used when comparing elements. 00264 The current implementation was derived from *BSD system qsort(): 00265 00266 * Copyright (c) 1992, 1993 00267 * The Regents of the University of California. All rights reserved. 00268 * 00269 * Redistribution and use in source and binary forms, with or without 00270 * modification, are permitted provided that the following conditions 00271 * are met: 00272 * 1. Redistributions of source code must retain the above copyright 00273 * notice, this list of conditions and the following disclaimer. 00274 * 2. Redistributions in binary form must reproduce the above copyright 00275 * notice, this list of conditions and the following disclaimer in the 00276 * documentation and/or other materials provided with the distribution. 00277 * 3. All advertising materials mentioning features or use of this software 00278 * must display the following acknowledgement: 00279 * This product includes software developed by the University of 00280 * California, Berkeley and its contributors. 00281 * 4. Neither the name of the University nor the names of its contributors 00282 * may be used to endorse or promote products derived from this software 00283 * without specific prior written permission. 00284 * 00285 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00286 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00287 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00288 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00289 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00290 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00291 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00292 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00293 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00294 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00295 * SUCH DAMAGE. 00296 00297 \****************************************************************************************/ 00298 00299 #define CV_IMPLEMENT_QSORT_EX( func_name, T, LT, user_data_type ) \ 00300 void func_name( T *array, size_t total, user_data_type aux ) \ 00301 { \ 00302 int isort_thresh = 7; \ 00303 T t; \ 00304 int sp = 0; \ 00305 \ 00306 struct \ 00307 { \ 00308 T *lb; \ 00309 T *ub; \ 00310 } \ 00311 stack[48]; \ 00312 \ 00313 aux = aux; \ 00314 \ 00315 if( total <= 1 ) \ 00316 return; \ 00317 \ 00318 stack[0].lb = array; \ 00319 stack[0].ub = array + (total - 1); \ 00320 \ 00321 while( sp >= 0 ) \ 00322 { \ 00323 T* left = stack[sp].lb; \ 00324 T* right = stack[sp--].ub; \ 00325 \ 00326 for(;;) \ 00327 { \ 00328 int i, n = (int)(right - left) + 1, m; \ 00329 T* ptr; \ 00330 T* ptr2; \ 00331 \ 00332 if( n <= isort_thresh ) \ 00333 { \ 00334 insert_sort: \ 00335 for( ptr = left + 1; ptr <= right; ptr++ ) \ 00336 { \ 00337 for( ptr2 = ptr; ptr2 > left && LT(ptr2[0],ptr2[-1]); ptr2--) \ 00338 CV_SWAP( ptr2[0], ptr2[-1], t ); \ 00339 } \ 00340 break; \ 00341 } \ 00342 else \ 00343 { \ 00344 T* left0; \ 00345 T* left1; \ 00346 T* right0; \ 00347 T* right1; \ 00348 T* pivot; \ 00349 T* a; \ 00350 T* b; \ 00351 T* c; \ 00352 int swap_cnt = 0; \ 00353 \ 00354 left0 = left; \ 00355 right0 = right; \ 00356 pivot = left + (n/2); \ 00357 \ 00358 if( n > 40 ) \ 00359 { \ 00360 int d = n / 8; \ 00361 a = left, b = left + d, c = left + 2*d; \ 00362 left = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a)) \ 00363 : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c)); \ 00364 \ 00365 a = pivot - d, b = pivot, c = pivot + d; \ 00366 pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a)) \ 00367 : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c)); \ 00368 \ 00369 a = right - 2*d, b = right - d, c = right; \ 00370 right = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a)) \ 00371 : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c)); \ 00372 } \ 00373 \ 00374 a = left, b = pivot, c = right; \ 00375 pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a)) \ 00376 : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c)); \ 00377 if( pivot != left0 ) \ 00378 { \ 00379 CV_SWAP( *pivot, *left0, t ); \ 00380 pivot = left0; \ 00381 } \ 00382 left = left1 = left0 + 1; \ 00383 right = right1 = right0; \ 00384 \ 00385 for(;;) \ 00386 { \ 00387 while( left <= right && !LT(*pivot, *left) ) \ 00388 { \ 00389 if( !LT(*left, *pivot) ) \ 00390 { \ 00391 if( left > left1 ) \ 00392 CV_SWAP( *left1, *left, t ); \ 00393 swap_cnt = 1; \ 00394 left1++; \ 00395 } \ 00396 left++; \ 00397 } \ 00398 \ 00399 while( left <= right && !LT(*right, *pivot) ) \ 00400 { \ 00401 if( !LT(*pivot, *right) ) \ 00402 { \ 00403 if( right < right1 ) \ 00404 CV_SWAP( *right1, *right, t ); \ 00405 swap_cnt = 1; \ 00406 right1--; \ 00407 } \ 00408 right--; \ 00409 } \ 00410 \ 00411 if( left > right ) \ 00412 break; \ 00413 CV_SWAP( *left, *right, t ); \ 00414 swap_cnt = 1; \ 00415 left++; \ 00416 right--; \ 00417 } \ 00418 \ 00419 if( swap_cnt == 0 ) \ 00420 { \ 00421 left = left0, right = right0; \ 00422 goto insert_sort; \ 00423 } \ 00424 \ 00425 n = MIN( (int)(left1 - left0), (int)(left - left1) ); \ 00426 for( i = 0; i < n; i++ ) \ 00427 CV_SWAP( left0[i], left[i-n], t ); \ 00428 \ 00429 n = MIN( (int)(right0 - right1), (int)(right1 - right) ); \ 00430 for( i = 0; i < n; i++ ) \ 00431 CV_SWAP( left[i], right0[i-n+1], t ); \ 00432 n = (int)(left - left1); \ 00433 m = (int)(right1 - right); \ 00434 if( n > 1 ) \ 00435 { \ 00436 if( m > 1 ) \ 00437 { \ 00438 if( n > m ) \ 00439 { \ 00440 stack[++sp].lb = left0; \ 00441 stack[sp].ub = left0 + n - 1; \ 00442 left = right0 - m + 1, right = right0; \ 00443 } \ 00444 else \ 00445 { \ 00446 stack[++sp].lb = right0 - m + 1; \ 00447 stack[sp].ub = right0; \ 00448 left = left0, right = left0 + n - 1; \ 00449 } \ 00450 } \ 00451 else \ 00452 left = left0, right = left0 + n - 1; \ 00453 } \ 00454 else if( m > 1 ) \ 00455 left = right0 - m + 1, right = right0; \ 00456 else \ 00457 break; \ 00458 } \ 00459 } \ 00460 } \ 00461 } 00462 00463 #define CV_IMPLEMENT_QSORT( func_name, T, cmp ) \ 00464 CV_IMPLEMENT_QSORT_EX( func_name, T, cmp, int ) 00465 00466 /****************************************************************************************\ 00467 * Structures and macros for integration with IPP * 00468 \****************************************************************************************/ 00469 00470 /* IPP-compatible return codes */ 00471 typedef enum CvStatus 00472 { 00473 CV_BADMEMBLOCK_ERR = -113, 00474 CV_INPLACE_NOT_SUPPORTED_ERR= -112, 00475 CV_UNMATCHED_ROI_ERR = -111, 00476 CV_NOTFOUND_ERR = -110, 00477 CV_BADCONVERGENCE_ERR = -109, 00478 00479 CV_BADDEPTH_ERR = -107, 00480 CV_BADROI_ERR = -106, 00481 CV_BADHEADER_ERR = -105, 00482 CV_UNMATCHED_FORMATS_ERR = -104, 00483 CV_UNSUPPORTED_COI_ERR = -103, 00484 CV_UNSUPPORTED_CHANNELS_ERR = -102, 00485 CV_UNSUPPORTED_DEPTH_ERR = -101, 00486 CV_UNSUPPORTED_FORMAT_ERR = -100, 00487 00488 CV_BADARG_ERR = -49, //ipp comp 00489 CV_NOTDEFINED_ERR = -48, //ipp comp 00490 00491 CV_BADCHANNELS_ERR = -47, //ipp comp 00492 CV_BADRANGE_ERR = -44, //ipp comp 00493 CV_BADSTEP_ERR = -29, //ipp comp 00494 00495 CV_BADFLAG_ERR = -12, 00496 CV_DIV_BY_ZERO_ERR = -11, //ipp comp 00497 CV_BADCOEF_ERR = -10, 00498 00499 CV_BADFACTOR_ERR = -7, 00500 CV_BADPOINT_ERR = -6, 00501 CV_BADSCALE_ERR = -4, 00502 CV_OUTOFMEM_ERR = -3, 00503 CV_NULLPTR_ERR = -2, 00504 CV_BADSIZE_ERR = -1, 00505 CV_NO_ERR = 0, 00506 CV_OK = CV_NO_ERR 00507 } 00508 CvStatus; 00509 00510 #define IPPI_CALL(stmt) CV_Assert((stmt) >= 0) 00511 00512 #define CV_NOTHROW throw() 00513 00514 typedef struct CvFuncTable 00515 { 00516 void* fn_2d[CV_DEPTH_MAX]; 00517 } 00518 CvFuncTable; 00519 00520 typedef struct CvBigFuncTable 00521 { 00522 void* fn_2d[CV_DEPTH_MAX*CV_CN_MAX]; 00523 } 00524 CvBigFuncTable; 00525 00526 #define CV_INIT_FUNC_TAB( tab, FUNCNAME, FLAG ) \ 00527 (tab).fn_2d[CV_8U] = (void*)FUNCNAME##_8u##FLAG; \ 00528 (tab).fn_2d[CV_8S] = 0; \ 00529 (tab).fn_2d[CV_16U] = (void*)FUNCNAME##_16u##FLAG; \ 00530 (tab).fn_2d[CV_16S] = (void*)FUNCNAME##_16s##FLAG; \ 00531 (tab).fn_2d[CV_32S] = (void*)FUNCNAME##_32s##FLAG; \ 00532 (tab).fn_2d[CV_32F] = (void*)FUNCNAME##_32f##FLAG; \ 00533 (tab).fn_2d[CV_64F] = (void*)FUNCNAME##_64f##FLAG 00534 00535 #endif /*_CXCORE_MISC_H_*/