1 /* 2 3 Copyright (C) 2008-2020 Michele Martone 4 5 This file is part of librsb. 6 7 librsb is free software; you can redistribute it and/or modify it 8 under the terms of the GNU Lesser General Public License as published 9 by the Free Software Foundation; either version 3 of the License, or 10 (at your option) any later version. 11 12 librsb is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15 License for more details. 16 17 You should have received a copy of the GNU Lesser General Public 18 License along with librsb; see the file COPYING. 19 If not, see <http://www.gnu.org/licenses/>. 20 21 */ 22 #ifndef RSB_RSB_STRUCT_H_INCLUDED 23 #define RSB_RSB_STRUCT_H_INCLUDED 24 25 /* @cond INNERDOC */ 26 27 /*! 28 * A type for the size (in bytes) of memory areas. */ 29 typedef size_t rsb_size_t; 30 31 /*! 32 * A typedef for printing non negative integers. 33 */ 34 typedef rsb_size_t rsb_printf_int_t; 35 36 /*! 37 * The inner datatype used for the bitmap structure. 38 * */ 39 typedef signed int rsb_bitmap_data_t; 40 41 /*! A type for specifying a sparse matrix format. */ 42 typedef rsb_flags_t rsb_fmt_t; 43 44 /*! A floating point numerical type for performance (MFLOPS) measurements. */ 45 typedef rsb_real_t rsb_perf_t; 46 47 /*! A floating point numerical type for fillin measurements (obsolete). */ 48 typedef rsb_real_t rsb_fillin_t; 49 50 /*! 51 An integer type for submatrix indices. 52 */ 53 typedef int rsb_submatrix_idx_t; 54 55 #define RSB_MAX_SUBM_COUNT (RSB_MAX_VALUE_FOR_TYPE(rsb_submatrix_idx_t)) 56 #define RSB_SUBM_IDX_MARKER (RSB_MAX_SUBM_COUNT) 57 58 /*! 59 \internal 60 An integer type which by definition should not overflow, in most cases of interest. 61 */ 62 typedef int rsb_non_overflowing_t; 63 64 65 #define RSB_BLK_MUL_OVERFLOW(R,C) RSB_MUL_OVERFLOW((R),(C),rsb_blk_idx_t,rsb_non_overflowing_t) 66 #define RSB_COO_MUL_OVERFLOW(R,C) RSB_MUL_OVERFLOW((R),(C),rsb_coo_idx_t,rsb_non_overflowing_t) 67 #define RSB_NNZ_MUL_OVERFLOW(R,C) RSB_MUL_OVERFLOW(R,C,rsb_nnz_idx_t,rsb_non_overflowing_t) 68 69 /*! 70 A type for byte strings. 71 */ 72 typedef unsigned char rsb_byte_t; 73 74 75 /* @cond INNERDOC */ 76 /*! 77 \name Macros for overflow detection in common (INTERNALS) operations. 78 79 They are tricky because should serve both signed and unsigned typedefs. 80 The following macros should be handled with care. 81 */ 82 #define RSB_INDEX_OF_SAFE_EXTRA 2 /*< this is the value that could be added with no overflow to indices values */ 83 #define RSB_ADD_OVERFLOW(R,C,T) ((int)((T)(((T)(R))+((T)(C)))<((T)(R))) || (int)((T)(((T)(R))+((T)(C)))<((T)(C)))) 84 #define RSB_MUL_OVERFLOW(R,C,T,H) ( ( R > C && RSB_MAX_VALUE_FOR_TYPE(T) / C < R ) || (RSB_MAX_VALUE_FOR_TYPE(T) / R < C ) ) 85 #define RSB_BLK_ADD_OVERFLOW(R,C) RSB_ADD_OVERFLOW((R),(C),rsb_blk_idx_t) 86 #define RSB_COO_ADD_OVERFLOW(R,C) RSB_ADD_OVERFLOW((R),(C),rsb_coo_idx_t) 87 #define RSB_NNZ_ADD_OVERFLOW(R,C) RSB_ADD_OVERFLOW((R),(C),rsb_nnz_idx_t) 88 89 /*! 90 Macros to get indices types liminal values (which we often use as markers). 91 */ 92 #define RSB_IS_UNSIGNED(T) (!RSB_IS_SIGNED(T)) 93 #define RSB_PROBABLY_SAME_TYPES(T1,T2) ((RSB_IS_SIGNED(T1)==RSB_IS_SIGNED(T2)) && sizeof(T1)==sizeof(T2)) 94 #define RSB_MIN_SIGNED(T) (-1 - RSB_MAX_SIGNED(T)) 95 96 #define RSB_IS_VALUE_MORE_THAN_HALF_BITS_LONG(V,T) (((V)>>RSB_COO_HALF_BITS_SIZE)>0) /*< */ 97 #define RSB_IS_COO_VALUE_MORE_THAN_HALF_BITS_LONG(V) RSB_IS_VALUE_MORE_THAN_HALF_BITS_LONG(V,rsb_coo_idx_t) /*< */ 98 99 #define RSB_MIN(X,Y) ((X)<(Y)?(X):(Y)) /*!< quick macro for minimum */ 100 #define RSB_MAX(X,Y) ((X)<(Y)?(Y):(X)) /*!< quick macro for maximum */ 101 #define RSB_ABS(X) ((X)<0?-(X):(X)) /*!< quick macro for abs()*/ 102 103 #define RSB_FOUR 4 /*!< a constant with the number of quadrants */ 104 /* @endcond */ 105 106 /* @cond INNERDOC */ 107 #define RSB_REAL_ZERO 0.0 /*!< \internal internal */ 108 #define RSB_TIME_ZERO RSB_REAL_ZERO /*!< \internal internal */ 109 #define RSB_BOOL_MAYBE (-1) /*!< a reserved, "maybe" value for rsb_bool_t */ 110 #define RSB_INVALID_FLAGS (-1) /*!< \internal internal */ 111 #define RSB_INVALID_TRANS RSB_INVALID_FLAGS /*!< \internal internal */ 112 #define RSB_XOR(X,Y) (((X)!=0)^ ((Y)!=0)) /*!< \internal internal */ 113 #define RSB_AND(X,Y) (((X)!=0)&&((Y)!=0)) /*!< \internal internal */ 114 #define RSB_OR(X,Y) (((X)!=0)||((Y)!=0)) /*!< \internal internal */ 115 #define RSB_NAND(X,Y) (!RSB_AND(X,Y)) /*!< \internal internal */ 116 /* @endcond */ 117 118 /* @cond INNERDOC */ 119 #define RSB_BOOL_XOR(X,Y) ((X)^(Y)) /*!< A logical XOR for rsb_bool_t values. */ 120 #define RSB_BOOL_OR(X,Y) ((X)||(Y)) /*!< A logical OR for rsb_bool_t values. */ 121 #define RSB_BOOL_AND(X,Y) ((X)&&(Y)) /*!< A logical OR for rsb_bool_t values. */ 122 #define RSB_BOOL_NOT(X) (!(X)) /*!< A logical NOT for rsb_bool_t values. */ 123 #define RSB_BOOL_NAND(X,Y) RSB_BOOL_NOT(RSB_BOOL_AND(X,Y)) /*!< A logical NAND for rsb_bool_t values. */ 124 #define RSB_BOOL_NOR(X,Y) RSB_BOOL_NOT(RSB_BOOL_OR(X,Y)) /*!< A logical NOR for rsb_bool_t values. */ 125 /* @endcond */ 126 127 128 129 /* @cond INNERDOC */ 130 /*! 131 * \internal 132 * \ingroup gr_internals 133 * \brief An internal, helper structure (OBSOLETE). 134 * \internal 135 */ 136 struct rsb_expected_info_t{ 137 /*! Expected fillin */ 138 /* FIXME : here should also be a map of expected fillin */ 139 rsb_fillin_t efillin; 140 }; 141 /* @endcond */ 142 143 /* @cond INNERDOC */ 144 /*! 145 * \internal 146 * \ingroup gr_internals 147 * \brief An internal, helper structure (not for end users). 148 * \internal 149 */ 150 struct rsb_translated_matrix_t 151 { 152 struct rsb_mtx_t * mtxlp; 153 rsb_submatrix_idx_t level; 154 rsb_coo_idx_t roff,coff; 155 rsb_coo_idx_t nr,nc; 156 }; 157 /* @endcond */ 158 159 /*! 160 * \ingroup rsb_doc_matrix_assembly 161 * \brief A structure for the RSB (Recursive Sparse Blocks) representation of sparse matrices. 162 * \n 163 * This is an opaque container for a recursive storage of COO/CSR submatrices. 164 * \n 165 * The user is not supposed to manipulate this structure directly. 166 * \n 167 * This structure shall be only manipulated through the use of appropriate functions. 168 * \n 169 * Knowledge of this structure is not required at all (in any case) use the library. 170 * \see rsb_doc_matrix_assembly on how to instantiate/destroy this structure. 171 * \see rsb_doc_matrix_operations for computational operations using it. 172 * 173 * \note: VBR and BCSR submatrices are not supported. 174 */ 175 struct rsb_mtx_t 176 { 177 /*! 178 values of matrix coefficients. 179 array sized ( element_count == nnz * fillin ) * el_size (CSR,BCSR,VBR) 180 */ 181 void * VA; 182 183 /*! bpntr[bri] points to the location of bindx of the first nonzero block entry of block row bri. 184 if the ith block row contains only zeros then bpntr[i]==bpntr[i+1] (VBR,BCSR,CSR) */ 185 rsb_nnz_idx_t *bpntr; 186 187 /*! bindx[bi] contains the block column index of the bi^th nonzero block (VBR,BCSR,CSR) */ 188 rsb_coo_idx_t *bindx; /* bindx[m->block_count] should be zero, for technical reasons (for the last 'virtual' block) */ 189 190 rsb_nnz_idx_t nnz; /*! matrix rows, columns */ 191 rsb_coo_idx_t nr,nc; /*! matrix (declared) nonzeros */ 192 rsb_flags_t flags; /*! structural flags, describing some optional features */ 193 rsb_blk_idx_t br, bc; /*! block row and column size (only if BCSR) */ 194 rsb_type_t typecode; /*! as specified in the RSB_NUMERICAL_TYPE_* preprocessor symbols in types.h (See \ref matrix_type_symbols_section) */ 195 rsb_fmt_t matrix_storage; /*! as specified in the RSB_MATRIX_STORAGE_* preprocessor symbols in types.h */ 196 197 /*! 198 intptr[bi] points (logically: in terms of numerical elements count) to the location in VA of the (0,0) entry in the bi^th block entry (VBR). 199 array sized 200 */ 201 rsb_nnz_idx_t *indptr; 202 203 /*! rpntr[bri] contains the row index of first row in the bri^th block row 204 ( row partitioning indices : M_b +1 elements ) (CSR,BCSR,VBR) 205 note that rpntr[Mdim] could be more than m. 206 */ 207 rsb_coo_idx_t *rpntr; 208 209 /*! cpntr[bcj] contains the column index of the first column in the bcj^th block column 210 ( column partitioning indices : K_b +1 elements ) (VBR) */ 211 rsb_coo_idx_t *cpntr; 212 213 /*! these are aliases for rpntr and cpntr for the major dimension (Mpntr) and minor one (mpntr) 214 */ 215 rsb_coo_idx_t *mpntr,*Mpntr; 216 217 /* int *mpntr,*Mpntr;*/ /* aliases for rpntr and cpntr (M stays for major, m for minor) */ 218 219 /*! block row and column counts */ 220 rsb_blk_idx_t M_b, K_b; 221 222 /*! these are aliases for M_b and K_b for the major dimension (Mdim) and minor one (mdim) 223 * ifdef RSB_FLAG_WANT_COLUMN_MAJOR_ORDER, the aliasing is swapped. 224 * */ 225 rsb_blk_idx_t Mdim,mdim; 226 227 /*! The count of blocks (regardless their size) : <= nnz */ 228 rsb_nnz_idx_t block_count; 229 230 /*! The overall number of elements el_size bytes each (>=nnz) */ 231 rsb_size_t element_count; 232 233 /*! the size >= 1, in bytes, of the sparse matrix numerical elements type */ 234 rsb_size_t el_size; 235 236 /*! Time needed for matrix structure analysis, during construction */ 237 rsb_time_t sat; 238 239 /*! Time needed for elements insertion, during construction */ 240 rsb_time_t eit; 241 242 /*! Time needed for sorting elements (if sorted), during construction */ 243 rsb_time_t est; 244 245 /*! Performance estimation time */ 246 rsb_time_t pet; 247 248 /*! Cooordinate cleanup time */ 249 rsb_time_t ect; 250 251 /*! Coordinate partitioning time */ 252 rsb_time_t cpt; 253 254 /*! Recursive sort time */ 255 rsb_time_t rpt; 256 257 /*! Total assembly time */ 258 rsb_time_t tat; 259 260 /*! Submatrix pointers for recursion storage */ 261 struct rsb_mtx_t * sm[RSB_FOUR]; 262 263 /* #if RSB_STORE_IDXSA */ 264 /*! Index storage amount. Temporarily here: FIXME. */ 265 rsb_size_t idxsa; 266 /* 267 #else */ 268 /*! A structure with expectation info during construction (FIXME: this member is obsolete and will be deleted soon) */ 269 /* struct rsb_expected_info_t einfo; */ 270 /* #endif */ 271 272 /*! A pointer to an array of leaf submatrices pointers (only valid on root) */ 273 struct rsb_translated_matrix_t * all_leaf_matrices; 274 275 /*! The number of leaf submatrices pointers in all_leaf_matrices (only valid on root) */ 276 rsb_submatrix_idx_t all_leaf_matrices_n; 277 278 /*! In a recursive representation, the offset of the submatrix with respect to the original one (respectively, rows and columns) */ 279 rsb_coo_idx_t roff,coff; 280 281 /*! In a recursive representation, with the RSB_FLAG_ASSEMBLED_IN_COO_ARRAYS flag, the offset of these data arrays from the beginning of the global ones */ 282 rsb_nnz_idx_t nzoff; 283 284 /*! In a recursive representation, broff (bcoff) is the offset of the submatrix first non empty row (column) with respect to the matrix. */ 285 rsb_coo_idx_t broff,bcoff; 286 287 /*! In a recursive representation, bm (bk) is the last non empty row (column) in the submatrix. */ 288 rsb_coo_idx_t bm,bk; 289 }; 290 291 /*! 292 * Macros for printing out summary info about a matrix. 293 * Accept a valid \ref rsb_mtx_t pointer as an argument. 294 * 295 * Usage example: 296 * \code 297 * printf(RSB_PRINTF_MTX_SUMMARY_ARGS(mtxAp)); 298 * \endcode 299 */ 300 #define RSB_PRINTF_MTX_SUMMARY_ARGS(MTXAP) \ 301 "(%d x %d)[%p]{%c} @ (%d(%d..%d),%d(%d..%d)) (%d nnz, %.2lg nnz/r) flags 0x%x (coo:%d, csr:%d, hw:%d, ic:%d), storage: %x, subm: %d, symflags:'"\ 302 "%s" \ 303 "%s" \ 304 "%s" \ 305 "%s" \ 306 "%s" \ 307 "'" \ 308 , \ 309 (MTXAP)->nr, (MTXAP)->nc, (const void*)(MTXAP), \ 310 (MTXAP)->typecode, \ 311 (MTXAP)->roff, \ 312 (MTXAP)->broff, \ 313 (MTXAP)->roff+(MTXAP)->bm, \ 314 (MTXAP)->coff, \ 315 (MTXAP)->bcoff, \ 316 (MTXAP)->coff+(MTXAP)->bk, \ 317 (MTXAP)->nnz, \ 318 ((double)(MTXAP)->nnz)/(MTXAP)->nr, \ 319 (MTXAP)->flags, \ 320 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_WANT_COO_STORAGE), \ 321 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_WANT_BCSS_STORAGE), \ 322 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_USE_HALFWORD_INDICES), \ 323 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_ASSEMBLED_IN_COO_ARRAYS), \ 324 (MTXAP)->matrix_storage, \ 325 (MTXAP)->all_leaf_matrices_n, \ 326 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_UPPER)?"U":"", \ 327 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_LOWER)?"L":"", \ 328 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_TRIANGULAR)?"T":"", \ 329 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_SYMMETRIC)?"S":"", \ 330 RSB_DO_FLAG_HAS((MTXAP)->flags,RSB_FLAG_HERMITIAN)?"H":"" 331 332 #define RSB_PRINTF_MATRIX_AT_SUMMARY_ARGS(MTXAP) \ 333 "%d x %d, type %c, %d nnz, %.2lg nnz/r, %ld subms, %d lsubms, %2.4lf bpnz"\ 334 , \ 335 (MTXAP)->nr, (MTXAP)->nc, \ 336 (MTXAP)->typecode, \ 337 (MTXAP)->nnz, \ 338 ((double)(MTXAP)->nnz)/(MTXAP)->nr, \ 339 rsb__submatrices(MTXAP), \ 340 (MTXAP)->all_leaf_matrices_n, \ 341 ((double)rsb__get_index_storage_amount(MTXAP)) / ((MTXAP)->nnz) 342 343 #define RSB_PRINTF_MATRIX_BOUNDS_SUMMARY_ARGS(MTXAP) \ 344 "(nr=%d x nc=%d, nnz=%d)[%p]{type=%c} @ (nzoff=%d, roff=%d,broff=%d,bm=%d, coff=%d,bcoff=%d,bk=%d) " \ 345 , \ 346 (MTXAP)->nr, (MTXAP)->nc, (MTXAP)->nnz, (const void*)(MTXAP), \ 347 (MTXAP)->typecode, \ 348 (MTXAP)->nzoff, \ 349 (MTXAP)->roff, \ 350 (MTXAP)->broff, \ 351 (MTXAP)->bm, \ 352 (MTXAP)->coff, \ 353 (MTXAP)->bcoff, \ 354 (MTXAP)->bk 355 /* @endcond */ 356 357 358 #endif 359