1 /*
2 * Copyright (C) 2014 The Android Open Source Project
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 "gtest/gtest.h"
18 #include "memcmp16.h"
19
20 class RandGen {
21 public:
RandGen(uint32_t seed)22 explicit RandGen(uint32_t seed) : val_(seed) {}
23
next()24 uint32_t next() {
25 val_ = val_ * 48271 % 2147483647 + 13;
26 return val_;
27 }
28
29 uint32_t val_;
30 };
31
32 class MemCmp16Test : public testing::Test {
33 };
34
35 // A simple implementation to compare against.
36 // Note: this version is equivalent to the generic one used when no optimized version is available.
memcmp16_compare(const uint16_t * s0,const uint16_t * s1,size_t count)37 int32_t memcmp16_compare(const uint16_t* s0, const uint16_t* s1, size_t count) {
38 for (size_t i = 0; i < count; i++) {
39 if (s0[i] != s1[i]) {
40 return static_cast<int32_t>(s0[i]) - static_cast<int32_t>(s1[i]);
41 }
42 }
43 return 0;
44 }
45
46 static constexpr size_t kMemCmp16Rounds = 100000;
47
CheckSeparate(size_t max_length,size_t min_length)48 static void CheckSeparate(size_t max_length, size_t min_length) {
49 RandGen r(0x1234);
50 size_t range_of_tests = 7; // All four (weighted) tests active in the beginning.
51
52 for (size_t round = 0; round < kMemCmp16Rounds; ++round) {
53 size_t type = r.next() % range_of_tests;
54 size_t count1, count2;
55 uint16_t *s1, *s2; // Use raw pointers to simplify using clobbered addresses
56
57 switch (type) {
58 case 0: // random, non-zero lengths of both strings
59 case 1:
60 case 2:
61 case 3:
62 count1 = (r.next() % max_length) + min_length;
63 count2 = (r.next() % max_length) + min_length;
64 break;
65
66 case 4: // random non-zero length of first, second is zero
67 count1 = (r.next() % max_length) + min_length;
68 count2 = 0U;
69 break;
70
71 case 5: // random non-zero length of second, first is zero
72 count1 = 0U;
73 count2 = (r.next() % max_length) + min_length;
74 break;
75
76 case 6: // both zero-length
77 count1 = 0U;
78 count2 = 0U;
79 range_of_tests = 6; // Don't do zero-zero again.
80 break;
81
82 default:
83 ASSERT_TRUE(false) << "Should not get here.";
84 continue;
85 }
86
87 if (count1 > 0U) {
88 s1 = new uint16_t[count1];
89 } else {
90 // Leave a random pointer, should not be touched.
91 s1 = reinterpret_cast<uint16_t*>(0xebad1001);
92 }
93
94 if (count2 > 0U) {
95 s2 = new uint16_t[count2];
96 } else {
97 // Leave a random pointer, should not be touched.
98 s2 = reinterpret_cast<uint16_t*>(0xebad2002);
99 }
100
101 size_t min = count1 < count2 ? count1 : count2;
102 bool fill_same = r.next() % 1 == 1;
103
104 if (fill_same) {
105 for (size_t i = 0; i < min; ++i) {
106 s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
107 s2[i] = s1[i];
108 }
109 for (size_t i = min; i < count1; ++i) {
110 s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
111 }
112 for (size_t i = min; i < count2; ++i) {
113 s2[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
114 }
115 } else {
116 for (size_t i = 0; i < count1; ++i) {
117 s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
118 }
119 for (size_t i = 0; i < count2; ++i) {
120 s2[i] = static_cast<uint16_t>(r.next() & 0xFFFF);
121 }
122 }
123
124 uint16_t* s1_pot_unaligned = s1;
125 uint16_t* s2_pot_unaligned = s2;
126 size_t c1_mod = count1;
127 size_t c2_mod = count2;
128
129 if (!fill_same) { // Don't waste a good "long" test.
130 if (count1 > 1 && r.next() % 10 == 0) {
131 c1_mod--;
132 s1_pot_unaligned++;
133 }
134 if (count2 > 1 && r.next() % 10 == 0) {
135 c2_mod--;
136 s2_pot_unaligned++;
137 }
138 }
139 size_t mod_min = c1_mod < c2_mod ? c1_mod : c2_mod;
140
141 int32_t expected = memcmp16_compare(s1_pot_unaligned, s2_pot_unaligned, mod_min);
142 int32_t computed = art::testing::MemCmp16Testing(s1_pot_unaligned, s2_pot_unaligned, mod_min);
143
144 ASSERT_EQ(expected, computed) << "Run " << round << ", c1=" << count1 << " c2=" << count2;
145
146 if (count1 > 0U) {
147 delete[] s1;
148 }
149 if (count2 > 0U) {
150 delete[] s2;
151 }
152 }
153 }
154
TEST_F(MemCmp16Test,RandomSeparateShort)155 TEST_F(MemCmp16Test, RandomSeparateShort) {
156 CheckSeparate(5U, 1U);
157 }
158
TEST_F(MemCmp16Test,RandomSeparateLong)159 TEST_F(MemCmp16Test, RandomSeparateLong) {
160 CheckSeparate(64U, 32U);
161 }
162
163 // TODO: What's a good test for overlapping memory. Is it important?
164 // TEST_F(MemCmp16Test, RandomOverlay) {
165 //
166 // }
167