Simplified generation of the MIX table.

diff --git a/tools/GenTables/include/common.h b/tools/GenTables/include/common.h
index a399c80..dd83d70 100644 (file)
--- a/tools/GenTables/include/common.h
+++ b/tools/GenTables/include/common.h
@@ -29,6 +29,23 @@ static inline uint32_t make_seed(void)
        return seed;
 }
 
+static inline invert_byte_buffer(uint8_t *const buffer, const size_t size)
+{
+       const size_t words = size / sizeof(uint32_t);
+       const size_t bytes = size % sizeof(uint32_t);
+       uint8_t *pos = buffer;
+       for (size_t i = 0; i < words; ++i)
+       {
+               *((uint32_t*)pos) = (~(*((uint32_t*)pos)));
+               pos += sizeof(uint32_t);
+       }
+       for (size_t i = 0; i < bytes; ++i)
+       {
+               *pos = (~(*pos));
+               pos += sizeof(uint8_t);
+       }
+}
+
 static inline uint32_t hamming_distance(const uint8_t *const a, const uint8_t *const b, const size_t len)
 {
        uint32_t distance = 0U;

diff --git a/tools/GenTables/src/gen_table_mix.c b/tools/GenTables/src/gen_table_mix.c
index e6d9bbc..0e8f932 100644 (file)
--- a/tools/GenTables/src/gen_table_mix.c
+++ b/tools/GenTables/src/gen_table_mix.c
@@ -26,6 +26,7 @@
 #include <stdint.h>
 #include <string.h>
 #include <time.h>
+#include <stdbool.h>
 
 //-----------------------------------------------------------------------------
 // Const
@@ -33,162 +34,74 @@
 
 #define HASH_LEN 384
 
-#define DISTANCE_MIN 46
-#define DISTANCE_MAX 48
-
-#define THREAD_COUNT 8
-
-#define BYTE_LEN (HASH_LEN / (8 * sizeof(uint8_t)))
-#define __DISTANCE_STR(X) #X
-#define _DISTANCE_STR(X) __DISTANCE_STR(X)
-#define DISTANCE_STR _DISTANCE_STR(DISTANCE_MIN)
+#define ROW_NUM (UINT8_MAX+1)           /*total number of rows*/
+#define ROW_LEN (HASH_LEN / CHAR_BIT)   /*number of bits per row*/
 
 //-----------------------------------------------------------------------------
 // Globals
 //-----------------------------------------------------------------------------
 
-static uint8_t g_table[UINT8_MAX+1][BYTE_LEN-1];
-static uint8_t g_mixed[UINT8_MAX+1][BYTE_LEN];
-static uint8_t g_ordered[BYTE_LEN];
-static size_t g_spinpos = 0;
-static char SPINNER[4] = { '/', '-', '\\', '|' };
+static uint8_t g_table[ROW_NUM][HASH_LEN];
 
 //-----------------------------------------------------------------------------
 // Utility Functions
 //-----------------------------------------------------------------------------
 
-static inline void apply_permutation(const uint8_t *const permut, uint8_t *const data)
-{
-       uint8_t temp;
-       for (size_t i = 0; i < BYTE_LEN - 1; i++)
-       {
-               const uint8_t j = permut[i];
-               temp = data[i];
-               data[i] = data[j];
-               data[j] = temp;
-       }
-}
-
 static inline void build_permutation(uint8_t *const row_buffer, twister_t *const rand)
 {
-       for (uint32_t i = 0; i < BYTE_LEN - 1; i++)
+       for (uint32_t i = 0; i < ROW_LEN; i++)
        {
-               row_buffer[i] = (uint8_t)(i + (next_rand_range(rand, BYTE_LEN - i)));
+               row_buffer[i] = (uint8_t)(i + (next_rand_range(rand, ROW_LEN - i)));
        }
 }
 
-static uint32_t compute_distance(const uint8_t *const a, const uint8_t *const b)
+static inline void apply_permutation(uint8_t *const row_buffe, const uint8_t *const permutation)
 {
-       uint32_t distance = 0;
-       for (int i = 0; i < BYTE_LEN; i++)
+       for (size_t i = 0; i < ROW_LEN; ++i)
        {
-               if (a[i] != b[i])
-               {
-                       distance++;
-               }
+               const uint8_t tmp = row_buffe[i];
+               row_buffe[i] = row_buffe[permutation[i]];
+               row_buffe[permutation[i]] = tmp;
        }
-       return distance;
 }
 
-static inline int check_distance(const size_t index, const uint8_t *const row_buffer)
+static inline bool test_permutation(const uint8_t *const permutation)
 {
-       uint8_t temp_mixed[BYTE_LEN];
-       memcpy(temp_mixed, g_ordered, sizeof(uint8_t) * BYTE_LEN);
-       apply_permutation(row_buffer, temp_mixed);
-       for (size_t k = 0; k < BYTE_LEN; k++)
+       uint8_t row_buffe[ROW_LEN];
+       for (size_t i = 0; i < ROW_LEN; ++i)
        {
-               if (temp_mixed[k] == ((uint8_t)k))
-               {
-                       return 0;
-               }
+               row_buffe[i] = ((uint8_t)i);
        }
-       for (size_t k = 0; k < index; k++)
-       {
-               const uint32_t dist = compute_distance(&g_mixed[k][0], temp_mixed);
-               if ((dist > DISTANCE_MAX) || (dist < DISTANCE_MIN))
-               {
-                       return 0;
-               }
-       }
-       return 1;
-}
 
-static dump_table(FILE *out)
-{
-       for (size_t i = 0; i < UINT8_MAX+1; i++)
+       apply_permutation(row_buffe, permutation);
+       for (size_t i = 0; i < ROW_LEN; ++i)
        {
-               fprintf(out, "%02X: ", (uint32_t)(i & 0xFF));
-               for (size_t j = 0; j < BYTE_LEN-1; j++)
+               if (row_buffe[i] == ((uint8_t)i))
                {
-                       fprintf(out, "0x%02X,", g_table[i][j]);
+                       return false;
                }
-               fprintf(out, "\n");
        }
-}
 
-//-----------------------------------------------------------------------------
-// Thread function
-//-----------------------------------------------------------------------------
-
-typedef struct
-{
-       size_t index;
-       uint8_t *row_buffer;
-       sem_t *stop;
-       pthread_mutex_t *mutex;
-       twister_t *rand;
+       return true;
 }
-thread_data_t;
 
-static void* thread_main(void *const param)
+static dump_table(FILE *out)
 {
-       const thread_data_t *const data = ((const thread_data_t*)param);
-       uint16_t check_cnt = 0;
-       do
+       fputs("uint8_t MHASH_384_TABLE_MIX[UINT8_MAX+1][MHASH_384_LEN] =\n{\n", out);
+       for (size_t i = 0; i < ROW_NUM; i++)
        {
-               if (++check_cnt == 0)
+               fputs("\t{ ", out);
+               for (size_t j = 0; j < ROW_LEN; j++)
                {
-                       if (SEM_TRYWAIT(data->stop))
+                       if (j > 0)
                        {
-                               return NULL;
+                               fputc(',', out);
                        }
+                       fprintf(out, "0x%02X", g_table[i][j]);
                }
-               build_permutation(data->row_buffer, data->rand);
-       } 
-       while (!check_distance(data->index, data->row_buffer));
-       
-       MUTEX_LOCK(data->mutex);
-       if (SEM_TRYWAIT(data->stop))
-       {
-               MUTEX_UNLOCK(data->mutex);
-               return NULL;
-       }
-       SEM_POST(data->stop, THREAD_COUNT);
-       MUTEX_UNLOCK(data->mutex);
-       return ((void*)1);
-}
-
-static void* thread_spin(void *const param)
-{
-       unsigned long delay = 0;
-       sem_t *const stop = ((sem_t*)param);
-       for (;;)
-       {
-               if (SEM_TRYWAIT(stop))
-               {
-                       return NULL;
-               }
-               _sleep(delay);
-               if (delay >= 1000)
-               {
-                       printf("\b\b\b[%c]", SPINNER[g_spinpos]);
-                       g_spinpos = (g_spinpos + 1) % 4;
-               }
-               else
-               {
-                       delay = (delay > 0) ? (2 * delay) : 1;
-               }
+               fprintf(out, " }%s /*%02X*/\n", (i != (ROW_NUM - 1)) ? "," : " ", (uint32_t)(i % 0x100));
        }
+       fputs("};\n", out);
 }
 
 //-----------------------------------------------------------------------------
@@ -197,81 +110,34 @@ static void* thread_spin(void *const param)
 
 int main()
 {
-       pthread_t thread_id[THREAD_COUNT + 1];
-       uint8_t thread_buffer[THREAD_COUNT][BYTE_LEN-1];
-       thread_data_t thread_data[THREAD_COUNT];
-       twister_t thread_rand[THREAD_COUNT];
-       sem_t stop_flag;
-       pthread_mutex_t stop_mutex;
        FILE *file_out = NULL;
 
        printf("MHash GenTableMIX [%s]\n\n", __DATE__);
-       printf("HashLen: %d, Distance Min/Max: %d/%d, Threads: %d\n\n", HASH_LEN, DISTANCE_MIN, DISTANCE_MAX, THREAD_COUNT);
+       printf("HashLen: %d\n\n", HASH_LEN);
 
        if ((HASH_LEN % (8 * sizeof(uint32_t))) != 0)
        {
                crit_exit("FATAL: Hash length must be a multiple of 32 bits!");
        }
 
-       for (size_t i = 0; i < BYTE_LEN; i++)
-       {
-               g_ordered[i] = (uint8_t)(i);
-       }
-       for (size_t i = 0; i < UINT8_MAX+1; i++)
-       {
-               memset(&g_table[i][0], 0, sizeof(uint8_t) * (BYTE_LEN - 1));
-               memcpy(&g_mixed[i][0], g_ordered, sizeof(uint8_t) * BYTE_LEN);
-       }
+       twister_t rand;
+       rand_init(&rand, make_seed());
 
-       memset(&thread_id, 0, sizeof(pthread_t) * (THREAD_COUNT + 1));
-       memset(&thread_data, 0, sizeof(thread_data_t) * THREAD_COUNT);
-       for (size_t t = 0; t < THREAD_COUNT; t++)
+       for (size_t i = 0; i < ROW_NUM; ++i)
        {
-               memset(&thread_buffer[t][0], 0, sizeof(uint8_t) * (BYTE_LEN-1));
-               rand_init(&thread_rand[t], make_seed());
-       }
-
-       SEM_INIT(&stop_flag);
-       MUTEX_INIT(&stop_mutex);
-
-       for (size_t i = 0; i < UINT8_MAX+1; i++)
-       {
-               uint32_t round = 0, minimum_distance = 0;
-               char time_string[64];
-
-               printf("Row %03u of %03u [%c]", (uint32_t)(i+1), UINT8_MAX+1, SPINNER[g_spinpos]);
-               g_spinpos = (g_spinpos + 1) % 4;
-
-               PTHREAD_CREATE(&thread_id[THREAD_COUNT], NULL, thread_spin, &stop_flag);
-               for (size_t t = 0; t < THREAD_COUNT; t++)
+               printf("Row %03u of %03u... ", (uint32_t)(i + 1U), ROW_NUM);
+               do
                {
-                       thread_data[t].index = i;
-                       thread_data[t].row_buffer = &thread_buffer[t][0];
-                       thread_data[t].stop = &stop_flag;
-                       thread_data[t].mutex = &stop_mutex;
-                       thread_data[t].rand = &thread_rand[t];
-                       PTHREAD_CREATE(&thread_id[t], NULL, thread_main, &thread_data[t]);
+                       build_permutation(&g_table[i][0], &rand);
                }
-
-               for (size_t t = 0; t < THREAD_COUNT; t++)
-               {
-                       void *return_value = NULL;
-                       PTHREAD_JOIN(thread_id[t], &return_value);
-                       if (return_value)
-                       {
-                               memcpy(&g_table[i][0], &thread_buffer[t][0], sizeof(uint8_t) * (BYTE_LEN-1));
-                               apply_permutation(&g_table[i][0], &g_mixed[i][0]);
-                       }
-               }
-               PTHREAD_JOIN(thread_id[THREAD_COUNT], NULL);
-               get_time_str(time_string, 64);
-               printf("\b\b\b[#] - %s\n", time_string);
+               while(!test_permutation(&g_table[i][0]));
+               puts("done");
        }
 
        printf("\n-----\n\n");
 
        dump_table(stdout);
-       if (fopen_s(&file_out, "table_out." DISTANCE_STR ".txt", "w") == 0)
+       if (fopen_s(&file_out, "table_out.MIX.txt", "w") == 0)
        {
                dump_table(file_out);
                fclose(file_out);
@@ -279,52 +145,6 @@ int main()
 
        printf("\n-----\n\n");
 
-       for (size_t i = 0; i < UINT8_MAX+1; i++)
-       {
-               int complete = 0;
-               for (size_t j = 0; j < BYTE_LEN; j++)
-               {
-                       for (size_t k = 0; k < BYTE_LEN; k++)
-                       {
-                               if (g_mixed[i][k] == g_ordered[j])
-                               {
-                                       complete++;
-                               }
-                       }
-               }
-               if (complete != BYTE_LEN)
-               {
-                       crit_exit("FATAL: Table verification has failed!");
-               }
-               for (size_t j = 0; j < UINT8_MAX+1; j++)
-               {
-                       uint8_t a[BYTE_LEN], b[BYTE_LEN];
-                       if (i == j)
-                       {
-                               continue;
-                       }
-                       memcpy(a, g_ordered, sizeof(uint8_t) * BYTE_LEN);
-                       memcpy(b, g_ordered, sizeof(uint8_t) * BYTE_LEN);
-                       apply_permutation(&g_table[i][0], a);
-                       apply_permutation(&g_table[j][0], b);
-                       const uint32_t dist = compute_distance(a, b);
-                       if ((dist > DISTANCE_MAX) || (dist < DISTANCE_MIN))
-                       {
-                               crit_exit("FATAL: Table verification has failed!");
-                       }
-               }
-       }
-       for (size_t i = 0; i < BYTE_LEN; i++)
-       {
-               if (g_ordered[i] != (uint8_t)(i))
-               {
-                       crit_exit("FATAL: Ordering verification has failed!");
-               }
-       }
-
-       SEM_DESTROY(&stop_flag);
-       MUTEX_DESTROY(&stop_mutex);
-
        printf("COMPLETED.\n\n");
        return getchar();
 }

diff --git a/tools/GenTables/src/gen_table_xor.c b/tools/GenTables/src/gen_table_xor.c
index 8bf1f66..a913178 100644 (file)
--- a/tools/GenTables/src/gen_table_xor.c
+++ b/tools/GenTables/src/gen_table_xor.c
@@ -63,7 +63,14 @@ static char SPINNER[4] = { '/', '-', '\\', '|' };
 // Utility Functions
 //-----------------------------------------------------------------------------
 
-static inline bool check_distance(const size_t index, const uint8_t *const row_buffer)
+
+static inline bool check_distance_rows(const size_t index_1, const size_t index_2)
+{
+       const uint32_t dist = hamming_distance(&g_table[index_1][0], &g_table[index_2][0], ROW_LEN);
+       return (dist <= DISTANCE_MAX) && (dist >= DISTANCE_MIN);
+}
+
+static inline bool check_distance_next(const size_t index, const uint8_t *const row_buffer)
 {
        for (size_t k = 0; k < index; k++)
        {
@@ -78,15 +85,21 @@ static inline bool check_distance(const size_t index, const uint8_t *const row_b
 
 static dump_table(FILE *out)
 {
+       fputs("uint8_t MHASH_384_TABLE_XOR[UINT8_MAX+2][MHASH_384_LEN] =\n{\n", out);
        for (size_t i = 0; i < ROW_NUM; i++)
        {
-               fprintf(out, "%02X: ", (uint32_t)(i & 0xFF));
+               fputs("\t{ ", out);
                for (size_t j = 0; j < ROW_LEN; j++)
                {
-                       fprintf(out, "0x%02X,", g_table[i][j]);
+                       if (j > 0)
+                       {
+                               fputc(',', out);
+                       }
+                       fprintf(out, "0x%02X", g_table[i][j]);
                }
-               fprintf(out, "\n");
+               fprintf(out, " }%s /*%02X*/\n", (i != (ROW_NUM - 1)) ? "," : " ", (uint32_t)(i % 0x100));
        }
+       fputs("};\n", out);
 }
 
 //-----------------------------------------------------------------------------
@@ -106,19 +119,26 @@ thread_data_t;
 static void* thread_main(void *const param)
 {
        const thread_data_t *const data = ((const thread_data_t*)param);
-       uint16_t check_cnt = 0;
+       uint16_t counter = 0;
        do
        {
-               if (++check_cnt == 0)
+               if ((++counter) == 0)
                {
                        if (SEM_TRYWAIT(data->stop))
                        {
                                return NULL;
                        }
                }
-               rand_next_bytes(data->rand, data->row_buffer, ROW_LEN);
-       } 
-       while (!check_distance(data->index, data->row_buffer));
+               if (counter & 1U)
+               {
+                       rand_next_bytes(data->rand, data->row_buffer, ROW_LEN);
+               }
+               else
+               {
+                       invert_byte_buffer(data->row_buffer, ROW_LEN);
+               }
+       }
+       while (!check_distance_next(data->index, data->row_buffer));
        
        MUTEX_LOCK(data->mutex);
        if (SEM_TRYWAIT(data->stop))
@@ -126,6 +146,7 @@ static void* thread_main(void *const param)
                MUTEX_UNLOCK(data->mutex);
                return NULL;
        }
+
        SEM_POST(data->stop, THREAD_COUNT);
        MUTEX_UNLOCK(data->mutex);
        return data->row_buffer;
@@ -240,8 +261,7 @@ static bool load_table_data(const wchar_t *const filename, size_t *const rows_co
                        }
                        for (size_t j = 0; j < i; j++)
                        {
-                               const uint32_t dist = hamming_distance(&g_table[i][0], &g_table[j][0], ROW_LEN);
-                               if ((dist > DISTANCE_MAX) || (dist < DISTANCE_MIN))
+                               if (!check_distance_rows(i, j))
                                {
                                        printf("ERROR: Table distance verification has failed!\n");
                                        success = false;
@@ -375,8 +395,7 @@ int wmain(int argc, wchar_t *argv[])
                        {
                                continue;
                        }
-                       const uint32_t dist = hamming_distance(&g_table[i][0], &g_table[j][0], ROW_LEN);
-                       if ((dist > DISTANCE_MAX) || (dist < DISTANCE_MIN))
+                       if (!check_distance_rows(i, j))
                        {
                                crit_exit("FATAL: Table verification has failed!");
                        }