tools/GenTables/src/gen_table_mix.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 #include "boxmuller.h"
  25
  26 #include <stdio.h>
  27 #include <stdint.h>
  28 #include <string.h>
  29 #include <time.h>
  30 #include <stdbool.h>
  31 #include <io.h>
  32
  33 //-----------------------------------------------------------------------------
  34 // Const
  35 //-----------------------------------------------------------------------------
  36
  37 #define HASH_LEN 384U
  38
  39 #define DISTANCE_MIN 45U
  40
  41 #define ROW_NUM 997U                    /*total number of rows*/
  42 #define ROW_LEN (HASH_LEN / CHAR_BIT)   /*number of indices per row*/
  43
  44 #define __DISTANCE_STR(X) #X
  45 #define _DISTANCE_STR(X) __DISTANCE_STR(X)
  46 #define DISTANCE_STR _DISTANCE_STR(DISTANCE_MIN)
  47
  48 #define MAGIC_NUMBER 0x76A3D06509A73016ui64
  49
  50 //-----------------------------------------------------------------------------
  51 // Globals
  52 //-----------------------------------------------------------------------------
  53
  54 static uint8_t g_table[ROW_NUM][HASH_LEN];
  55
  56 static size_t g_spinpos = 0;
  57 static char SPINNER[4] = { '/', '-', '\\', '|' };
  58
  59 //-----------------------------------------------------------------------------
  60 // Utility Functions
  61 //-----------------------------------------------------------------------------
  62
  63 static inline void swap(uint8_t *const row_buffer, const size_t a, const size_t b)
  64 {
  65         const uint8_t temp = row_buffer[a];
  66         row_buffer[a] = row_buffer[b];
  67         row_buffer[b] = temp;
  68 }
  69
  70 static inline void random_permutation(twister_t *const rand, uint8_t *const row_buffer)
  71 {
  72         for (uint32_t i = 0; i < ROW_LEN; ++i)
  73         {
  74                 row_buffer[i] = ((uint8_t)i);
  75         }
  76         for (uint32_t i = 0; i < ROW_LEN - 1U; ++i)
  77         {
  78                 swap(row_buffer, i, next_rand_range(rand, ROW_LEN - i) + i);
  79         }
  80 }
  81
  82 static inline void swap_multiple_random(twister_t *const rand, uint8_t *const row_buffer, const size_t count)
  83 {
  84         bool map[ROW_LEN];
  85         memset(&map[0], 0, sizeof(bool) * ROW_LEN);
  86         for (size_t i = 0U; i < count; ++i)
  87         {
  88                 size_t a, b;
  89                 do
  90                 {
  91                         a = next_rand_range(rand, ROW_LEN);
  92                         b = next_rand_range(rand, ROW_LEN);
  93                 }
  94                 while(map[a] || (a == b));
  95                 map[a] = map[b] = true;
  96                 swap(row_buffer, a, b);
  97         }
  98 }
  99
 100 static inline void rotate_row(uint8_t *const row_buffer)
 101 {
 102         const uint8_t temp = row_buffer[0];
 103         for (uint32_t k = 0U; k < ROW_LEN - 1U; ++k)
 104         {
 105                 row_buffer[k] = row_buffer[k + 1U];
 106         }
 107         row_buffer[ROW_LEN - 1U] = temp;
 108 }
 109
 110 static inline void reverse_row(uint8_t *const row_buffer)
 111 {
 112         size_t j = ROW_LEN - 1U;
 113         for (size_t i = 0U; i < ROW_LEN / 2U; ++i)
 114         {
 115                 swap(row_buffer, i, j--);
 116         }
 117 }
 118
 119 static inline uint32_t check_permutation(const size_t index, const uint8_t *const row_buffer, const uint32_t limit)
 120 {
 121         uint32_t error = 0U;
 122         for (size_t i = 0; i < ROW_LEN; ++i)
 123         {
 124                 if (row_buffer[i] == ((uint8_t)i))
 125                 {
 126                         ++error;
 127                 }
 128         }
 129         if(error)
 130         {
 131                 return ROW_LEN + error;
 132         }
 133         for (size_t i = 0; i < index; ++i)
 134         {
 135                 uint32_t distance = 0U;
 136                 for (size_t j = 0; j < ROW_LEN; ++j)
 137                 {
 138                         if (g_table[i][j] != row_buffer[j])
 139                         {
 140                                 distance++;
 141                         }
 142                 }
 143                 if (distance < DISTANCE_MIN)
 144                 {
 145                         if ((error = max_ui32(error, DISTANCE_MIN - distance)) >= limit)
 146                         {
 147                                 break; /*early termination*/
 148                         }
 149                 }
 150         }
 151         return error;
 152 }
 153
 154 static void print_row(const uint8_t *const row_buffer)
 155 {
 156         for (size_t i = 0; i < ROW_LEN; ++i)
 157         {
 158                 printf(i ? ",%02X" : "%02X", row_buffer[i]);
 159         }
 160         puts("");
 161 }
 162
 163 static inline void permutation_to_shuffle_indices(const uint8_t *const row_buffer, uint8_t *const indices_out)
 164 {
 165         uint8_t reference[ROW_LEN];
 166         for (uint32_t i = 0U; i < ROW_LEN; ++i)
 167         {
 168                 reference[i] = ((uint8_t)i);
 169         }
 170         for (uint32_t i = 0U; i < ROW_LEN; ++i)
 171         {
 172                 indices_out[i] = UINT8_MAX;
 173                 for (uint32_t j = i; j < ROW_LEN; ++j)
 174                 {
 175                         if (reference[j] == row_buffer[i])
 176                         {
 177                                 swap(&reference[0], i, j);
 178                                 indices_out[i] = ((uint8_t)j);
 179                                 break;
 180                         }
 181                 }
 182         }
 183         for (uint32_t i = 0; i < ROW_LEN; ++i)
 184         {
 185                 if ((indices_out[i] == UINT8_MAX) || (reference[i] != row_buffer[i]))
 186                 {
 187                         puts("ERROR: Failed to derive shuffle indices!\n");
 188                 }
 189         }
 190 }
 191
 192 static dump_table(FILE *out)
 193 {
 194         fprintf(out, "uint8_t MHASH_384_TABLE_MIX[%u][MHASH_384_LEN] =\n{\n", ROW_NUM);
 195         for (size_t i = 0; i < ROW_NUM; i++)
 196         {
 197                 uint8_t shuffle_indices[ROW_LEN];
 198                 permutation_to_shuffle_indices(&g_table[i][0], &shuffle_indices[0]);
 199                 fputs("\t{ ", out);
 200                 for (size_t j = 0; j < ROW_LEN; j++)
 201                 {
 202                         if (j > 0)
 203                         {
 204                                 fputc(',', out);
 205                         }
 206                         fprintf(out, "0x%02X", shuffle_indices[j]);
 207                 }
 208                 fprintf(out, " }%s /*%03u*/\n", (i != (ROW_NUM - 1)) ? "," : " ", (uint32_t)i);
 209         }
 210         fputs("};\n", out);
 211 }
 212
 213 //-----------------------------------------------------------------------------
 214 // Save / Load
 215 //-----------------------------------------------------------------------------
 216
 217 static bool save_table_data(const wchar_t *const filename, const size_t rows_completed_in)
 218 {
 219         FILE *const file = _wfopen(filename, L"wb");
 220         if (file)
 221         {
 222                 bool success = true;
 223                 const uint64_t magic_number = MAGIC_NUMBER;
 224                 const uint32_t hash_len = HASH_LEN, distance_min = DISTANCE_MIN, rows_completed = (uint32_t)rows_completed_in;
 225                 fwrite(&magic_number, sizeof(uint64_t), 1, file);
 226                 fwrite(&hash_len, sizeof(uint32_t), 1, file);
 227                 fwrite(&distance_min, sizeof(uint32_t), 1, file);
 228                 fwrite(&rows_completed, sizeof(uint32_t), 1, file);
 229                 for (uint32_t i = 0; i < rows_completed; ++i)
 230                 {
 231                         const uint32_t checksum = adler32(&g_table[i][0], ROW_LEN);
 232                         fwrite(&checksum, sizeof(uint32_t), 1, file);
 233                         fwrite(&g_table[i][0], sizeof(uint8_t), ROW_LEN, file);
 234                 }
 235                 if (ferror(file))
 236                 {
 237                         printf("ERROR: Failed to write table data!\n");
 238                         success = false;
 239                 }
 240                 fclose(file);
 241                 return success;
 242         }
 243         else
 244         {
 245                 printf("ERROR: Failed to open table file for writing!\n");
 246                 return false;
 247         }
 248 }
 249
 250 static bool load_table_data(const wchar_t *const filename, size_t *const rows_completed_out)
 251 {
 252         FILE *const file = _wfopen(filename, L"rb");
 253         if (file)
 254         {
 255                 bool success = true;
 256                 uint64_t magic_number;
 257                 uint32_t hash_len, distance_min, rows_completed;
 258                 fread(&magic_number, sizeof(uint64_t), 1, file);
 259                 fread(&hash_len, sizeof(uint32_t), 1, file);
 260                 fread(&distance_min, sizeof(uint32_t), 1, file);
 261                 fread(&rows_completed, sizeof(uint32_t), 1, file);
 262                 if (ferror(file) || feof(file))
 263                 {
 264                         printf("ERROR: Failed to read the table header!\n");
 265                         success = false;
 266                         goto failed;
 267                 }
 268                 if (magic_number != MAGIC_NUMBER)
 269                 {
 270                         printf("ERROR: Table file format could not be recognized!\n");
 271                         success = false;
 272                         goto failed;
 273                 }
 274                 if ((hash_len != HASH_LEN) || (distance_min != DISTANCE_MIN) || (rows_completed > ROW_NUM))
 275                 {
 276                         printf("ERROR: Table properties are incompatibe with this instance!\n");
 277                         success = false;
 278                         goto failed;
 279                 }
 280                 for (size_t i = 0; i < rows_completed; ++i)
 281                 {
 282                         uint32_t checksum_expected;
 283                         if ((fread(&checksum_expected, sizeof(uint32_t), 1, file) != 1) || (fread(&g_table[i][0], sizeof(uint8_t), ROW_LEN, file) != ROW_LEN))
 284                         {
 285                                 printf("ERROR: Failed to read table data from file!\n");
 286                                 success = false;
 287                                 goto failed;
 288                         }
 289                         if (adler32(&g_table[i][0], ROW_LEN) != checksum_expected)
 290                         {
 291                                 printf("ERROR: Table checksum does *not* match table contents!\n");
 292                                 success = false;
 293                                 goto failed;
 294                         }
 295                         if (check_permutation(i, &g_table[i][0], 0U) != 0U)
 296                         {
 297                                 printf("ERROR: Table distance verification has failed!\n");
 298                                 success = false;
 299                                 goto failed;
 300                         }
 301                 }
 302         failed:
 303                 fclose(file);
 304                 if (success && rows_completed_out)
 305                 {
 306                         *rows_completed_out = (size_t)rows_completed;
 307                 }
 308                 return success;
 309         }
 310         else
 311         {
 312                 printf("ERROR: Failed to open table file for reading!\n");
 313                 return false;
 314         }
 315 }
 316 //-----------------------------------------------------------------------------
 317 // MAIN
 318 //-----------------------------------------------------------------------------
 319
 320 int wmain(int argc, wchar_t *argv[])
 321 {
 322         FILE *file_out = NULL;
 323         size_t initial_row_index = 0;
 324         char time_string[64];
 325
 326         printf("MHash GenTableMIX [%s]\n\n", __DATE__);
 327         printf("HashLen: %d, Distance Min: %d\n\n", HASH_LEN, DISTANCE_MIN);
 328
 329         if ((HASH_LEN % (8 * sizeof(uint32_t))) != 0)
 330         {
 331                 crit_exit("FATAL: Hash length must be a multiple of 32 bits!");
 332         }
 333
 334         if (argc < 2)
 335         {
 336                 printf("Table file not specified!\n\n");
 337                 printf("Usage:\n");
 338                 printf("   GenTables_MIX.exe <table_file>\n\n");
 339                 return 1;
 340         }
 341
 342         twister_t rand;
 343         rand_init(&rand, make_seed());
 344
 345         bxmller_t bxmller;
 346         gaussian_noise_init(&bxmller);
 347
 348         if (_waccess(argv[1], 4) == 0)
 349         {
 350                 printf("Loading existing table data and proceeding...\n");
 351                 if (!load_table_data(argv[1], &initial_row_index))
 352                 {
 353                         return 1;
 354                 }
 355         }
 356
 357         for (size_t i = initial_row_index; i < ROW_NUM; ++i)
 358         {
 359                 printf("Row %03u of %03u [%c]", (uint32_t)(i + 1U), ROW_NUM, SPINNER[g_spinpos]);
 360                 uint16_t counter = 0U;
 361                 time_t ref_time = time(NULL);
 362                 uint8_t temp[ROW_LEN];
 363                 for (;;)
 364                 {
 365                         random_permutation(&rand, &g_table[i][0]);
 366                         uint32_t error = check_permutation(i, &g_table[i][0], 0U);
 367                         printf("\b\b\b[%c]", '!');
 368                         for (uint32_t rand_init = 0U; rand_init < 999983U; ++rand_init)
 369                         {
 370                                 random_permutation(&rand, &temp[0]);
 371                                 const uint32_t error_next = check_permutation(i, &temp[0], error);
 372                                 if (error_next < error)
 373                                 {
 374                                         memcpy(&g_table[i][0], &temp[0], sizeof(uint8_t) * ROW_LEN); /*keep*/
 375                                         if (!((error = error_next) > 0U))
 376                                         {
 377                                                 goto success;
 378                                         }
 379                                 }
 380                         }
 381                         if (error > 0U)
 382                         {
 383                                 for (size_t retry = 0U; retry < 9973U; ++retry)
 384                                 {
 385                                         bool improved = false;
 386                                         for (uint32_t rotate = 0U; rotate < ROW_LEN; ++rotate)
 387                                         {
 388                                                 rotate_row(&g_table[i][0]);
 389                                                 const uint32_t error_next = check_permutation(i, &g_table[i][0], error);
 390                                                 if (error_next < error)
 391                                                 {
 392                                                         improved = true;
 393                                                         if (!((error = error_next) > 0U))
 394                                                         {
 395                                                                 goto success;
 396                                                         }
 397                                                         break;
 398                                                 }
 399                                                 reverse_row(&g_table[i][0]);
 400                                                 const uint32_t error_next_rev = check_permutation(i, &g_table[i][0], error);
 401                                                 if (error_next_rev >= error)
 402                                                 {
 403                                                         reverse_row(&g_table[i][0]); /*revert*/
 404                                                 }
 405                                                 else
 406                                                 {
 407                                                         improved = true;
 408                                                         if (!((error = error_next_rev) > 0U))
 409                                                         {
 410                                                                 goto success;
 411                                                         }
 412                                                         break;
 413                                                 }
 414                                         }
 415                                         for (uint32_t swap_x = 0; swap_x < ROW_LEN; ++swap_x)
 416                                         {
 417                                                 for (uint32_t swap_y = swap_x + 1U; swap_y < ROW_LEN; ++swap_y)
 418                                                 {
 419                                                         swap(&g_table[i][0], swap_x, swap_y);
 420                                                         const uint32_t error_next = check_permutation(i, &g_table[i][0], error);
 421                                                         if (error_next >= error)
 422                                                         {
 423                                                                 swap(&g_table[i][0], swap_x, swap_y); /*revert*/
 424                                                         }
 425                                                         else
 426                                                         {
 427                                                                 improved = true;
 428                                                                 if (!((error = error_next) > 0U))
 429                                                                 {
 430                                                                         goto success;
 431                                                                 }
 432                                                         }
 433                                                 }
 434                                         }
 435                                         for (uint32_t loop = 0; loop < 99991U; ++loop)
 436                                         {
 437                                                 const uint32_t swap_count = gaussian_noise_next(&rand, &bxmller, 8.0, 2U, (ROW_LEN / 2U));
 438                                                 if (!((++counter) & 0xFFF))
 439                                                 {
 440                                                         const time_t curr_time = time(NULL);
 441                                                         if (curr_time - ref_time >= 180i64)
 442                                                         {
 443                                                                 ref_time = curr_time;
 444                                                                 rand_init(&rand, make_seed());
 445                                                                 printf("\b\b\b[%c]", '$');
 446                                                         }
 447                                                         else
 448                                                         {
 449                                                                 printf("\b\b\b[%c]", SPINNER[g_spinpos]);
 450                                                                 g_spinpos = (g_spinpos + 1) % 4;
 451                                                         }
 452                                                 }
 453                                                 for (uint32_t round = 0; round < 97U; ++round)
 454                                                 {
 455                                                         memcpy(&temp[0], &g_table[i][0], sizeof(uint8_t) * ROW_LEN);
 456                                                         swap_multiple_random(&rand, &temp[0], swap_count);
 457                                                         const uint32_t error_next = check_permutation(i, &temp[0], error);
 458                                                         if (error_next < error)
 459                                                         {
 460                                                                 memcpy(&g_table[i][0], &temp[0], sizeof(uint8_t) * ROW_LEN); /*keep*/
 461                                                                 improved = true;
 462                                                                 if (!((error = error_next) > 0U))
 463                                                                 {
 464                                                                         goto success;
 465                                                                 }
 466                                                         }
 467                                                 }
 468                                         }
 469                                         if (!improved)
 470                                         {
 471                                                 break; /*early termination*/
 472                                         }
 473                                 }
 474                         }
 475                         else
 476                         {
 477                                 break; /*success*/
 478                         }
 479                 }
 480
 481         success:
 482                 get_time_str(time_string, 64);
 483                 printf("\b\b\b[#] - %s\n", time_string);
 484
 485                 if (!save_table_data(argv[1], i + 1U))
 486                 {
 487                         return 1; /*failed to save current table data*/
 488                 }
 489         }
 490
 491         printf("\n-----\n\n");
 492
 493         dump_table(stdout);
 494         if (fopen_s(&file_out, "table_MIX." DISTANCE_STR ".txt", "w") == 0)
 495         {
 496                 dump_table(file_out);
 497                 fclose(file_out);
 498         }
 499
 500         printf("\n-----\n\n");
 501
 502         printf("COMPLETED.\n\n");
 503         return getchar();
 504 }