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