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 int
 106 main(void)
 107 {
 108     int n;
 109
 110     for (n = 0; n < 32; n++) {
 111         /* Check minimum x such that f(x) == n. */
 112         check_log_2_floor(1 << n, n);
 113         check_ctz(1 << n, n);
 114
 115         /* Check maximum x such that f(x) == n. */
 116         check_log_2_floor((1 << n) | ((1 << n) - 1), n);
 117         check_ctz(UINT32_MAX << n, n);
 118
 119         /* Check a random value in the middle. */
 120         check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
 121         check_ctz((random_uint32() | 1) << n, n);
 122     }
 123
 124     /* Check ctz(0).
 125      * (log_2_floor(0) is undefined.) */
 126     check_ctz(0, 32);
 127
 128     check_bitwise_copy();
 129
 130     return 0;
 131 }