test/interpolation.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4
   5 /* gcc interpolation.c -o interpolation */
   6
   7 void
   8 err(int eval, const char *fmt, ...)
   9 {
  10 }
  11 void
  12 errx(int eval, const char *fmt, ...)
  13 {
  14 }
  15
  16
  17 #define ED_MAX_SAMPLES_NO 1000
  18 #define ED_MAX_LINE_LEN 128
  19 #define EX_DATAERR 1
  20 #define EX_UNAVAILABLE  3
  21 #define ED_TOK_DELAY    "delay"
  22 #define ED_TOK_PROB     "prob"
  23 #define ED_SEPARATORS   " \t\n"
  24 #define ED_TOK_PROFILE_NO "profile_no"
  25
  26
  27 struct point {
  28         double prob;            /* y */
  29         double delay;           /* x */
  30 };
  31
  32 struct profile {
  33         char    filename[128];                   /* profile filename */
  34         int     samples[ED_MAX_SAMPLES_NO+1];    /* may be shorter */
  35         int     samples_no;                     /* actual len of samples[] */
  36 };
  37
  38 /*
  39  * returns 1 if s is a non-negative number, with at least one '.'
  40  */
  41 static int
  42 is_valid_number(const char *s)
  43 {
  44 #if 0
  45         int i, dots_found = 0;
  46         int len = strlen(s);
  47
  48         for (i = 0; i<len; ++i)
  49                 if (!isdigit(s[i]) && (s[i] !='.' || ++dots_found > 1))
  50                         return 0;
  51 #endif
  52         return 1;
  53 }
  54
  55 static int
  56 compare_points(const void *vp1, const void *vp2)
  57 {
  58         const struct point *p1 = vp1;
  59         const struct point *p2 = vp2;
  60         double res = 0;
  61
  62         res = p1->prob - p2->prob;
  63         if (res == 0)
  64                 res = p1->delay - p2->delay;
  65         if (res < 0)
  66                 return -1;
  67         else if (res > 0)
  68                 return 1;
  69         else
  70                 return 0;
  71 }
  72
  73 #define ED_EFMT(s) 1,"error in %s at line %d: "#s,filename,lineno
  74
  75 /*
  76  * The points defined by the user are stored in the ponts structure.
  77  * The number of user defined points is stored in points_no.
  78  *       We assume that The last point for the '1' value of the
  79  *       probability should be defined. (XXX add checks for this)
  80  * The user defined sampling value is stored in samples_no.
  81  * The resulting samples are in the "samples" pointer.
  82  */
  83 static void
  84 interpolate_samples(struct point *p, int points_no,
  85                 int *samples, int samples_no, const char *filename)
  86 {
  87         double dy;              /* delta on the y axis */
  88         double y;               /* current value of y */
  89         double x;               /* current value of x */
  90         double m;               /* the y slope */
  91         int i;                  /* samples index */
  92         int curr;               /* points current index */
  93
  94         dy = 1.0/samples_no;
  95         y = 0;
  96
  97         for (i=0, curr = 0; i < samples_no; i++, y+=dy) {
  98                 /* This statment move the curr pointer to the next point
  99                  * skipping the points with the same x value. We are
 100                  * guaranteed to exit from the loop because the
 101                  * last possible value of y is stricly less than 1
 102                  * and the last possible value of the y points is 1 */
 103                 while ( y >= p[curr+1].prob ) curr++;
 104
 105                 /* compute the slope of the curve */
 106                 m = (p[curr+1].delay - p[curr].delay) / (p[curr+1].prob - p[curr].prob);
 107                 /* compute the x value starting from the current point */
 108                 x = p[curr].delay + (y - p[curr].prob) * m;
 109                 samples[i] = x;
 110         }
 111
 112         /* add the last sample */
 113         samples[i] = p[curr+1].delay;
 114 }
 115
 116 #if 0
 117 static void
 118 interpolate_samples_old(struct point *points, int points_no,
 119                 int *samples, int samples_no, const char *filename)
 120 {
 121         int i;          /* pointer to the sampled array */
 122         int j = 0;      /* pointer to user defined samples */
 123         double dy;      /* delta y */
 124         double y;       /* current value of y */
 125         int x;          /* computed value of x */
 126         double m;       /* slope of the line */
 127         double y1, x1, y2, x2;  /* two points of the current line */
 128
 129         /* make sure that there are enough points. */
 130         /* XXX Duplicated shoule be removed */
 131         if (points_no < 3)
 132             errx(EX_DATAERR, "%s too few samples, need at least %d",
 133                 filename, 3);
 134
 135         qsort(points, points_no, sizeof(struct point), compare_points);
 136
 137         samples_no--;
 138         dy = 1.0/samples_no;
 139         printf("\nsamples no is %d dy is %f ", samples_no, dy);
 140
 141         /* start with the first two points */
 142         y1 = points[j].prob * samples_no;
 143         x1 = points[j].delay;
 144         j++;
 145         y2 = points[j].prob * samples_no;
 146         x2 = points[j].delay;
 147
 148         m = (y2-y1)/(x2-x1);
 149         printf("\nStart");
 150         printf("\n\tCurrent points x1 y1 %f %f next point x2y2 %f %f m %f\n",
 151                  x1, y1, x2, y2, m);
 152
 153         y = 0;
 154         x = x1;
 155
 156         for(i=0; i < samples_no+1; i++, y+=dy) {
 157                 printf("\ni:%d j:%d y:%f real y:%f", i, j, y, y*samples_no);
 158                 if ( (y*samples_no) >= y2 ) { /* move to the next point */
 159                         j++;
 160                         if ( j >= points_no ) {
 161                                 printf("\n\tNo more points, exit with j: %d i: %d and y:%f %f\n",
 162                                          j, i, y, (y*samples_no));
 163                                 break;  /* no more user defined points */
 164                         }
 165                         /* load a new point */
 166                         y1 = y2;
 167                         x1 = x2;
 168                         y2 = points[j].prob * samples_no;
 169                         x2 = points[j].delay;
 170                         m = (y2-y1)/(x2-x1);
 171                         if (x1==x2) { /* m = infinito */
 172                                 m = -1;
 173                                 x = x2;
 174                         }
 175                         /* very small m problem */
 176                         printf ("\ndelta %f\n", (y1 - y2));
 177                         if (abs(y1 - y2) < 0.00001) { /* m = 0 XXX Should this magic number depend on samples_no ? */
 178                                 m = 0;
 179                                 x = x2;
 180                         }
 181                         printf("\n\tCurrent points x1 y1 %f %f next point x2y2 %f %f (%f/%f)=m \n",
 182                                  x1, y1, x2, y2, (y2-y1), (x2-x1), m);
 183                 }
 184                 printf("\n\tcompute step y %f x[%d]=%d ",
 185                         y, i, x);
 186                 if ((m != -1) && ( m != 0 )) {
 187                         x = x + (dy * samples_no)/m;
 188                 }
 189                 samples[i] = x;
 190                 printf(" dy %f x new %d\n", dy*samples_no, x);
 191                 printf(" m %f (dy * samples_no)/m %f \n", m, (dy * samples_no)/m);
 192         }
 193
 194         x = samples[i-1];
 195         printf("Finish i is %d samples_no is %d\n", i, samples_no);
 196         /* The last point has a probability less than 1 */
 197         for (; i <= samples_no; i++)
 198                 samples[i] = x;
 199 }
 200 #endif
 201
 202 static void
 203 load_profile(struct profile *p)
 204 {
 205         FILE    *f;                     /* file handler */
 206         char    line[ED_MAX_LINE_LEN];
 207         int     lineno = 0;
 208         int     do_points = 0;
 209         int     delay_first = -1;
 210         int i;
 211
 212         struct  point points[1000]; /* MAX_POINTS_NO */
 213         int     points_no = 0;
 214
 215         char *filename = p->filename;
 216         f = fopen(filename, "r");
 217         if (f == NULL) {
 218             err(EX_UNAVAILABLE, "fopen: %s", filename);
 219         }
 220
 221
 222         while (fgets(line, ED_MAX_LINE_LEN, f)) {         /* read commands */
 223                 char *s, *cur = line, *name = NULL, *arg = NULL;
 224
 225                 ++lineno;
 226
 227                 /* parse the line */
 228                 while (cur) {
 229                         s = strsep(&cur, ED_SEPARATORS);
 230                         if (s == NULL || *s == '#')
 231                                 break;
 232                         if (*s == '\0')
 233                                 continue;
 234                         if (arg)
 235                                 errx(ED_EFMT("too many arguments"));
 236                         if (name == NULL)
 237                                 name = s;
 238                         else
 239                                 arg = s;
 240                 }
 241
 242                 if (name == NULL)
 243                         continue;
 244
 245                 if (!strcasecmp(name, ED_TOK_DELAY)) {
 246                     if (do_points)
 247                         errx(ED_EFMT("duplicated token: %s"), name);
 248                     delay_first = 1;
 249                     do_points = 1;
 250                     continue;
 251                 } else if (!strcasecmp(name, ED_TOK_PROB)) {
 252                     if (do_points)
 253                         errx(ED_EFMT("duplicated token: %s"), name);
 254                     delay_first = 0;
 255                     do_points = 1;
 256                     continue;
 257                 }
 258                 if (!strcasecmp(name, ED_TOK_PROFILE_NO)) {
 259                         int p_no = atof(arg);
 260                         if (p_no <= 0) {
 261                                 p_no = 100;
 262                                 printf("invalid interpolation samples, using %d\n",
 263                                          p_no);
 264                         }
 265                         if (p_no > ED_MAX_SAMPLES_NO) {
 266                                 p_no = ED_MAX_SAMPLES_NO;
 267                                 printf("invalid interpolation samples, using %d\n",
 268                                          p_no);
 269                         }
 270
 271                         p->samples_no = p_no;
 272                     continue;
 273
 274                 } else if (do_points) {
 275                     if (!is_valid_number(name) || !is_valid_number(arg))
 276                         errx(ED_EFMT("invalid point found"));
 277                     if (delay_first) {
 278                         points[points_no].delay = atof(name);
 279                         points[points_no].prob = atof(arg);
 280                     } else {
 281                         points[points_no].delay = atof(arg);
 282                         points[points_no].prob = atof(name);
 283                     }
 284                     if (points[points_no].prob > 1.0)
 285                         errx(ED_EFMT("probability greater than 1.0"));
 286                     ++points_no;
 287         /* XXX no more that 1000 */
 288                     continue;
 289                 } else {
 290                     errx(ED_EFMT("unrecognised command '%s'"), name);
 291                 }
 292         }
 293
 294         for(i=0; i < p->samples_no; i++) {
 295                 p->samples[i] = 666;
 296         }
 297
 298         /* This code assume the user define a value of X for the sampling value,
 299          * and that:
 300          * - the value stored in the emulator structure is X;
 301          * - the allocated structure for the samples is X+1;
 302          */
 303         interpolate_samples(points, points_no, p->samples, p->samples_no, filename);
 304
 305         // User defined samples
 306         printf("\nLoaded %d points:\n", points_no);
 307         for(i=0; i < points_no; i++) {
 308                 printf("%f %f\n", points[i].prob, points[i].delay);
 309         }
 310         printf("\n");
 311         printf("The sample value is %d \n", p->samples_no);
 312
 313 }
 314
 315 int main(int argc, char **argv)
 316 {
 317         if (argc < 2) {
 318                 printf("Usage: ./interpolation <filename>\n");
 319                 return -1;
 320         }
 321
 322         char *filename;
 323         filename = argv[1];
 324
 325         struct profile p;
 326         int i;
 327
 328         strncpy(p.filename, filename, 128);
 329         load_profile(&p);
 330         printf("-----------\n");
 331         for (i=0; i<=p.samples_no; i++)
 332                 printf("%d %d\n", i, p.samples[i]);
 333         printf("-----------\n");
 334         return 0;
 335 }