Merge "ARM: Improve String.equals() intrinsic for const strings."
diff --git a/compiler/optimizing/intrinsics_arm64.cc b/compiler/optimizing/intrinsics_arm64.cc
index 3fdad8c..1ed1b75 100644
--- a/compiler/optimizing/intrinsics_arm64.cc
+++ b/compiler/optimizing/intrinsics_arm64.cc
@@ -1633,12 +1633,13 @@
}
// Assertions that must hold in order to compare strings 8 bytes at a time.
+ // Ok to do this because strings are zero-padded to kObjectAlignment.
DCHECK_ALIGNED(value_offset, 8);
static_assert(IsAligned<8>(kObjectAlignment), "String of odd length is not zero padded");
if (const_string != nullptr &&
- const_string_length < (is_compressed ? kShortConstStringEqualsCutoffInBytes
- : kShortConstStringEqualsCutoffInBytes / 2u)) {
+ const_string_length <= (is_compressed ? kShortConstStringEqualsCutoffInBytes
+ : kShortConstStringEqualsCutoffInBytes / 2u)) {
// Load and compare the contents. Though we know the contents of the short const string
// at compile time, materializing constants may be more code than loading from memory.
int32_t offset = value_offset;
@@ -1646,7 +1647,7 @@
RoundUp(is_compressed ? const_string_length : const_string_length * 2u, 8u);
temp = temp.X();
temp1 = temp1.X();
- while (remaining_bytes > 8u) {
+ while (remaining_bytes > sizeof(uint64_t)) {
Register temp2 = XRegisterFrom(locations->GetTemp(0));
__ Ldp(temp, temp1, MemOperand(str.X(), offset));
__ Ldp(temp2, out, MemOperand(arg.X(), offset));
@@ -1682,7 +1683,6 @@
temp1 = temp1.X();
Register temp2 = XRegisterFrom(locations->GetTemp(0));
// Loop to compare strings 8 bytes at a time starting at the front of the string.
- // Ok to do this because strings are zero-padded to kObjectAlignment.
__ Bind(&loop);
__ Ldr(out, MemOperand(str.X(), temp1));
__ Ldr(temp2, MemOperand(arg.X(), temp1));
diff --git a/compiler/optimizing/intrinsics_arm_vixl.cc b/compiler/optimizing/intrinsics_arm_vixl.cc
index 82a97bc..76c1410 100644
--- a/compiler/optimizing/intrinsics_arm_vixl.cc
+++ b/compiler/optimizing/intrinsics_arm_vixl.cc
@@ -1721,6 +1721,22 @@
}
}
+// The cut off for unrolling the loop in String.equals() intrinsic for const strings.
+// The normal loop plus the pre-header is 9 instructions (18-26 bytes) without string compression
+// and 12 instructions (24-32 bytes) with string compression. We can compare up to 4 bytes in 4
+// instructions (LDR+LDR+CMP+BNE) and up to 8 bytes in 6 instructions (LDRD+LDRD+CMP+BNE+CMP+BNE).
+// Allow up to 12 instructions (32 bytes) for the unrolled loop.
+constexpr size_t kShortConstStringEqualsCutoffInBytes = 16;
+
+static const char* GetConstString(HInstruction* candidate, uint32_t* utf16_length) {
+ if (candidate->IsLoadString()) {
+ HLoadString* load_string = candidate->AsLoadString();
+ const DexFile& dex_file = load_string->GetDexFile();
+ return dex_file.StringDataAndUtf16LengthByIdx(load_string->GetStringIndex(), utf16_length);
+ }
+ return nullptr;
+}
+
void IntrinsicLocationsBuilderARMVIXL::VisitStringEquals(HInvoke* invoke) {
LocationSummary* locations = new (arena_) LocationSummary(invoke,
LocationSummary::kNoCall,
@@ -1728,12 +1744,29 @@
InvokeRuntimeCallingConventionARMVIXL calling_convention;
locations->SetInAt(0, Location::RequiresRegister());
locations->SetInAt(1, Location::RequiresRegister());
+
// Temporary registers to store lengths of strings and for calculations.
// Using instruction cbz requires a low register, so explicitly set a temp to be R0.
locations->AddTemp(LocationFrom(r0));
- locations->AddTemp(Location::RequiresRegister());
- locations->AddTemp(Location::RequiresRegister());
+ // For the generic implementation and for long const strings we need an extra temporary.
+ // We do not need it for short const strings, up to 4 bytes, see code generation below.
+ uint32_t const_string_length = 0u;
+ const char* const_string = GetConstString(invoke->InputAt(0), &const_string_length);
+ if (const_string == nullptr) {
+ const_string = GetConstString(invoke->InputAt(1), &const_string_length);
+ }
+ bool is_compressed =
+ mirror::kUseStringCompression &&
+ const_string != nullptr &&
+ mirror::String::DexFileStringAllASCII(const_string, const_string_length);
+ if (const_string == nullptr || const_string_length > (is_compressed ? 4u : 2u)) {
+ locations->AddTemp(Location::RequiresRegister());
+ }
+
+ // TODO: If the String.equals() is used only for an immediately following HIf, we can
+ // mark it as emitted-at-use-site and emit branches directly to the appropriate blocks.
+ // Then we shall need an extra temporary register instead of the output register.
locations->SetOut(Location::RequiresRegister());
}
@@ -1746,8 +1779,6 @@
vixl32::Register out = OutputRegister(invoke);
vixl32::Register temp = RegisterFrom(locations->GetTemp(0));
- vixl32::Register temp1 = RegisterFrom(locations->GetTemp(1));
- vixl32::Register temp2 = RegisterFrom(locations->GetTemp(2));
vixl32::Label loop;
vixl32::Label end;
@@ -1779,53 +1810,110 @@
// Receiver must be a string object, so its class field is equal to all strings' class fields.
// If the argument is a string object, its class field must be equal to receiver's class field.
__ Ldr(temp, MemOperand(str, class_offset));
- __ Ldr(temp1, MemOperand(arg, class_offset));
- __ Cmp(temp, temp1);
+ __ Ldr(out, MemOperand(arg, class_offset));
+ __ Cmp(temp, out);
__ B(ne, &return_false, /* far_target */ false);
}
- // Load `count` fields of this and argument strings.
- __ Ldr(temp, MemOperand(str, count_offset));
- __ Ldr(temp1, MemOperand(arg, count_offset));
- // Check if `count` fields are equal, return false if they're not.
- // Also compares the compression style, if differs return false.
- __ Cmp(temp, temp1);
- __ B(ne, &return_false, /* far_target */ false);
- // Return true if both strings are empty. Even with string compression `count == 0` means empty.
- static_assert(static_cast<uint32_t>(mirror::StringCompressionFlag::kCompressed) == 0u,
- "Expecting 0=compressed, 1=uncompressed");
- __ CompareAndBranchIfZero(temp, &return_true, /* far_target */ false);
+ // Check if one of the inputs is a const string. Do not special-case both strings
+ // being const, such cases should be handled by constant folding if needed.
+ uint32_t const_string_length = 0u;
+ const char* const_string = GetConstString(invoke->InputAt(0), &const_string_length);
+ if (const_string == nullptr) {
+ const_string = GetConstString(invoke->InputAt(1), &const_string_length);
+ if (const_string != nullptr) {
+ std::swap(str, arg); // Make sure the const string is in `str`.
+ }
+ }
+ bool is_compressed =
+ mirror::kUseStringCompression &&
+ const_string != nullptr &&
+ mirror::String::DexFileStringAllASCII(const_string, const_string_length);
+
+ if (const_string != nullptr) {
+ // Load `count` field of the argument string and check if it matches the const string.
+ // Also compares the compression style, if differs return false.
+ __ Ldr(temp, MemOperand(arg, count_offset));
+ __ Cmp(temp, Operand(mirror::String::GetFlaggedCount(const_string_length, is_compressed)));
+ __ B(ne, &return_false, /* far_target */ false);
+ } else {
+ // Load `count` fields of this and argument strings.
+ __ Ldr(temp, MemOperand(str, count_offset));
+ __ Ldr(out, MemOperand(arg, count_offset));
+ // Check if `count` fields are equal, return false if they're not.
+ // Also compares the compression style, if differs return false.
+ __ Cmp(temp, out);
+ __ B(ne, &return_false, /* far_target */ false);
+ }
// Assertions that must hold in order to compare strings 4 bytes at a time.
+ // Ok to do this because strings are zero-padded to kObjectAlignment.
DCHECK_ALIGNED(value_offset, 4);
static_assert(IsAligned<4>(kObjectAlignment), "String data must be aligned for fast compare.");
- if (mirror::kUseStringCompression) {
- // For string compression, calculate the number of bytes to compare (not chars).
- // This could in theory exceed INT32_MAX, so treat temp as unsigned.
- __ Lsrs(temp, temp, 1u); // Extract length and check compression flag.
- ExactAssemblyScope aas(assembler->GetVIXLAssembler(),
- 2 * kMaxInstructionSizeInBytes,
- CodeBufferCheckScope::kMaximumSize);
- __ it(cs); // If uncompressed,
- __ add(cs, temp, temp, temp); // double the byte count.
+ if (const_string != nullptr &&
+ const_string_length <= (is_compressed ? kShortConstStringEqualsCutoffInBytes
+ : kShortConstStringEqualsCutoffInBytes / 2u)) {
+ // Load and compare the contents. Though we know the contents of the short const string
+ // at compile time, materializing constants may be more code than loading from memory.
+ int32_t offset = value_offset;
+ size_t remaining_bytes =
+ RoundUp(is_compressed ? const_string_length : const_string_length * 2u, 4u);
+ while (remaining_bytes > sizeof(uint32_t)) {
+ vixl32::Register temp1 = RegisterFrom(locations->GetTemp(1));
+ UseScratchRegisterScope scratch_scope(assembler->GetVIXLAssembler());
+ vixl32::Register temp2 = scratch_scope.Acquire();
+ __ Ldrd(temp, temp1, MemOperand(str, offset));
+ __ Ldrd(temp2, out, MemOperand(arg, offset));
+ __ Cmp(temp, temp2);
+ __ B(ne, &return_false, /* far_label */ false);
+ __ Cmp(temp1, out);
+ __ B(ne, &return_false, /* far_label */ false);
+ offset += 2u * sizeof(uint32_t);
+ remaining_bytes -= 2u * sizeof(uint32_t);
+ }
+ if (remaining_bytes != 0u) {
+ __ Ldr(temp, MemOperand(str, offset));
+ __ Ldr(out, MemOperand(arg, offset));
+ __ Cmp(temp, out);
+ __ B(ne, &return_false, /* far_label */ false);
+ }
+ } else {
+ // Return true if both strings are empty. Even with string compression `count == 0` means empty.
+ static_assert(static_cast<uint32_t>(mirror::StringCompressionFlag::kCompressed) == 0u,
+ "Expecting 0=compressed, 1=uncompressed");
+ __ CompareAndBranchIfZero(temp, &return_true, /* far_target */ false);
+
+ if (mirror::kUseStringCompression) {
+ // For string compression, calculate the number of bytes to compare (not chars).
+ // This could in theory exceed INT32_MAX, so treat temp as unsigned.
+ __ Lsrs(temp, temp, 1u); // Extract length and check compression flag.
+ ExactAssemblyScope aas(assembler->GetVIXLAssembler(),
+ 2 * kMaxInstructionSizeInBytes,
+ CodeBufferCheckScope::kMaximumSize);
+ __ it(cs); // If uncompressed,
+ __ add(cs, temp, temp, temp); // double the byte count.
+ }
+
+ vixl32::Register temp1 = RegisterFrom(locations->GetTemp(1));
+ UseScratchRegisterScope scratch_scope(assembler->GetVIXLAssembler());
+ vixl32::Register temp2 = scratch_scope.Acquire();
+
+ // Store offset of string value in preparation for comparison loop.
+ __ Mov(temp1, value_offset);
+
+ // Loop to compare strings 4 bytes at a time starting at the front of the string.
+ __ Bind(&loop);
+ __ Ldr(out, MemOperand(str, temp1));
+ __ Ldr(temp2, MemOperand(arg, temp1));
+ __ Add(temp1, temp1, Operand::From(sizeof(uint32_t)));
+ __ Cmp(out, temp2);
+ __ B(ne, &return_false, /* far_target */ false);
+ // With string compression, we have compared 4 bytes, otherwise 2 chars.
+ __ Subs(temp, temp, mirror::kUseStringCompression ? 4 : 2);
+ __ B(hi, &loop, /* far_target */ false);
}
- // Store offset of string value in preparation for comparison loop.
- __ Mov(temp1, value_offset);
-
- // Loop to compare strings 4 bytes at a time starting at the front of the string.
- // Ok to do this because strings are zero-padded to kObjectAlignment.
- __ Bind(&loop);
- __ Ldr(out, MemOperand(str, temp1));
- __ Ldr(temp2, MemOperand(arg, temp1));
- __ Add(temp1, temp1, Operand::From(sizeof(uint32_t)));
- __ Cmp(out, temp2);
- __ B(ne, &return_false, /* far_target */ false);
- // With string compression, we have compared 4 bytes, otherwise 2 chars.
- __ Subs(temp, temp, mirror::kUseStringCompression ? 4 : 2);
- __ B(hi, &loop, /* far_target */ false);
-
// Return true and exit the function.
// If loop does not result in returning false, we return true.
__ Bind(&return_true);
diff --git a/test/021-string2/src/Main.java b/test/021-string2/src/Main.java
index 3b81d8e..c713aa4 100644
--- a/test/021-string2/src/Main.java
+++ b/test/021-string2/src/Main.java
@@ -556,12 +556,24 @@
Assert.assertTrue($noinline$equalsConstString0(""));
Assert.assertFalse($noinline$equalsConstString0("1"));
+ Assert.assertTrue($noinline$equalsConstString3("012"));
+ Assert.assertFalse($noinline$equalsConstString3("01"));
+ Assert.assertFalse($noinline$equalsConstString3("0123"));
+ Assert.assertFalse($noinline$equalsConstString3("01x"));
+ Assert.assertFalse($noinline$equalsConstString3("01\u0440"));
+
Assert.assertTrue($noinline$equalsConstString7("0123456"));
Assert.assertFalse($noinline$equalsConstString7("012345"));
Assert.assertFalse($noinline$equalsConstString7("01234567"));
Assert.assertFalse($noinline$equalsConstString7("012345x"));
Assert.assertFalse($noinline$equalsConstString7("012345\u0440"));
+ Assert.assertTrue($noinline$equalsConstString12("012345678901"));
+ Assert.assertFalse($noinline$equalsConstString12("01234567890"));
+ Assert.assertFalse($noinline$equalsConstString12("0123456789012"));
+ Assert.assertFalse($noinline$equalsConstString12("01234567890x"));
+ Assert.assertFalse($noinline$equalsConstString12("01234567890\u0440"));
+
Assert.assertTrue($noinline$equalsConstString14("01234567890123"));
Assert.assertFalse($noinline$equalsConstString14("0123456789012"));
Assert.assertFalse($noinline$equalsConstString14("012345678901234"));
@@ -587,12 +599,24 @@
Assert.assertFalse(
$noinline$equalsConstString35("0123456789012345678901234567890123\u0440"));
+ Assert.assertTrue($noinline$equalsConstNonAsciiString3("\u044012"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString3("\u04401"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString3("\u0440123"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString3("\u04401x"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString3("012"));
+
Assert.assertTrue($noinline$equalsConstNonAsciiString7("\u0440123456"));
Assert.assertFalse($noinline$equalsConstNonAsciiString7("\u044012345"));
Assert.assertFalse($noinline$equalsConstNonAsciiString7("\u04401234567"));
Assert.assertFalse($noinline$equalsConstNonAsciiString7("\u044012345x"));
Assert.assertFalse($noinline$equalsConstNonAsciiString7("0123456"));
+ Assert.assertTrue($noinline$equalsConstNonAsciiString12("\u044012345678901"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString12("\u04401234567890"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString12("\u0440123456789012"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString12("\u04401234567890x"));
+ Assert.assertFalse($noinline$equalsConstNonAsciiString12("012345678901"));
+
Assert.assertTrue($noinline$equalsConstNonAsciiString14("\u04401234567890123"));
Assert.assertFalse($noinline$equalsConstNonAsciiString14("\u0440123456789012"));
Assert.assertFalse($noinline$equalsConstNonAsciiString14("\u044012345678901234"));
@@ -631,12 +655,24 @@
Assert.assertTrue($noinline$constString0Equals(""));
Assert.assertFalse($noinline$constString0Equals("1"));
+ Assert.assertTrue($noinline$constString3Equals("012"));
+ Assert.assertFalse($noinline$constString3Equals("01"));
+ Assert.assertFalse($noinline$constString3Equals("0123"));
+ Assert.assertFalse($noinline$constString3Equals("01x"));
+ Assert.assertFalse($noinline$constString3Equals("01\u0440"));
+
Assert.assertTrue($noinline$constString7Equals("0123456"));
Assert.assertFalse($noinline$constString7Equals("012345"));
Assert.assertFalse($noinline$constString7Equals("01234567"));
Assert.assertFalse($noinline$constString7Equals("012345x"));
Assert.assertFalse($noinline$constString7Equals("012345\u0440"));
+ Assert.assertTrue($noinline$constString12Equals("012345678901"));
+ Assert.assertFalse($noinline$constString12Equals("01234567890"));
+ Assert.assertFalse($noinline$constString12Equals("0123456789012"));
+ Assert.assertFalse($noinline$constString12Equals("01234567890x"));
+ Assert.assertFalse($noinline$constString12Equals("01234567890\u0440"));
+
Assert.assertTrue($noinline$constString14Equals("01234567890123"));
Assert.assertFalse($noinline$constString14Equals("0123456789012"));
Assert.assertFalse($noinline$constString14Equals("012345678901234"));
@@ -662,12 +698,24 @@
Assert.assertFalse(
$noinline$constString35Equals("0123456789012345678901234567890123\u0040"));
+ Assert.assertTrue($noinline$constNonAsciiString3Equals("\u044012"));
+ Assert.assertFalse($noinline$constNonAsciiString3Equals("\u04401"));
+ Assert.assertFalse($noinline$constNonAsciiString3Equals("\u0440123"));
+ Assert.assertFalse($noinline$constNonAsciiString3Equals("\u04401x"));
+ Assert.assertFalse($noinline$constNonAsciiString3Equals("0123456"));
+
Assert.assertTrue($noinline$constNonAsciiString7Equals("\u0440123456"));
Assert.assertFalse($noinline$constNonAsciiString7Equals("\u044012345"));
Assert.assertFalse($noinline$constNonAsciiString7Equals("\u04401234567"));
Assert.assertFalse($noinline$constNonAsciiString7Equals("\u044012345x"));
Assert.assertFalse($noinline$constNonAsciiString7Equals("0123456"));
+ Assert.assertTrue($noinline$constNonAsciiString12Equals("\u044012345678901"));
+ Assert.assertFalse($noinline$constNonAsciiString12Equals("\u04401234567890"));
+ Assert.assertFalse($noinline$constNonAsciiString12Equals("\u0440123456789012"));
+ Assert.assertFalse($noinline$constNonAsciiString12Equals("\u04401234567890x"));
+ Assert.assertFalse($noinline$constNonAsciiString12Equals("012345678901"));
+
Assert.assertTrue($noinline$constNonAsciiString14Equals("\u04401234567890123"));
Assert.assertFalse($noinline$constNonAsciiString14Equals("\u0440123456789012"));
Assert.assertFalse($noinline$constNonAsciiString14Equals("\u044012345678901234"));
@@ -708,134 +756,138 @@
}
public static boolean $noinline$equalsConstString0(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("");
}
+ public static boolean $noinline$equalsConstString3(String s) {
+ return s.equals("012");
+ }
+
public static boolean $noinline$equalsConstString7(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("0123456");
}
+ public static boolean $noinline$equalsConstString12(String s) {
+ return s.equals("012345678901");
+ }
+
public static boolean $noinline$equalsConstString14(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("01234567890123");
}
public static boolean $noinline$equalsConstString24(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("012345678901234567890123");
}
public static boolean $noinline$equalsConstString29(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("01234567890123456789012345678");
}
public static boolean $noinline$equalsConstString35(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("01234567890123456789012345678901234");
}
+ public static boolean $noinline$equalsConstNonAsciiString3(String s) {
+ return s.equals("\u044012");
+ }
+
public static boolean $noinline$equalsConstNonAsciiString7(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("\u0440123456");
}
+ public static boolean $noinline$equalsConstNonAsciiString12(String s) {
+ return s.equals("\u044012345678901");
+ }
+
public static boolean $noinline$equalsConstNonAsciiString14(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("\u04401234567890123");
}
public static boolean $noinline$equalsConstNonAsciiString24(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("\u044012345678901234567890123");
}
public static boolean $noinline$equalsConstNonAsciiString29(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("\u04401234567890123456789012345678");
}
public static boolean $noinline$equalsConstNonAsciiString35(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("\u04401234567890123456789012345678901234");
}
public static boolean $noinline$constString0Equals(String s) {
- if (doThrow) { throw new Error(); }
return s.equals("");
}
+ public static boolean $noinline$constString3Equals(String s) {
+ return "012".equals(s);
+ }
+
public static boolean $noinline$constString7Equals(String s) {
- if (doThrow) { throw new Error(); }
return "0123456".equals(s);
}
+ public static boolean $noinline$constString12Equals(String s) {
+ return "012345678901".equals(s);
+ }
+
public static boolean $noinline$constString14Equals(String s) {
- if (doThrow) { throw new Error(); }
return "01234567890123".equals(s);
}
public static boolean $noinline$constString24Equals(String s) {
- if (doThrow) { throw new Error(); }
return "012345678901234567890123".equals(s);
}
public static boolean $noinline$constString29Equals(String s) {
- if (doThrow) { throw new Error(); }
return "01234567890123456789012345678".equals(s);
}
public static boolean $noinline$constString35Equals(String s) {
- if (doThrow) { throw new Error(); }
return "01234567890123456789012345678901234".equals(s);
}
+ public static boolean $noinline$constNonAsciiString3Equals(String s) {
+ return "\u044012".equals(s);
+ }
+
public static boolean $noinline$constNonAsciiString7Equals(String s) {
- if (doThrow) { throw new Error(); }
return "\u0440123456".equals(s);
}
+ public static boolean $noinline$constNonAsciiString12Equals(String s) {
+ return "\u044012345678901".equals(s);
+ }
+
public static boolean $noinline$constNonAsciiString14Equals(String s) {
- if (doThrow) { throw new Error(); }
return "\u04401234567890123".equals(s);
}
public static boolean $noinline$constNonAsciiString24Equals(String s) {
- if (doThrow) { throw new Error(); }
return "\u044012345678901234567890123".equals(s);
}
public static boolean $noinline$constNonAsciiString29Equals(String s) {
- if (doThrow) { throw new Error(); }
return "\u04401234567890123456789012345678".equals(s);
}
public static boolean $noinline$constNonAsciiString35Equals(String s) {
- if (doThrow) { throw new Error(); }
return "\u04401234567890123456789012345678901234".equals(s);
}
public static int $noinline$compareTo(String lhs, String rhs) {
- if (doThrow) { throw new Error(); }
return lhs.compareTo(rhs);
}
public static boolean $noinline$equals(String lhs, String rhs) {
- if (doThrow) { throw new Error(); }
return lhs.equals(rhs);
}
public static int $noinline$indexOf(String lhs, int ch) {
- if (doThrow) { throw new Error(); }
return lhs.indexOf(ch);
}
public static int $noinline$indexOf(String lhs, int ch, int fromIndex) {
- if (doThrow) { throw new Error(); }
return lhs.indexOf(ch, fromIndex);
}
-
- public static boolean doThrow = false;
}