mega-sena/mega-sena.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <unistd.h>
   4 #include <stdlib.h>
   5 #include <stdarg.h>
   6 #include <signal.h>
   7 #include <limits.h>
   8 #include <fcntl.h>
   9 #include <sys/stat.h>
  10 #include <sys/types.h>
  11
  12 #include "module.h"
  13 #include "mod_lp.h"
  14 #include "mod_cuckoo.h"
  15
  16 #define LINE_LEN           24
  17 #define LOTTERY_MAX         6          /* bytes */
  18
  19 static struct module *hash_module;
  20
  21 static sig_atomic_t show_status, reload_table;
  22 static unsigned long nr_runs, nr_found, ulong_max;
  23
  24 static void sig_handler(int signum)
  25 {
  26         switch (signum) {
  27         case SIGUSR1:
  28                 show_status = 1;
  29                 break;
  30         case SIGHUP:
  31                 reload_table = 1;
  32                 break;
  33         }
  34 }
  35
  36 /* fatal(): print error message and exit */
  37 static void fatal(const char *err, ...)
  38 {
  39         va_list params;
  40
  41         fputs("ERROR: ", stderr);
  42
  43         va_start(params, err);
  44         vfprintf(stderr, err, params);
  45         va_end(params);
  46
  47         putc('\n', stderr);
  48
  49         exit(1);
  50 }
  51
  52 /* FIXME: duplicated from load_file() */
  53 static int self_test(const char *path)
  54 {
  55         FILE *file;
  56         int found, ret;
  57         char line[LINE_LEN];
  58
  59         file = fopen(path, "r");
  60         if (!file)
  61                 return -1;
  62
  63         ret = 0;
  64         memset(line, 0, sizeof(line));
  65
  66         while (fgets(line, sizeof(line), file) != NULL) {
  67                 char *p;
  68
  69                 if (line[0] == '#') {
  70                         if (!strchr(line, '\n')) {
  71                                 int c;
  72
  73                                 while ((c = getc(file)) != '\n')
  74                                         /* NOTHING */;
  75                         }
  76                         memset(line, 0, sizeof(line));
  77                         continue;
  78                 }
  79
  80                 p = strchr(line, '\n');
  81                 if (p)
  82                         *p = '\0';
  83
  84                 found = hash_module->mod_lookup(line, NULL);
  85                 if (!found) {
  86                         printf("   Could not found: %s\n", line);
  87                         ret = -1;
  88                         break;
  89                 }
  90
  91                 memset(line, 0, sizeof(line));
  92         }
  93
  94         fclose(file);
  95
  96         found = hash_module->mod_lookup("aaaaaaaaaaaaaaaaa", NULL);
  97         if (found) {
  98                 fprintf(stderr, "found unknow string\n");
  99                 ret = 1;
 100         }
 101
 102         return ret;
 103 }
 104
 105 /* load the data from the file into the hash table */
 106 static int load_file(const char *path)
 107 {
 108         FILE *file;
 109         char line[LINE_LEN];
 110
 111         file = fopen(path, "r");
 112         if (!file)
 113                 return -1;
 114
 115         memset(line, 0, sizeof(line));
 116
 117         while (fgets(line, sizeof(line), file) != NULL) {
 118                 int err;
 119                 char *p;
 120
 121                 if (line[0] == '#') {
 122                         if (!strchr(line, '\n')) {
 123                                 int c;
 124
 125                                 while ((c = getc(file)) != '\n')
 126                                         /* NOTHING */;
 127                         }
 128                         memset(line, 0, sizeof(line));
 129                         continue;
 130                 }
 131
 132                 p = strchr(line, '\n');
 133                 if (p)
 134                         *p = '\0';
 135
 136                 p = strdup(line);
 137                 if (!p) {
 138                         fclose(file);
 139                         return -1;
 140                 }
 141
 142                 err = hash_module->mod_insert(p);
 143                 if (err) {
 144                         free(p);
 145                         if (err == -1) {
 146                                 fclose(file);
 147                                 return -1;
 148                         }
 149                         /* else key already exists */
 150                 }
 151
 152                 memset(line, 0, sizeof(line));
 153         }
 154
 155         fclose(file);
 156         return 0;
 157 }
 158
 159 static int set_seed(void)
 160 {
 161         int fd, ret;
 162         size_t bytes;
 163         unsigned int seed;
 164
 165         fd = open("/dev/random", O_RDONLY);
 166         if (fd < 0)
 167                 return -1;
 168
 169         bytes = read(fd, &seed, sizeof(seed));
 170         if (bytes != sizeof(seed)) {
 171                 ret = -1;
 172                 goto out;
 173         }
 174
 175         ret = 0;
 176         srand(seed);
 177         printf("\n-> Seed: %#X\n", seed);
 178
 179 out:
 180         close(fd);
 181         return ret;
 182 }
 183
 184 static void lottery(char *result, size_t size)
 185 {
 186         int num, i, j;
 187         int numbers[LOTTERY_MAX];
 188
 189         memset(result, 0, size);
 190         memset(numbers, -1, sizeof(numbers));
 191
 192         for (i = 0; i < LOTTERY_MAX; i++) {
 193                 for (;;) {
 194                         int found = 0;
 195
 196                         num = 1 + (int) (60.0 * (rand() / (RAND_MAX + 6.0)));
 197
 198                         for (j = 0; j < i; j++)
 199                                 if (numbers[j] == num) {
 200                                         found = 1;
 201                                         break;
 202                                 }
 203
 204                         if (!found) {
 205                                 numbers[i] = num;
 206                                 break;
 207                         }
 208                 }
 209         }
 210
 211         snprintf(result, size, "%02d %02d %02d %02d %02d %02d",
 212                 numbers[0], numbers[1], numbers[2],
 213                 numbers[3], numbers[4], numbers[5]);
 214 }
 215
 216 static void show_pid(void)
 217 {
 218         printf("-> PID: %d\n\n", getpid());
 219 }
 220
 221 /* usage(): print usage info */
 222 static void usage(void)
 223 {
 224         printf(
 225                "usage: mega-sena [options] < -c | -l > < file >\n\n"
 226                "  options:\n"
 227                "            -h  this text\n"
 228                "            -c  use cuckoo hashing\n"
 229                "            -l  use linear probing (open addressing)\n"
 230                "            -t  run self test for selected hashing algorithm\n"
 231                "\n"
 232                );
 233 }
 234
 235 int main(int argc, char *argv[])
 236 {
 237         unsigned int hash;
 238         int opt, run_stest, err;
 239         char result[LINE_LEN], *path;
 240
 241         run_stest = 0;
 242         hash_module = NULL;
 243
 244         while ((opt = getopt(argc, argv, "htcl")) != -1 ) {
 245                 switch (opt) {
 246                 case 'h':
 247                         usage();
 248                         exit(0);
 249                 case 't':
 250                         run_stest = 1;
 251                         break;
 252                 case 'l':
 253                         hash_module = &lp_module;
 254                         break;
 255                 case 'c':
 256                         hash_module = &cuckoo_module;
 257                         break;
 258                 default:
 259                         usage();
 260                         exit(1);
 261                 }
 262         }
 263
 264         if (optind >= argc)
 265                 fatal("you have to specify a filename");
 266
 267         if (!hash_module)
 268                 fatal("you have to select a hash algorithm");
 269
 270         path = argv[optind];
 271         setlinebuf(stdout);
 272
 273         err = hash_module->mod_init();
 274         if (err) {
 275                 perror("mod_init()");
 276                 exit(1);
 277         }
 278
 279         err = load_file(path);
 280         if (err) {
 281                 perror("load_file()");
 282                 err = 1;
 283                 goto out;
 284         }
 285
 286         hash_module->mod_stats();
 287
 288         if (run_stest) {
 289                 err = self_test(path);
 290                 printf("Performing self-test: ");
 291                 err ? printf("FAILED!\n") : printf("PASSED!\n");
 292                 err = 0;
 293                 goto out;
 294         }
 295
 296         err = set_seed();
 297         if (err) {
 298                 perror("set_seed()");
 299                 goto out;
 300         }
 301
 302         show_pid();
 303
 304         signal(SIGUSR1, sig_handler);
 305         signal(SIGHUP, sig_handler);
 306
 307         for (;;) {
 308                 int found;
 309
 310                 /*
 311                  * The following checks will probably make the program
 312                  * run slower, but I've implemented them because they're
 313                  * cool features (specially the reload table one).
 314                  */
 315
 316                 if (show_status) {
 317                         printf("-> Ran %lu (* %lu) times with %lu matches\n",
 318                                nr_runs, ulong_max, nr_found);
 319                         show_status = 0;
 320                 }
 321
 322                 if (reload_table) {
 323                         /*
 324                          * XXX: Reading all the file again isn't a smart
 325                          * way to do this, we could start reading from
 326                          * the last line read.
 327                          */
 328                         err = load_file(path);
 329                         if (err) {
 330                                 perror("load_file()");
 331                                 fprintf(stderr, "Aborting...\n");
 332                                 goto out;
 333                         }
 334
 335                         hash_module->mod_stats();
 336                         reload_table = 0;
 337                 }
 338
 339                 lottery(result, sizeof(result));
 340
 341                 found = hash_module->mod_lookup(result, &hash);
 342                 if (found) {
 343                         printf("-> HIT in run %lu: [%d] %s\n",
 344                                nr_runs, hash, result);
 345                         nr_found++;
 346                 }
 347
 348                 if (++nr_runs == ULONG_MAX) {
 349                         if (++ulong_max == ULONG_MAX) {
 350                                 printf("-> ulong_max blew up [%lu]\n",
 351                                        ulong_max);
 352                                 ulong_max = 0;
 353                         }
 354                         nr_runs = 0;
 355                 }
 356         }
 357
 358 out:
 359         hash_module->mod_destroy();
 360         return err;
 361 }