cxarray.cpp

detect rectangle by open cv.

        {
            int coi = 0;
            CV_CALL( hdr = cvGetMatND( arr, stubs + i, &coi ));
            if( coi != 0 )
                CV_ERROR( CV_BadCOI, "COI set is not allowed here" );
        }

        iterator->hdr[i] = hdr;

        if( i > 0 )
        {
            if( hdr->dims != hdr0->dims )
                CV_ERROR( CV_StsUnmatchedSizes,
                          "Number of dimensions is the same for all arrays" );
            
            if( i < count )
            {
                switch( flags & (CV_NO_DEPTH_CHECK|CV_NO_CN_CHECK))
                {
                case 0:
                    if( !CV_ARE_TYPES_EQ( hdr, hdr0 ))
                        CV_ERROR( CV_StsUnmatchedFormats,
                                  "Data type is not the same for all arrays" );
                    break;
                case CV_NO_DEPTH_CHECK:
                    if( !CV_ARE_CNS_EQ( hdr, hdr0 ))
                        CV_ERROR( CV_StsUnmatchedFormats,
                                  "Number of channels is not the same for all arrays" );
                    break;
                case CV_NO_CN_CHECK:
                    if( !CV_ARE_CNS_EQ( hdr, hdr0 ))
                        CV_ERROR( CV_StsUnmatchedFormats,
                                  "Depth is not the same for all arrays" );
                    break;
                }
            }
            else
            {
                if( !CV_IS_MASK_ARR( hdr ))
                    CV_ERROR( CV_StsBadMask, "Mask should have 8uC1 or 8sC1 data type" );
            }

            if( !(flags & CV_NO_SIZE_CHECK) )
            {
                for( j = 0; j < hdr->dims; j++ )
                    if( hdr->dim[j].size != hdr0->dim[j].size )
                        CV_ERROR( CV_StsUnmatchedSizes,
                                  "Dimension sizes are the same for all arrays" );
            }
        }
        else
            hdr0 = hdr;

        step = CV_ELEM_SIZE(hdr->type);
        for( j = hdr->dims - 1; j > dim0; j-- )
        {
            if( step != hdr->dim[j].step )
                break;
            step *= hdr->dim[j].size;
        }

        if( j == dim0 && step > INT_MAX )
            j++;

        if( j > dim0 )
            dim0 = j;

        iterator->hdr[i] = (CvMatND*)hdr;
        iterator->ptr[i] = (uchar*)hdr->data.ptr;
    }

    size = 1;
    for( j = hdr0->dims - 1; j > dim0; j-- )
        size *= hdr0->dim[j].size;

    dims = dim0 + 1;
    iterator->dims = dims;
    iterator->count = count;
    iterator->size = cvSize(size,1);

    for( i = 0; i < dims; i++ )
        iterator->stack[i] = hdr0->dim[i].size;

    __END__;

    return dims;
}


// returns zero value if iteration is finished, non-zero otherwise
CV_IMPL  int  cvNextNArraySlice( CvNArrayIterator* iterator )
{
    assert( iterator != 0 );
    int i, dims, size = 0;

    for( dims = iterator->dims; dims > 0; dims-- )
    {
        for( i = 0; i < iterator->count; i++ )
            iterator->ptr[i] += iterator->hdr[i]->dim[dims-1].step;

        if( --iterator->stack[dims-1] > 0 )
            break;

        size = iterator->hdr[0]->dim[dims-1].size;

        for( i = 0; i < iterator->count; i++ )
            iterator->ptr[i] -= (size_t)size*iterator->hdr[i]->dim[dims-1].step;

        iterator->stack[dims-1] = size;
    }

    return dims > 0;
}


/****************************************************************************************\
*                            CvSparseMat creation and basic operations                   *
\****************************************************************************************/


// Creates CvMatND and underlying data
CV_IMPL CvSparseMat*
cvCreateSparseMat( int dims, const int* sizes, int type )
{
    CvSparseMat* arr = 0;

    CV_FUNCNAME( "cvCreateSparseMat" );
    
    __BEGIN__;

    type = CV_MAT_TYPE( type );
    int pix_size1 = CV_ELEM_SIZE1(type);
    int pix_size = pix_size1*CV_MAT_CN(type);
    int i, size;
    CvMemStorage* storage;

    if( pix_size == 0 )
        CV_ERROR( CV_StsUnsupportedFormat, "invalid array data type" );

    if( dims <= 0 || dims > CV_MAX_DIM_HEAP )
        CV_ERROR( CV_StsOutOfRange, "bad number of dimensions" );

    if( !sizes )
        CV_ERROR( CV_StsNullPtr, "NULL <sizes> pointer" );

    for( i = 0; i < dims; i++ )
    {
        if( sizes[i] <= 0 )
            CV_ERROR( CV_StsBadSize, "one of dimesion sizes is non-positive" );
    }

    CV_CALL( arr = (CvSparseMat*)cvAlloc(sizeof(*arr)+MAX(0,dims-CV_MAX_DIM)*sizeof(arr->size[0])));

    arr->type = CV_SPARSE_MAT_MAGIC_VAL | type;
    arr->dims = dims;
    arr->refcount = 0;
    arr->hdr_refcount = 1;
    memcpy( arr->size, sizes, dims*sizeof(sizes[0]));

    arr->valoffset = (int)cvAlign(sizeof(CvSparseNode), pix_size1);
    arr->idxoffset = (int)cvAlign(arr->valoffset + pix_size, sizeof(int));
    size = (int)cvAlign(arr->idxoffset + dims*sizeof(int), sizeof(CvSetElem));

    CV_CALL( storage = cvCreateMemStorage( CV_SPARSE_MAT_BLOCK ));
    CV_CALL( arr->heap = cvCreateSet( 0, sizeof(CvSet), size, storage ));

    arr->hashsize = CV_SPARSE_HASH_SIZE0;
    size = arr->hashsize*sizeof(arr->hashtable[0]);
    
    CV_CALL( arr->hashtable = (void**)cvAlloc( size ));
    memset( arr->hashtable, 0, size );

    __END__;

    if( cvGetErrStatus() < 0 )
        cvReleaseSparseMat( &arr );

    return arr;
}


// Creates CvMatND and underlying data
CV_IMPL void
cvReleaseSparseMat( CvSparseMat** array )
{
    CV_FUNCNAME( "cvReleaseSparseMat" );
    
    __BEGIN__;

    if( !array )
        CV_ERROR_FROM_CODE( CV_HeaderIsNull );

    if( *array )
    {
        CvSparseMat* arr = *array;
        
        if( !CV_IS_SPARSE_MAT_HDR(arr) )
            CV_ERROR_FROM_CODE( CV_StsBadFlag );

        *array = 0;

        cvReleaseMemStorage( &arr->heap->storage );
        cvFree( &arr->hashtable );
        cvFree( &arr );
    }

    __END__;
}


// Creates CvMatND and underlying data
CV_IMPL CvSparseMat*
cvCloneSparseMat( const CvSparseMat* src )
{
    CvSparseMat* dst = 0;
    
    CV_FUNCNAME( "cvCloneSparseMat" );
    
    __BEGIN__;

    if( !CV_IS_SPARSE_MAT_HDR(src) )
        CV_ERROR( CV_StsBadArg, "Invalid sparse array header" );

    CV_CALL( dst = cvCreateSparseMat( src->dims, src->size, src->type ));
    CV_CALL( cvCopy( src, dst )); 

    __END__;

    if( cvGetErrStatus() < 0 )
        cvReleaseSparseMat( &dst );
    
    return dst;
}


CvSparseNode*
cvInitSparseMatIterator( const CvSparseMat* mat, CvSparseMatIterator* iterator )
{
    CvSparseNode* node = 0;
    
    CV_FUNCNAME( "cvInitSparseMatIterator" );

    __BEGIN__;

    int idx;

    if( !CV_IS_SPARSE_MAT( mat ))
        CV_ERROR( CV_StsBadArg, "Invalid sparse matrix header" );

    if( !iterator )
        CV_ERROR( CV_StsNullPtr, "NULL iterator pointer" );

    iterator->mat = (CvSparseMat*)mat;
    iterator->node = 0;

    for( idx = 0; idx < mat->hashsize; idx++ )
        if( mat->hashtable[idx] )
        {
            node = iterator->node = (CvSparseNode*)mat->hashtable[idx];
            break;
        }

    iterator->curidx = idx;

    __END__;

    return node;
}

#define ICV_SPARSE_MAT_HASH_MULTIPLIER  33

static uchar*
icvGetNodePtr( CvSparseMat* mat, const int* idx, int* _type,
               int create_node, unsigned* precalc_hashval )
{
    uchar* ptr = 0;
    
    CV_FUNCNAME( "icvGetNodePtr" );

    __BEGIN__;

    int i, tabidx;
    unsigned hashval = 0;
    CvSparseNode *node;
    assert( CV_IS_SPARSE_MAT( mat ));

    if( !precalc_hashval )
    {
        for( i = 0; i < mat->dims; i++ )
        {
            int t = idx[i];
            if( (unsigned)t >= (unsigned)mat->size[i] )
                CV_ERROR( CV_StsOutOfRange, "One of indices is out of range" );
            hashval = hashval*ICV_SPARSE_MAT_HASH_MULTIPLIER + t;
        }
    }
    else
    {
        hashval = *precalc_hashval;
    }

    tabidx = hashval & (mat->hashsize - 1);
    hashval &= INT_MAX;

    for( node = (CvSparseNode*)mat->hashtable[tabidx];
         node != 0; node = node->next )
    {
        if( node->hashval == hashval )
        {
            int* nodeidx = CV_NODE_IDX(mat,node);
            for( i = 0; i < mat->dims; i++ )
                if( idx[i] != nodeidx[i] )
                    break;
            if( i == mat->dims )
            {
                ptr = (uchar*)CV_NODE_VAL(mat,node);
                break;
            }
        }
    }

    if( !ptr && create_node )
    {
        if( mat->heap->active_count >= mat->hashsize*CV_SPARSE_HASH_RATIO )
        {
            void** newtable;
            int newsize = MAX( mat->hashsize*2, CV_SPARSE_HASH_SIZE0);
            int newrawsize = newsize*sizeof(newtable[0]);
            
            CvSparseMatIterator iterator;
            assert( (newsize & (newsize - 1)) == 0 );

            // resize hash table
            CV_CALL( newtable = (void**)cvAlloc( newrawsize ));
            memset( newtable, 0, newrawsize );

            node = cvInitSparseMatIterator( mat, &iterator );
            while( node )
            {
                CvSparseNode* next = cvGetNextSparseNode( &iterator );
                int newidx = node->hashval & (newsize - 1);
                node->next = (CvSparseNode*)newtable[newidx];
                newtable[newidx] = node;
                node = next;
            }

            cvFree( &mat->hashtable );
            mat->hashtable = newtable;
            mat->hashsize = newsize;
            tabidx = hashval & (newsize - 1);
        }

        node = (CvSparseNode*)cvSetNew( mat->heap );
        node->hashval = hashval;
        node->next = (CvSparseNode*)mat->hashtable[tabidx];
        mat->hashtable[tabidx] = node;
        CV_MEMCPY_INT( CV_NODE_IDX(mat,node), idx, mat->dims );
        ptr = (uchar*)CV_NODE_VAL(mat,node);
        if( create_node > 0 )
            CV_ZERO_CHAR( ptr, CV_ELEM_SIZE(mat->type));
    }

    if( _type )
        *_type = CV_MAT_TYPE(mat->type);

    __END__;

    return ptr;
}


static void
icvDeleteNode( CvSparseMat* mat, const int* idx, unsigned* precalc_hashval )
{
    CV_FUNCNAME( "icvDeleteNode" );

    __BEGIN__;

    int i, tabidx;
    unsigned hashval = 0;
    CvSparseNode *node, *prev = 0;
    assert( CV_IS_SPARSE_MAT( mat ));

    if( !precalc_hashval )
    {
        for( i = 0; i < mat->dims; i++ )
        {
            int t = idx[i];
            if( (unsigned)t >= (unsigned)mat->size[i] )
                CV_ERROR( CV_StsOutOfRange, "One of indices is out of range" );
            hashval = hashval*ICV_SPARSE_MAT_HASH_MULTIPLIER + t;
        }
    }
    else
    {
        hashval = *precalc_hashval;
    }

    tabidx = hashval & (mat->hashsize - 1);
    hashval &= INT_MAX;

    for( node = (CvSparseNode*)mat->hashtable[tabidx];
         node != 0; prev = node, node = node->next )
    {
        if( node->hashval == hashval )
        {
            int* nodeidx = CV_NODE_IDX(mat,node);
            for( i = 0; i < mat->dims; i++ )
                if( idx[i] != nodeidx[i] )
                    break;
            if( i == mat->dims )
                break;
        }
    }

    if( node )
    {
        if( prev )
            prev->next = node->next;
        else
            mat->hashtable[tabidx] = node->next;
        cvSetRemoveByPtr( mat->heap, node );
    }

    __END__;
}



/****************************************************************************************\
*                          Common for multiple array types operations                    *
\****************************************************************************************/

// Allocates underlying array data
CV_IMPL void
cvCreateData( CvArr* arr )
{
    CV_FUNCNAME( "cvCreateData" );
    
    __BEGIN__;

    if( CV_IS_MAT_HDR( arr ))
    {
        size_t step, total_size;
        CvMat* mat = (CvMat*)arr;
        step = mat->step;

        if( mat->data.ptr != 0 )
            CV_ERROR( CV_StsError, "Data is already allocated" );

        if( step == 0 )
            step = CV_ELEM_SIZE(mat->type)*mat->cols;

        total_size = step*mat->rows + sizeof(int) + CV_MALLOC_ALIGN;
        CV_CALL( mat->refcount = (int*)cvAlloc( (size_t)total_size ));
        mat->data.ptr = (uchar*)cvAlignPtr( mat->refcount + 1, CV_MALLOC_ALIGN );
        *mat->refcount = 1;
    }
    else if( CV_IS_IMAGE_HDR(arr))
    {
        IplImage* img = (IplImage*)arr;

        if( img->imageData != 0 )
            CV_ERROR( CV_StsError, "Data is already allocated" );

        if( !CvIPL.allocateData )
        {
            CV_CALL( img->imageData = img->imageDataOrigin = 
                        (char*)cvAlloc( (size_t)img->imageSize ));
        }
        else
        {
            int depth = img->depth;
            int width = img->width;

            if( img->depth == IPL_DEPTH_32F || img->nChannels == 64 )
            {
                img->width *= img->depth == IPL_DEPTH_32F ? sizeof(float) : sizeof(double);
                img->depth = IPL_DEPTH_8U;
            }

            CvIPL.allocateData( img, 0, 0 );

            img->width = width;
            img->depth = depth;
        }
    }
    else if( CV_IS_MATND_HDR( arr ))
    {
        CvMatND* mat = (CvMatND*)arr;
        int i;
        size_t total_size = CV_ELEM_SIZE(mat->type);

        if( mat->data.ptr != 0 )
            CV_ERROR( CV_StsError, "Data is already allocated" );

        if( CV_IS_MAT_CONT( mat->type ))
        {
            total_size = (size_t)mat->dim[0].size*(mat->dim[0].step != 0 ?
                         mat->dim[0].step : total_size);
        }
        else
        {
            for( i = mat->dims - 1; i >= 0; i-- )
            {
                size_t size = (size_t)mat->dim[i].step*mat->dim[i].size;

                if( total_size < size )
                    total_size = size;
            }
        }
        
        CV_CALL( mat->refcount = (int*)cvAlloc( total_size +
                                        sizeof(int) + CV_MALLOC_ALIGN ));
        mat->data.ptr = (uchar*)cvAlignPtr( mat->refcount + 1, CV_MALLOC_ALIGN );
        *mat->refcount = 1;