tools/GenTables/src/gen_table_xor.c

   1 /* ----------------------------------------------------------------------------------------------- */
   2 /* MHash-384 - Generate tables utility program                                                     */
   3 /* Copyright(c) 2016 LoRd_MuldeR <mulder2@gmx.de>                                                  */
   4 /*                                                                                                 */
   5 /* Permission is hereby granted, free of charge, to any person obtaining a copy of this software   */
   6 /* and associated documentation files(the "Software"), to deal in the Software without             */
   7 /* restriction, including without limitation the rights to use, copy, modify, merge, publish,      */
   8 /* distribute, sublicense, and / or sell copies of the Software, and to permit persons to whom the */
   9 /* Software is furnished to do so, subject to the following conditions:                            */
  10 /*                                                                                                 */
  11 /* The above copyright notice and this permission notice shall be included in all copies or        */
  12 /* substantial portions of the Software.                                                           */
  13 /*                                                                                                 */
  14 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING   */
  15 /* BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND      */
  16 /* NONINFRINGEMENT.IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,     */
  17 /* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,  */
  18 /* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.         */
  19 /* ----------------------------------------------------------------------------------------------- */
  20
  21 #include "common.h"
  22 #include "thread_utils.h"
  23 #include "twister.h"
  24
  25 #include <stdio.h>
  26 #include <stdint.h>
  27 #include <string.h>
  28 #include <time.h>
  29 #include <stdbool.h>
  30 #include <io.h>
  31
  32 //-----------------------------------------------------------------------------
  33 // Const
  34 //-----------------------------------------------------------------------------
  35
  36 #define HASH_LEN 384
  37
  38 #define DISTANCE_MIN 180
  39 #define DISTANCE_MAX DISTANCE_MIN + 32
  40
  41 #define THREAD_COUNT 8
  42
  43 #define ROW_NUM (UINT8_MAX+2)           /*total number of rows*/
  44 #define ROW_LEN (HASH_LEN / CHAR_BIT)   /*number of bits per row*/
  45
  46 #define __DISTANCE_STR(X) #X
  47 #define _DISTANCE_STR(X) __DISTANCE_STR(X)
  48 #define DISTANCE_STR _DISTANCE_STR(DISTANCE_MIN)
  49
  50 #define MAGIC_NUMBER 0X3C6058A7C1132CB2ui64
  51
  52 //-----------------------------------------------------------------------------
  53 // Globals
  54 //-----------------------------------------------------------------------------
  55
  56 static uint8_t g_table[ROW_NUM][ROW_LEN];
  57 static uint8_t g_thread_buffer[THREAD_COUNT][ROW_LEN];
  58
  59 static size_t g_spinpos = 0;
  60 static char SPINNER[4] = { '/', '-', '\\', '|' };
  61
  62 //-----------------------------------------------------------------------------
  63 // Utility Functions
  64 //-----------------------------------------------------------------------------
  65
  66
  67 static inline bool check_distance_rows(const size_t index_1, const size_t index_2)
  68 {
  69         const uint32_t dist = hamming_distance(&g_table[index_1][0], &g_table[index_2][0], ROW_LEN);
  70         return (dist <= DISTANCE_MAX) && (dist >= DISTANCE_MIN);
  71 }
  72
  73 static inline bool check_distance_next(const size_t index, const uint8_t *const row_buffer)
  74 {
  75         for (size_t k = 0; k < index; k++)
  76         {
  77                 const uint32_t dist = hamming_distance(&g_table[k][0], row_buffer, ROW_LEN);
  78                 if ((dist > DISTANCE_MAX) || (dist < DISTANCE_MIN))
  79                 {
  80                         return false;
  81                 }
  82         }
  83         return true;
  84 }
  85
  86 static dump_table(FILE *out)
  87 {
  88         fputs("uint8_t MHASH_384_TABLE_XOR[UINT8_MAX+2][MHASH_384_LEN] =\n{\n", out);
  89         for (size_t i = 0; i < ROW_NUM; i++)
  90         {
  91                 fputs("\t{ ", out);
  92                 for (size_t j = 0; j < ROW_LEN; j++)
  93                 {
  94                         if (j > 0)
  95                         {
  96                                 fputc(',', out);
  97                         }
  98                         fprintf(out, "0x%02X", g_table[i][j]);
  99                 }
 100                 fprintf(out, " }%s /*%02X*/\n", (i != (ROW_NUM - 1)) ? "," : " ", (uint32_t)(i % 0x100));
 101         }
 102         fputs("};\n", out);
 103 }
 104
 105 //-----------------------------------------------------------------------------
 106 // Thread function
 107 //-----------------------------------------------------------------------------
 108
 109 typedef struct
 110 {
 111         size_t index;
 112         uint8_t *row_buffer;
 113         sem_t *stop;
 114         pthread_mutex_t *mutex;
 115         twister_t *rand;
 116 }
 117 thread_data_t;
 118
 119 static void* thread_main(void *const param)
 120 {
 121         const thread_data_t *const data = ((const thread_data_t*)param);
 122         uint16_t counter = 0, reseed = 0;
 123         do
 124         {
 125                 if ((++counter) == 0)
 126                 {
 127                         if (SEM_TRYWAIT(data->stop))
 128                         {
 129                                 return NULL;
 130                         }
 131                         if (((++reseed) % 997U) == 0)
 132                         {
 133                                 rand_init(data->rand, make_seed());
 134                         }
 135                 }
 136                 if (counter & 1U)
 137                 {
 138                         rand_next_bytes(data->rand, data->row_buffer, ROW_LEN);
 139                 }
 140                 else
 141                 {
 142                         invert_byte_buffer(data->row_buffer, ROW_LEN);
 143                 }
 144         }
 145         while (!check_distance_next(data->index, data->row_buffer));
 146
 147         MUTEX_LOCK(data->mutex);
 148         if (SEM_TRYWAIT(data->stop))
 149         {
 150                 MUTEX_UNLOCK(data->mutex);
 151                 return NULL;
 152         }
 153
 154         SEM_POST(data->stop, THREAD_COUNT);
 155         MUTEX_UNLOCK(data->mutex);
 156         return data->row_buffer; /*success*/
 157 }
 158
 159 static void* thread_spin(void *const param)
 160 {
 161         unsigned long delay = 0;
 162         sem_t *const stop = ((sem_t*)param);
 163         for (;;)
 164         {
 165                 if (SEM_TRYWAIT(stop))
 166                 {
 167                         return NULL;
 168                 }
 169                 _sleep(delay);
 170                 if (delay >= 1000)
 171                 {
 172                         printf("\b\b\b[%c]", SPINNER[g_spinpos]);
 173                         g_spinpos = (g_spinpos + 1) % 4;
 174                 }
 175                 else
 176                 {
 177                         delay = (delay > 0) ? (2 * delay) : 1;
 178                 }
 179         }
 180 }
 181
 182 //-----------------------------------------------------------------------------
 183 // Save / Load
 184 //-----------------------------------------------------------------------------
 185
 186 static bool save_table_data(const wchar_t *const filename, const size_t rows_completed_in)
 187 {
 188         FILE *const file = _wfopen(filename, L"wb");
 189         if (file)
 190         {
 191                 bool success = true;
 192                 const uint64_t magic_number = MAGIC_NUMBER;
 193                 const uint32_t hash_len = HASH_LEN, distance_min = DISTANCE_MIN, distance_max = DISTANCE_MAX, rows_completed = (uint32_t)rows_completed_in;
 194                 fwrite(&magic_number, sizeof(uint64_t), 1, file);
 195                 fwrite(&hash_len, sizeof(uint32_t), 1, file);
 196                 fwrite(&distance_min, sizeof(uint32_t), 1, file);
 197                 fwrite(&distance_max, sizeof(uint32_t), 1, file);
 198                 fwrite(&rows_completed, sizeof(uint32_t), 1, file);
 199                 for (uint32_t i = 0; i < rows_completed; ++i)
 200                 {
 201                         const uint32_t checksum = adler32(&g_table[i][0], ROW_LEN);
 202                         fwrite(&checksum, sizeof(uint32_t), 1, file);
 203                         fwrite(&g_table[i][0], sizeof(uint8_t), ROW_LEN, file);
 204                 }
 205                 if (ferror(file))
 206                 {
 207                         printf("ERROR: Failed to write table data!\n");
 208                         success = false;
 209                 }
 210                 fclose(file);
 211                 return success;
 212         }
 213         else
 214         {
 215                 printf("ERROR: Failed to open table file for writing!\n");
 216                 return false;
 217         }
 218 }
 219
 220 static bool load_table_data(const wchar_t *const filename, size_t *const rows_completed_out)
 221 {
 222         FILE *const file = _wfopen(filename, L"rb");
 223         if (file)
 224         {
 225                 bool success = true;
 226                 uint64_t magic_number;
 227                 uint32_t hash_len, distance_min, distance_max, rows_completed;
 228                 fread(&magic_number, sizeof(uint64_t), 1, file);
 229                 fread(&hash_len, sizeof(uint32_t), 1, file);
 230                 fread(&distance_min, sizeof(uint32_t), 1, file);
 231                 fread(&distance_max, sizeof(uint32_t), 1, file);
 232                 fread(&rows_completed, sizeof(uint32_t), 1, file);
 233                 if (ferror(file) || feof(file))
 234                 {
 235                         printf("ERROR: Failed to read the table header!\n");
 236                         success = false;
 237                         goto failed;
 238                 }
 239                 if (magic_number != MAGIC_NUMBER)
 240                 {
 241                         printf("ERROR: Table file format could not be recognized!\n");
 242                         success = false;
 243                         goto failed;
 244                 }
 245                 if ((hash_len != HASH_LEN) || (distance_min != DISTANCE_MIN) || (distance_max != DISTANCE_MAX) || (rows_completed > ROW_NUM))
 246                 {
 247                         printf("ERROR: Table properties are incompatibe with this instance!\n");
 248                         success = false;
 249                         goto failed;
 250                 }
 251                 for (size_t i = 0; i < rows_completed; ++i)
 252                 {
 253                         uint32_t checksum_expected;
 254                         if ((fread(&checksum_expected, sizeof(uint32_t), 1, file) != 1) || (fread(&g_table[i][0], sizeof(uint8_t), ROW_LEN, file) != ROW_LEN))
 255                         {
 256                                 printf("ERROR: Failed to read table data from file!\n");
 257                                 success = false;
 258                                 goto failed;
 259                         }
 260                         if (adler32(&g_table[i][0], ROW_LEN) != checksum_expected)
 261                         {
 262                                 printf("ERROR: Table checksum does *not* match table contents!\n");
 263                                 success = false;
 264                                 goto failed;
 265                         }
 266                         for (size_t j = 0; j < i; j++)
 267                         {
 268                                 if (!check_distance_rows(i, j))
 269                                 {
 270                                         printf("ERROR: Table distance verification has failed!\n");
 271                                         success = false;
 272                                         goto failed;
 273                                 }
 274                         }
 275                 }
 276         failed:
 277                 fclose(file);
 278                 if (success && rows_completed_out)
 279                 {
 280                         *rows_completed_out = (size_t)rows_completed;
 281                 }
 282                 return success;
 283         }
 284         else
 285         {
 286                 printf("ERROR: Failed to open table file for reading!\n");
 287                 return false;
 288         }
 289 }
 290
 291 //-----------------------------------------------------------------------------
 292 // MAIN
 293 //-----------------------------------------------------------------------------
 294
 295 int wmain(int argc, wchar_t *argv[])
 296 {
 297         pthread_t thread_id[THREAD_COUNT + 1];
 298         thread_data_t thread_data[THREAD_COUNT];
 299         twister_t thread_rand[THREAD_COUNT];
 300         sem_t stop_flag;
 301         pthread_mutex_t stop_mutex;
 302         FILE *file_out = NULL;
 303         size_t initial_row_index = 0;
 304
 305         printf("MHash GenTableXOR [%s]\n\n", __DATE__);
 306         printf("HashLen: %d, Distance Min/Max: %d/%d, Threads: %d\n\n", HASH_LEN, DISTANCE_MIN, DISTANCE_MAX, THREAD_COUNT);
 307
 308         if ((HASH_LEN % (8 * sizeof(uint32_t))) != 0)
 309         {
 310                 crit_exit("FATAL: Hash length must be a multiple of 32 bits!");
 311         }
 312
 313         if (argc < 2)
 314         {
 315                 printf("Table file not specified!\n\n");
 316                 printf("Usage:\n");
 317                 printf("   GenTables_XOR.exe <table_file>\n\n");
 318                 return 1;
 319         }
 320
 321         for (size_t i = 0; i < ROW_NUM; i++)
 322         {
 323                 memset(&g_table[i][0], 0, sizeof(uint8_t) * ROW_LEN);
 324         }
 325
 326         memset(&thread_id, 0, sizeof(pthread_t) * (THREAD_COUNT + 1));
 327         memset(&thread_data, 0, sizeof(thread_data_t) * THREAD_COUNT);
 328         for (size_t t = 0; t < THREAD_COUNT; t++)
 329         {
 330                 memset(&g_thread_buffer[t][0], 0, sizeof(uint8_t) * ROW_LEN);
 331                 rand_init(&thread_rand[t], make_seed());
 332         }
 333
 334         SEM_INIT(&stop_flag);
 335         MUTEX_INIT(&stop_mutex);
 336
 337         if (_waccess(argv[1], 4) == 0)
 338         {
 339                 printf("Loading existing table data and proceeding...\n");
 340                 if (!load_table_data(argv[1], &initial_row_index))
 341                 {
 342                         return 1;
 343                 }
 344         }
 345
 346         for (size_t i = initial_row_index; i < ROW_NUM; i++)
 347         {
 348                 char time_string[64];
 349                 printf("Row %03u of %03u [%c]", (uint32_t)(i+1U), ROW_NUM, SPINNER[g_spinpos]);
 350                 g_spinpos = (g_spinpos + 1) % 4;
 351
 352                 PTHREAD_CREATE(&thread_id[THREAD_COUNT], NULL, thread_spin, &stop_flag);
 353                 for (size_t t = 0; t < THREAD_COUNT; t++)
 354                 {
 355                         thread_data[t].index = i;
 356                         thread_data[t].row_buffer = &g_thread_buffer[t][0];
 357                         thread_data[t].stop = &stop_flag;
 358                         thread_data[t].mutex = &stop_mutex;
 359                         thread_data[t].rand = &thread_rand[t];
 360                         PTHREAD_CREATE(&thread_id[t], NULL, thread_main, &thread_data[t]);
 361                 }
 362
 363                 for (size_t t = 0; t < THREAD_COUNT; t++)
 364                 {
 365                         void *return_value = NULL;
 366                         PTHREAD_JOIN(thread_id[t], &return_value);
 367                         if (return_value)
 368                         {
 369                                 memcpy(&g_table[i][0], return_value, sizeof(uint8_t) * ROW_LEN);
 370                         }
 371                 }
 372
 373                 PTHREAD_JOIN(thread_id[THREAD_COUNT], NULL);
 374                 get_time_str(time_string, 64);
 375                 printf("\b\b\b[#] - %s\n", time_string);
 376
 377                 if (!save_table_data(argv[1], i + 1U))
 378                 {
 379                         return 1; /*failed to save current table data*/
 380                 }
 381         }
 382
 383         printf("\n-----\n\n");
 384
 385         dump_table(stdout);
 386         if (fopen_s(&file_out, "table_out." DISTANCE_STR ".txt", "w") == 0)
 387         {
 388                 dump_table(file_out);
 389                 fclose(file_out);
 390         }
 391
 392         printf("\n-----\n\n");
 393
 394         for (size_t i = 0; i < ROW_NUM; i++)
 395         {
 396                 for (size_t j = 0; j < ROW_NUM; j++)
 397                 {
 398                         if (i == j)
 399                         {
 400                                 continue;
 401                         }
 402                         if (!check_distance_rows(i, j))
 403                         {
 404                                 crit_exit("FATAL: Table verification has failed!");
 405                         }
 406                 }
 407         }
 408
 409         SEM_DESTROY(&stop_flag);
 410         MUTEX_DESTROY(&stop_mutex);
 411
 412         printf("COMPLETED.\n\n");
 413         return getchar();
 414 }