186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu/* 286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * Copyright (C) 2014 The Android Open Source Project 386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * 486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * Licensed under the Apache License, Version 2.0 (the "License"); 586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * you may not use this file except in compliance with the License. 686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * You may obtain a copy of the License at 786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * 886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * http://www.apache.org/licenses/LICENSE-2.0 986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * 1086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * Unless required by applicable law or agreed to in writing, software 1186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * distributed under the License is distributed on an "AS IS" BASIS, 1286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * See the License for the specific language governing permissions and 1486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu * limitations under the License. 1586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu */ 1686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 1786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu#include "gtest/gtest.h" 1886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu#include "memcmp16.h" 1986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 2086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescuclass RandGen { 2186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu public: 2286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu explicit RandGen(uint32_t seed) : val_(seed) {} 2386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 2486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu uint32_t next() { 2586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu val_ = val_ * 48271 % 2147483647 + 13; 2686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu return val_; 2786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 2886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 2986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu uint32_t val_; 3086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu}; 3186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 3286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescuclass MemCmp16Test : public testing::Test { 3386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu}; 3486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 3586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu// A simple implementation to compare against. 3686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu// Note: this version is equivalent to the generic one used when no optimized version is available. 3786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescuint32_t memcmp16_compare(const uint16_t* s0, const uint16_t* s1, size_t count) { 3886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu for (size_t i = 0; i < count; i++) { 3986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (s0[i] != s1[i]) { 4086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu return static_cast<int32_t>(s0[i]) - static_cast<int32_t>(s1[i]); 4186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 4286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 4386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu return 0; 4486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu} 4586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 4686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescustatic constexpr size_t kMemCmp16Rounds = 100000; 4786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 4886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescustatic void CheckSeparate(size_t max_length, size_t min_length) { 4986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu RandGen r(0x1234); 5086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu size_t range_of_tests = 7; // All four (weighted) tests active in the beginning. 5186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 5286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu for (size_t round = 0; round < kMemCmp16Rounds; ++round) { 5386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu size_t type = r.next() % range_of_tests; 5486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu size_t count1, count2; 5586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu uint16_t *s1, *s2; // Use raw pointers to simplify using clobbered addresses 5686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 5786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu switch (type) { 5886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu case 0: // random, non-zero lengths of both strings 5986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu case 1: 6086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu case 2: 6186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu case 3: 6286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count1 = (r.next() % max_length) + min_length; 6386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count2 = (r.next() % max_length) + min_length; 6486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu break; 6586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 6686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu case 4: // random non-zero length of first, second is zero 6786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count1 = (r.next() % max_length) + min_length; 6886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count2 = 0U; 6986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu break; 7086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 7186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu case 5: // random non-zero length of second, first is zero 7286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count1 = 0U; 7386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count2 = (r.next() % max_length) + min_length; 7486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu break; 7586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 7686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu case 6: // both zero-length 7786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count1 = 0U; 7886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu count2 = 0U; 7986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu range_of_tests = 6; // Don't do zero-zero again. 8086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu break; 8186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 8286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu default: 8386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu ASSERT_TRUE(false) << "Should not get here."; 8486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu continue; 8586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 8686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 8786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (count1 > 0U) { 8886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s1 = new uint16_t[count1]; 8986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } else { 9086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu // Leave a random pointer, should not be touched. 9186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s1 = reinterpret_cast<uint16_t*>(0xebad1001); 9286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 9386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 9486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (count2 > 0U) { 9586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s2 = new uint16_t[count2]; 9686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } else { 9786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu // Leave a random pointer, should not be touched. 9886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s2 = reinterpret_cast<uint16_t*>(0xebad2002); 9986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 10086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 10186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu size_t min = count1 < count2 ? count1 : count2; 10286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu bool fill_same = r.next() % 1 == 1; 10386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 10486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (fill_same) { 10586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu for (size_t i = 0; i < min; ++i) { 10686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF); 10786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s2[i] = s1[i]; 10886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 10986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu for (size_t i = min; i < count1; ++i) { 11086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF); 11186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 11286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu for (size_t i = min; i < count2; ++i) { 11386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s2[i] = static_cast<uint16_t>(r.next() & 0xFFFF); 11486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 11586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } else { 11686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu for (size_t i = 0; i < count1; ++i) { 11786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s1[i] = static_cast<uint16_t>(r.next() & 0xFFFF); 11886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 11986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu for (size_t i = 0; i < count2; ++i) { 12086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s2[i] = static_cast<uint16_t>(r.next() & 0xFFFF); 12186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 12286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 12386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 12486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu uint16_t* s1_pot_unaligned = s1; 12586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu uint16_t* s2_pot_unaligned = s2; 12686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu size_t c1_mod = count1; 12786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu size_t c2_mod = count2; 12886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 12986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (!fill_same) { // Don't waste a good "long" test. 13086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (count1 > 1 && r.next() % 10 == 0) { 13186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu c1_mod--; 13286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s1_pot_unaligned++; 13386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 13486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (count2 > 1 && r.next() % 10 == 0) { 13586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu c2_mod--; 13686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu s2_pot_unaligned++; 13786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 13886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 13986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu size_t mod_min = c1_mod < c2_mod ? c1_mod : c2_mod; 14086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 14186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu int32_t expected = memcmp16_compare(s1_pot_unaligned, s2_pot_unaligned, mod_min); 14229b3841ad8c1c18ee7ddd2d8cab85806b3d62eaaAndreas Gampe int32_t computed = art::testing::MemCmp16Testing(s1_pot_unaligned, s2_pot_unaligned, mod_min); 14386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 14486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu ASSERT_EQ(expected, computed) << "Run " << round << ", c1=" << count1 << " c2=" << count2; 14586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 14686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (count1 > 0U) { 14772133adde48a7d48afc6becb505a26431cc28e74Evgenii Stepanov delete[] s1; 14886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 14986797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu if (count2 > 0U) { 15072133adde48a7d48afc6becb505a26431cc28e74Evgenii Stepanov delete[] s2; 15186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 15286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu } 15386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu} 15486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 15586797a791d692f81def5c1b5f0918992c49ed122Serban ConstantinescuTEST_F(MemCmp16Test, RandomSeparateShort) { 15686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu CheckSeparate(5U, 1U); 15786797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu} 15886797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 15986797a791d692f81def5c1b5f0918992c49ed122Serban ConstantinescuTEST_F(MemCmp16Test, RandomSeparateLong) { 16086797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu CheckSeparate(64U, 32U); 16186797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu} 16286797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu 16386797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu// TODO: What's a good test for overlapping memory. Is it important? 16486797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu// TEST_F(MemCmp16Test, RandomOverlay) { 16586797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu// 16686797a791d692f81def5c1b5f0918992c49ed122Serban Constantinescu// } 167