/* ----------------------------------------------------------------------------------------------- */
/* MHash-384 - Generate tables utility program */
-/* Copyright(c) 2016 LoRd_MuldeR <mulder2@gmx.de> */
+/* Copyright(c) 2016-2017 LoRd_MuldeR <mulder2@gmx.de> */
/* */
/* Permission is hereby granted, free of charge, to any person obtaining a copy of this software */
/* and associated documentation files(the "Software"), to deal in the Software without */
// Const
//-----------------------------------------------------------------------------
-#define HASH_LEN 384
+#define HASH_LEN 384U
-#define DISTANCE_MIN 45
-
-#define ROW_NUM 997 /*total number of rows*/
+#define ROW_NUM 251U /*total number of rows*/
#define ROW_LEN (HASH_LEN / CHAR_BIT) /*number of indices per row*/
+#define DISTANCE_MIN ROW_LEN-2 /*min. hamming distance*/
+
+#undef ENABLE_TRACE
#define __DISTANCE_STR(X) #X
#define _DISTANCE_STR(X) __DISTANCE_STR(X)
// Utility Functions
//-----------------------------------------------------------------------------
+#ifdef ENABLE_TRACE
+#define TRACE(X, ...) printf(X "\n", __VA_ARGS__)
+#else
+#define TRACE(X, ...) __noop()
+#endif
+
static inline void swap(uint8_t *const row_buffer, const size_t a, const size_t b)
{
const uint8_t temp = row_buffer[a];
static inline void swap_multiple_random(twister_t *const rand, uint8_t *const row_buffer, const size_t count)
{
+ const size_t count_min = min(count, ROW_LEN / 2U);
bool map[ROW_LEN];
memset(&map[0], 0, sizeof(bool) * ROW_LEN);
- for (size_t i = 0U; i < count; ++i)
+ for (size_t i = 0U; i < count_min; ++i)
{
size_t a, b;
do
}
}
-static inline uint32_t check_permutation(const size_t index, const uint8_t *const row_buffer)
+static inline uint32_t check_permutation(const size_t index, const uint8_t *const row_buffer, const uint32_t limit)
{
uint32_t error = 0U;
for (size_t i = 0; i < ROW_LEN; ++i)
{
if (row_buffer[i] == ((uint8_t)i))
{
- ++error;
+ if (++error >= limit)
+ {
+ break; /*early termination*/
+ }
}
}
if(error)
}
if (distance < DISTANCE_MIN)
{
- error = max_ui32(error, DISTANCE_MIN - distance);
+ if ((error = max_ui32(error, DISTANCE_MIN - distance)) >= limit)
+ {
+ break; /*early termination*/
+ }
}
}
return error;
fprintf(out, "uint8_t MHASH_384_TABLE_MIX[%u][MHASH_384_LEN] =\n{\n", ROW_NUM);
for (size_t i = 0; i < ROW_NUM; i++)
{
- uint8_t shuffle_indices[ROW_LEN];
- permutation_to_shuffle_indices(&g_table[i][0], &shuffle_indices[0]);
fputs("\t{ ", out);
for (size_t j = 0; j < ROW_LEN; j++)
{
if (j > 0)
{
- fputc(',', out);
+ fputs(", ", out);
}
- fprintf(out, "0x%02X", shuffle_indices[j]);
+ fprintf(out, "0x%02X", g_table[i][j]);
}
fprintf(out, " }%s /*%03u*/\n", (i != (ROW_NUM - 1)) ? "," : " ", (uint32_t)i);
}
success = false;
goto failed;
}
- if (check_permutation(i, &g_table[i][0]) != 0)
+ if (check_permutation(i, &g_table[i][0], 0U) != 0U)
{
printf("ERROR: Table distance verification has failed!\n");
success = false;
for (size_t i = initial_row_index; i < ROW_NUM; ++i)
{
printf("Row %03u of %03u [%c]", (uint32_t)(i + 1U), ROW_NUM, SPINNER[g_spinpos]);
- uint8_t counter = 0U;
- time_t ref_time = time(NULL);
uint8_t temp[ROW_LEN];
+ uint_fast16_t counter = 0U;
for (;;)
{
random_permutation(&rand, &g_table[i][0]);
- uint32_t error = check_permutation(i, &g_table[i][0]);
- printf("\b\b\b[%c]", '!');
- for (uint32_t rand_init = 0U; rand_init < 99991U; ++rand_init)
+ uint32_t error = check_permutation(i, &g_table[i][0], 2U * ROW_LEN);
+ if (!(error > 0U))
{
- random_permutation(&rand, &temp[0]);
- const uint32_t error_next = check_permutation(i, &temp[0]);
- if (error_next < error)
- {
- memcpy(&g_table[i][0], &temp[0], sizeof(uint8_t) * ROW_LEN); /*keep*/
- if (!((error = error_next) > 0U))
- {
- goto success;
- }
- }
+ goto success;
}
- if (error > 0U)
+ for (int_fast16_t retry = 0; retry < 4999; ++retry)
{
- for (size_t retry = 0U; retry < 9973U; ++retry)
+ if (!((++counter) & 0x3F))
{
- bool improved = false;
- for (uint32_t rotate = 0U; rotate < ROW_LEN; ++rotate)
+ printf("\b\b\b[%c]", SPINNER[g_spinpos]);
+ g_spinpos = (g_spinpos + 1) % 4;
+ }
+ for (uint_fast16_t rand_init = 0U; rand_init < 9973U; ++rand_init)
+ {
+ random_permutation(&rand, &temp[0]);
+ const uint32_t error_next = check_permutation(i, &temp[0], error);
+ if (error_next < error)
+ {
+ TRACE("Improved by rand init!");
+ retry = -1;
+ memcpy(&g_table[i][0], &temp[0], sizeof(uint8_t) * ROW_LEN); /*keep*/
+ if (!((error = error_next) > 0U))
+ {
+ goto success;
+ }
+ }
+ for (uint_fast8_t rotate = 0U; rotate < ROW_LEN; ++rotate)
{
- rotate_row(&g_table[i][0]);
- const uint32_t error_next = check_permutation(i, &g_table[i][0]);
+ rotate_row(&temp[0]);
+ const uint32_t error_next = check_permutation(i, &temp[0], error);
if (error_next < error)
{
- improved = true;
+ TRACE("Improved by rotate!");
+ retry = -1;
+ memcpy(&g_table[i][0], &temp[0], sizeof(uint8_t) * ROW_LEN); /*keep*/
if (!((error = error_next) > 0U))
{
goto success;
}
break;
}
- reverse_row(&g_table[i][0]);
- const uint32_t error_next_rev = check_permutation(i, &g_table[i][0]);
- if (error_next_rev >= error)
- {
- reverse_row(&g_table[i][0]); /*revert*/
- }
- else
+ }
+ reverse_row(&temp[0]);
+ const uint32_t error_next_reverse = check_permutation(i, &temp[0], error);
+ if (error_next_reverse < error)
+ {
+ TRACE("Improved by reverse!");
+ retry = -1;
+ memcpy(&g_table[i][0], &temp[0], sizeof(uint8_t) * ROW_LEN); /*keep*/
+ if (!((error = error_next_reverse) > 0U))
{
- improved = true;
- if (!((error = error_next_rev) > 0U))
- {
- goto success;
- }
- break;
+ goto success;
}
+ break;
}
- for (uint32_t swap_x = 0; swap_x < ROW_LEN; ++swap_x)
+ }
+ }
+ if (error > 0U)
+ {
+ static const int_fast16_t MAX_RETRY = 1201;
+ for (int_fast16_t retry = 0; retry < MAX_RETRY; ++retry)
+ {
+ TRACE("Optimizer round %u of %u", retry, MAX_RETRY);
+ if (!retry)
{
- for (uint32_t swap_y = swap_x + 1U; swap_y < ROW_LEN; ++swap_y)
+ rand_init(&rand, make_seed());
+ TRACE("First round!");
+ for (uint_fast8_t swap_x1 = 0; swap_x1 < ROW_LEN; ++swap_x1)
{
- swap(&g_table[i][0], swap_x, swap_y);
- const uint32_t error_next = check_permutation(i, &g_table[i][0]);
- if (error_next >= error)
- {
- swap(&g_table[i][0], swap_x, swap_y); /*revert*/
- }
- else
+ printf("\b\b\b[%c]", SPINNER[g_spinpos]);
+ g_spinpos = (g_spinpos + 1) % 4;
+ for (uint_fast8_t swap_y1 = swap_x1 + 1U; swap_y1 < ROW_LEN; ++swap_y1)
{
- improved = true;
- if (!((error = error_next) > 0U))
+ bool revert_1 = true;
+ swap(&g_table[i][0], swap_x1, swap_y1);
+ const uint32_t error_next = check_permutation(i, &g_table[i][0], error);
+ if (error_next < error)
{
- goto success;
+ TRACE("Improved by swap-1!");
+ revert_1 = false;
+ retry = -1;
+ if (!((error = error_next) > 0U))
+ {
+ goto success;
+ }
+ }
+ for (uint_fast8_t swap_x2 = 0; swap_x2 < ROW_LEN; ++swap_x2)
+ {
+ for (uint_fast8_t swap_y2 = swap_x2 + 1U; swap_y2 < ROW_LEN; ++swap_y2)
+ {
+ bool revert_2 = true;
+ swap(&g_table[i][0], swap_x2, swap_y2);
+ const uint32_t error_next = check_permutation(i, &g_table[i][0], error);
+ if (error_next < error)
+ {
+ TRACE("Improved by swap-2!");
+ revert_1 = revert_2 = false;
+ retry = -1;
+ if (!((error = error_next) > 0U))
+ {
+ goto success;
+ }
+ }
+ for (uint_fast8_t swap_x3 = 0; swap_x3 < ROW_LEN; ++swap_x3)
+ {
+ for (uint_fast8_t swap_y3 = swap_x3 + 1U; swap_y3 < ROW_LEN; ++swap_y3)
+ {
+ swap(&g_table[i][0], swap_x3, swap_y3);
+ const uint32_t error_next = check_permutation(i, &g_table[i][0], error);
+ if (error_next >= error)
+ {
+ swap(&g_table[i][0], swap_x3, swap_y3); /*revert*/
+ }
+ else
+ {
+ TRACE("Improved by swap-3!");
+ revert_1 = revert_2 = false;
+ retry = -1;
+ if (!((error = error_next) > 0U))
+ {
+ goto success;
+ }
+ }
+ }
+ }
+ if (revert_2)
+ {
+ swap(&g_table[i][0], swap_x2, swap_y2); /*revert*/
+ }
+ }
+ }
+ if (revert_1)
+ {
+ swap(&g_table[i][0], swap_x1, swap_y1); /*revert*/
}
}
}
}
- for (uint32_t loop = 0; loop < 99991U; ++loop)
+ const double sigma = 3.14159 * (1.0 + (retry / (double)MAX_RETRY));
+ for (int_fast16_t loop = 0; loop < 9973U; ++loop)
{
- const uint32_t swap_count = gaussian_noise_next(&rand, &bxmller, 8.0, 2U, (ROW_LEN / 2U));
- if (!(++counter))
+ const uint32_t swap_count = gaussian_noise_next(&rand, &bxmller, sigma, 4U, (ROW_LEN / 2U));
+ if (!((++counter) & 0x3FFF))
{
- const time_t curr_time = time(NULL);
- if (curr_time - ref_time >= 180i64)
- {
- ref_time = curr_time;
- rand_init(&rand, make_seed());
- printf("\b\b\b[%c]", '$');
- }
- else
- {
- printf("\b\b\b[%c]", SPINNER[g_spinpos]);
- g_spinpos = (g_spinpos + 1) % 4;
- }
+ printf("\b\b\b[%c]", SPINNER[g_spinpos]);
+ g_spinpos = (g_spinpos + 1) % 4;
}
- for (uint32_t round = 0; round < 97U; ++round)
+ for (int_fast16_t round = 0; round < 997U; ++round)
{
memcpy(&temp[0], &g_table[i][0], sizeof(uint8_t) * ROW_LEN);
swap_multiple_random(&rand, &temp[0], swap_count);
- const uint32_t error_next = check_permutation(i, &temp[0]);
+ const uint32_t error_next = check_permutation(i, &temp[0], error);
if (error_next < error)
{
+ TRACE("Improved by swap-n (%u)!", swap_count);
memcpy(&g_table[i][0], &temp[0], sizeof(uint8_t) * ROW_LEN); /*keep*/
- improved = true;
+ retry = -1;
if (!((error = error_next) > 0U))
{
goto success;
}
}
}
- if (!improved)
- {
- break; /*early termination*/
- }
}
}
else
}
success:
+ if (check_permutation(i, &g_table[i][0], 2U * ROW_LEN))
+ {
+ fprintf(stderr, "ERROR MISCOMPARE!\n");
+ abort();
+ }
+
get_time_str(time_string, 64);
printf("\b\b\b[#] - %s\n", time_string);
OSDN Git Service
