src/tests/test_compression_common.c

   1 /* MIT License
   2  *
   3  * Copyright (c) 2022 Samsung Electronics Co., Ltd.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy
   6  * of this software and associated documentation files (the "Software"), to deal
   7  * in the Software without restriction, including without limitation the rights
   8  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9  * copies of the Software, and to permit persons to whom the Software is furnished
  10  * to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  21  * THE SOFTWARE. */
  22
  23 #include <assert.h>
  24 #include <stdbool.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <unistd.h>
  29
  30 #include "logcommon.h"
  31 #include "test_compression_common.h"
  32 #include "fastlz_test.h"
  33
  34 // The strings to compress.
  35 static const char *const repeated_string = "Did you ever hear the tragedy of darth plagueis the wise?";
  36 static const char *const fuzzable_string = "Ala ma kota";
  37 static const char *const garbage_string = "fdffdfdfddfdfdfdd";
  38
  39 void modify_one_letter(char *str, size_t size)
  40 {
  41         str[rand() % size] = 'a' + rand() % 26;
  42 }
  43
  44 void copy_string_repeatedly(char *in, size_t size, const char *source, bool apply_fuzzing)
  45 {
  46         const size_t source_len = strlen(source);
  47         const size_t repeats = size / source_len;
  48
  49         for (size_t i = 0; i < repeats; ++i) {
  50                 memcpy(in + i * source_len, source, source_len);
  51                 if (apply_fuzzing)
  52                         modify_one_letter(in + i * source_len, source_len);
  53         }
  54 }
  55
  56 void gen_zeroes(char *in, size_t size)
  57 {
  58         for (size_t i = 0; i < size; ++i)
  59                 in[i] = '\0';
  60 }
  61
  62 void gen_alpha(char *in, size_t size)
  63 {
  64         for (size_t i = 0; i < size; ++i)
  65                 in[i] = 'a' + rand() % 26;
  66 }
  67
  68 void gen_01(char *in, size_t size)
  69 {
  70         /* Produce something like 010100101000111...
  71          * Note that the algorithm works at the level
  72          * of bytes, not bits, so these being mostly
  73          * composed of zero-bits doesn't matter much. */
  74         for (size_t i = 0; i < size; ++i)
  75                 in[i] = rand() % 2;
  76 }
  77
  78 void gen_repeated_string(char *in, size_t size)
  79 {
  80         /* Generates a pattern of a repeated string,
  81          * disrupted near the end by garbage (RRRRRRGR) */
  82
  83         gen_zeroes(in, size); // for strcat
  84
  85         const size_t extras = strlen(garbage_string) + strlen(repeated_string) + sizeof '\0';
  86         assert(size >= extras);
  87
  88         copy_string_repeatedly(in, size - extras, repeated_string, false);
  89         strcat(in, garbage_string);
  90         strcat(in, repeated_string);
  91 }
  92
  93 void gen_fuzzy_string(char *in, size_t size)
  94 {
  95         /* Generates a slightly corrupted pattern.
  96          * For example with the base of "Ala ma kota":
  97          *
  98          * Ula ma kota
  99          * Ala ma bota
 100          * Ala ma kopa
 101          * Ada ma kota
 102          * Ala ma koty
 103          * Ala ma kuta
 104          * Ale ma kota
 105          * Ala da kota */
 106
 107         const size_t fuzzable_len = strlen(fuzzable_string);
 108         gen_zeroes(in + size - fuzzable_len, fuzzable_len); // the pattern won't fit perfectly
 109
 110         copy_string_repeatedly(in, size, fuzzable_string, true);
 111 }
 112
 113 void gen_weighted_alpha(char *in, size_t size)
 114 {
 115         /* Produce a random string with letters weighted
 116          * by their ~actual English frequencies. */
 117         static const struct letter {
 118                 char letter;
 119                 size_t freq;
 120         } letters[] =
 121                 {{'E', 13}
 122                 ,{'T', 10}
 123                 ,{'A',  8}
 124                 ,{'O',  8}
 125                 ,{'I',  7}
 126                 ,{'N',  7}
 127
 128                 ,{'S',  6}
 129                 ,{'H',  6}
 130                 ,{'R',  6}
 131                 ,{'D',  5}
 132                 ,{'L',  4}
 133                 ,{'U',  3}
 134
 135                 ,{'C',  3}
 136                 ,{'M',  3}
 137                 ,{'W',  2}
 138                 ,{'F',  2}
 139                 ,{'G',  2}
 140                 ,{'Y',  2}
 141                 ,{'P',  2}
 142                 ,{'B',  1}
 143                 ,{'V',  1}
 144                 ,{'K',  1}
 145         };
 146
 147         size_t total = 0; // ideally this would be compile-time but we're not C++
 148         for (size_t i = 0; i < NELEMS(letters); ++i)
 149                 total += letters[i].freq;
 150
 151         for (size_t i = 0; i < size; ++i) {
 152                 int rnd = rand() % total;
 153                 int j = 0;
 154                 while (rnd > letters[j].freq) {
 155                         rnd -= letters[j].freq;
 156                         ++j;
 157                 }
 158                 in[i] = letters[j].letter;
 159         }
 160 }
 161
 162 typedef void (*generator_t)(char *, size_t);
 163 void test_via_generator(generator_t gen, size_t size, const struct test_algo *algo, const char *algo_name, const char *gen_name)
 164 {
 165         char *const in = malloc(size);
 166         assert(in);
 167         gen(in, size);
 168
 169         struct common_compressed *out;
 170         struct timespec ts_comp = algo->comp(in, size, &out);
 171         assert(out->size_compressed);
 172
 173         const size_t comp_size = out->size_compressed;
 174
 175         char *re;
 176         size_t re_size;
 177         struct timespec ts_decomp = algo->decomp(out, &re, &re_size);
 178
 179         for (size_t i = 0; i < re_size; ++i)
 180                 assert(re[i] == in[i]);
 181         free(in);
 182         free(re);
 183
 184         multiply_timespec(&ts_comp  , (double) MSEC_PER_SEC / ACTUAL_CALLS);
 185         multiply_timespec(&ts_decomp, (double) MSEC_PER_SEC / ACTUAL_CALLS);
 186
 187         printf("%s / %s / %zu\n"
 188                "\t  compressed in %d.%02dms\n"
 189                "\tdecompressed in %d.%02dms\n"
 190                "\tcompressed into %zu bytes (%.1f%%)\n"
 191                 , algo_name, gen_name, size
 192                 , (int)   ts_comp.tv_sec,   (int) ts_comp.tv_nsec / (NSEC_PER_SEC / 100)
 193                 , (int) ts_decomp.tv_sec, (int) ts_decomp.tv_nsec / (NSEC_PER_SEC / 100)
 194                 , comp_size, 100.f * comp_size / size
 195         );
 196 }
 197
 198 int main()
 199 {
 200 #ifdef ASAN_BUILD
 201         /* NB: The following tests fails when ASAN is enabled, with a supposed memory
 202          * violation in fastlz. This does not spark joy and we should probably fix this.
 203          * Hovever, we have more urgent things to do right now, so let's disable
 204          * the test on ASAN for now. */
 205
 206         return EXIT_SKIP;
 207 #endif /* ASAN_BUILD */
 208
 209         static const int sizes[] = {
 210                   4096, // max single log payload
 211                  65530, // just below 2^16, which may be a behaviour change threshold for some algos
 212                  65540, // just above 2^16
 213                 131072, // the size of the buffer used by dlog_logger
 214         };
 215
 216         static const struct {
 217                 const struct test_algo *algo;
 218                 const char *name;
 219         } algos[] = {
 220                 #define A(x) { .algo = &x, .name = #x }
 221                 A(fastlz),
 222                 #undef A
 223         };
 224
 225         static const struct {
 226                 const generator_t gen;
 227                 const char *name;
 228         } gens[] = {
 229                 #define G(x) { .gen = gen_ ## x, .name = #x }
 230                 G(zeroes),
 231                 G(01),
 232                 G(alpha),
 233                 G(repeated_string),
 234                 G(fuzzy_string),
 235                 G(weighted_alpha),
 236                 #undef G
 237         };
 238
 239         for (size_t s = 0; s < NELEMS(sizes); ++s)
 240         for (size_t g = 0; g < NELEMS(gens);  ++g)
 241         for (size_t a = 0; a < NELEMS(algos); ++a)
 242                 test_via_generator(gens[g].gen, sizes[s], algos[a].algo, algos[a].name, gens[g].name);
 243
 244         return EXIT_SUCCESS;
 245 }