fix.patch

From 5b7e17417e31e52f5920608399d20696b03b87e6 Mon Sep 17 00:00:00 2001
From: Cattalyya Nuengsigkapian <cattalyy@mit.edu>
Date: Sat, 14 Sep 2019 23:01:46 -0400
Subject: [PATCH] [Fix] Speed up overhead in tiers testing. Fix malloc issue if
 size is too large. Fix index overflow (32b to 64b) for very large size
 matrix.

---
 utils/libbmp.c |  5 +++++
 utils/main.c   | 13 +++++++++----
 utils/tester.c | 37 ++++++++++++++++++-------------------
 utils/utils.c  | 32 +++++++++++++++++++++-----------
 4 files changed, 53 insertions(+), 34 deletions(-)

diff --git a/utils/libbmp.c b/utils/libbmp.c
index 85fc63e..7e8f685 100644
--- a/utils/libbmp.c
+++ b/utils/libbmp.c
@@ -112,6 +112,11 @@ uint8_t *read_binary_bmp(const char *fname, int *_w, int *_h, int *_row_size,
   uint8_t *ret_img = malloc(info_header.height * row_size);
   uint8_t *image_data = malloc(image_size);
 
+  if (!ret_img || !image_data) {
+    printf("Error: Image size is too large to fit in heap space!\n");
+    assert(false);
+  }
+
   // Offset to and read the image data
   fseek(f, header.data_offset, SEEK_SET);
   if (!fread(image_data, 1, image_size, f)) {
diff --git a/utils/main.c b/utils/main.c
index 1a65bab..3a1b118 100644
--- a/utils/main.c
+++ b/utils/main.c
@@ -199,15 +199,20 @@ int main(int argc, char *argv[]) {
   case TEST_TIERS:
   {
     uint32_t TIER_TIMEOUT = 3000;
-    uint32_t TIMEOUT = 50000;
+    uint32_t TIMEOUT = 58000;
     bits_t START_SIZE = 26624;
     double GROWTH_RATE = 1.1;
 
     uint32_t tier = run_tester_tiers(rotate_bit_matrix, TIER_TIMEOUT, TIMEOUT, START_SIZE, GROWTH_RATE);
-    if (tier == -1)
+    if (tier == -1) {
         printf("FAIL: too slow for large tiers\n");
-    else
-        printf("Result: reached tier %d\n", tier);
+    } else {
+        if (tier == 19) {
+            printf("Congrats! You reach the highest tiers %d :)\n", tier);
+        } else {
+            printf("Result: reached tier %d\n", tier);
+        }
+    }
 
     break;
   }
diff --git a/utils/tester.c b/utils/tester.c
index f86663d..4391ed0 100644
--- a/utils/tester.c
+++ b/utils/tester.c
@@ -26,9 +26,8 @@
 #include <signal.h>
 #include <unistd.h>
 
-void exitfunc(int sig)
-{
-    printf("End execution due to 50s timeout\n");
+void exitfunc(int sig) {
+    printf("End execution due to 58s timeout\n");
     exit(0);
 }
 
@@ -280,13 +279,18 @@ bool run_tester_generated_bit_matrix(void (*rotate_fn)(uint8_t*,
 // Returns the tier number that `rotate_fn` got to
 //
 uint32_t run_tester_tiers(void (*rotate_fn)(uint8_t*, const bits_t),
-                          uint32_t tier_timeout, uint32_t timeout, 
+                          uint32_t tier_timeout, uint32_t timeout,
                           bits_t start_n, double increasing_ratio_of_n) {
-
+  // set timer
   uint32_t MS_TO_SEC = 1000;
   signal(SIGALRM, exitfunc);
   alarm((uint32_t)(timeout / MS_TO_SEC));
 
+  printf("Setting up tests ...\n");
+  // generate random matrix
+  uint64_t MAX_SIZE_N = 164416;
+  uint8_t *bit_matrix = generate_bit_matrix(MAX_SIZE_N);
+
   // Sanity check the input
   assert(rotate_fn);
 
@@ -301,10 +305,9 @@ uint32_t run_tester_tiers(void (*rotate_fn)(uint8_t*, const bits_t),
 
   uint32_t tier = 0;
 
+  printf("Start tiers testing\n");
   // Be sure to increase the matrix dimension on every iteration
-  for (;; N = (uint64_t) ceil(N * increasing_ratio_of_n / 64) * 64) {
-    uint8_t *bit_matrix = generate_bit_matrix(N);
-
+  for (; N <= MAX_SIZE_N; N = (uint64_t) ceil(N * increasing_ratio_of_n / 64) * 64) {
     // Call the user-defined `rotate_fn` and time it
     clock_t start = clock();
     rotate_fn(bit_matrix, N);
@@ -313,14 +316,10 @@ uint32_t run_tester_tiers(void (*rotate_fn)(uint8_t*, const bits_t),
     // Compute the user time in milliseconds
     uint32_t user_msec = user_diff * 1000 / CLOCKS_PER_SEC;
 
-    // Clean up after ourselves!
-    free(bit_matrix);
-
     // Exit if the user time is too much, but was still correct!
     if (user_msec >= tier_timeout) {
       printf("FAIL (timeout) : Tier %d : rotated %zux%zu matrix once in (%d >= %d) milliseconds\n",
              tier, N, N, user_msec, tier_timeout);
-
       // Exit!
       goto finish;
     } else {  // Success
@@ -337,6 +336,8 @@ uint32_t run_tester_tiers(void (*rotate_fn)(uint8_t*, const bits_t),
   }
 
   finish:
+    // Clean up after ourselves!
+    free(bit_matrix);
     // Save the highest tier and best runtime
     // in their respective return fields
     return tier - 1;
@@ -367,7 +368,7 @@ bool run_correctness_tester(void (*rotate_fn)(uint8_t*, const bits_t),
   const double SQRT_GOLDEN_RATIO = 1.2720196495141103;
 
   // Be sure to increase the matrix dimension on every iteration
-  for (;N < 10000; N = (uint64_t) ceil(N * SQRT_GOLDEN_RATIO / 64) * 64) {
+  for (; N < 10000; N = (uint64_t) ceil(N * SQRT_GOLDEN_RATIO / 64) * 64) {
     uint32_t i;
     uint8_t *bit_matrix = generate_bit_matrix(N);
     uint8_t *bit_matrix_copy = copy_bit_matrix(bit_matrix, N);
@@ -377,7 +378,6 @@ bool run_correctness_tester(void (*rotate_fn)(uint8_t*, const bits_t),
     const char *english_multiples[] = {"once", "twice", "three times"};
     uint32_t user_msec = 0;
     for (i = 0; i < 3; i++, tier++) {
-
       // Call the user-defined `rotate_fn` and time it
       clock_t start = clock();
       rotate_fn(bit_matrix, N);
@@ -386,12 +386,12 @@ bool run_correctness_tester(void (*rotate_fn)(uint8_t*, const bits_t),
       // Compute the user time in milliseconds
       user_msec += user_diff * 1000 / CLOCKS_PER_SEC;
 
-      // Checking correctness - Call our stock rotation function on bit_matrix 
+      // Checking correctness - Call our stock rotation function on bit_matrix
       _rotate_bit_matrix(bit_matrix_copy, N);
       correctness = memcmp(bit_matrix, bit_matrix_copy, bit_matrix_size) == 0;
 
-      if(!correctness) { // The rotation was not correct
-        printf("FAIL : Test %d : Incorrectly rotated %zux%zu matrix\n", 
+      if (!correctness) {  // The rotation was not correct
+        printf("FAIL : Test %d : Incorrectly rotated %zux%zu matrix\n",
                tier, N, N);
 
         // Exit!
@@ -404,9 +404,8 @@ bool run_correctness_tester(void (*rotate_fn)(uint8_t*, const bits_t),
 
       const char *random_celebration = celebrations[rand() % ncelebrations];
 
-      printf("PASS (%s!): Test %d : Rotated %zux%zu matrix %s in %d milliseconds\n", 
+      printf("PASS (%s!): Test %d : Rotated %zux%zu matrix %s in %d milliseconds\n",
              random_celebration, tier, N, N, english_multiples[i], user_msec);
-
     }
     // Clean up after ourselves!
     free(bit_matrix);
diff --git a/utils/utils.c b/utils/utils.c
index 7a4883d..b7347f9 100644
--- a/utils/utils.c
+++ b/utils/utils.c
@@ -21,6 +21,7 @@
  **/
 
 #include "./utils.h"
+#include <string.h>
 
 // Calculates the number of bytes required to hold `nbits` bits
 inline bytes_t bits_to_bytes(bits_t nbits) {
@@ -31,7 +32,7 @@ inline bytes_t bits_to_bytes(bits_t nbits) {
 //
 // The `row_size` are the number of bytes per row in `img`
 uint8_t get_bit(uint8_t *img, const bytes_t row_size, uint32_t i, uint32_t j) {
-  uint32_t byte_offset = j * row_size + (i / 8);
+  uint64_t byte_offset = j * row_size + (i / 8);
   uint8_t byte_mask = 0b10000000 >> (i % 8);
 
   uint8_t *img_byte = img + byte_offset;
@@ -46,7 +47,7 @@ void set_bit(uint8_t *img, const bytes_t row_size, uint32_t i, uint32_t j, uint8
   // Sanity check the input
   assert(value == 0 || value == 1);
 
-  uint32_t byte_offset = j * row_size + (i / 8);
+  uint64_t byte_offset = j * row_size + (i / 8);
   uint8_t byte_mask = 0b10000000 >> (i % 8);
 
   uint8_t *img_byte = img + byte_offset;
@@ -85,16 +86,24 @@ void print_bit_matrix(uint8_t *bit_matrix, const bits_t N, int32_t ncolumns) {
 uint8_t *generate_bit_matrix(const bits_t N) {
   // Sanity check the input
   assert(N > 0);
-  assert(!(N % 8));
+  assert(!(N % 64));
 
   bytes_t nbytes = bits_to_bytes(N);
 
   uint8_t *ret;
   ret = malloc(nbytes * N);
+  if (!ret) {
+    printf("Error: Run out of heap space! Please try smaller matrix size.\n");
+    assert(false);
+  }
 
-  uint32_t i;
-  for (i = 0; i < nbytes * N; i++) {
-    *(ret + i) = rand() % 256;
+  uint64_t i;
+  uint64_t* pt = (uint64_t *)ret;
+  for (i = 0; i < nbytes * nbytes; i++) {
+    *(pt + i) = ((uint64_t)rand() % 65536)
+        + (((uint64_t)rand() % 65536) << 16)
+        + (((uint64_t)rand() % 65536) << 32)
+        + (((uint64_t)rand() % 65536) << 48);
   }
 
   return ret;
@@ -103,18 +112,19 @@ uint8_t *generate_bit_matrix(const bits_t N) {
 uint8_t *copy_bit_matrix(uint8_t *bit_matrix, const bits_t N) {
   // Sanity check the input
   assert(N > 0);
-  assert(!(N % 8));
+  assert(!(N % 64));
 
   bytes_t nbytes = bits_to_bytes(N);
 
   uint8_t *ret;
   ret = malloc(nbytes * N);
+  if (!ret) {
+    printf("Error: Run out of heap space! Please try smaller matrix size.\n");
+    assert(false);
+  }
 
   // Copy the `bit_matrix`
-  uint32_t i;
-  for (i = 0; i < nbytes * N; i++) {
-    *(ret + i) = *(bit_matrix + i);
-  }
+  memcpy(ret, bit_matrix, nbytes * N);
 
   return ret;
 }
-- 
2.17.1