tests/test-util.c

   1 /*
   2  * Copyright (c) 2011, 2012, 2013 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18
  19 #include <getopt.h>
  20 #include <inttypes.h>
  21 #include <limits.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24
  25 #include "byte-order.h"
  26 #include "command-line.h"
  27 #include "random.h"
  28 #include "util.h"
  29 #include "vlog.h"
  30
  31 #undef NDEBUG
  32 #include <assert.h>
  33
  34 static void
  35 check_log_2_floor(uint32_t x, int n)
  36 {
  37     if (log_2_floor(x) != n) {
  38         fprintf(stderr, "log_2_floor(%"PRIu32") is %d but should be %d\n",
  39                 x, log_2_floor(x), n);
  40         abort();
  41     }
  42 }
  43
  44 static void
  45 test_log_2_floor(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
  46 {
  47     int n;
  48
  49     for (n = 0; n < 32; n++) {
  50         /* Check minimum x such that f(x) == n. */
  51         check_log_2_floor(1 << n, n);
  52
  53         /* Check maximum x such that f(x) == n. */
  54         check_log_2_floor((1 << n) | ((1 << n) - 1), n);
  55
  56         /* Check a random value in the middle. */
  57         check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
  58     }
  59
  60     /* log_2_floor(0) is undefined, so don't check it. */
  61 }
  62
  63 static void
  64 check_ctz(uint32_t x, int n)
  65 {
  66     if (ctz(x) != n) {
  67         fprintf(stderr, "ctz(%"PRIu32") is %d but should be %d\n",
  68                 x, ctz(x), n);
  69         abort();
  70     }
  71 }
  72
  73 static void
  74 test_ctz(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
  75 {
  76     int n;
  77
  78     for (n = 0; n < 32; n++) {
  79         /* Check minimum x such that f(x) == n. */
  80         check_ctz(1 << n, n);
  81
  82         /* Check maximum x such that f(x) == n. */
  83         check_ctz(UINT32_MAX << n, n);
  84
  85         /* Check a random value in the middle. */
  86         check_ctz((random_uint32() | 1) << n, n);
  87     }
  88
  89     /* Check ctz(0). */
  90     check_ctz(0, 32);
  91 }
  92
  93 /* Returns a random number in the range 'min'...'max' inclusive. */
  94 static uint32_t
  95 random_in_range(uint32_t min, uint32_t max)
  96 {
  97     return min == max ? min : min + random_range(max - min + 1);
  98 }
  99
 100 static void
 101 check_rup2(uint32_t x, int n)
 102 {
 103     uint32_t rup2 = ROUND_UP_POW2(x);
 104     if (rup2 != n) {
 105         fprintf(stderr, "ROUND_UP_POW2(%#"PRIx32") is %#"PRIx32" "
 106                 "but should be %#"PRIx32"\n", x, rup2, n);
 107         abort();
 108     }
 109 }
 110
 111 static void
 112 test_round_up_pow2(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 113 {
 114     int n;
 115
 116     for (n = 0; n < 32; n++) {
 117         /* Min, max value for which ROUND_UP_POW2 should yield (1 << n). */
 118         uint32_t min = ((1u << n) >> 1) + 1;
 119         uint32_t max = 1u << n;
 120
 121         check_rup2(min, 1u << n);
 122         check_rup2(max, 1u << n);
 123         check_rup2(random_in_range(min, max), 1u << n);
 124     }
 125     check_rup2(0, 0);
 126 }
 127
 128 static void
 129 check_rdp2(uint32_t x, int n)
 130 {
 131     uint32_t rdp2 = ROUND_DOWN_POW2(x);
 132     if (rdp2 != n) {
 133         fprintf(stderr, "ROUND_DOWN_POW2(%#"PRIx32") is %#"PRIx32" "
 134                 "but should be %#"PRIx32"\n", x, rdp2, n);
 135         abort();
 136     }
 137 }
 138
 139 static void
 140 test_round_down_pow2(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 141 {
 142     int n;
 143
 144     for (n = 0; n < 32; n++) {
 145         /* Min, max value for which ROUND_DOWN_POW2 should yield (1 << n). */
 146         uint32_t min = 1u << n;
 147         uint32_t max = ((1u << n) << 1) - 1;
 148
 149         check_rdp2(min, 1u << n);
 150         check_rdp2(max, 1u << n);
 151         check_rdp2(random_in_range(min, max), 1u << n);
 152     }
 153     check_rdp2(0, 0);
 154 }
 155
 156 static void
 157 shuffle(unsigned int *p, size_t n)
 158 {
 159     for (; n > 1; n--, p++) {
 160         unsigned int *q = &p[random_range(n)];
 161         unsigned int tmp = *p;
 162         *p = *q;
 163         *q = tmp;
 164     }
 165 }
 166
 167 static void
 168 check_popcount(uint32_t x, int n)
 169 {
 170     if (popcount(x) != n) {
 171         fprintf(stderr, "popcount(%#"PRIx32") is %d but should be %d\n",
 172                 x, popcount(x), n);
 173         abort();
 174     }
 175 }
 176
 177 static void
 178 test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 179 {
 180     unsigned int bits[32];
 181     int i;
 182
 183     for (i = 0; i < ARRAY_SIZE(bits); i++) {
 184         bits[i] = 1u << i;
 185     }
 186
 187     check_popcount(0, 0);
 188
 189     for (i = 0; i < 1000; i++) {
 190         uint32_t x = 0;
 191         int j;
 192
 193         shuffle(bits, ARRAY_SIZE(bits));
 194         for (j = 0; j < 32; j++) {
 195             x |= bits[j];
 196             check_popcount(x, j + 1);
 197         }
 198         assert(x == UINT32_MAX);
 199
 200         shuffle(bits, ARRAY_SIZE(bits));
 201         for (j = 31; j >= 0; j--) {
 202             x &= ~bits[j];
 203             check_popcount(x, j);
 204         }
 205         assert(x == 0);
 206     }
 207 }
 208
 209 /* Returns the sum of the squares of the first 'n' positive integers. */
 210 static unsigned int
 211 sum_of_squares(int n)
 212 {
 213     return n * (n + 1) * (2 * n + 1) / 6;
 214 }
 215
 216 static void
 217 test_bitwise_copy(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 218 {
 219     unsigned int n_loops;
 220     int src_ofs;
 221     int dst_ofs;
 222     int n_bits;
 223
 224     n_loops = 0;
 225     for (n_bits = 0; n_bits <= 64; n_bits++) {
 226         for (src_ofs = 0; src_ofs < 64 - n_bits; src_ofs++) {
 227             for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 228                 ovs_be64 src = htonll(random_uint64());
 229                 ovs_be64 dst = htonll(random_uint64());
 230                 ovs_be64 orig_dst = dst;
 231                 ovs_be64 expect;
 232
 233                 if (n_bits == 64) {
 234                     expect = dst;
 235                 } else {
 236                     uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 237                     expect = orig_dst & ~htonll(mask << dst_ofs);
 238                     expect |= htonll(((ntohll(src) >> src_ofs) & mask)
 239                                      << dst_ofs);
 240                 }
 241
 242                 bitwise_copy(&src, sizeof src, src_ofs,
 243                              &dst, sizeof dst, dst_ofs,
 244                              n_bits);
 245                 if (expect != dst) {
 246                     fprintf(stderr,"copy_bits(0x%016"PRIx64",8,%d, "
 247                             "0x%016"PRIx64",8,%d, %d) yielded 0x%016"PRIx64" "
 248                             "instead of the expected 0x%016"PRIx64"\n",
 249                             ntohll(src), src_ofs,
 250                             ntohll(orig_dst), dst_ofs,
 251                             n_bits,
 252                             ntohll(dst), ntohll(expect));
 253                     abort();
 254                 }
 255
 256                 n_loops++;
 257             }
 258         }
 259     }
 260
 261     if (n_loops != sum_of_squares(64)) {
 262         abort();
 263     }
 264 }
 265
 266 static void
 267 test_bitwise_zero(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 268 {
 269     unsigned int n_loops;
 270     int dst_ofs;
 271     int n_bits;
 272
 273     n_loops = 0;
 274     for (n_bits = 0; n_bits <= 64; n_bits++) {
 275         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 276             ovs_be64 dst = htonll(random_uint64());
 277             ovs_be64 orig_dst = dst;
 278             ovs_be64 expect;
 279
 280             if (n_bits == 64) {
 281                 expect = htonll(0);
 282             } else {
 283                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 284                 expect = orig_dst & ~htonll(mask << dst_ofs);
 285             }
 286
 287             bitwise_zero(&dst, sizeof dst, dst_ofs, n_bits);
 288             if (expect != dst) {
 289                 fprintf(stderr,"bitwise_zero(0x%016"PRIx64",8,%d, %d) "
 290                         "yielded 0x%016"PRIx64" "
 291                         "instead of the expected 0x%016"PRIx64"\n",
 292                         ntohll(orig_dst), dst_ofs,
 293                         n_bits,
 294                         ntohll(dst), ntohll(expect));
 295                 abort();
 296             }
 297
 298             n_loops++;
 299         }
 300     }
 301
 302     if (n_loops != 64 * (64 + 1) / 2) {
 303         abort();
 304     }
 305 }
 306
 307 static void
 308 test_bitwise_one(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 309 {
 310     unsigned int n_loops;
 311     int dst_ofs;
 312     int n_bits;
 313
 314     n_loops = 0;
 315     for (n_bits = 0; n_bits <= 64; n_bits++) {
 316         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 317             ovs_be64 dst = htonll(random_uint64());
 318             ovs_be64 orig_dst = dst;
 319             ovs_be64 expect;
 320
 321             if (n_bits == 64) {
 322                 expect = OVS_BE64_MAX;
 323             } else {
 324                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 325                 expect = orig_dst | htonll(mask << dst_ofs);
 326             }
 327
 328             bitwise_one(&dst, sizeof dst, dst_ofs, n_bits);
 329             if (expect != dst) {
 330                 fprintf(stderr,"bitwise_one(0x%016"PRIx64",8,%d, %d) "
 331                         "yielded 0x%016"PRIx64" "
 332                         "instead of the expected 0x%016"PRIx64"\n",
 333                         ntohll(orig_dst), dst_ofs,
 334                         n_bits,
 335                         ntohll(dst), ntohll(expect));
 336                 abort();
 337             }
 338
 339             n_loops++;
 340         }
 341     }
 342
 343     if (n_loops != 64 * (64 + 1) / 2) {
 344         abort();
 345     }
 346 }
 347
 348 static void
 349 test_bitwise_is_all_zeros(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 350 {
 351     int n_loops;
 352
 353     for (n_loops = 0; n_loops < 100; n_loops++) {
 354         ovs_be64 x = htonll(0);
 355         int i;
 356
 357         for (i = 0; i < 64; i++) {
 358             ovs_be64 bit;
 359             int ofs, n;
 360
 361             /* Change a random 0-bit into a 1-bit. */
 362             do {
 363                 bit = htonll(UINT64_C(1) << (random_range(64)));
 364             } while (x & bit);
 365             x |= bit;
 366
 367             for (ofs = 0; ofs < 64; ofs++) {
 368                 for (n = 0; n <= 64 - ofs; n++) {
 369                     bool expect;
 370                     bool answer;
 371
 372                     expect = (n == 64
 373                               ? x == 0
 374                               : !(x & htonll(((UINT64_C(1) << n) - 1)
 375                                              << ofs)));
 376                     answer = bitwise_is_all_zeros(&x, sizeof x, ofs, n);
 377                     if (expect != answer) {
 378                         fprintf(stderr,
 379                                 "bitwise_is_all_zeros(0x%016"PRIx64",8,%d,%d "
 380                                 "returned %s instead of %s\n",
 381                                 ntohll(x), ofs, n,
 382                                 answer ? "true" : "false",
 383                                 expect ? "true" : "false");
 384                         abort();
 385                     }
 386                 }
 387             }
 388         }
 389     }
 390 }
 391
 392 static void
 393 test_follow_symlinks(int argc, char *argv[])
 394 {
 395     int i;
 396
 397     for (i = 1; i < argc; i++) {
 398         char *target = follow_symlinks(argv[i]);
 399         puts(target);
 400         free(target);
 401     }
 402 }
 403
 404 static void
 405 test_assert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 406 {
 407     ovs_assert(false);
 408 }
 409 \f
 410 static const struct command commands[] = {
 411     {"ctz", 0, 0, test_ctz},
 412     {"round_up_pow2", 0, 0, test_round_up_pow2},
 413     {"round_down_pow2", 0, 0, test_round_down_pow2},
 414     {"popcount", 0, 0, test_popcount},
 415     {"log_2_floor", 0, 0, test_log_2_floor},
 416     {"bitwise_copy", 0, 0, test_bitwise_copy},
 417     {"bitwise_zero", 0, 0, test_bitwise_zero},
 418     {"bitwise_one", 0, 0, test_bitwise_one},
 419     {"bitwise_is_all_zeros", 0, 0, test_bitwise_is_all_zeros},
 420     {"follow-symlinks", 1, INT_MAX, test_follow_symlinks},
 421     {"assert", 0, 0, test_assert},
 422     {NULL, 0, 0, NULL},
 423 };
 424
 425 static void
 426 parse_options(int argc, char *argv[])
 427 {
 428     enum {
 429         VLOG_OPTION_ENUMS
 430     };
 431     static const struct option long_options[] = {
 432         VLOG_LONG_OPTIONS,
 433         {NULL, 0, NULL, 0},
 434     };
 435     char *short_options = long_options_to_short_options(long_options);
 436
 437     for (;;) {
 438         int c = getopt_long(argc, argv, short_options, long_options, NULL);
 439         if (c == -1) {
 440             break;
 441         }
 442
 443         switch (c) {
 444         VLOG_OPTION_HANDLERS
 445
 446         case '?':
 447             exit(EXIT_FAILURE);
 448
 449         default:
 450             abort();
 451         }
 452     }
 453     free(short_options);
 454 }
 455
 456 int
 457 main(int argc, char *argv[])
 458 {
 459     set_program_name(argv[0]);
 460     parse_options(argc, argv);
 461     run_command(argc - optind, argv + optind, commands);
 462     return 0;
 463 }