tests/test-util.c

   1 /*
   2  * Copyright (c) 2011, 2012 Nicira Networks.
   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 int
 147 main(void)
 148 {
 149     int n;
 150
 151     for (n = 0; n < 32; n++) {
 152         /* Check minimum x such that f(x) == n. */
 153         check_log_2_floor(1 << n, n);
 154         check_ctz(1 << n, n);
 155
 156         /* Check maximum x such that f(x) == n. */
 157         check_log_2_floor((1 << n) | ((1 << n) - 1), n);
 158         check_ctz(UINT32_MAX << n, n);
 159
 160         /* Check a random value in the middle. */
 161         check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
 162         check_ctz((random_uint32() | 1) << n, n);
 163     }
 164
 165     /* Check ctz(0).
 166      * (log_2_floor(0) is undefined.) */
 167     check_ctz(0, 32);
 168
 169     check_bitwise_copy();
 170
 171     check_bitwise_zero();
 172
 173     return 0;
 174 }