git.maemo.org Git - opencv/blob - cxcore/include/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 //                        Intel License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  14 // Third party copyrights are property of their respective owners.
  15 //
  16 // Redistribution and use in source and binary forms, with or without modification,
  17 // are permitted provided that the following conditions are met:
  18 //
  19 //   * Redistribution's of source code must retain the above copyright notice,
  20 //     this list of conditions and the following disclaimer.
  21 //
  22 //   * Redistribution's in binary form must reproduce the above copyright notice,
  23 //     this list of conditions and the following disclaimer in the documentation
  24 //     and/or other materials provided with the distribution.
  25 //
  26 //   * The name of Intel Corporation may not be used to endorse or promote products
  27 //     derived from this software without specific prior written permission.
  28 //
  29 // This software is provided by the copyright holders and contributors "as is" and
  30 // any express or implied warranties, including, but not limited to, the implied
  31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  32 // In no event shall the Intel Corporation or contributors be liable for any direct,
  33 // indirect, incidental, special, exemplary, or consequential damages
  34 // (including, but not limited to, procurement of substitute goods or services;
  35 // loss of use, data, or profits; or business interruption) however caused
  36 // and on any theory of liability, whether in contract, strict liability,
  37 // or tort (including negligence or otherwise) arising in any way out of
  38 // the use of this software, even if advised of the possibility of such damage.
  39 //
  40 //M*/
  41
  42 /* The header is mostly for internal use and it is likely to change.
  43    It contains some macro definitions that are used in cxcore, cv, cvaux
  44    and, probably, other libraries. If you need some of this functionality,
  45    the safe way is to copy it into your code and rename the macros.
  46 */
  47 #ifndef _CXCORE_MISC_H_
  48 #define _CXCORE_MISC_H_
  49
  50 #ifdef HAVE_CONFIG_H
  51     #include "cvconfig.h"
  52 #endif
  53
  54 #include <limits.h>
  55 #ifdef _OPENMP
  56 #include "omp.h"
  57 #endif
  58
  59 /****************************************************************************************\
  60 *                              Compile-time tuning parameters                            *
  61 \****************************************************************************************/
  62
  63 /* maximal size of vector to run matrix operations on it inline (i.e. w/o ipp calls) */
  64 #define  CV_MAX_INLINE_MAT_OP_SIZE  10
  65
  66 /* maximal linear size of matrix to allocate it on stack. */
  67 #define  CV_MAX_LOCAL_MAT_SIZE  32
  68
  69 /* maximal size of local memory storage */
  70 #define  CV_MAX_LOCAL_SIZE  \
  71     (CV_MAX_LOCAL_MAT_SIZE*CV_MAX_LOCAL_MAT_SIZE*(int)sizeof(double))
  72
  73 /* default image row align (in bytes) */
  74 #define  CV_DEFAULT_IMAGE_ROW_ALIGN  4
  75
  76 /* matrices are continuous by default */
  77 #define  CV_DEFAULT_MAT_ROW_ALIGN  1
  78
  79 /* maximum size of dynamic memory buffer.
  80    cvAlloc reports an error if a larger block is requested. */
  81 #define  CV_MAX_ALLOC_SIZE    (((size_t)1 << (sizeof(size_t)*8-2)))
  82
  83 /* the alignment of all the allocated buffers */
  84 #define  CV_MALLOC_ALIGN    32
  85
  86 /* default alignment for dynamic data strucutures, resided in storages. */
  87 #define  CV_STRUCT_ALIGN    ((int)sizeof(double))
  88
  89 /* default storage block size */
  90 #define  CV_STORAGE_BLOCK_SIZE   ((1<<16) - 128)
  91
  92 /* default memory block for sparse array elements */
  93 #define  CV_SPARSE_MAT_BLOCK    (1<<12)
  94
  95 /* initial hash table size */
  96 #define  CV_SPARSE_HASH_SIZE0    (1<<10)
  97
  98 /* maximal average node_count/hash_size ratio beyond which hash table is resized */
  99 #define  CV_SPARSE_HASH_RATIO    3
 100
 101 /* max length of strings */
 102 #define  CV_MAX_STRLEN  1024
 103
 104 /* maximum possible number of threads in parallel implementations */
 105 #ifdef _OPENMP
 106 #define CV_MAX_THREADS 128
 107 #else
 108 #define CV_MAX_THREADS 1
 109 #endif
 110
 111 #if 0 /*def  CV_CHECK_FOR_NANS*/
 112     #define CV_CHECK_NANS( arr ) cvCheckArray((arr))
 113 #else
 114     #define CV_CHECK_NANS( arr )
 115 #endif
 116
 117 /****************************************************************************************\
 118 *                                  Common declarations                                   *
 119 \****************************************************************************************/
 120
 121 /* get alloca declaration */
 122 #ifdef __GNUC__
 123     #undef alloca
 124     #define alloca __builtin_alloca
 125 #elif defined WIN32 || defined WIN64
 126     #if defined _MSC_VER || defined __BORLANDC__
 127         #include <malloc.h>
 128     #endif
 129 #elif defined HAVE_ALLOCA_H
 130     #include <alloca.h>
 131 #elif defined HAVE_ALLOCA
 132     #include <stdlib.h>
 133 #elif
 134     #error
 135 #endif
 136
 137 /* ! DO NOT make it an inline function */
 138 #define cvStackAlloc(size) cvAlignPtr( alloca((size) + CV_MALLOC_ALIGN), CV_MALLOC_ALIGN )
 139
 140 #if defined _MSC_VER || defined __BORLANDC__
 141     #define CV_BIG_INT(n)   n##I64
 142     #define CV_BIG_UINT(n)  n##UI64
 143 #else
 144     #define CV_BIG_INT(n)   n##LL
 145     #define CV_BIG_UINT(n)  n##ULL
 146 #endif
 147
 148 #define CV_IMPL CV_EXTERN_C
 149
 150 #if defined WIN32 && !defined WIN64 && (_MSC_VER >= 1200 || defined CV_ICC)
 151     #define CV_DBG_BREAK() __asm int 3
 152 #else
 153     #define CV_DBG_BREAK() assert(0);
 154 #endif
 155
 156 /* default step, set in case of continuous data
 157    to work around checks for valid step in some ipp functions */
 158 #define  CV_STUB_STEP     (1 << 30)
 159
 160 #define  CV_SIZEOF_FLOAT ((int)sizeof(float))
 161 #define  CV_SIZEOF_SHORT ((int)sizeof(short))
 162
 163 #define  CV_ORIGIN_TL  0
 164 #define  CV_ORIGIN_BL  1
 165
 166 /* IEEE754 constants and macros */
 167 #define  CV_POS_INF       0x7f800000
 168 #define  CV_NEG_INF       0x807fffff /* CV_TOGGLE_FLT(0xff800000) */
 169 #define  CV_1F            0x3f800000
 170 #define  CV_TOGGLE_FLT(x) ((x)^((int)(x) < 0 ? 0x7fffffff : 0))
 171 #define  CV_TOGGLE_DBL(x) \
 172     ((x)^((int64)(x) < 0 ? CV_BIG_INT(0x7fffffffffffffff) : 0))
 173
 174 #define  CV_NOP(a)      (a)
 175 #define  CV_ADD(a, b)   ((a) + (b))
 176 #define  CV_SUB(a, b)   ((a) - (b))
 177 #define  CV_MUL(a, b)   ((a) * (b))
 178 #define  CV_AND(a, b)   ((a) & (b))
 179 #define  CV_OR(a, b)    ((a) | (b))
 180 #define  CV_XOR(a, b)   ((a) ^ (b))
 181 #define  CV_ANDN(a, b)  (~(a) & (b))
 182 #define  CV_ORN(a, b)   (~(a) | (b))
 183 #define  CV_SQR(a)      ((a) * (a))
 184
 185 #define  CV_LT(a, b)    ((a) < (b))
 186 #define  CV_LE(a, b)    ((a) <= (b))
 187 #define  CV_EQ(a, b)    ((a) == (b))
 188 #define  CV_NE(a, b)    ((a) != (b))
 189 #define  CV_GT(a, b)    ((a) > (b))
 190 #define  CV_GE(a, b)    ((a) >= (b))
 191
 192 #define  CV_NONZERO(a)      ((a) != 0)
 193 #define  CV_NONZERO_FLT(a)  (((a)+(a)) != 0)
 194
 195 /* general-purpose saturation macros */
 196 #define  CV_CAST_8U(t)  (uchar)(!((t) & ~255) ? (t) : (t) > 0 ? 255 : 0)
 197 #define  CV_CAST_8S(t)  (schar)(!(((t)+128) & ~255) ? (t) : (t) > 0 ? 127 : -128)
 198 #define  CV_CAST_16U(t) (ushort)(!((t) & ~65535) ? (t) : (t) > 0 ? 65535 : 0)
 199 #define  CV_CAST_16S(t) (short)(!(((t)+32768) & ~65535) ? (t) : (t) > 0 ? 32767 : -32768)
 200 #define  CV_CAST_32S(t) (int)(t)
 201 #define  CV_CAST_64S(t) (int64)(t)
 202 #define  CV_CAST_32F(t) (float)(t)
 203 #define  CV_CAST_64F(t) (double)(t)
 204
 205 #define  CV_PASTE2(a,b) a##b
 206 #define  CV_PASTE(a,b)  CV_PASTE2(a,b)
 207
 208 #define  CV_EMPTY
 209 #define  CV_MAKE_STR(a) #a
 210
 211 #define  CV_DEFINE_MASK         \
 212     float maskTab[2]; maskTab[0] = 0.f; maskTab[1] = 1.f;
 213 #define  CV_ANDMASK( m, x )     ((x) & (((m) == 0) - 1))
 214
 215 /* (x) * ((m) == 1 ? 1.f : (m) == 0 ? 0.f : <ERR> */
 216 #define  CV_MULMASK( m, x )       (maskTab[(m) != 0]*(x))
 217
 218 /* (x) * ((m) == -1 ? 1.f : (m) == 0 ? 0.f : <ERR> */
 219 #define  CV_MULMASK1( m, x )      (maskTab[(m)+1]*(x))
 220
 221 #define  CV_ZERO_OBJ(x)  memset((x), 0, sizeof(*(x)))
 222
 223 #define  CV_DIM(static_array) ((int)(sizeof(static_array)/sizeof((static_array)[0])))
 224
 225 #define  CV_UN_ENTRY_C1(worktype)           \
 226     worktype s0 = scalar[0]
 227
 228 #define  CV_UN_ENTRY_C2(worktype)           \
 229     worktype s0 = scalar[0], s1 = scalar[1]
 230
 231 #define  CV_UN_ENTRY_C3(worktype)           \
 232     worktype s0 = scalar[0], s1 = scalar[1], s2 = scalar[2]
 233
 234 #define  CV_UN_ENTRY_C4(worktype)           \
 235     worktype s0 = scalar[0], s1 = scalar[1], s2 = scalar[2], s3 = scalar[3]
 236
 237 #define  cvUnsupportedFormat "Unsupported format"
 238
 239 CV_INLINE void* cvAlignPtr( const void* ptr, int align=32 )
 240 {
 241     assert( (align & (align-1)) == 0 );
 242     return (void*)( ((size_t)ptr + align - 1) & ~(size_t)(align-1) );
 243 }
 244
 245 CV_INLINE int cvAlign( int size, int align )
 246 {
 247     assert( (align & (align-1)) == 0 && size < INT_MAX );
 248     return (size + align - 1) & -align;
 249 }
 250
 251 CV_INLINE  CvSize  cvGetMatSize( const CvMat* mat )
 252 {
 253     CvSize size = { mat->width, mat->height };
 254     return size;
 255 }
 256
 257 #define  CV_DESCALE(x,n)     (((x) + (1 << ((n)-1))) >> (n))
 258 #define  CV_FLT_TO_FIX(x,n)  cvRound((x)*(1<<(n)))
 259
 260 #if 0
 261 /* This is a small engine for performing fast division of multiple numbers
 262    by the same constant. Most compilers do it too if they know the divisor value
 263    at compile-time. The algorithm was taken from Agner Fog's optimization guide
 264    at http://www.agner.org/assem */
 265 typedef struct CvFastDiv
 266 {
 267     unsigned delta, scale, divisor;
 268 }
 269 CvFastDiv;
 270
 271 #define CV_FAST_DIV_SHIFT 32
 272
 273 CV_INLINE CvFastDiv cvFastDiv( int divisor )
 274 {
 275     CvFastDiv fastdiv;
 276
 277     assert( divisor >= 1 );
 278     uint64 temp = ((uint64)1 << CV_FAST_DIV_SHIFT)/divisor;
 279
 280     fastdiv.divisor = divisor;
 281     fastdiv.delta = (unsigned)(((temp & 1) ^ 1) + divisor - 1);
 282     fastdiv.scale = (unsigned)((temp + 1) >> 1);
 283
 284     return fastdiv;
 285 }
 286
 287 #define CV_FAST_DIV( x, fastdiv )  \
 288     ((int)(((int64)((x)*2 + (int)(fastdiv).delta))*(int)(fastdiv).scale>>CV_FAST_DIV_SHIFT))
 289
 290 #define CV_FAST_UDIV( x, fastdiv )  \
 291     ((int)(((uint64)((x)*2 + (fastdiv).delta))*(fastdiv).scale>>CV_FAST_DIV_SHIFT))
 292 #endif
 293
 294 #define CV_MEMCPY_CHAR( dst, src, len )                                             \
 295 {                                                                                   \
 296     size_t _icv_memcpy_i_, _icv_memcpy_len_ = (len);                                \
 297     char* _icv_memcpy_dst_ = (char*)(dst);                                          \
 298     const char* _icv_memcpy_src_ = (const char*)(src);                              \
 299                                                                                     \
 300     for( _icv_memcpy_i_ = 0; _icv_memcpy_i_ < _icv_memcpy_len_; _icv_memcpy_i_++ )  \
 301         _icv_memcpy_dst_[_icv_memcpy_i_] = _icv_memcpy_src_[_icv_memcpy_i_];        \
 302 }
 303
 304
 305 #define CV_MEMCPY_INT( dst, src, len )                                              \
 306 {                                                                                   \
 307     size_t _icv_memcpy_i_, _icv_memcpy_len_ = (len);                                \
 308     int* _icv_memcpy_dst_ = (int*)(dst);                                            \
 309     const int* _icv_memcpy_src_ = (const int*)(src);                                \
 310     assert( ((size_t)_icv_memcpy_src_&(sizeof(int)-1)) == 0 &&                      \
 311             ((size_t)_icv_memcpy_dst_&(sizeof(int)-1)) == 0 );                      \
 312                                                                                     \
 313     for(_icv_memcpy_i_=0;_icv_memcpy_i_<_icv_memcpy_len_;_icv_memcpy_i_++)          \
 314         _icv_memcpy_dst_[_icv_memcpy_i_] = _icv_memcpy_src_[_icv_memcpy_i_];        \
 315 }
 316
 317
 318 #define CV_MEMCPY_AUTO( dst, src, len )                                             \
 319 {                                                                                   \
 320     size_t _icv_memcpy_i_, _icv_memcpy_len_ = (len);                                \
 321     char* _icv_memcpy_dst_ = (char*)(dst);                                          \
 322     const char* _icv_memcpy_src_ = (const char*)(src);                              \
 323     if( (_icv_memcpy_len_ & (sizeof(int)-1)) == 0 )                                 \
 324     {                                                                               \
 325         assert( ((size_t)_icv_memcpy_src_&(sizeof(int)-1)) == 0 &&                  \
 326                 ((size_t)_icv_memcpy_dst_&(sizeof(int)-1)) == 0 );                  \
 327         for( _icv_memcpy_i_ = 0; _icv_memcpy_i_ < _icv_memcpy_len_;                 \
 328             _icv_memcpy_i_+=sizeof(int) )                                           \
 329         {                                                                           \
 330             *(int*)(_icv_memcpy_dst_+_icv_memcpy_i_) =                              \
 331             *(const int*)(_icv_memcpy_src_+_icv_memcpy_i_);                         \
 332         }                                                                           \
 333     }                                                                               \
 334     else                                                                            \
 335     {                                                                               \
 336         for(_icv_memcpy_i_ = 0; _icv_memcpy_i_ < _icv_memcpy_len_; _icv_memcpy_i_++)\
 337             _icv_memcpy_dst_[_icv_memcpy_i_] = _icv_memcpy_src_[_icv_memcpy_i_];    \
 338     }                                                                               \
 339 }
 340
 341
 342 #define CV_ZERO_CHAR( dst, len )                                                    \
 343 {                                                                                   \
 344     size_t _icv_memcpy_i_, _icv_memcpy_len_ = (len);                                \
 345     char* _icv_memcpy_dst_ = (char*)(dst);                                          \
 346                                                                                     \
 347     for( _icv_memcpy_i_ = 0; _icv_memcpy_i_ < _icv_memcpy_len_; _icv_memcpy_i_++ )  \
 348         _icv_memcpy_dst_[_icv_memcpy_i_] = '\0';                                    \
 349 }
 350
 351
 352 #define CV_ZERO_INT( dst, len )                                                     \
 353 {                                                                                   \
 354     size_t _icv_memcpy_i_, _icv_memcpy_len_ = (len);                                \
 355     int* _icv_memcpy_dst_ = (int*)(dst);                                            \
 356     assert( ((size_t)_icv_memcpy_dst_&(sizeof(int)-1)) == 0 );                      \
 357                                                                                     \
 358     for(_icv_memcpy_i_=0;_icv_memcpy_i_<_icv_memcpy_len_;_icv_memcpy_i_++)          \
 359         _icv_memcpy_dst_[_icv_memcpy_i_] = 0;                                       \
 360 }
 361
 362
 363 /****************************************************************************************\
 364
 365   Generic implementation of QuickSort algorithm.
 366   ----------------------------------------------
 367   Using this macro user can declare customized sort function that can be much faster
 368   than built-in qsort function because of lower overhead on elements
 369   comparison and exchange. The macro takes less_than (or LT) argument - a macro or function
 370   that takes 2 arguments returns non-zero if the first argument should be before the second
 371   one in the sorted sequence and zero otherwise.
 372
 373   Example:
 374
 375     Suppose that the task is to sort points by ascending of y coordinates and if
 376     y's are equal x's should ascend.
 377
 378     The code is:
 379     ------------------------------------------------------------------------------
 380            #define cmp_pts( pt1, pt2 ) \
 381                ((pt1).y < (pt2).y || ((pt1).y < (pt2).y && (pt1).x < (pt2).x))
 382
 383            [static] CV_IMPLEMENT_QSORT( icvSortPoints, CvPoint, cmp_pts )
 384     ------------------------------------------------------------------------------
 385
 386     After that the function "void icvSortPoints( CvPoint* array, size_t total, int aux );"
 387     is available to user.
 388
 389   aux is an additional parameter, which can be used when comparing elements.
 390   The current implementation was derived from *BSD system qsort():
 391
 392     * Copyright (c) 1992, 1993
 393     *  The Regents of the University of California.  All rights reserved.
 394     *
 395     * Redistribution and use in source and binary forms, with or without
 396     * modification, are permitted provided that the following conditions
 397     * are met:
 398     * 1. Redistributions of source code must retain the above copyright
 399     *    notice, this list of conditions and the following disclaimer.
 400     * 2. Redistributions in binary form must reproduce the above copyright
 401     *    notice, this list of conditions and the following disclaimer in the
 402     *    documentation and/or other materials provided with the distribution.
 403     * 3. All advertising materials mentioning features or use of this software
 404     *    must display the following acknowledgement:
 405     *  This product includes software developed by the University of
 406     *  California, Berkeley and its contributors.
 407     * 4. Neither the name of the University nor the names of its contributors
 408     *    may be used to endorse or promote products derived from this software
 409     *    without specific prior written permission.
 410     *
 411     * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 412     * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 413     * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 414     * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 415     * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 416     * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 417     * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 418     * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 419     * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 420     * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 421     * SUCH DAMAGE.
 422
 423 \****************************************************************************************/
 424
 425 #define CV_IMPLEMENT_QSORT_EX( func_name, T, LT, user_data_type )                   \
 426 void func_name( T *array, size_t total, user_data_type aux )                        \
 427 {                                                                                   \
 428     int isort_thresh = 7;                                                           \
 429     T t;                                                                            \
 430     int sp = 0;                                                                     \
 431                                                                                     \
 432     struct                                                                          \
 433     {                                                                               \
 434         T *lb;                                                                      \
 435         T *ub;                                                                      \
 436     }                                                                               \
 437     stack[48];                                                                      \
 438                                                                                     \
 439     aux = aux;                                                                      \
 440                                                                                     \
 441     if( total <= 1 )                                                                \
 442         return;                                                                     \
 443                                                                                     \
 444     stack[0].lb = array;                                                            \
 445     stack[0].ub = array + (total - 1);                                              \
 446                                                                                     \
 447     while( sp >= 0 )                                                                \
 448     {                                                                               \
 449         T* left = stack[sp].lb;                                                     \
 450         T* right = stack[sp--].ub;                                                  \
 451                                                                                     \
 452         for(;;)                                                                     \
 453         {                                                                           \
 454             int i, n = (int)(right - left) + 1, m;                                  \
 455             T* ptr;                                                                 \
 456             T* ptr2;                                                                \
 457                                                                                     \
 458             if( n <= isort_thresh )                                                 \
 459             {                                                                       \
 460             insert_sort:                                                            \
 461                 for( ptr = left + 1; ptr <= right; ptr++ )                          \
 462                 {                                                                   \
 463                     for( ptr2 = ptr; ptr2 > left && LT(ptr2[0],ptr2[-1]); ptr2--)   \
 464                         CV_SWAP( ptr2[0], ptr2[-1], t );                            \
 465                 }                                                                   \
 466                 break;                                                              \
 467             }                                                                       \
 468             else                                                                    \
 469             {                                                                       \
 470                 T* left0;                                                           \
 471                 T* left1;                                                           \
 472                 T* right0;                                                          \
 473                 T* right1;                                                          \
 474                 T* pivot;                                                           \
 475                 T* a;                                                               \
 476                 T* b;                                                               \
 477                 T* c;                                                               \
 478                 int swap_cnt = 0;                                                   \
 479                                                                                     \
 480                 left0 = left;                                                       \
 481                 right0 = right;                                                     \
 482                 pivot = left + (n/2);                                               \
 483                                                                                     \
 484                 if( n > 40 )                                                        \
 485                 {                                                                   \
 486                     int d = n / 8;                                                  \
 487                     a = left, b = left + d, c = left + 2*d;                         \
 488                     left = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))     \
 489                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));    \
 490                                                                                     \
 491                     a = pivot - d, b = pivot, c = pivot + d;                        \
 492                     pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))    \
 493                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));    \
 494                                                                                     \
 495                     a = right - 2*d, b = right - d, c = right;                      \
 496                     right = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))    \
 497                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));    \
 498                 }                                                                   \
 499                                                                                     \
 500                 a = left, b = pivot, c = right;                                     \
 501                 pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))        \
 502                                    : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));       \
 503                 if( pivot != left0 )                                                \
 504                 {                                                                   \
 505                     CV_SWAP( *pivot, *left0, t );                                   \
 506                     pivot = left0;                                                  \
 507                 }                                                                   \
 508                 left = left1 = left0 + 1;                                           \
 509                 right = right1 = right0;                                            \
 510                                                                                     \
 511                 for(;;)                                                             \
 512                 {                                                                   \
 513                     while( left <= right && !LT(*pivot, *left) )                    \
 514                     {                                                               \
 515                         if( !LT(*left, *pivot) )                                    \
 516                         {                                                           \
 517                             if( left > left1 )                                      \
 518                                 CV_SWAP( *left1, *left, t );                        \
 519                             swap_cnt = 1;                                           \
 520                             left1++;                                                \
 521                         }                                                           \
 522                         left++;                                                     \
 523                     }                                                               \
 524                                                                                     \
 525                     while( left <= right && !LT(*right, *pivot) )                   \
 526                     {                                                               \
 527                         if( !LT(*pivot, *right) )                                   \
 528                         {                                                           \
 529                             if( right < right1 )                                    \
 530                                 CV_SWAP( *right1, *right, t );                      \
 531                             swap_cnt = 1;                                           \
 532                             right1--;                                               \
 533                         }                                                           \
 534                         right--;                                                    \
 535                     }                                                               \
 536                                                                                     \
 537                     if( left > right )                                              \
 538                         break;                                                      \
 539                     CV_SWAP( *left, *right, t );                                    \
 540                     swap_cnt = 1;                                                   \
 541                     left++;                                                         \
 542                     right--;                                                        \
 543                 }                                                                   \
 544                                                                                     \
 545                 if( swap_cnt == 0 )                                                 \
 546                 {                                                                   \
 547                     left = left0, right = right0;                                   \
 548                     goto insert_sort;                                               \
 549                 }                                                                   \
 550                                                                                     \
 551                 n = MIN( (int)(left1 - left0), (int)(left - left1) );               \
 552                 for( i = 0; i < n; i++ )                                            \
 553                     CV_SWAP( left0[i], left[i-n], t );                              \
 554                                                                                     \
 555                 n = MIN( (int)(right0 - right1), (int)(right1 - right) );           \
 556                 for( i = 0; i < n; i++ )                                            \
 557                     CV_SWAP( left[i], right0[i-n+1], t );                           \
 558                 n = (int)(left - left1);                                            \
 559                 m = (int)(right1 - right);                                          \
 560                 if( n > 1 )                                                         \
 561                 {                                                                   \
 562                     if( m > 1 )                                                     \
 563                     {                                                               \
 564                         if( n > m )                                                 \
 565                         {                                                           \
 566                             stack[++sp].lb = left0;                                 \
 567                             stack[sp].ub = left0 + n - 1;                           \
 568                             left = right0 - m + 1, right = right0;                  \
 569                         }                                                           \
 570                         else                                                        \
 571                         {                                                           \
 572                             stack[++sp].lb = right0 - m + 1;                        \
 573                             stack[sp].ub = right0;                                  \
 574                             left = left0, right = left0 + n - 1;                    \
 575                         }                                                           \
 576                     }                                                               \
 577                     else                                                            \
 578                         left = left0, right = left0 + n - 1;                        \
 579                 }                                                                   \
 580                 else if( m > 1 )                                                    \
 581                     left = right0 - m + 1, right = right0;                          \
 582                 else                                                                \
 583                     break;                                                          \
 584             }                                                                       \
 585         }                                                                           \
 586     }                                                                               \
 587 }
 588
 589 #define CV_IMPLEMENT_QSORT( func_name, T, cmp )  \
 590     CV_IMPLEMENT_QSORT_EX( func_name, T, cmp, int )
 591
 592 /****************************************************************************************\
 593 *                     Structures and macros for integration with IPP                     *
 594 \****************************************************************************************/
 595
 596 /* IPP-compatible return codes */
 597 typedef enum CvStatus
 598 {
 599     CV_BADMEMBLOCK_ERR          = -113,
 600     CV_INPLACE_NOT_SUPPORTED_ERR= -112,
 601     CV_UNMATCHED_ROI_ERR        = -111,
 602     CV_NOTFOUND_ERR             = -110,
 603     CV_BADCONVERGENCE_ERR       = -109,
 604
 605     CV_BADDEPTH_ERR             = -107,
 606     CV_BADROI_ERR               = -106,
 607     CV_BADHEADER_ERR            = -105,
 608     CV_UNMATCHED_FORMATS_ERR    = -104,
 609     CV_UNSUPPORTED_COI_ERR      = -103,
 610     CV_UNSUPPORTED_CHANNELS_ERR = -102,
 611     CV_UNSUPPORTED_DEPTH_ERR    = -101,
 612     CV_UNSUPPORTED_FORMAT_ERR   = -100,
 613
 614     CV_BADARG_ERR      = -49,  //ipp comp
 615     CV_NOTDEFINED_ERR  = -48,  //ipp comp
 616
 617     CV_BADCHANNELS_ERR = -47,  //ipp comp
 618     CV_BADRANGE_ERR    = -44,  //ipp comp
 619     CV_BADSTEP_ERR     = -29,  //ipp comp
 620
 621     CV_BADFLAG_ERR     =  -12,
 622     CV_DIV_BY_ZERO_ERR =  -11, //ipp comp
 623     CV_BADCOEF_ERR     =  -10,
 624
 625     CV_BADFACTOR_ERR   =  -7,
 626     CV_BADPOINT_ERR    =  -6,
 627     CV_BADSCALE_ERR    =  -4,
 628     CV_OUTOFMEM_ERR    =  -3,
 629     CV_NULLPTR_ERR     =  -2,
 630     CV_BADSIZE_ERR     =  -1,
 631     CV_NO_ERR          =   0,
 632     CV_OK              =   CV_NO_ERR
 633 }
 634 CvStatus;
 635
 636 #define CV_ERROR_FROM_STATUS( result )                \
 637     CV_ERROR( cvErrorFromIppStatus( result ), "OpenCV function failed" )
 638
 639 #define IPPI_CALL( Func )                                              \
 640 {                                                                      \
 641       CvStatus  ippi_call_result;                                      \
 642       ippi_call_result = Func;                                         \
 643                                                                        \
 644       if( ippi_call_result < 0 )                                       \
 645             CV_ERROR_FROM_STATUS( (ippi_call_result));                 \
 646 }
 647
 648 #define CV_PLUGIN_NONE      0
 649 #define CV_PLUGIN_OPTCV     1 /* custom "emerged" ippopencv library */
 650 #define CV_PLUGIN_IPPCV     2 /* IPP: computer vision */
 651 #define CV_PLUGIN_IPPI      3 /* IPP: image processing */
 652 #define CV_PLUGIN_IPPS      4 /* IPP: signal processing */
 653 #define CV_PLUGIN_IPPVM     5 /* IPP: vector math functions */
 654 #define CV_PLUGIN_IPPCC     6 /* IPP: color space conversion */
 655 #define CV_PLUGIN_MKL       8 /* Intel Math Kernel Library */
 656
 657 #define CV_PLUGIN_MAX      16
 658
 659 #define CV_PLUGINS1(lib1) ((lib1)&15)
 660 #define CV_PLUGINS2(lib1,lib2) (((lib1)&15)|(((lib2)&15)<<4))
 661 #define CV_PLUGINS3(lib1,lib2,lib3) (((lib1)&15)|(((lib2)&15)<<4)|(((lib2)&15)<<8))
 662
 663 #define CV_NOTHROW throw()
 664
 665 #ifndef IPCVAPI
 666 #define IPCVAPI(type,declspec,name,args)                        \
 667     /* function pointer */                                      \
 668     typedef type (declspec* name##_t) args;                     \
 669     extern name##_t name##_p;                                   \
 670     type declspec name args;
 671 #endif
 672
 673 #define IPCVAPI_EX(type,name,ipp_name,ipp_search_modules,args)  \
 674     IPCVAPI(type,CV_STDCALL,name,args)
 675
 676 #define IPCVAPI_C_EX(type,name,ipp_name,ipp_search_modules,args)\
 677     IPCVAPI(type,CV_CDECL,name,args)
 678
 679 #ifndef IPCVAPI_IMPL
 680 #define IPCVAPI_IMPL(type,name,args,arg_names)                  \
 681     static type CV_STDCALL name##_f args;                       \
 682     name##_t name##_p = name##_f;                               \
 683     type CV_STDCALL name args { return name##_p arg_names; }    \
 684     static type CV_STDCALL name##_f args
 685 #endif
 686
 687 /* IPP types' enumeration */
 688 typedef enum CvDataType {
 689     cv1u,
 690     cv8u, cv8s,
 691     cv16u, cv16s, cv16sc,
 692     cv32u, cv32s, cv32sc,
 693     cv32f, cv32fc,
 694     cv64u, cv64s, cv64sc,
 695     cv64f, cv64fc
 696 } CvDataType;
 697
 698 typedef enum CvHintAlgorithm {
 699     cvAlgHintNone,
 700     cvAlgHintFast,
 701     cvAlgHintAccurate
 702 } CvHintAlgorithm;
 703
 704 typedef enum CvCmpOp {
 705     cvCmpLess,
 706     cvCmpLessEq,
 707     cvCmpEq,
 708     cvCmpGreaterEq,
 709     cvCmpGreater
 710 } CvCmpOp;
 711
 712 typedef struct CvFuncTable
 713 {
 714     void*   fn_2d[CV_DEPTH_MAX];
 715 }
 716 CvFuncTable;
 717
 718 typedef struct CvBigFuncTable
 719 {
 720     void*   fn_2d[CV_DEPTH_MAX*CV_CN_MAX];
 721 }
 722 CvBigFuncTable;
 723
 724
 725 typedef struct CvBtFuncTable
 726 {
 727     void*   fn_2d[33];
 728 }
 729 CvBtFuncTable;
 730
 731 typedef CvStatus (CV_STDCALL *CvFunc2D_1A)(void* arr, int step, CvSize size);
 732
 733 typedef CvStatus (CV_STDCALL *CvFunc2D_1A1P)(void* arr, int step, CvSize size, void* param);
 734
 735 typedef CvStatus (CV_STDCALL *CvFunc2D_1A1P1I)(void* arr, int step, CvSize size,
 736                                                void* param, int flag);
 737
 738 typedef CvStatus (CV_STDCALL *CvFunc2DnC_1A1P)( void* arr, int step, CvSize size,
 739                                                 int cn, int coi, void* param );
 740
 741 typedef CvStatus (CV_STDCALL *CvFunc2DnC_1A1P)( void* arr, int step, CvSize size,
 742                                                 int cn, int coi, void* param );
 743
 744 typedef CvStatus (CV_STDCALL *CvFunc2D_1A2P)( void* arr, int step, CvSize size,
 745                                               void* param1, void* param2 );
 746
 747 typedef CvStatus (CV_STDCALL *CvFunc2DnC_1A2P)( void* arr, int step,
 748                                                 CvSize size, int cn, int coi,
 749                                                 void* param1, void* param2 );
 750
 751 typedef CvStatus (CV_STDCALL *CvFunc2D_1A4P)( void* arr, int step, CvSize size,
 752                                               void* param1, void* param2,
 753                                               void* param3, void* param4 );
 754
 755 typedef CvStatus (CV_STDCALL *CvFunc2DnC_1A4P)( void* arr, int step,
 756                                                 CvSize size, int cn, int coi,
 757                                                 void* param1, void* param2,
 758                                                 void* param3, void* param4 );
 759
 760 typedef CvStatus (CV_STDCALL *CvFunc2D_2A)( void* arr0, int step0,
 761                                             void* arr1, int step1, CvSize size );
 762
 763 typedef CvStatus (CV_STDCALL *CvFunc2D_2A1P)( void* arr0, int step0,
 764                                               void* arr1, int step1,
 765                                               CvSize size, void* param );
 766
 767 typedef CvStatus (CV_STDCALL *CvFunc2DnC_2A1P)( void* arr0, int step0,
 768                                                 void* arr1, int step1,
 769                                                 CvSize size, int cn,
 770                                                 int coi, void* param );
 771
 772 typedef CvStatus (CV_STDCALL *CvFunc2DnC_2A1P)( void* arr0, int step0,
 773                                                 void* arr1, int step1,
 774                                                 CvSize size, int cn,
 775                                                 int coi, void* param );
 776
 777 typedef CvStatus (CV_STDCALL *CvFunc2D_2A2P)( void* arr0, int step0,
 778                                               void* arr1, int step1, CvSize size,
 779                                               void* param1, void* param2 );
 780
 781 typedef CvStatus (CV_STDCALL *CvFunc2DnC_2A2P)( void* arr0, int step0,
 782                                                 void* arr1, int step1,
 783                                                 CvSize size, int cn, int coi,
 784                                                 void* param1, void* param2 );
 785
 786 typedef CvStatus (CV_STDCALL *CvFunc2D_2A1P1I)( void* arr0, int step0,
 787                                                 void* arr1, int step1, CvSize size,
 788                                                 void* param, int flag );
 789
 790 typedef CvStatus (CV_STDCALL *CvFunc2D_2A4P)( void* arr0, int step0,
 791                                               void* arr1, int step1, CvSize size,
 792                                               void* param1, void* param2,
 793                                               void* param3, void* param4 );
 794
 795 typedef CvStatus (CV_STDCALL *CvFunc2DnC_2A4P)( void* arr0, int step0,
 796                                                 void* arr1, int step1, CvSize size,
 797                                                 int cn, int coi,
 798                                                 void* param1, void* param2,
 799                                                 void* param3, void* param4 );
 800
 801 typedef CvStatus (CV_STDCALL *CvFunc2D_3A)( void* arr0, int step0,
 802                                             void* arr1, int step1,
 803                                             void* arr2, int step2, CvSize size );
 804
 805 typedef CvStatus (CV_STDCALL *CvFunc2D_3A1P)( void* arr0, int step0,
 806                                               void* arr1, int step1,
 807                                               void* arr2, int step2,
 808                                               CvSize size, void* param );
 809
 810 typedef CvStatus (CV_STDCALL *CvFunc2D_3A1I)( void* arr0, int step0,
 811                                               void* arr1, int step1,
 812                                               void* arr2, int step2,
 813                                               CvSize size, int flag );
 814
 815 typedef CvStatus (CV_STDCALL *CvFunc2DnC_3A1P)( void* arr0, int step0,
 816                                                 void* arr1, int step1,
 817                                                 void* arr2, int step2,
 818                                                 CvSize size, int cn,
 819                                                 int coi, void* param );
 820
 821 typedef CvStatus (CV_STDCALL *CvFunc2D_4A)( void* arr0, int step0,
 822                                             void* arr1, int step1,
 823                                             void* arr2, int step2,
 824                                             void* arr3, int step3,
 825                                             CvSize size );
 826
 827 typedef CvStatus (CV_STDCALL *CvFunc0D)( const void* src, void* dst, int param );
 828
 829 #define CV_DEF_INIT_FUNC_TAB_2D( FUNCNAME, FLAG )                   \
 830 static void  icvInit##FUNCNAME##FLAG##Table( CvFuncTable* tab )     \
 831 {                                                                   \
 832     assert( tab );                                                  \
 833                                                                     \
 834     tab->fn_2d[CV_8U]  = (void*)icv##FUNCNAME##_8u_##FLAG;          \
 835     tab->fn_2d[CV_8S]  = (void*)icv##FUNCNAME##_8s_##FLAG;          \
 836     tab->fn_2d[CV_16U] = (void*)icv##FUNCNAME##_16u_##FLAG;         \
 837     tab->fn_2d[CV_16S] = (void*)icv##FUNCNAME##_16s_##FLAG;         \
 838     tab->fn_2d[CV_32S] = (void*)icv##FUNCNAME##_32s_##FLAG;         \
 839     tab->fn_2d[CV_32F] = (void*)icv##FUNCNAME##_32f_##FLAG;         \
 840     tab->fn_2d[CV_64F] = (void*)icv##FUNCNAME##_64f_##FLAG;         \
 841 }
 842
 843
 844 #define CV_DEF_INIT_BIG_FUNC_TAB_2D( FUNCNAME, FLAG )               \
 845 static void  icvInit##FUNCNAME##FLAG##Table( CvBigFuncTable* tab )  \
 846 {                                                                   \
 847     assert( tab );                                                  \
 848                                                                     \
 849     tab->fn_2d[CV_8UC1]  = (void*)icv##FUNCNAME##_8u_C1##FLAG;      \
 850     tab->fn_2d[CV_8UC2]  = (void*)icv##FUNCNAME##_8u_C2##FLAG;      \
 851     tab->fn_2d[CV_8UC3]  = (void*)icv##FUNCNAME##_8u_C3##FLAG;      \
 852     tab->fn_2d[CV_8UC4]  = (void*)icv##FUNCNAME##_8u_C4##FLAG;      \
 853                                                                     \
 854     tab->fn_2d[CV_8SC1]  = (void*)icv##FUNCNAME##_8s_C1##FLAG;      \
 855     tab->fn_2d[CV_8SC2]  = (void*)icv##FUNCNAME##_8s_C2##FLAG;      \
 856     tab->fn_2d[CV_8SC3]  = (void*)icv##FUNCNAME##_8s_C3##FLAG;      \
 857     tab->fn_2d[CV_8SC4]  = (void*)icv##FUNCNAME##_8s_C4##FLAG;      \
 858                                                                     \
 859     tab->fn_2d[CV_16UC1] = (void*)icv##FUNCNAME##_16u_C1##FLAG;     \
 860     tab->fn_2d[CV_16UC2] = (void*)icv##FUNCNAME##_16u_C2##FLAG;     \
 861     tab->fn_2d[CV_16UC3] = (void*)icv##FUNCNAME##_16u_C3##FLAG;     \
 862     tab->fn_2d[CV_16UC4] = (void*)icv##FUNCNAME##_16u_C4##FLAG;     \
 863                                                                     \
 864     tab->fn_2d[CV_16SC1] = (void*)icv##FUNCNAME##_16s_C1##FLAG;     \
 865     tab->fn_2d[CV_16SC2] = (void*)icv##FUNCNAME##_16s_C2##FLAG;     \
 866     tab->fn_2d[CV_16SC3] = (void*)icv##FUNCNAME##_16s_C3##FLAG;     \
 867     tab->fn_2d[CV_16SC4] = (void*)icv##FUNCNAME##_16s_C4##FLAG;     \
 868                                                                     \
 869     tab->fn_2d[CV_32SC1] = (void*)icv##FUNCNAME##_32s_C1##FLAG;     \
 870     tab->fn_2d[CV_32SC2] = (void*)icv##FUNCNAME##_32s_C2##FLAG;     \
 871     tab->fn_2d[CV_32SC3] = (void*)icv##FUNCNAME##_32s_C3##FLAG;     \
 872     tab->fn_2d[CV_32SC4] = (void*)icv##FUNCNAME##_32s_C4##FLAG;     \
 873                                                                     \
 874     tab->fn_2d[CV_32FC1] = (void*)icv##FUNCNAME##_32f_C1##FLAG;     \
 875     tab->fn_2d[CV_32FC2] = (void*)icv##FUNCNAME##_32f_C2##FLAG;     \
 876     tab->fn_2d[CV_32FC3] = (void*)icv##FUNCNAME##_32f_C3##FLAG;     \
 877     tab->fn_2d[CV_32FC4] = (void*)icv##FUNCNAME##_32f_C4##FLAG;     \
 878                                                                     \
 879     tab->fn_2d[CV_64FC1] = (void*)icv##FUNCNAME##_64f_C1##FLAG;     \
 880     tab->fn_2d[CV_64FC2] = (void*)icv##FUNCNAME##_64f_C2##FLAG;     \
 881     tab->fn_2d[CV_64FC3] = (void*)icv##FUNCNAME##_64f_C3##FLAG;     \
 882     tab->fn_2d[CV_64FC4] = (void*)icv##FUNCNAME##_64f_C4##FLAG;     \
 883 }
 884
 885 #define CV_DEF_INIT_FUNC_TAB_0D( FUNCNAME )                         \
 886 static void  icvInit##FUNCNAME##Table( CvFuncTable* tab )           \
 887 {                                                                   \
 888     tab->fn_2d[CV_8U]  = (void*)icv##FUNCNAME##_8u;                 \
 889     tab->fn_2d[CV_8S]  = (void*)icv##FUNCNAME##_8s;                 \
 890     tab->fn_2d[CV_16U] = (void*)icv##FUNCNAME##_16u;                \
 891     tab->fn_2d[CV_16S] = (void*)icv##FUNCNAME##_16s;                \
 892     tab->fn_2d[CV_32S] = (void*)icv##FUNCNAME##_32s;                \
 893     tab->fn_2d[CV_32F] = (void*)icv##FUNCNAME##_32f;                \
 894     tab->fn_2d[CV_64F] = (void*)icv##FUNCNAME##_64f;                \
 895 }
 896
 897 #define CV_DEF_INIT_FUNC_TAB_1D  CV_DEF_INIT_FUNC_TAB_0D
 898
 899
 900 #define CV_DEF_INIT_PIXSIZE_TAB_2D( FUNCNAME, FLAG )                \
 901 static void icvInit##FUNCNAME##FLAG##Table( CvBtFuncTable* table )  \
 902 {                                                                   \
 903     table->fn_2d[1]  = (void*)icv##FUNCNAME##_8u_C1##FLAG;          \
 904     table->fn_2d[2]  = (void*)icv##FUNCNAME##_8u_C2##FLAG;          \
 905     table->fn_2d[3]  = (void*)icv##FUNCNAME##_8u_C3##FLAG;          \
 906     table->fn_2d[4]  = (void*)icv##FUNCNAME##_16u_C2##FLAG;         \
 907     table->fn_2d[6]  = (void*)icv##FUNCNAME##_16u_C3##FLAG;         \
 908     table->fn_2d[8]  = (void*)icv##FUNCNAME##_32s_C2##FLAG;         \
 909     table->fn_2d[12] = (void*)icv##FUNCNAME##_32s_C3##FLAG;         \
 910     table->fn_2d[16] = (void*)icv##FUNCNAME##_64s_C2##FLAG;         \
 911     table->fn_2d[24] = (void*)icv##FUNCNAME##_64s_C3##FLAG;         \
 912     table->fn_2d[32] = (void*)icv##FUNCNAME##_64s_C4##FLAG;         \
 913 }
 914
 915 #define  CV_GET_FUNC_PTR( func, table_entry )  \
 916     func = (table_entry);                      \
 917                                                \
 918     if( !func )                                \
 919         CV_ERROR( CV_StsUnsupportedFormat, "" )
 920
 921
 922 #endif /*_CXCORE_MISC_H_*/