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 <inttypes.h>
  20 #include <limits.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23
  24 #include "byte-order.h"
  25 #include "command-line.h"
  26 #include "random.h"
  27 #include "util.h"
  28
  29 #undef NDEBUG
  30 #include <assert.h>
  31
  32 static void
  33 check_log_2_floor(uint32_t x, int n)
  34 {
  35     if (log_2_floor(x) != n) {
  36         fprintf(stderr, "log_2_floor(%"PRIu32") is %d but should be %d\n",
  37                 x, log_2_floor(x), n);
  38         abort();
  39     }
  40 }
  41
  42 static void
  43 test_log_2_floor(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
  44 {
  45     int n;
  46
  47     for (n = 0; n < 32; n++) {
  48         /* Check minimum x such that f(x) == n. */
  49         check_log_2_floor(1 << n, n);
  50
  51         /* Check maximum x such that f(x) == n. */
  52         check_log_2_floor((1 << n) | ((1 << n) - 1), n);
  53
  54         /* Check a random value in the middle. */
  55         check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
  56     }
  57
  58     /* log_2_floor(0) is undefined, so don't check it. */
  59 }
  60
  61 static void
  62 check_ctz(uint32_t x, int n)
  63 {
  64     if (ctz(x) != n) {
  65         fprintf(stderr, "ctz(%"PRIu32") is %d but should be %d\n",
  66                 x, ctz(x), n);
  67         abort();
  68     }
  69 }
  70
  71 static void
  72 test_ctz(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
  73 {
  74     int n;
  75
  76     for (n = 0; n < 32; n++) {
  77         /* Check minimum x such that f(x) == n. */
  78         check_ctz(1 << n, n);
  79
  80         /* Check maximum x such that f(x) == n. */
  81         check_ctz(UINT32_MAX << n, n);
  82
  83         /* Check a random value in the middle. */
  84         check_ctz((random_uint32() | 1) << n, n);
  85     }
  86
  87     /* Check ctz(0). */
  88     check_ctz(0, 32);
  89 }
  90
  91 static void
  92 shuffle(unsigned int *p, size_t n)
  93 {
  94     for (; n > 1; n--, p++) {
  95         unsigned int *q = &p[rand() % n];
  96         unsigned int tmp = *p;
  97         *p = *q;
  98         *q = tmp;
  99     }
 100 }
 101
 102 static void
 103 check_popcount(uint32_t x, int n)
 104 {
 105     if (popcount(x) != n) {
 106         fprintf(stderr, "popcount(%#"PRIx32") is %d but should be %d\n",
 107                 x, popcount(x), n);
 108         abort();
 109     }
 110 }
 111
 112 static void
 113 test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 114 {
 115     unsigned int bits[32];
 116     int i;
 117
 118     for (i = 0; i < ARRAY_SIZE(bits); i++) {
 119         bits[i] = 1u << i;
 120     }
 121
 122     check_popcount(0, 0);
 123
 124     for (i = 0; i < 1000; i++) {
 125         uint32_t x = 0;
 126         int j;
 127
 128         shuffle(bits, ARRAY_SIZE(bits));
 129         for (j = 0; j < 32; j++) {
 130             x |= bits[j];
 131             check_popcount(x, j + 1);
 132         }
 133         assert(x == UINT32_MAX);
 134
 135         shuffle(bits, ARRAY_SIZE(bits));
 136         for (j = 31; j >= 0; j--) {
 137             x &= ~bits[j];
 138             check_popcount(x, j);
 139         }
 140         assert(x == 0);
 141     }
 142 }
 143
 144 /* Returns the sum of the squares of the first 'n' positive integers. */
 145 static unsigned int
 146 sum_of_squares(int n)
 147 {
 148     return n * (n + 1) * (2 * n + 1) / 6;
 149 }
 150
 151 static void
 152 test_bitwise_copy(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 153 {
 154     unsigned int n_loops;
 155     int src_ofs;
 156     int dst_ofs;
 157     int n_bits;
 158
 159     n_loops = 0;
 160     for (n_bits = 0; n_bits <= 64; n_bits++) {
 161         for (src_ofs = 0; src_ofs < 64 - n_bits; src_ofs++) {
 162             for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 163                 ovs_be64 src = htonll(random_uint64());
 164                 ovs_be64 dst = htonll(random_uint64());
 165                 ovs_be64 orig_dst = dst;
 166                 ovs_be64 expect;
 167
 168                 if (n_bits == 64) {
 169                     expect = dst;
 170                 } else {
 171                     uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 172                     expect = orig_dst & ~htonll(mask << dst_ofs);
 173                     expect |= htonll(((ntohll(src) >> src_ofs) & mask)
 174                                      << dst_ofs);
 175                 }
 176
 177                 bitwise_copy(&src, sizeof src, src_ofs,
 178                              &dst, sizeof dst, dst_ofs,
 179                              n_bits);
 180                 if (expect != dst) {
 181                     fprintf(stderr,"copy_bits(0x%016"PRIx64",8,%d, "
 182                             "0x%016"PRIx64",8,%d, %d) yielded 0x%016"PRIx64" "
 183                             "instead of the expected 0x%016"PRIx64"\n",
 184                             ntohll(src), src_ofs,
 185                             ntohll(orig_dst), dst_ofs,
 186                             n_bits,
 187                             ntohll(dst), ntohll(expect));
 188                     abort();
 189                 }
 190
 191                 n_loops++;
 192             }
 193         }
 194     }
 195
 196     if (n_loops != sum_of_squares(64)) {
 197         abort();
 198     }
 199 }
 200
 201 static void
 202 test_bitwise_zero(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 203 {
 204     unsigned int n_loops;
 205     int dst_ofs;
 206     int n_bits;
 207
 208     n_loops = 0;
 209     for (n_bits = 0; n_bits <= 64; n_bits++) {
 210         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 211             ovs_be64 dst = htonll(random_uint64());
 212             ovs_be64 orig_dst = dst;
 213             ovs_be64 expect;
 214
 215             if (n_bits == 64) {
 216                 expect = htonll(0);
 217             } else {
 218                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 219                 expect = orig_dst & ~htonll(mask << dst_ofs);
 220             }
 221
 222             bitwise_zero(&dst, sizeof dst, dst_ofs, n_bits);
 223             if (expect != dst) {
 224                 fprintf(stderr,"bitwise_zero(0x%016"PRIx64",8,%d, %d) "
 225                         "yielded 0x%016"PRIx64" "
 226                         "instead of the expected 0x%016"PRIx64"\n",
 227                         ntohll(orig_dst), dst_ofs,
 228                         n_bits,
 229                         ntohll(dst), ntohll(expect));
 230                 abort();
 231             }
 232
 233             n_loops++;
 234         }
 235     }
 236
 237     if (n_loops != 64 * (64 + 1) / 2) {
 238         abort();
 239     }
 240 }
 241
 242 static void
 243 test_bitwise_one(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 244 {
 245     unsigned int n_loops;
 246     int dst_ofs;
 247     int n_bits;
 248
 249     n_loops = 0;
 250     for (n_bits = 0; n_bits <= 64; n_bits++) {
 251         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
 252             ovs_be64 dst = htonll(random_uint64());
 253             ovs_be64 orig_dst = dst;
 254             ovs_be64 expect;
 255
 256             if (n_bits == 64) {
 257                 expect = htonll(UINT64_MAX);
 258             } else {
 259                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
 260                 expect = orig_dst | htonll(mask << dst_ofs);
 261             }
 262
 263             bitwise_one(&dst, sizeof dst, dst_ofs, n_bits);
 264             if (expect != dst) {
 265                 fprintf(stderr,"bitwise_one(0x%016"PRIx64",8,%d, %d) "
 266                         "yielded 0x%016"PRIx64" "
 267                         "instead of the expected 0x%016"PRIx64"\n",
 268                         ntohll(orig_dst), dst_ofs,
 269                         n_bits,
 270                         ntohll(dst), ntohll(expect));
 271                 abort();
 272             }
 273
 274             n_loops++;
 275         }
 276     }
 277
 278     if (n_loops != 64 * (64 + 1) / 2) {
 279         abort();
 280     }
 281 }
 282
 283 static void
 284 test_bitwise_is_all_zeros(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 285 {
 286     int n_loops;
 287
 288     for (n_loops = 0; n_loops < 100; n_loops++) {
 289         ovs_be64 x = htonll(0);
 290         int i;
 291
 292         for (i = 0; i < 64; i++) {
 293             ovs_be64 bit;
 294             int ofs, n;
 295
 296             /* Change a random 0-bit into a 1-bit. */
 297             do {
 298                 bit = htonll(UINT64_C(1) << (random_uint32() % 64));
 299             } while (x & bit);
 300             x |= bit;
 301
 302             for (ofs = 0; ofs < 64; ofs++) {
 303                 for (n = 0; n <= 64 - ofs; n++) {
 304                     bool expect;
 305                     bool answer;
 306
 307                     expect = (n == 64
 308                               ? x == 0
 309                               : !(x & htonll(((UINT64_C(1) << n) - 1)
 310                                              << ofs)));
 311                     answer = bitwise_is_all_zeros(&x, sizeof x, ofs, n);
 312                     if (expect != answer) {
 313                         fprintf(stderr,
 314                                 "bitwise_is_all_zeros(0x%016"PRIx64",8,%d,%d "
 315                                 "returned %s instead of %s\n",
 316                                 ntohll(x), ofs, n,
 317                                 answer ? "true" : "false",
 318                                 expect ? "true" : "false");
 319                         abort();
 320                     }
 321                 }
 322             }
 323         }
 324     }
 325 }
 326
 327 static void
 328 test_follow_symlinks(int argc, char *argv[])
 329 {
 330     int i;
 331
 332     for (i = 1; i < argc; i++) {
 333         char *target = follow_symlinks(argv[i]);
 334         puts(target);
 335         free(target);
 336     }
 337 }
 338 \f
 339 static const struct command commands[] = {
 340     {"ctz", 0, 0, test_ctz},
 341     {"popcount", 0, 0, test_popcount},
 342     {"log_2_floor", 0, 0, test_log_2_floor},
 343     {"bitwise_copy", 0, 0, test_bitwise_copy},
 344     {"bitwise_zero", 0, 0, test_bitwise_zero},
 345     {"bitwise_one", 0, 0, test_bitwise_one},
 346     {"bitwise_is_all_zeros", 0, 0, test_bitwise_is_all_zeros},
 347     {"follow-symlinks", 1, INT_MAX, test_follow_symlinks},
 348     {NULL, 0, 0, NULL},
 349 };
 350
 351 int
 352 main(int argc, char *argv[])
 353 {
 354     set_program_name(argv[0]);
 355     run_command(argc - 1, argv + 1, commands);
 356     return 0;
 357 }