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
20class RandGen {
21 public:
22  explicit RandGen(uint32_t seed) : val_(seed) {}
23
24  uint32_t next() {
25    val_ = val_ * 48271 % 2147483647 + 13;
26    return val_;
27  }
28
29  uint32_t val_;
30};
31
32class 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.
37int32_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
46static constexpr size_t kMemCmp16Rounds = 100000;
47
48static 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
155TEST_F(MemCmp16Test, RandomSeparateShort) {
156  CheckSeparate(5U, 1U);
157}
158
159TEST_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