tests/test-util.c

   1 /*
   2  * Copyright (c) 2011, 2012 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 static void
  94 shuffle(unsigned int *p, size_t n)
  95 {
  96     for (; n > 1; n--, p++) {
  97         unsigned int *q = &p[rand() % n];
  98         unsigned int tmp = *p;
  99         *p = *q;
 100         *q = tmp;
 101     }
 102 }
 103
 104 static void
 105 check_popcount(uint32_t x, int n)
 106 {
 107     if (popcount(x) != n) {
 108         fprintf(stderr, "popcount(%#"PRIx32") is %d but should be %d\n",
 109                 x, popcount(x), n);
 110         abort();
 111     }
 112 }
 113
 114 static void
 115 test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 116 {
 117     unsigned int bits[32];
 118     int i;
 119
 120     for (i = 0; i < ARRAY_SIZE(bits); i++) {
 121         bits[i] = 1u << i;
 122     }
 123
 124     check_popcount(0, 0);
 125
 126     for (i = 0; i < 1000; i++) {
 127         uint32_t x = 0;
 128         int j;
 129
 130         shuffle(bits, ARRAY_SIZE(bits));
 131         for (j = 0; j < 32; j++) {
 132             x |= bits[j];
 133             check_popcount(x, j + 1);
 134         }
 135         assert(x == UINT32_MAX);
 136
 137         shuffle(bits, ARRAY_SIZE(bits));
 138         for (j = 31; j >= 0; j--) {
 139             x &= ~bits[j];
 140             check_popcount(x, j);
 141         }
 142         assert(x == 0);
 143     }
 144 }
 145
 146 /* Returns the sum of the squares of the first 'n' positive integers. */
 147 static unsigned int
 148 sum_of_squares(int n)
 149 {
 150     return n * (n + 1) * (2 * n + 1) / 6;
 151 }
 152
 153 static void
 154 test_bitwise_copy(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 155 {
 156     unsigned int n_loops;
 157     int src_ofs;
 158     int dst_ofs;
 159     int n_bits;
 160
 161     n_loops = 0;
 162     for (n_bits = 0; n_bits <= 64; n_bits++) {
 163         for (src_ofs = 0; src_ofs < 64 - n_bits; src_ofs++) {
 164             for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 165                 ovs_be64 src = htonll(random_uint64());
 166                 ovs_be64 dst = htonll(random_uint64());
 167                 ovs_be64 orig_dst = dst;
 168                 ovs_be64 expect;
 169
 170                 if (n_bits == 64) {
 171                     expect = dst;
 172                 } else {
 173                     uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 174                     expect = orig_dst & ~htonll(mask << dst_ofs);
 175                     expect |= htonll(((ntohll(src) >> src_ofs) & mask)
 176                                      << dst_ofs);
 177                 }
 178
 179                 bitwise_copy(&src, sizeof src, src_ofs,
 180                              &dst, sizeof dst, dst_ofs,
 181                              n_bits);
 182                 if (expect != dst) {
 183                     fprintf(stderr,"copy_bits(0x%016"PRIx64",8,%d, "
 184                             "0x%016"PRIx64",8,%d, %d) yielded 0x%016"PRIx64" "
 185                             "instead of the expected 0x%016"PRIx64"\n",
 186                             ntohll(src), src_ofs,
 187                             ntohll(orig_dst), dst_ofs,
 188                             n_bits,
 189                             ntohll(dst), ntohll(expect));
 190                     abort();
 191                 }
 192
 193                 n_loops++;
 194             }
 195         }
 196     }
 197
 198     if (n_loops != sum_of_squares(64)) {
 199         abort();
 200     }
 201 }
 202
 203 static void
 204 test_bitwise_zero(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 205 {
 206     unsigned int n_loops;
 207     int dst_ofs;
 208     int n_bits;
 209
 210     n_loops = 0;
 211     for (n_bits = 0; n_bits <= 64; n_bits++) {
 212         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 213             ovs_be64 dst = htonll(random_uint64());
 214             ovs_be64 orig_dst = dst;
 215             ovs_be64 expect;
 216
 217             if (n_bits == 64) {
 218                 expect = htonll(0);
 219             } else {
 220                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 221                 expect = orig_dst & ~htonll(mask << dst_ofs);
 222             }
 223
 224             bitwise_zero(&dst, sizeof dst, dst_ofs, n_bits);
 225             if (expect != dst) {
 226                 fprintf(stderr,"bitwise_zero(0x%016"PRIx64",8,%d, %d) "
 227                         "yielded 0x%016"PRIx64" "
 228                         "instead of the expected 0x%016"PRIx64"\n",
 229                         ntohll(orig_dst), dst_ofs,
 230                         n_bits,
 231                         ntohll(dst), ntohll(expect));
 232                 abort();
 233             }
 234
 235             n_loops++;
 236         }
 237     }
 238
 239     if (n_loops != 64 * (64 + 1) / 2) {
 240         abort();
 241     }
 242 }
 243
 244 static void
 245 test_bitwise_one(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 246 {
 247     unsigned int n_loops;
 248     int dst_ofs;
 249     int n_bits;
 250
 251     n_loops = 0;
 252     for (n_bits = 0; n_bits <= 64; n_bits++) {
 253         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 254             ovs_be64 dst = htonll(random_uint64());
 255             ovs_be64 orig_dst = dst;
 256             ovs_be64 expect;
 257
 258             if (n_bits == 64) {
 259                 expect = htonll(UINT64_MAX);
 260             } else {
 261                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 262                 expect = orig_dst | htonll(mask << dst_ofs);
 263             }
 264
 265             bitwise_one(&dst, sizeof dst, dst_ofs, n_bits);
 266             if (expect != dst) {
 267                 fprintf(stderr,"bitwise_one(0x%016"PRIx64",8,%d, %d) "
 268                         "yielded 0x%016"PRIx64" "
 269                         "instead of the expected 0x%016"PRIx64"\n",
 270                         ntohll(orig_dst), dst_ofs,
 271                         n_bits,
 272                         ntohll(dst), ntohll(expect));
 273                 abort();
 274             }
 275
 276             n_loops++;
 277         }
 278     }
 279
 280     if (n_loops != 64 * (64 + 1) / 2) {
 281         abort();
 282     }
 283 }
 284
 285 static void
 286 test_bitwise_is_all_zeros(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 287 {
 288     int n_loops;
 289
 290     for (n_loops = 0; n_loops < 100; n_loops++) {
 291         ovs_be64 x = htonll(0);
 292         int i;
 293
 294         for (i = 0; i < 64; i++) {
 295             ovs_be64 bit;
 296             int ofs, n;
 297
 298             /* Change a random 0-bit into a 1-bit. */
 299             do {
 300                 bit = htonll(UINT64_C(1) << (random_uint32() % 64));
 301             } while (x & bit);
 302             x |= bit;
 303
 304             for (ofs = 0; ofs < 64; ofs++) {
 305                 for (n = 0; n <= 64 - ofs; n++) {
 306                     bool expect;
 307                     bool answer;
 308
 309                     expect = (n == 64
 310                               ? x == 0
 311                               : !(x & htonll(((UINT64_C(1) << n) - 1)
 312                                              << ofs)));
 313                     answer = bitwise_is_all_zeros(&x, sizeof x, ofs, n);
 314                     if (expect != answer) {
 315                         fprintf(stderr,
 316                                 "bitwise_is_all_zeros(0x%016"PRIx64",8,%d,%d "
 317                                 "returned %s instead of %s\n",
 318                                 ntohll(x), ofs, n,
 319                                 answer ? "true" : "false",
 320                                 expect ? "true" : "false");
 321                         abort();
 322                     }
 323                 }
 324             }
 325         }
 326     }
 327 }
 328
 329 static void
 330 test_follow_symlinks(int argc, char *argv[])
 331 {
 332     int i;
 333
 334     for (i = 1; i < argc; i++) {
 335         char *target = follow_symlinks(argv[i]);
 336         puts(target);
 337         free(target);
 338     }
 339 }
 340
 341 static void
 342 test_assert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 343 {
 344     ovs_assert(false);
 345 }
 346 \f
 347 static const struct command commands[] = {
 348     {"ctz", 0, 0, test_ctz},
 349     {"popcount", 0, 0, test_popcount},
 350     {"log_2_floor", 0, 0, test_log_2_floor},
 351     {"bitwise_copy", 0, 0, test_bitwise_copy},
 352     {"bitwise_zero", 0, 0, test_bitwise_zero},
 353     {"bitwise_one", 0, 0, test_bitwise_one},
 354     {"bitwise_is_all_zeros", 0, 0, test_bitwise_is_all_zeros},
 355     {"follow-symlinks", 1, INT_MAX, test_follow_symlinks},
 356     {"assert", 0, 0, test_assert},
 357     {NULL, 0, 0, NULL},
 358 };
 359
 360 static void
 361 parse_options(int argc, char *argv[])
 362 {
 363     enum {
 364         VLOG_OPTION_ENUMS
 365     };
 366     static struct option long_options[] = {
 367         VLOG_LONG_OPTIONS,
 368         {NULL, 0, NULL, 0},
 369     };
 370     char *short_options = long_options_to_short_options(long_options);
 371
 372     for (;;) {
 373         int c = getopt_long(argc, argv, short_options, long_options, NULL);
 374         if (c == -1) {
 375             break;
 376         }
 377
 378         switch (c) {
 379         VLOG_OPTION_HANDLERS
 380
 381         case '?':
 382             exit(EXIT_FAILURE);
 383
 384         default:
 385             abort();
 386         }
 387     }
 388     free(short_options);
 389 }
 390
 391 int
 392 main(int argc, char *argv[])
 393 {
 394     set_program_name(argv[0]);
 395     parse_options(argc, argv);
 396     run_command(argc - optind, argv + optind, commands);
 397     return 0;
 398 }