src/tests/test_fastlz_pos.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <time.h>
   6 #include <unistd.h>
   7
   8 #include "logcommon.h" // for NELEMS
   9 #include "fastlz.h"
  10
  11 // The string to compress.
  12 static const char *duplicate_string = "Did you ever hear the tragedy of darth plagueis the wise?";
  13 static const char *fuzzable_string = "Ala ma kota";
  14 static const char *random_string = "fdffdfdfddfdfdfdd";
  15
  16 size_t wrapper_compress(char *in, size_t size_in, char *out)
  17 {
  18         clock_t begin = clock();
  19         size_t ret = fastlz_compress(in, size_in, out);
  20         clock_t end = clock();
  21         double timer = (double)(end - begin) / CLOCKS_PER_SEC;
  22         printf("Comp time spent: %lf, size:%zu, size_compressed:%zu\n", timer, size_in, ret);
  23         return ret;
  24 }
  25
  26 /* in - compressed data | out - output */
  27 size_t wrapper_decompress(char *in, size_t size_in, char *out, size_t size_out)
  28 {
  29         clock_t begin = clock();
  30         size_t ret = fastlz_decompress(in, size_in, out, size_out);
  31         clock_t end = clock();
  32         double timer = (double)(end - begin) / CLOCKS_PER_SEC;
  33         printf("Decomp time spent: %lf, size:%zu, size_decompressed:%zu\n", timer, size_in, ret);
  34         return ret;
  35 }
  36
  37 void modify_one_letter(char *str, size_t begin, size_t end)
  38 {
  39         str[begin + rand() % (end - begin)] = 'a' + rand() % 26;
  40 }
  41
  42 char *copy_string(size_t calloc_size, size_t copy_size, const char *source, bool apply_fuzzing)
  43 {
  44         const size_t source_len = strlen(source);
  45
  46         assert(source);
  47         assert(copy_size > 0);
  48         assert(calloc_size > 0);
  49         assert(calloc_size >= copy_size);
  50
  51         int repeats_num = copy_size / source_len;
  52         assert(repeats_num > 0);
  53
  54         char *result = calloc(1, calloc_size);
  55         assert(result);
  56
  57         for (int i = 0; i < repeats_num; ++i) {
  58                 memcpy(result + i * source_len, source, source_len);
  59                 if (apply_fuzzing)
  60                         modify_one_letter(result, i * source_len, (i + 1) * source_len);
  61         }
  62
  63         return result;
  64 }
  65
  66 void test_duplicate_string(size_t size)
  67 {
  68         /* place for "ffdfdfd", one closing sentence and '\0'*/
  69         const size_t extras = sizeof '\0' + strlen(random_string) + strlen(duplicate_string);
  70         assert(size >= extras);
  71         size_t temp_size = size;
  72         temp_size -= extras;
  73         char *in = copy_string(size, temp_size, duplicate_string, false);
  74
  75         assert(in);
  76
  77         strcat(in, random_string);
  78         strcat(in, duplicate_string);
  79
  80         size_t src_len = strlen(in);
  81         char *out = malloc(FASTLZ_NEEDED_OUTPUT_SIZE(src_len));
  82         char *re = malloc(src_len);
  83
  84         assert(out);
  85         assert(re);
  86
  87         size_t compressed_size = wrapper_compress(in, src_len, out);
  88         assert(compressed_size);
  89
  90         size_t restored_size = wrapper_decompress(out, compressed_size, re, src_len);
  91         assert(restored_size == src_len);
  92         for (size_t i = 0; i < src_len; ++i)
  93                 assert(re[i] == in[i]);
  94
  95         free(out);
  96         free(re);
  97         free(in);
  98 }
  99
 100 void test_zeroes(size_t size)
 101 {
 102         char *in = calloc(size, 1);
 103         char *out = malloc(FASTLZ_NEEDED_OUTPUT_SIZE(size));
 104         char *re = malloc(size);
 105
 106         assert(in);
 107         assert(out);
 108         assert(re);
 109
 110         size_t compressed_size = wrapper_compress(in, size, out);
 111         assert(compressed_size);
 112         assert(compressed_size < 1024); // literally just zeroes, shouldn't take more than 1kB ever
 113
 114         size_t restored_size = wrapper_decompress(out, compressed_size, re, size);
 115         assert(restored_size == size);
 116         for (size_t i = 0; i < size; ++i)
 117                 assert(re[i] == in[i]);
 118
 119         free(in);
 120         free(out);
 121         free(re);
 122 }
 123
 124 void test_01(size_t size)
 125 {
 126         char *in = malloc(size);
 127         char *out = malloc(FASTLZ_NEEDED_OUTPUT_SIZE(size));
 128         char *re = malloc(size);
 129
 130         assert(in);
 131         assert(out);
 132         assert(re);
 133
 134         /* Produce something like 010100101000111...
 135          * Note that the algorithm works at the level
 136          * of bytes, not bits, so these being mostly
 137          * composed of zero-bits doesn't matter much. */
 138         for (size_t i = 0; i < size; ++i)
 139                 in[i] = rand() % 2;
 140
 141         size_t compressed_size = wrapper_compress(in, size, out);
 142         assert(compressed_size);
 143         assert(compressed_size < size * 0.52); // about half, plus a bit of overhead
 144
 145         size_t restored_size = wrapper_decompress(out, compressed_size, re, size);
 146         assert(restored_size == size);
 147         for (size_t i = 0; i < size; ++i)
 148                 assert(re[i] == in[i]);
 149
 150         free(in);
 151         free(out);
 152         free(re);
 153 }
 154
 155 void test_alpha_weighted(size_t size)
 156 {
 157         char *in = malloc(size);
 158         char *out = malloc(FASTLZ_NEEDED_OUTPUT_SIZE(size));
 159         char *re = malloc(size);
 160
 161         assert(in);
 162         assert(out);
 163         assert(re);
 164
 165         /* Produce a random string with letters weighted
 166          * by their ~actual English frequencies. */
 167         static const struct letter {
 168                 char letter;
 169                 size_t freq;
 170         } letters[] =
 171                 {{'E', 13}
 172                 ,{'T', 10}
 173                 ,{'A',  8}
 174                 ,{'O',  8}
 175                 ,{'I',  7}
 176                 ,{'N',  7}
 177
 178                 ,{'S',  6}
 179                 ,{'H',  6}
 180                 ,{'R',  6}
 181                 ,{'D',  5}
 182                 ,{'L',  4}
 183                 ,{'U',  3}
 184
 185                 ,{'C',  3}
 186                 ,{'M',  3}
 187                 ,{'W',  2}
 188                 ,{'F',  2}
 189                 ,{'G',  2}
 190                 ,{'Y',  2}
 191                 ,{'P',  2}
 192                 ,{'B',  1}
 193                 ,{'V',  1}
 194                 ,{'K',  1}
 195         };
 196
 197         size_t total = 0;
 198         for (size_t i = 0; i < NELEMS(letters); ++i)
 199                 total += letters[i].freq;
 200
 201         for (size_t i = 0; i < size; ++i) {
 202                 int rnd = rand() % total;
 203                 int j = 0;
 204                 while (rnd > letters[j].freq) {
 205                         rnd -= letters[j].freq;
 206                         ++j;
 207                 }
 208                 in[i] = letters[j].letter;
 209         }
 210
 211         size_t compressed_size = wrapper_compress(in, size, out);
 212         assert(compressed_size);
 213
 214         /* Suprisingly, fastlz can't really use the fact that the data is shaped like this.
 215          * Be happy if we get, say, 85% plus some overhead. */
 216         assert(compressed_size < (size_t) (size * 0.85) + 512);
 217
 218         size_t restored_size = wrapper_decompress(out, compressed_size, re, size);
 219         assert(restored_size == size);
 220         for (size_t i = 0; i < size; ++i)
 221                 assert(re[i] == in[i]);
 222
 223         free(in);
 224         free(out);
 225         free(re);
 226 }
 227
 228 void test_alpha(size_t size)
 229 {
 230         char *in = malloc(size);
 231         char *out = malloc(FASTLZ_NEEDED_OUTPUT_SIZE(size));
 232         char *re = malloc(size);
 233
 234         assert(in);
 235         assert(out);
 236         assert(re);
 237
 238         for (size_t i = 0; i < size; ++i)
 239                 in[i] = 'a' + (rand() % 20);
 240
 241         size_t compressed_size = wrapper_compress(in, size, out);
 242         assert(compressed_size);
 243
 244         /* Very random data, not too compressible.
 245          * Be happy if we get, say, 85% plus some overhead. */
 246         assert(compressed_size < (size_t)(size * 0.85) + 512);
 247
 248         size_t restored_size = wrapper_decompress(out, compressed_size, re, size);
 249         assert(restored_size == size);
 250         for (size_t i = 0; i < size; ++i)
 251                 assert(re[i] == in[i]);
 252
 253         free(in);
 254         free(out);
 255         free(re);
 256 }
 257
 258 void test_fuzzy_string(size_t size)
 259 {
 260         char *in = copy_string(size, size, fuzzable_string, true);
 261         assert(in);
 262         size_t in_len = strlen(in);
 263
 264         char *out = malloc(FASTLZ_NEEDED_OUTPUT_SIZE(in_len));
 265         char *re = malloc(in_len);
 266
 267         assert(out);
 268         assert(re);
 269
 270         size_t compressed_size = wrapper_compress(in, in_len, out);
 271         assert(compressed_size);
 272
 273         size_t restored_size = wrapper_decompress(out, compressed_size, re, in_len);
 274         assert(restored_size == in_len);
 275         for (size_t i = 0; i < in_len; ++i)
 276                 assert(re[i] == in[i]);
 277
 278         free(out);
 279         free(in);
 280         free(re);
 281 }
 282
 283 int main()
 284 {
 285 #ifdef ASAN_BUILD
 286         /* NB: The following tests fails when ASAN is enabled, with an supposed memory
 287         * violation in fastlz. This does not spark joy and we should probably fix this.
 288         * Hovever, we have more urgent things to do right now, so let's disable
 289         * the test on ASAN for now. */
 290
 291         return EXIT_SKIP;
 292 #endif /* ASAN_BUILD */
 293
 294         static const int sizes[] = {
 295                   4096, // a single log
 296                  65530, // just below the magic threshold which changes underlying algo
 297                  65540, // just above it
 298                 131072,
 299         };
 300
 301         for (size_t i = 0; i < NELEMS(sizes); ++i) {
 302                 const int size = sizes[i];
 303                 test_zeroes(size);
 304                 test_01(size);
 305                 test_alpha_weighted(size);
 306                 test_alpha(size);
 307                 test_duplicate_string(size);
 308                 test_fuzzy_string(size);
 309         }
 310
 311         return EXIT_SUCCESS;
 312 }