test/xdeltatest.c

   1 /* -*- Mode: C;-*-
   2  *
   3  * This file is part of XDelta - A binary delta generator.
   4  *
   5  * Copyright (C) 1997, 1998, 2001  Josh MacDonald
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20  *
  21  * Author: Josh MacDonald <jmacd@CS.Berkeley.EDU>
  22  *
  23  * $Id: xdeltatest.c 1.7.1.1 Sat, 27 Jan 2007 17:53:47 -0800 jmacd $
  24  */
  25
  26 #include <sys/param.h>
  27 #include <sys/types.h>
  28 #include <unistd.h>
  29 #include "config.h"
  30
  31 #if TIME_WITH_SYS_TIME
  32 # include <sys/time.h>
  33 # include <time.h>
  34 #else
  35 # if HAVE_SYS_TIME_H
  36 #  include <sys/time.h>
  37 # else
  38 #  include <time.h>
  39 # endif
  40 #endif
  41
  42 #include <fcntl.h>
  43 #include <sys/stat.h>
  44 #include <sys/wait.h>
  45 #include <sys/resource.h>
  46 #include <stdio.h>
  47 #include <zlib.h>
  48
  49 #include "xdelta.h"
  50
  51 //////////////////////////////////////////////////////////////////////
  52 // Configure these parameters
  53 // @@@ Of course, a real test wouldn't require this configuration,
  54 // fix that!
  55 //////////////////////////////////////////////////////////////////////
  56
  57 const char* cmd_data_source      = "/zerostreet2/small-scratch-file";
  58 guint       cmd_size             = 1<<20;
  59
  60 guint       cmd_warmups          = 2;
  61 guint       cmd_reps             = 20;
  62
  63 guint       cmd_changes          = 1000;
  64 guint       cmd_deletion_length  = 30;
  65 guint       cmd_insertion_length = 15;
  66
  67 //////////////////////////////////////////////////////////////////////
  68 //
  69 //////////////////////////////////////////////////////////////////////
  70
  71 #define ARRAY_LENGTH(x) (sizeof(x)/sizeof(x[0]))
  72
  73 #define TEST_PREFIX "/tmp/xdeltatest"
  74
  75 #define TEST_IS_GZIP   1
  76 #define TEST_IS_XDELTA 2
  77
  78 typedef struct _File        File;
  79 typedef struct _Patch       Patch;
  80 typedef struct _TestProfile TestProfile;
  81 typedef struct _Instruction Instruction;
  82
  83 struct _Instruction {
  84   guint32 offset;
  85   guint32 length;
  86   Instruction* next;
  87 };
  88
  89 struct _File
  90 {
  91   char name[MAXPATHLEN];
  92 };
  93
  94 struct _Patch
  95 {
  96   guint8  *data;
  97   guint32  length;
  98 };
  99
 100 struct _TestProfile
 101 {
 102   const char *name;
 103   const char *progname;
 104   int         flags;
 105 };
 106
 107 #undef  BUFSIZ
 108 #define BUFSIZ (1<<24)
 109
 110 guint8 __tmp_buffer[BUFSIZ];
 111
 112 // Note: Of course you should be able to set all this up on the
 113 // command line.
 114
 115 TestProfile cmd_profiles[] =
 116 {
 117   { "xdelta -qn   ", "../xdelta",     TEST_IS_XDELTA },
 118   { "diff --rcs -a", "/usr/bin/diff", 0 },
 119   { "gzip         ", "/bin/gzip",     TEST_IS_GZIP },
 120 };
 121
 122 int         cmd_slevels[] = { 16, 32, 64 };
 123 int         cmd_zlevels[] = { 0, 1, 3, 6, 9 };
 124 guint16     cmd_seed[3]          = { 47384, 8594, 27489 };
 125
 126 FILE*       data_source_handle;
 127 guint       data_source_length;
 128 File*       data_source_file;
 129
 130 long        current_to_size;
 131 long        current_from_size;
 132
 133 double      __total_time;
 134 off_t       __dsize;
 135
 136 void
 137 reset_stats ()
 138 {
 139   __total_time = 0;
 140   __dsize      = -1;
 141 }
 142
 143 void add_tv (GTimer *timer)
 144 {
 145   __total_time += g_timer_elapsed (timer, NULL);
 146 }
 147
 148 void
 149 report (TestProfile *tp, int zlevel, int slevel)
 150 {
 151   static gboolean once = TRUE;
 152
 153   double t = __total_time / (double) cmd_reps;
 154   double s;
 155   const char *u;
 156   char  slevel_str[16];
 157
 158   if (tp->flags & TEST_IS_XDELTA)
 159     {
 160       sprintf (slevel_str, "%d", slevel);
 161     }
 162   else
 163     {
 164       slevel_str[0] = 0;
 165     }
 166
 167   if (tp->flags & TEST_IS_GZIP)
 168     {
 169       s = __dsize / (double) current_to_size;
 170       u = "total size";
 171     }
 172   else
 173     {
 174       s = __dsize / (double) (cmd_changes * cmd_insertion_length);
 175       u = "insertion size";
 176     }
 177
 178   if (once)
 179     {
 180       once = FALSE;
 181
 182       g_print ("Program\t\tzlevel\tslevel\tSeconds\tNormalized\n\t\t\t\t\tcompression\n");
 183     }
 184
 185   g_print ("%s\t%d\t%s\t%0.3f\t%0.3f (of %s)\n", tp->name, zlevel, slevel_str, t, s, u);
 186 }
 187
 188 guint32
 189 random_offset (guint len)
 190 {
 191   return lrand48 () % (data_source_length - len);
 192 }
 193
 194 void
 195 fail ()
 196 {
 197   g_warning ("FAILURE\n");
 198   abort ();
 199 }
 200
 201 gboolean starts_with (const char* s, const char *start)
 202 {
 203   return strncmp (s, start, strlen (start)) == 0;
 204 }
 205
 206 Patch*
 207 read_patch (File *file, struct stat *sbuf)
 208 {
 209   Patch *p = g_new0 (Patch,1);
 210   FILE  *f = fopen (file->name, "r");
 211
 212   p->length = (int)sbuf->st_size;
 213
 214   p->data   = g_malloc (p->length);
 215
 216   if (! f || fread (p->data, 1, p->length, f) != p->length)
 217     {
 218       perror ("fread");
 219       fail ();
 220     }
 221
 222   fclose (f);
 223
 224   return p;
 225 }
 226
 227 File*
 228 empty_file ()
 229 {
 230   static gint count = 0;
 231   File *file = g_new0 (File, 1);
 232
 233   sprintf (file->name, "%s.%d.%d", TEST_PREFIX, getpid (), count++);
 234
 235   return file;
 236 }
 237
 238 void
 239 compare_files (File* fromfile, File* tofile)
 240 {
 241   gint pos = 0;
 242
 243   FILE* toh;
 244   FILE* fromh;
 245
 246   guint8 buf1[1024], buf2[1024];
 247
 248   toh   = fopen (tofile->name, "r");
 249   fromh = fopen (fromfile->name, "r");
 250
 251   if (!toh || !fromh)
 252     fail ();
 253
 254   for (;;)
 255     {
 256       gint readf = fread (buf1, 1, 1024, fromh);
 257       gint readt = fread (buf2, 1, 1024, toh);
 258       gint i, m = MIN(readf, readt);
 259
 260       if (readf < 0 || readt < 0)
 261         fail ();
 262
 263       for (i = 0; i < m; i += 1, pos += 1)
 264         {
 265           if (buf1[i] != buf2[i])
 266             fail ();
 267         }
 268
 269       if (m != 1024)
 270         {
 271           if (readt == readf)
 272             {
 273               fclose (toh);
 274               fclose (fromh);
 275               return;
 276             }
 277
 278           fail ();
 279         }
 280     }
 281 }
 282
 283 int
 284 write_file (File* file, Instruction* inst)
 285 {
 286   FILE* h;
 287   int ret;
 288   int size = 0;
 289
 290   if (! (h = fopen (file->name, "w"))) {
 291     perror (file->name);
 292     fail ();
 293   }
 294
 295   for (; inst; inst = inst->next)
 296     {
 297       g_assert (inst->length <= BUFSIZ);
 298
 299       if ((ret = fseek (data_source_handle, inst->offset, SEEK_SET))) {
 300         perror ("fseek");
 301         fail ();
 302       }
 303
 304       if ((ret = fread (__tmp_buffer, 1, inst->length, data_source_handle)) != inst->length) {
 305         perror ("fread");
 306         fail ();
 307       }
 308
 309       if ((ret = fwrite (__tmp_buffer, 1, inst->length, h)) != inst->length) {
 310         perror ("fwrite");
 311         fail ();
 312       }
 313
 314       size += inst->length;
 315     }
 316
 317   if ((ret = fclose (h))) {
 318     perror ("fclose");
 319     fail ();
 320   }
 321
 322   return size;
 323 }
 324
 325 Instruction*
 326 perform_change_rec (Instruction* inst, guint32 change_off, guint* total_len)
 327 {
 328   if (change_off < inst->length)
 329     {
 330       guint32 to_delete = cmd_deletion_length;
 331       guint32 avail = inst->length;
 332       guint32 this_delete = MIN (to_delete, avail);
 333       Instruction* new_inst;
 334
 335       // One delete
 336       inst->length -= this_delete;
 337       to_delete -= this_delete;
 338
 339       while (to_delete > 0 && inst->next->length < to_delete)
 340         {
 341           to_delete -= inst->next->length;
 342           inst->next = inst->next->next;
 343         }
 344
 345       if (to_delete > 0)
 346         inst->next->offset += to_delete;
 347
 348       // One insert
 349       new_inst = g_new0 (Instruction, 1);
 350
 351       new_inst->offset = random_offset (cmd_insertion_length);
 352       new_inst->length = cmd_insertion_length;
 353       new_inst->next = inst->next;
 354       inst->next = new_inst;
 355
 356       (* total_len) += cmd_insertion_length - cmd_deletion_length;
 357
 358       return inst;
 359     }
 360   else
 361     {
 362       inst->next = perform_change_rec (inst->next, change_off - inst->length, total_len);
 363       return inst;
 364     }
 365 }
 366
 367 Instruction*
 368 perform_change (Instruction* inst, guint* len)
 369 {
 370   return perform_change_rec (inst, lrand48() % ((* len) - cmd_deletion_length), len);
 371 }
 372
 373 gboolean
 374 xdelta_verify (TestProfile *tp, int zlevel, int slevel, File* from, File* to, File* out, File *re)
 375 {
 376   int pid, status;
 377
 378   if ((pid = vfork()) < 0)
 379     return FALSE;
 380
 381   if (pid == 0)
 382     {
 383       execl (tp->progname,
 384              tp->progname,
 385              "patch",
 386              out->name,
 387              from->name,
 388              re->name,
 389              NULL);
 390       perror ("execl failed");
 391       _exit (127);
 392     }
 393
 394   if (waitpid (pid, &status, 0) != pid)
 395     {
 396       perror ("wait failed");
 397       fail ();
 398     }
 399
 400   // Note: program is expected to return 0, 1 meaning diff or no diff,
 401   // > 1 indicates failure
 402   if (! WIFEXITED (status) || WEXITSTATUS (status) > 1)
 403     {
 404       g_warning ("patch command failed\n");
 405       fail ();
 406     }
 407
 408   compare_files (to, re);
 409
 410   return TRUE;
 411 }
 412
 413 gboolean
 414 run_command (TestProfile *tp, int zlevel, int slevel, File* from, File* to, File* out, File *re, gboolean accounting)
 415 {
 416   int pid, status, outfd;
 417   struct stat sbuf;
 418   char xdelta_args[16];
 419   char xdelta_args2[16];
 420   char diff_gzargs[16];
 421   char gzip_args[16];
 422
 423   GTimer *timer = g_timer_new ();
 424
 425   sprintf (xdelta_args, "-qn%d", zlevel);
 426   sprintf (xdelta_args2, "-s%d", slevel);
 427   sprintf (diff_gzargs, "wb%d", zlevel);
 428   sprintf (gzip_args, "-c%d", zlevel);
 429
 430   unlink (out->name);
 431
 432   g_timer_start (timer);
 433
 434   if ((pid = vfork()) < 0)
 435     return FALSE;
 436
 437   if (pid == 0)
 438     {
 439       if (starts_with (tp->name, "xdelta"))
 440         {
 441           execl (tp->progname,
 442                  tp->progname,
 443                  "delta",
 444                  xdelta_args,
 445                  xdelta_args2,
 446                  from->name,
 447                  to->name,
 448                  out->name,
 449                  NULL);
 450         }
 451       else
 452         {
 453           outfd = open (out->name, O_CREAT | O_TRUNC | O_WRONLY, 0777);
 454
 455           if (outfd < 0)
 456             {
 457               perror ("open");
 458               fail ();
 459             }
 460
 461           dup2(outfd, STDOUT_FILENO);
 462
 463           if (close (outfd))
 464             {
 465               perror ("close");
 466               fail ();
 467             }
 468
 469           if (starts_with (tp->name, "diff"))
 470             execl (tp->progname,
 471                    tp->progname,
 472                    "--rcs",
 473                    "-a",
 474                    from->name,
 475                    to->name,
 476                    NULL);
 477           else if (starts_with (tp->name, "gzip"))
 478             execl (tp->progname,
 479                    tp->progname,
 480                    gzip_args,
 481                    to->name,
 482                    NULL);
 483           else
 484             abort ();
 485         }
 486
 487       perror ("execl failed");
 488       _exit (127);
 489     }
 490
 491   if (waitpid (pid, &status, 0) != pid)
 492     {
 493       perror ("wait failed");
 494       fail ();
 495     }
 496
 497   // Note: program is expected to return 0, 1 meaning diff or no diff,
 498   // > 1 indicates failure
 499   if (! WIFEXITED (status) || WEXITSTATUS (status) > 1)
 500     {
 501       g_warning ("delta command failed\n");
 502       fail ();
 503     }
 504
 505   if (stat (out->name, & sbuf))
 506     {
 507       perror ("stat");
 508       fail ();
 509     }
 510
 511   // Do zlib compression on behalf of diff
 512   if (zlevel > 0 && starts_with (tp->name, "diff"))
 513     {
 514       Patch  *patch   = read_patch (out, & sbuf);
 515       gzFile *rewrite = gzopen (out->name, diff_gzargs);
 516
 517       if (! rewrite) fail ();
 518
 519       if (gzwrite (rewrite, patch->data, patch->length) == 0) { perror ("gzwrite"); fail (); }
 520       if (gzclose (rewrite) != Z_OK)                          { perror ("gzclose"); fail (); }
 521       if (stat    (out->name, & sbuf))                        { perror ("stat");    fail (); }
 522     }
 523
 524   g_timer_stop (timer);
 525
 526   if (accounting)
 527     {
 528       add_tv (timer);
 529     }
 530
 531   if (__dsize < 0)
 532     {
 533       __dsize = sbuf.st_size;
 534
 535       // Verify only once
 536
 537       if (starts_with (tp->name, "xdelta"))
 538         {
 539           if (! xdelta_verify (tp, zlevel, slevel, from, to, out, re))
 540             {
 541               g_warning ("verify failed");
 542               fail ();
 543             }
 544         }
 545     }
 546   else
 547     {
 548       if (__dsize != sbuf.st_size)
 549         {
 550           g_warning ("%s -%d: delta command produced different size deltas: %d and %d",
 551                      tp->progname, zlevel, (int)__dsize, (int)sbuf.st_size);
 552           fail ();
 553         }
 554     }
 555
 556   g_timer_destroy (timer);
 557
 558   return TRUE;
 559 }
 560
 561 void
 562 test1 (TestProfile *test_profile,
 563        File        *from_file,
 564        File        *to_file,
 565        File        *out_file,
 566        File        *re_file)
 567 {
 568   int ret;
 569   guint i, change, current_size = cmd_size;
 570   guint end_size = (cmd_changes * cmd_insertion_length) + cmd_size;
 571   Instruction* inst;
 572   struct stat sbuf;
 573   int zlevel_i, slevel_i;
 574
 575   seed48 (cmd_seed);
 576
 577   if ((ret = stat (cmd_data_source, & sbuf)))
 578     {
 579       perror (cmd_data_source);
 580       fail ();
 581     }
 582
 583   if (! (data_source_handle = fopen (cmd_data_source, "r")))
 584     {
 585       perror (cmd_data_source);
 586       fail ();
 587     }
 588
 589   data_source_length = sbuf.st_size;
 590
 591   /* arbitrary checks */
 592   if (data_source_length < (1.5 * end_size))
 593     g_warning ("data source should be longer\n");
 594
 595   if ((cmd_changes * cmd_deletion_length) > cmd_size)
 596     {
 597       g_warning ("no copies are expected\n");
 598       fail ();
 599     }
 600
 601   inst = g_new0 (Instruction, 1);
 602
 603   inst->offset = random_offset (cmd_size);
 604   inst->length = cmd_size;
 605
 606   current_from_size = write_file (from_file, inst);
 607
 608   for (change = 0; change < cmd_changes; change += 1)
 609     inst = perform_change (inst, & current_size);
 610
 611   current_to_size = write_file (to_file, inst);
 612
 613   for (slevel_i = 0; slevel_i < ARRAY_LENGTH(cmd_slevels); slevel_i += 1)
 614     {
 615       int slevel = cmd_slevels[slevel_i];
 616
 617       if ((test_profile->flags & TEST_IS_XDELTA) == 0 && slevel_i != 0)
 618         {
 619           continue;
 620         }
 621
 622       for (zlevel_i = 0; zlevel_i < ARRAY_LENGTH(cmd_zlevels); zlevel_i += 1)
 623         {
 624           int zlevel = cmd_zlevels[zlevel_i];
 625
 626           if (test_profile->flags & TEST_IS_GZIP)
 627             {
 628               if (zlevel != 1 && zlevel != 9)
 629                 continue;
 630             }
 631
 632           reset_stats ();
 633
 634           for (i = 0; i < cmd_warmups + cmd_reps; i += 1)
 635             {
 636               if (! run_command (test_profile,
 637                                  zlevel,
 638                                  slevel,
 639                                  from_file,
 640                                  to_file,
 641                                  out_file,
 642                                  re_file,
 643                                  (i >= cmd_warmups) /* true => accounting */))
 644                 {
 645                   fail ();
 646                 }
 647             }
 648
 649           report (test_profile, zlevel, slevel);
 650         }
 651
 652       g_print ("\n");
 653     }
 654 }
 655
 656 int
 657 main (gint argc, gchar** argv)
 658 {
 659   int profile_i;
 660
 661   File *from_file;
 662   File *to_file;
 663   File *out_file;
 664   File *re_file;
 665
 666   system ("rm -rf " TEST_PREFIX "*");
 667
 668   from_file = empty_file ();
 669   to_file   = empty_file ();
 670   out_file  = empty_file ();
 671   re_file   = empty_file ();
 672
 673   for (profile_i = 0; profile_i < ARRAY_LENGTH(cmd_profiles); profile_i += 1)
 674     {
 675       test1 (& cmd_profiles[profile_i], from_file, to_file, out_file, re_file);
 676
 677       system ("rm -rf " TEST_PREFIX "*");
 678     }
 679
 680   return 0;
 681 }