ovsdb-idl: Simplify transaction retry.
[openvswitch] / 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 }