4 #include <barvinok/barvinok.h>
14 { BV_APPROX_SIGN_NONE
, BV_APPROX_NONE
, 0 },
15 { BV_APPROX_SIGN_APPROX
, BV_APPROX_BERNOULLI
, 0 },
16 { BV_APPROX_SIGN_APPROX
, BV_APPROX_DROP
, 0 },
17 { BV_APPROX_SIGN_APPROX
, BV_APPROX_VOLUME
, BV_VOL_LIFT
},
18 { BV_APPROX_SIGN_APPROX
, BV_APPROX_VOLUME
, BV_VOL_VERTEX
},
19 { BV_APPROX_SIGN_APPROX
, BV_APPROX_VOLUME
, BV_VOL_BARYCENTER
},
20 { BV_APPROX_SIGN_APPROX
, BV_APPROX_SCALE
, 0 },
21 { BV_APPROX_SIGN_APPROX
, BV_APPROX_SCALE
, BV_APPROX_SCALE_CHAMBER
},
22 { BV_APPROX_SIGN_APPROX
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
},
23 { BV_APPROX_SIGN_APPROX
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_CHAMBER
},
24 { BV_APPROX_SIGN_LOWER
, BV_APPROX_DROP
, 0 },
25 { BV_APPROX_SIGN_LOWER
, BV_APPROX_VOLUME
, BV_VOL_LIFT
},
26 { BV_APPROX_SIGN_LOWER
, BV_APPROX_VOLUME
, BV_VOL_VERTEX
},
27 { BV_APPROX_SIGN_LOWER
, BV_APPROX_VOLUME
, BV_VOL_BARYCENTER
},
28 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, 0 },
29 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_CHAMBER
},
30 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
},
31 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_CHAMBER
},
32 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW
},
33 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW
| BV_APPROX_SCALE_CHAMBER
},
34 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW
},
35 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW
| BV_APPROX_SCALE_CHAMBER
},
36 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW2
},
37 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW2
| BV_APPROX_SCALE_CHAMBER
},
38 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW2
},
39 { BV_APPROX_SIGN_LOWER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW2
| BV_APPROX_SCALE_CHAMBER
},
40 { BV_APPROX_SIGN_UPPER
, BV_APPROX_DROP
, 0 },
41 { BV_APPROX_SIGN_UPPER
, BV_APPROX_VOLUME
, BV_VOL_LIFT
},
42 { BV_APPROX_SIGN_UPPER
, BV_APPROX_VOLUME
, BV_VOL_VERTEX
},
43 { BV_APPROX_SIGN_UPPER
, BV_APPROX_VOLUME
, BV_VOL_BARYCENTER
},
44 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, 0 },
45 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_CHAMBER
},
46 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
},
47 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_CHAMBER
},
48 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW
},
49 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW
| BV_APPROX_SCALE_CHAMBER
},
50 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW
},
51 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW
| BV_APPROX_SCALE_CHAMBER
},
52 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW2
},
53 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_NARROW2
| BV_APPROX_SCALE_CHAMBER
},
54 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW2
},
55 { BV_APPROX_SIGN_UPPER
, BV_APPROX_SCALE
, BV_APPROX_SCALE_FAST
| BV_APPROX_SCALE_NARROW2
| BV_APPROX_SCALE_CHAMBER
},
58 #define nr_methods (sizeof(methods)/sizeof(*methods))
60 struct argp_option argp_options
[] = {
67 struct verify_options verify
;
70 static error_t
parse_opt(int key
, char *arg
, struct argp_state
*state
)
72 struct options
*options
= (struct options
*) state
->input
;
76 state
->child_inputs
[0] = options
->verify
.barvinok
;
77 state
->child_inputs
[1] = &options
->verify
;
84 return ARGP_ERR_UNKNOWN
;
91 double RE_sum
[nr_methods
];
93 clock_t ticks
[nr_methods
];
94 size_t size
[nr_methods
];
97 void result_data_init(struct result_data
*result
)
100 for (i
= 0; i
< nr_methods
; ++i
) {
101 result
->RE_sum
[i
] = 0;
102 result
->ticks
[i
] = 0;
105 value_init(result
->n
);
108 void result_data_clear(struct result_data
*result
)
111 value_clear(result
->n
);
114 void result_data_print(struct result_data
*result
, int n
)
118 fprintf(stderr
, "%d", result
->ticks
[0]/n
);
119 for (i
= 1; i
< nr_methods
; ++i
)
120 fprintf(stderr
, ", %d", result
->ticks
[i
]/n
);
121 fprintf(stderr
, "\n");
123 fprintf(stderr
, "%d", result
->size
[0]/n
);
124 for (i
= 1; i
< nr_methods
; ++i
)
125 fprintf(stderr
, ", %d", result
->size
[i
]/n
);
126 fprintf(stderr
, "\n");
128 fprintf(stderr
, "%g\n", VALUE_TO_DOUBLE(result
->n
));
129 fprintf(stderr
, "%g", result
->RE_sum
[0]/VALUE_TO_DOUBLE(result
->n
));
130 for (i
= 1; i
< nr_methods
; ++i
)
131 fprintf(stderr
, ", %g", result
->RE_sum
[i
]/VALUE_TO_DOUBLE(result
->n
));
132 fprintf(stderr
, "\n");
135 struct test_approx_data
{
136 struct check_poly_data cp
;
138 struct result_data
*result
;
141 static void eval(const evalue
*EP
, Value
*z
, int sign
, Value
*v
)
145 res
= evalue_eval(EP
, z
);
146 if (sign
== BV_APPROX_SIGN_LOWER
)
147 mpz_cdiv_q(*v
, res
->x
.n
, res
->d
);
148 else if (sign
== BV_APPROX_SIGN_UPPER
)
149 mpz_fdiv_q(*v
, res
->x
.n
, res
->d
);
150 else if (sign
== BV_APPROX_SIGN_APPROX
)
151 mpz_tdiv_q(*v
, res
->x
.n
, res
->d
);
153 assert(value_one_p(res
->d
));
154 value_assign(*v
, res
->x
.n
);
156 free_evalue_refs(res
);
160 static int test_approx(const struct check_poly_data
*data
, int nparam
, Value
*z
,
161 const struct verify_options
*options
)
163 struct test_approx_data
* ta_data
= (struct test_approx_data
*) data
;
170 eval(ta_data
->EP
[0], z
, BV_APPROX_SIGN_NONE
, &exact
);
173 value_print(stderr, VALUE_FMT, exact);
176 value_increment(ta_data
->result
->n
, ta_data
->result
->n
);
177 for (i
= 1; i
< nr_methods
; ++i
) {
179 eval(ta_data
->EP
[i
], z
, methods
[i
].sign
, &approx
);
181 fprintf(stderr, ", ");
182 value_print(stderr, VALUE_FMT, approx);
184 if (methods
[i
].sign
== BV_APPROX_SIGN_LOWER
)
185 assert(value_le(approx
, exact
));
186 if (methods
[i
].sign
== BV_APPROX_SIGN_UPPER
)
187 assert(value_ge(approx
, exact
));
188 value_subtract(approx
, approx
, exact
);
189 if (value_zero_p(exact
))
190 error
= abs(VALUE_TO_DOUBLE(approx
));
192 error
= abs(VALUE_TO_DOUBLE(approx
)) / VALUE_TO_DOUBLE(exact
);
193 ta_data
->result
->RE_sum
[i
] += error
;
197 fprintf(stderr, "\n");
205 static void test(Polyhedron
*P
, Polyhedron
*C
, evalue
**EP
,
206 struct result_data
*result
,
207 struct verify_options
*options
)
211 unsigned nparam
= C
->Dimension
;
212 struct test_approx_data data
;
214 CS
= check_poly_context_scan(P
, &C
, C
->Dimension
, options
);
216 p
= Vector_Alloc(P
->Dimension
+2);
217 value_set_si(p
->p
[P
->Dimension
+1], 1);
219 check_poly_init(C
, options
);
222 data
.cp
.check
= test_approx
;
224 data
.result
= result
;
225 check_poly(CS
, &data
.cp
, nparam
, 0, p
->p
+P
->Dimension
-nparam
+1,
227 if (!options
->print_all
)
237 void Matrix_File_Read_Input(FILE *in
, Matrix
*Mat
)
241 char *c
, s
[1024],str
[1024];
244 for (i
=0;i
<Mat
->NbRows
;i
++) {
246 c
= fgets(s
, 1024, in
);
247 while(isspace(*c
) && *c
!='\n')
249 } while(c
&& (*c
=='#' || *c
== '\n'));
252 errormsg1( "Matrix_Read", "baddim", "not enough rows" );
255 for (j
=0;j
<Mat
->NbColumns
;j
++) {
256 if(!c
|| *c
=='\n' || *c
=='#') {
257 errormsg1("Matrix_Read", "baddim", "not enough columns");
260 if (sscanf(c
,"%s%n",str
,&n
) == 0) {
261 errormsg1( "Matrix_Read", "baddim", "not enough columns" );
264 value_read(*(p
++),str
);
268 } /* Matrix_Read_Input */
271 * Read the contents of the matrix 'Mat' from standard input.
272 * A '#' in the first column is a comment line
274 Matrix
*Matrix_File_Read(FILE *in
)
277 unsigned NbRows
, NbColumns
;
281 while ((*s
=='#' || *s
=='\n') ||
282 (sscanf(s
, "%d %d", &NbRows
, &NbColumns
)<2))
284 Mat
= Matrix_Alloc(NbRows
,NbColumns
);
286 errormsg1("Matrix_Read", "outofmem", "out of memory space");
289 Matrix_File_Read_Input(in
, Mat
);
293 void handle(FILE *in
, struct result_data
*result
, struct verify_options
*options
)
299 evalue
*EP
[nr_methods
];
301 M
= Matrix_File_Read(in
);
302 A
= Constraints2Polyhedron(M
, options
->barvinok
->MaxRays
);
304 M
= Matrix_File_Read(in
);
305 C
= Constraints2Polyhedron(M
, options
->barvinok
->MaxRays
);
307 param_name
= Read_ParamNames(in
, C
->Dimension
);
309 for (i
= 0; i
< nr_methods
; ++i
) {
312 options
->barvinok
->polynomial_approximation
= methods
[i
].sign
;
313 options
->barvinok
->approximation_method
= methods
[i
].method
;
314 if (methods
[i
].method
== BV_APPROX_SCALE
)
315 options
->barvinok
->scale_flags
= methods
[i
].flags
;
316 else if (methods
[i
].method
== BV_APPROX_VOLUME
)
317 options
->barvinok
->volume_triangulate
= methods
[i
].flags
;
320 EP
[i
] = barvinok_enumerate_with_options(A
, C
, options
->barvinok
);
322 result
->ticks
[i
] = en_cpu
.tms_utime
- st_cpu
.tms_utime
;
324 print_evalue(stdout, EP[i], param_name);
327 for (i
= 0; i
< nr_methods
; ++i
)
328 result
->size
[i
] = evalue_size(EP
[i
])/4;
329 test(A
, C
, EP
, result
, options
);
330 for (i
= 0; i
< nr_methods
; ++i
) {
331 free_evalue_refs(EP
[i
]);
335 Free_ParamNames(param_name
, C
->Dimension
);
340 int main(int argc
, char **argv
)
342 struct barvinok_options
*bv_options
= barvinok_options_new_with_defaults();
343 char path
[PATH_MAX
+1];
344 struct result_data all_result
;
346 static struct argp_child argp_children
[] = {
347 { &barvinok_argp
, 0, 0, 0 },
348 { &verify_argp
, 0, "verification", BV_GRP_LAST
+1 },
351 static struct argp argp
= { argp_options
, parse_opt
, 0, 0, argp_children
};
352 struct options options
;
354 options
.verify
.barvinok
= bv_options
;
355 set_program_name(argv
[0]);
356 argp_parse(&argp
, argc
, argv
, 0, 0, &options
);
358 if (options
.verify
.M
== INT_MIN
)
359 options
.verify
.M
= 100;
360 if (options
.verify
.m
== INT_MAX
)
361 options
.verify
.m
= -100;
363 result_data_init(&all_result
);
365 while (fgets(path
, sizeof(path
), stdin
)) {
366 struct result_data result
;
371 result_data_init(&result
);
372 fprintf(stderr
, "%s", path
);
373 *strchr(path
, '\n') = '\0';
374 in
= fopen(path
, "r");
376 handle(in
, &result
, &options
.verify
);
380 result_data_print(&result
, 1);
382 value_addto(all_result
.n
, all_result
.n
, result
.n
);
383 for (i
= 0; i
< nr_methods
; ++i
) {
384 all_result
.RE_sum
[i
] += result
.RE_sum
[i
];
385 all_result
.ticks
[i
] += result
.ticks
[i
];
386 all_result
.size
[i
] += result
.size
[i
];
389 result_data_clear(&result
);
391 if (!options
.quiet
) {
392 fprintf(stderr
, "average\n");
393 result_data_print(&all_result
, n
);
397 result_data_clear(&all_result
);
399 barvinok_options_free(bv_options
);