tools/GenTables/src/gen_table_mix.c

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