1 2 /*+-----------------------------------------------------------------** 3 ** OpenScop Library ** 4 **-----------------------------------------------------------------** 5 ** vector.c ** 6 **-----------------------------------------------------------------** 7 ** First version: 30/04/2008 ** 8 **-----------------------------------------------------------------** 9 10 11 ***************************************************************************** 12 * OpenScop: Structures and formats for polyhedral tools to talk together * 13 ***************************************************************************** 14 * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * 15 * / / / // // // // / / / // // / / // / /|,_, * 16 * / / / // // // // / / / // // / / // / / / /\ * 17 * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * 18 * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * 19 * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * 20 * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * 21 * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * 22 * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * 23 * | I | | | | e | | | | | | | | | | | | | \ \ \ * 24 * | T | | | | | | | | | | | | | | | | | \ \ \ * 25 * | E | | | | | | | | | | | | | | | | | \ \ \ * 26 * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * 27 * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * 28 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * 29 * * 30 * Copyright (C) 2008 University Paris-Sud 11 and INRIA * 31 * * 32 * (3-clause BSD license) * 33 * Redistribution and use in source and binary forms, with or without * 34 * modification, are permitted provided that the following conditions * 35 * are met: * 36 * * 37 * 1. Redistributions of source code must retain the above copyright notice, * 38 * this list of conditions and the following disclaimer. * 39 * 2. Redistributions in binary form must reproduce the above copyright * 40 * notice, this list of conditions and the following disclaimer in the * 41 * documentation and/or other materials provided with the distribution. * 42 * 3. The name of the author may not be used to endorse or promote products * 43 * derived from this software without specific prior written permission. * 44 * * 45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * 46 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * 47 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * 48 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * 49 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * 50 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * 51 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * 52 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * 53 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * 54 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * 55 * * 56 * OpenScop Library, a library to manipulate OpenScop formats and data * 57 * structures. Written by: * 58 * Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and * 59 * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> * 60 * * 61 *****************************************************************************/ 62 63 64#include <stdlib.h> 65#include <stdio.h> 66#include <ctype.h> 67 68#include <osl/macros.h> 69#include <osl/util.h> 70#include <osl/int.h> 71#include <osl/vector.h> 72 73 74/*+*************************************************************************** 75 * Structure display function * 76 *****************************************************************************/ 77 78 79/** 80 * osl_vector_idump function: 81 * Displays a osl_vector_t structure (*vector) into a file (file, possibly 82 * stdout) in a way that trends to be understandable without falling in a deep 83 * depression or, for the lucky ones, getting a headache... It includes an 84 * indentation level (level) in order to work with others idump functions. 85 * \param[in] file File where informations are printed. 86 * \param[in] vector The vector whose information have to be printed. 87 * \param[in] level Number of spaces before printing, for each line. 88 */ 89void osl_vector_idump(FILE * file, osl_vector_p vector, int level) { 90 int j; 91 92 if (vector != NULL) { 93 // Go to the right level. 94 for (j = 0; j < level; j++) 95 fprintf(file,"|\t"); 96 fprintf(file,"+-- osl_vector_t ("); 97 osl_int_dump_precision(file, vector->precision); 98 fprintf(file, ")\n"); 99 100 for (j = 0; j <= level; j++) 101 fprintf(file,"|\t"); 102 fprintf(file,"%d\n", vector->size); 103 104 // Display the vector. 105 for (j = 0; j <= level; j++) 106 fprintf(file, "|\t"); 107 108 fprintf(file, "[ "); 109 110 for (j = 0; j < vector->size; j++) { 111 osl_int_print(file, vector->precision, vector->v, j); 112 fprintf(file, " "); 113 } 114 115 fprintf(file, "]\n"); 116 } 117 else { 118 // Go to the right level. 119 for (j = 0; j < level; j++) 120 fprintf(file, "|\t"); 121 fprintf(file, "+-- NULL vector\n"); 122 } 123 124 // The last line. 125 for (j = 0; j <= level; j++) 126 fprintf(file, "|\t"); 127 fprintf(file, "\n"); 128} 129 130 131/** 132 * osl_vector_dump function: 133 * This function prints the content of a osl_vector_t structure 134 * (*vector) into a file (file, possibly stdout). 135 * \param[in] file File where informations are printed. 136 * \param[in] vector The vector whose information have to be printed. 137 */ 138void osl_vector_dump(FILE * file, osl_vector_p vector) { 139 osl_vector_idump(file, vector, 0); 140} 141 142 143/*+*************************************************************************** 144 * Memory allocation/deallocation function * 145 *****************************************************************************/ 146 147 148/** 149 * osl_vector_pmalloc function: 150 * (precision malloc) this function allocates the memory space for an 151 * osl_vector_t structure and sets its fields with default values. Then 152 * it returns a pointer to the allocated space. 153 * \param[in] precision The precision of the vector entries. 154 * \param[in] size The number of entries of the vector to allocate. 155 * \return A pointer to the newly allocated osl_vector_t structure. 156 */ 157osl_vector_p osl_vector_pmalloc(int precision, int size) { 158 osl_vector_p vector; 159 int i; 160 161 OSL_malloc(vector, osl_vector_p, sizeof(osl_vector_t)); 162 vector->size = size; 163 vector->precision = precision; 164 if (size == 0) { 165 vector->v = NULL; 166 } 167 else { 168 OSL_malloc(vector->v, void *, size * osl_int_sizeof(precision)); 169 for (i = 0; i < size; i++) 170 osl_int_init_set_si(precision, vector->v, i, 0); 171 } 172 return vector; 173} 174 175 176/** 177 * osl_vector_malloc function: 178 * This function allocates the memory space for a osl_vector_t structure 179 * and sets its fields with default values. Then it returns a pointer to the 180 * allocated space. The precision of the vector elements corresponds to the 181 * precision environment variable or to the highest available precision if it 182 * is not defined. 183 * \param[in] size The number of entries of the vector to allocate. 184 * \return A pointer to the newly allocated osl_vector_t structure. 185 */ 186osl_vector_p osl_vector_malloc(int size) { 187 int precision = osl_util_get_precision(); 188 return osl_vector_pmalloc(precision, size); 189} 190 191 192/** 193 * osl_vector_free function: 194 * This function frees the allocated memory for a osl_vector_t structure. 195 * \param[in] vector The pointer to the vector we want to free. 196 */ 197void osl_vector_free(osl_vector_p vector) { 198 int i; 199 200 if (vector != NULL) { 201 if (vector->v != NULL) { 202 for (i = 0; i < vector->size; i++) 203 osl_int_clear(vector->precision, vector->v, i); 204 205 free(vector->v); 206 } 207 free(vector); 208 } 209} 210 211 212/*+*************************************************************************** 213 * Processing functions * 214 *****************************************************************************/ 215 216 217/** 218 * osl_vector_add_scalar function: 219 * This function adds a scalar to the vector representation of an affine 220 * expression (this means we add the scalar only to the very last entry of the 221 * vector). It returns a new vector resulting from this addition. 222 * \param[in] vector The basis vector. 223 * \param[in] scalar The scalar to add to the vector. 224 * \return A pointer to a new vector, copy of the basis one plus the scalar. 225 */ 226osl_vector_p osl_vector_add_scalar(osl_vector_p vector, int scalar) { 227 int i, precision, last; 228 osl_vector_p result; 229 230 if ((vector == NULL) || (vector->size < 2)) 231 OSL_error("incompatible vector for addition"); 232 233 precision = vector->precision; 234 last = vector->size - 1; 235 236 result = osl_vector_pmalloc(precision, vector->size); 237 for (i = 0; i < vector->size; i++) 238 osl_int_assign(precision, result->v, i, vector->v, i); 239 osl_int_add_si(precision, result->v, last, vector->v, last, scalar); 240 241 return result; 242} 243 244 245/** 246 * osl_vector_add function: 247 * This function achieves the addition of two vectors and returns the 248 * result as a new vector (the addition means the ith entry of the new vector 249 * is equal to the ith entry of vector v1 plus the ith entry of vector v2). 250 * \param v1 The first vector for the addition. 251 * \param v2 The second vector for the addition. 252 * \return A pointer to a new vector, corresponding to v1 + v2. 253 */ 254osl_vector_p osl_vector_add(osl_vector_p v1, osl_vector_p v2) { 255 int i; 256 osl_vector_p v3; 257 258 if ((v1 == NULL) || (v2 == NULL) || 259 (v1->size != v2->size) || (v1->precision != v2->precision)) 260 OSL_error("incompatible vectors for addition"); 261 262 v3 = osl_vector_pmalloc(v1->precision, v1->size); 263 for (i = 0; i < v1->size; i++) 264 osl_int_add(v1->precision, v3->v, i, v1->v, i, v2->v, i); 265 266 return v3; 267} 268 269 270/** 271 * osl_vector_sub function: 272 * This function achieves the subtraction of two vectors and returns the 273 * result as a new vector (the addition means the ith entry of the new vector 274 * is equal to the ith entry of vector v1 minus the ith entry of vector v2). 275 * \param v1 The first vector for the subtraction. 276 * \param v2 The second vector for the subtraction (result is v1-v2). 277 * \return A pointer to a new vector, corresponding to v1 - v2. 278 */ 279osl_vector_p osl_vector_sub(osl_vector_p v1, osl_vector_p v2) { 280 int i; 281 osl_vector_p v3; 282 283 if ((v1 == NULL) || (v2 == NULL) || 284 (v1->size != v2->size) || (v1->precision != v2->precision)) 285 OSL_error("incompatible vectors for subtraction"); 286 287 v3 = osl_vector_pmalloc(v1->precision, v1->size); 288 for (i = 0; i < v1->size; i++) 289 osl_int_sub(v1->precision, v3->v, i, v1->v, i, v2->v, i); 290 291 return v3; 292} 293 294 295/** 296 * osl_vector_tag_inequality function: 297 * This function tags a vector representation of a contraint as being an 298 * inequality >=0. This means in the PolyLib format, to set to 1 the very 299 * first entry of the vector. It modifies directly the vector provided as 300 * an argument. 301 * \param vector The vector to be tagged. 302 */ 303void osl_vector_tag_inequality(osl_vector_p vector) { 304 if ((vector == NULL) || (vector->size < 1)) 305 OSL_error("vector cannot be tagged"); 306 osl_int_set_si(vector->precision, vector->v, 0, 1); 307} 308 309 310/** 311 * osl_vector_tag_equality function: 312 * This function tags a vector representation of a contraint as being an 313 * equality ==0. This means in the PolyLib format, to set to 0 the very 314 * first entry of the vector. It modifies directly the vector provided as 315 * an argument. 316 * \param vector The vector to be tagged. 317 */ 318void osl_vector_tag_equality(osl_vector_p vector) { 319 if ((vector == NULL) || (vector->size < 1)) 320 OSL_error("vector cannot be tagged"); 321 osl_int_set_si(vector->precision, vector->v, 0, 0); 322} 323 324 325/** 326 * osl_vector_equal function: 327 * this function returns true if the two vectors are the same, false 328 * otherwise. 329 * \param v1 The first vector. 330 * \param v2 The second vector. 331 * \return 1 if v1 and v2 are the same (content-wise), 0 otherwise. 332 */ 333int osl_vector_equal(osl_vector_p v1, osl_vector_p v2) { 334 int i; 335 336 if (v1 == v2) 337 return 1; 338 339 if ((v1->size != v2->size) || (v1->precision != v2->precision)) 340 return 0; 341 342 for (i = 0; i < v1->size; i++) 343 if (osl_int_ne(v1->precision, v1->v, i, v2->v, i)) 344 return 0; 345 346 return 1; 347} 348 349 350/** 351 * osl_vector_mul_scalar function: 352 * this function returns a new vector corresponding to the one provided 353 * as parameter with each entry multiplied by a scalar. 354 * \param v The vector to multiply. 355 * \param scalar The scalar coefficient. 356 * \return A new vector corresponding to scalar * v. 357 */ 358osl_vector_p osl_vector_mul_scalar(osl_vector_p v, int scalar) { 359 int i; 360 osl_vector_p result = osl_vector_pmalloc(v->precision, v->size); 361 362 for (i = 0; i < v->size; i++) 363 osl_int_mul_si(v->precision, result->v, i, v->v, i, scalar); 364 365 return result; 366} 367 368 369/** 370 * osl_vector_is_scalar function: 371 * this function returns 1 if the vector represents a scalar value 372 * (all but its last element is 0), 0 otherwise. 373 * \param[in] vector The vector to check whether it is scalar or not. 374 * \return 1 if the vector is scalar, 0 otherwise. 375 */ 376int osl_vector_is_scalar(osl_vector_p vector) { 377 int i; 378 379 if (vector == NULL) 380 return 0; 381 382 for (i = 0; i < vector->size - 1; i++) 383 if (!osl_int_zero(vector->precision, vector->v, i)) 384 return 0; 385 return 1; 386} 387 388