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