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